Witness stacks in serialized form (optimization follow-ups) #36918

pull sipa wants to merge 19 commits into bitcoin:master from sipa:202610_witpack changing 66 files +876 −244
  1. sipa commented at 6:27 PM on November 19, 2026: member

    This is a PR showing follow-up optimizations onto #36895. Draft while that PR is not merged.

    Benchmarks for the various commits, in milliseconds, on recent Zen5 machine, gcc 15.3 -O2, median of 11 runs. All measure time from receipt to accept/reject (covering everything from deserialization to validation, if relevant):

    block master #36895 + deser + offset + lazy
    ✅ unknown version, 2.0M × 0–2 B (random) 104 177 71 72 21
    ✅ unknown version, 2.0M × 1 B 128 185 92 91 14
    ✅ unknown version, 1.33M × 2 B 55 98 61 60 12
    ❌ P2WSH mismatch, 2.0M × 1 B 128 163 74 65 65
    ❌ bad commitment, 2.0M × 1 B 101 131 14 14 14
    ❌ P2WSH stack too large, 4.0M × 0 B 346 313 72 58 59
    ✅ 5,169 P2WSH × 403 items 31 30 27 21 22
    ✅ 14,690 signed P2WPKH 118 118 117 117 118
    ✅ unknown version, 1 × 4.0 MB 1.6 3.4 3.4 3.4 2.8
  2. script: give CScriptWitness an interface that hides its representation
    Add element access through spans (forward iteration, front(), back(), and
    indexing), conversion to and construction from a vector of elements,
    serialization, and memory usage accounting, so that users no longer need to
    access the stack vector directly. This prepares for a future commit which
    will replace the representation with a more compact & efficient one.
    
    The stack vector itself stays public until the next commits have converted
    its users.
    18403ab754
  3. test: check CScriptWitness against the vector of vectors it represents
    Add a unit test and a fuzz test that compare CScriptWitness's interface
    (accessors, construction, and serialization) with the
    std::vector<std::vector<unsigned char>> it represents. The unit test
    focuses on element counts and sizes around CompactSize encoding
    boundaries.
    49c0f21971
  4. scripted-diff: use CScriptWitness's size(), empty() and back()
    Convert the uses of CScriptWitness::stack that only need the number of
    elements, whether there are any, or the last element, which the witness
    provides itself. Other uses are converted in the next commits.
    
    -BEGIN VERIFY SCRIPT-
    # Lines that need the stack itself (to compute the size of its
    # serialization without the element count, to pass the last element
    # where a vector is expected, or to index all elements in a loop) are
    # left for the manual changes.
    sed -i -E -e '/GetSizeOfCompactSize|TAPROOT_LEAF_TAPSCRIPT|i < (txin\.)?scriptWitness\.stack/b' \
        -e 's/\.stack\.(size|empty|back)\(\)/.\1()/g' \
        $(git grep -l -E '\.stack\.(size|empty|back)\(\)' -- src ':!src/script/miniscript.*' ':!src/script/script.h')
    -END VERIFY SCRIPT-
    a271d6b773
  5. scripted-diff: read and compare CScriptWitness through its interface
    Convert the uses of CScriptWitness::stack that read an element by index,
    bind a const reference to the stack, or compare two stacks, and the
    uses of IsNull().
    
    -BEGIN VERIFY SCRIPT-
    FILES=$(git grep -l -E '\.stack\b' -- src ':!src/script/miniscript.*' ':!src/script/script.h')
    
    # Reading an element by index: the witness has operator[] itself. Writes
    # to elements, and loops indexing all elements (which can be quadratic
    # with indexing that is not constant-time), are left for the manual
    # changes.
    sed -i -E -e '/MAX_STANDARD_P2WSH_STACK_ITEM_SIZE|HexStr\((txin\.)?scriptWitness\.stack\[|\.stack\[[^]]*\]( =|\.resize)|^\s*\+\+/b' \
        -e 's/\.stack\[/[/g' $FILES
    
    # Const references to the stack: refer to the witness itself, which
    # provides the same read-only accessors.
    sed -i -E 's/^(\s*const auto& \w+( = |\{).*)\.stack(\}?;)$/\1\3/' $FILES
    
    # Comparisons of two stacks: compare the witnesses, which are equal
    # exactly when their stacks are.
    sed -i -E '/\.stack [!=]= /s/\.stack\b//g' $FILES
    
    # IsNull(): use empty(), which the witness provides along with size()
    # and its other container-like accessors.
    sed -i -E -e 's/(scriptWitness|final_script_witness)\.IsNull\(\)/\1.empty()/g' \
        -e 's/witness->IsNull\(\)/witness->empty()/g' \
        $(git grep -l -E '(scriptWitness|final_script_witness)\.IsNull\(\)|witness->IsNull\(\)' -- src)
    -END VERIFY SCRIPT-
    9a7fdee51d
  6. scripted-diff: serialize CScriptWitness rather than its stack
    Convert the uses of CScriptWitness::stack that serialize or deserialize
    it, or compute the size of its serialization. The witness itself has the
    same serialization as its stack.
    
    -BEGIN VERIFY SCRIPT-
    sed -i -E -e 's/ (>>|<<) ([][A-Za-z0-9_.]+)\.stack( <<|;)/ \1 \2\3/' \
        -e 's/(SerializeToVector|UnserializeFromVector)\(s, (\w+)\.stack\)/\1(s, \2)/' \
        -e 's/::GetSerializeSize\(([][A-Za-z0-9_.]+)\.stack\)/::GetSerializeSize(\1)/' \
        $(git grep -l -E '\.stack\b' -- src ':!src/script/miniscript.*' ':!src/script/script.h')
    -END VERIFY SCRIPT-
    940d5dc167
  7. scripted-diff: replace witnesses as a whole instead of their stack
    Convert the uses of CScriptWitness::stack (and SetNull()) that clear the
    stack, assign a new one, or push a single element onto an empty one, to
    assigning a new witness. The remaining uses are converted manually in
    the next commits.
    
    -BEGIN VERIFY SCRIPT-
    FILES=$(git grep -l -E '\.stack\b|(scriptWitness|final_script_witness)\.SetNull\(\)' -- src ':!src/script/miniscript.*' ':!src/script/script.h')
    
    # Clearing the stack (SetNull(), clear() or resize(0)): assign an empty
    # witness. A clear() followed by pushing elements in a loop is left for
    # the manual changes.
    sed -i -E -e '/txin\.scriptWitness\.stack\.clear/b' \
        -e 's/(scriptWitness|final_script_witness)\.SetNull\(\)/\1 = {}/' \
        -e 's/(scriptWitness)\.stack\.(clear\(\)|resize\(0\));$/\1 = {};/' $FILES
    
    # Assigning a vector of elements to the stack: assign a witness
    # constructed from it (moving from the vector is pointless, as the
    # witness is constructed from a const reference). An assignment that
    # spells out the vector's type is left for the manual changes.
    sed -i -E -e '/\.stack = std::vector</b' \
        -e 's/(\w+)\.stack = (std::move\((\w+)\)|(.*));$/\1 = CScriptWitness{\3\4};/' $FILES
    
    # Pushing a single element onto an empty witness (in these benchmarks
    # and tests): assign a witness constructed from that element. The one
    # place that pushes onto a non-empty witness (to make a different
    # witness) is left for the manual changes, as are pushes in loops.
    sed -i -E '/ tx\.vin\[0\]\.scriptWitness\.stack\.push_back\(\{5\}\)|Consume/!s/(\w+)\.stack\.push_back\((.*)\);$/\1 = CScriptWitness{{\2}};/' \
        src/bench/blockencodings.cpp src/bench/mempool_eviction.cpp src/bench/mempool_stress.cpp src/bench/rpc_mempool.cpp \
        src/test/fuzz/connect_block.cpp src/test/fuzz/txdownloadman.cpp src/test/orphanage_tests.cpp src/test/txdownload_tests.cpp \
        src/test/validation_block_tests.cpp
    -END VERIFY SCRIPT-
    3c57d948d5
  8. script: let ExecuteWitnessScript take its initial stack by value
    This lets callers move the stack into it, rather than having it be
    copied from a span. This will be used in a future commit.
    fa5d9491b5
  9. script: build the witness execution stack with ToVectors()
    VerifyWitnessProgram used a span over CScriptWitness::stack, popped the
    elements with other roles (the witness script, the annex, the control
    block, and the leaf script) off that span, and copied the remaining
    elements into the initial execution stack.
    
    Instead, convert the witness to a vector of vectors once, using
    ToVectors(), pop those elements off that vector, and move what remains
    into the execution stack.
    d55243249a
  10. refactor: use CScriptWitness's interface where that needs more than a rename
    Convert the remaining non-test uses of CScriptWitness::stack, which need
    more than a substitution.
    
    This includes the range-based for loops over the stack. Iterating over a
    CScriptWitness yields its elements as spans, by value, where the stack's
    elements were vectors bound by reference. The spans refer to memory
    owned by the witness, so they stay valid as long as it is not modified.
    0a82e05e34
  11. test, bench, fuzz: build witness stacks before constructing a CScriptWitness
    Convert the remaining uses of CScriptWitness::stack in tests, benchmarks,
    and fuzz tests, by constructing witnesses from a separately-built vector
    of elements, rather than modifying the stack in place.
    1a0e6223f5
  12. script: remove CScriptWitness's old interface
    All users of CScriptWitness now go through the interface that hides its
    representation. Make the stack vector private, turning the struct into a
    class, and remove IsNull() and SetNull(), which have no callers left.
    
    The representation itself does not change here.
    e6e42947d0
  13. span: add SameSpan
    Add a helper that tells whether two spans refer to the same range of
    memory, rather than whether their contents are equal. A future commit
    uses it to compare iterators that consist of a span.
    2366d35e07
  14. script: store witness stacks as their serialization
    Replace CScriptWitness's vector of vectors with a single allocation,
    containing the size of the stack's serialization (4 bytes, little
    endian), followed by that serialization. An empty stack uses no
    allocation at all.
    
    This means a witness stack no longer needs one allocation per non-empty
    element plus one for the outer vector, and no longer has a 24-byte
    overhead per element. A block whose witnesses consist of millions of
    tiny elements thus no longer costs tens of bytes of memory and an
    allocation per byte. It also shrinks CScriptWitness from 24 to 8 bytes,
    and thus CTxIn from 112 to 96 bytes. The downside is that indexing
    becomes O(n) in the distance from the bottom of the stack.
    
    This is the simplest implementation of this representation:
    deserialization still goes through a vector of vectors, and elements
    are found by parsing the serialization with SpanReader and
    ReadCompactSize. Both can be made faster in follow-up changes.
    0c981e75a9
  15. bench: add block deserialization benchmarks for synthetic blocks
    Add benchmarks deserializing blocks filled up to the weight limit with
    synthetic transactions of a few shapes that stress different parts of
    deserialization:
    * spends of P2WPKH outputs to P2WPKH outputs (a typical segwit block)
    * the smallest segwit transactions
    * one transaction with as many inputs as fit,
    * one transaction with as many outputs as fit,
    * one transaction whose witness has as many 1-byte elements as fit.
    81c3d99d23
  16. script: deserialize witness stacks directly into their serialization
    Instead of deserializing a witness stack as a vector of vectors and then
    serializing that again, build the serialization directly while reading,
    with the same checks. This makes deserializing a block whose witness
    consists of millions of 1-byte elements about 10x faster.
    
    To support this, add AppendCompactSize to serialize.h, which cheaply
    appends a CompactSize to a byte vector.
    d4f200ef35
  17. script: decode the CompactSizes in witness stacks inline
    Add DecodeCompactSize to serialize.h, which decodes a CompactSize from a
    span without any checks, making it small enough to be inlined.
    
    Use it to find the elements in a CScriptWitness's serialization, which
    is known to be valid as CScriptWitness constructed it. This makes
    iterating over witness stacks 5-7x faster, both for real blocks and for
    blocks whose witnesses consist of millions of 1-byte elements. As a
    bonus, script.h no longer needs streams.h.
    5efcd887c5
  18. script: store the offset of a witness stack's last element
    Add the offset of the last element to the header of CScriptWitness's
    allocation, making back() and accessing the last element by index O(1).
    The last element is used in P2WSH sigop counting, policy checks, and
    BIP352 public key extraction.
    
    This adds 4 bytes to the allocation of every non-empty witness stack,
    but does not change the minimum allocation size of a single-element
    stack, nor the worst-case ratio of memory usage to weight or size.
    07a83d785f
  19. policy: iterate over witness stacks directly in IsWitnessStandard
    Instead of converting a witness stack to a vector of spans for the P2WSH
    and Taproot checks, use its size() and back() (which are constant-time)
    and iterate over its elements directly. This avoids an allocation for
    every witness spend that is checked.
    
    These were the only uses of CScriptWitness::ToSpans(), so remove it.
    c462cc5430
  20. script: only convert the witness to vectors when it is used
    VerifyWitnessProgram converted the whole witness to a vector of vectors
    before looking at the witness program. That is wasted work when the
    rules for the program do not use the witness: unknown witness versions,
    v0 programs of an unknown length, pay-to-anchor, and taproot when
    SCRIPT_VERIFY_TAPROOT is not set. Such a witness is only limited by the
    block weight, so it can consist of millions of elements.
    
    Instead, convert inside the P2WSH and taproot branches, and for P2WPKH
    only after checking that the witness has exactly 2 elements.
    ced8967731
  21. DrahtBot commented at 6:27 PM on November 19, 2026: contributor

    <!--e57a25ab6845829454e8d69fc972939a-->

    The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

    <!--006a51241073e994b41acfe9ec718e94-->

    External sites

    <!--021abf342d371248e50ceaed478a90ca-->

    Reviews

    See the guideline and AI policy for information on the review process. A summary of reviews will appear here.

    <!--5faf32d7da4f0f540f40219e4f7537a3-->


github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-11-19 19:51 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me