Hashing and Fiat-Shamir in Recursion

This section uses a width-16/rate-8, degree-4 Poseidon2 configuration to explain hashing in recursive verification and transcript compatibility with native Plonky3. Supported custom configurations also select Poseidon1 or a different geometry; see Configuration.

Overview

Recursive verification requires two distinct uses of the permutation used by the selected prover configuration:

1. Fiat-Shamir Challenger: Derives random challenges from the transcript (commitments, opened values, etc.)
2. MMCS/Merkle Verification: Verifies Merkle tree opening proofs for commitments

In the Poseidon2 example below, both operations use the same underlying permutation, but they interact with it differently:

┌─────────────────────────────────────────────────────────────────────┐
│                    Poseidon2 Permutation (WIDTH=16)                 │
├──────────────────────────────┬──────────────────────────────────────┤
│     Fiat-Shamir Challenger   │        MMCS/Merkle Hashing           │
├──────────────────────────────┼──────────────────────────────────────┤
│ • Duplex sponge construction │ • Compression function               │
│ • Absorb/squeeze pattern     │ • Hash two siblings → parent         │
│ • ~20 calls per verification │ • Hundreds of calls per verification │
│ • Transcript-sensitive       │ • Position-sensitive                 │
└──────────────────────────────┴──────────────────────────────────────┘

The Poseidon2 Permutation

The concrete Poseidon2 example uses:

• WIDTH = 16: The permutation operates on 16 field elements
• RATE = 8: In sponge mode, 8 elements are absorbed/squeezed per permutation

These width-16/rate-8 values describe this example. The selected supported permutation family, geometry, and backend degree depend on the configuration.

Base Field vs Extension Field Views

The same Poseidon2 permutation can be viewed in two equivalent ways:

D=1 View (Base Field)

Input:  [e₀, e₁, e₂, ..., e₁₅]     ← 16 base field elements
Output: [f₀, f₁, f₂, ..., f₁₅]     ← 16 base field elements

D=4 View (Extension Field)

Input:  [E₀, E₁, E₂, E₃]           ← 4 extension field elements
Output: [F₀, F₁, F₂, F₃]           ← 4 extension field elements

where each Eᵢ = eᵢ₀ + eᵢ₁·ω + eᵢ₂·ω² + eᵢ₃·ω³

Both views represent the same Poseidon2 permutation over the base field. The difference is purely representational:

• D=1: Direct representation as 16 base field elements
• D=4: Packed representation as 4 degree-4 extension field elements

The Fiat-Shamir Challenger

Native Plonky3 Behavior

Plonky3's native DuplexChallenger maintains internal state as base field elements:

#![allow(unused)]
fn main() {
struct DuplexChallenger<F, Permutation, const WIDTH: usize, const RATE: usize> {
    sponge_state: [F; WIDTH],        // 16 base field elements
    input_buffer: Vec<F>,            // Pending observations (0..RATE)
    output_buffer: Vec<F>,           // Available samples (0..RATE)
}
}

The challenger implements a duplex sponge construction as follows:

┌────────────────────────────────────────────────────────────────┐
│                     Duplex Sponge Operation                    │
├────────────────────────────────────────────────────────────────┤
│                                                                │
│   observe(value):                                              │
│     1. Clear output_buffer (any pending outputs are invalid)   │
│     2. Push value to input_buffer                              │
│     3. If input_buffer.len() == RATE, apply duplexing:         │
│        • Overwrite state[0..RATE] with input_buffer            │
│        • Apply Poseidon2 permutation                           │
│        • Fill output_buffer from state[0..RATE]                │
│        • Clear input_buffer                                    │
│                                                                │
│   sample():                                                    │
│     1. If input_buffer not empty OR output_buffer empty:       │
│        • Trigger duplexing (same as step 3 above)              │
│     2. Pop and return from output_buffer                       │
│                                                                │
└────────────────────────────────────────────────────────────────┘

Circuit Challenger Design

The recursive circuit operates over extension field elements, but must produce identical transcripts to the native challenger. This requires careful state management.

