AEX: Non-Intrusive Multi-Hop Attestation and Provenance for LLM APIs

This paper proposes AEX, a non-intrusive attestation extension for LLM APIs that uses signed objects to cryptographically bind client requests to verified responses or streaming outputs, thereby providing direct evidence of output provenance and preventing intermediary manipulation without altering existing API semantics.

The Gist

Imagine you order a custom cake from a famous bakery through a delivery app. You want to be 100% sure that:

1. The cake you get is actually the one you ordered, not a random cake from a different baker.
2. No one tampered with it while it was in transit.
3. If the delivery driver added a little extra frosting or swapped the box, you know exactly who did it and that it was an authorized change, not a theft.

Currently, with Large Language Models (LLMs) like the ones powering chatbots, we are in a world where you send a request (the order), but you have no real proof that the answer you get (the cake) actually came from the specific model you asked for, or that it wasn't altered by a middleman along the way.

AEX is a new "digital seal" system designed to fix this. Here is how it works, broken down into simple concepts:

1. The Problem: The "Shadow Bakery"

Recently, researchers found that many unofficial websites claim to sell cakes from famous bakeries, but they are actually baking their own (often worse) versions. Even if the cake looks similar, it might taste different.

• Current solutions are like trying to guess the baker by smelling the cake (fingerprinting) or checking if the oven is the right temperature (hardware checks). These are helpful, but they are indirect and often fail.
• The Gap: We need a way to say, "This specific answer came from this specific request, signed by a trusted authority, and here is the history of any changes made along the way."

2. The Solution: The "Digital Seal" (AEX)

AEX acts like a tamper-evident, signed receipt that gets attached to the very top of the answer. It doesn't change the cake (the answer); it just adds a special, unbreakable sticker.

How it works in three steps:

Step A: The "Order Receipt" (Request Binding)
When you send your prompt, AEX creates a unique digital fingerprint of your request.

• The Analogy: Imagine you write your order on a piece of paper. AEX takes a photo of that paper and seals it in a plastic bag.
• The Twist: Sometimes, the bakery (the API) needs to add a "trace ID" or fix a typo before baking. AEX allows the bakery to say, "We added a trace ID, but we promise the core order is the same." It creates a chain of receipts showing exactly what changed and who authorized it.

Step B: The "Delivery Chain" (Streaming Integrity)
LLMs often answer word-by-word (streaming), like a conveyor belt dropping out cookies one by one.

• The Analogy: If someone sneaks in and swaps a chocolate chip cookie for a raisin one in the middle of the line, the whole batch is ruined.
• The Fix: AEX links every single "cookie" (word chunk) to the one before it using a cryptographic chain. If a cookie is missing, swapped, or added, the chain breaks, and the seal on the final box will show "Tampered."

Step C: The "Repackaging Receipt" (Trusted Rewriting)
Sometimes, a middleman (like a company firewall) needs to edit the answer to remove sensitive info or change the format (e.g., turning a long stream of text into a single summary).

• The Analogy: Imagine the bakery sends the cake in a box, but a middleman repacks it into a gift basket.
• The Fix: AEX doesn't treat this as a crime. Instead, the middleman signs a new receipt saying, "I took the original sealed box, repacked it, and here is the new seal." This proves the final gift basket came from the original cake, even if the packaging changed.

3. What AEX Does (and Doesn't) Do

✅ What it DOES:

• Proves Origin: It proves a trusted issuer signed the link between your question and their answer.
• Proves Integrity: It proves no one sneaked in to change the words while they were traveling.
• Proves History: It shows a clear, signed history of any authorized changes (like a middleman editing the text).
• Non-Intrusive: It works with existing systems. You don't need to rebuild your entire app; you just add the "sticker" to the response.

❌ What it DOESN'T do:

• It doesn't prove the cake tastes good. (It doesn't check if the answer is factually true or smart).
• It doesn't prove the baker didn't use a secret ingredient. (It doesn't check the internal code or weights of the AI model).
• It doesn't stop a malicious baker. If the bakery itself is lying and signs a fake receipt, AEX can't stop them. You still have to trust the bakery.

The Bottom Line

AEX is like a notary public for AI conversations. It doesn't guarantee the AI is smart or honest about the world, but it guarantees that this specific conversation happened exactly as recorded, that no one tampered with the text in transit, and that any changes made were done by people you explicitly trust.

It turns the "black box" of AI APIs into a transparent, auditable transaction where you can finally say, "I know exactly where this answer came from and that it hasn't been messed with."

Technical Summary

1. Problem Statement

The rapid adoption of Hosted Large Language Models (LLMs) via remote APIs has shifted the trust boundary from local execution to the API interface. Recent audits of "shadow APIs" (unofficial or intermediary endpoints) reveal significant issues:

• Behavioral Divergence: Unofficial endpoints often deviate from claimed model behavior (up to 47% utility divergence).
• Inadequate Verification: Existing methods like fingerprinting, statistical testing, and Trusted Execution Environment (TEE) attestation are either inferential, intrusive, or answer different questions (e.g., "what model is running?" vs. "did this specific request produce this specific output?").
• Middleware Complexity: Real-world API traffic passes through gateways, proxies, and middleware that may rewrite prompts, inject policies, buffer streams, or repackage outputs. Current protocols cannot distinguish between benign/trusted transformations and malicious tampering.

The Core Gap: There is no mechanism to provide direct, online, verifiable evidence that a specific client-visible request is bound to a specific response or streaming output sequence, while accommodating necessary middleware transformations.

2. Methodology: The AEX Protocol

The authors propose AEX (Attestation EXtension), a non-intrusive protocol extension for existing JSON-based LLM APIs (specifically OpenAI-compatible chat-completions).

Key Design Principles

• Non-Intrusive: AEX preserves existing request/response semantics, tool-calling, streaming, and error handling. It does not require changing the business payload.
• Detached Attestation: It adds a signed top-level attestation object to the JSON response. This object binds the request to the output without altering the payload itself.
• Canonicalization: It uses the JSON Canonicalization Scheme (JCS) to ensure cryptographic operations are invariant to whitespace, field ordering, or numeric spelling differences.
• Cryptographic Primitives: It relies on standard Ed25519 signatures and SHA-256 hashing, avoiding new cryptographic primitives.

Core Mechanisms

1. Request Commitments:

   • Request Commit: A hash of the client-visible request (using a specific binding mode).
   • Effective Request Commit: A hash of the request after trusted rewriting (e.g., by a gateway).
   • Binding Modes: Clients can choose strictness levels (full, top_level_exclude, top_level_include) to handle benign middleware changes (like adding trace IDs) without breaking verification.
   • Request-Transform Receipts: A chain of signed receipts from trusted intermediaries proving how the original request was transformed into the effective request.

2. Output Commitments & Streaming:

   • Non-Streaming: A hash of the complete JSON response object.
   • Streaming: Uses a dual-anchor hash chain. The chain is seeded by the request commitment and updated with every JSON chunk.
   • Two Proof Modes:
     • Source-Stream Prefix Mode: Used when the stream is untransformed. Allows "checkpoints" to verify prefixes of the stream in real-time.
     • Complete-Output Lineage Mode: Used when the output has been rewritten, buffered, or repackaged. Checkpoints are forbidden; instead, the final attestation includes an origin_output receipt and a chain of output_transforms receipts linking the source output to the final delivered output.

3. Trusted Transformations:

   • AEX explicitly models trusted rewriting. If a gateway rewrites a prompt or aggregates a stream, it signs a receipt. The final issuer verifies these receipts and includes them in the terminal attestation, proving the lineage without requiring the client to see the intermediate hidden states.

3. Key Contributions

1. Protocol Design: A concrete, interoperable protocol for adding request-output attestation to existing LLM APIs without changing their body semantics.
2. Explicit Binding Modes: A novel approach allowing clients to define how strictly requests are bound, distinguishing between malicious mutation and trusted middleware normalization.
3. Lineage Metadata: Introduction of origin_output and output_transforms receipts to create an auditable chain of custody for outputs that have been rewritten, aggregated, or re-encoded.
4. Streaming Distinction: A clear separation between "source-stream prefix proofs" (for unmodified streams) and "complete-output lineage" (for transformed outputs), preventing clients from misinterpreting partial evidence.
5. Implementation & Validation:
   • A reference TypeScript prototype.
   • Automated conformance testing (unit, integration, and browser E2E tests).
   • Microbenchmarks demonstrating low overhead (e.g., ~0.5ms verification time for non-streaming responses).

4. Results and Evaluation

• Correctness: The prototype successfully validated all defined scenarios, including request binding modes, request-transform chains, streaming checkpoints, and cross-mode output lineage (e.g., stream-to-non-stream conversion).
• Performance:
  • Non-streaming: Median client completion time was ~2.29ms; gateway verification time was ~0.50ms.
  • Streaming: Verification overhead remained low (~0.8ms to ~1.5ms depending on lineage complexity). The latency was dominated by artificial delays in the simulator to test checkpoint behavior, not cryptographic costs.
  • Overhead: The protocol adds minimal size to the payload (the attestation object) and negligible processing time.
• Security Analysis: The paper demonstrates that AEX effectively detects tampering (insertion, deletion, reordering, truncation) and distinguishes it from trusted transformations. It clarifies that AEX does not prove model truthfulness, hidden prompt absence, or specific hardware/weights, but rather the integrity of the transaction boundary.

5. Significance and Impact

• Practical Deployment: Unlike TEE attestation or verifiable inference which often require hardware changes or intrusive model modifications, AEX is designed for immediate deployment on existing JSON APIs.
• Trust in Middleware: It solves a critical real-world problem: how to trust the output when it has passed through multiple layers of infrastructure (gateways, safety filters, aggregators) without treating every modification as a security failure.
• Complementary to Existing Tech: AEX does not replace fingerprinting or TEEs but complements them. It provides the "transactional binding" layer that is currently missing, allowing auditors to verify what was sent and received, while other tools verify how it was generated.
• Standardization Path: The paper outlines a clear path for standardization, including an OpenAI-compatible profile, JWKS-based key discovery, and a structured failure state machine for SDKs.

In summary, AEX provides a pragmatic, cryptographic solution to the "black box" nature of LLM API interactions, enabling clients to verify the integrity and provenance of AI-generated content even in complex, multi-hop network environments.