binius_frontend/compiler/hints/
secp256k1_endosplit.rs

1// Copyright 2025 Irreducible Inc.
2//! Secp256k1 endomorphism split
3//!
4//! The curve has an endomorphism `λ (x, y) = (βx, y)` where `λ³=1 (mod n)`
5//! and `β³=1 (mod p)` (`n` being the scalar field modulus and `p` coordinate field one).
6//!
7//! For a 256-bit scalar `k` it is possible to split it into `k1` and `k2` such that
8//! `k1 + λ k2 = k (mod n)` and both `k1` and `k2` are no farther than `2^128` from zero.
9//!
10//! The `k` scalar is represented by four 64-bit limbs in little endian order. The return value is
11//! quadruple of `(k1_neg, k2_neg, k1_abs, k2_abs)` where `k1_neg` and `k2_neg` are MSB-bools
12//! indicating whether `k1_abs` or `k2_abs`, respectively, should be negated. `k1_abs` and `k2_abs`
13//! are at most 128 bits and are represented with two 64-bit limbs. When `k` cannot be represented
14//! in this way (any valid scalar can, so it has to be modulus or above) both  `k1_abs` and `k2_abs`
15//! are assigned zero values.
16//!
17//! This is a hint - a deterministic computation that happens only on the prover side.
18//! The result should be additionally constrained by using bignum circuits to check that
19//! `k1 + λ k2 = k (mod n)`.
20//!
21//! The method used here comes straight from libsecp256k1, follow the link for derivation:
22//! <https://github.com/bitcoin-core/secp256k1/blob/master/src/scalar_impl.h#L92-L141>
23
24use binius_core::Word;
25use hex_literal::hex;
26use num_bigint::BigUint;
27
28use super::Hint;
29use crate::util::num_biguint_from_u64_limbs;
30
31pub struct Secp256k1EndosplitHint {
32	minus_b1: BigUint,
33	minus_b2: BigUint,
34	g1: BigUint,
35	g2: BigUint,
36	endomorphism_lambda: BigUint,
37	scalar_modulus: BigUint,
38	scalar_modulus_half: BigUint,
39	k1_tight_bound: BigUint,
40	k2_tight_bound: BigUint,
41}
42
43impl Secp256k1EndosplitHint {
44	pub fn new() -> Self {
45		let [
46			minus_b1,
47			minus_b2,
48			g1,
49			g2,
50			endomorphism_lambda,
51			scalar_modulus,
52			k1_tight_bound,
53			k2_tight_bound,
54		] = [
55			hex!("e4437ed6010e88286f547fa90abfe4c3").as_slice(),
56			hex!("fffffffffffffffffffffffffffffffe8a280ac50774346dd765cda83db1562c").as_slice(),
57			hex!("3086d221a7d46bcde86c90e49284eb153daa8a1471e8ca7fe893209a45dbb031").as_slice(),
58			hex!("e4437ed6010e88286f547fa90abfe4c4221208ac9df506c61571b4ae8ac47f71").as_slice(),
59			hex!("5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72").as_slice(),
60			hex!("fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141").as_slice(),
61			hex!("a2a8918ca85bafe22016d0b917e4dd77").as_slice(),
62			hex!("8a65287bd47179fb2be08846cea267ed").as_slice(),
63		]
64		.map(num_bigint::BigUint::from_bytes_be);
65
66		let scalar_modulus_half = &scalar_modulus >> 1;
67
68		Self {
69			minus_b1,
70			minus_b2,
71			g1,
72			g2,
73			endomorphism_lambda,
74			scalar_modulus,
75			scalar_modulus_half,
76			k1_tight_bound,
77			k2_tight_bound,
78		}
79	}
80
81	fn scalar_abs(&self, scalar: BigUint) -> (Word, BigUint) {
82		if scalar > self.scalar_modulus_half {
83			(Word::ALL_ONE, &self.scalar_modulus - scalar)
84		} else {
85			(Word::ZERO, scalar)
86		}
87	}
88}
89
90impl Default for Secp256k1EndosplitHint {
91	fn default() -> Self {
92		Self::new()
93	}
94}
95
96impl Hint for Secp256k1EndosplitHint {
97	const NAME: &'static str = "binius.secp256k1_endosplit";
98
99	fn shape(&self, dimensions: &[usize]) -> (usize, usize) {
100		assert!(dimensions.is_empty(), "Secp256k1EndosplitHint has constant shape");
101		(4, 6)
102	}
103
104	fn execute(&self, dimensions: &[usize], inputs: &[Word], outputs: &mut [Word]) {
105		assert!(dimensions.is_empty(), "Secp256k1EndosplitHint has constant shape");
106
107		assert_eq!(inputs.len(), 4);
108		assert_eq!(outputs.len(), 6);
109
110		let k =
111			num_biguint_from_u64_limbs(inputs.iter().map(|w| w.as_u64())) % &self.scalar_modulus;
112
113		// https://github.com/bitcoin-core/secp256k1/blob/master/src/scalar_impl.h#L92-L141
114		let c1 = div_pow2_round(&k * &self.g1, 384) * &self.minus_b1;
115		let c2 = div_pow2_round(&k * &self.g2, 384) * &self.minus_b2;
116
117		let k2 = (c1 + c2) % &self.scalar_modulus;
118		let k2_lambda = (&k2 * &self.endomorphism_lambda) % &self.scalar_modulus;
119		let k1 = (&self.scalar_modulus - k2_lambda + k) % &self.scalar_modulus;
120
121		// bring the magnitude of k1 & k2 below 2^128 by conditional negation
122		let (k1_neg, mut k1_abs) = self.scalar_abs(k1);
123		let (k2_neg, mut k2_abs) = self.scalar_abs(k2);
124
125		if k1_abs >= self.k1_tight_bound || k2_abs >= self.k2_tight_bound {
126			k1_abs = BigUint::ZERO;
127			k2_abs = BigUint::ZERO;
128		}
129
130		outputs.fill(Word::ZERO);
131
132		outputs[0] = k1_neg;
133		outputs[1] = k2_neg;
134
135		for (output, limb) in outputs[2..4].iter_mut().zip(k1_abs.iter_u64_digits()) {
136			*output = Word::from_u64(limb);
137		}
138
139		for (output, limb) in outputs[4..6].iter_mut().zip(k2_abs.iter_u64_digits()) {
140			*output = Word::from_u64(limb);
141		}
142	}
143}
144
145fn div_pow2_round(value: BigUint, shift: u64) -> BigUint {
146	let increment = if shift == 0 || !value.bit(shift - 1) {
147		BigUint::ZERO
148	} else {
149		BigUint::from(1usize)
150	};
151	(value >> shift) + increment
152}
binius_frontend/compiler/hints/secp256k1_endosplit.rs

binius_frontend/compiler/hints/
secp256k1_endosplit.rs
