Gadgets

const Gadgets: {
  "Field3": {
     "provable": {
        "fromValue": Field3;
        "toValue": bigint;
       };
     "from": Field3;
     "isConstant": boolean;
     "toBigint": bigint;
     "toBigints": [...{ [i in string | number | symbol]: bigint }[]];
    };
  "ForeignField": {
     "Sum": Sum;
     "add": Field3;
     "assertAlmostReduced": void;
     "assertLessThan": void;
     "assertLessThanOrEqual": void;
     "assertMul": void;
     "div": Field3;
     "inv": Field3;
     "mul": Field3;
     "neg": Field3;
     "sub": Field3;
     "sum": Field3;
    };
  "SHA256": SHA256;
  "addMod32": (x: Field, y: Field) => Field;
  "divMod32": (n: Field, quotientBits: number) => {
     "quotient": Field;
     "remainder": Field;
    };
  "and": Field;
  "compactMultiRangeCheck": [Field, Field, Field];
  "isDefinitelyInRangeN": Bool;
  "leftShift32": Field;
  "leftShift64": Field;
  "multiRangeCheck": void;
  "not": Field;
  "rangeCheck16": void;
  "rangeCheck32": void;
  "rangeCheck3x12": void;
  "rangeCheck64": [Field, Field, Field, Field];
  "rangeCheck8": void;
  "rangeCheckN": void;
  "rightShift64": Field;
  "rotate32": Field;
  "rotate64": Field;
  "xor": Field;
};

Type declaration

Field3

Field3: {
  "provable": {
     "fromValue": Field3;
     "toValue": bigint;
    };
  "from": Field3;
  "isConstant": boolean;
  "toBigint": bigint;
  "toBigints": [...{ [i in string | number | symbol]: bigint }[]];
};

Field3.provable

provable: {
  "fromValue": Field3;
  "toValue": bigint;
};

Provable<T> interface for Field3 = [Field, Field, Field].

Note: Witnessing this creates a plain tuple of field elements without any implicit range checks.

Field3.provable.fromValue()

Parameters

• x: bigint | Field3

Returns

Field3

Field3.provable.toValue()

Parameters

• x: Field3

Returns

bigint

Field3.from()

Turn a bigint into a 3-tuple of Fields

Parameters

• x: bigint | Field3

Returns

Field3

Field3.isConstant()

Check whether a 3-tuple of Fields is constant

Parameters

• x: Field3

Returns

boolean

Field3.toBigint()

Turn a 3-tuple of Fields into a bigint

Parameters

• x: Field3

Returns

bigint

Field3.toBigints()

Turn several 3-tuples of Fields into bigints

Type parameters

• T extends Tuple\<Field3>

Parameters

• ...xs: T

Returns

[...{ [i in string | number | symbol]: bigint }[]]

ForeignField

ForeignField: {
  "Sum": Sum;
  "add": Field3;
  "assertAlmostReduced": void;
  "assertLessThan": void;
  "assertLessThanOrEqual": void;
  "assertMul": void;
  "div": Field3;
  "inv": Field3;
  "mul": Field3;
  "neg": Field3;
  "sub": Field3;
  "sum": Field3;
};

Gadgets for foreign field operations.

A foreign field is a finite field different from the native field of the proof system.

The ForeignField namespace exposes operations like modular addition and multiplication, which work for any finite field of size less than 2^259.

Foreign field elements are represented as 3 limbs of native field elements. Each limb holds 88 bits of the total, in little-endian order.

All ForeignField gadgets expect that their input limbs are constrained to the range [0, 2^88). Range checks on outputs are added by the gadget itself.

ForeignField.Sum()

Lazy sum of Field3 elements, which can be used as input to Gadgets.ForeignField.assertMul.

Parameters

• x: Field3

Returns

Sum

ForeignField.add()

Foreign field addition: x + y mod f

The modulus f does not need to be prime.

Inputs and outputs are 3-tuples of native Fields. Each input limb is assumed to be in the range [0, 2^88), and the gadget is invalid if this is not the case. The result limbs are guaranteed to be in the same range.

Parameters

• x: Field3

left summand

• y: Field3

right summand

• f: bigint

modulus

Returns

Field3

x + y mod f

Example

let x = Provable.witness(Field3.provable, () => Field3.from(9n));
let y = Provable.witness(Field3.provable, () => Field3.from(10n));

// range check x and y
Gadgets.multiRangeCheck(x);
Gadgets.multiRangeCheck(y);

// compute x + y mod 17
let z = ForeignField.add(x, y, 17n);

Provable.log(z); // ['2', '0', '0'] = limb representation of 2 = 9 + 10 mod 17

Warning: The gadget does not assume that inputs are reduced modulo f, and does not prove that the result is reduced modulo f. It only guarantees that the result is in the correct residue class.

ForeignField.assertAlmostReduced()

Prove that each of the given Field3 elements is "almost" reduced modulo f, i.e., satisfies the assumptions required by Gadgets.ForeignField.mul and other gadgets:

each limb is in the range [0, 2^88)
the most significant limb is less or equal than the modulus, x[2] <= f[2]

Note: This method is most efficient when the number of input elements is a multiple of 3.

Parameters

• xs: Field3[]

• f: bigint

• __namedParameters= {}

• __namedParameters.skipMrc: undefined | boolean= false

Returns

void

Throws

if any of the assumptions is violated.

Example

let x = Provable.witness(Field3.provable, () => Field3.from(4n));
let y = Provable.witness(Field3.provable, () => Field3.from(5n));
let z = Provable.witness(Field3.provable, () => Field3.from(10n));

ForeignField.assertAlmostReduced([x, y, z], f);

// now we can use x, y, z as inputs to foreign field multiplication
let xy = ForeignField.mul(x, y, f);
let xyz = ForeignField.mul(xy, z, f);

// since xy is an input to another multiplication, we need to prove that it is almost reduced again!
ForeignField.assertAlmostReduced([xy], f); // TODO: would be more efficient to batch this with 2 other elements

ForeignField.assertLessThan()

Prove that x < f for any constant f < 2^264, or for another Field3 f.

If f is a finite field modulus, this means that the given field element is fully reduced modulo f. This is a stronger statement than ForeignField.assertAlmostReduced and also uses more constraints; it should not be needed in most use cases.

Note: This assumes that the limbs of x are in the range [0, 2^88), in contrast to ForeignField.assertAlmostReduced which adds that check itself.

Parameters

• x: Field3

• f: bigint | Field3

Returns

void

Throws

if x is greater or equal to f.

Example

let x = Provable.witness(Field3.provable, () => Field3.from(0x1235n));

 // range check limbs of x
Gadgets.multiRangeCheck(x);

// prove that x is fully reduced mod f
Gadgets.ForeignField.assertLessThan(x, f);

ForeignField.assertLessThanOrEqual()

Prove that x <= f for any constant f < 2^264, or for another Field3 f.

See ForeignField.assertLessThan for details and usage examples.

Parameters

• x: Field3

• f: bigint | Field3

Returns

void

ForeignField.assertMul()

Optimized multiplication of sums in a foreign field, for example: (x - y)*z = a + b + c mod f

Note: This is much more efficient than using Gadgets.ForeignField.add and Gadgets.ForeignField.sub separately to compute the multiplication inputs and outputs, and then using Gadgets.ForeignField.mul to constrain the result.

The sums passed into this method are "lazy sums" created with Gadgets.ForeignField.Sum. You can also pass in plain Field3 elements.

Assumptions: The assumptions on the summands are analogous to the assumptions described in Gadgets.ForeignField.mul:

each summand's limbs are in the range [0, 2^88)
summands that are part of a multiplication input satisfy x[2] <= f[2]

Parameters

• x: Field3 | Sum

• y: Field3 | Sum

• z: Field3 | Sum

• f: bigint

Returns

void

Throws

if the modulus is so large that the second assumption no longer suffices for validity of the multiplication. For small sums and moduli < 2^256, this will not fail.

Throws

if the provided multiplication result is not correct modulo f.

Example

// range-check x, y, z, a, b, c
ForeignField.assertAlmostReduced([x, y, z], f);
Gadgets.multiRangeCheck(a);
Gadgets.multiRangeCheck(b);
Gadgets.multiRangeCheck(c);

