Bitcoins for the impatient (and for my mum)

Bitcoins for the impatient and for my mum

You can find all sorts of explanation on Internet with regards to Bitcoins (A bitcoin is a virtual or crypto currency) technologies and protocols.
However, I have not found a reference where I could point my mum to - a simple page explaining what is Bitcoins, how it works, in layman terms.
This is my attempt at explaining bitcoins. Mum, be patient. Read through it and then we will talk. Let’s start with some cryptography concepts.

Cryptography concepts

It is quite unfortunate - but to understand bitcoins and the fancy distributed ledger concept you have to understand a little bit of cryptography.
Do not be scared.
Behind the mathematical complexity of asymmetric encryption lies a very simple concept: it is easy to multiply, but very hard to factorize.
This is the concept behind asymmetric cryptosystems such as RSA (Rivest Shamir Adleman) and ECC (Elliptic Curve Cryptography), where the public key is known to everyone, but the private key only known to you.
Throughout the years, the best way I have found to explain this is to take the following example.
There is an inherent relationship between the public key and the private key, but what is it?
Take the following number, 221, and treat it as my public key. Everyone knows I am the owner of a public key of value 221.
My public key is the product of two prime numbers (a natural number greater than 1 that has no positive divisors other than 1 and itself.).
It would probably take two 1 or 2 minutes to figure out what those numbers are.
You will find that 221 = 13 * 17.
My private key is the pair (13, 17), supposedly only known to me.

It is very easy to compute the public key (221) knowing the private key (13, 17) but a lot more difficult to factorize 221 to find (13, 17). Whereas the multiplication would take you 5 seconds to do, it would take you 60 seconds or more to find the factors.

That’s it. You got it. RSA, ECC the most two famous asymmetric crypto systems are simply based on that principle!

RSA or ECC?

Bitcoins uses ECC, not RSA, mainly because the key sizes are much shorter in ECC than in RSA for the same cryptography strength.
An ECC key size of 160 bits is equivalent to a RSA key size of 1024, ECC 256 to RSA 3072, etc.
Shorter size usually means less space to take, and less computing power needed.

Hold on son, bits, what are bits?

Mum, a bit is either 1 or 0. Computers work like that.. yeah sorry.
So anything we deal with, like I am typing this, is translated at some point into a series of 1 and 0, “base 2”, or binary representation.
For example, the sentence, “Les sanglots longs des violons de l'automne” translates into:
1001100, 1100101, 1110011, 100000, 1110011, 1100001, 1101110, 1100111, 1101100, 1101111, 1110100, 1110011, 100000, 1101100, 1101111, 1101110, 1100111, 1110011, 100000, 1100100, 1100101, 1110011, 100000, 1110110, 1101001, 1101111, 1101100, 1101111, 1101110, 1110011, 100000, 1100100, 1100101, 100000, 1101100, 100111, 1100001, 1110101, 1110100, 1101111, 1101101, 1101110, 1100101

I am sure you are quite happy to know that!?

Bitcoins uses key lengths of 256 bits

This is a large number, quite large.
2^256 = 115792089237316195423570985008687907853269984665640564039457584007913129639936
There are 78 digits in the above number. It is slightly less than 10^77
FYI, the number of atoms in the observable universe is 10^80
You now see how hard it can be to factorize a number as big as this!

Alright, so what? I have large numbers, a public key and a private key

Each transaction (to send or receive money) of bitcoins is made public. How do we know the transaction comes from you, the public key owner?
By digitally signing it.
Digital signatures use your private key and the resulting computation can be checked or verified using your public key!
Bitcoins uses SHA256 - a secure hash function. (They are actually hashing twice, using two different algorithms, but we want to keep this simple, right!)
Behind the barbaric term hash function, or one-way hash function, lies another simple concept, “collision resistance”, i.e., it is hard to find two different inputs to the function that would produce the same output or hash.

I am a bit confused: how does SHA (hash function) relate to public/private keys?

They are both needed to digitally sign an electronic document, or bitcoin transaction.
SHA produces a fingerprint. The private keys signs the fingerprint, producing an electronic signature.
This electronic signature can be verified by anyone using your public key.

Standards exist so that implementors of cryptographic systems can talk to each other. Bitcoins relies on ECDSA (Elliptic Curve Digital Signature Algorithm).

Ok, I think I get it

Each transaction in the Bitcoins network is checked using cryptographic concepts such as ECC, SHA, ECDSA - those transactions are made public and inserted into a public ledger.
The public ledger is composed of block chains - and the key principle of Bitcoins’ implementation is that there is no central authority.
If there is no central authority, how do they avoid double spending or duplicate transactions?

