Intuition To The Blockchain's Crypography - 1
Almost everyone here is aware of blockchain, bitcoin and other related terminologies and have a black box understanding of these things, but I was yet to see a detailed explanation of the inner workings of blockchain that goes into the cryptographic aspects with mathematical rigor. So, I decided to write my own. Having a mathematical intuition will help you understand why it's reliable and secure and you probably may appreciate the beauty of bitcoin even more!
I'll assume some basic knowledge of mathematics to follow. This article may get lengthy so I've decided to split it into multiple parts.
To understand how the Bitcoin blockchain works, one needs to understand Elliptic Curve Cryptography and the Secure Hash Algorithm (SHA).
One-Way Functions
The notion of a one-way function is central to public-key cryptography. These are functions that are relatively easy to compute, but significantly harder to reverse. That is, given x it is easy to compute f(x), but given f(x) it is hard to compute x. In this context, "hard" is defined something akin to "It would take millions of years to compute x from f(x) with the computing power that is available currently and into the foreseeable future ", (quantum computers may change things, however).
Breaking a plate is a good real-world example of a one-way function. It is easy to smash a plate into a thousand tiny pieces but it’s a practically impossible task to put all of those tiny pieces back together reconstruct the plate.
Indeed, the example given above is handwavey and if we are being strictly mathematical, we have no proof that one-way functions exist, nor any real evidence that they can be constructed.
Even so, many functions behave as one-way functions: We can compute them efficiently but, as of now, know of no easy way to reverse engineer them.
For example, in a finite field x^2 is easy to compute, but x^1/2 is much 'harder'. Since these problems are computationally infeasible to reverse engineer, we may assume them to be 'one-way' functions.
A message encrypted with the one-way function isn’t useful though; no one could decrypt it. Consider the broken plate example, you write a message on thousands of broken bits of the plate and give them to your friend for him to reassemble them and read off the message, then again, this is an impractical task. So for public-key cryptography, we need something else.
A "trapdoor one-way function" is a special type of one-way function, one with a secret trapdoor. It is easy to compute in one direction but very hard to compute in the other direction. However, if one knows the secret, they can easily compute the function in the other direction. In other words, it is easy to compute f(x) given x, and hard to compute x given f(x), but with some additional information, that is y (which remains secret), it becomes easy to compute f(x) from x.
Disassembling a watch is a good real world example of a trap-door one-way function. It is simple to disassemble a watch several of small pieces, and it is very difficult to put those tiny pieces back together into a working watch. However, by making use of some secret information, that is, the assembly instructions of the watch—it is a straightforward task to put the watch back together.
Communications Using Public-Key Cryptography
In 1976, Whitfield Diffie and Martin Hellman introduced the concept of public-key cryptography. They used two different keys—one public and the other private. It is computationally hard to deduce the private key from the public key. Anyone with the public key can encrypt a message but not decrypt it. Only the person with the private key can decrypt the message.
The mailbox is a good analogy to describe this. anyone can put mail in the mailbox, simply open the slot and drop it in, this is akin to the encryption process using the public key. Similary, getting the mail out of a mailbox is akin to the decryption process using a private key.
Getting the mail out of the mailbox without possessing the unique key is another story. However, if you have the secret (the physical key to the mailbox), it’s easy to get mail out of a mailbox. Mathematically, the process is based on the trap-door one-way functions discussed.
Encryption is the easy algorithm. Instructions for encryption are the public key; anyone can encrypt a message. Decryption is the harder part. It’s made "hard enough" that people with supercomputers couldn’t decrypt the message in thousands of years without possessing the secret. The secret, or trapdoor, is the private key. With that secret, decryption is as easy as encryption.
Digital Signatures
Handwritten signatures as proof of authorship of, or agreement with, the contents of a document, since forever. What are the necessary properties of a signature ?
1. Authenticity. The signature convinces the document’s recipient that the signer deliberately signed the document.
2. Non-Forgeable. The signature is proof that the signer, and no one else, deliberately signed the document.
3. Non-Reusable. The signature is part of the document; an unscrupulous person cannot move the signature to a different document.
4. Unalterable. After the document is signed, it cannot be altered.
5. Non-Repudiation. The signature and the document are physical things. The signer cannot later claim that he or she didn’t sign it.
But in reality, none of these statements about signatures are completely true. They can be forged, lifted from one piece of paper and moved to another, and documents can be altered after signing. Nothing is free from imperfections, but we are willing to live with these problems because of the difficulty in cheating and the risk of detection.
We do the same sort of thing on computers, but problems arise.
Firstly, digital files are trivial to copy. Even if a person’s signature were difficult to forge (consider a .JPG of a written signature, for example), it would be easy to cut and paste a valid signature from one document to another. Then the mere presence of such a signature would mean nothing.
Secondly, computer files are easy to modify after they are signed, without leaving any evidence of modification.
Signing Documents with Public-Key Cryptography
There are public-key algorithms that can be used for digital signatures. In some algorithms— RSA is an example, either the public key or the private key can be used for encryption. Encrypt a document using your private key, and you have a secure digital signature. In other cases— DSA is an example, there is a separate algorithm for digital signatures that cannot be used for encryption.
The basic protocol is simple and is as follows :
- A encrypts the document with his private key, thereby signing the document.
- A sends the signed document to B.
- B decrypts the document with A’s public key, thereby verifying the signature
Elliptic Curve Digital Signature Algorithm (ECDSA)
ECDSA is used to create a "Digital Signature" for some data (eg: a file). A digital signature enables one to verify a file's authenticity without compromising its security. Kind of like a real signature, everyone can recognize it, but one can't forge it without others knowing about it. Bitcoin uses the ECDSA to create digital signatures. ECDSA, much like the wider known RSA algorithm, creates a pair of different but connected keys. The first of the two is called "private key", only known to the person who created it and used to sign messages by performing a series of computations. The second, "public key", is known to everybody in the network. It is the only existing key that can reverse the series of computations done with the corresponding private key in the course of signing a message. Given the public key, it is computationally infeasible to calculate the corresponding private key. It is an NP hard problem. To sign a message one uses the private key to create a signature from the message. The recipient of a message and the corresponding signature can check whether the sending persons public key decodes the signature back into the message and thereby verify, that the author of the message is in fact the “owner“ of both the private and public key.
I hope to delve into the mathematical details in future posts.