Module folding::expressions

source ·
Expand description

Implement a library to represent expressions/multivariate polynomials that can be used with folding schemes like Nova.

We do enforce expressions to be degree 2 maximum to apply our folding scheme.

Before folding, we do suppose that each expression has been reduced to degree 2 using crate::quadraticization.

The library introduces different types of expressions:

When using the library, the user should:

The user can also choose to build a structure crate::FoldingScheme from a list of FoldingCompatibleExpr.

As a reminder, after we reduce to degree 2, the multivariate polynomial P(X_{1}, ..., X_{n}) describing the NP relation will be “relaxed” in another polynomial of the form P_relaxed(X_{1}, ..., X_{n}, u). First, we decompose the polynomial P in its monomials of degree 0, 1 and 2:

P(X_{1}, ..., X_{n}) = ∑_{i} f_{i, 0}(X_{1}, ..., X_{n}) +
                       ∑_{i} f_{i, 1}(X_{1}, ..., X_{n}) +
                       ∑_{i} f_{i, 2}(X_{1}, ..., X_{n})

where f_{i, 0} is a monomial of degree 0, f_{i, 1} is a monomial of degree 1 and f_{i, 2} is a monomial of degree 2. For instance, for the polynomial P(X_{1}, X_{2}, X_{3}) = X_{1} * X_{2} + (1 - X_{3}), we have:

f_{0, 0}(X_{1}, X_{2}, X_{3}) = 1
f_{0, 1}(X_{1}, X_{2}, X_{3}) = -X_{3}
f_{0, 2}(X_{1}, X_{2}, X_{3}) = X_{1} * X_{2}

Then, we can relax the polynomial P in P_relaxed by adding a new variable u in the following way:

  • For the monomials f_{i, 0}, i.e. the monomials of degree 0, we add u^2 to the expression.
  • For the monomials f_{i, 1}, we add u to the expression.
  • For the monomials f_{i, 2}, we keep the expression as is.

For the polynomial P(X_{1}, X_{2}, X_{3}) = X_{1} * X_{2} + (1 - X_{3}), we have:

P_relaxed(X_{1}, X_{2}, X_{3}, u) = X_{1} * X_{2} + u (u - X_{3})

From the relaxed form of the polynomial, we can “fold” multiple instances of the NP relation by randomising it into a single instance by adding an error term E. For instance, for the polynomial P_relaxed(X_{1}, X_{2}, X_{3}, u) = X_{1} * X_{2} + u (u - X_{3}), for two instances (X_{1}, X_{2}, X_{3}, u) and (X_{1}', X_{2}', X_{3}', u'), we can fold them into a single instance by coining a random value r:

X''_{1} = X_{1} + r X_{1}'
X''_{2} = X_{2} + r X_{2}'
X''_{3} = X_{3} + r X_{3}'
u'' = u + r u'

Computing the polynomial P_relaxed(X''_{1}, X''_{2}, X''_{3}, u'') will give:

  (X_{1} + r X'_{1}) (X_{2} + r X'_{2}) \
