multiScalar_multiplication Pippeneger算法

1. 引言

multiScalar_multiplication定义如下： V = a 1 P 1 + a 2 P 2 + . . . + a n P n ， 其 中 a i 为 s c a l a r 值 ， P i 为 e l l i p t i c − c u r v e   p o i n t V=a_1P_1+a_2P_2+...+a_nP_n，其中a_i为scalar值，P_i为elliptic-curve\ point V=a1​P1​+a2​P2​+...+an​Pn​，其中ai​为scalar值，Pi​为elliptic−curve point

在论文《Faster batch forgery identification》第四节中，分别提及了三种算法：

• Bos-Coster算法：对multiScalar_multiplication速度的提升有限。
• Straus算法：选择 w = 5 w=5 w=5。
• Pippenger算法：可分别选择 w = 6 w=6 w=6、 w = 7 w=7 w=7、 w = 8 w=8 w=8。

2. curve25519-dalek中算法选择边界

curve25519-dalek的边界为：

• 0.05) No change in performance detected. Found 3 outliers among 15 measurements (20.00%) 1 (6.67%) high mild 2 (13.33%) high severe Variable-time variable-base multiscalar multiplication/799 time: [9.8895 ms 9.9910 ms 10.142 ms] change: [-13.810% +4.7550% +23.994%] (p = 0.70 > 0.05) No change in performance detected. Found 3 outliers among 15 measurements (20.00%) 3 (20.00%) high severe Variable-time variable-base multiscalar multiplication/800 time: [9.9245 ms 9.9687 ms 10.077 ms] change: [-15.381% +3.3416% +29.183%] (p = 0.78 > 0.05) No change in performance detected. Found 2 outliers among 15 measurements (13.33%) 2 (13.33%) high severe all w=7: Running target/release/deps/dalek_benchmarks-53fcb1faec6cb376 Variable-time variable-base multiscalar multiplication/189 time: [3.5630 ms 3.5914 ms 3.6504 ms] change: [-11.315% +12.310% +41.991%] (p = 0.39 > 0.05) No change in performance detected. Found 3 outliers among 15 measurements (20.00%) 3 (20.00%) high severe Variable-time variable-base multiscalar multiplication/190 time: [3.5012 ms 3.5234 ms 3.5752 ms] change: [-10.315% +10.701% +39.224%] (p = 0.41 > 0.05) No change in performance detected. Found 3 outliers among 15 measurements (20.00%) 3 (20.00%) high severe Variable-time variable-base multiscalar multiplication/499 time: [6.6358 ms 6.6664 ms 6.7455 ms] change: [-22.010% -2.0152% +25.105%] (p = 0.83 > 0.05) No change in performance detected. Found 2 outliers among 15 measurements (13.33%) 2 (13.33%) high severe Variable-time variable-base multiscalar multiplication/500 time: [6.6411 ms 6.6746 ms 6.7609 ms] change: [-22.621% -3.1515% +24.251%] (p = 0.80 > 0.05) No change in performance detected. Found 2 outliers among 15 measurements (13.33%) 2 (13.33%) high severe Variable-time variable-base multiscalar multiplication/799 time: [9.6734 ms 9.7493 ms 9.8566 ms] change: [-32.201% -15.383% +6.3693%] (p = 0.20 > 0.05) No change in performance detected. Found 2 outliers among 15 measurements (13.33%) 2 (13.33%) high severe Variable-time variable-base multiscalar multiplication/800 time: [9.6891 ms 9.7310 ms 9.8314 ms] change: [-21.197% -4.7756% +15.300%] (p = 0.66 > 0.05) No change in performance detected. Found 2 outliers among 15 measurements (13.33%) 2 (13.33%) high severe all w=6: Running target/release/deps/dalek_benchmarks-53fcb1faec6cb376 Variable-time variable-base multiscalar multiplication/189 time: [3.1587 ms 3.1799 ms 3.2284 ms] change: [-17.560% +4.6755% +32.986%] (p = 0.74 > 0.05) No change in performance detected. Found 3 outliers among 15 measurements (20.00%) 3 (20.00%) high severe Variable-time variable-base multiscalar multiplication/190 time: [3.1706 ms 3.1918 ms 3.2404 ms] change: [-21.148% +1.7730% +30.036%] (p = 0.90 > 0.05) No change in performance detected. Found 3 outliers among 15 measurements (20.00%) 3 (20.00%) high severe Variable-time variable-base multiscalar multiplication/499 time: [6.8064 ms 6.8407 ms 6.9261 ms] change: [-30.371% -12.039% +12.024%] (p = 0.32 > 0.05) No change in performance detected. Found 2 outliers among 15 measurements (13.33%) 2 (13.33%) high severe Variable-time variable-base multiscalar multiplication/500 time: [6.8180 ms 6.8740 ms 6.9684 ms] change: [-31.891% -13.085% +10.826%] (p = 0.29 > 0.05) No change in performance detected. Found 3 outliers among 15 measurements (20.00%) 1 (6.67%) high mild 2 (13.33%) high severe Variable-time variable-base multiscalar multiplication/799 time: [10.399 ms 10.546 ms 10.819 ms] change: [-27.627% -9.1493% +13.573%] (p = 0.46 > 0.05) No change in performance detected. Found 3 outliers among 15 measurements (20.00%) 1 (6.67%) high mild 2 (13.33%) high severe Variable-time variable-base multiscalar multiplication/800 time: [10.281 ms 10.318 ms 10.392 ms] change: [-39.340% -22.582% -2.0183%] (p = 0.06 > 0.05) No change in performance detected. Found 2 outliers among 15 measurements (13.33%) 2 (13.33%) high severe all straus: Running target/release/deps/dalek_benchmarks-53fcb1faec6cb376 Variable-time variable-base multiscalar multiplication/189 time: [2.9865 ms 3.0344 ms 3.1013 ms] change: [-18.787% +2.8603% +30.058%] (p = 0.84 > 0.05) No change in performance detected. Found 3 outliers among 15 measurements (20.00%) 1 (6.67%) high mild 2 (13.33%) high severe Variable-time variable-base multiscalar multiplication/190 time: [2.9745 ms 3.0011 ms 3.0599 ms] change: [-22.820% -0.3394% +30.681%] (p = 0.98 > 0.05) No change in performance detected. Found 3 outliers among 15 measurements (20.00%) 3 (20.00%) high severe Variable-time variable-base multiscalar multiplication/499 time: [7.7750 ms 7.8195 ms 7.9154 ms] change: [-17.989% +2.7770% +32.322%] (p = 0.83 > 0.05) No change in performance detected. Found 2 outliers among 15 measurements (13.33%) 2 (13.33%) high severe Variable-time variable-base multiscalar multiplication/500 time: [7.8235 ms 7.8651 ms 7.9713 ms] change: [-7.2904% +16.179% +49.302%] (p = 0.26 > 0.05) No change in performance detected. Found 2 outliers among 15 measurements (13.33%) 2 (13.33%) high severe Variable-time variable-base multiscalar multiplication/799 time: [12.478 ms 12.538 ms 12.667 ms] change: [+4.1941% +28.354% +57.937%] (p = 0.02 < 0.05) Performance has regressed. Found 2 outliers among 15 measurements (13.33%) 2 (13.33%) high severe Variable-time variable-base multiscalar multiplication/800 time: [12.667 ms 12.782 ms 12.937 ms] change: [+4.4294% +34.305% +70.910%] (p = 0.03 < 0.05) Performance has regressed. Found 2 outliers among 15 measurements (13.33%) 2 (13.33%) high severe default: Running target/release/deps/dalek_benchmarks-53fcb1faec6cb376 Variable-time variable-base multiscalar multiplication/189 time: [2.9304 ms 2.9669 ms 3.0377 ms] change: [-78.836% -74.890% -70.059%] (p = 0.00 < 0.05) Performance has improved. Found 3 outliers among 15 measurements (20.00%) 1 (6.67%) high mild 2 (13.33%) high severe Variable-time variable-base multiscalar multiplication/190 time: [3.1322 ms 3.1516 ms 3.1971 ms] change: [-78.159% -74.341% -68.876%] (p = 0.00 < 0.05) Performance has improved. Found 3 outliers among 15 measurements (20.00%) 1 (6.67%) high mild 2 (13.33%) high severe Variable-time variable-base multiscalar multiplication/499 time: [6.8036 ms 7.0906 ms 7.7292 ms] change: [-74.384% -69.294% -62.834%] (p = 0.00 < 0.05) Performance has improved. Found 3 outliers among 15 measurements (20.00%) 2 (13.33%) high mild 1 (6.67%) high severe Variable-time variable-base multiscalar multiplication/500 time: [6.6848 ms 6.7521 ms 6.8618 ms] Found 2 outliers among 15 measurements (13.33%) 2 (13.33%) high severe Variable-time variable-base multiscalar multiplication/799 time: [9.5685 ms 9.7077 ms 9.9853 ms] Found 3 outliers among 15 measurements (20.00%) 3 (20.00%) high severe Variable-time variable-base multiscalar multiplication/800 time: [9.7910 ms 9.8422 ms 9.9460 ms] Found 2 outliers among 15 measurements (13.33%) 2 (13.33%) high severe

  #[cfg(feature = "alloc")]
  impl VartimeMultiscalarMul for EdwardsPoint {
      type Point = EdwardsPoint;
  
      fn optional_multiscalar_mul(scalars: I, points: J) -> Option
      where
          I: IntoIterator,
          I::Item: Borrow,
          J: IntoIterator,
      {
          // Sanity-check lengths of input iterators
          let mut scalars = scalars.into_iter();
          let mut points = points.into_iter();
  
          // Lower and upper bounds on iterators
          let (s_lo, s_hi) = scalars.by_ref().size_hint();
          let (p_lo, p_hi) = points.by_ref().size_hint();
  
          // They should all be equal
          assert_eq!(s_lo, p_lo);
          assert_eq!(s_hi, Some(s_lo));
          assert_eq!(p_hi, Some(p_lo));
  
          // Now we know there's a single size.
          // Use this as the hint to decide which algorithm to use.
          let size = s_lo;
  
          if size < 190 {
              scalar_mul::straus::Straus::optional_multiscalar_mul(scalars, points)
          } else {
              scalar_mul::pippenger::Pippenger::optional_multiscalar_mul(scalars, points)
          }
      }
  }
  

  参考资料： [1] 论文《Faster batch forgery identification》