Offline-Verifiable Accountability for Cross-Organization Agent Messaging: A Preserved Evidence-Bundle Approach

Adil Alshammari; Hayretdin Bahsi

cs.CRAug 28, 2026

Offline-Verifiable Accountability for Cross-Organization Agent Messaging: A Preserved Evidence-Bundle Approach

Authors: Adil Alshammari, Hayretdin Bahsi

Organizations: School of Informatics, Computing, and Cyber Systems, Northern Arizona University, United States · Department of Computer Science, College of Computer and Information Sciences, Majmaah University, Majmaah 11952, Saudi Arabia · School of Information Technologies, Tallinn University of Technology, Estonia

Abstract

Cross-organization agent workflows require preserved evidence that remains independently verifiable during later audit or dispute review. They may involve multiple organizations, delegated actions, policy-relevant events, and disputed accountability claims. This is difficult when live systems are unavailable, controlled by one party, or not trusted by all participants. Existing mechanisms provide useful pieces, including authenticated logging, delegation semantics, signed checkpoints, and consistency checks. What remains missing is a verifier-centered event-level bundle for checking evidence sufficiency offline under an explicit policy. We propose a preserved evidence-bundle model and a policy-controlled offline verifier for agent-to-agent workflow events. Each bundle preserves policy-required evidence, including sender authentication, authenticated log commitment, witness-backed checkpoint evidence, append-only continuity, delegation-aware authorization evidence, and explicit receiver-signed receipt evidence when required. The verifier accepts only claims supported by the selected policy-required evidence, giving a later reviewer an offline basis for assessing evidence sufficiency. It does not infer delivery or receipt from transport behavior or log inclusion alone. In a prototype evaluation over 300 complete workflows and 1200 valid preserved bundles, we measure offline verifier-side latency across policy profiles and workflow-event evidence requirements. Checkpoint-context anchoring has the highest latency in the current prototype, while delegation and workflow-prerequisite evidence require additional verification steps. In targeted negative-evidence tests, all corrupted or policy-insufficient bundles were rejected, with no false acceptance observed. These results support evidence-based audit and dispute review without relying on live services or platform-specific logs.

Figures & tables

Reference	Year	Context	Evidence bundle	Offline verification	Signed checkpoint	Inclusion proof	Witness / consistency	Delegation evidence
Dirksen et al. [ 8 ]	2021	Web PKI	$\times$	$\triangle$	$\triangle$	$\triangle$	$\checkmark$	$\times$
Malvai et al. [ 21 ]	2023	E2EE messaging	$\times$	$\triangle$	$\triangle$	$\triangle$	$\checkmark$	$\times$
Li et al. [ 19 ]	2024	Medical data	$\times$	$\triangle$	$\times$	$\times$	$\times$	$\checkmark$
Ferretti et al. [ 11 ]	2021	IIoT	$\times$	$\triangle$	$\triangle$	$\triangle$	$\times$	$\checkmark$
This work	2026	Agent messaging	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$

Table 1: Comparison of related work by verifier-relevant evidence support.

Boundary	Verifier implication
Agent-side domains	Verify sender identity and policy-bound evidence.
Untrusted transport	Do not treat transport success as evidence.
Evidence-producing services	Check only policy-required evidence.
Preserved evidence stores	Check for omission, substitution, or tampering.
Local verifier trust base	Use local policy, keys, and trust anchors.
External action boundary	Do not infer endpoint correctness or execution.

Table 2: Evidence-control boundaries and verifier implications.

Notation	Description
$m$	Canonicalized message representation.
$h(m)$	Message commitment derived from $m$ .
$H(\cdot)$	Hash or commitment function.
$\sigma_{S}$	Sender signature over the canonical message.
$\sigma_{R}$	Explicit receiver-signed receipt.
$\sigma_{L}$	Log signature over signed-checkpoint fields.

Table 3: Main notation.