This is what the Double-Spending link says:
“Bitcoin protects against double spending by verifying each transaction added to the block chain to ensure that the inputs for the transaction had not previously already been spent.”
A transaction is considered valid when confirmation takes place: meaning that is has been mined with a depth of one, then, the transaction is inserted into the a block chain.

How confirmation works is very innovative. How does it work?

Block chains? Confirmation?
A block chain is a set of transaction that potentially contains all transactions ever executed up to the genesis block (The first block ever created).
Each block contains a hash (now you know what it is) of the previous block and so forth.
This is the most important part of Bitcoins, the innovation, how do transactions get validated without a central authority and how to stop double-spending.
The original paper introduces the concept of timestamps, via a timestamp server.
The idea to avoid double-spending is to detect if an owner did not sign an earlier transaction. If there is an attempt to sign a later transaction, it would be ignored.

The timestamp server (I am quoting the paper here) “works by taking a hash of a block of items to be timestamped and widely publishing the hash, such as in a newspaper (...). The timestamp proves that the data must have existed at the time, obviously, in order to get into the hash. Each timestamp includes the previous timestamp in its hash, forming a chain, with each additional timestamp reinforcing the ones before it”. (See Section 3 of the original paper from Satoshi Nakamoto).

Now it makes sense. The brain (or set of brains) behind Bitcoins, Satoshi Nakamoto, introduces a timestamp server that creates a set of hashes that are broadcasted to the network, proving the existence of data.
Also, as stated before, each block having a reference to the hash of the previous block makes difficult to modify one block as it would imply modifying all the blocks before it in the chain.
By difficult, I mean computationally difficult or very hard to do.

This block chain concept is actively used by startups in FinTech. Check the reference for Ripple Labs.

Are we done? I am falling asleep. Hold on, no central authority?

Yes, no central authority. The use of a single timestamps server would makes things easier… but as Bitcoins is designed to work on a peer-to-peer network (P2P: a bunch of computers collaborating to achieve some common goal), this timestamp server needs to work on a P2P basis.
This concept took me a short while to get - what Satoshi Nakamoto refers to as “proof of work”.
The idea, at least as I understand it, is that you do not want to give the decision to (in)validate a set of transactions to a unique entity or to a set of individuals, this would defeat the purpose of “no central authority”.

How do you achieve fairness in the decision process on a distributed peer-to-peer network? This part is key and is the true innovation of Bitcoins.

Think about it.

Bitcoins uses a concept called “hashcash” invented by the cryptographer Adam Back.
All “miners” (the people validating the transaction for a small fee) compete by trying to find a solution to a problem (they receive the transactions to validate). The winner inserts the transactions into a block chain, etc., and the start competing again to validate the next set of transactions.
What is this problem? It is about finding a hash that satisfies a pattern. There is a difficulty target that is automatically adjusted every two weeks by the Bitcoins network.

Ok, it is still a little bit cryptic.It is a beauty. Let me try to explain a little bit better.

Imagine a network of “miners” - people/computers validating transactions for acceptance by the whole network. Let’s say we have 10.
We do not want one computer, or a set of computers to take over the control of blocks generation.
Those 10 miners constantly compete by computing a hash tied to the data of the block being mined. The winner is the one who finds a hash that matches a dynamically adjusted pattern.

More details please.

The idea is to calculate the SHA256 for example on a data block until the resulting hash would match a pattern. (In reality, it is a bit more complex, you need to worry about Merkel trees, longest chains, mining depth, etc.).
What is this pattern? It can be as simple as finding a hash whose prefix contains a specific number of 0s. The more 0s to find, the more time-consuming for the miner, the more difficult.

Nothing beats an example. (Code is below).

Let’s take this block of data, the string “Les sanglots longs des violons de l'automne”.
To find the SHA256 with 3 0s takes 27,228 iterations in 20 milliseconds, with the resulting hash: 000NL9xhiJT093++6ai2tyUm0SiDvvakO4RyI86zzTw=
To find the SHA256 with 4 0s takes 17,770,201 iterations in 14 seconds, with the resulting hash: 0000i0Myy+PtP8FFu11+20UDVRaS0WJyPz+dZI6dWGY=
It is a crypto lottery process.

As mentioned by Satoshi Nakamoto, “proof-of-work” is essentially "one-CPU-one-vote”.

Summary

Tried my best to conceptualize Bitcoins. This is it in small nutshell. There is obviously a lot more to it: wallets, addresses, what is a transaction, etc.
At least now I hope that you have the appetite to go and learn more. Lots of links below.
I highly recommend this Mastering Bitcoin: Unlocking Digital Cryptocurrencies from Andreas M. Antonopoulos

