From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 09 Jun 2026 11:40:01 -0700 Received: from mail-oa1-f60.google.com ([209.85.160.60]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1wX1Ml-0007Bn-9i for bitcoindev@gnusha.org; Tue, 09 Jun 2026 11:40:01 -0700 Received: by mail-oa1-f60.google.com with SMTP id 586e51a60fabf-43d08878f48sf9562646fac.0 for ; Tue, 09 Jun 2026 11:39:59 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1781030393; cv=pass; d=google.com; s=arc-20240605; b=XfNvYTQ51g+xM+Z5J99h+G5imQEjNmtfrFJz0yObdFnHLUHWjBivcHgaB29QP6uTWP Y/zYxysJ5ypeUxaqWNVbp+QVWaY+t5XTvwi7gSOd2DzPVndhMzpSSDDKx/k6bQMCAkB2 R1l3TrNNWEF7QC+UmYfr7Pzgqk5kcBe2RKM9B1sFqRwOsrjdpJnbdUABCXX207rtnfM6 2X4gpVKiE5N/B+wlnT6O41/rvh9utdKDDucEr7Q2B5jdZcJlz0DRfq60j2/0E766baqE H5XvhAftGttEo84SAsQgz96oKFK4vccYrZz8M5n8J7RvWAIxoBF8+VbgsRR21F4dhTv5 UmIw== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:content-transfer-encoding :in-reply-to:from:content-language:references:to:subject :mime-version:date:message-id:sender:dkim-signature; bh=PY1vkQgcZiD5vN/eV5fza+UmmE5vonVqc/T9Lt5jj2E=; fh=u9/2k0HODszv7RoFgdPvhZSzwVZ18w0VZ/9O8ikU6xk=; b=AnKbaVzikhUi0HuuQF/kJaARgkHbhW+Me985rl6PsR6TVmEaqCH//PuXm8s7drRvfx /Z/E3mBkATRDvFvOjviDsJL5hSXZ28v0cnY2ujEUZIG1MTeQ0/uq7q7d9ZhiEPKalemQ 95SNWyG0CLzj51J/aIU/mB82y1Qf2i2Z1AK0llMyJL27Z6lj6q7E9MkrwVCO3UevDyJ3 SAI4EhCA1F1Dih1A5PXnIMy3ZU3mq56ZmL8xdWm4NPCPGhObnS9CH+zcqxUos3mk2lrE +mjssdFmO6IOdRXrdKVy97bq51u+spDfahhnGAv/h9CY4F/LJOmaLtp2+ayGOu5epDuD Y2Cg==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@mattcorallo.com header.s=1781028062 header.b=JgnGZhHN; dkim=pass header.i=@clients.mail.as397444.net header.s=1781028064 header.b=X+PMF3d3; spf=pass (google.com: domain of lf-lists@mattcorallo.com designates 69.59.18.99 as permitted sender) smtp.mailfrom=lf-lists@mattcorallo.com; dmarc=pass (p=NONE sp=REJECT dis=NONE) header.from=mattcorallo.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20251104; t=1781030393; x=1781635193; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:content-transfer-encoding:in-reply-to:from :content-language:references:to:subject:mime-version:date:message-id :sender:from:to:cc:subject:date:message-id:reply-to; bh=PY1vkQgcZiD5vN/eV5fza+UmmE5vonVqc/T9Lt5jj2E=; b=S4Z1ofNXzLaKXkWVavIyZNCF9SfxJeUTQhUCMYXoYoQg36EJCczSKN7G8nKVzhC+DR md0ua8kGydWDnwhFoHnkbdxC7aO1j+NCPWYCJcf7ekCmvrYRjj0Nn9/HienUDDgEawF6 0JhlHSue9aSnQ060nC/zJxMh11QOzRxEgtfv09jJMJIdBD+IUY5vF9Al4/fGeamVij5p LLj/9PaOVE68KaFLL20DQNjd4/BrgTppKN3BEF48Gy6CuG3onCBdAyeg30DCg0eSQeVV +tniNhWC296eWTD0BoKfZyfMuM1RX9OYERECNaKmScnh4oFIW1Ratkqu7dbvIY4bzAaq sOSg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1781030393; x=1781635193; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:content-transfer-encoding:in-reply-to:from :content-language:references:to:subject:mime-version:date:message-id :x-beenthere:x-gm-message-state:sender:from:to:cc:subject:date :message-id:reply-to; bh=PY1vkQgcZiD5vN/eV5fza+UmmE5vonVqc/T9Lt5jj2E=; b=cWq1/A68SphJNiSKfFdYkhwhOtH2C93B0Orfl+iMPSPqvDLxlWBMmtQQjzi3RIdG7M LMBOjhFs1ozwyhVutSkMOfdNnlkkBkRtMoKFBuWLBfiXZFXk6gOhE6ApUeUsUd0UumCD o1U0y2cAJpT/7p52SAY0QXP12i9XO8rPdlmGo5pxZ29jV1zROWK7KoUABUF0cqFJAx8s EpcHokzNDxGgh84SJPTanNqoTr1MUEZ+QjJ7y+tlvKbjaeDofbxwD5oNbKqDYOJ71HsZ bYL/QdeYUIbfJpKjz0+rOC3KWKhVcY/BVPx8+VFWzudtr91W71a0yu4iUXi50q9JDNdj WFpA== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=2; AFNElJ8JBcNGN+gQnhsXJ/BzankYSVS8xxGfrqB2T8Z5KIgMlVOJpwZFckogqfKXLMxHf/hom+V9B6Pb5JnV@gnusha.org X-Gm-Message-State: AOJu0YxzyKD69VJzrDPQfV/RuD9Orv2AIDHFhYZnDM7NRQ6lVteVhchx nGUAk3XEw+UUStcif/0/mqKsl9D6GakUd9i56AwXP8sOvwshZBW4HJOC X-Received: by 2002:a05:6871:147:b0:42c:2042:1652 with SMTP id 586e51a60fabf-4413d8f702dmr12536230fac.24.1781030393026; Tue, 09 Jun 2026 11:39:53 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="AX0PUUcgJnxCd3t/GiCweYIQQsnbj9DKLORGZDLnfKbokJYgxA==" Received: by 2002:a05:6871:cf03:b0:43d:1d34:8bb9 with SMTP id 586e51a60fabf-44109227240ls2690169fac.0.-pod-prod-05-us; Tue, 09 Jun 2026 11:39:48 -0700 (PDT) X-Forwarded-Encrypted: i=2; AFNElJ81gYG05ql42SclZrPFnChJ+WC5uj950vXZpsVAtFh/OkT28SfrQ48OS4jPDpEq130ONiuJVJ05fqj9@googlegroups.com X-Received: by 2002:a05:6808:1a19:b0:486:4bd0:9a18 with SMTP id 5614622812f47-4868dfb0c20mr12763484b6e.40.1781030387823; Tue, 09 Jun 2026 11:39:47 -0700 (PDT) Received: by 2002:a05:6809:10:20b0:486:3611:b101 with SMTP id 5614622812f47-48702263b20msb6e; Tue, 9 Jun 2026 11:30:15 -0700 (PDT) X-Forwarded-Encrypted: i=2; AFNElJ8rUB/1MKLhpqxO+Xb86fQdDvYq5SMmxhlZG9Fe9SVsKo+jb+k+JulNi3V8MRSWf940MckdO40M2fow@googlegroups.com X-Received: by 2002:a05:6a00:1d9e:b0:837:f79d:909 with SMTP id d2e1a72fcca58-842b0fbc2efmr21482136b3a.39.1781029814756; Tue, 09 Jun 2026 11:30:14 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1781029814; cv=none; d=google.com; s=arc-20240605; b=Swp1GVQU0IFkAT8hjd/ghIVa9xALhncYcvfig2azAYS6CG4D9urOJ5c83ulcMTPtiq v0aImG85TbCq7du9XAZlczZxc3+1c4H9YmkmOORFLtC9K0fSZrsu0DTWaekFz9nswjM0 EtS0hO64L5Bygof4+Cs7jheGvRtb7CuUatycsEFLvLrywfZE7SVpNBIfVKycEKNgjvdj Hz87NOc4JrEOmgFoU7xuDoqHqgRDP0lLG380Z9XlRTUfWmAi71v+wQYIl3mSPLXrhfSs r5i5YU9EpmvFIV1I6xlduyYlXBvWIPqcGqi2XcVjHkYaGVhPaxxYcQ1FSZDSH5f6Pvtd uARA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=content-transfer-encoding:in-reply-to:from:content-language :references:to:subject:mime-version:date:message-id:dkim-signature :dkim-signature; bh=mFG9F2SqzDMh04iZmtkjO0iSDbW7Mm2DJapC1rhICyA=; fh=O/m8Qbol2xC9HMOqOMb80/r3SrEmoRMmVLQujFeN570=; b=TO1J8qBsTA0Ki9JmHaE7A4SJ2iPIkgtQRsXSPwc3Ocnaqs4/Kvy9F3OZxV9aSImqkF yXG9N0ZR/y0reCUktcaMeHhNaa7wQkjwer7IXJT60v+pQMEVVQtQevKCN70e9VOQNsnh 3IL2ziCqA3llpAEcrXFtl/Gw59PbCnp5itfXAxfDVZgVQoKrXjVf2D3hB2zK5RXOL7NO 8+XVg6izornBKTkWKjQb/RvQdqgrYRSuBPq1YjTWhbE4dXZIi8xlO3k/LikJnhqh+nqm 4Rcy/RakYkTPEH0Hz+TIYEd6clY7/XOvhjTVI05FipVMbWA1Bn9OjBsXAaV9WHCk/0t4 H77w==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@mattcorallo.com header.s=1781028062 header.b=JgnGZhHN; dkim=pass header.i=@clients.mail.as397444.net header.s=1781028064 header.b=X+PMF3d3; spf=pass (google.com: domain of lf-lists@mattcorallo.com designates 69.59.18.99 as permitted sender) smtp.mailfrom=lf-lists@mattcorallo.com; dmarc=pass (p=NONE sp=REJECT dis=NONE) header.from=mattcorallo.com Received: from mail.as397444.net (mail.as397444.net. [69.59.18.99]) by gmr-mx.google.com with ESMTPS id d2e1a72fcca58-8428233f1ecsi621722b3a.2.2026.06.09.11.30.14 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 09 Jun 2026 11:30:14 -0700 (PDT) Received-SPF: pass (google.com: domain of lf-lists@mattcorallo.com designates 69.59.18.99 as permitted sender) client-ip=69.59.18.99; X-DKIM-Note: Keys used to sign are likely public at X-DKIM-Note: https://as397444.net/dkim/mattcorallo.com and X-DKIM-Note: https://as397444.net/dkim/clients.mail.as397444.net X-DKIM-Note: For more info, see https://as397444.net/dkim/ Received: by mail.as397444.net with esmtpsa (TLS1.3) (Exim) (envelope-from ) id 1wX1DJ-000000054UT-0k9b; Tue, 09 Jun 2026 18:30:13 +0000 Message-ID: <00be6fe9-7178-4069-9722-5595fde55b72@mattcorallo.com> Date: Tue, 9 Jun 2026 14:30:11 -0400 MIME-Version: 1.0 Subject: Re: [bitcoindev] Prohibit Merkle Internal Node Preimages That Encode Minimal 64-Byte Transactions To: jeremy , Bitcoin Development Mailing List References: Content-Language: en-US From: Matt Corallo In-Reply-To: Content-Type: text/plain; charset="UTF-8"; format=flowed Content-Transfer-Encoding: quoted-printable X-Original-Sender: lf-lists@mattcorallo.com X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@mattcorallo.com header.s=1781028062 header.b=JgnGZhHN; dkim=pass header.i=@clients.mail.as397444.net header.s=1781028064 header.b=X+PMF3d3; spf=pass (google.com: domain of lf-lists@mattcorallo.com designates 69.59.18.99 as permitted sender) smtp.mailfrom=lf-lists@mattcorallo.com; dmarc=pass (p=NONE sp=REJECT dis=NONE) header.from=mattcorallo.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.8 (/) Hey Jeremy, While this is certainly an interesting alternative mitigation against some = attacks, the fact that it=20 implies that miners have to change their block-building software to handle = potential malicious=20 transaction selection which can cause them to create invalid blocks seems t= o make this a total=20 nonstarter. Not breaking existing deployed software, including miners who in some cases= have custom=20 block-building logic is obviously an important goal for soft forks. Given t= here's no (known) use of=20 64-byte transactions anywhere (and they've been non-standard for a longggg = time!) its hard to argue=20 banning 64-byte transactions would have any similar issues. As others have = noted, banning 64-byte=20 transactions seems to be a more complete fix as well. Matt On 6/1/26 1:46 PM, jeremy wrote: > Esteemed Colleagues, >=20 > As a result of some of my research on 64-byte transactions, I'd like to d= iscuss an alternative soft=20 > fork proposal that preserves the ability to encode 64-byte transactions w= hile offering protection to=20 > SPV users (who must make a small patch to validate the path property). >=20 > The rule, stated simply, is: >=20 > A block is invalid if any Merkle Tree 64-byte preimage has the exact byte= structure of a minimal=20 > one-input, one-output, witness stripped transaction. >=20 > [With the miracle of GPT,] I've drafted a relatively complete BIP for dis= cussion. >=20 > Happy International Children's Day, >=20 > Jeremy >=20 > p.s. I will later propose potentially a couple other mitigations separate= ly, for discussion as well. >=20 > -------------------------------------------------------------------------= --------------------------- >=20 > BIP: TBD > Layer: Consensus (soft fork) > Title: Prohibit Merkle Internal Node Preimages That Encode Minimal 64-Byt= e Transactions > Author: TBD > Status: Draft > Type: Standards Track > Created: 2026-06-01 > License: BSD-2-Clause >=20 > *Abstract* >=20 > This document specifies a consensus rule that invalidates a block if any = transaction Merkle tree=20 > internal node preimage encodes a minimal 64-byte transaction. >=20 > For each internal Merkle node, Bitcoin computes: >=20 > parent =3D SHA256d(left || right) >=20 > * > * >=20 > where leftand rightare 32-byte hashes. The 64-byte string left || rightis= the internal node preimage. >=20 > After activation, a block is invalid if any such 64-byte preimage has the= exact byte structure of a=20 > minimal one-input, one-output, non-witness transaction. >=20 > This prevents a 64-byte transaction serialization from being malleated in= to an internal Merkle node=20 > preimage in SPV transaction inclusion proofs. It does not make 64-byte tr= ansactions invalid in general. >=20 > *Motivation* >=20 > Bitcoin transaction identifiers and transaction Merkle internal nodes are= both computed with double=20 > SHA256: >=20 > txid =C2=A0 =3D SHA256d(serialized_transaction) >=20 > parent =3D SHA256d(left_child_hash || right_child_hash) >=20 > * > * >=20 > If a valid transaction serialization is exactly 64 bytes, the same byte s= tring can also be=20 > interpreted as the concatenation of two 32-byte Merkle child hashes: >=20 > serialized_transaction =3D left_child_hash || right_child_hash >=20 > * > * >=20 > This creates an ambiguity between a transaction leaf preimage and an inte= rnal node preimage. >=20 > An SPV verifier that accepts a Merkle proof without authenticating the fu= ll tree shape can be made=20 > to accept a proof terminating at an internal node rather than at an actua= l transaction leaf. >=20 > This proposal removes that ambiguity by forbidding Merkle internal node p= reimages that have the only=20 > practical 64-byte transaction encoding shape. >=20 > *SegWit and transaction identifiers* >=20 > Since SegWit activation, Bitcoin transactions have two related identifier= s: >=20 > txid=C2=A0 =3D SHA256d(legacy serialization) >=20 > wtxid =3D SHA256d(witness serialization) >=20 > * > * >=20 > The distinction is important for understanding this proposal. >=20 > A SegWit transaction is serialized on the wire as: >=20 > nVersion >=20 > marker >=20 > flag >=20 > vin >=20 > vout >=20 > witness >=20 > nLockTime >=20 > * > * >=20 > where: >=20 > marker =3D 0x00 >=20 > flag =C2=A0 =3D 0x01 >=20 > * > * >=20 > The marker and flag bytes indicate that witness data is present. >=20 > However, the transaction identifier (txid) is not computed from this witn= ess serialization. Instead,=20 > the txidis computed from the legacy serialization: >=20 > nVersion >=20 > vin >=20 > vout >=20 > nLockTime >=20 > * > * >=20 > with the marker, flag, and witness fields omitted. >=20 > Therefore: >=20 > txid =3D SHA256d(non-witness serialization) >=20 > * > * >=20 > while: >=20 > wtxid =3D SHA256d(full witness serialization) >=20 > * > * >=20 > The transaction Merkle root committed in the block header is built from t= ransaction identifiers=20 > (txids), not witness transaction identifiers (wtxids). >=20 > Consequently: >=20 > Merkle root =3D Merkle(txid_0, txid_1, ..., txid_n) >=20 > * > * >=20 > and not: >=20 > Merkle(wtxid_0, wtxid_1, ..., wtxid_n) >=20 > * > * >=20 > This means that the marker byte (0x00), flag byte (0x01), and witness dat= a never appear in the=20 > transaction Merkle tree committed by the block header. >=20 > SegWit does define a separate witness Merkle tree whose root is committed= through the coinbase=20 > witness commitment, but that witness Merkle tree is distinct from the tra= nsaction Merkle tree=20 > discussed in this proposal. >=20 > As a result, the ambiguity addressed by this proposal concerns only trans= action identifiers (txids)=20 > and the transaction Merkle root. The SegWit marker and flag bytes are irr= elevant to the transaction=20 > Merkle root because they are excluded from txidserialization. >=20 > *Minimal 64-byte transaction shape* >=20 > This proposal is concerned with the serialization used to compute a trans= action's txid. >=20 > For legacy transactions, and for SegWit transactions when computing the t= xid, the serialization=20 > format is: >=20 > 4 bytes =C2=A0 nVersion >=20 > 1 byte=C2=A0 =C2=A0 vin count =3D 0x01 >=20 > 36 bytes=C2=A0 prevout >=20 > 1 byte=C2=A0 =C2=A0 scriptSig length =3D x >=20 > x bytes =C2=A0 scriptSig >=20 > 4 bytes =C2=A0 nSequence >=20 > 1 byte=C2=A0 =C2=A0 vout count =3D 0x01 >=20 > 8 bytes =C2=A0 nValue >=20 > 1 byte=C2=A0 =C2=A0 scriptPubKey length =3D y >=20 > y bytes =C2=A0 scriptPubKey >=20 > 4 bytes =C2=A0 nLockTime >=20 > * > * >=20 > Notably, this serialization does not include: >=20 > marker >=20 > flag >=20 > witness stack >=20 > * > * >=20 > because those fields are excluded from txidcomputation. >=20 > The fixed overhead is: >=20 > 4 + 1 + 36 + 1 + 4 + 1 + 8 + 1 + 4 =3D 60 bytes >=20 > * > * >=20 > Therefore, for total serialized size 64: >=20 > x + y =3D 4 >=20 > * > * >=20 > There are exactly five possible script-length splits: >=20 > scriptSig length=C2=A0 =C2=A0 scriptPubKey length >=20 > 0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 4 >=20 > 1 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 3 >=20 > 2 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 2 >=20 > 3 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 1 >=20 > 4 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 0 >=20 > * > * >=20 > This proposal defines a forbidden Merkle internal node preimage as a 64-b= yte byte string satisfying=20 > one of those five layouts and whose single output value is in the consens= us money range. >=20 > *Specification* >=20 > After activation, a block is invalid if any transaction Merkle internal n= ode preimage encodes a=20 > minimal 64-byte transaction. >=20 > For every internal Merkle parent computation in the transaction Merkle tr= ee: >=20 > parent =3D SHA256d(left || right) >=20 > * > * >=20 > where leftand rightare 32-byte child hashes, define: >=20 > P =3D left || right >=20 > * > * >=20 > The block is invalid if Psatisfies all of the following: >=20 > 1. >=20 > P[4] =3D=3D 0x01. >=20 > 2. >=20 > P[41]is one of 0, 1, 2, 3, 4. >=20 > 3. >=20 > Let x =3D P[41]. >=20 > 4. >=20 > Let sequence_pos =3D 42 + x. >=20 > 5. >=20 > Let vout_count_pos =3D sequence_pos + 4. >=20 > 6. >=20 > Let value_pos =3D vout_count_pos + 1. >=20 > 7. >=20 > Let scriptpubkey_len_pos =3D value_pos + 8. >=20 > 8. >=20 > P[vout_count_pos] =3D=3D 0x01. >=20 > 9. >=20 > P[scriptpubkey_len_pos] =3D=3D 4 - x. >=20 > 10. >=20 > Let locktime_pos =3D scriptpubkey_len_pos + 1 + (4 - x). >=20 > 11. >=20 > locktime_pos + 4 =3D=3D 64. >=20 > 12. >=20 > The 8-byte little-endian integer at P[value_pos..value_pos+7]is in Mo= neyRange. >=20 > Equivalently, the forbidden preimage is a 64-byte serialization of a one-= input, one-output, non-=20 > witness transaction with single-byte CompactSize counts and script length= s, where the two script=20 > lengths sum to 4 and the output value is in range. >=20 > For clarity, "non-witness transaction" here refers to the serialization u= sed for txidcomputation.=20 > Even for SegWit transactions, the transaction Merkle tree uses txids, so = the marker byte, flag byte,=20 > and witness data are excluded. >=20 > This rule applies to every transaction Merkle internal node used to compu= te the block header's=20 > transaction Merkle root. >=20 > *Odd-entry duplication* >=20 > If a Merkle level has an odd number of entries, Bitcoin duplicates the fi= nal hash: >=20 > parent =3D SHA256d(last || last) >=20 > * > * >=20 > The preimage: >=20 > last || last >=20 > * > * >=20 > MUST be checked by the same rule. >=20 > *SPV verification rule* >=20 > An SPV verifier relying on this soft fork MUST reject a Merkle proof if a= ny branch preimage in the=20 > proof encodes a minimal 64-byte transaction under the predicate above. >=20 > For each branch step, the verifier knows: >=20 > 1. >=20 > The current hash. >=20 > 2. >=20 > The sibling hash. >=20 > 3. >=20 > The branch direction. >=20 > It reconstructs: >=20 > P =3D left_child_hash || right_child_hash >=20 > * > * >=20 > The verifier MUST check: >=20 > IsForbiddenMerkleInternalNodePreimage(P) =3D=3D false >=20 > * > * >=20 > for every branch preimage in the proof. >=20 > If any branch preimage passes the forbidden-preimage predicate, the proof= MUST be rejected. >=20 > The verifier still performs the ordinary Merkle path computation and bloc= k header proof-of-work=20 > validation. >=20 > *Rationale* >=20 > The known 64-byte transaction SPV malleability issue requires a byte stri= ng that is both: >=20 > a valid 64-byte transaction serialization >=20 > * > * >=20 > and: >=20 > a transaction Merkle internal node preimage >=20 > * > * >=20 > This proposal forbids that overlap at the Merkle internal node boundary. >=20 > The rule is narrower than invalidating all 64-byte transactions. A 64-byt= e transaction remains valid=20 > unless its exact serialization appears as a transaction Merkle internal n= ode preimage in the same=20 > block's transaction Merkle tree. >=20 > The rule also avoids adding a general transaction validity rule that exis= ts only to protect Merkle=20 > proof semantics. >=20 > *Why SegWit does not eliminate the ambiguity* >=20 > It is sometimes assumed that SegWit automatically removes this ambiguity = because SegWit transactions=20 > contain the marker and flag bytes: >=20 > 00 01 >=20 > * > * >=20 > However, the ambiguity exists at the txidlayer, not at the witness-serial= ization layer. >=20 > The transaction Merkle root in the block header is computed from txids, a= nd txidsare computed from=20 > the serialization that excludes: >=20 > marker >=20 > flag >=20 > witness >=20 > * > * >=20 > Therefore the relevant byte string remains: >=20 > nVersion >=20 > vin >=20 > vout >=20 > nLockTime >=20 > * > * >=20 > exactly as before SegWit. >=20 > The witness serialization affects the wtxid, but the block header's trans= action Merkle root does not=20 > commit to wtxids. >=20 > As a result, the existence of the SegWit marker and flag bytes does not p= revent a txidpreimage from=20 > having the same byte structure as a Merkle internal node preimage. >=20 > The ambiguity addressed by this proposal therefore remains relevant in th= e SegWit era. >=20 > *Contrast with a 64-byte transaction invalidity rule* >=20 > A direct alternative is: >=20 > A transaction is invalid if its serialized size is exactly 64 bytes. >=20 > * > * >=20 > That rule has several advantages: >=20 > 1. >=20 > It is simple to specify. >=20 > 2. >=20 > It is simple for SPV verifiers to implement. >=20 > 3. >=20 > It removes the original ambiguity by eliminating all valid 64-byte tr= ansaction leaves. >=20 > However, it is not correct to describe that rule as automatically fixing = all light clients. >=20 > A 64-byte transaction invalidity rule protects an SPV verifier only if th= e verifier enforces the new=20 > rule when interpreting the claimed transaction. Existing or application-s= pecific SPV verifiers that=20 > merely receive a byte string and a Merkle branch may remain vulnerable if= they do not parse the=20 > claimed transaction and reject exactly-64-byte transaction serializations= . >=20 > More generally, a consensus rule invalidating 64-byte transactions does n= ot prevent arbitrary=20 > internal node preimages from existing. It only prevents those preimages f= rom being valid Bitcoin=20 > transactions under upgraded consensus rules. A bridge, wallet, or deposit= system that accepts SPV-=20 > style proofs but performs incomplete transaction parsing may still be ind= uced to treat an internal=20 > node preimage as an application-level event. >=20 > For example, suppose an application-level SPV verifier treats a proved by= te string as a "deposit" if=20 > some field inside the alleged transaction matches a registered deposit ad= dress, deposit script, or=20 > deposit commitment, but does not fully enforce the upgraded transaction-v= alidity rule. An attacker=20 > may be able to grind child hashes so that: >=20 > left_child_hash || right_child_hash >=20 > * > * >=20 > has bytes that the application interprets as a deposit transaction or dep= osit commitment. In some=20 > systems, the attacker may also be able to choose or register deposit data= that matches bytes already=20 > present in the left-hand side of an internal node preimage. >=20 > This is not a failure of upgraded full-node consensus. It is a failure of= the assumption that=20 > changing full-node transaction validity automatically upgrades every SPV = verifier and every bridge,=20 > wallet, or application that consumes SPV-style proofs. >=20 > Therefore, both approaches require light-client changes: >=20 > 64-byte transaction invalidity: >=20 > =C2=A0=C2=A0Light clients must reject claimed 64-byte transaction serial= izations. >=20 > * > * >=20 > Merkle-internal-node preimage invalidity: >=20 > =C2=A0=C2=A0Light clients must reject proofs containing forbidden intern= al branch preimages. >=20 > * > * >=20 > The 64-byte transaction invalidity rule is simpler for light clients that= correctly implement it,=20 > but it is broader at the transaction layer. This proposal places the rule= at the Merkle ambiguity=20 > boundary and preserves 64-byte transactions generally. >=20 > In summary: >=20 > 64-byte transaction invalidity: >=20 > =C2=A0=C2=A0- Simpler SPV rule when implemented correctly. >=20 > =C2=A0=C2=A0- Broader transaction validity change. >=20 > =C2=A0=C2=A0- Invalidates all 64-byte transactions. >=20 > =C2=A0=C2=A0- Does not automatically fix SPV applications that fail to e= nforce the new rule. >=20 > * > * >=20 > Merkle-internal-node preimage invalidity: >=20 > =C2=A0=C2=A0- Preserves 64-byte transactions generally. >=20 > =C2=A0=C2=A0- Places the rule at the Merkle ambiguity boundary. >=20 > =C2=A0=C2=A0- Requires SPV verifiers to parse all branch preimages. >=20 > =C2=A0=C2=A0- Directly forbids the ambiguous internal-node preimage cond= ition. >=20 > * > Minimal C++ implementation sketch* >=20 > This implementation checks only the minimal forbidden 64-byte shape. It d= oes not invoke the full=20 > transaction deserializer. >=20 > The function returns trueif the 64-byte preimage is forbidden. >=20 > static constexpr int64_t COIN =3D 100000000; >=20 > static constexpr int64_t MAX_MONEY =3D 21000000 * COIN; >=20 > * > * >=20 > static inline bool MoneyRange(int64_t nValue) >=20 > { >=20 > =C2=A0=C2=A0=C2=A0=C2=A0return nValue >=3D 0 && nValue <=3D MAX_MONEY; >=20 > } >=20 > * > * >=20 > static inline uint64_t ReadLE64(const unsigned char* p) >=20 > { >=20 > =C2=A0=C2=A0=C2=A0=C2=A0return uint64_t{p[0]} >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0| (uint64_t{p[1]} << 8) >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0| (uint64_t{p[2]} << 16) >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0| (uint64_t{p[3]} << 24) >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0| (uint64_t{p[4]} << 32) >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0| (uint64_t{p[5]} << 40) >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0| (uint64_t{p[6]} << 48) >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0| (uint64_t{p[7]} << 56)= ; >=20 > } >=20 > * > * >=20 > static bool IsForbiddenMerkleInternalNodePreimage64(const unsigned char p= [64]) >=20 > { >=20 > =C2=A0=C2=A0=C2=A0=C2=A0// Minimal 64-byte legacy transaction shape: >=20 > =C2=A0=C2=A0=C2=A0=C2=A0// >=20 > =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 4 bytes =C2=A0 nVersion >=20 > =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 1 byte=C2=A0 =C2=A0 vin count =3D 0x01 >=20 > =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 36 bytes=C2=A0 prevout >=20 > =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 1 byte=C2=A0 =C2=A0 scriptSig length = =3D x >=20 > =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 x bytes =C2=A0 scriptSig >=20 > =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 4 bytes =C2=A0 nSequence >=20 > =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 1 byte=C2=A0 =C2=A0 vout count =3D 0x0= 1 >=20 > =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 8 bytes =C2=A0 nValue >=20 > =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 1 byte=C2=A0 =C2=A0 scriptPubKey lengt= h =3D y >=20 > =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 y bytes =C2=A0 scriptPubKey >=20 > =C2=A0=C2=A0=C2=A0=C2=A0// =C2=A0 4 bytes =C2=A0 nLockTime >=20 > =C2=A0=C2=A0=C2=A0=C2=A0// >=20 > =C2=A0=C2=A0=C2=A0=C2=A0// Since the fixed overhead is 60 bytes, x + y m= ust equal 4. >=20 > * > * >=20 > =C2=A0=C2=A0=C2=A0=C2=A0if (p[4] !=3D 0x01) { >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0return false; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0} >=20 > * > * >=20 > =C2=A0=C2=A0=C2=A0=C2=A0const unsigned int x =3D p[41]; >=20 > * > * >=20 > =C2=A0=C2=A0=C2=A0=C2=A0switch (x) { >=20 > =C2=A0=C2=A0=C2=A0=C2=A0case 0: >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0if (p[46] !=3D 0x01) ret= urn false; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0if (p[55] !=3D 0x04) ret= urn false; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0break; >=20 > * > * >=20 > =C2=A0=C2=A0=C2=A0=C2=A0case 1: >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0if (p[47] !=3D 0x01) ret= urn false; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0if (p[56] !=3D 0x03) ret= urn false; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0break; >=20 > * > * >=20 > =C2=A0=C2=A0=C2=A0=C2=A0case 2: >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0if (p[48] !=3D 0x01) ret= urn false; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0if (p[57] !=3D 0x02) ret= urn false; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0break; >=20 > * > * >=20 > =C2=A0=C2=A0=C2=A0=C2=A0case 3: >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0if (p[49] !=3D 0x01) ret= urn false; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0if (p[58] !=3D 0x01) ret= urn false; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0break; >=20 > * > * >=20 > =C2=A0=C2=A0=C2=A0=C2=A0case 4: >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0if (p[50] !=3D 0x01) ret= urn false; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0if (p[59] !=3D 0x00) ret= urn false; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0break; >=20 > * > * >=20 > =C2=A0=C2=A0=C2=A0=C2=A0default: >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0return false; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0} >=20 > * > * >=20 > =C2=A0=C2=A0=C2=A0=C2=A0const size_t value_pos =3D 47 + x; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0const uint64_t raw_value =3D ReadLE64(p + value_= pos); >=20 > * > * >=20 > =C2=A0=C2=A0=C2=A0=C2=A0if (raw_value > static_cast(std::numer= ic_limits::max())) { >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0return false; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0} >=20 > * > * >=20 > =C2=A0=C2=A0=C2=A0=C2=A0const int64_t nValue =3D static_cast(ra= w_value); >=20 > * > * >=20 > =C2=A0=C2=A0=C2=A0=C2=A0if (!MoneyRange(nValue)) { >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0return false; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0} >=20 > * > * >=20 > =C2=A0=C2=A0=C2=A0=C2=A0return true; >=20 > } >=20 > * > * >=20 > static bool IsForbiddenMerkleInternalNode( >=20 > =C2=A0=C2=A0=C2=A0=C2=A0const uint256& left, >=20 > =C2=A0=C2=A0=C2=A0=C2=A0const uint256& right) >=20 > { >=20 > =C2=A0=C2=A0=C2=A0=C2=A0unsigned char p[64]; >=20 > * > * >=20 > =C2=A0=C2=A0=C2=A0=C2=A0std::memcpy(p, left.begin(), 32); >=20 > =C2=A0=C2=A0=C2=A0=C2=A0std::memcpy(p + 32, right.begin(), 32); >=20 > * > * >=20 > =C2=A0=C2=A0=C2=A0=C2=A0return IsForbiddenMerkleInternalNodePreimage64(p= ); >=20 > } >=20 > * > * >=20 > A Merkle parent computation then checks the preimage before hashing: >=20 > static uint256 ComputeMerkleParentChecked( >=20 > =C2=A0=C2=A0=C2=A0=C2=A0const uint256& left, >=20 > =C2=A0=C2=A0=C2=A0=C2=A0const uint256& right, >=20 > =C2=A0=C2=A0=C2=A0=C2=A0bool& invalid) >=20 > { >=20 > =C2=A0=C2=A0=C2=A0=C2=A0if (IsForbiddenMerkleInternalNode(left, right)) = { >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0invalid =3D true; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0return uint256{}; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0} >=20 > * > * >=20 > =C2=A0=C2=A0=C2=A0=C2=A0unsigned char p[64]; >=20 > =C2=A0=C2=A0=C2=A0=C2=A0std::memcpy(p, left.begin(), 32); >=20 > =C2=A0=C2=A0=C2=A0=C2=A0std::memcpy(p + 32, right.begin(), 32); >=20 > * > * >=20 > =C2=A0=C2=A0=C2=A0=C2=A0return Hash(Span(p, 64)); >=20 > } >=20 > * > * >=20 > This is the intended minimal rule. It checks the five possible 64-byte on= e-input, one-output=20 > transaction layouts directly. >=20 > *Miner considerations* >=20 > Accidental violations by honest miners are expected to be rare. >=20 > Adversarial violations are possible. An attacker may grind transaction id= entifiers so that two=20 > transactions, if placed as siblings in the transaction Merkle tree, form: >=20 > txid_A || txid_B >=20 > * > * >=20 > which encodes a forbidden minimal 64-byte transaction. >=20 > An attacker may attempt to influence sibling placement by fee rate, packa= ge construction, direct=20 > miner submission, or transaction ordering effects. >=20 > Therefore miners MUST check candidate block templates before mining. Mine= rs MUST NOT rely on=20 > accidental violation probability. >=20 > *Merkle construction failure recovery* >=20 > If a candidate block template violates this rule, the miner usually does = not need to discard the=20 > entire template. The violation is local to one or more internal Merkle no= de preimages: >=20 > left_child_hash || right_child_hash >=20 > * > * >=20 > A miner can usually repair the candidate block by changing transaction or= der so that the offending=20 > pair of child hashes no longer appears as siblings at the violating Merkl= e tree level. >=20 > *Recommended recovery procedure* >=20 > When Merkle root construction fails because an internal node preimage is = forbidden, mining software=20 > SHOULD use the following procedure: >=20 > 1. >=20 > Record each offending internal node preimage. >=20 > 2. >=20 > Identify the transaction subtree contributing to each offending child= hash. >=20 > 3. >=20 > Attempt to repair the block by shuffling transaction order while pres= erving consensus > transaction-order constraints. >=20 > 4. >=20 > Recompute the Merkle root and re-run the internal-node preimage check= . >=20 > 5. >=20 > If the shuffled template passes, mine the repaired template. >=20 > 6. >=20 > If shuffling fails repeatedly, remove one or more transactions contri= buting to the offending > subtree and rebuild the template. >=20 > *Preserving transaction-order constraints* >=20 > A shuffle MUST NOT violate transaction dependency ordering. >=20 > If transaction Bspends an output created by transaction Ain the same bloc= k, then AMUST appear before B. >=20 > The coinbase transaction MUST remain the first transaction in the block. >=20 > Mining software SHOULD shuffle only transactions whose relative order is = not constrained by in-block=20 > dependencies, or use a randomized topological ordering of the block's tra= nsaction dependency graph. >=20 > *Simple shuffle algorithm* >=20 > A simple repair algorithm is: >=20 > 1. Keep the coinbase fixed at index 0. >=20 > 2. Build a dependency graph for all non-coinbase transactions. >=20 > 3. Generate a randomized topological ordering of the graph. >=20 > 4. Construct the Merkle tree using that ordering. >=20 > 5. Reject the ordering if any internal node preimage is forbidden. >=20 > 6. Retry with a new randomized topological ordering. >=20 > * > * >=20 > This changes Merkle sibling relationships without violating in-block tran= saction dependencies. >=20 > *Repeated failure* >=20 > If randomized repair fails repeatedly, mining software SHOULD remove tran= sactions contributing to=20 > the repeated offending subtree. >=20 > A reasonable policy is: >=20 > If Merkle construction fails after 2 independent shuffle attempts, >=20 > remove at least one transaction from each repeatedly offending pair or su= btree. >=20 > * > * >=20 > For a bottom-level violation, the offending subtree usually corresponds t= o two sibling transaction=20 > identifiers: >=20 > txid_A || txid_B >=20 > * > * >=20 > In that case, the miner may remove either tx_Aor tx_B. >=20 > For a higher-level violation, each child hash commits to a subtree contai= ning multiple transactions.=20 > In that case, the miner may: >=20 > 1. Try another dependency-preserving shuffle. >=20 > 2. If the same higher-level violation recurs, remove one transaction from= one child subtree. >=20 > 3. Prefer removing the lowest-feerate removable transaction that does not= force removal of higher-=20 > feerate descendants. >=20 > * > * >=20 > This policy does not need to identify a malicious transaction. It only ne= eds to produce a valid=20 > block template with minimal fee loss. >=20 > *Fee impact* >=20 > The expected fee impact for honest block templates should be negligible b= ecause accidental=20 > violations are rare. >=20 > If an adversary intentionally creates transactions that cause violations = when paired, shuffling will=20 > usually defeat the attempt without fee loss. If shuffling does not repair= the template, removing one=20 > or more offending transactions bounds the miner's exposure. >=20 > The adversary's practical effect is limited to potentially causing some t= ransactions to be omitted=20 > from a candidate block template. The rule prevents upgraded miners from m= ining invalid blocks,=20 > provided miners check the Merkle construction before mining. >=20 > *Relation to unupgraded miners* >=20 > Because accidental violations are rare, unupgraded miners are unlikely to= encounter the rule during=20 > ordinary operation. >=20 > However, an adversary can construct transaction pairs intended to trigger= the rule under specific=20 > sibling placement. >=20 > Unupgraded miners that do not enforce this rule may mine a block that upg= raded nodes reject after=20 > activation. Low accidental probability improves deployment safety but is = not a substitute for miner=20 > enforcement. >=20 > *Probability analysis* >=20 > This section estimates accidental violation probability under simplified = randomness assumptions. >=20 > *Random left || right* >=20 > Assume the 64-byte internal node preimage is uniformly random. >=20 > For the preimage to encode a minimal one-input, one-output 64-byte transa= ction, it must satisfy: >=20 > vin_count =3D 0x01 >=20 > scriptSig_len =3D x, where x =E2=88=88 {0,1,2,3,4} >=20 > vout_count =3D 0x01 at the position determined by x >=20 > scriptPubKey_len =3D 4 - x >=20 > nValue =E2=88=88 [0, MAX_MONEY] >=20 > * > * >=20 > Ignoring nValue, the structural probability is approximately: >=20 > 5 / 256^3 >=20 > * > * >=20 > because there are five valid (scriptSig_len, scriptPubKey_len)splits, and= three one-byte constraints: >=20 > vin_count >=20 > vout_count >=20 > scriptPubKey_len >=20 > * > * >=20 > Numerically: >=20 > 5 / 256^3 =E2=89=88 2.980232238769531e-7 >=20 > * > * >=20 > or approximately: >=20 > 1 in 3,355,443 >=20 > * > * >=20 > Including the output value money range: >=20 > MAX_MONEY =3D 21,000,000 * 100,000,000 >=20 > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=3D 2,100,00= 0,000,000,000 >=20 > * > * >=20 > For a uniformly random unsigned 64-bit output value, the probability of b= eing in range is approximately: >=20 > (MAX_MONEY + 1) / 2^64 >=20 > =E2=89=88 1.1384122811097797e-4 >=20 > * > * >=20 > Therefore the approximate probability that a random 64-byte preimage is s= tructurally valid and has=20 > an in-range output value is: >=20 > (5 / 256^3) * ((MAX_MONEY + 1) / 2^64) >=20 > =E2=89=88 3.392733219831406e-11 >=20 > * > * >=20 > or approximately: >=20 > 1 in 29,475,000,000 >=20 > * > Random left || left* >=20 > For an odd-entry duplicated Merkle node, the preimage has the form: >=20 > left || left >=20 > * > * >=20 > where the first 32 bytes equal the last 32 bytes. >=20 > Let the 32-byte half be: >=20 > A[0..31] >=20 > * > * >=20 > Then: >=20 > P[0..31]=C2=A0 =3D A[0..31] >=20 > P[32..63] =3D A[0..31] >=20 > * > * >=20 > For the same one-input, one-output 64-byte transaction shape: >=20 > P[4]=C2=A0 =3D 0x01 >=20 > P[41] =3D scriptSig_len =3D x >=20 > P[vout_count_pos] =3D 0x01 >=20 > P[scriptpubkey_len_pos] =3D 4 - x >=20 > * > * >=20 > Because positions after byte 31 alias positions in the first half: >=20 > P[i] =3D A[i mod 32] >=20 > * > * >=20 > The relevant positions are: >=20 > vin_count_pos=C2=A0 =C2=A0 =C2=A0 =C2=A0 =3D 4 >=20 > 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 >=20 > vout_count_pos =C2=A0 =C2=A0 =C2=A0 =3D 46 + x=C2=A0 =E2=89=A1 14 + x mod= 32 >=20 > scriptpubkey_len_pos =3D 55 + x=C2=A0 =E2=89=A1 23 + x mod 32 >=20 > * > * >=20 > The constraints are: >=20 > A[4]=C2=A0 =C2=A0 =C2=A0 =3D 0x01 >=20 > A[9]=C2=A0 =C2=A0 =C2=A0 =3D x >=20 > A[14 + x] =3D 0x01 >=20 > A[23 + x] =3D 4 - x >=20 > * > * >=20 > For each fixed x, these are four independent one-byte constraints under t= he random-half model. >=20 > Thus the structural probability is approximately: >=20 > 5 / 256^4 >=20 > =E2=89=88 1.1641532182693481e-9 >=20 > * > * >=20 > or approximately: >=20 > 1 in 858,993,459 >=20 > * > * >=20 > The output value begins at: >=20 > value_pos =3D 47 + x >=20 > * > * >=20 > which aliases to an 8-byte window in the random 32-byte half: >=20 > A[15 + x .. 22 + x] >=20 > * > * >=20 > Using the same simplified independence approximation, the probability of = being in MoneyRangeis=20 > approximately: >=20 > (MAX_MONEY + 1) / 2^64 >=20 > =E2=89=88 1.1384122811097797e-4 >=20 > * > * >=20 > So the approximate probability that a random left || leftpreimage is stru= cturally valid and has an=20 > in-range output value is: >=20 > (5 / 256^4) * ((MAX_MONEY + 1) / 2^64) >=20 > =E2=89=88 1.3252864140005492e-13 >=20 > * > * >=20 > or approximately: >=20 > 1 in 7,545,600,000,000 >=20 > * > Block-level accidental probability* >=20 > A block with ntransactions has approximately n - 1internal Merkle nodes, = plus duplicated-node cases=20 > depending on tree shape. >=20 > Using the rough random left || rightestimate: >=20 > p =E2=89=88 3.39e-11 >=20 > * > * >=20 > A block with 10,000 transactions has approximate accidental violation pro= bability: >=20 > 1 - (1 - p)^9999 =E2=89=88 3.39e-7 >=20 > * > * >=20 > or roughly: >=20 > 1 in 2,950,000 blocks >=20 > * > * >=20 > This is a simplified estimate. Actual txids are not perfect independent r= andom samples in all cases,=20 > duplicated nodes have lower estimated probability, and additional impleme= ntation details may reduce=20 > or alter the rate. >=20 > The deployment-relevant conclusion is: >=20 > Honest accidental violations should be rare. >=20 > Adversarial violations are possible. >=20 > Miners must enforce the rule. >=20 > * > Backward compatibility* >=20 > This is a soft fork. Blocks violating the new rule were previously valid = and become invalid after=20 > activation. >=20 > Unupgraded full nodes may accept violating blocks after activation. Activ= ation therefore requires=20 > ordinary soft-fork deployment procedures. >=20 > Unupgraded SPV clients remain vulnerable to the legacy proof ambiguity. S= PV clients must update=20 > their Merkle proof validation logic to obtain the benefit of this rule. >=20 > *Test vectors* >=20 > Test vectors should include: >=20 > 1. >=20 > A block whose transaction Merkle internal node preimages do not encod= e minimal 64-byte > transactions. The block is valid. >=20 > 2. >=20 > A block containing a 64-byte transaction whose serialization does not= appear as an internal node > preimage. The block is valid. >=20 > 3. >=20 > A block where an internal node preimage encodes a minimal 64-byte tra= nsaction. The block is invalid. >=20 > 4. >=20 > A block where an odd-entry duplicated preimage h || hencodes a minima= l 64-byte transaction. The > block is invalid. >=20 > 5. >=20 > An SPV proof where one branch preimage encodes a minimal 64-byte tran= saction. The proof is rejected. >=20 > 6. >=20 > An SPV proof for a 64-byte transaction where no branch preimage encod= es a minimal 64-byte > transaction. The proof is accepted if otherwise valid. >=20 > *Open questions* >=20 > 1. >=20 > Should the rule include only the explicit minimal 64-byte legacy tran= saction shape above, or > should it call the full consensus transaction deserializer? >=20 > 2. >=20 > Should future transaction serialization changes be required to preser= ve this exact forbidden- > preimage invariant? >=20 > 3. >=20 > Should pre-activation relay policy discourage transaction pairs that = can form forbidden sibling > preimages? >=20 > 4. >=20 > Should mining software standardize a recovery procedure for failed Me= rkle construction, or > should this remain implementation-specific? >=20 > 5. >=20 > Should SPV proof formats include an explicit version bit indicating b= ranch-preimage checking > support? >=20 > --=20 > You received this message because you are subscribed to the Google Groups= "Bitcoin Development=20 > Mailing List" group. > To unsubscribe from this group and stop receiving emails from it, send an= email to=20 > bitcoindev+unsubscribe@googlegroups.com . > To view this discussion visit https://groups.google.com/d/msgid/bitcoinde= v/f97afcc5-54ba-4284-8e9b-=20 > e8c35c7101f6n%40googlegroups.com f97afcc5-54ba-4284-8e9b-e8c35c7101f6n%40googlegroups.com?utm_medium=3Dema= il&utm_source=3Dfooter>. --=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/= 00be6fe9-7178-4069-9722-5595fde55b72%40mattcorallo.com.