+ (u + r u') [(u + r u') - (X_{3} + r X'_{3})]

which can be simplified into:

  P_relaxed(X_{1}, X_{2}, X_{3}, u) + P_relaxed(r X_{1}', r X_{2}', r X_{3}', r u')
+ r [u (u' - X_{3}) + u' (u - X_{3})] + r [X_{1} X_{2}'   +   X_{2} X_{1}']
  \---------------------------------/   \----------------------------------/
 cross terms of monomials of degree 1   cross terms of monomials of degree 2
             and degree 0

The error term T (or “cross term”) is the last term of the expression, multiplied by r. More generally, the error term is the sum of all monomials introduced by the “cross terms” of the instances. For example, if there is a monomial of degree 2 like X_{1} * X_{2}, it introduces the cross terms r X_{1} X_{2}' + r X_{2} X_{1}'. For a monomial of degree 1, for example u X_{1}, it introduces the cross terms r u X_{1}' + r u' X_{1}.

Note that:

      P_relaxed(r X_{1}', r X_{2}', r X_{3}', r u')
= r^2 P_relaxed(X_{1}',   X_{2}',   X_{3}',   u')

and P_relaxed is of degree 2. More precisely, P_relaxed is homogenous. And that is the main idea of folding: the “relaxation” of a polynomial means we make it homogenous for a certain degree d by introducing the new variable u, and introduce the concept of “error terms” that will englobe the “cross-terms”. The prover takes care of computing the cross-terms and commit to them.

While folding, we aggregate the error terms of all instances into a single error term, E. In our example, if we have a folded instance with the non-zero error terms E_{1} and E_{2}, we have:

E = E_{1} + r T + E_{2}

Aggregating constraints

The library also provides a way to fold NP relations described by a list of multi-variate polynomials, like we usually have in a zkSNARK circuit.

In PlonK, we aggregate all the polynomials into a single polynomial by coining a random value α. For instance, if we have two polynomials P and Q describing our computation in a zkSNARK circuit, we usually use the randomized polynomial P + α Q (used to build the quotient polynomial in PlonK).

More generally, if for each row, our computation is constrained by the polynomial list [P_{1}, P_{2}, ..., P_{n}], we can aggregate them into a single polynomial P_{agg} = ∑_{i} α^{i} P_{i}. Multiplying by the α terms consequently increases the overall degree of the expression.

In particular, when we reduce a polynomial to degree 2, we have this case where the circuit is described by a list of polynomials and we aggregate them into a single polynomial.

For instance, if we have two polynomials P(X_{1}, X_{2}, X_{3}) and Q(X_{1}, X_{2}, X_{3}) such that:

P(X_{1}, X_{2}, X_{3}) = X_{1} * X_{2} + (1 - X_{3})
Q(X_{1}, X_{2}, X_{3}) = X_{1} + X_{2}

The relaxed form of the polynomials are:

P_relaxed(X_{1}, X_{2}, X_{3}, u) = X_{1} * X_{2} + u (u - X_{3})
Q_relaxed(X_{1}, X_{2}, X_{3}, u) = u X_{1} + u X_{2}

We start by coining α_{1} and α_{2} and we compute the polynomial P'(X_{1}, X_{2}, X_{3}, u, α_{1}) and Q'(X_{1}, X_{2}, X_{3}, α_{2}) such that:

P'(X_{1}, X_{2}, X_{3}, u, α_{1}) = α_{1} P_relaxed(X_{1}, X_{2}, X_{3}, u)
                                  = α_{1} (X_{1} * X_{2} + u (u - X_{3}))
                                  = α_{1} X_{1} * X_{2} + α_{1} u^2 - α_{1} u X_{3}
Q'(X_{1}, X_{2}, X_{3}, u, α_{2}) = α_{2} Q_relaxed(X_{1}, X_{2}, X_{3}, u)
                                  = α_{2} (u X_{1} + u X_{2})
                                  = α_{2} u X_{1} + α_{2} u X_{2}

and we want to fold the multivariate polynomial S defined over six variables:

  S(X_{1}, X_{2}, X_{3}, u, α_{1}, α_{2})
= P'(X_{1}, X_{2}, X_{3}, u, α_{1}) + Q'(X_{1}, X_{2}, X_{3}, u, α_{2})`.
= α_{1} X_{1} X_{2} +
  α_{1} u^2 -
  α_{1} u X_{3} +
  α_{2} u X_{1} +
  α_{2} u X_{2}

Note that we end up with everything of the same degree, which is 3 in this case. The variables α_{1} and α_{2} increase the degree of the homogeneous expressions by one.

For two given instances (X_{1}, X_{2}, X_{3}, u, α_{1}, α_{2}) and (X_{1}', X_{2}', X_{3}', u', α_{1}', α_{2}'), we coin a random value r and we compute:

X''_{1} = X_{1} + r X'_{1}
X''_{2} = X_{2} + r X'_{2}
X''_{3} = X_{3} + r X'_{3}
u'' = u + r u'
α''_{1} = α_{1} + r α'_{1}
α''_{2} = α_{2} + r α'_{2}

From there, we compute the evaluations of the polynomial S at the point S(X''_{1}, X''_{2}, X''_{3}, u'', α''_{1}, α''_{2}), which gives:

  S(X_{1}, X_{2}, X_{3}, u, α_{1}, α_{2})
+ S(r X'_{1}, r X'_{2}, r X'_{3}, r u', r α'_{1}, r α'_{2})
+ r T_{0}
+ r^2 T_{1}

where T_{0} (respectively T_{1}) are cross terms that are multiplied by r (respectively r^2). More precisely, for T_{0} we have:

T_{0} = a_{1} X_{1} X'{2} +
        X_{2} (α_{1} X'_{1} + α'_{1} X_{1}) +
        // we repeat for a_{1} u^{2}, ... as described below

We must see each monomial as a polynomial P(X, Y, Z) of degree 3, and the cross-term for each monomial will be, for (X’, Y’, Z’) and (X, Y, Z):

X Y Z' + Z (X Y' + X' Y)

As for the degree2 case described before, we notice that the polynomial S is homogeneous of degree 3, i.e.

      S(r X'_{1}, r X'_{2}, r X'_{3}, r u', r α'_{1}, r α'_{2})
= r^3 S(X'_{1},   X'_{2},   X'_{3},   u',   α'_{1},   α'_{2})

Fiat-Shamir challenges, interactive protocols and lookup arguments

Until now, we have described a way to fold multi-variate polynomials, which is mostly a generalization of Nova for any multi-variate polynomial. However, we did not describe how it can be used to describe and fold interactive protocols based on polynomials, like PlonK. We do suppose the interactive protocol can be made non-interactive by using the Fiat-Shamir transformation.

To fold interactive protocols, our folding scheme must also support Fiat-Shamir challenges. This implementation handles this by representing challenges as new variables in the polynomial describing the NP relation. The challenges are then aggregated in the same way as the other variables.

For instance, let’s consider the additive lookup/logup argument. For a detailed description of the protocol, see the online documentation. We will suppose we have only one table T and Alice wants to prove to Bob that she knows that all evaluations of f(X) is in t(X). The additive lookup argument is described by the polynomial equation:

β + f(x) = m(x) (β + t(x))

where β is the challenge, f(x) is the polynomial whose evaluations describe the value Alice wants to prove to Bob that is in the table, m(x) is the polynomial describing the multiplicities, and t(x) is the polynomial describing the (fixed) table.

The equation can be described by the multi-variate polynomial LOGUP:

LOGUP(β, F, M, T) = β + F - M (β + T)

The relaxed/homogeneous version of the polynomial LOGUP is:

LOGUP_relaxed(β, F, M, T, u) = u β + u F - M (β + T)

Folding this polynomial means that we will coin a random value r, and we compute:

β'' = β + r β'
F'' = F + r F'
M'' = M + r M'
T'' = T + r T'
u'' = u + r u'

Supporting polynomial commitment blinders

The library also supports polynomial commitment blinders. The blinding factors are represented as new variables in the polynomial describing the NP relation. The blinding factors are then aggregated in the same way as the other variables. We want to support blinders in the polynomial commitment scheme to avoid committing to the zero zero polynomial. Using a blinder, we can always suppose that our elliptic curves points are not the point at infinity. The library handles the blinding factors as variables in each instance.

When doing the final proof, the blinder factor that will need to be used is the one from the final relaxed instance.

Structs

  • IntegratedFoldingExpr
    A value of type IntegratedFoldingExpr is the result of the split of a polynomial in its monomials of degree 0, 1 and 2. It is used to compute the error terms. For an example, have a look at the top level documentation.
  • Term
    A term of a polynomial For instance, in the polynomial 3 X_{1} X_{2} + 2 X_{3}, the terms are 3 X_{1} X_{2} and 2 X_{3}. The sign is used to encode the sign of the term at the expression level. It is used to split a polynomial in its terms/monomials of degree 0, 1 and 2.

Enums

Traits

Functions