binius_frontend/compiler/hints/
mod.rs

1// Copyright 2025 Irreducible Inc.
2//! Hint system.
3//!
4//! Hints are deterministic computations that happen on the prover side.
5//!
6//! They can be used for operations that require many constraints to compute but few constraints
7//! to verify.
8
9use std::{
10	collections::HashMap,
11	hash::{DefaultHasher, Hash, Hasher},
12};
13
14use binius_core::Word;
15
16mod big_uint_divide;
17mod big_uint_mod_pow;
18mod mod_inverse;
19mod secp256k1_endosplit;
20
21pub use big_uint_divide::BigUintDivideHint;
22pub use big_uint_mod_pow::BigUintModPowHint;
23pub use mod_inverse::ModInverseHint;
24pub use secp256k1_endosplit::Secp256k1EndosplitHint;
25
26pub type HintId = u32;
27
28/// Hint handler trait for extensible operations.
29///
30/// Each implementor declares a globally unique `NAME`. The registry identifies hints by the
31/// hash of this name (see [`hint_id_of`]), so registering the same hint twice is a no-op
32/// and every gate using the same hint type shares a single handler entry.
33///
34/// # The `dimensions` parameter
35///
36/// Both [`shape`](Hint::shape) and [`execute`](Hint::execute) take a `dimensions: &[usize]`
37/// slice. This is hint-defined parameterization for a single gate — the values the caller
38/// passes when invoking the hint via
39/// [`CircuitBuilder::call_hint`](crate::compiler::CircuitBuilder::call_hint). The same slice
40/// is then handed back to `execute` at witness-generation time.
41///
42/// `dimensions` controls input/output arity: `shape(dimensions) -> (n_in, n_out)` tells the
43/// builder how many wires the gate consumes and produces, and `execute` is later called with
44/// `inputs.len() == n_in` and `outputs.len() == n_out`. A hint whose arity is fixed
45/// (e.g. always 4 inputs / 6 outputs) takes an empty slice and ignores it. A hint that is
46/// parameterized over, say, big-integer limb counts takes those counts as `dimensions`.
47///
48/// Example: `BigUintDivideHint` uses `dimensions = [dividend_limbs, divisor_limbs]` and
49/// computes `(n_in, n_out) = (dividend_limbs + divisor_limbs, dividend_limbs + divisor_limbs)`.
50/// `Secp256k1EndosplitHint` uses an empty `dimensions` and returns `(4, 6)` unconditionally.
51pub trait Hint: Send + Sync + 'static {
52	/// Globally unique name for this hint. Used to derive a stable [`HintId`].
53	const NAME: &'static str;
54
55	/// Compute the gate's input/output arity as a function of `dimensions`.
56	///
57	/// Called once when the gate is emitted by `call_hint` to allocate output wires. The
58	/// returned `(n_in, n_out)` is the contract for the matching [`execute`](Hint::execute)
59	/// call: the builder will provide `n_in` input wires and expect `n_out` outputs.
60	///
61	/// Implementations must be a pure function of `dimensions` and must agree with
62	/// [`execute`](Hint::execute) on the same `dimensions`.
63	fn shape(&self, dimensions: &[usize]) -> (usize, usize);
64
65	/// Compute the hint's outputs from its inputs at witness-generation time.
66	///
67	/// Receives the same `dimensions` slice that was passed to [`shape`](Hint::shape) when the
68	/// gate was emitted. `inputs.len() == n_in` and `outputs.len() == n_out` where
69	/// `(n_in, n_out) == self.shape(dimensions)`. Implementations write all `n_out` output
70	/// slots — including zero-padding when the natural result has fewer significant words.
71	fn execute(&self, dimensions: &[usize], inputs: &[Word], outputs: &mut [Word]);
72}
73
74/// Derive a [`HintId`] from a hint's name.
75///
76/// Hashes the name with `std::hash::DefaultHasher` (fixed seed, deterministic across runs)
77/// and folds the resulting 64-bit value down to 32 bits by XORing its two halves.
78pub fn hint_id_of(name: &str) -> HintId {
79	let mut hasher = DefaultHasher::new();
80	name.hash(&mut hasher);
81	let h = hasher.finish();
82	(h as u32) ^ ((h >> 32) as u32)
83}
84
85/// Object-safe adapter so the registry can store hints behind `Box<dyn _>`.
86///
87/// `Hint` itself is not dyn-compatible because it carries an associated `const NAME`.
88/// A blanket impl adapts any `Hint` to this trait.
89trait ErasedHint: Send + Sync {
90	fn shape(&self, dimensions: &[usize]) -> (usize, usize);
91	fn execute(&self, dimensions: &[usize], inputs: &[Word], outputs: &mut [Word]);
92}
93
94impl<T: Hint> ErasedHint for T {
95	fn shape(&self, dimensions: &[usize]) -> (usize, usize) {
96		<T as Hint>::shape(self, dimensions)
97	}
98
99	fn execute(&self, dimensions: &[usize], inputs: &[Word], outputs: &mut [Word]) {
100		<T as Hint>::execute(self, dimensions, inputs, outputs)
101	}
102}
103
104/// Registry for hint handlers keyed by [`HintId`].
105///
106/// Registration is idempotent: the same hint type always hashes to the same id, so a second
107/// call to [`HintRegistry::register`] with the same concrete type is a no-op.
108pub struct HintRegistry {
109	handlers: HashMap<HintId, Box<dyn ErasedHint>>,
110}
111
112impl HintRegistry {
113	pub fn new() -> Self {
114		Self {
115			handlers: HashMap::new(),
116		}
117	}
118
119	/// Register a hint, returning its stable [`HintId`]. No-op if the same hint is already
120	/// registered.
121	pub fn register<T: Hint>(&mut self, handler: T) -> HintId {
122		let id = hint_id_of(T::NAME);
123		self.handlers.entry(id).or_insert_with(|| Box::new(handler));
124		id
125	}
126
127	/// Compute the `(n_in, n_out)` arity of the hint identified by `hint_id`.
128	pub fn shape(&self, hint_id: HintId, dimensions: &[usize]) -> (usize, usize) {
129		self.handlers[&hint_id].shape(dimensions)
130	}
131
132	pub fn execute(
133		&self,
134		hint_id: HintId,
135		dimensions: &[usize],
136		inputs: &[Word],
137		outputs: &mut [Word],
138	) {
139		self.handlers[&hint_id].execute(dimensions, inputs, outputs);
140	}
141}
142
143impl Default for HintRegistry {
144	fn default() -> Self {
145		Self::new()
146	}
147}
binius_frontend/compiler/hints/mod.rs

binius_frontend/compiler/hints/
mod.rs
