Knowledge Base

Overview

“Angela: A Sparse, Distributed, and Highly Concurrent Merkle Tree” is a 2018 UC Berkeley CS262a graduate systems project report by Janakirama Kalidhindi, Alex Kazorian, Aneesh Khera, and Cibi Pari. It addresses a hard problem in authenticated data structures: because a parent node’s hash depends on its children, updates to a Merkle tree normally must be serialized, so the standard approach (Google’s Trillian, used by Google Key Transparency) locks the entire tree per update. Angela is a sparse Merkle tree that supports concurrent batched updates via fine-grained locking on only the conflict nodes between updates, and distributes the tree across a cluster. The authors report roughly a 2x speedup over the naive serial approach and demonstrate that the distributed design scales with cluster size.

Key points

• Motivation: Google Key Transparency uses Trillian, a sparse Merkle tree that pairs a user identifier leaf with a public key value; each update locks the whole tree and serializes, which becomes a bottleneck at the billion-leaf scale the project targets.
• Sparse design: the tree has 2^256 leaves, most of them empty; empty subtrees get a constant precomputed hash per level (base case is the hash of the empty string), so hashes of empty regions are computed lazily. Nodes are prefix-encoded (append 0 going left, 1 going right), assuming IDs are pre-mapped by a verifiable random function as in CONIKS.
• Core insight, conflict nodes: for a leaf, the only contended point between two concurrent updates is their conflict node, the deepest common ancestor (longest common prefix). For N batched updates there are exactly N-1 conflict nodes; locking is needed only at those points, reducing lock surface area from the whole tree to linear in the number of updates.
• Finding conflicts requires sorting the batch by encoding first; conflict search on adjacent (pairwise-sorted) leaves yields the unique closest conflict points, avoiding missed conflicts that naive pairwise comparison would produce. Updates percolate concurrently; when two update paths meet at a visited parent, one thread returns early and lets the other continue, keeping contention small.
• Systems build: updates are batched into epochs, publishing a new signed root per epoch. The Python orchestrator uses Ray (UC Berkeley RISELab) for distribution and load balancing across Amazon EC2; stateless Go worker nodes each own a virtually-addressed subtree; Amazon Aurora (MySQL-compatible) is the storage layer, with an epoch-versioned nodes table keyed on (nodeId, epochNumber). Go is bridged to Ray’s Python API through cgo C extensions. Merkle updates are idempotent, so recovery is redo-without-undo.
• Results and caveats: on a MacBook Pro (2.2GHz Core i7, 16GB) the concurrent BatchInsert beat naive serial insertion by about 2x, expected to improve with more cores. It is a course project constrained by a $300 AWS budget; challenges included the Python GIL (forcing the move off pure Python through Cython to Go) and early-stage Ray (release 0.6.0).

Relevance to Truestamp

Angela is directly relevant to how Truestamp scales Merkle-based proofs: it tackles concurrency in the same RFC 6962-style hash-tree model that underpins Truestamp’s inclusion proofs, where a leaf’s existence is verified against a published root. Its sparse-tree and key-transparency lineage (CONIKS, Trillian) informs the design space for high-throughput verifiable logs. Truestamp’s own tamper evidence over time comes from its block hash chain and external commitments rather than from consistency proofs, so the append-only machinery of a transparency log has no counterpart here.

Citations

1. Angela: A Sparse, Distributed, and Highly Concurrent Merkle Tree. Janakirama Kalidhindi, Alex Kazorian, Aneesh Khera, Cibi Pari; UC Berkeley CS262a project report, Fall 2018.