halo2_gadgets and the ECC Chip

1. Why this chapter exists

halo2_proofs gives you the proving system. halo2_gadgets gives you a library of common circuits already written for you. The library has two architectural patterns worth knowing: the chip / instruction-trait split, and the convention that gadgets are written against a trait so multiple chips can satisfy them. The ECC gadget is the canonical example. If you ever write a chip of your own, copy its shape.

2. Definitions

Definition (Chip). A type that owns a Config (a set of columns and gates) and provides typed methods that synthesize assignments using those columns. Defined in chapter 06.

Definition (Instruction trait). A trait whose methods name the operations a chip should provide (e.g. add, mul, witness_point). The gadget code uses only the trait; the trait can be implemented by multiple chips with different column / gate trade-offs.

Definition (Fixed-base scalar multiplication). Computing $[k]G$ for a fixed base point $G$ known at circuit definition time. The chip can precompute a windowed lookup table and constrain the multiplication efficiently.

Definition (Variable-base scalar multiplication). Computing $[k]P$ for a witnessed point $P$. Cannot use precomputed tables; relies on the incomplete-and-then-complete double-and-add gates.

3. The code

3.1 The crate surface

halo2_gadgets/src/lib.rs

//! This crate provides various common gadgets and chips for use with `halo2_proofs`.
//!
//! # Gadgets
//!
//! Gadgets are an abstraction for writing reusable and interoperable circuit logic. They
//! do not create any circuit constraints or assignments themselves, instead interacting
//! with the circuit through a defined "instruction set". A circuit developer uses gadgets
//! by instantiating them with a particular choice of chip.
//!
//! # Chips
//!
//! Chips implement the low-level circuit constraints. The same instructions may be
//! implemented by multiple chips, enabling different performance trade-offs to be made.
//! Chips can be highly optimised by their developers, as long as they conform to the
//! defined instructions.

#![cfg_attr(docsrs, feature(doc_cfg))]
// Catch documentation errors caused by code changes.
#![deny(rustdoc::broken_intra_doc_links)]
#![deny(missing_debug_implementations)]
#![deny(missing_docs)]
#![deny(unsafe_code)]

pub mod ecc;
pub mod poseidon;
#[cfg(feature = "unstable-sha256-gadget")]
#[cfg_attr(docsrs, doc(cfg(feature = "unstable-sha256-gadget")))]
pub mod sha256;
pub mod sinsemilla;
pub mod utilities;

#[cfg(test)]
mod test_circuits;

Four top-level modules:

• ecc: Pallas / Vesta points.
• poseidon: Poseidon sponge.
• sinsemilla: Sinsemilla hash + Merkle path.
• sha256: SHA-256 (feature-gated).
• utilities: shared building blocks (cond_swap, decompose_running_sum, lookup_range_check).

3.2 The EccInstructions trait

halo2_gadgets/src/ecc.rs

