[NOT-101] Weeknotes individual update: November 13, 2023

[dtbuchholz]

Multiset Hash in Go using Ristretto

by Avichal Pandey

We previously explored set-based cryptographic hashes in the context of homomorphic hashing. In this post, I want to illustrate implementing a hashing scheme with multi-set semantics in Go using the go-ristretto library.

Multisets are sets where elements can repeat. In our hashing scheme, an item's hash representation does not depend on the order of elements. Elliptic curve operations do all the heavy lifting for computing the hashes. The go-ristretto library provides a Go implementation of the - Ristretto group.

Ristretto is a technique to construct a prime-order group from a non-prime-order elliptic curve, providing safer and more efficient cryptographic operations.

// MultisetHash contains `accumulator`,
// it is a pointer to a `ristretto.Point`.
// This point serves as the cumulative hash
// of all elements in the multiset at any time.
// 
// Each item in the set is represented as
// a `ristretto.Point` on the curve
type MultisetHash struct {
    accumulator *ristretto.Point 
}

func NewMultisetHash() *MultisetHash {
    var p ristretto.Point
    p.SetBase()
    return &MultisetHash{
        accumulator: &p,
    }
}

// Insert implements a "set" insert,
// using Elliptic Curve Addition.
func (h *MultisetHash) Insert(p *ristretto.Point) {
    h.accumulator.Add(h.accumulator, p) 
}

// Removes recomputes the hash of set with the 
// item removed.
func (h *MultisetHash) Remove(p *ristretto.Point) {
    h.accumulator.Sub(h.accumulator, p)
}

// Similarly, you can implement other methods
// relevant to sets

// Here is an example of using the Insert
hashSet := NewMultisetHash()

// Create a new point for your data
var point ristretto.Point
point.DeriveDalek([]byte("foobarbaz"))
// Insert into the set!
hashSet.Insert(&point)

As shown, elements are inserted by adding their corresponding Ristretto points to the accumulator. They are removed by performing subtraction on elliptic curve points. Similarly, we can implement other set operations such as union, set-difference, etc.

The multi-set hashes are versatile. They can be used in several applications, such as ensuring the integrity of datasets where the order of data isn't fixed. They are also used as cryptographic accumulators in specific scenarios.

_{From SyncLinear.com | NOT-101}