Crypto-Graph Replay: Verifying Agent State Transitions with Merkle Trees in Postgres

When you run a swarm of autonomous agents, you need to know they did what they claim. Logs can be forged, databases can be corrupted, and memory can lie. But if you structure state transitions as a cryptographic graph and store the roots in Postgres, you get something close to a blockchain without the overhead. You get deterministic replay, tamper-evident history, and the ability to prove to a third party that a given agent state is authentic.

In this article, I'll show you how to implement a Merkle tree over state transitions in Postgres, how to replay agent actions deterministically, and how to verify the entire history with a single SQL query. No blockchain. No external service. Just Postgres, a few extensions, and some careful schema design.

Why Merkle Trees?

A Merkle tree is a binary tree where each leaf is a hash of a data block, and each internal node is a hash of its two children. The root hash summarizes the entire dataset. If any leaf changes, the root changes. You can prove that a specific leaf belongs to the tree with a logarithmic-size proof, without revealing the whole dataset.

For agent state transitions, think of each transition as a leaf. The tree's root is a fingerprint of the entire history. Store that root in a table after every transition. If someone alters a past transition, the root won't match, and you'll know.

Why not just hash a chain? Because a chain requires linear verification. With a Merkle tree, you can verify any subset of transitions independently, and you can detect tampering without replaying everything. Also, you can prune old leaves while keeping the root—useful for long-running agents.

Setting Up Postgres

I'm assuming Postgres 16 or later. You'll need the pgcrypto extension for hashing and pg_trgm for some index tricks later. If you want to compute Merkle roots in SQL, you can use a recursive CTE, but for performance, I recommend doing the tree computation in a small stored procedure or in the application layer. For this article, I'll stick to SQL where possible.

CREATE EXTENSION IF NOT EXISTS pgcrypto;
CREATE EXTENSION IF NOT EXISTS pg_trgm;

Schema for State Transitions

We'll represent agent state as a series of transitions. Each transition has an ID, an agent ID, a sequence number, a payload (the state after the transition), and a hash of the payload. We'll also store the Merkle root after each transition.

CREATE TABLE agent_transitions (
    id BIGSERIAL PRIMARY KEY,
    agent_id UUID NOT NULL,
    seq INTEGER NOT NULL,
    payload JSONB NOT NULL,
    payload_hash BYTEA NOT NULL,
    merkle_root BYTEA NOT NULL,
    created_at TIMESTAMPTZ DEFAULT now(),
    UNIQUE (agent_id, seq)
);

The payload is the full state after the transition. It could be a JSON document, a binary blob, or a set of key-value pairs. The payload hash is a SHA-256 of the canonical JSON representation. We'll use pgcrypto's digest function.

CREATE OR REPLACE FUNCTION sha256_hex(data text) RETURNS text AS $$
    SELECT encode(digest(data, 'sha256'), 'hex');
$$ LANGUAGE sql IMMUTABLE STRICT;

Computing the Merkle Root in Postgres

There are several ways to compute a Merkle root. The simplest is to use a recursive CTE that builds the tree level by level. For a small number of leaves (say, up to a few thousand), this is fine. For larger sets, you might want to do it in the application, but let's start with SQL.

Given a set of hashes, the root is computed by repeatedly hashing pairs. If the number of leaves is odd, we duplicate the last one. We can do this with a recursive CTE:

WITH RECURSIVE merkle(level, idx, hash) AS (
    SELECT 0, row_number() OVER (ORDER BY seq) - 1, payload_hash
    FROM agent_transitions
    WHERE agent_id = $1
    UNION ALL
    SELECT level + 1, idx / 2, sha256_hex(hash || COALESCE(lead(hash) OVER (PARTITION BY level ORDER BY idx), hash))
    FROM merkle
    WHERE level < (SELECT ceil(log(2, count(*)))::int FROM agent_transitions WHERE agent_id = $1)
)
SELECT hash FROM merkle WHERE level = (SELECT max(level) FROM merkle);

This is a bit convoluted because window functions in recursive CTEs have limitations. A cleaner approach is to write a PL/pgSQL function that loops. Let's do that for clarity.

CREATE OR REPLACE FUNCTION compute_merkle_root(agent_id UUID) RETURNS BYTEA AS $$
DECLARE
    hashes BYTEA[];
    level BYTEA[];
    next_level BYTEA[];
    i INT;