// create lazy input sums
let xMinusY = ForeignField.Sum(x).sub(y);
let aPlusBPlusC = ForeignField.Sum(a).add(b).add(c);

// assert that (x - y)*z = a + b + c mod f
ForeignField.assertMul(xMinusY, z, aPlusBPlusC, f);

ForeignField.div()

Foreign field division: x * y^(-1) mod f

See Gadgets.ForeignField.mul for assumptions on inputs and usage examples.

This gadget adds an extra bound check on the result, so it can be used directly in another foreign field multiplication.

Parameters

• x: Field3

• y: Field3

• f: bigint

Returns

Field3

Throws

Different than Gadgets.ForeignField.mul, this fails on unreduced input x, because it checks that x === (x/y)*y and the right side will be reduced.

ForeignField.inv()

Foreign field inverse: x^(-1) mod f

See Gadgets.ForeignField.mul for assumptions on inputs and usage examples.

This gadget adds an extra bound check on the result, so it can be used directly in another foreign field multiplication.

Parameters

• x: Field3

• f: bigint

Returns

Field3

ForeignField.mul()

Foreign field multiplication: x * y mod f

The modulus f does not need to be prime, but has to be smaller than 2^259.

Assumptions: In addition to the assumption that input limbs are in the range [0, 2^88), as in all foreign field gadgets, this assumes an additional bound on the inputs: x * y < 2^264 * p, where p is the native modulus. We usually assert this bound by proving that x[2] < f[2] + 1, where x[2] is the most significant limb of x. To do this, we use an 88-bit range check on 2^88 - x[2] - (f[2] + 1), and same for y. The implication is that x and y are almost reduced modulo f.

All of the above assumptions are checked by Gadgets.ForeignField.assertAlmostReduced.

Warning: This gadget does not add the extra bound check on the result. So, to use the result in another foreign field multiplication, you have to add the bound check on it yourself, again.

Parameters

• x: Field3

• y: Field3

• f: bigint

Returns

Field3

Example

// example modulus: secp256k1 prime
let f = (1n << 256n) - (1n << 32n) - 0b1111010001n;

let x = Provable.witness(Field3.provable, () => Field3.from(f - 1n));
let y = Provable.witness(Field3.provable, () => Field3.from(f - 2n));

// range check x, y and prove additional bounds x[2] <= f[2]
ForeignField.assertAlmostReduced([x, y], f);

// compute x * y mod f
let z = ForeignField.mul(x, y, f);

Provable.log(z); // ['2', '0', '0'] = limb representation of 2 = (-1)*(-2) mod f

ForeignField.neg()

Foreign field negation: -x mod f = f - x

See ForeignField.add for assumptions and usage examples.

Parameters

• x: Field3

• f: bigint

Returns

Field3

Throws

fails if x > f, where f - x < 0.

ForeignField.sub()

Foreign field subtraction: x - y mod f

See Gadgets.ForeignField.add for assumptions and usage examples.

Parameters

• x: Field3

• y: Field3

• f: bigint

Returns

Field3

Throws

fails if x - y < -f, where the result cannot be brought back to a positive number by adding f once.

ForeignField.sum()

Foreign field sum: xs[0] + signs[0] * xs[1] + ... + signs[n-1] * xs[n] mod f

This gadget takes a list of inputs and a list of signs (of size one less than the inputs), and computes a chain of additions or subtractions, depending on the sign. A sign is of type 1n | -1n, where 1n represents addition and -1n represents subtraction.

Note: For 3 or more inputs, sum() uses fewer constraints than a sequence of add() and sub() calls, because we can avoid range checks on intermediate results.

See Gadgets.ForeignField.add for assumptions on inputs.

Parameters

• xs: Field3[]

• signs: (1n | -1n)[]

• f: bigint

Returns

Field3

Example

let x = Provable.witness(Field3.provable, () => Field3.from(4n));
let y = Provable.witness(Field3.provable, () => Field3.from(5n));
let z = Provable.witness(Field3.provable, () => Field3.from(10n));

// range check x, y, z
Gadgets.multiRangeCheck(x);
Gadgets.multiRangeCheck(y);
Gadgets.multiRangeCheck(z);

