1  # Constantine
  2  # Copyright (c) 2018-2019    Status Research & Development GmbH
  3  # Copyright (c) 2020-Present Mamy André-Ratsimbazafy
  4  # Licensed and distributed under either of
  5  #   * MIT license (license terms in the root directory or at http://opensource.org/licenses/MIT).
  6  #   * Apache v2 license (license terms in the root directory or at http://www.apache.org/licenses/LICENSE-2.0).
  7  # at your option. This file may not be copied, modified, or distributed except according to those terms.
  8  
  9  # ############################################################
 10  #
 11  #             Benchmark of elliptic curves
 12  #
 13  # ############################################################
 14  
 15  import
 16    # Internals
 17    ../constantine/platforms/abstractions,
 18    ../constantine/math/config/curves,
 19    ../constantine/math/arithmetic,
 20    ../constantine/math/io/io_bigints,
 21    ../constantine/math/elliptic/[
 22      ec_shortweierstrass_affine,
 23      ec_shortweierstrass_projective,
 24      ec_shortweierstrass_jacobian,
 25      ec_shortweierstrass_jacobian_extended,
 26      ec_shortweierstrass_batch_ops,
 27      ec_scalar_mul, ec_endomorphism_accel],
 28      ../constantine/math/constants/zoo_subgroups,
 29    # Helpers
 30    ../helpers/prng_unsafe,
 31    ./platforms,
 32    ./bench_blueprint,
 33    # Reference unsafe scalar multiplication
 34    ../constantine/math/elliptic/ec_scalar_mul_vartime
 35  
 36  export notes
 37  export abstractions # generic sandwich on SecretBool and SecretBool in Jacobian sum
 38  
 39  proc separator*() = separator(179)
 40  
 41  macro fixEllipticDisplay(EC: typedesc): untyped =
 42    # At compile-time, enums are integers and their display is buggy
 43    # we get the Curve ID instead of the curve name.
 44    let instantiated = EC.getTypeInst()
 45    var name = $instantiated[1][0] # EllipticEquationFormCoordinates
 46    let fieldName = $instantiated[1][1][0]
 47    let curveName = $Curve(instantiated[1][1][1].intVal)
 48    name.add "[" & fieldName & "[" & curveName & "]]"
 49    result = newLit name
 50  
 51  proc report(op, elliptic: string, start, stop: MonoTime, startClk, stopClk: int64, iters: int) =
 52    let ns = inNanoseconds((stop-start) div iters)
 53    let throughput = 1e9 / float64(ns)
 54    when SupportsGetTicks:
 55      echo &"{op:<68} {elliptic:<36} {throughput:>15.3f} ops/s {ns:>16} ns/op {(stopClk - startClk) div iters:>12} CPU cycles (approx)"
 56    else:
 57      echo &"{op:<68} {elliptic:<36} {throughput:>15.3f} ops/s {ns:>16} ns/op"
 58  
 59  template bench*(op: string, EC: typedesc, iters: int, body: untyped): untyped =
 60    measure(iters, startTime, stopTime, startClk, stopClk, body)
 61    report(op, fixEllipticDisplay(EC), startTime, stopTime, startClk, stopClk, iters)
 62  
 63  func `+=`[F; G: static Subgroup](P: var ECP_ShortW_JacExt[F, G], Q: ECP_ShortW_JacExt[F, G]) {.inline.}=
 64    P.sum_vartime(P, Q)
 65  func `+=`[F; G: static Subgroup](P: var ECP_ShortW_JacExt[F, G], Q: ECP_ShortW_Aff[F, G]) {.inline.}=
 66    P.madd_vartime(P, Q)
 67  
 68  proc addBench*(EC: typedesc, iters: int) =
 69    var r {.noInit.}: EC
 70    let P = rng.random_unsafe(EC)
 71    let Q = rng.random_unsafe(EC)
 72  
 73    when EC is ECP_ShortW_JacExt:
 74      bench("EC Add vartime " & $EC.G, EC, iters):
 75        r.sum_vartime(P, Q)
 76    else:
 77      block:
 78        bench("EC Add " & $EC.G, EC, iters):
 79          r.sum(P, Q)
 80      block:
 81        bench("EC Add vartime " & $EC.G, EC, iters):
 82          r.sum_vartime(P, Q)
 83  
 84  proc mixedAddBench*(EC: typedesc, iters: int) =
 85    var r {.noInit.}: EC
 86    let P = rng.random_unsafe(EC)
 87    let Q = rng.random_unsafe(EC)
 88    var Qaff: ECP_ShortW_Aff[EC.F, EC.G]
 89    Qaff.affine(Q)
 90  
 91    when EC is ECP_ShortW_JacExt:
 92      bench("EC Mixed Addition vartime " & $EC.G, EC, iters):
 93        r.madd_vartime(P, Qaff)
 94    else:
 95      block:
 96        bench("EC Mixed Addition " & $EC.G, EC, iters):
 97          r.madd(P, Qaff)
 98      block:
 99        bench("EC Mixed Addition vartime " & $EC.G, EC, iters):