Artifact	Supports	Does not establish
Sender signature	Message authorship	Logging, receipt, or delivery
Log evidence	Log commitment	Receipt, delivery, or endpoint correctness
Signed receipt	Receipt claim	Delivery or downstream execution
Witness evidence	Checkpoint support	Receipt, delivery, or real-time equivocation prevention
AOEP evidence	Append-only extension	Global consistency or collusion resistance
Checkpoint context	Checkpoint anchoring	Continuity, receipt, or endpoint correctness

Table 4: Evidence artifacts and claim limits.

Figure 1: Sender-authenticated messages are validated, logged, augmented with policy-required checkpoint evidence, and preserved as evidence bundles for offline verification.

Figure 2: Sequence-level evidence generation for the running workflow example. Event 1 is refer_patient , Event 2 is order_mri , Event 3 is send_result , and Event 4 is submit_claim . Events 1–3 share the signed-message, validation, logging, and evidence-storage pattern. Event 4 adds delegation and workflow-prerequisite evidence.

Figure 3: Offline verification inputs and policy-controlled checks over a preserved evidence bundle.

Figure 4: Policy-controlled evidence checks used by the fully enabled verifier profile and the single-control policy comparison.

ID	Property	Required evidence and scope
P1	Authenticated log commitment	Inclusion proof and signed checkpoint; verified checkpoint only.
P2	Sender-authenticated message binding	Sender-authenticated message fields and payload-to-log binding evidence.
P3	Append-only continuity	Prior-checkpoint context and append-only extension evidence; policy-enabled.
P4	Witness-backed checkpoint validity	Witness evidence; does not imply receipt, delivery, or real-time equivocation prevention.
P5	Capability and policy-required workflow checks	Delegation-aware authorization evidence and required workflow evidence.
P6	Checkpoint-context validation	Checkpoint-context evidence and permitted WCL context; policy-enabled.

Table 5: Verifier-supported security properties and required evidence.

ID	Security threat	Affected evidence	Evidence issue	Props.
T1	Identity spoofing	Signed-message submission	False or impersonated sender identity.	P2
T2	Log tampering	Log evidence	Inclusion proof, signed checkpoint, or log material modified.	P1
T3	Rebinding	Payload-to-log binding	Commitment, leaf index, or Merkle path modified or rebound.	P1, P2
T4	Repudiation	Sender evidence	Sender denies authorship despite preserved sender authentication.	P2
T5	Tampering or omission	Witness/AOEP/context	Required evidence missing or modified.	P3, P4, P6
T6	Unauthorized delegation	Workflow/delegation	Capability or workflow evidence forged, rebound, or missing.	P5

Table 6: Evidence-level security threats mapped to verifier-supported properties.

Exp.	Evaluation question	Method	Interpretation
E1	Which policy checks add verifier time?	Single-control comparison over valid submit_claim bundles.	Latency attribution relative to the ALL_ON baseline.
E2	Does latency vary by event evidence?	Paired comparison across the four workflow events.	Event-level evidence analysis, not throughput benchmarking.
E3	Does invalid or policy-insufficient evidence fail at the expected check?	Targeted negative-evidence cases mapped to checks, threats, and properties.	Diagnostic rejection coverage, not exhaustive adversarial search.

Table 7: Evaluation design and claim-matched purpose of each experiment.

Profile	Disabled verifier control	Median [95% CI] (ms)	P95 (ms)	Reduction vs. ALL_ON
ALL_ON	None	785.52 [774.38–799.62]	1064.33	–
NO_WIT	Witness validation	745.60 [738.85–755.89]	954.92	5.1%
NO_AOEP	AOEP continuity	761.93 [754.90–772.95]	1063.04	3.0%
NO_CAP	Capability/workflow check	761.82 [751.83–775.11]	1027.94	3.0%
NO_EPOCH	Checkpoint-context anchoring	183.04 [174.52–200.43]	417.64	76.7%

Table 8: Experiment E1 within-experiment verifier-side latency attribution under single-control policy comparisons for valid submit_claim bundles (

n=300

per profile).

