Skip to main content
info

zkApp programmability is not yet available on the Mina Mainnet, but zkApps can now be deployed on the Mina Devnet.

Bitwise Operations

Bitwise operations manipulate individual bits within a binary representation of a number. They can, at times, resemble boolean operations but apply to a sequence of bits instead of booleans. Bitwise operations are generally available in most programming languages, including TypeScript. o1js provides versions of them that operate on Field elements and result in the necessary circuit constraints to generate a zero knowledge proof of the computation. This is especially useful when implementing hashing algorithms such as SHA256.

In o1js, bitwise operations and their attendant helper functions are implemented as gadgets.

Bitwise operations:

Helper functions:

and()​

and(a: Field, b: Field, length: number) => Field

The bitwise and() gadget is a provable equivalent to the bitwise AND (&) operator in JavaScript. It receives two Field elements and compares the corresponding pairs of bits from the binary representation of each. The comparison returns 1 only if both bits are 1 and returns 0 if either bit is not 1. This results in a new binary number, which is returned as a Field element.

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

The length parameter:

  • Specifies how many bits to compare.
  • Adds more constraints for larger numbers.

Example:

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

not()​

not(a: Field, length: number, checked: boolean) => Field

The bitwise not() gadget is a provable equivalent to the Bitwise NOT (~) operator in JavaScript. It receives a Field element and negates each bit of its binary representation, turning all the 1s into 0s and all the 0s into 1s. It essentially flips all the bits in a Field element. This results in a new binary number, which is returned as a Field element.

The implementation varies depending on whether the input length is checked. Not checking the input length is more efficient. The input is subtracted from an all-ones bitmask (where all the bits in a binary sequence are set to 1). The tradeoff is that you need to know the input length up front. This is safe when the input Field is the result of some other proven operation with a known output length. When the input length is checked, however, the xor() gadget is reused. An all-ones bitmask of equal length to the input Field is supplied as the second argument. This results in the same operation with proven input length and more constraints.

The input Field must be 254 bits or less.

The length parameter:

  • Specifies how many bits to negate.
  • Adds more constraints for larger numbers.

The checked parameter:

  • Specifies whether to check the length of the input.
  • Defaults to false.

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

Example:

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

b.assertEquals(0b1010);

xor()​

xor(a: Field, b: Field, length: number) => Field

The xor() gadget is a provable equivalent to the Bitwise XOR (^) operator in JavaScript. It receives two Field elements and compares the corresponding pairs of bits from the binary representation of each. The comparison returns 1 if the bits differ and 0 if they are the same. This results in a new binary number, which is returned as a Field element.

The length parameter:

  • Specifies how many bits to compare.
  • Adds more constraints for larger numbers.

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

Example:

let a = Field(0b0101);
let b = Field(0b0011);

let c = Gadgets.xor(a, b, 4); // xor-ing 4 bits
c.assertEquals(0b0110);

leftShift32()​

leftShift32(field: Field, bits: number) => Field

The leftShift32() gadget is a provable equivalent to the Left shift (<<) operator in JavaScript. It moves the bits of a binary number to the left by the specified number of bits. Any bits that fall off the left side are discarded. 0s are padded in from the right. It returns a new Field element that is range-checked to 32 bits.

The input Field must not exceed 32 bits in size. You can use rangeCheck32 to ensure this.

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

leftShift64(field: Field, bits: number) => Field

The leftShift64() gadget is a provable equivalent to the Left shift (<<) operator in JavaScript. It moves the bits of a binary number to the left by the specified number of bits. Any bits that fall off the left side are discarded. 0s are padded in from the right. It returns a new Field element that is range-checked to 64 bits.

The input Field must not exceed 64 bits in size. You can use rangeCheck64 to ensure this.

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));
Gadgets.leftShift64(xLarge, 32); // throws an error since input exceeds 64 bits

rightShift64()​

rightShift64(field: Field, bits: number) => Field

The rightShift64() gadget is a provable equivalent to the Right shift (>>) operator in JavaScript. It moves the bits of a binary number to the right by the specified number of bits. Any bits that fall off the right side are discarded. 0s are padded in from the left. It returns a new Field element.

