multiset-hash

本crate提供了一个针对多重集的哈希函数，该函数可以增量更新。此函数接受一组对象，每个对象可能出现多次，并输出一个摘要。此结果仅取决于哪些对象在集中，以及它们出现的次数。以不同的顺序或不同的方式对对象进行分组时调用该函数，不会改变函数的结果。

这使得函数可以增量地添加新对象，而无需在内存中保留整个集合。

实现

本crate受到了Clarke等人于2003年发表的一篇论文的启发：一篇论文。他们定义了一个具有多重性x的对象哈希函数m(x)为

sum_x m(x) * H(x)

其中H是一个到适当阿贝尔群的哈希函数。在他们的情况下，他们使用了有限域的乘法群。从那时起，我们已经发展出了更优雅（在我看来）的椭圆曲线群。本crate使用了由Ristretto实现的curve25519-dalek crate。

示例

在通常情况下，你可以添加不同的字节切片，具有多重性。例如，要哈希集合{cat, cat, dog, dog}，你可以这样做

# use multiset_hash::RistrettoHash;
use digest::Digest;
use sha2::Sha512;

let mut hash = RistrettoHash::<Sha512>::default();
hash.add(b"cat", 2);
hash.add(b"dog", 2);

这相当于对具有不同分组和顺序相同数量的对象进行哈希

# use multiset_hash::RistrettoHash;
# use sha2::Sha512;
use digest::Digest;

let mut hash = RistrettoHash::<Sha512>::default();
hash.add(b"dog", 1);
hash.add(b"cat", 1);
hash.add(b"cat", 1);
hash.add(b"dog", 1);

您还可以使用update方法对多个部分的对象进行哈希

# use multiset_hash::RistrettoHash;
# use sha2::Sha512;
use digest::Digest;

let mut hash = RistrettoHash::<Sha512>::default();
hash.update(b"d");
hash.update(b"og");
hash.end_update(2);
hash.add(b"cat", 2);

如果使用update，则必须在添加另一个对象或调用finalize以获取哈希函数的输出之前调用end_update。