kernel: add btck_witness_stack_get_items #36909

pull pzafonte wants to merge 14 commits into bitcoin:master from pzafonte:kernel-witness-stack-iterate-items changing 65 files +677 −239
  1. pzafonte commented at 4:24 PM on November 18, 2026: contributor

    With the change on #36895 :

    libbitcoinkernel's witness stack element accessor becomes O(n) in the index of the witness element; using it to iterate a whole witness may therefore become O(n^2).

    This adds btck_witness_stack_get_items which reads the stack in one O(n) pass and writes each item's pointer and size into two arrays passed to it. WitnessStackApi::GetItems is the C++ wrapper. The pointers are valid as long as the witness stack exists.

    An earlier version passed each item to a callback from the bottom of the stack to the top. That order followed the serialization, which can only be read from the bottom up, more than how a stack should actually be read. This version lets the items be read from either end.

  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.
    a6a4df2770
  15. DrahtBot added the label Validation on Nov 18, 2026
  16. DrahtBot commented at 4:24 PM on November 18, 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-->

    LLM Linter (✨ experimental)

    Possible typos and grammar issues:

    • src/kernel/bitcoinkernel.h: Each pointer is valid as long as the witness stack → Each pointer is valid as long as the witness stack exists [the sentence is missing a verb]

    <sup>2026-11-19 05:48:18</sup>

  17. DrahtBot added the label CI failed on Nov 18, 2026
  18. in src/kernel/bitcoinkernel.h:1891 in 957ca2962f
    1884 | @@ -1878,6 +1885,21 @@ BITCOINKERNEL_API int BITCOINKERNEL_WARN_UNUSED_RESULT btck_witness_stack_get_it
    1885 |      btck_WriteBytes writer,
    1886 |      void* user_data) BITCOINKERNEL_ARG_NONNULL(1, 3);
    1887 |  
    1888 | +/**
    1889 | + * @brief Pass each item of a witness stack to the callback, in index order.
    1890 | + * This reads the stack once, unlike repeated btck_witness_stack_get_item_at
    1891 | + * calls.
    


    ajtowns commented at 3:50 AM on November 19, 2026:

    This processes the witness stack from the bottom to the top, treating it more like a queue than a stack. Doesn't really feel the right API to me?


    pzafonte commented at 5:08 AM on November 19, 2026:

    Hmmm, I think that's a fair point. I suppose I was too focused on how because of it being serialized it can only be read one item at a time from the bottom up. On second thought / glance a call that writes every item's pointer and size into two arrays passed to it, so the items can be read from either end might be the better shape for the API.


    pzafonte commented at 6:02 AM on November 19, 2026:

    I switched to this shape in 9d0f1d05bd. I feel much better about this approach.

  19. yuvicc commented at 5:13 AM on November 19, 2026: contributor

    Instead of adding a new callback type to the API, we could expose the witness stack's serialization, e.g. btck_witness_stack_to_bytes, which would also read the whole witness in a single call, and let the bindings or caller decide how to decode it?

    update: opened #36911 as an alternative.

  20. kernel: add btck_witness_stack_get_items
    Reading a whole witness stack with btck_witness_stack_get_item_at is
    O(n^2) because each call walks the items before the one it returns.
    This function gets every item in one O(n) pass and the caller can
    read them in any order.
    9d0f1d05bd
  21. pzafonte force-pushed on Nov 19, 2026
  22. pzafonte renamed this:
    kernel: add btck_witness_stack_iterate_items
    kernel: add btck_witness_stack_get_items
    on Nov 19, 2026
  23. pzafonte commented at 6:15 AM on November 19, 2026: contributor

    Instead of adding a new callback type to the API, we could expose the witness stack's serialization

    Thanks! The latest push drops the callback. The function now writes every item's pointer and size into two arrays passed to it. I'll take a look your PR as well!

  24. DrahtBot removed the label CI failed on Nov 19, 2026
  25. pzafonte commented at 6:15 PM on November 19, 2026: contributor

    Just for reference here I ran #36909 on top of @optout21 's commit f122aeeb88 from pr36895-oo-optim1. Both with an input with n one-byte witness items through the C API.

    n get_item_at loop (before / after) get_items (before / after)
    3 68 ns / 15 ns 33 ns / 7 ns
    100 28 µs / 6.6 µs 814 ns / 227 ns
    10,000 260 ms / 97 ms 82 µs / 27 µs

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