In the series of posts, I am going to write about underlying technologies for crypto-currencies and smart contracts. Bitcoin is one such crypto-currency developed in the year 2009 by an unidentified person named Satoshi Nakamoto. This post is about Bitcoins, their goodness and the underlying cryptography.
What is a Bitcoin ?
It can be thought of as a digital equivalent of cash – it’s just one person transferring value to another person, no bank involved. In fact, Bitcoins are not issued by a bank or government. More specifically, Bitcoin is a peer-to-peer electronic cash system, where all online transaction can be processed without going through a financial institution or a trusted third party.
Goodness of Bitcoin or Why Bitcoin ?
- Get rid of transaction costs : Because no financial institution is needed, there is nobody charging a transaction cost. Banks, card issuers and payment processors places a 1-5% transaction fee on all the transactions we do, even for that coffee you bought this morning, and everything else you buy. This is not very visible in everyday life, because it’s almost always baked into the price of things, but if you start transferring money internationally with companies like Western Union, you realize that there is quite a bit of money in the business of transferring money.
- Take currency power away from banks and government : Banks and government have the legal and physical ability to create money. Whenever money is created, it dilutes the value of everyone’s money, which makes it a super-fast, completely silent, taxation. Sometimes, governments and banks use this power responsibly, but sometimes, they do not.
What cryptographic primitives are used in Bitcoins?
Digital Signatures : A digital signature is supposed to be the digital analog to a handwritten signature on paper. We desire two properties from digital signatures that correspond well to the handwritten signature analogy. Firstly, only you can make your signature, but anyone who sees it can verify that it’s valid. Secondly, we want the signature to be tied to a particular document so that the signature cannot be used to indicate your agreement or endorsement of a different document.
A digital signature scheme consists of the following three algorithms:
- (sk, pk) := generateKeys(keysize). The generateKeys method takes a key size and generates a key pair. The secret key sk is kept privately and used to sign messages, and the public key pk that is given to everybody, anyone with this key can verify the signature, signed using secret key sk.
- sig := sign(sk, msg) The sign method takes a message msg and a secret key sk, as input and outputs a signature for message under sk.
- isValid := verify(pk, msg, sig) The verify method takes a message msg, a signature, and a public key as input. It returns a boolean value, isValid, that will be true if sig is a valid signature for message under public key pk, and false otherwise.
We require that the following two properties hold:
- Valid signatures must verify, verify(pk, message, sign(sk, message)) == true
- Signatures are existentially unforgeable: adversary who knows pk gets to see signatures on messages of his choice can’t produce a verifiable signature on another message.
Bitcoin uses ECDSA standard (Elliptic Curve Digital Signature Algorithm)
Cryptographically secure hash functions : For a hash function to be cryptographically secure, we’re going to require that it has the following three properties:
Note that the puzzle‐friendliness property, is not a general requirement for cryptographic hash functions, but one that will be useful for cryptocurrencies.
Collision‐resistance: A hash function H is said to be collision resistant if it is infeasible to find two values, x and y, such that x ≠ y, yet H(x)= H(y).
What is collision‐resistance useful for? The hash serves as a fixed length digest, or unambiguous summary, of a message. This gives us a very efficient way to remember things we’ve seen before and recognize them again. Whereas the entire file might have been gigabytes long, the hash is of fixed length. This greatly reduces the storage requirement.
Hiding: If a secret value r is chosen from a probability distribution that has high min-entropy, then given H(r||x), it is infeasible to find x.
Application: Digital Commitment, it is the analogue of taking a value, sealing it in an envelope, and putting that envelope out on the table where everyone can see it. When you do that, you’ve committed yourself to what’s inside the envelope, without actually revealing what inside the envelope. A person can commit to a message msg, by publishing the hash of a msg concatenated with a random key.
Hcom, Hkey = H(Key || msg), H(key)
At later point in time when the msg is revealed, it can be verified by
H(Key || msg) == HCom and H(key) == Hkey
This way we are able to achieve the two goal of the commitment scheme :
- Hiding: Given H(key || msg), infeasible to find msg.
- Binding: Infeasible to find msg != msg’ , such that H(key || msg) == H(key || msg’)
Puzzle friendliness: For every possible output value y, if k is chosen from a distribution with high min-entropy, then it is infeasible to find x such that H(k || x) = y.
Application : Proof-of-work as in Hashcash, more on this in the later posts.
One of the prevalent cryptographic hash function is SHA256. It is used in Bitcoins as well.
Note: I the above post words like infeasible, hard are used in the sense of computational complexity of the system, i.e. it will take infeasible amount of time.
Next post will be about Bitcoin storage and transactions.