zkMemory

chiro@orochi.network

Voluteer at

Agenda

• Whoami?
• Intro to ZKP
• Overview
• Specification
• Growth potential
• Q & A

~$ whoami

• Founder of Orochi Network
  • ZKP
  • MPC (threshold signature, ECVRF)
  • VRF and VDF
  • Cryptography
• Love Open Source. Yes, i love GNU/Linux
• Love Programming. Yes, i love Rust
• Love Cyber Security & Cryptography

Intro to ZKP #1

• Everything is in heavily development
• Hard to catch up with academic side
• Code works or not work magically
• High complexity
• Security is a mist

Intro to ZKP #2

Intro to ZKP #3

Schrödinger's cat but in zkSNARK.

Overview

• Everybody who do zkVM, have to handle the memory themselves
• No one actually try to generalized the memory
• Modular is a thing (think about everything can be built in lego style)

Spec #1 What is memory?

• Storage is a memory but it's persist
• Stack is a memory with a pointer
• Registers can be emulated by several memory cells

Spec #2 Why we need to commit the memory?

• Make sure the memory state is consistent
• Prover can not cheat in a private computation

Spec #3 How do we do it?

You might aware that the memory can be constructed as a simple state machine with \(2\) instructions READ and WRITE.

Spec #4 Memory trace

Spec #5 Memory Cell

Spec #6 Merkle tree proof cost \(\mathcal{O}(log_2n)\)

Spec #7 KZG Commitment

• \(\mathsf{Setup}\): Output \(crs=\left(\{[s^i]\}_{i \in \{0,\dots, k-1\}}\right)\).
• \(\mathsf{Commit}(f(X),crs)\): Output \([f(s)]_1\).
• \(\mathsf{OpenWitness}(f(X),crs,i)\): Output \(\pi=(i,f(i),[(f(s)-f(i))/(s-i)])\).
• \(\mathsf{VerifyWitness}(crs,C,\pi=(i,y,w_i))\): Check \(e(C-[y],[1])=e([s-i],w_i)\).

Spec #8 KZG without verkle tree

Combining KZG with Verkle Tree:

• Construction time: \(\mathcal{O}(kn)\).
• Constant proof size and verfication time.

Spec #9 Verkle Tree

Sepc #10 Milestones

• Implement zkMemory as a state machine
• Support Halo2
• Support Nova & SuperNova
• Research folding scheme for vector commiment

Growth potential

What if we combine zkMemory with Nova like proof system?

• ZK File System (distributed storage + ZKP)
• ZK Database \(^{1}\) (provable data)
• Support all zkVM projects\(^{2}\)

Thank You for Your Attention

Q & A