Skip to content

Latest commit

 

History

History
130 lines (83 loc) · 3.93 KB

README.md

File metadata and controls

130 lines (83 loc) · 3.93 KB

stwo-brainfuck

stwo-brainfuck is a ZK-VM for the Brainfuck language1, based on Stwo2.

CLI - Installation

Here are the steps to get the Brainfuck ZK-VM up and running.

You can either download the binaries from the releases, or build them from source.

Build from Source

  1. Clone the repository
git clone git@github.com:kkrt-labs/stwo-brainfuck.git
  1. Build the brainfuck_prover

The brainfuck_prover has a feature flag which enables the CPU parallelization feature of Stwo.

No feature flags:

cargo build --package brainfuck_prover --release

Parallel feature flag:

cargo build --package brainfuck_prover --features parallel --release

CLI - Usage

The brainfuck_prover CLI has two subcommands:

  • prove, which generates a CSTARK proof from a given Brainfuck program file or code string.
  • verify, which verify a CSTARK proof from a given Brainfuck proof file.

For more information, try brainfuck_prover --help, brainfuck_prover prove --help and brainfuck_prover verify --help.

Example usage

Consider this Brainfuck program which, given an ASCII character from Stdin, outputs the following two characters in the ASCII table:

++>,<[>+.<-]

Prove

To generate a proof of this program, you can provide the Brainfuck program as a string, with the --code argument, or store it in a file my_program.bf and provide the path to it with the --file argument.

Here, the proof will be serialized to a JSON file my_program_proof.json. You can also print the proof to stdout with the --print flag.

  1. Proof from a Brainfuck program given in the command
brainfuck_prover prove --code "++>,<[>+.<-]" --output my_program_proof.json

Or if you built from source,

./target/release/brainfuck_prover prove --code "++>,<[>+.<-]" --output my_program_proof.json
  1. Proof from program file
brainfuck_prover prove --file my_program.bf --output my_program_proof.json

Or if you built from source,

./target/release/brainfuck_prover prove --file my_program.bf --output my_program_proof.json

Verify

To verify a proof, the proof must be stored in a JSON file (--output flag from the prove subcommand).

brainfuck_prover verify my_program_proof.json

Project Objectives

  • Capacity of generating and verifying a proof for arbitrary Brainfuck programs.
  • Understanding of using Stwo for building ZK-VMs
  • Understanding of modern AIR (RAP) design for (C)STARK-based systems.

Design choices

Brainfuck VM

The Brainfuck language has a very loose specification, though, a general specification has been established as a minimal base. We try to follow these guidelines.

  • The memory cells take values in the Mersenne31 (M31) field: $[0..2^{31} - 1)$
  • Memory is fixed at 30,000 cells by default, but is configurable.
  • Memory wraps on overflow/underflow.
    • It can be used for memory value mv and memory pointer mp, but it will usually panic for mp as the memory size will be much smaller than $2^{31} - 1$.
  • Inputs are line-buffered (ends with the linefeed ASCII character 10).
  • CLI uses Stdin and Stdout for IO.
  • For library use, input can be simulated by any reader (e.g. Cursor) and output with any writer (e.g. a custom writer).

Acknowledgements

The constraints used here rely on work made by Alan Szepieniec3 and sibling article from Neptune Cash4. The Brainfuck compiler and interpreter have been adapted from rkdud0075

Footnotes

  1. Brainfuck Language ↩

  2. Stwo repository ↩

  3. BrainSTARK - Alan Szepieniec ↩

  4. BrainSTARK - Neptune Cash ↩

  5. rkdud007 brainfuck-zkvm repo ↩