ZK in agents: results, limits and open problems

Read the case study’s evidence the way a careful engineer should: separate what is proven from what is only tested and what is only measured, attribute every benchmark to the prototype under its conditions, catalogue the honest negative properties and limitations, and identify the open problems that remain — so the results are never mistaken for universal properties of zero-knowledge systems.

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

The single most important thing to carry out of this case study is how to read its claims. The paper is explicit that it gives mechanisms and TESTS rather than proofs: for each property, the test suite constructs the violating input and asserts rejection. There are no theorems of correctness. So “the property holds” here means “a test constructs a violation and the system rejects it,” not “there is a formal proof.” Keep three categories separate.

(a) Proven — formally

Nothing in this work is offered as a formal theorem. The paper deliberately substitutes a test suite for proofs and says so. Treat any “proven” claim about it as a category error.

(b) Tested

Correctness properties (no hop widens authority; no reuse of another party’s chain; a note is accepted at most once) are established by ~46 tests across seven suites, including dedicated invariant tests that build a widening hop, a tampered signature, an expired credential, a substituted credential, and assert rejection. Strong evidence, bounded by the cases the suite constructs.

(c) Measured / experimental

Every size, time, gas and throughput figure is a measurement of the PROTOTYPE under stated conditions. Some measurements are of a FRAGMENT of the check (the hash-based and folding adapters), and messaging/transparency figures are synthetic — they characterize cryptographic and structural cost, not the behaviour of a live multi-organization deployment.

The figures were taken on a single host that was deliberately NOT idle: it ran other container stacks under realistic concurrent load, which the paper treats as the normal condition rather than an accident. Load sensitivity was measured at a factor of about 2.1, so every figure should be read as best-effort under load and pessimistic by roughly a factor of two — not best-case in isolation. A reader benchmarking on a quiesced machine should expect better numbers, and that gap is the point: the paper reports the pessimistic case on purpose.

Representative prototype figures (all attributed to the prototype, under load): a pairing-based proof is a small constant size (hundreds of bytes to ~2 kB) with verification flat at single-digit milliseconds regardless of depth, while a transparent baseline grows with depth and discloses the whole witness; generation time is where backends separate (one pairing-based system stays tens of milliseconds, another rises into hundreds to thousands as depth grows, the price of a universal ceremony). The reception gate reports accepting a few thousand notes per second and rejecting faster, because rejection short-circuits at the root/authority check before signature verification.

The paper tabulates seven properties with their status and states plainly which do not hold. This candour is the model to imitate.

• ▸P1 No hop widens authority — holds (tested on both lanes).
• ▸P2 No reuse of another party’s chain — holds (tested).
• ▸P3 A note is accepted at most once — holds, AFTER a correction; the deduplication had to be reformulated as a uniqueness-constrained insertion to be correct under concurrency.
• ▸P4 The chain topology stays hidden — holds only PARTLY: a per-depth circuit family leaks the chain depth through which verification key is used. Padding to a maximum depth restores it at a cost, or a folding scheme with a single key removes the leak.
• ▸P5 A proof reflects current validity — NO: the circuit’s public signals carry no instant, so a proof keeps verifying after the credential has expired or been revoked. It attests that an authorization of that shape once existed, not that it still holds.
• ▸P6 Revocation applies on the proof lane — NO: the revocation check ranges over the chain, which a verifier holding only a proof cannot see; restoring it needs a non-membership argument against an accumulator.
• ▸P7 A proof binds the stored credentials — NO, by construction of the curve translation: the proof preserves depth, attenuation pattern and authorized action, but nothing commits to the digests of the specific stored credentials.

The paper measures its own cleartext chain validation against two widely used alternatives (one signs append-only blocks with public keys and evaluates a policy language; one chains message authentication codes). On the same host and harness, its lane is the SLOWEST and LARGEST of the three — a few times slower than one alternative, more than an order of magnitude slower than the other, with credentials that grow with depth.

The conclusion it draws is NOT that its lane should be faster. The gap is structural: its lane performs one independent public-key signature per hop and serializes the chain in a canonical textual encoding; the MAC-based alternative does only symmetric authentication, but its verifier must hold the root secret — so every party able to check is able to mint, which forecloses non-repudiation to a third party. The honest reading: a deployment that needs neither disclosure control nor cross-organizational verification should use a cheaper alternative. The measured cost is what the extra guarantees are priced at.

Three runtime defects were found not by testing and not by code review, but by trying to state the replay property precisely enough to tabulate it. Each had survived review and a passing test suite, and each surfaced the moment the authors tried to write down exactly what the system guarantees. This is a methodological finding the paper foregrounds: specification is a distinct verification activity from testing.

