The Mathematics Behind Crypto-Currencies

The mathematics behind crypto-currencies

Crypto-currencies (bitcoin et al) have caught the attention of Governments, enforcement agencies, geeks, and the general public. This course provides a simple introduction to crypto-currencies and briefly introduces terms such as cryptography, hash functions, proof-of-work, digital signatures, mining, Merkle root & tree, crypto-currency addresses, and wallets.

Note: Although this course mentions Bitcoin, most of it applies to any system that “uses public-key cryptography, peer-to-peer networking, and proof-of-work to process and verify payments”.

Note: This course is intended for the novice reader and may suffer from errors inherent when a complex topic is (over?) simplified.

1. Evolution of money

From cowry shells to the blockchain

Our ancestors started off with the barter system — something like “I will give you 2 buffaloes in return for 5 shiny new super-sharp axes”. Soon they realised that the barter system had too many limitations — everyone didn’t want buffaloes, buffaloes were neither divisible (not too many people would want 0.35 buffaloes) nor very portable (imagine having to carry a buffalo on your shoulders while going shopping).

So they moved on to more acceptable, divisible, homogeneous, and portable forms of money — cowry shells, salt, gold, silver, and lots more. The Chinese invention of paper eventually led to the birth of paper currency, which was initially backed by gold or other precious metals. Then the world moved on to fiat money — the currency that’s declared as legal tender by a government but not backed by a physical commodity.

This brings us to an essential question — what is money? Money’s a matter of functions four, a Medium, a Measure, a Standard, a Store. So goes the couplet based on William Stanley Jevons analysis of money in 1875. This meant that for something to be called as money, it must function as a medium of exchange, a measure of value, a standard of deferred payment and a store of value.

The birth of computers and the Internet brought in many electronic payment systems including debit cards, stored value cards, giro transfers, credit cards, net-banking, electronic bill payments, electronic cheques, mobile wallets, digital gold currencies, digital wallets, electronic funds transfer at point of sale, mobile banking, SMS banking, online banking, payment cards, real-time gross settlement systems, SWIFT, wire transfers and more.

And then came Satoshi Nakamoto’s path breaking whitepaper — Bitcoin: A Peer-to-Peer Electronic Cash System in October 2008. This brought the world its first truly peer-to-peer electronic currency.

Bitcoin earned a lot of notoriety primarily because of its use by members of the now shut-down Silk Road — an illegal online marketplace that facilitated the sale of hundreds of millions of dollars worth of drugs, guns, stolen financial information, counterfeit documents and more. All Silk Road transactions were conducted exclusively in bitcoin.

A lot of crypto-currencies piggybacked on Bitcoin’s underlying innovation — the blockchain. In fact we now have hundreds of virtual currencies being used around the world. And now we have become a world where bankers wake up each morning wondering — “ has the meaning of money and banking changed while I slept “.

This rapid change in the global money ecosystem has implications for all of us — from Governments looking to clamp down on money laundering, tax evasion, and terrorist funding to banks looking to understand the implications of the blockchain technology. From law enforcement looking to clamp down on the Mafia using Bitcoin to businesses looking for faster and cheaper ways to receive and transfer money globally.

2. Math Money

The mathematics behind crypto-currencies

Sanya’s a naughty young girl who’s been grounded for a week. She wants to sneak out for desert with her friends but obviously can’t let her dad know about it. She’s not allowed to use her cellphone, so the only way for her to call her friends is by using the good old landline in her dad’s room.

Since she regularly gets grounded, she and her friends have worked out a simple system for sharing secrets. When she says, “ have you read the book I told you about” she actually means “ let’s sneak out tonight”. When she says something about “ page 10” of the book, she means “ pick me up at 10 pm “. Continuing the logic, page 11 would mean 11 pm and so on.

So on the phone she asks her friend “ Have you read the book I told you about? Page 12 is really funny”, she means, “ Let’s sneak out tonight, pick me up at midnight “.

What we have just seen is cryptography (and a rebellious teenager) in action in the real world.

The sentence “Let’s sneak out tonight, pick me up at midnight” is plain text — what Sanya actually wants to convey. The sentence “Have you read the book I told you about? Page 12 is really funny” is the cipher text — something that an adversary (her dad in this case) should not be able to understand.

Encryption is the process of converting plain text to cipher text. The reverse process is decryption.

2.1 Symmetric Cryptography

This science of encrypting and decrypting messages ( cryptography) has been used for thousands of years. It is believed that when Julius Caesar sent messages to his generals, he replaced every A in his messages with a D, every B with an E, and so on through the alphabet. Only someone who knew the “shift by 3” rule could decipher his messages.

