Re: [bitcoin-dev] Consensus protocol immutability is a feature

[vjudeu <vjudeu@gazeta.pl>]

> Because the above block header format is hashed to generate the `prevBlockHash` for the *next* block, it is almost impossible to change the format without a hardfork.

First, assume that everything should be validated as today to be backward-compatible. For that reason, removing SHA-256 is impossible. Then, notice that breaking SHA-256 would mean that there would be more and more leading zeroes in "prevBlockHash". Breaking SHA-256 fully would mean reaching all zeroes hash. So, the old client would see "prevBlockHash" with all zeroes.

Soft-fork means that previously valid blocks could be invalid, so rules should be more strict. And that means we could have two headers, one for SHA-256 and one for SHA-3. Normally, it would mean that our 80-byte headers would take 160 bytes instead. But we could compress it a little bit if we share some data.

> * `nVersion`: 4 bytes

Version would be some higher number than today and validated as today. It could be shared for both headers.

> * `prevBlockHash`: 32 bytes, SHA2 of previous block.

Previous block hash in SHA-256 would have more and more leading zeroes, so we could reuse them and fill with SHA-3 truncated to N bits. In this way, after fully breaking SHA-256 it would be fully replaced by SHA-3. Until then, first N bits could refer to truncated SHA-3 and the rest to SHA-256. When passing that to old nodes, that bits could be zeroed, but all new nodes should see them and perform SHA-3 validation.

Example:

SHA-2 of some block: 000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f
SHA-3 of the same data: 95587d55da5108290c46bac70b622715ae380ef7a313febcc27aeb1c51a28d90
32 bytes stored for that block: 95587d550019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f

Of course, we should perform SHA-3 on a different data than used for SHA-2, at least merkle root should be recalculated, but it is just an example showing how single 32-byte string could store data for both hash functions.

> * `merkleTreeRoot`: 32 bytes, SHA2 of topmost Merkle tree node.

If SHA-256 would be broken, then we could use single coinbase transaction to prevent doing transactions in the old way. That transaction would contain SHA-3 of the new merkle root, as you mentioned. New nodes could treat that transaction as some kind of annex to the block header, but still doing SHA-2 is needed for backward compatibility. For that reason, storing 32 bytes for SHA-2 and 32 bytes for SHA-3 is needed, unless we have some fast way to get hash with all zeroes, then we can save that 32 bytes.

> * `nTime`: 4 bytes, miner-imagined time.

Time should be the same in both headers, so there is no need to duplicate it.

> * `nBits`: 4 bytes, encoded difficulty target

Difficulty should be different for SHA-2 and SHA-3. Finally when SHA-256 would be broken, we could reach 03000000 for SHA-256 and store only SHA-3 difficulty.

> * `nonce`: 4 bytes, random number with no other meaning.

Nonce should be also different for SHA-2 and SHA-3. If SHA-256 would be fully broken, it could be set to zero for SHA-2 and stored only for SHA-3.

