Skip to content
This repository was archived by the owner on Jun 20, 2024. It is now read-only.

Latest commit

 

History

History
354 lines (245 loc) · 28.9 KB

ch05-08-02-constraints-rust.md

File metadata and controls

354 lines (245 loc) · 28.9 KB

Copyright 2019 StarkWare Industries Ltd. Licensed under the Apache License, Version 2.0 (the "License"). You may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.starkware.co/open-source-license/ Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Part 2: Constraints

In this part, we are going to create a set of constraints over the trace a. The constraints will be expressions in the trace’s cells that are polynomials (rather than rational functions) if and only if the trace represents a valid computation of the FibonacciSq. We will get there in three steps:

  1. Start by specifying the constraints we care about (the FibonacciSq constraints).

  2. Translate the FibonacciSq constraints into polynomial constraints.

  3. Translate those into rational functions that represent polynomials if and only if the original constraints hold.

Step 1 - FibonacciSq Constraints

For a to be a correct trace of a FibonacciSq sequence that proves our claim:

  1. The first element has to be 1, namely = 1].

  2. The last element has to be 2338775057, namely = 2338775057].

  3. The FibonacciSq rule must apply, that is - for every , [i+2]=a[i+1]²+a[i]².

Step 2 - Polynomial Constraints

Recall that f is a polynomial over the trace domain, that evaluates exactly to a over where is the "small" group generated by .

We now rewrite the above three constraints in a form of polynomial constraints over f:

  1. = 1] is translated to the polynomial , which evaluates to 0 for (note that is ).

  2. = 2338775057] is translated to the polynomial , which evaluates to 0 for .

  3. [i+2]=a[i+1]²+a[i]² for every is translated to the polynomial , which evaluates to 0 for .

Hands on

First, since this is a separate notebook from Part 1, let’s run the following piece of code to have all the variables here with their correct values. Note that it may take up to 30 seconds, since it reruns the polynomial interpolation.

:dep stark101-rs = { path = "stark101" }
:dep sha256 = "1.1.2"
use stark101_rs::{field::FieldElement, channel::Channel, polynomial::{Polynomial, x}};
use stark101_rs::parts::part1();

let (a, g, G, h, H, eval_domain, f, f_eval, f_merkle, channel) = part1();
println!("Success!");

Success!

You will obtain each of the three constraints as a quotient of two polynomials, making sure the remainder is the zero polynomial.

Step 3 - Rational Functions (That are in Fact Polynomials)

Each of the constraints above is represented by a polynomial that supposedly evaluates to on certain elements of the group . That is, for some , we claim that

(note that for the first two constraints, because they only refer to one point and for the third ).

This is equivalent to saying that is divisible, as a polynomial, by all of , or, equivalently, by

Therefore, each of the three constraints above can be written as a rational function of the form:

for the corresponding and . In this step we will construct these three rational functions and show that they are indeed polynomials.

The First Constraint:

In the first constraint, and .

We will now construct the polynomial , making sure that is indeed divisible by .

// First constraint. Construct numer0 and denom0.
let numer0: Polynomial = todo!();
let denom0: Polynomial = todo!();

Solution:

let numer0: Polynomial = f.clone() - FieldElement::one();
let denom0: Polynomial = x() - FieldElement::one();

Convince yourself that vanishes at by making sure that evaluating this polynomial at yields :

todo!("You should evaluate f(x) - 1 at x = 1");

The fact that has a root at implies that it is divisible by . Run the following cell to convince yourself that the remainder of numer0 modulo denom0 is , and therefore division indeed yields a polynomial:

numer0.clone() % denom0.clone()

Polynomial([])

Run the following cell to construct p0, the polynomial representing the first constraint, by dividing numer0 by denom0:

let p0: Polynomial = numer0 / denom0;

Run test:

assert_eq!(p0(2718), 2509888982);
println!("Success!");

Success!

The Second Constraint

Construct the polynomial p1 representing the second constraint, , similarly:

// Second constraint.
let p1: Polynomial = todo!();

Solution:

let numer1: Polynomial = f.clone() - FieldElement::new(2338775057);
let denom1: Polynomial = x() - g.pow(1022usize);
let p1: Polynomial = numer1 / denom1.clone();

Run test:

assert_eq!(p1(5772), 232961446);
println!("Success!");

Success!

The Third Constraint - Succinctness

The last constraint’s rational function is slightly more complicated:

whose denominator can be rewritten, so that the entire expression is easier to compute:

This follows from the equality

Convince yourself of this equality using the function prod that takes a list and computes its product:

// Construct a list `lst` of the linear terms (x-g**i):
let lst: Vec<Polynomial> = todo!();
// Compute the product of `lst` and see that it is indeed the succinct polynomial x**1024 - 1
Polynomial::prod(&lst);

thread '<unnamed>' panicked at 'not yet implemented', src/lib.rs:134:28
stack backtrace:
   0: _rust_begin_unwind
   1: core::panicking::panic_fmt
   2: core::panicking::panic
   3: <core::panic::unwind_safe::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once
   4: _run_user_code_14
   5: evcxr::runtime::Runtime::run_loop
   6: evcxr::runtime::runtime_hook
   7: evcxr_jupyter::main
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

Solution:

let lst: Vec<Polynomial> = (0..1024).into_iter().map(|i| x() - g.pow(i)).collect();
Polynomial::prod(&lst)

Polynomial([FieldElement(3221225472), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(1)])

For more information, see our blog post titled Arithmetization II.

Let’s pause for a moment, and look at a simple example on how polynomials are composed. After that we will generate the third constraint.

