Module lthash

commonware_cryptography

Module lthash 

Source
Expand description

A homomorphic hash function that enables efficient incremental updates.

LtHash is an additive homomorphic hash function over crate::Blake3, meaning that the hash of a sum equals the sum of the hashes: H(a + b) = H(a) + H(b). This useful property enables the efficient addition or removal of elements from some hashed set without recomputing the entire hash from scratch. This unlocks the ability to compare set equality without revealing the entire set or requiring items be added in a specific order.

§Properties

  • Homomorphic: Supports addition and subtraction of hashes (H(a ± b) = H(a) ± H(b))
  • Commutative: Operation order doesn’t matter (H(a) + H(b) = H(b) + H(a))
  • Incremental: Update existing hashes in O(1) time instead of rehashing everything

If your application requires a (probabilistic) membership check, consider using crate::BloomFilter instead.

§Security

LtHash’s state consists of 1024 16-bit unsigned integers (2048 bytes), as recommended in “Securing Update Propagation with Homomorphic Hashing”. This provides (by their estimates) at least 200 bits of security.

§Warning

This construction has a known vulnerability: adding the same element 2^16 times will cause overflow and result in the same hash as not adding it at all. For applications where this is a concern, consider adding unique metadata (like indices or timestamps) to each element.

§Example

use commonware_cryptography::lthash::LtHash;

// Demonstrate the homomorphic property
let mut lthash = LtHash::new();

// Add elements to our set
lthash.add(b"alice");
lthash.add(b"bob");
lthash.add(b"charlie");

// Remove an element (homomorphic subtraction)
lthash.subtract(b"bob");

// This is equivalent to just adding alice and charlie
let mut lthash2 = LtHash::new();
lthash2.add(b"alice");
lthash2.add(b"charlie");

assert_eq!(lthash.checksum(), lthash2.checksum());

// Order doesn't matter (commutative property)
let mut lthash3 = LtHash::new();
lthash3.add(b"charlie");
lthash3.add(b"alice");

assert_eq!(lthash2.checksum(), lthash3.checksum());

§Acknowledgements

The following resources were used as references when implementing this crate:

Structs§

LtHash
An additive homomorphic hash function over crate::Blake3.