The input Field must not exceed 64 bits in size. You can use rangeCheck64 to ensure this.

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));
Gadgets.rightShift64(xLarge, 32); // throws an error since input exceeds 64 bits

rotate32()​

rotate32(field: Field, bits: number, direction: 'left' | 'right' = 'left') {
  return rotate32(field, bits, direction);
},

The rotate32() gadget performs provable bit rotation on 32-bit numbers. It is similar to left shift and right shift, except the bits that fall off the end wrap around to reappear on the opposite side instead of being discarded. It accepts a Field element, the number of bits to rotate, and a direction of left or right. The default direction is left.

The input Field must not exceed 32 bits in size. You can use rangeCheck32 to ensure this.

For implementation details, see ROTATION in the Mina book.

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

rotate64(field: Field, bits: number, direction: 'left' | 'right' = 'left') {
  return rotate64(field, bits, direction);
},

The rotate64() gadget performs provable bit rotation on 32-bit numbers. It is similar to left shift and right shift, except the bits that fall off the end wrap around to reappear on the opposite side instead of being discarded. It accepts a Field element, the number of bits to rotate, and a direction of left or right. The default direction is left.

The input Field must not exceed 64 bits in size. You can use rangeCheck64 to ensure this.

For implementation details, see ROTATION in the Mina book.

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

addMod32()​

addMod32(a: Field, b: Field) => Field

The addMod32() helper performs addition that overflows on 32-bit numbers, much like the int32 type. It returns the result of addition modulo 2^32 in a new Field element.

The input Fields must not exceed 32 bits in size. You can use rangeCheck32 to ensure this.

Example:

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

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

divMod32()​

divMod32(field: Field) => { remainder: Field, quotient: Field }

The divMod32() helper performs division modulo 2^32, decomposing a Field element into two 32-bit limbs, remainder and quotient. It returns a tuple of two Field elements.

The helper asserts that the input is no larger than 64 bits in size and that both outputs are no larger than 32 bits in size. It is, therefore, unnecessary to perform range checks.

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

rangeCheck32()​

rangeCheck32(x: Field) => void

The rangecheck32() helper asserts that the input Field does not exceed 32 bits in size. Note that small, negative inputs are interpreted as large integers close to the field size and will not pass the 32-bit check. To prove that a value lies in the int32 range [-2^31, 2^31), you can use rangeCheck32(x.add(1n << 31n)).

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

rangeCheck64()​

rangeCheck64(x: Field) => void

The rangecheck64() helper asserts that the input Field does not exceed 64 bits in size. Note that small, negative inputs are interpreted as large integers close to the field size and will not pass the 64-bit check. To prove that a value lies in the int64 range [-2^63, 2^63), use rangeCheck64(x.add(1n << 63n)).

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

multiRangeCheck()​

multiRangeCheck([x, y, z]: [Field, Field, Field]) => void

The multiRangeCheck() helper asserts that all three input Fields do not exceed 88 bits in size. This is done more efficiently than the standalone range check helpers. The 3x88-bit range check supports BigInts up to 264 bits, which is enough for foreign field multiplication with moduli up to 2^259.

Example:

const x = Provable.witness(Field, () => Field(12345678n));
const y = Provable.witness(Field, () => Field(12345678n));
const z = Provable.witness(Field, () => Field(12345678n));
const xLarge = Provable.witness(Field, () => Field(12345678901234567890123456789012345678n));

Gadgets.multiRangeCheck([x, y, z]); // succeeds
Gadgets.multiRangeCheck([xLarge, y, z]); // fails

compactMultiRangeCheck()​

compactMultiRangeCheck(xy: Field, z: Field) => [Field, Field, Field];

The compactMultiRangeCheck() helper is a variant of multiRangeCheck where the first two inputs x and y are passed in combined form xy = x + 2^88*y. It splits x and y, performs the range check, and returns x, y, and z separately.

Example:

let [x, y, z] = Gadgets.compactMultiRangeCheck([xy, z]);