t_finite_fields_vs_gmp.nim
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 import 10 # Standard library 11 std/[random, macros, times], 12 # Third-party 13 gmp, 14 # Internal 15 ../../constantine/platforms/abstractions, 16 ../../constantine/serialization/codecs, 17 ../../constantine/math/io/[io_bigints, io_fields], 18 ../../constantine/math/arithmetic, 19 ../../constantine/math/config/curves, 20 # Test utilities 21 ../../helpers/prng_unsafe 22 23 echo "\n------------------------------------------------------\n" 24 25 var RNG {.compileTime.} = initRand(1234) 26 27 const AvailableCurves = [ 28 P224, 29 BN254_Nogami, BN254_Snarks, 30 P256, Secp256k1, Edwards25519, Bandersnatch, Pallas, Vesta, 31 BLS12_377, BLS12_381, BW6_761 32 ] 33 34 const # https://gmplib.org/manual/Integer-Import-and-Export.html 35 GMP_WordLittleEndian = -1'i32 36 GMP_WordNativeEndian = 0'i32 37 GMP_WordBigEndian = 1'i32 38 39 GMP_MostSignificantWordFirst = 1'i32 40 GMP_LeastSignificantWordFirst = -1'i32 41 42 # ############################################################ 43 # 44 # Helpers 45 # 46 # ############################################################ 47 # 48 # Factor common things in proc to avoid generating 100k+ lines of C code 49 50 proc binary_prologue[C: static Curve, N: static int]( 51 rng: var RngState, 52 a, b, p: var mpz_t, 53 aTest, bTest: var Fp[C], 54 aBuf, bBuf: var array[N, byte]) = 55 56 # Build the field elements 57 aTest = rng.random_unsafe(Fp[C]) 58 bTest = rng.random_unsafe(Fp[C]) 59 60 # Set modulus to curve modulus 61 let err = mpz_set_str(p, Curve(C).Mod.toHex(), 0) 62 doAssert err == 0, "Error on prime for curve " & $Curve(C) 63 64 ######################################################### 65 # Conversion to GMP 66 const aLen = C.getCurveBitwidth().ceilDiv_vartime(8) 67 const bLen = C.getCurveBitwidth().ceilDiv_vartime(8) 68 69 var aBuf: array[aLen, byte] 70 var bBuf: array[bLen, byte] 71 72 aBuf.marshal(aTest, bigEndian) 73 bBuf.marshal(bTest, bigEndian) 74 75 mpz_import(a, aLen, GMP_MostSignificantWordFirst, 1, GMP_WordNativeEndian, 0, aBuf[0].addr) 76 mpz_import(b, bLen, GMP_MostSignificantWordFirst, 1, GMP_WordNativeEndian, 0, bBuf[0].addr) 77 78 proc binary_epilogue[C: static Curve, N: static int]( 79 r, a, b: mpz_t, 80 rTest: Fp[C], 81 aBuf, bBuf: array[N, byte], 82 operation: string 83 ) = 84 85 ######################################################### 86 # Check 87 88 {.push warnings: off.} # deprecated csize 89 var aW, bW, rW: csize # Word written by GMP 90 {.pop.} 91 92 var rGMP: array[N, byte] 93 discard mpz_export(rGMP[0].addr, rW.addr, GMP_MostSignificantWordFirst, 1, GMP_WordNativeEndian, 0, r) 94 95 var rConstantine: array[N, byte] 96 marshal(rConstantine, rTest, bigEndian) 97 98 # Note: in bigEndian, GMP aligns left while constantine aligns right 99 doAssert rGMP.toOpenArray(0, rW-1) == rConstantine.toOpenArray(N-rW, N-1), block: 100 # Reexport as bigEndian for debugging 101 discard mpz_export(aBuf[0].unsafeAddr, aW.addr, GMP_MostSignificantWordFirst, 1, GMP_WordNativeEndian, 0, a) 102 discard mpz_export(bBuf[0].unsafeAddr, bW.addr, GMP_MostSignificantWordFirst, 1, GMP_WordNativeEndian, 0, b) 103 "\nModular " & operation & " on curve " & $C & " with operands\n" & 104 " a: " & aBuf.toHex & "\n" & 105 " b: " & bBuf.toHex & "\n" & 106 "failed:" & "\n" & 107 " GMP: " & rGMP.toHex() & "\n" & 108 " Constantine: " & rConstantine.toHex() & "\n" & 109 "(Note that GMP aligns bytes left while constantine aligns bytes right)" 110 111 # ############################################################ 112 # 113 # Test Definitions 114 # 115 # ############################################################ 116 117 proc addTests(rng: var RngState, a, b, p, r: var mpz_t, C: static Curve) = 118 # echo "Testing: random modular addition on ", $C 119 120 const 121 bits = C.getCurveBitwidth() 122 bufLen = bits.ceilDiv_vartime(8) 123 var 124 aTest, bTest{.noInit.}: Fp[C] 125 aBuf, bBuf: array[bufLen, byte] 126 binary_prologue(rng, a, b, p, aTest, bTest, aBuf, bBuf) 127 128 mpz_add(r, a, b) 129 mpz_mod(r, r, p) 130 131 var rTest {.noInit.}: Fp[C] 132 rTest.sum(aTest, bTest) 133 134 var r2Test = aTest 135 r2Test += bTest 136 137 binary_epilogue(r, a, b, rTest, aBuf, bBuf, "Addition (with result)") 138 binary_epilogue(r, a, b, r2Test, aBuf, bBuf, "Addition (in-place)") 139 140 proc subTests(rng: var RngState, a, b, p, r: var mpz_t, C: static Curve) = 141 # echo "Testing: random modular substraction on ", $C 142 143 const 144 bits = C.getCurveBitwidth() 145 bufLen = bits.ceilDiv_vartime(8) 146 var 147 aTest, bTest{.noInit.}: Fp[C] 148 aBuf, bBuf: array[bufLen, byte] 149 binary_prologue(rng, a, b, p, aTest, bTest, aBuf, bBuf) 150 151 mpz_sub(r, a, b) 152 mpz_mod(r, r, p) 153 154 var rTest {.noInit.}: Fp[C] 155 rTest.diff(aTest, bTest) 156 157 var r2Test = aTest 158 r2Test -= bTest 159 160 # Substraction with r and b aliasing 161 var r3Test = bTest 162 r3Test.diff(aTest, r3Test) 163 164 binary_epilogue(r, a, b, rTest, aBuf, bBuf, "Substraction (with result)") 165 binary_epilogue(r, a, b, r2Test, aBuf, bBuf, "Substraction (in-place)") 166 binary_epilogue(r, a, b, r3Test, aBuf, bBuf, "Substraction (result aliasing)") 167 168 proc mulTests(rng: var RngState, a, b, p, r: var mpz_t, C: static Curve) = 169 # echo "Testing: random modular multiplication on ", $C 170 171 const 172 bits = C.getCurveBitwidth() 173 bufLen = bits.ceilDiv_vartime(8) 174 var 175 aTest, bTest{.noInit.}: Fp[C] 176 aBuf, bBuf: array[bufLen, byte] 177 binary_prologue(rng, a, b, p, aTest, bTest, aBuf, bBuf) 178 179 mpz_mul(r, a, b) 180 mpz_mod(r, r, p) 181 182 var rTest {.noInit.}: Fp[C] 183 rTest.prod(aTest, bTest) 184 185 var r2Test = aTest 186 r2Test *= bTest 187 188 binary_epilogue(r, a, b, rTest, aBuf, bBuf, "Multiplication (with result)") 189 binary_epilogue(r, a, b, r2Test, aBuf, bBuf, "Multiplication (in-place)") 190 191 proc invTests(rng: var RngState, a, b, p, r: var mpz_t, C: static Curve) = 192 # We use the binary prologue epilogue but the "b" parameter is actual unused 193 # echo "Testing: random modular inversion on ", $C 194 195 const 196 bits = C.getCurveBitwidth() 197 bufLen = bits.ceilDiv_vartime(8) 198 var 199 aTest, bTest{.noInit.}: Fp[C] 200 aBuf, bBuf: array[bufLen, byte] 201 binary_prologue(rng, a, b, p, aTest, bTest, aBuf, bBuf) 202 203 let exist = mpz_invert(r, a, p) 204 doAssert exist != 0 205 206 var rTest {.noInit.}: Fp[C] 207 rTest.inv(aTest) 208 209 binary_epilogue(r, a, b, rTest, aBuf, bBuf, "Inversion (b is unused)") 210 211 # ############################################################ 212 # 213 # Test Runners 214 # 215 # ############################################################ 216 217 macro randomTests(numTests: static int, curveSym, body: untyped): untyped = 218 ## Generate `num` random tests at compile-time to test against GMP 219 ## for A mod M 220 result = newStmtList() 221 222 for _ in 0 ..< numTests: 223 let curve = RNG.sample(AvailableCurves) 224 225 result.add quote do: 226 block: 227 const `curveSym` = Curve(`curve`) 228 block: 229 `body` 230 231 template testSetup {.dirty.} = 232 var rng: RngState 233 let seed = uint32(getTime().toUnix() and (1'i64 shl 32 - 1)) # unixTime mod 2^32 234 rng.seed(seed) 235 echo "\n------------------------------------------------------\n" 236 echo "test_finite_fields_vs_gmp** seed: ", seed 237 238 var a, b, p, r: mpz_t 239 mpz_init(a) 240 mpz_init(b) 241 mpz_init(p) 242 mpz_init(r) 243 244 proc mainMul() = 245 testSetup() 246 echo "Testing modular multiplications vs GMP" 247 randomTests(24, curve): 248 mulTests(rng, a, b, p, r, curve) 249 250 proc mainAdd() = 251 testSetup() 252 echo "Testing modular additions vs GMP" 253 randomTests(24, curve): 254 addTests(rng, a, b, p, r, curve) 255 256 proc mainSub() = 257 testSetup() 258 echo "Testing modular substractions vs GMP" 259 randomTests(24, curve): 260 subTests(rng, a, b, p, r, curve) 261 262 proc mainInv() = 263 testSetup() 264 echo "Testing modular inversions vs GMP" 265 randomTests(24, curve): 266 invTests(rng, a, b, p, r, curve) 267 268 269 mainMul() 270 mainAdd() 271 mainSub() 272 mainInv()