Block hashing algorithm

From Litecoin Wiki
Jump to: navigation, search

When generating litecoins, you hash a block header over and over again, changing it slightly every time. Each iteration results in entirely different hashes. A block header contains these fields: Version, hashPrevBlock, hashMerkleRoot, Time, Bits, Nonce.

See Block header

The body of the block contains the transactions; these are hashed only indirectly through the Merkle root. Transactions aren't hashed directly; therefore hashing a block with a single transaction takes the same amount of effort as hashing a block with 10,000 transactions.

The Bits field is a representation of the current target, using a special floating-point encoding. This encoding uses three bytes for the mantissa, and the leading byte as a base-256 exponent. Only the 5 lowest bits are used.

The Nonce starts at 0 and is incremented for each hash. Whenever it overflows, the extraNonce portion of the generation transaction is incremented, which changes the Merkle root.

Given just those fields, people would frequently generate the exact sequence of hashes as each other and the fastest miner would almost always win. However, it is [almost always] 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 Litecoin addresses. Since your block is different from everyone else's blocks, you are [almost always] guaranteed to produce different hashes. Every hash you calculate has the same chance of winning as every other hash calculated by the network.

Litecoin uses scrypt (with parameters N=1024, r=1, p=1) for computing the proof-of-work hashes which are checked against the target, and SHA-256d (SHA-256 applied twice) for all other purposes. When computing hashes, you need to be particularly careful about byte-order.

The following Python code will calculate the SHA-256d hash of Block 100000. The header is built from the six fields described above, concatenated together as little-endian values in hex notation:

>>> import hashlib
>>> header_hex = ("01000000" +
...   "ae178934851bfa0e83ccb6a3fc4bfddff3641e104b6c4680c31509074e699be2" +
...   "bd672d8d2199ef37a59678f92443083e3b85edef8b45c71759371f823bab59a9" +
...   "7126614f" +
...   "44d5001d" +
...   "45920180")
>>> header_bin = header_hex.decode('hex')
>>> hash = hashlib.sha256(hashlib.sha256(header_bin).digest()).digest()
>>> hash.encode('hex_codec')
'60ce4639bf63532b27e8f8b036b9846f5d2ae18556289f80e38b85a5df4910e1'
>>> hash[::-1].encode('hex_codec')
'e11049dfa5858be3809f285685e12a5d6f84b936b0f8e8272b5363bf3946ce60'

Here is how to compute the scrypt hash of the same block, using the ltc_scrypt module included in P2Pool:

>>> import ltc_scrypt
>>> pow_hash = ltc_scrypt.getPoWHash(header_bin)
>>> pow_hash[::-1].encode('hex_codec')
'000000003b4ba52ab765631e20a04b88cd27f0b66d3509fb2da7781fae6d7901'

Alternatively, using the scrypt package:

>>> import scrypt
>>> pow_hash = scrypt.hash(header_bin, header_bin, 1024, 1, 1, 32)
>>> pow_hash[::-1].encode('hex_codec')
'000000003b4ba52ab765631e20a04b88cd27f0b66d3509fb2da7781fae6d7901'

Note that the scrypt hash, which is a 256-bit number, has many leading zero bits when stored or printed as a big-endian value (leading digits are the most significant digits).

Block explorers usually display hashes in big-endian notation.

Portions of this content was copied from the Bitcoin wiki under the CC-BY-3.0 license.