Trust Without a Central Authority: Cryptographic Identity & Verifiable Reputation in the Agentic Web

1. The Trust Gap: Why Gossip Decay Is Not Enough

In the predecessor tutorial, when our Orchestrator Ω discovered DrugInteractionAgent through three hops of gossip (GenomicsAgent had worked with it, and GenomicsAgent was discovered via the registry), we applied a simple heuristic: trust = remote_agent.trust * 0.7 per hop. After three hops, a peer starting with trust score 1.0 decays to 0.34. The orchestrator then used this scalar to weight candidate rankings during recruitment.

This approach has three fatal problems in any real-world deployment, and especially in a regulated healthcare environment like prior authorization.

Addressing these problems requires replacing the scalar trust heuristic with a layered cryptographic trust architecture. The remainder of this tutorial constructs that architecture from first principles, drawing on four bodies of research that have converged dramatically in 2024–2025: decentralized identifiers (W3C DIDs), verifiable credentials (W3C VC 2.0), zero-knowledge proofs (ZKPs), and blockchain-anchored reputation ledgers.

2. Decentralized Identifiers — Self-Sovereign Agent Identity

A Decentralized Identifier (DID) is a W3C standard (v1.0 ratified 2022; see also Verifiable Credentials v2.0, ratified May 2025) that provides a globally unique, cryptographically verifiable identifier that requires no centralized registration authority. In the context of multi-agent systems, a DID is controlled entirely by its owner: the agent itself or the organization that deploys it.

Why does this matter for our prior authorization coalition? In the predecessor tutorial, each Agent Card had an agent_id field like "agent://mednet/clinical-evidence-synth-v2". This is a human-readable label, but it is not cryptographically bound to the agent's operator. Anyone could stand up a service at that URI and claim to be ClinEvidence. A DID replaces this with a keypair-anchored identity.

{
  "@context": ["https://www.w3.org/ns/did/v1", "https://w3id.org/security/suites/ed25519-2020/v1"],
  "id": "did:web:mednet.health:agents:clin-evidence-v2",
  "verificationMethod": [{
    "id": "did:web:mednet.health:agents:clin-evidence-v2#key-1",
    "type": "Ed25519VerificationKey2020",
    "controller": "did:web:mednet.health:agents:clin-evidence-v2",
    "publicKeyMultibase": "z6MkhaXgBZDvotDkL5257faiztiGiC2QtKLGpbnnEGta2doK"
  }],
  "authentication": ["did:web:mednet.health:agents:clin-evidence-v2#key-1"],
  "service": [{
    "id": "did:web:mednet.health:agents:clin-evidence-v2#a2a",
    "type": "AgentToAgentService",
    "serviceEndpoint": "https://agents.mednet.health/clin-evidence/a2a"
  }]
}

The critical property: when Ω receives this DID Document (via registry, gossip, or direct resolution), it can issue a cryptographic challenge in the form of a random nonce and verify that the responding agent holds the private key corresponding to publicKeyMultibase. This is proof of identity, not a claim of identity. Spoofing requires possession of the private key, which is never transmitted.

2.1 DID Resolution in the Agent Discovery Pipeline

How does DID resolution integrate with the registry-based and gossip-based discovery we built in the predecessor tutorial? The modification is surgical. When the registry returns a candidate, it now returns the candidate's DID rather than (or in addition to) a plain URI. The orchestrator then resolves the DID, retrieves the DID Document, and authenticates the agent before sending any task proposals.

// Step 1: Query registry (same as before, but results include DIDs)
candidates = registry.search({
    capability: "clinical evidence synthesis",
    protocol:   "a2a/1.0",
    constraints: { hipaa: true }
})
// → [{ did: "did:web:mednet.health:agents:clin-evidence-v2",
//       match_score: 0.94, ... }]

// Step 2: Resolve the DID to get the DID Document
did_doc = did_resolver.resolve(candidate.did)
// → { verificationMethod: [...], service: [...] }

// Step 3: Authenticate — challenge-response
nonce = crypto.random_bytes(32)
challenge = { nonce: nonce, timestamp: now(), challenger: self.did }
signed_response = send_challenge(did_doc.service[0].serviceEndpoint, challenge)

