# 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

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

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

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

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.

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.

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

#### 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()

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.

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

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

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

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

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

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

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

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.

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

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