From: Chris Stewart <stewart.chris1234@gmail•com>
To: Antoine Poinsot <darosior@protonmail•com>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Update on the Great Consensus Cleanup Revival
Date: Mon, 10 Feb 2025 15:21:59 -0600 [thread overview]
Message-ID: <CAGL6+mFYCKjhD8O1G9diC4pbM=_XubW0YxTfeqyyRpDe9t2fng@mail.gmail.com> (raw)
In-Reply-To: <jiyMlvTX8BnG71f75SqChQZxyhZDQ65kldcugeIDJVJsvK4hadCO3GT46xFc7_cUlWdmOCG0B_WIz0HAO5ZugqYTuX5qxnNLRBn3MopuATI=@protonmail.com>
[-- Attachment #1: Type: text/plain, Size: 13387 bytes --]
Hi everyone! Excited to see this work moving forward. I've taken the
liberty of carving off the 64 byte transaction portion of this proposal and
drafted a BIP. You can view a rendered draft with references here:
https://github.com/Christewart/bips/blob/2024-12-20-64bytetxs/bip-XXXX.mediawiki
<pre>
BIP: ?
Layer: Consensus (soft fork)
Title: Disallow 64 byte transactions
Author: Chris Stewart <stewart.chris1234@gmail•com>
Status: Draft
Type: Specification
License: BSD-3-Clause
Created: ?
</pre>
==Abstract==
This BIP describes the rationale for disallowing transactions that are
serialized to 64 bytes without the transaction's witness.
We describe the weaknesses to the merkle tree included in bitcoin block
headers, various exploits for those weaknesses.
==Motivation==
Bitcoin block headers include a commitment to the set of transactions in a
given
block, which is implemented by constructing a Merkle tree of transaction
id’s
(double-SHA256 hash of a transaction) and including the root of the tree in
the
block header. This in turn allows for proving to a Bitcoin light client
that a
given transaction is in a given block by providing a path through the tree
to the
transaction. However, Bitcoin’s particular construction of the Merkle tree
has
several security weaknesses, including at least two forms of block
malleability
that have an impact on the consensus logic of Bitcoin Core, and an attack on
light clients, where an invalid transaction could be ”proven” to appear in
a block
by doing substantially less work than a SHA256 hash collision would require.
This has been prevented by relay policy since 2018<ref>[
https://github.com/bitcoin/bitcoin/pull/11423/commits/7485488e907e236133a016ba7064c89bf9ab6da3
PR #11423 disallows 64 byte transactions in bitcoin core relay]</ref>
==Specification==
This BIP disallows bitcoin transactions that are serialized to 64 bytes in
length without it's witness.
==Rationale==
=== Block malleability ===
64 byte transactions introduce block malleability. Malicious peers can
construct consensus valid and invalid 64 byte
transactions that have the same serialization as the concatenation of 2
nodes in the merkle tree.
Assume we have a valid bitcoin block with 2 transactions in it -
T<sub>0</sub> and T<sub>1</sub>.
The merkle root for this block is H(T<sub>0</sub>||T<sub>1</sub>).
A user could find a malicious 64 byte transaction T<sub>m</sub> that
serializes to T<sub>0</sub>||T<sub>1</sub>.
Next the malicious user relays the block containing the malicious
T<sub>m</sub> rather than the
valid bitcoin transactions T<sub>0</sub> and T<sub>1</sub>.
==== Block malleability with consensus INVALID transactions ====
The peer receiving the malicious block marks the block as invalid as
T<sub>m</sub>
is not a valid transaction according to network consensus rules.
Other peers on the network receive the valid block containing T<sub>0</sub>
and T<sub>1</sub>
add the block to their blockchain. Peers that receive the invalid block
before the valid block
will never come to consensus with their peers due to the malicious user
finding a collision
within the block's merkle root. Finding this collision approximately 22
bits worth of work<ref>[
https://github.com/Christewart/bips/blob/2024-12-20-64bytetxs/bip-XXXX/2-BitcoinMerkle.pdf
to produce a block that has a Merkle
root which is a hash of a 64-byte quantity that deserializes validly, it’s
enough
to just do 8 bits of work to find a workable coinbase (which will hash to
the first
32 bytes), plus another ≈22 bits of work ((1/5) ∗224, so slightly less) to
find
a workable second transaction which will hash to the second 32 bytes) – a
very
small amount of computation.]</ref>
This attack vector was fixed in 0.6.2<ref>[
https://bitcoin.org/en/alert/2012-05-14-dos#risks CVE-2012-2459]</ref>,
re-introduced in 0.13.x<ref>[https://github.com/bitcoin/bitcoin/pull/7225
#7225]</ref> and patched again in
0.14<ref>[https://github.com/bitcoin/bitcoin/pull/9765 #9765]</ref> of
bitcoin core.
==== Block malleability with consensus VALID transactions ====
Producing a valid bitcoin transaction T<sub>m</sub> that adheres to network
consesnsus
rules requires 224 bits of work<ref>[
https://github.com/Christewart/bips/blob/2024-12-20-64bytetxs/bip-XXXX/2-BitcoinMerkle.pdf
Note that the first transaction in a block must be a coinbase, and as
discussed
above, that largely constrains the first 32 bytes of the first transaction:
only
the 4 version bytes are unconstrained. So it would take at least 28*8= 224
bits
of work to find the first node in a given row of the tree that would match
the
first half of a coinbase, in addition to the amount of work required to
grind the
second half of the transaction to something meaningful (which is much
easier –
only 16 bytes or so are constrained, so approximately 128 bits of work to
find a collision). Of course, any of the rows in the Merkle tree could be
used, but it nevertheless seems clear that this should be computationally
infeasible.]</ref>.
This is computationally and financially expensive but theoretically
possible. This can lead to a persistent chain split on the network.
=== Attack on SPV clients ===
BIP37<ref>[https://github.com/bitcoin/bips/blob/master/bip-0037.mediawiki
BIP37]</ref>provides a partial merkle tree format<ref>[
https://github.com/bitcoin/bips/blob/master/bip-0037.mediawiki#user-content-Partial_Merkle_branch_format
Partial Merkle Tree Format]</ref>
that allows you to verify your bitcoin transaction is included in a merkle
root embedded in a bitcoin block header.
Notably this format does not commit to the height of the merkle tree.
Suppose a (valid) 64-byte transaction T is included in a block with the
property that the second 32 bytes (which
are less constrained than the first 32 bytes) are constructed so that they
collide
with the hash of some other fake, invalid transaction F. The attacker can
fool the SPV client into believing that F
was included in a bitcoin block rather than T with 81 bits<ref>[
https://github.com/Christewart/bips/blob/2024-12-20-64bytetxs/bip-XXXX/2-BitcoinMerkle.pdf
An attacker who can do 81 bits of work (followed by another 40 bits of
work, to
construct the funding transaction whose coins will be spent by this one) is
able
to fool an SPV client in this way.]</ref> of work. This also reduces
implementation complexity of SPV wallets<ref>[
https://delvingbitcoin.org/t/great-consensus-cleanup-revival/710/43 The
steps needed to make sure a merkle proof for a transaction is
secure.]</ref>.
This could be mitigated by knowing the depth of the merkle tree. Requiring
SPV clients to request both the coinbase transaction could mitigate this
attack.
To produce a valid coinbase transaction at the same depth that our fake
transaction F occurs at would require 224 bits of work.
As mentioned above, this is computionally and financially expensive, but
theoretically possible.
==Backward compatibility==
There have been 5 64 byte transactions that have occcurred in the bitcoin
blockchain as of this
writing <ref>[
https://github.com/Christewart/bips/blob/2024-12-20-64bytetxs/64byte-tx-mainnet.txt
64 byte transactions in the bitcoin blockchain]</ref>
With the last transaction
7f2efc6546011ad3227b2da678be0d30c7f4b08e2ce57b5edadd437f9e27a612<ref>[
https://mempool.space/tx/7f2efc6546011ad3227b2da678be0d30c7f4b08e2ce57b5edadd437f9e27a612
Last 64 byte transaction in the bitcoin blockchain]</ref>
occurring at block height 419,606<ref>[
https://mempool.space/block/000000000000000000308f1efc24419f34a3bafcc2b53c32dd57e4502865fd84
Block 419,606]</ref>.
TODO
==Reference implementation==
<source lang="cpp">
/**
* We want to enforce certain rules (specifically the 64-byte transaction
check)
* before we call CheckBlock to check the merkle root. This allows us to
enforce
* malleability checks which may interact with other CheckBlock checks.
* This is currently called both in AcceptBlock prior to writing the block
to
* disk and in ConnectBlock.
* Note that as this is called before merkle-tree checks so must never
return a
* non-malleable error condition.
*/
static bool ContextualBlockPreCheck(const CBlock& block,
BlockValidationState& state, const ChainstateManager& chainman, const
CBlockIndex* pindexPrev)
{
if (DeploymentActiveAfter(pindexPrev, chainman,
Consensus::DEPLOYMENT_64BYTETX)) {
for (const auto& tx : block.vtx) {
if (::GetSerializeSize(TX_NO_WITNESS(tx)) == 64) {
return state.Invalid(BlockValidationResult::BLOCK_MUTATED,
"64-byte-transaction", strprintf("size of tx %s without witness is 64
bytes", tx->GetHash().ToString()));
}
}
}
return true;
}
</source>
https://github.com/bitcoin-inquisition/bitcoin/pull/24/files
== Rationale ==
<references />
==Copyright==
This BIP is licensed under the [https://opensource.org/license/BSD-3-Clause
BSD-3-Clause License].
==Acknowledgements==
Suhas Daftuar, AJ Towns, Sergio Demian Lerner, Greg Maxwell, Matt Corallo,
Antoine Poinsont, Dave Harding and Erik Voskuil
On Wed, Feb 5, 2025 at 6:57 PM 'Antoine Poinsot' via Bitcoin Development
Mailing List <bitcoindev@googlegroups.com> wrote:
> Hi everyone,
>
> A bit over a year ago i started working on revisiting the 2019 Great
> Consensus Cleanup proposal from
> Matt Corallo [0]. His proposal included:
> - making <=64 bytes transactions invalid to fix merkle tree weaknesses;
> - making non-pushonly scriptSigs, FindAndDelete matches, OP_CODESEPARATOR
> and non-standard sighash
> types fail script validation to mitigate the worst case block validation
> time;
> - restrict the nTime field of the first block in each difficulty
> adjustment interval to be no less
> than 600 seconds lower than the previous block's;
>
> I set out to research the impact of each of the vulnerabilities this
> intended to patch, the
> alternative fixes possible for each and finally if there was any other
> protocol bug fix we'd want to
> include if we went through the considerable effort of soft forking Bitcoin
> already.
>
> Later in March i shared some first findings on Delving [1] and advertized
> the effort on this mailing
> list [2]. I also created a companion thread on Delving, kept private, to
> discuss the details of the
> worst case block validation time [3]. As one would expect due to the
> larger design space available
> to fix this issue, this private thread is where most of the discussion
> would happen. Thank you to
> everyone who contributed feedback, insights, ideas and argumented opinions
> on the different issues
> all along the process.
>
> Now i would like to update the broader Bitcoin development community on
> the outcome of this effort.
> I believe a Consensus Cleanup proposal should include the following.
> - A fix for vulnerabilities surrounding the use of timestamps in the
> difficulty adjustment
> algorithm. In particular, a fix for the timewarp attack with a 7200
> seconds grace period as well
> as a fix for the Murch-Zawy attack [4] by making invalid any difficulty
> adjustment period with a
> negative duration.
> - A fix for long block validation times with a minimal "confiscation
> surface", by introducing a
> per-transaction limit on the number of legacy sigops in the inputs.
> - A fix for merkle tree weaknesses by making transactions which serialize
> to exactly 64 bytes
> invalid.
> - A fix for duplicate transactions to supplement BIP34 in order to avoid
> resuming unnecessary BIP30
> validation in the future. This is achieved by mandating the nLockTime
> field of coinbase
> transaction to be set to the height of their block minus 1.
>
> I have started drafting a BIP draft with the detailed specs for this.
>
> Antoine Poinsot
>
>
> [0]
> https://github.com/TheBlueMatt/bips/blob/7f9670b643b7c943a0cc6d2197d3eabe661050c2/bip-XXXX.mediawiki
> [1] https://delvingbitcoin.org/t/great-consensus-cleanup-revival/710
> [2] https://groups.google.com/g/bitcoindev/c/CAfm7D5ppjo/m/bYJ3BiOuAAAJ
> [3] https://delvingbitcoin.org/t/worst-block-validation-time-inquiry/711
> [4]
> https://delvingbitcoin.org/t/zawy-s-alternating-timestamp-attack/1062#variant-on-zawys-attack-2
>
> --
> You received this message because you are subscribed to the Google Groups
> "Bitcoin Development Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to bitcoindev+unsubscribe@googlegroups•com.
> To view this discussion visit
> https://groups.google.com/d/msgid/bitcoindev/jiyMlvTX8BnG71f75SqChQZxyhZDQ65kldcugeIDJVJsvK4hadCO3GT46xFc7_cUlWdmOCG0B_WIz0HAO5ZugqYTuX5qxnNLRBn3MopuATI%3D%40protonmail.com
> .
>
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAGL6%2BmFYCKjhD8O1G9diC4pbM%3D_XubW0YxTfeqyyRpDe9t2fng%40mail.gmail.com.
[-- Attachment #2: Type: text/html, Size: 17129 bytes --]
next prev parent reply other threads:[~2025-02-10 21:23 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-02-05 18:09 'Antoine Poinsot' via Bitcoin Development Mailing List
2025-02-06 21:34 ` Murch
2025-02-06 22:03 ` 'Antoine Poinsot' via Bitcoin Development Mailing List
2025-02-07 13:02 ` Antoine Riard
2025-02-10 16:28 ` 'Antoine Poinsot' via Bitcoin Development Mailing List
2025-02-14 17:40 ` Peter Todd
2025-02-15 21:13 ` Antoine Riard
2025-02-10 21:21 ` Chris Stewart [this message]
2025-02-11 21:20 ` Antoine Riard
2025-02-21 1:22 ` Matt Corallo
2025-02-23 22:35 ` 'Antoine Poinsot' via Bitcoin Development Mailing List
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAGL6+mFYCKjhD8O1G9diC4pbM=_XubW0YxTfeqyyRpDe9t2fng@mail.gmail.com' \
--to=stewart.chris1234@gmail$(echo .)com \
--cc=bitcoindev@googlegroups.com \
--cc=darosior@protonmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox