Arithmetization II
This is the third post in our STARK Math series, if you haven’t read the first and the second posts, we recommend you do so before reading on. Fair warning: this one is a bit mathier than its predecessors.
Recap
In the previous post we introduced arithmetization — the process of transforming a Computational Integrity (CI) statement into checking whether a polynomial is of low degree. This transformation allows us to achieve succinct verification, where the verifier of the CI statement requires exponentially less resources than those needed for naive replay. In the previous post we zoomed into the first step in this transformation through the example of transforming a CI statement about a Collatz sequence into an execution trace and a set of polynomial constraints. In this post we take the next step and show — using a Fibonacci sequence this time — how the prover can combine the execution trace and the polynomial constraints to obtain a polynomial that is guaranteed to be of low degree if and only if the execution trace satisfies the polynomial constraints that we started with. Moreover, we will show how the domain over which the polynomial is considered allows the verifier to evaluate it succinctly. We also briefly discuss how error correction codes play a role in STARKs.
We will assume familiarity with finite groups, polynomials over finite fields, and the previous posts in this series.
Queries and Error Correction Codes
Recall that our goal is to make it possible for a verifier to ask a prover a very small number of questions, and decide whether to accept or reject the proof with a guaranteed high level of accuracy. Ideally, the verifier would like to ask the prover to provide the values in a few (random) places in the execution trace, and check that the polynomial constraints hold for these places. A correct execution trace will naturally pass this test. However, it is not hard to construct a completely wrong execution trace, that violates the constraints only at a single place, and, doing so, reach a completely far and different outcome. Identifying this fault via a small number of random queries is highly improbable.
Common techniques that address similar problems are Error Correction Codes.
Error Correction Codes transform a set of strings, some of which may be very similar to one another, into a set of strings that are pairwise very different, by replacing the original strings with longer strings.
Interestingly, polynomials can be used to construct good error correction codes, since two polynomials of degree d, evaluated on a domain that is considerably larger than d, are different almost everywhere¹. Such codes are called Reed-Solomon codes.
Observing that, we can extend the execution trace by thinking of it as an evaluation of a polynomial on some domain, and evaluating this same polynomial on a much larger domain. Extending in a similar fashion an incorrect execution trace, results in a vastly different string, which in turn makes it possible for the verifier to distinguish between these cases using a small number of queries.
Our plan is therefore to 1) rephrase the execution trace as a polynomial, 2) extend it to a large domain, and 3) transform that, using the polynomial constraints, into yet another polynomial that is guaranteed to be of low degree if and only if the execution trace is valid.
Toy Example: Boolean Execution Trace
Suppose that the CI statement in question is “The prover has a sequence of 512 numbers, all of which are either 0 or 1”, which we would like to verify by reading substantially less than 512 numbers. Let’s see what kind of execution trace and polynomial constraints express this toy example:
- The execution trace has 512 rows, each row containing a single cell with either zero or one in it.
- The polynomial constraint we use here is simply Aᵢ⋅Aᵢ-Aᵢ=0, where Aᵢ denotes the i-th cell in this single-column execution trace (a number is equal to its square if and only if it is either 0 or 1).
In order to rephrase this execution trace in terms of polynomials, we specify the field we will be working in — we go with Z₉₆₇₆₉, obtained from the set of integers 0,1,…,96768 with addition and multiplication modulo 96769. Next we pick a subgroup G of Z₉₆₇₆₉* (we use F* to denote the multiplicative group² of F) such that |G|=512, and some generator³ g of G. The existence of such a subgroup is guaranteed since 512 divides the size of this group (which is 96768).
We now think of the elements in the execution trace as evaluations of some polynomial f(x) of degree less than 512 in the following way: the i-th cell contains the evaluation of f on the generator’s i-th power.
Formally:
Such a polynomial of degree at most 512 can be computed by interpolation, and we then proceed to evaluate it on a much larger domain⁴, forming a special case of Reed-Solomon codeword.
Lastly, we use this polynomial to create another one, whose low degreeness depends on the constraint being satisfied over the execution trace.
To do so, we must go on a tangent and discuss roots of polynomials.
Roots of Polynomials
A basic fact about polynomials and their roots is that if p(x) is a polynomial, then p(a)=0 for some specific value a, if and only if there exists a polynomial q(x) such that (x-a)q(x)=p(x), and deg(p)=deg(q)+1.
Moreover, for all x≠a, we can evaluate q(x) by computing:
By induction, a similar fact is true for k roots. Namely, if aᵢ is a root of p for all i=0..k-1, then there exists a polynomial q of degree deg(p)-k, and in all but these k values, it is exactly equal to
Putting It Together
Rephrasing the polynomial constraint in terms of f yields the following polynomial:
We have defined f such that the roots of this expression are 1, g, g², …, g⁵¹¹ if and only if the cells in the execution trace are 0 or 1. We can define:
And we know from the previous paragraph that there exists a polynomial of degree at most 2·deg(f)-512 that agrees with p on all x ∉{1, g, g², …, g⁵¹¹} if and only if the execution trace is indeed a list of 512 bits (i.e., 0 or 1). Note that earlier on, the prover has extended the execution trace to a larger domain, so querying for the polynomial values in that domain is well defined.
If there exists a protocol by which the prover can convince⁵ the verifier that this polynomial is of low degree, such that in it the verifier only asks for values outside the execution trace, then indeed the verifier will be convinced about the truthfulness of the CI statement only when it is true. In fact, in the next post, we will show a protocol that does exactly that, with some very small probability of error. For the time being — let’s take a look at another example, that is still simple, but not completely trivial, and see how the reduction works in that case.
Fibonacci
The example that we use next is that of correctly computing a Fibonacci sequence in Z₉₆₇₆₉ to the 512-th place. The sequence is defined formally by:
And our claim (i.e., the CI statement) is that a₅₁₁=62215.
We can create an execution trace for this CI statement by simply writing down all 512 numbers:
The polynomial constraints that we use are
Translate to Polynomials
Here, too, we define a polynomial f(x) of degree at most 512, such that the elements in the execution trace are evaluations of f in powers of some generator g.
Formally:
Expressing the polynomial constraints in terms of f instead of A, we get:
Since a composition of polynomials is still a polynomial — substituting the Aᵢ in the constraints with f(gⁱ) still means these are polynomial constraints.
Note that 1, 2, and 4 are constraints that refer to a single value of f, we refer to them as boundary constraints.
The Fibonacci recurrence relation, in contrast, embodies a set of constraints over the entire execution trace, and it may be alternatively rephrased as:
The use of a generator to index the rows of the execution trace allows us to encode the notion of “next row” as a simple algebraic relation. If x is some row in the execution trace, then gx is the next row, g²x is the row after that, g⁻¹x is the previous row and so on.
The recurrence relation polynomial: f(g²x)-f(gx)-f(x) is zero for every x that indexes a row in the execution trace, except for the last two. It means that 1, g, g², …, g⁵⁰⁹ are all roots of this recurrence relation polynomial (and it is of degree at most 510), so we can construct q(x) as follows:
In STARK lore, this is often referred to as the composition polynomial. Indeed, when the original execution trace obeys the Fibonacci recurrence relation, this expression agrees with some polynomial whose degree is at most 2 (recall that the degree of f is at most 512) on all but these 510 values: 1, g, g², …, g⁵⁰⁹ . However, the term composition polynomial is somewhat misleading, as when the execution trace does not satisfy the polynomial constraint — the evaluations of this expression differ from any low degree polynomial in many places. In other words — it is close to a low-degree polynomial if and only if the original CI is correct, which indeed was our goal.
This concludes the promised reduction, that translates the problem of checking whether certain polynomial constraints are satisfied over some execution trace, to the problem of checking whether some polynomial (known to the prover) is of low degree.
Succinctness
Having a very efficient verification technique is key to STARKs, and it can be seen as comprised of two parts — using a small number of queries, and having the verifier perform a small computation on each query. The former is achieved by error correction codes, which allow querying in very few places, and the latter we have sort of sweeped under the rug throughout this post, until now. The verifier’s work can be summed up as 1) querying the composition polynomial in random places, and 2) checking low-degreeness based on these queries. Low degreeness succinct checking will be handled in the next post, but what exactly do we mean by “querying the composition polynomial”? The avid reader may have been suspicious of this expression, and rightfully so. The prover, after all, may be malicious. When the verifier asks for the evaluation of the composition polynomial at some x, the prover may reply with the evaluation of some truly low-degree polynomial, that will pass any low-degree testing, but is not the composition polynomial.
To prevent this, the verifier explicitly queries the Fibonacci execution trace at some row w by asking for the values of f in three places: f(w), f(gw), f(g²w).
The verifier can now compute the value of the composition polynomial at w by:
Where the numerator can be computed using the values obtained from the prover, and the denominator… well, there’s the rub (that was sweeped under the rug).
On the one hand the denominator is completely independent of the execution trace, so the verifier can compute it before ever communicating with the prover.
On the other hand, in practicality — the trace may be comprised of hundreds of thousands of rows, and computing the denominator would cost the verifier dearly in running time.
Here’s where the arithmetization is crucial to succinctness — since calculating this expression for the special case where the powers of g form a subgroup can be done very efficiently if one notices that:
This equality is true because both sides are polynomials of degree |G| whose roots are exactly the elements of G.
Computing the right hand side of this equation seems to require a number of operations that is linear in |G|. However, if we resort to exponentiation by squaring, the left hand side of this equation can be computed in running time that is logarithmic in |G|.
And the actual denominator of the Fibonacci composition polynomial in question can be obtained by rewriting it as:
This seeming technicality stands at the core of the verifier being able to run in polylogarithmic time, and it is enabled only because we view the execution trace as evaluations of a polynomial over some subgroup of the field, and that the polynomial constraints in question hold over a subgroup.
Similar tricks can be applied for more sophisticated execution traces, but it is crucial that the repeating pattern of the constraint coincides with some subgroup of the field.
More Constraints, More Columns!
The examples in this post were deliberately simple, to highlight key aspects of arithmetization. A natural question that arises will be: how is the case of multiple columns and multiple constraints handled. The answer is straightforward: multiple columns simply mean that there’s more than one polynomial to work with, and multiple composition polynomials — resulting from the multiple constraints — are combined into a single polynomial, a random linear combination of all of them, for the sake of the last phase in STARK, which is a low degree test. With high probability, the linear combination is of low degree if and only if so are all of its components.
Wrapping Up
We have shown how, given an execution trace and constraint polynomials, the prover can construct a polynomial which is of low degree if and only if the original CI statement holds. Furthermore, we have shown how the verifier can query the values of this polynomial efficiently, making sure that the prover did not replace the true polynomial with some false low-degree one.
In the next post, which will go into the details of low-degree testing, showing how this magic, of querying a small number of values and determining whether some polynomial is of low degree, is done.
Shir Peled
StarkWare
¹ To see this, notice that the difference between distinct degree-d polynomials is a non-zero polynomial of degree d, hence has at most d zeros.
² Reminder: the multiplicative group is obtained by omitting the zero element from the field.
³ A generator is an element in the subgroup whose powers span the entire subgroup.
⁴ Choosing this domain’s size directly translates into the soundness error, the bigger it is — the smaller the soundness error.
⁵ Such that the verifier is convinced if and only if the prover is not cheating.
