Hashing, Encryption, Blockchain and Bitcoin Mining with Python¶
A free Webinar from The Python Quants
Some Bitcoin Data¶
Total Number of Bitcoins¶
We work with data from http://quandl.com. First, the total number of bitcoins mined.
import quandl as q
bn = q.get('BCHAIN/TOTBC') / 1e6 # in millions
bn.plot(figsize=(10, 6));
Total Number of Transactions¶
The total number of transactions.
bt = q.get('BCHAIN/NTRAT') / 1e6 # in millions
bt.plot(figsize=(10, 6));
Number of Unique Addresses¶
The number of unique bitcoin addresses.
ba = q.get('BCHAIN/NADDU')
ba.plot(figsize=(10, 6));
Bitcoin Value in USD¶
The USD/Bitcoin exchange rate.
be = q.get('BCHAIN/MKPRU')
be.plot(figsize=(10, 6));
Bitcoin Value in USD¶
The market capitalization in USD.
bm = q.get('BCHAIN/MKTCP') / 1e9 # in billions
bm.plot(figsize=(10, 6));
Bitcoin Transaction Volume (Units)¶
The Bitcoin transaction volume (in Bitcoins).
bv = q.get('BCHAIN/ETRAV')
bv.plot(figsize=(10, 6));
Bitcoin Transaction Volume (USD)¶
The Bitcoin transaction volume (in USD).
v = be * bv / 1e9 # in billions
v.plot(figsize=(10, 6));
Bitcoin Mining Difficulty¶
The bitcoin mining difficulty. How hard is it to mine a new bitcoin block?
bd = q.get('BCHAIN/DIFF') / 1e9 # in billions
bd.plot(figsize=(10, 6));
Bitcoin Network Hashrate¶
The hashrate of the Bitcoin mining network. How many giga hashes per second (GH/s) does the bitcoin mining network calculate per second?
bh = q.get('BCHAIN/HRATE')
bh.plot(figsize=(10, 6));
Hashing¶
From https://en.wikipedia.org/wiki/Hash_function:
A hash function is any function that can be used to map data of arbitrary size to data of fixed size. The values returned by a hash function are called hash values, hash codes, hash sums, or simply hashes.
A Simple Hash Function¶
The first simplistic hash function that we consider maps any string to a three digit integer. It uses ordinal numbers of one-character string objects.
ord('a')
chr(97)
The implementation of the simplistic hash function ("average integer ordinal number").
def hash_function(text):
value = sum([ord(l) for l in text]) / len(text)
return '%03d' % value
Some examples.
hash_function('!')
hash_function('yves')
hash_function('yves2')
hash_function('Quant4711')
Collisions are easily found.
hash_function('yves')
hash_function('sevy')
Our function has a target space of 10 bits (only).
bin(999)
2 ** 10
Modern hash functions have a target space of 128 bits, i.e. $2^{128} - 1$ possible values.
2 ** 128
hex(2 ** 128)
len(hex(2 ** 128)) - 4
Or 256 bits.
2 ** 256
hex(2 ** 256)
len(hex(2 ** 256)) - 4
Or even 384 bits.
2 ** 384
hex(2 ** 384)
len(hex(2 ** 384)) - 4
The universe is assumed to consist of $10^{80}$ atoms.
10 ** 80
hex(10 ** 80)
len(hex(10 ** 80)) - 3 # close to 2 ** 256
We require the following properties from a hash function:
- collision resistance: it is highly unlikely to find to inputs that yield the same output
- hiding: it is really difficult to find the exact input if you know an output
- puzzle friendliness: if someone targets a certain output value and if parts of the input are randomly chosen then it is difficult to find another input value that hits exactly that target
MD5 Hash Codes¶
First, importing Python's hashing function library.
import hashlib
The first MD5 hash codes (cf. https://en.wikipedia.org/wiki/MD5).
md5_1 = hashlib.md5(b'yves').hexdigest()
md5_1
md5_2 = hashlib.md5(b'yves2').hexdigest()
md5_2
hashlib.md5(b'Dr. Yves Johannes Hilpisch').hexdigest()
Brute Force Hash (Password) Cracking¶
We define first a character set of lower case letters only.
import string
charset = string.ascii_lowercase
charset
Hash codes for all single characters in charset.
for c in charset:
md5 = hashlib.md5(c.encode('ascii'))
print(c, md5.hexdigest())
Now doing brute force hash code cracking — 'knowing' that the relevant word has a maximum of 4 characters.
import itertools as it
%%time
for i in range(1, 5):
print('%d CHARACTERS USED NOW' % i)
pm = it.product(charset, repeat=i)
for comb in pm:
comb = ''.join(comb)
md5 = hashlib.md5(comb.encode('ascii')).hexdigest()
if md5 == md5_1:
print('SUCCESS')
print(comb, md5)
break
Let us enlarge the character set to include digits as well.
charset2 = string.ascii_lowercase + string.digits
charset2
Time to crack the second hash code increases due to greater passworword length and larger character set.
from itertools import product
import time
t0 = time.time()
z = 0
for i in range(1, 6):
print('%d CHARACTERS USED NOW' % i)
pm = it.product(charset2, repeat=i)
for comb in pm:
comb = ''.join(comb)
md5 = hashlib.md5(comb.encode('ascii')).hexdigest()
z += 1
if md5 == md5_2:
print('SUCCESS')
print(comb, md5)
break
sec = time.time() - t0
print('time in sec: %.1f' % sec)
The algorithm has checked about 43 mn hashes before being successful. This represents a speed of about 850,000 hashes per second.
z
z / sec
Using Dedicated Password Cracking Tools ("Better Software")¶
Dedicated password cracking tools like Hashcat (cf. http://hashcat.net) allow for a much faster and more intelligent/targeted approach.
Let us check how long Hashcat needs to find the password yves2 stored as an MD5 hash. We assume:
- password length is 5 letters
- only lower case letters or digits
r1 = '''
664d839e06bada38ce04f7208896efdf:yves2
Session.Name...: hashcat
Status.........: Cracked
Input.Mode.....: Mask (?1?1?1?1?1) [5]
Custom.Chars...: -1 ?l?d, -2 Undefined, -3 Undefined, -4 Undefined
Hash.Target....: 664d839e06bada38ce04f7208896efdf
Hash.Type......: MD5
Time.Started...: Mon Aug 22 19:34:16 2016 (2 secs)
Speed.Dev.#1...: 13710.9 kH/s (0.94ms)
Recovered......: 1/1 (100.00%) Digests, 1/1 (100.00%) Salts
Progress.......: 28803600/60466176 (47.64%)
Rejected.......: 0/28803600 (0.00%)
Restore.Point..: 799470/1679616 (47.60%)
Started: Mon Aug 22 19:34:16 2016
Stopped: Mon Aug 22 19:34:22 2016
real 0m6.055s
user 0m1.750s
sys 0m1.490s
'''
Make Use of Human Traits ("Social Cracking")¶
Mask attacks are some of the most powerful tools (strategies) in password cracking. It relies on the fact that human beings like to use certain (easy to remember) structures for their passwords. An interesting analysis is found here: https://www.praetorian.com/blog/statistics-will-crack-your-password-mask-structure. The major finding is:
- 50% of all passwords analyzed rely on
- 13 password masks only out of
- 260,000+ masks analyzed in total
An example: lisa2008 = name of daughter born in 2008
Let us consider the following case. A password is assumed to consist of upper case letters, lower case letters and digits. In this case, we make use of insights about "humanly generated passwords". I.e. we do a so-called mask attack where we implement the following rules:
- password length is 9 letters
- first letter is upper case (like
A) - next four letters are lower case (like
bbbb) - last four letters are digits (like
1992)
We assume a structure like Abbbb1992.
r2 = '''
8769d3723ec8f853d91f28208e97acce:Quant4711
Session.Name...: hashcat
Status.........: Cracked
Input.Mode.....: Mask (?u?l?l?l?l?d?d?d?d) [9]
Hash.Target....: 8769d3723ec8f853d91f28208e97acce
Hash.Type......: MD5
Time.Started...: Mon Aug 22 17:39:32 2016 (10 mins, 23 secs)
Speed.Dev.#1...: 42944.7 kH/s (13.43ms)
Recovered......: 1/1 (100.00%) Digests, 1/1 (100.00%) Salts
Progress.......: 27138885360/118813760000 (22.84%)
Rejected.......: 0/27138885360 (0.00%)
Restore.Point..: 1543910/6760000 (22.84%)
Started: Mon Aug 22 17:39:32 2016
Stopped: Mon Aug 22 17:50:03 2016
real 10m30.744s
user 12m24.880s
sys 0m35.770s
'''
Using GPUs and ASICs ("Better Hardware")¶
Cheapest Nvidia GPU (about 30 EUR net of VAT) reaches a MD5 hashing speed of about 400MH/s.
High-end Nvidia GPU cluster Brutalis reaches a MD5 hashing speed of about 200GH/s (cf. https://gist.github.com/epixoip/a83d38f412b4737e99bbef804a270c40).
Dedicated Application Specific Integrated Circuit (ASIC) chips reach even higher speed at much lower cost. AntMiner S5 achieves a speed of 1,155 GH/s for Bitcoin mining (SHA256). Used at Amazon for about 200 EUR.
Basics of RSA Encryption¶
On the Wikipedia web site https://en.wikipedia.org/wiki/RSA_(cryptosystem) you find:
RSA is one of the first practical public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and differs from the decryption key which is kept secret. In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem. RSA is made of the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1977.
Introductory Example¶
In the respective Wikipedia article, you find the following example. Consider two (small) prime numbers.
p = 61
q = 53
Compute the product of these numbers as:
n = p * q
n
Compute the so-called totient of the product as:
t = (p - 1) * (q - 1)
t
Choose any number $1 < e < t$ which is coprime to $t$ like:
e = 17
Compute the modular multiplicative inverse $d$ (cf. https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) for which we have
$$d \cdot e \mod t = 1$$as
d = 2753
Let us check:
d * e % t
The public key the is $n=3233, e=17$. The encryption function for a $m$ is
$$c(m) = m^{17} \mod 3233$$m = 77 # our message
c = m ** e % n # encryption
c
The private key is $d = 2753$. The decryption function for a ciphertext message $c$ is
$$m(c) = c^{2753} \mod 3233$$m = c ** d % n
m
Working with "Real" RSA Key Pairs¶
The library PyCryptodome provides a multitude of security algorithms and techniques for easy use with Python. Cf. https://pycryptodome.readthedocs.io/en/latest/ (pip install pycryptodomex).
from Cryptodome.PublicKey import RSA
secret_code = 'PythonQuants'
key = RSA.generate(2048)
The public key.
pub_key = key.publickey().exportKey()
print(pub_key)
The private key.
priv_key = key.exportKey()
print(priv_key)
Let us now encrypt and decrypt a message with these keys. First, the encryption step using the public key — assuming that someone sends a message to The Python Quants who own the private key.
from Cryptodome.Cipher import PKCS1_OAEP
m = b'Hello TO The Python Quants. ' * 5
cipher = PKCS1_OAEP.new(key.publickey()) # public key
ciphertext = cipher.encrypt(m)
ciphertext
Second, the decryption step using the private key.
cipher = PKCS1_OAEP.new(key) # private key
message = cipher.decrypt(ciphertext)
message
Using openssl¶
Beyond Python, it is easy to generate RSA key pairs by the use of openssl (cf. https://www.openssl.org/).
# !openssl req -x509 -nodes -days 365 -newkey rsa:1024 -keyout cert.key -out cert.pem -b
Signing Messages with Hashes and RSA Keys¶
Let us electronically sign a message The Python Quants send to someone else. To this end, we combine hashing with RSA encryption.
m = b'Hello FROM The Python Quants.' * 5
We generate a hash code for the message.
from Cryptodome.Hash import SHA256
h = SHA256.new(m)
hd = h.hexdigest()
hd
We next sign the message, i.e. we encrypt the hash code with the private key from before.
from Cryptodome.Signature import PKCS1_v1_5
signer = PKCS1_v1_5.new(key)
signature = signer.sign(h) # private key
signature
Someone else — i.e. the receiver of our message — who knows our public key can now verify that we have signed the message as follows.
hashcode = SHA256.new(m)
hashcode.hexdigest()
PKCS1_v1_5.new(key.publickey()).verify(hashcode, signature) # public key
Basic Idea Behind Block Chains¶
Very Simple Example¶
Let us now illustrate the basic idea behind a block chain based on a very simple example first. Recall the properties of hash functions that we require (collision resistence, hiding, puzzle friendliness). Let us focus on collision resistence and hiding for the moment.
As a starter, it is obviously easy to calculate the hash value of a string ("first block"), for instance, as follows:
import hashlib
b1 = 'Jil, 2004' # our first dog
h1 = hashlib.md5(b1.encode('ascii')).hexdigest() # hash for first block
h1
It is highly unlikely that another input yields the same output. It is also really difficult ("almost impossible") to find the input given a certain ouput.
A block chain can be used to document events over time (e.g. transactions, new dogs). To this end, we take the hash code from the first block, add the second block information and calculate a new hash value:
b2 = h1 + ', Liz, 2009'
h2 = hashlib.md5(b2.encode('ascii')).hexdigest()
h2
A third block is as easily added:
b3 = h2 + ', Phineas, 2011'
h3 = hashlib.md5(b3.encode('ascii')).hexdigest()
h3
Our block chain now is:
print(b1)
print(b2)
print(b3)
There is one major problem with this approach: the block chain is really easy to manipulate since you only need to re-calculate the whole chain. You have all the information needed.
We need add therefore one security measure to avoid manipulation (in theory): signing of the last hash value.
h3
# key generation
from Cryptodome.PublicKey import RSA
key = RSA.generate(2048)
# signing
from Cryptodome.Hash import MD5
from Cryptodome.Signature import PKCS1_v1_5
md5 = MD5.new(b3.encode('ascii'))
signature = PKCS1_v1_5.new(key).sign(md5) # private key
signature
If we can make sure that the private key is safe, then the block chain plus the signature for the final hash value are "almost impossible" to manipulate — although all the information is publicly available.
b1, b2, b3, h3, signature
Another idea is to make it hard to construct another block chain with the same inputs (but in different sequence) or other inputs that satisfies a certain property. Let us define that only hash values with five zeros at the end are allowed. To this end, we must allow for an additional input parameter.
%%time
n = 0
while True:
b = str(n) + ', ' + b1
md5 = hashlib.md5(b.encode('ascii')).hexdigest()
if md5[-5:] == '00000':
print(b + ' --> ' + md5)
break
n += 1
Someone wanting to manipulate the block chain must put in much more effort in this case than without such a requirement. The difficulty can easily be increased by requiring eg more trailing zeros.
%%time
n = 0
while True:
b = str(n) + ', ' + b1
md5 = hashlib.md5(b.encode('ascii')).hexdigest()
if md5[-6:] == '000000':
print(b + ' --> ' + md5)
break
n += 1
The first security measure "signing" is vulnerable to stealing the private key (especially when multiple versions exist, e.g. due to backups). The second one "targeting" to sheer brute force. A combination of both, of course, works as well — and is probably more secure.
Another approach that adds some security is to use a random, publicly known, fixed initial hash.
import os
h0 = os.urandom(16).hex()
h0
b1 = h0 + ', Jil, 2004' # our first dog
h1 = hashlib.md5(b1.encode('ascii')).hexdigest() # hash for first block
h1
Simple Cryptocurrency based on a Block Chain¶
Let us now implement a simple cryptocurrency based on the block chain idea. The example is from the book Narayanan et al. (2016): Bitcoin and Cryptocurrency Technologies.
Consider a central authority, The Python Quants (TPQ), that issues a cryptocurrency calles TPQ Coins. Two basic transactions are possible CreateCoins and PayCoins in the system.
There are many participants in the system that are identified by their public key of a RSA key pair.
Consider an original transaction by which TPQ create 10 TPQ Coins. We have transaction id of 0. The coins created have a coin id of 0(0). The value is 10 and the recipient are TPQ represented by their public key. We also generate an initial hash value to be included in the first block. We define the initial block as follows:
# h = h0 = os.urandom(16).hex()
h = hashlib.md5('my secret passphrase'.encode('ascii')).hexdigest()
# prev. hash, transID, transaction, value, coinID, recipient
b0 = h + '\n0, CreateCoins, 10, 0a, 0xTPQ'
print(b0)
This initial block gets hashed and the hash value gets signed by TPQ.
TPQ now pays another participant in the system 5 TPQ Coins. This is a PayCoins transaction with id 1.
h = hashlib.md5(b0.encode('ascii')).hexdigest()
b1 = h + '\n1, Consumed Coins: 0a\n'
# prev. hash, transID, transaction, value, transID, recipient
b1 += '1, PayCoins, 5, 1a, 0xRE1\n'
b1 += '1, PayCoins, 5, 1b, 0xTP2' # another address of TPQ
print(b1)
This second block gets hashed and the hash value gets signed by TPQ.
Now, the participant with address (public key) of 0xRE1 is able to spend TPQ Coins to e.g. buy goods or services from someone identified by 0xSEL.
h = hashlib.md5(b1.encode('ascii')).hexdigest()
b2 = h + '\n2, Consumed Coins: 1a\n'
# prev. hash, transID, transaction, value, coinID, recipient
b2 += '2, PayCoins, 2.5, 2a, 0xSEL\n' # payment to seller
b2 += '2, PayCoins, 2.5, 2b, 0xRE2' # another address of 0xRE1
print(b2)
This block gets hashed and signed by the payer 0xRE1. It then gets added to the block chain by TPQ, signed by TPQ and published. Everybody now can recover the complete history of the TPQ Coins.
The block chain respresenting the history of the TPQ Coins now looks as follows.
print(b0)
print(b1)
print(b2)
Bitcoin Addresses¶
Bitcoin addresses are based on Elliptic Curve Digital Signature Algorithm (ECDSA), cf. https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm. The starting point, however, is a SHA256 hash code. Using respective libraries you can generate it randomly or via a passphrase.
In what follows, we are going to use a Python 3 implementation for the generation of a Bitcoin address. See:
- source: https://github.com/Shultzi/Bitpy
- blog post: http://zeltsinger.com/2016/07/18/keys/
# %load bckeys.py
#
# Bitcoin Address Generation
# with Python 3.5
#
# Source: https://github.com/Shultzi/Bitpy
# Blog Post: http://zeltsinger.com/2016/07/18/keys/
#
import os
import ecdsa # pip install ecdsa
import hashlib
import base58 # pip install base58
import binascii
class Key(object):
def __init__(self, private_key=0):
if private_key == 0:
self.private_key = os.urandom(32)
self.printable_pk = str(
binascii.hexlify(self.private_key), "ascii")
else:
self.printable_pk = private_key
self.private_key = binascii.unhexlify(private_key.encode('ascii'))
self.sk = ecdsa.SigningKey.from_string(
self.private_key, curve=ecdsa.SECP256k1)
self.vk = self.sk.verifying_key
self.public_key = b"04" + binascii.hexlify(self.vk.to_string())
ripemd160 = hashlib.new('ripemd160')
ripemd160.update(hashlib.sha256(
binascii.unhexlify(self.public_key)).digest())
self.hashed_public_key = b"00" + binascii.hexlify(ripemd160.digest())
self.checksum = binascii.hexlify(hashlib.sha256(hashlib.sha256(
binascii.unhexlify(self.hashed_public_key)).digest()).digest()[:4])
self.binary_addr = binascii.unhexlify(
self.hashed_public_key + self.checksum)
self.addr = base58.b58encode(self.binary_addr)
def get_addr(self):
return self.addr
An address can be generated based on a random private key.
key = Key()
key.printable_pk
Having generated the private key, the public key is generated then via ECDSA, i.e. via multiplying the private key with the respective generator point G (x,y) of the elliptic curve. The idea is that the multiplication is easy and straightforward when the factorization is an almost impossible to solve problem.
key.public_key
Bitcoin addresses are represented in the so-called Wallet Import Format (WIF) (https://en.bitcoin.it/wiki/Wallet_import_format) which is based on the Base58Check encoding format (https://en.bitcoin.it/wiki/Base58Check_encoding).
key.addr
Of course, you can generate a private key based on your own passphrase.
pk = hashlib.sha256('Bitcoin is really cool.'.encode('ascii')).hexdigest()
pk
key = Key(pk)
key.printable_pk
key.public_key
key.addr
Bitcoin Transactions¶
Bitcoin addresses are the basis for bitcoin transations.
o1 = '''
$ bitcoin-cli -regtest getnewaddress
mvbnrCX3bg1cDRUu8pkecrvP6vQkSLDSou
$ NEW_ADDRESS=mvbnrCX3bg1cDRUu8pkecrvP6vQkSLDSou
'''
Here, Bitcoins are sent to the previously generated address.
o2 = '''
$ bitcoin-cli -regtest sendtoaddress $NEW_ADDRESS 10.00
263c018582731ff54dc72c7d67e858c002ae298835501d80200f05753de0edf0
'''
10 Bitcoins belong now to the generated address.
o3 = '''
$ bitcoin-cli -regtest listunspent 0
[
{
"txid" : "263c018582731ff54dc72c7d67e858c002ae298835501d\
80200f05753de0edf0",
"vout" : 0,
"address" : "muhtvdmsnbQEPFuEmxcChX58fGvXaaUoVt",
"scriptPubKey" : "76a9149ba386253ea698158b6d34802bb9b550\
f5ce36dd88ac",
"amount" : 40.00000000,
"confirmations" : 0
},
{
"txid" : "263c018582731ff54dc72c7d67e858c002ae298835501d\
80200f05753de0edf0",
"vout" : 1,
"address" : "mvbnrCX3bg1cDRUu8pkecrvP6vQkSLDSou",
"account" : "",
"scriptPubKey" : "76a914a57414e5ffae9ef5074bacbe10a320bb\
2614e1f388ac",
"amount" : 10.00000000,
"confirmations" : 0
}
]
'''
Basic Idea Behind Mining¶
Bitcoin mining is based on SHA256 hash codes (cf. https://en.wikipedia.org/wiki/SHA-2)
sha256 = hashlib.sha256('yves'.encode('ascii'))
sha256.hexdigest()
The idea behind mining is to find a hash code that is 'small enough', i.e. lies below a certain target level (mainly defined by 'leading zeros' in the target hex value).
target = '%064x' % (1000000000 << 200)
target
The original hash code for python is not small enough.
target
sha256.hexdigest() < target
However, adding (a) certain number(s) to the string, yields a hash code small enough.
sh = hashlib.sha256(b'%dyves' % 23240167).hexdigest()
sh
sh < target
The following code simulates a mining procedure.
%%time
i = 0
while True:
sha256 = hashlib.sha256(b'%d' % i + b'yves')
if sha256.hexdigest() < target:
print('SUCCESS')
print(i, sha256.hexdigest())
# break
if i % 2500000 == 0:
print(i)
i += 1
if i > 55000000:
break
The time to find a suitable hash code depends on the input string.
%%time
i = 0
while True:
sha256 = hashlib.sha256(b'%d' % i + b'yveshilpisch')
if sha256.hexdigest() < target:
print('SUCCESS')
print(i, sha256.hexdigest())
# break
if i % 2500000 == 0:
print(i)
i += 1
if i > 55000000:
break
Mining a Bitcoin Block¶
The following example is from http://www.righto.com/2014/02/bitcoin-mining-hard-way-algorithms.html and is about a 'real' bitcoin block and how to mine it wih Python.
In what follows we need the struct module (cf. https://docs.python.org/3/library/struct.html).
import struct
import binascii
import hashlib
The basic elements of a bitcoin block.
The elements translated into Python code. Cf. also https://en.bitcoin.it/wiki/Block_hashing_algorithm.
ver = 2
prev_block = b'000000000000000117c80378b8da0e33559b5997f2ad55e2f7d18ec1975b9717'
mrkl_root = b'871714dcbae6c8193a2bb9b2a69fe1c0440399f38d94b3a0f1b447275a29978a'
time_ = 0x53058b35 # 2014-02-20 04:57:25
bits = 0x19015f53 # difficulty
bits
Cf. https://bitcoinwisdom.com/bitcoin/difficulty for data about mining difficulty and hash rates. See also https://en.bitcoin.it/wiki/Difficulty.
The following code snippets illustrate the derivation of the target value which is the upper limit for a successful hash code. Cf. https://www.codecademy.com/courses/python-intermediate-en-KE1UJ/0/1 for bitwise operations in Python.
ex = bits >> 24
ex
mant = bits & 0xffffff
mant
hex(mant)
8 * (ex - 3)
The concrete values.
target_hexstr = '%064x' % (mant * (1 << (8 * (ex - 3))))
target_hexstr
target_str = binascii.unhexlify(target_hexstr)
target_str # C struct
The Python module struct can be used to convert Python values to C structs represented as Python strings and vice versa.
pa = struct.pack('LLL', 1, 20, 300) # packing data
pa
struct.unpack('LLL', pa) # unpacking data
The nonce is the value which is to be added to the other block elements during the hash code generation. One looks for the nonce that gives a hash code smaller than the target level.
nonce = 850000000
# nonce = 856192328
# Block 286819
# check under https://blockexplorer.com
Finally, the Python code to do the mining activitiy. Basically, the nonce values gets increased by 1 during the look, a new hash code is generated and compared to the target level.
%%time
while nonce < 0x100000000:
header = (struct.pack("<L", ver)
+ binascii.unhexlify(prev_block)[::-1]
+ binascii.unhexlify(mrkl_root)[::-1]
+ struct.pack("<LLL", time_, bits, nonce))
hs = hashlib.sha256(hashlib.sha256(header).digest()).digest()
if nonce % 200000 == 0:
print(nonce, binascii.hexlify(hs[::-1]))
if binascii.hexlify(hs[::-1]) < binascii.hexlify(target_str):
print(nonce, binascii.hexlify(hs[::-1]))
print('success')
break
nonce += 1
Merkle Hash¶
The following are the hard-coded transaction hashes for the Bitcoin block under consideration (http://www.righto.com/2014/02/bitcoin-mining-hard-way-algorithms.html).
# https://blockexplorer.com/rawblock/0000000000000000e067a478024addfecdc93628978aa52d91fabd4292982a50
txHashes = [
"00baf6626abc2df808da36a518c69f09b0d2ed0a79421ccfde4f559d2e42128b",
"91c5e9f288437262f218c60f986e8bc10fb35ab3b9f6de477ff0eb554da89dea",
"46685c94b82b84fa05b6a0f36de6ff46475520113d5cb8c6fb060e043a0dbc5c",
"ba7ed2544c78ad793ef5bb0ebe0b1c62e8eb9404691165ffcb08662d1733d7a8",
"b8dc1b7b7ed847c3595e7b02dbd7372aa221756b718c5f2943c75654faf48589",
"25074ef168a061fcc8663b4554a31b617683abc33b72d2e2834f9329c93f8214",
"0fb8e311bffffadc6dc4928d7da9e142951d3ba726c8bde2cf1489b62fb9ebc5",
"c67c79204e681c8bb453195db8ca7d61d4692f0098514ca198ccfd1b59dbcee3",
"bd27570a6cbd8ad026bfdb8909fdae9321788f0643dea195f39cd84a60a1901b",
"41a06e53ffc5108358ddcec05b029763d714ae9f33c5403735e8dee78027fe74",
"cc2696b44cb07612c316f24c07092956f7d8b6e0d48f758572e0d611d1da6fb9",
"8fc508772c60ace7bfeb3f5f3a507659285ea6f351ac0474a0a9710c7673d4fd",
"62fed508c095446d971580099f976428fc069f32e966a40a991953b798b28684",
"928eadbc39196b95147416eedf6f635dcff818916da65419904df8fde977d5db",
"b137e685df7c1dffe031fb966a0923bb5d0e56f381e730bc01c6d5244cfe47c1",
"b92207cee1f9e0bfbd797b05a738fab9de9c799b74f54f6b922f20bd5ec23dd6",
"29d6f37ada0481375b6903c6480a81f8deaf2dcdba03411ed9e8d3e5684d02dd",
"48158deb116e4fd0429fbbbae61e8e68cb6d0e0c4465ff9a6a990037f88c489c",
"be64ea86960864cc0a0236bbb11f232faf5b19ae6e2c85518628f5fae37ec1ca",
"081363552e9fff7461f1fc6663e1abd0fb2dd1c54931e177479a18c4c26260e8",
"eb87c25dd2b2537b1ff3dbabc420e422e2a801f1bededa6fa49ef7980feaef70",
"339e16fcc11deb61ccb548239270af43f5ad34c321416bada4b8d66467b1c697",
"4ad6417a3a04179482ed2e4b7251c396e38841c6fba8d2ce9543337ab7c93c02",
"c28a45cded020bf424b400ffc9cb6f2f85601934f18c34a4f78283247192056a",
"882037cc9e3ee6ddc2d3eba86b7ca163533b5d3cbb16eaa38696bb0a2ea1137e",
"179bb936305b46bb0a9df330f8701984c725a60e063ad5892fa97461570b5c04",
"9517c585d1578cb327b7988f38e1a15c663955ea288a2292b40d27f232fbb980",
"2c7e07d0cf42e5520bcbfe2f5ef63761a9ab9d7ccb00ea346195eae030f3b86f",
"534f631fc42ae2d309670e01c7a0890e4bfb65bae798522ca14df09c81b09734",
"104643385619adb848593eb668a8066d1f32650edf35e74b0fc3306cb6719448",
"87ac990808239c768182a752f4f71cd98558397072883c7e137efb49d22b9231",
"9b3e2f1c47d59a444e9b6dc725f0ac6baf160d22f3a9d399434e5e65b14eccb0",
"fbe123066ae5add633a542f151663db4eb5a7053e388faadb40240671ae1b09b",
"1dd07e92e20b3cb9208af040031f7cfc4efd46cc31ec27be20a1047965a42849",
"2709bb9ed27353c1fd76b9240cab7576a44de68945e256ad44b2cb8d849a8060",
"d0174db2c712573432a7869c1508f371f3a1058aeedddc1b53a7e04d7c56c725",
"b4a16f724cddb8f77ddf3d2146a12c4be13d503885eaba3518a03da005009f62",
"2aa706d75decbe57745e01d46f9f5d30a08dedaf3288cee14cc4948e3684e1d4",
"ee49c5f6a5129ccaf2abebbc1d6d07a402a600af6221476b89aafaa683ca95b7",
"bea1011c77874845e9b4c876ed2ceebd530d428dd4a564ad003d9211d40bb091",
"f1e88ffc2b1de2aa4827002f06943ce5468735f7433f960bf01e75885b9f832b",
"19247d017e002fb9143d1a89eb921222a94f8a3d0faaf2e05b0f594989edc4c4",
"13f714ff62ee7d26b6d69ca980c141ebc54e9f71d2697083fe6c5efc1b02bd0f",
"0c78cbb8246572f015fbdc53dc9798fa54d1119ec77c1f07ac310bcbcc40dbf8",
"4bcde0ef92a6d24a2be7be50ac5e5299d776df2e6229ba5d475c2491da94f255",
"0cfd7d1058502730cf0b2ffa880c78ef534651e06832b5d87c0d7eb84eac5b0c",
"3a168f794d6e0c614429ad874317cc4cd67a8177214880ff6ea1704d29228c2f",
"f9a555d817334397b402518d6fd959dc73d981ee7f5fe67969b63974ebbef127",
"24b52691f66eaed4ce391a473902e309018257c98b9f02aaa33b399c9e6f3168",
"a37b5e623dc26a180d9e2c9510d06885b014e86e533adb63ec40511e10b55046",
"9dbaeb485e51d9e25a5621dc46e0bc0aaf51fb26be5acc4e370b96f62c469b80",
"a6431d3d39f6c38c5df48405090752cab03bfdf5c77cf881b18a946807fba74a",
"faa77e309f125373acf19855dd496fffe2f74962e545420844557a3adc7ebc11",
"3523f52543ecfea2f78486dc91550fad0e6467d46d9d9c82ca63b2e0230bfa71",
"a0583e358e42d77d18d1fd0533ff0a65615fc3b3112061ef92f168a00bf640c1",
"42ae900888d5e5dde59c8e3d06e13db9e84ef05d27726d4b67fd00c50cd9406a",
"154940777d3ff78f592ef02790131a59263c36b4958bbc836f9a767ea1a9f178",
"6a0337de6ac75eecf748306e8ebc5bfe5c811a1481ae50f6956a9e7f26a679f5",
"c99530c2148e09688d0b88795625943371183bf1f5d56c7446c6ed51ea133589",
"626421dbe8ad6a0fd0d622d5dd3308a1cdc00b98575a41a91fe01a439e6f40bd",
"b2f3a559f605a158cc395126c3cf394a7e92a53b7514c75157e1dc43a6c7f93e",
"dffe06d1bea81f2a01c76786404bb867258f9e68013bf25454097ce935090738",
"0860159ec7a2a51ce107c182a988c40b4bc2057a734354a1219b6c65e72640ed",
"a405ff1bb51846b1867acc0b0da17f6f9616e592a0a7ff5ef3297c1ecfd60911",
"a7d451924263284765f6343bca8a21b79b89ebfe611c7355dd88e0ec1c29e232",
"41c758d08a4d3fe4d90645711589b832a2cd54dd25bd5b66e463e5d389a53aff",
"a05c1a93a521fa5dbc1790cfbb808893453a428a65f2c6b2d51249fbb12db309",
"90997920aa9786e10f513cfdd14e294feee6739cee1ab61b3fb1e3f42e7a915d",
"99fcb9cb62c20a3135484a70bd3f73983f8f3b7b26266dad34f3993958a7642c",
"e05f9a668b37e5f78bd3b9d047f29f92b33a87f11dd48390410006f858188b7b",
"56dbc65895f7992da4a6985e7edba4d1c00879f1b28442c644c8a07658ceab27",
"5e9004fe262b829563d0804656ba68b1de1690401f08a1915273230d8c902fc0",
"1ea9ed3717523c5e304b7a7ac8058a87fb4f3fed8c6004769f226c9bb67e79c5",
"f0f1a4c009b3f1b2729e89898e2f5c0fcdc312edea5df884a9c897cb90e4c566",
"b5bb4ddf04863e6a60f33cb96c20dac8175d3bae55f335781503143c97a50e43",
"f14cc97a20c6f627b4b78301352ae35463bc359362589cd178a06c0fa90850b7",
"628801c8f614015c0fa0ccb2768cccc3e7b9d41ceed06071ce2534d31f7236d6",
"3be1013c8f8da150e2195408093153b55b08b037fd92db8bb5e803f4c2538aae",
"c9e1f8777685f54ba65c4e02915fd649ee1edcbf9c77ddf584b943d27efb86c3",
"4274e92ed3bd02eb101baa5fb8ff7b96236830762d08273749fbb5166db8ab0b",
"aa84c955bea04c7cee8f5bbbec97d25930fcaca363eed1b8cad37b931556d3e3",
"d6a29c948677fb1f71aaf16debc3d071a4dd349458eb9e056dce3a000ff853da",
"ba84bdb3d78367ca365016ac4bff9269576eb010f874c2967af73e0de5638de0",
"1546c79951e3b541bc64d1957b565b7a2850fc87192c7b374aee6cfc69b9805e",
"f119227d492ebe27fe9aae321980802454dfa64b2691efbe796c5075d5b07f62",
"b8cf13d64818b32f96bbb585998b1bc9505f6a94055488e5a71fee9479c6f2a9",
"1aaf459705b6afef2d7b83e3f181f1af55be0813daf55edce104cc59abc28ed7",
"61ac185c8f520b5e3134953dc52ff292a40e1e96b088dab259558a9d240ec02f",
"2da96e3154d7ec2329f787b73cb8a436b92d64cf3cc28e920d073279ea73b5f8",
"1c4d72ce733b971b9ec4e24f37d733355f6f2ea635cc67ffb3e22748484df446",
"2a6f89769f3272ac8c7a36a42a57627eca6b260ab2c76d8046a27d44d4034893",
"f8d11df51a2cc113698ebf39a958fe81179d7d973d2044322771c0fe63f4d7c9",
"f2287f17a4fa232dca5715c24a92f7112402a8101b9a7b276fb8c8f617376b90",
"bb5ee510a4fda29cae30c97e7eee80569d3ec3598465f2d7e0674c395e0256e9",
"647ab8c84365620d60f2523505d14bd230b5e650c96dee48be47770063ee7461",
"34b06018fcc33ba6ebb01198d785b0629fbdc5d1948f688059158f053093f08b",
"ff58b258dab0d7f36a2908e6c75229ce308d34806289c912a1a5f39a5aa71f9f",
"232fc124803668a9f23b1c3bcb1134274303f5c0e1b0e27c9b6c7db59f0e2a4d",
"27a0797cc5b042ba4c11e72a9555d13a67f00161550b32ede0511718b22dbc2c",
]
Function to generate the (pair-wise) Merkle hash.
# hash pairs of items recursively until a single value is obtained
def merkle(hashList):
if len(hashList) == 1:
return hashList[0]
newHashList = []
# process pairs; for odd length, the last is skipped
for i in range(0, len(hashList)-1, 2):
newHashList.append(hash2(hashList[i], hashList[i+1]))
if len(hashList) % 2 == 1: # odd, hash last item twice
newHashList.append(hash2(hashList[-1], hashList[-1]))
return merkle(newHashList)
def hash2(a, b):
# reverse inputs before and after hashing
# due to big-endian / little-endian nonsense
a1 = binascii.unhexlify(a)[::-1]
b1 = binascii.unhexlify(b)[::-1]
h = hashlib.sha256(hashlib.sha256(a1 + b1).digest()).digest()
return binascii.hexlify(h[::-1])
Finally, the Merkle hash code for the above transaction hashes as found in the block header.
print(merkle(txHashes))
http://tpq.io | @dyjh | team@tpq.io
Python Quant Platform | http://quant-platform.com
Python for Finance | Python for Finance @ O'Reilly
Derivatives Analytics with Python | Derivatives Analytics @ Wiley Finance
Listed Volatility and Variance Derivatives | Listed VV Derivatives @ Wiley Finance