# Keccak-f[1600]

> Prove SHA-3, SHAKE128 and SHAKE256 hashes in zero knowledge with a Keccak-f[1600] circuit; your program chains the sponge over the permutation calls.

- URL: https://oumuamua.dev/primitives/hashing/keccak
- Published: 2026-10-03T10:49:16+07:00
- Updated: 2026-10-11T12:51:24+07:00

The Keccak chiplet proves the Keccak-f[1600] permutation: for every call, the output state is Keccak-f[1600] of the
input state. Host helpers run SHA3-256, SHA3-512, SHAKE128 and SHAKE256 as sponges over the permutation and return the
calls to prove. The [ML-DSA](https://oumuamua.dev/primitives/signatures/mldsa) and [ML-KEM](https://oumuamua.dev/primitives/encryption/mlkem) chiplets hash through it.

## What the proof states

Each call permutes the 1600-bit state, 25 lanes of 64 bits. The host trace holds call k's input lanes on row 25k and
its output lanes on row 25k + 24, and the chiplet proves every output is Keccak-f[1600] of its input.

The state is virtually packed: 25 physical 64-bit columns hold the 1600 state bits, which expand into bits in
registers during constraint evaluation. A layout with one column per bit would need 1600 columns.

## Binding a digest to a message

The permutation is the whole statement. A SHA-3 digest says something about a message only when the host program
chains the calls: each call's input is the previous output with the next message block XORed into its rate lanes, and
the digest is read from the last output. `sha3_256`, `sha3_512`, `shake128` and `shake256` compute the digest and
return the calls in that order; the constraints that tie the calls together belong to the host program.

## Outside the proof

- **Sponge chaining and padding**, which the host program constrains.
- **Other Keccak-based functions.** There are no named helpers for SHA3-224, SHA3-384, Keccak-256 (the
  pre-standard padding Ethereum uses), cSHAKE or KMAC. A host program that builds their sponge, with
  `KeccakSpongeNative` or its own code, can still prove the permutation calls.

## Examples

[`hekate/examples/keccak.rs`][example] mounts the permutation in the CPU trace and publishes the digest as the first
4 lanes of the final state. From a hekate checkout:

```bash
HEKATE_NUM_VARS=20 just example keccak public
```

`HEKATE_NUM_VARS` sets the trace to 2^n rows. `public` builds the variable-time `table-math` prover that the README's
measurements use. Without it the recipe builds the constant-time prover, the one to use when the witness is private.

The program below turns the example into a full SHA3-256 statement: the prover knows a 200-byte message whose SHA3-256
digest is the published value. It takes three files:

- `src/program.rs` mounts the chiplet and adds the constraints that bind the digest to a message. The first call's
  capacity lanes start at zero. The second call's input is the first call's output with the second block XORed into
  the rate: lanes 0 to 7 carry the last 64 message bytes and stay free, lanes 8 to 16 carry the padding (`0x06` in
  lane 8, `0x80` in the top byte of lane 16), and the capacity lanes pass through unchanged. The digest is published
  from the last output.
- `src/trace.rs` writes each call's input and output into the host table and appends the chiplet's columns.
- `src/main.rs` hashes a random message with `sha3_256`, which returns the digest and both calls, then proves and
  verifies.

Start from the crates in [Installation](https://oumuamua.dev/hekate/docs/getting-started/installation) and add `hekate-keccak` and `rand`.

```rust src/program.rs:1
use hekate_core::config::Config;
use hekate_core::errors;
use hekate_keccak::KeccakChiplet;
use hekate_math::{Block128, TowerField};
use hekate_program::chiplet::ChipletDef;
use hekate_program::circuit::{Circuit, CircuitProgram, Col, ColRange};
use hekate_program::constraint::builder::ConstraintSystem;
use hekate_program::{FixedShape, define_columns};

pub const MESSAGE_LEN: usize = 200;
pub const CHAIN_ROW: usize = output_row(0);

const RATE: usize = 136;
const CALLS: usize = MESSAGE_LEN / RATE + 1;

pub type F = Block128;

define_columns! {
    pub HostColumns {
        LANES: [B64; 25],
        SELECTOR: Bit,
        CHAIN_AT: Bit,
    }
}

pub const fn input_row(call: usize) -> usize {
    call * KeccakChiplet::BLOCK_ROWS
}

pub const fn output_row(call: usize) -> usize {
    input_row(call) + KeccakChiplet::BLOCK_ROWS - 1
}

pub fn table_rows(config: &Config) -> usize {
    (CALLS * KeccakChiplet::BLOCK_ROWS)
        .next_power_of_two()
        .max(config.min_table_rows())
}

pub fn build_program(num_rows: usize) -> errors::Result<CircuitProgram<F>> {
    let mut cx = Circuit::<F>::new("keccak-sha3", num_rows)?;

    let host = cx.schema(&HostColumns::build_layout());
    let selector = host.at(HostColumns::SELECTOR);
    let call_values: [Col; 25] = core::array::from_fn(|lane| host.at(HostColumns::LANES + lane));

    cx.call(&KeccakChiplet::service(), &call_values, selector)?;
    cx.fix(
        selector,
        KeccakChiplet::host_selector_shape(KeccakChiplet::BLOCK_ROWS, CALLS),
    );
    cx.mount(ChipletDef::from_air(&KeccakChiplet::new(num_rows, CALLS))?);

    for &lane in &call_values[17..] {
        cx.boundary(lane, input_row(0), F::ZERO);
    }

    cx.fix(
        host.at(HostColumns::CHAIN_AT),
        FixedShape::Sparse(vec![(CHAIN_ROW, F::ONE)]),
    );
    chain(cx.cs(), host);

    let last_output_row = output_row(CALLS - 1);

    for &lane in &call_values[..4] {
        cx.publish(lane, last_output_row);
    }

    cx.compile()
}

fn chain(cs: &ConstraintSystem<F>, host: ColRange) {
    let col = |c: usize| cs.col(host.at(c).index());
    let next = |c: usize| cs.next(host.at(c).index());
    let chain_at = col(HostColumns::CHAIN_AT);

    for i in 8..25 {
        let lane = HostColumns::LANES + i;
        let pad: u64 = match i {
            8 => 0x06,
            16 => 0x80 << 56,
            _ => 0,
        };

        cs.assert_zero_when(
            chain_at,
            next(lane) + col(lane) + cs.constant(F::from(u128::from(pad))),
        );
    }
}
```

```rust src/trace.rs:1
use crate::program::{CHAIN_ROW, HostColumns, input_row, output_row};
use hekate_core::errors;
use hekate_core::trace::{ColumnTrace, TraceBuilder};
use hekate_keccak::{KeccakCall, generate_keccak_trace};
use hekate_math::{Bit, Block64, TowerField};

pub fn generate_combined_trace(
    calls: &[KeccakCall],
    num_rows: usize,
) -> errors::Result<ColumnTrace> {
    let num_vars = num_rows.trailing_zeros() as usize;
    let mut tb = TraceBuilder::new_secret(&HostColumns::build_layout(), num_vars)?;

    for (call, (input, output)) in calls.iter().enumerate() {
        tb.set_b64_array(
            HostColumns::LANES,
            input_row(call),
            &input.map(Block64::from),
        )?;
        tb.set_b64_array(
            HostColumns::LANES,
            output_row(call),
            &output.map(Block64::from),
        )?;

        tb.set_bit(HostColumns::SELECTOR, input_row(call), Bit::ONE)?;
        tb.set_bit(HostColumns::SELECTOR, output_row(call), Bit::ONE)?;
    }

    tb.set_bit(HostColumns::CHAIN_AT, CHAIN_ROW, Bit::ONE)?;

    let inputs: Vec<[Block64; 25]> = calls
        .iter()
        .map(|(input, _)| input.map(Block64::from))
        .collect();

    let mut trace = tb.build();

    for column in generate_keccak_trace(&inputs, num_rows)?.into_columns() {
        trace.add_column(column)?;
    }

    Ok(trace)
}
```

```rust src/main.rs:1
mod program;
mod trace;

use hekate_core::config::Config;
use hekate_crypto::DefaultHasher;
use hekate_crypto::transcript::Transcript;
use hekate_keccak::sha3_256;
use hekate_program::digest::program_id;
use hekate_program::{ProgramInstance, ProgramWitness};
use hekate_prover_sys::prove;
use hekate_sdk::preflight;
use hekate_verifier::HekateVerifier;
use program::{F, MESSAGE_LEN, build_program, table_rows};
use rand::{TryRng, rngs::SysRng};
use std::error::Error;
use trace::generate_combined_trace;

const LABEL: &[u8] = b"keccak-sha3";

fn main() -> Result<(), Box<dyn Error>> {
    let mut message = [0; MESSAGE_LEN];
    SysRng.try_fill_bytes(&mut message)?;

    let (digest, calls) = sha3_256(&message);

    let config = Config::default();
    let num_rows = table_rows(&config);
    let program = build_program(num_rows)?;

    let (lanes, _) = digest.as_chunks::<8>();
    let public_inputs = lanes
        .iter()
        .map(|&lane| F::from(u128::from(u64::from_le_bytes(lane))));
    let instance = ProgramInstance::new(num_rows, public_inputs.collect());

    let witness = ProgramWitness::new(generate_combined_trace(&calls, num_rows)?);

    let report = preflight(&program, &instance, &witness)?;

    if !report.is_clean() {
        eprintln!("{report}");

        return Err("the trace fails preflight".into());
    }

    let mut seed = [0; 32];
    SysRng.try_fill_bytes(&mut seed)?;

    let proof = prove(LABEL, &program, &instance, &witness, &config, seed, None)?;

    let id = program_id::<F, _>(&program)?;
    let mut transcript = Transcript::<DefaultHasher>::new(LABEL);

    let valid = HekateVerifier::<F, DefaultHasher>::verify(
        &id,
        &program,
        &instance,
        &proof,
        &mut transcript,
        &config,
    )?;

    if !valid {
        return Err("the verifier rejects the proof".into());
    }

    let hex: String = digest.iter().map(|byte| format!("{byte:02x}")).collect();

    println!("sha3-256 {hex}");
    println!("the verifier accepts the proof");

    Ok(())
}
```

The message stays in the witness. The padding pins fit the 200 bytes in `MESSAGE_LEN`, and another length fails
preflight until its pins change. [Your First ZK Program](https://oumuamua.dev/hekate/docs/getting-started/your-first-zk-program) binds
single-block messages the same way.

## Performance

Zero-knowledge proofs, measured on Apple M3 Max, 16 cores. Build: `--release`, `std parallel blake3 table-math public`. Best of three on an otherwise idle machine. The [Benchmarks](https://oumuamua.dev/hekate/benchmarks) page has the base-protocol figures and the command for each run.

| Workload | Input | Proving | Verify | Proof size | Peak memory |
|:---|:---|:---|:---|:---|:---|
| Keccak-f\[1600\], 2^15 rows | \~178 KB | 163 ms | 4.7 ms | 852 KiB | 143 MiB |
| Keccak-f\[1600\], 2^20 rows | \~5.4 MB | 3.23 s | 7.0 ms | 3,539 KiB | 2,428 MiB |

## Security

The crate has not been audited and may contain bugs and security flaws, as its README states. Hekate proves 100 bits
of soundness.

## License

`hekate-keccak` is AGPL-3.0-only. Commercial licenses are available from Oumuamua Labs at
[info@oumuamua.dev](mailto:info@oumuamua.dev). The [README's Usage section][usage] builds the permutation calls of one
SHA3-256 hash, and the API reference is on docs.rs.

[example]: https://github.com/oumuamua-labs/hekate/blob/main/hekate/examples/keccak.rs
[usage]: https://github.com/oumuamua-labs/hekate/blob/main/hekate-keccak/README.md#usage