ecmh#

Elliptic Curve Multiset Hash (ECMH) for Rust and WebAssembly — a homomorphic hash function for multisets based on Maitin-Shepard et al. (2016).

ECMH maps each set element to an elliptic curve point and sums them. The hash of the union of two multisets is simply the sum of their individual hashes, enabling efficient incremental updates without rehashing the entire set.

Features#

• Incremental: insert and remove elements without recomputing from scratch
• Order-independent: H({a, b}) == H({b, a})
• Homomorphic: H(A ∪ B) == H(A) + H(B)
• Multiple curve backends behind feature flags:

• Operator overloading: +, -, +=, -= for combining hashes
• Custom curves: implement the CurveBackend trait
• WebAssembly: first-class wasm support via wasm-pack

Usage#

Rust#

[dependencies]
ecmh = "0.1"

For a specific curve backend:

[dependencies]
ecmh = { version = "0.1", default-features = false, features = ["p256"] }

WebAssembly#

Build the wasm package with wasm-pack:

wasm-pack build --target web --features wasm

This produces a pkg/ directory containing the .wasm binary, JS glue, and TypeScript definitions ready for npm publish or direct use.

For additional curve backends in the wasm build:

wasm-pack build --target web --features wasm,p256,k256

Example (Rust)#

use ecmh::RistrettoEcmh;

// Build a multiset hash incrementally
let mut hash = RistrettoEcmh::new();
hash.insert(b"alice");
hash.insert(b"bob");

// Order doesn't matter
let mut hash2 = RistrettoEcmh::new();
hash2.insert(b"bob");
hash2.insert(b"alice");
assert_eq!(hash, hash2);

// Combine disjoint sets
let a = RistrettoEcmh::from_element(b"alice");
let b = RistrettoEcmh::from_element(b"bob");
assert_eq!(hash, a + b);

// Remove an element
let mut h = hash.clone();
h.remove(b"bob");
assert_eq!(h, RistrettoEcmh::from_element(b"alice"));

// Build from an iterator
let from_iter = RistrettoEcmh::from_elements([
    b"alice".as_slice(),
    b"bob".as_slice(),
]);
assert_eq!(from_iter, hash);

// Serialize / deserialize
let bytes = hash.to_bytes();
let recovered = RistrettoEcmh::from_bytes(&bytes).unwrap();
assert_eq!(recovered, hash);

Example (JavaScript / TypeScript)#

import init, { EcmhRistretto } from './pkg/ecmh.js';

await init();

const enc = new TextEncoder();

// Build a multiset hash incrementally
const hash = new EcmhRistretto();
hash.insert(enc.encode("alice"));
hash.insert(enc.encode("bob"));

// Order doesn't matter
const hash2 = new EcmhRistretto();
hash2.insert(enc.encode("bob"));
hash2.insert(enc.encode("alice"));
console.log(hash.equals(hash2)); // true

// Combine disjoint sets
const a = EcmhRistretto.fromElement(enc.encode("alice"));
const b = EcmhRistretto.fromElement(enc.encode("bob"));
console.log(a.union(b).equals(hash)); // true

// Serialize
console.log(hash.toHex());   // 64-char hex string
console.log(hash.toBytes()); // Uint8Array(32)

// Deserialize
const recovered = EcmhRistretto.fromBytes(hash.toBytes());
console.log(recovered.equals(hash)); // true

The wasm build exposes one class per enabled curve backend:

Custom curve backend#

Implement the CurveBackend trait to use any elliptic curve:

use ecmh::CurveBackend;

#[derive(Clone, Default, Debug)]
struct MyCurve;

impl CurveBackend for MyCurve {
    type Point = /* your point type */;
    const POINT_SIZE: usize = /* compressed size */;

    fn identity() -> Self::Point { /* ... */ }
    fn hash_to_point(data: &[u8]) -> Self::Point { /* ... */ }
    fn add(a: &Self::Point, b: &Self::Point) -> Self::Point { /* ... */ }
    fn sub(a: &Self::Point, b: &Self::Point) -> Self::Point { /* ... */ }
    fn is_identity(p: &Self::Point) -> bool { /* ... */ }
    fn to_bytes(p: &Self::Point) -> Vec<u8> { /* ... */ }
    fn from_bytes(bytes: &[u8]) -> Option<Self::Point> { /* ... */ }
}

References#

• Elliptic Curve Multiset Hash — Maitin-Shepard, Tibouchi, Aranha (2016)
• jbms/ecmh — C++ reference implementation
• cronokirby/multiset-hash — earlier Rust crate (Ristretto only, outdated deps)
• ECMH BIP proposal — Bitcoin specification using secp256k1

License#

MIT OR Apache-2.0