From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Mon, 01 Jun 2026 11:03:01 -0700 Received: from mail-oo1-f61.google.com ([209.85.161.61]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1wU6yY-0003ME-H3 for bitcoindev@gnusha.org; Mon, 01 Jun 2026 11:03:01 -0700 Received: by mail-oo1-f61.google.com with SMTP id 006d021491bc7-69dc9cb3663sf8196504eaf.1 for ; Mon, 01 Jun 2026 11:02:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20251104; t=1780336972; x=1780941772; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:message-id:to:from:date:sender:from:to:cc:subject:date :message-id:reply-to; bh=YJOHPJcitcePwzbKnrD++XfzHrug5YZpGKZwQDtpXgk=; b=mP8FWHxfbRtlxZx66kCZMmZdJdXduHS7On7E6OlNXs6KELt1Z3xd5ChX4QOwT4iP4F 30nRzvQWvsNBR8ztfJ0ytrEJHdF0gsq7OA5n96LHn6s3VzzU+RHFOYy16Yqo/mp4ShVg 3fvWlg+dqqv6NErlDtMWhwgCeDLvyaPrqz1/zMJdRjtkJcq5Xy3yyyGVOrEW5MjszfEn 76N6jfCOYTpcCZt1exguscdT3V449zDwQYeMNwGArATz/ZmPUyq872hdjDQjK7+k2+uG 3HCtSY1LCw/ko8d/4md+qqleTZTh0Ml4DH6a5HBHbXBIh8AgCHoBpslWYcshkMt3Y7T9 690Q== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1780336972; x=1780941772; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:message-id:to:from:date:from:to:cc:subject:date:message-id :reply-to; bh=YJOHPJcitcePwzbKnrD++XfzHrug5YZpGKZwQDtpXgk=; b=FIxOHRPCgg80QUAZ0jsHBLSONUV4uusgSAy8Gplu81YIT7MYPlI7yvA5kPYG2wYHHf jUf763+WSQGuubpzlZTkftrq7zteU2yVAXxJxqcRCDfSph66hg8Tsl0eCIYcG3/0TGLF 06H7VjwSsgglTZWnXfkM1hAjMvmJS1oeIWz/A4u8/iW4oWhXV15ZtclKWxHTKblyb3R0 6iGUX3oapyQ15Xpkvd5+vo8pAvCT3Kbk6yPLgGeHvSgQP73acK7FEUDnYmKp6bSp9Dgh CMQCMJ0lXIx78Y2VpY5f4G2hB3ghC4c7N+a1BxUlmC60Oi6GyI3L+qTjVH5yt4BA5Ot3 23rA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1780336972; x=1780941772; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:message-id:to:from:date:x-beenthere:x-gm-message-state :sender:from:to:cc:subject:date:message-id:reply-to; bh=YJOHPJcitcePwzbKnrD++XfzHrug5YZpGKZwQDtpXgk=; b=TXledpf63kkQG56kVxIlbVWzlLgd0uMATaCV7IvI3nD1nPvXt6SRfUWFRqJtC3+vEZ Lf4g9SRwNluIDZ4gl2jWljKmxK2jcUiQvHTO6081mkywovzEQ1Hqif6o2kYNdrJGdt36 QukA3/+bq1gFNxwLzSaT4dD4CER7eQdmMC8aun3zDaYMck7F0Kd15rJJeUaA7gpzElAb JuhpnfDj6HNPztsph3fix+AzwaPwCKdXjmiD7K5ZlQUpWv3WBWgpXoZN1mohGzbBS9WV mGTNomhYQefMIuF5T/wZotum6SXmxoV/tr3NWaK63OgiAJgzY0wisJOkY1HQ20u9FSD0 2SXQ== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AFNElJ88Nt0ORn7OREYhO5Pl1HM+FeP9wIktT21QXKxAfWDyJwdk2o/e1uhWfmoGcksj20yIVrTTHOQmLUSu@gnusha.org X-Gm-Message-State: AOJu0Yxi8SIynhTJxoSYzxcXkCMzm2wp0D4ZSVFbWnUK+oZSX7OgM5Nj pUwClvpWx8VekAzWga2Rv96TB20IHewAJ2gZsjy9i8Y7cNyUs7QjfYpJ X-Received: by 2002:a05:6820:c8a:b0:69e:327f:f048 with SMTP id 006d021491bc7-69e32800993mr1075584eaf.56.1780336971006; Mon, 01 Jun 2026 11:02:51 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="AUV6zMM2xIMT22pvEtG03dGDJbQqspMtC933wqR0UFlfvRp0bQ==" Received: by 2002:a05:6820:2081:b0:67b:f5b9:99d8 with SMTP id 006d021491bc7-69df41f8ad9ls2814367eaf.0.-pod-prod-02-us; Mon, 01 Jun 2026 11:02:43 -0700 (PDT) X-Received: by 2002:a05:6808:5094:b0:479:eb19:6e6a with SMTP id 5614622812f47-485fbcc64c6mr8324361b6e.34.1780336963468; Mon, 01 Jun 2026 11:02:43 -0700 (PDT) Received: by 2002:a05:690c:5688:b0:7ba:f5aa:4ab8 with SMTP id 00721157ae682-7dc2f3656ccms7b3; Mon, 1 Jun 2026 10:46:42 -0700 (PDT) X-Received: by 2002:a05:690c:7006:b0:7b4:6f40:635 with SMTP id 00721157ae682-7e05cb40f54mr109250067b3.16.1780336000848; Mon, 01 Jun 2026 10:46:40 -0700 (PDT) Date: Mon, 1 Jun 2026 10:46:40 -0700 (PDT) From: jeremy To: Bitcoin Development Mailing List Message-Id: Subject: [bitcoindev] Prohibit Merkle Internal Node Preimages That Encode Minimal 64-Byte Transactions MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_487476_1918830888.1780336000367" X-Original-Sender: Jeremy.L.Rubin@gmail.com Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -0.5 (/) ------=_Part_487476_1918830888.1780336000367 Content-Type: multipart/alternative; boundary="----=_Part_487477_1559598651.1780336000367" ------=_Part_487477_1559598651.1780336000367 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Esteemed Colleagues, As a result of some of my research on 64-byte transactions, I'd like to=20 discuss an alternative soft fork proposal that preserves the ability to=20 encode 64-byte transactions while offering protection to SPV users (who=20 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= =20 structure of a minimal one-input, one-output, witness stripped transaction. [With the miracle of GPT,] I've drafted a relatively complete BIP for=20 discussion. Happy International Children's Day, Jeremy p.s. I will later propose potentially a couple other mitigations=20 separately, for discussion as well. ------------------------------ BIP: TBD Layer: Consensus (soft fork) Title: Prohibit Merkle Internal Node Preimages That Encode Minimal 64-Byte= =20 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=20 transaction Merkle tree internal node preimage encodes a minimal 64-byte=20 transaction. For each internal Merkle node, Bitcoin computes: parent =3D SHA256d(left || right) where left and right are 32-byte hashes. The 64-byte string left || right= =20 is the internal node preimage. After activation, a block is invalid if any such 64-byte preimage has the= =20 exact byte structure of a minimal one-input, one-output, non-witness=20 transaction. This prevents a 64-byte transaction serialization from being malleated into= =20 an internal Merkle node preimage in SPV transaction inclusion proofs. It=20 does not make 64-byte transactions invalid in general. *Motivation* Bitcoin transaction identifiers and transaction Merkle internal nodes are= =20 both computed with double SHA256: txid =3D SHA256d(serialized_transaction) parent =3D SHA256d(left_child_hash || right_child_hash) If a valid transaction serialization is exactly 64 bytes, the same byte=20 string can also be interpreted as the concatenation of two 32-byte Merkle= =20 child hashes: serialized_transaction =3D left_child_hash || right_child_hash This creates an ambiguity between a transaction leaf preimage and an=20 internal node preimage. An SPV verifier that accepts a Merkle proof without authenticating the full= =20 tree shape can be made to accept a proof terminating at an internal node=20 rather than at an actual transaction leaf. This proposal removes that ambiguity by forbidding Merkle internal node=20 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 =3D SHA256d(legacy serialization) wtxid =3D 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 =3D 0x00 flag =3D 0x01 The marker and flag bytes indicate that witness data is present. However, the transaction identifier (txid) is not computed from this=20 witness serialization. Instead, the txid is computed from the legacy=20 serialization: nVersion vin vout nLockTime with the marker, flag, and witness fields omitted. Therefore: txid =3D SHA256d(non-witness serialization) while: wtxid =3D SHA256d(full witness serialization) The transaction Merkle root committed in the block header is built from=20 transaction identifiers (txids), not witness transaction identifiers (wtxid= s ). Consequently: Merkle root =3D 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= =20 never appear in the transaction Merkle tree committed by the block header. SegWit does define a separate witness Merkle tree whose root is committed= =20 through the coinbase witness commitment, but that witness Merkle tree is=20 distinct from the transaction Merkle tree discussed in this proposal. As a result, the ambiguity addressed by this proposal concerns only=20 transaction identifiers (txids) and the transaction Merkle root. The SegWit= =20 marker and flag bytes are irrelevant to the transaction Merkle root because= =20 they are excluded from txid serialization. *Minimal 64-byte transaction shape* This proposal is concerned with the serialization used to compute a=20 transaction's txid. For legacy transactions, and for SegWit transactions when computing the txi= d,=20 the serialization format is: 4 bytes nVersion 1 byte vin count =3D 0x01 36 bytes prevout 1 byte scriptSig length =3D x x bytes scriptSig 4 bytes nSequence 1 byte vout count =3D 0x01 8 bytes nValue 1 byte scriptPubKey length =3D 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 =3D 60 bytes Therefore, for total serialized size 64: x + y =3D 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=20 64-byte byte string satisfying one of those five layouts and whose single= =20 output value is in the consensus money range. *Specification* After activation, a block is invalid if any transaction Merkle internal=20 node preimage encodes a minimal 64-byte transaction. For every internal Merkle parent computation in the transaction Merkle tree= : parent =3D SHA256d(left || right) where left and right are 32-byte child hashes, define: P =3D left || right The block is invalid if P satisfies all of the following: 1.=20 =20 P[4] =3D=3D 0x01. 2.=20 =20 P[41] is one of 0, 1, 2, 3, 4. 3.=20 =20 Let x =3D P[41]. 4.=20 =20 Let sequence_pos =3D 42 + x. 5.=20 =20 Let vout_count_pos =3D sequence_pos + 4. 6.=20 =20 Let value_pos =3D vout_count_pos + 1. 7.=20 =20 Let scriptpubkey_len_pos =3D value_pos + 8. 8.=20 =20 P[vout_count_pos] =3D=3D 0x01. 9.=20 =20 P[scriptpubkey_len_pos] =3D=3D 4 - x. 10.=20 =20 Let locktime_pos =3D scriptpubkey_len_pos + 1 + (4 - x). 11.=20 =20 locktime_pos + 4 =3D=3D 64. 12.=20 =20 The 8-byte little-endian integer at P[value_pos..value_pos+7] is in=20 MoneyRange. =20 Equivalently, the forbidden preimage is a 64-byte serialization of a=20 one-input, one-output, non-witness transaction with single-byte CompactSize= =20 counts and script lengths, where the two script lengths sum to 4 and the=20 output value is in range. For clarity, "non-witness transaction" here refers to the serialization=20 used for txid computation. Even for SegWit transactions, the transaction=20 Merkle tree uses txids, so the marker byte, flag byte, and witness data are= =20 excluded. This rule applies to every transaction Merkle internal node used to compute= =20 the block header's transaction Merkle root. *Odd-entry duplication* If a Merkle level has an odd number of entries, Bitcoin duplicates the=20 final hash: parent =3D 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= =20 branch preimage in the proof encodes a minimal 64-byte transaction under=20 the predicate above. For each branch step, the verifier knows: 1.=20 =20 The current hash. 2.=20 =20 The sibling hash. 3.=20 =20 The branch direction. =20 It reconstructs: P =3D left_child_hash || right_child_hash The verifier MUST check: IsForbiddenMerkleInternalNodePreimage(P) =3D=3D false for every branch preimage in the proof. If any branch preimage passes the forbidden-preimage predicate, the proof= =20 MUST be rejected. The verifier still performs the ordinary Merkle path computation and block= =20 header proof-of-work validation. *Rationale* The known 64-byte transaction SPV malleability issue requires a byte string= =20 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= =20 transaction remains valid unless its exact serialization appears as a=20 transaction Merkle internal node preimage in the same block's transaction= =20 Merkle tree. The rule also avoids adding a general transaction validity rule that exists= =20 only to protect Merkle proof semantics. *Why SegWit does not eliminate the ambiguity* It is sometimes assumed that SegWit automatically removes this ambiguity=20 because SegWit transactions contain the marker and flag bytes: 00 01 However, the ambiguity exists at the txid layer, not at the=20 witness-serialization layer. The transaction Merkle root in the block header is computed from txids, and= =20 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=20 transaction Merkle root does not commit to wtxids. As a result, the existence of the SegWit marker and flag bytes does not=20 prevent a txid preimage from having the same byte structure as a Merkle=20 internal node preimage. The ambiguity addressed by this proposal therefore remains relevant in the= =20 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: 1.=20 =20 It is simple to specify. 2.=20 =20 It is simple for SPV verifiers to implement. 3.=20 =20 It removes the original ambiguity by eliminating all valid 64-byte=20 transaction leaves. =20 However, it is not correct to describe that rule as automatically fixing=20 all light clients. A 64-byte transaction invalidity rule protects an SPV verifier only if the= =20 verifier enforces the new rule when interpreting the claimed transaction.= =20 Existing or application-specific SPV verifiers that merely receive a byte= =20 string and a Merkle branch may remain vulnerable if they do not parse the= =20 claimed transaction and reject exactly-64-byte transaction serializations. More generally, a consensus rule invalidating 64-byte transactions does not= =20 prevent arbitrary internal node preimages from existing. It only prevents= =20 those preimages from being valid Bitcoin transactions under upgraded=20 consensus rules. A bridge, wallet, or deposit system that accepts SPV-style= =20 proofs but performs incomplete transaction parsing may still be induced to= =20 treat an internal node preimage as an application-level event. For example, suppose an application-level SPV verifier treats a proved byte= =20 string as a "deposit" if some field inside the alleged transaction matches= =20 a registered deposit address, deposit script, or deposit commitment, but=20 does not fully enforce the upgraded transaction-validity rule. An attacker= =20 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=20 deposit commitment. In some systems, the attacker may also be able to=20 choose or register deposit data that matches bytes already present in the= =20 left-hand side of an internal node preimage. This is not a failure of upgraded full-node consensus. It is a failure of= =20 the assumption that changing full-node transaction validity automatically= =20 upgrades every SPV verifier and every bridge, wallet, or application that= =20 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=20 preimages. The 64-byte transaction invalidity rule is simpler for light clients that= =20 correctly implement it, but it is broader at the transaction layer. This=20 proposal places the rule at the Merkle ambiguity boundary and preserves=20 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=20 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=20 does not invoke the full transaction deserializer. The function returns true if the 64-byte preimage is forbidden. static constexpr int64_t COIN =3D 100000000; static constexpr int64_t MAX_MONEY =3D 21000000 * COIN; static inline bool MoneyRange(int64_t nValue) { return nValue >=3D 0 && nValue <=3D 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=20 p[64]) { // Minimal 64-byte legacy transaction shape: // // 4 bytes nVersion // 1 byte vin count =3D 0x01 // 36 bytes prevout // 1 byte scriptSig length =3D x // x bytes scriptSig // 4 bytes nSequence // 1 byte vout count =3D 0x01 // 8 bytes nValue // 1 byte scriptPubKey length =3D y // y bytes scriptPubKey // 4 bytes nLockTime // // Since the fixed overhead is 60 bytes, x + y must equal 4. if (p[4] !=3D 0x01) { return false; } const unsigned int x =3D p[41]; switch (x) { case 0: if (p[46] !=3D 0x01) return false; if (p[55] !=3D 0x04) return false; break; case 1: if (p[47] !=3D 0x01) return false; if (p[56] !=3D 0x03) return false; break; case 2: if (p[48] !=3D 0x01) return false; if (p[57] !=3D 0x02) return false; break; case 3: if (p[49] !=3D 0x01) return false; if (p[58] !=3D 0x01) return false; break; case 4: if (p[50] !=3D 0x01) return false; if (p[59] !=3D 0x00) return false; break; default: return false; } const size_t value_pos =3D 47 + x; const uint64_t raw_value =3D ReadLE64(p + value_pos); if (raw_value >=20 static_cast(std::numeric_limits::max())) { return false; } const int64_t nValue =3D static_cast(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 =3D true; return uint256{}; } unsigned char p[64]; std::memcpy(p, left.begin(), 32); std::memcpy(p + 32, right.begin(), 32); return Hash(Span(p, 64)); } This is the intended minimal rule. It checks the five possible 64-byte=20 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=20 identifiers so that two transactions, if placed as siblings in the=20 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= =20 construction, direct miner submission, or transaction ordering effects. Therefore miners MUST check candidate block templates before mining. Miners= =20 MUST NOT rely on accidental violation probability. *Merkle construction failure recovery* If a candidate block template violates this rule, the miner usually does=20 not need to discard the entire template. The violation is local to one or= =20 more internal Merkle node preimages: left_child_hash || right_child_hash A miner can usually repair the candidate block by changing transaction=20 order so that the offending pair of child hashes no longer appears as=20 siblings at the violating Merkle tree level. *Recommended recovery procedure* When Merkle root construction fails because an internal node preimage is=20 forbidden, mining software SHOULD use the following procedure: 1.=20 =20 Record each offending internal node preimage. 2.=20 =20 Identify the transaction subtree contributing to each offending child=20 hash. 3.=20 =20 Attempt to repair the block by shuffling transaction order while=20 preserving consensus transaction-order constraints. 4.=20 =20 Recompute the Merkle root and re-run the internal-node preimage check. 5.=20 =20 If the shuffled template passes, mine the repaired template. 6.=20 =20 If shuffling fails repeatedly, remove one or more transactions=20 contributing to the offending subtree and rebuild the template. =20 *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=20 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=20 not constrained by in-block dependencies, or use a randomized topological= =20 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=20 transaction dependencies. *Repeated failure* If randomized repair fails repeatedly, mining software SHOULD remove=20 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=20 subtree. For a bottom-level violation, the offending subtree usually corresponds to= =20 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=20 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= =20 one child subtree. 3. Prefer removing the lowest-feerate removable transaction that does not= =20 force removal of higher-feerate descendants. This policy does not need to identify a malicious transaction. It only=20 needs to produce a valid block template with minimal fee loss. *Fee impact* The expected fee impact for honest block templates should be negligible=20 because accidental violations are rare. If an adversary intentionally creates transactions that cause violations=20 when paired, shuffling will usually defeat the attempt without fee loss. If= =20 shuffling does not repair the template, removing one or more offending=20 transactions bounds the miner's exposure. The adversary's practical effect is limited to potentially causing some=20 transactions to be omitted from a candidate block template. The rule=20 prevents upgraded miners from mining invalid blocks, provided miners check= =20 the Merkle construction before mining. *Relation to unupgraded miners* Because accidental violations are rare, unupgraded miners are unlikely to= =20 encounter the rule during ordinary operation. However, an adversary can construct transaction pairs intended to trigger= =20 the rule under specific sibling placement. Unupgraded miners that do not enforce this rule may mine a block that=20 upgraded nodes reject after activation. Low accidental probability improves= =20 deployment safety but is not a substitute for miner enforcement. *Probability analysis* This section estimates accidental violation probability under simplified=20 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=20 transaction, it must satisfy: vin_count =3D 0x01 scriptSig_len =3D x, where x =E2=88=88 {0,1,2,3,4} vout_count =3D 0x01 at the position determined by x scriptPubKey_len =3D 4 - x nValue =E2=88=88 [0, MAX_MONEY] Ignoring nValue, the structural probability is approximately: 5 / 256^3 because there are five valid (scriptSig_len, scriptPubKey_len) splits, and= =20 three one-byte constraints: vin_count vout_count scriptPubKey_len Numerically: 5 / 256^3 =E2=89=88 2.980232238769531e-7 or approximately: 1 in 3,355,443 Including the output value money range: MAX_MONEY =3D 21,000,000 * 100,000,000 =3D 2,100,000,000,000,000 For a uniformly random unsigned 64-bit output value, the probability of=20 being in range is approximately: (MAX_MONEY + 1) / 2^64 =E2=89=88 1.1384122811097797e-4 Therefore the approximate probability that a random 64-byte preimage is=20 structurally valid and has an in-range output value is: (5 / 256^3) * ((MAX_MONEY + 1) / 2^64) =E2=89=88 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] =3D A[0..31] P[32..63] =3D A[0..31] For the same one-input, one-output 64-byte transaction shape: P[4] =3D 0x01 P[41] =3D scriptSig_len =3D x P[vout_count_pos] =3D 0x01 P[scriptpubkey_len_pos] =3D 4 - x Because positions after byte 31 alias positions in the first half: P[i] =3D A[i mod 32] The relevant positions are: vin_count_pos =3D 4 script_len_pos =3D 41 =E2=89=A1 9 mod 32 vout_count_pos =3D 46 + x =E2=89=A1 14 + x mod 32 scriptpubkey_len_pos =3D 55 + x =E2=89=A1 23 + x mod 32 The constraints are: A[4] =3D 0x01 A[9] =3D x A[14 + x] =3D 0x01 A[23 + x] =3D 4 - x For each fixed x, these are four independent one-byte constraints under the= =20 random-half model. Thus the structural probability is approximately: 5 / 256^4 =E2=89=88 1.1641532182693481e-9 or approximately: 1 in 858,993,459 The output value begins at: value_pos =3D 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=20 being in MoneyRange is approximately: (MAX_MONEY + 1) / 2^64 =E2=89=88 1.1384122811097797e-4 So the approximate probability that a random left || left preimage is=20 structurally valid and has an in-range output value is: (5 / 256^4) * ((MAX_MONEY + 1) / 2^64) =E2=89=88 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,= =20 plus duplicated-node cases depending on tree shape. Using the rough random left || right estimate: p =E2=89=88 3.39e-11 A block with 10,000 transactions has approximate accidental violation=20 probability: 1 - (1 - p)^9999 =E2=89=88 3.39e-7 or roughly: 1 in 2,950,000 blocks This is a simplified estimate. Actual txids are not perfect independent=20 random samples in all cases, duplicated nodes have lower estimated=20 probability, and additional implementation details may reduce or alter the= =20 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=20 and become invalid after activation. Unupgraded full nodes may accept violating blocks after activation.=20 Activation therefore requires ordinary soft-fork deployment procedures. Unupgraded SPV clients remain vulnerable to the legacy proof ambiguity. SPV= =20 clients must update their Merkle proof validation logic to obtain the=20 benefit of this rule. *Test vectors* Test vectors should include: 1.=20 =20 A block whose transaction Merkle internal node preimages do not encode= =20 minimal 64-byte transactions. The block is valid. 2.=20 =20 A block containing a 64-byte transaction whose serialization does not=20 appear as an internal node preimage. The block is valid. 3.=20 =20 A block where an internal node preimage encodes a minimal 64-byte=20 transaction. The block is invalid. 4.=20 =20 A block where an odd-entry duplicated preimage h || h encodes a minimal= =20 64-byte transaction. The block is invalid. 5.=20 =20 An SPV proof where one branch preimage encodes a minimal 64-byte=20 transaction. The proof is rejected. 6.=20 =20 An SPV proof for a 64-byte transaction where no branch preimage encodes= =20 a minimal 64-byte transaction. The proof is accepted if otherwise valid. =20 *Open questions* 1.=20 =20 Should the rule include only the explicit minimal 64-byte legacy=20 transaction shape above, or should it call the full consensus transactio= n=20 deserializer? 2.=20 =20 Should future transaction serialization changes be required to preserve= =20 this exact forbidden-preimage invariant? 3.=20 =20 Should pre-activation relay policy discourage transaction pairs that can= =20 form forbidden sibling preimages? 4.=20 =20 Should mining software standardize a recovery procedure for failed=20 Merkle construction, or should this remain implementation-specific? 5.=20 =20 Should SPV proof formats include an explicit version bit indicating=20 branch-preimage checking support? =20 --=20 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 e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= f97afcc5-54ba-4284-8e9b-e8c35c7101f6n%40googlegroups.com. ------=_Part_487477_1559598651.1780336000367 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

Esteemed Colleagues,

As a result of some of my research on 64-byte transacti= ons, I'd like to discuss an alternative soft fork proposal that preserves t= he 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 ex= act byte structure of a minimal one-input, one-output, witness stripped tra= nsaction.

[With the miracle of GP= T,] I've drafted a relatively complete BIP for discussion.

Happy International Children's Day,

Jeremy

p.s. I will later pro= pose potentially a couple other mitigations separately, for discussion as w= ell.

BIP: TBD
Layer: Cons= ensus (soft fork)
Title: Prohibit Merkle Internal Node Preimages That Encode Minima= l 64-Byte Transactions
Author: TBD
Status: Draft
Type: Standards TrackCreated: 2026-06-01
License: BSD-2-Clause

Abstract

This docu= ment specifies a consensus rule that invalidates a block if any transaction= Merkle tree internal node preimage encodes a minimal 64-byte transaction.<= /span>

For each internal Merkle node, Bi= tcoin computes:

parent =3D SHA256d(= left || right)


where left and right are = 32-byte hashes. The 64-byte string left || right is the internal no= de 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 serializati= on from being malleated into an internal Merkle node preimage in SPV transa= ction inclusion proofs. It does not make 64-byte transactions invalid in ge= neral.

Motivation

= txid =C2=A0 =3D SHA256d(serialized_transaction)

parent =3D 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-byt= e Merkle child hashes:

serialized_t= ransaction =3D left_child_hash || right_child_hash


This c= reates an ambiguity between a transaction leaf preimage and an internal nod= e preimage.

An SPV verifier that = accepts a Merkle proof without authenticating the full tree shape can be ma= de to accept a proof terminating at an internal node rather than at an actu= al transaction leaf.

This proposa= l removes that ambiguity by forbidding Merkle internal node preimages that = have the only practical 64-byte transaction encoding shape.

SegWit an= d transaction identifiers

Since SegWit activation, Bitcoin transactions have two related identifi= ers:

txid=C2=A0 =3D SHA256d(legacy = serialization)

wtxid =3D SHA256d(wi= tness serialization)


<= /b>

The distinction is important for und= erstanding this proposal.

A SegWi= t transaction is serialized on the wire as:

nVersion

marker

flag

vin

vout

witness

nLockTime


where:

marker =3D 0= x00

flag =C2=A0 =3D 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, t= he txid is computed from the legacy serialization:

= nVersion

vi= n

vout

nLockTime


with the marker, flag, and witness= fields omitted.

Therefore:

txid =3D SHA256d(non-witness serializati= on)


while:

wtxid = =3D SHA256d(full witness serialization)


The transaction M= erkle root committed in the block header is built from transaction identifi= ers (txids), not witness transaction identifiers (wtxids).<= /span>

Consequently:

Merkle root =3D Merkle(txid_0, txid_1, ..., txid_n)


and not:

Merkle(wtx= id_0, wtxid_1, ..., wtxid_n)


This means that the marker b= yte (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 t= hat witness Merkle tree is distinct from the transaction Merkle tree discus= sed in this proposal.

As a result= , the ambiguity addressed by this proposal concerns only transaction identi= fiers (txids) and the transaction Merkle root. The SegWit marker an= d flag bytes are irrelevant to the transaction Merkle root because they are= excluded from txid serialization.

Minimal 64-byte transactio= n shape

This proposal = is concerned with the serialization used to compute a transaction's = txid.

For legacy transactions, a= nd for SegWit transactions when computing the txid, the serializati= on format is:

4 bytes =C2=A0 nVersi= on

1 byte=C2=A0 =C2=A0 vin count = =3D 0x01

36 bytes=C2=A0 prevout

1 byte=C2=A0 =C2=A0 scriptSig length = =3D x

x bytes =C2=A0 scriptSig

4 bytes =C2=A0 nSequence

1 byte=C2=A0 =C2=A0 vout count =3D 0x01

8 bytes =C2=A0 nValue

1 byte=C2=A0 =C2=A0 scriptPubKey length =3D y

<= p dir=3D"ltr" style=3D"line-height: 1.38; margin-top: 0pt; margin-bottom: 0= pt;">y bytes =C2=A0 scriptPubKey

= 4 bytes =C2=A0 nLockTime


Notably,= this serialization does not include:

marker

flag

witness stack


because those fields ar= e excluded from txid computation.

The fixed overhead is:

4 += 1 + 36 + 1 + 4 + 1 + 8 + 1 + 4 =3D 60 bytes


Therefore, f= or total serialized size 64:

x + y = =3D 4


There are exactly five possible script-length spl= its:

scriptSig length=C2=A0 =C2=A0 = scriptPubKey length

0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 4

1 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 3

2 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 2

3 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 1

4 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 0

This proposal defines a for= bidden Merkle internal node preimage as a 64-byte byte string satisfying on= e of those five layouts and whose single output value is in the consensus m= oney 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:

par= ent =3D SHA256d(left || right)


where left and <= /span>right are 32-byte child hashes, define:

P =3D left || right


The block is invalid if = P satisfies all of the following:

  1. P[4] =3D=3D 0x01.

  2. is one of 0, 1, 2, 3, 4.

  3. Let x =3D P[41].

  4. Let sequence_pos =3D 42 + x.

  5. =

    Let vout_count_pos =3D sequence_pos + 4.

  6. L= et value_pos =3D vout_c= ount_pos + 1.

  7. Let sc= riptpubkey_len_pos =3D value_pos + 8.=

  8. P[vout_count= _pos] =3D=3D 0x01.

  9. P[scriptpubkey_len_pos] =3D=3D 4= - x.

  10. Let lockti= me_pos =3D scriptpubkey_len_pos + 1 + (4 - x).

  11. lock= time_pos + 4 =3D=3D 64.

  12. 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 sin= gle-byte CompactSize counts and script lengths, where the two script length= s sum to 4 and the output value is in range.

For clarity, "non-witness transaction" here refers to the seri= alization used for txid= computation. Even for SegWit transactions, = the transaction Merkle tree uses txids, so the marker byte, flag by= te, and witness data are excluded.

Odd-entry duplication<= /span>

If a Merkle level has = an odd number of entries, Bitcoin duplicates the final hash:

parent =3D SHA256d(last || last)


last || last=


MUST be checked by the same rule.

SPV verification rule<= /span>

An SPV verifier relyin= g on this soft fork MUST reject a Merkle proof if any branch preimage in th= e proof encodes a minimal 64-byte transaction under the predicate above.

For each branch step, the verifier = knows:

  1. The current hash.

  2. The sibling hash.

    <= /li>

  3. The branch direction.

    4. <= /ol>

    It reconstructs:

    P =3D left_child_hash || right_child_hash


    The verifier MUST check:

    IsForbi= ddenMerkleInternalNodePreimage(P) =3D=3D 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-wor= k validation.

    Rationale

    The known 64-byte transaction SPV malleability issue requires a byt= e string that is both:

    a valid 64-b= yte transaction serialization

    and:

    a transaction Merkle internal node preimage

    =

    This proposal forbids that overlap at the Merkle internal node boundar= y.

    The rule is narrower than inva= lidating all 64-byte transactions. A 64-byte transaction remains valid unle= ss its exact serialization appears as a transaction Merkle internal node pr= eimage in the same block's transaction Merkle tree.

    The rule also avoids adding a general transaction validi= ty rule that exists only to protect Merkle proof semantics.

    Why SegWi= t 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 layer, not at the witness-serializati= on layer.

    The transaction Merkle = root in the block header is computed from txids, and txids = are computed from the serialization that excludes:

    marker

    flag<= /p>

    witness


    Therefore the re= levant byte string remains:

    nVersio= n

    vin

    vout

    nLockTime<= /p>


    exactly as before SegWit.

    The witness serialization affects the wtxid, but the block he= ader's transaction Merkle root does not commit to wtxids.

    As a result, the existence of the SegWit m= arker and flag bytes does not prevent a txid preimage from having t= he same byte structure as a Merkle internal node preimage.

    The ambiguity addressed by this proposal therefor= e remains relevant in the SegWit era.

    Contrast with a 64-byte transac= tion invalidity rule

    A= direct alternative is:

    A transacti= on is invalid if its serialized size is exactly 64 bytes.


    That rule has several advantages:

    1. It is simple to specify.

    2. It is simple for SPV verifiers to implement.

    3. It removes the original ambiguity by eliminating all = valid 64-byte transaction leaves.

    However, it is not correct to describe that rule as automatica= lly fixing all light clients.

    A 6= 4-byte transaction invalidity rule protects an SPV verifier only if the ver= ifier enforces the new rule when interpreting the claimed transaction. Exis= ting or application-specific SPV verifiers that merely receive a byte strin= g and a Merkle branch may remain vulnerable if they do not parse the claime= d transaction and reject exactly-64-byte transaction serializations.=

    More generally, a consensus rule invali= dating 64-byte transactions does not prevent arbitrary internal node preima= ges from existing. It only prevents those preimages from being valid Bitcoi= n transactions under upgraded consensus rules. A bridge, wallet, or deposit= system that accepts SPV-style proofs but performs incomplete transaction p= arsing may still be induced to treat an internal node preimage as an applic= ation-level event.

    For example, s= uppose 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_ch= ild_hash || right_child_hash


    has bytes that the applicati= on interprets as a deposit transaction or deposit commitment. In some syste= ms, the attacker may also be able to choose or register deposit data that m= atches bytes already present in the left-hand side of an internal node prei= mage.

    This is not a failure of up= graded full-node consensus. It is a failure of the assumption that changing= full-node transaction validity automatically upgrades every SPV verifier a= nd every bridge, wallet, or application that consumes SPV-style proofs.

    Therefore, both approaches require l= ight-client changes:

    64-byte transa= ction invalidity:

    =C2=A0=C2=A0Light= clients must reject claimed 64-byte transaction serializations.

    =


    Merkle-internal-node preimage invalidity:

    =C2=A0=C2=A0Light clients must reject proofs containing forbid= den internal branch preimages.


    The 64-byte transaction in= validity rule is simpler for light clients that correctly implement it, but= it is broader at the transaction layer. This proposal places the rule at t= he Merkle ambiguity boundary and preserves 64-byte transactions generally.<= /span>

    In summary:

    64-byte transaction invalidity:

    =C2=A0=C2=A0- Simpler SPV rule when implemented correctly.<= /span>

    =C2=A0=C2=A0- Broader transaction v= alidity change.

    =C2=A0=C2=A0- Inval= idates all 64-byte transactions.

    = =C2=A0=C2=A0- Does not automatically fix SPV applications that fail to enfo= rce the new rule.


    =

    Merkle-internal-node preimage invalidity:=

    =C2=A0=C2=A0- Preserves 64-byte tr= ansactions generally.

    =C2=A0=C2=A0-= Places the rule at the Merkle ambiguity boundary.

    =C2=A0=C2=A0- Requires SPV verifiers to parse all branch pr= eimages.

    =C2=A0=C2=A0- Directly for= bids 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 int= 64_t COIN =3D 100000000;

    static con= stexpr int64_t MAX_MONEY =3D 21000000 * COIN;


    static inline= bool MoneyRange(int64_t nValue)

    {<= /span>

    =C2=A0=C2=A0=C2=A0=C2=A0return nVal= ue >=3D 0 && nValue <=3D MAX_MONEY;

    }


    <= /p>

    static inline uint64_t ReadLE64(const unsi= gned char* p)

    {

    =C2=A0=C2=A0=C2=A0=C2=A0return uint64_t{p[0]}

    =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0| (uint64_t{p[1]} << 8)

    =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0| (uint64_t{p[2]} <<= 16)

    =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0| (uint64_t{p[3]} << 24)

    =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0| (uint64_t{p= [4]} << 32)

    =C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0| (uint64_t{p[5]} << 40)

    <= p dir=3D"ltr" style=3D"line-height: 1.38; margin-top: 0pt; margin-bottom: 0= pt;">=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0| (uint64_t{p[6]} << 48)

    = =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0| (uint64_t{p[7]} << = 56);

    }


    static bool = IsForbiddenMerkleInternalNodePreimage64(const unsigned char p[64])

    {

    = =C2=A0=C2=A0=C2=A0=C2=A0// Minimal 64-byte legacy transaction shape:=

    =C2=A0=C2=A0=C2=A0=C2=A0//

    =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 4 bytes =C2=A0 = nVersion

    =C2=A0=C2=A0=C2=A0=C2=A0//= =C2=A0 1 byte=C2=A0 =C2=A0 vin count =3D 0x01

    =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 36 bytes=C2=A0 prevout

    =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 1 byte= =C2=A0 =C2=A0 scriptSig length =3D x

    =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 4 bytes =C2=A0 = nSequence

    =C2=A0=C2=A0=C2=A0=C2=A0/= / =C2=A0 1 byte=C2=A0 =C2=A0 vout count =3D 0x01

    =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 8 bytes =C2=A0 nValue

    =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 1 byte= =C2=A0 =C2=A0 scriptPubKey length =3D y

    =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 y bytes =C2=A0 scriptPubKey

    =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 4 bytes = =C2=A0 nLockTime

    =C2=A0=C2=A0=C2=A0= =C2=A0//

    =C2=A0=C2=A0=C2=A0=C2=A0//= Since the fixed overhead is 60 bytes, x + y must equal 4.


    = =C2=A0=C2=A0=C2=A0=C2=A0if (p[4] !=3D 0x01) {

    =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0return false;<= /span>

    =C2=A0=C2=A0=C2=A0=C2=A0}


    =C2=A0=C2=A0=C2=A0=C2=A0const unsigned int x =3D p[41];


    =C2=A0=C2=A0=C2=A0=C2=A0switch (x) {

    =C2=A0=C2=A0=C2=A0=C2=A0case 0:

    =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0if (p[46] !=3D 0x01) ret= urn false;

    =C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0if (p[55] !=3D 0x04) return false;

    = =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0bre= ak;


    =C2=A0=C2=A0=C2=A0=C2=A0case 1:

    =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0if (p[47] = !=3D 0x01) return false;

    =C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0if (p[56] !=3D 0x03) return false;

    =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0break;


    =C2=A0=C2=A0=C2=A0=C2=A0case 2:

    =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0if (p[48] !=3D 0x01) return false;

    =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0if (p[57] !=3D 0x02) = return false;

    =C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0break;


    =C2=A0=C2=A0=C2=A0=C2=A0c= ase 3:

    =C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0if (p[49] !=3D 0x01) return false;

    =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0if (p[= 58] !=3D 0x01) return false;

    =C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0break;


    =C2=A0=C2= =A0=C2=A0=C2=A0case 4:

    =C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0if (p[50] !=3D 0x01) return false;

    =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0if (p[59] !=3D 0x00) return false;

    =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0break;

    =


    =C2=A0=C2=A0=C2=A0=C2=A0default:

    =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0return false;

    =C2=A0=C2=A0=C2=A0=C2=A0}


    = =C2=A0=C2=A0=C2=A0=C2=A0const size_t value_pos =3D 47 + x;

    = =C2=A0=C2=A0=C2=A0=C2=A0const uint64_t raw_value = =3D ReadLE64(p + value_pos);


    =C2=A0=C2=A0=C2=A0=C2=A0if (ra= w_value > static_cast<uint64_t>(std::numeric_limits<int64_t>= ::max())) {

    =C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0return false;

    =C2=A0=C2=A0=C2=A0=C2=A0}


    =C2=A0=C2=A0=C2=A0=C2=A0con= st int64_t nValue =3D static_cast<int64_t>(raw_value);

    <= b style=3D"font-weight: normal;">

    =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0return fa= lse;

    =C2=A0=C2=A0=C2=A0=C2=A0}


    =C2=A0=C2=A0=C2=A0=C2=A0return true;

    }


    <= /p>

    static bool IsForbiddenMerkleInternalNode(=

    =C2=A0=C2=A0=C2=A0=C2=A0const uint= 256& left,

    =C2=A0=C2=A0=C2=A0= =C2=A0const uint256& right)

    {

    =C2=A0=C2=A0=C2=A0=C2=A0unsigned cha= r p[64];


    =C2=A0=C2=A0=C2=A0=C2=A0std::memcpy(p, left.begin(= ), 32);

    =C2=A0=C2=A0=C2=A0=C2=A0std= ::memcpy(p + 32, right.begin(), 32);


    =C2=A0=C2=A0=C2=A0=C2= =A0return IsForbiddenMerkleInternalNodePreimage64(p);

    }


    <= /b>

    A Merkle parent computation then che= cks the preimage before hashing:

    st= atic uint256 ComputeMerkleParentChecked(

    =C2=A0=C2=A0=C2=A0=C2=A0const uint256& left,

    =C2=A0=C2=A0=C2=A0=C2=A0const uint256& right,

    =C2=A0=C2=A0=C2=A0=C2=A0bool& invali= d)

    {

    =C2=A0=C2=A0=C2=A0=C2=A0if (IsForbiddenMerkleInternalNode(left, r= ight)) {

    =C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0invalid =3D true;

    =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0return uint256{};

    =C2=A0=C2=A0=C2=A0=C2=A0}

    <= p>

    =C2=A0=C2=A0=C2=A0=C2=A0unsigned char p[64];

    =C2=A0=C2=A0=C2=A0=C2=A0std::memcpy(p, left.begin(), 32);

    =C2=A0=C2=A0=C2=A0=C2=A0std::memcpy(p= + 32, right.begin(), 32);

    <= br />

    =C2=A0=C2=A0=C2=A0=C2=A0return H= ash(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 directl= y.

    Miner considerations

    Accidental violations by honest miners are expected to be rare= .

    Adversarial violations are poss= ible. An attacker may grind transaction identifiers so that two transaction= s, if placed as siblings in the transaction Merkle tree, form:

    txid_A || txid_B


    which encode= s a forbidden minimal 64-byte transaction.

    An attacker may attempt to influence sibling placement by fee = rate, package construction, direct miner submission, or transaction orderin= g effects.

    Therefore miners MUST = check candidate block templates before mining. Miners MUST NOT rely on acci= dental violation probability.

    Merkle construction failure recovery

    If a candidate block tem= plate violates this rule, the miner usually does not need to discard the en= tire template. The violation is local to one or more internal Merkle node p= reimages:

    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 n= o longer appears as siblings at the violating Merkle tree level.

    =

    Reco= mmended recovery procedure

    When Merkle root construction fails because an internal node preimage = is forbidden, mining software SHOULD use the following procedure:

    1. Record each offending internal node p= reimage.

    2. Identify the transa= ction subtree contributing to each offending child hash.

      3. Attempt to repair the block by shuffling trans= action order while preserving consensus transaction-order constraints.

    3. Recompute the Merkle root and re= -run the internal-node preimage check.

    4. If the shuffled template passes, mine the repaired template.

    5. If shuffling fails repeatedl= y, remove one or more transactions contributing to the offending subtree an= d rebuild the template.

    Preserving transaction-order constr= aints

    A shuffle MUST N= OT violate transaction dependency ordering.

    If transaction B spends an output created by transacti= on A in the same block, then A MUST appear before <= span style=3D"font-size: 11pt; font-family: "Roboto Mono", monosp= ace; color: rgb(24, 128, 56); background-color: transparent; font-weight: 4= 00; font-style: normal; font-variant: normal; text-decoration: none; vertic= al-align: baseline; white-space: pre-wrap;">B.

    The coinbase transaction MUST = remain the first transaction in the block.

    Mining software SHOULD shuffle only transactions whose relativ= e order is not constrained by in-block dependencies, or use a randomized to= pological ordering of the block's transaction dependency graph.

    <= p>Simpl= e 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 t= he graph.

    4. Construct the Merkle t= ree 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 viola= ting in-block transaction dependencies.

    Repeated failure

    If randomized repair fails repeate= dly, mining software SHOULD remove transactions contributing to the repeate= d offending subtree.

    A reasonable= policy is:

    If Merkle construction = fails after 2 independent shuffle attempts,

    remove at least one transaction from each repeatedly offending pa= ir or subtree.


    For a bottom-level violation, the offendin= g 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 ch= ild hash commits to a subtree containing multiple transactions. In that cas= e, the miner may:

    1. Try another de= pendency-preserving shuffle.

    2. If = the same higher-level violation recurs, remove one transaction from one chi= ld subtree.

    3. Prefer removing the = lowest-feerate removable transaction that does not force removal of higher-= feerate descendants.


    <= /b>

    This policy does not need to identif= y 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 th= at cause violations when paired, shuffling will usually defeat the attempt = without fee loss. If shuffling does not repair the template, removing one o= r more offending transactions bounds the miner's exposure.

    The adversary's practical effect is limited to po= tentially causing some transactions to be omitted from a candidate block te= mplate. The rule prevents upgraded miners from mining invalid blocks, provi= ded miners check the Merkle construction before mining.

    Relation to u= nupgraded miners

    Becau= se accidental violations are rare, unupgraded miners are unlikely to encoun= ter the rule during ordinary operation.

    However, an adversary can construct transaction pairs intended to tr= igger 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 probabili= ty improves deployment safety but is not a substitute for miner enforcement= .

    Probability analysis

    This section estimates accidental violation probability under simpli= fied randomness assumptions.

    Random left || right

    Assume the 64-byte internal node preimage is uniformly random.=

    For the preimage to encode a min= imal one-input, one-output 64-byte transaction, it must satisfy:

    =

    vin_count =3D 0x01

    scriptSig_len =3D x, where x =E2=88=88 {0,1,2,3,4}

    =

    vout_count =3D 0x01 at the position determine= d by x

    scriptPubKey_len =3D 4 - x

    nValue =E2=88=88 [0, MAX_MONEY]


    Ignoring = nValue, the structural probability is approx= imately:

    5 / 256^3


    (scriptSig_len, scriptPubKey_len) sp= lits, and three one-byte constraints:

    vin_count

    vout_count

    <= p dir=3D"ltr" style=3D"line-height: 1.38; margin-top: 0pt; margin-bottom: 0= pt;">scriptPubKey_len


    Numerically= :

    5 / 256^3 =E2=89=88 2.98023223876= 9531e-7


    or approximately:

    1 in 3,355,443

    Including the output value money= range:

    MAX_MONEY =3D 21,000,000 * = 100,000,000

    =C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=3D 2,100,000,000,000,000

    =


    For a uniformly random unsigned 64-bit output value, the probabilit= y of being in range is approximately:

    (MAX_MONEY + 1) / 2^64

    =E2=89=88= 1.1384122811097797e-4


    Therefore the approximate probabil= ity that a random 64-byte preimage is structurally valid and has an in-rang= e output value is:

    (5 / 256^3) * ((= MAX_MONEY + 1) / 2^64)

    =E2=89=88 3.= 392733219831406e-11


    or approximately:

    1 in 29,475,000,000


    Random left || left

    For an odd-entry duplicated Merkle node, the pr= eimage 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]=C2=A0 =3D A[0..31]

    P[32..63] =3D A[0..31]


    For the same one-= input, one-output 64-byte transaction shape:

    P[4]=C2=A0 =3D 0x01

    P[41]= =3D scriptSig_len =3D x

    P[vout_cou= nt_pos] =3D 0x01

    P[scriptpubkey_len= _pos] =3D 4 - x


    Because positions after byte 31 alias pos= itions in the first half:

    P[i] =3D = A[i mod 32]


    The relevant positions are:

    = vin_count_pos=C2=A0 =C2=A0 =C2=A0 =C2=A0 =3D 4

    script_len_pos =C2=A0 =C2=A0 =C2=A0 =3D= 41=C2=A0 =C2=A0 =C2=A0 =E2=89=A1 9=C2=A0 mod 32

    vout_count_pos =C2=A0 =C2=A0 =C2=A0 =3D 46 + x=C2=A0 =E2=89= =A1 14 + x mod 32

    scriptpubkey_len_= pos =3D 55 + x=C2=A0 =E2=89=A1 23 + x mod 32


    The constrai= nts are:

    A[4]=C2=A0 =C2=A0 =C2=A0 = =3D 0x01

    A[9]=C2=A0 =C2=A0 =C2=A0 = =3D x

    A[14 + x] =3D 0x01

    =

    A[23 + x] =3D 4 - x


    For eac= h fixed x, these are four independent one-byte constraints under th= e random-half model.

    Thus the str= uctural probability is approximately:

    5 / 256^4

    =E2=89=88 1.1641532182= 693481e-9


    or approximately:

    1 in 858,993,459

    The output value begins at:=

    value_pos =3D 47 + x

    =

    which aliases to an 8-byte window in the random 32-byte half:

    A[15 + x .. 22 + x]


    Usi= ng the same simplified independence approximation, the probability of being= in MoneyRange is approximately:

    (MAX_MONEY + 1) / 2^64

    =E2=89= =88 1.1384122811097797e-4

    So the approximate probability = that a random left || l= eft preimage is structurally valid and has a= n in-range output value is:

    (5 / 25= 6^4) * ((MAX_MONEY + 1) / 2^64)

    =E2= =89=88 1.3252864140005492e-13

    or approximately:

    1 in 7,545,600,000,000


    Block-lev= el accidental probability

    A block with n transactions has approximately n - 1 int= ernal Merkle nodes, plus duplicated-node cases depending on tree shape.

    Using the rough random left || right estimate:

    p =E2=89=88 3.39= e-11


    <= span style=3D"font-size: 11pt; font-family: Arial, sans-serif; color: rgb(0= , 0, 0); background-color: transparent; font-weight: 400; font-style: norma= l; font-variant: normal; text-decoration: none; vertical-align: baseline; w= hite-space: pre-wrap;">A block with 10,000 transactions has approximate acc= idental violation probability:

    1 - = (1 - p)^9999 =E2=89=88 3.39e-7


    or roughly:

    1 in 2,950,000 blocks


    This is a= simplified estimate. Actual txids are not perfect independent random sampl= es in all cases, duplicated nodes have lower estimated probability, and add= itional implementation details may reduce or alter the rate.

    The deployment-relevant conclusion is:

    Honest accidental violations should be rare= .

    Adversarial violations are possib= le.

    Miners must enforce the rule.


    Backward compatibility

    This is a soft fork. Blocks violating the new rule were previ= ously valid and become invalid after activation.

    Unupgraded full nodes may accept violating blocks after act= ivation. Activation therefore requires ordinary soft-fork deployment proced= ures.

    Unupgraded SPV clients rema= in vulnerable to the legacy proof ambiguity. SPV clients must update their = Merkle proof validation logic to obtain the benefit of this rule.

    Tes= t vectors

    Test vectors= should include:

    1. A block who= se transaction Merkle internal node preimages do not encode minimal 64-byte= transactions. The block is valid.

    2. A block containing a 64-byte transaction whose serialization does no= t appear as an internal node preimage. The block is valid.

      3. <= li dir=3D"ltr" style=3D"list-style-type: decimal; font-size: 11pt; font-fam= ily: Arial, sans-serif; color: rgb(0, 0, 0); background-color: transparent;= font-weight: 400; font-style: normal; font-variant: normal; text-decoratio= n: none; vertical-align: baseline; white-space: pre;">

      A block where an internal node preimage enc= odes a minimal 64-byte transaction. The block is invalid.

      A block where an odd-entry duplicated preim= age h || h encodes a minimal 64-byte transaction. The block is inva= lid.

    3. =

      An SPV proof where one = branch preimage encodes a minimal 64-byte transaction. The proof is rejecte= d.

    4. An SPV proof for a 64-by= te transaction where no branch preimage encodes a minimal 64-byte transacti= on. The proof is accepted if otherwise valid.

    Open question= s

    1. Should the rule= include only the explicit minimal 64-byte legacy transaction shape above, = or should it call the full consensus transaction deserializer?

    2. Should future transaction serialization = changes be required to preserve this exact forbidden-preimage invariant?

    3. Should pre-activation relay p= olicy discourage transaction pairs that can form forbidden sibling preimage= s?

    4. Should mining software st= andardize a recovery procedure for failed Merkle construction, or should th= is remain implementation-specific?

    5. 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 &= quot;Bitcoin Development Mailing List" group.
    To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
    To view this discussion visit https://groups.google.com/d/msgid/bitcoind= ev/f97afcc5-54ba-4284-8e9b-e8c35c7101f6n%40googlegroups.com.
    ------=_Part_487477_1559598651.1780336000367-- ------=_Part_487476_1918830888.1780336000367--