Gadgets

y

Returns

Example

let a = Field(8n);
let b = Field(1n << 64n);

Gadgets.addMod64(a, b).assertEquals(Field(8n));

arrayGet()

arrayGet: (array: Field[], index: Field) => Field;

Get value from array at a Field element index, in O(n) constraints, where n is the array length.

Warning: This gadget assumes that the index is within the array bounds [0, n), and returns an unconstrained result otherwise. To use it with an index that is not already guaranteed to be within the array bounds, you should add a suitable range check.

let array = Provable.witnessFields(3, () => [1n, 2n, 3n]);
let index = Provable.witness(Field, () => 1n);

let value = Gadgets.arrayGet(array, index);

Note: This saves n constraints compared to Provable.switch(array.map((_, i) => index.equals(i)), type, array).

Get value from array in O(n) rows.

Assumes that index is in [0, n), returns an unconstrained result otherwise.

Note: This saves 0.5*n constraints compared to equals() + switch() even if equals() were implemented optimally.

Parameters

array

Field[]

index

Returns

arrayGetGeneric()

arrayGetGeneric: <T>(type: ProvableType<T>, array: T[], index: Field) => T;

Get value from array in O(n) constraints.

Assumes that index is in [0, n), returns an unconstrained result otherwise.

Get value from array in O(n) constraints.

Assumes that index is in [0, n), returns an unconstrained result otherwise.

Type Parameters

• T

Parameters

type

ProvableType<T>

array

T[]

index

Returns

T

BLAKE2B

BLAKE2B: {
  get IV: UInt64[];
  hash: Bytes;
};

Implementation of the BLAKE2b hash function. Hash function with arbitrary length output.

Applies the BLAKE2b 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 digest length.

Param

Bytes representing the message to hash.

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

BLAKE2B.IV

Get Signature

get IV(): UInt64[]

Defined in: lib/provable/gadgets/blake2b.ts:77

Returns

UInt64[]

BLAKE2B.hash()

Parameters

data

digestLength

number = 64

Returns

Bytes

Constants

Constants: {
  l: bigint;
  l2: bigint;
  l2Mask: bigint;
  l3: bigint;
  lMask: bigint;
};

Default limb size constants mostly used in range checks.

Constants.l

l: bigint;

Constants.l2

l2: bigint;

Constants.l2Mask

l2Mask: bigint;

Constants.l3

l3: bigint;

Constants.lMask

lMask: bigint;

divMod32()

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

Division modulo 2^32. The operation decomposes a Field element in the range [0, 2^64) into two 32-bit limbs, remainder and quotient, using the following equation: n = quotient * 2^32 + remainder.

Note: The gadget acts as a proof that the input is in the range [0, 2^64). If the input exceeds 64 bits, the gadget fails.

Asserts that both remainder and quotient are in the range [0, 2^32) using Gadgets.rangeCheck32.

Parameters

n

nBits

number = 64

Returns

{
  quotient: Field;
  remainder: Field;
}

quotient

quotient: Field;

remainder

remainder: Field;

Example

let n = Field((1n << 32n) + 8n)
let { remainder, quotient } = Gadgets.divMod32(n);
// remainder = 8, quotient = 1

n.assertEquals(quotient.mul(1n << 32n).add(remainder));

divMod64()

divMod64: (n: Field, nBits: number) => {
  quotient: Field;
  remainder: Field;
};

Division modulo 2^64. The operation decomposes a Field element in the range [0, 2^128) into two 64-bit limbs, remainder and quotient, using the following equation: n = quotient * 2^64 + remainder.

Note: The gadget acts as a proof that the input is in the range [0, 2^128). If the input exceeds 128 bits, the gadget fails.

Asserts that both remainder and quotient are in the range [0, 2^64) using Gadgets.rangeCheck64.

Parameters

n

nBits

number = 128

Returns

{
  quotient: Field;
  remainder: Field;
}

quotient

quotient: Field;

remainder

remainder: Field;

Example

let n = Field((1n << 64n) + 8n)
let { remainder, quotient } = Gadgets.divMod64(n);
// remainder = 8, quotient = 1

