Ed25519 and Merkle Trees: A Trustless Audit Trail for Autonomous Agents

The claim that needs replacing

Agent-to-agent payment rails are solved. Coinbase’s x402 and Stripe’s Machine Payments Protocol both let one agent pay another without a human in the loop. What none of them address is the question that follows: was the work actually done?

Today the answer comes from the platform that took the payment. That is the same party with the strongest incentive to say yes, and the buyer has no way to check. At small transaction values nobody minds. The moment agents transact at volume, "trust the marketplace" becomes the ceiling on how large those transactions can get.

The alternative is to make execution provable. Every task produces a signed receipt; anyone holding it can verify the signature locally, with no call back to the platform and no account required. The platform is never asked whether the proof is valid — the signature math decides, in the verifier’s own process.

Signing something deterministic

A signature is only as useful as the bytes underneath it. If two implementations serialise the same task differently, they compute different digests and the signature fails for reasons unrelated to authenticity.

So the signable payload is a fixed field set, canonicalised: keys sorted, no whitespace, numbers formatted exactly as JavaScript would emit them.

{"agent_id":"summarization-v1","budget_pence":15000,
 "completed_at":"1785795015650","cost_pence":2,
 "input_hash":"eefcb79a...","output_hash":"4fd36ee7...",
 "started_at":1785795012187,"task_id":"wtask_4cbd33a4..."}

Two details in there cause more cross-language failures than the cryptography does. started_at is a JSON number while completed_at is a string holding the same kind of value — preserve that distinction or the digest changes. And whole floats must serialise without a decimal point: Ruby’s to_json emits 1783860125.0 where JavaScript emits 1783860125, which is a different digest and a failed verification.

The digest is sha256(canonical_json). That is what gets signed — not the raw task, not the output.

Batching, and the ordering that matters

Signing every task individually is straightforward and slow. Batching amortises it: hash each task’s digest as a leaf, build a Merkle tree, sign only the root. One signature covers the batch, and each task carries the sibling path proving its membership.

Verification then has two steps, and their order is the security property:

// 1. does this digest actually belong to the claimed root?
if (!verifyMerkleInclusion(digest, inclusion_proof, root)) return false

// 2. only now, is that root genuinely signed?
return edVerify(signature, root, publicKey)

Reverse those and the scheme collapses. Checking the signature first establishes only that the platform signed some root. It says nothing about whether the digest in front of you is a leaf of that tree — so a valid signature over an unrelated root becomes proof of an arbitrary task. The inclusion check is what binds the two together, and it has to happen before the signature is trusted rather than after.

The walk itself is deliberately dull. Each sibling carries its own position, so ordering is never derived from index arithmetic:

current = leaf_digest
for step in siblings:
    current = sha256_hex(current + step.hash) if step.position == "right" \
              else sha256_hex(step.hash + current)
return current == expected_root

Hashing is over concatenated hex strings, not raw bytes. That is an easy and silent mistake in typed languages, where byte concatenation is the idiomatic choice.

Where implementations actually break

Across twelve language SDKs, none of the real failures were in the cryptography. Every library got Ed25519 right. The breakages were all at the edges:

• Key format. Java and Kotlin’s KeyFactory parses full SPKI DER. CryptoKit, NSec, libsodium and package:cryptography want the raw 32 bytes. Ed25519 SPKI has a fixed-length prefix per RFC 8410, so the raw key is the final 32 bytes of the DER — taking it from a hardcoded offset at the start is the version that breaks.
• Number coercion. Covered above, and responsible for more failed verifications than anything else.
• The unhandled branch. An if covering only the non-batched algorithm, with no else, so batched proofs fall through and report failure without ever being checked.

That last one shipped in all twelve SDKs simultaneously. Not a shared dependency — twelve separate codebases, twelve different crypto libraries, one shared assumption that quietly stopped being true.

Verifying one yourself

Proofs are public and need no key. Pick any task ID and fetch it:

curl https://api.forcedream.ai/v1/workforce/proof/\
  wtask_4cbd33a4104e6a5b05c9/public

curl https://api.forcedream.ai/v1/workforce/proof/public-key

Rebuild the canonical payload, hash it, walk the inclusion path to the root, and check the signature against the published key. If it verifies, that task ran and its inputs and outputs are exactly what the proof says. If someone altered a single field afterwards, it will not.

Any of the twelve SDKs does this in one call, and each one runs the same public conformance suite in CI so their answers cannot quietly diverge. The point is not that our verifier says yes. It is that you never have to ask it.