Understanding Bitcoin mining & difficulty for fun and no profit
This post is for understanding the particulars of mining a block from the Bitcoin network. It assumes you have read Ken Shirrif’s post on the subject and have a vague understanding of it. If some of the details behind the Python mining simulator seemed a bit rushed, that’s what this post will attempt to ramify.
I will also attempt to make some of the details in the difficulty wiki article a bit more clear, so it’s worth giving that a skim.
Ken posted a small Python program to simulate how mining works here. He doesn’t really go into the details, so I did, and I’d like to share.
I will go through the code line by line, explaining what it does. After that I plan to convert the code to Ruby, using (I think) better naming conventions and function abstraction.
import hashlib, struct ver = 2 prev_block = "000000000000000117c80378b8da0e33559b5997f2ad55e2f7d18ec1975b9717" mrkl_root = "871714dcbae6c8193a2bb9b2a69fe1c0440399f38d94b3a0f1b447275a29978a" time_ = 0x53058b35 # 2014-02-20 04:57:25 bits = 0x19015f53 # https://en.bitcoin.it/wiki/Difficulty exp = bits >> 24 mant = bits & 0xffffff target_hexstr = '%064x' % (mant * (1<<(8*(exp - 3)))) target_str = target_hexstr.decode('hex') nonce = 0 while nonce < 0x100000000: header = ( struct.pack("<L", ver) + prev_block.decode('hex')[::-1] + mrkl_root.decode('hex')[::-1] + struct.pack("<LLL", time_, bits, nonce)) hash = hashlib.sha256(hashlib.sha256(header).digest()).digest() print nonce, hash[::-1].encode('hex') if hash[::-1] < target_str: print 'success' break nonce += 1
Let’s get started.
ver = 2
This is simply the Bitcoin protocol version being used.
prev_block = "000000000000000117c80378b8da0e33559b5997f2ad55e2f7d18ec1975b9717"
Hopefully you have a basic understanding of the goal of mining - to find an acceptable hash (essentially) of a block. This is that hash, of the block before this one in the Blockchain. It is the end result of this post, for the previous block.
mrkl_root = "871714dcbae6c8193a2bb9b2a69fe1c0440399f38d94b3a0f1b447275a29978a"
The Merkle Root deserves a post in itself, but James D'Angelo explains it pretty damn well. If you don’t feel like diving in, imagine the Merkle Root as the unique representation of all of transactions in this block. It is (essentially) a hash of all of the transactions in the block.
time_ = 0x53058b35 # 2014-02-20 04:57:25
This is simply the standard unix timestamp of the date shown. Why did he choose to show it in hex? Probably because everything else it in hex. Same output though! (1392872245 in unix time).
bits = 0x19015f53
This is a ‘packed’ representation of difficulty. This is stored on the block. This is what is given to every miner in the network. In order to understand what miners do with this (they all must do the same thing) we have to dive into some formulas that may seem alarming, but really aren’t.
When you think about Bitcoin ‘difficulty’, you have to remember what miners are trying to achieve. They want to find the hash of this block + some random number that (in base16) is less than the target (the target is just another 256bit base16 number, that gets lower every block as the network adds more difficulty).
The target at the time of writing this is
00000000000000003AAEA2000000000000000000000000000000000000000000 in base16, or
1438882362326364789097016808333128944459434864174551793664 in base10.
So if a miner gets the number (in base10)
1438882362326364789097016808333128944459434864174551793664 + 1, he did not succeed and must try again, and again, and again…….
But the miner isn’t given the target. He’s given the packed representation
0x19015f53. To get a target hex string, the formula is as follows. Let’s say the packed version,
P. The first two numbers in
19. From hex -> base10, that’s 25 (
F). The rest of the numbers in
015f53. From hex -> base10 that’s 89939 (
R * (2 ** (8 * (F - 3)))
The explanation for the above formula will be covered in a later blog post. This gives you, in 256 bit hex string:
This is the target for the given block.
8614444778121073626993210829679478604092861119379437256704 in base10.
‘Difficulty’ itself is just a ratio of the easiest target that ever was (also the highest target that ever was, as targets’ value are getting smaller and smaller) to the current target (the hardest target that ever was).
Easiest target ever, for the Genesis Block was
00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF which in base10 is
Largest, easiest target / Smallest, hardest target
which for this block was
3129573174 base10. But this number doesn’t really mean anything unless you know where it comes from.
# https://en.bitcoin.it/wiki/Difficulty exp = bits >> 24
F from above? This is the computational way of removing the first two numbers from
bits. You end up with the same answer. This is a right bitwise shift which converts bits to, well bits, then shifts the bits over 24 places.
Then shift it to the right…
25, which is
0x19, which is the first two numbers in
mant = bits & 0xffffff
Maybe you guessed this is
R, the value of the rest of the numbers. How does this work? This a bitwise &.
0x19015f53 in binary ->
0xffffff in binary (same length) ->
Put the first over the second and take each column and & them. So only if they are both ones do you get a 1 in the result. Because the first 8 bits in the second number are 0s, those numbers get removed. Each character in the hex number is 4 bits, so it’s same as removing the first 2 numbers/characters from the hex.
00011001000000010101111101010011 00000000111111111111111111111111 _______________________________ 00000000000000010101111101010011
target_hexstr = '%064x' % (mant * (1<<(8*(exp - 3))))
This is essentially the same formula as stated above. It may look a bit different. First, dismiss the
'%064x' % - this just means format the number you get as a 64character string, with padding 0s at the beginning, interpreted as hexadecimal. Easy.
1 << x is the same as raising 2 to
x. Don’t believe me? Work it out! Faster for the processor, says the internets.
target_str = target_hexstr.decode('hex')
Here we are taking a hex string like ‘9f’ and turning that into a hex byte string. In this case, the hex string is
00000000000000015f5300000000000000000000000000000000000000000000 and we turn that into
nonce = 0
The holy grail! The nonce. As you’ll see below - the miner is trying to concatenate all of these pieces of the puzzle together in a certain way (which will remain the same for him). His extra seasoning is the nonce, which is just a number added to the end in attempt to make that random SHA256 machine make a number below the target.
The code below just loops over nonces until it finds a solution - it’s a bit messy. So I’m going to show my Ruby code immediately after - hopefully it clears everything up.
while nonce < 0x100000000: header = ( struct.pack("<L", ver) + prev_block.decode('hex')[::-1] + mrkl_root.decode('hex')[::-1] + struct.pack("<LLL", time_, bits, nonce)) hash = hashlib.sha256(hashlib.sha256(header).digest()).digest() print nonce, hash[::-1].encode('hex') if hash[::-1] < target_str: print 'success' break nonce += 1
Some methods to make things easier to read:
require 'digest/sha2' def sha256(str) (Digest::SHA256.new << str).digest end def little_endian_bytestr(*args) #just pack every arg together, using little endian args.pack(('L' * args.size) + '<') end def hex_str_to_hex_bytestr(str) [str].pack('H*') end def hex_bytestr_to_hex_str(bytestr) bytestr.unpack('H*').first end def first_byte(bytes) bytes.to_s(16)[0..1].hex # AKA `bytes >> (4 * ((# OF BYTES) - 2))` end def rest_bytes(bytes) bytes.to_s(16)[2..-1].hex # AKA bytes >> 0xffffff (# of fs is determined by (# bytes - 2)) end def zero_padded_256bit_str(num) '%064x' % num end
And here’s the meat of it.
version = 2 prev_block = "000000000000000117c80378b8da0e33559b5997f2ad55e2f7d18ec1975b9717" merkle_root = "871714dcbae6c8193a2bb9b2a69fe1c0440399f38d94b3a0f1b447275a29978a" time = 1392872245 # 2014-02-20 04:57:25 bits = 0x19015f53 # https://en.bitcoin.it/wiki/Difficulty target_hexstr = zero_padded_256bit_str( rest_bytes(bits) * (2 ** (8 * (first_byte(bits) - 3))) ) target_bytestr = hex_str_to_hex_bytestr(target_hexstr) puts target_hexstr (0x0..0x100000000).each do |nonce| header = little_endian_bytestr(version) + hex_str_to_hex_bytestr(prev_block).reverse + hex_str_to_hex_bytestr(merkle_root).reverse + little_endian_bytestr(time, bits, nonce) hash = sha256(sha256(header)) reversed_hash = hash.reverse puts nonce.to_s + ' ' + hex_bytestr_to_hex_str(reversed_hash) if reversed_hash < target_bytestr puts 'SUCCESS' end end
I am a Bitcoin enthusiast, but neophyte - so if I have made any kind of mistake give me a shout at
jameslarisch.com - thanks!