BEGIN
    SELECT array_agg(payload_hash ORDER BY seq) INTO hashes
    FROM agent_transitions
    WHERE agent_id = compute_merkle_root.agent_id;

    IF hashes IS NULL OR array_length(hashes, 1) = 0 THEN
        RETURN NULL;
    END IF;

    level := hashes;
    WHILE array_length(level, 1) > 1 LOOP
        next_level := '{}';
        i := 1;
        WHILE i <= array_length(level, 1) LOOP
            IF i + 1 <= array_length(level, 1) THEN
                next_level := next_level || digest(level[i] || level[i+1], 'sha256');
            ELSE
                next_level := next_level || digest(level[i] || level[i], 'sha256');
            END IF;
            i := i + 2;
        END LOOP;
        level := next_level;
    END LOOP;
    RETURN level[1];
END;
$$ LANGUAGE plpgsql;

This function takes an agent ID, fetches all payload hashes in order, and builds the Merkle tree iteratively. It's O(n log n) and works fine for thousands of transitions.

Inserting a Transition and Updating the Root

When a new transition occurs, we insert the payload and compute the new Merkle root. To avoid race conditions, we should do this in a transaction with a lock on the agent's transitions. We'll use pg_advisory_xact_lock to serialize writes per agent.

CREATE OR REPLACE FUNCTION add_transition(
    p_agent_id UUID,
    p_payload JSONB
) RETURNS BIGINT AS $$
DECLARE
    new_seq INT;
    new_hash BYTEA;
    new_root BYTEA;
    trans_id BIGINT;
BEGIN
    PERFORM pg_advisory_xact_lock(hashtext(p_agent_id::text));

    SELECT COALESCE(MAX(seq), 0) + 1 INTO new_seq
    FROM agent_transitions
    WHERE agent_id = p_agent_id;

    new_hash := digest(p_payload::text, 'sha256');

    INSERT INTO agent_transitions (agent_id, seq, payload, payload_hash, merkle_root)
    VALUES (p_agent_id, new_seq, p_payload, new_hash, '\x')
    RETURNING id INTO trans_id;

    new_root := compute_merkle_root(p_agent_id);

    UPDATE agent_transitions
    SET merkle_root = new_root
    WHERE agent_id = p_agent_id;

    RETURN trans_id;
END;
$$ LANGUAGE plpgsql;

Note: We insert a placeholder root and then update all rows for that agent with the new root. This is inefficient if you have many transitions, but for typical agent histories (hundreds to thousands), it's acceptable. If you need to scale, you can store the root in a separate table per agent, but then you lose the ability to verify per-row. We'll stick with per-row for simplicity.

Verifying a Transition

To verify that a transition is authentic, we need to recompute the Merkle root from that transition's leaf up to the root, using the stored hashes of sibling nodes. But we don't store sibling hashes. Instead, we can recompute the entire tree from the stored payload hashes. That's O(n) per verification, which is fine for small histories. If you need efficient proofs, you'd store auxiliary data, but that's overkill for most self-hosted systems.

For our purpose, verification means: given an agent ID and a sequence number, we recompute the Merkle root from scratch and compare it to the stored root for that transition. If they match, the transition is authentic.

CREATE OR REPLACE FUNCTION verify_transition(
    p_agent_id UUID,
    p_seq INT,
    p_expected_hash BYTEA DEFAULT NULL
) RETURNS BOOLEAN AS $$
DECLARE
    stored_hash BYTEA;
    stored_root BYTEA;
    computed_root BYTEA;
BEGIN
    SELECT payload_hash, merkle_root INTO stored_hash, stored_root
    FROM agent_transitions
    WHERE agent_id = p_agent_id AND seq = p_seq;

    IF NOT FOUND THEN
        RETURN FALSE;
    END IF;

    IF p_expected_hash IS NOT NULL AND p_expected_hash <> stored_hash THEN
        RETURN FALSE;
    END IF;

    computed_root := compute_merkle_root(p_agent_id);
    RETURN computed_root = stored_root;
END;
$$ LANGUAGE plpgsql;

This function checks that the payload hash matches the expected hash (if provided) and that the recomputed root matches the stored root. If an attacker modified a past payload, the stored hash would change, and the recomputed root would differ from the stored root.

