1use core::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign};
30
31use crate::signing::field::Fp5;
32
33pub const LIMBS: usize = 5;
35
36pub const SCALAR_BYTES: usize = LIMBS * 8;
38
39pub const ORDER: Scalar = Scalar([
43 0xE80F_D996_948B_FFE1,
44 0xE888_5C39_D724_A09C,
45 0x7FFF_FFE6_CFB8_0639,
46 0x7FFF_FFF1_0000_0016,
47 0x7FFF_FFFD_8000_0007,
48]);
49
50const N0I: u64 = 0xD78B_EF72_057B_7BDF;
52
53const R2: Scalar = Scalar([
56 0xA010_01DC_E33D_C739,
57 0x6C32_28D3_3F62_ACCF,
58 0xD1D7_96CC_91CF_8525,
59 0xAADF_FF5D_1574_C1D8,
60 0x4ACA_13B2_8CA2_51F5,
61]);
62
63#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
70pub struct Scalar(pub [u64; LIMBS]);
71
72impl Scalar {
73 pub const ZERO: Self = Self([0; LIMBS]);
75
76 pub const ONE: Self = Self([1, 0, 0, 0, 0]);
78
79 #[inline]
85 #[must_use]
86 pub const fn from_limbs(limbs: [u64; LIMBS]) -> Self {
87 Self(limbs)
88 }
89
90 #[inline]
92 #[must_use]
93 pub const fn to_limbs(self) -> [u64; LIMBS] {
94 self.0
95 }
96
97 #[must_use]
99 pub fn is_canonical(self) -> bool {
100 for i in (0..LIMBS).rev() {
101 if self.0[i] < ORDER.0[i] {
102 return true;
103 }
104
105 if self.0[i] > ORDER.0[i] {
106 return false;
107 }
108 }
109 false
110 }
111
112 #[inline]
114 #[must_use]
115 pub const fn is_zero(self) -> bool {
116 let mut acc: u64 = 0;
117 let mut i = 0;
118
119 while i < LIMBS {
120 acc |= self.0[i];
121 i += 1;
122 }
123 acc == 0
124 }
125
126 #[must_use]
128 pub fn to_le_bytes(self) -> [u8; SCALAR_BYTES] {
129 let mut out = [0u8; SCALAR_BYTES];
130
131 for (i, limb) in self.0.iter().enumerate() {
132 out[i * 8..(i + 1) * 8].copy_from_slice(&limb.to_le_bytes());
133 }
134 out
135 }
136
137 #[must_use]
140 pub fn from_le_bytes_reduce(bytes: [u8; SCALAR_BYTES]) -> Self {
141 let mut limbs = [0u64; LIMBS];
142
143 for (i, slot) in limbs.iter_mut().enumerate() {
144 let mut chunk = [0u8; 8];
145 chunk.copy_from_slice(&bytes[i * 8..(i + 1) * 8]);
146 *slot = u64::from_le_bytes(chunk);
147 }
148
149 let s = Self(limbs);
150 if s.is_canonical() {
151 s
152 } else {
153 let (s1, b1) = s.sub_inner(ORDER);
156 let s_after1 = if b1 != 0 { s } else { s1 };
157 let (s2, b2) = s_after1.sub_inner(ORDER);
158 if b2 != 0 { s_after1 } else { s2 }
159 }
160 }
161
162 #[inline]
165 #[must_use]
166 pub const fn select(c: u64, a0: Self, a1: Self) -> Self {
167 Self([
168 a0.0[0] ^ (c & (a0.0[0] ^ a1.0[0])),
169 a0.0[1] ^ (c & (a0.0[1] ^ a1.0[1])),
170 a0.0[2] ^ (c & (a0.0[2] ^ a1.0[2])),
171 a0.0[3] ^ (c & (a0.0[3] ^ a1.0[3])),
172 a0.0[4] ^ (c & (a0.0[4] ^ a1.0[4])),
173 ])
174 }
175
176 #[inline]
178 #[must_use]
179 pub fn add_inner(self, rhs: Self) -> Self {
180 let mut r = [0u64; LIMBS];
181 let mut carry: u8 = 0;
182
183 for (i, slot) in r.iter_mut().enumerate() {
184 let (t1, c1) = self.0[i].overflowing_add(rhs.0[i]);
185 let (t2, c2) = t1.overflowing_add(u64::from(carry));
186 *slot = t2;
187 carry = u8::from(c1) | u8::from(c2);
188 }
189 Self(r)
190 }
191
192 #[inline]
196 #[must_use]
197 pub fn sub_inner(self, rhs: Self) -> (Self, u64) {
198 let mut r = [0u64; LIMBS];
199 let mut borrow: u8 = 0;
200
201 for (i, slot) in r.iter_mut().enumerate() {
202 let (t1, b1) = self.0[i].overflowing_sub(rhs.0[i]);
203 let (t2, b2) = t1.overflowing_sub(u64::from(borrow));
204 *slot = t2;
205 borrow = u8::from(b1) | u8::from(b2);
206 }
207 let mask = if borrow != 0 { u64::MAX } else { 0 };
208 (Self(r), mask)
209 }
210
211 #[must_use]
217 pub fn monty_mul(self, rhs: Self) -> Self {
218 debug_assert!(self.is_canonical(), "Scalar::monty_mul: lhs not canonical",);
219
220 let mut r = [0u64; LIMBS];
221 for m in rhs.0 {
222 let f = (self.0[0].wrapping_mul(m).wrapping_add(r[0])).wrapping_mul(N0I);
223
224 let mut cc1: u64 = 0;
225 let mut cc2: u64 = 0;
226
227 for j in 0..LIMBS {
228 let prod = u128::from(self.0[j]) * u128::from(m);
229 let s1 = prod + u128::from(r[j]) + u128::from(cc1);
230 cc1 = (s1 >> 64) as u64;
231 let s1_lo = s1 as u64;
232
233 let prod_n = u128::from(f) * u128::from(ORDER.0[j]);
234 let s2 = prod_n + u128::from(s1_lo) + u128::from(cc2);
235 cc2 = (s2 >> 64) as u64;
236 let s2_lo = s2 as u64;
237
238 if j > 0 {
239 r[j - 1] = s2_lo;
240 }
241 }
242 r[LIMBS - 1] = cc1.wrapping_add(cc2);
243 }
244
245 let r0 = Self(r);
246 let (r1, c) = r0.sub_inner(ORDER);
247 Self::select(c, r1, r0)
248 }
249
250 #[must_use]
257 pub fn from_fp5(e: Fp5) -> Self {
258 let mut bytes = [0u8; SCALAR_BYTES];
259 let encoded = e.to_le_bytes();
260 bytes.copy_from_slice(&encoded);
261 Self::from_le_bytes_reduce(bytes)
262 }
263
264 #[must_use]
268 pub fn split_to_4_bit_limbs(self) -> [u8; 80] {
269 let mut out = [0u8; 80];
270
271 for i in 0..LIMBS {
272 for j in 0..16 {
273 out[i * 16 + j] = ((self.0[i] >> (j * 4)) & 0xF) as u8;
274 }
275 }
276 out
277 }
278
279 pub fn recode_signed(self, ss: &mut [i32], w: u32) {
289 recode_signed_from_limbs(&self.0, ss, w);
290 }
291}
292
293pub fn recode_signed_from_limbs(limbs: &[u64], ss: &mut [i32], w: u32) {
296 debug_assert!((2..=10).contains(&w), "window width must be in 2..=10");
297
298 let mw = (1u32 << w) - 1;
299 let hw = 1u32 << (w - 1);
300
301 let mut acc: u64 = 0;
302 let mut acc_len: i32 = 0;
303 let mut j: usize = 0;
304 let mut cc: u32 = 0;
305 let w_i32 = w as i32;
306
307 for slot in ss.iter_mut() {
308 let bb: u32 = if acc_len < w_i32 {
309 if j < limbs.len() {
310 let nl = limbs[j];
311 j += 1;
312 let bits = ((acc | (nl << acc_len)) as u32) & mw;
313 acc = nl >> (w_i32 - acc_len);
314 acc_len += 64 - w_i32;
315 bits
316 } else {
317 let bits = (acc as u32) & mw;
318 acc = 0;
319 acc_len += 64 - w_i32;
320 bits
321 }
322 } else {
323 let bits = (acc as u32) & mw;
324 acc_len -= w_i32;
325 acc >>= w;
326 bits
327 };
328
329 let sum = bb.wrapping_add(cc);
330 cc = (hw.wrapping_sub(sum)) >> 31;
331 *slot = (sum as i32) - ((cc << w) as i32);
332 }
333}
334
335impl Default for Scalar {
336 #[inline]
337 fn default() -> Self {
338 Self::ZERO
339 }
340}
341
342impl Add for Scalar {
343 type Output = Self;
344
345 fn add(self, rhs: Self) -> Self {
346 debug_assert!(self.is_canonical(), "Scalar add: lhs not canonical");
347 debug_assert!(rhs.is_canonical(), "Scalar add: rhs not canonical");
348
349 let r0 = self.add_inner(rhs);
350 let (r1, c) = r0.sub_inner(ORDER);
351 Self::select(c, r1, r0)
352 }
353}
354
355impl AddAssign for Scalar {
356 fn add_assign(&mut self, rhs: Self) {
357 *self = *self + rhs;
358 }
359}
360
361impl Sub for Scalar {
362 type Output = Self;
363
364 fn sub(self, rhs: Self) -> Self {
365 debug_assert!(self.is_canonical(), "Scalar sub: lhs not canonical");
366 debug_assert!(rhs.is_canonical(), "Scalar sub: rhs not canonical");
367
368 let (r0, c) = self.sub_inner(rhs);
369 let r1 = r0.add_inner(ORDER);
370 Self::select(c, r0, r1)
371 }
372}
373
374impl SubAssign for Scalar {
375 fn sub_assign(&mut self, rhs: Self) {
376 *self = *self - rhs;
377 }
378}
379
380impl Neg for Scalar {
381 type Output = Self;
382
383 fn neg(self) -> Self {
384 debug_assert!(self.is_canonical(), "Scalar neg: input not canonical");
385 Self::ZERO - self
386 }
387}
388
389impl Mul for Scalar {
390 type Output = Self;
391
392 fn mul(self, rhs: Self) -> Self {
393 debug_assert!(self.is_canonical(), "Scalar mul: lhs not canonical");
394 debug_assert!(rhs.is_canonical(), "Scalar mul: rhs not canonical");
395
396 self.monty_mul(R2).monty_mul(rhs)
397 }
398}
399
400impl MulAssign for Scalar {
401 fn mul_assign(&mut self, rhs: Self) {
402 *self = *self * rhs;
403 }
404}
405
406#[cfg(test)]
407mod tests {
408 use proptest::prelude::*;
409 use rstest::rstest;
410
411 use super::*;
412 use crate::signing::fixtures::{arb_scalar, arb_scalar_nonzero};
413
414 #[rstest]
415 fn order_round_trips_through_le_bytes() {
416 let bytes = ORDER.to_le_bytes();
417 let s = Scalar::from_le_bytes_reduce(bytes);
420 assert_eq!(s, Scalar::ZERO);
421 }
422
423 #[rstest]
424 fn add_inner_carries_through_top_limb() {
425 let scalar1 = Scalar([
426 0xFFFF_FFFF_FFFF_FFFF,
427 0xFFFF_FFFF_FFFF_FFFF,
428 0xFFFF_FFFF_FFFF_FFFF,
429 0xFFFF_FFFF_FFFF_FFFF,
430 0xFFFF_FFFF_FFFF_FFFF,
431 ]);
432 let scalar2 = Scalar([
433 0x00FF_FFFF_FFFE_EFFF,
434 12_312_321_312,
435 0xFFFF_FFFF_FFFF_FFFF,
436 0x00FF_FFFF_FACD_FFFF,
437 0xBCAF_FFFF_FFFF_FFFF,
438 ]);
439 let expected = Scalar([
440 0x00FF_FFFF_FFFE_EFFE,
441 0x0000_0002_DDDF_1D20,
442 0xFFFF_FFFF_FFFF_FFFF,
443 0x00FF_FFFF_FACD_FFFF,
444 0xBCAF_FFFF_FFFF_FFFF,
445 ]);
446 assert_eq!(scalar1.add_inner(scalar2), expected);
447 }
448
449 #[rstest]
450 fn sub_inner_signals_borrow() {
451 let scalar1 = Scalar::ZERO;
452 let scalar2 = Scalar([u64::MAX; 5]);
453 let (result, borrow) = scalar1.sub_inner(scalar2);
454 assert_eq!(result, Scalar([1, 0, 0, 0, 0]));
455 assert_eq!(borrow, u64::MAX);
456 }
457
458 #[rstest]
459 fn modular_sub_wraps_through_order() {
460 let scalar1 = Scalar([1, 2, 0, 0, 0]);
461 let scalar2 = Scalar([
462 0xFFFF_FFFF_FFFF_FFFF,
463 0xFFFF_FFFF_FFFF_FFFF,
464 0xFFFF_FFFF_FFFF_FFFF,
465 0xFFFF_FFFF_FFFF_FFFF,
466 0x0FFF_FFFF_FFFF_FFFF,
467 ]);
468 assert!(scalar2.is_canonical());
469
470 let result = scalar1 - scalar2;
471 let expected = Scalar([
472 0xE80F_D996_948B_FFE3,
473 0xE888_5C39_D724_A09E,
474 0x7FFF_FFE6_CFB8_0639,
475 0x7FFF_FFF1_0000_0016,
476 8_070_450_521_510_510_599,
477 ]);
478 assert_eq!(result, expected);
479 }
480
481 #[rstest]
482 fn select_picks_branch_by_mask() {
483 let a0 = Scalar([1, 2, 3, 4, 5]);
484 let a1 = Scalar([
485 0xFFFF_FFFF_FFFF_FFFF,
486 0xFFFF_FFFF_FFFF_FFFE,
487 0xFFFF_FFFF_FFFF_FFFD,
488 0xFFFF_FFFF_FFFF_FFFC,
489 0xFFFF_FFFF_FFFF_FFFB,
490 ]);
491 assert_eq!(Scalar::select(0, a0, a1), a0);
492 assert_eq!(Scalar::select(u64::MAX, a0, a1), a1);
493 }
494
495 #[rstest]
496 fn one_is_multiplicative_identity() {
497 let s = Scalar([
498 0x1234_5678_90AB_CDEF,
499 0xFEDC_BA98_7654_3210,
500 0x0123_4567_89AB_CDEF,
501 0xFEDC_BA98_7654_3210,
502 0x1234_5678_90AB_CDEF,
503 ]);
504 assert!(s.is_canonical());
505 assert_eq!(s * Scalar::ONE, s);
506 assert_eq!(Scalar::ONE * s, s);
507 }
508
509 #[rstest]
510 fn neg_is_additive_inverse() {
511 let s = Scalar([7, 11, 13, 17, 19]);
512 let zero = s + (-s);
513 assert_eq!(zero, Scalar::ZERO);
514 }
515
516 #[rstest]
517 fn split_to_4_bit_limbs_matches_reference_vector() {
518 let scalar = Scalar([
519 6_950_590_877_883_398_434,
520 17_178_336_263_794_770_543,
521 11_012_823_478_139_181_320,
522 16_445_091_359_523_510_936,
523 5_882_925_226_143_600_273,
524 ]);
525
526 let limbs = scalar.split_to_4_bit_limbs();
527 assert_eq!(limbs[0], 2);
529 assert_eq!(limbs[1], 2);
530 assert_eq!(limbs[2], 9);
531 assert_eq!(limbs[16], 15);
532 assert_eq!(limbs[39], 13);
533 assert_eq!(limbs[79], 5);
534
535 assert_eq!(reconstruct_from_4_bit_nibbles(limbs), scalar.0);
537 }
538
539 fn reconstruct_from_4_bit_nibbles(nibbles: [u8; 80]) -> [u64; LIMBS] {
542 let mut out = [0u64; LIMBS];
543 for (i, slot) in out.iter_mut().enumerate() {
544 let mut v: u64 = 0;
545 for j in 0..16 {
546 v |= u64::from(nibbles[i * 16 + j]) << (j * 4);
547 }
548 *slot = v;
549 }
550 out
551 }
552
553 fn reconstruct_from_signed_digits(ss: &[i32], w: u32) -> [u64; LIMBS] {
557 let mut limbs = [0i128; LIMBS + 2];
560
561 for (i, &d) in ss.iter().enumerate() {
562 let shift = (i as u64) * u64::from(w);
563 if shift >= ((LIMBS + 2) as u64) * 64 {
564 continue;
565 }
566 let limb_idx = (shift / 64) as usize;
567 let bit_off = (shift % 64) as u32;
568 let shifted = (d as i128) << bit_off;
571 let lo_mask: i128 = (1i128 << 64) - 1;
572 limbs[limb_idx] += shifted & lo_mask;
573 if limb_idx + 1 < limbs.len() {
574 limbs[limb_idx + 1] += shifted >> 64;
575 }
576 }
577 let mut out = [0u64; LIMBS];
578 let mut carry: i128 = 0;
579 for (i, slot) in out.iter_mut().enumerate() {
580 let v = limbs[i] + carry;
581 *slot = v as u64;
582 carry = v >> 64;
583 }
584 out
585 }
586
587 #[rstest]
588 fn recode_signed_top_digit_is_nonnegative() {
589 use crate::signing::field::MODULUS;
595
596 let mut ss = [0i32; 66];
597 let scalar = Scalar([
598 MODULUS - 1,
599 MODULUS - 2,
600 MODULUS - 3,
601 0xFFFF_FFFF_FFFF_FFFF,
602 MODULUS - 5,
603 ]);
604 scalar.recode_signed(&mut ss, 5);
605
606 assert_eq!(ss[6], -4);
607 assert_eq!(ss[19], -2);
608 assert_eq!(ss[25], -8);
609 assert_eq!(ss[32], -1);
610
611 assert_eq!(reconstruct_from_signed_digits(&ss, 5), scalar.0);
614 }
615
616 proptest! {
617 #[rstest]
619 fn prop_add_commutative(a in arb_scalar(), b in arb_scalar()) {
620 prop_assert_eq!(a + b, b + a);
621 }
622
623 #[rstest]
625 fn prop_add_associative(a in arb_scalar(), b in arb_scalar(), c in arb_scalar()) {
626 prop_assert_eq!((a + b) + c, a + (b + c));
627 }
628
629 #[rstest]
631 fn prop_neg_inverse(a in arb_scalar()) {
632 prop_assert_eq!(a + (-a), Scalar::ZERO);
633 }
634
635 #[rstest]
637 fn prop_sub_round_trip(a in arb_scalar(), b in arb_scalar()) {
638 prop_assert_eq!((a + b) - b, a);
639 }
640
641 #[rstest]
643 fn prop_sub_via_add_neg(a in arb_scalar(), b in arb_scalar()) {
644 prop_assert_eq!(a - b, a + (-b));
645 }
646
647 #[rstest]
649 fn prop_mul_commutative(a in arb_scalar(), b in arb_scalar()) {
650 prop_assert_eq!(a * b, b * a);
651 }
652
653 #[rstest]
655 fn prop_mul_associative(a in arb_scalar(), b in arb_scalar(), c in arb_scalar()) {
656 prop_assert_eq!((a * b) * c, a * (b * c));
657 }
658
659 #[rstest]
661 fn prop_distributive(a in arb_scalar(), b in arb_scalar(), c in arb_scalar()) {
662 prop_assert_eq!(a * (b + c), a * b + a * c);
663 }
664
665 #[rstest]
667 fn prop_one_is_identity(a in arb_scalar()) {
668 prop_assert_eq!(a * Scalar::ONE, a);
669 prop_assert_eq!(Scalar::ONE * a, a);
670 }
671
672 #[rstest]
674 fn prop_zero_annihilates(a in arb_scalar()) {
675 prop_assert_eq!(a * Scalar::ZERO, Scalar::ZERO);
676 prop_assert_eq!(Scalar::ZERO * a, Scalar::ZERO);
677 }
678
679 #[rstest]
682 fn prop_from_le_bytes_reduce_idempotent(s in arb_scalar()) {
683 prop_assert_eq!(Scalar::from_le_bytes_reduce(s.to_le_bytes()), s);
684 }
685
686 #[rstest]
688 fn prop_from_le_bytes_reduce_yields_canonical(bytes in any::<[u8; SCALAR_BYTES]>()) {
689 prop_assert!(Scalar::from_le_bytes_reduce(bytes).is_canonical());
690 }
691
692 #[rstest]
694 fn prop_is_canonical_matches_lex_compare(s in arb_scalar()) {
695 let mut expected = false;
697
698 for i in (0..LIMBS).rev() {
699 if s.0[i] < ORDER.0[i] {
700 expected = true;
701 break;
702 }
703
704 if s.0[i] > ORDER.0[i] {
705 expected = false;
706 break;
707 }
708 }
709 prop_assert_eq!(s.is_canonical(), expected);
710 }
711
712 #[rstest]
714 fn prop_select_picks_branch(a in arb_scalar(), b in arb_scalar()) {
715 prop_assert_eq!(Scalar::select(0, a, b), a);
716 prop_assert_eq!(Scalar::select(u64::MAX, a, b), b);
717 }
718
719 #[rstest]
722 fn prop_recode_signed_reconstructs(s in arb_scalar(), w in 2u32..=10) {
723 let len = (320usize.div_ceil(w as usize)) + 2;
726 let mut ss = vec![0i32; len];
727 s.recode_signed(&mut ss, w);
728 prop_assert_eq!(reconstruct_from_signed_digits(&ss, w), s.0);
729
730 let bound: i32 = 1 << (w - 1);
732
733 for (i, &d) in ss.iter().enumerate() {
734 prop_assert!(
735 d >= -bound && d <= bound,
736 "digit {d} at index {i} outside [-{bound}, {bound}]",
737 );
738 }
739 }
740
741 #[rstest]
744 fn prop_split_to_4_bit_limbs_round_trip(s in arb_scalar()) {
745 prop_assert_eq!(reconstruct_from_4_bit_nibbles(s.split_to_4_bit_limbs()), s.0);
746 }
747
748 #[rstest]
750 fn prop_split_to_4_bit_limbs_in_range(s in arb_scalar()) {
751 for &nibble in &s.split_to_4_bit_limbs() {
752 prop_assert!(nibble <= 15);
753 }
754 }
755 }
756
757 proptest! {
761 #[rstest]
762 fn prop_double_via_add(s in arb_scalar_nonzero()) {
763 prop_assert_eq!(s + s, s * Scalar::from_limbs([2, 0, 0, 0, 0]));
764 }
765 }
766}