// Step 4: Verify signature using the public key from the DID Document
valid = crypto.verify(
    public_key = did_doc.verificationMethod[0].publicKeyMultibase,
    message    = challenge,
    signature  = signed_response.sig
)

if not valid:
    raise AuthenticationFailure("Agent failed DID challenge-response")

// Step 5: Now proceed to negotiate (TaskProposal) — we KNOW who we're talking to

This challenge-response handshake adds a single round-trip to the recruitment flow, but it eliminates the entire class of impersonation attacks. In the gossip path, the same verification occurs: when Ω learns about DrugInteractionAgent through GenomicsAgent's peer exchange, the gossip entry now includes the DID. Ω resolves and authenticates before trusting any forwarded claim.

3. Verifiable Credentials — Attestations Without a Phone Call

DIDs solve authentication, confirming that the agent you're communicating with controls the cryptographic identity it claims. But authentication alone does not establish authorization or qualification. Knowing that you are genuinely talking to ClinEvidence does not tell you whether ClinEvidence is certified to make clinical determinations, whether its operator has signed a Business Associate Agreement (BAA), or whether its underlying model has been validated against FDA-recognized evidence standards.

This is where Verifiable Credentials (VCs) enter the architecture. The W3C published Verifiable Credentials Data Model v2.0 as a full W3C Recommendation in May 2025, marking its maturation from experimental standard to production-ready infrastructure. A VC is a digitally signed attestation made by an issuer about a subject, held by a holder, and presented to a verifier. The three-party model maps directly onto the agent trust problem.

The absence of a callback to the issuer during verification is what makes VCs suitable for runtime agent-to-agent trust. In our prior auth scenario, the orchestrator does not need to call CMS at runtime to verify that ClinEvidence is certified. It merely checks the cryptographic signature on the VC against CMS's known public key (published in CMS's own DID Document). This check is a local, sub-millisecond computation, making it viable even under tight latency budgets.

3.1 A Concrete VC for the Prior Authorization Domain

Let us construct a realistic Verifiable Credential for the ClinEvidence agent. This credential attests that ClinEvidence has been certified by a hypothetical healthcare standards body for clinical evidence synthesis in support of prior authorization decisions.

{
  "@context": [
    "https://www.w3.org/ns/credentials/v2",
    "https://w3id.org/security/data-integrity/v2",
    "https://schema.healthit.gov/agent-trust/v1"
  ],
  "type": ["VerifiableCredential", "HealthAgentCertification"],
  "issuer": "did:web:standards.healthit.gov",
  "validFrom": "2025-06-01T00:00:00Z",
  "validUntil": "2026-06-01T00:00:00Z",
  "credentialSubject": {
    "id": "did:web:mednet.health:agents:clin-evidence-v2",
    "certification": {
      "type": "ClinicalDecisionSupportAgent",
      "scope": ["evidence-synthesis", "grade-assessment"],
      "regulatoryFramework": "42 CFR § 438.210",
      "hipaaCompliance": {
        "baaOnFile": true,
        "dataPolicy": "ephemeral",
        "encryptionStandard": "AES-256-GCM"
      }
    },
    "operatingOrganization": "did:web:mednet.health",
    "modelVersion": "2.4.1",
    "lastAuditDate": "2025-04-15"
  },
  "proof": {
    "type": "DataIntegrityProof",
    "cryptosuite": "eddsa-rdfc-2022",
    "verificationMethod": "did:web:standards.healthit.gov#key-1",
    "proofPurpose": "assertionMethod",
    "proofValue": "z58DAdFfa9SkqZMVPxAQp...base58-encoded-signature"
  }
}

Several features merit close attention. The credentialSubject.id is the agent's DID, cryptographically binding the credential to the same identity we verified in Section 2. The issuer is itself a DID (did:web:standards.healthit.gov), meaning the issuer's public key can be resolved and used to verify the proof.proofValue signature. The validUntil field ensures credentials expire and force periodic re-certification, which is critical in a regulatory environment where compliance status changes. And the hipaaCompliance block encodes machine-readable attestations that an orchestrator can programmatically evaluate during recruitment.

3.2 Verifiable Presentations — Selective Disclosure at Recruitment

