Topic: Redesign of bitcoin block header (Read 2529 times)

IIRC, eldentyrell once used time field to timebomb his FPGA bitstream

From the wordpress article:


Cryptographic hash functions are interesting to me, having learned about them since learning about Bitcoin.  Can you say more about these attacks and the "terribly technical details".  Thanks.

Regretfully (or thankfully, depending on your point of view) this isn't the case. There's a lot of supposedly very new software and hardware that uses short (16- and 32-bit) timestamps. Off the top of my head: in the ATSC & DVB TV standards, lots of physical security hardware/software systems, countless price-sensitive embedded systems (including medical).

Edit: especially the medical field is notorious for implicit and explicit "expiration date"s. They've been using this concept for quite a while now, e.g. by giving expiration dates to completely stable chemical compounds.

Thanks for the correction.  So it is year 2106 not 2036.  I agree hardly a pressing concern but it will be changed eventually.


Well it won't be decided by me regardless, I am just throwing ideas out there.  People can already put arbitrary data in the coinbase field and create the same "problems".  I don't see a "scratchpad" of ~32 bytes in the extended header to support future uses in an optional non breaking manner to be a real concern.  It really isn't a requirement but sometimes a little flexibility can be a good thing.  Merged mining and the solution to duplicate coinbase txs were possible because of the flexibility of the coinbase field.  The optimization (lack of flexibility) is what makes expanding the header now more complex.

Also for information, time_t is a 64-bit field on current boxes, so the bitcoin header is not using a "standard" unix time_t anyway, to the extent that such a thing exists.  I don't think time_t has been a 32-bit value anywhere important since 1995. 

Anyway, we're looking at 2106 (unix epoch exceeds unsigned 32-bit value) not 2038 (unix epoch exceeds signed 32-bit value) before the bitcoin protocol becomes undefined. 

This has already been discussed/dealt with. The timestamp field is meant to be "unsigned int32_t" which gives us additional over fifty years to ponder the proper way to hard fork.

For comparison, Unix time_t has to be signed to remain compatible with the existing programs that compute time differences.

Edit: Whatever you come up with, please do not leave it "undefined". Some jokers will put "This program cannot be run in DOS mode" there to create panic amongst Windows antivirus users. Luke-jr will probably put some prayers into them. Please just demand them to be zeros.

Yeah the more I think about it trying to create a variant of SHA-2 is just a kludge workaround.  The only way forward is either to modify the header without changing the length from 640 bits or to use a hash of an extended header to provide additional space.  In hindsight, it would have been better to use a 64 bit nonce from the beginning.  Bitcoin will need to work around that going forward but sadly no altcoin has done this AFAIK despite me and other bringing it up years ago.  It shows how much innovation has occurred in the altcoin space.  One thing I would point out is that the current bitcoin protocol is undefined after 2106 2038 as that is the limit of the 4 byte signed unsigned UNIX timestamp. Eventually the protocol will need to be updated regardless even if it is nothing more than changing how time is defined.

One other thing i thought of is that if the pool signed the extended header then miners could use this to verify they aren't subject to a MITM attack.  The pool server could someday even use a HSM to handle signing of the extended header to provide enhanced security.  This doesn't eliminate the risk of the pool being malicious but it does attacks involving the DNS system as redirecting miners to an attack server will not allow the attacker to properly sign the extended header.  Sadly with only 24 bytes SECP256k1 can't be used.  

Another potential enhancement to consider would be employing oblivious shares to eliminate any possibility of a withholding attack against mining pools.  This was first proposed by Meni Rosenfeld http://arxiv.org/pdf/1112.4980.pdf

Note: this method was proposed in 2011 and assumes pool shares are always difficulty 1.  The same concept can be applied to variable difficulty shares (and simplified).  The basic concept is that a miner can determine if they have a valid share but not if they have a valid block because an element in computing the hash for the purposes of difficulty validation is not provided to the miner.  A miner will not know when they solve a block only when they solve a share however the miner can compare any future blocks against the extended header_hash to ensure the pool doesn't cheat (if block is published but miners not given credit and it matches the work completed by miner, then miner knows the pool has cheated all miners in the pool).

The original proposal:

I think that this is the winning proposition.  With existing ASICs we can't change the length of the header without making them fail to produce standard SHA256, but we can change its structure to include a hash of the things we can't add (and the things we had to displace to make room for the hash, sigh).   You're right that we have to use the version field as intended; otherwise current clients will produce unimaginable confusion. 

Agreed.  Maybe someone with detailed knowledge of the exact inputs provided to an ASIC can shed some light but I think it is unlikely any ASIC accepts as an input the length of the blockheader and instead works on a fixed assumption of 640 bits.  If the length of the header =/= 640 bits and the protocol expects the hash to be SHA-2 compliant then it would break all existing hardware.  On the other hand if the protocol uses the output of existing ASICs when the header is =/= 640 bits then the hash no longer follows the SHA-2 spec.   Bitcoin would be using a hashing function based on SHA-2 but it would no longer be SHA-2.  

