ZK in agents: architecture & algorithms, step by step

Work through every major component, data structure and algorithm of the delegation layer in detail — the credential and chain structures, the five-check validation, the ten-check reception gate, the delegation circuit’s formal statement and constraints, the curve translation, the proving-system adapter interface, and the concurrency-safe replay guard — and trace a complete three-hop delegation end to end.

Track

Research

Module

5 · Research case studies

Prerequisites

ZK in agents: credentials, chains and the delegation circuit · ZK in agents: verification, integration and fail-closed reception · Digital signatures

The system has five strata, and the value of the design is largely in how strictly they are separated. From the bottom: a best-effort infrastructure layer (append-only store, one-way audit bus, key store, telemetry); a separable cryptographic engine (the delegation model, scope language, revocation, messaging/reception, transparency, composition, and a proving-system abstraction behind which the adapters sit); a set of attesting agents (authority, prover, verifier, witness, relayer) that inherit the host’s agent machinery but decide nothing in any application domain; an integration layer that wires the engine into the host runtime (court judge, store, event producer/consumer, key custody); and the entry points (a service surface, direct runtime invocation, and the host’s policy court).

The single most load-bearing boundary is that the engine does NOT import the runtime — the dependency is one-way and optional — which is what makes the artefact independently publishable and independently measurable. The paper checks this separability as an invariant, not as a convention.

A delegation hop is the atomic unit. A chain is an ordered list of hops. A note is what actually travels on the wire at reception time: a signed payload plus the chain that authorizes its sender. The digest is the hash that binds a child hop to its parent.

didactic data model (synthetic)
Hop := {
  issuer   : PublicKey,     // who delegates
  subject  : PublicKey,     // who receives
  scope    : ScopeMask,     // set of permitted action TYPES (a bitmask / pattern set)
  parent   : Digest | GENESIS,  // hash of the parent hop, or genesis marker for hop 0
  expiry   : Instant | NONE,
  sig      : Signature      // issuer's signature over encode(hop \ sig)
}

digest(h : Hop) : Digest := H( canonical_encode(h without h.sig) )
// NOTE: the signature is NOT part of the digest; the next hop links to this digest.

Chain := [ Hop_0, Hop_1, ..., Hop_{d-1} ]   // root = Hop_0.issuer, leaf = Hop_{d-1}.subject, depth = d

Note := {
  topic    : TopicId,       // a topic fixes a trusted root + a required action
  payload  : Bytes,
  ts       : Instant,
  psig     : Signature,     // payload signer == chain's leaf subject
  chain    : Chain
}

Validation walks root-to-leaf and stops at the first failure, returning a typed reason. The five checks are V1 continuity of identity, V2 continuity of linkage, V3 authenticity, V4 freshness, V5 attenuation.

validate_chain (didactic pseudocode)
validate_chain(C : Chain, now : Instant) -> OK | Reject(reason):
  for i in 0 .. len(C)-1:
    h = C[i]
    if i == 0:
      if h.parent != GENESIS:        return Reject(BAD_GENESIS)
    else:
      prev = C[i-1]
      if h.issuer  != prev.subject:  return Reject(V1_IDENTITY_BREAK)   # V1
      if h.parent  != digest(prev):  return Reject(V2_LINK_BREAK)       # V2
    if not verify(h.issuer, encode(h\sig), h.sig):  return Reject(V3_BAD_SIG)   # V3
    if h.expiry != NONE and now > h.expiry:         return Reject(V4_EXPIRED)   # V4
    if i > 0 and not subset(h.scope, C[i-1].scope):  return Reject(V5_WIDENS)    # V5
  return OK

# Authorization contract over a VALID chain, given expected root R and action a:
authorize(C, R, a, now):
  return validate_chain(C, now) == OK
     and C[0].issuer == R                      # root is the expected authority
     and member(a, leaf_scope(C))              # required action is within leaf scope