Figure 5: Offline verification latency across workflow event types under the fully enabled verifier profile (

n=300

paired workflows). Circles show median latency with 95% bootstrap confidence intervals, square markers show P95 latency, and vertical spans show the median-to-P95 range. The y-axis uses a truncated lower bound for readability. The submit_claim event requires the most verification time because it exercises the richest workflow-accountability path.

Case	Verifier check	Threat ID	Property	Mutation or misuse
C1	Payload binding	T3	P2	Canonical payload modified after issuance.
C2	Merkle inclusion	T3	P1	Audit-path sibling hash replaced.
C3	Merkle inclusion	T3	P1	Leaf index modified while preserving the bundle structure.
C4	Signed checkpoint validation	T2	P1	Signed checkpoint root modified.
C5	Append-only continuity	T5	P3	AOEP proof element modified between checkpoints.
C6	Capability binding	T6	P5	Capability scope modified.

Table 9: Negative-evidence cases mapped to evidence-level security threats and verifier-supported properties.

AI Agent Auditing

AI agent auditing examines agents’ actions, tool use, evidence, and outcomes to assess safety, compliance, reliability, and accountability.

See all 269 papers

Agent Flight Recorder: Tamper-Evident Audit Trails with On-Chain Anchoring for Long-Horizon Tool-Using Agents
Sep 1, 2026Laurent Bindschaedler, Quentin Botha, Christoph SiebenbrunnerData Provenance Algorithmic Auditing
Max Planck Institute for Software Systems · Research Institute for Cryptoeconomics, Vienna University of Economics and Business
ClaimReceipt: Verifying Evidence Sufficiency and Coverage in Agent Evaluations
Sep 2, 2026Peiying Zhu, Sidi ChangClaim Verification Data Provenance
Blossom AI Blossom AI Labs San Francisco, CA, USA
Evidence-First Agentic Verification
Oct 13, 2026Reza Sanayei, Razvan-Gabriel Dumitru, Sunjie Hou +7LLM Agent Verification AI Agent Evaluation
Scale AI · University of Arizona

Sep 1, 2026J/K move · Enter open · S save

Agent Flight Recorder: Tamper-Evident Audit Trails with On-Chain Anchoring for Long-Horizon Tool-Using Agents

Laurent Bindschaedler, Quentin Botha, Christoph Siebenbrunner

Max Planck Institute for Software Systems · Research Institute for Cryptoeconomics, Vienna University of Economics and Business

Data Provenance Algorithmic Auditing AI Agent Auditing AI Agent Monitoring Tamper-Evident Logging

Open paper AskPDF arXiv

Long-horizon agents execute thousands of actions, resulting in sequential failures rather than isolated errors. When a coding agent deletes a production database or a prompt injection spreads across agents, the incident raises questions of causality, authority, and non-repudiable third-party verification. The Agent Flight Recorder captures each agent action as a structured, canonically serialized event binding eight semantic fields from intent through execution to provenance. Hash chaining and Merkle batching provide tamper evidence and compact inclusion proofs. For cross-organizational disputes where no party's infrastructure qualifies as neutral ground, periodic on-chain anchoring of epoch roots lets any verifier with the disclosed payload and Merkle proof check the record independently, without pre-agreeing on a trusted intermediary. The on-chain footprint is minimal: each anchor stores a 32-byte epoch root and a back-pointer, and no event content touches the chain. We evaluate the system across five cumulative ablation configurations on synthetic agent workloads. The full system adds ~48 microseconds median per-event latency and 512 bytes per event. L2 anchoring costs $2.30 per 100K events at 100-event epochs. The full integrity stack detects edit, delete, reorder, and fork tampering at 100% with zero false positives. Structured forensic queries achieve 1.0 precision on guardrail and delegation lookups where unstructured text search yields 0.013 and 0.077 respectively.

Abstract

AI Agent Auditing

Explore similar work

Agent Flight Recorder: Tamper-Evident Audit Trails with On-Chain Anchoring for Long-Horizon Tool-Using Agents

ClaimReceipt: Verifying Evidence Sufficiency and Coverage in Agent Evaluations

Evidence-First Agentic Verification