Digital signatures are requirements for any working blockchain; their attributes are of paramount importance and can profoundly impact the characteristics of a blockchain.
Since the reasoning behind the selection of a signature scheme is often invisible to users, our goal is to demystify the concept and help you develop a better intuition for thinking about digital signatures in the context of blockchain technology.
Written signatures have been standard practice for providing unique consent on information since at least the 17th century. They are used to formalize countless types of agreements such as job contracts, credit card receipts, and even war treaties. The digital age ushered in a new way to communicate that is no longer bound by paper and mailboxes. How, then, can we verify the authenticity of digital messages? The solution involves what are known as digital signatures.
Just as written signatures tie a person to a particular document, digital signatures cryptographically link an identity to a particular message. Digital signatures are nearly impossible to forge due to their use of number theory to guarantee functionality and use a system called public key cryptography in which users own both a public key and a private key, forming a pair. The public key can be thought of as the identity of the owner and the private key can be thought of as secret information that allows the owner to prove their ownership of the public key.
In order to understand how public key cryptography is used in digital signatures, you must first know how it works with encryption to guarantee message security while protecting sensitive key information. For example, if Alice wants to send an encrypted message to Bob, and Bob’s public key is available for anyone to see, Alice can use his public key in the algorithm that encrypts her message.
Observers may be able to see or intercept the encrypted message, however, they will not be able to decrypt the message unless they have Bob’s private key, which is only known by Bob. Thus, Alice can ensure that Bob is the only user who can see the original message without personally requiring his private key.
For digital signatures, the operations of the keys are reversed. Instead of performing the initial computation with a public key, Alice can use her private key in the signing algorithm to create a signature linked to her message and public key. No party can derive Alice’s private key, or forge a valid signature for Alice, with just her signature and public key. However, anyone that knows Alice’s public key can easily verify that the message is signed by Alice’s private key.
Digital signatures are a fundamental building block in blockchains; they are primarily used to verify the authenticity of 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 also spending those funds. Every node in the network will verify the conditions of the submitted transaction and check all other nodes’ work to agree on a correct state.
If Alice wants to send 1 BTC to Bob, she must sign a transaction spending 1 BTC of inputs using her private key and send it to nodes on the network. The miners, who have knowledge of her public key, will then check the conditions of the transaction and validate the authenticity of the signature. Once validity is confirmed, the block containing that transaction will be then ready for finalization by a validator/miner.
Cryptography relies on the assumption that some mathematical problems are difficult to solve. For example the RSA algorithm, one of the first public-key cryptosystems, assumes that factoring two large prime numbers is difficult.
The signature scheme currently used in Bitcoin is the Elliptic Curve Digital Signature Algorithm (ECDSA). Compared to RSA, ECDSA uses shorter keys and requires fewer computational requirements while still maintaining strong security. ECDSA also uses what is known as elliptic curves over finite fields. Think of an elliptic curve group as a finite group of points on a curve where some operation is easy to perform in one direction but difficult to perform in the other direction.
In addition, ECSDA relies on the discrete log problem instead of the hardness of prime factorization 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.
The ECDSA algorithm relies on this property to generate signatures that are difficult to forge and easy to verify. The specific curve that Bitcoin uses for ECDSA is called secp256k1 and is an elliptic curve standardized by a government agency called the National Institute of Standards and Technology (NIST). Although its key sizes are relatively short, and it improves on computational efficiency compared to RSA, ECDSA can be easily implemented poorly.
Most notably, Bitcoin suffered from an implementation of ECDSA in which identifiers for a transaction could be modified by altering the signature of the transaction, which was later fixed with Segwit. Implementations of ECDSA may also be prone to weak randomness or simply be prone to a variety of other exploits.
Despite its problems, ECDSA has generally served Bitcoin well over the years. However, ECDSA lacks a key desirable property: there is no efficient way to compress and verify signatures together. In recent years, there has been a push to switch to a new signature scheme to improve the scalability, efficiency, and privacy of Bitcoin: Schnorr signatures. Schnorr signatures are an elegant signature scheme, proposed in 1988 by Claus-Peter Schnorr, that were patented until 2008. Since Schnorr was not as widely accepted/standardized until recent years, Satoshi chose ECDSA for Bitcoin 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 that is valid for all public keys).
The linearity property has two benefits for Bitcoin. First, linearity enables multiple signers in a multi-signature transaction to combine their public keys into a single aggregated key (key aggregation). For context, multi-sig functionality is not native to Bitcoin and has traditionally been limited to P2SH scripts, where all parties must submit their public keys and signatures in a transaction. For such transactions, observers can see whether a multi-sig transaction is occurring and identify its corresponding participants.
In contrast, Schnorr signatures allow the list and number of participants to be hidden by aggregating public keys and producing a single aggregated signature which is indistinguishable from a normal signature. This property would further reduce block load and increase privacy by enabling the Taproot smart contract construction, a technique that makes complex scripts indistinguishable from normal transactions.
Schnorr signatures additionally enable cross input aggregation. Bitcoin transactions often have many inputs that each require individual signatures and can occupy large amounts of space in a block. Schnorr signatures allow individual signatures in a transaction to be aggregated and therefore allow all inputs in a transaction to be spent with a single signature. This ability to combine signatures 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 may also provide privacy benefits by making it more difficult to track inputs.
Like Bitcoin, the current Ethereum chain also uses ECDSA. However, when Ethereum transitions to Proof of Stake with eth2, ECDSA will be unable to support that chain’s intense validation requirements.
The eth2 chain will involve thousands of validators across committees and each will be required to produce thousands of signatures in very short time frames. Every node cannot possibly verify every signature if this system is to be scalable. For example, assuming that there are as many as 64 committees for every block and each committee can have as many as 2048 validators, 131,072 (64*2048) signatures can be computed and verified for every block (12 sec). A signature scheme that allows for efficient signature verification in consensus is clearly needed. To achieve this, eth2 plans to use BLS signatures.
BLS (Boneh-Lynn-Shacham) signatures were proposed just after the start of the 21st century and rely on a type of cryptography called pairings-based cryptography. It has different hardness assumptions compared to ECDSA and operates on different types of curves (pairing friendly curves). BLS signatures are similar to Schnorr signatures in that they enable key and signature aggregation but BLS signatures are deterministic (no randomness), can allow for signature aggregation across an entire block, and most notably, are much smaller than Schnorr signatures (~ 50% smaller).
In addition, while Schnorr multi-signatures require multiple rounds of communication and may depend on a large growing data structure (Merkle Tree) for signature aggregation, BLS signatures are extremely easy to generate and have fewer communication requirements. The major downside to BLS signatures is that signature verification is extremely inefficient and is orders of magnitude more expensive than Schnorr signatures.
Similar to eth2, many of the newer blockchains (the majority of which are Proof of Stake) are also planning to use BLS signatures. Polkadot plans to use BLS signatures for GRANDPA validation in a manner similar to eth2. Even Grin, a privacy-preserving Proof of Work blockchain, is investigating BLS signatures for reducing transaction load (kernel aggregation) and easier multi-signature functionality.
The characteristics of a digital signature scheme have cascading effects on the functionality of a blockchain. As such, selecting a scheme is a fundamental part of the protocol development process. Tradeoffs exist and no solution will remain the gold standard. In a world where every miner or validator has to verify every signature, blockchain technology would not be able to serve the world as a globally usable technology without the right signature schemes.
New optimizations to improve the usability of signatures are constant in order to improve signature sizes, verification time, or security. One signature scheme can be a more viable option than another if the benefits are compelling. For example, BLS signatures were barely used until the past few years when papers dedicated to improving their efficiency particularly for blockchain protocols were released. Protocol teams must remain flexible and open to changing digital signature schemes and design accordingly when compelling reasons arise.
The signature schemes discussed above have been around for decades and are likely to be around for the foreseeable future. Yet it is inevitable they will eventually be replaced by newer schemes developed from research being conducted today. Widespread implementation of a new cryptographic system rarely takes place when it is initially proposed; an informal trial period to test the security of a system and prove or disprove its assumptions are necessary.
Cryptography research has been propelled as a result of the corresponding growth of the blockchain space and will continue to do so for the foreseeable future. While much of the relevant research today is being dedicated to zero-knowledge proofs, other fields of cryptography currently not in the intersection of blockchains may also provide strong relevance in the future.
Cryptography deals with some of the most sensitive information possible and it is non-negotiable that these schemes are vetted to the fullest extent possible. This delay means new schemes could take decades to come into prominence. Despite the wait, the industry will not be any less excited when they get here.
Bison Trails is an Infrastructure-as-a-Service company, based in New York City, specifically focused on blockchain participation. We’ve built a platform for anyone who wants to participate in new chains effortlessly (e.g. by running Cosmos Validators, Tezos Bakers, and Libra Validators, etc.)—without having to invest time and resources into developing any of the engineering, protocol, dev ops, or security competencies in-house. Our goal is for the entire blockchain ecosystem to flourish by providing robust infrastructure for the pioneers of tomorrow.