The contract of the whole system is exactly those seven conditions: V1–V5 per hop, plus root-is-expected-authority and action-in-leaf-scope over the complete chain. Everything else in the architecture enforces this, proves it, or measures the cost of proving it.

Enforcement operates on notes, not bare chains, and is closed by default. A message is processed if and only if all ten checks pass, in order, with no bypass. The ordering matters for performance: cheap, discriminating checks come first so that rejection short-circuits before the expensive signature work.

accept_note (didactic pseudocode)
accept_note(n : Note, topic : TopicConfig, now : Instant) -> PROCESS | DROP(reason):
  if n is absent:                              return DROP(A1_NO_NOTE)       # A1
  if n.topic != topic.id:                      return DROP(A2_WRONG_TOPIC)   # A2
  if not verify(leaf_subject(n.chain), n.payload, n.psig):
                                               return DROP(A3_BAD_PAYLOAD_SIG) # A3
  if n.chain[0].issuer != topic.trusted_root:  return DROP(A4_WRONG_ROOT)    # A4
  if signer(n.psig) != leaf_subject(n.chain):  return DROP(A5_SIGNER_MISMATCH) # A5
  if validate_chain(n.chain, now) != OK:       return DROP(A6_CHAIN_INVALID) # A6
  if not member(topic.required_action, leaf_scope(n.chain)):
                                               return DROP(A7_OUT_OF_SCOPE)  # A7
  if any_revoked(n.chain):                      return DROP(A8_REVOKED)       # A8
  if now - n.ts > topic.freshness_window:       return DROP(A9_STALE)         # A9
  if not seen_set.insert_unique(digest(n.payload)):   # A10 (see replay guard)
                                               return DROP(A10_REPLAY)
  return PROCESS

# Enforcement invariant: PROCESS  <=>  (A1 AND A2 AND ... AND A10). No alternate path.

The circuit proves “a valid chain of some depth, rooted at this authority, exists whose leaf scope covers this action” while revealing only the statement. Below, R(·) denotes the relation “this witness is a valid chain for this statement.”

statement / witness / proved relation (didactic)
Public statement  x := ( root_key_coords (ρx, ρy) on a circuit-friendly curve,
                          action_mask μA )
Private witness   w := for each hop i:  ( issuer_i, subject_i : curve coords,
                                          scope_mask μi,
                                          sig_i : three components )

Proved:  ∃ w of depth d  such that  R( x, w ) = 1

R(x,w)=1  iff  the five constraints below hold for all hops and the leaf.

Five constraints are imposed — four at every hop, and a fifth at the leaf. The attenuation constraint is the one worth writing out, because it turns “child scope is contained in parent scope” into arithmetic a circuit can enforce.

the five constraints (didactic)
# (1) ATTENUATION, per hop i>0 — bitwise containment μi ⊆ μ(i-1):
#     for every bit position j, a bit set in the child must be set in the parent.
∀ j :  bits(μi)[j] · ( 1 - bits(μ(i-1))[j] ) = 0     # == 0 forbids "set in child, unset in parent"

# (2) LINKAGE, per hop:   circuit_friendly_hash(hop_{i-1}) == parent_link_i   (signal equality)
# (3) CONTINUITY, per hop: subject_{i-1} == issuer_i                          (signal equality)
# (4) SIGNATURE, per hop:  in_circuit_verify(issuer_i, encode(hop_i), sig_i) == true   # cost-dominant
# (5) LEAF:                μA ⊆ μ_{d-1}                                        # same bit relation as (1)

Cost is dominated by in-circuit signature verification. The paper reports approximately 9.15×10³ constraints per hop — e.g. about 18,302 at depth 2 and 27,453 at depth 3 — a measured figure for THIS circuit on THIS curve, not a property of zero-knowledge in general.

There is a subtlety that creates an honest limitation. In-circuit signature verification is only affordable on a particular circuit-friendly curve, but the agents sign credentials with a scheme that is prohibitively expensive to verify in-circuit. So the circuit operates on a TRANSLATED representation.