Thanks

TJ

Links

RSA: https://en.wikipedia.org/wiki/RSA_(cryptosystem)
ECC: https://en.wikipedia.org/wiki/Elliptic_curve_cryptography
ECC Key Sizes: https://www.nsa.gov/business/programs/elliptic_curve.shtml
Atoms in universe: http://www.universetoday.com/36302/atoms-in-the-universe/
Collision resistance: https://en.wikipedia.org/wiki/Collision_resistance
ECDSA: https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
EC Domain parameters: https://tools.ietf.org/html/draft-ietf-pkix-ecc-nist-recommended-curves-00
Double spending: https://en.bitcoin.it/wiki/Double-spending
Confirmation: https://en.bitcoin.it/wiki/Confirmation
Original Bitcoin Paper: https://bitcoin.org/bitcoin.pdf
Block Chains: https://en.bitcoin.it/wiki/Block_chain
Ripple Labs: http://www.smh.com.au/business/banking-and-finance/ripple-plans-to-wash-away-currency-exchange-20150506-1myyo1.html
Adam Back: http://www.cypherspace.org/adam/
Hashcash: http://www.hashcash.org/
Merkle Tree: https://en.wikipedia.org/wiki/Merkle_tree

String to bits

"Les sanglots longs des violons de l'automne".map(c => Integer.toBinaryString(c))

2^256

Use bc or

new java.math.BigInteger("2").pow(256) = 115792089237316195423570985008687907853269984665640564039457584007913129639936

Digital signature and verification

package org.tj.ecc

import java.security.KeyPairGenerator
import java.security.spec.ECGenParameterSpec
import java.security.Signature
import java.util.Base64

object ECCTests {
  val eccKpg = KeyPairGenerator.getInstance("EC", "SunEC")
  val ecsp = new ECGenParameterSpec("secp256r1")
  eccKpg.initialize(ecsp)

  val kp = eccKpg.genKeyPair
  
  val text2sign = "Les sanglots longs des violons de l'automne"
  val ecdsa = Signature.getInstance("SHA256withECDSA", "SunEC")
  val privKey = kp.getPrivate
  <<(s"Private Key $privKey")
  ecdsa.initSign(privKey)
  ecdsa.update(text2sign.getBytes)
  val sig = ecdsa.sign
  val signatureb64 = new String(Base64.getEncoder.encode(sig))
  <<(s"Signature for text: $signatureb64")
  
  val signature = Signature.getInstance("SHA256withECDSA", "SunEC")
  val pubKey = kp.getPublic
  <<(s"Public Key $pubKey")
  signature.initVerify(pubKey)
  signature.update(text2sign.getBytes)
  val result = signature.verify(sig)
  <<(s"Verified signature: $result")
  
  def main(args: Array[String]): Unit = {
  }
  
  def <<(any: AnyRef) = println(any)
}

Output is

Private Key sun.security.ec.ECPrivateKeyImpl@9364
Signature for text: MEUCIHCss5744CdiTZB6NbjmS/KUoYij62g4MyNbzaLxDmOiAiEAjD41Rjcy91IdBGvrexRc4eFhxd884FIMQmRPCUhA2+4=
Public Key Sun EC public key, 256 bits
  public x coord: 65479953046212531738762935537232089915367280178473139038566429069872218746437
  public y coord: 54888950959211905102812252682418929722745382700581796025271727271177672920890
  parameters: secp256r1 [NIST P-256, X9.62 prime256v1] (1.2.840.10045.3.1.7)
Verified signature: true

Hashcash competition

package org.tj.ecc

import java.security.MessageDigest
import java.util.Base64
import scala.annotation.tailrec

object HashCash {
  def proofOfWork(data: String, pattern: String, maxIter: Int): Option[Int] = {
    val md = MessageDigest.getInstance("SHA-256")
    val encoder = Base64.getEncoder
    
    @tailrec
    def helper(nonce: Int, iter: Int): Option[Int] = {
      if (iter > maxIter) None
      else {
        val datum = data + nonce
        md.reset
        md.update(datum.getBytes)
        val digest = new String(encoder.encode(md.digest))
        if (digest.startsWith(pattern)) Some(nonce)
        else helper(nonce + 1, iter + 1)
      }
    }
    
    helper(0, 0)
  }
  
  def main(args: Array[String]): Unit = {
    val t0 = System.currentTimeMillis
    val result = proofOfWork("Les sanglots longs des violons de l'automne", "0000", 100000000)
    val tf = (System.currentTimeMillis() - t0)
    println(s"Result $result in $tf millis")
  }
}