Topic: Notes on the use of midstate compression for coinbase transaction commitments (Read 1039 times)

I will add some reasoning about free start pre-image / collisions attacks that makes me think it is less of a problem for this particular use. These are the reasons:

1. The security of pre-image resistance of SHA-256 in bits is 256 bits. If SHA-256 were 100% secure, an attacker that wants to reuse the PoW of another merge-mined block will need to perform 2^256 operations.  This attack will never be practical for SHA-256, even having a free start. There has be no successful practical pre-image attack to any of the once standardized hash functions (including MD5, SHA-1, etc.). The best theoretical pre-image attack to the broken MD5 requires 2^125 operations, which is much more than the current PoW difficulty.

2. A simpler attack is to first try to find two or more free-start collisions in the coinbase, and then create a merge-mined block.  The collision resistance security of SHA-256 is 128 bits.

The best freestart attacks on SHA-1 requires around 2^60 operations and only produce a single collision (it does not extend to create multiple collisions). There is no known free start collision vulnerability in full SHA-256.

As an example, suppose that a full free start collision that requires 2^100 operations is found. That would be devastating for SHA-256, and everyone (including Bitcoin) will start to move away from SHA-256. However, it still won't affect this particular use.

We can assume the Bitcoin proof-of-work will not have more than 100 zero prefix bits for the next 50 years (assuming Moore's law stays true, and performance per watt keeps increasing exponentially, since currently Bitcoin PoW it has around 72 zero bits). And that would be a very positive scenario, as Bitcoin reward will be 4096 times lower, to keep up with the same amount of mining hashing power the Bitcoin will need to be 4096 times more valuable (1 BTC = 1.3M USD) or each block would need to be 400 GB to pay enough fees.

But the operations involved in finding a collision are not equivalent to PoW hash operations (SHA256D). There will be no pre-built optimized ASICs to execute such attack, and the attack will require the use of GPUs. So we can expect another 1000x performance ratio between them (10 bits).
 
3. Generally attacks start being unpractical and then they get slowly better over time, so when an initial vulnerability is found, there is plenty of time to hard-fork. Assuming the attack only produces a single collision, and a successful and immediate attack is found, the consequence would be a short period of very fast blocks (e.g. 1 per second), followed by a difficulty adjustment that will prevent the merged block-chain from growing without limit. That would give plenty of time for a hard-fork, rendering the attack useless.

4. Even if the attack could find many collisions at once, it would be very easy to prevent the reuse of Bitcoin headers by not allowing the repetition of the Bitcoin header in the last 100 mined blocks. Checking the timestamp of the Bitcoin block, and not allowing the use of an old header (e.g. the header timestamp must be not older than 1 hour, or the median timestamp of the last 10 blocks) can also help.

5. The attack would be immediately detected as the coinbase part presented would surely not be a valid coinbase transaction tail.

So I expect that using the mid-state for coinbase compression in merge-mining will not be a problem for the next 50 years. 
 

We're actually doing this in Rootstock. I had the same thoughts about weakening the security of the hash function, but I don't know any successful freestart attack on SHA-256. This is how we handle it:

Rootstock tag Embedding

The embedding consist of a binary tag including the hash of the Rootstock block header, and it must be unique (there should not be a way to create a Bitcoin block that can be associated with two different Rootstock blocks). There is no accepted standard of where a tag for Merge-mining should be located. It can be located in the coinbase field of the coinbase transaction (the first transaction of a block), in the outputs of the coinbase transaction (generally as an OP_RETURN payload), or in the remaining transactions.

Rootstock standarizes that the tag is located in the coinbase transaction. To specify a Rootstock block hash, the coinbase transaction has to include the RSK tag in any part, generally an input or output script. The RSK tag is: ROOTSTOCK:RskBlockHeaderHash
“ROOTSTOCK:” is the ASCII string consisting of the bytes: 524f4f5453544f434b3a
RskBlockHeaderHash is the  hash of the Rootstock Block header in binary format.
The Rootstock tag is meant to be included following the OP_RETURN OP_PUSHDATA1 opcodes, but this is not mandatory.

The following additional restrictions apply:

The number of bytes after RskBlockHeaderHash to the end of the coinbase transaction must be lower or equal to 128 bytes.
The trail of raw bytes must not contain the binary string "ROOTSTOCK:". 52 4f 4f 54 53 54 4f 43 4b 3a
The probability of the RSK tag to appear by chance is negligible, but pool servers must not rule out the possibility of a rogue Bitcoin address included in an output of the coinbase transaction having this pattern, and being used as an attack to break the validity of the merge-mined header.
The limitation on the number of bytes past the tag generally means that the tag is located within the last 4 outputs of the coinbase transaction.
This restriction allows to create a compressed SPV proof for Rootstock that consist of:
The Bitcoin header (80 bytes)
A Merkle Branch to the Coinbase transaction (approximately 320 bytes)
A mid-state of SHA-256 consuming the head of the coinbase transaction (32 bytes)
A 64 byte aligned chunk containing a trail of the coinbase transaction, including the RSK tag (max. 232 bytes). The trail allows to build a proof that the trail belongs to the coinbase transaction as a free-start hash starting with the given mid-state.
Currently the maximum size of a SPV merge-mining proof is 843 bytes.
 
Also we may extend the tag to 22 bytes to prevent a OP_HASH160 OP_EQUALVERIFY from being a possible Rootstock tag.

A GMaxwell says, I suppose this has already been done.

Do you think it should be better to use a short second transaction to store the tag? It requires more space and it requires having mature UTXOs ready to be consumed for this purpose. That complicates everything.

regards

Wikipedia has a list of generic attacks: https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction#Security_characteristics

Merkle damgard construction fragile? How so?

I thought I'd leave a note for posterity related to the reoccurring scheme of using mid-state compression to avoid sending coinbase transactions; as it seems to get reinvented from time to time.  This has been discussed several times scattered about in various places, and I thought it useful to put the folklore understanding in one place.

In Bitcoin today various schemes like P2Pool or UTXO set commitments are suggested that require adding some mandatory data to a coinbase transaction.  To prove the mandatory data is present you must then transmit the whole coinbase transaction.  Coinbase transactions can be large, e.g. in p2pool and Eligius like pools that pay directly or for other reasons. In theory, a coinbase transaction can be upto the size of the whole block.

The reoccurring optimization is to put your mandatory data at the end of the coinbase transaction, and then send a sha256 midstate. The receiver can then complete the hashing with the mandatory data and verify agreement.

I personally think this design is inadvisable because it peels back the black box of the already fragile merkle-damgård construction and may open some novel prefix-extension attacks that no one has thought to check sha2 for... but if it is done, implementations _must_ be very careful to avoid complications from serialization capture. E.g. if you require your last commitment to be a free standing output "OP_RETURN PUSH(data)" someone can instead make their final output "OP_RETURN [other stuff] PUSH__8+4+data+size", and then that output will consume the appended commitment, and then it's possible to send a misleading midstate proof, that would be parsed differently by a midstate only client and implementations that work with the whole coinbase transaction; opening up the avenue to attacks.

Another way of saying it is that due to the use of variable length fields the transaction serialization cannot be read backwards, and so no application using midstate compression-- which inherently hides the front of transaction-- can have any dependency on the serialized structure beyond "ends with these bytes"..

For commitment applications, these problems can be avoided like p2pool does by making your rule be specific to the last N bytes of the transaction (your commitment + nlocktime), regardless of what comes before them (e.g. embedded in another output is fine)... but I  still think it's best to avoid this construction entirely.