Digital signatures in blockchain technology

Digital signatures are used to verify data comes from a specific source and typically use public key cryptography: the private key is used to sign data and the public key can be used to verify the signature. As long as the private key is kept secure, nobody can forge the signature so that data source can be considered reliable. A digital signature can be also used to verify the integrity of the data against tampering and to ensure non-repudiation of the data.

Bitcoin uses a signature scheme called the Elliptical Curve Digital Signature Algorithm or ECDSA, with the elliptical curve parameters of secp256k1. ECDSA and similar alternatives such as EdDSA are frequently used in blockchains due to the fact they are well battle tested and have undergone extensive cryptanalysis over the years, so it’s easy to use and implement them. ECDSA is reliable against non-quantum attacks, while quantum computers are likely decades off, so that being impervious to quantum attacks is not a priority. Signature schemes such as ECDSA use a single public/private key pair per transaction which is not as efficient as it could be.

Signature aggregation in Mintlayer

In order to reduce the blocksize and speed up transactions, Mintlayer settled on the use of signature aggregation, which means being able to aggregate several signatures together into a single one. This way, only a signature needs to be verified and validation is quicker and more efficient. It also has the benefit of making chain analysis more difficult, especially when multiple transactions are aggregated together. Batching, coinjoin and mixing procedures widely increase the privacy while reducing the size of each payment.

Why Mintlayer adopts BLS

There are several ways of handling signature aggregation and they include BLS, Schnorr signatures and bulletproofs which were the 3 methods Mintlayer narrowed down the analysis. In order to decide between them a few research experiments have been performed, looking at either theoretical framework and real-life use cases as benchmarks.

Bulletproofs are a form of non-interactive zero knowledge proof currently implemented in Monero. Rather than signature creation and verification bulletproofs require the creation of a proof and then the verification of that proof. Unfortunately it was the time required to create that proof that ruled bulletproofs out through our experiments being notably slower than the other two techniques; bulletproofs would also be the most difficult of the 3 schemes to implement and maintain so the decision was a sensible one.

Schnorr: it is the proposed method of signature aggregation by the Bitcoin core team and they are implemented as part of Taproot. As a result, Schnorr signatures would have been an obvious choice for such a Bitcoin focused project. Despite this, Schnorr signatures have a major weakness in the fact they require an extra round of communication between the individual signers and aggregator, due to the interactivity between the signers which takes 3 rounds. Despite several methods have been proposed to drop this to 2 rounds, Drijvers et al. have suggested that all extant attempts to solve this problem are flawed. MuSig2 may change this in the future, but for now the 3 rounds required add a significant time overhead with a large latency, which BLS does not require.

BLS: on paper, aggregated Schnorr signatures are quicker than aggregated BLS signatures but in real-life we found the differences to be negligible, with the verification for BLS even being quicker for large numbers of signatures. There are also highly optimised versions of BLS that perform far better than any Schnorr implementation we could find. The extensibility to BLS as well as the ability to hide transactions through m-out-of-n multisig aggregation, within aggregated BLS signatures made them the more attractive choice.

Although it is likely that Mintlayer will also add support for Schnorr signatures in the future, the extensibility and flexibility of BLS along with the far smaller aggregated signature size of BLS made the decision an easy one for us.

Both of the above graphs of benchmarks come from Logos Network analysis

From our own tests on publicly available implementations you can see that Schnorr beats naive BLS but cannot come close to an optimised version. A plain Ed25519 benchmark is included to give a point of comparison for the BLS implementation. These benchmarks, except the optimized implementation were taken in a substrate environment to as closely as possible match the future Mintlayer node. Given the performance of the optimised BLS implementation, we have chosen to implement BLS ourselves and aim to slowly optimise it to improve on performance as we move forwards with the project. The numbers for bulletproofs and ECDSA are off the scale of this chart.

A technical introduction to BLS

Boneh-Lynn-Shacham or BLS, is a cryptographic digital signature scheme with native support for signature aggregation. So how exactly does BLS work? BLS signatures are based on a bilinear pairing system for verification and signatures of group elements on elliptical curves. BLS relies on intractable Diffie-Hellman problems within a gap Diffie-Hellman group. The problem asks if it is easy to find g^ab given g, g^a and g^b. A decisional diffie-hellman problem with a defined bilinear pair is said to be easy because given g^a, g^b, g^c for c=ab we can check if g^c is different from a random element in G. That is e(g^a, g^b) = e(g,g)^ab = e(g,g)^c = e(g,g^c). For those of you who don’t know what a pair is in the world of cryptography, rather than defining it myself I will use Wikipedia’s definition as it’s far clearer than anything I could come up with.

Let G₁, G₂ be two additive cyclic groups of prime order q and G_T another cyclic group of order q written multiplicatively. A pairing is a map e : G₁ x G₂ → G_T which satisfies the following:

Bilinearity: ∀a,b ∈ F_q*, ∀P ∈ G₁, Q∈ G₂ : e(aP, bQ) = e(P,Q)^ab

Non-degeneracy: e ≠ 1

Computability: there exists an efficient algorithm to compute e

So how does that help verify the signature?

Assuming the existence of a random oracle and the intractability in a gap group, as mentioned above, the signature of a message, m (m ∈ {0,1}^*) is given by σ = H(m)^x where x (x ∈ ℤ_p) is a private key and the public is g^x. The signature can be rearranged to (g, h = g^x, H(m), σ).

Given the above definition of e the signature verification step becomes e(H(m),g^x) = e(H(m)^x, g) for the defined g, g^x.

To expand this definition to include aggregated signatures we must first look at how signatures are aggregated within BLS. In BLS the aggregated signature is merely the sum of the signatures.

σ_total = σ₁ + σ₂ + .... + σ_n

e(G, σ_total) = e(g^x1, H(m₁)) * e(g^x2, H(m₂)) ^* .... * e(g^xn,H(m_n))

For a more detailed look at BLS it’s worth looking at the RFC published by Boneh et al. or this simple python implementation.

‍