Formal Cryptographic Protocol for Agent Identity (KYA)

Research Direction Analysis

1. Problem Formalization

a16z's "Know Your Agent" (KYA) concept identifies a critical gap: as AI agents transact autonomously across platforms, there is no standardized, cryptographically rigorous way to establish who an agent is, who authorized it, and what it's allowed to do. KYC solves this for humans with documents and biometrics. Agents have neither. We need a formal protocol.

A KYA protocol must satisfy the following properties:

  • Unforgeability. No entity should be able to fabricate a valid agent credential without the cooperation of a legitimate issuer (the principal or a delegating authority). This must hold even if an adversary compromises other agents in the system. Formally: existential unforgeability under chosen-message attack (EUF-CMA) for the underlying signature scheme.

  • Selective Disclosure / Privacy. An agent proving it has authorization to spend ≤$100 should not need to reveal its owner's identity, total budget, or other credentials. The protocol must support zero-knowledge proofs over credential attributes. Unlinkability is also desirable: two verifiers should not be able to collude to determine that the same agent interacted with both.

  • Revocability. A principal must be able to revoke an agent's credentials in near-real-time. This is non-trivial in decentralized settings — revocation must be checkable without contacting the issuer. Accumulators (RSA or bilinear) or on-chain revocation registries are candidate approaches.

  • Delegation. Agents spawn sub-agents. A credential system must support delegation chains of bounded depth, where each link attenuates permissions (never amplifies). The chain must be verifiable end-to-end without revealing intermediate agents.

  • Composability. KYA credentials must compose with payment protocols, access control systems, and reputation frameworks. The protocol should be modular — a credential proving "authorized by human X" should be combinable with a separate credential proving "reputation ≥ Z" in a single composite proof.

2. Existing Building Blocks

Several cryptographic and standards-track primitives are directly relevant:

Anonymous Credentials. Camenisch-Lysyanskaya (CL) signatures and BBS+ signatures enable a credential holder to selectively disclose attributes and produce unlinkable presentations. BBS+ is particularly attractive: it supports efficient multi-message signing, selective disclosure, and proof of knowledge, all over pairing-friendly curves. The recent IETF draft for BBS+ (draft-irtf-cfrg-bbs-signatures) provides a path toward standardization.

W3C Verifiable Credentials (VCs) and DIDs. The VC data model provides the envelope — issuer, subject, claims, proof. Decentralized Identifiers (DIDs) provide the identifier layer, resolvable without a central registry. DID methods vary widely (did:web, did:key, did:ion, did:ethr), and the choice of method affects trust assumptions. For agents, did:key (ephemeral, self-certifying) or did:ethr (Ethereum-anchored, revocable) are natural fits.

Soul-Bound Tokens (SBTs). Weyl, Ohlhaver, and Buterin's proposal for non-transferable tokens captures the idea that certain credentials should be bound to an identity. For agents, SBTs could represent non-transferable authorization — but they lack privacy (on-chain, publicly visible) and don't support selective disclosure. They are a useful registry mechanism but insufficient as a complete credential system.

ERC-725/735. These Ethereum standards for on-chain identity and claims provide a smart-contract-based identity proxy. ERC-725 defines a key-management contract; ERC-735 adds claim attachment. These could serve as the on-chain anchor for agent identity, with off-chain ZKP-based credential presentations.

3. Proposed Construction Sketch

We propose a layered architecture:

Layer 0 — Principal Identity. A human principal holds a DID and a BBS+ signing key. The principal issues a delegation credential to an agent's DID, specifying: (a) the agent's public key, (b) a permission vector (budget caps, allowed actions, service scopes), (c) an expiration time, and (d) a revocation handle.

Layer 1 — Agent Credential. The agent holds the BBS+ credential and can derive zero-knowledge proofs over its attributes. When interacting with a service, the agent produces a proof demonstrating, e.g.:

  • "I am authorized by a principal whose DID is in the set of known-good principals" (set membership via accumulator)
  • "My spending limit is ≥ the requested amount" (range proof)
  • "My credential has not been revoked" (non-membership proof against a revocation accumulator)