100          r.madd_vartime(P, Qaff)
101  
102  proc doublingBench*(EC: typedesc, iters: int) =
103    var r {.noInit.}: EC
104    let P = rng.random_unsafe(EC)
105    bench("EC Double " & $EC.G, EC, iters):
106      r.double(P)
107  
108  proc affFromProjBench*(EC: typedesc, iters: int) =
109    var r {.noInit.}: ECP_ShortW_Aff[EC.F, EC.G]
110    let P = rng.random_unsafe(EC)
111    bench("EC Projective to Affine " & $EC.G, EC, iters):
112      r.affine(P)
113  
114  proc affFromJacBench*(EC: typedesc, iters: int) =
115    var r {.noInit.}: ECP_ShortW_Aff[EC.F, EC.G]
116    let P = rng.random_unsafe(EC)
117    bench("EC Jacobian to Affine " & $EC.G, EC, iters):
118      r.affine(P)
119  
120  proc affFromProjBatchBench*(EC: typedesc, numPoints: int, useBatching: bool, iters: int) =
121    var r = newSeq[affine(EC)](numPoints)
122    var points = newSeq[EC](numPoints)
123  
124    for i in 0 ..< numPoints:
125      points[i] = rng.random_unsafe(EC)
126  
127    if useBatching:
128      bench("EC Projective to Affine -   batched " & $EC.G & " (" & $numPoints & " points)", EC, iters):
129        r.asUnchecked().batchAffine(points.asUnchecked(), numPoints)
130    else:
131      bench("EC Projective to Affine - unbatched " & $EC.G & " (" & $numPoints & " points)", EC, iters):
132        for i in 0 ..< numPoints:
133          r[i].affine(points[i])
134  
135  proc affFromJacBatchBench*(EC: typedesc, numPoints: int, useBatching: bool, iters: int) =
136    var r = newSeq[affine(EC)](numPoints)
137    var points = newSeq[EC](numPoints)
138  
139    for i in 0 ..< numPoints:
140      points[i] = rng.random_unsafe(EC)
141  
142    if useBatching:
143      bench("EC Jacobian to Affine -   batched " & $EC.G & " (" & $numPoints & " points)", EC, iters):
144        r.asUnchecked().batchAffine(points.asUnchecked(), numPoints)
145    else:
146      bench("EC Jacobian to Affine - unbatched " & $EC.G & " (" & $numPoints & " points)", EC, iters):
147        for i in 0 ..< numPoints:
148          r[i].affine(points[i])
149  
150  proc scalarMulGenericBench*(EC: typedesc, bits, window: static int, iters: int) =
151    var r {.noInit.}: EC
152    var P = rng.random_unsafe(EC)
153    P.clearCofactor()
154  
155    let exponent = rng.random_unsafe(BigInt[bits])
156  
157    bench("EC ScalarMul " & $bits & "-bit " & $EC.G & " (window-" & $window & ", generic)", EC, iters):
158      r = P
159      r.scalarMulGeneric(exponent, window)
160  
161  proc scalarMulEndo*(EC: typedesc, bits: static int, iters: int) =
162    var r {.noInit.}: EC
163    var P = rng.random_unsafe(EC)
164    P.clearCofactor()
165  
166    let exponent = rng.random_unsafe(BigInt[bits])
167  
168    bench("EC ScalarMul " & $bits & "-bit " & $EC.G & " (endomorphism accelerated)", EC, iters):
169      r = P
170      r.scalarMulEndo(exponent)
171  
172  proc scalarMulEndoWindow*(EC: typedesc, bits: static int, iters: int) =
173    var r {.noInit.}: EC
174    var P = rng.random_unsafe(EC)
175    P.clearCofactor()
176  
177    let exponent = rng.random_unsafe(BigInt[bits])
178  
179    bench("EC ScalarMul " & $bits & "-bit " & $EC.G & " (window-2, endomorphism accelerated)", EC, iters):
180      r = P
181      when EC.F is Fp:
182        r.scalarMulGLV_m2w2(exponent)
183      else:
184        {.error: "Not implemented".}
185  
186  proc scalarMulVartimeDoubleAddBench*(EC: typedesc, bits: static int, iters: int) =
187    var r {.noInit.}: EC
188    var P = rng.random_unsafe(EC)
189    P.clearCofactor()
190  
191    let exponent = rng.random_unsafe(BigInt[bits])
192  
193    bench("EC ScalarMul " & $bits & "-bit " & $EC.G & " (vartime reference DoubleAdd)", EC, iters):
194      r = P
195      r.scalarMul_doubleAdd_vartime(exponent)
196  
197  proc scalarMulVartimeMinHammingWeightRecodingBench*(EC: typedesc, bits: static int, iters: int) =
198    var r {.noInit.}: EC
199    var P = rng.random_unsafe(EC)
200    P.clearCofactor()
201  
202    let exponent = rng.random_unsafe(BigInt[bits])
203  
204    bench("EC ScalarMul " & $bits & "-bit " & $EC.G & " (vartime min Hamming Weight recoding)", EC, iters):
205      r = P
206      r.scalarMul_minHammingWeight_vartime(exponent)
207  
208  proc scalarMulVartimeWNAFBench*(EC: typedesc, bits, window: static int, iters: int) =
209    var r {.noInit.}: EC
210    var P = rng.random_unsafe(EC)
211    P.clearCofactor()
212  
213    let exponent = rng.random_unsafe(BigInt[bits])
214  
215    bench("EC ScalarMul " & $bits & "-bit " & $EC.G & " (vartime wNAF-" & $window & ")", EC, iters):
216      r = P
217      r.scalarMul_minHammingWeight_windowed_vartime(exponent, window)
218  
219  proc scalarMulVartimeEndoWNAFBench*(EC: typedesc, bits, window: static int, iters: int) =
220    var r {.noInit.}: EC
221    var P = rng.random_unsafe(EC)
222    P.clearCofactor()
223  
224    let exponent = rng.random_unsafe(BigInt[bits])
225  
226    bench("EC ScalarMul " & $bits & "-bit " & $EC.G & " (vartime endomorphism + wNAF-" & $window & ")", EC, iters):
227      r = P
228      r.scalarMulEndo_minHammingWeight_windowed_vartime(exponent, window)
229  
230  proc multiAddBench*(EC: typedesc, numPoints: int, useBatching: bool, iters: int) =
231    var points = newSeq[ECP_ShortW_Aff[EC.F, EC.G]](numPoints)
232  
233    for i in 0 ..< numPoints:
234      points[i] = rng.random_unsafe(ECP_ShortW_Aff[EC.F, EC.G])
235  
236    var r{.noInit.}: EC
237  
238    if useBatching:
239      bench("EC Multi Add batched                  " & $EC.G & " (" & $numPoints & " points)", EC, iters):
240        r.sum_reduce_vartime(points)
241    else:
242      bench("EC Multi Mixed-Add unbatched          " & $EC.G & " (" & $numPoints & " points)", EC, iters):
243        r.setInf()
244        for i in 0 ..< numPoints:
245          r += points[i]
246  
247  
248  proc msmBench*(EC: typedesc, numPoints: int, iters: int) =
249    const bits = EC.F.C.getCurveOrderBitwidth()
250    var points = newSeq[ECP_ShortW_Aff[EC.F, EC.G]](numPoints)
251    var scalars = newSeq[BigInt[bits]](numPoints)
252  
253    for i in 0 ..< numPoints:
254      var tmp = rng.random_unsafe(EC)
255      tmp.clearCofactor()
256      points[i].affine(tmp)
257      scalars[i] = rng.random_unsafe(BigInt[bits])
258  
259    var r{.noInit.}: EC
260    var startNaive, stopNaive, startMSMbaseline, stopMSMbaseline, startMSMopt, stopMSMopt: MonoTime
261  
262    if numPoints <= 100000:
263      bench("EC scalar muls                " & align($numPoints, 7) & " (scalars " & $bits & "-bit, points) pairs ", EC, iters):
264        startNaive = getMonotime()
265        var tmp: EC
266        r.setInf()
267        for i in 0 ..< points.len:
268          tmp.fromAffine(points[i])
269          tmp.scalarMul(scalars[i])
270          r += tmp
271        stopNaive = getMonotime()
272  
273    block:
274      bench("EC multi-scalar-mul baseline  " & align($numPoints, 7) & " (scalars " & $bits & "-bit, points) pairs ", EC, iters):
275        startMSMbaseline = getMonotime()
276        r.multiScalarMul_reference_vartime(scalars, points)
277        stopMSMbaseline = getMonotime()
278  
279    block:
280      bench("EC multi-scalar-mul optimized " & align($numPoints, 7) & " (scalars " & $bits & "-bit, points) pairs ", EC, iters):
281        startMSMopt = getMonotime()
282        r.multiScalarMul_vartime(scalars, points)
283        stopMSMopt = getMonotime()
284  
285    let perfNaive = inNanoseconds((stopNaive-startNaive) div iters)
286    let perfMSMbaseline = inNanoseconds((stopMSMbaseline-startMSMbaseline) div iters)
287    let perfMSMopt = inNanoseconds((stopMSMopt-startMSMopt) div iters)
288  
289    if numPoints <= 100000:
290      let speedupBaseline = float(perfNaive) / float(perfMSMbaseline)
291      echo &"Speedup ratio baseline over naive linear combination: {speedupBaseline:>6.3f}x"
292  
293      let speedupOpt = float(perfNaive) / float(perfMSMopt)
294      echo &"Speedup ratio optimized over naive linear combination: {speedupOpt:>6.3f}x"
295  
296    let speedupOptBaseline = float(perfMSMbaseline) / float(perfMSMopt)
297    echo &"Speedup ratio optimized over baseline linear combination: {speedupOptBaseline:>6.3f}x"