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

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

NOT adds the implementation for a NOT gate to the existing Gadgets namespace. A bitwise NOT is an operation that 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.

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