Range proof fails when value is maximum

[mark-moir]

Hi

We've been updating some of our tests to use a later version of the DockNetwork crypto proof_system, specifically this one, which we believe is from this commit.

Our range proof tests include a case in which the signed value is the maximum value in the required range. This test passed with earlier versions and now fails. A simple way to reproduce this is to change this line to:

                .map(|_| Fr::from(max as u64))

so that all of the values are the maximum of the range specified for the test, and then run:

cargo test pok_of_bbs_plus_sig_and_bounded_message 

which yields this failure:

---- pok_of_bbs_plus_sig_and_bounded_message stdout ----
...
Constraint trace requires enabling `ConstraintLayer`
thread 'pok_of_bbs_plus_sig_and_bounded_message' panicked at proof_system/tests/bound_check_legogroth16.rs:561:1:
called `Result::unwrap()` on an `Err` value: LegoGroth16Error(SynthesisError(Unsatisfiable))

Is this an intentional semantic change or a bug?

Thanks.

[lovesh]

Hi Mark,

This was an intentional change to make the bounds uniform across all supported protocols. The upper bound (max) is exclusive, i.e. protocol enforces bound [min, max)

And I just published a newer version of that crate. Please use that.

[mark-moir]

Thanks @lovesh. As far as I can tell, with this arrangement, there is no way to express a minimum value without imposing a maximum (other than the maximum representable value). In contrast, AnonCreds v2 can express this either explicitly or implicitly. For example, based on the tests here, the following additional tests all pass:

// Test that 42 >= 30, with implicit maximum value
range_test_with!(in_range_min_implicit_max, 42, Some(30), None, false);

// Test that 42 >= 30, with explicit maximum value
range_test_with!(in_range_min_explicit_max, 42, Some(30), Some(isize::MAX), false);

// Test that isize::Max >= 30
range_test_with!(in_range_min_explicit_max_max, isize::MAX, Some(30), Some(isize::MAX), false);

I don't think the last one can be expressed using DockNetwork crypto, due the changed interface.

For us, wanting to abstract both libraries, this presents a bit of a challenge. I would welcome your thoughts.

[mark-moir]

Happy New Year @lovesh. Any thoughts on the above comment (edited for freshness and clarity)? Thanks.

[lovesh]

Happy New Year @mark-moir and sorry for the late reply. I think the problem is not about the bounds being explicit or not (as we don't support implicit bounds) but being able to support a value of isize::MAX. So how important is it to support the value isize::MAX? The reason for the change to bounds as [min, max) was because its how Bulletproof treats ranges by default so if you have a protocol for supporting n-bit range the bounds you can support are [0, 2^n) and not [0, 2^n]. An unrelated point - you should avoid isize/usize in non test code (like in RangeStatement) as their width depends on the architecture.

[mark-moir]

Happy New Year @mark-moir and sorry for the late reply.

No problem, thanks for the response.

I think the problem is not about the bounds being explicit or not (as we don't support implicit bounds) but being able to support a value of isize::MAX. So how important is it to support the value isize::MAX?

My point is not so much about isize::MAX specifically, but about the maximum value representable by whatever type range proofs support. This discussion makes clear that perhaps we should refine our abstraction so that it can be implemented by different underlying libraries that support range proofs over different types/ranges. That will give us the opportunity to make it easier to switch between implementations despite their differences in terms of ranges and expressing bounds. We'll look into that.

The reason for the change to bounds as [min, max) was because its how Bulletproof treats ranges by default so if you have a protocol for supporting n-bit range the bounds you can support are [0, 2^n) and not [0, 2^n]. An unrelated point - you should avoid isize/usize in non test code (like in RangeStatement) as their width depends on the architecture.

Thanks. Note that RangeStatement is defined in the anoncreds-v2-rs repo. We have just added some tests and small fixes there. Our abstraction work, with the first implementation being over the AnonCreds 2 library, can be seen in our public fork of that repo, mostly under src/vcp and tests/vcp.