Please note that zkApp programmability is not yet available on Mina Mainnet, but zkApps can now be deployed to Berkeley Testnet.
Foreign Field Arithmetic
A foreign field is a finite field different from the native field of the proof system. o1js exposes operations like modular addition and multiplication that work in any finite field of size less than 2^259.
Foreign fields are useful for implementing cryptographic algorithms in provable code. For example, you use them for verification of Ethereum-compatible ECDSA signatures (coming soon).
Why foreign fields?
If you already know what you need foreign fields for, you can skip this section.
For additional context, recall that the core data type in o1js is Field. It represents the field that is native to the proof system. In other words, addition and multiplication of Fields are the fundamental operations upon which all provable code is built. Because a lot of cryptography uses finite fields, o1js supports several crypto algorithms natively, with high efficiency. See classes and modules like Poseidon, PublicKey, PrivateKey, Signature and Encryption.
However, none of these are compatible with the cryptography used in the wider world: Signature.verify() doesn't let you verify a signed JWT or e-mail, and Encryption.decrypt() won't help you with your WhatsApp messages. That's because these use different finite fields than our native Field (which was chosen primarily to enable efficient zk proofs).
Here is where foreign fields come in: They let you perform algorithms that connect your zkApp with the outside world of cryptography. Foreign fields come with an efficiency hit compared to the native field, but we heavily engineered them to be efficient enough to unlock many interesting use cases.
Basic usage
What follows is a brief overview of how to use foreign fields. For more details, refer to the API reference or the doccomments on each method.
The entry point for using foreign fields is the createForeignField() function:
import { createForeignField } from 'o1js';
class Field17 extends createForeignField(17n) {}
The only parameter that createForeignField() takes is the modulus or size of the field. In the code example, you are passing in 17n, which means that SmallField allows you to perform arithmetic modulo 17 (yes, it's a toy example):
let x = Field17.from(16);
x.assertEquals(-1); // 16 = -1 (mod 17)
x.mul(x).assertEquals(1); // 16 * 16 = 15 * 17 + 1 = 1 (mod 17)
As modulus, any number of up to 259 bits is supported. This means that ForeignField can be used for many elliptic curve algorithms (where bit sizes are often just below 256), but not for RSA with its typical bit size of 2048.
Notably, the modulus does not have to be a prime number. For example, your can create a UInt256 class where the modulus is 2^256:
class UInt256 extends createForeignField(1n << 256n) {}
// and now you can do arithmetic modulo 2^256!
let a = UInt256.from(1n << 255n);
let b = UInt256.from((1n << 255n) + 7n);
a.add(b).assertEquals(7);
The base type that is common to classes created by createForeignField() is ForeignField:
import { ForeignField } from 'o1js';
// ...
let zero: ForeignField = Field17.from(0);
let alsoZero: ForeignField = UInt256.from(0);
ForeignField supports the basic arithmetic operations:
x.add(x); // addition
x.sub(2); // subtraction
x.neg(); // negation
x.mul(3); // multiplication
x.div(x); // division
x.inv(); // inverse
Note that these operations happen modulo the field size. So, Field17.from(1).div(2) gives 9 because 2 * 9 = 18 = 1 (mod 17).
ForeignField also comes with a few other provable methods:
x.assertEquals(y); // assert x == y
x.assertLessThan(2); // assert x < 2
let bits = x.toBits(); // convert to a `Bool` array of size log2(modulus);
Field17.fromBits(bits); // convert back
And there are non-provable methods for converting to and from JS values:
let y = SmallField.from(5n); // convert from bigint or number
y.toBigInt() === 5n; // convert to bigint
As usual, you can find more information about each method in the API reference.
The kinds of ForeignField
If the basic usage examples look straightforward, here is where it gets a bit complicated.
For each class created with createForeignField(), there are actually three different variants. We call them unreduced, almost reduced and canonical.
Unreduced fields
Most arithmetic operations return unreduced fields:
let z = x.add(x);
assert(z instanceof Field17.Unreduced);
In short, unreduced means that a value can be larger than the modulus.
For example, if x has the value 16, it is valid for x.add(x) to contain the value 32. The addition is correct modulo 17, but doesn't guarantee a result smaller than 17.
Unreduced doesn't usually mean that the underlying witness is larger than the modulus. It just means that we have not proved it to be smaller. A malicious prover could make it larger, by slightly modifying their local version of o1js and creating a proof with that.
Unreduced fields can be added and subtracted, but not be used in multiplication or division:
z.add(1).sub(x); // works
assert((z as any).mul === undefined); // z.mul() is not defined
assert((z as any).inv === undefined);
assert((z as any).div === undefined);
Almost reduced fields
To do multiplication, you need almost reduced fields. You can convert to that by using .assertAlmostReduced():
let zAlmost = z.assertAlmostReduced();
assert(zAlmost instanceof SmallField.AlmostReduced);
Now you can do multiplication and division:
let zz = zAlmost.mul(zAlmost); // zAlmost.mul() is defined
// but .mul() returns an unreduced field again:
assert(zz instanceof SmallField.Unreduced);
// zAlmost.inv() is defined, and returns an almost reduced result!
assert(zAlmost.inv() instanceof SmallField.AlmostReduced);
There is an exported base type common to all almost reduced fields:
import { AlmostReducedField } from 'o1js';
zAlmost satisfies AlmostReducedField;
The definition of almost reduced is somewhat technical and we won't dwell on it for too long. The main motivation is to guarantee that the way we prove modular multiplication is sound. That is definitely true for field elements < 2^259. (Recall that we require the modulus to be < 2^259).
However, we usually prove a stronger condition, which lets us save a few constraints in some places:
z is almost reduced modulo f, if z >> 176 is smaller or equal than f >> 176. (>> means a right shift.)
Example: Assume x is a Field17 holding the value 1. After computing z = x.mul(1), it is valid for z to be 1*1 + 2^256 * 17, which is larger than 2^260.
However, by calling z.assertAlmostReduced(), we prove that z is smaller than 2^259 and safe to use in another multiplication. According to our stronger definition, we even have z < 2^176.
Why are we exposing AlmostReducedField as a separate type, and don't always prove conditions necessary for multiplication?
To allow you to use the minimum amount of constraints, in a way that is safely guided by the type system!
Here is a trick to save constraints: It's most efficient to always reduce field elements in batches of 3. Do this when doing many multiplications in a row:
let z1 = x.mul(7);
let z2 = x.add(11);
let z3 = x.sub(13);
let [z1r, z2r, z3r] = Field17.assertAlmostReduced(z1, z2, z3);
z1r.mul(z2r);
z2r.div(z3r);
ForeignField.assertAlmostReduced() takes any number of inputs, but is most efficient when called with a multiple of 3 inputs.