1//! Multi-scalar multiplication over secp256k1 using k256 group arithmetic2//! (`ProjectivePoint` / `AffinePoint` / `Scalar`), instrumented with operation counters.3//!4//! Two algorithms are implemented here from scratch (not taken from k256):5//! * `straus` — Straus/Shamir interleaving with width-w signed-digit (wNAF) recoding,6//! one odd-multiple table per term, projective-projective additions.7//! * `pippenger` — bucket method (Pippenger 1976), c-bit windows, bucket accumulation with8//! mixed (projective + affine) additions and the running-sum trick.9//! The k256 library routines `lincomb` (constant-time GLV + radix-16) and `lincomb_vartime`10//! (GLV + wNAF multiscalar) are also exposed for comparison; they are not instrumented.11//! Scalar recoding is done on `u64` limbs (exact integer arithmetic only).1213use k256::elliptic_curve::group::{Group, GroupEncoding};14use k256::elliptic_curve::ops::{LinearCombination, Reduce};15use k256::elliptic_curve::ff::PrimeField;16use k256::{AffinePoint, CompressedPoint, FieldBytes, ProjectivePoint, Scalar};17use serde::Serialize;18use sha2::{Digest, Sha256};1920#[derive(Serialize, Clone, Copy, Debug, Default)]21pub struct OpCounts {22 /// projective + projective additions (includes additions involving the identity)23 pub adds: u64,24 /// projective + affine (mixed) additions25 pub mixed_adds: u64,26 /// point doublings27 pub doublings: u64,28 /// additions where one operand was the identity (subset of adds + mixed_adds; cheap in math,29 /// full cost in k256's complete formulas)30 pub identity_adds: u64,31}3233impl OpCounts {34 pub fn total(&self) -> u64 {35 self.adds + self.mixed_adds + self.doublings36 }37}3839/// BIP340 `lift_x`: the point with the given x coordinate and even y, if any.40pub fn lift_x(x: &[u8; 32]) -> Option<AffinePoint> {41 let mut c = [0u8; 33];42 c[0] = 2;43 c[1..].copy_from_slice(x);44 let cp = CompressedPoint::from(c);45 AffinePoint::from_bytes(&cp).into_option()46}4748pub fn tagged_hash_prefix(tag: &str) -> [u8; 32] {49 let th = Sha256::digest(tag.as_bytes());50 let mut out = [0u8; 32];51 out.copy_from_slice(&th);52 out53}5455/// e = int(tagged_hash("BIP0340/challenge", r || pk || msg)) mod n56pub fn challenge(th: &[u8; 32], r: &[u8; 32], pk: &[u8; 32], msg: &[u8]) -> Scalar {57 let h = Sha256::new()58 .chain_update(th)59 .chain_update(th)60 .chain_update(r)61 .chain_update(pk)62 .chain_update(msg)63 .finalize();64 let mut b = [0u8; 32];65 b.copy_from_slice(&h);66 <Scalar as Reduce<FieldBytes>>::reduce(&FieldBytes::from(b))67}6869pub fn scalar_from_bytes_strict(b: &[u8]) -> Option<Scalar> {70 let mut a = [0u8; 32];71 a.copy_from_slice(b);72 Scalar::from_repr(FieldBytes::from(a)).into_option()73}7475/// Little-endian 64-bit limbs of a scalar (exact).76pub fn limbs(s: &Scalar) -> [u64; 4] {77 let b = s.to_bytes();78 let mut l = [0u64; 4];79 for i in 0..4 {80 l[3 - i] = u64::from_be_bytes(b[i * 8..i * 8 + 8].try_into().unwrap());81 }82 l83}8485fn is_zero(x: &[u64; 5]) -> bool {86 x.iter().all(|&v| v == 0)87}8889fn sub_small(x: &mut [u64; 5], d: u64) {90 let mut borrow = d;91 for limb in x.iter_mut() {92 let (v, b) = limb.overflowing_sub(borrow);93 *limb = v;94 borrow = b as u64;95 if borrow == 0 {96 break;97 }98 }99}100101fn add_small(x: &mut [u64; 5], d: u64) {102 let mut carry = d;103 for limb in x.iter_mut() {104 let (v, c) = limb.overflowing_add(carry);105 *limb = v;106 carry = c as u64;107 if carry == 0 {108 break;109 }110 }111}112113fn shr1(x: &mut [u64; 5]) {114 for i in 0..5 {115 let hi = if i + 1 < 5 { x[i + 1] << 63 } else { 0 };116 x[i] = (x[i] >> 1) | hi;117 }118}119120/// Width-w non-adjacent form: digits d_i in {0, ±1, ±3, …, ±(2^{w-1}-1)}, least significant first.121pub fn wnaf(k: &[u64; 4], w: u32) -> Vec<i8> {122 debug_assert!((2..=7).contains(&w));123 let mut x = [k[0], k[1], k[2], k[3], 0u64];124 let mask = (1u64 << w) - 1;125 let half = 1i64 << (w - 1);126 let mut out = Vec::with_capacity(258);127 while !is_zero(&x) {128 if x[0] & 1 == 1 {129 let mut d = (x[0] & mask) as i64;130 if d >= half {131 d -= 1 << w;132 }133 if d > 0 {134 sub_small(&mut x, d as u64);135 } else {136 add_small(&mut x, (-d) as u64);137 }138 out.push(d as i8);139 } else {140 out.push(0);141 }142 shr1(&mut x);143 }144 out145}146147/// Straus interleaved wNAF multi-scalar multiplication: Σ k_i P_i.148pub fn straus(terms: &[(ProjectivePoint, Scalar)], w: u32, cnt: &mut OpCounts) -> ProjectivePoint {149 let tsize = 1usize << (w - 2); // odd multiples 1,3,…,2^{w-1}-1150 let mut tables: Vec<Vec<ProjectivePoint>> = Vec::with_capacity(terms.len());151 let mut digits: Vec<Vec<i8>> = Vec::with_capacity(terms.len());152 for (p, k) in terms {153 let dbl = p.double();154 cnt.doublings += 1;155 let mut t = Vec::with_capacity(tsize);156 t.push(*p);157 for i in 1..tsize {158 t.push(t[i - 1] + dbl);159 cnt.adds += 1;160 }161 tables.push(t);162 digits.push(wnaf(&limbs(k), w));163 }164 let maxlen = digits.iter().map(|d| d.len()).max().unwrap_or(0);165 let mut acc = ProjectivePoint::IDENTITY;166 let mut started = false;167 for i in (0..maxlen).rev() {168 if started {169 acc = acc.double();170 cnt.doublings += 1;171 }172 for (j, d) in digits.iter().enumerate() {173 if i < d.len() && d[i] != 0 {174 let idx = (d[i].unsigned_abs() / 2) as usize;175 let pt = tables[j][idx];176 if !started {177 cnt.identity_adds += 1;178 }179 acc += if d[i] > 0 { pt } else { -pt };180 cnt.adds += 1;181 started = true;182 }183 }184 }185 acc186}187188fn window(l: &[u64; 4], shift: u32, c: u32) -> usize {189 let li = (shift / 64) as usize;190 let off = shift % 64;191 let mut v = l[li] >> off;192 if off + c > 64 && li + 1 < 4 {193 v |= l[li + 1] << (64 - off);194 }195 (v & ((1u64 << c) - 1)) as usize196}197198/// Window width heuristic for Pippenger as a function of the number of terms.199pub fn pippenger_window(n_terms: usize) -> u32 {200 match n_terms {201 0..=7 => 3,202 8..=31 => 4,203 32..=127 => 5,204 128..=511 => 6,205 512..=2047 => 7,206 2048..=8191 => 8,207 _ => 9,208 }209}210211/// Pippenger bucket method: Σ k_i P_i with affine inputs (mixed additions into buckets).212pub fn pippenger(terms: &[(AffinePoint, Scalar)], c: u32, cnt: &mut OpCounts) -> ProjectivePoint {213 let n_windows = (256 + c - 1) / c;214 let lim: Vec<[u64; 4]> = terms.iter().map(|(_, k)| limbs(k)).collect();215 let nb = (1usize << c) - 1;216 let mut buckets = vec![ProjectivePoint::IDENTITY; nb];217 let mut touched = vec![false; nb];218 let mut acc = ProjectivePoint::IDENTITY;219 let mut started = false;220 for wi in (0..n_windows).rev() {221 if started {222 for _ in 0..c {223 acc = acc.double();224 cnt.doublings += 1;225 }226 }227 for (b, t) in buckets.iter_mut().zip(touched.iter_mut()) {228 *b = ProjectivePoint::IDENTITY;229 *t = false;230 }231 let shift = wi * c;232 let mut any = false;233 for (i, (p, _)) in terms.iter().enumerate() {234 let d = window(&lim[i], shift, c);235 if d != 0 {236 if !touched[d - 1] {237 cnt.identity_adds += 1;238 touched[d - 1] = true;239 }240 buckets[d - 1] += p;241 cnt.mixed_adds += 1;242 any = true;243 }244 }245 if !any {246 continue;247 }248 // running-sum trick: Σ_j j·B_j = Σ_j (Σ_{i ≥ j} B_i)249 let mut running = ProjectivePoint::IDENTITY;250 let mut sum = ProjectivePoint::IDENTITY;251 let mut run_started = false;252 for (j, b) in buckets.iter().enumerate().rev() {253 if touched[j] {254 if !run_started {255 cnt.identity_adds += 1;256 }257 running += b;258 cnt.adds += 1;259 run_started = true;260 }261 if run_started {262 sum += running;263 cnt.adds += 1;264 }265 }266 if started {267 acc += sum;268 cnt.adds += 1;269 } else {270 acc = sum;271 started = true;272 }273 }274 acc275}276277#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize)]278#[serde(rename_all = "snake_case")]279pub enum MsmAlgo {280 Straus,281 Pippenger,282 K256LincombVartime,283 K256LincombCt,284}285286impl MsmAlgo {287 pub fn name(&self) -> &'static str {288 match self {289 MsmAlgo::Straus => "straus_wnaf5",290 MsmAlgo::Pippenger => "pippenger",291 MsmAlgo::K256LincombVartime => "k256_lincomb_vartime",292 MsmAlgo::K256LincombCt => "k256_lincomb_ct",293 }294 }295}296297/// One BIP340 signature to batch-verify (public key already lifted; `lift_x(R)` and the298/// challenge hash are computed inside the batch routine, as in a real verifier).299pub struct SigItem {300 pub pk_x: [u8; 32],301 pub p: AffinePoint,302 pub msg: [u8; 32],303 pub sig: [u8; 64],304}305306pub struct BatchOutcome {307 pub valid: bool,308 pub counts: OpCounts,309 pub msm_ns: u128,310 pub n_terms: usize,311 pub window: u32,312}313314/// Batch verification Σ a_i s_i G − Σ a_i R_i − Σ a_i e_i P_i = O with a_1 = 1,315/// a_i random 128-bit (BIP340 §"Batch Verification"; Bernstein et al. 2012 for Ed25519).316pub fn batch_verify(items: &[&SigItem], weights: &[[u8; 16]], algo: MsmAlgo, th: &[u8; 32], pip_c: u32) -> BatchOutcome {317 let n = items.len();318 let mut terms: Vec<(AffinePoint, Scalar)> = Vec::with_capacity(2 * n + 1);319 let mut s_g = Scalar::ZERO;320 let mut cnt = OpCounts::default();321 let fail = |n_terms| BatchOutcome { valid: false, counts: OpCounts::default(), msm_ns: 0, n_terms, window: 0 };322 for (i, it) in items.iter().enumerate() {323 let r: [u8; 32] = it.sig[..32].try_into().unwrap();324 let s = match scalar_from_bytes_strict(&it.sig[32..]) {325 Some(s) => s,326 None => return fail(0),327 };328 let rp = match lift_x(&r) {329 Some(p) => p,330 None => return fail(0),331 };332 let e = challenge(th, &r, &it.pk_x, &it.msg);333 let a = if i == 0 { Scalar::ONE } else { Scalar::from(u128::from_le_bytes(weights[i])) };334 s_g += a * s;335 // negate the points (free in affine) rather than the scalars, so a_i stays 128-bit336 terms.push((-rp, a));337 terms.push((-it.p, a * e));338 }339 terms.push((AffinePoint::GENERATOR, s_g));340 let n_terms = terms.len();341 let t0 = std::time::Instant::now();342 let (res, window) = match algo {343 MsmAlgo::Straus => {344 let proj: Vec<(ProjectivePoint, Scalar)> = terms.iter().map(|(p, k)| (ProjectivePoint::from(*p), *k)).collect();345 (straus(&proj, 5, &mut cnt), 5)346 }347 MsmAlgo::Pippenger => {348 let c = if pip_c == 0 { pippenger_window(n_terms) } else { pip_c };349 (pippenger(&terms, c, &mut cnt), c)350 }351 MsmAlgo::K256LincombVartime => {352 let proj: Vec<(ProjectivePoint, Scalar)> = terms.iter().map(|(p, k)| (ProjectivePoint::from(*p), *k)).collect();353 (<ProjectivePoint as LinearCombination<[(ProjectivePoint, Scalar)]>>::lincomb_vartime(proj.as_slice()), 0)354 }355 MsmAlgo::K256LincombCt => {356 let proj: Vec<(ProjectivePoint, Scalar)> = terms.iter().map(|(p, k)| (ProjectivePoint::from(*p), *k)).collect();357 (<ProjectivePoint as LinearCombination<[(ProjectivePoint, Scalar)]>>::lincomb(proj.as_slice()), 0)358 }359 };360 let msm_ns = t0.elapsed().as_nanos();361 BatchOutcome { valid: bool::from(res.is_identity()), counts: cnt, msm_ns, n_terms, window }362}363