Sunday, 28 June 2015

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!


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


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




ECC Key Sizes:
Atoms in universe:
Collision resistance:
EC Domain parameters:
Double spending:
Original Bitcoin Paper:
Block Chains:
Ripple Labs:
Adam Back:
Merkle Tree:

String to bits

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


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

Digital signature and verification


import java.util.Base64

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

  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")
  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")
  val result = signature.verify(sig)
  <<(s"Verified signature: $result")
  def main(args: Array[String]): Unit = {
  def <<(any: AnyRef) = println(any)
Output is
Private Key
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


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
    def helper(nonce: Int, iter: Int): Option[Int] = {
      if (iter > maxIter) None
      else {
        val datum = data + nonce
        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")


Hemant said...

Nice article. Very comprehensively defined! It looks so complicated but when looking at the code and explanations it seems to be bit simpler.

Thierry Janaudy said...

Thanks Hemant. The more I study, the more I understand all the low level details.
There are some inaccuracies in my blog post, but to the expert, they are easy to spot.
To the novice, I just want to give them an incentive to learn more.

Bob said...

omg TJ not sure how I landed on this page but what an awesome blog!
reminded me all the way back to final year at Uni and my favourite course computer cryptography and my favourite instructor :)

Blogger said...

YoBit lets you to claim FREE CRYPTO-COINS from over 100 unique crypto-currencies, you complete a captcha one time and claim as much as coins you want from the available offers.

After you make about 20-30 claims, you complete the captcha and keep claiming.

You can click CLAIM as much as 30 times per one captcha.

The coins will held in your account, and you can exchange them to Bitcoins or Dollars.

Blog Archive