Keep witness stacks in serialized form in CScriptWitness #36521

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.

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.

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.

Convert the uses of CScriptWitness::stack for which the new interface
is a simple substitution. The remaining ones 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')

# Element count, emptiness, and last element: the witness has size(), empty() and back() itself. 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/b' \
    -e 's/\.stack\.(size|empty|back)\(\)/.\1()/g' $FILES

# 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\[[^]]*\]( =|\.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

# Serialization of the stack, and its size: serialize the witness itself, which has the same serialization.
sed -i -E -e 's/ (>>|<<) ([][A-Za-z0-9_.]+)\.stack;/ \1 \2;/' \
    -e 's/(SerializeToVector|UnserializeFromVector)\(s, (\w+)\.stack\)/\1(s, \2)/' \
    -e 's/::GetSerializeSize\(([][A-Za-z0-9_.]+)\.stack\)/::GetSerializeSize(\1)/' $FILES

# Range-for loops over the stack: iterate over the witness. Its elements are spans, returned by value, so they are not
# bound by reference.
sed -i -E 's/for \(const auto& (\w+) : ([][A-Za-z0-9_.]+)\.stack\)/for (const auto \1 : \2)/' $FILES

# 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).
sed -i -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/block_assemble.cpp 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

# 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-

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.

Convert the remaining non-test uses of CScriptWitness::stack, which need
more than a substitution. The script interpreter now converts the
witness stack to a vector of vectors once, and moves the remaining
elements into the execution stack, rather than copying them.

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.

This returns the data that has not been read yet, as a span referring
to the underlying data. It will be used in the next commit to find the
elements of a witness stack within its 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. Future commits will make both faster.

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.

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.

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.

Add a reject_empty flag to TransactionSerParams, which makes
deserialization fail as soon as a transaction is found to have no
inputs or no outputs. Such transactions are never valid, but are
currently fully deserialized (along with the rest of the message) before
validation rejects them.

This bounds the memory a peer can make us allocate by sending a block:
without the flag, a block of 10-byte empty transactions costs about 17
bytes of memory (and one allocation per 10 bytes) per byte received.
With it, the worst case is a block of minimal transactions with one
input and one output, costing about 6 bytes of memory per byte.

The flag is enabled (as TX_WITH_WITNESS_P2P) only where transactions are
received from P2P peers: tx and block messages, and the transactions in
cmpctblock and blocktxn messages. Like other malformed messages, these
are now ignored, rather than causing the peer to be disconnected for
sending an invalid transaction or block. The functional tests are
updated accordingly.