Re: [bitcoindev] Prohibit Merkle Internal Node Preimages That Encode Minimal 64-Byte Transactions

["'Antoine Poinsot' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>]

[-- Attachment #1: Type: text/plain, Size: 30815 bytes --]

Jeremy,

Thanks for sharing the proposal you have been teasing.

If requiring a change from SPV verifiers is acceptable, then there are already mitigations available today that don't need a consensus change. In fact SPV verifiers could already reject Merkle proofs where any node deserializes to a Bitcoin transaction.

Introducing a consensus rule to address this issue is interesting if it allows to patch the issue "from under" Merkle proofs users. Because despite mitigations being available today, we keep seeing new SPV verifiers deployed without such mitigations in place by implementers who are not aware of this vulnerability. I don't think we should blame implementers here: this is really a quirk that we should fix at the consensus level if we have the opportunity to.

When comparing your proposal to simply invalidating 64-byte transactions, you claim that the latter would also require SPV verifiers to patch their software:

> More generally, a consensus rule invalidating 64-byte transactions does not prevent arbitrary internal node preimages from existing. It only prevents those preimages from being valid Bitcoin transactions under upgraded consensus rules. A bridge, wallet, or deposit system that accepts SPV-style proofs but performs incomplete transaction parsing may still be induced to treat an internal node preimage as an application-level event.

This is incorrect for any bridge, wallet, or deposit system that does not receive funds to a script that either burns the funds or that anyone can spend.

Sure, an SPV verifier for a bridge or a wallet that wants to receive funds into the void would have to be patched to make sure it rejects proofs for 64-byte transactions.. But i don't think this is a meaningful distinction, as any system that actually matters and tries to secure value would not have to be patched. This is why we chose this approach for BIP 54 (see the Rationale section).

Antoine
On Monday, June 1st, 2026 at 2:02 PM, jeremy <jeremy.l.rubin@gmail.com> wrote:

> Esteemed Colleagues,
>
> As a result of some of my research on 64-byte transactions, I'd like to discuss an alternative soft fork proposal that preserves the ability to encode 64-byte transactions while offering protection to SPV users (who must make a small patch to validate the path property).
>
> The rule, stated simply, is:
>
> A block is invalid if any Merkle Tree 64-byte preimage has the exact byte structure of a minimal one-input, one-output, witness stripped transaction.
>
> [With the miracle of GPT,] I've drafted a relatively complete BIP for discussion.
>
> Happy International Children's Day,
>
> Jeremy
>
> p.s. I will later propose potentially a couple other mitigations separately, for discussion as well.
>
> ---------------------------------------------------------------
>
> BIP: TBD
> Layer: Consensus (soft fork)
> Title: Prohibit Merkle Internal Node Preimages That Encode Minimal 64-Byte Transactions
> Author: TBD
> Status: Draft
> Type: Standards Track
> Created: 2026-06-01
> License: BSD-2-Clause
>
> Abstract
>
> This document specifies a consensus rule that invalidates a block if any transaction Merkle tree internal node preimage encodes a minimal 64-byte transaction.
>
> For each internal Merkle node, Bitcoin computes:
>
> parent = SHA256d(left || right)
>
> where left and right are 32-byte hashes. The 64-byte string left || right is the internal node preimage.
>
> After activation, a block is invalid if any such 64-byte preimage has the exact byte structure of a minimal one-input, one-output, non-witness transaction.
>
> This prevents a 64-byte transaction serialization from being malleated into an internal Merkle node preimage in SPV transaction inclusion proofs. It does not make 64-byte transactions invalid in general.
>
> Motivation
>
> Bitcoin transaction identifiers and transaction Merkle internal nodes are both computed with double SHA256:
>
> txid = SHA256d(serialized_transaction)
>
> parent = SHA256d(left_child_hash || right_child_hash)
>
> If a valid transaction serialization is exactly 64 bytes, the same byte string can also be interpreted as the concatenation of two 32-byte Merkle child hashes:
>
> serialized_transaction = left_child_hash || right_child_hash
>
> This creates an ambiguity between a transaction leaf preimage and an internal node preimage.
>
> An SPV verifier that accepts a Merkle proof without authenticating the full tree shape can be made to accept a proof terminating at an internal node rather than at an actual transaction leaf.
>
> This proposal removes that ambiguity by forbidding Merkle internal node preimages that have the only practical 64-byte transaction encoding shape.
>
> SegWit and transaction identifiers
>
> Since SegWit activation, Bitcoin transactions have two related identifiers:
>
> txid = SHA256d(legacy serialization)
>
> wtxid = SHA256d(witness serialization)
>
> The distinction is important for understanding this proposal.
>
> A SegWit transaction is serialized on the wire as:
>
> nVersion
>
> marker
>
> flag
>
> vin
>
> vout
>
> witness
>
> nLockTime
>
> where:
>
> marker = 0x00
>
> flag = 0x01
>
> The marker and flag bytes indicate that witness data is present.
>
> However, the transaction identifier (txid) is not computed from this witness serialization. Instead, the txid is computed from the legacy serialization:
>
> nVersion
>
> vin
>
> vout
>
> nLockTime
>
> with the marker, flag, and witness fields omitted.
>
> Therefore:
>
> txid = SHA256d(non-witness serialization)
>
> while:
>
> wtxid = SHA256d(full witness serialization)
>
> The transaction Merkle root committed in the block header is built from transaction identifiers (txids), not witness transaction identifiers (wtxids).
>
> Consequently:
>
> Merkle root = Merkle(txid_0, txid_1, ..., txid_n)
>
> and not:
>
> Merkle(wtxid_0, wtxid_1, ..., wtxid_n)
>
> This means that the marker byte (0x00), flag byte (0x01), and witness data never appear in the transaction Merkle tree committed by the block header.
>
> SegWit does define a separate witness Merkle tree whose root is committed through the coinbase witness commitment, but that witness Merkle tree is distinct from the transaction Merkle tree discussed in this proposal.
>
> As a result, the ambiguity addressed by this proposal concerns only transaction identifiers (txids) and the transaction Merkle root. The SegWit marker and flag bytes are irrelevant to the transaction Merkle root because they are excluded from txid serialization.
>
> Minimal 64-byte transaction shape
>
> This proposal is concerned with the serialization used to compute a transaction's txid.
>
> For legacy transactions, and for SegWit transactions when computing the txid, the serialization format is:
>
> 4 bytes nVersion
>
> 1 byte vin count = 0x01
>
> 36 bytes prevout
>
> 1 byte scriptSig length = x
>
> x bytes scriptSig
>
> 4 bytes nSequence
>
> 1 byte vout count = 0x01
>
> 8 bytes nValue
>
> 1 byte scriptPubKey length = y
>
> y bytes scriptPubKey
>
> 4 bytes nLockTime
>
> Notably, this serialization does not include:
>
> marker
>
> flag
>
> witness stack
>
> because those fields are excluded from txid computation.
>
> The fixed overhead is:
>
> 4 + 1 + 36 + 1 + 4 + 1 + 8 + 1 + 4 = 60 bytes
>
> Therefore, for total serialized size 64:
>
> x + y = 4
>
> There are exactly five possible script-length splits:
>
> scriptSig length scriptPubKey length
>
> 0 4
>
> 1 3
>
> 2 2
>
> 3 1
>
> 4 0
>
> This proposal defines a forbidden Merkle internal node preimage as a 64-byte byte string satisfying one of those five layouts and whose single output value is in the consensus money range.
>
> Specification
>
> After activation, a block is invalid if any transaction Merkle internal node preimage encodes a minimal 64-byte transaction.
>
> For every internal Merkle parent computation in the transaction Merkle tree:
>
> parent = SHA256d(left || right)
>
> where left and right are 32-byte child hashes, define:
>
> P = left || right
>
> The block is invalid if P satisfies all of the following:
>
> -
>
> P[4] == 0x01.
>
> -
>
> P[41] is one of 0, 1, 2, 3, 4.
>
> -
>
> Let x = P[41].
>
> -
>
> Let sequence_pos = 42 + x.
>
> -
>
> Let vout_count_pos = sequence_pos + 4.
>
> -
>
> Let value_pos = vout_count_pos + 1.
>
> -
>
> Let scriptpubkey_len_pos = value_pos + 8.
>
> -
>
> P[vout_count_pos] == 0x01.
>
> -
>
> P[scriptpubkey_len_pos] == 4 - x.
>
> -
>
> Let locktime_pos = scriptpubkey_len_pos + 1 + (4 - x).
>
> -
>
> locktime_pos + 4 == 64.
>
> -
>
> The 8-byte little-endian integer at P[value_pos..value_pos+7] is in MoneyRange.
>
> Equivalently, the forbidden preimage is a 64-byte serialization of a one-input, one-output, non-witness transaction with single-byte CompactSize counts and script lengths, where the two script lengths sum to 4 and the output value is in range.
>
> For clarity, "non-witness transaction" here refers to the serialization used for txid computation. Even for SegWit transactions, the transaction Merkle tree uses txids, so the marker byte, flag byte, and witness data are excluded.
>
> This rule applies to every transaction Merkle internal node used to compute the block header's transaction Merkle root.
>
> Odd-entry duplication
>
> If a Merkle level has an odd number of entries, Bitcoin duplicates the final hash:
>
> parent = SHA256d(last || last)
>
> The preimage:
>
> last || last
>
> MUST be checked by the same rule.
>
> SPV verification rule
>
> An SPV verifier relying on this soft fork MUST reject a Merkle proof if any branch preimage in the proof encodes a minimal 64-byte transaction under the predicate above.
>
> For each branch step, the verifier knows:
>
> -
>
> The current hash.
>
> -
>
> The sibling hash.
>
> -
>
> The branch direction.
>
> It reconstructs:
>
> P = left_child_hash || right_child_hash
>
> The verifier MUST check:
>
> IsForbiddenMerkleInternalNodePreimage(P) == false
>
> for every branch preimage in the proof.
>
> If any branch preimage passes the forbidden-preimage predicate, the proof MUST be rejected.
>
> The verifier still performs the ordinary Merkle path computation and block header proof-of-work validation.
>
> Rationale
>
> The known 64-byte transaction SPV malleability issue requires a byte string that is both:
>
> a valid 64-byte transaction serialization
>
> and:
>
> a transaction Merkle internal node preimage
>
> This proposal forbids that overlap at the Merkle internal node boundary.
>
> The rule is narrower than invalidating all 64-byte transactions. A 64-byte transaction remains valid unless its exact serialization appears as a transaction Merkle internal node preimage in the same block's transaction Merkle tree.
>
> The rule also avoids adding a general transaction validity rule that exists only to protect Merkle proof semantics.
>
> Why SegWit does not eliminate the ambiguity
>
> It is sometimes assumed that SegWit automatically removes this ambiguity because SegWit transactions contain the marker and flag bytes:
>
> 00 01
>
> However, the ambiguity exists at the txid layer, not at the witness-serialization layer.
>
> The transaction Merkle root in the block header is computed from txids, and txids are computed from the serialization that excludes:
>
> marker
>
> flag
>
> witness
>
> Therefore the relevant byte string remains:
>
> nVersion
>
> vin
>
> vout
>
> nLockTime
>
> exactly as before SegWit.
>
> The witness serialization affects the wtxid, but the block header's transaction Merkle root does not commit to wtxids.
>
> As a result, the existence of the SegWit marker and flag bytes does not prevent a txid preimage from having the same byte structure as a Merkle internal node preimage.
>
> The ambiguity addressed by this proposal therefore remains relevant in the SegWit era.
>
> Contrast with a 64-byte transaction invalidity rule
>
> A direct alternative is:
>
> A transaction is invalid if its serialized size is exactly 64 bytes.
>
> That rule has several advantages:
>
> -
>
> It is simple to specify.
>
> -
>
> It is simple for SPV verifiers to implement.
>
> -
>
> It removes the original ambiguity by eliminating all valid 64-byte transaction leaves.
>
> However, it is not correct to describe that rule as automatically fixing all light clients.
>
> A 64-byte transaction invalidity rule protects an SPV verifier only if the verifier enforces the new rule when interpreting the claimed transaction. Existing or application-specific SPV verifiers that merely receive a byte string and a Merkle branch may remain vulnerable if they do not parse the claimed transaction and reject exactly-64-byte transaction serializations.
>
> More generally, a consensus rule invalidating 64-byte transactions does not prevent arbitrary internal node preimages from existing. It only prevents those preimages from being valid Bitcoin transactions under upgraded consensus rules. A bridge, wallet, or deposit system that accepts SPV-style proofs but performs incomplete transaction parsing may still be induced to treat an internal node preimage as an application-level event.
>
> For example, suppose an application-level SPV verifier treats a proved byte string as a "deposit" if some field inside the alleged transaction matches a registered deposit address, deposit script, or deposit commitment, but does not fully enforce the upgraded transaction-validity rule. An attacker may be able to grind child hashes so that:
>
> left_child_hash || right_child_hash
>
> has bytes that the application interprets as a deposit transaction or deposit commitment. In some systems, the attacker may also be able to choose or register deposit data that matches bytes already present in the left-hand side of an internal node preimage.
>
> This is not a failure of upgraded full-node consensus. It is a failure of the assumption that changing full-node transaction validity automatically upgrades every SPV verifier and every bridge, wallet, or application that consumes SPV-style proofs.
>
> Therefore, both approaches require light-client changes:
>
> 64-byte transaction invalidity:
>
> Light clients must reject claimed 64-byte transaction serializations.
>
> Merkle-internal-node preimage invalidity:
>
> Light clients must reject proofs containing forbidden internal branch preimages.
>
> The 64-byte transaction invalidity rule is simpler for light clients that correctly implement it, but it is broader at the transaction layer. This proposal places the rule at the Merkle ambiguity boundary and preserves 64-byte transactions generally.
>
> In summary:
>
> 64-byte transaction invalidity:
>
> - Simpler SPV rule when implemented correctly.
>
> - Broader transaction validity change.
>
> - Invalidates all 64-byte transactions.
>
> - Does not automatically fix SPV applications that fail to enforce the new rule.
>
> Merkle-internal-node preimage invalidity:
>
> - Preserves 64-byte transactions generally.
>
> - Places the rule at the Merkle ambiguity boundary.
>
> - Requires SPV verifiers to parse all branch preimages.
>
> - Directly forbids the ambiguous internal-node preimage condition.
>
> Minimal C++ implementation sketch
>
> This implementation checks only the minimal forbidden 64-byte shape. It does not invoke the full transaction deserializer.
>
> The function returns true if the 64-byte preimage is forbidden.
>
> static constexpr int64_t COIN = 100000000;
>
> static constexpr int64_t MAX_MONEY = 21000000 * COIN;
>
> static inline bool MoneyRange(int64_t nValue)
>
> {
>
> return nValue >= 0 && nValue <= MAX_MONEY;
>
> }
>
> static inline uint64_t ReadLE64(const unsigned char* p)
>
> {
>
> return uint64_t{p[0]}
>
> | (uint64_t{p[1]} << 8)
>
> | (uint64_t{p[2]} << 16)
>
> | (uint64_t{p[3]} << 24)
>
> | (uint64_t{p[4]} << 32)
>
> | (uint64_t{p[5]} << 40)
>
> | (uint64_t{p[6]} << 48)
>
> | (uint64_t{p[7]} << 56);
>
> }
>
> static bool IsForbiddenMerkleInternalNodePreimage64(const unsigned char p[64])
>
> {
>
> // Minimal 64-byte legacy transaction shape:
>
> //
>
> // 4 bytes nVersion
>
> // 1 byte vin count = 0x01
>
> // 36 bytes prevout
>
> // 1 byte scriptSig length = x
>
> // x bytes scriptSig
>
> // 4 bytes nSequence
>
> // 1 byte vout count = 0x01
>
> // 8 bytes nValue
>
> // 1 byte scriptPubKey length = y
>
> // y bytes scriptPubKey
>
> // 4 bytes nLockTime
>
> //
>
> // Since the fixed overhead is 60 bytes, x + y must equal 4.
>
> if (p[4] != 0x01) {
>
> return false;
>
> }
>
> const unsigned int x = p[41];
>
> switch (x) {
>
> case 0:
>
> if (p[46] != 0x01) return false;
>
> if (p[55] != 0x04) return false;
>
> break;
>
> case 1:
>
> if (p[47] != 0x01) return false;
>
> if (p[56] != 0x03) return false;
>
> break;
>
> case 2:
>
> if (p[48] != 0x01) return false;
>
> if (p[57] != 0x02) return false;
>
> break;
>
> case 3:
>
> if (p[49] != 0x01) return false;
>
> if (p[58] != 0x01) return false;
>
> break;
>
> case 4:
>
> if (p[50] != 0x01) return false;
>
> if (p[59] != 0x00) return false;
>
> break;
>
> default:
>
> return false;
>
> }
>
> const size_t value_pos = 47 + x;
>
> const uint64_t raw_value = ReadLE64(p + value_pos);
>
> if (raw_value > static_cast<uint64_t>(std::numeric_limits<int64_t>::max())) {
>
> return false;
>
> }
>
> const int64_t nValue = static_cast<int64_t>(raw_value);
>
> if (!MoneyRange(nValue)) {
>
> return false;
>
> }
>
> return true;
>
> }
>
> static bool IsForbiddenMerkleInternalNode(
>
> const uint256& left,
>
> const uint256& right)
>
> {
>
> unsigned char p[64];
>
> std::memcpy(p, left.begin(), 32);
>
> std::memcpy(p + 32, right.begin(), 32);
>
> return IsForbiddenMerkleInternalNodePreimage64(p);
>
> }
>
> A Merkle parent computation then checks the preimage before hashing:
>
> static uint256 ComputeMerkleParentChecked(
>
> const uint256& left,
>
> const uint256& right,
>
> bool& invalid)
>
> {
>
> if (IsForbiddenMerkleInternalNode(left, right)) {
>
> invalid = true;
>
> return uint256{};
>
> }
>
> unsigned char p[64];
>
> std::memcpy(p, left.begin(), 32);
>
> std::memcpy(p + 32, right.begin(), 32);
>
> return Hash(Span<const unsigned char>(p, 64));
>
> }
>
> This is the intended minimal rule. It checks the five possible 64-byte one-input, one-output transaction layouts directly.
>
> Miner considerations
>
> Accidental violations by honest miners are expected to be rare.
>
> Adversarial violations are possible. An attacker may grind transaction identifiers so that two transactions, if placed as siblings in the transaction Merkle tree, form:
>
> txid_A || txid_B
>
> which encodes a forbidden minimal 64-byte transaction.
>
> An attacker may attempt to influence sibling placement by fee rate, package construction, direct miner submission, or transaction ordering effects.
>
> Therefore miners MUST check candidate block templates before mining. Miners MUST NOT rely on accidental violation probability.
>
> Merkle construction failure recovery
>
> If a candidate block template violates this rule, the miner usually does not need to discard the entire template. The violation is local to one or more internal Merkle node preimages:
>
> left_child_hash || right_child_hash
>
> A miner can usually repair the candidate block by changing transaction order so that the offending pair of child hashes no longer appears as siblings at the violating Merkle tree level.
>
> Recommended recovery procedure
>
> When Merkle root construction fails because an internal node preimage is forbidden, mining software SHOULD use the following procedure:
>
> -
>
> Record each offending internal node preimage.
>
> -
>
> Identify the transaction subtree contributing to each offending child hash.
>
> -
>
> Attempt to repair the block by shuffling transaction order while preserving consensus transaction-order constraints.
>
> -
>
> Recompute the Merkle root and re-run the internal-node preimage check.
>
> -
>
> If the shuffled template passes, mine the repaired template.
>
> -
>
> If shuffling fails repeatedly, remove one or more transactions contributing to the offending subtree and rebuild the template.
>
> Preserving transaction-order constraints
>
> A shuffle MUST NOT violate transaction dependency ordering.
>
> If transaction B spends an output created by transaction A in the same block, then A MUST appear before B.
>
> The coinbase transaction MUST remain the first transaction in the block.
>
> Mining software SHOULD shuffle only transactions whose relative order is not constrained by in-block dependencies, or use a randomized topological ordering of the block's transaction dependency graph.
>
> Simple shuffle algorithm
>
> A simple repair algorithm is:
>
> 1. Keep the coinbase fixed at index 0.
>
> 2. Build a dependency graph for all non-coinbase transactions.
>
> 3. Generate a randomized topological ordering of the graph.
>
> 4. Construct the Merkle tree using that ordering.
>
> 5. Reject the ordering if any internal node preimage is forbidden.
>
> 6. Retry with a new randomized topological ordering.
>
> This changes Merkle sibling relationships without violating in-block transaction dependencies.
>
> Repeated failure
>
> If randomized repair fails repeatedly, mining software SHOULD remove transactions contributing to the repeated offending subtree.
>
> A reasonable policy is:
>
> If Merkle construction fails after 2 independent shuffle attempts,
>
> remove at least one transaction from each repeatedly offending pair or subtree.
>
> For a bottom-level violation, the offending subtree usually corresponds to two sibling transaction identifiers:
>
> txid_A || txid_B
>
> In that case, the miner may remove either tx_A or tx_B.
>
> For a higher-level violation, each child hash commits to a subtree containing multiple transactions. In that case, the miner may:
>
> 1. Try another dependency-preserving shuffle.
>
> 2. If the same higher-level violation recurs, remove one transaction from one child subtree.
>
> 3. Prefer removing the lowest-feerate removable transaction that does not force removal of higher-feerate descendants.
>
> This policy does not need to identify a malicious transaction. It only needs to produce a valid block template with minimal fee loss.
>
> Fee impact
>
> The expected fee impact for honest block templates should be negligible because accidental violations are rare.
>
> If an adversary intentionally creates transactions that cause violations when paired, shuffling will usually defeat the attempt without fee loss. If shuffling does not repair the template, removing one or more offending transactions bounds the miner's exposure.
>
> The adversary's practical effect is limited to potentially causing some transactions to be omitted from a candidate block template. The rule prevents upgraded miners from mining invalid blocks, provided miners check the Merkle construction before mining.
>
> Relation to unupgraded miners
>
> Because accidental violations are rare, unupgraded miners are unlikely to encounter the rule during ordinary operation.
>
> However, an adversary can construct transaction pairs intended to trigger the rule under specific sibling placement.
>
> Unupgraded miners that do not enforce this rule may mine a block that upgraded nodes reject after activation. Low accidental probability improves deployment safety but is not a substitute for miner enforcement.
>
> Probability analysis
>
> This section estimates accidental violation probability under simplified randomness assumptions.
>
> Random left || right
>
> Assume the 64-byte internal node preimage is uniformly random.
>
> For the preimage to encode a minimal one-input, one-output 64-byte transaction, it must satisfy:
>
> vin_count = 0x01
>
> scriptSig_len = x, where x ∈ {0,1,2,3,4}
>
> vout_count = 0x01 at the position determined by x
>
> scriptPubKey_len = 4 - x
>
> nValue ∈ [0, MAX_MONEY]
>
> Ignoring nValue, the structural probability is approximately:
>
> 5 / 256^3
>
> because there are five valid (scriptSig_len, scriptPubKey_len) splits, and three one-byte constraints:
>
> vin_count
>
> vout_count
>
> scriptPubKey_len
>
> Numerically:
>
> 5 / 256^3 ≈ 2.980232238769531e-7
>
> or approximately:
>
> 1 in 3,355,443
>
> Including the output value money range:
>
> MAX_MONEY = 21,000,000 * 100,000,000
>
> = 2,100,000,000,000,000
>
> For a uniformly random unsigned 64-bit output value, the probability of being in range is approximately:
>
> (MAX_MONEY + 1) / 2^64
>
> ≈ 1.1384122811097797e-4
>
> Therefore the approximate probability that a random 64-byte preimage is structurally valid and has an in-range output value is:
>
> (5 / 256^3) * ((MAX_MONEY + 1) / 2^64)
>
> ≈ 3.392733219831406e-11
>
> or approximately:
>
> 1 in 29,475,000,000
>
> Random left || left
>
> For an odd-entry duplicated Merkle node, the preimage has the form:
>
> left || left
>
> where the first 32 bytes equal the last 32 bytes.
>
> Let the 32-byte half be:
>
> A[0..31]
>
> Then:
>
> P[0..31] = A[0..31]
>
> P[32..63] = A[0..31]
>
> For the same one-input, one-output 64-byte transaction shape:
>
> P[4] = 0x01
>
> P[41] = scriptSig_len = x
>
> P[vout_count_pos] = 0x01
>
> P[scriptpubkey_len_pos] = 4 - x
>
> Because positions after byte 31 alias positions in the first half:
>
> P[i] = A[i mod 32]
>
> The relevant positions are:
>
> vin_count_pos = 4
>
> script_len_pos = 41 ≡ 9 mod 32
>
> vout_count_pos = 46 + x ≡ 14 + x mod 32
>
> scriptpubkey_len_pos = 55 + x ≡ 23 + x mod 32
>
> The constraints are:
>
> A[4] = 0x01
>
> A[9] = x
>
> A[14 + x] = 0x01
>
> A[23 + x] = 4 - x
>
> For each fixed x, these are four independent one-byte constraints under the random-half model.
>
> Thus the structural probability is approximately:
>
> 5 / 256^4
>
> ≈ 1.1641532182693481e-9
>
> or approximately:
>
> 1 in 858,993,459
>
> The output value begins at:
>
> value_pos = 47 + x
>
> which aliases to an 8-byte window in the random 32-byte half:
>
> A[15 + x .. 22 + x]
>
> Using the same simplified independence approximation, the probability of being in MoneyRange is approximately:
>
> (MAX_MONEY + 1) / 2^64
>
> ≈ 1.1384122811097797e-4
>
> So the approximate probability that a random left || left preimage is structurally valid and has an in-range output value is:
>
> (5 / 256^4) * ((MAX_MONEY + 1) / 2^64)
>
> ≈ 1.3252864140005492e-13
>
> or approximately:
>
> 1 in 7,545,600,000,000
>
> Block-level accidental probability
>
> A block with n transactions has approximately n - 1 internal Merkle nodes, plus duplicated-node cases depending on tree shape.
>
> Using the rough random left || right estimate:
>
> p ≈ 3.39e-11
>
> A block with 10,000 transactions has approximate accidental violation probability:
>
> 1 - (1 - p)^9999 ≈ 3.39e-7
>
> or roughly:
>
> 1 in 2,950,000 blocks
>
> This is a simplified estimate. Actual txids are not perfect independent random samples in all cases, duplicated nodes have lower estimated probability, and additional implementation details may reduce or alter the rate.
>
> The deployment-relevant conclusion is:
>
> Honest accidental violations should be rare.
>
> Adversarial violations are possible.
>
> Miners must enforce the rule.
>
> Backward compatibility
>
> This is a soft fork. Blocks violating the new rule were previously valid and become invalid after activation.
>
> Unupgraded full nodes may accept violating blocks after activation. Activation therefore requires ordinary soft-fork deployment procedures.
>
> Unupgraded SPV clients remain vulnerable to the legacy proof ambiguity. SPV clients must update their Merkle proof validation logic to obtain the benefit of this rule.
>
> Test vectors
>
> Test vectors should include:
>
> -
>
> A block whose transaction Merkle internal node preimages do not encode minimal 64-byte transactions. The block is valid.
>
> -
>
> A block containing a 64-byte transaction whose serialization does not appear as an internal node preimage. The block is valid.
>
> -
>
> A block where an internal node preimage encodes a minimal 64-byte transaction. The block is invalid.
>
> -
>
> A block where an odd-entry duplicated preimage h || h encodes a minimal 64-byte transaction. The block is invalid.
>
> -
>
> An SPV proof where one branch preimage encodes a minimal 64-byte transaction. The proof is rejected.
>
> -
>
> An SPV proof for a 64-byte transaction where no branch preimage encodes a minimal 64-byte transaction. The proof is accepted if otherwise valid.
>
> Open questions
>
> -
>
> Should the rule include only the explicit minimal 64-byte legacy transaction shape above, or should it call the full consensus transaction deserializer?
>
> -
>
> Should future transaction serialization changes be required to preserve this exact forbidden-preimage invariant?
>
> -
>
> Should pre-activation relay policy discourage transaction pairs that can form forbidden sibling preimages?
>
> -
>
> Should mining software standardize a recovery procedure for failed Merkle construction, or should this remain implementation-specific?
>
> -
>
> Should SPV proof formats include an explicit version bit indicating branch-preimage checking support?
>
> --
> You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/f97afcc5-54ba-4284-8e9b-e8c35c7101f6n%40googlegroups.com.

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/MuaBBWyHNVBd2i0ppWeXGlhAx8C_UqdUZctkuQ7stQeo8CudqJSWfeJHsmJLYLgXz_XZgRw5i1nTJ4wAZCsdCyQccR1Xh4IzA4QjBMVUJpU%3D%40protonmail.com.

[-- Attachment #2: Type: text/html, Size: 229703 bytes --]