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: {
"compression": sha256Compression;
"createMessageSchedule": (M: UInt32[]) => 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.
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.compression()
compression: (H: UInt32[], W: UInt32[]) => UInt32[] = sha256Compression;
Performs the SHA-256 compression function on the given hash values and message schedule.
Parameters
• H: UInt32
[]
The initial or intermediate hash values (8-element array of UInt32).
• W: UInt32
[]
The message schedule (64-element array of UInt32).
Returns
UInt32
[]
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: UInt32
[]
The 512-bit message block (16-element array of UInt32).
Returns
UInt32
[]
The message schedule (64-element array of UInt32).
SHA256.initialState
get initialState(): UInt32[]
Returns
UInt32
[]
Source
lib/provable/gadgets/sha256.ts:105
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);