BN256 Aggregated SignaturesIn this page, we will aggregate signatures with BN256, along with aggregating the public keys. With this, we will have two key pairs of (\(sk_1,pk_1\)) and (\(sk_2,pk_2\)) and which will produce signatures of \(\sigma_1\) and \(\sigma_2\), respectively. We can then aggregate the signatures with \(\sigma_a = \sigma_1 + \sigma_2\), and the equivalent public key will be \(pk_a = pk_1 + pk_2\). |
Method
With BN256, we create the private key from a random number. This is a scalar value (\(sk_1\)) and a public key mapped to the G2 curve::
\(pub_1=sk_1.G_2\)
Next we create a hash of the message (\(h(M)\)) and then create the signature of:
\(\sigma_1 =sk_1.H(M)\)
Next we check the pair:
\( e(\sigma_1, G_2) == e(H(m), pk_1 )\)
This works because:
\( e(\sigma_1, G_2) == e(H(m), pk_1 )\)
is:
\( e(x.H(M), G_2) == e(H(m), pk_1 )\)
and:
\( e(H(M), x.G_2) == e(H(m), pk_1 )\)
which is:
\( e(H(M), pk_1) == e(H(m), pk_1 )\)
If lhs is equal to rhs, the pairing works, and the signature is verified.
Now we can aggregate the signatures. For a second set of keys, we now have a public key of:
\(pub_2=sk_2.G_2\)
and where the second signature will be:
\(\sigma_2 =sk_2.H(M)\)
Then the aggregated public key will be:
\(pk_a=pub_1+pub_2\)
Then the aggregated signature will be:
\(\sigma_a=\sigma_1+\sigma_2\)
The check is then:
\( e(\sigma_a, G_2) == e(H(m),pk_a )\)
Coding
An outline of the Go code is:
package main import ( "bytes" "fmt" "math/big" "os" "crypto/rand" "github.com/cloudflare/bn256" ) func main() { salt := []byte{11, 12, 13, 14} message:="hello" argCount := len(os.Args[1:]) if argCount > 0 { message = os.Args[1] } msg := []byte(message) G2 := new(bn256.G2).ScalarBaseMult(big.NewInt(1)) privKey, _ := rand.Int(rand.Reader, bn256.Order) pubKey := new(bn256.G2).ScalarBaseMult(privKey) hash := bn256.HashG1(msg, salt) sigma := new(bn256.G1).ScalarMult(hash, privKey) // check e(sigma, g2) == e(H(m), pk ) rhs := bn256.Pair(hash, pubKey) lhs := bn256.Pair(sigma, G2) fmt.Printf("Message %s\n", message) fmt.Printf("Private key 1: %x\n", privKey) fmt.Printf("\nPublic key 1: %x\n", pubKey.Marshal()) fmt.Printf("\nSignature (sigma): %x\n", sigma.Marshal()) if bytes.Equal(rhs.Marshal(), lhs.Marshal()) { fmt.Printf("\nSignature verified!\n") } beta,_:= rand.Int(rand.Reader, bn256.Order) betapubKey := new(bn256.G2).ScalarBaseMult(beta) sigmabeta := new(bn256.G1).ScalarMult(hash, beta) fmt.Printf("Private key 2: %x\n", privKey) fmt.Printf("\nPublic key 2: %x\n", pubKey.Marshal()) fmt.Printf("\nSignature (sigma2): %x\n", sigma.Marshal()) sigma_aggr := sigma.Add(sigma, sigmabeta) pub_aggr := pubKey.Add(pubKey, betapubKey) fmt.Printf("\nSignature aggregated: %x\n", sigma.Marshal()) fmt.Printf("\nPublic key aggregated: %x\n", pub_aggr.Marshal()) rhs = bn256.Pair(hash, pub_aggr) lhs = bn256.Pair(sigma_aggr, G2) if bytes.Equal(rhs.Marshal(), lhs.Marshal()) { fmt.Printf("\nAggregated Signature verified!") } }
A sample run:
Message abc Private key 1: 1b2d4de0fda90bc7c2dfe643e2638304affa190271dad1a9c3b117b1e9cfa622 Public key 1: 0189b2de7fe86b0fbf0cb8bfdde21823b5146e6c4bef32fb7b9599b670bbfe08498399ce31c353517ebc7963dc1ab5f538e0246f01c74a8e65404b10a6c744010e3a9e538d6d8635b8dc7158ec637385a1c8b54c46fb95a0442713421d8d10f12a5e59d6547e7cedbe17a739d371f604654a73ac4b46c69b0891b52a6c871155a8 Signature (sigma): 08fcbee36219b6170258c04c592deb2eeb31b6eef117f2207f128c792b757b276d8613c5c342693ee9e1a200c9bdf1b0340c0f3b91f5dbcac4e0ba38fd1d0319 Signature verified! Private key 2: 1b2d4de0fda90bc7c2dfe643e2638304affa190271dad1a9c3b117b1e9cfa622 Public key 2: 0189b2de7fe86b0fbf0cb8bfdde21823b5146e6c4bef32fb7b9599b670bbfe08498399ce31c353517ebc7963dc1ab5f538e0246f01c74a8e65404b10a6c744010e3a9e538d6d8635b8dc7158ec637385a1c8b54c46fb95a0442713421d8d10f12a5e59d6547e7cedbe17a739d371f604654a73ac4b46c69b0891b52a6c871155a8 Signature (sigma2): 08fcbee36219b6170258c04c592deb2eeb31b6eef117f2207f128c792b757b276d8613c5c342693ee9e1a200c9bdf1b0340c0f3b91f5dbcac4e0ba38fd1d0319 Signature aggregated: 6c2611463c139433f8faa8e0dc2e4ba233c9a4fcba662eed01d1cc82fa79ab9c5bf8ec339998c759f7259a956643ed2d8a8ec724fd5befeb458e2cdd27ba394b Public key aggregated: 0183afce8d5155c681d6b12cd7beb648ab878e29578d396c785eba6f773c32e61e3e83e2707e2833062ec401f3bb4bc39d43688f31061cd6f5db6ad208182808136ddab6233ac78221f4a3580a1c35d91cb8784c4744a6a504d59e8dc65ff45bdd401232feec6f5a9f67ebaf962173d13c4c73dcd9eabe19dc0eb46e14df66fde6 Aggregated Signature verified!