• ▸The guard failed open — when its store was unavailable the deduplication guard silently fell back to process-local memory and processed the message with no deduplication; it now fails closed and emits a counter.
• ▸The retention relation was not enforced — the seen-set retention must exceed the freshness window plus clock skew; it was a hard-coded constant against a caller-supplied bound. The service now refuses to start unless the relation holds, and caps the caller-supplied bound.
• ▸Background writes could vanish — audit and event writes were dispatched as detached tasks with no retained reference, so the runtime could reclaim one before it completed; references are now held with a completion callback.

The paper distills five transferable lessons, three of them negative and one overturning an assumption the authors did not know they held. None was visible from the construction alone; all five came from running the system and writing the result down.

L1 — what a per-depth circuit family discloses

An abstraction can be leak-free at the level it names and leaky at the level below: the interface hides the witness, but the SELECTION of a verification key is observable outside the interface’s vocabulary (this is P4). When a component is parameterized by a property of the data, that parameter becomes part of the interface whether or not it is declared.

L2 — two guarantees that do not compose

Revocation ranges over the witness, so any lane that hides the witness loses revocation (P6). The intuition that a zero-knowledge lane strictly dominates a cleartext one is wrong; in a two-lane design, each lane’s guarantee set must be enumerated and compared explicitly.

L3 — structure is not validity

A proof of this form keeps verifying after the credential expires or is revoked (P5), a direct consequence of what the circuit’s public signals do and do not contain. It became visible only when the reception path grew freshness and replay checks and the count of conditions on the two lanes diverged.

L4 — accept if and only if provable

Of three scope-expressiveness levels implemented, only the simplest is enforced; excluding the richer two was a reasoned decision, because without matching circuit components the enforcement lane would accept patterns the proof lane could not demonstrate. A transferable principle for any system with both a cleartext path and a proof path — with a real cost in expressiveness foregone.

L5 — expressiveness does not order cost

Cost was expected to follow expressiveness; it did not. A measured intermediate scope level cost more than an order of magnitude above the simplest and many times the level above it, because cost follows the DECISION PROCEDURE, not the position in an expressiveness ordering. Found by measurement contradicting the assumption.

Beyond the negative properties, the paper names limitations that remain open rather than claiming to have closed them.

• ▸Clock dependence — the freshness condition is two-sided, so clock skew between independent organizations consumes the acceptance window and produces legitimate rejections indistinguishable from attack; synchronization becomes part of the security model.
• ▸Audit durability — persistence of the audit record is best-effort and drops events precisely under peak load, the regime one most wants recorded; a drop counter is the minimum and a durable outbox the correct answer, neither yet implemented.
• ▸Evaluation scale — ALL figures were obtained on a bench. Validation under the intended conditions (several independent organizations, each running an agent population continuously for days over a shared backbone, with frontier models deciding and delegating) has NOT been performed.
• ▸Two adapters prove only a fragment — the hash-based and folding backends leave in-circuit signature verification out, so they do not yet prove the full check; making all backends prove the same relation is open work.
• ▸A cross-commitment to close P7, circuit components for richer scope levels, and a reconciliation of two different anti-equivocation mechanisms all remain future work.
• ▸No specification and no public source at time of writing — the cleartext layer is specifiable, but the circuit is not on the same terms (two implementations that both “produce a proof” do not interoperate unless their constraint systems agree constraint by constraint), and a responsible specification would need conformance vectors and a second independent implementation that do not yet exist.

Expected direction: Something like: “The prototype in the reference paper REPORTS (measured, under load) small constant-size proofs on the order of hundreds of bytes to a couple of kilobytes for its pairing-based backends, with verification roughly flat in depth. These are prototype measurements, not universal ZK properties, and nothing is formally proven — correctness is established by tests. The proof lane does NOT support revocation (P6) and does NOT reflect current validity (P5): a proof can keep verifying after expiry or revocation, and it does not even bind the specific stored credentials (P7).”

In what sense does a property “hold” in this paper, and in what sense does it not?

It holds in that a test suite constructs the violating input and the system rejects it; it does not hold in the sense of a formal theorem — the paper explicitly gives mechanisms and tests rather than proofs.

Why should the reported performance numbers be read as pessimistic, and may they be cited as ZK properties in general?

They were measured on a non-idle host under realistic load (sensitivity ~2.1x), so a quiesced machine would do better; and no — they are properties of this prototype/circuit under these conditions, never of all ZK systems.

Name two properties the paper admits do NOT hold on the proof lane, and the architectural reason their consequence is bounded.

P5 (a proof reflects current validity) and P6 (revocation applies on the proof lane) — also P7 (a proof binds stored credentials). Their consequence is bounded because no enforcement decision is ever taken on the proof lane, so the system never accepts what it cannot check.

What was the methodological lesson behind the three defects found while writing?

Specification is a distinct verification activity from testing: each defect had survived code review and a passing test suite and only surfaced when the authors tried to state precisely what the system guarantees.