CScriptWitness stores a witness stack as a std::vector<std::vector<unsigned char>>, which costs a 24-byte vector object and an allocation for every element. This makes it possible to construct transactions that take a large amount of memory after deserialization, while becoming very slow to deserialize.
This PR stores the stack as its serialization in a single allocation (or none if the stack is empty), with a small header holding its size and the offset of the last element. Witnesses can no longer be modified in place, only allowing replacing them entirely. Access to the individual witness stack elements is done by on-the-fly deserialization instead. CScriptWitness shrinks from 24 to 8 bytes, and CTxIn from 112 to 96 bytes.
Later commits also introduce stricter checking during deserialization, rejecting the following before fully deserializing:
- Transactions with more inputs/outputs than are possible in a valid transaction.
- Transactions with 0 inputs or 0 outputs (applied in P2P, but not RPC etc. for backward compatibility).
- Transactions/blocks that exceed the 4M weight limit (also only applied in P2P).
The result is a significant reduction in the worst-case time and memory allocations needed for deserialization, both in valid and invalid transactions. With it, the worst-case memory of a valid deserialized block drops from 106.8 MiB to 6.0 MiB. Memory usage during deserialization can temporarily be higher: up to 7.8 MiB for valid blocks, and up to 13.4 MiB for invalid blocks, which can combine a few temporary vector allocations of up to 5 MB each.
Deserialization time and memory of the deserialized block, master → PR. Runtimes are medians in milliseconds. Memory usage is in MiB, and ✕ means rejected at deserialization time. Peak memory refers to the memory during deserialization itself, not persisted in the deserialized CBlock object. Numbers over 50 ms, 20 MiB usage, or 100 MiB peak are in bold.
| block | gcc | clang | mem | peak mem | |---|--:|--:|--:|--:| | Valid blocks | | 1 tx, max 1-byte wit elems | 99.1 → 16.0 | 111.4 → 21.9 | 106.8 → 3.8 | 145.9 → 7.8 | | 1 tx, max empty wit elems | 279.2 → 18.7 | 293.7 → 25.1 | 91.5 → 3.8 | 182.2 → 7.8 | | max txs, 1 txin, 1 txout, 1-item wit | 12.33 → 13.39 | 15.00 → 15.43 | 6.7 → 6.0 | 6.7 → 6.0 | | max txs, 1 txin and 1 txout | 6.43 → 7.04 | 7.87 → 8.30 | 5.8 → 5.6 | 5.8 → 5.6 | | 1 tx, max txins, 1-elem wit | 4.53 → 4.68 | 5.04 → 5.37 | 4.0 → 2.9 | 4.0 → 2.9 | | mainnet block 969729 | 5.30 → 5.47 | 5.97 → 6.20 | 3.5 → 2.9 | 3.5 → 2.9 | | Invalid blocks | | 400k txs, many wit elems, truncated | 84.8 → 16.1 | 95.6 → 21.8 | ✕ → ✕ | 150.7 → 12.6 | | 400k txs, big wit+scriptsig, truncated | 84.0 → 16.1 | 96.0 → 21.7 | ✕ → ✕ | 150.7 → 13.4 | | 1 tx, 2M 1-byte wit elems | 98.0 → 10.6 | 109.9 → 16.2 | 106.8 → ✕ | 145.9 → 7.8 | | 1 tx, 4M empty wit elems | 271.0 → 13.4 | 288.9 → 19.6 | 91.6 → ✕ | 182.2 → 7.8 | | max empty txs | 101.0 → 0.006 | 139.0 → 0.008 | 67.1 → ✕ | 67.1 → 4.8 | | max txs, 1 txin, 1 txout | 27.6 → 7.3 | 34.5 → 8.5 | 23.4 → ✕ | 23.4 → 6.4 |
So in addition to improving worst cases very significantly, it also provides modest memory usage improvements to the common case. This translates to mildly increasing the effective capacity of memory-bounded data structures that store transactions, like the mempool.
Some notable changes:
- By implementing some checks (for inherently consensus-invalid things) in the deserialization logic, behavior may change. In particular, deserialization errors in P2P cause messages to be dropped/ignored, rather than triggering validation or net processing logic (which may include disconnections and/or inserting into reject filters).
- The rejection of transactions with too many inputs or outputs applies everywhere, including in RPC. That's hopefully a desirable change, but a change in behavior still.
- Random access to the witness stack elements becomes $\mathcal{O}(n)$. This is not a problem for any validation logic, but may be relevant for the libbitcoinkernel API which exposes an individual element accessor.
Issue reported by furszy and 0xB10C.
There are a few possible follow-ups:
- Enforce the 400k WU policy limit during transaction deserialization when active (instead of the 4M WU consensus limit).
- Extend this approach to entire
CTransaction, allowing all transaction data to be stored packed together in a few allocations (rather than one per input, one per output, one per witness) plus some index structure to access it efficiently. That's a much bigger change, needing abstractions like #35569, but would reduce the maximum memory usage per WU for valid blocks from around 1.5 bytes/WU to 1.1 bytes/WU (compared to ~28 bytes/WU in master).
