Structured polynomial class that represents the coefficients 'a' of a_0 + a_1 x ... a_n x^n of a finite field polynomial equation of degree that is at most the size of some zk circuit. Past 'n' it has a virtual size where it conceptually has coefficients all equal to 0. Notably, we allow indexing past 'n' up to our virtual size (checked only in a debug build, however). As well, we have a start index that means coefficients before start_index are also considered to be 0. The polynomial is used to represent the gates of our arithmetized zk programs. Polynomials use the majority of the memory in proving, so caution should be used in making sure unnecessary copies are avoided, both for avoiding unnecessary memory usage and performance due to unnecessary allocations. The polynomial has a maximum degree in the underlying SharedShiftedVirtualZeroesArray, dictated by the circuit size, this is just used for debugging as we represent.
More...
|
| | Polynomial (size_t size, size_t virtual_size, size_t start_index=0) |
| | Initialize a Polynomial to size 'size', zeroing memory.
|
| |
| | Polynomial (size_t size) |
| |
| | Polynomial (size_t size, size_t virtual_size, size_t start_index, DontZeroMemory flag) |
| | Initialize a Polynomial to size 'size'. Important: This does NOT zero memory.
|
| |
| | Polynomial (size_t size, size_t virtual_size, DontZeroMemory flag) |
| |
| | Polynomial (size_t size, DontZeroMemory flag) |
| |
| | Polynomial (const Polynomial &other) |
| |
| | Polynomial (const Polynomial &other, size_t target_size) |
| |
| | Polynomial (Polynomial &&other) noexcept=default |
| |
| | Polynomial (std::span< const Fr > coefficients, size_t virtual_size) |
| |
| | Polynomial (std::span< const Fr > coefficients) |
| |
| | Polynomial ()=default |
| |
| | Polynomial (std::span< const Fr > interpolation_points, std::span< const Fr > evaluations, size_t virtual_size) |
| | Create the degree-(m-1) polynomial T(X) that interpolates the given evaluations. We have T(xⱼ) = yⱼ for j=1,...,m.
|
| |
| Polynomial & | operator= (Polynomial &&other) noexcept=default |
| |
| Polynomial & | operator= (const Polynomial &other) |
| |
| | ~Polynomial ()=default |
| |
| Polynomial | share () const |
| |
| void | clear () |
| |
| bool | is_zero () const |
| | Check whether or not a polynomial is identically zero.
|
| |
| bool | operator== (Polynomial const &rhs) const |
| |
| const Fr & | get (size_t i, size_t virtual_padding=0) const |
| | Retrieves the value at the specified index.
|
| |
| bool | is_empty () const |
| |
| Polynomial | shifted () const |
| | Returns a Polynomial the left-shift of self.
|
| |
| Polynomial | right_shifted (const size_t magnitude) const |
| | Returns a Polynomial equal to the right-shift-by-magnitude of self.
|
| |
| Polynomial | reverse () const |
| | Returns the polynomial equal to the reverse of self.
|
| |
| Fr | evaluate_mle (std::span< const Fr > evaluation_points, bool shift=false) const |
| | evaluate multi-linear extension p(X_0,…,X_{n-1}) = \sum_i a_i*L_i(X_0,…,X_{n-1}) at u = (u_0,…,u_{n-1}) If the polynomial is embedded into a lower dimension k<n, i.e, start_index + size <= 2^k, we evaluate it in a more efficient way. Note that a_j == 0 for any j >= 2^k. We fold over k dimensions and then multiply the result by (1 - u_k) * (1 - u_{k+1}) ... * (1 - u_{n-1}). In this case, for any i < 2^k, L_i is a multiple of (1 - X_k) * (1 - X_{k+1}) ... * (1 - X_{n-1}). Dividing p by this monomial leads to a multilinear extension over variables X_0, X_1, ..X_{k-1}.
|
| |
| Polynomial | partial_evaluate_mle (std::span< const Fr > evaluation_points) const |
| | Partially evaluates in the last k variables a polynomial interpreted as a multilinear extension.
|
| |
| Fr | compute_barycentric_evaluation (const Fr &z, const EvaluationDomain< Fr > &domain) |
| |
| Fr | compute_kate_opening_coefficients (const Fr &z) |
| |
| void | factor_roots (const Fr &root) |
| | Divides p(X) by (X-r) in-place. Assumes that p(rⱼ)=0 for all j.
|
| |
| Fr | evaluate (const Fr &z, size_t target_size) const |
| |
| Fr | evaluate (const Fr &z) const |
| |
| void | add_scaled (PolynomialSpan< const Fr > other, Fr scaling_factor) & |
| | adds the polynomial q(X) 'other', multiplied by a scaling factor.
|
| |
| Polynomial & | operator+= (PolynomialSpan< const Fr > other) |
| | adds the polynomial q(X) 'other'.
|
| |
| Polynomial & | operator-= (PolynomialSpan< const Fr > other) |
| | subtracts the polynomial q(X) 'other'.
|
| |
| Polynomial & | operator*= (Fr scaling_factor) |
| | sets this = p(X) to s⋅p(X)
|
| |
| void | mask () |
| | Add random values to the coefficients of a polynomial. In practice, this is used for ensuring the commitment and evaluation of a polynomial don't leak information about the coefficients in the context of zero knowledge.
|
| |
| std::size_t | size () const |
| |
| std::size_t | virtual_size () const |
| |
| void | increase_virtual_size (const size_t size_in) |
| |
| Fr * | data () |
| |
| const Fr * | data () const |
| |
| Fr & | at (size_t index) |
| | Our mutable accessor, unlike operator[]. We abuse precedent a bit to differentiate at() and operator[] as mutable and immutable, respectively. This means at() can only index within start_index()..end_index() unlike operator[] which can index 0..virtual_size.
|
| |
| const Fr & | at (size_t index) const |
| |
| const Fr & | operator[] (size_t i) |
| |
| const Fr & | operator[] (size_t i) const |
| |
| Polynomial | expand (const size_t new_start_index, const size_t new_end_index) const |
| | Expands the polynomial with new start_index and end_index The value of the polynomial remains the same, but defined memory region differs.
|
| |
| void | shrink_end_index (const size_t new_end_index) |
| | The end_index of the polynomial is decreased without any memory de-allocation. This is a very fast way to zeroize the polynomial tail from new_end_index to the end. It also means that the new end_index might be smaller than the backed memory.
|
| |
| Polynomial | full () const |
| | Copys the polynomial, but with the whole address space usable. The value of the polynomial remains the same, but defined memory region differs.
|
| |
| size_t | start_index () const |
| |
| size_t | end_index () const |
| |
| std::span< Fr > | coeffs (size_t offset=0) |
| | Strictly iterates the defined region of the polynomial. We keep this explicit, instead of having an implicit conversion to span. This is safer as it is more likely that we need to consider our start_index() along with the span, as in PolynomialSpan below.
|
| |
| std::span< const Fr > | coeffs (size_t offset=0) const |
| |
| | operator PolynomialSpan< Fr > () |
| | Convert to an std::span bundled with our start index.
|
| |
| | operator PolynomialSpan< const Fr > () const |
| | Convert to an std::span bundled with our start index.
|
| |
| auto | indices () const |
| |
| auto | indexed_values () |
| |
| auto | indexed_values () const |
| |
| bool | is_valid_set_index (size_t index) const |
| | Is this index valid for a set? i.e. calling poly.at(index) = value.
|
| |
| void | set_if_valid_index (size_t index, const Fr &value) |
| | Like setting with at(), but allows zeroes to result in no set.
|
| |
| template<typename T > |
| void | copy_vector (const std::vector< T > &vec) |
| | Copy over values from a vector that is of a convertible type.
|
| |
| Fr | debug_hash () const |
| |
Structured polynomial class that represents the coefficients 'a' of a_0 + a_1 x ... a_n x^n of a finite field polynomial equation of degree that is at most the size of some zk circuit. Past 'n' it has a virtual size where it conceptually has coefficients all equal to 0. Notably, we allow indexing past 'n' up to our virtual size (checked only in a debug build, however). As well, we have a start index that means coefficients before start_index are also considered to be 0. The polynomial is used to represent the gates of our arithmetized zk programs. Polynomials use the majority of the memory in proving, so caution should be used in making sure unnecessary copies are avoided, both for avoiding unnecessary memory usage and performance due to unnecessary allocations. The polynomial has a maximum degree in the underlying SharedShiftedVirtualZeroesArray, dictated by the circuit size, this is just used for debugging as we represent.
- Template Parameters
-
Definition at line 74 of file polynomial.hpp.
evaluate multi-linear extension p(X_0,…,X_{n-1}) = \sum_i a_i*L_i(X_0,…,X_{n-1}) at u = (u_0,…,u_{n-1}) If the polynomial is embedded into a lower dimension k<n, i.e, start_index + size <= 2^k, we evaluate it in a more efficient way. Note that a_j == 0 for any j >= 2^k. We fold over k dimensions and then multiply the result by (1 - u_k) * (1 - u_{k+1}) ... * (1 - u_{n-1}). In this case, for any i < 2^k, L_i is a multiple of (1 - X_k) * (1 - X_{k+1}) ... * (1 - X_{n-1}). Dividing p by this monomial leads to a multilinear extension over variables X_0, X_1, ..X_{k-1}.
this function allocates a temporary buffer of size 2^(k-1)
- Parameters
-
| evaluation_points | evaluation vector of size n |
| shift | a boolean and when set to true, we evaluate the shifted counterpart polynomial: enforce a_0 == 0 and compute \sum_i a_{i+1}*L_i(X_0,…,X_{n-1}) |
Definition at line 202 of file polynomial.cpp.
Partially evaluates in the last k variables a polynomial interpreted as a multilinear extension.
Partially evaluates p(X) = (a_0, ..., a_{2^n-1}) considered as multilinear extension p(X_0,…,X_{n-1}) = \sum_i a_i*L_i(X_0,…,X_{n-1}) at u = (u_0,…,u_{m-1}), m < n, in the last m variables X_n-m,…,X_{n-1}. The result is a multilinear polynomial in n-m variables g(X_0,…,X_{n-m-1})) = p(X_0,…,X_{n-m-1},u_0,...u_{m-1}).
- Note
- Intuitively, partially evaluating in one variable collapses the hypercube in one dimension, halving the number of coefficients needed to represent the result. To partially evaluate starting with the first variable (as is done in evaluate_mle), the vector of coefficents is halved by combining adjacent rows in a pairwise fashion (similar to what is done in Sumcheck via "edges"). To evaluate starting from the last variable, we instead bisect the whole vector and combine the two halves. I.e. rather than coefficents being combined with their immediate neighbor, they are combined with the coefficient that lives n/2 indices away.
- Parameters
-
| evaluation_points | an MLE partial evaluation point u = (u_0,…,u_{m-1}) |
- Returns
- DensePolynomial<Fr> g(X_0,…,X_{n-m-1})) = p(X_0,…,X_{n-m-1},u_0,...u_{m-1})
Definition at line 207 of file polynomial.cpp.
1.9.8