more docs and tests pls

erhant · Jul 20, 2023 · 2373184 · 2373184
1 parent ed2c344
commit 2373184
Show file tree

Hide file tree

Showing 13 changed files with 130 additions and 115 deletions.
diff --git a/.vscode/settings.json b/.vscode/settings.json
@@ -4,6 +4,7 @@
   },
   // https://raw.githubusercontent.com/PKief/vscode-material-icon-theme/main/images/folderIcons.png
   "material-icon-theme.folders.associations": {
-    "circuits": "App"
+    "circuits": "App",
+    "inputs": "Json"
   }
 }
diff --git a/README.md b/README.md
@@ -19,7 +19,7 @@ Any other symbol is ignored, and may effectively be used as comments.
 
 ## Virtual Machine
 
-We have written a Brainfuck compiler & runner in Go, which you can find under the [vm](./vm/) folder. Assuming you have Go installed, you can build the binary simply via:
+We have written a smol Brainfuck VM in Go, which you can find under the [vm](./vm/) folder. Assuming you have Go installed, you can build the binary simply via:
 
 ```sh
 yarn vm:build
@@ -29,21 +29,20 @@ Afterwards, you can run the binary with:
 
 ```sh
 yarn vm:run
-  -ticks int
-    # maximum number of ticks (default 65536)
-  -code string
-    # brainfuck code (default ",+++++[-.]")
-  -memory int
-    # memory size (default 128)
-  -num
-    # use numbers for input & output instead of characters
-  -path string
-    # path to file with brainfuck code (overwrites -code)
-  -verbose
-    # print compiled code
+  -code   string   # brainfuck code (default ",+++++[-.]")
+  -export string   # path to export program information
+  -path   string   # path to import brainfuck code
+  -memory uint     # memory size (default 128)
+  -opsize uint     # operations size
+  -ticks  uint     # maximum number of ticks (default 2048)
+  -num             # use numbers for input & output instead of runes
 ```
 
-You may find a few example Brainfuck codes in [here](./vm/sample). To run them, pass their paths via the `-path` option. By default, the VM will run `,+++++[-.]` which takes an input, increments it 5 times and then starts decrementing it, printing the value each time.
+You may find a few example Brainfuck codes in [here](./vm/sample). To run them, pass their paths via the `-path` option. By default, the VM will run `,+++++[-.]` which takes an input, increments it 5 times and then starts decrementing it, printing the value each time. Note that this implementation does not allow for underflows, neither for the program counter or memory pointer.
+
+### From Code to Integers
+
+...
 
 ## Proving Execution
 

diff --git a/circuits/brainfuck.circom b/circuits/brainfuck.circom
@@ -28,45 +28,42 @@ include "./vm.circom";
 // Parameters:
 // - `TICKS`: number of ticks to run
 // - `MEMSIZE`: maximum memory size
-// - `OPSIZE`: number of operations
-// - `INSIZE`: number of inputs
-// - `OUTSIZE`: number of outputs
+// - `OPSIZE`: maximum number of operations
+// - `INSIZE`: maximum number of inputs
+// - `OUTSIZE`: maximum number of outputs
 //
 // Inputs:
 // - `ops`: compiled code, as an array of integers where 0 is no-op
-// - `inputs`: inputs in the order they appear
-// - `outputs`: outputs in the order they appear
+// - `inputs`: inputs in the order they appear, append zeros for no input
+// - `outputs`: outputs in the order they appear, append zeros for no output
 //
 template Brainfuck(TICKS, MEMSIZE, OPSIZE, INSIZE, OUTSIZE) {
   signal input ops[OPSIZE];
   signal input inputs[INSIZE];
   signal input outputs[OUTSIZE];
 
+  signal pgm_ctrs[TICKS];
   signal mem_ptrs[TICKS];
-  mem_ptrs[0] <== 0;
-
   signal input_ptrs[TICKS];
-  input_ptrs[0] <== 0;
-
   signal output_ptrs[TICKS];
-  output_ptrs[0] <== 0;
-
   signal mems[TICKS][MEMSIZE];
+
+  pgm_ctrs[0] <== 7; // skip prepended zeros
+  mem_ptrs[0] <== 0;
+  input_ptrs[0] <== 0;
+  output_ptrs[0] <== 0;
+  // entire memory is zeros at first
   for (var i = 0; i < MEMSIZE; i++) {
     mems[0][i] <== 0;
   }
-
-  signal pgm_ctrs[TICKS];
-  pgm_ctrs[0] <== 7; // skips prepended zeros
+  // ops must be zero-padded
   for (var i = 0; i < 7; i++) {
     ops[i] === 0;
   }
+  // last possible op must be no-op
+  ops[OPSIZE - 1] === 0;
 
-  // at worst, the last op must be a NO_OP
-  // effectively halting the program until we run out of ticks
-  ops[OPSIZE-1] === 0;
-
-  component vm[TICKS];
+  component vm[TICKS - 1];
   for (var tick = 0; tick < TICKS - 1; tick++) {
     vm[tick] = VM(MEMSIZE, OPSIZE);
 

diff --git a/circuits/utils.circom b/circuits/utils.circom
@@ -1,6 +1,7 @@
 pragma circom 2.1.0;
 
 include "circomlib/circuits/comparators.circom";
+include "./functions/bits.circom";
 
 // If-else branching.
 //

diff --git a/circuits/vm.circom b/circuits/vm.circom
@@ -1,16 +1,15 @@
 pragma circom 2.1.0;
 
 include "./utils.circom";
-include "./functions/bits.circom";
 
 template VM(MEMSIZE, OPSIZE) {
-  var OP_NOOP    = 0;
-  var OP_INC_PTR = 1;
-  var OP_DEC_PTR = 2;
-  var OP_INC_MEM = 3;
-  var OP_DEC_MEM = 4;
-  var OP_INPUT   = 5;
-  var OP_OUTPUT  = 6;
+  var OP_NOOP    = 0; //    no operation
+  var OP_INC_PTR = 1; // >  move pointer right
+  var OP_DEC_PTR = 2; // <  move pointer left
+  var OP_INC_MEM = 3; // +  increment pointed memory
+  var OP_DEC_MEM = 4; // -  decrement pointed memory
+  var OP_INPUT   = 5; // ,  input value to pointed memory
+  var OP_OUTPUT  = 6; // .  output value from pointed memory
 
   signal input op;           // current operation
   signal input in;           // input at this tick
@@ -35,8 +34,7 @@ template VM(MEMSIZE, OPSIZE) {
   signal is_OP_INPUT   <== IsEqual()([OP_INPUT,   op]);
   signal is_OP_OUTPUT  <== IsEqual()([OP_OUTPUT,  op]);
 
-  // looping flag (when no operation is matched)
-  // we expect this sum to result in 1 or 0 due to distinct IsEquals
+  // we expect this sum to result in 1 or 0 due to distinct IsEquals above
   var is_OP = Sum(7)([
     is_OP_NOOP,
     is_OP_INC_PTR,
@@ -46,31 +44,35 @@ template VM(MEMSIZE, OPSIZE) {
     is_OP_INPUT,
     is_OP_OUTPUT
   ]);
+
+  // if no OP is matched, we must be looping
   signal is_LOOP <== 1 - is_OP;
 
-  // currently pointed value
-  signal val <== ArrayRead(MEMSIZE)(mem, mem_ptr); // pointed value: mem[mem_ptr]
-  signal val_is0 <== IsZero()(val);                // is pointed value zero? (used by loops)
+  // currently pointed value `mem[mem_ptr]` is referred to as `val`
+  signal val <== ArrayRead(MEMSIZE)(mem, mem_ptr);
+  signal val_is0 <== IsZero()(val);
 
+  // determine jump destination; since program counter is incremented
+  // we can jump by adding (destination - 1 - pgm_ctr) to the default value
+  // if not, the offset is kept to be 0
   signal is_pgm_ctr_lt_op <== LessThan(numBits(OPSIZE)+1)([pgm_ctr, op]);
-
   signal is_LOOP_BEGIN    <== is_LOOP * is_pgm_ctr_lt_op;
   signal is_LOOP_END      <== is_LOOP * (1 - is_pgm_ctr_lt_op);
   signal is_LOOP_JUMP     <== Sum(2)([is_LOOP_BEGIN * val_is0, is_LOOP_END * (1 - val_is0)]);
-
-  signal jmp_offset       <== is_LOOP_JUMP * (op - 1);
+  signal jmp_offset       <== is_LOOP_JUMP * (op - 1 - pgm_ctr);
 
   // program counter is incremented by default
   // if there is a loop, we add `jump_target - 1` to cancel incremention
   // and set the counter to target
   // if no-op, we cancel the incremention to cause program to halt
   next_pgm_ctr <== pgm_ctr + 1 + jmp_offset - is_OP_NOOP;
 
-  // memory pointer is incremented or decremented w.r.t op
-  // otherwise, is equal to its current value
+  // memory pointer stays the same by default
+  // otherwise it is only incremented or decremented
   next_mem_ptr <== mem_ptr + is_OP_INC_PTR - is_OP_DEC_PTR;
 
-  // input & output pointers are incremented w.r.t their ops
+  // input and output pointers stay the same by default
+  // if there is an input or output, the respective pointer is incremented
   next_input_ptr <== input_ptr + is_OP_INPUT;
   next_output_ptr <== output_ptr + is_OP_OUTPUT;
 
@@ -84,4 +86,7 @@ template VM(MEMSIZE, OPSIZE) {
   // output is only set during its respective op
   var expectedOut = IfElse()(is_OP_OUTPUT, val, out);
   out === expectedOut;
+
+  // in case of emergency, break glass
+  // log("op:", op, "\tval", val, "\tp:", mem_ptr, "\ti:", pgm_ctr);
 }
diff --git a/tests/brainfuck.test.ts b/tests/brainfuck.test.ts
@@ -1,42 +1,29 @@
-import { Circomkit, WitnessTester } from "circomkit";
-import { CircuitParameters, ProgramExecution } from "./types";
+import { Circomkit, type WitnessTester } from "circomkit";
 import { prepareProgramForCircuit } from "./utils";
+import { helloworld } from "./inputs";
 
-const circomkit = new Circomkit();
+const circomkit = new Circomkit({
+  verbose: false,
+});
 
-const program: ProgramExecution = {
-  ticks: 47,
-  memsize: 0,
-  opsize: 18,
-  insize: 1,
-  outsize: 10,
-  ops: [0, 0, 0, 0, 0, 0, 0, 5, 3, 3, 3, 3, 3, 16, 4, 6, 13, 0],
-  inputs: [5],
-  outputs: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0],
-};
-const params: CircuitParameters = {
-  insize: 2,
-  outsize: 15,
-  opsize: 20,
-  memsize: 10,
-  ticks: 80,
-};
-describe("zkbrainfuck", () => {
-  let circuit: WitnessTester<["ops", "inputs", "outputs"]>;
-  const INPUT = prepareProgramForCircuit(program, params);
+[helloworld].map(({ program, params, name }) =>
+  describe(`zkBrainfuck (${name})`, () => {
+    let circuit: WitnessTester<["ops", "inputs", "outputs"]>;
+    const INPUT = prepareProgramForCircuit(program, params);
 
-  before(async () => {
-    circuit = await circomkit.WitnessTester("zkbrainfuck", {
-      file: "brainfuck",
-      template: "Brainfuck",
-      params: [params.ticks, params.memsize, params.opsize, params.insize, params.outsize],
+    before(async () => {
+      console.time("compiled in");
+      circuit = await circomkit.WitnessTester(name, {
+        file: "brainfuck",
+        template: "Brainfuck",
+        params: [params.ticks, params.memsize, params.opsize, params.insize, params.outsize],
+      });
+      console.timeEnd("compiled in");
+      console.log("constraints:", await circuit.getConstraintCount());
     });
 
-    console.log("#constraints:", await circuit.getConstraintCount());
-  });
-
-  it("should execute circuit", async () => {
-    console.log("executing...");
-    await circuit.expectPass(INPUT);
-  });
-});
+    it("should execute circuit", async () => {
+      await circuit.expectPass(INPUT);
+    });
+  })
+);
diff --git a/tests/inputs/helloworld.ts b/tests/inputs/helloworld.ts
@@ -0,0 +1,28 @@
+import type { TestCase } from "../types";
+
+export const helloworld: TestCase = {
+  program: {
+    ticks: 972,
+    memsize: 6,
+    opsize: 138,
+    insize: 0,
+    outsize: 13,
+    ops: [
+      0, 0, 0, 0, 0, 0, 0, 30, 5, 6, 12, 6, 10, 5, 6, 6, 5, 5, 5, 3, 5, 4, 5, 2, 1, 5, 27, 26, 6, 6, 7, 3, 3, 3, 3, 3,
+      3, 3, 3, 79, 1, 3, 3, 3, 3, 64, 1, 3, 3, 1, 3, 3, 3, 1, 3, 3, 3, 1, 3, 2, 2, 2, 2, 4, 45, 1, 3, 1, 3, 1, 4, 1, 1,
+      3, 76, 2, 74, 2, 4, 39, 1, 1, 6, 1, 4, 4, 4, 6, 3, 3, 3, 3, 3, 3, 3, 6, 6, 3, 3, 3, 6, 1, 1, 6, 2, 4, 6, 2, 6, 3,
+      3, 3, 6, 4, 4, 4, 4, 4, 4, 6, 4, 4, 4, 4, 4, 4, 4, 4, 6, 1, 1, 3, 6, 1, 3, 3, 6, 0,
+    ],
+    inputs: [],
+    outputs: [72, 101, 108, 108, 111, 32, 87, 111, 114, 108, 100, 33, 10],
+  },
+  params: {
+    insize: 0,
+    outsize: 15,
+    opsize: 140,
+    memsize: 8,
+    ticks: 1000,
+  },
+  name: "hello-world",
+  num: false,
+};
diff --git a/tests/inputs/index.ts b/tests/inputs/index.ts
@@ -0,0 +1 @@
+export { helloworld } from "./helloworld";
diff --git a/tests/types/index.ts b/tests/types/index.ts
@@ -32,3 +32,12 @@ export type CircuitParameters = {
   insize: number;
   outsize: number;
 };
+
+/** A test case */
+export type TestCase = {
+  program: ProgramExecution;
+  params: CircuitParameters;
+  name: string;
+  /** treat the memory as integers (true) or ASCII (false)? */
+  num: boolean;
+};
diff --git a/tests/utils/index.ts b/tests/utils/index.ts
@@ -5,7 +5,7 @@ export function prepareProgramForCircuit(program: ProgramExecution, circuit: Cir
   if (program.memsize > circuit.memsize) throw new Error("Program memory exceed circuit memory.");
   if (program.insize > circuit.insize) throw new Error("Program inputs exceed circuit inputs.");
   if (program.outsize > circuit.outsize) throw new Error("Program outputs exceed circuit outputs.");
-  if (program.opsize > circuit.opsize) throw new Error("Program operaitons exceed circuit operations.");
+  if (program.opsize > circuit.opsize) throw new Error("Program operations exceed circuit operations.");
 
   return {
     ops: program.ops.concat(Array.from({ length: circuit.opsize - program.opsize }, () => 0)),

diff --git a/vm/cmd/main.go b/vm/cmd/main.go
@@ -16,13 +16,12 @@ func main() {
 	path := flag.String("path", "", "path to file with brainfuck code")
 	export := flag.String("export", "", "path to export program information")
 	isNumFmt := flag.Bool("num", false, "use numbers for input & output instead of runes")
-	verbose := flag.Bool("verbose", false, "print compiled code")
 	maxTicks := flag.Uint("ticks", 1<<11, "maximum number of ticks")
 	memorySize := flag.Uint("memory", 128, "memory size")
 	opsize := flag.Uint("opsize", 0, "operations size")
 	flag.Parse()
 
-	// if export is given, we need to record IOTrace
+	// if export is given, we need to record program execution
 	// and export it to a JSON file
 	record := false
 	if len(*export) != 0 {
@@ -47,26 +46,21 @@ func main() {
 		log.Fatalf("COMPILER ERROR: %s", err)
 	}
 
-	// print compilation result if verbose
-	if *verbose {
-		fmt.Printf("%v\n\n", operations)
-	}
-
 	// run code
-	if trace, err := vm.Execute(operations, *isNumFmt, *memorySize, *maxTicks, record); err != nil {
+	if programExecution, err := vm.Execute(operations, *isNumFmt, *memorySize, *maxTicks, record); err != nil {
 		fmt.Println()
 		log.Fatalf("RUNTIME ERROR: %s", err)
 	} else {
 		if record {
-			if err := export_trace(*export, trace); err != nil {
+			if err := export_program_execution(*export, programExecution); err != nil {
 				log.Fatalf("EXPORT ERROR: %s", err)
 			}
 		}
 	}
 	fmt.Println()
 }
 
-func export_trace(path string, trace *vm.ProgramExecution) error {
+func export_program_execution(path string, trace *vm.ProgramExecution) error {
 	file, err := json.Marshal(trace)
 	if err != nil {
 		return err

diff --git a/vm/out/hello.json b/vm/out/hello.json
@@ -1,15 +1 @@
-{
-  "ticks": 972,
-  "memsize": 6,
-  "opsize": 138,
-  "insize": 0,
-  "outsize": 13,
-  "ops": [
-    0, 0, 0, 0, 0, 0, 0, 30, 5, 6, 12, 6, 10, 5, 6, 6, 5, 5, 5, 3, 5, 4, 5, 2, 1, 5, 27, 26, 6, 6, 7, 3, 3, 3, 3, 3, 3,
-    3, 3, 79, 1, 3, 3, 3, 3, 64, 1, 3, 3, 1, 3, 3, 3, 1, 3, 3, 3, 1, 3, 2, 2, 2, 2, 4, 45, 1, 3, 1, 3, 1, 4, 1, 1, 3,
-    76, 2, 74, 2, 4, 39, 1, 1, 6, 1, 4, 4, 4, 6, 3, 3, 3, 3, 3, 3, 3, 6, 6, 3, 3, 3, 6, 1, 1, 6, 2, 4, 6, 2, 6, 3, 3, 3,
-    6, 4, 4, 4, 4, 4, 4, 6, 4, 4, 4, 4, 4, 4, 4, 4, 6, 1, 1, 3, 6, 1, 3, 3, 6, 0
-  ],
-  "inputs": [],
-  "outputs": [72, 101, 108, 108, 111, 32, 87, 111, 114, 108, 100, 33, 10]
-}
+{"ticks":972,"memsize":6,"opsize":138,"insize":0,"outsize":13,"ops":[0,0,0,0,0,0,0,30,5,6,12,6,10,5,6,6,5,5,5,3,5,4,5,2,1,5,27,26,6,6,7,3,3,3,3,3,3,3,3,79,1,3,3,3,3,64,1,3,3,1,3,3,3,1,3,3,3,1,3,2,2,2,2,4,45,1,3,1,3,1,4,1,1,3,76,2,74,2,4,39,1,1,6,1,4,4,4,6,3,3,3,3,3,3,3,6,6,3,3,3,6,1,1,6,2,4,6,2,6,3,3,3,6,4,4,4,4,4,4,6,4,4,4,4,4,4,4,4,6,1,1,3,6,1,3,3,6,0],"inputs":[],"outputs":[72,101,108,108,111,32,87,111,114,108,100,33,10]}