Bitcoin Wiki - User contributions [en]

Block hashing algorithm

2014-01-12T00:07:36Z

RomanKnight:

When generating, you constantly hash the block header. The block is also occasionally updated as you are working on it. A block header contains these fields:
{| class="wikitable"
|-
! Field
! Purpose
! Updated when...
! Size (Bytes)
|-
|Version
|Block version number
|You upgrade the software and it specifies a new version
|4
|-
|hashPrevBlock
|256-bit hash of the previous block header
|A new block comes in
|32
|-
|hashMerkleRoot
|256-bit hash based on all of the transactions in the block
|A transaction is accepted
|32
|-
|Time
|Current timestamp as seconds since 1970-01-01T00:00 UTC
|Every few seconds
|4
|-
|Bits
|Current [[target]] in compact format
|The [[difficulty]] is adjusted
|4
|-
|Nonce
|32-bit number (starts at 0)
|A hash is tried (increments)
|4
|}

The body of the block contains the transactions. These are hashed only indirectly through the Merkle root. Because transactions aren't hashed directly, hashing a block with 1 transaction takes exactly the same amount of effort as hashing a block with 10,000 transactions.

The compact format of target is a special kind of floating-point encoding using 3 bytes mantissa, the leading byte as exponent (where only the 5 lowest bits are used) and its base is 256.
Most of these fields will be the same for all users. There might be some minor variation in the timestamps. The nonce will usually be different, but it increases in a strictly linear way. "Nonce" starts at 0 and is incremented for each hash. Whenever Nonce overflows (which it does frequently), the extraNonce portion of the generation transaction is incremented, which changes the Merkle root.

Given just those fields, people would frequently generate the exact same sequence of hashes as each other and the fastest CPU would almost always win. However, it is (nearly) impossible for two people to have the same Merkle root because the first transaction in your block is a generation "sent" to one of ''your'' unique Bitcoin addresses. Since your block is different from everyone else's blocks, you are (nearly) guaranteed to produce different hashes. Every hash you calculate has the same chance of winning as every other hash calculated by the network.

Bitcoin uses: SHA256(SHA256(Block_Header)) but you have to be careful about byte-order.

