Witnesses and Accumulators in Kryptology for ZKP[Pairing Home][Home]
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 number of strings "alice", "bob" "eve", "carol", "dave", "grace" and "faith". Bob can then provide a witness proof that one of these exists in the accumulator, and Alice can prove this. We will then remove one of the these strings, and we will prove that the witness statement will fail.
|
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)
Generating a witness proof
We can now make our accumulator value public to anyone who wants to view it, along with revealing our public key (pk). No-one should be able to see any of the values we have added to the accumulator, but where we can create witness proofs to show that we have actually added something. If we haven't, the witness statement will be invalid. Now Bob will create a witness proof \(w\) that a given value (\(y_1\)) is in the accumulator. We compute the witness proof by showing the difference between the accumulator with \(y_1\) and without it:
\(w=a(\textrm{with}~ y_1)-a(\textrm{without}~ y_1)\)
Overall we prove the following pairing-based crypto statement:
\( \hat{e}(w,y.G_2+pk) \cdot \hat{e}(-a,G_2)=1\)
Within Krytology this is implemented as:
g2 := pk.value.Generator().(curves.PairingPoint) // y*tildeP + tildeQ, tildeP is a G2 generator. p := g2.Mul(mw.y).Add(pk.value).(curves.PairingPoint) // Prepare witness := mw.c.(curves.PairingPoint) v := acc.value.Neg().(curves.PairingPoint) // Check e(witness, y*tildeP + tildeQ) * e(-acc, tildeP) == Identity result := p.MultiPairing(witness, p, v, g2)
So, let's prove this. We get our witness proof, by removing \(y_1\) from \(a\):
\(w=\frac{a}{y_1+sk}\)
We have the proof of:
\( \hat{e}(w,y_1.G_2+pk) \cdot \hat{e}(-a,G_2)\)
To give:
\( \hat{e}(\frac{a}{y_1+sk},y_1.G_2+pk) \cdot \hat{e}(-a,G_2)\)
Next, we use the pairing rule of \( \hat{e}(U_1+U_2,V) = \hat{e}(U_1,V) \hat{e}(U_1,V) \):
\( \hat{e}(\frac{a}{y_1+sk},y_1.G_2) \cdot \hat{e}(\frac{a}{y_1+sk},pk) \cdot \hat{e}(-a,G_2)\)
and replace the public key:
\( \hat{e}(\frac{a}{y_1+sk},y_1.G_2) \cdot \hat{e}(\frac{a}{y_1+sk},sk \cdot G_2) \cdot \hat{e}(-a,G_2)\)
and using the pairing rule of \(\hat{e}(a.G_1,G_2) = \hat{e}(G_1,a.G_2) \):
\( \hat{e}(\frac{a . y_1}{y_1+sk},G_2) \cdot \hat{e}(\frac{a. sk}{y_1+sk},sk \cdot G_2) \cdot \hat{e}(-a,G_2)\)
and then:
\( \hat{e}(\frac{a.(y+sk)}{y_1+sk},G_2) \cdot \hat{e}(-a,G_2)\)
and then:
\( \hat{e}(a,G_2) \cdot \hat{e}(-a,G_2)\)
and which will equal unity, and will have proven the presense of \(y_1\).
Implementation
The following is an implementation of a witness:
package main import ( "fmt" "os" "strconv" "github.com/coinbase/kryptology/pkg/accumulator" "github.com/coinbase/kryptology/pkg/core/curves" ) func main() { curve := curves.BLS12381(&curves.PointBls12381G1{}) var seed [32]byte sk, _ := new(accumulator.SecretKey).New(curve, seed[:]) pk, _ := sk.GetPublicKey(curve) sk_b, _ := sk.MarshalBinary() pk_b, _ := pk.MarshalBinary() eltoremove := 0 argCount := len(os.Args[1:]) if argCount > 0 { eltoremove, _ = strconv.Atoi(os.Args[1]) } fmt.Printf("Secret key: %x\n", sk_b) fmt.Printf("Public key: %x\n", pk_b) element1 := curve.Scalar.Hash([]byte("alice")) element2 := curve.Scalar.Hash([]byte("bob")) element3 := curve.Scalar.Hash([]byte("eve")) element4 := curve.Scalar.Hash([]byte("carol")) element5 := curve.Scalar.Hash([]byte("dave")) element6 := curve.Scalar.Hash([]byte("grace")) element7 := curve.Scalar.Hash([]byte("faith")) elements := []accumulator.Element{element1, element2, element3, element4, element5, element6, element7} acc, _ := new(accumulator.Accumulator).WithElements(curve, sk, elements) wit, _ := new(accumulator.MembershipWitness).New(elements[eltoremove], acc, sk) acc_b, _ := acc.MarshalBinary() wit_b, _ := wit.MarshalBinary() fmt.Printf("\n=== Now adding elements ===\n") fmt.Printf("Accummulator: %x\n", acc_b) fmt.Printf("Witness: %x\n", wit_b) rtn := wit.Verify(pk, acc) if rtn == nil { fmt.Printf("Valid Witness\n") } else { fmt.Printf("Not Valid Witness\n") } fmt.Printf("\n=== Now removing element [%d] ===\n", eltoremove) acc, _ = acc.Remove(sk, elements[eltoremove]) acc_b, _ = acc.MarshalBinary() fmt.Printf("Accumulator: %x\n", acc_b) rtn = wit.Verify(pk, acc) if rtn == nil { fmt.Printf("Valid Witness\n") } else { fmt.Printf("Not Valid Witness\n") } }
A sample run:
Secret key: 2007ec86a2ab79613fc0294e058151ddc74db38b0cde95a4678eb91f1258f31b400a424c5331323338314731 Public key: 60a99213e935279e8f568e1736bb7050d6b7aa7ca7faa80daa31eabbfded84c3c2b49edb380b49898c90ff2494b4849c3a003e8019cbdbb2d446ddda6b8299591abf3c805058b5569568031b61a57d236e692ed1ae9700a8d08023ab81836710cf0a424c5331323338314732 === Now adding elements === Accummulator: 30b73125d9efaf7bd14015991fb4506b9cb383b7d8eb41ff77a7467440b51fc6d2edc4af0046c177c035f82fd60b4d30c50a424c5331323338314731 Witness: 50b79652a4f3f4779a72ab417616b20fade9318150a26ec95b8c1a78cb8ea62f99bdb4cab03fb17f11bf26650f312729b1495423d677fd827467948aeab963cea2b4acb9225f9c649cd15b40bde8b71a1e0a424c5331323338314731 Valid Witness === Now removing element [0] === Accumulator: 30b79652a4f3f4779a72ab417616b20fade9318150a26ec95b8c1a78cb8ea62f99bdb4cab03fb17f11bf26650f312729b10a424c5331323338314731 Not Valid Witness