The protocol would expect the final block of the header to be 16 bytes of data followed by 40 bytes of zeroes followed by a static 8 bytes (always 0x0000000000000280).  Of course other uses of SHA-2 function (transactions, pubkeyhash, message digest for signatures, etc) would use the existing "by the spec" version which makes this a pretty ugly hack in my opinion.  Thanks for pointing this out Cryddit as I have been pondering this some time and I forgot all about the length being appended to the padded final block.

Extended Inner Header
There is an alternate way to extend the header that remains compatible with the SHA-2 spec and fixed length of 640 bits imposed by existing hardware.  It would be in the form of an extended header which contains most of the header elements) and a hash of that is added to the "main" header.  It is a little cludgy but it would make the header length the same as what is expected by mining ASICs.  The block header is still 640 bits so the virtual length field is still correct even if miners are using a fixed 640 bit length.

Extended header (can be arbitrary length not bounded by current blockheader size or format)

*Extended header could be defined to be any size.  The SHA-2 spec breaks messages into blocks of 64 bytes.  The trailing block only has room for 55 bytes as the spec requires the message to be appended with a 1 and then sufficient zeroes added to make length of the appended message 56 bytes.  The length of the actual message is appended as an 8 byte unsigned integer.  So final block <=55 bytes of data + 1 byte marker (0x01) + 0 or more zeroed bytes of padding + 8 byte message length


extended_header_hash = SHA-256(extended_header)

Block header (must be exactly 80 bytes and meet the offsets expected by existing hardware)

