- authenticated data structure that represents a path in a graph as a balanced or biased binary tree of hash digests
- internal nodes store hashes of concatenated sub-paths
- enables logarithmic-size cryptographic proofs for graph properties: connectivity, distance, type queries
- core building block of authenticated_graphs
- how it works
- given a path
v₀ → v₁ → ... → vₖ in a graph
- build a binary tree over the path edges
- each leaf is the hash of an edge label or vertex attribute
- each internal node is
H(left_child || right_child)
- the root digest commits to the entire path
- to prove a sub-path or property, reveal the sibling hashes along the tree (logarithmic in path length)
- comparison with Merkle trees
- Merkle trees authenticate sets or sequences of data
- hash path accumulators authenticate paths in graphs specifically
- both use binary tree structure with hash nodes
- hash path accumulators are optimized for path queries (connectivity, reachability, shortest path)
- role in folding and incrementally verifiable computation
- accumulators serve as the “running digest” in folding schemes
- in Nova and related schemes, the accumulator absorbs each new proof instance without fully verifying it
- the final accumulated value is then checked once via a single decider proof
- this is what makes IVC efficient: fold instead of verify at each step
- dynamic variants
- dynamic authenticated forests support link/cut operations with
O(log n) proofs and O(n) space
- paths are partitioned into solid and dashed segments whose accumulators are linked
- enables real-time updates as the cybergraph evolves
- applications in cyber
- cybergraph path verification: prove that two particles are connected through a specific chain of cyberlinks without transmitting the full path
- authenticated_graphs with fractional cascading: hash path accumulators form the per-shard layer, with fractional cascading overlay for cross-shard queries
- focus proof infrastructure: every random-walk step in the relevance machine publishes its proof against the attention root, enabling anyone to recompute focus
- light client verification: neurons verify shard integrity with logarithmic bandwidth using path proofs
- negative proofs: prove that a forbidden relationship is absent via authenticated complement paths
- zero-knowledge friendly variants
- when using hash functions like Poseidon, the accumulator tree can be verified inside a ZK circuit efficiently
- each hash costs ~300 constraints vs ~1 constraint per field operation
- this is why hash function choice (see ADR-001) is critical for accumulator performance in proof systems
- related