For example, if we want to encode the word “SECRET” using Caesar’s key value of 3, we offset the alphabet so that the 3rd letter down, (D), begins the alphabet.

So starting with ABCDEFGHIJKLMNOPQRSTUVWXYZ

and sliding everything up by 3, you get

DEFGHIJKLMNOPQRSTUVWXYZABC

where D=A, E=B, F=C, and so on.

Using this scheme, the plaintext, “SECRET” encrypts as “VHFUHW”. To allow someone else to read the cipher text, you tell him or her that the key is 3. This method is called symmetric cryptography and involves using the same key for encrypting as well as decrypting a message. This naturally poses a serious problem — what if an adversary gets hold of this key? At some point of time the sender and receiver need to exchange the key. That’s when an adversary could get hold of the key. In modern cryptography, keys are really really large numbers.

2.2 Asymmetric Cryptography & the RSA algorithm

The secure-key-exchange problem was solved with the birth of asymmetric key cryptography — in which two different but related keys are used — the public key to encrypt data and the corresponding private key to decrypt the data. If Sanya were to send an encrypted message to Karan, she would encrypt the message using his public key (which is available to the world). Once encrypted, the message can only be decrypted using Karan’s private key (which would only be available to Karan).

To understand how this works, lets look at the RSA algorithm (named after its inventors Ron Rivest, Adi Shamir, and Leonard Adleman).

The RSA public-key encryption algorithm works in the following manner:

  1. Generation of a public-private key pair.
  2. Encryption of a message (plain text) with the public key generated in step (1) to get the cipher-text.
  3. Decryption of the cipher-text by using the corresponding private key generated in step (1).

Step 1: Generation of a key pair

  1. Select two large integer primes p and q.
  2. Obtain φ which is the product of (p-1) and (q-1), that means
  3. Select e such that 1<e<φ and the greatest common divisor of e and φ is 1. That means e and φ are coprime.
  4. Compute d such that 1<d<φ and ed ≡ 1 mod φ. This means that the value of d must be such that ed-1 should be completely divisible by φ or (ed-1) / φ should be an integer.
  5. The public-key is (e, n) and the corresponding private key is (d, n).

Step 2: Encryption process

Suppose the message to be encrypted is m. The cipher-text c is obtained by raising the message to the value of e and finding out its modulo n.

That means c = m^e mod n.

Step 3: Decryption process

Decryption is achieved by raising the cipher-text c obtained in step 2 to the value of d and finding out its modulo n.

That means m=c^d mod n.

Let’s try the algorithm with really small prime numbers: 3 and 11. (In reality, the primes chosen would be really really large).

  1. Compute φ = ( p — 1) * ( q — 1) = 2 * 10 = 20
  2. Compute a value for such that 1<d<φ and ed ≡ 1 mod φ. One solution is d = 3.
  3. Public key is ( e, n) => (7, 33) and Private key is ( d, n) => (3, 33)
  4. Suppose the plain text is 2. The ciphertext will be c = m^e mod n. That’s 2⁷ mod 33 = 128 mod 33 = 29
  5. The decryption will be c^d mod n = 29³ mod 33 = 24389 mod 33 = 2

The security of the RSA cryptosystem is based on the integer factorization problem. Any adversary who wishes to decipher the cipher-text c must do so by using the publicly available information (n, e). One possible method is to first factor n, and then compute φ and d just as was done in the above mentioned steps. The factoring of n is currently computationally infeasible (provided sufficiently large prime numbers are chosen as p and q) and therein lays the strength of the RSA cryptosystem.

The security of the RSA cryptosystem is based on the integer factorization problem. Any adversary who wishes to decipher the cipher-text c must do so by using the publicly available information (n, e). One possible method is to first factor n, and then compute φ and d just as was done in the above mentioned steps. The factoring of n is currently computationally infeasible (provided sufficiently large prime numbers are chosen as p and q) and therein lays the strength of the RSA cryptosystem.

2.3 Hash functions

Before we get into the nuts and bolts of how crypto-currencies work, we need to understand some more concepts including hash functions. A one-way hash function takes an input (e.g. a PDF file, a video, an email, a string etc.) and produces a fixed-length output e.g. 160-bits.

The hash function ensures that if the information is changed in any way — even by just one bit — an entirely different output value is produced. The table below shows some sample output values using the sha1 (40) hash function.

Input: sanya
Hash: c75491c89395de9fa4ed29affda0e4d29cbad290

Input: SANYA
Hash: 33fef490220a0e6dee2f16c5a8f78ce491741adc

