Scalability Magic: BLS Signatures
Blockchain Scalability
Blockchain scalability has likely been one of the most researched topics in crypto environments in the past few years. Regardless of their involvement in the crypto world, almost everyone at this stage is aware of the ridiculously low amount of transactions processed per second of Bitcoin with respect to VISA for example.
To translate this statement into numbers, Bitcoin Wiki reports that at the time of writing, VISA’s average transactions per second is about 2,000, with some peaks at around 4,000 daily, while the maximum capacity is estimated to be around 60,000 transactions per second. In other words, not even on crazy Christmas shopping days is VISA in danger of being unable to sustain incoming transaction requests.
On the other hand, Bitcoin today reportedly handles a sustained average of 7 transactions per second, mostly due to the fact that the block size is restricted to 1MB and that it takes on average about 10 minutes to mine a block. Most popular blockchains and cryptocurrencies today are undeniably slow, and as a result, infeasible to truly compete with payment processors like VISA.
The low TPS is directly caused by the fact that, while VISA relies on a centralized system, thousands of nodes are necessary to be engaged to fully validate a single transaction on a decentralized network like Bitcoin. Thus, it could be argued that one way to speed up the such a system in which block size is fixed may involve decreasing the amount of nodes required in the processing of an individual transaction.
Scalability and Decentralization
The reality, however, is quite different. In fact, the more active honest nodes participating the more security in a decentralized environment. To explain, consider this example:
John is completely blindfolded, and he is given a marble. The person who gave the marble to him asks him to find out whether the marble is black or white, without taking the blindfold off. If John picks the color correctly, he will win $1,000. If he is wrong, he will lose $1,000. As the stake is relatively high, John is concerned with finding a reliable solution to the riddle. Since however he cannot check the color himself, he must rely on external parties.
The options that may be considered are mainly two:
John could ask his friend, Alan. John and Alan have been friends since first grade and John trusts him a lot. Sounds like nothing could possibly go wrong. Nothing unless Alan is angry at John because John did not show up to his party, and purposely tells him the wrong color. As a second option, John could instead walk downtown and start asking random people the color of his marble, until he’s asked a large enough sample who all agree on a particular color.
This example explains the underlying difference between VISA and Bitcoin, i.e. between centralized and decentralized systems. The benefits and downsides of both options are quite evident — while John can quickly discover the color of his marble by asking Alan, he must fully rely on his friend’s loyalty. On the other hand, if he asks a large number of people at random, he will end up with a more reliable secure result, however at the expense of time and repetition.
By the same token (pun intended), decentralized platform designs must rely on a greater number of validating nodes in order to grant the users safety of their transactions.
The above clearly explains that scalability in the majority of permissionless distributed ledger platforms may not be achieved via a cut in the number of validators per each transaction being processed. In the past, Vitalik Buterin, one of the co-founders of Ethereum, coined the term “Blockchain Trilemma” to address the apparent impossibility to achieve security, scalability, and decentralization all at once. During the recent years, the trilemma issue has however been tackled by a number of distributed ledger entities in different ways.
Digital Signature Schemes
One of the most well-known methods for attempting to break this “trilemma” and achieve scalability, while, of course, maintaining decentralization and security, is by leveraging clever cryptography and specifically aggregate signatures. This is achieved specifically via the so-called BLS signature aggregation, which is a recent implementation of a digital signature scheme ideated by Boneh, Lynn and Shacham in a paper from 2001.
The idea behind this concept is that it is possible to shrink the size of a block by reducing the size of the signature, compressing multiple individual signatures into a single, shorter one — thereby enabling more transactions to be included in the block. Although it may seem complicated, it is simpler than it looks. Let me explain…
The most common digital signature schemes for blockchains is ECDSA, which is implemented on Bitcoin, and Schnorr Signatures, which were however protected by a patent till only more recently.
ECDSA signatures work generally well. They are fast, secure, and relatively easy to use. However, they have one big problem: they cannot be aggregated. This means that when the number of validating nodes for a single transaction increases from 1 to 100, the information that is stored will be increased by 100 times. It is quite clear to see then that ECDSA signatures are not very efficient, and as a result may be antithetical to blockchain scalability.
Schnorr signatures, on the other hand, allow for aggregation of multiple signatures into a single one. However, when the number of validators rise, and especially in fault-tolerant conditions when m-out-of-n threshold of signatures are required for validation, the size of the Merkle tree on which Schnorr relies to build signature aggregation skyrockets in size, thus becoming inefficient.
BLS Signatures
BLS signatures solve both of the aforementioned problems. They are often referred to as “magical”, though no spells nor potions are involved. Well-designed maths and graphs will explain this mysterious “magic”!
The ingredients to a BLS signature, in mathematical terms, are the following:
- Bilinear pairing function: e: G0*G1 → Gt
- Hash function: H0: M → G0
The signature scheme is in turn defined by three functions:
- KeyGen() → Choose a random α and set h ß g1(α) output pk:=(h) and sk:=(α)
- Sign(sk,m) → Output σ ß H(0)m α belonging to G0. The signature is a single group element
- Verify(pk,m,σ) → if e(g1, σ)=e(pk,H0(m)) output «accept», otherwise output «reject»
Two main components shall be defined in order to understand their underlying design:
- Hashing to the curve
- (Elliptic) curves pairings, also referred to as bilinear maps
Unlike the majority of digital signature schemes, which use the hash algorithm like a number, BLS signatures use the hashed message directly as a generator. In other words, BLS signatures use a special algorithm that hashes directly to the curve.
This implies that “special” curves may only be used to allow for direct hashing to the graph. The family to which these special curves belong is called, “pairing friendly elliptic curves.”
An extremely useful property that such curves display is called bilinear property, and works as follows:
e(x*P,Q) = e(P,x*Q)
In other words, we can swap the multipliers without changing the result! This will again come in handy when dealing with the verification of BLS signatures.
On the elliptic curve, the signature would look like the following:
As you can see, the public key is simply the product of the generator function G with the private key. Then, to obtain the signature, it is enough to multiply the message by the private key.
To verify the correctness of the signature, referred to as elliptic curve pairing check, the message and the public key are needed only. The verification process works as follows:
e(P,H(m)) = e(G,S)
Which holds true by the bilinear property described in the above paragraphs. The proof of the verification equation looks like the following:
e(P,H(m)) = e(pk*G,H(m)) = e(G,pk*H(m)) = e(G,S)
Why are BLS signatures so good?
BLS signatures display two fundamental properties:
- Efficient computability
- Non-degeneracy
In other words, BLS signatures are extremely easy to use (or generate) and extremely difficult to get tampered with. This allows for high efficiency in generation and enhanced security with respect to other digital signature schemes.
Additionally, while the aggregation of Schnorr signatures requires n rounds of communication, BLS signatures allow for the same goal to be achieved via only two rounds of communication.
Furthermore, as BLS signatures pair directly to the curve, they do not rely on random numbers of any sort, which may be tampered with and undermine the overall security of the process. Conversely to other digital signature schemes such as ECDSA or Schnorr, which rely on random numbers for pairing to the curve, the process of signature generation in BLS signatures is completely deterministic
Most importantly, however, is that BLS signatures can be very easily aggregated, i.e. both the individual signatures and the individual public keys of the single validators in a transaction may be easily combined into one, shorter piece of information, just by adding them up.
Given triples (pki, mi, σi) for i=1,…,n, anyone can aggregate the signatures σ1,… σn belonging to G0 into a short aggregate signature σ by computing:
σ ← σ1…σn ∈ G0
Verifying an aggregate signature reduces to:
e(g1, σ) = e((pk)1, H0(m1 ))… = e((pk)n, H0(mn))
When all messages are the same, verification is simplified.
But not perfect
Although they are undoubtedly very elegant tools, BLS signatures are not free from imperfections. As a matter of fact, while signature aggregation in BLS sounds so simple, it is actually not at all: the process of signature aggregation in BLS is orders of magnitude harder than, for example, Schnorr signatures. Then, because of the peculiarity of the elliptic curve, verification of a BLS signature is a relatively slow process by comparison.
The graph above displays the verification times for ECDSA and BLS signatures (when no optimization is added).
There are always tradeoffs, however, and with Schnorr the tradeoff is that signature aggregation gets extremely complex and confusing for a high number of nodes in the network, and especially in the case of the aggregation of m-out-of-n signatures, which case is usually to be preferred for fault tolerance reasons.
Despite this, BLS signatures are at the time of writing an extremely popular method for digital signatures in the crypto community. This is due to the fact that blockchain communities are increasingly working on optimizations that may be implemented to make BLS aggregate signatures a much leaner tool. However, such methods will not be discussed at this time in this article.
Finally, BLS signatures are subject to rogue public-key attacks (for a more detailed explanation, see the rogue public-key attack section of this paper, or here). Defenses to this problem are however quite simple, and include the following methods:
- Requiring every user on the network to prove knowledge of the corresponding secret key, to a given public key
- Signing of different messages per each user
- Addition of non-linearity to the scheme
- A modified implementation of BLS signatures, such as the one proposed by Boneh et al. in a paper from 2018.
Conclusion
Despite its ten years of age, Bitcoin is still far from achieving a comparable throughput as VISA. This obstacle to scalability is mostly caused by the same system designs that give Bitcoin decentralization and security. This seems to suggest that a large number of validators per single transaction being processed is necessary to maintain security in a decentralized environment. However, signature aggregation schemes like BLS and Schnorr may hold the secret to turning this on its head.
BLS signatures may play a crucial role in solving the blockchain Trilemma. They outrun previous digital signature schemes on five main fronts. First, it is well known that ECDSA suffer from an underlying problem: when the number of validating nodes grow, the amount of signature information grows linearly with it. By allowing for simple aggregation, BLS signatures can compress thousands of individual public keys and signatures into one, shorter piece of information. Second, although Schnorr signatures are fairly efficient concerning signature aggregation and verification when the number of validating nodes is low, things dramatically change as the size of the network increases. In fact, as signature aggregation in Schnorr is built on Merkle trees, the size of the tree tends to grow very fast, especially in the case of aggregation of m-out-of-n signatures, which are generally to be preferred for reasons of fault tolerance. Third, the intrinsic characteristics of elliptic curves, i.e. efficient computability and non-degeneracy, make BLS strong with respect to security parameters.
This statement is further strengthened by the fact that BLS signature generation does not rely on random numbers, which may run into the risk of being tampered with, while it is completely deterministic.
Finally, BLS signature aggregation only requires two rounds of communication, differently from Schnorr which requires n.
However, the current design of BLS signature schemes is yet to be perfected, and verification of such cryptographic tools still requires a fairly long amount of time and computational power when compared to other signature schemes.
However, BLS signatures allow for extremely simple aggregation of both public keys and signatures of all the validating nodes.
To make the process leaner and more efficient, academics, researchers, and developers around the world are working on optimizations that could make BLS signatures the clear winners for cryptographic environments.
For further technical details on BLS digital signatures and defenses against rogue public-key attacks, you can refer to the slides here.
