|
barretenberg
|
Classes | |
| struct | Basis |
| struct | Limb |
Public Types | |
| typedef T | TParams |
| typedef barretenberg::field< T > | native |
Public Member Functions | |
| bigfield (const field_t< Builder > &low_bits, const field_t< Builder > &high_bits, const bool can_overflow=false, const size_t maximum_bitlength=0) | |
| bigfield (Builder *parent_context=nullptr) | |
| bigfield (Builder *parent_context, const uint256_t &value) | |
| bigfield (const field_t< Builder > &a, const field_t< Builder > &b, const field_t< Builder > &c, const field_t< Builder > &d, const bool can_overflow=false) | |
| bigfield (const field_t< Builder > &a, const field_t< Builder > &b, const field_t< Builder > &c, const field_t< Builder > &d, const field_t< Builder > &prime_limb, const bool can_overflow=false) | |
| bigfield (const byte_array< Builder > &bytes) | |
| bigfield (const bigfield &other) | |
| bigfield (bigfield &&other) | |
| bigfield & | operator= (const bigfield &other) |
| bigfield & | operator= (bigfield &&other) |
| byte_array< Builder > | to_byte_array () const |
| uint512_t | get_value () const |
| uint512_t | get_maximum_value () const |
| bigfield | add_to_lower_limb (const field_t< Builder > &other, uint256_t other_maximum_value) const |
| Add a field element to the lower limb. CAUTION (the element has to be constrained before using this function) | |
| bigfield | operator+ (const bigfield &other) const |
| bigfield | operator- (const bigfield &other) const |
| bigfield | operator* (const bigfield &other) const |
| bigfield | bad_mul (const bigfield &other) const |
| bigfield | operator/ (const bigfield &other) const |
| bigfield | operator- () const |
| bigfield | operator+= (const bigfield &other) |
| bigfield | operator-= (const bigfield &other) |
| bigfield | operator*= (const bigfield &other) |
| bigfield | operator/= (const bigfield &other) |
| bigfield | sqr () const |
| bigfield | sqradd (const std::vector< bigfield > &to_add) const |
| bigfield | madd (const bigfield &to_mul, const std::vector< bigfield > &to_add) const |
| bigfield | conditional_negate (const bool_t< Builder > &predicate) const |
| bigfield | conditional_select (const bigfield &other, const bool_t< Builder > &predicate) const |
| Create an element which is equal to either this or other based on the predicate. | |
| void | assert_is_in_field () const |
| void | assert_less_than (const uint256_t upper_limit) const |
| void | assert_equal (const bigfield &other) const |
| void | assert_is_not_equal (const bigfield &other) const |
| void | self_reduce () const |
| bool | is_constant () const |
| void | convert_constant_to_fixed_witness (Builder *builder) |
| void | fix_witness () |
| Builder * | get_context () const |
Static Public Member Functions | |
| static bigfield | create_from_u512_as_witness (Builder *ctx, const uint512_t &value, const bool can_overflow=false, const size_t maximum_bitlength=0) |
| Creates a bigfield element from a uint512_t. Bigfield element is constructed as a witness and not a circuit constant. | |
| static bigfield | from_witness (Builder *ctx, const barretenberg::field< T > &input) |
| static void | perform_reductions_for_mult_madd (std::vector< bigfield > &mul_left, std::vector< bigfield > &mul_right, const std::vector< bigfield > &to_add) |
| Performs individual reductions on the supplied elements as well as more complex reductions to prevent CRT modulus overflow and to fit the quotient inside the range proof. | |
| static bigfield | mult_madd (const std::vector< bigfield > &mul_left, const std::vector< bigfield > &mul_right, const std::vector< bigfield > &to_add, bool fix_remainder_to_zero=false) |
| static bigfield | dual_madd (const bigfield &left_a, const bigfield &right_a, const bigfield &left_b, const bigfield &right_b, const std::vector< bigfield > &to_add) |
| static bigfield | msub_div (const std::vector< bigfield > &mul_left, const std::vector< bigfield > &mul_right, const bigfield &divisor, const std::vector< bigfield > &to_sub, bool enable_divisor_nz_check=false) |
| static bigfield | sum (const std::vector< bigfield > &terms) |
| Create constraints for summing these terms. | |
| static bigfield | internal_div (const std::vector< bigfield > &numerators, const bigfield &denominator, bool check_for_zero) |
| static bigfield | div_without_denominator_check (const std::vector< bigfield > &numerators, const bigfield &denominator) |
| static bigfield | div_check_denominator_nonzero (const std::vector< bigfield > &numerators, const bigfield &denominator) |
| static bigfield | one () |
| static bigfield | zero () |
| static constexpr bigfield | unreduced_zero () |
| Create an unreduced 0 ~ p*k, where p*k is the minimal multiple of modulus that should be reduced. | |
| static constexpr uint512_t | get_maximum_unreduced_value (const size_t num_products=1) |
| static constexpr uint1024_t | get_maximum_crt_product () |
| static size_t | get_quotient_max_bits (const std::vector< uint1024_t > &remainders_max) |
| Compute the maximum number of bits for quotient range proof to protect against CRT underflow. | |
| static bool | mul_product_overflows_crt_modulus (const uint1024_t &a_max, const uint1024_t &b_max, const std::vector< bigfield > &to_add) |
| static bool | mul_product_overflows_crt_modulus (const std::vector< uint512_t > &as_max, const std::vector< uint512_t > &bs_max, const std::vector< bigfield > &to_add) |
| static constexpr uint256_t | get_maximum_unreduced_limb_value () |
Public Attributes | |
| Builder * | context |
| Limb | binary_basis_limbs [4] |
| field_t< Builder > | prime_basis_limb |
Static Public Attributes | |
| static constexpr uint256_t | modulus = (uint256_t(T::modulus_0, T::modulus_1, T::modulus_2, T::modulus_3)) |
| static constexpr uint512_t | modulus_u512 = uint512_t(modulus) |
| static constexpr uint64_t | NUM_LIMB_BITS = NUM_LIMB_BITS_IN_FIELD_SIMULATION |
| static constexpr uint64_t | NUM_LAST_LIMB_BITS = modulus_u512.get_msb() + 1 - (NUM_LIMB_BITS * 3) |
| static constexpr uint1024_t | DEFAULT_MAXIMUM_REMAINDER |
| static constexpr uint256_t | DEFAULT_MAXIMUM_LIMB = (uint256_t(1) << NUM_LIMB_BITS) - uint256_t(1) |
| static constexpr uint256_t | DEFAULT_MAXIMUM_MOST_SIGNIFICANT_LIMB |
| static constexpr uint64_t | LOG2_BINARY_MODULUS = NUM_LIMB_BITS * 4 |
| static constexpr bool | is_composite = true |
| static constexpr uint256_t | prime_basis_maximum_limb |
| static constexpr Basis | prime_basis { uint512_t(barretenberg::fr::modulus), barretenberg::fr::modulus.get_msb() + 1 } |
| static constexpr Basis | binary_basis { uint512_t(1) << LOG2_BINARY_MODULUS, LOG2_BINARY_MODULUS } |
| static constexpr Basis | target_basis { modulus_u512, modulus_u512.get_msb() + 1 } |
| static constexpr barretenberg::fr | shift_1 = barretenberg::fr(uint256_t(1) << NUM_LIMB_BITS) |
| static constexpr barretenberg::fr | shift_2 = barretenberg::fr(uint256_t(1) << (NUM_LIMB_BITS * 2)) |
| static constexpr barretenberg::fr | shift_3 = barretenberg::fr(uint256_t(1) << (NUM_LIMB_BITS * 3)) |
| static constexpr barretenberg::fr | shift_right_1 = barretenberg::fr(1) / shift_1 |
| static constexpr barretenberg::fr | shift_right_2 = barretenberg::fr(1) / shift_2 |
| static constexpr barretenberg::fr | negative_prime_modulus_mod_binary_basis |
| static constexpr uint512_t | negative_prime_modulus = binary_basis.modulus - target_basis.modulus |
| static constexpr uint256_t | neg_modulus_limbs_u256 [4] |
| static constexpr barretenberg::fr | neg_modulus_limbs [4] |
| static constexpr uint64_t | MAX_ADDITION_LOG = 10 |
| static constexpr uint64_t | MAX_UNREDUCED_LIMB_SIZE |
| bigfield< Builder, T > proof_system::plonk::stdlib::bigfield< Builder, T >::add_to_lower_limb | ( | const field_t< Builder > & | other, |
| uint256_t | other_maximum_value | ||
| ) | const |
Add a field element to the lower limb. CAUTION (the element has to be constrained before using this function)
Sometimes we need to add a small constrained value to a bigfield element (for example, a boolean value), but we don't want to construct a full bigfield element for that as it would take too many gates. If the maximum value of the field element being added is small enough, we can simply add it to the lowest limb and increase its maximum value. That will create 2 additional constraints instead of 5/3 needed to add 2 bigfield elements and several needed to construct a bigfield element.
| Builder | Builder |
| T | Field Parameters |
| other | Field element that will be added to the lower |
| other_maximum_value | The maximum value of other |
| bigfield proof_system::plonk::stdlib::bigfield< Builder, T >::bad_mul | ( | const bigfield< Builder, T > & | other | ) | const |
FOR TESTING PURPOSES ONLY DO NOT USE THIS IN PRODUCTION CODE FOR THE LOVE OF GOD!
| bigfield< Builder, T > proof_system::plonk::stdlib::bigfield< Builder, T >::conditional_select | ( | const bigfield< Builder, T > & | other, |
| const bool_t< Builder > & | predicate | ||
| ) | const |
Create an element which is equal to either this or other based on the predicate.
| Builder | |
| T |
| other | The other bigfield element |
| predicate | Predicate controlling the result (0 for this, 1 for the other) |
|
inline |
Create a witness form a constant. This way the value of the witness is fixed and public.
|
static |
Creates a bigfield element from a uint512_t. Bigfield element is constructed as a witness and not a circuit constant.
| ctx | |
| value | |
| can_overflow | Can the input value have more than log2(modulus) bits? |
| maximum_bitlength | Provide the explicit maximum bitlength if known. Otherwise bigfield max value will be either log2(modulus) bits iff can_overflow = false, or (4 * NUM_LIMB_BITS) iff can_overflow = true |
This method is 1 gate more efficient than constructing from 2 field_ct elements.
|
static |
Div method with constraints for denominator!=0.
Similar to operator/ but numerator can be linear sum of multiple elements
TODO: After we create a mechanism for easy updating of witnesses, create a test with proof check
|
static |
Div method without constraining denominator!=0.
Similar to operator/ but numerator can be linear sum of multiple elements
|
static |
Compute (left_a * right_a) + (left_b * right_b) + ...to_add = c mod p
This is cheaper than two multiplication operations, as the above only requires one quotient/remainder
|
inline |
Fix a witness. The value of the witness is constrained with a selector
|
inlinestatic |
Compute the maximum number of bits for quotient range proof to protect against CRT underflow.
| remainders_max | Maximum sizes of resulting remainders |
|
static |
Division of a sum with an optional check if divisor is zero. Should not be used outside of class.
| numerators | Vector of numerators |
| denominator | Denominator |
| check_for_zero | If the zero check should be enabled |
| bigfield< Builder, T > proof_system::plonk::stdlib::bigfield< Builder, T >::madd | ( | const bigfield< Builder, T > & | to_mul, |
| const std::vector< bigfield< Builder, T > > & | to_add | ||
| ) | const |
Compute a * b + ...to_add = c mod p
| to_mul | Bigfield element to multiply by |
| to_add | Vector of elements to add |
|
static |
multiply, subtract, divide. This method computes:
result = -(\sum{mul_left[i] * mul_right[i]} + ...to_add) / divisor
Algorithm is constructed in this way to ensure that all computed terms are positive
i.e. we evaluate: result * divisor + (\sum{mul_left[i] * mul_right[i]) + ...to_add) = 0
It is critical that ALL the terms on the LHS are positive to eliminate the possiblity of underflows when calling evaluate_multiple_multiply_add
only requires one quotient and remainder + overflow limbs
We proxy this to mult_madd, so it only requires one quotient and remainder + overflow limbs
|
inlinestatic |
Check that the maximum value of a sum of bigfield productc with added values overflows ctf modulus.
| as_max | Vector of multiplicands' maximum values |
| b_max | Vector of multipliers' maximum values |
| to_add | Vector of field elements to be added |
|
inlinestatic |
Check that the maximum value of a bigfield product with added values overflows ctf modulus.
| a_max | multiplicand maximum value |
| b_max | multiplier maximum value |
| to_add | vector of field elements to be added |
|
static |
Evaluate the sum of products and additional values safely.
| mul_left | Vector of bigfield multiplicands |
| mul_right | Vector of bigfield multipliers |
| to_add | Vector of bigfield elements to add to the sum of products |
|
inlinestatic |
Create a public one constant
| bigfield< Builder, T > proof_system::plonk::stdlib::bigfield< Builder, T >::operator* | ( | const bigfield< Builder, T > & | other | ) | const |
Evaluate a non-native field multiplication: (a * b = c mod p) where p == target_basis.modulus
We compute quotient term q and remainder c and evaluate that:
a * b - q * p - c = 0 mod modulus_u512 (binary basis modulus, currently 2**272) a * b - q * p - c = 0 mod circuit modulus
| bigfield< Builder, T > proof_system::plonk::stdlib::bigfield< Builder, T >::operator- | ( | const bigfield< Builder, T > & | other | ) | const |
Subtraction operator.
Like operator+, we use lazy reduction techniques to save on field reductions.
Instead of computing *this - other, we compute offset X and compute: *this + X - other This ensures we do not underflow!
Offset X will be a multiple of our bigfield modulus p
i.e X = m * p
It is NOT enough to ensure that the integer value of *this + X - other does not underflow. We must ALSO ensure that each LIMB of the result does not underflow
We must compute the MINIMUM value of m that ensures that none of the bigfield limbs will underflow!
i.e. We must compute the MINIMUM value of m such that, for each limb i, the following result is positive:
*this.limb[i] + X.limb[i] - other.limb[i]
Plookup bigfield subtractoin
We have a special addition gate we can toggle, that will compute: (w_1 + w_4 - w_4_omega + q_arith = 0) This is in addition to the regular addition gate
We can arrange our wires in memory like this:
| 1 | 2 | 3 | 4 | |--—|--—|--—|--—| | b.p | a.0 | b.0 | c.p | (b.p + c.p - a.p = 0) AND (a.0 - b.0 - c.0 = 0) | a.p | a.1 | b.1 | c.0 | (a.1 - b.1 - c.1 = 0) | a.2 | b.2 | c.2 | c.1 | (a.2 - b.2 - c.2 = 0) | a.3 | b.3 | c.3 | — | (a.3 - b.3 - c.3 = 0)
Step 1: For each limb compute the MAXIMUM value we will have to borrow from the next significant limb
i.e. if we assume that *this = 0 and other = other.maximum_value, how many bits do we need to borrow from the next significant limb to ensure each limb value is positive?
N.B. for this segment maximum_value really refers to maximum NEGATIVE value of the result
Step 2: Compute the constant value X = m * p we must add to the result to ensure EVERY limb is >= 0
We need to find a value X where X.limb[3] > limb_3_maximum_value. As long as the above holds, we can borrow bits from X.limb[3] to ensure less significant limbs are positive
Start by setting constant_to_add = p
Step 3: Compute offset terms t0, t1, t2, t3 that we add to our result to ensure each limb is positive
t3 represents the value we are BORROWING from constant_to_add.limb[3] t2, t1, t0 are the terms we will ADD to constant_to_add.limb[2], constant_to_add.limb[1], constant_to_add.limb[0]
i.e. The net value we add to constant_to_add is 0. We must ensure that: t3 = t0 + (t1 << NUM_LIMB_BITS) + (t2 << NUM_LIMB_BITS * 2)
e.g. the value we borrow to produce t0 is subtracted from t1, the value we borrow from t1 is subtracted from t2 the value we borrow from t2 is equal to t3
Compute the limbs of constant_to_add, including our offset terms t0, t1, t2, t3 that ensure each result limb is positive
Update the maximum possible value of the result. We assume here that (*this.value) = 0
Compute the binary basis limbs of our result
Compute the prime basis limb of the result
| bigfield< Builder, T > proof_system::plonk::stdlib::bigfield< Builder, T >::operator/ | ( | const bigfield< Builder, T > & | other | ) | const |
Division operator. Doesn't create constraints for b!=0, which can lead to vulnerabilities. If you need a safer variant use div_check_denominator_nonzero.
To evaluate (a / b = c mod p), we instead evaluate (c * b = a mod p).
|
static |
Performs individual reductions on the supplied elements as well as more complex reductions to prevent CRT modulus overflow and to fit the quotient inside the range proof.
| Builder | builder |
| T | basefield |
| mul_left | |
| mul_right | |
| to_add |
| bigfield< Builder, T > proof_system::plonk::stdlib::bigfield< Builder, T >::sqr |
Compute a * a = c mod p
Slightly cheaper than operator* for StandardPlonk
| bigfield< Builder, T > proof_system::plonk::stdlib::bigfield< Builder, T >::sqradd | ( | const std::vector< bigfield< Builder, T > > & | to_add | ) | const |
Compute a * a + ...to_add = b mod p
We can chain multiple additions to a square/multiply with a single quotient/remainder.
Chaining the additions here is cheaper than calling operator+ because we can combine some gates in evaluate_multiply_add
|
static |
Create constraints for summing these terms.
| Builder | |
| T |
| terms |
|
inlinestaticconstexpr |
Create an unreduced 0 ~ p*k, where p*k is the minimal multiple of modulus that should be reduced.
We need it for division. If we always add this element during division, then we never run into the formula-breaking situation
|
inlinestatic |
Create a public zero constant
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
1.9.6