Giter VIP home page Giter VIP logo

olavm's Introduction

OlaVM

LICENSE CI checks issues

OlaVM is a STARK-based ZK-friendly ZKVM, it is built on a small finite field called Goldilocks field. As the most important component of the Ola system, OlaVM is mainly used to execute a program and generate a valid proof for the programmable scalable case and the programmable private case.

Warning: This repository shouldn't be used for production case, as it is still in development phase and has not been audited, so it might contain many bugs and security holes..

Overview

OlaVM is a Turing complete VM, which means that it can execute any computation on it and at the same time it could generate a valid proof for it. For getting a smaller proof time, we have many powerful designs that are relevant with ZK-friendly.

  • if you want to know more about ZK-friendly and VM designs, check out the doc/olavm;
  • if you want to know more about the circuit design, check out circuit crate;
  • if you want to know more about the performance of OlaVM, check out Performance section;
  • if you want to know more about STARKS, check out References section;

Key Features

There are a lot of tricks to get a very ZK-friendly ZKVM in OlaVM. We would like to highlight some of them:

  • Algebraic RISC. The property of the instruction set of OlaVM is Algebraic RISC: "Algebraic" refers to the supported operations are field operation, "RISC" refers to the minimality of the instruction set. We can achieve a concise transition constraint based on this, see circuit/cpu to learn more;

  • Small finite field. The word defined in OlaVM is a finite field, Goldilocks. The prime of Goldilocks is p = 2^64 - 2^32 + 1, which is less than 64 bits. The computation based on these field elements could be expected to be much faster than other large finite fields;

  • Builtins. Since the cyclic group size is limited, it would be better if the trace table could contain as many transactions as possible. This means that if there are some computation cost a large trace lines in transaction logic, we should remove them from the main trace table and add a special sub-trace table to store them, this is the reason that introduce builtins, like hash, bitwise operation and so on, check the doc/olavm for more details;

  • Prophets. It is designed for non-deterministic computation, which means "implementation is expensive, verification is cheap". So to some extent Prophets is more like an external helper. It helps you compute the results of some non-deterministic computation, and then you verify the results using the instruction sets, should note that this verification is done by the VM, not by constraints which is different with builtins, see the doc/olavm for more details;

Status

Features Status
Algebraic RISC $\color{Green}{Done}$
Small finite field $\color{Green}{Done}$
Builtins - bitwise $\color{Green}{Done}$
Builtins - rangecheck $\color{Green}{Done}$
Builtins - cmp $\color{Green}{Done}$
Builtins - poseidon $\color{Green}{Done}$
Storage $\color{Green}{Done}$
Cross-contract call $\color{Green}{Done}$
Prover optimization $\color{Green}{Done}$
Builtins - ecdsa $\color{Yellow}{Doing}$
Prophet libs $\color{Yellow}{Doing}$
u32/u64/u256 lib $\color{Yellow}{Doing}$
Support privacy $\color{Yellow}{Doing}$

Project structure

This project consists of several crates:

Crate Description
core Define instruction structure and instruction sets
circuits 1. Constraints for instruction sets, builtins, memory; 2. Generate proof
executor Execute the programme and generate the execution trace for the Ola-prover
client Some commands can be used by developers
plonky2 A SNARK implementation based on techniques from PLONK and FRI techniques
infrastructure Write the execution trace to an Excel file

Performance

Many optimizations have not yet been applied, and we expect to see some speed improvements as we devote more time to performance optimization. The benchmarks below should only be used as a rough guide to expected future performance.

Algorithm Execution Instructions Lines in CPU Table Mac(8-cpu 16GB-Mem) Execution and Generate trace Time Mac(10-cpu 32GB-Mem) Prove Time Linux(64-cpu 128GB-Mem) Execution and Generate Trace Time Linux(64-cpu 128GB-Mem) Prove Time
Calculate the 47th Fibonacci number 1000 times. 866115 2^20 0.275s, 0.571s 80.524s 0.315s, 0.95s 39.767 s
Calculate the sqrt of 1,073,741,824 16000 times. 544113 2^20 0.892s, 0.572s 65.758s 1.185s, 0.955s 29.935 s

Overall, we don't expect the benchmarks to change significantly, but there will definitely be some deviation from the numbers below in the future.

A few general notes on performance:

Software:

Hardware:

  • Integrate GPU accelerated FFT
  • Integrate GPU accelerated polynomial evaluation
  • Integrate FPGA accelerated FFT
  • Integrate FPGA accelerated polynomial evaluation

References