When ClinEvidence is recruited by Ω, it does not simply dump all of its credentials into the A2A handshake. Instead, it constructs a Verifiable Presentation (VP): a signed wrapper that bundles only the credentials relevant to the current interaction, proving that the holder is presenting their own credentials and not someone else's.

// During A2A session establishment, after DID authentication
on SessionNegotiation(orchestrator):
    // Ω sends a Presentation Request specifying what it needs to see
    request = receive(orchestrator, PresentationRequest)
    // → { required_credentials: [
    //       { type: "HealthAgentCertification",
    //         fields: ["hipaaCompliance", "scope", "validUntil"] },
    //       { type: "PerformanceAttestation",
    //         fields: ["accuracy_p95", "uptime_sla"] }
    //   ] }

    // ClinEvidence selects matching VCs from its credential wallet
    selected_vcs = wallet.select(request.required_credentials)

    // Construct a VP — signed by ClinEvidence's DID key
    vp = VerifiablePresentation {
        holder: self.did,
        verifiableCredential: selected_vcs,
        proof: self.sign(selected_vcs, purpose="authentication")
    }

    send(orchestrator, vp)

4. Zero-Knowledge Proofs — Proving Claims Without Revealing Secrets

VCs solve the attestation problem, but they introduce a new tension: disclosure. When ClinEvidence presents its HIPAA compliance credential, it reveals the full credential contents, including its operating organization, model version, last audit date, and encryption standards. In many enterprise contexts, this is acceptable. But consider two scenarios where full disclosure is problematic.

First, in cross-organizational coalitions, a competing health plan's orchestrator might extract proprietary model architecture details from credentials. Second, in privacy-sensitive regulatory contexts (particularly those involving European patients under GDPR), even the disclosure of processing pipeline metadata may be excessive. The principle of data minimization demands that agents disclose only what is strictly necessary.

