mod.rs

#![allow(unused_variables)]
use std::f64;
use std::io::Read;

use instruction::Indices;
use instruction::InstructionTable;
use io::IOTable;
use memory::MemoryTable;
use processor::ProcessorTable;

use crate::channel;
use crate::channel::*;
use crate::fields::Field;
use crate::fields::FieldElement;
use crate::fri::*;
use crate::merkle::*;
use crate::tables::*;
use crate::univariate_polynomial::*;
use chrono::Local;
use log::{info, Level, LevelFilter, Metadata, Record};
use rayon::prelude::*;

pub struct Stark<'a> {
    pub running_time: i32,
    pub memory_length: usize,
    pub program: &'a [FieldElement],
    pub input_symbols: String,
    pub output_symbols: String,
    expansion_factor: u32,
    security_level: u32,
    num_collinearity_checks: u32,
}

pub enum ChallengeIndices {
    A,
    B,
    C,
    D,
    E,
    F,
    Alpha,
    Beta,
    Delta,
    Gamma,
    Eta,
}

// prove:
//give matrices created by vm in this order-> processor, memory, instruction, input, output
//1. create table from the func given in their respective module.

pub fn prove(
    matrices: &[&[Vec<FieldElement>]],
    inputs: String,
    field: Field,
    offset: FieldElement,
    expansion_f: usize,
    num_queries: usize,
) -> (
    u128,
    Vec<Vec<u8>>,
    Vec<FieldElement>,
    Vec<FieldElement>,
    Vec<FieldElement>,
    Vec<FieldElement>,
    Vec<FieldElement>,
    Vec<Vec<FieldElement>>,
) {
    let start_time = Local::now();
    let generator = field.generator().pow((1 << 32) - 1);
    let order = 1 << 32;
    let mut t = Local::now();
    let mut processor_table = ProcessorTable::new(
        field,
        matrices[0].len() as u128,
        roundup_npow2(matrices[2].len() as u128),
        generator,
        order,
        matrices[0],
    );
    let mut memory_table = MemoryTable::new(
        field,
        matrices[1].len() as u128,
        roundup_npow2(matrices[2].len() as u128),
        generator,
        order,
        matrices[1],
    );
    let mut instruction_table = InstructionTable::new(
        field,
        matrices[2].len() as u128,
        generator,
        order,
        matrices[2],
    );
    let mut input_table = IOTable::new(
        field,
        matrices[3].len() as u128,
        generator,
        order,
        matrices[3],
    );
    let mut output_table = IOTable::new(
        field,
        matrices[4].len() as u128,
        generator,
        order,
        matrices[4],
    );
    log::info!(
        "Generating tables took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();
    //2.pad all tables
    processor_table.pad();
    memory_table.pad();
    instruction_table.pad();
    input_table.pad();
    output_table.pad();
    processor_table.table.generate_omicron_domain();
    memory_table.table.generate_omicron_domain();
    instruction_table.table.generate_omicron_domain();

    log::info!(
        "Padding all tables took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    //3.interpolate all tables
    t = Local::now();
    let processor_interpol_columns: Vec<Polynomial> = processor_table
        .table
        .clone()
        .interpolate_columns(vec![0, 1, 2, 3, 4, 5, 6]);
    log::info!(
        "interpolating processor table took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );

    t = Local::now();
    let memory_interpol_columns: Vec<Polynomial> = memory_table
        .table
        .clone()
        .interpolate_columns(vec![0, 1, 2]);

    log::info!(
        "Interpolating memory table took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();
    let instruction_interpol_columns: Vec<Polynomial> = instruction_table
        .table
        .clone()
        .interpolate_columns(vec![0, 1, 2]);
    log::info!(
        "Interpolating instruction table took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );

    t = Local::now();
    let initial_length = roundup_npow2(9 * (instruction_table.table.clone().height - 1));

    // all codewords are evaluated on this expanded domain that has length expanded_length
    let expanded_length = initial_length * (expansion_f as u128);

    let domain = FriDomain::new(
        offset,
        derive_omicron(generator, order, expanded_length),
        expanded_length,
    );

    log::info!(
        "Extending the domain took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();
    // basecodewords vector order:
    // processor: clk, ip, ci, ni, mp, mv, inv
    // memory: clk, mp, mv
    // instruction: ip, ci, ni
    // input and output tables are public, we dont commit to those, we only check their terminal extensions after extending
    let mut basecodewords: Vec<Vec<FieldElement>> = Vec::with_capacity(
        processor_interpol_columns.len()
            + memory_interpol_columns.len()
            + instruction_interpol_columns.len(),
    );

    // @todo make these functions rust native, by using iter.
    //4.Evaluating all tables on the extended domain
    for i in 0..processor_interpol_columns.clone().len() {
        basecodewords.push(domain.evaluate(processor_interpol_columns[i].clone()));
    }

    for i in 0..memory_interpol_columns.clone().len() {
        basecodewords.push(domain.evaluate(memory_interpol_columns[i].clone()));
    }

    for i in 0..instruction_interpol_columns.clone().len() {
        basecodewords.push(domain.evaluate(instruction_interpol_columns[i].clone()));
    }

    log::info!(
        "Evaluating on the extended domain took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();

    // 5.zipping all the base codewords (for each index in order) by taking their merkle root
    let mut basecodeword: Vec<FieldElement> = Vec::with_capacity(expanded_length as usize);

    for i in 0..expanded_length as usize {
        let mut x: Vec<FieldElement> = vec![];
        for j in 0..basecodewords.len() {
            x.push(basecodewords[j][i]);
        }
        let merkle = MerkleTree::new(&x);
        let root = FieldElement::from_bytes(
            merkle
                .inner
                .root()
                .as_ref()
                .map(|array| array.as_slice())
                .unwrap_or(&[]),
        );
        basecodeword.push(root);
    }
    log::info!(
        "Zipping all the codewords on the extended domain took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();

    //6.commitng the base codewords
    let mut channel = Channel::new();
    let merkle1 = MerkleTree::new(&basecodeword);
    //Sending merkle root to channel i.e. verifier
    // channel acts as verifier, simulates verifier, in proof generation of non-interactive proving setup. and vice versa for proof verification
    // to convert interactive proving to non interactive proving, fiat shamir heuristic is used.
    // with fiat shamir heuristic, the channel is deterministic for both prover and verifier.
    channel.send(merkle1.inner.root().unwrap().to_vec());
    log::info!(
        "Commiting the base codewords took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );

    let mut challenges_extension = vec![];
    //7.receiving the challenges from the channel i.e. verifier to compute extension columns
    for _ in 0..=10 {
        let x = channel.receive_random_field_element(field);
        challenges_extension.push(x);
    }

    //8.use extend column function on tables to extend the base columns to extension columns
    t = Local::now();
    let terminal_processor = processor_table.extend_columns(challenges_extension.clone());
    let terminal_memory = memory_table.extend_column_ppa(1, challenges_extension.clone());
    let terminal_instruction = instruction_table.extend_column(1, challenges_extension.clone());
    let terminal_input = input_table
        .extend_column_ea(0, challenges_extension[ChallengeIndices::Gamma as usize])
        .clone();
    let terminal_output = output_table
        .extend_column_ea(0, challenges_extension[ChallengeIndices::Delta as usize])
        .clone();
    log::info!(
        "Generating the extension column using the fiat-shamir challenges took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();

    //9. interpolate the extension columns
    let processor_interpol_columns_2 = processor_table
        .table
        .clone()
        .interpolate_columns(vec![7, 8, 9, 10]);
    let memory_interpol_columns_2 = memory_table.table.clone().interpolate_columns(vec![3]);
    let instruction_interpol_columns_2 = instruction_table
        .table
        .clone()
        .interpolate_columns(vec![3, 4]);

    let mut extension_codewords: Vec<Vec<FieldElement>> = Vec::with_capacity(
        processor_interpol_columns_2.len()
            + memory_interpol_columns_2.len()
            + instruction_interpol_columns_2.len(),
    );
    log::info!(
        "Interpolating the extension columns took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();

    // extensioncodewords vector order:
    // processor: ipa, mpa, iea, oea
    // memory: ppa
    // instruction: ppa, pea
    // input and output tables are public, we dont commit to those, we only check their terminal extensions after extending
    //10.Evaluating all extended columns on the extended domain
    for i in 0..processor_interpol_columns_2.clone().len() {
        extension_codewords.push(domain.evaluate(processor_interpol_columns_2[i].clone()));
    }

    for i in 0..memory_interpol_columns_2.clone().len() {
        extension_codewords.push(domain.evaluate(memory_interpol_columns_2[i].clone()));
    }

    for i in 0..instruction_interpol_columns_2.clone().len() {
        extension_codewords.push(domain.evaluate(instruction_interpol_columns_2[i].clone()));
    }

    log::info!(
        "Evaluating the extension columns on the extended domain took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();
    //11. zipping all the extension codewords
    let mut extension_codeword: Vec<FieldElement> = Vec::with_capacity(expanded_length as usize);
    for i in 0..expanded_length as usize {
        let mut x: Vec<FieldElement> = vec![];
        for j in 0..extension_codewords.len() {
            x.push(extension_codewords[j][i]);
        }
        let merkle = MerkleTree::new(&x);
        let root = FieldElement::from_bytes(
            merkle
                .inner
                .root()
                .as_ref()
                .map(|array| array.as_slice())
                .unwrap_or(&[]),
        );
        extension_codeword.push(root);
    }
    log::info!(
        "Zipping all the extension codewords took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();
    //12.commiting the extension codewords
    let merkle2 = MerkleTree::new(&extension_codeword);
    //Sending merkle root to channel i.e. verifier
    channel.send(merkle2.inner.root().unwrap().to_vec());

    log::info!(
        "Commiting the extension codewords took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();
    //13.receveing challenges from channel (verifier) for computing the combination polynomial
    let mut challenges_combination = vec![];
    let x = channel.receive_random_field_element(field);
    challenges_combination.push(x);

    challenges_combination.push(channel.receive_random_field_element(field));
    let eval = FieldElement::zero(field);

    log::info!(
        "receiving challenges for the combination polynomial took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();
    //14. generating all the AIRs for different tables
    let processor_air = processor_table.generate_air(
        challenges_extension.clone(),
        terminal_processor[0],
        terminal_processor[1],
        terminal_processor[2],
        terminal_processor[3],
        eval,
    );

    log::info!(
        "generating the processor AIR took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();

    let memory_air = memory_table.generate_air(challenges_extension.clone(), terminal_memory[0]);
    log::info!(
        "generating the memory AIR took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();

    let instruction_air = instruction_table.generate_air(
        challenges_extension.clone(),
        terminal_instruction[0],
        terminal_instruction[1],
    );
    log::info!(
        "generating the instruction AIR took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();
    //15. generating the zerofier for boundary,transition and terminal constraints for each table
    let processor_zerofiers = processor_table.generate_zerofier();
    log::info!(
        "generating the processor zerofiers took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();

    let memory_zerofiers = memory_table.generate_zerofier();
    log::info!(
        "generating the memory zerofiers took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();

    let instruction_zerofiers = instruction_table.generate_zerofier();
    log::info!(
        "generating the instruction zerofiers took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();

    //16.generating the quotient polynomial for each table
    let zero = FieldElement::zero(field);
    let processor_q = (0..processor_zerofiers.len())
        .into_par_iter()
        .map(|i| {
            let c = processor_air[i]
                .clone()
                .q_div(processor_zerofiers[i].clone());
            assert_eq!(c.1, Polynomial::constant(zero));
            c.0
        })
        .collect();

    let memory_q = (0..memory_zerofiers.len())
        .into_par_iter()
        .map(|i| {
            let c = memory_air[i].clone().q_div(memory_zerofiers[i].clone());
            assert_eq!(c.1, Polynomial::constant(zero), "Failed at memory_q: {}", i);
            c.0
        })
        .collect();

    let instruction_q = (0..instruction_zerofiers.len())
        .into_par_iter()
        .map(|i| {
            let c = instruction_air[i]
                .clone()
                .q_div(instruction_zerofiers[i].clone());
            assert_eq!(c.1, Polynomial::zero(field), "failed at {}", i);

            c.0
        })
        .collect();
    log::info!(
        "generating the quotient polynomial of all tables took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();

    // 17. generating the combination polynomial from quotient polynomials of diff tables
    // the maximum degree bound will be 9*height
    let degree_bound = roundup_npow2(9 * (instruction_table.table.height - 1)) - 1;

    //@todo optimize this
    let combination = combination_polynomial(
        processor_q,
        memory_q,
        instruction_q,
        challenges_combination,
        (degree_bound + 1) as usize,
        field,
    );
    log::info!(
        "generating the combination polynomial took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    //18. evaluating the combination polynomial on the extended domain
    t = Local::now();
    let combination_codeword = domain.evaluate(combination.clone());
    log::info!(
        "evaluating the combination polynomial took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();
    //19. commiting the combnation codewords
    let merkle_combination = MerkleTree::new(&combination_codeword);
    channel.send(merkle_combination.inner.root().unwrap().to_vec());
    log::info!(
        "commiting the combination codewords took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();
    // Now we have commited to the combination polynomial.
    // Composition polynomial will be a polynomial only if all the contraints are satisfied.
    // Using F.R.I, we will show composition polynomial is close to a polynomial of low degree.
    // A function is close to a polynomial if its distance to the polynomial is small.
    // distance of a function and polynomial is measured as, f:Domain->F, Distance(f, p) => for every d in Domain, f(d) != p(d)
    // How can we prove that a composition polynomial is close to polynomial of low degree?
    // Here comes F.R.I, Fast Reed solomon Interactive oracle proofs of proximity.
    // FRI is a folding scheme, similar to what we see in FFT for breaking down the polynomial into 2 polynomials of even degree(s).
    // Prover tries to convence the verifier that, the commitment of composition polynomial is close to a low degree polynomial.
    // F.R.I Protocol:
    // 1. Receive random element `beta` from verifier.
    // 2. Apply the FRI folding scheme or FRI operator to the composition polynomial.
    // 3. Commit to the new polynomial obtained after applying FRI operator.
    // 4. Send the new commitment to the verifier.
    // 5. Repeat step 1-4, until the polynomial degree is less than accepted degree in terms of security. in this case repeat till degree is 0.
    // 6. Prover sends the result to the verifier.

    // F.R.I Operator or folding scheme:
    // from proving: function is close to a polynomial of degree < D
    // to proving: new function is close to a new polynomial of degree < D/2, where new function has half the domain size of old polynomial.
    // Example: To prove: A function is close to a polynomial of a degree < 1024, with function domain size = 8192
    //          After applying the FRI operator we need to prove the new polynomial degree < 512 with new function domain size = 4096
    // split ot even and odd powers.
    // P_0(x) = g(x^2) + x h(x^2)
    // Get random element beta from verifier
    // P_1(y) = g(y) + beta * h(y)

    // For this example, repeat steps 1-4 till degree of polynomial < 1, when domain size is 8.

    // The new evaluation domain, will be half of the old evaluation domain.
    // and new evaluation domain is first half of the old evaluation domain squared.
    // eval domain: w, w.h, w.h2, .... w.h^8091
    // new eval domain: w^2, (w.h)^2, ... (w.h^4095)^2
    // square of the first half of the old eval domian, is equal to square of second half of old eval domain. This is a cyclic group property.

    //20.generate fri layers and commit to the fri layers.
    let (_fri_polys, fri_domains, fri_layers, fri_merkles) = fri_commit(
        combination.clone(),
        domain,
        combination_codeword,
        merkle_combination,
        &mut channel,
    );
    log::info!(
        "generating and commiting the Fri_layer took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    t = Local::now();

    // Proof or provers work contains generating commitments and decommiting them, to convence the verifier over the integrity of the computation.
    // i)  Commitment ✅
    // ii) Decommitment -> query phase
    // Decommitment involves verifier sending random elements from evaluation domain to prover. and prover responding with decommitments to the evaluations, which involve sending merkle paths along with evaluations.

    // with each successful query and valid decommitment, verifiers confidence in the proof increases.

    let no_of_queries = num_queries;
    decommit_fri(
        no_of_queries,
        expansion_f,
        (expanded_length - expansion_f as u128) as u64,
        vec![&basecodeword, &extension_codeword],
        vec![&merkle1, &merkle2],
        &fri_layers,
        &fri_merkles,
        &mut channel,
    );
    log::info!(
        "decommiting the Fri_layer took: {:?}ms",
        (Local::now() - t).num_milliseconds()
    );
    let mut fri_eval_domains = vec![];
    for i in 0..fri_domains.len() {
        fri_eval_domains.push(fri_domains[i].list());
    }

    let x = channel.compressed_proof.clone();
    log::info!(
        "proof generation complete, time taken: {}ms, proof size: {} bytes, compressed proof size: {} bytes",
        (Local::now() - start_time).num_milliseconds(),
        channel.proof_size(),
        channel.compressed_proof_size()
    );

    (
        degree_bound,
        x,
        terminal_processor,
        terminal_memory,
        terminal_instruction,
        terminal_input,
        terminal_output,
        fri_eval_domains,
    )
}

// prover sends to verifier -
//-> height (whose correctness is indirectly verified through fri and degree bound)
//-> base codewords merkle root, extension codewords merkle root
// ->for each query (index) of verifier, prover sends respective evaluation and merkle authentication path of evaluation

//panic for invalid proof

pub fn verify_proof(
    num_of_queries: usize,
    maximum_random_int: u64,
    blow_up_factor: usize,
    field: Field,
    fri_domains: &[Vec<FieldElement>],
    compressed_proof: &[Vec<u8>],
    terminal_processor: Vec<FieldElement>,
    terminal_instruction: Vec<FieldElement>,
    terminal_memory: Vec<FieldElement>,
    terminal_input: Vec<FieldElement>,
    terminal_output: Vec<FieldElement>,
    degree_bound: usize,
) {
    log::info!("verifying proof");
    let start = Local::now();
    let mut channel = Channel::new();
    //merkle root of the zipped base codewords
    let base_merkle_root = compressed_proof[0].clone();

    channel.send(base_merkle_root.clone());

    // get challenges for the extension columns
    let mut challenges_extension = vec![];

    for _ in 0..10 {
        let x = channel.receive_random_field_element(field);
        challenges_extension.push(x);
    }
    challenges_extension.push(channel.receive_random_field_element(field));
    // merkle root of the zipped exten codewords
    let exten_merkle_root = compressed_proof[1].clone();

    channel.send(exten_merkle_root.clone());

    // get challenges for the combination polynomial
    let mut challenges_combination = vec![];
    let x = channel.receive_random_field_element(field);
    challenges_combination.push(x);

    challenges_combination.push(channel.receive_random_field_element(field));

    let combination_merkle_root = compressed_proof[2].clone();

    channel.send(combination_merkle_root);

    //commit to fri
    // fri.layer.len = 1+ log(height)/log2

    let number = degree_bound + 1_usize;
    let log_base_2 = (number as f64).log2();
    let fri_layer_length: usize = (log_base_2 + 1_f64) as usize;
    let mut fri_merkle_roots: Vec<Vec<u8>> = Vec::with_capacity(fri_layer_length - 1_usize);
    let mut betas: Vec<FieldElement> = Vec::with_capacity(fri_layer_length - 1_usize);
    for i in 0..fri_layer_length - 1_usize {
        let beta = channel.receive_random_field_element(field);
        betas.push(beta);
        let fri_root = compressed_proof[3 + i].clone();
        channel.send(fri_root.clone());
        fri_merkle_roots.push(fri_root);
    }
    let last_layer_free_term = compressed_proof[2_usize + fri_layer_length].clone();
    // last root will be 3+fri_layer_length-1
    // last term of the constant polynomial

    channel.send(last_layer_free_term.clone());
    // base_idx will be the point where the end of the compressed_proof indices for thr fri-layer_root commitment after this we have added the element and there authentication path
    let mut base_idx = 3_usize + fri_layer_length;
    for i in 0..num_of_queries {
        let idx = channel.receive_random_int(0, maximum_random_int, true) as usize;
        // verify_queries
        verify_queries(
            base_idx + i,
            idx,
            blow_up_factor,
            field,
            &fri_merkle_roots,
            fri_domains,
            compressed_proof,
            &betas,
            &mut channel,
            terminal_processor.clone(),
            terminal_instruction.clone(),
            terminal_memory.clone(),
            terminal_input.clone(),
            terminal_output.clone(),
            degree_bound,
            fri_layer_length,
        );
        base_idx += 8 + (4 * (fri_layer_length - 1));
    }
    log::info!(
        "verification successful, time taken: {:?}µs",
        (Local::now() - start).num_microseconds().unwrap()
    );
}

/// verify queries on the zipped value of base codewords and the extension codeowrds and also the terminal values
pub fn verify_queries(
    base_idx: usize,
    idx: usize,
    blow_up_factor: usize,
    field: Field,
    fri_merkle_roots: &[Vec<u8>],
    fri_domains: &[Vec<FieldElement>],
    compressed_proof: &[Vec<u8>],
    betas: &[FieldElement],
    channel: &mut Channel,
    terminal_processor: Vec<FieldElement>,
    terminal_instruction: Vec<FieldElement>,
    terminal_memory: Vec<FieldElement>,
    terminal_input: Vec<FieldElement>,
    terminal_output: Vec<FieldElement>,
    degree_bound: usize,
    fri_layer_length: usize,
) {
    // length of the eval_domain
    let len = (degree_bound + 1_usize) * blow_up_factor;
    let base_merkle_root = compressed_proof[0].clone();

    let base_x = compressed_proof[base_idx].clone();
    channel.send(base_x.clone());

    let base_x_auth = compressed_proof[base_idx + 1].clone();
    channel.send(base_x_auth.clone());

    assert!(MerkleTree::validate(
        base_merkle_root.clone(),
        base_x_auth,
        idx,
        base_x,
        len
    ));

    let base_gx = compressed_proof[base_idx + 2].clone();
    channel.send(base_gx.clone());
    let base_gx_auth = compressed_proof[base_idx + 3].clone();
    channel.send(base_gx_auth.clone());
    assert!(MerkleTree::validate(
        base_merkle_root.clone(),
        base_gx_auth,
        idx + blow_up_factor,
        base_gx,
        len
    ));
    let exten_merkle_root = compressed_proof[1].clone();
    let exten_x = compressed_proof[base_idx + 4].clone();
    channel.send(exten_x.clone());

    let exten_x_auth = compressed_proof[base_idx + 5].clone();
    channel.send(exten_x_auth.clone());
    assert!(MerkleTree::validate(
        exten_merkle_root.clone(),
        exten_x_auth,
        idx,
        exten_x,
        len
    ));
    let exten_gx = compressed_proof[base_idx + 6].clone();
    channel.send(exten_gx.clone());
    let exten_gx_auth = compressed_proof[base_idx + 7].clone();
    channel.send(exten_gx_auth.clone());
    assert!(MerkleTree::validate(
        exten_merkle_root.clone(),
        exten_gx_auth,
        idx + blow_up_factor,
        exten_gx,
        len
    ));
    //for inter table arguments constraints
    //Tipa = Tppa
    assert_eq!(terminal_processor[0], terminal_instruction[0]);
    //Tmpa = Tppa
    assert_eq!(terminal_processor[1], terminal_memory[0]);
    //Tiea = Tea input
    if !terminal_input.is_empty() {
        assert_eq!(terminal_processor[2], terminal_input[0]);
    }
    //Toea = Tea output
    if !terminal_output.is_empty() {
        assert_eq!(terminal_processor[3], terminal_output[0]);
    }

    verify_fri_layers(
        base_idx + 8,
        idx,
        field,
        fri_merkle_roots,
        fri_domains,
        compressed_proof,
        betas,
        channel,
        len,
        fri_layer_length,
    );
}

/// verify the consistency of all the fri_layers with the given betas
pub fn verify_fri_layers(
    base_idx: usize,
    idx: usize,
    field: Field,
    fri_merkle_roots: &[Vec<u8>],
    fri_domains: &[Vec<FieldElement>],
    compressed_proof: &[Vec<u8>],
    betas: &[FieldElement],
    channel: &mut Channel,
    intial_length: usize,
    fri_layer_length: usize,
) {
    let mut lengths: Vec<usize> = vec![0_usize; fri_layer_length - 1_usize];
    for i in 0..fri_layer_length - 1_usize {
        lengths[i] = intial_length / 2_usize.pow(i as u32);
    }
    for i in 0..fri_layer_length - 1_usize {
        let length = lengths[i];
        let elem_idx = idx % length;
        let elem = compressed_proof[base_idx + 4 * i].clone();
        channel.send(elem.clone());
        let elem_proof = compressed_proof[base_idx + 4 * i + 1].clone();
        channel.send(elem_proof.clone());
        let merkle_root = if i == 0 {
            compressed_proof[2].clone()
        } else {
            fri_merkle_roots[i - 1].clone()
        };
        if i != 0 {
            // checking fri polynomials consistency.
            let prev_elem =
                FieldElement::from_bytes(&compressed_proof[base_idx + 4 * (i - 1)].clone());
            let prev_sibling =
                FieldElement::from_bytes(&compressed_proof[base_idx + 4 * (i - 1) + 2].clone());
            let two = FieldElement(2, field);
            let computed_elem = (prev_elem + prev_sibling) / two
                + (betas[i - 1] * (prev_elem - prev_sibling)
                    / (two * fri_domains[i - 1][idx % lengths[i - 1]]));
            assert!(computed_elem.0 == FieldElement::from_bytes(&elem).0);
        }
        assert!(MerkleTree::validate(
            merkle_root.clone(),
            elem_proof,
            elem_idx,
            elem.clone(),
            length,
        ));
        let sibling_idx = (idx + length / 2) % length;
        let sibling = compressed_proof[base_idx + 4 * i + 2].clone();
        channel.send(sibling.clone());
        let sibling_proof = compressed_proof[base_idx + 4 * i + 3].clone();
        channel.send(sibling_proof.clone());

        assert!(MerkleTree::validate(
            merkle_root,
            sibling_proof,
            sibling_idx,
            sibling.clone(),
            length,
        ));
    }
    let last_elem = compressed_proof[base_idx + 4 * (fri_layer_length - 1)].clone();
    channel.send(last_elem);
}

#[cfg(test)]
mod stark_test {
    use crate::fields::{Field, FieldElement};
    use crate::fri::FriDomain;
    use crate::stark::instruction::InstructionTable;
    use crate::stark::{derive_omicron, prove, roundup_npow2, verify_proof};
    use crate::vm::VirtualMachine;
    #[test]
    fn test_proving() {
        let field = Field(18446744069414584321);
        let vm = VirtualMachine::new(field);
        //let code = "++>+++++[<+>-]++++++++[<++++++>-]<.".to_string();
        //let code = ",++>+-[+--]++.".to_string();
        let code = "++++++>+>+<<--[>>[>+<<+>-]<[>+<-]>>[<<+>>-]<<<-]>>.".to_string();
        //let code = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.".to_string();
        let program = vm.compile(code);

        let (running_time, input_symbols, _output_symbols) = vm.run(&program, "4".to_string());

        let (processor_matrix, memory_matrix, instruction_matrix, input_matrix, output_matrix) =
            vm.simulate(&program, "4".to_string());
        assert_eq!(running_time as usize, processor_matrix.len());

        let offset = FieldElement::one(field);
        let expansion_f = 1;
        let num_queries = 1;

        let v: &[&[Vec<FieldElement>]] = &[
            &processor_matrix,
            &memory_matrix,
            &instruction_matrix,
            &input_matrix,
            &output_matrix,
        ];

        let (degree_bound, compressed_proof, tp, tm, tins, ti, to, fri_d) = prove(
            v.into(),
            input_symbols,
            field,
            offset,
            expansion_f,
            num_queries,
        );

        let maximum_random_int =
            ((degree_bound + 1) * expansion_f as u128 - expansion_f as u128) as u64;
        verify_proof(
            num_queries as usize,
            maximum_random_int,
            expansion_f as usize,
            field,
            &fri_d,
            &compressed_proof,
            tp,
            tins,
            tm,
            ti,
            to,
            degree_bound as usize,
        );
    }

    #[test]
    fn helper_tests() {
        let x = FieldElement::new(318, Field::new(421));
        println!("{}", x);
        let y = x.to_bytes();
        for i in 0..y.len() {
            print!("{}, ", y[i]);
        }
    }
}