OlaVM runs based on the Goldilocks field and uses STARK to generate proofs for the inner layer and more will use Plonky2 to generate recursive proofs for inner proofs. There are some resources to learn more about it.

Goldilocks field & plonky2

STARK

Vitalik Buterin's blog series on zk-STARKs:

  • Part-1: Proofs with Polynomials
  • Part-2: Thank Goodness It's FRI-day
  • Part-3: Into the Weeds

Alan Szepieniec's STARK tutorials:

Sin7Y's STARK explanation:

Privacy:

License

This project is under MIT licensed.

olavm's People

Contributors

bchyl avatar cyimon avatar hongyuanyang-uu avatar matthiasgoergens avatar peinlcy avatar softcloud88 avatar spartucus avatar succinctpaul avatar web3moon avatar web3softcloud avatar yp945 avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

olavm's Issues

thread 'main' panicked at assembler/src/encode.rs:263:18: not match opcode:{

I followed the tutorial to run the asm file and wanted to generate a code file, but this step reported an error:

$ ola asm --input fib.asm --output fib.code
Input assemble file path: fib.asm
thread 'main' panicked at assembler/src/encode.rs:263:18:
not match opcode:{
note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

Use squash merging as the pr merge strategy.

What?

There are three pr merge strategies: (normal) merge, squash, rebase.
More info about them on https://docs.github.com/en/repositories/configuring-branches-and-merges-in-your-repository/configuring-pull-request-merges/about-merge-methods-on-github .

Why?

  1. Clean git logs. As we all know, when someone new a pr, usually, there are more than one commit. Using this strategy can squash many into one.
  2. The commit msg will be Pr title + pr num. We can easy track the pr context of a commit.
  • A demo as below:

image

How?

  • Go to repo->settings->General
  • Confg the Pull Requests like below:

image

memory permutation constraint

When we get memory trace from vm, we call this raw memory trace raw_mem_trace, we need sort it by address, clk, pc. We call sorted memory trace sorted_mem_trace,

address clk pc value rw
12 322 87 100 w
12 323 88 100 r
12 435 138 100 r

we then can do memory constraint:

  • First time operation of specified address should be write.
  • Address should be increased(since we sorted them).
  • When operation is read, the value must be same as last operation.
  • more...

Constraint sorted memory is not enough, we need permutation argument to make sure raw_mem_trace and sorted_mem_trace are permuted.

Request for Turkish Translation of README

Hello,

I would like to request the creation of a Turkish version of the current English README. Providing a Turkish translation will help to make the project more accessible to Turkish-speaking users and contributors.

Proposed Solution:

Translate the entire README from English to Turkish.
Ensure that all technical terms are accurately translated or appropriately kept in English if they do not have a direct Turkish equivalent.
Add a link to the Turkish version at the top of the existing README for easy access.

Context:

I am a Turkish speaker and would be happy to assist with or fully handle the translation process. Please let me know if this is something the project maintainers are open to, and if there are any specific guidelines or formats that I should follow.

Thank you for considering this request!

Refactor code

The execute function in executor::Process is way too large, consider refactor it to multiple smaller functions based on each instruction.

u64 vs GoldilocksField in vm

Should we use u64 as our main type for operands? In contrast, currently we use GoldilocksField, which is a 63 bit field(more precisely, P = 2^64 - 2^33 + 1). So the question is: what are the pros vs cons?

Refactor readme doc

For now, there are several broken color tags in readme, e.g the status (done, doing, to do). Fix these with emoji.

Is there a simple walkthrough on how to use olavm?

Hey guys,
I'm new at this field and I just read your documentation and I'm a little confused.
I don't know the step-by-step process for writing a guest program on the circuit and validating it.
I would appreciate it if you guys help me through this.
Thanks.

How to ensure that the program and the proof are bound together

I found that the verification command only needs to input a proof file, so how to ensure that the proof received by the verifier is the proof of the given program. Some stark proofs I have learned will include the hash of the program in order to bind the program and the proof.

Custom serializer for Stark proofs

Right now, we use serde to serialize StarkProof, which wastes quite a bit of space. We should make custom serializer, like plonky2 proof do. We better 'inherit' Buffer, add StarkOpeningSet read/write function.

more utils gates

We need more utils gates, like range check, comparison. So we can use these gates whenever we need. And we can also use these gates internally in builtins.

For example, something like PSE's lt gadget.

Constraint register read/write

At present, there is no constraint on the reading and writing of register, but after preprocessing, the data of register is taken out and constructed into AIR trace. We should consider make these constraints.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.