* A variant would be to use this for some specific purpose.  One option would be to optionally support signing the blockheader.
** I would use the 4 or 8 of the bytes marked AVAILABLE in block 1 to hold a partial hash of the prior block.  This would allow miner software to verify they are at least on the best chain (pool couldn't be circumvented to produce an attack chain).  These 8 bytes are very valuable so there should be some debate on how to best use them.  
*** The nonce64 must be split to maintain compatibility with existing hardware which expects the modifiable elements to be at offset 4 (time) and offset 12 (nonce32).  The purpose for using a larger nonce is that it eliminates the need to change other elements of the block header as a kludge to support more computing power.  To fully increment a 64 bit nonce in 1 second would require a single miner to have > 18,447 PH/s of computing power.  64 bits is probably more than necessary.  Even 48 bit extra nonce would require >281 TH/s to increment in 1 second.  The upper 32 bits of the nonce could be reduced to 16 bits if those 16 bits saved were necessary for another purpose.

On edit: added version to main header as this is necessary so that existing clients are aware the block represents a new incompatible version that they do not support (rather than just incompatible garbage).  Existing clients would be unable to validate the new block version but they could at least notify users ("Incompatible newer version of block detected.  Client upgrade may be required").

As DeathAndTaxes indicates, and for the same reasons both you and he have mentioned, that's almost certainly the case.  So it turns out that the difficulty field can be moved if needed.  

But I'm still concerned about the (virtual) 'length' field at offset 56 in the last block.  If we use existing ASICs, I'm pretty sure they'll continue to hash based on an image of the last block that ends with the length of the current bitcoin header rather than the length of the revised header.  The result will be that bitcoin hashing via ASICs, while still possible, would be according to a variant away from standard SHA256, and various software tools that use standard SHA256 as a building block would need modifications to account for the difference.  

In fact, the first of these would be bitcoind itself, where the SHA256 calls that it sources from SSL would spit out a different hash resulting in an 'invalid block' message.  It would need to implement a "SHA256D_Variant" to avoid an (additional) immediate hard fork.

Obviously we're talking about a hard fork change anyway...

It may only use two bytes but regardless they are in the wrong location.   If the hardware is incrementing the lower two bytes of the time field that would be at offset 6 (full time begins at offset 4).


The difficulty (bits) can be moved without issue.  AFAIK no ASIC hardware uses that.  They return all hashes smaller than the share target which is larger than the block target anyways.  If the only returns results meeting the block difficulty the hardware couldn't be used for pool mining as it would return nothing unless a block was solved.

I don't see the purpose of the partial hash of prior elements.  To verify that would require knowing the prior elements and if the miner knows that the h0 and h1 could be computed directly.  The issue of mining security comes up because pools do NOT provide the full block header and instead only provide the h0 (or in your proposal h1).  With just h1 the partial header hash can't be verified.  Instead I would use a partial hash (least significant 8 bytes) of the prior blockhash.  This would make it possible to a miner to verify they are on the proper chain without the full header.

Some other proposed changes:
* Increase the time value in the second block to 8 bytes to eliminate the year 2038 (and 2106) problem. 
* Add a field to explicitly record the block height

Lastly based on whatever spec is used some amount of padding may be necessary to ensure the last block is exactly 16 bytes in length to preserve backwards compatibility.  In your draft it is 48 bytes but that may vary based on   I wouldn't mandate that the excess space be zeroed but rather indicate it is arbitrary value of fixed length.  This would allow it to be used as a scratchpad to provide soft fork capabilities in the future.  It also may lead to applications that we haven't considered yet. 

It is a nice draft but it will probably take input from multiple sources (including hardware developers) to come up with a finalized spec.

My idea was to leave only the two least significant bytes of the time there (the nonce2 field) since I don't think the hardware take more than two bytes of the field for nonce (random) purposes.
I don't think the hardware uses the time field to keep up with the time. It may use it to add more nonce space.


I don't know a lot about the hardware but I think the difficulty should be read and interpreted by the software, and then sent to the hardware in a more machine-friendly way, such as the number of preceding zeros. Are you sure it is the hardware that interprets difficulty?

That is a good point.  I assumed that the time field was being incremented outside of the hardware (i.e. in cgminer) per ntime rolling but if it is being incremented internally then yes this would need to be a nonce field.  Although less clear it would be possible to extend the nonce to be a 64 bit number using these bytes as the upper 32 bit.  Time could be stored properly in a prior block (using sha definition not bitcoin definition) to avoid the "hack" of using wrong timestamps as a extra nonce.


This is not correct.  If it were the case then a hardware could only be used for solo mining and would never return any result except one that solves a block.  The hardware is fed a lower share difficulty (not part of the actual block structure) and the hardware returns results smaller than that (which by definition also includes all results smaller than the block target).


Correct.

Based on your input about the timestamp field if that is being incremented internally in hardware I would split the 64 bit nonce to be two 32 bit numbers at offset 4 and 12.  This is because we have a limited amount of space in the final block and that would preserve the most bits.  It would give us 8 bytes to improve the security of mining.  Two possibilities for using those bytes would be a partial hash of the prior block which would allow miners to verify their hashpower isn't being used for malicious purpose and/or the elements required for opaque mining (a technique to prevent withholding attacks) however I haven't looked closely to see if that would be possible and still remain backwards compatible.

Final block
Offset 0 - 4 bytes AVAILABLE
Offset 4 - 4 bytes upper 32 bits of nonce64
Offset 8 - 4 bytes AVAILABLE
Offset 12 - 4 bytes lower 32 bits of nonce64

So we gain a larger nonce range and 8 bytes for additional security features while maintaining backwards compatibility with existing hardware.



Correct.  The padding is just used to ensure that the format of the last block remains compatible by ensuring the 64 byte boundaries are observed.  It would be possible to add an entire additional block if you needed more space.


That is a good question.  If that is being appended internally then you are probably right.  This would make Bitcoin a nonstandard variant of SHA-256.

Okay...  What the hardware ASICs get is a hash representing previous 64-byte blocks, and the last block.   In standard SHA256, the last 8 bytes of the last block are used to append a length, so the last block can be at most 56 bytes long.  If it's longer, the standard SHA256 algorithm appends another 64-byte block (padded with more zeros) to hold the length field. 

But existing ASICs are depending heavily on the particular structure of the last block, so there are rules about the last block which you can't change while maintaining compatibility with existing ASICs.

The timestamp at offset 4 (bytes 4 - 7 in the last block) either can't move, or must become an added nonce field, because existing hardware is modifying that location in order to extend the nonce range already, resulting in timestamps on mined blocks that are inaccurate by up to 256 seconds.  Nothing else (except another nonce field) could be modified in that way without destroying the validity of the block. 

The difficulty field at offset 8 (bytes 8 - 12 in the last block) can't move because that's the location that existing ASICs read in order to find out whether the hashes they're coming up with are low enough to win or not.

The nonce field at offset 12 (bytes 12 - 16 in the last block) can't move because ASICs are testing images of the blocks with all possible values there, and will cough out the value to overwrite that location with.

Important values that the hash has to include cannot be located after offset 12 in  the last block because existing ASICs are only reading the first 12 bytes of the last block before they start work to determine what to overwrite bytes 12-16 with (the rest is assumed to be zero-padded out to offset 56, and followed with a constant length field).

Your point that the nonce field at offset 12 could compatibly be an 8 or 16-byte field instead of a 4-byte field is a good one.  Future generations of ASICs could use that, as you say, to support faster hashing without messing with the timestamp field.

But your answer to my original question is that the second 48 bytes of the second block could be used to hold data.  For example, if we wanted to put the (32 byte) Merkle root of the current UTXO set in the header, we could put it there. 

Also, now I have a second question.  Since current ASICs presume they are working on the second=last block, won't they be putting the length of the current rather than the revised block header in at offset 56?  And therefore won't the results deviate from "real" SHA256 when they are used on the third=last block?

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.

Sergio Lerner has made a proposal on his blog for a redesign of the bitcoin block header. 

http://bitslog.wordpress.com/2014/03/18/the-re-design-of-the-bitcoin-block-header/

The intent is to increase security somewhat, (owing to "terribly technical details about the way the hashing algo works") allowing space for some additional information, while leaving the structure compatible with the existing investment in ASICs etc.

I'm interested in this question and would like to hear what people think on reviewing it.

One thing I do not understand is why the last 48 bytes of the second block of his proposed redesign have to remain with "zero, do not use."