Add and Removing Data from ECC Accumulators

Add and Removing Data from ECC Accumulators

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 use a basic ECC method to make commitments to data elements.

We will use a BL12 curve, and which has two cyclic groups of 𝔾1 and 𝔾2. Initially, we generate a key pair on the 𝔾1 group, and where the private key values will be used to add and delete data entities on the accumulator. Initially, we create a random secret key value (sk) and then a public key of:

The outline code is to add the hash of a message to the accumulator, and then remove it back to its original state [here]:

package main

import (
	"fmt"
	"os"

	"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

	sk := curve.Scalar.Hash(seed[:])
	acc := curve.Scalar.Point().Generator()

	fmt.Printf("Curve: %s", curve.Name)

	element := curve.Scalar.Hash([]byte(msg))

	fmt.Printf("\nAccumulator (initialisation): \n%x\n%x\n", acc.ToAffineUncompressed()[0:48], acc.ToAffineUncompressed()[48:])
	fmt.Printf(" Message to add: %x", msg)
	fmt.Printf(" Hash to add: %x", element.Bytes())

	/// Add
	val := element.Add(sk)
	acc = acc.Mul(val)

	fmt.Printf("\nAccumulator (after adding): \n%x\n%x\n", acc.ToAffineUncompressed()[0:48], acc.ToAffineUncompressed()[48:])

	// remove
	val = element.Add(sk) // y + sk
	y, _ := val.Invert()  // 1/(y+sk)
	acc = acc.Mul(y)

	fmt.Printf("\nAccumulator (after deletion): \n%x\n%x\n", acc.ToAffineUncompressed()[0:48], acc.ToAffineUncompressed()[48:])

}

A sample run [here]:

Curve: BLS12-831
Accumulator (initialisation): 
17f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb
08b3f481e3aaa0f1a09e30ed741d8ae4fcf5e095d5d00af600db18cb2c04b3edd03cc744a2888ae40caa232946c5e7e1
 Message to add: the
 Hash to add: 6c8e6f2b9d45f59961087ae96ead4c3b58dcdb04de92015a05bec15c7b916a9f

Accumulator (after adding): 
15a8343542abd5e37d13d4450ad4d24528c26c3c0046aa4a6772f9d5f1b297c71f1e970af923c71955ffe25d00a7c6a3
1004b985bb385d499184f64431e8d248af7cf6fc9ac268227cfa9571c02d77a15a33ed9e3364eb5bda38808ce7606838

Accumulator (after deletion): 
17f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb
08b3f481e3aaa0f1a09e30ed741d8ae4fcf5e095d5d00af600db18cb2c04b3edd03cc744a2888ae40caa232946c5e7e1

We can see that we start with the base point on G1 for the accumulator. Next, we add the message as a hash value. This is achieved by multiplying the existing accumulator value, with (sk + H), and where H is the hash of the new message. To remove the value of H, we would just divide by (sk+H). For this, we just compute (sk+H) and then compute the inverse value for this.