/// The set of circuit instructions required to use the ECC gadgets.
pub trait EccInstructions<C: CurveAffine>:
    Chip<C::Base> + UtilitiesInstructions<C::Base> + Clone + Debug + Eq
{
    /// Variable representing a scalar used in variable-base scalar mul.
    ///
    /// This type is treated as a full-width scalar. However, if `Self` implements
    /// [`BaseFitsInScalarInstructions`] then this may also be constructed from an element
    /// of the base field.
    type ScalarVar: Clone + Debug;
    /// Variable representing a full-width element of the elliptic curve's
    /// scalar field, to be used for fixed-base scalar mul.
    type ScalarFixed: Clone + Debug;
    /// Variable representing a signed short element of the elliptic curve's
    /// scalar field, to be used for fixed-base scalar mul.
    ///
    /// A `ScalarFixedShort` must be in the range [-(2^64 - 1), 2^64 - 1].
    type ScalarFixedShort: Clone + Debug;
    /// Variable representing an elliptic curve point.
    type Point: From<Self::NonIdentityPoint> + Clone + Debug;
    /// Variable representing a non-identity elliptic curve point.
    type NonIdentityPoint: Clone + Debug;
    /// Variable representing the affine short Weierstrass x-coordinate of an
    /// elliptic curve point.
    type X: Clone + Debug;
    /// Enumeration of the set of fixed bases to be used in scalar mul.
    /// TODO: When associated consts can be used as const generics, introduce
    /// `Self::NUM_WINDOWS`, `Self::NUM_WINDOWS_BASE_FIELD`, `Self::NUM_WINDOWS_SHORT`
    /// and use them to differentiate `FixedPoints` types.
    type FixedPoints: FixedPoints<C>;

    /// Constrains point `a` to be equal in value to point `b`.
    fn constrain_equal(
        &self,
        layouter: &mut impl Layouter<C::Base>,
        a: &Self::Point,
        b: &Self::Point,
    ) -> Result<(), Error>;

    /// Witnesses the given point as a private input to the circuit.
    /// This allows the point to be the identity, mapped to (0, 0) in
    /// affine coordinates.
    fn witness_point(
        &self,
        layouter: &mut impl Layouter<C::Base>,
        value: Value<C>,
    ) -> Result<Self::Point, Error>;

A few associated types make the trait surface clean:

• Point, NonIdentityPoint, X: witness representations of a curve point and its $x$-coordinate.
• ScalarVar, ScalarFixed, ScalarFixedShort: three scalar widths. The "short" scalar covers values fitting in 64 signed bits and exists so that fixed-base scalar mul for small scalars can be cheaper.
• FixedPoints: an enumeration of all fixed bases the chip supports.

Methods include witness_point, add, add_incomplete, mul, mul_fixed, mul_fixed_short, mul_fixed_base_field_elem, plus a constrain_equal for cross-region equality. Each method is split into one or more rows of a column-dense gate; see the chip impl.

3.3 The EccChip config

halo2_gadgets/src/ecc/chip.rs

        Self {
            x: non_id_point.x,
            y: non_id_point.y,
        }
    }
}

/// Configuration for [`EccChip`].
#[derive(Clone, Debug, Eq, PartialEq)]
#[allow(non_snake_case)]
pub struct EccConfig<
    FixedPoints: super::FixedPoints<pallas::Affine>,
    Lookup: PallasLookupRangeCheck = PallasLookupRangeCheckConfig,
> {
    /// Advice columns needed by instructions in the ECC chip.
    pub advices: [Column<Advice>; 10],

    /// Incomplete addition
    add_incomplete: add_incomplete::Config,

    /// Complete addition
    add: add::Config,

    /// Variable-base scalar multiplication
    mul: mul::Config<Lookup>,

    /// Fixed-base full-width scalar multiplication
    mul_fixed_full: mul_fixed::full_width::Config<FixedPoints>,
    /// Fixed-base signed short scalar multiplication
    mul_fixed_short: mul_fixed::short::Config<FixedPoints>,
    /// Fixed-base mul using a base field element as a scalar
    mul_fixed_base_field: mul_fixed::base_field_elem::Config<FixedPoints, Lookup>,

    /// Witness point
    witness_point: witness_point::Config,

    /// Lookup range check using 10-bit lookup table
    pub lookup_config: Lookup,
}

/// A trait representing the kind of scalar used with a particular `FixedPoint`.

The config records which advice columns and selectors are allocated for each sub-gate. The columns are shared across sub-gates; each selector turns on a different polynomial identity. This is what makes the chip dense.

3.4 The EccChip itself

halo2_gadgets/src/ecc/chip.rs

    /// Returns the Lagrange coefficients for this fixed point.
    fn lagrange_coeffs(&self) -> Vec<[C::Base; H]> {
        compute_lagrange_coeffs(self.generator(), Self::FixedScalarKind::NUM_WINDOWS)
    }
}

/// An [`EccInstructions`] chip that uses 10 advice columns.
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct EccChip<
    FixedPoints: super::FixedPoints<pallas::Affine>,
    Lookup: PallasLookupRangeCheck = PallasLookupRangeCheckConfig,
> {
    config: EccConfig<FixedPoints, Lookup>,
}