// compute x + y - z mod 17
let sum = ForeignField.sum([x, y, z], [1n, -1n], 17n);

Provable.log(sum); // ['16', '0', '0'] = limb representation of 16 = 4 + 5 - 10 mod 17

SHA256

SHA256: {
  "hash": Bytes;
};

Implementation of the SHA256 hash function. Hash function with 256bit output.

Applies the SHA2-256 hash function to a list of byte-sized elements.

The function accepts Bytes as the input message, which is a type that represents a static-length list of byte-sized field elements (range-checked using Gadgets.rangeCheck8). Alternatively, you can pass plain number[], bigint[] or Uint8Array to perform a hash outside provable code.

Produces an output of Bytes that conforms to the chosen bit length.

Param

Bytes representing the message to hash.

let preimage = Bytes.fromString("hello world");
let digest = Gadgets.SHA256.hash(preimage);

SHA256.hash()

Parameters

• data: FlexibleBytes

Returns

Bytes

addMod32()

addMod32: (x: Field, y: Field) => Field;

Parameters

• x: Field

• y: Field

Returns

Field

divMod32()

divMod32: (n: Field, quotientBits: number) => {
  "quotient": Field;
  "remainder": Field;
};

Parameters

• n: Field

• quotientBits: number= 32

Returns

{
  "quotient": Field;
  "remainder": Field;
}

quotient

quotient: Field;

remainder

remainder: Field;

and()

Bitwise AND gadget on Field elements. Equivalent to the bitwise AND & operator in JavaScript. The AND gate works by comparing two bits and returning 1 if both bits are 1, and 0 otherwise.

It can be checked by a double generic gate that verifies the following relationship between the values below (in the process it also invokes the Gadgets.xor gadget which will create additional constraints depending on length).

The generic gate verifies:\ a + b = sum and the conjunction equation 2 * and = sum - xor\ Where:\ a + b = sum\ a ^ b = xor\ a & b = and

You can find more details about the implementation in the Mina book

The length parameter lets you define how many bits should be compared. length is rounded to the nearest multiple of 16, paddedLength = ceil(length / 16) * 16, and both input values are constrained to fit into paddedLength bits. The output is guaranteed to have at most paddedLength bits as well.

Note: Specifying a larger length parameter adds additional constraints.

Note: Both Field elements need to fit into 2^paddedLength - 1. Otherwise, an error is thrown and no proof can be generated. For example, with length = 2 (paddedLength = 16), and() will fail for any input that is larger than 2**16.

Parameters

• a: Field

• b: Field

• length: number

Returns

Field

Example

let a = Field(3);    // ... 000011
let b = Field(5);    // ... 000101

let c = Gadgets.and(a, b, 2);    // ... 000001
c.assertEquals(1);

compactMultiRangeCheck()

Compact multi-range check

This is a variant of multiRangeCheck where the first two variables are passed in combined form xy = x + 2^88*y.

The gadget

splits up xy into x and y
proves that xy = x + 2^88*y
proves that x, y, z are all in the range [0, 2^88).

The split form [x, y, z] is returned.

Parameters

• xy: Field

• z: Field

Returns

[Field, Field, Field]

Example

let [x, y] = Gadgets.compactMultiRangeCheck([xy, z]);

Throws

Throws an error if xy exceeds 2*88 = 176 bits, or if z exceeds 88 bits.

isDefinitelyInRangeN()

Returns a boolean which being true proves that x is in the range [0, 2^n).

Beware: The output being false does not prove that x is not in the range [0, 2^n). This should not be viewed as a standalone provable method but as an advanced helper function for gadgets which need a weakened form of range check.

Parameters

• n: number

The number of bits to be considered for the range check.

• x: Field

The value to be weakly range-checked.

Returns

Bool

a Bool that is definitely only true if the input is in the range [0, 2^n), but could also be false even if the input is in the range [0, 2^n).

Example

const x = Provable.witness(Field, () => Field(12345678n));
let definitelyInRange = Gadgets.isDefinitelyInRangeN(32, x); // could be true or false

leftShift32()

Performs a left shift operation on the provided Field element. This operation is similar to the << shift operation in JavaScript, where bits are shifted to the left, and the overflowing bits are discarded.

