Skip to content

Latest commit

 

History

History
30 lines (21 loc) · 1.55 KB

README.md

File metadata and controls

30 lines (21 loc) · 1.55 KB

Zijkstra

Educational tool. Proving the shortest path through a maze with recursive SNARKs.

NOTE: Updating the README after wrapping up another project this week. If you want to look around before then, all the magic happens in nova/src/main.rs and nova/circom/traversal.circom. Hopefully wrote everything so it's easy to follow. Also note that if you clone this repo to run, you have to clone my fork of nova-snark and nova-scotia in the parent directory (mainly made a few structs public to dissect).

Motivation

Meant for learning more about recent proving systems- Nova and Plonky2 in particular- for recursive SNARKs. Verifying shortest paths found via Dijsktra's Algorithm. Ideal for focusing on the basic SNARK mechanics since maze traversal is a familiar problem that doesn't involve many constraint-heavy operations.

Why Dijkstra's insead of a simpler DFS? Because Zijkstra is catchier than Maze Zolver of course.

Step Circuit

PUBLIC INPUTS

  1. H(grid): Hash of the grid / maze
  2. L1: Location before stepping
  3. C1: Cost accrued to get to the location

PUBLIC OUTPUTS (symmetric, same as public inputs)

  1. H(grid): Hash of the same grid / maze
  2. L2: Location after stepping
  3. C2: Cost accrued + additional cost for moving to location

PRIVATE INPUTS

  1. A: Grid that is traversed
  2. m: Move for this step [dRow, dCol]

LOGIC

  1. Checks that the proposed move is valid
  2. Updates location and accrued cost