Skip to main content

Hash Gadgets: Poseidon, Sinsemilla, SHA-256

1. Why this chapter exists​

The three hash chips in halo2_gadgets exist because no single hash function dominates in the in-circuit setting. Poseidon is the cheapest algebraic hash; Sinsemilla is purpose-built for Pallas-curve commitments and used in the Orchard Merkle tree; SHA-256 is required by Bitcoin / Zcash interop and uses the lookup-heavy table16 chip. Each one is a case study in a different chip architecture. If you ever add a new hash chip, the patterns here are the templates to copy.

2. Definitions​

Definition (Algebraic hash). A hash whose round function is a low-degree polynomial in the field. Cheap inside a circuit because each round becomes one (or a few) gates. Poseidon is the canonical example.

Definition (Sponge construction). A hash mode that absorbs input in RATE-sized chunks and squeezes output in similar chunks. Halo 2's Poseidon API exposes the sponge as Sponge<F, S, T, RATE>, where T is the state width and RATE = T - 1 for the standard variant.

Definition (Sinsemilla). A SNARK-friendly hash family designed by Bowe and Hopwood, optimized for the Pallas curve. The hash absorbs a message as a sequence of KK-bit chunks and accumulates the running point PP as P←P+QiP \leftarrow P + Q_i where QiQ_i is a precomputed generator indexed by the chunk. The construction is in ZIP 224.

Definition (Merkle path verification). Given a root rr, a leaf value ℓ\ell, and a sibling list, the gadget computes root(path, leaf) and constrains it equal to rr. Halo 2's implementation in halo2_gadgets::sinsemilla::merkle uses Sinsemilla as the underlying hash, hence MerkleCRH.

Definition (SHA-256 table16 chip). An in-circuit implementation of SHA-256 that uses a 16-bit "spread table" to turn bitwise XOR / AND operations into lookups, dramatically reducing the per-bit constraint cost.

3. The code​

3.1 The Spec trait (halo2_poseidon)​

halo2_poseidon/src/lib.rs

/// The type used to hold the MDS matrix and its inverse.
pub type Mds<F, const T: usize> = [[F; T]; T];

/// A specification for a Poseidon permutation.
pub trait Spec<F: Field, const T: usize, const RATE: usize>: fmt::Debug {
    /// The number of full rounds for this specification.
    ///
    /// This must be an even number.
    fn full_rounds() -> usize;

    /// The number of partial rounds for this specification.
    fn partial_rounds() -> usize;

    /// The S-box for this specification.
    fn sbox(val: F) -> F;

    /// Side-loaded index of the first correct and secure MDS that will be generated by
    /// the reference implementation.
    ///
    /// This is used by the default implementation of [`Spec::constants`]. If you are
    /// hard-coding the constants, you may leave this unimplemented.
    fn secure_mds() -> usize;

    /// Generates `(round_constants, mds, mds^-1)` corresponding to this specification.
    fn constants() -> (Vec<[F; T]>, Mds<F, T>, Mds<F, T>);
}

/// Generates `(round_constants, mds, mds^-1)` corresponding to this specification.
pub fn generate_constants<
    F: FromUniformBytes<64> + Ord,
    S: Spec<F, T, RATE>,
    const T: usize,
    const RATE: usize,
>() -> (Vec<[F; T]>, Mds<F, T>, Mds<F, T>) {
    let r_f = S::full_rounds();
    let r_p = S::partial_rounds();

    let mut grain = grain::Grain::new(SboxType::Pow, T as u16, r_f as u16, r_p as u16);

    let round_constants = (0..(r_f + r_p))
        .map(|_| {
            let mut rc_row = [F::ZERO; T];
            for (rc, value) in rc_row
                .iter_mut()
                .zip((0..T).map(|_| grain.next_field_element()))
            {
                *rc = value;
            }
            rc_row
        })
        .collect();

    let (mds, mds_inv) = mds::generate_mds::<F, T>(&mut grain, S::secure_mds());

    (round_constants, mds, mds_inv)
}

/// Runs the Poseidon permutation on the given state.
///
/// Exposed for testing purposes only.
#[cfg(feature = "test-dependencies")]
pub fn test_only_permute<F: Field, S: Spec<F, T, RATE>, const T: usize, const RATE: usize>(
    state: &mut State<F, T>,
    mds: &Mds<F, T>,
    round_constants: &[[F; T]],
) {
    permute::<F, S, T, RATE>(state, mds, round_constants);
}

/// Runs the Poseidon permutation on the given state.
pub(crate) fn permute<F: Field, S: Spec<F, T, RATE>, const T: usize, const RATE: usize>(
    state: &mut State<F, T>,
    mds: &Mds<F, T>,
    round_constants: &[[F; T]],
) {
    let r_f = S::full_rounds() / 2;
    let r_p = S::partial_rounds();

    let apply_mds = |state: &mut State<F, T>| {
        let mut new_state = [F::ZERO; T];
        // Matrix multiplication
        #[allow(clippy::needless_range_loop)]
        for i in 0..T {
            for j in 0..T {
                new_state[i] += mds[i][j] * state[j];

A Spec<F, T, RATE> implementation provides:

  • full_rounds(), partial_rounds(): round counts.
  • sbox(val) -> F: the S-box.
  • secure_mds(): choice of MDS matrix.
  • constants(): the round constants.

The crate ships P128Pow5T3 which is the parameters Orchard uses.

3.2 The Pow5Chip (in-circuit Poseidon)​

halo2_gadgets/src/poseidon/pow5.rs
}

/// A Poseidon chip using an $x^5$ S-Box.
///
/// The chip is implemented using a single round per row for full rounds, and two rounds
/// per row for partial rounds.
#[derive(Debug)]
pub struct Pow5Chip<F: Field, const WIDTH: usize, const RATE: usize> {
    config: Pow5Config<F, WIDTH, RATE>,
}

impl<F: Field, const WIDTH: usize, const RATE: usize> Pow5Chip<F, WIDTH, RATE> {
    /// Configures this chip for use in a circuit.
    ///
    /// # Side-effects
    ///
    /// All columns in `state` will be equality-enabled.
    //
    // TODO: Does the rate need to be hard-coded here, or only the width? It probably
    // needs to be known wherever we implement the hashing gadget, but it isn't strictly
    // necessary for the permutation.
    pub fn configure<S: Spec<F, WIDTH, RATE>>(
        meta: &mut ConstraintSystem<F>,
        state: [Column<Advice>; WIDTH],
        partial_sbox: Column<Advice>,
        rc_a: [Column<Fixed>; WIDTH],
        rc_b: [Column<Fixed>; WIDTH],
    ) -> Pow5Config<F, WIDTH, RATE> {
        assert_eq!(RATE, WIDTH - 1);
        // Generate constants for the Poseidon permutation.
        // This gadget requires R_F and R_P to be even.
        assert!(S::full_rounds() & 1 == 0);
        assert!(S::partial_rounds() & 1 == 0);
        let half_full_rounds = S::full_rounds() / 2;
        let half_partial_rounds = S::partial_rounds() / 2;
        let (round_constants, m_reg, m_inv) = S::constants();

        // This allows state words to be initialized (by constraining them equal to fixed
        // values), and used in a permutation from an arbitrary region. rc_a is used in
        // every permutation round, while rc_b is empty in the initial and final full
        // rounds, so we use rc_b as "scratch space" for fixed values (enabling potential
        // layouter optimisations).
        for column in iter::empty()
            .chain(state.iter().cloned().map(Column::<Any>::from))
            .chain(rc_b.iter().cloned().map(Column::<Any>::from))
        {
            meta.enable_equality(column);
        }

        let s_full = meta.selector();
        let s_partial = meta.selector();
        let s_pad_and_add = meta.selector();

        let alpha = [5, 0, 0, 0];
        let pow_5 = |v: Expression<F>| {
            let v2 = v.clone() * v.clone();
            v2.clone() * v2 * v
        };

        meta.create_gate("full round", |meta| {
            let s_full = meta.query_selector(s_full);

            Constraints::with_selector(
                s_full,
                (0..WIDTH)
                    .map(|next_idx| {

The chip implements PoseidonInstructions using the standard x5x^5 S-box and the round constants from halo2_poseidon::p128pow5t3. It allocates WIDTH + 1 advice columns (one per state element plus one for the result of the S-box of the first element); the remaining round operations are folded into compound gates.

3.3 The Poseidon sponge and hash API​

halo2_gadgets/src/poseidon.rs
    }
    *state = chip.permute(&mut layouter, state)?;
    Ok(PoseidonChip::get_output(state))
}

/// A Poseidon sponge.
#[derive(Debug)]
pub struct Sponge<
    F: Field,
    PoseidonChip: PoseidonSpongeInstructions<F, S, D, T, RATE>,
    S: Spec<F, T, RATE>,
    M: SpongeMode,
    D: Domain<F, RATE>,
    const T: usize,
    const RATE: usize,
> {
    chip: PoseidonChip,
    mode: M,
    state: State<PoseidonChip::Word, T>,
    _marker: PhantomData<D>,
}

impl<
        F: Field,
        PoseidonChip: PoseidonSpongeInstructions<F, S, D, T, RATE>,
        S: Spec<F, T, RATE>,
        D: Domain<F, RATE>,
        const T: usize,
        const RATE: usize,
    > Sponge<F, PoseidonChip, S, Absorbing<PaddedWord<F>, RATE>, D, T, RATE>
{
    /// Constructs a new duplex sponge for the given Poseidon specification.
    pub fn new(chip: PoseidonChip, mut layouter: impl Layouter<F>) -> Result<Self, Error> {
        chip.initial_state(&mut layouter).map(|state| Sponge {
            chip,
            mode: Absorbing::init_empty(),
            state,
            _marker: PhantomData::default(),
        })
    }

    /// Absorbs an element into the sponge.
    pub fn absorb(
        &mut self,
        mut layouter: impl Layouter<F>,
        value: PaddedWord<F>,
    ) -> Result<(), Error> {
        let value = match self.mode.absorb(value) {
            Ok(()) => return Ok(()),
            Err(value) => value,
        };

        // We've already absorbed as many elements as we can
        let _ = poseidon_sponge(
            &self.chip,
            layouter.namespace(|| "PoseidonSponge"),

Sponge<F, S, T, RATE> is the in-circuit sponge; Hash<F, S, T, RATE, L> is the convenience type that fixes an absorption mode. The L parameter records the length of a single hash invocation at compile time, which the type system uses to ensure correct padding.

3.4 Sinsemilla: the chip​

halo2_gadgets/src/sinsemilla/chip.rs
        let q_s2 = meta.query_fixed(self.q_sinsemilla2);
        q_s2.clone() * (q_s2 - one)
    }
}

/// A chip that implements 10-bit Sinsemilla using a lookup table and 5 advice columns.
///
/// [Chip description](https://zcash.github.io/halo2/design/gadgets/sinsemilla.html#plonk--halo-2-constraints).
#[derive(Eq, PartialEq, Clone, Debug)]
pub struct SinsemillaChip<Hash, Commit, Fixed, Lookup = PallasLookupRangeCheckConfig>
where
    Hash: HashDomains<pallas::Affine>,
    Fixed: FixedPoints<pallas::Affine>,
    Commit: CommitDomains<pallas::Affine, Fixed, Hash>,
    Lookup: PallasLookupRangeCheck,
{
    config: SinsemillaConfig<Hash, Commit, Fixed, Lookup>,
}

impl<Hash, Commit, Fixed, Lookup> Chip<pallas::Base> for SinsemillaChip<Hash, Commit, Fixed, Lookup>
where
    Hash: HashDomains<pallas::Affine>,
    Fixed: FixedPoints<pallas::Affine>,
    Commit: CommitDomains<pallas::Affine, Fixed, Hash>,
    Lookup: PallasLookupRangeCheck,
{
    type Config = SinsemillaConfig<Hash, Commit, Fixed, Lookup>;
    type Loaded = ();

    fn config(&self) -> &Self::Config {
        &self.config
    }

    fn loaded(&self) -> &Self::Loaded {
        &()
    }
}

impl<Hash, Commit, F, Lookup> SinsemillaChip<Hash, Commit, F, Lookup>
where
    Hash: HashDomains<pallas::Affine>,
    F: FixedPoints<pallas::Affine>,
    Commit: CommitDomains<pallas::Affine, F, Hash>,
    Lookup: PallasLookupRangeCheck,
{
    /// Reconstructs this chip from the given config.
    pub fn construct(config: <Self as Chip<pallas::Base>>::Config) -> Self {
        Self { config }
    }

    /// Loads the lookup table required by this chip into the circuit.
    pub fn load(
        config: SinsemillaConfig<Hash, Commit, F, Lookup>,
        layouter: &mut impl Layouter<pallas::Base>,
    ) -> Result<<Self as Chip<pallas::Base>>::Loaded, Error> {
        // Load the lookup table.
        config.generator_table.load(config.lookup_config, layouter)
    }

    /// Creates the Sinsemilla chip
    ///

SinsemillaChip<Hash, Commit, Fixed, Lookup> is generic over four type parameters because Sinsemilla is used in two flavours (a hash and a commitment) over two domains (MerkleCRH and SinsemillaCommit), each with its own generator table. The hot file chip/hash_to_point.rs contains the inner loop that turns a chunk index into a generator lookup and accumulates the running point. This is the file with the most changes per year in the entire halo2_gadgets crate.

3.5 Sinsemilla-Merkle​

halo2_gadgets/src/sinsemilla/merkle.rs
/// Instructions to check the validity of a Merkle path of a given `PATH_LENGTH`.
/// The hash function used is a Sinsemilla instance with `K`-bit words.
/// The hash function can process `MAX_WORDS` words.
pub trait MerkleInstructions<
    C: CurveAffine,
    const PATH_LENGTH: usize,
    const K: usize,
    const MAX_WORDS: usize,
>:
    SinsemillaInstructions<C, K, MAX_WORDS>
    + CondSwapInstructions<C::Base>
    + UtilitiesInstructions<C::Base>
    + Chip<C::Base>
{
    /// Compute MerkleCRH for a given `layer`. The hash that computes the root
    /// is at layer 0, and the hashes that are applied to two leaves are at
    /// layer `MERKLE_DEPTH - 1` = layer 31.
    #[allow(non_snake_case)]
    fn hash_layer(
        &self,
        layouter: impl Layouter<C::Base>,
        Q: C,
        l: usize,
        left: Self::Var,
        right: Self::Var,
    ) -> Result<Self::Var, Error>;
}

/// Gadget representing a Merkle path that proves a leaf exists in a Merkle tree at a
/// specific position.
#[derive(Clone, Debug)]
pub struct MerklePath<
    C: CurveAffine,
    MerkleChip,
    const PATH_LENGTH: usize,
    const K: usize,
    const MAX_WORDS: usize,
    const PAR: usize,
> where
    MerkleChip: MerkleInstructions<C, PATH_LENGTH, K, MAX_WORDS> + Clone,
{
    chips: [MerkleChip; PAR],
    domain: MerkleChip::HashDomains,
    leaf_pos: Value<u32>,
    // The Merkle path is ordered from leaves to root.
    path: Value<[C::Base; PATH_LENGTH]>,
}

impl<
        C: CurveAffine,
        MerkleChip,
        const PATH_LENGTH: usize,
        const K: usize,
        const MAX_WORDS: usize,
        const PAR: usize,
    > MerklePath<C, MerkleChip, PATH_LENGTH, K, MAX_WORDS, PAR>
where
    MerkleChip: MerkleInstructions<C, PATH_LENGTH, K, MAX_WORDS> + Clone,

MerkleInstructions defines the per-layer hash, and MerklePath<...>::calculate_root runs the path verification. The level-specific personalization (each Merkle layer absorbs the layer number to prevent attacks across heights) is in hash_to_point.rs.

3.6 SHA-256 table16 chip​

halo2_gadgets/src/sha256/table16.rs
/// Configuration for a [`Table16Chip`].
#[derive(Clone, Debug)]
pub struct Table16Config {
    lookup: SpreadTableConfig,
    message_schedule: MessageScheduleConfig,
    compression: CompressionConfig,
}

/// A chip that implements SHA-256 with a maximum lookup table size of $2^16$.
#[derive(Clone, Debug)]
pub struct Table16Chip {
    config: Table16Config,
    _marker: PhantomData<pallas::Base>,
}

impl Chip<pallas::Base> for Table16Chip {
    type Config = Table16Config;
    type Loaded = ();

    fn config(&self) -> &Self::Config {
        &self.config
    }

    fn loaded(&self) -> &Self::Loaded {
        &()
    }
}

impl Table16Chip {
    /// Reconstructs this chip from the given config.
    pub fn construct(config: <Self as Chip<pallas::Base>>::Config) -> Self {
        Self {
            config,
            _marker: PhantomData,
        }
    }

    /// Configures a circuit to include this chip.
    pub fn configure(
        meta: &mut ConstraintSystem<pallas::Base>,
    ) -> <Self as Chip<pallas::Base>>::Config {
        // Columns required by this chip:
        let message_schedule = meta.advice_column();
        let extras = [
            meta.advice_column(),
            meta.advice_column(),
            meta.advice_column(),
            meta.advice_column(),
            meta.advice_column(),
            meta.advice_column(),
        ];

        // - Three advice columns to interact with the lookup table.
        let input_tag = meta.advice_column();
        let input_dense = meta.advice_column();
        let input_spread = meta.advice_column();

        let lookup = SpreadTableChip::configure(meta, input_tag, input_dense, input_spread);
        let lookup_inputs = lookup.input.clone();

        // Rename these here for ease of matching the gates to the specification.

The Table16Chip decomposes each 32-bit SHA-256 word into two 16-bit halves and uses a 16-bit "spread" lookup (table16/spread_table.rs) to turn bitwise XOR / AND into constant-cost lookups. The chip is feature-gated by unstable-sha256-gadget; if you do not enable that feature, halo2_gadgets::sha256 is empty.

The cost trade-off: a single SHA-256 block costs roughly the order of 2162^{16} table rows (mostly shared across all SHA-256 invocations in the circuit), plus a few thousand gate rows per block.

3.7 Where this fits in Orchard​

Each hash family is chosen for a specific Orchard primitive. See the protocol-context chapter for the underlying definitions; the mapping is:

Orchard primitive (spec)Hash familyChip
NoteCommit^Orchard (the note commitment)SinsemillaCommithalo2_gadgets::sinsemilla::CommitDomain
MerkleCRH^Orchard (per-layer Merkle hash)Sinsemilla hashhalo2_gadgets::sinsemilla::merkle::MerklePath
Commit^ivk (incoming viewing key derivation)SinsemillaCommithalo2_gadgets::sinsemilla::CommitDomain
PRF^nfOrchard(nk, rho) (nullifier scalar)Poseidonhalo2_gadgets::poseidon::Hash over Pow5Chip
Note encryption key derivation KDF^OrchardBlake2b (out-of-circuit)(no in-circuit chip; runs in the wallet)
Sapling-pool / Bitcoin / Zcash interop hashingSHA-256halo2_gadgets::sha256::Table16Chip (feature unstable-sha256-gadget)

This is why Sinsemilla and Poseidon dominate this chapter: every in-circuit Orchard hash is one of those two. SHA-256 is in the crate for legacy and interop reasons (e.g. proving statements about transparent-pool addresses), but Orchard itself does not use it on the proving side.

The Merkle-layer personalization that hash_to_point.rs enforces is what binds a leaf to its layer number; without it, a forged MerklePath could move a commitment up or down the tree. The Orchard tree is fixed-depth MERKLE_DEPTH_ORCHARD = 32; the same constant appears verbatim in sinsemilla/merkle.rs and in the Zcash Protocol Specification's "MerkleCRH^Orchard" section.

The Poseidon Spec that Orchard actually uses is P128Pow5T3 (8 full rounds, 56 partial rounds, x^5 S-box), imported in the chip's tests under the alias OrchardNullifier:

halo2_gadgets/src/poseidon/pow5.rs
    use super::{PoseidonInstructions, Pow5Chip, Pow5Config, StateWord};
    use crate::poseidon::{
        primitives::{self as poseidon, ConstantLength, P128Pow5T3 as OrchardNullifier, Spec},
        Hash,
    };

That alias is the most explicit Orchard reference in the crate; treat it as a flag that whatever the test is exercising will appear in the deployed Orchard circuit.

4. Failure modes​

  • Mismatched Spec. The in-circuit Pow5Chip and the out-of-circuit halo2_poseidon::Hash must use the same Spec. Two Specs with different round constants produce two different hash functions; the circuit will be unprovable.
  • Sinsemilla generator drift. The generator table inside SinsemillaChip must match the spec's fixed bases. Adding a new generator without updating both sides silently changes the hash.
  • Forgetting the Merkle layer personalization. A naive Merkle implementation that hashes only (left || right) is vulnerable to second-preimage attacks across tree heights. Sinsemilla-Merkle absorbs the layer number; do not skip this if you write a new Merkle gadget.
  • Compiling SHA-256 without the feature. A use halo2_gadgets::sha256; will fail to link unless the feature flag is enabled.

5. Spec pointers​

6. Exercises​

  1. Open halo2_poseidon/src/p128pow5t3.rs and identify the round constants and MDS matrix. Note the full_rounds() and partial_rounds() counts; cross-check them against the Poseidon paper.

  2. Run the Poseidon benchmark:

    cargo bench -p halo2_gadgets --bench poseidon

    Identify the dominant cost: gates, lookups, or MSM.

  3. Trace one absorption step inside halo2_gadgets/src/sinsemilla/chip/hash_to_point.rs. Identify the lookup that picks the generator, and the accumulator update.

  4. Build the SHA-256 benchmark with the feature flag:

    cargo bench -p halo2_gadgets --bench sha256 \
        --features unstable-sha256-gadget

    Compare per-block cost against a single Poseidon permutation.

Answers in the code​

  • Exercise 1: P128Pow5T3 has 8 full rounds and 56 partial rounds (for the standard 128-bit security parameters).
  • Exercise 3: the lookup is into the per-domain generator table declared in sinsemilla/chip/generator_table.rs; the accumulator update uses incomplete addition.

7. Further reading​