GuildOfWeavers / distaff

Zero-knowledge virtual machine written in Rust
MIT License
244 stars 44 forks source link

Add support for random access memory #20

Open bobbinth opened 4 years ago

bobbinth commented 4 years ago

Currently, stack is the only place to store values. This is rather limiting, and can be improved by introducing random access memory. Adding RAM would require:

  1. Implementing ALT stack #19
  2. Limiting total constraint degree to 7. This can be achieved by splitting instructions into high-degree and low-degree instructions #18
  3. Implementing instruction mirroring
  4. Adding an extra register to store root of the RAM state
  5. Adding LOAD and STORE instructions to access RAM state register

Overall performance impact of the above changes would probably result in over 50% execution slowdown with instruction mirroring being the biggest driver.