PaperlayerView exact revision on arXiv

Source-linked AI summary

Attesting Outputs and Delegation Ancestry in Multi-Agent AI Systems

Lifei Liu, Haoran Yu

arXiv:2608.30387v1cs.CR

TL;DR

Multi-agent delegation lacks evidence that a trusted runtime released particular bytes or that both deployers authorized a dynamically created cross-deployer edge. The paper proposes separate output and ancestry attestation layers and compares three path constructions; after child-key compromise, only the co-signed DAG rejects an unauthorized parent claim, while its evaluated workflows passed complete verification. The design supports audit and attribution, but does not prevent prompt injection and its cloud evaluation excludes several production latencies and controls.

  • Problem

    Credentials identify actors and permissions but need not bind later output bytes or prove authorization of dynamically created cross-deployer edges.

  • Method

    The paper combines deployer-runtime output-hash signatures with ancestry records and compares a signed linked list, Merkle-chain variant, and co-signed DAG.

  • Results

    After child-key compromise, only the co-signed DAG rejects a new parent claim because it requires the parent’s signature on the edge; all evaluated signed-DAG tasks and paths passed complete verification.

  • Takeaways & Limitations

    The construction supports post-incident audit and attribution, while explicit parent authorization is required for resistance to unauthorized cross-deployer edges.

  • Takeaways & Limitations

    The local workflow uses separate loopback trust domains and excludes public-network latency, TLS/mTLS, OAuth, KMS, production authorization-service latency, and several operational concerns.

Abstract

from arXiv · show

Multi-agent applications delegate work across independently operated deployers. After an incident, a verifier must answer two questions: which deployer released the reported bytes, and whether each cross-deployer edge was authorized. Credentials establish who may act, but need not bind them to later output bytes or prove both deployers authorized a dynamically created edge. We present a two-layer attestation design for dynamic delegation without a shared authority, public log, or precommitted workflow. A trusted deployer runtime signs a hash of each released output; this records released bytes but does not prevent prompt injection. Ancestry evidence records edge authorization. Under a unified threat model, we compare a signed linked list, a Merkle-chain variant, and a co-signed DAG. The primitives are standard; the contribution is deployer-side binding and the evidence needed for the two questions. After child-key compromise, the single-signer designs permit an unauthorized parent binding, whereas the co-signed DAG rejects it because the parent must authorize the edge. Fixed adversary matrices and regression tests validate the composed verifier. On an Apple M1 Pro, ancestry-only checks take 24.3-499.2us per hop. In a live local multi-service workflow, a parent discovers the child's A2A Agent Card; the child calls an MCP tool and releases local-LLM output: all 30 signed-DAG tasks passed complete verification, while a controlled child-key-only claim was rejected; its mean end-to-end latency was 813.1ms versus 770.8ms without evidence. In a complementary three-availability-zone AWS deployment, all 1,000 valid co-signed-DAG paths verified; issuance averaged 3.651ms and complete verification 5.015ms. The cloud result excludes TLS/mTLS, KMS, and model-serving latency.

I. INTRODUCTION

The paper separates output attribution from delegation authorization, addressing evidence gaps that credentials alone leave in dynamic multi-agent paths. It proposes deployer-side output binding plus ancestry evidence, and compares constructions that differ under child-key compromise.

  • Credentials identify principals and permissions but need not bind later released bytes or establish authorization for each dynamically created cross-deployer edge.
  • A trusted deployer runtime signs each output hash, while an ancestry record carries authorization evidence for every delegation edge.The verifier evaluates a presented path without requiring a shared authorization service, public log, or precommitted workflow.
  • After child-key compromise, linked-list and Merkle variants accept child-authorized parent bindings, whereas the co-signed DAG requires the parent’s signature and rejects unauthorized edges.
  • The output-attestation interface records bytes released under a trusted-runtime assumption but does not detect or prevent prompt injection.
  • The paper’s scope is post-incident evidence of released bytes and delegation ancestry, complemented by existing behavioral and authorization controls rather than replacing them.

III. SYSTEM AND UNIFIED THREAT MODEL

The system models delegation records emitted by deployers and verified as a presented root-to-leaf path. Its two evidence layers bind released output bytes and delegation ancestry, with cross-deployer edges optionally requiring approval from both endpoint deployers.

  • System model: A deployer hosts an agent, controls its signing key, and emits a delegation record when the agent invokes another agent.Each record identifies the issuer, child instance, proposed parent, declared depth, expiry time, nonce, and evidence construction.
  • Verification model: Consumers verify a claimed path from a root principal to a leaf agent using the ordered, presented root-to-leaf chain.The prototype has no separately named global chain_id.
  • Evidence layers: Output evidence binds deployer-issued credentials to released bytes, while ancestry evidence binds delegation records to parents and can require both endpoint deployers to approve cross-deployer edges.The objectives include rejecting substituted output, replay with persistent nonce state, malformed or spliced ancestry, and unauthorized cross-deployer relationships.

B. Unified Trust Boundary