what translation preserves and drops (didactic)
translate( real_chain )  ->  circuit_chain
  preserves:  depth
              attenuation pattern (the ⊆ relation among scope masks)
              authorized action
  does NOT bind: the digests / identity of the SPECIFIC stored credentials

# Therefore (property P7, FAILS by construction):
#   a verifying proof attests  "an authorization of THIS SHAPE existed"
#   it does NOT attest         "these exact stored credentials are the ones behind it"

Requirement R6 (substitutable cryptography) is met by an interface, not a commitment to one system. Every adapter implements three operations over a statement and witness, and — crucially — DECLARES five properties of itself. Nothing in the system resolves an adapter by type; resolution is by name through a registry, so swapping a backend is a code change, never a type change.

adapter interface + declared-property vector (didactic)
interface ProofAdapter:
  setup(circuit)           -> params            # may require a trusted ceremony
  prove(params, x, w)      -> proof             # x public, w private
  verify(params, x, proof) -> bool              # MUST return false on bad input, never throw

  # declared, load-bearing — the registry and callers read these:
  declares: { zero_knowledge: bool,
              succinct:       bool,
              needs_ceremony: bool,
              quantum_resist: bool,
              recursive:      bool,
              proves:         FULL_CHECK | FRAGMENT }   # <-- honesty flag

# Prototype adapters (prototype-reported):
#   transparent : reveals witness; baseline, not a competitor; proves FULL_CHECK in the clear
#   groth16     : succinct, per-circuit ceremony, ZK;   proves FULL_CHECK (with in-circuit signatures)
#   plonk       : succinct, universal ceremony, ZK;     proves FULL_CHECK (with in-circuit signatures)
#   stark       : no ceremony, quantum-resistant;       proves FRAGMENT (attenuation + linkage only)
#   nova        : folding, constant size;               proves FRAGMENT (attenuation + linkage only)

Check A10 is the only acceptance step that mutates shared state, and it sits on the critical path of every accepted message. Done naively as check-then-write, it is wrong under concurrency.

wrong vs correct replay guard (didactic)
# WRONG (check-then-write) — admits an interleaving where two copies both proceed:
if digest not in seen_set:        # both threads observe "absent"
    seen_set.add(digest)          # both add; both ACCEPT the same message
    return ACCEPT
return REPLAY

# CORRECT — make the uniqueness constraint itself the detector (atomic):
inserted = seen_set.insert_unique(digest)   # single atomic op; violation == duplicate
return ACCEPT if inserted else REPLAY

# Two companion invariants:
#  (a) retention(seen_set) > freshness_window + clock_skew   # checked at startup; refuse to start otherwise
#  (b) if store unreachable: FAIL CLOSED (reject) — never fall back to process-local memory,
#      because a local set loses the AT-MOST-ONCE property, not just durability.

Replication sharpens the point. Verification is a pure function and replicates with no coordination; the replay guard cannot, because its correctness depends on a single logical seen-set. Replicas must share the store. The paper reports that an earlier implementation silently degraded to local memory when its store was unreachable — a bug found while writing — and now fails closed.

Non-repudiation of individual artefacts does not stop a registry from showing two different histories to two different auditors. The transparency mechanism separates three properties onto three mechanisms, which is the lesson to carry: do not expect one mechanism to deliver attribution, privacy and consistency at once.

equivocation detection (didactic)
# Registry publishes a chain of epoch roots:   root_0 -> root_1 -> root_2 -> ...
# Independent witnesses observe and SIGN the root they see each epoch.
# Equivocation (two histories) is detectable iff two witnesses sit on different branches:
detect_split_view(signed_roots_per_witness, epoch):
    views = { w.view(epoch) for w in witnesses }
    return DIVERGENCE if |distinct(views)| > 1 else CONSISTENT

# Three mechanisms, three properties:
#   signatures  -> attribution (who)
#   circuit     -> disclosure-free demonstration (prove without revealing)
#   epoch roots -> consistency of the record over time (no undetected two histories)

