Knowledge Base

Browse the concepts behind Truestamp. Follow the links between concepts, or search across everything.

Angela: A Sparse, Distributed, and Highly Concurrent Merkle Tree

UC Berkeley CS262a project report on Angela, a sparse distributed Merkle tree with fine-grained conflict-node locking for concurrent batched updates, built on Ray and Amazon Aurora, achieving 2x over Trillian.

Open resource

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 from the epoch hashes it writes to Stellar and Bitcoin 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.