The threat model trusts the deployer runtime, signing key, authorized-deployer registry, and verifier, while treating agents, tools, transport, and chain documents as potentially malicious. It targets structural evidence manipulation and attribution failures, not prompt-injection prevention or every downstream consequence of compromise.

  • Unified Trust Boundary: The trusted boundary comprises the deployer runtime, its private signing key, the authorized-deployer registry, and the verifier implementation.LLM agents, tool responses, network transport, and supplied chain documents may be malicious.
  • Adversary model: The adversary may control tools and agent behavior, replay or modify evidence, and construct structural payloads, but cannot forge uncompromised signatures or compromise the trusted runtime.The single-key compromise study relaxes secrecy for one deployer’s signing key.
  • Structural attacks: The evaluation covers orphan insertion, middle-node removal, chain transplant, and ancestor revision; sibling fanout remains an application-policy issue.Sibling fanout can require a signed child limit plus verifier state.
  • Scope boundary: Evidence manipulation can misattribute responsibility and obstruct revocation or incident investigation, but chain integrity is not claimed to deter every prompt-injection attacker.The taxonomy addresses evidence manipulation rather than the attacker’s incentives after causing harm.

E. Holistic Security Rationale

The composed verifier separately authenticates output bytes and delegation structure, so passing one layer cannot substitute for the other. Its guarantees depend on registered keys, verifier predicates, and the trusted runtime, with replay and key-rotation capabilities bounded by the prototype’s local state.

  • Output verification: Output verification requires the signed output hash, primary signature, key identifier, validity interval, and nonce to match the received bytes.The output check is distinct from ancestry verification.
  • Ancestry verification: Ancestry verification requires registered issuers, consistent parent references and depths, and any required cross-deployer co-signatures.A valid chain does not authenticate altered output bytes, and an output-check failure does not satisfy ancestry predicates.
  • Security rationale: Accepted tampered output or structural edits would imply a broken cryptographic assumption, trusted-runtime violation, missing verifier predicate, or compromised signing key.The key-compromise analysis isolates compromised signing keys as a distinct case.
  • Operational boundaries: The verifier uses a local authorized-key registry and optional persistent nonce store, but does not implement production key rotation, distributed revocation propagation, or cross-verifier replay storage.These limitations bound the prototype’s deployment scope.
  • Layer 1 placement: Output attestation binds a deployer runtime to released bytes after runtime production and before delivery or delegation; the agent does not hold the signing key.The construction addresses output attribution rather than AI-specific cryptographic primitives.
  • Attestation record: Each output record includes identifiers, timing, ancestry, a SHA-256 output_hash, nonce, binding scope, lifecycle metadata, and a derived key_id in the wire envelope.The deployer signs a deterministic recursively keysorted JSON serialization.
  • Composed verification: The verifier resolves deployers through a trusted registry, checks key identity and revocation, validates signatures and intervals, recomputes hashes, and rejects duplicate or previously consumed nonces when persistent state is supplied.These checks establish integrity and origin under the stated trust boundary.

B. Current Granularity Boundary

The design draws a current evidence boundary: signed records attest released bytes and ancestry, but the prototype does not enforce streaming or session semantics. Its baseline path checks bind records structurally yet do not establish parent consent for new cross-deployer edges.

  • Current Granularity Boundary: The prototype signs one deterministic output per graph node, so it does not evidence streaming or token-window enforcement.Deployments requiring these semantics must add and verify explicit session and sequence fields before making claims about reordering or cross-session transplantation.
  • Current Granularity Boundary: A trusted runtime’s signed record identifies the deployer that released bytes and correlates them with delegation ancestry, but does not prevent attacker-directed output.Preventing such output requires a separate control before release.
  • Signed Linked-List Baseline: The linked-list baseline commits each record to its parent, enabling complete-path verification with one hash and one signature check per hop.Structural edits such as removing or transplanting nodes break descendant commitments while relevant signing keys remain secret.
  • Signed Linked-List Baseline: A child can still sign a well-formed record naming any visible parent, so the baseline lacks authorization evidence from that parent.This is a missing parent authorization statement, not a failure of hash chaining.

C. Baseline 2: Merkle-Chain Variant

The Merkle-chain variant offers compact partial-path proofs but does not add a new authorization principal, so child-key compromise still permits an unauthorized parent binding. The co-signed DAG addresses that gap by requiring parent authorization for cross-deployer edges, at the cost of parent availability.

  • Baseline 2: Merkle-Chain Variant: The Merkle variant replaces per-hop parent commitments with a Merkle commitment over the current ancestry prefix.Its leaves are canonical node representations.
  • Baseline 2: Merkle-Chain Variant: For complete-path verification, the Merkle variant adds a consistency check but not a different authorization principal, so it fails R3 after child-key compromise.A compromised child can recompute the affected root and sign the new node.
  • Baseline 2: Merkle-Chain Variant: Merkle commitments may provide logarithmic-size inclusion proofs when a consumer verifies a selected ancestor, but this optimization is outside the complete-path evaluation.The evaluated consumer verifies the full ancestry to detect omission and splice attacks.
  • Cross-Deployer Design: Co-Signed DAG: Only the co-signed DAG rejects arbitrary cross-deployer parent binding because it requires the uncompromised parent’s co-signature.All three designs accept a same-deployer suffix rewrite.
  • Cross-Deployer Design: Co-Signed DAG: The co-signed property requires the parent deployer to be online, and refusal or timeout causes cross-deployer delegation to fail closed.Same-deployer hops can use the linked representation while cross-deployer requests are queued.