impl<FixedPoints: super::FixedPoints<pallas::Affine>, Lookup: PallasLookupRangeCheck>
    Chip<pallas::Base> for EccChip<FixedPoints, Lookup>
{
    type Config = EccConfig<FixedPoints, Lookup>;
    type Loaded = ();

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

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

impl<Fixed: super::FixedPoints<pallas::Affine>, Lookup: PallasLookupRangeCheck>
    UtilitiesInstructions<pallas::Base> for EccChip<Fixed, Lookup>
{
    type Var = AssignedCell<pallas::Base, pallas::Base>;
}

impl<FixedPoints: super::FixedPoints<pallas::Affine>, Lookup: PallasLookupRangeCheck>
    EccChip<FixedPoints, Lookup>
{
    /// Reconstructs this chip from the given config.
    pub fn construct(config: <Self as Chip<pallas::Base>>::Config) -> Self {
        Self { config }
    }

    /// # Side effects
    ///

The chip stores its Config and the parameter type that fixes the set of base points. EccChip::configure is where the sub-gates are declared.

3.5 The sub-gates

Each sub-gate lives in its own file:

• chip/witness_point.rs: enforce the curve equation $y^2 = x^3 + ax + b$ on a witnessed $(x, y)$.
• chip/add_incomplete.rs: incomplete addition, valid when $P \neq Q$ and neither is the identity. Cheaper than the complete formula.
• chip/add.rs: complete addition. Used wherever the inputs are not provably distinct.
• chip/mul.rs: variable-base scalar mul (double-and-add).
• chip/mul_fixed/: fixed-base scalar mul with precomputed windowed tables.

3.6 The shared utilities

halo2_gadgets/src/utilities/lookup_range_check.rs

//! Make use of a K-bit lookup table to decompose a field element into K-bit
//! words.

use halo2_proofs::{
    circuit::{AssignedCell, Layouter, Region},
    plonk::{Advice, Column, ConstraintSystem, Constraints, Error, Selector, TableColumn},
    poly::Rotation,
};
use std::{convert::TryInto, fmt::Debug, marker::PhantomData};

use ff::PrimeFieldBits;

use crate::sinsemilla::{chip::generator_table::GeneratorTableConfig, primitives as sinsemilla};
use pasta_curves::pallas;
use sinsemilla::SINSEMILLA_S;

use super::*;

/// The running sum $[z_0, ..., z_W]$. If created in strict mode, $z_W = 0$.
#[derive(Debug)]
pub struct RunningSum<F: PrimeFieldBits>(Vec<AssignedCell<F, F>>);
impl<F: PrimeFieldBits> std::ops::Deref for RunningSum<F> {
    type Target = Vec<AssignedCell<F, F>>;

    fn deref(&self) -> &Vec<AssignedCell<F, F>> {
        &self.0
    }
}

impl<F: PrimeFieldBits> RangeConstrained<F, AssignedCell<F, F>> {
    /// Witnesses a subset of the bits in `value` and constrains them to be the correct
    /// number of bits.
    ///
    /// # Panics
    ///
    /// Panics if `bitrange.len() >= K`.
    pub fn witness_short<const K: usize, Lookup: LookupRangeCheck<F, K>>(
        lookup_config: &Lookup,
        layouter: impl Layouter<F>,
        value: Value<&F>,
        bitrange: Range<usize>,
    ) -> Result<Self, Error> {
        let num_bits = bitrange.len();
        assert!(num_bits < K);

        // Witness the subset and constrain it to be the correct number of bits.
        lookup_config
            .witness_short_check(
                layouter,
                value.map(|value| bitrange_subset(value, bitrange)),
                num_bits,
            )
            .map(|inner| Self {
                inner,
                num_bits,
                _phantom: PhantomData::default(),
            })
    }
}

LookupRangeCheck is used by ECC and Sinsemilla alike to assert that a witnessed value fits in $K$ bits, using a lookup table of size $2^K$. It is one of the most-touched files in the repo (see hot files in chapter 02); changes here affect many downstream chips.

3.7 Where this fits in Orchard

The ECC chip exists because every consensus-critical Orchard primitive that touches a curve point is constrained through it. See the protocol-context chapter for the underlying definitions; the mapping is:

Orchard primitive (spec)	Operation on Pallas	Chip method
nf = Extract([PRF^nfOrchard(nk, rho) + psi] K^Orchard + cm)	fixed-base mul on $K^{\mathsf{Orchard}}$, complete add, $x$-coord extract	mul_fixed, add, X::from(...)
cv = [v] V^Orchard + [rcv] R^Orchard	fixed-base short-signed mul for $v$, fixed-base mul for $\mathsf{rcv}$, complete add	mul_fixed_short, mul_fixed, add
rk = ak + [alpha] SpendAuthG	variable-base mul + complete add	mul, add
cm = NoteCommit(...) randomness $[\mathsf{rcm}] R^{\mathsf{Note}}$	fixed-base mul, then a Sinsemilla evaluation (chapter 15)	mul_fixed (the ECC half)
Sinsemilla accumulator step $P \leftarrow P + Q_i$ when $P \neq Q_i$	incomplete add (faster, valid by Sinsemilla's pre-image argument)	add_incomplete (used internally by SinsemillaChip)

This is why the chip exposes three scalar types: $v$ is 64-bit signed (hence ScalarFixedShort); $\mathsf{rcv}$ and $\mathsf{rcm}$ are full 255-bit scalars (ScalarFixed); the spend-auth randomizer $\alpha$ is a witnessed full-width scalar (ScalarVar). The short-signed variant exists exclusively to make the value commitment efficient.

The Extract_P operation that turns the nullifier curve point into a field element is implemented as the X associated type on EccInstructions and the Point::extract_p method on EccChip. The reason it exists at all is to let the nullifier fit in a single Pallas base-field element so it can be hashed into the next action's $\rho$.

4. Failure modes

• Using add_incomplete for inputs that may collide. If $P = Q$ or one of them is the identity, the incomplete formula produces a wrong answer with no failure indication; the resulting constraint will hold on a wrong witness. Always use add (complete) unless you have a separate argument for distinctness.
• Forgetting EccChip::config().fixed_bases. Fixed-base scalar mul needs the chip to be configured with the specific base point. Adding a new fixed base requires regenerating the precomputed windowed table.
• Mixing scalar types. ScalarVar, ScalarFixed, and ScalarFixedShort are not interchangeable. Passing a ScalarFixedShort to a method that expects a ScalarFixed is a compile-time error; passing the wrong-width witness to either of them is a runtime constraint failure.
• Skipping range checks on witness scalars. The ECC chip assumes scalars are properly range-checked elsewhere (typically via LookupRangeCheck). Forgetting to range-check a witness scalar leaves the chip open to canonicalization attacks (e.g. scalars exceeding the curve order).

5. Spec pointers

• The Halo 2 Book "Elliptic curve cryptography" chapter derives the in-circuit addition formulas. Section Incomplete and complete addition is the prerequisite reading for chip/add*.rs.
• Zcash Protocol Spec, section 5.4.9 "Pallas and Vesta": the curve constants and group structure.
• Hopwood et al., "Recursive Proof Composition without a Trusted Setup": the recursion framing that motivated the ECC chip's design.

6. Exercises

1. Open halo2_gadgets/src/ecc.rs and identify the difference between Point and NonIdentityPoint. Why does the gadget distinguish them?

2. Read halo2_gadgets/src/ecc/chip/add_incomplete.rs and identify the gate degree. Compare with add.rs's complete-addition gate degree; the increase explains why the incomplete variant exists.

3. Run the ECC tests:

   cargo test --release -p halo2_gadgets ecc

   Identify each integration test and the chip API it exercises.

4. Pick one fixed-base scalar mul test, find the chosen base in the test setup, and confirm the precomputed table for that base lives in halo2_gadgets/src/ecc/chip/constants.rs.

Answers in the code

• Exercise 1: Point includes the identity (as the special encoding $(0, 0)$); NonIdentityPoint is provably not the identity. The split lets the chip pick incomplete addition whenever both arguments are NonIdentityPoint.
• Exercise 2: the incomplete gate has degree 3; the complete gate has degree 6 in halo2's encoding. The 2x degree increase doubles the extended-domain size and roughly doubles prover cost.

7. Further reading

• The Halo 2 Book "Variable-base scalar multiplication" chapter for the full double-and-add walkthrough.