|
barretenberg
|
Public Types | |
| using | View = field_t |
Public Member Functions | |
| field_t (Builder *parent_context=nullptr) | |
| field_t (Builder *parent_context, const barretenberg::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 barretenberg::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) | |
| operator bool_t< Builder > () const | |
| field_t & | operator= (const field_t &other) |
| field_t & | operator= (field_t &&other) noexcept |
| field_t | operator+ (const field_t &other) const |
| field_t | operator- (const field_t &other) const |
| field_t | operator* (const field_t &other) const |
| field_t | operator/ (const field_t &other) const |
| field_t | divide_no_zero_check (const field_t &other) const |
| field_t | sqr () const |
| 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 |
| field_t | conditional_negate (const bool_t< Builder > &predicate) const |
| void | assert_equal (const field_t &rhs, std::string const &msg="field_t::assert_equal") const |
| Constrain that this field is equal to the given field. | |
| void | assert_not_equal (const field_t &rhs, std::string const &msg="field_t::assert_not_equal") const |
| void | assert_is_in_set (const std::vector< field_t > &set, std::string const &msg="field_t::assert_not_in_set") const |
| field_t | madd (const field_t &to_mul, const field_t &to_add) const |
| field_t | add_two (const field_t &add_a, const field_t &add_b) const |
| bool_t< Builder > | operator== (const field_t &other) const |
| bool_t< Builder > | operator!= (const field_t &other) const |
| field_t | normalize () const |
| barretenberg::fr | get_value () const |
| Builder * | get_context () const |
| std::array< field_t, 3 > | slice (uint8_t msb, uint8_t lsb) const |
| bool_t< Builder > | is_zero () const |
| void | create_range_constraint (size_t num_bits, std::string const &msg="field_t::range_constraint") const |
| void | assert_is_not_zero (std::string const &msg="field_t::assert_is_not_zero") const |
| void | assert_is_zero (std::string const &msg="field_t::assert_is_zero") const |
| bool | is_constant () const |
| void | set_public () const |
| void | convert_constant_to_fixed_witness (Builder *ctx) |
| void | fix_witness () |
| uint32_t | get_witness_index () const |
| std::vector< bool_t< Builder > > | decompose_into_bits (size_t num_bits=256, std::function< witness_t< Builder >(Builder *ctx, uint64_t, uint256_t)> get_bit=[](Builder *ctx, uint64_t j, const uint256_t &val) { return witness_t< Builder >(ctx, val.get_bit(j));}) const |
Build a circuit allowing a user to prove that they have deomposed this into bits. | |
| 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^{input_bits} - 1 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 *parent_context, uint32_t witness_index) |
| static field_t | copy_as_new_witness (Builder &context, field_t const &other) |
| static field_t | coset_generator (const size_t generator_idx) |
| static field_t | external_coset_generator () |
| 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) |
| 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) |
| 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) |
| 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) |
| static void | evaluate_linear_identity (const field_t &a, const field_t &b, const field_t &c, const field_t &d) |
| static void | evaluate_polynomial_identity (const field_t &a, const field_t &b, const field_t &c, const field_t &d) |
| static field_t | accumulate (const std::vector< field_t > &to_add) |
| static field_t | from_witness (Builder *ctx, const barretenberg::fr &input) |
Public Attributes | |
| Builder * | context = nullptr |
| barretenberg::fr | additive_constant |
| barretenberg::fr | multiplicative_constant |
| uint32_t | witness_index = IS_CONSTANT |
Static Public Attributes | |
| static constexpr bool | is_composite = false |
| static constexpr uint256_t | modulus = barretenberg::fr::modulus |
|
static |
Compute sum of inputs
If we are using UltraCircuitBuilder, we can accumulate 3 values into a sum per gate. We track a decumulating sum of values in the 4th wire of every row. i.e. the 4th wire of the first row is the total output value
At every gate, we subtract off three elements from input. Every gate apart from the final gate, is an 'extended' addition gate, that includes the 4th wire of the next gate
e.g. to accumulate 9 limbs, structure is:
| l_1 | l_2 | l_3 | s_3 | | l_4 | l_5 | l_6 | s_2 | | l_7 | l_8 | l_9 | s_1 |
We validate:
s_3 - l_1 - l_2 - l_3 - s_2 = 0 s_2 - l_4 - l_5 - l_6 - s_1 = 0 s_1 - l_7 - l_8 - l_9 = 0
If num elements is not a multiple of 3, the final gate will be padded with zero_idx wires
| void proof_system::plonk::stdlib::field_t< Builder >::assert_equal | ( | const field_t< Builder > & | rhs, |
| std::string const & | msg = "field_t< Builder >::assert_equal" |
||
| ) | const |
Constrain that this field is equal to the given field.
|
inline |
Create a witness form a constant. This way the value of the witness is fixed and public (public, because the value becomes hard-coded as an element of the q_c selector vector).
| std::vector< bool_t< Builder > > proof_system::plonk::stdlib::field_t< Builder >::decompose_into_bits | ( | size_t | num_bits = 256, |
| std::function< witness_t< Builder >(Builder *ctx, uint64_t, uint256_t)> | get_bit = [](Builder* ctx, uint64_t j, const uint256_t& val) { return witness_t<Builder>(ctx, val.get_bit(j)); } |
||
| ) | const |
Build a circuit allowing a user to prove that they have deomposed this into bits.
A bit vector result is extracted and used to to construct a sum sum using the normal binary expansion. Along the way, we extract a value shifted_high_limb which is equal to sum_hi in the natural decomposition sum = sum_lo + 2**128*sum_hi. We impose a copy constraint between sum and this but that only imposes equality in Fr; it could be that result has overflowed the modulus r. To impose a unique value of result, we constrain sum to satisfy r - 1 >= sum >= 0. In order to do this inside of Fr, we must reduce break the check down in the smaller checks so that we can check non-negativity of integers using range constraints in Fr.
At circuit compilation time we build the decomposition r - 1 = p_lo + 2**128*p_hi. Then desired schoolbook subtraction is p_hi - b | p_lo + b*2**128 (++foo++ is foo crossed out) ++p_hi++ | ++p_lo++ (b = 0, 1)
y_lo := p_hi - b - sum_hi | y_hi := p_lo + b*2**128 - sum_lo
Here b is the boolean "a carry is necessary". Each of the resulting values can be checked for underflow by imposing a small range constraint, since the negative of a small value in Fr is a large value in Fr.
|
inline |
Fix a witness. The value of the witness is constrained with a selector
| bool_t< Builder > proof_system::plonk::stdlib::field_t< Builder >::is_zero |
| field_t< Builder > proof_system::plonk::stdlib::field_t< Builder >::madd | ( | const field_t< Builder > & | to_mul, |
| const field_t< Builder > & | to_add | ||
| ) | const |
multiply *this by to_mul and add to_add One madd call costs 1 constraint for Ultra plonk
this * to_mul + to_add | field_t< Builder > proof_system::plonk::stdlib::field_t< Builder >::normalize |
normalize returns a field_t element with equivalent value to this, but where multiplicative_constant = 1 and additive_constant = 0. I.e. the returned value is defined entirely by the builder variable that witness_index points to (no scaling factors).
If the witness_index of this is ever needed, normalize should be called first.
Will cost 1 constraint if the field element is not already normalized, as a new witness value would need to be created. Constants do not need to be normalized, as there is no underlying 'witness'; a constant's value is wholly tracked by this.additive_constant, so we definitely don't want to set that to 0!
| field_t< Builder > proof_system::plonk::stdlib::field_t< Builder >::operator* | ( | const field_t< Builder > & | other | ) | const |
Let: a := this; b := other; a.v := ctx->variables[this.witness_index]; b.v := ctx->variables[other.witness_index]; .mul = .multiplicative_constant .add = .additive_constant
Value of this = a.v * a.mul + a.add; Value of other = b.add Value of result = a * b = a.v * [a.mul * b.add] + [a.add * b.add] ^ ^result.mul ^result.add ^result.v
Value of this = a.add; Value of other = b.v * b.mul + b.add Value of result = a * b = b.v * [a.add * b.mul] + [a.add * b.add] ^ ^result.mul ^result.add ^result.v
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 form 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 |
Return (a < b) as bool circuit type. This method assumes that both a and b are < 2^{input_bits} - 1 i.e. it is not checked here, we assume this has been done previously.
| Builder | |
| input_bits |
| a | |
| b |
| std::array< field_t< Builder >, 3 > proof_system::plonk::stdlib::field_t< Builder >::slice | ( | uint8_t | msb, |
| uint8_t | lsb | ||
| ) | const |
Slices a field_t at given indices (msb, lsb) both included in the slice, returns three parts: [low, slice, high].
|
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 |
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 * w_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.6