Zero-Knowledge Proofs and Accumulators Using Kryptography and Crypto Pairings

Zero-Knowledge Proofs and Accumulators Using Kryptography and Crypto Pairings

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 Lan Nyugen [1] [here]:

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.

Creating an accumulator

We can create an accumulator with the BLS curve (BLS 12381). 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)

In this case we will use the BLS curve to provide our accumulator [here]:

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 [here]:

Message to prove: Hello
Nonce: 0000000000000000000000000000000000000000000000000000000000000000
Key: 2007ec86a2ab79613fc0294e058151ddc74db38b0cde95a4678eb91f1258f31b400a424c5331323338314731
Before add: 3097f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb0a424c5331323338314731

After add: 30a2ad98cb32af3afdaedac08e48e61c67929578f78d2a0985f5f55bfbe8ede8747b5f917ce2be90477bae72c4ae7734430a424c5331323338314731

After remove: 3097f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb0a424c5331323338314731

Conclusion

Zero is good! We can scale this method so that a witness can gather many proofs from hosts, and then compile into a single proof that is produced by the wistness. Another application is for Bob and Alice to agree to a starting point for the proofs, and where Bob and Alice can keep a trace of the current accumulator, and know what the expected new value will be. Only by knowing the original seed value of the accumulator, will they be able to know the next value.

If you are interested, here’s the running code:

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. [here]