n.assertEquals(quotient.mul(1n << 64n).add(remainder));

Field3

Field3: {
  provable: {
     fromValue: Field3;
     toValue: bigint;
    };
  split: (x: bigint) => bigint3;
  from: Field3;
  isConstant: boolean;
  toBigint: bigint;
  toBigints: [...{ [i in string | number | symbol]: bigint }[]];
};

Helper methods to interact with 3-limb vectors of Fields.

Note: This interface does not contain any provable methods.

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.split()

split: (x: bigint) => bigint3;

Splits a bigint into three limbs using bitwise operations.

Parameters

x

bigint

Returns

bigint3

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: {
  sliceField3: (__namedParameters: Field3, __namedParameters: {
     chunkSize: number;
     maxBits: number;
    }) => Field[];
  add: Field3;
  assertEquals: void;
  assertLessThan: void;
  assertLessThanOrEqual: void;
  equals: Bool;
  neg: Field3;
  sub: Field3;
  sum: Field3;
  toCanonical: 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.sliceField3()

sliceField3: (__namedParameters: Field3, __namedParameters: {
  chunkSize: number;
  maxBits: number;
 }) => Field[];

Provable method for slicing a 3x88-bit bigint into smaller bit chunks of length chunkSize

This serves as a range check that the input is in [0, 2^maxBits)

Provable method for slicing a 3x88-bit bigint into smaller bit chunks of length chunkSize

This serves as a range check that the input is in [0, 2^maxBits)

Parameters

__namedParameters

Field3

__namedParameters

chunkSize

number

maxBits

number

Returns

Field[]

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, () => 9n);
let y = Provable.witness(Field3, () => 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.assertEquals()

Proves that x is equal to y.

Parameters

x

Field3

y

Field3

Returns

void

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, () => 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.equals()

Check whether x = c mod f

c is a constant, and we require c in [0, f)

Assumes that x is almost reduced modulo f, so we know that x might be c or c + f, but not c + 2f, c + 3f, ...

Parameters

x

Field3

c

bigint

f

bigint

Returns

Bool

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, () => 4n);
let y = Provable.witness(Field3, () => 5n);
let z = Provable.witness(Field3, () => 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

ForeignField.toCanonical()

Convert x, which may be unreduced, to a canonical representative xR < f such that x = xR mod f

Note: This method is complete, it works for all unreduced field elements. It can therefore be used to protect against incompleteness of field operations in other places.

Parameters

x

Field3

f

bigint

Returns

Field3

SHA2

SHA2: {
  compression: <T>(length: Length, H: T[], W: T[]) => T[];
  messageSchedule: <T>(length: Length, M: T[]) => T[];
  padding: <T>(length: Length, data: FlexibleBytes) => T[][];
  hash: Bytes;
  initialState: T[];
};

Implementation of the SHA2 hash function. Hash function with 224 | 256 | 384 | 512 bit output.

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

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

Param

224 | 256 | 384 | 512 representing the length of the hash.

Param

Bytes representing the message to hash.

let preimage = Bytes.fromString("hello world");
let digest = Gadgets.SHA2.hash(512, preimage);

SHA2.compression()

compression: <T>(length: Length, H: T[], W: T[]) => T[];

Performs the SHA-2 compression function on the given hash values and message schedule.

Type Parameters

• T extends UInt64 | UInt32

Parameters

length

Length

Whether this is a SHA2-224 or SHA2-256 or SHA2-384 or SHA2-512

H

T[]

The initial or intermediate hash values (8-element array of T).

W

T[]

The message schedule (64-element array of T).

Returns

T[]

The updated intermediate hash values after compression.

SHA2.messageSchedule()

messageSchedule: <T>(length: Length, M: T[]) => T[];

Prepares the message schedule for the SHA2 compression function from the given message block.

Type Parameters

• T extends UInt64 | UInt32

Parameters

length

Length

Whether this is a SHA2-224 or SHA2-256 or SHA2-384 or SHA2-512

M

T[]

The 512-bit message block (16-element array of UInt32) or the 1024-bit message block (16-element array of UInt64).

Returns

T[]

The message schedule (64-element array of UInt32 or 80-element array of UInt64).

SHA2.padding()

padding: <T>(length: Length, data: FlexibleBytes) => T[][];

Padding function for SHA2, as specified in §5.1.1, §5.1.2,

Type Parameters

• T extends UInt64 | UInt32

Parameters

length

Length

Whether this is a SHA2-224 or SHA2-256 or SHA2-384 or SHA2-512

data

The message to hash

Returns

T[][]

SHA2.hash()

Implementation of NIST SHA-2 hash Function. Supports output lengths of 224, 256, 384, or 512 bits.

Applies the SHA-2 hash function to a list of big-endian byte-sized Field elements, flexible to handle varying output lengths (224, 256, 384, 512 bits) as specified.

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[] of Uint8Array to perform a hash outside provable code.

Produces an output of Bytes that conforms to the chosen bit length. Both input and output bytes are big-endian.

Type Parameters

• T extends Length

Parameters

length

T

data

Returns

Bytes

SHA2.initialState()

Type Parameters

• T extends UInt64 | UInt32

Parameters

length

Length

Returns

T[]

SHA256

SHA256: {
  compression: (H: UInt32[], W: UInt32[]) => UInt32[];
  createMessageSchedule: (M: UInt32[]) => UInt32[];
  padding: (data: FlexibleBytes) => UInt32[][];
  get initialState: UInt32[];
  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.

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);

Deprecated

SHA256 is deprecated in favor of SHA2, which supports more variants of the hash function.

SHA256.compression()

compression: (H: UInt32[], W: UInt32[]) => UInt32[] = sha256Compression;

Performs the SHA-256 compression function on the given hash values and message schedule.

Parameters

H

The initial or intermediate hash values (8-element array of UInt32).

W

The message schedule (64-element array of UInt32).

Returns

The updated intermediate hash values after compression.

SHA256.createMessageSchedule()

createMessageSchedule: (M: UInt32[]) => UInt32[];

Prepares the message schedule for the SHA-256 compression function from the given message block.

Parameters

M

The 512-bit message block (16-element array of UInt32).

Returns

The message schedule (64-element array of UInt32).

SHA256.padding()

padding: (data: FlexibleBytes) => UInt32[][];

Parameters

data

Returns

UInt32[][]

SHA256.initialState

Get Signature

get initialState(): UInt32[]

Defined in: lib/provable/gadgets/sha256.ts:103

Returns

SHA256.hash()

Parameters

data

Returns

Bytes

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

b

length

number

Returns

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

z

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.

inTable()

In-circuit check that up to 3 pairs of index and value are in the runtime table given by the identifier. Each given pair is a tuple composed of a bigint and a Field.

Internally, it creates a lookup gate for the three pairs. If fewer pairs are given, the remaining pairs are duplicates of the first one.

Parameters

id

number

pair0

[bigint, Field]

pair1?

[bigint, Field]

pair2?

[bigint, Field]

Returns

void

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

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 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

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 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

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

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

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.

or()

Bitwise OR gadget on Field elements. Equivalent to the bitwise OR | operator in JavaScript. The OR gate works by comparing two bits and returning 1 if at least one bit is 1, and 0 otherwise.

Note: Specifying a larger length parameter adds additional constraints.

Parameters

a

b

length

number

Returns

Example

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

let c = Gadgets.or(a, b, 16);    // ... 000111
c.assertEquals(7);

rangeCheck16()

Parameters

x

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

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

The first Field element to be checked.

v1

The second Field element to be checked.

v2

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

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

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

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 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

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 element to rotate.

bits

number

amount of bits to rotate this Field element with.

direction

left or right rotation direction.

"left" | "right"

Returns

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 element to rotate.

bits

number

amount of bits to rotate this Field element with.

direction

left or right rotation direction.

"left" | "right"

Returns

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 element to compare.

b

Field element to compare.

length

number

amount of bits to compare.

Returns