# Stark Engine Overview
In the previous blogs, we have discussed the structure of the STARK engine in detail. Now, we will summarize all the information we have covered so far to create the workflow of a ZKVM that proves the computational integrity of the Brainfuck ISA. The Brainfuck ISA is conducive to proving and verifying, i.e., it can be easily *arithmetized*- described as the zero set of a small number of low-degree univariate/multivariate polynomials.

A STARK engine consists of three parts: a virtual machine, a prover, and a verifier.
Our virtual machine has two main operations:
* `run` takes the program and the input, executes the program, and returns the output.
* `simulate` does the same but additionally outputs the execution trace.

The tuple **(input, program, output)** represents the **computational integrity claim**, which is received as input by both the prover and verifier. The **execution trace** serves as a secret additional input for the prover.

## Prover Workflow

The prover follows the steps below. The verifier's corresponding operations align with this workflow. Although presented in an interactive manner, the protocol can be made non-interactive using the **Fiat-Shamir transform**.

1. **Populate Tables**: Use data from the execution trace to populate the base columns of the tables. Pad the tables to match the maximum next power of two (instruction table's height).
2. **Base Codewords**: Interpolate the base columns and evaluate the resulting polynomials on the expanded domain to obtain the **base codewords**.
3. **Merkle Tree for Base Codewords**: Zip the base codewords and compute their Merkle tree. Send the Merkle root to the verifier and receive random scalars called challenges.
4. **Table Extensions**: Compute the table extensions using the received challenges.
5. **Extension Codewords**: Interpolate the extension columns and evaluate the resulting polynomials on the expanded domain to obtain the **extension codewords**.
6. **Quotient Polynomials**: Form **AIR polynomials** using AIR constraints for all tables, and divide out by their corresponding zerofiers, to get **quotient polynomials**.
7. **Merkle Tree for Extension Codewords**: Zip the extension codewords and compute their Merkle tree. Send the Merkle root to the verifier and receive random scalars or weights.
8. **Nonlinear Combination**: Compute the combination polynomials using the weights received. Evaluate this polynomial on the evaluation domain to get the **combination codeword.**
9. **Nonlinear Combination Merkle Tree**: Compute the Merkle tree of the **combination codeword**. Send the root of this tree to the verifier and receive **t indices** where the combination is to be checked.
10. **FRI Protocol**: Run FRI Protocol with the combination codeword. This establishes that the Merkle root of the nonlinear combination codeword decommits to a codeword corresponding to a low degree polynomial.


You have now learnt how to build a zkVM from scratch :). Happy building!

Github repository of Ooty VM: [link](https://github.com/manojkgorle/brainfuckvm)

---