Bitcoin: What’s the Math?

Bitcoin- will it replace fiat currency? How does the math work? And where can I get one of those physical coins?

I came across Bitcoin about 6 months ago, thanks to a friend who started her own company that uses blockchain technology. I’d heard of Bitcoin before- my general idea was “Bitcoin is a virtual currency that my brother used to mine when I was in high school.” I didn’t know much other than that, like most people.

What really sparked my interest was my realization that Bitcoin and other digital currencies are a great application of cryptography (hence the name “cryptocurrency”), a field that I’ve always been very fascinated by. Cryptography, to me, is a perfect way to use math in the real world. Once this realization hit, I decided to actually look into the math behind bitcoin.

Although I read countless articles, including the original Nakamoto whitepaper, I still struggled to find a resource that would answer the fundamental question: What’s the math? The best I could find was articles that would discuss elliptic curve cryptography, and the particular parameters used for Bitcoin. This didn’t satisfy me.

As per the suggestion of my friend, I got a copy of Andreas Antonopolous’ Mastering Bitcoin: Programming the Open Blockchain. This book really brought everything together for me. I highly recommend it!

I hope this blog post can help you understand the Bitcoin protocol and the Bitcoin blockchain, from a mathematical perspective. I’ll assume first that you’re familiar with Bitcoin, and second that you have a knowledge of the math. I’ll leave links to explanations of the math topics below, for those who are not so familiar.

Blockchain and Mining: SHA256, Merkle Trees

It’s commonly thought that the purpose of mining is to issue new currency. Actually, mining is the process in which transactions are verified. Mining allows a decentralized network-wide consensus of the state of the blockchain, which is what makes this technology so special. The issuance of new currency is the incentive.

Despite currency issuance being the incentive rather than the goal, we will start our discussion with a mining, and the “creation” of new BTC (or XBT). From there, we will look at how this currency is “spent,”  and the math involved there.

Let’s say Alice has a mining node, which is really just a computer program. The goal of the miner is to construct a new block, and solve a computationally expensive cryptographic puzzle, so that this new block can be accepted by the network, and incorporated into the blockchain. Upon solving this cryptographic puzzle, Alice’s miner will “win” and collect a payout (currently 12.5 BTC as of this writing), payable to her Bitcoin address. Alice will also collect the fees of all the transactions included in this newly mined block.

The first step in Alice’s mining is the verification of the newest block on the blockchain. Let’s call this most recent block A. Upon verification of the transactions in A, Alice’s mining program will construct a header for the potential next block in the chain. Let’s call this block B. The header of new block has 6 fields: The version, previous block hash, Merkle root, timestamp, target, and none. There’s a decent amount of math in italics to unpack here.

Previous block hash: double-SHA256

If Alice’s miner wants to make a look up of any block in the blockchain, there are two ways it can do this. The first way to do this is to reference the block height. The second way is to calculate the block ID, where block ID = double-SHA256(block header). The block ID is also the previous block hash. For example, let’s say the block ID of A is A’ = double-SHA256(blockIDA). Then for block B, which extends the blockchain, its field “previous block hash” is set equal to A’. This extends the chain of blocks from block A to B, with block B being the child, and A being the parent. This is also how Alice’s miner users its mining power to “vote” for block A as the most recent block in the chain.

Merkle root: a concept in itself, and double-SHA256

A Merkle root is the final hash in a Merkle tree. A Merkle tree, in short, is a binary tree where every parent node is the hash of its children. This is constructed in Bitcoin by recursively computing double-SHA256 pairs of nodes until there is only one hash in the tree- and this is the Merkle root. In the case of Bitcoin, every child contains transaction information, so the Merkle root summarizes all transactions in a block.

A simple figure of creating a Merkle Root. The hash function H is double-SHA256, with the transactions (T) as the inputs. Thanks to Microsoft Paint for helping me make this beautiful figure!

Target and nonce

The target is a 256-bit number that all mining nodes share. The goal of mining is to find a nonce (a one-time use number that starts at 0) such that the hash (SHA256) of the header and the nonce together is less than or equal to the target. The target is updated every 2016 blocks.

To continue with our example, Alice’s miner wants to include the new block B in the block chain. The goal is to find a nonce such that:

SHA256(header of B + nonce) <= target.

It’s very computationally expensive to find this nonce, but very easy to verify, due to the nature of this hash function. Finding this nonce then is the proof that a miner did the required amount of work, hence, “Proof of Work.” Once the nonce is found, Alice’s miner will propagate the information of B to the entire Bitcoin network. Once enough of the miners have verified that the transactions included in B are truthful, then B is the next block in the chain, and Alice will collect her payout of 12.5 BTC to her wallet, plus transaction fees. All miners in the network, including Alice’s, will then construct a new block C, where the previous block hash field references the ID of B.

A note on Proof of Work: it’s important that the cryptographic puzzle (i.e. finding a hash less than the target) must be computationally expensive. If it was not, then a dishonest person with access to computational power equal to 51% of the network could rewrite transactions to be paid to their own wallet, and then include this block in the chain. (However, as this expense grows, it becomes problematic, which is the subject of another post. There are new protocols that are attempting to solve this problem!)

Now we have 12.5 BTC in Alice’s wallet. Next we’ll be looking at how she spends it, and the math involve here.

