# Multiset Hashes

Suppose we had an unordered set of possibly repeating elements, and we wanted to be able to efficiently update its hash without needing to keep the entire set around in memory. That's exactly what a multiset hash does.

Why a *multiset hash*, not a *set hash*? Two reasons - firstly, because when we're incrementally updating the hash, we can't know if the element we're adding already exists in the set if we only have the hash, so we instead consider the *number of times* the element appears in the set.

Secondly, we use them because collections in the [Maru programming model](/proxima/maru/programming-model.md) are multisets. In particular, for "linear" operators that don't require an [arrangement](/proxima/maru/how-maru-works/arrangements.md) (e.g. map, filter, sum, count) we won't need to use merkle trees at all, which are quite expensive to verify and update in a SNARK/STARK.

> A Multiset is a set of elements such that, for each element, we keep track of its "multiplicity" - that is, the number of times the element appears in the set. This is different from a set, because sets do not consider "duplicates" - adding an element a to a set S that already contains a will not change S. If S was a multiset, it *would* change. For more background on multiset hashes, check out [this awesome article](https://cronokirby.com/posts/2021/07/on_multi_set_hashing/) by [Lúcás Meier](https://twitter.com/cronokirby).

### The Hash Function <a href="#the-hash-function" id="the-hash-function"></a>

In Maru, we use the following hash function from [Clarke et.al](https://people.csail.mit.edu/devadas/pubs/mhashes.pdf):

$$\mathcal{H}(A) = \prod\_{a \in A}{H(a)^{m(a)}}$$

Where arithmetic is done over a field in which the discrete log problem is hard and $$H$$ is a cryptographic hash function whose output is an element in the field, and $$m(a)$$ denotes the multiplicity of $$a$$ in the multiset $$A$$.

We can then incrementally update the hash with a (possibly single-element) set of new values to add $$B$$ as follows, without keeping the entirety of $$A$$ in memory:

$$\mathcal{H}(A \cup B) = \mathcal{H}(A)\mathcal{H}(B)$$

An implementation of this function can be found at <https://github.com/proxima-one/multiplicity>.

There's just one problem with the hash function as it was introduced by Clarke et.al - it requires a really big field to be secure (\~4000 bits), and that's way too big to put into a starky STARK or plonky2 SNARK, whose native field is only 64 bits.

Luckily we can do the same thing in an elliptic curve group instead of a field:

$$\mathcal{H}(A \cup B) = \mathcal{H}(A)\mathcal{H}(B)$$

The only difference here is that $$H$$ is now a hash function that outputs a point on the **elliptic curve**, not the field. This allows us to use a much smaller elliptic curve representation, which should be cheaper in a starky STARK or plonky2 SNARK. [Lúcás Meier](https://twitter.com/cronokirby) wrote a [concrete implementation of this version over the Ristretto curve](https://github.com/cronokirby/multiset-hash).

### The "Goldilocks Curve" <a href="#the-goldilocks-curve" id="the-goldilocks-curve"></a>

Since we're doing this in STARKs and SNARKs, we want to avoid non-native field arithmetic. Even though the elliptic curve representation is smaller, non-native field arithmetic is quite expensive. Luckily, [Thomas Pornin](https://twitter.com/bearsslnews) found a curve whose base field is a degree-5 extension of Goldilocks, the native field for both starky and plonky2. While this curve is *technically* called ecgfg5, we call it the "Goldilocks curve" because its value to us is that it's base field is a native extension.

An implementation of the multiset hash using this curve will allow us to avoid non-native field arithmetic when performing multiset hashes, which will make our STARK/SNARK circuits much more efficient.

A safe-rust implementation of the curve can be found [here](https://github.com/pornin/ecgfp5) - in practice, we'll want to build atop [plonky2](https://github.com/mir-protocol/plonky2/blob/52faa0ceb7f52551f6c5f6e4f9c776234a35a2d0/field/src/goldilocks_extensions.rs#L94)'s implementation of the quintic goldilocks extension instead since we'll be using it in circuits.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://docs.proxima.one/proxima/maru/background-knowledge/multiset-hashes.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.