Conceptually, the Poseidon2 circuit challenger in this example maintains coefficient-level targets. This sketch is not its literal Rust definition:

#![allow(unused)]
fn main() {
struct CircuitChallenger<const WIDTH: usize, const RATE: usize> {
    state: Vec<Target>,           // Targets, (base field coefficients)
    input_buffer: Vec<Target>,    // Pending observations
    output_buffer: Vec<Target>,   // Available samples
    poseidon2_config: Poseidon2Config,
}
}

Each target in state represents a base field element embedded in the extension field (i.e., only the constant coefficient is non-zero).

Duplexing in the Circuit

When the circuit challenger needs to permute, it must bridge between coefficient-level state and the Poseidon2 permutation:

    16 coefficient targets                4 extension targets
    [c₀, c₁, c₂, ..., c₁₅]    ────►     [E₀, E₁, E₂, E₃]
                               recompose
                                  │
                                  ▼
                          ┌─────────────┐
                          │  Poseidon2  │
                          │ Permutation │
                          └─────────────┘
                                  │
                                  ▼
    [c'₀, c'₁, c'₂, ..., c'₁₅]  ◄────   [F₀, F₁, F₂, F₃]
                               decompose

Recomposition (16 coefficients → 4 extension elements):

E₀ = c₀ + c₁·ω + c₂·ω² + c₃·ω³
E₁ = c₄ + c₅·ω + c₆·ω² + c₇·ω³
E₂ = c₈ + c₉·ω + c₁₀·ω² + c₁₁·ω³
E₃ = c₁₂ + c₁₃·ω + c₁₄·ω² + c₁₅·ω³

Decomposition (4 extension elements → 16 coefficients): The inverse operation, extracting basis coefficients from each extension element.

Row Overhead

For this width-16/rate-8, degree-4 example, recomposition/decomposition adds overhead in the primitive tables:

This example adds a total of approximately 70 rows over the different primitive tables per challenger duplexing.

Optimization Note: When using D=1 configuration (base field challenges), no recomposition/decomposition is needed as the state maps directly to the Poseidon2 inputs, eliminating this overhead.

Coexistence on a Single Trace

Both D=1 and D=4 views share the same Poseidon2 AIR trace. The AIR constrains the Poseidon2 permutation over the base field regardless of how inputs/outputs are packed:

┌───────────────────────────────────────────────────────────────────────────────────┐
│                          Poseidon2 AIR Trace (WIDTH=16)                           │
├───────────────────────────────────────────────────────────────────────────────────┤
│                                                                                   │
│  Each row: [s₀, s₁, s₂, s₃, s₄, s₅, s₆, s₇, s₈, s₉, s₁₀, s₁₁, s₁₂, s₁₃, s₁₄, s₁₅] │
│                                                                                   │
│  The AIR constraints enforce the Poseidon2 round function:                        │
│     • S-box application                                                           │
│     • Linear layer (MDS matrix multiplication)                                    │
│     • Round constant addition                                                     │
│                                                                                   │
│  These constraints are identical whether the caller interprets the 16 columns as: │
│     • 16 individual base field elements (D=1), or                                 │
│     • 4 extension field elements of degree 4 (D=4)                                │
│                                                                                   │
└───────────────────────────────────────────────────────────────────────────────────┘

Transcript Compatibility

For recursive verification to be sound, the circuit challenger must produce identical challenge values to the native challenger given the same inputs. This requires:

1. Same observation order: Values must be absorbed in the exact same sequence
2. Same duplexing triggers: Permutation must occur at the same points
3. Same output buffer management: Samples must come from the same buffer positions

Extension Field Operations

The native challenger provides methods for extension field values:

These methods ensure that extension field observations/samples are transcript-compatible.

In addition, when observing opened values in batch verification, we must ensure to respect the order the native verifier performed for the recursive circuit to be able to satisfy the associated constraints.

Configuration

For the Poseidon2 examples here, Poseidon2Config specifies the field and permutation extension degree:

For supported custom WHIR configurations using Poseidon1 or Poseidon2, backend input validation also checks the actual base field and challenge dimension. See Configuration for the supported combinations and matching requirements.