DOCSEARCHbyAlgolia
Submit Docs

BeeKEM: Concurrent Group Key Agreement

repository·main·Indexed 42 days ago

https://github.com/inkandswitch/keyhive

A concurrent variant of TreeKEM for Continuous Group Key Agreement (CGKA) designed for local-first, peer-to-peer applications. BeeKEM enables secure, end-to-end encrypted data management without a central coordinator by utilizing causal ordering, binary tree structures, and conflict keys to provide forward secrecy and post-compromise security. It supports core operations including key rotation (Update), member addition, member removal, and root secret decryption using Diffie-Hellman, BLAKE3, and ChaCha20-Poly1305.

Tokens
40.8K
Snippets
106
Records
163
Agent score
54%

What's inside BeeKEM

  1. Overview of Keyhive libraries

    main

    Keyhive is a collection of libraries focused on end-to-end encrypted data management and signing. The current pre-alpha release includes three primary components:

    • beelay-core: Provides authentication-enabled synchronization over end-to-end encrypted data.
    • keyhive_core: The foundational system for signing, encryption, and delegation.
    • keyhive_wasm: A WebAssembly (Wasm) wrapper around keyhive_core that includes TypeScript bindings for web/client-side use.

  2. BeeKEM Overview

    main

    BeeKEM is a Continuous Group Key Agreement (CGKA) protocol designed for local-first, peer-to-peer applications. It is an adaptation of TreeKEM that operates without a central ordering server, relying instead on the causal ordering of operations. It is designed to maintain shared encryption keys for a dynamic group of peers, supporting offline operation and concurrent membership changes while providing forward secrecy and post-compromise security.

    Key characteristics:

    • No central coordinator: Uses causal ordering instead of a central server.
    • Standard primitives: Uses Diffie-Hellman (DH), BLAKE3 hashing, and ChaCha20-Poly1305.
    • Security: Provides forward secrecy (past data is safe if current keys are compromised) and post-compromise security (future data is safe after key rotation).

  3. Core architecture and design goals of Keyhive

    main

    Keyhive is designed for the authorization (authZ) of updates to local-first data (specifically optimized for Automerge). It provides end-to-end encryption (E2EE), continuous group key agreement (CGKA), and a capability system.

    Key design principles include:

    • Local-first & Partition Tolerance: Designed to run in environments where network boundaries cannot be relied upon (unlike OPAQUE), ensuring the application works on every replica based on its eventually-consistent view.
    • Agnostic Identity: Keyhive does not manage identity or account recovery. It is compatible with various PKI and identity systems (e.g., DID, Keyoxide, KERI, OpenPGP, ATProto) by focusing solely on public key cryptography (Ed25519) for signing and verifying data.
    • Two-part Security Model:
      1. Mutation Control: Managed via a capability system.
      2. Read Control: Managed via encryption-at-rest (E2EE).
    • Runtime Flexibility: Designed to run both natively and in the browser.

  4. How to use Reverse Depth First Traversal for stable ordering

    main

    To ensure that concurrent changes do not change the contents of a chunk (which would break synchronization), Sedimentree uses a reverse depth first traversal.

    Instead of traversing from the root (parents) to the leaves (children), you reverse the direction of the arrows and perform a depth first traversal starting from the ends (heads) of the graph. Because the parents of a commit never change, this traversal produces a stable ordering even when new commits are added to the DAG.

  5. Storage requirements for encrypted blobs

    main
    When using causal encryption, there is no dependency on the ordering of encrypted blobs in the underlying storage. Any set of blobs can be stored in any order, as the causal relationships and decryption paths are managed via the pointers and keys embedded within the blocks themselves.

  6. Manage Agent Re-Adds and Seniority

    main

    In Keyhive, an Agent may be re-added to a group after being removed.

    Requirements for Re-Adds:

    1. Causal Succession: The re-add operation MUST transitively causally succeed the agent's previous revocation.
    2. Seniority Preservation: When calculating an agent's seniority, the system MUST use their earliest Add operation (the one occurring prior to the revocation).

  7. How the Beelay sync system works

    main

    Beelay is the Keyhive Relay responsible for syncing E2EE chunks. It is designed to be efficient for both relays and sync servers.

    Key features of Beelay:

    • Statelessness: Application-level requests are stateless and run over TLS or mTLS, allowing for easy horizontal scaling.
    • E2EE Content: Relays can store and send diffs to authorized clients, but they cannot read the E2EE content.
    • Identity Agnostic: The sync system does not require identities. Access is granted by proving the ability to invoke a capability. If a requester can invoke a capability, the receiver can calculate what data the requester is authorized to pull or edit.
    • Transport Agnostic: While HTTP transports expose IP addresses, the model supports P2P, sync servers, and other methods as long as patches eventually reach their destination.

  8. Handling Loose Commits in a Sedimentree

    main

    Loose commits are commits that do not yet belong to a defined stratum because they lack a child that serves as a stratum boundary.

    To manage loose commits:

    1. Storage: They must be stored and transmitted as individual commits.
    2. Support Verification: To allow a loose commit to be discarded once a covering stratum is received, you must retain all commits that link the original commit back to its parent stratum boundaries.

  9. How BeeKEM handles concurrent updates and membership changes

    main

    BeeKEM manages concurrency by assuming causal delivery of operations. When operations are not causally ordered (concurrent), BeeKEM uses specific merge strategies to ensure all peers converge to the same tree structure.

    Merging Concurrent Path Changes (Updates)

    When applying a path change from another member that was created concurrently:

    1. Validate the path: A path is valid only if the originating member is at the same leaf index and the path length matches. If the tree structure changed (e.g., a concurrent add reshuffled leaves), the path is invalid.
    2. Invalid Path Handling: If invalid, only update the leaf's public key by merging it with the existing one. The rest of the path is blanked.
    3. Valid Path Handling:
      • At the leaf: Merge the new public key with the existing one. If the existing key was in the "removed keys" list, it is substituted. Otherwise, both are kept as conflict keys.
      • At inner nodes: Merge the new secret store's versions into the existing one. Remove versions whose public keys are in the "removed keys" list and append new versions. If the node was blank, insert the new store.
    4. Root State: If the root has a single version, record the new encrypter. If the root has multiple conflicting versions, clear the encrypter. A tree with conflicts has no valid root key until a fresh update is performed.

    Merging Concurrent Membership Changes (Adds/Removes)

    If a batch of concurrent operations includes an add or remove:

    1. Apply all operations in the batch.
    2. Cleanup Step:
      • Re-blank removed members' paths: Ensures that concurrent updates from other members didn't accidentally write data back onto a path belonging to a removed member.
      • Sort and re-add concurrent leaves: If multiple members added leaves concurrently, they might target the same position. Pull these leaves out, sort them deterministically by identity, and re-insert them in order to ensure structural convergence.

    Causal Ordering and Epochs

    Operations form a Directed Acyclic Graph (DAG) where each operation records its causal predecessors. When concurrency exists (multiple heads), BeeKEM:

    1. Topologically sorts operations.
    2. Groups them into epochs (sets of mutually concurrent operations).
    3. Applies epochs in causal order.
    4. If concurrency is too complex to merge incrementally (e.g., after a membership change), the entire tree is replayed from scratch by re-applying all topologically sorted operations in epoch order.

  10. Sedimentree Terminology and Data Model

    main

    When working with or implementing Sedimentree, use the following terminology to describe the data structure components:

    • Commit: An abstract node in the Directed Acyclic Graph (DAG) containing a payload, a hash, and a set of parent hashes.
    • Stratum: A compressed range of commits. Each stratum is defined by a start hash, an end hash, and zero or more interior checkpoint hashes.
    • Loose Commit: A commit that is stored outside of any defined stratum.
    • Blob: A content-addressed binary array used to store the payloads of both strata and loose commits, separating payload data from metadata.
    • Level: A property of a stratum indicating its depth in the tree. The first level of strata is level 1. Higher levels represent larger ranges of the commit graph that 'support' the strata above them.
    • Minimal Sedimentree: A simplified version of a sedimentree where all strata or loose commits that are already supported by strata below them have been recursively removed.

  11. Handle Cycles in Group Delegations

    main

    Group delegations form a directed graph. This graph MAY contain cycles.

    A common pattern is Co-delegation, where two different groups (e.g., BigCo and Ink & Switch) delegate full control to each other. While they maintain separate memberships, they effectively function as a single unified group for authority purposes because of this mutual delegation.

  12. Manage group membership via Stateful Agents

    main

    Keyhive maintains groups with mutable membership using an operation-based CRDT.

    In a Stateful Agent (Group), membership changes (additions and removals) are recorded as operations. The operations that constitute the state's history must begin at the Stateful Agent's public key.

    Key behaviors:

    • Authority: Once a Stateful Agent grants control to another Agent, the original Stateful Agent MAY delete its secret key.
    • Membership by Parenthood: To establish a hierarchy, a creator can include an operation in the initialization of a new Agent that adds the creator to the new Agent's membership list.