Transactions which spend coinbase outputs early

[DannyHamilton]

- snip -
A while back I proposed a way to expand the header while still maintaining compatibility with existing ASICs (but would require a hard fork and updated mining software). Maybe I can find a link.
- snip -

This one?

https://bitcointalk.org/index.php?topic=626377.msg6963192#msg6963192

SHA-256 handles messages larger than 512 bits by breaking the message into blocks that are 512 bits long.  The first block input is fed into the hashing function and that output (h0) is combined with the second input block and that output (h1) is combined with the third input, etc, etc, until all inputs have been hashed. This is how a message of arbitrary size (even say a 4GB ISO) can be reduced to a single 256 bit value.

The "zeroes" are simply spacing bits.  They could be anything as long as the format of the final block (partial hash not bitcoin blocks) remains the same length and ends with a 32 bit nonce.

The current bitcoin block header is 640 bits long
This means the first 512 bits is hashed and the output of the function is stored h0
The next 128 bits is then hashed with the output of h0 to produce h1.  This is then hashed again because Bitcoin uses SHA256d.

Now ASICS are "dumb" they really have no idea what they are hashing.  Since h0 remains relatively static (the nonce is in the second block), the mining software (local miner) will compute the h0 partial hash and feed that plus the 96 bits in the second block to the ASIC.  The ASIC appends the 32 bit counter (nonce) and computes the hash incrementing internally as needed and returning results.

So to remain compatible with existing ASICS requires two things:
a) a 256 bit h(x) partial hash value
b) the last block (partial hash input) must consist of exactly 96 bits + a 32 bit nonce.

Anything different would result in a format that existing ASICS don't understand.   

The comment about "must be zero do not use" just means it is padding and must be consistent in the protocol it could be anything all zeroes, all ones, ASCII code for "Satoshi Rules 123...." as long as it is 48 bytes long.  There is no actual requirement that the protocol/standard must only use zeroes.  If a different format was used the padding would be smaller or longer to to ensure that 96 bits + a 32 bit nonce are the only elements in the final partial hash.  This way no matter how large you want the header to be it will still hash down to a h(x) partial hash plus 96 bits + a 32 bit nonce and be compatible with existing hardware.

Personally I have considered a change like this but I would propose a modified structure.  I would use a 64 bit nonce in the last segment (replacing the nonce, nonce2, and nonce3).  This would support for miners as powerful as 18,446 PH/s without overflowing the nonce.   The larger nonce field could be supported by existing hardware in a backwards compatible mode in a similar manner to how 32 bit values are stored in 64 bit CPU registers.   The upper 32 bits would simply be zeroed.   The existing miners (who only understand the concept of a 32 bit nonce) would simply hash a value which ends with 00000000 plus a 32 bit nonce.  The local miner (cgminer) could increment the upper 32 bits to provide support for higher hashrate hardware.  In time ASIC developers would release "enhanced" hardware which uses a larger nonce space internally to handle higher throughput.

[1715145517]

1715145517

[TierNolan]

Luckily that is not correct.  A while back I proposed a way to expand the header while still maintaining compatibility with existing ASICs (but would require a hard fork and updated mining software). Maybe I can find a link.  

Changing the merkle tree is easiest if you are going to hard-fork anyway.

The header will eventually need to be updated when the Unix time value overflows the 32 bit integer but we have a 'little' while before that happens.

That is pretty easy to fix without changing the size of the field.  Define the timestamp field as the 4 least significant bytes of the timestamp.  The MSBs can be worked out by selecting the value so that the time step between blocks is smallest.

This will work unless the time between 2 blocks is more than ~70 years.

It needs a protocol fork, but no change to mining equipment.

[DeathAndTaxes]

This one?

https://bitcointalk.org/index.php?topic=626377.msg6963192#msg6963192

Thanks for finding it.  That was the thread.  I think this post is clearer:
https://bitcointalk.org/index.php?topic=626377.msg6975690#msg6975690

[StephenMorse]

If the point is to make getting more work easier by not having to hash 10-20 Kb of coinbase data, then why not just use transaction #2 in the block as the place where the extraNonce is stored rather than transaction #1 (the coinbase tx)? Transaction #2 can just be a really simple transaction with an OP_RETURN output for including extranonce data. Any input signed would have to be signed with SIGHASH_NONE, so that the scriptPubKey with the OP_RETURN output can be modified by the miner.

This essentially makes use of the transaction's malleability to change the merkle root and get more nonce space. Once it's included in the block, though, it's no longer malleable.

In the stratum protocol, this would just mean that the list of hashes that create the merkle branch would just have to be used slightly differently, with the first element being hashed on the left and the rest of the elements being hashed on the right. A new parameter could even be introduced that describes how the merkle branch should be used (the specific left-right pattern), and the default could be all on the right (like for the coinbase).

One downside might be that it means the miners can't look at the coinbase to see that they are getting paid, because they don't even have access to it. But I don't know of any mining programs that actually check the data like that before doing work. Another would be the slight waste of space, but I think this is pretty negligible. The coinbase's input could be seen as a slight waste of space as well, since it could be as small as a few bytes. The extraNonce data has to be put somewhere, may as well put it somewhere that's not connected to a massive transaction.

[DeathAndTaxes]

If the point is to make getting more work easier by not having to hash 10-20 Kb of coinbase data, then why not ...

The 'work' is recreating the merkle tree not the single hash of a single tx.  A change to the tx set will require recomputing the merkle tree.   It really isn't that much of a problem.  If the block header is updated it would be very smart to put a extanonce in the header itself to prevent needing to recompute the merkle tree but hashing even the full merkle tree is not that much of a load compared to the cost of ECDSA validation.  So I would chalk it up as a "it would be nice to do if we are updating the header format anyways".

[StephenMorse]

You don't need to recompute the whole merkle tree, though, just one branch of it (the branch that connects the transaction with the extra nonce in it). Recalculating this requires hashing the transaction with extraNonce updated and 64*(height of merkle tree) bytes. So, updating the merkle root by modifying the 20 kb coinbase transaction in a block with 2000 transactions would require hashing

20,000 + 64*log2(2000) = 20.7 kb

But modifying the extranonce in a transaction of size 300 bytes only requires hashing

300 + 64*log2(2000) = 1 kb

Either way, I haven't seen any numbers that show that a CPU can't recalculate merkle roots as fast as an ASIC can exhaust a whole 2^32 nonce range. Is that actually an issue?

I agree that it would be better to have the extra nonce right in the header to avoid recalculating the merkle root entirely, but while I find the extended header idea interesting, I'm not sure it's in sufficient need that it would be worth all the extra work and support.

Related: http://bitcoin.stackexchange.com/questions/32603/why-didnt-satoshi-make-the-nonce-space-larger

[DeathAndTaxes]

Either way, I haven't seen any numbers that show that a CPU can't recalculate merkle roots as fast as an ASIC can exhaust a whole 2^32 nonce range. Is that actually an issue?

No and probably will not be for sometime if ever.

I agree that it would be better to have the extra nonce right in the header to avoid recalculating the merkle root entirely, but while I find the extended header idea interesting, I'm not sure it's in sufficient need that it would be worth all the extra work and support.

A hard fork and new block header format just to move the extranonce to the header?  No it probably isn't worth it.  My post was more to illustrate that expanding the header is possible while still being backwards compatible with existing ASIC hardware.  Eventually the header will probably need to be updated for one reason or another.