Important: The gadgets assumes that its input is at most 32 bits in size.

The output is range checked to 32 bits.

Parameters

• field: Field

Field element to shift.

• bits: number

Amount of bits to shift the Field element to the left. The amount should be between 0 and 32 (or else the shift will fail).

Returns

Field

Example

const x = Provable.witness(Field, () => Field(0b001100)); // 12 in binary
const y = Gadgets.leftShift32(x, 2); // left shift by 2 bits
y.assertEquals(0b110000); // 48 in binary

leftShift64()

Important: The gadgets assumes that its input is at most 64 bits in size.

If the input exceeds 64 bits, the gadget is invalid and fails to prove correct execution of the shift. Therefore, to safely use leftShift(), you need to make sure that the values passed in are range checked to 64 bits. For example, this can be done with Gadgets.rangeCheck64.

Parameters

• field: Field

Field element to shift.

• bits: number

Amount of bits to shift the Field element to the left. The amount should be between 0 and 64 (or else the shift will fail).

Returns

Field

Throws

Throws an error if the input value exceeds 64 bits.

Example

const x = Provable.witness(Field, () => Field(0b001100)); // 12 in binary
const y = Gadgets.leftShift64(x, 2); // left shift by 2 bits
y.assertEquals(0b110000); // 48 in binary

const xLarge = Provable.witness(Field, () => Field(12345678901234567890123456789012345678n));
leftShift64(xLarge, 32); // throws an error since input exceeds 64 bits

multiRangeCheck()

Multi-range check.

Proves that x, y, z are all in the range [0, 2^88).

This takes 4 rows, so it checks 88*3/4 = 66 bits per row. This is slightly more efficient than 64-bit range checks, which can do 64 bits in 1 row.

In particular, the 3x88-bit range check supports bigints up to 264 bits, which in turn is enough to support foreign field multiplication with moduli up to 2^259.

Parameters

• limbs: Field3

Returns

void

Example

Gadgets.multiRangeCheck([x, y, z]);

Throws

Throws an error if one of the input values exceeds 88 bits.

not()

