An accumulator allows Bob to add values onto a fixed-length digest, and to provide proof of the values added, without revealing them within the accumulated value. In this case, we will add a message onto an accumulator for a given message, and then we will remove it to show that the accumulator goes back to its original state. In this was Bob can prove that he knows something without actually revealing it to Alice, and where Bob can provide proof to it. In this case, we will use the Kyptography library from Coinbase, and add a message onto an accumulator, to prove that we know the message without actually revealing it. After we generate the proof, we will remove the message from the accumulator, and prove that it has gone back to its original value. Overall, we can add and remove any number of elements, and prove multiple proofs in a single round.
Accumulators |
Method
We give away too much of our private information. In most cases when we log into a system we have to reveal our password to the system. If someone is listening to the communications, they could reveal our password. So why can't we just prove that we know something, without revealing it? Well, Zero Knowledge Proofs (ZKPs) aim to do that. In this case we will look at an accumulator method using Bilinear Maps, as first proposed by Nyugen [1]. Overall, we can create an accumulator with a BLS curve. For this we generate a random nonce and generated a shared secret key for the proof:
curve := curves.BLS12381(&curves.PointBls12381G1{}) var seed [32]byte key, _ := new(accumulator.SecretKey).New(curve, seed[:])
We are not generating a random seed here, but, in practice, it would be a random value. Next we can create the new accumulator with this secret key::
acc, _ := new(accumulator.Accumulator).New(curve)
Now we can add a message as an element onto the accumulator:
element := curve.Scalar.Hash([]byte(msg)) _, _ = acc.Add(key, element)
We can then share the accumulator value to show that we know the message. If we want, we can now remove the message from the accmulator with:
_, _ = acc.Remove(key, element)
Adding and removing from an accumulator
We will use a BL12 curve, and which has two cyclic groups \(\mathbb{G}_1\) and \(\mathbb{G}_2\). We generate a key pair on the \(\mathbb{G}_1\) group. Initially we create a random secret key value (\(sk\)) and then a public key of:
\(pk= sk.G_1\)
and where \(G_1\) is the base point on the \(\mathbb{G}_1\) group. We can then initialise the accumulator with:
\(a_0=G_1\)
To add \(y_1\), we add to the accumulator with:
\(a_1=(y_1+sk).a_0\)
To add \(y_2\), we add to the accumulator with:
\(a_2=(y_2+sk).a_1 = (y_2+sk) (y_1+sk). a_0 \)
To remove \(y_1\) from \(a_2\):
\(a_3=a_2 . \frac{1}{y_1+sk} = \frac{ (y_1+sk).a_0 . (y_2 + sk) } {y_1+sk} = (y_2+sk) . a_0 \)
The code in Kryptology to add \(y\):
val := y.Add(sk) acc.value = acc.value.Mul(val)
and to remove \(y\):
val := y.Add(sk) // y + sk y, err := val.Invert() // 1/(y+sk) acc.value = acc.value.Mul(y)
Coding
In this case we will use the BLS curve:
package main import ( "fmt" "os" "github.com/coinbase/kryptology/pkg/accumulator" "github.com/coinbase/kryptology/pkg/core/curves" ) func main() { msg := "Hello" argCount := len(os.Args[1:]) if argCount > 0 { msg = os.Args[1] } curve := curves.BLS12381(&curves.PointBls12381G1{}) var seed [32]byte key, _ := new(accumulator.SecretKey).New(curve, seed[:]) acc, _ := new(accumulator.Accumulator).New(curve) element := curve.Scalar.Hash([]byte(msg)) rtn, _ := acc.MarshalBinary() fmt.Printf("Before add: %x\n", rtn) _, _ = acc.Add(key, element) rtn, _ = acc.MarshalBinary() fmt.Printf("\nAfter add: %x\n", rtn) _, _ = acc.Remove(key, element) rtn, _ = acc.MarshalBinary() fmt.Printf("\nAfter remove: %x\n", rtn) }
A sample run:
Message to prove: Hello Nonce: 0000000000000000000000000000000000000000000000000000000000000000 Key: 2007ec86a2ab79613fc0294e058151ddc74db38b0cde95a4678eb91f1258f31b400a424c5331323338314731 Before add: 3097f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb0a424c5331323338314731 After add: 30a2ad98cb32af3afdaedac08e48e61c67929578f78d2a0985f5f55bfbe8ede8747b5f917ce2be90477bae72c4ae7734430a424c5331323338314731 After remove: 3097f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb0a424c5331323338314731
Coding
References
[1] Nguyen, L. (2005, February). Accumulators from bilinear pairings and applications. In Cryptographers' track at the RSA conference (pp. 275–292). Springer, Berlin, Heidelberg.