Lurk
LispベースのZKP DSL
https://www.youtube.com/watch?v=iLtv4yauW3s
特徴
Novaをバックエンドに採用し、IVCスキームを利用することでループ回数が未定の回路が扱える。Lurkは非常に軽量なzkVMとみなすことができる。Lispの状態遷移規則は少数しかないため、zkEVMなどと比べ大幅に少ない制約数で実装されている。 https://scrapbox.io/files/646af347c82f46001d81e241.png
動画によれば、Novaのrecursion overheadと同程度の制約数で状態遷移が記述されているよう
使い方
git repositoryをcloneして、cargo run -rを実行するとREPLが起動する。インストールしたい場合はcargo install --path .でlurkrsがインストールされる。
例
四則演算
> (+ 1 2)
[3 iterations] => 3
他にも-, *, /が使える
commitmentを求める
> (commit 123)
[2 iterations] => (comm 0x2937881eff06c2bcc2c8c1fa0818ae3733c759376f76fc10b7439269e9aaa9bc)
commitmentのopen
> (open (comm 0x2937881eff06c2bcc2c8c1fa0818ae3733c759376f76fc10b7439269e9aaa9bc))
[4 iterations] => 123
関数のcommitmentを求める
> (commit (lambda (x) (+7 (* x x))))
[2 iterations] => (comm 0x375ee32e0e8b65b75fb686ece5f54e8dcad2762caf0f3ec33ec15df578ee1c86)
let文
> (let ((a 2) (b 2)) (* a b))
[10 iterations] => 4
let + lambda(無名関数)
> (let ((double (lambda (x) (* 2 x)))) (double 5))
[9 iterations] => 10
lambda (x) (* 2 x)にdoubleという名前をつけて5に対して適応している
if文
> (if (= 1 1) 2 3)
[6 iterations] => 2
cons (ペアを作成する関数)
> (cons 1 2)
[3 iterations] => (1 . 2)
letrec (letの再帰関数を含むバージョン。lispのscheme方言の用法)
(letrec ((factorial (lambda (n)
(if (<= n 1)
1
(* n (factorial (- n 1)))))))
(factorial 5))
[76 iterations] => 120
フィボナッチ数列の例
(letrec ((next (lambda (a b n target) (if (eq n target)
a
(next b
(+ a b)
(+ 1 n)
target))))
(fib (next 0 1 0)))
(fib 10))
[521 iterations] => 55