Zero-Knowledge Proofs (ZKPs) resolve this tension. A ZKP allows one party (the prover) to convince another party (the verifier) that a statement is true without revealing any information beyond the truth of the statement itself. ZKPs satisfy three properties: completeness (an honest prover always convinces an honest verifier), soundness (a dishonest prover cannot convince a verifier of a false statement except with negligible probability), and zero-knowledge (the verifier learns nothing beyond the statement's validity).

4.1 ZKPs in the Agent Credential Flow

The integration of ZKPs into the VC ecosystem is accomplished through BBS+ signatures and selective disclosure, a cryptographic technique formalized in the W3C VC-DI-BBS specification (currently a Candidate Recommendation as of 2025). BBS+ signatures allow a credential holder to derive a proof from a signed credential that reveals only a chosen subset of attributes, while the verifier can still confirm the issuer's original signature covers the full (undisclosed) credential.

// Ω needs GenomicsAgent to prove HIPAA compliance
// But GenomicsAgent doesn't want to reveal its model version or auditor

// GenomicsAgent holds a full VC with 12 attributes
full_vc = wallet.get("HealthAgentCertification")

// Generate a ZK derived proof revealing ONLY the required fields
zkp_disclosure = bbs_plus.derive_proof(
    credential:     full_vc,
    reveal_indices: [
        "credentialSubject.certification.hipaaCompliance.baaOnFile",
        "credentialSubject.certification.hipaaCompliance.dataPolicy",
        "validUntil"
    ],
    // These fields are PROVEN to exist and be signed by the issuer,
    // but their VALUES are not transmitted:
    hide_indices: [
        "credentialSubject.modelVersion",          // proprietary
        "credentialSubject.lastAuditDate",          // sensitive
        "credentialSubject.operatingOrganization",   // competitive
        "credentialSubject.certification.scope",     // not needed
    ],
    nonce: orchestrator_nonce   // binds proof to this specific interaction
)

// What Ω receives and verifies:
// ✓ baaOnFile = true              (revealed)
// ✓ dataPolicy = "ephemeral"      (revealed)
// ✓ validUntil = "2026-06-01..."  (revealed)
// ✓ Issuer's BBS+ signature covers ALL 12 fields (cryptographic proof)
// ✗ modelVersion = ???            (hidden — ZK proven to exist)
// ✗ lastAuditDate = ???           (hidden — ZK proven to exist)

4.2 Beyond Attribute Disclosure: ZKPs for Computation Integrity

Zero-Knowledge Machine Learning (ZKML) represents an emerging frontier that extends ZKPs from attribute disclosure to computation verification. The core idea: an agent can prove that it ran a specific model on specific inputs and produced a specific output, without revealing the model's weights or the full input data. This is accomplished through zkVMs (zero-knowledge virtual machines) that generate cryptographic proofs of correct program execution.

In our prior auth scenario, this enables a powerful guarantee: ClinEvidence could prove to Ω that its evidence synthesis output was genuinely produced by the model version attested in its VC, run on the patient's PICO query, without revealing the model architecture. The proof is a compact mathematical object (typically a few hundred bytes) that Ω can verify in milliseconds.

5. Blockchain-Anchored Trust — Immutable Audit & Smart Contracts

DIDs provide identity, VCs provide attestation, and ZKPs provide privacy-preserving proof. But none of these mechanisms address the problem of tamper-proof record-keeping. Who recorded that ClinEvidence completed task T1 at 14:32:07 with output hash 0xa3f9...? Where is this record stored, and can it be retroactively altered?

In healthcare, this is not an abstract concern. CMS requires that prior authorization decisions include a complete audit trail documenting the evidence considered, the reasoning applied, and the agents (human or algorithmic) involved. If that trail is stored in a single organization's database, it is vulnerable to tampering, accidental deletion, or disputes about what actually happened.

Blockchain-anchored trust addresses this by recording critical interaction metadata on an immutable distributed ledger. The key 2025 contribution in this space is BlockA2A (Zou et al., 2025), the first unified framework to formally integrate blockchain primitives with Google's A2A protocol, providing identity anchoring, immutable audit logging, and smart contract-based access control for multi-agent systems.

5.1 The BlockA2A Three-Layer Architecture

5.2 Practical Design: On-Chain vs. Off-Chain Partitioning

A critical architectural decision in blockchain-anchored trust is what goes on-chain versus what stays off-chain. Storing full agent interaction payloads on-chain would be prohibitively expensive, slow, and a privacy violation. BlockA2A and the broader DMAS literature (Hossen et al., 2025) converge on a consistent pattern: store hashes and metadata on-chain, store payloads off-chain (typically on IPFS or in encrypted object storage), and use the on-chain hash as an integrity anchor.

struct TaskAuditEntry {
    bytes32  taskId;              // unique task identifier
    string   agentDID;            // DID of the executing agent
    bytes32  outputHash;          // SHA-256 of the full output (stored off-chain)
    bytes32  inputHash;           // SHA-256 of the input received
    uint256  timestamp;           // block timestamp
    bytes    agentSignature;      // agent's Ed25519 signature over the entry
    bytes    orchestratorSig;     // orchestrator's countersignature
    string   offchainPointer;     // IPFS CID for the full output payload
}

// Both agent AND orchestrator must sign → multi-sig consensus
// Neither party can unilaterally alter the record
// Verifier retrieves payload via IPFS CID, checks hash against on-chain anchor

6. Reputation Systems — Trust That Evolves Over Time

DIDs, VCs, and blockchain anchoring together provide a robust foundation for initial trust by verifying who an agent is, what certifications it holds, and that its interaction history is tamper-proof. But they do not capture the most nuanced dimension of trust: performance over time.

An agent may hold a valid HIPAA certification yet consistently produce low-quality evidence syntheses. A credential says what an agent is authorized to do; a reputation score says how well it does it.

6.1 The EigenTrust Analogy for Agent Networks

The foundational model for peer-to-peer reputation is EigenTrust (Kamvar, Schlosser & Garcia-Molina, 2003), originally designed for file-sharing networks. The core idea: each peer maintains local trust ratings of peers it has directly interacted with. These local ratings are then aggregated globally via an iterative algorithm (conceptually similar to PageRank) to produce a global reputation score for every peer in the network. Agents that are trusted by highly-trusted agents receive higher global scores, with trust propagating transitively and weighted by the trustworthiness of the source.

Adapting EigenTrust to our agent network replaces the trust * 0.7 placeholder from the predecessor tutorial with a principled, data-driven mechanism. After each coalition completes, the orchestrator and member agents publish trust ratings as on-chain attestations, recording task completion quality, latency adherence, and protocol compliance. These ratings accumulate into a reputation graph that any future orchestrator can query.

// After coalition dissolution, Ω publishes a signed trust attestation
trust_rating = TrustAttestation {
    rater:        self.did,                     // Ω's DID
    subject:      "did:web:mednet.health:agents:clin-evidence-v2",
    coalition_id: "coalition-alpha-20250815",
    task_id:      "T1",
    metrics: {
        output_quality:     0.95,   // assessed by Ω's validation logic
        latency_compliance: 1.0,    // completed within deadline
        protocol_adherence: 0.98,   // followed A2A schema correctly
        data_handling:      1.0,    // no PHI retained post-task
    },
    composite_score: 0.97,          // weighted average
    timestamp: now(),
    signature: self.sign(...)       // non-repudiable
}

// Publish to the reputation ledger
reputation_ledger.submit(trust_rating)

6.2 Computing Global Reputation

With individual ratings accumulating on-chain, the global reputation of any agent can be computed by any party. The computation follows a weighted aggregation that accounts for three factors: the recency of the rating (recent interactions matter more), the reputation of the rater (ratings from highly-reputed orchestrators carry more weight, following the EigenTrust recursion), and the volume of interactions (more data points produce more confident estimates).

function compute_global_reputation(agent_did, ledger, decay_rate=0.95):
    // Fetch all trust ratings for this agent
    ratings = ledger.query(subject=agent_did)

    weighted_sum = 0
    weight_total = 0

    for rating in ratings:
        // Temporal decay: older ratings matter less
        age_days = (now() - rating.timestamp).days
        recency_weight = decay_rate ** age_days

        // Rater credibility: recursive — how reputed is the rater?
        rater_reputation = compute_global_reputation(rating.rater, ledger)
        credibility_weight = rater_reputation  // EigenTrust recursion

        // Combined weight
        w = recency_weight * credibility_weight
        weighted_sum += rating.composite_score * w
        weight_total += w

    if weight_total == 0:
        return 0.5   // default for unknown agents (Bayesian prior)

    return weighted_sum / weight_total

// In practice, this recursion is unrolled via matrix iteration
// (the EigenTrust "power method") to avoid infinite recursion.
// Convergence is typically achieved in 5–10 iterations.

The recursive structure mitigates Sybil attacks, in which an adversary creates many fake agents to inflate a target's reputation. Fake agents, having no interactions with reputable agents, receive near-zero credibility weights. Their ratings barely influence the target's global score. This is the same mechanism that makes PageRank robust to link farms: you cannot fabricate authority from nothing.

7. Worked Example: Trustworthy Prior Authorization, End to End

Let us now replay the predecessor tutorial's coalition formation for precision medicine prior authorization, this time with the full trust stack in operation. We will trace exactly how DIDs, VCs, ZKPs, blockchain anchoring, and reputation interact at each phase.

Replaying Recruitment: ClinEvidence for Task T1

The Mid-Task Growth Scenario — Revisited with Trust

Recall from the predecessor tutorial that GenomicsAgent detected a CYP2D6 poor metabolizer status and recommended DrugInteractionAgent from its gossip cache. In the trust-augmented version, this gossip recommendation now includes DrugInteractionAgent's DID. When Ω recruits DrugInteractionAgent, it must still complete the full six-step trust handshake, even when the recommendation came from a trusted peer.

8. Architectural Synthesis & Trade-Off Analysis

The four trust mechanisms we have examined are not alternatives to be chosen between; they are layers that compose. However, each layer introduces costs. A production architecture must make deliberate trade-offs based on the deployment context.

8.1 Revised Recruitment Algorithm — Integrating the Full Trust Stack

The predecessor tutorial's recruit_for_subtask function ranked candidates by match_score, trust (gossip decay), latency, and load_avail. We now replace this with a trust-enriched version:

function recruit_for_subtask_v2(subtask, registry, peer_cache, rep_ledger):
    required = extract_capability_requirements(subtask)
    candidates = registry.search(required) ∪ peer_cache.search(required)

    verified_candidates = []
    for candidate in candidates:
        // === LAYER 1: DID Authentication ===
        did_doc = did_resolver.resolve(candidate.did)
        if not authenticate_did(did_doc):
            continue   // identity check failed — skip

        // === LAYER 2: Credential Verification ===
        vp = request_presentation(candidate, subtask.required_credentials)
        if not verify_presentation(vp, subtask.min_credential_requirements):
            continue   // credentials invalid, expired, or insufficient

        // === LAYER 3 (optional): ZKP verification ===
        if subtask.requires_zkp:
            zkp_valid = verify_zkp_disclosure(vp.zkp_proofs, subtask.zkp_policy)
            if not zkp_valid:
                continue

        // === LAYER 4: Reputation lookup ===
        rep_score = rep_ledger.get_global_reputation(candidate.did)

        verified_candidates.append({
            agent:          candidate,
            did_doc:        did_doc,
            credentials:    vp,
            reputation:     rep_score,
            match_score:    candidate.match_score,
        })

    // Rank by composite trust-enriched score
    ranked = sort(verified_candidates, key=lambda c:
        0.25 * c.match_score +
        0.25 * c.reputation +
        0.25 * credential_strength(c.credentials) +
        0.15 * latency_score(c.did_doc) +
        0.10 * load_availability(c.agent)
    )

    // Negotiate with top candidate (same as before)
    for candidate in ranked:
        response = candidate.agent.negotiate(TaskProposal { ... })
        if response.status == "ACCEPTED":
            return candidate

    raise RecruitmentFailure("No verified agent found")

The critical difference: candidates that fail any trust layer are eliminated before reaching the ranking stage. No amount of capability match or low latency compensates for an unverifiable identity or expired credential. Trust is a prerequisite, not a trade-off dimension.

9. Open Frontiers & What Remains Unsolved

The trust stack presented here, comprising DIDs, VCs, ZKPs, blockchain anchoring, and reputation systems, represents the converging state of the art as of late 2025. But several hard problems remain at the frontier.

9.1 Credential Revocation at Coalition Speed

What happens if an agent's credential is revoked during a coalition's execution? The agent was verified at recruitment time, but its certifying body revoked the credential 10 minutes later (perhaps due to a discovered vulnerability). Current revocation mechanisms such as Certificate Revocation Lists (CRLs) and the Online Certificate Status Protocol (OCSP) introduce polling latency and external dependencies. Real-time revocation propagation across active coalitions remains an open protocol design challenge, identified as a critical requirement in the Huang et al. (2025) zero-trust identity framework.

9.2 Trust Across Heterogeneous Protocol Boundaries

Our tutorial assumes all agents communicate via A2A. In practice, a coalition may include agents using MCP (Anthropic), ACP (Cisco), or proprietary protocols. Each has different authentication and session semantics. The Agent Naming Service (ANS) proposal from the Cloud Security Alliance (2025) envisions a protocol-agnostic discovery and verification layer, but mapping trust primitives across protocol boundaries is an unsolved integration engineering challenge, especially when one of those protocols lacks native DID support.

9.3 Reputation Cold Start

New agents have no interaction history and thus a default reputation score (0.5 in our model). This creates a bootstrapping problem: new agents struggle to be recruited, which prevents them from building reputation, which perpetuates their exclusion. Solutions include credential-bootstrapped reputation (agents with strong VCs from reputable issuers start with an elevated prior), sandbox coalitions (low-stakes tasks where new agents can demonstrate capability), and staking mechanisms (agents or their operators deposit collateral that is slashed for poor performance, providing economic trust in the absence of historical trust).

9.4 ZKML Scalability

As noted in Section 4.2, generating zero-knowledge proofs for large language model inference is currently infeasible in real-time. If the agentic web is to provide verifiable computation guarantees at the model layer rather than only at the credential layer, ZK proof systems must improve by orders of magnitude in throughput. Specialized hardware (ZK ASICs) and recursive proof composition (proving a proof of a proof) are active research areas that may close this gap within 2–3 years.

9.5 Governance of the Trust Infrastructure Itself

Who governs the DID methods, the credential schemas, the reputation algorithms, and the smart contract policies? If a single entity controls these standards, we have re-centralized at a different layer. The emerging model is federated governance, in which consortia of healthcare organizations, technology providers, and regulatory bodies jointly manage trust infrastructure parameters. The Decentralized Identity Foundation (DIF) and the Trust over IP Foundation are leading this standardization effort, but healthcare-specific governance models for agent trust infrastructure remain nascent.