AI agents that run shell commands inside containers produce long execution logs. These logs naturally form a tree: a task spawns sub-plans, sub-plans spawn tool calls, and failed attempts sit beside successful retries. Benchmark operators, auditors, and customers increasingly want proof that a claimed result came from a real, untampered run. The people who produced the run often cannot hand over the whole log, because its shape gives away the scaffold's search strategy, how many retries it needed, and which branches it abandoned. The options today are poor. An auditor can read a plaintext log and trust it, as audit harnesses currently do. A Merkle hash tree proves the log is intact but exposes its exact geometry. Padding the tree to a fixed complete shape hides the geometry, but the cost grows exponentially with depth.
We propose signing agent execution trees with structural signatures. These come from Structural signatures for tree data structures, which assigns each node randomized pre-order and post-order numbers. The numbers keep the tree's order relations, so ancestry and sibling order between any two nodes can still be checked, while depth, position, and sibling counts stay hidden. A run owner can then disclose an arbitrary subset of the run, for example the final successful path plus the commands that produced the reported numbers. A verifier can confirm that these pieces belong to one authentic, correctly ordered run, even when intermediate nodes are withheld. Every disclosed command node is also bound to a pinned container image digest, so the verifier can re-execute it and compare output hashes. The resulting claim is checkable: integrity, process ordering, and re-executability can all be verified for a partial disclosure, at a leakage level that we measure with trained attackers rather than assert.
Core Claim
Cryptographic integrity of a log and confidentiality of its shape are usually treated as a trade-off between Merkle proofs and padding. Agent provenance trees are deep, irregular, and unbalanced, which makes that trade-off especially bad. Randomized traversal numbers sidestep it. The property they rely on is that node $u$ is an ancestor of node $v$ exactly when $\mathrm{pre}(u) < \mathrm{pre}(v)$ and $\mathrm{post}(u) > \mathrm{post}(v)$. Here $\mathrm{pre}$ and $\mathrm{post}$ are the randomized pre-order and post-order numbers. They are drawn as random increasing values rather than consecutive integers, so the gaps between them carry no count information.
Because of this property, a verifier can check ancestry and order among disclosed nodes that are not adjacent in the tree. This is the capability that simpler "sign each node with its parent's random ID" schemes lack. We expect the disclosure-time leakage to be close to that of a flat, unlinked set of signed records, while tamper detection approaches that of a full Merkle log. The open question this proposal answers empirically is how close each of those comes.
Positioning
Three groups of prior work shape this proposal.
The first group motivates it. Audit-Grade Harness for Agent-driven Scientific Computation Workflows (SciAgent) runs agents inside more than 25 version-pinned scientific containers. It logs parent–child execution trees to append-only JSONL files and audits them with a fresh-context LLM verifier, meaning a separate model that sees only logs and artifacts. That paper concedes the verifier can be wrong. It also shows a verifier with parent-only visibility returning INSUFFICIENT on a photonics task, and VERIFIED only after recursive access to child logs. Its logs are plaintext with no integrity guarantee and no way to share part of a run. We keep its container discipline and tree-shaped provenance and replace trust-the-log with signed, selectively disclosable proofs. Agent-Diff checks agents by diffing sandbox state before and after a run. That approach is reproducible but blind to the process that produced the final state, and it requires disclosing that state in plaintext.
The second group supplies the method. The Kundu–Bertino structural signatures were evaluated only on static, simulated XML health records, with dynamic updates left open. Our setting is append-only growth of a tree whose final shape is unknown while it is being built. This is a new and harder use of the scheme.
The third group constrains the design. Padding approaches, such as Secure Collaborative Training and Inference for XGBoost (16.7x–178.2x overhead for full obliviousness inside SGX enclaves) and GTree, as well as shuffling approaches such as Constant-Round Private Decision Tree Evaluation for Secret Shared Data (communication exponential in depth, impractical beyond depth 15), all hide shape by making cost grow with depth. SoK: Modular and Efficient Private Decision Tree Evaluation makes the blowup from $m$ to $m'$ nodes explicit. Agent trees routinely exceed depth 15, which is why we do not pad. Finally, A Qualitative Study on the Sources, Impacts, and Mitigation Strategies of Flaky Tests warns that unseeded randomness causes flakiness inside hermetic environments. This constrains how the traversal randomness is generated, as described below.
Research Program
Online signer. We build a signer that plugs into a container harness. We start with Harbor, the orchestration layer from Terminal-Bench, and the SciAgent harness. The central technical problem is assigning randomized traversal numbers online, since a node's post-order number is not known until its subtree closes.
We will compare two designs. The first assigns pre-order numbers from a widely spaced random sequence when a node opens, and post-order numbers when it closes. Order still holds because a node closes only after all of its descendants. The second assigns both numbers by random interval splitting at node creation, so nodes can be signed immediately. The cost is that some parent intervals may run out of room and need re-signing, which is the dynamic-update problem Kundu and Bertino left open. Every node record includes the command, a hash of its standard output and output files, the container image digest, and a timestamp.
The traversal randomness comes from a per-run secret seed held by the run owner. Re-running the signer on the same trace then reproduces the same signatures, avoiding the flakiness concern. Different runs remain unlinkable to anyone without the seed.
Selective disclosure and verification. Given a chosen subset of nodes, the prover sends the node records, their randomized numbers, and the signature material. The verifier checks three things. First, every disclosed node is authentic and belongs to the same signed root. Second, the claimed ancestry and order relations hold. Third, re-executing each disclosed command node in its pinned image reproduces the committed output hash, within a tolerance policy for commands that are known to be nondeterministic.
Completeness. Order checks alone do not reveal that a prover silently withheld a failed child inside a subtree it claims to disclose in full. Completeness is the hardest property, so we will test one small extension: a signed child count that is revealed only for nodes disclosed as "complete." This leaks local branching only where the owner chooses to reveal it.
Leakage analysis. We train attackers to infer hidden properties from disclosures: total tree size, depth, number of retries, which scaffold or model produced the run, and whether the task first failed. The attacks are run on Merkle disclosures, structural-signature disclosures, and unlinked-record disclosures.
Baselines
Do nothing. The naive reference is SciAgent's practice: plaintext JSONL logs handed over in full and read by a fresh-context LLM verifier, run with the same models and containers. This gives maximal leakage and no integrity guarantee. The one figure we can use is SciAgent's reported audit cost of 1.7%–9.9% of total compute, which serves as the budget our cryptographic overhead must be compared against. We do not have a tamper-detection rate for this baseline. No reported result was found on Lacuna for LLM-verifier detection of injected log tampering, so we measure it ourselves.
Merkle provenance. This is the strongest integrity competitor: a Merkle tree over the same execution tree, disclosing the same node subsets with authentication paths. It is the obvious engineering choice and its tamper detection is strong. To beat it, we must match its tamper detection while pushing attacker accuracy on hidden-shape properties close to the chance or prior rate, where Merkle disclosures should let attackers do far better. No reported result was found on Lacuna for Merkle or structural-signature performance on agent traces. Kundu and Bertino report only that verification is "more efficient" than Merkle as data size grows, with no numbers in the file.
Padded complete tree. This is the strongest shape-hiding competitor: the run tree is padded to its maximum depth and branching before Merkle signing, the approach used in the enclave and GPU works above. It is evaluated on the same runs and judged on storage, signing time, and leakage. To beat it, we must reach comparable leakage at linear rather than exponential cost on trees deeper than 15.
Key-ingredient ablation. Each node is signed with a random identifier for itself and for its parent, with no traversal numbers. This isolates whether the order-preserving numbers actually matter. All methods share the same trajectories, containers, hardware, and attacker-training budget.
Why not just…?
Why not just use a Merkle tree? Merkle trees give integrity, but every authentication path reveals depth and sibling hashes. For agent runs this exposes retry counts and branching, which is exactly what scaffold owners want hidden. The question is settled empirically by the shape-inference attacks. If attackers do no better against Merkle disclosures than against ours, the case for this proposal collapses, and we will report that outcome.
Why not just sign each node with random parent links? This is the most serious threat, because it is simpler and hides shape well. Its weakness is that when the owner withholds an intermediate node, the verifier can no longer check that two disclosed nodes are ancestor and descendant, or check their order. A prover can then splice a successful command from another run, or from another branch, under a disclosed plan step. Our tamper suite includes exactly these cross-branch and cross-run splices. If the parent-link scheme catches them at similar rates for the disclosure patterns auditors actually use, we will adopt it and narrow the claim.
Why not just trust a fresh-context LLM verifier or a state diff? SciAgent's own results show the verifier depends on evidence it cannot authenticate: its INSUFFICIENT and VERIFIED verdicts flip with log visibility. State diffs in Agent-Diff and SWE-bench check only outcomes. Neither would detect a forged log claiming cluster execution when the run actually executed locally, which is the deviation SciAgent's own audit flagged on its BRCA1 task. We treat these as complements: the LLM verifier reads only authenticated disclosures, and we measure how much its error rate falls once its inputs are signed.
Proposed Experiments
Data. Trees come from three sources. We collect Terminal-Bench 2.0 runs (89 tasks via Harbor) from two scaffolds and at least two open models. For context on these tasks, Terminal-Bench reports GPT-5.2 with Codex CLI at 62.9% and models below the frontier under 15%. We also use the SciAgent photonics, BRCA1, and CFD tasks, and a sample of the 50,733 TerminalTraj trajectories from Large-Scale Terminal Agentic Trajectory Generation from Dockerized Environments. TerminalTraj supplies a large, diverse corpus for training the attackers.
Tamper suite. We inject five kinds of tampering:
- deleted failed attempts;
- reordered steps;
- splices from other runs or other branches;
- fabricated outputs;
- swapped container digests, which simulate silent fallback to a lower-fidelity image.
Metrics. We report:
- tamper-detection rate per kind;
- attacker accuracy on each hidden property, compared with a predict-the-prior reference;
- signing time per node and proof size as functions of tree depth and size;
- the fraction of disclosed commands that reproduce bit-exactly on re-execution in their pinned image, which also quantifies how much nondeterminism the tolerance policy must absorb.
Decisive checks. First, on trees deeper than 15, the padded baseline's cost should grow exponentially while ours grows linearly. Second, splice detection should separate our scheme from the parent-link ablation. Third, retry-count and scaffold-identity attacks should separate our scheme from Merkle. If none of these three separations appears, randomized traversal numbers add nothing over simpler signing, and the proposal fails.
References
- Structural signatures for tree data structures
- Audit-Grade Harness for Agent-driven Scientific Computation Workflows
- Agent-Diff: Benchmarking LLM Agents on Enterprise API Tasks via Code Execution with State-Diff-Based Evaluation
- Secure Collaborative Training and Inference for XGBoost
- GTree: GPU-friendly Privacy-preserving Decision Tree Training and Inference
- Constant-Round Private Decision Tree Evaluation for Secret Shared Data
- SoK: Modular and Efficient Private Decision Tree Evaluation
- A Qualitative Study on the Sources, Impacts, and Mitigation Strategies of Flaky Tests
- Terminal-Bench: Benchmarking Agents on Hard, Realistic Tasks in Command Line Interfaces
- Large-Scale Terminal Agentic Trajectory Generation from Dockerized Environments