All without revealing the principal's DID, the exact spending limit, or any other attribute.

Layer 2 — Verification. Verifiers check the ZKP against the issuer's public parameters and the current revocation accumulator state. Verification is stateless from the verifier's perspective — no callback to the issuer is needed, only access to a public accumulator (which can be on-chain or replicated).

Composite Proofs. Using Groth16 or Plonk-based SNARKs as a "glue layer," multiple BBS+ credential proofs can be composed into a single succinct proof. An agent could simultaneously prove authorization, budget, and reputation in one ~200-byte proof verifiable in <10ms.

4. Delegation Chains

When Agent A spawns Agent B, A issues a sub-credential to B. This sub-credential:

  • Contains a back-pointer (commitment) to A's credential
  • Attenuates permissions: B's budget ≤ A's budget, B's scope ⊆ A's scope
  • Increments a delegation depth counter, which is bounded by the principal's original credential (e.g., max depth = 3)

Verification of a delegation chain requires proving, in zero knowledge, that a valid chain of credentials exists from the presenting agent back to a legitimate principal, with monotonically non-increasing permissions at each step. This is expressible as a recursive SNARK (e.g., using Nova/SuperNova folding schemes), where each step verifies one link and accumulates the chain proof.

Accountability. While presentations are unlinkable by default, the protocol includes a tracing mechanism: the principal's credential embeds an opening that a designated auditor (or the principal themselves) can use to link a presentation back to the agent. This is analogous to the "tracing authority" in group signatures. The opening is encrypted under the auditor's public key within each proof, enabling deanonymization only with auditor cooperation.

5. Open Problems and Research Questions

  • Efficient recursive verification. Current recursive SNARKs (Nova) are promising but not yet production-ready for credential chains of depth >2. What is the concrete verification cost at depth 5? Can IVC (incrementally verifiable computation) be specialized for credential chains?

  • Cross-chain / cross-platform revocation. If an agent's credential is revoked on Ethereum, how quickly does this propagate to a verifier on Solana, or an off-chain API? Latency bounds matter for financial transactions.

  • Reputation bootstrapping. New agents have no history. How do you bootstrap reputation without inheriting the principal's reputation entirely (which creates a privacy leak)?

  • Collusion resistance. If a principal and a rogue agent collude, can they create credentials that circumvent attenuation? The delegation chain must be unforgeable even against a malicious issuer of sub-credentials.

  • Standardization surface. Which layer should be standardized first? The DID method? The credential schema? The proof system? Premature standardization risks lock-in; too-late standardization risks fragmentation.

  • Liveness vs. privacy in revocation. Non-interactive revocation checks (accumulators) sacrifice liveness. Real-time revocation checks (OCSP-like) sacrifice privacy. Is there a middle ground with bounded staleness guarantees?

6. Connection to x402/A402 Payment Protocols

The x402 protocol (HTTP 402-based machine payments) and its proposed A402 extension for agentic payments require the payer to prove authorization. Currently, this relies on API keys or wallet signatures — neither of which supports delegation, attenuation, or privacy.

A KYA credential plugs directly into the payment flow:

  1. Agent requests resource → receives 402 response with price and payment terms.
  2. Agent constructs payment proof — a composite ZKP proving: "I hold a valid, unrevoked credential from a principal; my remaining budget ≥ price; my credential authorizes this service category."
  3. Payment is authorized — the proof serves as both identity attestation and spending authorization, eliminating the need for a separate payment token or API key.

This creates a unified identity-payment layer: the credential is the wallet authorization. The principal sets a budget in the credential; every payment decrements it (tracked via a nullifier scheme to prevent double-spending without revealing the running total). The merchant verifies the proof, delivers the resource, and submits the nullifier to a public registry to prevent replay.

This tight integration between KYA and x402/A402 is arguably the most commercially valuable aspect of the research: it transforms agent identity from a compliance exercise into the core primitive enabling autonomous economic activity.

Research impact: A formal KYA protocol would be foundational infrastructure for the agentic economy — the equivalent of TLS certificates for the web, but for autonomous software agents operating with delegated human authority.