Anchoring Trust in Agentic AI: A Cost and Security Evaluation of Tamper-Evident Audit Logs

Abstract

If an AI agent’s actions are logged, the log is only useful if nobody can quietly change it afterwards. A hash chain makes edits visible, but a determined insider who holds the signing key can rebuild the whole chain, and someone who simply cuts off the end of the log leaves a chain that still verifies. The standard remedy is to send periodic signed summaries, called anchors, to an outside witness. This paper works out what that costs and what it buys. We implemented a signed hash-chained log with Merkle batches, inclusion and consistency proofs, and an external witness, using real Ed25519 signatures and SHA-256, and attacked it with 300 real rewrites, edits and truncations for each of seven anchoring settings. We prove that the window of records an attacker can alter undetected is exactly the set of records since the last anchor (or last signed checkpoint, if the attacker has no key), and the attacks bore this out in every case. Anchoring cost and window length are tied by a simple invariant: the fraction of time spent anchoring times the window in seconds equals the cost of one anchor. Signing every record cost 54 µs against 8.4 for chain-only logging, but signing every 100 records was within measurement noise of chain-only. A full audit of 100,000 records took about 313 ms, while one Merkle inclusion proof for a million records was 20 hashes and verified in 24 µs. Without a witness, auditors who gossip can still catch a fork, and we give an exact formula for how long that takes. Finally, anchoring right after high-risk records beats uniform anchoring exactly when the high-risk records carry more than their share of the risk, and we give the break-even ratio. Timings come from one machine and the witness latency is modelled.