E. Path Completeness and Lifecycle Checks

Path verification checks presentation completeness using signed ancestry depth, while lifecycle-event semantics remain outside the current cryptographic evaluation. Deployments must validate lifecycle invariants against their own runtime event models.

  • Path Completeness: The verifier rejects a presented path when its record count differs from the signed ancestry_depth.Nonce checks also prevent reuse of a record at the same verifier.
  • Lifecycle Checks: The evaluation does not claim a complete lifecycle-semantics audit because lifecycle invariants are separate from cryptographic predicates.Deployments must validate those invariants against their own runtime event model.

VI. EVALUATION

The evaluation combines fixed adversary matrices, implementation-conformance checks, and platform-specific experiments to assess structural behavior and verification cost. These tests are bounded validation exercises rather than open-world security guarantees.

  • The evaluation asks what protection each ancestry construction provides, whether structural predicates are enforced, and what issuing and verification cost they impose.
  • 27,000 fixed mutations produced no accepted invalid presentation across the covered conformance checks.The composed-receipt matrix repeats B1–B4, while B5 is exercised only in ancestry-only mode.
  • The current experiments use 1,000 trials per design–attack pair and distinguish ancestry-only checks from composed-receipt verification.
  • The current matrix measures conformance on a finite, hand-specified attack set, not a cryptographic or open-world security guarantee.Historical LLM-guided aggregates are retained only as exploratory context.

B. Structural Security Comparison

The structural comparison separates ordinary ancestry binding from cross-deployer edge authorization under child-key compromise. Single-signer formats allow unauthorized parent claims, while the co-signed DAG requires the parent’s signature.

  • Under child-key compromise, LINKED-LIST and MERKLE permit arbitrary parent claims because the child can sign a record using a public parent commitment.
  • The edge-authorization game treats success as creating an accepted cross-deployer edge to an uncompromised parent that did not sign the transcript.
  • The SIGNED-DAG rejects unauthorized cross-deployer edges because each edge transcript requires the uncompromised parent deployer’s signature.The corresponding edge-authorization success probability is negligible under the stated signature and hash assumptions.
  • The theorem proves edge creation only and excludes policy-semantic authorization, revocation freshness, and collusion by both endpoints.

C. Implementation-Conformance Validation

Implementation validation found zero accepted attacks in the deterministic structural matrices and successful end-to-end operation across local framework, live multi-service, and AWS deployments. The reported measurements separate conformance evidence from performance and deployment scope.

  • C. Implementation-Conformance Validation: All 15 ancestry-only matrix cells rejected every trial, with a Wilson 95% upper bound of 0.38% per cell.The separate composed-receipt matrix also had zero accepts in all 12 cells.
  • D. Performance and Framework-Integration Overhead: At ancestry depth five, mean ancestry-only checks took 24.3 µs for LINKED-LIST, 72.7 µs for MERKLE, and 499.2 µs for SIGNED-DAG.These figures exclude primary receipt checks and are not complete-verifier costs.
  • D. Performance and Framework-Integration Overhead: The LangGraph integration passed composed verification for every three-node chain across 1,000 executions.Signing averaged 0.171 ms per node and 0.512 ms per task.
  • D. Performance and Framework-Integration Overhead: Every live local workflow task passed complete verification across discovery, A2A, MCP, local LLM generation, issuance, and verification.The experiment ran 30 tasks per condition after ten warm-ups.
  • D. Performance and Framework-Integration Overhead: The AWS deployment verified all 1,000 valid two-signer paths, with 3.651 ms mean issuance and 5.015 ms mean complete verification.The configuration-specific measurements exclude TLS, KMS, and model-serving latency.

VII. DEPLOYMENT IMPLICATIONS AND LIMITATIONS

Deployment choice follows the trust relationship: linked representations minimize local ancestry-verification cost, while co-signed DAGs provide explicit parent authorization for cross-deployer edges. The evaluation verifies the co-signed-DAG path across several deployments, but local workflow scope excludes important production security and latency factors.

  • Deployment implications: A signed linked list had the lowest measured local ancestry-verification cost within one deployer trust domain.
  • Deployment implications: A co-signed DAG is appropriate when cross-deployer edges require explicit parent authorization and an online co-signature handshake is acceptable.
  • Limitations: The local MCP/A2A workflow does not measure public-network latency, TLS/mTLS, OAuth, KMS, or production authorization-service latency.
  • Deployment implications: The prototype verified co-signed-DAG paths in process, container, three-zone AWS, and live local MCP/A2A/LLM workflows.
  • Limitations: The construction supports post-incident audit and attribution, not prompt-injection prevention.
Loading 2608.30387v1…