Bitwise NOT gate on Field elements. Similar to the [bitwise NOT ~ operator in JavaScript](https://developer.mozilla.org/en-US/docs/ Web/JavaScript/Reference/Operators/Bitwise_NOT).

Note: The NOT gate only operates over the amount of bits specified by the length parameter.

A NOT gate works by returning 1 in each bit position if the corresponding bit of the operand is 0, and returning 0 if the corresponding bit of the operand is 1.

The length parameter lets you define how many bits to NOT.

Note: Specifying a larger length parameter adds additional constraints. The operation will fail if the length or the input value is larger than 254.

NOT is implemented in two different ways. If the checked parameter is set to true the Gadgets.xor gadget is reused with a second argument to be an all one bitmask the same length. This approach needs as many rows as an XOR would need for a single negation. If the checked parameter is set to false, NOT is implemented as a subtraction of the input from the all one bitmask. This implementation is returned by default if no checked parameter is provided.

You can find more details about the implementation in the Mina book

Parameters

• a: Field

The value to apply NOT to. The operation will fail if the value is larger than 254.

• length: number

The number of bits to be considered for the NOT operation.

• checked: boolean= false

Optional boolean to determine if the checked or unchecked not implementation is used. If it is set to true the Gadgets.xor gadget is reused. If it is set to false, NOT is implemented as a subtraction of the input from the all one bitmask. It is set to false by default if no parameter is provided.

Returns

Field

Example

// not-ing 4 bits with the unchecked version
let a = Field(0b0101);
let b = Gadgets.not(a,4,false);

b.assertEquals(0b1010);

// not-ing 4 bits with the checked version utilizing the xor gadget
let a = Field(0b0101);
let b = Gadgets.not(a,4,true);

b.assertEquals(0b1010);

Throws

Throws an error if the input value exceeds 254 bits.

rangeCheck16()

Parameters

• x: Field

Returns

void

rangeCheck32()

Asserts that the input value is in the range [0, 2^32).

This function proves that the provided field element can be represented with 32 bits. If the field element exceeds 32 bits, an error is thrown.

Parameters

• x: Field

The value to be range-checked.

Returns

void

Throws

Throws an error if the input value exceeds 32 bits.

Example

const x = Provable.witness(Field, () => Field(12345678n));
Gadgets.rangeCheck32(x); // successfully proves 32-bit range

const xLarge = Provable.witness(Field, () => Field(12345678901234567890123456789012345678n));
Gadgets.rangeCheck32(xLarge); // throws an error since input exceeds 32 bits

Note: Small "negative" field element inputs are interpreted as large integers close to the field size, and don't pass the 32-bit check. If you want to prove that a value lies in the int32 range [-2^31, 2^31), you could use rangeCheck32(x.add(1n << 31n)).

rangeCheck3x12()

Checks that three Field elements are in the range [0, 2^12) (using only one row).

Internally, this gadget relies on the 12-bit range check table. All three inputs are checked to be included in that table.

It's possible to use this as a range check for bit lengths n < 12, by passing in two values.

the value to be checked, x, to prove that x in [0, 2^12)
x scaled by 2^(12 - n), to prove that either x in [0, 2^n) or x * 2^(12 - n) overflows the field size (which is excluded by the first check)

Note that both of these checks are necessary to prove x in [0, 2^n).

You can find more details about lookups in the Mina book

Parameters

• v0: Field

The first Field element to be checked.

• v1: Field

The second Field element to be checked.

• v2: Field

The third Field element to be checked.

Returns

void

Throws

Throws an error if one of the input values exceeds 2^12.

Example

let a = Field(4000);
rangeCheck3x12(a, Field(0), Field(0)); // works, since `a` is less than 12 bits

let aScaled = a.mul(1 << 4); // scale `a`, to assert that it's less than 8 bits
rangeCheck3x12(a, aScaled, Field(0)); // throws an error, since  `a` is greater than 8 bits (and so `aScaled` is greater than 12 bits)

rangeCheck64()

Asserts that the input value is in the range [0, 2^64).

This function proves that the provided field element can be represented with 64 bits. If the field element exceeds 64 bits, an error is thrown.

Parameters

• x: Field

The value to be range-checked.

Returns

[Field, Field, Field, Field]

Throws

Throws an error if the input value exceeds 64 bits.

Example

const x = Provable.witness(Field, () => Field(12345678n));
Gadgets.rangeCheck64(x); // successfully proves 64-bit range

const xLarge = Provable.witness(Field, () => Field(12345678901234567890123456789012345678n));
Gadgets.rangeCheck64(xLarge); // throws an error since input exceeds 64 bits

Note: Small "negative" field element inputs are interpreted as large integers close to the field size, and don't pass the 64-bit check. If you want to prove that a value lies in the int64 range [-2^63, 2^63), you could use rangeCheck64(x.add(1n << 63n)).

Advanced usage: This returns the 4 highest limbs of x, in reverse order, i.e. [x52, x40, x28, x16]. This is useful if you want to do a range check for 52, 40, 28, or 16 bits instead of 64, by constraining some of the returned limbs to be 0.

rangeCheck8()

Asserts that the input value is in the range [0, 2^8).

See Gadgets.rangeCheck64 for analogous details and usage examples.

Parameters

• x: Field

Returns

void

rangeCheckN()

Asserts that the input value is in the range [0, 2^n). n must be a multiple of 16.

This function proves that the provided field element can be represented with n bits. If the field element exceeds n bits, an error is thrown.

Parameters

• n: number

The number of bits to be considered for the range check.

• x: Field

The value to be range-checked.

• message?: string

Optional message to be displayed when the range check fails.

Returns

void

Throws

Throws an error if the input value exceeds n bits.

Example

const x = Provable.witness(Field, () => Field(12345678n));
Gadgets.rangeCheckN(32, x); // successfully proves 32-bit range

const xLarge = Provable.witness(Field, () => Field(12345678901234567890123456789012345678n));
Gadgets.rangeCheckN(32, xLarge); // throws an error since input exceeds 32 bits

rightShift64()

Performs a right shift operation on the provided Field element. This is similar to the >> shift operation in JavaScript, where bits are moved to the right. The rightShift64 function utilizes the rotation method internally to implement this operation.

It’s important to note that these operations are performed considering the big-endian 64-bit representation of the number, where the most significant (64th) bit is on the left end and the least significant bit is on the right end.

Important: The gadgets assumes that its input is at most 64 bits in size.

If the input exceeds 64 bits, the gadget is invalid and fails to prove correct execution of the shift. To safely use rightShift64(), you need to make sure that the value passed in is range-checked to 64 bits; for example, using Gadgets.rangeCheck64.

Parameters

• field: Field

Field element to shift.

• bits: number

Amount of bits to shift the Field element to the right. The amount should be between 0 and 64 (or else the shift will fail).

Returns

Field

Throws

Throws an error if the input value exceeds 64 bits.

Example

const x = Provable.witness(Field, () => Field(0b001100)); // 12 in binary
const y = Gadgets.rightShift64(x, 2); // right shift by 2 bits
y.assertEquals(0b000011); // 3 in binary

const xLarge = Provable.witness(Field, () => Field(12345678901234567890123456789012345678n));
rightShift64(xLarge, 32); // throws an error since input exceeds 64 bits

rotate32()

A (left and right) rotation operates similarly to the shift operation (<< for left and >> for right) in JavaScript, with the distinction that the bits are circulated to the opposite end of a 32-bit representation rather than being discarded. For a left rotation, this means that bits shifted off the left end reappear at the right end. Conversely, for a right rotation, bits shifted off the right end reappear at the left end.

It’s important to note that these operations are performed considering the big-endian 32-bit representation of the number, where the most significant (32th) bit is on the left end and the least significant bit is on the right end. The direction parameter is a string that accepts either 'left' or 'right', determining the direction of the rotation.

Important: The gadget assumes that its input is at most 32 bits in size.

If the input exceeds 32 bits, the gadget is invalid and fails to prove correct execution of the rotation. To safely use rotate32(), you need to make sure that the value passed in is range-checked to 32 bits; for example, using Gadgets.rangeCheck32.

Parameters

• field: Field

Field element to rotate.

• bits: number

amount of bits to rotate this Field element with.

• direction: "left" | "right"= 'left'

left or right rotation direction.

Returns

Field

Throws

Throws an error if the input value exceeds 32 bits.

Example

const x = Provable.witness(Field, () => Field(0b001100));
const y = Gadgets.rotate32(x, 2, 'left'); // left rotation by 2 bits
const z = Gadgets.rotate32(x, 2, 'right'); // right rotation by 2 bits
y.assertEquals(0b110000);
z.assertEquals(0b000011);

const xLarge = Provable.witness(Field, () => Field(12345678901234567890123456789012345678n));
Gadgets.rotate32(xLarge, 32, "left"); // throws an error since input exceeds 32 bits

rotate64()

A (left and right) rotation operates similarly to the shift operation (<< for left and >> for right) in JavaScript, with the distinction that the bits are circulated to the opposite end of a 64-bit representation rather than being discarded. For a left rotation, this means that bits shifted off the left end reappear at the right end. Conversely, for a right rotation, bits shifted off the right end reappear at the left end.

It’s important to note that these operations are performed considering the big-endian 64-bit representation of the number, where the most significant (64th) bit is on the left end and the least significant bit is on the right end. The direction parameter is a string that accepts either 'left' or 'right', determining the direction of the rotation.

Important: The gadget assumes that its input is at most 64 bits in size.

If the input exceeds 64 bits, the gadget is invalid and fails to prove correct execution of the rotation. To safely use rotate64(), you need to make sure that the value passed in is range-checked to 64 bits; for example, using Gadgets.rangeCheck64.

You can find more details about the implementation in the Mina book

Parameters

• field: Field

Field element to rotate.

• bits: number

amount of bits to rotate this Field element with.

• direction: "left" | "right"= 'left'

left or right rotation direction.

Returns

Field

Throws

Throws an error if the input value exceeds 64 bits.

Example

const x = Provable.witness(Field, () => Field(0b001100));
const y = Gadgets.rotate64(x, 2, 'left'); // left rotation by 2 bits
const z = Gadgets.rotate64(x, 2, 'right'); // right rotation by 2 bits
y.assertEquals(0b110000);
z.assertEquals(0b000011);

const xLarge = Provable.witness(Field, () => Field(12345678901234567890123456789012345678n));
Gadgets.rotate64(xLarge, 32, "left"); // throws an error since input exceeds 64 bits

xor()

Bitwise XOR gadget on Field elements. Equivalent to the bitwise XOR ^ operator in JavaScript. A XOR gate works by comparing two bits and returning 1 if two bits differ, and 0 if two bits are equal.

This gadget builds a chain of XOR gates recursively. Each XOR gate can verify 16 bit at most. If your input elements exceed 16 bit, another XOR gate will be added to the chain.

Note: Specifying a larger length parameter adds additional constraints.

It is also important to mention that specifying a smaller length allows the verifier to infer the length of the original input data (e.g. smaller than 16 bit if only one XOR gate has been used). A zkApp developer should consider these implications when choosing the length parameter and carefully weigh the trade-off between increased amount of constraints and security.

Important: Both Field elements need to fit into 2^paddedLength - 1. Otherwise, an error is thrown and no proof can be generated.

For example, with length = 2 (paddedLength = 16), xor() will fail for any input that is larger than 2**16.

You can find more details about the implementation in the Mina book

Parameters

• a: Field

Field element to compare.

• b: Field

Field element to compare.

• length: number

amount of bits to compare.

Returns

Field

Throws

Throws an error if the input values exceed 2^paddedLength - 1.

Example

let a = Field(0b0101);
let b = Field(0b0011);

let c = Gadgets.xor(a, b, 4); // xor-ing 4 bits
c.assertEquals(0b0110);

Source

lib/provable/gadgets/gadgets.ts:36

Type declaration​

Field3​

Field3.provable​

Field3.provable.fromValue()​

Parameters​

Returns​

Field3.provable.toValue()​

Parameters​

Returns​

Field3.from()​

Parameters​

Returns​

Field3.isConstant()​

Parameters​

Returns​

Field3.toBigint()​

Parameters​

Returns​

Field3.toBigints()​

Type parameters​

Parameters​

Returns​

ForeignField​

ForeignField.Sum()​

Parameters​

Returns​

ForeignField.add()​

Parameters​

Returns​

Example​

ForeignField.assertAlmostReduced()​

Parameters​

Returns​

Throws​

Example​

ForeignField.assertLessThan()​

Parameters​

Returns​

Throws​

Example​

ForeignField.assertLessThanOrEqual()​

Parameters​

Returns​

ForeignField.assertMul()​

Parameters​

Returns​

Throws​

Throws​

Example​

ForeignField.div()​

Parameters​

Returns​

Throws​

ForeignField.inv()​

Parameters​

Returns​

ForeignField.mul()​

Parameters​

Returns​

Example​

ForeignField.neg()​

Parameters​

Returns​

Throws​

ForeignField.sub()​

Parameters​

Returns​

Throws​

ForeignField.sum()​

Parameters​

Returns​

Example​

SHA256​

Param​

SHA256.hash()​

Parameters​

Returns​

addMod32()​

Parameters​

Returns​

Type declaration

Field3

Field3.provable

Field3.provable.fromValue()

Parameters

Returns

Field3.provable.toValue()

Parameters

Returns

Field3.from()

Parameters

Returns

Field3.isConstant()

Parameters

Returns

Field3.toBigint()

Parameters

Returns

Field3.toBigints()

Type parameters

Parameters

Returns

ForeignField

ForeignField.Sum()

Parameters

Returns

ForeignField.add()

Parameters

Returns

Example

ForeignField.assertAlmostReduced()

Parameters

Returns

Throws

Example

ForeignField.assertLessThan()

Parameters

Returns

Throws

Example

ForeignField.assertLessThanOrEqual()

Parameters

Returns

ForeignField.assertMul()

Parameters

Returns

Throws

Throws

Example

ForeignField.div()

Parameters

Returns

Throws

ForeignField.inv()

Parameters

Returns

ForeignField.mul()

Parameters

Returns

Example

ForeignField.neg()

Parameters

Returns

Throws

ForeignField.sub()

Parameters

Returns

Throws

ForeignField.sum()

Parameters

Returns

Example

SHA256

Param

SHA256.hash()

Parameters

Returns

addMod32()

Parameters

Returns