Ooty VM: Proving computational integrity of BrainFuck ISA

We have implemented all the cryptography libraries needed for this VM from scratch. Before going through this VM, you must have a strong understanding of the STARK protocol. To help with that, we recommend going through the stark101 by Starkware and reviewing the stark101 implementation in Rust.

We have made some modifications to the Brainstark, such as using univariate polynomials and applying the FRI protocol on the combination of quotient polynomials. Additionally, we have implemented optimizations to reduce the proving time, such as parallel computing for Lagrange polynomials, among other improvements.

⚠️ Warning: This code is unaudited and made available only for educational purposes. Not recommended for production use. Check license for usage.

Structure

• main.rs - execute, prove and verify hello world brain fuck program.
• vm - tools to compile, run and simulate the brain fuck program.
• stark - prover and verifier functions along with helpers.
• tables - Processor, Instruction, IO and Memory Tables.
• fri- Minimal implementation of FRI protocol.
• field - Modular operations.
• polynomial - Univariate polynomial and modulo polynomial primitives.
• merkle tree - A wrapped implementation of merkle tree.
• channel - Simulates prover and verifer interactions as a fiat shamir oracle.

Resources:

• Brainstark part 1
• Brainstark part 2
• Brainstark part 3
• Brainfuck ISA
• Writing your own VM
• How to code fri from scratch
• A summary on the fri low degree testing