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, 0x19015f53 is P. The first two numbers in P are 19. From hex -> base10, that’s 25 (F). The rest of the numbers in P are 015f53. From hex -> base10 that’s 89939 (R).

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:
00000000000000015f5300000000000000000000000000000000000000000000.

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 26959946667150639794667015087019630673637144422540572481103610249215.

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

Remember 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.

0x19015f53 -> 11001000000010101111101010011

Then shift it to the right…

1 : 01100100000001010111110101001

2 : 00110010000000101011111010100

24: 0000000000000000000000011001

Which is 25, which is 0x19, which is the first two numbers in bits.

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 -> 00011001000000010101111101010011.

0xffffff in binary (same length) -> 00000000111111111111111111111111
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 \x00\x00\x00\x00\x00\x00\x00\x01_S\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00.

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

MY CODE

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 root @ jameslarisch.com - thanks!

 
43
Kudos
 
43
Kudos

Now read this

Distributed Hash Tables: Introduction

This post assumes you have ~ 1 or more years of programming or Computer Science experience. I’d say if you’re comfortable with hash functions & some basic network ideas, there’s something here for you. This series of posts is... Continue →