Permissioned Repo Commits with ECMH#

This document describes how ECMH is used to build authenticated, per-reader commits for permissioned repositories. Each commit characterizes the current set of live records in a repo without exposing that information to other readers.

Permissioned repo commits#

Each user's permissioned repo within a space is represented by a cryptographic commit: a compact digest that characterizes the current set of live records, independent of history.

We use ECMH (Elliptic Curve Multiset Hash), a set hash where adding or removing an element is a single point operation rather than a full recompute. Two permissioned repos with the same live records produce the same ECMH digest regardless of the order records were written or deleted.

This commitment plays the same role as the MST root hash for public data: a single value that definitively characterizes what is in the repo. Unlike the MST, it does not support partial sync or single-record proofs. The tradeoff is a noticeably lower-overhead cryptographic structure and sync protocol.

The problem with bare ECMH digests#

ECMH is deterministic. If client-a and client-b happen to have permissioned repos with identical live records, their bare ECMH digests will be identical. A party who obtains both commits can tell that the two repos contain the same data, even without knowing what that data is.

Worse, a bare digest can be rebroadcast. If client-a receives a commit from the server, nothing stops client-a from forwarding that commit to a third party who can then verify it against data they obtain independently.

Both problems are solved by authenticating the ECMH digest with a randomly generated, transient HMAC key that is unique to each reader.

Commit structure#

A permissioned repo commit is composed of four fields:

commit = {
    ecmh:       bytes,    // the ECMH digest of the live record set
    hmac:       bytes,    // HMAC-SHA256(hmac_key, ecmh)
    hmac_key:   bytes,    // randomly generated, unique per reader
    sig:        bytes,    // atproto signing key signature over (ecmh, hmac, hmac_key)
}

The server generates a fresh HMAC key for every reader on every read. The signature binds all fields together under the repo owner's signing key.

Why this works#

Different commits for identical repos#

Even when two readers have access to repos with the exact same live records, the ECMH digests are the same but the commits are different because each reader receives a distinct random HMAC key:

Reader A receives:
    ecmh     = 0x7a3f...   (deterministic, same for identical sets)
    hmac_key = 0x91ab...   (random, unique to this reader)
    hmac     = HMAC-SHA256(0x91ab..., 0x7a3f...)  →  0xd4e7...
    sig      = sign(ecmh || hmac || hmac_key)

Reader B receives:
    ecmh     = 0x7a3f...   (same ECMH — same records)
    hmac_key = 0xc30f...   (different random key)
    hmac     = HMAC-SHA256(0xc30f..., 0x7a3f...)  →  0x18b2...
    sig      = sign(ecmh || hmac || hmac_key)

The two commits share the same ECMH value, but the HMACs are completely different. A third party comparing the two commits cannot determine whether the underlying repos are identical without independently knowing the record sets.

Deniability#

The HMAC key is included in the commit. This is intentional. Because anyone who holds the key can produce a valid HMAC over any ECMH digest, a leaked commit does not serve as cryptographic proof that the signer sent that specific content to that specific reader. The signature covers the bundle, but the HMAC key's presence means the reader could have constructed the HMAC themselves.

This gives the signer plausible deniability: the commit authenticates the data for the intended reader, but is not a transferable proof to third parties.

No rebroadcast#

Each commit is authenticated for exactly one party. If client-a forwards their commit to client-b, client-b has no reason to trust it: the HMAC key was chosen for client-a, and client-b has their own key. The server will never produce the same HMAC key for two different readers.

Demonstration#

The following shows how the ECMH layer fits into the commit protocol. The HMAC and signature operations use standard cryptographic primitives alongside the ecmh crate.

use ecmh::RistrettoEcmh;
use hmac::{Hmac, Mac};
use sha2::Sha256;

type HmacSha256 = Hmac<Sha256>;

/// A permissioned repo commit.
struct Commit {
    ecmh: Vec<u8>,
    hmac: Vec<u8>,
    hmac_key: Vec<u8>,
    sig: Vec<u8>,
}

// --- Server side ---

