Field Arithmetic

Download quests in Questplay

Completing this quest requires knowledge in elliptic curve operations. If you are not read, we recommend trying our theory campaign first!

Take a look at contracts/ObsidianGates.sol, a contract that uses an elliptic curve signature scheme for access control. The contract itself requires no modification, but for it to work, we must implement the underlying elliptic curve (in FieldElement.sol and EllipticCurve.sol).

ObsidianGates uses the NIST P-256 curve, rather than the EVM's secp256k1 curve. The curve is given by the equation:

$y^{2} \equiv x^{3} + a x + b (m o d p) y^2 \equiv x^3 + ax +b \pmod p$

where:

$a = 0 x f f f f f f f f 00000001000000000000000000000000 f f f f f f f f f f f f f f f f f f f f f f f c a = \mathrm{0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc}$
$b = 0 x 5 a c 635 d 8 a a 3 a 93 e 7 b 3 e b b d 55769886 b c 651 d 06 b 0 c c 53 b 0 f 63 b c e 3 c 3 e 27 d 2604 b b = \mathrm{0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b}$
$p = 0 x f f f f f f f f 00000001000000000000000000000000 f f f f f f f f f f f f f f f f f f f f f f f f p = \mathrm{0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff}$

The curve is restricted over a prime field $F_{p} \mathbb{F}_p$ , which uses modulo arithmetic for all field calculations. Hence, before implementing this curve in Solidity, it would be useful to first create a user-defined type for the field element.

In contracts/FieldElement.sol, we have defined a new type Felt (aka field element), along with some user-defined operators for +, -, *, and ==.

Felt is uint256;
using {
  add as +, 
  sub as -, 
  mul as *,
  equals as ==, inv 
} for Felt global;

We want to define these operations to be modular operations under $p p$ . By doing so, we can later comfortably handle field arithmetic when implementing the NIST P-256 curve itself.

Your Task

In contracts/FieldElement.sol, implement the logic for add, sub, mul, equals, and inv. These functions must be implemented efficiently.

You can safely assume that all Felt inputs in functions will be within valid range (i.e., $\leq p \le p$ ).

Run tests in Questplay

The Obsidian Gates are imbued with elliptic curve magic. To restore them, we must first build from the ground up...