Math Money: A simple introduction to crypto-currencies

Abstract: Crypto-currencies (bitcoin et al) have caught the attention of Governments, enforcement agencies, geeks and the general public. This document 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. This document is intended for the novice reader and may suffer from errors inherent when a complex topic is (over?) simplified.

Note: Although this document 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 document 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 - currency that's declared as legal tender by a government but not backed by a physical commodity[1].

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[2]. 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[3] piggybacked on Bitcoin’s underlying innovation – the blockchain. In fact we now have more than 650 virtual currencies[4] 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. The mathematics of it all

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

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.

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

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[6].

Input: sanya
Hash:  c75491c89395de9fa4ed29affda0e4d29cbad290

Input: SANYA
Hash:  33fef490220a0e6dee2f16c5a8f78ce491741adc

Input: Sanya
Hash:  4c391643f247937bee14c0bcca9ffb985fc0d0ba

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.

Having understood hash functions, let’s have a look at another interesting concept calledproof-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.

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:

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

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:

Input: rn@asianlaws.org:info@lexcode.com:18032016:1
Hash: 288721860bec3a490811981c831702d4f41e54c3f8c183c5650ac73ff231659c

Input: rn@asianlaws.org:info@lexcode.com:18032016:2
Hash:  11caf434535c35cdc843e801382f0a8643a03500649a9bfa41c8e6a4be65a413

Input: rn@asianlaws.org:info@lexcode.com:18032016:3
Hash:  aad80b9c58e977a5da90f81b2667af443b50425876920528f237df0a6ffe1aa4

And so on till .. 1580661

Input: rn@asianlaws.org:info@lexcode.com:18032016:1580661
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.

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[7].

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.

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[8].

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.

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 block chain, 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[9].

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

The overview of the Bitcoin process is explained very well on Ken Shirriff's blog[10].

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[11].

There are currently two address formats in common use:

Common P2PKH which begin with the number 1
Example: 1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2 

Newer P2SH type starting with the number 3
Example: 3J98t1WpEZ73CNmQviecrnyiWrnqRhWNLy 

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[12]:

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

3. Additional reading and other resources

1. Blind Digital Signatures 

2. Bitcoin: A Peer-to-Peer Electronic Cash System

3. Bitcoin wiki

4. FATF Report on Virtual Currencies Key Definitions and Potential AML/CFT Risks

[1] Have a look at a 100-rupee note. It caries a promise signed by the Governor of the Reserve Bank of India (RBI) – “I promise to pay the bearer the sum of one hundred rupees”. If you were to take this note to the Governor of the RBI, he would give you coins or one-rupee notes totaling 100 rupees. The RBI gets the power to issue currency notes by section 31 of the Reserve Bank of India Act, 1934. This section states that “No person in India other than the Bank or, as expressly authorized by this Act, the Central Government shall draw, accept, make or issue any bill of exchange, hundi, promissory note or engagement for the payment of money payable to bearer on demand, or borrow, owe or take up any sum or sums of money on the bills, hundis or notes payable to bearer on demand of any such person…”

[2] Virtual currency is a digital representation of value that can be digitally traded and functions as (1) a medium of exchange; and/or (2) a unit of account; and/or (3) a store of value, but does not have legal tender status (i.e., when tendered to a creditor, is a valid and legal offer of payment) in any jurisdiction. It is not issued nor guaranteed by any jurisdiction, and fulfils the above functions only by agreement within the community of users of the virtual currency. Virtual currency is distinguished from fiat currency (a.k.a. “real currency,” “real money,” or “national currency”), which is the coin and paper money of a country that is designated as its legal tender; circulates; and is customarily used and accepted as a medium of exchange in the issuing country. It is distinct from e-money, which is a digital representation of fiat currency used to electronically transfer value denominated in fiat currency. E-money is a digital transfer mechanism for fiat currency—i.e., it electronically transfers value that has legal tender status. [Source: FATF report on Virtual Currencies - Key Definitions and Potential AML/CFT Risks]

[3] Cryptocurrency refers to a math-based, decentralised convertible virtual currency that is protected by cryptography. - i.e., it incorporates principles of cryptography to implement a distributed, decentralised, secure information economy. Cryptocurrency relies on public and private keys to transfer value from one person (individual or entity) to another, and must be cryptographically signed each time it is transferred. The safety, integrity and balance of cryptocurrency ledgers is ensured by a network of mutually distrustful parties (in Bitcoin, referred to as miners) who protect the network in exchange for the opportunity to obtain a randomly distributed fee (in Bitcoin, a small number of newly created bitcoins, called the “block reward” and in some cases, also transaction fees paid by users as a incentive for miners to include their transactions in the next block). Hundreds of cryptocurrency specifications have been defined, mostly derived from Bitcoin, which uses a proof- of-work system to validate transactions and maintain the block chain. While Bitcoin provided the first fully implemented cryptocurrency protocol, there is growing interest in developing alternative, potentially more efficient proof methods, such as systems based on proof-of-stake. [Source: FATF report on Virtual Currencies - Key Definitions and Potential AML/CFT Risks]

