- Generated by
1.9.8
|
Barretenberg
The ZK-SNARK library at the core of Aztec
|
#include <field.hpp>
Public Types | |
| using | Builder = Builder_ |
| using | View = field_t |
| using | CoefficientAccumulator = field_t |
| using | native = bb::fr |
Public Member Functions | |
| field_t (Builder *parent_context=nullptr) | |
| field_t (Builder *parent_context, const bb::fr &value) | |
| field_t (const int value) | |
| field_t (const unsigned long long value) | |
| field_t (const unsigned int value) | |
| field_t (const unsigned long value) | |
| field_t (const bb::fr &value) | |
| field_t (const uint256_t &value) | |
| field_t (const witness_t< Builder > &value) | |
| field_t (const field_t &other) | |
| field_t (field_t &&other) noexcept | |
| field_t (const bool_t< Builder > &other) | |
| ~field_t ()=default | |
| operator bool_t< Builder > () const | |
Convert field_t element to bool_t and enforce bool constraints. | |
| field_t & | operator= (const field_t &other) |
| field_t & | operator= (field_t &&other) noexcept |
| field_t | operator+ (const field_t &other) const |
| Field addition operator. | |
| field_t | operator- (const field_t &other) const |
| Subtraction operator deduced from the addition operator. | |
| field_t | operator* (const field_t &other) const |
| Field multiplication operator. | |
| field_t | operator/ (const field_t &other) const |
| Since in divide_no_zero_check, we check \( a / b = q \) by the constraint \( a = b \cdot q\), if \( a =
b= 0\), we can set \( q \) to any value and it will pass the constraint. Hence, when not having prior knowledge of \( b \) not being zero it is essential to check. | |
| bool_t< Builder > | operator== (const field_t &other) const |
Compute a bool_t equal to (a == b) | |
| bool_t< Builder > | operator!= (const field_t &other) const |
Compute a bool_t equal to (a != b) | |
| field_t | divide_no_zero_check (const field_t &other) const |
Given field elements a = *this and b = other, output a / b without checking whether b = 0. | |
| field_t | sqr () const |
| field_t | pow (const uint32_t &exponent) const |
| Raise this field element to the power of the provided uint32_t exponent. | |
| field_t | pow (const field_t &exponent) const |
| Raise a field_t to a power of an exponent (field_t). Note that the exponent must not exceed 32 bits and is implicitly range constrained. | |
| field_t | operator+= (const field_t &other) |
| field_t | operator-= (const field_t &other) |
| field_t | operator*= (const field_t &other) |
| field_t | operator/= (const field_t &other) |
| field_t & | operator++ () |
| field_t | operator++ (const int) |
| field_t | invert () const |
| field_t | operator- () const |
| void | set_origin_tag (const OriginTag &new_tag) const |
| OriginTag | get_origin_tag () const |
| void | set_free_witness_tag () |
| Set the free witness flag for the field element's tag. | |
| void | unset_free_witness_tag () const |
| Unset the free witness flag for the field element's tag. | |
| void | clear_round_provenance () const |
| field_t | conditional_negate (const bool_t< Builder > &predicate) const |
| If predicate's value == true, negate the value, else keep it unchanged. | |
| void | assert_equal (const field_t &rhs, std::string const &msg="field_t::assert_equal") const |
Copy constraint: constrain that *this field is equal to rhs element. | |
| void | assert_not_equal (const field_t &rhs, std::string const &msg="field_t::assert_not_equal") const |
Constrain *this to be not equal to rhs. | |
| void | assert_is_in_set (const std::vector< field_t > &set, std::string const &msg="field_t::assert_not_in_set") const |
Constrain *this \in set by enforcing that P(X) = \prod_{s \in set} (X - s) is 0 at X = *this. | |
| field_t | madd (const field_t &to_mul, const field_t &to_add) const |
| field_t | add_two (const field_t &add_b, const field_t &add_c) const |
Efficiently compute (this + a + b) using big_mul gate. | |
| field_t | normalize () const |
| Return a new element, where the in-circuit witness contains the actual represented value (multiplicative constant is 1 and additive_constant is 0) | |
| bb::fr | get_value () const |
| Given a := *this, compute its value given by a.v * a.mul + a.add. | |
| Builder * | get_context () const |
| std::pair< field_t< Builder >, field_t< Builder > > | no_wrap_split_at (const size_t lsb_index, const size_t num_bits=grumpkin::MAX_NO_WRAP_INTEGER_BIT_LENGTH) const |
| Splits the field element into (lo, hi), where: | |
| bool_t< Builder > | is_zero () const |
| Validate whether a field_t element is zero. | |
| void | create_range_constraint (size_t num_bits, std::string const &msg="field_t::range_constraint") const |
| Let x = *this.normalize(), constrain x.v < 2^{num_bits}. | |
| void | assert_is_not_zero (std::string const &msg="field_t::assert_is_not_zero") const |
| Constrain *this to be non-zero by establishing that it has an inverse. | |
| void | assert_is_zero (std::string const &msg="field_t::assert_is_zero") const |
| Enforce a copy constraint between *this and 0 stored at zero_idx of the Builder. | |
| bool | is_constant () const |
| bool | is_normalized () const |
| uint32_t | set_public () const |
| void | convert_constant_to_fixed_witness (Builder *ctx) |
| void | fix_witness () |
| uint32_t | get_witness_index () const |
| Get the witness index of the current field element. | |
| template<size_t num_bits> | |
| bool_t< Builder > | ranged_less_than (const field_t< Builder > &other) const |
| Return (a < b) as bool circuit type. This method assumes that both a and b are < 2^{num_bits} i.e. it is not checked here, we assume this has been done previously. | |
Static Public Member Functions | |
| static field_t | from_witness_index (Builder *ctx, uint32_t witness_index) |
| static field_t | copy_as_new_witness (Builder &context, field_t const &other) |
| static field_t | conditional_assign_internal (const bool_t< Builder > &predicate, const field_t &lhs, const field_t &rhs) |
| If predicate == true then return lhs, else return rhs. | |
| static field_t | conditional_assign (const bool_t< Builder > &predicate, const field_t &lhs, const field_t &rhs) |
| static std::array< field_t, 4 > | preprocess_two_bit_table (const field_t &T0, const field_t &T1, const field_t &T2, const field_t &T3) |
Given a table T of size 4, outputs the monomial coefficients of the multilinear polynomial in t0, t1 that on a input binary string b of length 2, equals T_b. In the Lagrange basis, the desired polynomial is given by the formula (1 - t0)(1 - t1).T0 + t0(1 - t1).T1 + (1 - t0)t1.T2 + t0.t1.T3. | |
| static field_t | select_from_two_bit_table (const std::array< field_t, 4 > &table, const bool_t< Builder > &t1, const bool_t< Builder > &t0) |
Given a multilinear polynomial in 2 variables, which is represented by a table of monomial coefficients, compute its evaluation at the point (t0, t1) using minimal number of gates. | |
| static std::array< field_t, 8 > | preprocess_three_bit_table (const field_t &T0, const field_t &T1, const field_t &T2, const field_t &T3, const field_t &T4, const field_t &T5, const field_t &T6, const field_t &T7) |
Given a table T of size 8, outputs the monomial coefficients of the multilinear polynomial in t0, t1, t2, that on a input binary string b of length 3, equals T_b. | |
| static field_t | select_from_three_bit_table (const std::array< field_t, 8 > &table, const bool_t< Builder > &t2, const bool_t< Builder > &t1, const bool_t< Builder > &t0) |
Given a multilinear polynomial in 3 variables, which is represented by a table of monomial coefficients, compute its evaluation at (t0, t1, t2) using minimal number of gates. | |
| static void | evaluate_linear_identity (const field_t &a, const field_t &b, const field_t &c, const field_t &d, const std::string &msg="field_t::evaluate_linear_identity") |
| Constrain a + b + c + d to be equal to 0. | |
| static void | evaluate_polynomial_identity (const field_t &a, const field_t &b, const field_t &c, const field_t &d, const std::string &msg="field_t::evaluate_polynomial_identity") |
Given a, b, c, d, constrain a * b + c + d = 0 by creating a big_mul_gate. | |
| static field_t | accumulate (const std::vector< field_t > &input) |
Efficiently compute the sum of vector entries. Using big_add_gate we reduce the number of gates needed to compute from input.size() to input_size.size() / 3. | |
| static field_t | from_witness (Builder *ctx, const bb::fr &input) |
| template<typename T > | |
| static field_t | from_witness (Builder *ctx, const T &input)=delete |
| static field_t | reconstruct_from_public (const std::span< const field_t, PUBLIC_INPUTS_SIZE > &limbs) |
| static bool | witness_indices_match (const field_t &a, const field_t &b) |
| Check if two field elements have the same witness index (for identity checks). | |
Public Attributes | |
| Builder * | context = nullptr |
| bb::fr | additive_constant |
| bb::fr | multiplicative_constant |
| OriginTag | tag {} |
Static Public Attributes | |
| static constexpr size_t | PUBLIC_INPUTS_SIZE = FR_PUBLIC_INPUTS_SIZE |
| static constexpr bool | is_composite = false |
| static constexpr uint256_t | modulus = bb::fr::modulus |
Private Attributes | |
| uint32_t | witness_index = IS_CONSTANT |
Friends | |
| template<typename B > | |
| class | bool_t |
| template<typename B , typename T > | |
| class | bigfield |
| template<typename B > | |
| void | mark_witness_as_used (const field_t< B > &field) |
| using bb::stdlib::field_t< Builder_ >::Builder = Builder_ |
| using bb::stdlib::field_t< Builder_ >::CoefficientAccumulator = field_t |
| using bb::stdlib::field_t< Builder_ >::native = bb::fr |
| using bb::stdlib::field_t< Builder_ >::View = field_t |
| bb::stdlib::field_t< Builder >::field_t | ( | Builder * | parent_context = nullptr | ) |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inlinenoexcept |
|
default |
|
static |
Efficiently compute the sum of vector entries. Using big_add_gate we reduce the number of gates needed to compute from input.size() to input_size.size() / 3.
Note that if the size of the input vector is not a multiple of 3, the final gate will be padded with zero_idx wires
| void bb::stdlib::field_t< Builder >::assert_equal | ( | const field_t< Builder_ > & | rhs, |
| std::string const & | msg = "field_t< Builder_ >::assert_equal" |
||
| ) | const |
Copy constraint: constrain that *this field is equal to rhs element.
| void bb::stdlib::field_t< Builder >::assert_is_in_set | ( | const std::vector< field_t< Builder_ > > & | set, |
| std::string const & | msg = "field_t< Builder_ >::assert_not_in_set" |
||
| ) | const |
| void bb::stdlib::field_t< Builder >::assert_is_not_zero | ( | std::string const & | msg = "field_t< Builder_ >::assert_is_not_zero" | ) | const |
| void bb::stdlib::field_t< Builder >::assert_is_zero | ( | std::string const & | msg = "field_t< Builder_ >::assert_is_zero" | ) | const |
| void bb::stdlib::field_t< Builder >::assert_not_equal | ( | const field_t< Builder_ > & | rhs, |
| std::string const & | msg = "field_t< Builder_ >::assert_not_equal" |
||
| ) | const |
|
inline |
|
static |
If predicate == true then return lhs, else return rhs.
Conditional assign x = (predicate) ? lhs : rhs can be expressed arithmetically as follows x = predciate * lhs + (1 - predicate) * rhs which is equivalent to x = (lhs - rhs) * predicate + rhs = (lhs - rhs)*madd(predicate, rhs) where take advantage of madd() to create less gates.
|
inline |
|
inlinestatic |
| void bb::stdlib::field_t< Builder >::create_range_constraint | ( | size_t | num_bits, |
| std::string const & | msg = "field_t< Builder_ >::range_constraint" |
||
| ) | const |
Let x = *this.normalize(), constrain x.v < 2^{num_bits}.
|
static |
|
inline |
|
inlinestatic |
|
staticdelete |
|
inline |
|
inline |
| bb::fr bb::stdlib::field_t< Builder >::get_value | ( | ) | const |
|
inline |
Get the witness index of the current field element.
This method normalizes the field element in place and returns the witness index of the normalized representation, such that the witness actually contains the value it represents (multiplicative_constant = 1, additive_constant = 0).
Note: the normalization may add gates to the circuit, but this is the safest option that prevents soundness vulnerabilities from using witness indices that don't contain the actual field value.
Within the field_t class implementation, the raw witness_index member can be accessed directly when needed (e.g., for checking if two fields share the exact same representation).
|
inline |
|
inline |
|
inline |
| bool_t< Builder > bb::stdlib::field_t< Builder >::is_zero | ( | ) | const |
Validate whether a field_t element is zero.
Let a := (*this).normalize() is_zero := (a == 0)
To check whether a = 0, we use the fact that, if a != 0, it has a modular inverse I, such that a * I = 1.
We reduce the check to the following algebraic constraints 1) a * I - 1 + is_zero = 0 2) -is_zero * I + is_zero = 0
If the value of is_zero is false, the first equation reduces to a * I = 1 then I must be the modular inverse of a, therefore a != 0. This explains the first constraint.
If is_zero = true, then either a or I is zero (or both). To ensure that a = 0 && I != 0 we use the second constraint, it validates that (is_zero.v = true) ==> (I = 1) This way, if a * I = 0, we know that a = 0.
assert_is_zero | std::pair< field_t< Builder >, field_t< Builder > > bb::stdlib::field_t< Builder >::no_wrap_split_at | ( | const size_t | lsb_index, |
| const size_t | num_bits = grumpkin::MAX_NO_WRAP_INTEGER_BIT_LENGTH |
||
| ) | const |
Splits the field element into (lo, hi), where:
hi contains bits [lsb_index, num_bits)
Max bits is specified as an argument, and must be <= grumpkin::MAX_NO_WRAP_INTEGER_BIT_LENGTH (to ensure no modular wrap).
| field_t< Builder > bb::stdlib::field_t< Builder >::normalize | ( | ) | const |
|
explicit |
| bool_t< Builder > bb::stdlib::field_t< Builder >::operator!= | ( | const field_t< Builder_ > & | other | ) | const |
| field_t< Builder > bb::stdlib::field_t< Builder >::operator* | ( | const field_t< Builder_ > & | other | ) | const |
Field multiplication operator.
Optimized to not create extra gates when at least one of the multiplicands is constant.
Both inputs are circuit variables: create a * b constraint.
Value of this = a.v * a.mul + a.add; Value of other = b.v * b.mul + b.add; Value of result = a * b = [a.v * b.v] * [a.mul * b.mul] + a.v * [a.mul * b.add] + b.v * [a.add * b.mul] + [a.ac * b.add] = [a.v * b.v] * [ q_m ] + a.v * [ q_l ] + b.v * [ q_r ] + [ q_c ] ^ ^Notice the add/mul_constants are placed into selectors when a gate is created. | Only the witnesses (pointed-to by the witness_indexes) form the wires in/out of | the gate. ^This entire value is pushed to ctx->variables as a new witness. The implied additive & multiplicative constants of the new witness are 0 & 1 resp. Left wire value: a.v Right wire value: b.v Output wire value: result.v (with q_o = -1)
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
| field_t< Builder > bb::stdlib::field_t< Builder >::operator/ | ( | const field_t< Builder_ > & | other | ) | const |
Since in divide_no_zero_check, we check \( a / b = q \) by the constraint \( a = b \cdot q\), if \( a = b= 0\), we can set \( q \) to any value and it will pass the constraint. Hence, when not having prior knowledge of \( b \) not being zero it is essential to check.
If \( b = 0 \) and is constant, this method aborts due to failed BB_ASSERT( b !=0 ) condition inside assert_is_not_zero(). If \( b = 0 \) and is not constant, a Builder failure is set and an unsatisfiable constraint 1 = 0 is created.
|
inline |
|
inline |
|
inlinenoexcept |
| field_t< Builder > bb::stdlib::field_t< Builder >::pow | ( | const uint32_t & | exponent | ) | const |
|
static |
|
static |
Given a table T of size 4, outputs the monomial coefficients of the multilinear polynomial in t0, t1 that on a input binary string b of length 2, equals T_b. In the Lagrange basis, the desired polynomial is given by the formula (1 - t0)(1 - t1).T0 + t0(1 - t1).T1 + (1 - t0)t1.T2 + t0.t1.T3.
Expand the coefficients to obtain the coefficients in the monomial basis.
|
inline |
|
inlinestatic |
|
static |
Given a multilinear polynomial in 3 variables, which is represented by a table of monomial coefficients, compute its evaluation at (t0, t1, t2) using minimal number of gates.
The straightforward thing would be eight multiplications to get the monomials and several additions between them. It turns out you can do it in 7 madd gates using the formulas X := ((t0*a_012 + a12)*t1 + a2)*t2 + a_const // - 3 gates Y := (t0*a01 + a1)*t1 + X // - 2 gates Z := (t2*a02 + a0)*t0 + Y // - 2 gates
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inlinestatic |
Check if two field elements have the same witness index (for identity checks).
Checks if two field elements share the exact same witness_index representation. Used for optimization checks like "if inputs are identical, skip computation". Does NOT check value equality - use operator== for that.
| a | First field element |
| b | Second field element |
|
friend |
|
mutable |
additive_constant and multiplicative_constant are constant scaling factors applied to a field_t object.
The 'value' represented by a field_t is calculated as:
field_ts with witness_index = IS_CONSTANT: this.additive_constantfield_ts: this.context->variables[this.witness_index] * this.multiplicative_constant + this.additive_constantWe track these scaling factors, because we can apply the same scaling factors to Plonk wires when creating gates. I.e. if we want to multiply a wire by a constant, or add a constant, we do not need to add extra gates to do this. Instead, we track the scaling factors, and apply them to the relevant wires when adding constraints.
This also makes constant field_t objects effectively free. (Where 'constant' is a circuit constant, not a C++ constant!). E.g. the following 3 lines of code add 0 constraints into a circuit:
field_t foo = 1; field_t bar = 5; field_t bar *= foo;
Similarly if we add in:
field_t zip = witness_t(context, 10); zip *= bar + foo;
The above adds 0 constraints, the only effect is that zip's scaling factors have been modified. However if we now add:
field_t zap = witness_t(context, 50); zip *= zap;
This will add a constraint, as both zip and zap map to circuit witnesses.
|
mutable |
|
staticconstexpr |
|
staticconstexpr |
|
mutable |
|
staticconstexpr |
|
mutable |
|
mutableprivate |
Every builder object contains a vector variables (a.k.a. 'witnesses'); circuit variables that can be assigned to wires when creating constraints. witness_index describes a location in this container. I.e. it 'points' to a circuit variable.
A witness is not the same thing as a 'wire' in a circuit. Multiple wires can be assigned to the same witness via Plonk's copy constraints. Alternatively, a witness might not be assigned to any wires! This case would be similar to an unused variable in a regular program
E.g. if we write field_t foo = witness_t(context, 100), this will add the value 100 into context's list of circuit variables. However if we do not use foo in any operations, then this value will never be assigned to a wire in a circuit.
For a more in depth example, consider the following code:
field_t foo = witness_t(context, 10); field_t bar = witness_t(context, 50); field_t baz = foo * (bar + 7);
This will add 3 new circuit witnesses (10, 50, 570) to variables. One constraint will also be created, that validates baz has been correctly constructed. The builder will assign foo, bar, baz to wires w_1, w_2, w_3 in a new gate which checks that:
w_1 * w_2 + w_1 * 7 - w_3 = 0
If any of foo, bar, baz are used in future arithmetic, copy constraints will be automatically applied, this ensure that all gate wires that map to foo, for example, will contain the same value.
If witness_index == IS_CONSTANT, the object represents a constant value. i.e. a value that's hardcoded in the circuit, that a prover cannot change by modifying their witness transcript.
A Plonk gate is a mix of witness values and selector values. e.g. the regular PLONK arithmetic gate checks that:
w_1 * w_2 * q_m + w_1 * q_1 + w_2 * q_2 + w_3 * q_3 + q_c = 0
The w value are wires, the q values are selector constants. If a field object contains a witness_index, it will be assigned to w values when constraints are applied. If it's a circuit constant, it will be assigned to q values.
TLDR: witness_index is a pseudo pointer to a circuit witness
1.9.8