Why digital signatures are essential for blockchains

Written signatures have been used to verify documents since at least the 17th century. They are used on countless types of agreements, from job contracts and credit card receipts to international treaties. But the digital age has ushered in new ways to communicate, no longer bound by paper and physical mailboxes. So how can we verify digital messages? The solution is digital signatures.

Here we will demystify the concept of digital signature systems to help you understand why they are chosen, and to develop a better understanding of their place in blockchain technology.

Just as written signatures tie a person to a particular document, digital signatures cryptographically link an identity to a message. 

Digital signatures are almost impossible to forge because they are based on number theory. In what is called “public key cryptography”, users own a public key and a private key, which form a pair. Public key cryptography uses encryption to guarantee security and protect sensitive key information. 

The public key represents the owner’s identity and the private key is secret, allowing them to prove they own the public key. Let’s say Alice wants to send an encrypted message to Bob. Anyone can see Bob’s public key, so Alice can use it in the algorithm that encrypts her message.

Observers can see or intercept the encrypted message but they can't decrypt it without Bob’s private key, which only he knows. So Alice can ensure nobody but Bob can see the message unless they have his private key.

For digital signatures, the operation is reversed. Instead of doing the initial computation with a public key, Alice uses her private key in the signing algorithm to link a signature to her message and public key. No one can derive Alice’s private key, or forge a valid signature for her, using only her signature and public key. However, anyone who knows Alice’s public key can easily verify that the message was signed by her private key.

Visualization of public key encryption Source

Digital signatures are a fundamental building block in blockchains, used mainly to authenticate transactions. When users submit transactions, they must prove to every node in the system that they are authorized to spend those funds, while preventing other users from spending them. Every node in the network will verify the submitted transaction and check all other nodes’ work to agree on a correct state.

If Alice wants to send Bob 1 bitcoin, she must sign a transaction spending 1 bitcoin of inputs with her private key and send it to nodes on the network. The miners, who know her public key, will then check the conditions of the transaction and validate the signature. Once validity is confirmed, the block containing that transaction is ready for finalization by a validator/miner.

Cryptography relies on some mathematical problems being difficult to solve. For example, the RSA algorithm, one of the first public-key cryptosystems, assumes that it is hard to factor two large prime numbers.

ECDSA

Bitcoin’s current signature scheme is known as the Elliptic Curve Digital Signature Algorithm (ECDSA). This uses shorter keys and requires fewer computational requirements than the RSA system, while maintaining strong security. ECDSA uses “elliptic curves” instead of finite fields. An elliptic curve is a finite group of points on a curve where some operations are easy to perform in one direction but difficult in the other direction.

ECSDA relies on the discrete log problem instead of the difficulty of factoring primes for security. The problem is as follows:

Let a, b, and c be integers such that a^b = c. If you are given c and a, it is difficult to find b if b is a large enough number. Now apply this equation to an elliptic curve group and compute Q = nP, where n is some integer, P is a point on the curve, and Q is the result of the operation (“multiplying” points). In elliptic curves, it is easy to calculate Q given n and P, but it is difficult to find n given P and Q. This is known as the “elliptic curve discrete logarithm problem”.

An elliptic curve Source

The ECDSA algorithm relies on this to generate signatures that are difficult to forge and easy to verify. Bitcoin uses a specific curve called “secp256k1”, which is standardized by U.S. government agency the National Institute of Standards and Technology (NIST).

Although its key sizes are relatively short and it has better computational efficiency than RSA, ECDSA is easy to implement poorly. Most notably, Bitcoin suffered from an implementation of ECDSA in which a transaction’s identifier could be modified by altering its signature. This was fixed by a process called SegWit (Segregated Witness). ECDSA may also be prone to weak randomness and a variety of other problems.

SCHNORR SIGNATURES (BITCOIN)

ECDSA has generally served Bitcoin well over the years. But it lacks one key property: there is no efficient way to compress and verify signatures together. So there has been a push recently to switch to a new scheme to improve the cryptocurrency’s scalability, efficiency, and privacy: the Schnorr signature. This is an elegant signature scheme, proposed in 1988 by Claus-Peter Schnorr, that was patented until 2008. Since Schnorr was not widely accepted or standardized until recent years, Bitcoin founder Satoshi Nakamoto chose ECDSA instead.

