- generalization of incrementally verifiable computation from sequential chains to arbitrary DAGs
- allows multiple independent computations to be combined into a single proof
- each node in the DAG carries a proof that
- all predecessor proofs are valid
- the local computation at this node is correct
- where incrementally verifiable computation handles a linear chain of steps, PCD handles branching and merging computation paths
- a node can have multiple parents: it absorbs and combines their proofs via folding into a shared accumulator
- enables distributed proof generation where different neurons prove different parts of the computation and results are merged
- constructions
- built on top of IVC schemes like Nova, HyperNova, Protostar
- requires a compliance predicate that defines what “valid computation” means at each node
- the compliance predicate checks predecessor proofs and the local transition function
- applications in cyber
- DAG-structured cybergraph verification: the knowledge graph is not a chain but a DAG of cyberlinks, PCD matches this topology naturally
- parallel validator proving: different validators prove different subgraphs, then merge proofs at shard boundaries
- cross-shard integrity: when a query spans multiple shards of the cybergraph, PCD combines per-shard proofs into a global certificate
- multi-agent reasoning: when multiple neurons contribute to a computation (e.g. collective ranking), PCD proves the aggregate is correct without re-executing each contribution
- authenticated_graphs with fractional cascading: PCD enables composition of proofs across the shard hierarchy described in authenticated_graphs
- properties
- succinctness: final proof is small regardless of the DAG size
- parallelism: independent branches can be proved concurrently
- composability: any subtree of proofs can be verified independently
- generality: subsumes incrementally verifiable computation as the special case of a single-path DAG
- related