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