From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 16 Jun 2026 13:22:58 -0700 Received: from mail-oo1-f62.google.com ([209.85.161.62]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1wZaJD-0002DL-38 for bitcoindev@gnusha.org; Tue, 16 Jun 2026 13:22:58 -0700 Received: by mail-oo1-f62.google.com with SMTP id 006d021491bc7-69e61a0e999sf201394eaf.0 for ; Tue, 16 Jun 2026 13:22:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20251104; t=1781641369; x=1782246169; 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:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=dWxM4adRoFI7EkVGaUALuhh4IpBxIebe9I+nKb+W+CQ=; b=uzha9XLxfOECNEpk4nWQ1fuajkexjGLFH8p5CggZCUCgmvc5RoPIG9oblpaYXcgW4P rWM5TWY0AFRA6mykF5rkWE/CvZy5KdFoh1Mi/EX7vjRWW1LlGl1O29d8Wf+o+qO1NvNO RwllmkswIPmbuRhfO8qqyQ3H/NgEiTlb42ihW+K5xC5jYiapCSyssO+VhEGKNhxepDqk kA9yoW3yWn4xGdzfhLlto+QkBjiiIA4cL2/mgTPH9pc9JeopQP7miAG8hcOe6t9/KfAZ fkJ0xDT8f4x+SFMaSWEZTZezDDtw9q9jlNUpqy3rBObVG3LXWjjAkqsNgiwaosBqvbJG 4nrQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1781641369; x=1782246169; 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:references:in-reply-to:message-id:to:from:date:from:to:cc :subject:date:message-id:reply-to; bh=dWxM4adRoFI7EkVGaUALuhh4IpBxIebe9I+nKb+W+CQ=; b=ngJQoh5g/Y/J3WrXrC7KMeTuMOi+nhtVnVljW2Wd7Vwvxd6NUtQ/5gmYzrz552UwiH GydsGEQoGoXmjemEifpxUYBLvMhpDcCDrePdRlsRJ35h3ijEf4sC5kgNkdDdH3m6GCvq Yu6YDtv8TKVrP2sKS+rE1qlLLpkRafdVJ/NkoZ2EpGVwt+/VF9Wp9L3IdHQp7I2CxDIf m5OP1OKBnMxZQvHKZGDeDHw1I85/WazEBJ2d9UpyJI37cmjrAMc0AcPCwqnIr0r7MF77 tv2ouYmNhJSiIUN876F005SDfM3wjUXP/hXBsT5TUKXCR6ozh+wrKExK5R6VzdVcp3cT kByQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1781641369; x=1782246169; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=dWxM4adRoFI7EkVGaUALuhh4IpBxIebe9I+nKb+W+CQ=; b=iiE+1DuSKiS94aF+dCvVuUYiXyRS5MbLte1Ff8hoBpTZyE4tht0uB7HHhL0Fxfz++b tYjGJRPx16WtPBe09fk+BVpOojOnO95xXoQeKSDMnkqDrLWA54eSfPmypyixTq/8S7dC KDME2JObFbaRiQcEuVRoV31xwwfNF/jRiVAvjjSDeseZSAqmzfRRSiZ8S+TYQj+V9jdo 4pe+pE4uFNut3PxD00S2zTU8Qe2Yoa5OZlzF+Bch+780TY4dXvucVKIHkJPi87M+GEG9 11aaRP2/GKs+4Xt5fC75v9ENAiN80+X4BdR6nVQu6TvWbwd6MF4vX9ug2Zyti4os+rPy ODuA== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AFNElJ+gVKVsCvIPH4KzE36e00v+96fhUeA4iUH71nB3sAZy3sTs6nusT7vsqa8DZMuxEPP9HLVB5Fz/E75A@gnusha.org X-Gm-Message-State: AOJu0YzMKHLsJpOJqYBp/i/OYezInzxrZ1ErNKZpJ30TdAa7wk+hh79n FLoeRIiPneJrXJ2kDEq55nfK5PdTScL2uV/0HJJF3g2RSiel2BXScfoU X-Received: by 2002:a05:6820:8108:b0:69d:5a5f:a94 with SMTP id 006d021491bc7-6a0b7ab60b4mr145689eaf.15.1781641368955; Tue, 16 Jun 2026 13:22:48 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="AX0PUUdiEJZO+z1d1IVP2a7PipGfb2b1N/fqxzm7zECVvIFY8w==" Received: by 2002:a05:6871:680a:b0:43c:2dcc:e1c with SMTP id 586e51a60fabf-442624e0dffls3622869fac.2.-pod-prod-07-us; Tue, 16 Jun 2026 13:22:43 -0700 (PDT) X-Received: by 2002:a05:6808:244c:b0:486:37ab:e829 with SMTP id 5614622812f47-48942b189f6mr1062772b6e.41.1781641363421; Tue, 16 Jun 2026 13:22:43 -0700 (PDT) Received: by 2002:a05:690c:360c:b0:7fd:3980:ebd6 with SMTP id 00721157ae682-7fe3e761b37ms7b3; Tue, 16 Jun 2026 12:59:35 -0700 (PDT) X-Received: by 2002:a05:690c:6208:b0:7ba:eefe:9fa1 with SMTP id 00721157ae682-7fe5b0ec69dmr6253047b3.6.1781639974206; Tue, 16 Jun 2026 12:59:34 -0700 (PDT) Date: Tue, 16 Jun 2026 12:59:33 -0700 (PDT) From: jeremy To: Bitcoin Development Mailing List Message-Id: <2cae3f35-2058-4e41-8fe9-d2ef06259e0dn@googlegroups.com> In-Reply-To: References: Subject: [bitcoindev] Re: Prohibit Merkle Internal Node Preimages That Encode Minimal 64-Byte Transactions MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_10388_1232895752.1781639973748" 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_10388_1232895752.1781639973748 Content-Type: multipart/alternative; boundary="----=_Part_10389_20215392.1781639973748" ------=_Part_10389_20215392.1781639973748 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Adding a note & reference that Rootstock uses a similar mitigation for it's= =20 SPV proofs: See the below code: https://github.com/rsksmart/bitcoinj-thin/blob/f89816871d644436e34cd8d0a70c= 3c8ef41b0836/src/main/java/co/rsk/bitcoinj/core/PartialMerkleTree.java#L187 And SDL's blog post on the=20 topic: https://bitslog.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-= tree-design So enforcing this rule would align with existing deployed systems. On Monday, June 1, 2026 at 2:02:51=E2=80=AFPM UTC-4 jeremy wrote: > 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 transactio= n. > > [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-Byt= e=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=20 > into an internal Merkle node preimage in SPV transaction inclusion proofs= .=20 > It 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=20 > full tree shape can be made to accept a proof terminating at an internal= =20 > node 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 identifier= s: > > 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 ( > wtxids). > > 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=20 > data never appear in the transaction Merkle tree committed by the block= =20 > 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=20 > SegWit marker and flag bytes are irrelevant to the transaction Merkle roo= t=20 > because 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= =20 > txid, 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=20 > 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 CompactSi= ze=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= =20 > are excluded. > > This rule applies to every transaction Merkle internal node used to=20 > compute 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= =20 > any branch preimage in the proof encodes a minimal 64-byte transaction=20 > under 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 bloc= k=20 > header proof-of-work validation. > > *Rationale* > > The known 64-byte transaction SPV malleability issue requires a byte=20 > 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-byt= e=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=20 > exists 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,= =20 > 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=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 th= e=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 th= e=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= =20 > not prevent arbitrary internal node preimages from existing. It only=20 > prevents those preimages from being valid Bitcoin transactions under=20 > upgraded consensus rules. A bridge, wallet, or deposit system that accept= s=20 > SPV-style proofs but performs incomplete transaction parsing may still be= =20 > induced to treat an internal node preimage as an application-level event. > > For example, suppose an application-level SPV verifier treats a proved=20 > byte string as a "deposit" if some field inside the alleged transaction= =20 > matches a registered deposit address, deposit script, or deposit=20 > commitment, but does not fully enforce the upgraded transaction-validity= =20 > 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=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,=20 > package construction, direct miner submission, or transaction ordering=20 > effects. > > Therefore miners MUST check candidate block templates before mining.=20 > Miners 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 t= o=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 chec= k=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 improv= es=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,=20 > and 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= =20 > the 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=20 > nodes, 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 th= e=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.= =20 > SPV 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=20 > minimal 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=20 > encodes a minimal 64-byte transaction. The proof is accepted if otherw= ise=20 > 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 transact= ion=20 > deserializer? > 2.=20 > =20 > Should future transaction serialization changes be required to=20 > preserve this exact forbidden-preimage invariant? > 3.=20 > =20 > Should pre-activation relay policy discourage transaction pairs that= =20 > can 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/= 2cae3f35-2058-4e41-8fe9-d2ef06259e0dn%40googlegroups.com. ------=_Part_10389_20215392.1781639973748 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Adding a note & reference that Rootstock uses a similar mitigation= for it's SPV proofs:

See the below code:
<= div>
https://github.com/rsksmart/bitcoinj-thin/blob/f89816871d64= 4436e34cd8d0a70c3c8ef41b0836/src/main/java/co/rsk/bitcoinj/core/PartialMerk= leTree.java#L187

And SDL's blog post on the topic:=C2= =A0https://bitslog.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-tree= -design


So enforcing this rule = would align with existing deployed systems.

On Monday, June 1, 2026= at 2:02:51=E2=80=AFPM UTC-4 jeremy wrote:

Esteemed Colleagues,

As a res= ult 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 s= mall 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 transa= ction.

[With the miracle of GPT,] I've drafted a relativel= y complete BIP for discussion.

Happy International Children= 9;s Day,

Jeremy

p.s. I will later propose potentia= lly a couple other mitigations separately, for discussion as well.

<= hr>

BIP: TBD
Layer: Consensus (soft fork)
Title: Prohibit Merkle Internal Node Preimages That Encode Mi= nimal 64-Byte Transactions
Author: TBD
Status: Draft
Type: Standards Track
Created: 2026-06-01
License: BSD-2-Clause

Abstract

Thi= s document specifies a consensus rule that invalidates a block if any trans= action Merkle tree internal node preimage encodes a minimal 64-byte transac= tion.

For each internal Merkle node, Bitcoin computes:<= /p>

parent =3D SHA256d(left || right)


where left and = right are 32-byte hashes. The 64-byte = string left || right is the internal n= ode 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 trans= action serialization from being malleated into an internal Merkle node prei= mage in SPV transaction inclusion proofs. It does not make 64-byte transact= ions invalid in general.

<= span style=3D"font-size:23pt;font-family:Arial,sans-serif;color:rgb(0,0,0);= background-color:transparent;font-weight:700;font-style:normal;font-variant= :normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">= Motivation

Bitcoin transaction identifiers and tran= saction Merkle internal nodes are both computed with double SHA256:<= /p>

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

parent =3D= SHA256d(left_child_hash || right_child_hash)


If a valid transaction serialization is exac= tly 64 bytes, the same byte string can also be interpreted as the concatena= tion of two 32-byte Merkle child hashes:

serialized_transaction = =3D left_child_hash || right_child_hash


This creates an ambiguity between a transaction le= af preimage and an internal node preimage.

An SPV verifier t= hat accepts a Merkle proof without authenticating the full tree shape can b= e 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 6= 4-byte transaction encoding shape.

SegWit and transaction identifiers

Since = SegWit activation, Bitcoin transactions have two related identifiers:

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

wtxid =3D SHA= 256d(witness serialization)

The distinction is important for understanding this proposal.<= /span>

A SegWit transaction is serialized on the wire as:

<= p dir=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;margin-bottom:0pt"><= span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);= background-color:transparent;font-weight:400;font-style:normal;font-variant= :normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">= nVersion

marker

flag

vin

vout=

witness

nLockTime


where:

marker =3D 0x00

flag= =C2=A0 =3D 0x01


<= p dir=3D"ltr" style=3D"line-height:1.38;margin-top:12pt;margin-bottom:12pt"= >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 serializ= ation:

nVersion

vin

vout

nLock= Time


with the m= arker, flag, and witness fields omitted.

Therefore:

=

= txid =3D SHA256d(non-witness serialization)


while:

wtxid =3D SHA256d(full witn= ess serialization)


The transaction Merkle root committed in the block header is built from= transaction identifiers (txids), not = witness transaction identifiers (wtxids= ).

Consequently:

Merkle root =3D Merkle(txid_0, tx= id_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 transact= ion Merkle tree committed by the block header.

SegWit does def= ine a separate witness Merkle tree whose root is committed through the coin= base witness commitment, but that witness Merkle tree is distinct from the = transaction Merkle tree discussed in this proposal.

As a resul= t, the ambiguity addressed by this proposal concerns only transaction ident= ifiers (txids) and the transaction Mer= kle root. The SegWit marker and flag bytes are irrelevant to the transactio= n Merkle root because they are excluded from t= xid serialization.

Minimal 64-byte transaction shape

This proposal i= s 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 =C2=A0 nVe= rsion

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<= /span>

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

y byt= es =C2=A0 scriptPubKey

4 bytes =C2=A0 nLockTime


Notably, this serialization doe= s not include:

marker

flag

witness stack


because those fi= elds are excluded from txid computati= on.

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=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 forbidden Merkle internal= node preimage as a 64-byte byte string satisfying one of those five layout= s 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:<= /p>

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. P[4] =3D=3D 0x01.

  2. P[41] i= s 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. Let value_pos =3D vout_count_pos + 1.

  7. L= et scriptpubkey_len_pos =3D value_pos + 8.

  8. P[vout_count_pos] =3D=3D 0x01.

    9. P[s= criptpubkey_len_pos] =3D=3D 4 - x.

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

  10. lockti= me_pos + 4 =3D=3D 64.

  11. =

    The 8-byte little-endian integer at P[value_pos..value_pos+7] is in MoneyRange.

Equivalently, the forbid= den preimage is a 64-byte serialization of a one-input, one-output, non-wit= ness transaction with single-byte CompactSize counts and script lengths, wh= ere 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 computati= on. Even for SegWit transactions, the transaction Merkle tree uses <= span style=3D"font-size:11pt;font-family:"Roboto Mono",monospace;= color:rgb(24,128,56);background-color:transparent;font-weight:400;font-styl= e:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;w= hite-space:pre-wrap">txids, so the marker byte, flag byte, and witn= ess data are excluded.

This rule applies to every transaction = Merkle internal node used to compute the block header's transaction Mer= kle root.

Odd-entry dupli= cation

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

parent =3D SHA256d(last |= | last)


The pre= image:

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 br= anch preimage in the 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 direct= ion.

It reconstructs:

P =3D left_child_ha= sh || right_child_hash


The verifier MUST check:

IsForbiddenMerkleInternalNodePr= eimage(P) =3D=3D false


for every branch preimage in the proof.

If any branch = preimage passes the forbidden-preimage predicate, the proof MUST be rejecte= d.

The verifier still performs the ordinary Merkle path comput= ation 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 in= ternal node preimage


<= /p>

This proposal forbids that overlap at the Merkle internal node bounda= ry.

The rule is narrower than invalidating all 64-byte transac= tions. A 64-byte transaction remains valid unless its exact serialization a= ppears as a transaction Merkle internal node preimage in the same block'= ;s transaction Merkle tree.

The rule also avoids adding a gene= ral transaction validity rule that exists only to protect Merkle proof sema= ntics.

Why SegWit does no= t eliminate the ambiguity

It is sometimes assumed t= hat 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-serial= ization 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

<= p>

Therefore the relevant byt= e string remains:

nVersion

vin

vout

nLockTime


= exactly as before SegWit.

The witness serialization affects t= he wtxid, but the block header's t= ransaction Merkle root does not commit to wtxi= ds.

As a result, the existence of the SegWit marker an= d flag bytes does not prevent a txid p= reimage from having the same byte structure as a Merkle internal node preim= age.

The ambiguity addressed by this proposal therefore remain= s relevant in the SegWit era.

= Contrast with a 64-byte transaction invalidity rule<= /p>

A direct alternative is:

A transaction is invalid if its s= erialized size is exactly 64 bytes.


That rule has several advantages:

  1. It is simple to specify.

  2. It is simple for SPV verifiers to impl= ement.

  3. = It removes the original ambiguity by eliminating all valid 64-byte transac= tion 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 o= r application-specific SPV verifiers that merely receive a byte string and = a Merkle branch may remain vulnerable if they do not parse the claimed tran= saction and reject exactly-64-byte transaction serializations.

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

For= example, suppose an application-level SPV verifier treats a proved byte st= ring 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 att= acker may be able to grind child hashes so that:

left_child_hash= || right_child_hash


<= /p>

has bytes that the application interprets as a deposit transaction or= deposit commitment. In some systems, the attacker may also be able to choo= se 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 cha= nging full-node transaction validity automatically upgrades every SPV verif= ier and every bridge, wallet, or application that consumes SPV-style proofs= .

Therefore, both approaches require light-client changes:

64-byte transaction invalidity:

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


Merkle-internal-node preimage inva= lidity:

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


The 64-byte transaction invalidity rule is simpler fo= r light clients that correctly implement it, but it is broader at the trans= action layer. This proposal places the rule at the Merkle ambiguity boundar= y and preserves 64-byte transactions generally.

In summary:

64-byte transaction invalidity:

=C2=A0=C2=A0- Simpler S= PV rule when implemented correctly.

=C2=A0=C2=A0- Broader transa= ction validity change.

=C2=A0=C2=A0- Invalidates all 64-byte tra= nsactions.

=C2=A0=C2=A0- Does not automatically fix SPV applicat= ions that fail to enforce the new rule.


Merkle-internal-node preimage invalidity:

=

= =C2=A0=C2=A0- Preserves 64-byte transactions generally.

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

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

=

= =C2=A0=C2=A0- Directly forbids the ambiguous internal-node preimage condit= ion.


Minimal C++ impl= ementation sketch

This implementation checks only t= he 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 con= stexpr int64_t COIN =3D 100000000;

static constexpr int64_t MAX_= MONEY =3D 21000000 * COIN;

static inline bool MoneyRange(int64_t nValue)

{=

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

}

static inline uint64_t ReadLE64(const unsigned 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:0pt"><= span style=3D"font-size:11pt;font-family:Arial,sans-serif;color:rgb(0,0,0);= background-color:transparent;font-weight:400;font-style:normal;font-variant= :normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">= =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 u= nsigned char p[64])

{

=C2=A0=C2=A0=C2=A0=C2=A0// Mini= mal 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 0= x01

=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 len= gth =3D x

=C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 x bytes =C2=A0 scrip= tSig

=C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 4 bytes =C2=A0 nSequence<= /span>

=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 nValu= e

=C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 1 byte=C2=A0 =C2=A0 scriptPu= bKey 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;

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


=C2=A0=C2=A0=C2=A0=C2=A0co= nst 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) return 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=A0break;


=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;


<= /b>

=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 fa= lse;

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


=C2=A0=C2=A0=C2=A0= =C2=A0case 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 fa= lse;

=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=A0co= nst uint64_t raw_value =3D ReadLE64(p + value_pos);


=C2=A0=C2=A0=C2=A0=C2=A0if (raw_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=A0const int64_t nValue =3D stat= ic_cast<int64_t>(raw_value);


=C2=A0=C2=A0=C2=A0=C2=A0if (!MoneyRange(nValue)) {=

=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}

<= br>

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

}

=

static bool IsForbiddenMerkleI= nternalNode(

=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=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);


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

}


= A Merkle parent computation then checks the preimage before hashing:

static 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& invalid)

{

=C2=A0=C2=A0=C2=A0=C2=A0if (IsForbiddenMerkleInterna= lNode(left, right)) {

=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=A0unsi= gned char p[64];

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

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


=C2= =A0=C2=A0=C2=A0=C2=A0return Hash(Span<const unsigned char>(p, 64));

}


Thi= s is the intended minimal rule. It checks the five possible 64-byte one-inp= ut, one-output transaction layouts directly.

Miner considerations

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

Adversar= ial violations are possible. An attacker may grind transaction identifiers = so that two transactions, if placed as siblings in the transaction Merkle t= ree, form:

txid_A || txid_B


which encodes a forbidden minimal 64-byte transacti= on.

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

Therefore miners MUST check candidate block tem= plates before mining. Miners MUST NOT rely on accidental violation probabil= ity.

Merkle constructio= n failure recovery

If a candidate block template vi= olates this rule, the miner usually does not need to discard the entire tem= plate. 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 has= hes no longer appears as siblings at the violating Merkle tree level.

Recommended recovery procedure=

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

  1. Record each offending intern= al node preimage.

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

  3. Attempt to repair the block by shuffling transaction order while prese= rving consensus transaction-order constraints.

  4. Recompute the Merkle root and re-ru= n the internal-node preimage check.

  5. If the shuffled template passes, mine the repa= ired template.

  6. If shuffling fails repeatedly, remove one or more transactions con= tributing 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.

<= p dir=3D"ltr" style=3D"line-height:1.38;margin-top:12pt;margin-bottom:12pt"= >The coinbase transaction MUST remain the first transaction in the block.<= /span>

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>

Simple shuffle algorithm<= /span>

A simple repair algorithm is:

1. Keep the coinb= ase fixed at index 0.

2. Build a dependency graph for all non-co= inbase transactions.

3. Generate a randomized topological orderi= ng of the graph.

4. Construct the Merkle tree using that orderin= g.

5. Reject the ordering if any internal node preimage is forbi= dden.

6. Retry with a new randomized topological ordering.


This changes Merkle = sibling relationships without violating in-block transaction dependencies.<= /span>

Repeated failure

If randomized repair fails repeatedly, mining software SHOU= LD remove transactions contributing to the repeated offending subtree.

A reasonable policy is:

If Merkle construction fails af= ter 2 independent shuffle attempts,

remove at least one transact= ion from each repeatedly offending pair or subtree.


For a bottom-level violation, the of= fending subtree usually corresponds to two sibling transaction identifiers:=

txid_A || txid_B

<= br>

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 high= er-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 identif= y a malicious transaction. It only needs to produce a valid block template = with minimal fee loss.

Fe= e impact

The expected fee impact for honest block t= emplates should be negligible because accidental violations are rare.

If an adversary intentionally creates transactions that cause viola= tions when paired, shuffling will usually defeat the attempt without fee lo= ss. If shuffling does not repair the template, removing one or more offendi= ng 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 constru= ction before mining.

Rela= tion to unupgraded miners

Because accidental violat= ions are rare, unupgraded miners are unlikely to encounter the rule during = ordinary operation.

However, an adversary can construct transa= ction pairs intended to trigger the rule under specific sibling placement.<= /span>

Unupgraded miners that do not enforce this rule may mine a blo= ck 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 rando= m.

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

vin_count =3D 0x01<= /p>

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

vout_coun= t =3D 0x01 at the position determined by x

scriptPubKey_len = =3D 4 - x

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


Ignoring , the structural probability is approximately:

5= / 256^3


becaus= e there are five valid (scriptSig_len, scriptP= ubKey_len) splits, and three one-byte constraints:

vin_c= ount

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 mon= ey 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 u= niformly random unsigned 64-bit output value, the probability of being in r= ange is approximately:

(MAX_MONEY + 1) / 2^64

=E2= =89=88 1.1384122811097797e-4

<= br>

Therefore the approximate probability that a random 64-byte p= reimage is structurally valid and has an in-range output value is:

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

=E2=89=88 3.3927332198= 31406e-11


or = approximately:

1 in 29,475,000,000


Random left || left

For an odd-entry duplicated Merkle node, the preimag= e has the form:

left || left


where the first 32 bytes equal the last 32 bytes.<= /span>

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 scri= ptSig_len =3D x

P[vout_count_pos] =3D 0x01

P[scriptpu= bkey_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=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_cou= nt_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 constraints 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 each fixed= x, these are four independent one-byt= e constraints under the random-half model.

Thus the structur= al 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 proba= bility of being in MoneyRange is appro= ximately:

(MAX_MONEY + 1) / 2^64

=E2=89=88 1.1384122= 811097797e-4


So= the approximate probability that a random lef= t || left preimage is 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 probab= ility

A block with n transactions has approximately n - 1 internal Merkle nodes, plus duplicated-node cases depending on tree s= hape.

Using the rough random left= || right estimate:

p =E2=89=88 3.39e-11


A block with 10,000 transactio= ns has approximate accidental violation probability:

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


<= /b>

or roughly:

1 in 2,950,000 blocks


This is a simplified estimate. Actu= al txids are not perfect independent random samples in all cases, duplicate= d nodes have lower estimated probability, and additional implementation det= ails may reduce or alter the rate.

The deployment-relevant con= clusion is:

Honest accidental violations should be rare.<= /p>

Adversarial violations are possible.

Miners must enforce the= rule.


Backward compa= tibility

This is a soft fork. Blocks violating the = new rule were previously valid and become invalid after activation.<= /p>

Unupgraded full nodes may accept violating blocks after activation. A= ctivation therefore requires ordinary soft-fork deployment procedures.

Unupgraded SPV clients remain vulnerable to the legacy proof ambig= uity. SPV clients must update their Merkle proof validation logic to obtain= the benefit of this rule.

Test vectors

Test vectors should include:<= /p>

  1. A block whose transaction Merkle internal node= preimages do not encode minimal 64-byte transactions. The block is valid.<= /span>

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

  3. A block where an internal node preima= ge encodes a minimal 64-byte transaction. The block is invalid.

    <= /li>

  4. A block where an o= dd-entry duplicated preimage h || h en= codes a minimal 64-byte transaction. The block is invalid.

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

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

  5. An = SPV proof for a 64-byte transaction where no branch preimage encodes a mini= mal 64-byte transaction. The proof is accepted if otherwise valid.

Open questions

  1. Should the rule include only the exp= licit 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 pr= e-activation relay policy discourage transaction pairs that can form forbid= den sibling preimages?

  4. Should mining software standardize a recovery procedure = for failed Merkle construction, or should this remain implementation-specif= ic?

  5. Sh= ould SPV proof formats include an explicit version bit indicating branch-pr= eimage 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/2cae3f35-2058-4e41-8fe9-d2ef06259e0dn%40googlegroups.com.
------=_Part_10389_20215392.1781639973748-- ------=_Part_10388_1232895752.1781639973748--