For example, this python code will calculate the hash of the block with the smallest hash as of June 2011, [http://blockexplorer.com/block/00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d Block 125552]. The header is built from the six fields described above, concatenated together as little-endian values in hex notation:

>>> import hashlib
>>> header_hex = ("01000000" +
"81cd02ab7e569e8bcd9317e2fe99f2de44d49ab2b8851ba4a308000000000000" +
"e320b6c2fffc8d750423db8b1eb942ae710e951ed797f7affc8892b0f1fc122b" +
"c7f5d74d" +
"f2b9441a" +
"42a14695")
>>> header_bin = header_hex.decode('hex')
>>> hash = hashlib.sha256(hashlib.sha256(header_bin).digest()).digest()
>>> hash.encode('hex_codec')
'1dbd981fe6985776b644b173a4d0385ddc1aa2a829688d1e0000000000000000'
>>> hash[::-1].encode('hex_codec')
'00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d'

Note that the actual hash, which is a 256-bit number, has lots of leading zero bits. When stored or printed as a big-endian hexadecimal constant, but it has leading zero bytes and if stored or printed as little-endian, these are the trailing zero bytes. E.g. if interpretation as a string -- lowest (or start of) string address keeps lowest significant byte, thus little-endian.
The output of [http://blockexplorer.com blockexplorer] displays the hash values as big-endians numbers as notation for numbers is usual -- leading digits are the most significant digits read from left to right.

For another example, [http://pastebin.com/bW3fQA2a here] is a version in plain C without any optimization, threading or error checking.

Here is the same example in plain PHP without any optimization.

<?
//This reverses and then swaps every other char
function SwapOrder($in){
$Split = str_split(strrev($in));
$x='';
for ($i = 0; $i < count($Split); $i+=2) {
$x .= $Split[$i+1].$Split[$i];
}
return $x;
}

//makes the littleEndian
function littleEndian($value){
return implode (unpack('H*',pack("V*",$value)));
}

$version = littleEndian(1);
$prevBlockHash = SwapOrder('00000000000008a3a41b85b8b29ad444def299fee21793cd8b9e567eab02cd81');
$rootHash = SwapOrder('2b12fcf1b09288fcaff797d71e950e71ae42b91e8bdb2304758dfcffc2b620e3');
$time = littleEndian(1305998791);
$bits =littleEndian( 440711666);
$nonce = littleEndian(2504433986);

//concat it all
$header_hex = $version . $prevBlockHash . $rootHash . $time . $bits . $nonce;

//convert from hex to binary
$header_bin = hex2bin($header_hex);
//hash it then convert from hex to binary
$pass1 = hex2bin( hash('sha256', $header_bin ) );
//Hash it for the seconded time
$pass2 = hash('sha256', $pass1);
//fix the order
$FinalHash = SwapOrder($pass2);

echo $FinalHash;
?>

[[Category:Technical]]

Talk:Block hashing algorithm

2014-01-11T15:24:25Z

RomanKnight:

What is licensing/copyright information on that code? Public domain?

"Because transactions aren't hashed directly, hashing a block with 1 transaction takes exactly the same amount of effort as hashing a block with 10,000 transactions."

Doesn't it take more effort to calculate the Merkle root for 10,000 transactions than it does than for 1 transaction? Of course, you only have to do this once per block, but it's misleading. It seems you're using "hashing a block" to specifically mean the (iterative) hash calculation, not the process of block generation. I recommend rewording to :

"These are hashed only indirectly through the Merkle root. Because transactions aren't hashed directly, hashing a block with 1 transaction takes exactly the same amount of effort as hashing a block with 10,000 transactions, once the Merkle root of those transactions is calculated." [[User:Therealplato|Therealplato]] 23:41, 28 January 2012 (GMT)

I added PHP code this code will help beginners with what is going on. The code is simple and well documented anyone regardless of PHP knowledge should be able to read this and know how to hash Bitcoins. [[User:RomanKnight|RomanKnight]] 10:23, 11 January 2014 (EST)

Block hashing algorithm

2014-01-11T15:20:17Z

RomanKnight:

When generating, you constantly hash the block header. The block is also occasionally updated as you are working on it. A block header contains these fields:
{| class="wikitable"
|-
! Field
! Purpose
! Updated when...
! Size (Bytes)
|-
|Version
|Block version number
|You upgrade the software and it specifies a new version
|4
|-
|hashPrevBlock
|256-bit hash of the previous block header
|A new block comes in
|32
|-
|hashMerkleRoot
|256-bit hash based on all of the transactions in the block
|A transaction is accepted
|32
|-
|Time
|Current timestamp as seconds since 1970-01-01T00:00 UTC
|Every few seconds
|4
|-
|Bits
|Current [[target]] in compact format
|The [[difficulty]] is adjusted
|4
|-
|Nonce
|32-bit number (starts at 0)
|A hash is tried (increments)
|4
|}

The body of the block contains the transactions. These are hashed only indirectly through the Merkle root. Because transactions aren't hashed directly, hashing a block with 1 transaction takes exactly the same amount of effort as hashing a block with 10,000 transactions.

The compact format of target is a special kind of floating-point encoding using 3 bytes mantissa, the leading byte as exponent (where only the 5 lowest bits are used) and its base is 256.
Most of these fields will be the same for all users. There might be some minor variation in the timestamps. The nonce will usually be different, but it increases in a strictly linear way. "Nonce" starts at 0 and is incremented for each hash. Whenever Nonce overflows (which it does frequently), the extraNonce portion of the generation transaction is incremented, which changes the Merkle root.

Given just those fields, people would frequently generate the exact same sequence of hashes as each other and the fastest CPU would almost always win. However, it is (nearly) impossible for two people to have the same Merkle root because the first transaction in your block is a generation "sent" to one of ''your'' unique Bitcoin addresses. Since your block is different from everyone else's blocks, you are (nearly) guaranteed to produce different hashes. Every hash you calculate has the same chance of winning as every other hash calculated by the network.

Bitcoin uses: SHA256(SHA256(Block_Header)) but you have to be careful about byte-order.

For example, this python code will calculate the hash of the block with the smallest hash as of June 2011, [http://blockexplorer.com/block/00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d Block 125552]. The header is built from the six fields described above, concatenated together as little-endian values in hex notation:

>>> import hashlib
>>> header_hex = ("01000000" +
"81cd02ab7e569e8bcd9317e2fe99f2de44d49ab2b8851ba4a308000000000000" +
"e320b6c2fffc8d750423db8b1eb942ae710e951ed797f7affc8892b0f1fc122b" +
"c7f5d74d" +
"f2b9441a" +
"42a14695")
>>> header_bin = header_hex.decode('hex')
>>> hash = hashlib.sha256(hashlib.sha256(header_bin).digest()).digest()
>>> hash.encode('hex_codec')
'1dbd981fe6985776b644b173a4d0385ddc1aa2a829688d1e0000000000000000'
>>> hash[::-1].encode('hex_codec')
'00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d'

Note that the actual hash, which is a 256-bit number, has lots of leading zero bits. When stored or printed as a big-endian hexadecimal constant, but it has leading zero bytes and if stored or printed as little-endian, these are the trailing zero bytes. E.g. if interpretation as a string -- lowest (or start of) string address keeps lowest significant byte, thus little-endian.
The output of [http://blockexplorer.com blockexplorer] displays the hash values as big-endians numbers as notation for numbers is usual -- leading digits are the most significant digits read from left to right.

For another example, [http://pastebin.com/bW3fQA2a here] is a version in plain C without any optimization, threading or error checking.

Here is same example in plain PHP without any optimization.

<?
//This reverses and then swaps every other char
function SwapOrder($in){
$Split = str_split(strrev($in));
$x='';
for ($i = 0; $i < count($Split); $i+=2) {
$x .= $Split[$i+1].$Split[$i];
}
return $x;
}

//makes the littleEndian
function littleEndian($value){
return implode (unpack('H*',pack("V*",$value)));
}

$version = littleEndian(1);
$prevBlockHash = SwapOrder('00000000000008a3a41b85b8b29ad444def299fee21793cd8b9e567eab02cd81');
$rootHash = SwapOrder('2b12fcf1b09288fcaff797d71e950e71ae42b91e8bdb2304758dfcffc2b620e3');
$time = littleEndian(1305998791);
$bits =littleEndian( 440711666);
$nonce = littleEndian(2504433986);

//concat it all
$header_hex = $version . $prevBlockHash . $rootHash . $time . $bits . $nonce;

//convert from hex to binary
$header_bin = hex2bin($header_hex);
//hash it then convert from hex to binary
$pass1 = hex2bin( hash('sha256', $header_bin ) );
//Hash it for the seconded time
$pass2 = hash('sha256', $pass1);
//fix the order
$FinalHash = SwapOrder($pass2);

echo $FinalHash;
?>

[[Category:Technical]]