Issue with LessThan Function: No Support for Field Elements Greater Than 253 Bits

[shreyas-londhe]

Hello,

I am currently developing a Zero-Knowledge (ZK) application and have encountered a limitation with the lessThan function in the Field class. Specifically, the function seems to only support field elements of size less than or equal to 253 bits.

In my particular use case, I need to work with field elements that are larger than 253 bits. This limitation is causing a significant roadblock in the development of my application.

I am referring to the implementation found at this location: https://github.com/o1-labs/snarkyjs/blob/main/src/lib/field.ts#L699

I would greatly appreciate any guidance or potential solutions to overcome this limitation. Is there a workaround or an alternative function that I could use to compare larger field elements? Or is there a plan to extend the lessThan function to support larger field elements in the future?

Thank you in advance for your assistance and I look forward to your response.

[mitschabaude]

I'm sure we can help you implement something custom with existing snarkyjs methods.
Can provide more details on what field elements you want to compare? Are they "random" elements (or hash outputs, or something like that)? In that case we can assume they are 254 bit with overwhelming probability. You might have a look at Field.isEven() and see how it decomposes a 254 bit Field element into a 253 bit high part and a 1 bit low part (the parity bit).
You might be able to work out a solution from that (if not I can help)

[shreyas-londhe]

Hi, I implemented a lessThanWrapper to do what you suggested, but it turns out that the numbers are 255 bits. Any other solution for this?

Code:

import { Field, Provable } from 'snarkyjs';
import { Snarky } from 'snarkyjs/dist/node/snarky';
import { FieldConst } from 'snarkyjs/dist/node/lib/field';
import { Field as Fp } from 'snarkyjs/dist/node/provable/field-bigint';

const separateHighPart = (x: Field): [Field, Field] => {
  let [, isOddVar, xDiv2Var] = Snarky.exists(2, () => {
    let bits = Fp.toBits(x.toBigInt());
    Provable.log('bitlen', bits.length);
    let isOdd = bits.shift()! ? 1n : 0n;

    return [
      0,
      FieldConst.fromBigint(isOdd),
      FieldConst.fromBigint(Fp.fromBits(bits)),
    ];
  });
  return [new Field(xDiv2Var), new Field(isOddVar)];
};

export const lessThanWrapper = (a: Field, b: Field) => {
  let [aHigh, aParity] = separateHighPart(a);
  let [bHigh, bParity] = separateHighPart(b);

  Provable.log('aHigh', aHigh);
  Provable.log('aParity', aParity);
  Provable.log('bHigh', bHigh);
  Provable.log('bParity', bParity);

  let highPartLessThan = aHigh.lessThan(bHigh);
  let highPartEqual = aHigh.equals(bHigh);
  let parityLessThan = aParity.lessThan(bParity);

  return highPartLessThan.or(highPartEqual.and(parityLessThan)).toField();
};

[mitschabaude]

You can treat 255 bit numbers equivalently, instead of splitting them into 1 + 253 bits you split them into 2 + 253 bits.
Also, FYI, there is Provable.witness() which is a more user friendly version of exists() and is exported from snarkyjs

[shreyas-londhe]

Hey, thanks for the solution. I am running into the problem where one of the input to the lessThan function is a negative number, so that is very near to the Modulus, so i guess that's why it's going beyond 253 bits and the functions fails. What is the ideal thing to do in such a case?

[mitschabaude]

@shryasss I was suggesting that you split it into 2 + 253 in this case.

If you know that inputs are smallish negative or positive numbers, say they have an absolute value < MAX, then there is an even easier solution: check whether
x + MAX < y + MAX
so that both sides become smallish positive numbers

[shreyas-londhe]

Yes, I have implemented a lessThanWrapper to handle case where input is >253 bits.

import { Field, Provable } from 'snarkyjs';
import { Snarky } from 'snarkyjs/dist/node/snarky';
import { FieldConst } from 'snarkyjs/dist/node/lib/field';
import { Field as Fp } from 'snarkyjs/dist/node/provable/field-bigint';

const separateHighPart = (x: Field): [Field, Field] => {
  let [, isOddVar, xDiv2Var] = Snarky.exists(2, () => {
    let bits = Fp.toBits(x.toBigInt());
    let highPart = [];
    for (let i = 0; i < 2; i++) {
      highPart.push(bits.shift()! ? 1n : 0n);
    }

    return [
      0,
      FieldConst.fromBigint(Fp.fromBits(highPart.map((x) => x === 1n))),
      FieldConst.fromBigint(Fp.fromBits(bits)),
    ];
  });
  return [new Field(xDiv2Var), new Field(isOddVar)];
};

export const lessThanWrapper = (a: Field, b: Field) => {
  let [aHigh, aLow] = separateHighPart(a);
  let [bHigh, bLow] = separateHighPart(b);

  let highPartLessThan = aHigh.lessThan(bHigh);
  let lowPartLessThan = aLow.lessThan(bLow);

  return highPartLessThan
    .or(lowPartLessThan.and(aHigh.equals(bHigh)))
    .toField();
};

But as you mentioned in the last response, the inputs might not be smallish, as a negative number will be very close to the Field Order, so it won't be smallish.

Also, if I do -- x + Max < y + Max, won't it be equivalent to -- x < y, I am not able to understand the difference here.

Thanks for the prompt responses, appreciate it a lot!

[mitschabaude]

Also, if I do -- x + Max < y + Max, won't it be equivalent to -- x < y, I am not able to understand the difference here

Yeah that's the point, it's equivalent but both sides are small, by adding MAX you turn the "negative" (close to field order) into a small positive number, so it no longer has too many bits

Also, does your 2 + 253 bit solution above not work?

[shreyas-londhe]

Yeah that's the point, it's equivalent but both sides are small, by adding MAX you turn the "negative" (close to field order) into a small positive number, so it no longer has too many bits

I think the problem here will be that if only one of the input is close to the Field Order, then if I add the modulus to both the numbers, then the other number becomes close to the Field Order. Any thoughts on this?

Also, does your 2 + 253 bit solution above not work

Yes, it works

[mitschabaude]

I think the problem here will be that if only one of the input is close to the Field Order, then if I add the modulus to both the numbers, then the other number becomes close to the Field Order. Any thoughts on this?

I didn't suggest to add the modulus, but some number MAX that's large enough to make all your inputs positive but small enough so that x + MAX is less than 253 for all your inputs. Of course, it depends on the application whether such a number exists. As I wrote above, this is applicable if all your inputs are either small negative or small positive numbers (as is the case for many applications)

[shreyas-londhe]

Ohh right, got it. It makes a lot of sense to do that. Thanks, will try to implement this in my wrapper and share the code here. Thank you so much for the help!!

[mitschabaude]

solved by #1523