To summarize this section, the math is:

  • Double-SHA256(block header) to create an ID of block A, which will be in the previous block hash field for a new block B, where B is the child of A.
  • Merkle trees and recursively performing double-SHA256 to create a Merkle root that summarizes all transactions in a block.
  • SHA256 of a block header and nonce, to perform the Proof of Work required to verify all the transactions in the block, and to find a hash that is less than or equal to the target. Upon discovery of this nonce, the block will be included in the blockchain.

Transactions and Wallets: ECDSA, RIPEMD160, SHA256

Bitcoin uses public key cryptography for its transactions, specifically Elliptic Curve Digital Signature Algorithm (ECDSA), based on the discrete logarithm problem.

Wallets: like a keychain

A Bitcoin wallet does not contain actual Bitcoin. Instead, it contains the keys that point to a transaction output on the public ledger, the blockchain. Only those with the corresponding private keys can “spend” the Bitcoin associated with a recipient’s wallet address.

Making a transaction: authentication

Let’s continue our example. Say Alice wants to send 1 BTC to her friend Bob. Alice will use her wallet to construct a transaction that sends this 1 BTC to Bob’s public wallet address. This transaction is the message. Alice will sign the message with her signature (r,s), to provide authenticity, and this will be propagated to the network. Any peer can verify Alice’s identity by using her public key, which is associated with her wallet address. In other words, the process is as follows:

Let D = Alice’s private key, E = Alice’s public key, M = the transaction.
1. Alice’s wallet constructs M, which sends 1 BTC to Bob’s public address.
2. Alice signs M to produce M’ = D(M).
3. Any peer can verify Alice’s authenticity by performing E(M’) = M.

Now how can Bob spend this 1 Bitcoin from Alice? When Alice constructed M, she was essentially constructing a message that said “I’ll give 1 BTC to whoever has the private key corresponding to this public address [which is Bob’s address, in this case].” For Bob to spend this amount, his wallet will construct a new transaction, he’ll sign it with his signature (r’,s’), which is derived from the private key (as per elliptic curve cryptography) that only he has access to, and the process continues.

What Bitcoin does is use ECDSA to confer authenticity of the sender, and this authentication is what is required to “spend” bitcoin. Bitcoin transactions do not require encryption, since every transaction is propagated to the network, and specifies the recipient’s public address, which is anonymous.

Creating a Bitcoin address

As per elliptic curve cryptography, the public key is generated from the private key, and from this public key, the bitcoin address is created.

The private key k is in the range of [1, n-1], where n is the order of the elliptic curve. The particular elliptic curve used in the Bitcoin protocol is secp256k1, which specifies the coefficients of the elliptic curve, as well as the generator G. The steps to creating a Bitcoin address are as follows:

1. The private key k is randomly generated.
2. The public key K = k * G, where G is the generator.
3. The wallet address A = RIPEMD160(SHA256(K)).
4. The address A is Base58Check encoded to produce A’ = prefix || A || checksum, and this is the final wallet address (“||” denotes concatenation).

Base58Check is a combination of Base58, which is the set of characters {upper case, lower case, numbers} \ {0, O, I, l}, and a checksum. The particular checksum is the first 4 bytes of the output of double-SHA256(prefix + A), where the prefix is 0 in this case. The final Base58Check encoded address A’ = prefix || A || checksum.

The elliptic curve with the parameters of secp256k1, over the real numbers. Yay math!

In summary, the math for this section is:

  • ECDSA to “spend” bitcoin, with the signature (r,s).
  • Elliptic curve cryptography to generate a public key K from a private key k.
  • RIPEMD160 and SHA256 together, together called HASH160, and Base58Check encoding to produce a Bitcoin wallet address from the public key K.

Conclusion

When I first started delving into the math of Bitcoin, all I knew was that it uses elliptic curve cryptography in some respect. I didn’t know how ECC was used- was in the transactions, issuing currency, or what? Finally, I have a clear understanding of how math is used to make Bitcoin and blockchain such a powerful, disruptive technology.

Math is used to verify transactions (mining), make transactions, and to create wallet addresses to which transactions are sent. Double-SHA256 is used to identify blocks and to summarize transactions into Merkle roots, and single SHA256 is used for Proof of Work during mining. ECDSA is used to “sign” transactions. RIPEMD160 and SHA256 are used together with Base58Check encoding to make create wallet addresses. It all makes sense now!

Resources

For those who would like to look more into the details, whether it’s your first time, or you’d simply like to refresh your memory:

Wikipedia and Bitcoin Wiki:

Public key cryptography: https://en.wikipedia.org/wiki/Public-key_cryptography
Elliptic curve cryptography: https://en.wikipedia.org/wiki/Elliptic-curve_cryptography
Elliptic curve digital signature algorithm: https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm (much better than the bitcoinwiki page, in my opinion)
Secp256k1: https://en.bitcoin.it/wiki/Secp256k1
SHA256: https://en.wikipedia.org/wiki/SHA-2
RIPEMD160: https://en.wikipedia.org/wiki/RIPEMD

Books:

Cryptography and Network Security by William Stallings: A really great book on cryptography. I recommend it to anyone who’s motivated to dive into the math. It even provides an intro to number theory, so it’s great if it’s your first time learning this sort of thing.
Mastering Bitcoin by Andreas Antonopolous: A must read!


Also published on Medium.

2 thoughts on “Bitcoin: What’s the Math?”

Leave a Reply

Your email address will not be published. Required fields are marked *