Keccak Channel & Proof Serialization

Custom Fiat-Shamir channel replacing Blake2s with Keccak-256 for EVM-native hashing, and the deterministic proof serialization format.

Overview

The Fiat-Shamir channel transforms an interactive proof protocol into a non-interactive one by deriving all verifier challenges from the proof transcript.

This page covers:

Why we replaced Stwo's Blake2s with Keccak-256
The Rust-side KeccakMerkleChannel implementation
The Solidity-side KeccakChannel library
The deterministic proof serialization format

1. Why Keccak-256?

Stwo uses Blake2s-256 for Merkle hashing and Fiat-Shamir. Ethereum's precompile situation:

Hash	EVM Support	Gas (approx)
Keccak-256	Native opcode	~30 per 32 bytes
SHA-256	Precompile (0x02)	~60 + 12/word
Blake2b	Precompile (0x09, EIP-152)	~12 per round
Blake2s	None	~3,000–5,000 pure Solidity

Blake2s and Blake2b are different algorithms. The EIP-152 precompile gives Blake2b rounds, not Blake2s. A pure-Solidity Blake2s would add millions of gas to verification.

The fix: Stwo's Channel and MerkleChannel traits are generic over the hash function. We implemented a custom KeccakMerkleChannel in Rust that uses Keccak-256 for all hash operations. The Solidity verifier then uses the native keccak256 opcode — ~100x cheaper.

Soundness is preserved: Keccak-256 provides 128-bit collision resistance (same as Blake2s-256). Replacing the hash function in a Fiat-Shamir transform only requires collision resistance and random oracle behavior.

2. Rust Implementation: KeccakMerkleChannel

Core channel state:

pub struct KeccakChannel {
    digest: KeccakHash,    // 32-byte Keccak state
    channel_time: ChannelTime,
}

Mix operations update the digest by hashing current_digest ‖ new_data. Draw operations produce pseudorandom output by hashing digest ‖ nDraws_counter ‖ 0x00.

Leaf hashing encodes each M31 value as 4 little-endian bytes, concatenated across columns:

leaf = keccak256(col0_LE4 ‖ col1_LE4 ‖ ... ‖ colN_LE4)

3. Solidity Implementation: KeccakChannel

struct State {
    bytes32 digest;   // 32-byte Keccak state
    uint32 nDraws;    // draw counter (reset on each mix)
}

Little-Endian Encoding

All integers are encoded as little-endian bytes. Solidity is big-endian natively, requiring explicit byte swapping for every u32:

function _toLEBytes4(uint32 val) private pure returns (bytes4) {
    return bytes4(uint32(
        ((val & 0xFF) << 24) | (((val >> 8) & 0xFF) << 16) |
        (((val >> 16) & 0xFF) << 8) | ((val >> 24) & 0xFF)
    ));
}

Draw QM31 Challenge

function drawSecureFelt(State memory state) internal pure returns (uint128) {
    while (true) {
        uint32[8] memory u32s = drawU32s(state);
        // Rejection sampling: accept only values in [0, 2p)
        bool valid = true;
        for (uint256 i = 0; i < 8; i++) {
            if (uint256(u32s[i]) >= 2 * P) { valid = false; break; }
        }
        if (!valid) continue;
        return qm31FromM31(
            _reduceToM31(u32s[0]), _reduceToM31(u32s[1]),
            _reduceToM31(u32s[2]), _reduceToM31(u32s[3])
        );
    }
}

4. Proof Serialization Format

┌─────────────────────────────────────────────────┐
│ COMMITMENTS        (3 × 32 bytes + headers)      │
├─────────────────────────────────────────────────┤
│ SAMPLED VALUES     (OOD evaluations, QM31 each)  │
├─────────────────────────────────────────────────┤
│ DECOMMITMENTS      (Merkle paths)                │
├─────────────────────────────────────────────────┤
│ QUERIED VALUES     (trace values at query points)│
├─────────────────────────────────────────────────┤
│ PROOF OF WORK      (nonce: 8 bytes LE)           │
├─────────────────────────────────────────────────┤
│ FRI PROOF          (7 layers of commitments,     │
│                     witnesses, decommitments,    │
│                     last-layer polynomial)       │
└─────────────────────────────────────────────────┘

Total proof size (withdrawal circuit): ~4,808 bytes

5. Transcript Replay Order

The Solidity verifier must reproduce the exact same channel state as the Rust prover:

1. Initialize channel (digest = 0, nDraws = 0)
2. mixRoot(commit0)             // Preprocessed tree
3. mixRoot(commit1)             // Trace tree
4. drawSecureFelt()             // composition_random_coeff
5. mixRoot(commit2)             // Composition tree
6. drawSecureFelt()             // → oodsT (OOD point parameter)
7. mixFeltsFlat(sampled_values) // All OOD values as flat M31s
8. drawSecureFelt()             // → friRandomCoeff (α for quotients)
9. ... FRI commitments: mixRoot + drawSecureFelt per layer ...
10. verifyPowNonce(nonce)
11. mixU64(nonce)
12. drawU32s() × ⌈N_QUERIES / 8⌉  // → query positions

Any encoding mismatch (byte order, field element order) causes immediate divergence.

6. Common Pitfalls

Pitfall	Description
Endianness	Every integer must be little-endian — natural in Rust, explicit in Solidity
abi.encodePacked ordering	Must match Rust `hasher.update()` call order exactly
nDraws reset	Every `mix` resets `nDraws` to 0
QM31 element order	$(m_0, m_1, m_2, m_3)$ serialized as `m0_LE4 ‖ m1_LE4 ‖ m2_LE4 ‖ m3_LE4`
Sampled values flattening	Mixed as flat M31 array, not as QM31 elements

Keccak Channel & Proof Serialization

On this page