Introducing Distaff: a STARK-based VM written in Rust

https://ethresear.ch/t/introducing-distaff-a-stark-based-vm-written-in-rust/7318

@bobbinth wrote:

I have implemented an early prototype of a zero-knowledge VM based on the ideas from A sketch for a STARK-based VM post. The project repo is here.

The VM consumes a program and inputs for the program, executes the program against these inputs, and returns program output together with a STARK proof of program execution. This proof can then be used by anyone to verify that the program was executed correctly without the need for re-executing it or even knowing what the program was.

Performance

The instruction set is still pretty limited, but the prototype is fully functional, and the performance is much better than I expected. I benchmarked the performance using a simple program which calculates n-th Fibonacci number. The results are below (and some more results are here):

Operation Count Execution time Execution RAM Verification time Proof size
210 150 ms negligible 2 ms 86 KB
214 2.2 sec 130 MB 3 ms 142 KB
218 44 sec 2.6 GB 3 ms 212 KB

This was run on Intel Core i5-7300U @ 2.60GHz (single thread) with 8 GB of RAM.

One interesting observation: the proof overhead is about 2000x. That is, out of the execution time shown above, about 0.05% is spent on executing the program itself, and 99.95% is spent on generating the proof for it.

I expect the performance to decrease somewhat as more instructions are added to the VM, but at the same time, this is not a particularly well optimized implementation running in a single thread. So, even with new instructions, once optimized for multi-threaded execution, the performance will improve significantly.

For example, once hashing instructions are implemented, I expect the VM to be able to do over 1000 Rescue hashes/second on a 4 core machine.

Example

Here is a example of how to execute a simple program which pushes two numbers onto the stack and computes their sum (Distaff VM is a stack machine):

use distaff::{ ProofOptions, processor, processor::opcodes };

// this is our program
let program = [
    opcodes::PUSH, 1,
    opcodes::PUSH, 2,
    opcodes::ADD
];

// let's execute it
let (outputs, program_hash, proof) = processor::execute(
        &program,
        &[],        // we won't initialize the stack with any inputs
        1,          // a single item form the stack will be returned
        &ProofOptions::default()); // we'll be using default options

// the output should be 3
assert_eq!(vec![3], outputs);

A slightly more sophisticated example of a Fibonacci number calculator is here.

Current limitations/issues

  • As I mentioned above, the instruction set is currently very limited. But I’m planning to add many more instructions to manipulate the stack, perform hashing, compare values etc. For some possible future instructions see here.
  • Distaff VM has no random access memory – all values live on the stack. I’d like to add a memory module, if it doesn’t introduce too much computational overhead.
  • To generate program hash I’m using a modified version of Rescue hash function. This modification likely makes the function insecure. An un-modified version can be used, though, it would add some complexity (something I’d like to avoid).
  • STARK proof generation is currently single-threaded. Though, I’ve built a lot of plumbing to make implementing multi-threaded execution simpler in the future.
  • I’m using the original FRI algorithm in STARK proofs. I’d like to swap it out for DEEP-FRI.

If you’d like to get involved and help in solving some of the issues (or many others) – let me know. Any contributions and feedback are welcome!

Posts: 1

Participants: 1

Read full topic

zk-STARK for Schnorr signature verification

https://ethresear.ch/t/zk-stark-for-schnorr-signature-verification/7034

@bobbinth wrote:

I used AirAssembly to create a zk-STARK which can be used to prove that verification of a Schnorr signature was executed correctly. Specifically:

Given a message m, a public key P, and a signature (R, s) a prover can generate a proof that s cdot G = R + hash(P, R, m) cdot P.

In the current implementation, the verifier needs to know m, P, and R (but not s) to check the proof. It should be possible (with some effort) to update the scheme so that the verifier can verify the proof with only m and hash(P), and I believe this would result in a quantum-resistant signature scheme.

benchmarks

The STARK can be used to prove verification of one or more signatures. Proof sizes look roughly as follows:

  • 1 signature: 110 KB
  • 8 signatures: 140 KB
  • 64 signatures: 180 KB

Extrapolating this further, it seems like a proof for 10K signatures should be somewhere around 300 KB in size. Moreover, with some optimizations, it may be possible to reduce proof sizes by 10% – 20%.

Proving time is currently rather slow: on my machine, it takes just under 2 seconds to prove a single signature verification, and a bit over 2 mins to prove 64 signature verifications. But, all is not lost:

  • The field I’m using has not been optimized with WebAssembly – so, all math happens in JavaScript which is terribly slow. Moving math operations to WebAssembly should speed things up by a factor of 6x – 8x (and native code would be even faster than that).
  • AirAssembly compiler hasn’t been optimized yet – so, the code it outputs is pretty inefficient. Optimizing it could speed things up by a factor of 2x – 3x.
  • I’m running everything in a single thread. With multithreading, things will get significantly faster.

STARK structure

AirAssembly source code for the STARK is here and the runable example is here. Despite looking intimidating, the structure is rather simple:

  • Execution trace has 14 registers:
    • The first 7 are used to compute s cdot G ,
    • The other 7 are used to compute R + h cdot P, where h is an input equal to hash(P, R, m).
  • I use a simple double-and-add algorithm for elliptic curve multiplication:
    • At each step the base point is doubled, and when needed, added to the accumulated result (x, y coordinates for base points and accumulated results account for 4 out of 7 registers used in each multiplication).
    • I also pre-compute slopes for addition/doubling one step before the actual addition/doubling to keep constraint degree low.
  • The total number of transition constraints is 18, and the highest constraint degree is 6.

The elliptic curve I’m currently using is P-224 because it is one of the standard curves defined over a “STARK-friendly” field. But swapping it out for some other curve is trivial.

If anyone sees any issues, or has any feedback – let me know!

Posts: 1

Participants: 1

Read full topic