Input: Sanya
Hash: 4c391643f247937bee14c0bcca9ffb985fc0d0ba

Computing hash of an electronic record is a very simple process. E.g. in php it can be done with: 

hash_file(‘sha256’, $filename)

It can be seen from the table above that by changing the input from sanya to SANYA, an entirely different hash value is generated. What must be kept in mind is that irrespective of the size of the input, the hash output will always be of the same size.

Two things must be borne in mind with regard to one-way hash functions:

  1. It is computationally infeasible to find two different input messages that will yield the same hash output.
  2. It is computationally infeasible to reconstruct the original message from its hash output.

2.4 Proof of work

Having understood hash functions, let’s have a look at another interesting concept called proof-of-work. This is a way to reduce spam and denial of service attacks by requiring a computer to spend some time and processing power to solve something.

rn@asianlaws.org: info@lexcode.com:18032016:xxxx

One such proof-of-work system that is used in crypto-currencies is hashcash. The basic premise of hashcash is that if the sender of an email can prove that she has spent reasonable time and computational power to solve some puzzle, it can be believed that the sender is not a spammer. The logic is that spamming would be economically infeasible if a spammer had to spend non-trivial time and computational power for every single email being sent.

Let’s develop an elementary proof-of-work system, based on hashcash, which can be used to control spam. Let’s presume that rn@asianlaws.org is sending an email to info@lexcode.com. The sender must include something similar to the following in the header of the email:

That’s 4 pieces of information separated by colons. The first piece is the sender’s email address, the second is the receiver’s email address and the third is the current date in DDMMYYYY format. The fourth piece is something that needs to be calculated by the sender’s computer. Let’s call it a nonce.

The objective is to find an input that would result in a sha256 hash which begins with 5 zeros.

So we start the nonce at a value of 0 and then keep incrementing it (1, 2, 3 … ) and calculating the hash. Something like this:

rn@asianlaws.org:info@lexcode.com:18032016:1
sha256 hash 288721860bec3a490811981c831702d4f41e54c3f8c183c5650ac73ff231659c

rn@asianlaws.org:info@lexcode.com:18032016:2
sha256 hash 11caf434535c35cdc843e801382f0a8643a03500649a9bfa41c8e6a4be65a413

rn@asianlaws.org:info@lexcode.com:18032016:3
sha256 hash aad80b9c58e977a5da90f81b2667af443b50425876920528f237df0a6ffe1aa4

And so on till .. 1580661

rn@asianlaws.org:info@lexcode.com:18032016:1580661
sha256 hash 0000080602f705257e74a4e847e9ed23ab61be5b2ba4263fbacc90bd7c7c7ab4

Calculating this may not take a genuine sender a lot of time and computational power but if a spammer were to make these calculations for millions of emails, it will take a non-trivial amount of time and computational power.

At the receiver’s end, the computer will simply take the following line from the header of the email and calculate the hash.

rn@asianlaws.org:info@lexcode.com:18032016:1580661

If the hash begins with a pre-defined number of zeros (5 in this example), the email would not be considered spam. This will take the receiver a trivial amount of time and computational power since it just has to calculate the hash of one input. The date can be used as an additional validation parameter — e.g. if the date is within 24 hours of the time of receipt, the email will be approved for download.

2.5 Digital Signatures

A very important application of public key cryptography is a digital signature. In this, the signer first calculates the hash of the message she wants to digitally sign. Then using her private key and the hash, she creates a digital signature, using the relevant algorithm.

This digital signature is unique to the message.

The signer then sends the message and the digital signature to the receiver. The receiver re-computes the hash from the message. The receiver also computes another string using the digital signature and the signer’s public key (using the relevant algorithm). If this string and the hash match, the digital signature is verified.

Blind digital signatures were subsequently developed for use in digital cash and cryptographic voting systems. In this system, the content of the message is disguised before it is signed. The resulting blind signature can be verified against the original, un-blinded message in the manner of a regular digital signature (Source).

An often-used analogy to the cryptographic blind signature is the physical act of a voter enclosing a completed anonymous ballot in a special carbon paper lined envelope that has the voter’s credentials pre-printed on the outside. The ballot can be marked through the envelope by the carbon paper. The voter hands the sealed envelope to an official who verifies the credentials and signs it. Once signed, the package is given back to the voter, who transfers the now signed ballot to a new unmarked normal envelope. Thus, the signer does not view the message content, but a third party can later verify the signature and know that the signature is valid within the limitations of the underlying signature scheme.

However, blind digital signatures do not solve the double-spending problem. In case of physical currency notes, you cannot double-spend a note because once you hand the note over to someone, you don’t have the note anymore to spend again. Since electronic records are easily duplicated, a “digital coin” can be spent multiple times.

2.6 Merkle root

Bitcoin solves the double-spending problem through the blockchain — a public ledger containing an ordered and time-stamped record of transactions. In addition to preventing double-spending, the blockchain prevents the modification of previous transaction records.

A block of one or more new transactions is collected into the transaction data part of a block. Copies of each transaction are hashed, and the hashes are then paired, hashed, paired again, and hashed again until a single hash remains, the Merkle root of a Merkle tree. [Source

Lets consider a simple illustration of how the blockchain works. Consider a block that has 6 transactions a, b, c, d, e and f.

The merkle tree is:

d1 = double-hash (a)
d2 = double-hash (b)
d3 = double-hash (c)
d4 = double-hash (d)
d5 = double-hash (e)
d6 = double-hash (f)

d7 = double-hash (d1 concatenated with d2)
d8 = double-hash (d3 concatenated with d4)
d9 = double-hash (d5 concatenated with d6)
d10 = double-hash (d7 concatenated with d8)
d11 = double-hash (d9 concatenated with d9)

Since there are an odd number of hashes, we take d9 twice

d12 = double-hash (d10 concatenated with d11)

d12 is the merkle root of the 6 transactions in this block. This is stored in the block header. Additionally, each block also stores the hash of the header of the previous block. This chains the blocks together and ensures that a transaction cannot be modified without modifying the block that records it and all following blocks. Transactions are also chained together.

2.7 Blockchain

2.8 How Bitcoin works

Bitcoin uses a proof-of-work technique similar (but more complex) than the one discussed earlier in this document. Since good cryptographic hash algorithms convert arbitrary inputs into “seemingly-random” hashes, it is not feasible to modify the input to make the hash predictable. To prove that she did some extra work to create a block, a miner must create a hash of the block header, which does not exceed a certain value.

The term miner must not be compared with a gold or coal miner in the real world. While a gold miner digs into the earth to discover gold, a bitcoin miner uses computational power to calculate hashes. To add an entire block to the blockchain, a Bitcoin miner must successfully hash a block header to a value below the target threshold. Bitcoin miners spend a lot of money (for computational power and electricity) and are compensated by way of a reward for each block they mine — this was initially 50 bitcoins per block and is halving every 210,000 blocks. Miners also earn transaction fees. Miners usually operate as part of a large pool instead of as individuals.

Interestingly, Bitcoins can be also be mined with a pencil and paper.

The first-ever Bitcoin block is known as the genesis block. Each subsequent block is addressed by its block height, which represents the number of blocks between it and the genesis block.

New blocks are added to the block chain if their hash is at least as challenging as a difficulty value expected by the Bitcoin consensus protocol. According to the bitcoin protocol, it should take 2 weeks for 2016 blocks to be generated. If the time taken is more or less than 2 weeks then the difficulty value is relatively decreased or increased.

A Bitcoin address is an identifier of 26 to 35 alphanumeric characters, beginning with the number 1 or 3, which represents a possible destination for a bitcoin payment. Addresses can be generated at no cost by any user of Bitcoin (Source).

Bitcoin wallets at their core are a collection of private keys. These collections are stored digitally in a file, or can even be physically stored on pieces of paper. The simplest Bitcoin wallet is a program, which performs these functions (Source).

  • it generates private keys,
  • derives the corresponding public keys,
  • helps distribute those public keys as necessary,
  • monitors for outputs spent to those public keys,
  • creates and signs transactions spending those outputs, and
  • broadcasts the signed transactions.

Although it’s called a wallet, a Bitcoin wallet does not store bitcoins. The wallet is a collection of public-private key-pairs.

As discussed, the blockchain is a database of transaction information. It is constantly growing and is sent out to all nodes in the Bitcoin network. Every transaction is distributed to the network and all valid transactions are included in the next block, which is mined.

Imagine a real-world transaction where your salary is transferred to your bank account through an online transfer made by your employer. You then use your debit card to pay for dinner. This transfers some of the money to the restaurant’s account. In these 2 transactions, did you see a single currency note? No. So we can say that in today’s world most money exists as a history of transactions and balances.

Bitcoin, or for that matter most virtual currencies work the same way. They don’t actually “exist” in the true sense of the word. They just are there!

A bitcoin can be divided down to 8 decimal places — 0.00000001 is the smallest amount, also referred to as a satoshi. The last block that will generate bitcoins will be block 6,929,999. This is expected to be generated around the year 2140. After that, the total number of bitcoins will remain static at just below 21 million.