Composing Polynomials (a detour)

Create the two polynomials , :

let q: Polynomial = x().pow(2)*2usize + 1;
let r = x() - 3usize;

Composing on yields a new polynomial: Run the following cell to create a third polynomial cmp by composing q on r and convince yourself that cmp is indeed the composition of q and r:

let cmp = q(r);
cmp

Polynomial([FieldElement(19), FieldElement(3221225461), FieldElement(2)])

Back to Polynomial Constraints

Construct the third constraint p2 in a similar manner to the construction of p0 and p1, using polynomial composition. Along the way, verify that is a root of the numerator while is not.

let p2: Polynomial = todo!();

Solution:

let numer_1: Polynomial = f(x() * g.pow(2));
let numer_2: Polynomial = f(x() * g).pow(2) * FieldElement::new((-1 + FieldElement::k_modulus() as i128) as usize);
let numer_3: Polynomial = f.pow(2) * FieldElement::new((-1 + FieldElement::k_modulus() as i128) as usize);
let numer2: Polynomial = numer_1 + numer_2 + numer_3;
println!("Numerator at g^1020 is {:?}", numer2.clone()(g.pow(1020)));
println!("Numerator at g^1021 is {:?}", numer2(g.pow(1021usize)));
let denom2 = (x().pow(1024usize) - 1) / ((x() - g.pow(1021)) * (x() - g.pow(1022)) * (x() - g.pow(1023)));

let p2: Polynomial = numer2 / denom2;

Numerator at g^1020 is FieldElement(0)
Numerator at g^1021 is FieldElement(230576507)

Run test:

let p2_degree = p2.degree();
assert_eq!(p2.degree(), 1023, "The degree of the third constraint is {p2_degree} when it should be 1023.");
assert_eq!(p2(31415), 2090051528);
println!("Success!");

Success!

Run the following cell to observe the degrees of the constraint polynomials p0, p1 and p2, all less than . This will be important in the next part.

println!("deg p0 = {}", p0.degree());
println!("deg p1 = {}", p1.degree());
println!("deg p2 = {}", p2.degree());

deg p0 = 1021
deg p1 = 1021
deg p2 = 1023

Step 4 - Composition Polynomial

Recall that we’re translating a problem of checking the validity of three polynomial constraints to checking that each of the rational functions are polynomials.

Our protocol uses an algorithm called FRI to do so, which will be discussed in the next part. In order for the proof to be succinct (short), we prefer to work with just one rational function instead of three. For that, we take a random linear combination of called the compostion polynomial (CP for short):

where are random field elements obtained from the verifier, or in our case - from the channel.

Proving that (the rational function) is a polynomial guarantees, with high probability, that each of , , are themselves polynomials.

In the next part, you will generate a proof for an equivalent fact. But first, let’s create CP using Channel.receive_random_field_element to obtain :

// Note that alpha0, alpha1, alpha2 have to be drawn from the channel in this order.
fn get_CP(p1: Polynomial, p2: Polynomial, p3: Polynomial, channel: Channel) -> Polynomial {
    todo!();
}

Solution:

fn get_CP(p0: Polynomial, p1: Polynomial, p2: Polynomial, channel: &mut Channel) -> Polynomial {
    let alpha0 = channel.receive_random_field_element();
    let alpha1 = channel.receive_random_field_element();
    let alpha2 = channel.receive_random_field_element();
    (p0 * alpha0) + (p1 * alpha1) + (p2 * alpha2)
}

Run test:

let mut test_channel: Channel = Channel::new();
let cp_test = get_CP(p0, p1, p2, &mut test_channel);
let cp_test_degree = cp_test.degree();
assert_eq!(cp_test.degree(), 1023, "The degree of cp is {cp_test_degree} when it should be 1023.");
let expected = cp_test(2439804);
assert_eq!(cp_test(2439804), 838767343, "cp(2439804) = {expected:?}, when it should be 838767343");
println!("Success!");

Success!

Commit on the Composition Polynomial

Lastly, we evaluate over the evaluation domain (eval_domain), build a Merkle tree on top of that and send its root over the channel. This is similar to committing on the LDE trace, as we did at the end of part 1.

// Fix this. CP_eval is the evaluation of CP on all the points in domain. For a hint - look at "Evaluate on a Coset" on part 1.
fn cp_eval(p0: Polynomial, p1: Polynomial, p2: Polynomial, domain: Vec<FieldElement>, channel: &mut Channel) {
    let cp = get_CP(p0, p1, p2, channel);
    todo!();
}

Solution:

fn cp_eval(p0: Polynomial, p1: Polynomial, p2: Polynomial, domain: Vec<FieldElement>, channel: &mut Channel) -> Vec<FieldElement> {
    let cp = get_CP(p0, p1, p2, channel);
    domain.into_iter().map(|d| cp(d)).collect()
}

Construct a Merkle Tree over the evaluation and send its root over the channel.

let channel = Channel::new();
let cp_merkle = MerkleTree::new(todo!()); // Fix this line
channel.send(cp_merkle.root);

Solution:

use stark101_rs::merkle_tree::MerkleTree;
let mut channel = Channel::new();
let cp_merkle: MerkleTree = MerkleTree::new(cp_eval(p0, p1, p2, eval_domain, &mut channel));
channel.send(cp_merkle.root());

Test your code:

assert_eq!(cp_merkle.root(), "26db4de93f69af9591eac0bf224a26f5ffd99d07a325b82ee34381069a205a53", "Merkle tree root is wrong.");
println!("Success!");

Success!