I agree, i think we should just use nLockTime and make the rule kick in at height 1,983,702 (in about 21 years).
As mentioned earlier, the witness commitment that appears in the coinbase for an empty block where the coinbase witness is all zeroes is aa21a9ed (commitment marker) followed by e2f61c3f71d1defd3fa999dfa36953755c690689799962b48bebd836974e8cf9 (commitment).
Requiring the presence of a commitment doesn’t prevent it from taking any particular value; so it should remain equally useful. Changing the coinbase witness from all zeroes would also change the witness commitment for empty blocks from the constant above, of course.
I don’t think that’s actually possible in a soft-fork friendly way: once you add one commitment widely deployed, adding a second commitment will either prevent those nodes from validating the commitment they could validate (making the second commitment a hard fork, or allowing miners to disable validation of the first commitment on a per-block basis by inventing their own additional commitments), or will require providing a full merkle-path to all but the most recent commitment, which effectively just means publishing all the leaf commitments in each block directly.
I don’t really think it’s much different either way for bitcoind; but I expect many empty blocks are generated via manual scripts in a KISS-manner, in which case bumping the nLockTime to match the BIP34 height commitment is likely a lot easier than adding support for even an all-zero coinbase witness, plus its commitment. So, 
Having a new rule not have any effect until decades in the future seems like a good way to have people not implement it (at all, let alone correctly), and leave it to being a potentially big problem for a future generation, a la Y2K. For a simple change like this, a couple of years’ notice seems much better than ~20 years to me. (For a larger change, perhaps up to five years could be reasonable, or perhaps some similar timespan that matched mining equipment’s expected lifecycle).
1 Like
Huh? If we fix the coinbase witness value to 00000000height, then you cannot start shoving further commitments in it? We could go ahead and make it a merkle tree of commitments where the left-most commitment is required to be 000000height, of course, but that isn’t what I saw proposed here.
Sure, I was referring specifically to the coinbase witness value, which AFAIU currently has no consensus rules (and is only 0s by default behavior of Bitcoin Core).
Indeed, any time you add a new commitment you’ll have to have new nodes give old nodes the contents of the commitments/merkle paths, but that isn’t a soft-fork-incompatible change, rather requires only a P2P extension.
Strongly agree. Also because I’d like to actually write software that is able to more easily look at block heights without looking at stupid scripts in my lifetime 
The idea isn’t to encode the height in the coinbase witness, just to require that the coinbase have some witness. That ensures there’s an OP_RETURN output in every future coinbase that isn’t present in any of the potentially duplicatable existing coinbases.
5 Likes
Ah, fair enough. I’d still very much love to see the nLockTime set to the block height, it makes pulling the block height out of the coinbase transaction simpler, though its not a super critical difference.
I’m not sure if Matt is talking about deserialization being simpler or that compact extraction using a SHA256 midstate would be simpler. The former is pretty obvious—there’s no need to deal with CScript (yay!)—but the later might not be clear, so I’ll briefly describe it: with a consensus-enforced commitment to height in the locktime field, which is the last field in a serialized transaction, I can prove to you that a particular 80-byte header is for block 999999 by giving you the 32-byte sha256 midstate of the coinbase transaction up to the final 1 or 2 chunks, the missing chunks (64 bytes each), and a partial merkle tree for the coinbase transaction (448 bytes or less). You take the midstate and SHA256 iterate over the remaining chunks that commit to the locktime to get the coinbase transaction’s txid. You insert that in the partial merkle tree and verify the tree connects to the merkle root in the block header.
By comparison, to prove that now with the BIP30 height commitment, I need to give you the entire coinbase transaction plus the partial merkle tree (or I need to use a fancier proof system). A coinbase transaction can be up to almost 1 MB, so the worst case proof of header height now is ~1 MB compared to ~700 bytes with a consensus-enforced commitment in locktime.
I can’t think of how that would be useful offhand, but it seems like a nice advantage of the locktime approach.
(Edited: @ajtowns reminded me that SHA256 chunks are 64 bytes, not 32 bytes.)
2 Likes
Do you have a use case in mind where you need the block height but can’t just count the headers? I suppose an air-gapped embedded hardware device could enforce a rule like: “this transaction must exist above a certain height, and I’ll believe it if you give me X cumulative difficulty of surrounding headers”.
IIUC @harding explains how such a proof would be more compact.
This does imply that we should enforce this rule as soon as the soft fork activates and not wait for block 1,983,702.
Perhaps it should activate a (few) year(s) later, if it turns out miners have to do more than just upgrade their node. At first glance I would think getblocktemplate can just take this new rule into account and everything should be fine. But who knows what custom software miners run to process the coinbase transaction.
Here’s a branch (PR to self) that adds -coinbaselocktime and has our mining code set it:
If we end up going for this solution, we could encourage miners to run this well before any activation parameters are set, to figure out if there is a problem we’re not aware of.
I don’t see any reflection here of the discussion on bitcoin-dev regarding block hash malleability. As that discussion presently stands I see no justification for the proposed invalidation of 64 byte transactions. As discussed, there is a much simpler, more efficient, and equally effective resolution that requires no new consensus rule.
In the referenced thread, you wrote:
The only possible benefit that I can see here is the possible very small bandwidth savings pertaining to SPV proofs. I would have a very hard time justifying adding any consensus rule to achieve only that result.
It’s true that the attack against simplified verification can be prevented through proofs that are a maximum of about 400 bytes larger per block in the worse case, which is about a 70% increase in proof size[1]. That doesn’t seem significant in network traffic when many lightweight clients might be using something like BIP157/158 compact block filters that send extra megabytes of data even in the best case. However, that extra 400 bytes per proof could be significant if merkle proofs are being validated in consensus protocols (e.g. after a script upgrade to Bitcoin).
[1] Base proof: 80 byte header + 448 byte partial merkle tree = 528 bytes. Proof with coinbase tx, assuming the coinbase tx is in the left half of the tree and the tx to prove is in the right half of the tree: 80 byte header + 416 bytes partial merkle tree for coinbase tx + 416 bytes partial merkle tree for tx = 912 bytes.
This minor wallet optimization was not even mentioned in the above rationale for the new rule. If the sole objective of the proposed rule was to save a small amount of bandwidth for SPV proofs, we would not be having this discussion. The bandwidth savings was a modest side effect benefit of fixing a perceived consensus-related security issue, which has been shown to be a suboptimal and unnecessary fix. It is not a trivial thing to add a new consensus rule, even with the assuption of a roll-up soft fork. This should not even be under consideration at this point.
The rationale for the new rule starts by describing the vulnerability that affects almost all deployed SPV software. I myself had forgotten the mention in Daftuar’s paper that checking the depth of the coinbase transaction could provide a trustless way for SPV clients to avoid the attack. I’m not sure how many authors of SPV software are aware of that.
My point was that, as a solution, it still leaves something to be desired. It increases the amount of code that needs to be written to verify an SPV proof (the client now needs a way to request a coinbase transaction even if it doesn’t know its txid, and it needs verify the coinbase tx appears in the correct location in the merkle tree and that its initial bytes have the correct structure for a coinbase transaction). I previously mentioned that it inflates proof sizes by about 70%, but I now think it’s greater than that (I think verification of the initial bytes of the coinbase transaction are required, which means the entire coinbase transaction needs to be downloaded to calculate its txid, which can inflate proof size by up to almost 1 MB).
Fixing a vulnerability that affects widely used software, that simplifies the design of future software, and that reduces network (and potentially consensus) bandwidth seems useful to me.
Let’s be absolutely clear about this. The proposed invalidation of 64 byte transactions does not in any way represent a fix to a vulnerability. Valid blocks do not have malleable block hashes.
Nor does it simplify the design of mitigating the invalid block hash caching weakness. Just the opposite, as a mitigation it is far more complex and costly than the existing solution. And note that caching of invalid messages as a DoS optimization is itself counterproductive, as discussed in detail.
In terms of consensus, it adds a pointless and counterproductive rule. It will require validation checks that are not necessary. If you want to argue it as an SPV bandwidth optimization, have at it. But please do not perpetuate this error that it fixes something.
I recall you making similar proclamations during the milk sad disclosure. The intuitive way of using your API was not the secure way to use it. Rather than change your API, you put a single piece of documentation about the insecurity on a page that many API users may never have read. Many other pages of your documentation gave examples that used the API in an insecure way. You believed this was acceptable. Others disagreed.
We have a similar situation with Bitcoin’s merkle trees. They were intended to allow the generation of cryptographically secure transaction inclusion proofs with a single partial merkle branch. Now Bitcoin protocol developers know that is insecure. There’s some limited propagation of that knowledge to downstream developers, but it remains an obscure problem with an abstruse solution. We could content ourselves with the limited documentation we’ve written about it and claim anyone who later loses money due to this problem is the victim of incompetence—or we could carefully weigh the consensus change required to restore the security of the simple, intuitive, and efficient way of generating and verifying transaction inclusion proofs.
Restoring a simple protocol to its originally intended security is a fix, in my opinion.
If you think that making this reference improves your argument, it does not. But it does reflect on you.
No, we do not. You are quite literally arguing in favor of a new and unnecessary CONSENSUS RULE because of “limited propagation of knowledge.”
One thing to note here is that partially verifying merkle trees can have subtle risks; for example if your actual coinbase tx is 400 bytes serialized with an nLockTime of 900,000; it could be that the last four bytes of the txid of the second tx in the block has the value 0x88bf0d00 (901,000 in little endian), at which point the concatenation of the two txids looks something like a 64-byte transaction with an nLockTime of 901,000, and you could give a “valid” merkle proof that the height of the block is 1000 blocks higher than its true height. That problem goes away if the verifier is able to assume that the coinbase tx for a valid block is always greater than 64 bytes (true provided either five or more bytes of extranonce is used, a segwit commitment is included, or the block reward is not burnt) and verifies the provided midstate is not the sha256 initial state.
1 Like
The previously-cited discussion on bitcoin-dev centered on the detection of a malleated block message, for the purpose of caching block invalidity. As justification for the proposal it was argued that the fork allows for (1) earlier and therefore more efficient detection/prevention of block hash malleation, (2) that this is important because of the supposed DoS benefit of caching invalid block hashes, (3) that this would allow a block hash to uniquely identify a block (presumably the block message payload), valid or otherwise.
It was shown in the discussion, and I believe agreed, that these arguments aren’t valid. (1) Detection is presently possible without even parsing beyond the input point of the coinbase tx, whereas prevention via size constraint requires parsing every transaction in the block to determine sizes, (2) caching the hashes of block headers that are determined to represent invalid blocks serves no effective DoS protection purpose, instead opening the node to a disk fill attack (similar to the recent banning vulnerability) that must be mitigated, and (3) this objective is not achieved as duplicated tx hash malleation remains.
These are the aspects that pertain to a node/consensus. As I stated above, one can certainly argue that this fork can simplify/optimize SPV implementation. My point is to exclude the invalid arguments from consideration.
I’ll withdraw this statement, I got a little carried away. It’s worthy of consideration as long as we are clear about the meaningful objectives. Once invalid objectives are discarded it may (or may not) be that other SPV optimizations become more attractive.
3 Likes
According to my quick computations, the average coinbase size for all blocks up to the most recent halving is 256 bytes and starting from segwit activation is 260 bytes. The average Merkle tree depth is 8 and 11 respectively. This implies an average segwit-era download cost of 11*32 + 260 = 612 bytes to validate the Merkle proofs for all txs of a given block (.34 seconds on a 14,400 baud modem).
Given the speeds involved and these averages, basing such a decision on worst case seems unreasonable to me. The largest coinbase in the above BTC history is 31,353 bytes, while the largest in the segwit era is just 6,825 bytes.
Its block hash is a sufficient coinbase identifier.
Another way to fix SPV wallets is to require, along with a Merkle-proof of the inclusion of a transaction E, a Merkle proof for the coinbase transaction. Because building a dual transaction-node for the coinbase transaction requires brute-forcing 225 bits, showing a valid coinbase and its corresponding Merkle inclusion proof is enough to discover the tree height. Both the E branch and the coinbase branch should have equal tree depths. - Leaf-Node weakness in Bitcoin Merkle Tree Design
I recall you making similar proclamations during the milk sad disclosure. The intuitive way of using your API was not the secure way to use it. Rather than change your API, you put a single piece of documentation about the insecurit> y on a page that many API users may never have read. Many other pages of your documentation gave examples that used the API in an insecure way. You believed this was acceptable. Others disagreed.
Come on Dave… this is borderline sheer intellectual dishonesty. I think you’re worth better than that.
I had a look few months on the libibtcoin full report about the milk sad disclosure (and I read previously the milk.sad report from their original authors when it was made available). I could easily point out many places of the Bitcoin Core API, which are weak in terms of usage documentation, and I’m polite. Designing a secure API, both in terms of code and conveying reasonable information on usage to downstream users ain’t an easy task…
We have a similar situation with Bitcoin’s merkle trees. They were intended to allow the generation of cryptographically secure transaction inclusion proofs with a single partial merkle branch. Now Bitcoin protocol developers know that is insecure. There’s some limited propagation of that knowledge to downstream developers, but it remains an obscure problem with an abstruse solution. We could content ourselves with the limited documentation we’ve written about it and claim anyone who later loses money due to this problem is the victim of incompetence—or we could carefully weigh the consensus change required to restore the security of the simple, intuitive, and efficient way of generating and verifying transaction inclusion proofs.
If the crux of the conversation is reestablishing simplified payment verification in a robust fashion as it is described in the whitepaper section 8, I think there is one aspect which is missed in the section by Satoshi, and that has been corroborated by deploying things like bip37. Namely increasing the DoS surface of full-nodes delivering such transaction inclusion proofs, as generating and indexing can be a non-null computing cost for a full-node, already made that observation in the past e.g on the scalability issues of lightweight clients.
In my view, making a consensus change to optimize SPV verification (e.g such as requesting coinbase transaction to be invalid) is still running short of coming first with a paradigm finding an equilibrium for the network economics (what is already the number of available Electrum / BIP157 public servers ? like a x1000 order of magnitude less than IP-distinct full-nodes ?). It can be still be deemed a valuable goal, though I believe we’re missing the wider picture.
This can be reduced by 36 bytes, since a valid coinbase must always contain the null point: 0xffffffff0000000000000000000000000000000000000000000000000000000000000000. As this can be assumed, the segwit-era average download cost to validate all Merkle proofs for a given block would actually be 576 bytes.
It’s also worth pointing out that the associated storage cost is nominally one byte (actually 4 bits) per block, since the only required information is the proven Merkle tree depth.
Another soft-forking solution is to require that a new field “depth” requiring 4 bits is embedded in the block version field. This new fields should specify the Merkle tree depth minus one. By using 4 bits, a a tree of depth 16, containing up to 65K transactions can be specified. Full nodes much check that the actual tree depth matches the value of “depth” given. SPV nodes can check that the “depth” field matches the Merkle branch length received. - Ibid.
I see reasonable arguments on both sides. Thanks everyone for contributing those.
To evaluate whether to include it in a future Consensus Cleanup proposal, i’d like to weigh the remaining pros and cons of making 64 bytes transactions invalid through a soft fork. To do so i’ll list the main pros and cons i can think of and/or were raised by others (notably Dave and Eric above). Then i’ll try to make the best case for each position’s arguments, and provide a rebuttal for some of the points presented when i can.
Please let me know if an argument (or rebuttal) is missing or could be better presented.
Here are the pros:
- Reduces the bandwidth of block inclusion proofs for transactions.
- Eliminates potential risks when implementing an application that verifies such a proof.
And the cons:
- Introduces a non-obvious transaction validity rule.
- Requires a soft fork.
Let’s try to make the best case for each argument, starting with the pros.
This change would allow merkle proofs to be ~50% smaller in both the worst and average cases for a typical 200 bytes transaction [0]. In addition it would remove a large footgun threatening anyone implementing software which needs to verify transaction merkle proofs. This concern is growing since, as network hashrate increases, the price of a fake inclusion proof using this method is decreasing compared to the price of mining an invalid block. This is in addition to the fact this method allows to fake any number of confirmations, compared to a single one by producing an invalid block. Finally, it is important to not only consider lite clients. Proofs of inclusion of a transaction in a block are useful in other, existing or potential, applications. Examples include sidechains, or future Script changes which would allow to check a merkle proof directly in the interpreter.
Here is a list of rebuttals to those specific points:
- Looking at the worst case cost is not a valid way of judging efficiency gains.
- True. But the proof size reduction is (very) similar in the average case.
- Hypothetical future consensus changes should not be taken into account for the purpose of this standalone fix. Because it’s hard to weigh the benefit this usecase brings since we don’t know whether it would ever exist, and simply because the fix could then be bundled with a future soft fork which enables this usecase.
- Sure. Other usecases than lite-client remain though, such as sidechains. It’s also not hard to imagine a Bitcoin-related application could verify a block inclusion proof.
Now, the cons.
All changes to consensus rules bear a cost. The proof size reduction and proof verifier simplification does not meet the bar to be considered as a soft fork. The proof size reduction seems large in proportion, but it’s small in absolute: a few hundred bytes. In addition you need only one per block, so the efficiency improvement decreases quickly as you query proofs for more than one transaction per block. The implementation simplification is also not a given. It removes one non-obvious check to be performed by inclusion proofs verifiers by another that needs to be performed by all validating nodes, which introduces consensus “seam”.
And a list of rebuttals for those:
- Part of the fixed cost of the soft fork itself is compensated by bundling this fix with others. The cost inherent to changing the consensus rules should be weighed against the benefits brought by all the fixes together.
- It’s true making 64 bytes transactions invalid introduces consensus “seam”, but it’s not clear how it’s an issue. It’s a simple and straightforward rule which adds virtually no cost for full nodes to check.
- It’s true that “all transaction sizes that fit in a block are valid except for 64 bytes” is surprising as a rule. But we can’t equate this with “actually merkle proofs for 64 bytes transactions are insecure and you need to be aware of this clever-yet-convoluted workaround of asking for a proof for the coinbase too”. In addition, we can generally expect protocol developers implementing a full node to be more aware of intricacies in the protocol than would be an application developer.
Anything i’m missing?
[0] 200 bytes is a slight over-estimation. The median vsize of transactions using a moving average over the past 1000 days is about 189 vbytes according to transactionfee.info. Calculation assumes a 260 bytes coinbase transaction, not compressed. In the worst case the proof is 80 + 14*32 + 200 = 728 without the coinbase vs 80 + 2*14*32 + 200 + 260 = 1436 with. In the modern average case under the same assumption the proof is 80 + 11*32 + 200 = 1244 without the coinbase vs 80 + 2*11*32 + 200 + 260 = 632 with.
3 Likes