On 2021-05-23 20:12:00 user ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
> Good morning vjudeu,
> 
> > > Perhaps the only things that cannot be usefully changed in a softfork is the block header format and how proof-of-work is computed from the block header.
> >
> > Why not? I can imagine a soft fork where the block header would contain SHA-256 and SHA-3 hashes in the same place. The SHA-256 would be calculated as-is, but the SHA-3 would be truncated only to cover zero bits in SHA-256 hashes. In this way, if SHA-256 would be totally broken, old nodes would see zero hashes in the previous block hash and the merkle tree hash, but the new nodes would see correct SHA-3 hashes in the same place. So, for example if we have 1d00ffff difficulty, the first 32-bits would be zeroes for all old nodes, but all new nodes would see SHA-3 truncated to 32-bits in the same place. The difficulty could tell us how many zero bits we should truncate our SHA-3 result to. Also, in the same way we could introduce SHA-4 in the future as a soft-fork if SHA-3 would be broken and we would see many zero bits in our mixed SHA-256 plus SHA-3 consensus.
> 
> I do not think I follow.
> 
> The block header has a Merkle tree root that is a SHA-256 of some Merkle tree node, is that what you refer to?
> Do you mean the same Merkle tree node has to hash to some common value in both SHA-2 and SHA-3?
> 
> Or do you refer to the `prevBlockHash`?
> Do you mean the same `prevBlockHash` has to somehow be the same, for some number of bits, in both SHA-2 and SHA-3?
> 
> More specifically:
> 
> * `nVersion`: 4 bytes
> * `prevBlockHash`: 32 bytes, SHA2 of previous block.
> * `merkleTreeRoot`: 32 bytes, SHA2 of topmost Merkle tree node.
> * `nTime`: 4 bytes, miner-imagined time.
> * `nBits`: 4 bytes, encoded difficulty target
> * `nonce`: 4 bytes, random number with no other meaning.
> 
> What do you refer to?
> 
> Because the above block header format is hashed to generate the `prevBlockHash` for the *next* block, it is almost impossible to change the format without a hardfork.
> 
> Regaards,
> ZmnSCPxj
> 
> >
> > On 2021-05-23 13:01:32 user ZmnSCPxj via bitcoin-dev bitcoin-dev@lists.linuxfoundation.org wrote:
> >
> > > Good morning Jorge, et al,
> > >
> > > > Hardforks can be useful too.
> > > > But, yes, I agree softforks are preferable whenever possible.
> > >
> > > I think in principle the space of possible softforks is very much wider than can be trivially expected.
> > > For instance, maaku7 once proposed a softfork that could potentially change the block discovery rate as a softfork.
> > > Although this required exploiting a consensus bug that has since been closed.
> > > The example of SegWit shows us that we can in fact create massive changes to the transaction and block formats with a softfork.
> > > For example, it is possible to change the Merkle Tree to use SHA3 instead, in a softfork, by requiring that miners no longer use the "normal" existing Merkle Tree, but instead to require miners to embed a commitment to the SHA3-Merkle-Tree on the coinbase of the "original" block format, and to build "empty" SHA2-Merkle-Trees containing only the coinbase.
> > > To unupgraded nodes it looks as if there is a denial-of-service attack permanently, while upgraded nodes will seek blocks that conform to the SHA3-Merkle-Tree embedded in the coinbase.
> > > (Do note that this definition of "softfork" is the "> 50% of miners is enough to pull everyone to the fork".
> > > Some thinkers have a stricter definition of "softfork" as "non-upgraded nodes can still associate addresses to values in the UTXO set but might not be able to detect consensus rules violations in new address types", which fits SegWit and Taproot.)
> > > (In addition, presumably the reason to switch to SHA3 is to avoid potential preimage attacks on SHA2, and the coinbase is still in a SHA2-Merkle-Tree, so... this is a bad example)
> > > Perhaps the only things that cannot be usefully changed in a softfork is the block header format and how proof-of-work is computed from the block header.
> > > But the flexibility of the coinbase allows us to hook new commitments to new Merkle Trees to it, which allows transactions to be annotated with additional information that is invisible to unupgraded nodes (similar to the `witness` field of SegWit transactions).
> > >
> > > Even if you do have a softfork, we should be reminded to look at the histories of SegWit and Taproot.
> > > SegWit became controversial later on, which delayed its activation.
> > > On the other hand, Taproot had no significant controversy and it was widely accepted as being a definite improvement to the network.
> > > Yet its implementation and deployment still took a long time, and there was still controversy on how to properly implement the activation code.
> > > Any hardforks would not only have to go through the hurdles that Taproot and SegWit had to go through, but will also have to pass through the much higher hurdle of being a hardfork.
> > > Thus, anyone contemplating a hardfork, for any reason, must be prepared to work on it for several years before anyone even frowns and says "hmm maybe" instead of everyone just outright dismissing it with a simple "hardfork = hard pass".
> > > As a simple estimate, I would assume that any hardfork would require twice the average amount of engeineering-manpower involved in SegWit and Taproot.
> > > (this assumes that hardforks are only twice as hard as softforks --- this estimate may be wrong, and this might provide only a minimum rather than an expected average)
> > > There are no quick solutions in this space.
> > > Either we work with what we have and figure out how to get around issues with no real capability to fix them at the base layer, or we have insight on future problems and start working on future solutions today.
> > > For example, I know at least one individual was maintaining an "emergency" branch to add some kind of post-quantum signature scheme to Bitcoin, in case of a quantum break.
> > > Regards,
> > > ZmnSCPxj
> > >
> > > bitcoin-dev mailing list
> > > bitcoin-dev@lists.linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 
> 
>