// The repo's live record set, maintained incrementally.
let mut repo = RistrettoEcmh::new();
repo.insert(b"at://did:plc:abc/app.bsky.feed.post/3abc");
repo.insert(b"at://did:plc:abc/app.bsky.feed.post/3def");
repo.insert(b"at://did:plc:abc/app.bsky.feed.like/3ghi");

let ecmh_bytes = repo.to_bytes();

// Generate a commit for reader A.
let hmac_key_a: [u8; 32] = rand::random();
let mut mac_a = HmacSha256::new_from_slice(&hmac_key_a).unwrap();
mac_a.update(&ecmh_bytes);
let hmac_a = mac_a.finalize().into_bytes();

// Generate a commit for reader B — same repo, different key.
let hmac_key_b: [u8; 32] = rand::random();
let mut mac_b = HmacSha256::new_from_slice(&hmac_key_b).unwrap();
mac_b.update(&ecmh_bytes);
let hmac_b = mac_b.finalize().into_bytes();

// The ECMH digests are identical (same live records)...
assert_eq!(ecmh_bytes, repo.to_bytes());

// ...but the HMACs are different (different transient keys).
assert_ne!(hmac_a.as_slice(), hmac_b.as_slice());

// Each commit is then signed by the repo owner's atproto signing key
// and delivered to the respective reader.

Verification by the reader#

The reader verifies the commit by:

1. Checking the signature against the repo owner's public key
2. Recomputing the HMAC from the provided key and ECMH digest
3. Comparing the recomputed HMAC to the one in the commit
4. Optionally, recomputing the ECMH from the received records to verify consistency

// --- Reader A side ---

// Reader A receives the commit and the record set from the server.
let received_ecmh = &ecmh_bytes;
let received_hmac = hmac_a.as_slice();
let received_key = &hmac_key_a;

// Step 1: verify signature (omitted — use atproto signing key verification)

// Step 2: recompute HMAC
let mut verifier = HmacSha256::new_from_slice(received_key).unwrap();
verifier.update(received_ecmh);
verifier.verify_slice(received_hmac).expect("HMAC mismatch");

// Step 3: recompute ECMH from the records to check consistency
let mut local = RistrettoEcmh::new();
local.insert(b"at://did:plc:abc/app.bsky.feed.post/3abc");
local.insert(b"at://did:plc:abc/app.bsky.feed.post/3def");
local.insert(b"at://did:plc:abc/app.bsky.feed.like/3ghi");
assert_eq!(local.to_bytes(), *received_ecmh);

Incremental sync#

When records are added or removed, the server updates the ECMH incrementally and issues a new commit with a fresh HMAC key:

// Server adds a new record
repo.insert(b"at://did:plc:abc/app.bsky.feed.post/3jkl");

// Server deletes an old record
repo.remove(b"at://did:plc:abc/app.bsky.feed.like/3ghi");

// New commit for reader A with a fresh key
let new_ecmh = repo.to_bytes();
let new_hmac_key: [u8; 32] = rand::random();
let mut mac = HmacSha256::new_from_slice(&new_hmac_key).unwrap();
mac.update(&new_ecmh);
let new_hmac = mac.finalize().into_bytes();

// The new ECMH reflects the updated record set.
// The new HMAC key ensures this commit is distinct from all prior commits,
// even if the record set happens to return to a previous state.

Security properties#

Limitations#

ECMH equality across readers. The raw ECMH field is the same for identical repos. The HMAC prevents trivial comparison of commits, but a reader who strips the HMAC and compares raw ECMH values with another reader can determine set equality. If this is a concern, the ECMH digest itself can be encrypted or omitted from the wire format, transmitting only the HMAC.

Small record universes. If the space of possible records is small enough to enumerate, an attacker can brute-force the ECMH by hashing all possible subsets. ECMH security relies on the record space being large.

HMAC key lifecycle. The HMAC key must be generated fresh for every read and never reused. Reusing a key across readers or across time would allow the same comparison attacks the HMAC is designed to prevent.

No partial proofs. Unlike a Merkle tree, ECMH does not support proving that a single record is or is not in the set without revealing the entire set. The tradeoff is significantly lower computational and storage overhead.