Aggregation of BLS Signature with CIRCLBoneh–Lynn–Shacham (BLS) [1,2] signature method produces short signatures. They use elliptic curve pairing (and which are also known as bilinear maps), and can be used to aggregate signatures. In this case, we will generate two random key pairs, and which are used to sign two messages. For example, Bob has a message and Alice has another message. We can then generate two signatures, and then aggregate them together. We can then check against the public keys of Bob and Alice. |
Background
The first main concept we need to understand is a pairing, and where we have two values (\(P\) and \(Q\)). A pairing (or bilinear 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 \times (b+c) = a \times b + a \times c\)
\((a \times c) + (b \times c) = (a + b) \times c\)
In our function we can operate in the same way:
\(e(P,Q+R) = e(P,Q) \times e(P,R)\))
\(e(P+S,Q) = e(P,Q) \times e(S,Q)\))
We can also swap \(\times\) for \(+\), and it should still work. We can try a pair with: \(e(x,y)=2^{xy}\), and use the values of \(x=5\) and \(y=6\):
\(e(5,6) = 2^{5 \times 6}=2^{30}\)
\(e(5,4+2) = e(5,4) \times e(5,2) = 2^{5 \times 4} \times 2^{5 \times 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) \rightarrow 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
We have 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.
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 = a G\)
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 \times 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 \times H(m)) = e(a \times 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:
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:
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 (\(S_i\)) and each are associated with a public key of \(P_i\) (and a message \(M_i\)).
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. The signature is then:
\(S=S_1+S_2+ ... +S_{100}\)
We can then verify with (and where we use a multiply operation):
\(e(G, S) = e(P_1, H(M_1))⋅e(P_2, H(M_2))⋅…⋅e(P_{100}, H(M_{100}))\)
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]:
Sample code
The following is sample code::
package main import ( "crypto/rand" "fmt" "os" "github.com/cloudflare/circl/sign/bls" ) func main() { m1:="Hello" m2:="Goodbye" argCount := len(os.Args[1:]) if argCount > 0 { m1 = string(os.Args[1]) } if argCount > 1 { m2 = string(os.Args[2]) } keyInfo := []byte("Additional information") salt := [32]byte{} ikm := [32]byte{} _, _ = rand.Reader.Read(ikm[:]) _, _ = rand.Reader.Read(salt[:]) msgs := make([][]byte, 2) sigs := make([]bls.Signature, 2) pubKeys := make([]*bls.PublicKey[bls.G1], 2) msgs[0]=[]byte(m1) priv1, _ := bls.KeyGen[bls.G1](ikm[:], salt[:], keyInfo) pubKeys[0] = priv1.PublicKey() sigs[0] = bls.Sign(priv1, msgs[0]) _, _ = rand.Reader.Read(ikm[:]) _, _ = rand.Reader.Read(salt[:]) msgs[1]=[]byte(m2) priv2, _:= bls.KeyGen[bls.G1](ikm[:], salt[:], keyInfo) pubKeys[1] = priv2.PublicKey() sigs[1] = bls.Sign(priv2, msgs[1]) aggSig, _ := bls.Aggregate(*new(bls.G1), sigs) ok := bls.VerifyAggregate(pubKeys, msgs, aggSig) pr1,_:=priv1.MarshalBinary() pb1,_:=pubKeys[0].MarshalBinary() pr2,_:=priv2.MarshalBinary() pb2,_:=pubKeys[1].MarshalBinary() fmt.Printf("Message 1:\t%s\n",m1) fmt.Printf("Message 2:\t%s\n",m2) fmt.Printf("\nPrivate key 1:\t%x\n",pr1) fmt.Printf("Public key 1:\t%x\n",pb1) fmt.Printf("Private key 2:\t%x\n",pr2) fmt.Printf("Public key 2:\t%x\n",pb2) fmt.Printf("\nSignature 1:\t%x\n",sigs[0]) fmt.Printf("\nSignature 2:\t%x\n",sigs[1]) fmt.Printf("\nAggregated Signature:\t%x\n",aggSig) fmt.Printf("Verified: %v\n",ok) }
A sample run is:
Message 1: Help Me! Message 2: I am okay! Private key 1: 0b3caf29e9d9a5e78053e63dc18aef66b1439c07165f8db8ee83d5a5b8aae9f4 Public key 1: b90b93d5dde9739db7b799feb4ebf9381a550c6d53864606b326e14aa44574dfc2797bb6dc1d686e2efbaad62cbe7cf6 Private key 2: 1329bd26cde1150cb83b00d8889aab26e85c5aaa239c70742dbc50f61685e3e7 Public key 2: b955b1ad8d127a615afc7c4c8d53e9cbb15e3e5df25be9d54edbbeb23e72b928081bd795d1d82dd4b4c24984f577dacd Signature 1: 98b252224ec1e91bff45b7fe605dc703bfe2eea14376c13eba09e28ab3483e3a4d467309166aad3f0772c282005802b101deeb1dcb6dbb6bb65b3549bbfb3a57a120dad6c9cfdca31c5bf03b8b4c760527419543b365373620b701028e2f69b9 Signature 2: a8f24a34461816350474f9e4ae3bd27f3dc2bb69cfe8a25428ccd4892fac47ead485b4b5790a9ddd8f00bd214184d81d08700ee411d2897554b34a55af9ec2fe7b96cb72b7a0ca79d5b277726d6f3f733dd9897b5710100b352692dd4af8bec1 Aggregated Signature: 8353036d89fa16e19f2b5ed19f83f064af588622b89864fe67594e7755f671d7f2bbf67807719918de42b66c99829cc5080bc28d82289b0a54f27c86abeafe0f1a268559293910d118f58cb36dccdfeff0599ce4d75795e0c2041fa2f63b1964 Verified: true
References
[1] Barreto, P. S., Lynn, B., & Scott, M. (2003). Constructing elliptic curves with prescribed embedding degrees. In Security in Communication Networks: Third International Conference, SCN 2002 Amalfi, Italy, September 11–13, 2002 Revised Papers 3 (pp. 257-267). Springer Berlin Heidelberg.
[2] BLS Signatures: https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-bls-signature-05