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

Can I use div_mod on an arbitrary field element? #93

Open
mmagician opened this issue Jul 11, 2023 · 2 comments
Open

Can I use div_mod on an arbitrary field element? #93

mmagician opened this issue Jul 11, 2023 · 2 comments

Comments

@mmagician
Copy link
Contributor

mmagician commented Jul 11, 2023

In your tests the element that I'm dividing is known to have a fixed number of bits.

However, I would like to apply this function to an arbitrary field element - the problem is that the number of bits can be up to F::NUM_BITS, so I end up with something like:

let small_mod: usize = 1 << 16;
let (_, r) = range_gate.div_mod(ctx, arbitrary_field_element, small_mod, F::NUM_BITS as usize);

which doesn't actually work (aside from not being efficient, if it did) as I get an index out of bounds error. By increasing the param a_num_bits to F::NUM_BITS + 2 circumvents this error but then it panics with some low level assert failure.

Perhaps the specific errors aren't very relevant, because I suspect that using div_mod for this purpose is simply not the best approach in the first place. If you're wondering why I care about arbitrary elements, it's because these elements comes from a hash output, and at a later stage I want to treat them as indices to an array.

Let me know if you have any better ideas for modular reduction of F to "usize" and constraining that the resulting F is indeed less than the modulus - many thanks!

@jonathanpwang
Copy link
Contributor

This has to do with our implementation of range_check, which does not quite work all the way up to F::NUM_BITS.

Let's say you call div_mod(ctx, a, b, num_bits). It will call check_big_less_than_safe to range check a // b to num_bits - log2(b) + 1 bits. In your case that's F::NUM_BITS - 15 bits.

Now check_big_less_than_safe will make several range checks, all to range_bits = F::NUM_BITS - 15 bits. Our requirement on range_bits is that ceil(range_bits / lookup_bits) * lookup_bits <= F::NUM_BITS - 1 due to some optimizations in range check.

So it seems that if you make lookup_bits >= 16, then the above assumption will fail for range_bits = F::NUM_BITS - 15. However it will probably work if you use a smaller lookup_bits.

In the long term we could consider enhancing range_check so for range_bits very close to F::NUM_BITS, it doesn't have this ceiling requirement. In the short term if you are ok using slightly smaller lookup_bits, that's likely the most immediate solution.

@mmagician
Copy link
Contributor Author

Thanks so much for a quick and detailed reply @jonathanpwang!
I've tried out your suggestion and indeed that seems to solve the panic issue.

I've moved on to the next error now :) 'circuit was not satisfied'. I've prepared a concise code piece that's an extended poseidon example from your scaffold:
https://github.com/HungryCatsStudio/halo2-scaffold/tree/div-mod-panic where this panic is shown on running the example.

Help is greatly appreciated, but also let me know if I can assist in fixing this!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants
@mmagician @jonathanpwang and others