State Root Chain Approach for ZK Games

An analysis of using cryptographic state root chains for zero-knowledge game verification.

The Approach

Instead of proving facts about a game after it ends, prove each state transition as it happens:

Traditional ZK Game:
  Play game → Game ends → Generate proof of outcome
  
State Root Chain:
  Move 1 → Proof 1 → Move 2 → Proof 2 → ... → Move N → Proof N
     ↓         ↓         ↓         ↓              ↓         ↓
  root_0 → root_1   → root_1 → root_2    →   root_n-1 → root_n

Each proof verifies:

The move is valid given the current state
The state transition is correct
The prover knows the actual state (private input) that hashes to the public root

Advantages

1. Incremental Verification

Approach	When Verification Happens
Traditional	After game ends (must wait)
State Root Chain	After each move (immediate)

Benefits:

Live spectating with real-time proof verification
Dispute resolution mid-game (don't need to finish)
Partial game analysis
Early exit if cheating detected

2. Composable History

Each proof is standalone but chainable:

Proof 5 contains:
  - pre_state_root  (must equal post_state_root from Proof 4)
  - post_state_root (becomes pre_state_root for Proof 6)
  - move details (position, player)

This enables:

Verify move 47 without replaying moves 1-46
Splice verified game segments together
Prove "these 5 moves happened" without revealing others
Aggregate proofs from multiple games

3. Constant-Size Verification

No matter how long the game:

Operation	Complexity
Verify single move	O(1)
Verify chain integrity	O(n) hash comparisons
Storage per move	~256 bytes proof + 64 bytes roots

A 1000-move game doesn't cost more per-move than a 5-move game.

4. On-Chain Efficiency

For blockchain-based games, this is optimal:

contract ZKGame {
    bytes32 public stateRoot;
    IVerifier public moveVerifier;
    
    function makeMove(
        uint256[8] calldata proof,
        uint256[4] calldata publicInputs
    ) external {
        // publicInputs: [preRoot, postRoot, position, player]
        
        // Chain integrity check
        require(
            bytes32(publicInputs[0]) == stateRoot,
            "Pre-root doesn't match current state"
        );
        
        // Verify the ZK proof
        require(
            moveVerifier.verifyProof(proof, publicInputs),
            "Invalid move proof"
        );
        
        // Update state root
        stateRoot = bytes32(publicInputs[1]);
        
        emit MoveMade(publicInputs[2], publicInputs[3]);
    }
}

Gas costs are constant regardless of:

Game length
Board complexity
Move history

The contract only stores one bytes32 - the current state root.

5. Fraud Proofs & Dispute Resolution

If Alice claims the game went one way and Bob claims another:

Alice's version: root_0 → root_1 → root_2 → root_3
Bob's version:   root_0 → root_1 → root_2' → root_3'

Resolution is deterministic:

Find the first divergence point
Both submit their proof for that transition
At most one proof can be valid
Invalid proof = fraud proven
No arbitration needed - just math

6. Privacy Composition

State roots can hide information:

Public:  root_5 = 0x7a3f...
Private: board = [X, O, _, _, X, _, O, _, _]

The root proves the board exists without revealing it.

Combined with selective disclosure:

Reveal only what's needed for each proof
Public inputs are minimal (roots + move)
Private inputs stay private (full board state)

Disadvantages

1. More Proofs Generated

Game Length	Traditional	State Root Chain
5 moves	1 proof	5 proofs
9 moves	1 proof	9 proofs
N moves	1 proof	N proofs

Mitigation: Proofs can be generated in parallel across different games, and modern proving is fast (~100ms per proof with gnark/Groth16).

2. Sequential Dependency Within a Game

❌ Can't generate proof_5 until root_4 exists
❌ No parallelization within a single game
✅ Can parallelize across different games

This is inherent to the chain structure - each link depends on the previous.

3. Hash Function Constraints

MiMC (used in this implementation) adds ~3000 constraints per hash.

Hash Function	Constraints	ZK-Friendly	Notes
MiMC	~3000	✅	Simple, audited
Poseidon	~300	✅	More efficient
Pedersen	~1500	✅	Good for Groth16
SHA256	~25000	❌	Expensive in circuits

Mitigation: Switch to Poseidon for 10x fewer constraints if needed.

4. Storage Overhead

If storing full proof history:

Per move:
  - Proof: ~256 bytes
  - Public inputs: ~128 bytes
  - Metadata: ~50 bytes
  
9-move game: ~4 KB total

Not significant for most applications, but worth noting for high-frequency games.

When to Use State Root Chains

✅ Good Fit

Use Case	Why
On-chain games	Constant gas per move
Tournament play	Verifiable replays, dispute resolution
Live spectating	Real-time verification
Competitive gaming	No "trust me" - proofs for everything
Game replays/analysis	Verify without replaying
Cross-chain games	Portable proofs

❌ Not Ideal

Use Case	Better Alternative
Just prove who won	Single win proof
Hide moves from opponent	Commit-reveal or encrypted state
Extremely high-frequency moves	Optimistic approach with fraud proofs
Privacy of move sequence	Additional encryption layer needed

Architectural Alignment

The state root chain maps perfectly to event sourcing:

Event Sourcing:
  Events:     [e1, e2, e3, e4, ...]
  State:      fold(events) → current_state
  
State Root Chain:
  Moves:      [m1, m2, m3, m4, ...]
  Roots:      [r0, r1, r2, r3, r4, ...]
  Proofs:     [p1, p2, p3, p4, ...]
  
  Each proof verifies: apply(state_n, move_n) → state_n+1

If your system already uses event sourcing (like Petri-pilot does), adding ZK verification is architecturally natural:

Events = Moves with proofs attached
Aggregate = Current state root
Replay = Verify proof chain instead of re-executing

Implementation Notes

Circuit Design

Two circuits work well for games:

Move Circuit (per-move verification):

Public Inputs:
  - pre_state_root
  - post_state_root  
  - position
  - player

Private Inputs:
  - board[9]
  - turn_count

Constraints:
  - hash(board) == pre_state_root
  - board[position] == EMPTY
  - player == (turn_count % 2 == 0 ? X : O)
  - new_board = board with position = player
  - hash(new_board) == post_state_root

Win Circuit (end-game verification):

Public Inputs:
  - state_root
  - winner

Private Inputs:
  - board[9]

Constraints:
  - hash(board) == state_root
  - check_win_patterns(board, winner) == true

Proof Format for Solidity

{
  "a": ["0x...", "0x..."],
  "b": [["0x...", "0x..."], ["0x...", "0x..."]],
  "c": ["0x...", "0x..."],
  "public_inputs": ["0x...", "0x...", "0x...", "0x..."]
}

Directly usable with standard Groth16 verifier contracts.

Conclusion

State root chains trade more proofs for better properties:

Property	Value
Incremental verification	✅
Constant on-chain cost	✅
Composable history	✅
Deterministic disputes	✅
Minimal on-chain storage	✅
Proof generation overhead	⚠️ (acceptable)

For games where verifiability, on-chain efficiency, or dispute resolution matter, it's the right approach.

References

Groth16 - The proving system
MiMC - ZK-friendly hash
Poseidon - More efficient ZK hash
gnark - Go ZK library
Dark Forest - State root chains in production

Live Demo

Try it yourself: pilot.pflow.xyz/zk-tic-tac-toe

Enable ZK Mode
Play a game
Click "Verify Game History"
Inspect each proof to see the chain in action

stackdump/zk-state-root-chain-analysis.md

Select an option

No results found