binius_examples/circuits/
ec_msm.rs

1// Copyright 2026 The Binius Developers
2use std::iter;
3
4use anyhow::Result;
5use binius_circuits::{
6	bignum::{BigUint, assert_eq},
7	ecdsa::scalar_mul::msm_strauss_endo,
8	secp256k1::{N_LIMBS, Secp256k1, Secp256k1Affine},
9};
10use binius_core::word::Word;
11use binius_frontend::{CircuitBuilder, WitnessFiller};
12use clap::Args;
13use k256::{
14	ProjectivePoint, Scalar, U256,
15	elliptic_curve::{scalar::FromUintUnchecked, sec1::ToSec1Point},
16};
17use rand::prelude::*;
18
19use crate::ExampleCircuit;
20
21/// Example circuit that computes a multi-scalar multiplication `Σ_i scalars[i] · points[i]` over
22/// secp256k1 with a statically-known number of points, using the GLV fixed-window (Straus)
23/// algorithm (see [`msm_strauss_endo`]).
24///
25/// The points and scalars are public inputs (the points are constrained to lie on the curve), and
26/// the claimed result is a public input that the circuit checks against the in-circuit MSM.
27pub struct EcMsmExample {
28	scalars: Vec<BigUint>,
29	points: Vec<AffinePoint>,
30	expected: AffinePoint,
31}
32
33/// Public input wires for an affine secp256k1 point (assumed not to be the point at infinity).
34struct AffinePoint {
35	x: BigUint,
36	y: BigUint,
37}
38
39impl AffinePoint {
40	fn new_inout(builder: &CircuitBuilder) -> Self {
41		Self {
42			x: BigUint::new_inout(builder, N_LIMBS),
43			y: BigUint::new_inout(builder, N_LIMBS),
44		}
45	}
46}
47
48#[derive(Args, Debug, Clone)]
49pub struct Params {
50	/// Number of (scalar, point) pairs in the multi-scalar multiplication
51	#[arg(short = 'n', long, default_value_t = 2, value_parser = clap::value_parser!(u16).range(1..))]
52	pub n_points: u16,
53	/// Window size in bits for the Straus algorithm (4 is typically optimal)
54	#[arg(short = 'w', long, default_value_t = 4, value_parser = clap::value_parser!(u16).range(1..64))]
55	pub window: u16,
56}
57
58#[derive(Args, Debug, Clone)]
59pub struct Instance {}
60
61impl ExampleCircuit for EcMsmExample {
62	type Params = Params;
63	type Instance = Instance;
64
65	fn build(params: Params, builder: &mut CircuitBuilder) -> Result<Self> {
66		let n_points = params.n_points as usize;
67		let curve = Secp256k1::new(builder);
68
69		let scalars = (0..n_points)
70			.map(|_| BigUint::new_inout(builder, N_LIMBS))
71			.collect::<Vec<_>>();
72		let points = (0..n_points)
73			.map(|_| AffinePoint::new_inout(builder))
74			.collect::<Vec<_>>();
75
76		// Build affine inputs and constrain each to be a valid curve point.
77		let affine_points = points
78			.iter()
79			.map(|p| {
80				let point = Secp256k1Affine {
81					x: p.x.clone(),
82					y: p.y.clone(),
83					is_point_at_infinity: builder.add_constant(Word::ZERO),
84				};
85				curve.assert_on_curve(builder, &point);
86				point
87			})
88			.collect::<Vec<_>>();
89
90		let window = params.window as usize;
91		let result = msm_strauss_endo(builder, &curve, window, &scalars, &affine_points);
92
93		let expected = AffinePoint::new_inout(builder);
94		assert_eq(builder, "msm_result_x", &result.x, &expected.x);
95		assert_eq(builder, "msm_result_y", &result.y, &expected.y);
96
97		Ok(Self {
98			scalars,
99			points,
100			expected,
101		})
102	}
103
104	fn populate_witness(&self, _instance: Instance, w: &mut WitnessFiller<'_>) -> Result<()> {
105		let mut rng = StdRng::seed_from_u64(42);
106		let mut expected = ProjectivePoint::IDENTITY;
107
108		for (scalar, point) in iter::zip(&self.scalars, &self.points) {
109			// Random 256-bit multiplier scalar.
110			let mut scalar_bytes = [0u8; 32];
111			rng.fill(&mut scalar_bytes);
112			let k256_scalar = Scalar::from_uint_unchecked(U256::from_be_slice(&scalar_bytes));
113
114			// Random curve point, generated as `g^r` so that it is guaranteed on-curve.
115			let mut point_seed = [0u8; 32];
116			rng.fill(&mut point_seed);
117			let r = Scalar::from_uint_unchecked(U256::from_be_slice(&point_seed));
118			let p = ProjectivePoint::mul_by_generator(&r);
119			expected += p * k256_scalar;
120
121			scalar.populate_limbs(w, &le_limbs(&num_bigint::BigUint::from_bytes_be(&scalar_bytes)));
122			populate_point(w, &p, &point.x, &point.y);
123		}
124
125		populate_point(w, &expected, &self.expected.x, &self.expected.y);
126
127		Ok(())
128	}
129
130	fn param_summary(params: &Self::Params) -> Option<String> {
131		Some(format!("{}p-w{}", params.n_points, params.window))
132	}
133}
134
135/// Populate the `x` and `y` limb wires from a k256 projective point's affine coordinates.
136fn populate_point(w: &mut WitnessFiller<'_>, p: &ProjectivePoint, x: &BigUint, y: &BigUint) {
137	let bytes = p.to_affine().to_sec1_point(false).to_bytes();
138	// Uncompressed SEC1 encoding: `0x04 || x (32 bytes) || y (32 bytes)`.
139	x.populate_limbs(w, &le_limbs(&num_bigint::BigUint::from_bytes_be(&bytes[1..33])));
140	y.populate_limbs(w, &le_limbs(&num_bigint::BigUint::from_bytes_be(&bytes[33..65])));
141}
142
143/// Decompose a big integer into exactly `N_LIMBS` little-endian 64-bit limbs (zero-padded).
144fn le_limbs(value: &num_bigint::BigUint) -> Vec<u64> {
145	let mut limbs = value.to_u64_digits();
146	assert!(limbs.len() <= N_LIMBS, "value exceeds {N_LIMBS} limbs");
147	limbs.resize(N_LIMBS, 0);
148	limbs
149}
binius_examples/circuits/ec_msm.rs

binius_examples/circuits/
ec_msm.rs
