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.
ECC accumulators with Golang |
Method
We will use a BL12 curve, and which has two cyclic groups of \(\mathbb{G}_1\) and \(\mathbb{G}_2\). For this, we generate a key pair on the \(\mathbb{G}_1\) group, and where the private key value 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:
\(pk= sk.G_1\)
and where \(G_1\) is the base point on the \(\mathbb{G}_1\) group. We can then initialise the accumulator from the base point on the \(\mathbb{G}_1\) group:
\(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 \(element\) and which is a hash of a message (\(msg\)):
element := curve.Scalar.Hash([]byte(msg)) /// Add val := element.Add(sk) // e+sk acc = acc.Mul(val)
and to remove this:
val = element.Add(sk) // e + sk y, _ := val.Invert() // 1/(e+sk) acc = acc.Mul(y)
Coding
The outline code is to add the hash of a message to the accumulator, and then remove it back to its original state:
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:
Curve: BLS12831 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 \(\mathbb{G}_1\) for the accummulator. Next we add the message as a hash value. This is achived 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.