Synthetic scenario. Organization A (root) delegates to contractor B, B sub-delegates to worker W, and W publishes a message on a topic whose trusted root is A and whose required action is "report:write". Scopes are sets of action types; each hop narrows.

the chain (synthetic)
Hop_0: issuer=A, subject=B, scope={report:*, vault:read}, parent=GENESIS,         expiry=T1, sig=sigA
Hop_1: issuer=B, subject=W, scope={report:write, report:read}, parent=digest(Hop_0), expiry=T2, sig=sigB
# leaf = W ; leaf_scope = {report:write, report:read} ; depth = 2 hops

Note: topic=audit-feed, payload=<the report bytes>, ts=now, psig=sign(W, payload), chain=[Hop_0,Hop_1]
TopicConfig(audit-feed): trusted_root=A, required_action=report:write, freshness_window=30s

reception trace (synthetic)
accept_note(Note, TopicConfig(audit-feed), now):
  A1 note present                              -> ok
  A2 topic == audit-feed                       -> ok
  A3 verify(W, payload, psig)                   -> ok
  A4 chain[0].issuer == A (trusted root)        -> ok
  A5 signer(psig) == leaf subject W             -> ok
  A6 validate_chain:
       V1 Hop_1.issuer(B) == Hop_0.subject(B)   -> ok
       V2 Hop_1.parent == digest(Hop_0)         -> ok
       V3 verify sigA, sigB                      -> ok
       V4 now < T1, now < T2                     -> ok
       V5 {report:write,report:read} ⊆ {report:*,vault:read} -> ok
  A7 report:write ∈ leaf_scope                  -> ok
  A8 no hop revoked                             -> ok
  A9 now - ts <= 30s                            -> ok
  A10 seen_set.insert_unique(digest(payload))   -> inserted
  => PROCESS

Now two instructive failures. (1) If B had tried to grant W the scope {report:write, vault:write}, V5 fails at Hop_1 because vault:write is not in B’s scope — attenuation is enforced per hop, so B cannot widen beyond what A granted, even if B’s deciding component was manipulated into trying. (2) If an attacker replays the exact note a second time, A1–A9 pass again but A10’s unique insertion fails, so the duplicate is dropped — at-most-once holds. And separately: a zero-knowledge PROOF of this same chain would attest that an authorization of this shape, rooted at A, covering report:write, existed — but (P5) would keep verifying after T2, (P7) would not bind these exact credential digests, and (P4) could leak that the chain had depth 2 through the choice of verification key.

Expected direction: Moving signature verification first forces the expensive public-key operation on every message, including ones that would be rejected almost for free by topic/root checks. The case study reports rejection being faster than acceptance precisely because rejection short-circuits at the cheap authority/topic checks before signature work; reordering A3 to the front removes that short-circuit, so a flood of wrong-topic/wrong-root messages now each pays a signature verification, collapsing rejection throughput toward (or below) acceptance throughput and handing an attacker a cheap amplification.

Why is the hop signature excluded from the digest that the next hop links to?

Because the digest must bind the hop’s content (issuer, subject, scope, parent, expiry) for linkage, while the signature is over that content; linking to the canonical encoding minus the signature gives a stable parent reference and lets V3 verify the signature separately.

Write the attenuation constraint in words and say what it forbids.

For every bit position, bits(child_scope)[j] · (1 - bits(parent_scope)[j]) = 0; it forbids any bit being set in the child scope while unset in the parent, i.e. it arithmetically enforces child_scope ⊆ parent_scope at every hop.

Why must verify() return false on bad input rather than throw, as an interface rule?

So rejection is an ordinary value on the enforcement path (fail-closed, auditable) rather than an exception that could crash, be swallowed, or be routed around — a thrown error is a bypass risk; a false is a decision.

Give one reason the replay guard cannot be replicated the way verification can.

Verification is a pure function of the artefact and public parameters, so replicas need no coordination; the replay guard’s at-most-once property depends on a single logical seen-set, so replicas must share the store or two of them can each accept the same message.