# SHA-256

> Prove SHA-256 hashes in zero knowledge: all 64 rounds of the FIPS 180-4 compression function per block, with padding and block chaining in your program.

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

The SHA-256 chiplet proves the 64 rounds of the SHA-256 compression function, FIPS 180-4 §6.2.2, on one 512-bit block,
from an input state to an output state. The [RSA chiplet](https://oumuamua.dev/primitives/signatures/rsa) hashes its message through it.

## What the proof states

The host program requests (state_in, block) → state_out once per block over the `sha256_rounds` bus and applies the
feed-forward addition h_out = h_in + state_out itself, through `CpuSha256Block`. The chiplet constrains the rounds
over bit-expanded 32-bit columns, with one committed carry word per 32-bit addition, Ch and Maj committed, and
composition degree 2.

- **Rounds per row:** 1, 2, 4, 8 or 16, each a divisor of 64; a block takes 64 / rounds_per_row rows.

## Padding and chaining

Both belong to the host program. The [README's Usage section][usage] pads the message in host code with `pad_message`,
pins the first block's h_in to the initial hash value with boundary constraints, and constrains every later block's
h_in to equal the previous block's h_out. The digest is the last block's h_out, which the program publishes.

## Outside the proof

- **SHA-224, SHA-384, SHA-512 and SHA-512/t.**
- **Message padding**, unless the host program constrains it.

## Examples

[`hekate/examples/sha256.rs`][example] scales SHA-256 with the chiplet mounted inline in the CPU trace. From a hekate checkout:

```bash
HEKATE_NUM_VARS=21 HEKATE_ROUNDS_PER_ROW=4 just example sha256 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 SHA-256 statement: the prover knows a 56-byte message whose SHA-256
digest is the published value. It hashes the two-block example message of FIPS 180-2, Appendix B.2, at two rounds per
row, in three files:

- `src/program.rs` mounts the chiplet, pins the first block's input to the initial hash value, chains the second block
  to the first, pins every padding word of a 56-byte message and publishes the digest. It refuses a length that is not
  a multiple of 4 bytes, because a word that mixes message bytes and padding cannot be pinned whole.
- `src/trace.rs` runs the two compressions on the host and fills the table, with the chiplet's columns appended.
- `src/main.rs` proves and verifies.

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

```rust src/program.rs:1
use hekate_core::config::Config;
use hekate_core::errors;
use hekate_core::trace::ColumnType;
use hekate_math::{Block128, TowerField};
use hekate_program::FixedShape;
use hekate_program::circuit::{Circuit, CircuitProgram, Col};
use hekate_sha2::{BLOCK_WORDS, CpuSha256Block, IV, ROUNDS, Sha256Chiplet, pad_message};

const ROUNDS_PER_ROW: usize = 2;
pub const ROWS_PER_BLOCK: usize = ROUNDS / ROUNDS_PER_ROW;

pub const CPU_ACTIVE: usize = CpuSha256Block::COLUMNS;
pub const CPU_CARRY: usize = CPU_ACTIVE + 1;
pub const CPU_CHAIN: usize = CPU_CARRY + 1;

pub type F = Block128;

pub fn table_rows(num_blocks: usize, config: &Config) -> usize {
    (num_blocks * ROWS_PER_BLOCK)
        .next_power_of_two()
        .max(config.min_table_rows())
}

pub fn cpu_layout() -> Vec<ColumnType> {
    let mut layout = CpuSha256Block::layout().to_vec();
    layout.extend([ColumnType::Bit; 3]);

    layout
}

pub fn build_program(
    message_len: usize,
    num_rows: usize,
) -> errors::Result<(CircuitProgram<F>, CpuSha256Block, Sha256Chiplet<F>)> {
    if !message_len.is_multiple_of(size_of::<u32>()) {
        return Err(errors::Error::Protocol {
            protocol: "sha256",
            message: "padding is pinned per word: the message length must be a multiple of 4",
        });
    }

    let message_words = message_len / size_of::<u32>();
    let padded = pad_message(&vec![0; message_len]);
    let num_blocks = padded.len();

    let chiplet = Sha256Chiplet::<F>::new(num_rows, num_blocks, ROUNDS_PER_ROW)?;

    let mut cx = Circuit::<F>::new("Sha256Inline", num_rows)?;

    let block = CpuSha256Block::declare(&mut cx, 0);
    let active = cx.column(ColumnType::Bit);
    let carry = cx.column(ColumnType::Bit);
    let chain = cx.column(ColumnType::Bit);

    block.connect(&mut cx, active)?;

    cx.fix(active, cadence(num_blocks, |off| off == 0));
    cx.fix(carry, cadence(num_blocks, |off| off + 1 < ROWS_PER_BLOCK));
    cx.fix(
        chain,
        cadence(num_blocks - 1, |off| off + 1 == ROWS_PER_BLOCK),
    );

    for (h_in, &iv) in block.h_in_words.iter().zip(&IV) {
        cx.boundary(h_in, 0, F::from(u128::from(iv)));
    }

    for (b, words) in padded.iter().enumerate() {
        let row = b * ROWS_PER_BLOCK;
        let taken = message_words.saturating_sub(b * BLOCK_WORDS);

        for (msg, &word) in block.msg.iter().zip(words).skip(taken) {
            cx.boundary(msg, row, F::from(u128::from(word)));
        }
    }

    let cs = cx.cs();
    let col = |c: Col| cs.col(c.index());
    let next = |c: Col| cs.next(c.index());
    let carry = col(carry);
    let chain = col(chain);

    for (h_in, h_out) in block.h_in_words.iter().zip(block.h_out_words.iter()) {
        let word = col(h_out);

        cs.assert_zero_when(carry, next(h_out) + word);
        cs.assert_zero_when(chain, next(h_in) + word);
    }

    for h_out in block.h_out_words.iter() {
        cx.publish(h_out, (num_blocks - 1) * ROWS_PER_BLOCK);
    }

    cx.mount(chiplet.def()?);

    Ok((cx.compile()?, block, chiplet))
}

fn cadence(count: usize, pred: impl Fn(usize) -> bool) -> FixedShape<F> {
    let values = (0..ROWS_PER_BLOCK)
        .map(|off| if pred(off) { F::ONE } else { F::ZERO })
        .collect();

    FixedShape::Cadence {
        stride: ROWS_PER_BLOCK,
        count,
        origin: 0,
        values,
    }
}
```

```rust src/trace.rs:1
use crate::program::{CPU_ACTIVE, CPU_CARRY, CPU_CHAIN, F, ROWS_PER_BLOCK, cpu_layout};
use hekate_core::errors;
use hekate_core::trace::{ColumnTrace, TraceBuilder};
use hekate_math::{Bit, TowerField};
use hekate_sha2::{CpuSha256Block, IV, STATE_WORDS, Sha256Call, Sha256Chiplet, pad_message};

pub fn compressions(message: &[u8]) -> (Vec<Sha256Call>, [u32; STATE_WORDS]) {
    let blocks = pad_message(message);
    let mut calls = Vec::with_capacity(blocks.len());
    let mut h = IV;

    for block in blocks.iter() {
        let call = Sha256Call {
            h_in: h,
            block: *block,
        };

        h = call.h_out();

        calls.push(call);
    }

    (calls, h)
}

pub fn combined_trace(
    block: &CpuSha256Block,
    chiplet: &Sha256Chiplet<F>,
    calls: &[Sha256Call],
) -> errors::Result<ColumnTrace> {
    let num_vars = chiplet.num_rows().trailing_zeros() as usize;
    let mut tb = TraceBuilder::new_secret(&cpu_layout(), num_vars)?;

    for (b, call) in calls.iter().enumerate() {
        let first_row = b * ROWS_PER_BLOCK;
        let last_row = first_row + ROWS_PER_BLOCK - 1;

        for row in first_row..=last_row {
            block.write(&mut tb, row, call)?;
        }

        tb.set_bit(CPU_ACTIVE, first_row, Bit::ONE)?;

        for row in first_row..last_row {
            tb.set_bit(CPU_CARRY, row, Bit::ONE)?;
        }

        if b + 1 < calls.len() {
            tb.set_bit(CPU_CHAIN, last_row, Bit::ONE)?;
        }
    }

    let mut trace = tb.build();

    for col in chiplet.trace(calls)?.into_columns() {
        trace.add_column(col)?;
    }

    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_program::digest::program_id;
use hekate_program::{ProgramInstance, ProgramWitness};
use hekate_prover_sys::prove;
use hekate_sdk::preflight;
use hekate_sha2::{STATE_WORDS, digest_bytes};
use hekate_verifier::HekateVerifier;
use program::{F, build_program, table_rows};
use rand::{TryRng, rngs::SysRng};
use std::error::Error;
use trace::{combined_trace, compressions};

const LABEL: &[u8] = b"sha256";
const MESSAGE: &[u8] = b"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq";

fn main() -> Result<(), Box<dyn Error>> {
    let (calls, digest) = compressions(MESSAGE);

    let config = Config::default();
    let rows = table_rows(calls.len(), &config);
    let (program, block, chiplet) = build_program(MESSAGE.len(), rows)?;

    let inputs = digest.iter().map(|&word| F::from(u128::from(word)));
    let instance = ProgramInstance::new(rows, inputs.collect());

    let witness = ProgramWitness::new(combined_trace(&block, &chiplet, &calls)?);

    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());
    }

    println!("digest {}", hex(&digest));
    println!("the verifier accepts the proof");

    Ok(())
}

fn hex(digest: &[u32; STATE_WORDS]) -> String {
    digest_bytes(digest)
        .iter()
        .map(|byte| format!("{byte:02x}"))
        .collect()
}
```

The verifier sees only the digest; the message stays in the witness. The program prints the same digest that
`shasum -a 256` gives for the test message:

```output
digest 248d6a61d20638b8e5c026930c3e6039a33ce45964ff2167f6ecedd419db06c1
the verifier accepts the proof
```

## 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 |
|:---|:---|:---|:---|:---|:---|
| SHA-256, 2^11 rows | 2.5 KB | 56 ms | 3.2 ms | 522 KiB | 60 MiB |
| SHA-256, 2^21 rows | 8.4 MB | 8.37 s | 10.8 ms | 5,480 KiB | 5,096 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-sha2` 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 SHA-256 of one message
with one compression per host row, and the API reference is on docs.rs.

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