Skip to main content
info

Please note that zkApp programmability is not yet available on Mina Mainnet, but zkApps can now be deployed to Berkeley Testnet.

Gadgets

Gadgets are low-level building blocks that accelerate special computations. Most gadgets build upon custom gates and act as low-level accelerators in the proof system.

Gadgets are elements in TypeScript that the lowest level gates in the proof system (addition, multiplication) into more sophisticated boolean operations (XOR, NOT). Gadgets in o1js simplify the process of creating new cryptographic primitives and make it possible to efficiently implement other crypto algorithms, such as SHA.

See https://docs.minaprotocol.com/zkapps/o1js-reference/modules#gadgets

The https://github.com/o1-labs/o1js/blob/main/src/lib/gadgets/gadgets.ts namespace (let's explain).

Bitwise Gadgets in o1js​

Bitwise operations work on two-bit patterns of equal lengths by positionally matching their individual bits.

and, xor, rot, not, range checks, left shift and right shift https://github.com/o1-labs/o1js/blob/main/src/lib/gadgets/gadgets.ts

and()​

and(a: Field, b: Field, length: number) {
    return and(a, b, length);

The bitwise and() gadget on Field elements is equivalent to the bitwise AND (&) operator in JavaScript.

  • The and() gadget works by comparing two bits and returns 1 only if both bits are 1, otherwise it returns 0.

  • Can be checked by a double generic gate that verifies the following relationship between the values. In the process, the and() gadget also invokes the xor() gadget that creates 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

For details about the implementation, see AND in the Mina book.

The length parameter:

  • Lets you define how many bits should be compared.
  • Rounds length to the nearest multiple of 16, paddedLength = ceil(length / 16) * 16.
  • Constrains both input values to fit into paddedLength bits.
  • Guarantees that the output is guaranteed to have at most paddedLength bits.
  • Note: Specifying a larger length parameter adds additional constraints.

Both Field elements must fit into 2^paddedLength - 1 or an error is thrown and no proof is generated.

With length = 2 (paddedLength = 16), and() fails for any input that is larger than 2**16.

Example:

let a = Field(3);    // ... 000011
let b = Field(5);    // ... 000101
let c = Gadgets.and(a, b, 2);    // ... 000001
c.assertEquals(1);

multiRangeCheck()​

Building block for non-native arithmetic with BigInt of size up to 264 bits. https://github.com/o1-labs/o1js/pull/1216

A building block for non-native arithmetic with BigInt of size up to 264 bits. A provable method for efficient 64-bit range checks using lookup tables. https://github.com/o1-labs/o1js/pull/1181


not()​

not(a: Field, length: number, checked: boolean = false) {
    return not(a, length, checked);
  },

A provable method to support bitwise shifting for native field elements. https://github.com/o1-labs/o1js/pull/1198

The bitwise not() gadget on Field elements is similar to the Bitwise NOT (~) operator in JavaScript.

The NOT gate operates only over the amount of bits specified by the length parameter. A bitwise NOT operation returns 1 in each bit position if the corresponding bit of the operand is 0, and returns 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 fails 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 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 requires 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. If not provided, the default implementation uses false.

For details about the implementation, see NOT in the Mina book.

Example not-ing 4 bits with the unchecked version:

let a = Field(0b0101);
let b = Gadgets.not(a,4,false);

b.assertEquals(0b1010);

Example not-ing 4 bits with the checked version using the xor() gadget:

let a = Field(0b0101);
let b = Gadgets.not(a,4,true);

b.assertEquals(0b1010);

where:

  • Parameter a is the value to apply NOT to. The operation fails if the value is larger than 254.
  • Parameter length is the number of bits to be considered for the NOT operation.
  • Parameter checked (???) is an optional boolean to determine if the checked or unchecked not implementation is used. If it

The operation throws an error if the input value exceeds 254 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.
  • @param x - The value to be range-checked.
  • @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)). */ rangeCheck64(x: Field) { return rangeCheck64(x); },

rotate()​

A provable method to support bitwise rotation for native field elements. https://github.com/o1-labs/o1js/pull/1182

A rotation, often referred to as a bitwise rotation, is an operation that shifts the bits of a binary number either to the left or to the right. In contrast to a standard shift operation, the bits that fall off the end are not discarded. Instead, they wrap around to the other end.

Rotate Left (ROL): In this operation, bits are shifted to the left. The bits that fall off the leftmost side wrap around and reappear on the rightmost side. Rotate Right (ROR): In this operation, bits are shifted to the right. The bits that fall off the rightmost side wrap around and reappear on the leftmost side.

The ROT implementation handles the constant case by using the added functionality in the bindings. For the prover case, how to implement?


left shift and right shift​

Provable methods that support bitwise shifting, an operation that moves the bits of a binary number to the left or right. Unlike rotation, the bits that fall off at the end are discarded and the vacant positions are filled with zeros.

handles the constant case by using the added functionality in the bindings. For the prover case,


https://github.com/o1-labs/o1js/pull/1194

xor()​

A provable method to support bitwise XOR operations for native field elements. https://github.com/o1-labs/o1js/pull/1177


Examples​

are all gadgets in ZkProgram? I see only rot, xor, and

https://github.com/o1-labs/o1js/blob/main/src/examples/zkprogram/gadgets.ts