Introduction
I first heard about Bitcoin in 2012. I was in the first year of college and I remember browsing obscure internet forums to figure out how to create my bitcoin wallet and the mathematics behind how it works. The technology has come a long way since then. Cryptocurrencies are now a real market with huge trading volumes, hundreds of different coins, and notoriously volatile prices. In addition, modern blockchains are also capable of executing arbitrary logic - called “smart contracts” that in my opinion have the same revolutionary potential today as the internet had in the early 1990s.
The first half of 2022 has not been kind to the world of crypto. Firms are announcing layoffs and several famous bankruptcies and wallet hacks have soured the public view of crypto. Despite these setbacks, I think the technology has enormous potential and is worth learning about. Even if cryptocurrencies fall out of favor, the technology behind blockchains will likely endure in some form for the foreseeable future.
The mathematics of cryptography is the foundation upon which modern blockchain systems are built. A public, decentralized blockchain that nobody controls raises some questions:
If I send a request to transfer some of my bitcoin to my friend, how can the network of computers know that I was the one who sent the request without having a human verify my ID?
How can a smart contract that logs your attendance verify confidently that you are who you claim to be?
How does Solana know that the person who sent a transaction sent it at a specific time?
How does a bitcoin miner prove that they did the work to verify a block of transactions?
The answer to all these questions lies in the math of cryptography. Cryptographic systems let us encrypt data, prove the origin of documents and provide several mechanisms for blockchains to reach consensus. In this article series, I’ll do a deep dive into many of the components of the cryptographic systems that make blockchains tick.
Part 3 - Digital Signatures
Digital Signatures
Consider a scenario where you want to sign a digital document in an unforgeable way. How do you do it in a way that proves you’ve signed it but without revealing a method to forge the signature? A first thought would be a password or secret phrase that only the signer knows. But signing the document with the secret phrase would reveal to everyone the secret phrase - letting others forge the signature.
Public Key Encryption for Signing
The answer to the digital signature problem lies in public key cryptography. An interesting property of the RSA algorithm is that the private and public keys can be used interchangeably for encryption, i.e. - I can use my private key to encrypt a message and my public key (and only my public key) can be used to decrypt it.
The consequence is that any message encrypted using my private key acts like a signature for the message. If the message can be decrypted by the public key, it proves that the person who knows the private key has seen and generated the encrypted message. This is impossible to forge without knowing the signer’s private keys.
Using Hashes
In practice, digital signatures are not implemented this way because the signature would be as long as the message. If the file that needs to be signed is very large, verifying the signature will take up a lot of bandwidth and computing power. This is where the power of cryptographic hash functions can be used.
Modern digital signature systems use the signer’s private keys to encrypt the hash of a file rather than the full file. Verification is done by decrypting the hash with the signer’s public keys and comparing the decrypted hash with the hash of the file calculated by the verifier. Due to the properties of cryptographic hash functions described in Part 1, the hashes of two random files are unlikely to be the same. So being able to decrypt the hash of the file proves that the file has been signed by only those who know the private keys. If the signer has kept their private keys secure, it proves that the signer has indeed seen and signed the file.
Elliptic Curve Digital Signature Schemes (ECDSA)
One disadvantage of RSA is that the sizes of keys for secure encryption and signing tend to be quite long. A key size of 1024 bits or longer is recommended to prevent someone from factoring out the private key from the public key. Large key sizes can be a problem for encrypting in resource-constrained systems like micro-controllers and for systems that do signing and verification at scale - like web servers. A decrease in the key size and computational resources needed to perform these cryptographic functions can drastically reduce cost and environmental impact.
This is where elliptic curve cryptography comes in. Elliptic curves are the set of 2D coordinates that satisfy the equation:
In Part 2 I described how the RSA encryption scheme depends on the fact that multiplying two large primes is easy compared to factoring the result into two primes. In general mathematical operations that are easy to perform one way but hard to reverse have potential use in cryptographic systems. Elliptic curves too have such a one-way operation.
Point “addition” takes two points on the curve P and Q and follows a specific procedure to produce another point on the curve.
Point “multiplication” of point P by a scalar value k is adding P to itself k times.
I put addition and multiplication in quotes. Mathematicians call these operations “addition” and “multiplication” but it’s really important to keep in mind that these operations are not the same addition and multiplication that everyone is used to. In fact, it may be better to call them something else like “point operation A” and “point multi-operation A”. For curves drawn with real numbers like in the image above, there is a geometric interpretation for point multiplication and addition.
However, for cryptography, the curves are instead defined over a finite set of integers modulo some number. The details of these addition and multiplication operations involve wading into group theory - which is beyond the scope of this article. See references [3] and [4] for more details.
The relevant fact is that point multiplication is believed to be a one-way operation. It is easy to apply point multiplication to the base point P to calculate P x k = R. But given the base point P and R, it is not feasible to find k. This is known as the elliptic curve discrete logarithm problem (ECDLP). Mathematicians believe that not only is finding k hard, but it is also much harder than the integer factorization problem. So hard that Elliptic Curves can offer the same level of security at 256-bit key sizes as RSA with over 3000-bit key sizes.
For elliptic curve cryptography, the value k becomes our private key and the value R becomes our public key. The base point P must be the same for everyone and is chosen essentially at random.
In blockchains, digital signatures are used to prove the origin of a transaction sent to the network and, along with the consensus mechanism are a foundational pillar that allows blockchains to work the way they do. In the bitcoin network, for example, a transaction that transfers bitcoin between wallets must include a digital signature of the origin wallet to prove that the sender actually wants to send bitcoin.
Summary
Hashes create a digital fingerprint of files that allows us to easily check if two files are the same. Encrypting the hash using the private key of a public key cryptographic system allows anyone to verify that the file was seen and signed by the holder of the private key.