#multiset #hash #difference #homomorphic #incremental #union #additively

multiplicity

A simple additively homomorphic multiset hash function

2 releases

0.1.1 Apr 4, 2022
0.1.0 Mar 29, 2022

#14 in #multiset

MIT license

8KB
99 lines

multiplicity

Crates.io Documentation

This library provides a generic implementation of MSet-Mu-Hash from Clarke et. al's incremental multiset hash function paper. The implementation has not been autided, so use it at your own risk.

See the docs or check out tests in lib.rs for example usage.

Multisets

In this library, we interpret union of a multiset to mean that the multiplicity of each element in the union is the sum of its multiplicites in the inputs. We interpret "difference" to mean that the multiplicity of each element in the difference to be the difference between its multiplicities in the inputs.

It's worth noting that our intepretation of "difference" necessarily allows multisets to have negative multiplicities. This is weird, but it's quite useful when trying to commit to "state deltas" instead of entire states.

Dependencies

~115KB