State Encoding and Encoders
This document explains how the Valence ZK Coprocessor handles state encoding for zero-knowledge proofs and cross-chain state synchronization. Understanding these concepts is essential for building applications that work across multiple blockchains.
Implementation Status: The state encoding mechanisms described in this document represent the design goals and architecture for the Valence ZK Coprocessor. While the core coprocessor infrastructure exists (as shown in the valence-coprocessor-app template), the full state encoding and cross-chain coordination features are still in active development.
The State Encoding Challenge
The core challenge in ZK coprocessor design lies in encoding state. ZK applications are pure functions that must utilize existing state as arguments to produce an evaluated output state. This means we need a way to compress blockchain state into a format suitable for zero-knowledge proofs.
For any state transition, we can describe it as a pure function: f(A) = B
, where A
is the initial state and B
is the resulting state after applying function f
.
Pure Functions in zkVMs
The Valence ZK Coprocessor leverages zero-knowledge virtual machines (zkVMs) to execute Rust programs and generate proofs of their execution. Specifically, Valence uses a RISC-V zkVM, currently Succinct's SP1. For state encoding purposes, these applications must be structured as pure functions f(x) = y
.
The zkVM workflow for state transitions follows the following pattern:
- Application definition: The state transition logic is written in Rust as a pure function
- Key generation: The compiled application produces a proving key
pk
and verifying keyvk
- Proof generation: Given inputs
x
, the zkVM callsprove(pk, x)
to generate proofp
- Verification: The proof is verified by calling
verify(vk, x, y, p)
This pure function constraint is what necessitates the state encoding mechanisms described in this document - we must compress mutable blockchain state into immutable inputs and outputs suitable for zero-knowledge proving.
Unary Encoder
The Unary Encoder compresses account state transitions into zero-knowledge proofs. It handles the transformation from on-chain state mutations to ZK-provable computations.
Basic State Transition Example
Consider an account with a key-value store that maps addresses to balances. A traditional on-chain transfer function might look like:
#![allow(unused)] fn main() { fn transfer(&mut self, signature: Signature, from: Address, to: Address, value: u64) { assert!(signature.verify(&from)); assert!(value > 0); let balance_from = self.get(&from).unwrap(); let balance_to = self.get(&to).unwrap_or(0); self.insert(from, balance_from.checked_sub(value).unwrap()); self.insert(to, balance_to.checked_add(value).unwrap()); } }
For ZK execution, we can create a trusted version that delegates signature verification to the ZK circuit:
#![allow(unused)] fn main() { fn transfer_trusted(&mut self, from: Address, to: Address, value: u64) { let balance_from = self.get(&from).unwrap(); let balance_to = self.get(&to).unwrap_or(0); self.insert(from, balance_from - value); self.insert(to, balance_to + value); } }
ZK Application Structure
In the current Valence Coprocessor template, ZK applications consist of two components: a controller and a circuit. The controller processes inputs and generates witnesses, while the circuit performs the ZK-provable computation.
Controller (processes JSON inputs and generates witnesses):
#![allow(unused)] fn main() { pub fn get_witnesses(args: Value) -> anyhow::Result<Vec<Witness>> { let (signature, from, to, value) = parse_transfer_args(args); // Verify signature off-chain and prepare witness data signature.verify(&from)?; let witness_data = TransferWitness { from, to, value, initial_state: get_current_state(), }; Ok(vec![Witness::Data(witness_data.encode())]) } }
Circuit (performs ZK computation):
#![allow(unused)] fn main() { pub fn circuit(witnesses: Vec<Witness>) -> Vec<u8> { let witness_data = TransferWitness::decode(witnesses[0].as_data().unwrap()); let mut state = witness_data.initial_state; // Perform trusted transfer (signature already verified in controller) state.transfer_trusted(witness_data.from, witness_data.to, witness_data.value); // Return state commitment for on-chain verification state.commitment().encode() } }
Note: The above examples show the conceptual structure for state encoding. The current template implementation uses simpler examples (like incrementing a counter), as the full state encoding mechanisms are still in development.
On-Chain Verification
When the target chain receives the proof and circuit output, it can verify execution correctness:
#![allow(unused)] fn main() { fn verify(&self, proof: Proof, circuit_output: Vec<u8>) { let current_commitment = self.state.commitment(); // Extract the new state commitment from circuit output let new_commitment = StateCommitment::decode(circuit_output); // Verify the ZK proof proof.verify(&self.vk, &[current_commitment, new_commitment].concat()); // Apply the proven state transition self.state.apply_commitment(new_commitment); } }
Merkleized Encoder
For cross-chain applications, the Merkleized Encoder handles state transition dependencies across multiple domains. This enables parallel execution while maintaining correctness for chains that depend on each other's state.
Cross-Chain State Dependencies
Consider three chains where:
- Chain 1 executes independently
- Chain 2 executes independently
- Chain 3 depends on the result from Chain 1
The Merklelized Encoder creates a Merkle tree structure:
R (Root)
/ \
M1 M2
/ \ / \
C1 C2 C3 0
| | |
Chain1 Chain2 Chain3
Each leaf contains the encoded state transition for its respective chain:
C1
:(S1 → T1), K1
(Chain 1 transition)C2
:(S2 → T2), K2
(Chain 2 transition)C3
:(S3 → T3), K3
(Chain 3 transition, depends on T1)
Parallel and Sequential Execution
The ZK coprocessor can execute proofs in parallel where possible:
- Independent execution: Chain 1 and Chain 2 can execute in parallel
- Sequential dependency: Chain 3 waits for Chain 1's result
T1
- State sharing: Chain 3 receives
T1
and validates the foreign state while processing
Optimized Verification
The Merkle tree structure provides logarithmic verification efficiency. Each chain only needs:
- Its own state transition arguments
- The Merkle path to the root
R
- Any dependent state from other chains
For example, Chain 2 only needs C1
and M2
for its Merkle proof, not the complete state data from Chains 1 and 3.
On-Chain Proof Distribution
Each chain receives the minimal data needed for verification:
- Chain 1:
(R1, T1)
- Chain 2:
(R2, T2)
- Chain 3:
(R3, T3, R1, T1, C2)
Chain 3's verification process includes:
- Verify its own transition:
verify(R3, T3)
- Verify the dependency:
verify(R1, T1)
- Query the foreign state:
query(T1)
- Reconstruct the commitments and validate the Merkle root
This architecture enables the Valence Coprocessor to securely and efficiently coordinate complex cross-chain programs.