Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add builtin function to return the size of a field #182

Open
katat opened this issue Sep 10, 2024 · 1 comment
Open

Add builtin function to return the size of a field #182

katat opened this issue Sep 10, 2024 · 1 comment
Assignees

Comments

@katat
Copy link
Collaborator

katat commented Sep 10, 2024

We should avoid the need for the users to put in the size of a value (a field), since size of a value should be determined by the used backend and should be returned by a builtin function.

The field size should be constant, so this size can be treated as a generic value for circuit compilation.

The problem: require manual input for field size

Without a builtin function to determine this constant value for the field size, the user needs to do it like the following:

fn less_than(const LEN: Field, lhs: Field, rhs: Field) -> Field {
    // todo: find a better way to encapsulate the relationship among the LEN, lhs and rhs.
    // I think in general, the LEN should be the length of the bit array representing the lhs and rhs.
    // Asking the caller to provide the LEN can be error-prone, running into the similar issues that circom facing.
    let bit_len = LEN + 1;

    // 1 << LEN
    let mut pow2 = 1;
    for ii in 0..LEN {
        pow2 = pow2 + pow2;
    }

    let sum = pow2 + lhs - rhs;
    let sum_bit = bits::to_bits(bit_len, sum);

    return 1 - sum_bit[bit_len];
}

Builtin function field_len

With a builtin function to get the field size:

fn less_than(lhs: Field, rhs: Field) -> Field {
    // bit length for the sum value, which is `lhs + rhs`,
    // thus, its length should be the max of the bit lengths of fields `lhs` and `rhs` plus 1, considering the potential carry from the sum. 
    // assuming the builtin function to determine the bit length of a field is `field_len(field_type)`:
    let bit_len = max(field_size(Field), field_size(Field)) + 1;
    ...
    let sum_bit = bits::to_bits(bit_len, sum);
    ...
}

Take it further: support numeric types with varying sizes

However, the default Field is large in bit length, around 250 bits. Often it is not necessary to use such big number of bit length, thus it can waste constraints introduced by the range checks from functions like bits::to_bits(bit_len, val). Therefore, this can be related to the discussion on whether we should support numeric types such as u32, u64 etc.

Checking at two levels:

  • TAST phase: For constant values, it type checks the constant value corresponding to the types in TAST phase.
  • Synthesizer phase: For cell vars, it should automatically add constraints for range checks.
@katat
Copy link
Collaborator Author

katat commented Sep 10, 2024

related idea: #165

@katat katat self-assigned this Sep 15, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant