/ constantine / ethereum_evm_precompiles.nim
ethereum_evm_precompiles.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 ./platforms/abstractions, 11 ./serialization/io_limbs, 12 ./math/config/curves, 13 ./math/[arithmetic, extension_fields], 14 ./math/arithmetic/limbs_montgomery, 15 ./math/ec_shortweierstrass, 16 ./math/pairings/[pairings_generic, miller_accumulators], 17 ./math/constants/zoo_subgroups, 18 ./math/io/[io_bigints, io_fields], 19 ./math_arbitrary_precision/arithmetic/bigints_views 20 21 # ############################################################ 22 # 23 # Ethereum EVM precompiles 24 # 25 # ############################################################ 26 27 # No exceptions for the EVM API 28 {.push raises: [].} 29 30 type 31 CttEVMStatus* = enum 32 cttEVM_Success 33 cttEVM_InvalidInputSize 34 cttEVM_InvalidOutputSize 35 cttEVM_IntLargerThanModulus 36 cttEVM_PointNotOnCurve 37 cttEVM_PointNotInSubgroup 38 39 func parseRawUint( 40 dst: var Fp[BN254_Snarks], 41 src: openarray[byte]): CttEVMStatus = 42 ## Parse an unsigned integer from its canonical 43 ## big-endian or little-endian unsigned representation 44 ## And store it into a field element. 45 ## 46 ## Return false if the integer is larger than the field modulus. 47 ## Returns true on success. 48 var big {.noInit.}: BigInt[254] 49 big.unmarshal(src, bigEndian) 50 51 if not bool(big < Mod(BN254_Snarks)): 52 return cttEVM_IntLargerThanModulus 53 54 dst.fromBig(big) 55 return cttEVM_Success 56 57 func fromRawCoords( 58 dst: var ECP_ShortW_Jac[Fp[BN254_Snarks], G1], 59 x, y: openarray[byte]): CttEVMStatus = 60 61 # Deserialization 62 # ---------------------- 63 # Encoding spec https://eips.ethereum.org/EIPS/eip-196 64 65 let status_x = dst.x.parseRawUint(x) 66 if status_x != cttEVM_Success: 67 return status_x 68 let status_y = dst.y.parseRawUint(y) 69 if status_y != cttEVM_Success: 70 return status_y 71 72 # Handle point at infinity 73 if dst.x.isZero().bool and dst.y.isZero().bool: 74 dst.setInf() 75 return cttEVM_Success 76 77 # Otherwise regular point 78 dst.z.setOne() 79 80 # Deserialization checks 81 # ---------------------- 82 83 # Point on curve 84 if not bool(isOnCurve(dst.x, dst.y, G1)): 85 return cttEVM_PointNotOnCurve 86 87 # BN254_Snarks is a curve with cofactor 1, 88 # so no subgroup checks are necessary 89 90 return cttEVM_Success 91 92 func eth_evm_ecadd*(r: var openArray[byte], inputs: openarray[byte]): CttEVMStatus = 93 ## Elliptic Curve addition on BN254_Snarks 94 ## (also called alt_bn128 in Ethereum specs 95 ## and bn256 in Ethereum tests) 96 ## 97 ## Name: ECADD 98 ## 99 ## Inputs: 100 ## - A G1 point P with coordinates (Px, Py) 101 ## - A G1 point Q with coordinates (Qx, Qy) 102 ## 103 ## Each coordinate is a 32-bit bigEndian integer 104 ## They are serialized concatenated in a byte array [Px, Py, Qx, Qy] 105 ## If the length is less than 128 bytes, input is virtually padded with zeros. 106 ## If the length is greater than 128 bytes, input is truncated to 128 bytes. 107 ## 108 ## Output 109 ## - Output buffer MUST be of length 64 bytes 110 ## - A G1 point R with coordinates (Px + Qx, Py + Qy) 111 ## - Status code: 112 ## cttEVM_Success 113 ## cttEVM_IntLargerThanModulus 114 ## cttEVM_PointNotOnCurve 115 ## 116 ## Spec https://eips.ethereum.org/EIPS/eip-196 117 118 if r.len != 64: 119 return cttEVM_InvalidOutputSize 120 121 # Auto-pad with zero 122 var padded: array[128, byte] 123 padded.rawCopy(0, inputs, 0, min(inputs.len, padded.len)) 124 125 var P{.noInit.}, Q{.noInit.}, R{.noInit.}: ECP_ShortW_Jac[Fp[BN254_Snarks], G1] 126 127 let statusP = P.fromRawCoords( 128 x = padded.toOpenArray(0, 31), 129 y = padded.toOpenArray(32, 63)) 130 if statusP != cttEVM_Success: 131 return statusP 132 let statusQ = Q.fromRawCoords( 133 x = padded.toOpenArray(64, 95), 134 y = padded.toOpenArray(96, 127)) 135 if statusQ != cttEVM_Success: 136 return statusQ 137 138 R.sum_vartime(P, Q) 139 var aff{.noInit.}: ECP_ShortW_Aff[Fp[BN254_Snarks], G1] 140 aff.affine(R) 141 142 r.toOpenArray(0, 31).marshal(aff.x, bigEndian) 143 r.toOpenArray(32, 63).marshal(aff.y, bigEndian) 144 return cttEVM_Success 145 146 func eth_evm_ecmul*(r: var openArray[byte], inputs: openarray[byte]): CttEVMStatus = 147 ## Elliptic Curve multiplication on BN254_Snarks 148 ## (also called alt_bn128 in Ethereum specs 149 ## and bn256 in Ethereum tests) 150 ## 151 ## Name: ECMUL 152 ## 153 ## Inputs: 154 ## - A G1 point P with coordinates (Px, Py) 155 ## - A scalar s in 0 ..< 2²⁵⁶ 156 ## 157 ## Each coordinate is a 32-bit bigEndian integer 158 ## They are serialized concatenated in a byte array [Px, Py, r] 159 ## If the length is less than 96 bytes, input is virtually padded with zeros. 160 ## If the length is greater than 96 bytes, input is truncated to 96 bytes. 161 ## 162 ## Output 163 ## - Output buffer MUST be of length 64 bytes 164 ## - A G1 point R = [s]P 165 ## - Status code: 166 ## cttEVM_Success 167 ## cttEVM_IntLargerThanModulus 168 ## cttEVM_PointNotOnCurve 169 ## 170 ## Spec https://eips.ethereum.org/EIPS/eip-196 171 172 if r.len != 64: 173 return cttEVM_InvalidOutputSize 174 175 # Auto-pad with zero 176 var padded: array[96, byte] 177 padded.rawCopy(0, inputs, 0, min(inputs.len, padded.len)) 178 179 var P{.noInit.}: ECP_ShortW_Jac[Fp[BN254_Snarks], G1] 180 181 let statusP = P.fromRawCoords( 182 x = padded.toOpenArray(0, 31), 183 y = padded.toOpenArray(32, 63)) 184 if statusP != cttEVM_Success: 185 return statusP 186 187 var smod{.noInit.}: Fr[BN254_Snarks] 188 var s{.noInit.}: BigInt[256] 189 s.unmarshal(padded.toOpenArray(64,95), bigEndian) 190 191 when true: 192 # The spec allows s to be bigger than the curve order r and the field modulus p. 193 # As, elliptic curve are a cyclic group mod r, we can reduce modulo r and get the same result. 194 # This allows to use windowed endomorphism acceleration 195 # which is 31.5% faster than plain windowed scalar multiplication 196 # at the low cost of a modular reduction. 197 198 # Due to mismatch between the BigInt[256] input and the rest being BigInt[254] 199 # we use the low-level getMont instead of 'fromBig' 200 getMont(smod.mres.limbs, s.limbs, 201 Fr[BN254_Snarks].fieldMod().limbs, 202 Fr[BN254_Snarks].getR2modP().limbs, 203 Fr[BN254_Snarks].getNegInvModWord(), 204 Fr[BN254_Snarks].getSpareBits()) 205 P.scalarMul_vartime(smod.toBig()) 206 else: 207 P.scalarMul_vartime(s) 208 209 var aff{.noInit.}: ECP_ShortW_Aff[Fp[BN254_Snarks], G1] 210 aff.affine(P) 211 212 r.toOpenArray(0, 31).marshal(aff.x, bigEndian) 213 r.toOpenArray(32, 63).marshal(aff.y, bigEndian) 214 return cttEVM_Success 215 216 func subgroupCheck(P: ECP_ShortW_Aff[Fp2[BN254_Snarks], G2]): bool = 217 ## A point may be on a curve but in case the curve has a cofactor != 1 218 ## that point may not be in the correct cyclic subgroup. 219 ## If we are on the subgroup of order r then [r]P = 0 220 var Q{.noInit.}: ECP_ShortW_Jac[Fp2[BN254_Snarks], G2] 221 Q.fromAffine(P) 222 return bool(Q.isInSubgroup()) 223 224 func fromRawCoords( 225 dst: var ECP_ShortW_Aff[Fp[BN254_Snarks], G1], 226 x, y: openarray[byte]): CttEVMStatus = 227 228 # Deserialization 229 # ---------------------- 230 # Encoding spec https://eips.ethereum.org/EIPS/eip-196 231 232 let status_x = dst.x.parseRawUint(x) 233 if status_x != cttEVM_Success: 234 return status_x 235 let status_y = dst.y.parseRawUint(y) 236 if status_y != cttEVM_Success: 237 return status_y 238 239 # Handle point at infinity 240 if dst.x.isZero().bool and dst.y.isZero().bool: 241 return cttEVM_Success 242 243 # Deserialization checks 244 # ---------------------- 245 246 # Point on curve 247 if not bool(isOnCurve(dst.x, dst.y, G1)): 248 return cttEVM_PointNotOnCurve 249 250 # BN254_Snarks is a curve with cofactor 1, 251 # so no subgroup checks are necessary 252 253 return cttEVM_Success 254 255 func fromRawCoords( 256 dst: var ECP_ShortW_Aff[Fp2[BN254_Snarks], G2], 257 x0, x1, y0, y1: openarray[byte]): CttEVMStatus = 258 259 # Deserialization 260 # ---------------------- 261 # Encoding spec https://eips.ethereum.org/EIPS/eip-196 262 263 let status_x0 = dst.x.c0.parseRawUint(x0) 264 if status_x0 != cttEVM_Success: 265 return status_x0 266 let status_x1 = dst.x.c1.parseRawUint(x1) 267 if status_x1 != cttEVM_Success: 268 return status_x1 269 270 let status_y0 = dst.y.c0.parseRawUint(y0) 271 if status_y0 != cttEVM_Success: 272 return status_y0 273 let status_y1 = dst.y.c1.parseRawUint(y1) 274 if status_y1 != cttEVM_Success: 275 return status_y1 276 277 # Handle point at infinity 278 if dst.x.isZero().bool and dst.y.isZero().bool: 279 return cttEVM_Success 280 281 # Deserialization checks 282 # ---------------------- 283 284 # Point on curve 285 if not bool(isOnCurve(dst.x, dst.y, G2)): 286 return cttEVM_PointNotOnCurve 287 288 if not subgroupCheck(dst): 289 return cttEVM_PointNotInSubgroup 290 291 return cttEVM_Success 292 293 func eth_evm_ecpairing*( 294 r: var openArray[byte], inputs: openarray[byte]): CttEVMStatus = 295 ## Elliptic Curve pairing on BN254_Snarks 296 ## (also called alt_bn128 in Ethereum specs 297 ## and bn256 in Ethereum tests) 298 ## 299 ## Name: ECPAIRING 300 ## 301 ## Inputs: 302 ## - An array of [(P0, Q0), (P1, Q1), ... (Pk, Qk)] points in (G1, G2) 303 ## 304 ## Output 305 ## - Output buffer MUST be of length 32 bytes 306 ## - 0 or 1 in uint256 BigEndian representation 307 ## - Status code: 308 ## cttEVM_Success 309 ## cttEVM_IntLargerThanModulus 310 ## cttEVM_PointNotOnCurve 311 ## cttEVM_InvalidInputSize 312 ## 313 ## Spec https://eips.ethereum.org/EIPS/eip-197 314 if r.len != 32: 315 return cttEVM_InvalidOutputSize 316 317 let N = inputs.len div 192 318 if inputs.len mod 192 != 0: 319 return cttEVM_InvalidInputSize 320 321 if N == 0: 322 # Spec: "Empty input is valid and results in returning one." 323 zeroMem(r[0].addr, r.len-1) 324 r[r.len-1] = byte 1 325 return cttEVM_Success 326 327 var P{.noInit.}: ECP_ShortW_Aff[Fp[BN254_Snarks], G1] 328 var Q{.noInit.}: ECP_ShortW_Aff[Fp2[BN254_Snarks], G2] 329 330 var acc {.noInit.}: MillerAccumulator[Fp[BN254_Snarks], Fp2[BN254_Snarks], Fp12[BN254_Snarks]] 331 acc.init() 332 var foundInfinity = false 333 334 for i in 0 ..< N: 335 let pos = i*192 336 337 let statusP = P.fromRawCoords( 338 x = inputs.toOpenArray(pos, pos+31), 339 y = inputs.toOpenArray(pos+32, pos+63)) 340 341 if statusP != cttEVM_Success: 342 return statusP 343 344 # Warning EIP197 encoding order: 345 # Fp2 (a, b) <=> a*𝑖 + b instead of regular a+𝑖b 346 let statusQ = Q.fromRawCoords( 347 x1 = inputs.toOpenArray(pos+64, pos+95), 348 x0 = inputs.toOpenArray(pos+96, pos+127), 349 y1 = inputs.toOpenArray(pos+128, pos+159), 350 y0 = inputs.toOpenArray(pos+160, pos+191)) 351 352 if statusQ != cttEVM_Success: 353 return statusQ 354 355 let regular = acc.update(P, Q) 356 if not regular: 357 foundInfinity = true 358 359 if foundInfinity: # pairing with infinity returns 1, hence no need to compute the following 360 zeroMem(r[0].addr, r.len-1) 361 r[r.len-1] = byte 1 362 return cttEVM_Success 363 364 var gt {.noinit.}: Fp12[BN254_Snarks] 365 acc.finish(gt) 366 gt.finalExp() 367 368 zeroMem(r[0].addr, r.len) 369 if gt.isOne().bool: 370 r[r.len-1] = byte 1 371 return cttEVM_Success 372 373 func eth_evm_modexp*(r: var openArray[byte], inputs: openArray[byte]): CttEVMStatus {.noInline, tags:[Alloca, Vartime], meter.} = 374 ## Modular exponentiation 375 ## 376 ## Name: MODEXP 377 ## 378 ## Inputs: 379 ## - `baseLen`: 32 bytes base integer length (in bytes) 380 ## - `exponentLen`: 32 bytes exponent length (in bytes) 381 ## - `modulusLen`: 32 bytes modulus length (in bytes) 382 ## - `base`: base integer (`baseLen` bytes) 383 ## - `exponent`: exponent (`exponentLen` bytes) 384 ## - `modulus`: modulus (`modulusLen` bytes) 385 ## 386 ## Output: 387 ## - baseᵉˣᵖᵒⁿᵉⁿᵗ (mod modulus) 388 ## The result buffer size `r` MUST match the modulusLen 389 ## - status code: 390 ## cttEVM_Success 391 ## cttEVM_InvalidInputSize if the lengths require more than 32-bit or 64-bit addressing (depending on hardware) 392 ## cttEVM_InvalidOutputSize 393 ## 394 ## Spec 395 ## Yellow Paper Appendix E 396 ## EIP-198 - https://github.com/ethereum/EIPs/blob/master/EIPS/eip-198.md 397 ## 398 ## Hardware considerations: 399 ## This procedure stack allocates a table of (16+1)*modulusLen and many stack temporaries. 400 ## Make sure to validate gas costs and reject large inputs to bound stack usage. 401 402 # Input parse sizes 403 # ----------------- 404 405 # Auto-pad with zero 406 var paddedLengths: array[96, byte] 407 paddedLengths.rawCopy(0, inputs, 0, min(inputs.len, paddedLengths.len)) 408 409 let 410 bL = BigInt[256].unmarshal(paddedLengths.toOpenArray(0, 31), bigEndian) 411 eL = BigInt[256].unmarshal(paddedLengths.toOpenArray(32, 63), bigEndian) 412 mL = BigInt[256].unmarshal(paddedLengths.toOpenArray(64, 95), bigEndian) 413 414 maxSize = BigInt[256].fromUint(high(uint)) # A CPU can only address up to high(uint) 415 416 # Input validation 417 # ----------------- 418 if bool(bL > maxSize): 419 return cttEVM_InvalidInputSize 420 if bool(eL > maxSize): 421 return cttEVM_InvalidInputSize 422 if bool(mL > maxSize): 423 return cttEVM_InvalidInputSize 424 425 let 426 baseByteLen = cast[int](bL.limbs[0]) 427 exponentByteLen = cast[int](eL.limbs[0]) 428 modulusByteLen = cast[int](mL.limbs[0]) 429 430 baseWordLen = baseByteLen.ceilDiv_vartime(WordBitWidth div 8) 431 modulusWordLen = modulusByteLen.ceilDiv_vartime(WordBitWidth div 8) 432 433 if r.len != modulusByteLen: 434 return cttEVM_InvalidOutputSize 435 436 # Special cases 437 # ---------------------- 438 if paddedLengths.len + baseByteLen + exponentByteLen >= inputs.len: 439 # Modulus value is in the infinitely right padded zeros input, hence is zero. 440 r.setZero() 441 return cttEVM_Success 442 443 if modulusByteLen == 0: 444 r.setZero() 445 return cttEVM_Success 446 447 if exponentByteLen == 0: 448 r.setZero() 449 r[r.len-1] = byte 1 # 0^0 = 1 and x^0 = 1 450 return cttEVM_Success 451 452 if baseByteLen == 0: 453 r.setZero() 454 return cttEVM_Success 455 456 # Input deserialization 457 # --------------------- 458 459 # Inclusive stops 460 # Due to special-case checks and early returns, 461 # only the modulus can require right-padding with zeros here 462 # inputs[expStop] cannot buffer overflow 463 let baseStart = paddedLengths.len 464 let baseStop = baseStart+baseByteLen-1 465 let expStart = baseStop+1 466 let expStop = expStart+exponentByteLen-1 467 let modStart = expStop+1 468 let modStop = modStart+modulusByteLen-1 469 470 # We assume that gas checks prevent numbers too big for stack allocation. 471 var baseBuf = allocStackArray(SecretWord, baseWordLen) 472 var modulusBuf = allocStackArray(SecretWord, modulusWordLen) 473 var outputBuf = allocStackArray(SecretWord, modulusWordLen) 474 475 template base(): untyped = baseBuf.toOpenArray(0, baseWordLen-1) 476 template exponent(): untyped = inputs.toOpenArray(expStart, expStop) 477 template modulus(): untyped = modulusBuf.toOpenArray(0, modulusWordLen-1) 478 template output(): untyped = outputBuf.toOpenArray(0, modulusWordLen-1) 479 480 # Base deserialization 481 base.toOpenArray(0, baseWordLen-1).unmarshal(inputs.toOpenArray(baseStart, baseStop), WordBitWidth, bigEndian) 482 483 # Modulus deserialization 484 let realLen = paddedLengths.len + baseByteLen + exponentByteLen + modulusByteLen 485 let overflowLen = realLen - inputs.len 486 if overflowLen > 0: 487 let physLen = inputs.len-modStart # Length of data physically present (i.e. excluding padded zeros) 488 var paddedModBuf = allocStackArray(byte, modulusByteLen) 489 template paddedMod(): untyped = paddedModBuf.toOpenArray(0, modulusByteLen-1) 490 491 paddedMod.rawCopy(0, inputs, modStart, physLen) 492 zeroMem(paddedMod[physLen].addr, overflowLen) 493 modulus.unmarshal(paddedMod, WordBitWidth, bigEndian) 494 else: 495 modulus.unmarshal(inputs.toOpenArray(modStart, modStop), WordBitWidth, bigEndian) 496 497 # Computation 498 # --------------------- 499 output.powMod_vartime(base, exponent, modulus, window = 4) 500 501 # Output serialization 502 # --------------------- 503 r.marshal(output, WordBitWidth, bigEndian) 504 return cttEVM_Success