Deterministic Replay

Now, the real power: we can replay an agent's state transitions deterministically. Since each transition payload is the full state, we can simply walk through them in order. But we want to ensure that the replay produces the same state as the original run. We can do this by verifying the chain of hashes.

A naive replay would just apply each payload. But to verify, we need to ensure that each transition's payload is consistent with the previous one. In a well-designed agent, the transition function is deterministic: given the previous state and an action, it produces the next state. We can capture that by storing the previous state hash in the payload, or by using a separate table for actions.

For simplicity, let's assume the payload contains the full state, and we have a function that computes the next state from the previous state and an action. We'll store the action in a separate column, but for this article, we'll just store the state.

To replay, we can do:

CREATE OR REPLACE FUNCTION replay_agent(p_agent_id UUID) RETURNS TABLE(seq INT, state JSONB) AS $$
DECLARE
    rec RECORD;
BEGIN
    FOR rec IN
        SELECT seq, payload
        FROM agent_transitions
        WHERE agent_id = p_agent_id
        ORDER BY seq
    LOOP
        -- Verify that the payload hash matches the stored hash
        IF digest(rec.payload::text, 'sha256') <> (SELECT payload_hash FROM agent_transitions WHERE agent_id = p_agent_id AND seq = rec.seq) THEN
            RAISE EXCEPTION 'Hash mismatch at seq %', rec.seq;
        END IF;
        RETURN QUERY SELECT rec.seq, rec.payload;
    END LOOP;
END;
$$ LANGUAGE plpgsql;

This replay function verifies each payload's hash as it goes. If any hash mismatches, it raises an exception. This ensures that the data wasn't tampered with.

But we can go further: we can verify that the state transitions are deterministic by applying a transition function. Suppose we have a function apply_action(state JSONB, action JSONB) RETURNS JSONB. We can store the action in a separate table, but for now, let's assume the payload includes the action as well.

We can then replay by starting from the first state and applying each action, comparing the result to the stored state. This is the true test of determinism.

Case Study: Auditing a Multi-Agent Swarm

Let's consider a concrete example. You have a swarm of agents that process user requests. Each agent maintains a state that includes a queue of tasks, a set of completed tasks, and a log of decisions. You want to prove to a client that a particular decision was made correctly.

With our schema, you can extract the agent's transition history and compute the Merkle root. You can then provide the root and the relevant transition IDs. The client can verify that the root matches the history, and that the specific transition they care about is part of that history. They don't need to trust you; they can compute the root themselves from the public payload hashes.

This is similar to a blockchain, but without the distributed consensus. You are the sole writer, but you can prove immutability after the fact.

Performance Considerations

Computing the Merkle root on every insert is O(n log n). For agents with thousands of transitions, this is fine. For millions, you'd want to optimize. One approach is to store the tree in a separate table and update only the affected nodes. Another is to use a different data structure, like a hash chain, but that loses the ability to verify subsets.

In practice, agent histories rarely exceed tens of thousands of transitions. Postgres can handle that easily. The function compute_merkle_root is fast enough.

Extending to Cross-Agent Integrity

You can also build a global Merkle tree that spans all agents. This gives you a single root for the entire system. To do that, you'd have leaves that are the roots of each agent's tree. This is useful for proving that the entire system state is consistent.

You can compute this global root in a similar way, by aggregating the per-agent roots.

Security Considerations

• Hash collisions: SHA-256 is collision-resistant. You're safe.
• Timing attacks: The digest function is constant-time? Not necessarily, but for this use case, it's fine.
• SQL injection: Use parameterized queries.
• Permissions: Only allow trusted roles to insert transitions. Use row-level security if needed.

Alternatives to Merkle Trees

• Blockchain: Overkill, slow, expensive.
• Hash chains: Simpler but linear verification, no subset proofs.
• Signed logs: Use a digital signature on each entry. That's also good, but requires key management. Merkle trees give you the same tamper-evidence without per-entry signatures.

Conclusion

Merkle trees in Postgres give you a lightweight, auditable record of agent state transitions. You get deterministic replay, tamper-evidence, and the ability to prove authenticity to third parties—all without leaving your database. This is a powerful tool for self-hosted AI systems where trust and transparency matter.

Next time you build an agent swarm, consider adding a Merkle root to your state transitions. It's a small investment that pays off in trust.