|
barretenberg
|
A standard library fixed-width unsigned integer type. Useful, e.g., for hashing. Use safe_uint instead if looking to represent integer arithmetic inside of Fr. More...
#include <uint.hpp>
Public Member Functions | |
| uint (const witness_t< Builder > &other) | |
| uint (const field_t< Builder > &other) | |
| uint (const uint256_t &value=0) | |
| uint (Builder *builder, const uint256_t &value=0) | |
| uint (const byte_array< Builder > &other) | |
| uint (Builder *parent_context, const std::vector< bool_t< Builder > > &wires) | |
| uint (Builder *parent_context, const std::array< bool_t< Builder >, width > &wires) | |
| uint (const Native v) | |
| std::vector< uint32_t > | constrain_accumulators (Builder *ctx, const uint32_t witness_index, const size_t num_bits, std::string const &msg) const |
| Constrain accumulators. | |
| uint (const uint &other) | |
| uint (uint &&other) | |
| uint & | operator= (const uint &other) |
| uint & | operator= (uint &&other) |
| operator byte_array< Builder > () const | |
| operator field_t< Builder > () const | |
| uint | operator+ (const uint &other) const |
Return a uint which, if range constrained, would be proven to be the sum of self and other. | |
| uint | operator- (const uint &other) const |
Return a uint which, if range constrained, would be proven to be the difference of self and other. | |
| uint | operator* (const uint &other) const |
| Multiply two uint_ct's, trucating overflowing bits. | |
| uint | operator/ (const uint &other) const |
| uint | operator% (const uint &other) const |
| uint | operator& (const uint &other) const |
| uint | operator^ (const uint &other) const |
| uint | operator| (const uint &other) const |
| uint | operator~ () const |
| uint | operator>> (const size_t shift) const |
| Right shift a uint. | |
| uint | operator<< (const size_t shift) const |
| uint | ror (const size_t target_rotation) const |
| uint | rol (const size_t target_rotation) const |
| uint | ror (const uint256_t target_rotation) const |
| uint | rol (const uint256_t target_rotation) const |
| bool_t< Builder > | operator> (const uint &other) const |
| Determine whether this > other. | |
| bool_t< Builder > | operator< (const uint &other) const |
| bool_t< Builder > | operator>= (const uint &other) const |
| bool_t< Builder > | operator<= (const uint &other) const |
| bool_t< Builder > | operator== (const uint &other) const |
| bool_t< Builder > | operator!= (const uint &other) const |
| bool_t< Builder > | operator! () const |
| uint | operator+= (const uint &other) |
| uint | operator-= (const uint &other) |
| uint | operator*= (const uint &other) |
| uint | operator/= (const uint &other) |
| uint | operator%= (const uint &other) |
| uint | operator&= (const uint &other) |
| uint | operator^= (const uint &other) |
| uint | operator|= (const uint &other) |
| uint | operator>>= (const size_t shift) |
| uint | operator<<= (const size_t shift) |
| uint256_t | get_mask () const |
| uint | normalize () const |
| For non-constants, weakly normalize and constrain the updated witness to width-many bits. | |
| uint256_t | get_value () const |
| bool | is_constant () const |
| Builder * | get_context () const |
| bool_t< Builder > | at (const size_t bit_index) const |
| Extract the bit value at a given position. | |
| size_t | get_width () const |
| uint32_t | get_witness_index () const |
| uint256_t | get_additive_constant () const |
Static Public Member Functions | |
| static constexpr size_t | num_accumulators () |
Static Public Attributes | |
| static constexpr size_t | width = sizeof(Native) * 8 |
Protected Types | |
| enum | WitnessStatus { OK , NOT_NORMALIZED , WEAK_NORMALIZED } |
Protected Attributes | |
| Builder * | context |
| uint256_t | additive_constant |
| WitnessStatus | witness_status |
| std::vector< uint32_t > | accumulators |
| uint32_t | witness_index |
Static Protected Attributes | |
| static constexpr uint256_t | CIRCUIT_UINT_MAX_PLUS_ONE = (uint256_t(1) << width) |
| static constexpr uint256_t | MASK = CIRCUIT_UINT_MAX_PLUS_ONE - 1 |
A standard library fixed-width unsigned integer type. Useful, e.g., for hashing. Use safe_uint instead if looking to represent integer arithmetic inside of Fr.
| Builder | The type of the builder context. |
| Native | One of the native uint types uintN_t, where N = 8, 16, 32, 64. |
All arithmetic operations in Native is done modulo 2**N, and the same is true for uint<Builder, Native>.
| bool_t< Builder > proof_system::plonk::stdlib::uint< Builder, Native >::at | ( | const size_t | bit_index | ) | const |
Extract the bit value at a given position.
Since we represent our uint's using quads, to extract a bit we must distinguish between the case where that bit is the low bit of a quad or a high bit of a quad.
Calculating the position of the bit:
Therefore we need to access accumulators[pivot] and accumulators[pivot-1], where pivot = (width//2) - 1 + (bit_index//2)
Write Δ = accumulators[pivot] - 4 . accumulators[pivot - 1]. We would like to construct the bit representation of Δ by imposing the constraint that Δ = lo_bit + 2 . hi_bit and then return either lo_bit or hi_bit, depending on the parity of bit_index. The big addition gate with bit extraction imposes the equivalent relation obtained by scaling both sides by 3.
constraint: 3 lo_bit + 0 * 0 - 3 a_pivot + 12 a_{pivot - 1} + 0 + 6 high bit of (A_pivot - 4 A_{pivot - 1}) == 0 i.e., lo_bit + 2 high bit of (A_pivot - 4 A_{pivot - 1}) = A_pivot - 4 A_{pivot - 1} == 0
constraint: 0 * 0 - 6 hi_bit + 0 A_pivot + 0 * A_{pivot - 1} + 0 + 6 high bit of (A_pivot - 4 A_{pivot - 1}) == 0 Note: we have normalized self, so A_pivot - 4 A_{pivot - 1} is known to be in {0, 1, 2, 3}. Our protocol's bit extraction gate is trusted to correctly extract 6 * (high bit c - 4d).
| uint< Builder, Native > proof_system::plonk::stdlib::uint< Builder, Native >::operator* | ( | const uint< Builder, Native > & | other | ) | const |
Multiply two uint_ct's, trucating overflowing bits.
Notation: a = this, const_a = this.additive_constant; b = other, const_b = other.additive_constant. We are computing (a + const_a) * (b + const_b) modulo 2**width. We could record that we have computed the long division of ab + b*const_a + a*const_b + const_a*const_b, by 2**width and return the remainder. However, as in operator+, we trust ourselves to correctly reduce products of constants, so we instead record that we have computed the long division of ab + b*const_a + a*const_b + (const_a*const_b % 2**width).
constraint: ab + a const_b + b const_a - r - (2**width) overflow + (const_a const_b % 2**width) == 0
| uint< Builder, Native > proof_system::plonk::stdlib::uint< Builder, Native >::operator+ | ( | const uint< Builder, Native > & | other | ) | const |
Return a uint which, if range constrained, would be proven to be the sum of self and other.
Shorthand: write a for the uint self, and b for the uint other.
The function gives part of a circuit allowing a prover to demonstrate knowledge of the remainder under division of the integer (a_val + const_a) + (b_val + const_b) = a_val + b_val + (const_a + const_b) by 2^width. The desired remainder is unchanged under subtraction of multiple of 2^width from the constant part const_a + const_b. Therefore, for efficiency (to minimize the number of possible quotient values), we may (and do) replace the sum const_a + const_b by c = (const_a + const_b) % 2**width.
The function operator+ imposes the constraints a_val + b_val - 2^width * ov - rem + c == 0 and ov in {0, 1, 2}, and returns rem.
Note that, if ov were not constrained, there is the possibility of returning a malicious value of rem. The point is that, if the constraints hold, then the constraint a_val + b_val - 2^width * (ov + x) - (rem - x*2^width) + c == 0 holds for any field element x. Suppose that rem is constrained to width-many bits for the widths we allow. Then, if ov is in {0, 1, 2}, and also ov + x is in {0, 1, 2}, then rem - x*2^width will not be constrained to width-many bits unless x = 0. Now suppose, instead, that ov is unconstrianed. If y is width-bit integer less than the field modulus, then setting x = (rem - y)/2^width gives an equation proving that y is sum mod 2^width.
Constraints: witness + other_witness - remainder - 2^width . overflow + constants == 0 and overflow lies in {0, 1, 2} The sum L = witness + other_witness + constants is at most 3.(2^width-1). In the maximal case, we have L = (2^w - 3) + 2*2^width, showing that a minimal range of values for the overflow is {0, 1, 2}.
| uint< Builder, Native > proof_system::plonk::stdlib::uint< Builder, Native >::operator- | ( | const uint< Builder, Native > & | other | ) | const |
Return a uint which, if range constrained, would be proven to be the difference of self and other.
Shorthand: write a for the uint self, and b for the uint other.
The function gives part of a circuit allowing a prover to demonstrate knowledge of the remainder under division of the integer (a_val + const_a) - (b_val + const_b) = a_val + b_val + (const_a - const_b) by 2^width. We apply two transformations to this problem.
1) The desired remainder is unchanged under subtraction of multiples of 2^width from the constant part const_a - const_b. Therefore, for efficiency (to minimize the number of possible quotient values), we replace const_a - const_b by c = (const_a - const_b) % 2**width.
2) Set d' = a_val - b_val + c. Then the integer d' lies in the range [-2^{width} + 1, 2*2^{width} - 2], so the integer d = d' + 2^width lies in [1, 3*2^width -2]. Therefore, there there is a unique equation of the form d = 2^width * ov + rem, (ov in [0, 1, 2], rem in [0, 2^width - 1]). Then a_val - b_val + (c + 2^width) = d = 2^width * ov + rem.
The function operator- imposes the constraints a_val - b_val - 2^width * ov - rem + (c + 2^width) == 0 and ov in {0, 1, 2}, and returns rem. These constraints do not show that rem is actually the desired remainder, but if the prover also normalizes rem (i.e., constrains it to width-many bits), then rem is shown to be the desired remainder.
| uint< Builder, Native > proof_system::plonk::stdlib::uint< Builder, Native >::operator<< | ( | const size_t | shift | ) | const |
Shift by an even number of bits s = 2x, keeping the lowest width-many bits. Assume width is even and let w = width / 2. Let s = shift. Then we can express A << s in terms of the accumulator decomposition of A by writing w-1 x-1 === === \ j \ k A << s = A.4**x = / a 4 + 4**w / a 4 === j-x === w-x+k j = x k = 0
= (value * 2**shift) % 2**32 + 2**width . A_{x-1}
Now s = 2x + 1. As above, we compute 2**s and subtract part outside of the lowest width-many bits. Again let w = width / 2 and s = shift. Illustration: A = [ w-1+x wi-2+x ... wi+2 wi+1 | wi | wi-1 ... 2x+2 2x+1 ... 0 ] \ / \ / \ / \ / a_{w-1} a_{w-x} a_{w-1-x} a_0
Then bits width+1 through width-1+x of the shift A*2**s are given by
\ j 2**{width+1}.A_{x-1} = 2*4**{w}A_{x-1} = 2 / a 4 === j-x . j = w Only the bit at position equal width is unaccounted-for. This bit is the high bit of a_{w-1-x} = A_x - 4.A_{x-1}, which can be accessed through our addition gate with bit extraction. Altogether, we would like to impose that s width+1 width out = 2 . A - 2 . A - 2 (high bit of A - 4A ) x-1 ( x x-1 )
Since our gate with bit extraction adds the term 6 * (high bit of w_0 - 4.w_4), we scale the entire equation by -6/2**width.
constraint: -(-6/2**width) output + (-6/2**width) . 2**s . A + 0 A_x - (-12/2**width) 2**width A_{x-1}
| bool_t< Builder > proof_system::plonk::stdlib::uint< Builder, Native >::operator> | ( | const uint< Builder, Native > & | other | ) | const |
Determine whether this > other.
This allows a prover to demonstrate that they have correctly classified a, b as satisfying either a > b or a <= b.
The field_t operator on uints normalizes its input, so a and be have been constrained to the width of Native. That is, both a and b lie in the closed interval [0, 2*{width} - 1]. Now, (a > b) <==> (a - b - 1) is in the range [0, 2**{width} - 2] and !(a > b) <==> (b - a) is in the range [0, 2**{width} - 1]. Consider comparison_check = (a - b - 1)result + (b - a)(1 - result). If comparison_check is in the range [0, 2**{width} - 1] and result is boolean, then we are left with three possibilities: (1) a - b - 1 = 2**{width} - 1 (2) a > b (3) !(a > b) The bool_t operator on witnesses applies the relevant constraint to result, so we are left to eliminate possibility (1). The difference a - b is calculated relative to the circuit modulus r. The number D of distinct Fr elements that can be written this way is at most M = 2*(2**{width}-1) + 1 = 2**{width+1} - 1, and in fact, D = M if r > M. Since our r has 252 bits, it suffices to ensure that 2**252 >= M. Altogether, as long as 252 > width, 2**width cannot be written as the additive inverse of a of that width.
| uint< Builder, Native > proof_system::plonk::stdlib::uint< Builder, Native >::operator>> | ( | const size_t | shift | ) | const |
Right shift a uint.
Note that the result is only weakly normalized.
We represent uints using a set of accumulating base-4 sums, which adds complexity to bit shifting.
Right shifts by even values are trivial because of how our accumulators are defined. Shifts by odd values are harder as we only have quads to work with.
To recap accumulators. Our uint A can be described via a sum of its quads (a_0, ..., a_{width - 1}) (we use w as shorthand for 'width / 2' and assume the width is even.)
w - 1 === \ i
A = / a . 4 === i i = 0
Our range constraint will represent A via its accumulating sums (A_0, ..., A_{w-1}), where
i
===
\ j
A = / a . 4 i === (w - 1 - i + j) j = 0
Write x = 2y + z with z in {0,1}. Let
w - 1 - y
===
\ j
R = A/4**y = / a . 4 === (y + j) j = 0
We can see that if x is even, (A>>x) = A . w - 1 - (x/2)
If x is odd, then first over-shift to calculate A>>(x+1), then correct by doubling and adding the needed low bit. The first shift discards, in order, the quads a_0, ..., a_{(x+1)/2 - 1}, so the needed low bit is the high bit of a_y. Defining A_{-1} = 0, we have a_{w-1-i} = A_{i} - 4.A_{i-1}, i >= 0. Therefore,
(A>>x) = b + 2 . A x w - 1 - ((x+1)/2).
where b is the most significant bit of A - 4. A x w - ((x+1)/2) w - 1 - ((x+1)/2)
We have a special selector configuration in our arithmetic widget that extracts 6.b_x from given the two relevant accumulators. The factor of 6 is for efficiency reasons. We need to scale our other gate coefficients by 6 to accommodate this.
| uint< Builder, Native > proof_system::plonk::stdlib::uint< Builder, Native >::ror | ( | const size_t | target_rotation | ) | const |
Rotate A = \sum_{i=0}^{width-1} a_i.4^i rightward by an even number r = 2x of bits, yielding output A'. Assume width is even and let w = width / 2. Since r is even, rotating A is equivalent to rotate half as many of the quads a_i. Illustration in terms of quads: A = [a_{w-1} ... a_{x} a_{x-1} ... a_{0}] ~~> A' = [a_{x-1} ... a_{0} a_{w-1} ... a_{x}] We get the higest x quads of A' from the lowest x quads of 4**{w-x} A, and use an appropriate accumulator to add in the lowest w-x quads to A' and to remove the highest w-x quads from 4**{w-x} A. Since the accumulator A_i encodes the highest i+1 bits of A, we arrive at the formula A' = 4**{w-x} A + (1 - 4**w) A_{w-x}
Now rotate A by an even number r = 2(x-1)+1 of bits, yielding output A'. Let a_j = a_{j,0} + 2a_{j, 1} be the bit decomposition of a_j, j = 0, ... , w-1. Illustration in terms of bits: A = [ a_{w-1,1} ... a_{x,0} a_{x-1,1} | a_{x-2,0} ... a_{0,1} | a_{0, 0} ] ~~> A' = [ a_{x-1,0} ... a_{0,1} a_{0, 0} | a_{w-1,1} ... a_{x.0} | a_{x-1,1} ] [-----—from 2 * 4^{w-x} A----—|--—from A_{w-x-1}--—|–extracted-] As in the even case, the high bits of A' come from a shift of A, while an accumulator contributes the lower bits while removing bits of the shift of A beyond width. This handles all but two bits: the 0th bit of A', and one dangling bit coming from the shift of A. These are handled using the bit extraction gate. Recall that the accumulators A_i satisfy a_{w-1-i} = A_{i} - 4.A_{i-1}, i >= 0, when we set A_{-1} = 0. We see that to extract a_{x-1, 1}, we should set i = w - x.
constraint: w-x w / \ 6 6 . 2 . 4 12 - 6 . 2 . 4 | 6 * the highest bit of |
1.9.6