[4] Source: www.mapofcoins.com, retrieved on 19th March, 2016.

[5] Source: https://www.cs.utexas.edu/~mitra/honors/soln.html

[6] Computing hash of an electronic record is a very simple process. E.g. in php it can be done with: hash_file('sha256', $filename).

[7] Source: https://en.wikipedia.org/wiki/Blind_signature. 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.

[8] Source: https://bitcoin.org/en/developer-guide#block-chain-overview

[9] See: http://www.righto.com/2014/09/mining-bitcoin-with-pencil-and-paper.html

[10] To simplify slightly, bitcoins consist of entries in a distributed database that keeps track of the ownership of bitcoins. Unlike a bank, bitcoins are not tied to users or accounts. Instead bitcoins are owned by a Bitcoin address, for example 1KKKK6N21XKo48zWKuQKXdvSsCf95ibHFa. A transaction is the mechanism for spending bitcoins. In a transaction, the owner of some bitcoins transfers ownership to a new address. A key innovation of Bitcoin is how transactions are recorded in the distributed database through mining. Transactions are grouped into blocks and about every 10 minutes a new block of transactions is sent out, becoming part of the transaction log known as the blockchain, which indicates the transaction has been made (more-or-less) official. Bitcoin mining is the process that puts transactions into a block, to make sure everyone has a consistent view of the transaction log. To mine a block, miners must find an extremely rare solution to an (otherwise-pointless) cryptographic problem. Finding this solution generates a mined block, which becomes part of the official block chain.

Mining is also the mechanism for new bitcoins to enter the system. When a block is successfully mined, new bitcoins are generated in the block and paid to the miner. This mining bounty is large - currently 25 bitcoins per block. In addition, the miner gets any fees associated with the transactions in the block. Because of this, mining is very competitive with many people attempting to mine blocks. The difficulty and competitiveness of mining is a key part of Bitcoin security, since it ensures that nobody can flood the system with bad blocks.

There is no centralized Bitcoin server. Instead, Bitcoin runs on a peer-to-peer network. If you run a Bitcoin client, you become part of that network. The nodes on the network exchange transactions, blocks, and addresses of other peers with each other. When you first connect to the network, your client downloads the blockchain from some random node or nodes. In turn, your client may provide data to other nodes. When you create a Bitcoin transaction, you send it to some peer, who sends it to other peers, and so on, until it reaches the entire network. Miners pick up your transaction, generate a mined block containing your transaction, and send this mined block to peers. Eventually your client will receive the block and your client shows that the transaction was processed.

Bitcoin uses digital signatures to ensure that only the owner of bitcoins can spend them. The owner of a Bitcoin address has the private key associated with the address. To spend bitcoins, they sign the transaction with this private key, which proves they are the owner. (It's somewhat like signing a physical check to make it valid.) A public key is associated with each Bitcoin address, and anyone can use it to verify the digital signature.

Blocks and transactions are identified by a 256-bit cryptographic hash of their contents. This hash value is used in multiple places in the Bitcoin protocol. In addition, finding a special hash is the difficult task in mining a block.

[11] Source: https://en.bitcoin.it/wiki/Address. The technical process to create Bitcoinaddresses is explained as under:

• Step 0: Having a private Elliptic Curve Digital Signature Algorithm key:

18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725

• Step 1: Take the corresponding public key generated with it:

0450863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B23522CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6

• Step 2: Perform SHA-256 hashing on the public key

600FFE422B4E00731A59557A5CCA46CC183944191006324A447BDB2D98D4B408

• Step 3: Perform RIPEMD-160 hashing on the result of SHA-256

            010966776006953D5567439E5E39F86A0D273BEE

• Step 4: Add version byte in front of RIPEMD-160 hash (0x00 for Main Network)

00010966776006953D5567439E5E39F86A0D273BEE

(note that below steps are the Base58Check encoding[11])

• Step 5: Perform SHA-256 hash on the extended RIPEMD-160 result

            445C7A8007A93D8733188288BB320A8FE2DEBD2AE1B47F0F50BC10BAE845C094

• Step 6: Perform SHA-256 hash on the result of the previous SHA-256 hash

            D61967F63C7DD183914A4AE452C9F6AD5D462CE3D277798075B107615C1A8A30

• Step 7: Take the first 4 bytes of the second SHA-256 hash. This is the address checksum

            D61967F6

• Step 8: Add the 4 checksum bytes from the previous stage at the end of extended RIPEMD-160 hash from stage 4. This is the 25-byte binary Bitcoin Address.

                  00010966776006953D5567439E5E39F86A0D273BEED61967F6

• Step 9: Convert the result from a byte string into a base58 string using Base58Check encoding. This is the most commonly used Bitcoin Address format

                  16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM

[12] https://bitcoin.org/en/developer-guide#wallet-programs