Boneh–Lynn–Shacham (BLS) signatures
How To Create a General Election With a Single Signature for All Votes: Meet Boneh–Lynn–Shacham (BLS) signatures
Building a More Trusted World
Introduction
What a completely untrusted Internet we have created, and where little in our digital world can be fully trusted. To overcome this we need to provide digital signatures in order to prove the integrity the data and of the entity that is signing. This often involves creating a hash of a message and then signing with our private key. The public key is then used to prove the signer.
Some applications, though, involve many signers signing for a transaction. This could relate to an on-line petition, and where Bob, Alice and Carol sign the petition with their private key, and then add their signature to the petition:
“We the undersigned believe that that there are too many cooks in the kitchen”
0x546043654323 [Bob]
0x646583654313 [Alice]
0x344583854099 [Carol]
We can see we have three signatures, and which could be checked against the public key of each of the signers. But if we increase the number of signers, the amount of space used to store all the signatures will also increase, and we must check them all in order to prove the signatures. The Schnorr and Boneh–Lynn–Shacham (BLS) signature methods can then be used in order to merge signatures into a single signature. In addition to this, the BLS signature method can aggregate all of the public keys into one, and create a single signing key to check against. In the following we have merged the signature, and also the public key of the signers:
“We the undersigned believe that that there are too many cooks in the kitchen”
Signed: 0x54703246543 [Bob, Alice, Carol]
Public key: 0764396512022 [Bob, Alice, Carol]
In this way we could create a general election for the UK, and where 26 million people could vote. Each citizen would then be allocated their own private key (and associated public key), and cast their vote and add their signature. At the end, we could create a single signature to prove all the votes, and also a single public key to check against. This public key will be a merger of all the public keys of the voters.
Magic!
The demo of the method used in this article is here.
ECDSA to Schnorr
While we use ECDSA to sign Bitcoin transactions, it has been shown to be inefficient as we need to add a signature from multiple signers. We have thus migrated the ECDSA method of signing Bitcoin transactions as the method has been shown to be only has strong as the randomness of the random numbers used. It also requires all the public keys to be checked where there are multiple signers. This was causing Bitcoin to slow down, so the signature scheme was changed to the Schnorr scheme. With this we can merge the signing process, and aggregate the public keys together into a single signature.
But the Boneh–Lynn–Shacham (BLS) signature method is seen to be even strong for signing. It uses a bi-linear pairing with an elliptic curve group and provides some protection against index calculus attacks. BLS also products short signatures and has been shown to be secure. While Schnorr requires random numbers to generate multiple signers, BLS does not rely on these.
Background
The first main concept we need to understand is a pairing, and where we have two values (P and Q). A pairing (or bi-linear map) is then defined as:
e(P,Q)
We must then find the method for e that is efficient, and for it to be bilinear it must conform to the following algebra operations:
a+b=b+a
a×(b+c)=a×b+b×c
(a×c)+(b×c)=(a+b)×c
In our function we can operate in the same way:
e(P,Q+R)=e(P,Q)×e(P,R))
e(P+S,Q)=e(P,Q)×e(S,Q))
We can also swap ×for +, and it should still work. We can try a pair with: e(x,y)=2xy, and use the values of x=5 and y=6:
e(5,6)=2^{5×6}=2^{30}
e(5,4+2)=e(5,4)×e(5,2)=2^{5×4}×2^{5×2}=2^{30}
Within pairing in elliptic curve, we take two points on a curve (or on different curves) as P and Q. We then create a function (e) which returns a value:
e(P,Q)→n
With pairing, we create a function where we can take a scalar value (x), and come up with the same result if we multiply the value by P or by Q:
e(xP,Q)=e(P,xQ)
If we have two values (a and b) we can then create a function which makes these equivalent:
e(aP,bQ)=e(P,abQ)=e(abP,Q)=e(P,Q)^{ab}
Theory
If Alice wants to create a BLS signature, she first generates her private key (a) and then takes a point on the elliptic curve (G) and computes her public key (P):
P=aG
She takes a hash of the message, and then map the hash value to a point on an elliptic curve. If we use SHA-256 we can convert the message into a 256-bit x-point. If we do not manage to get a point on the curve, we add an incremental value to find the first time that we reach the point. The signature of a message (M) and then computed with:
S=a×H(M)
and where H(M) is the 256-bit hash of the message (M). Her private key is a and her public key (P) and which is equal to aG. The test for the signature is then:
e(G,S)=e(P,H(M))
This can be proven as:
e(G,S)=e(G,a×H(m))=e(a×G,H(m))=e(P,H(M))
and where G is the generator point on the elliptic curve.
For the signature, we generate a new point on the elliptic curve and is 512 bits long, and use the x-point of the result. This gives us a 256-bit value, and thus our signature is 32 bytes long. This is a much smaller signatures than Schnorr and ECDSA. The signature for “Hello” is: [here]
Message: Hello
name=BN254 curve order=16798108731015832284940804142231733909759579603404752749028378864165570215949
-----Signature Test----
secretKey 3e6a4c7dae8f3563fabb9b57d04b4b21d3f2b9f4544adc7bedc6cbb36f036b10
publicKey a96fee792a1b933badbbadb9613ecd7f9903da5edfd100209622dc3402739b13df01cbb184ce620dc474d08bd83b47ac1a394e1ab652839b6232555a9be25499
signature 424d9ebf795d85e8abbbbddc264b110550afcb627dc90608e357d0cd3c2d7f08
When we look at ECDSA we see that we create an R and an S value, and which produces a longer signature [here]:
Message: Hello
Private key: Key priv: 2aabe11b7f965e8b16f525127efa01833f12ccd84daf9748373b66838520cdb7 pub: EC Point x: 39516301f4c81c21fbbc97ada61dee8d764c155449967fa6b02655a4664d1562 y: d9aa170e4ec9da8239bd0c151bf3e23c285ebe5187cee544a3ab0f9650af1aa6
Public key: EC Point x: 39516301f4c81c21fbbc97ada61dee8d764c155449967fa6b02655a4664d1562 y: d9aa170e4ec9da8239bd0c151bf3e23c285ebe5187cee544a3ab0f9650af1aa6
Signature: Signature {
r: BN: 905eceb65a8de60f092ffb6002c829454e8e16f3d83fa7dcd52f8eb21e55332b,
s: BN: 8f22e3d95beb05517a1590b1c5af4b2eaabf8e231a799300fffa08208d8f4625,
recoveryParam: 0 }One of the great advantages of BLS is that we can aggregate signatures together. For this we could have 100 transactions and where we had a signature for each one (Si) and each are associated with a public key of Pi (and a message Mi). The overall signature is then:
S=S1+S2+S3…+S100
We can then just add a single signature for our 100 transactions, and the result will only have 33 bytes (rather than having to store all the signatures). In Bitcoin we can perform a single transaction with multiple addresses. This involves multiple keys, and, with BLS, we can aggregate the signatures together. With this we merge signatures into a single signature and merge the keys into a single key.
We can then verify with (and where we use a multiply operation):
e(G,S)=e(P1,H(M1))⋅e(P2,H(M2))⋅…⋅e(P100,H(M100))
If we have the same message — such as a cryptocurrency transaction — we can merge the public keys together (key aggregation) and check the signature (N-by-N signature):
Presentation
The following is a presentation [slides]:
Conclusions
BLS signatures have many advantages, including being able to merge the multiple signatures (multisig) and merge public keys into a single public key. This has great advantages in applications where there are many signers to a transaction. For something of the size of a general election, we can create a single signature for every vote, and we can produce a single public key which can verify this signature.
We need to move towards a more trusted world, and dump wet signatures, and create a world where citizens sign for things with their private key.