zk-SNARKsを用いたオンチェーンスケーリング

概要

plasmaやstate channelsなどのliveness assumptionsなレイヤー2を利用せずに、zk-snarksを用いることでオンチェーンのトランザクション検証をスケールさせる。

Two main challenges of Plasma are ensuring correct transaction execution (preventing incorrect/malicious transactions) and ensuring data availability. It seems like SNARKs/STARKs should take care of the former in future, and erasure coding might be an elegant solution for the later (most implementations currently require users to download whole chains, which is quite a burden)?

a gain of ~24x for ETH transactions and ~50x for ERC20 transfers

zk-snarksはcomputation integrityまででデータ可用性問題までは解決しないが、オンチェーンなので問題なし。

relayerがtransactorsからTxを集めそれを１つのTxに集約し、そのTxに対するzk-snark proofをpublishする。

relayerはtransactorsから手数料報酬を得る。

このシステムを管理するコントラクトは以下の２つのマークルルート(bytes32)をsteteとして保持する。

A: address book

B: balances + nonces

初めは2^24個の(0,0)のマークルツリー。

transacotrsの操作

registration

deposit/withdraw

sending

Register

ユーザーはindex iのMerkle branchを提示する。

if i=0; require(A[i] == 0);

else if i>0; require(A[i] == 0); require(A[i-1] != 0);

then

A[i] = msg.sender

ユーザーが扱えるようにMerkle branchはlogに保持。

log eventはleafにつき1840 gasほど?

Deposit or Withdraw

if D > 0

if D < 0

ETH or Tokenをmsg.senderに送る

then

B[i][0] += D

まだtransactorsとして登録されていない場合は登録とデポジットのステップを同時に行うことができる。

Sending

ユーザーは以下のデータを生成

from address index (3 bytes)

to address index (3 bytes)

amount (<=6bytes)

fee (1 byte: top 5bits are exponent, bottom 3 are mantissa（仮数） )

nonce (2 bytes)

これに署名を加えて送信。

relayerがこれらの操作を集め、zk-snarkのproofを生成し、マークルツリーBのbalance, nonceのデータをアップデートしていく。

そのTxがpayment batch Txであり、merkle tree witnessを再scanする必要があるアラートをユーザーに送るためlogを発行する。

ユーザーが保持しているmerkle branchが状態遷移前のデータになる。

indexに対応するようにmarkle branchをlogに保持。

zk-SNARK検証のコストは~600,000 gas プラス base tx cost, log cost, storage slot変更などのオーバーヘッドで~50,000gas。

通常の送金でのmarginal costは、8 * 3 (from) + 68 * 3 (to) + 68 * 1 (fee) + 68 * 4 + 4 * 2 (amount) + 68 * 2 (nonce) = 892 gasほど。

このシステムを利用するtransctorが多いほど集約できるTxが増えるので効率化される。

長期的には、proof生成はGPUsを走らせるminersのような主体によって行われる。しかし、このスキームだと51%攻撃は起こりえないので、ある１つの主体が90%計算を生み出しても問題ない。

同じマークルルートの同じslotをregistarionしようとすると片方はfailしてしまうので、1ブロックに1登録。

public inputひとつにつきオンチェーンでのverificationではmodaddとmodmulが行われgasがやばい。→public inputはできるだけ少なく。

snark内でecrecoverをやるのはpracticalなのか問題。

200k-30s

logにポストされたmerkle branchがsnarksによって証明される状態遷移（Proverが計算してオンチェーンにsubmitしたMerkle root）が対応することを検証するために、全てのTxをpublic inputとしてverificationに含める必要がある。

gas対策のためにTx群をまとめたハッシュ値とinputsをpublic inputにすればgas節約できる。(?)

proveには生txをpublic inputに入れなくてはならないので、verifyの引数もそれと一致しなければならないはずなので、?

I would say make a simple hash of the inputs be a public parameter, along with the inputs, and verify the hash on chain (SHA3 is 6 gas per 32 bytes, so ~3 gas per operation).

This is why I suggested putting using hash of the submitted data as the public input, and then computing the hash on chain as that is only 6 gas per 32 bytes for SHA3 (for SHA256 it’s somewhat more but still tiny).

記録されているlogがsnarkによって証明されたstateのアップデートに対応するか検証する必要がある。

このために、public inputにTxを含めなければならないがTxごとにecmul演算が増えることになってしまう。

public inputのTxとそれぞれのlog merkle branchを再計算しrootに一致するか検証。

集約Txのハッシュ値をpublic inputにし、

snarkをpublic inputとしてTxを渡すと22Txでgas欠。

So, merkle treeをpublic inputにして、privateにsnark内で同じmerkle treeを生成し、オンチェーンで一致するか検証する。つまり、merkle tree内の任意のデータ変更がmerkle root一致のproovingに集約される。

But, EVMでsha256はcheapなのに対し、snark内ではvery expensiveになる。つまりproving timeがやばい。代わりにpedersen commitmentsを用いればsnark内ではやすくなるが、evmで高くなってしまう。

勉強会メモ

salva説によると、更新が少ないアドレスのツリーを分離したのではないか