Generalize range check in Prio3Sum

[cjpatton]

In Prio3Sum and Prio3SumVec we do a simple $[0, 2^k)$ range check by encoding the integer as a $k$-bit string and checking each bit is $0$ or $1$. In #287 we devised a simple strategy for generalizing this check to $[0, C)$ for any $C > 0$, even if $C$ is not a power of $2$. What's more, this check is concretely efficient in that it doesn't change the input length or the number of gadget calls. (The affine part of the computation is a bit more complex.)

Could we, and would it be worth it to, do the same for Prio3Sum and Prio3SumVec? It seems to me this would be a valuable improvement.

cc/ @divergentdave, @junyechen1996

[divergentdave]

I don't immediately see how we could do this without increasing the input size of Prio3Sum. In the other case, we relied on the already-present range checks on histogram bits for the ≥0 end of the range.

One unoptimized way we could extend Prio3Sum to do different range checks would be to double the input length, encode the measurement as a bit vector, and then encode the measurement plus some constant as a bit vector. The validity circuit would range check all the bits, and then do a sum check on the two halves of the input, confirming that the latter encoded integer is equal to the former plus the constant. This effectively lets us slide two [0, 2^n) range checks over each other, and build a [0, m) range check from their intersection.

[cjpatton]

:face_palm: You are absolutely right, we'd need to double the input length to apply the same trick.

I think it's worth doing for Prio3Sum since input is fairly small.

For Prio3SumVec, we definitely don't want to blow up the common "bit-vector" use case ($k=1$). If we wanted to change Prio3SumVec this way, then we probably would want to split out the bit-vector circuit into a different variant, e..g, Prio3CountVec or something.

[cjpatton]

We may end up with a breaking change for Prio3Sum as part of #262. If so, we should also consider taking this change as well.