Schnorr signatures are provably secure with standard cryptographic assumptions (discrete log), non-malleable (a third party cannot alter a valid signature to create another valid one for the same key and message), and provide linearity (multiple parties can collaborate to produce a single signature valid for all public keys).

Linearity enables signers in a multi-signature transaction to combine their public keys into a single aggregated key (key aggregation). Multi-sig functionality is not native to Bitcoin and has traditionally been limited to Pay-to-Script-Hash (P2SH) scripts, wherein all parties must submit their public keys and signatures in a transaction. In these transactions, observers can see when a multi-sig transaction is occurring and identify its participants.

By contrast, Schnorr signatures allow the list and number of participants to be hidden by aggregating public keys into a single, aggregated signature indistinguishable from a normal one. This would reduce block load and increase privacy by enabling the “taproot smart contract construction”, a technique that makes complex scripts indistinguishable from normal transactions.

Simplified visualization of a traditional signature scheme compared to aggregation Source

Schnorr signatures also enable cross-input aggregation. Bitcoin transactions often have many inputs, each requiring individual signatures. These can occupy large amounts of space in a block. Schnorr signatures allow individual signatures in a transaction to be aggregated, so all inputs can be spent with a single signature. This leaves more room for transaction data in blocks and is estimated to increase capacity by 20-40%. In privacy protocols such as Coinjoin, cross-input aggregation aids privacy by making it harder to track inputs.

BLS SIGNATURES (ETH2)

The current Ethereum chain also uses ECDSA. However, when Ethereum moves to Proof of Stake with eth2, ECDSA will no longer support its validation requirements.

The eth2 chain will involve thousands of validators across committees, each required to produce thousands of signatures in a very short time. If this is to be scalable, every node cannot verify every signature. For example, assuming there are 64 committees for every block, with each committee having as many as 2,048 validators, 131,072 (64x2048) signatures must be computed and verified for every block (12 seconds). A signature scheme that enables efficient signature verification in consensus is clearly needed: eth2 plans to use BLS (Boneh-Lynn-Shacham) signatures.

Proposed at the start of the century, these signatures rely on “pairings-based” cryptography. This uses different hardness assumptions from those used by ECDSA, operating on different types of curves (pairing-friendly curves). Like Schnorr, BLS signatures enable key and signature aggregation but they are deterministic (with no randomness), allow signature aggregation across an entire block, and, most notably, are approximately 50% smaller.

Schnorr multi-signatures also require many rounds of communication and may depend on a growing data structure (Merkle Tree) for aggregation, while BLS signatures are easy to generate, with fewer communication requirements. The major downside of BLS signatures is that verification is extremely inefficient and far more expensive than Schnorr.

Many newer blockchains (most of which are Proof of Stake) also plan to use BLS signatures. Polkadot plans to use them for GRANDPA validation in a similar way to eth2. Even Grin, a privacy-preserving Proof of Work blockchain, is investigating BLS signatures as a way of reducing transaction load (kernel aggregation) and easier multi-signature functionality.

In a world where every miner or validator must verify every signature, blockchain technology could not function globally without the right signature schemes.

Any scheme will have cascading consequences for blockchain functionality. So selecting the right one is fundamental to developing the protocol. Trade-offs exist and no solution will remain gold standard.

Improvements to signature size, verification time, or security constantly come along. One scheme can become more viable than another if the benefits are compelling. For example, BLS signatures were barely used until the past few years, when papers were released dedicated to improving their efficiency, particularly for blockchain protocols. Protocol teams must remain flexible and open to change whenever compelling reasons arise.

The signature schemes discussed here have been around for decades and are likely to exist for the foreseeable future. Yet it is inevitable that they will eventually be replaced by schemes developed from research being conducted today. New cryptographic systems rarely achieve widespread implementation when initially proposed – an informal trial period is needed to test security and prove their assumptions.

Cryptography research has grown along with the blockchain space, and will continue to do so. Much relevant research today is dedicated to zero-knowledge proofs, and other fields of cryptography currently not relevant to blockchains may become important in the future.

Cryptography deals with some of the most sensitive information, and it is essential that these schemes are vetted as fully as possible. That’s why schemes could take decades to achieve prominence. But the industry will be no less excited when they do arrive.