Can I Reveal Part of My Answer To You, Without Revealing The Rest of It?

Can I Reveal Part of My Answer To You, Without Revealing The Rest of It? … Meet Accumulators and Witnesses

Let’s say a teacher asks pupils to name six of the largest counties in the world. The answers would be: Canada, Russia, China, US, Brazil and Australia. Now she tells the pupils to not show their answers but to commit them onto a piece of paper. After this, the teacher asks each pupil to show evidence of the counties they have selected with something she could witness, but not reveal the answer. She calls out Russia, and ask pupils to reveal their evidence, but not their answer. The pupils hold up the evidence and the teacher checks it. This evidence might be a drawing of the Russian flag, and the teacher can then witness the answer, without the pupil revealing the answer they have given. This is the wonderful world of zero-knowledge proofs and where we can commit to data, and then reveal part of it when required, without revealing the rest of the data we have.

Accumulators — adding and removing data

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 witness proof that one of these exists in the accumulator, and Alice can prove this. We will then remove one of these strings, and we will prove that the witness statement will fail.

Let’s investigate accumulators first, and where we create your accumulator and add and remove data elements using:

Creating a witness

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.

The method of creating a witness is then:

I have tried to outline the method on pen-and-paper here:

The following is an implementation of a witness [here]:

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

Secret key: 2007ec86a2ab79613fc0294e058151ddc74db38b0cde95a4678eb91f1258f31b400a424c5331323338314731
Public key: 60a99213e935279e8f568e1736bb7050d6b7aa7ca7faa80daa31eabbfded84c3c2b49edb380b49898c90ff2494b4849c3a003e8019cbdbb2d446ddda6b8299591abf3c805058b5569568031b61a57d236e692ed1ae9700a8d08023ab81836710cf0a424c5331323338314732

=== Now adding elements ===
Accummulator: 30b73125d9efaf7bd14015991fb4506b9cb383b7d8eb41ff77a7467440b51fc6d2edc4af0046c177c035f82fd60b4d30c50a424c5331323338314731
Witness: 50b79652a4f3f4779a72ab417616b20fade9318150a26ec95b8c1a78cb8ea62f99bdb4cab03fb17f11bf26650f312729b1495423d677fd827467948aeab963cea2b4acb9225f9c649cd15b40bde8b71a1e0a424c5331323338314731
Valid Witness

=== Now removing element [0] ===
Accumulator: 30b79652a4f3f4779a72ab417616b20fade9318150a26ec95b8c1a78cb8ea62f99bdb4cab03fb17f11bf26650f312729b10a424c5331323338314731
Not Valid Witness