Yellow Paper IntMax1.0下書き

# Yellow Paper IntMax1.0下書き # Chapter 1: Overview and Terminology Intmaxにおいて、スマートコントラクト上の変数、ユーザーの資産ステート、スマートコントラクトアドレス(CA)の持つ資産ステートはマークルツリーの中に含まれる領域において分離された形で格納される。一部オンチェーンに保存されるデータがあり、これらの保存と公開は全てゼロ知識証明の回路により束縛される。資産はERC20,ERC721,ERC1155の形あるいはその拡張に限定され、これらに関する操作をアトミックスワップを用いて行うのがIntMax1.0,zkEVMを加えて行うのがIntMax2.0である。では上述のスマートコントラクト上の変数、ユーザーの資産ステート、スマートコントラクトアドレス(CA)の持つ資産ステートというマークルツリー内の領域について述べる。このうちCAの資産ステートの差分だけはそのままEthereum onchain calldataに刻まれ、他は基本的にオフチェーンにおける保存となる。つまり、オペレーターに限らず全ての人が再現・確認可能である。CAの資産への残余請求権は債権トークンあるいは債権NFTによって書かれることが開発者に強制され、これは各ユーザーの資産ステートまたは他のコントラクトの資産ステートの中に保存される。債権者の権利の合計は必ずCA資産の合計と一致することがコンパイル時に強制される。ユーザーの資産ステートに関して、ユーザー個々の持つ資産ステート全体は当該ユーザーしか知ることはない。オペレーターはコントラクト実行に関係のある一部をアカウントアドレス抜きにプルーフをユーザーから渡され、多くを知らないまま実行し、レシートとして実行されたユーザーステートの差分を公表する。ユーザーのみが自分の受け取る差分を見つけ、自分のステートへのマージをzkpを用いて実行し、結果のマークルルートとzkpのproofデータをオペレーターに適当なタイミングで送り、トランザクションが完了する。オペレーターが保管するマークルツリーにはユーザーの資産ステートのマークルルートのみが保管されることとなり、オンチェーンには保存されない。IntMax2.0において、オペレーター間でのこのマークルルートの集まった部分木データの受け渡しの際には、Onchainデータを介さず直接同期することとなる。同期が全ノードで不可能な場合は後述のフリーズモードに入り、セキュリティは保持されるも、ライブネスは失われ、ユーザーはLayer1へのExitを強いられる。この部分木のマークルルートはオンチェーンに保存される。スマートコントラクト上の変数に関しては、全てオフチェーンに保存され、その全てをまとめたマークルルートのみがOnchainに保存される。これらもIntMax2.0においては、同期不可能な状態に入った時、ユーザーはLayer1にExitする。それぞれ保管の方法と義務の違いにより上記のストレージを３つに分類し呼称する。分散ストレージに管理される、スマートコントラクト上の変数が格納されている領域とユーザー資産のマークルルートが格納されている領域を合わせてCommonly Shared Storageと呼ぶ。ユーザーが管理するユーザーの資産ステートのあるマークルルート以下の領域をUser Asset Storage、Onchain calldataで管理されるCAの資産ステートが格納される領域をCA Asset Storageと呼ぶ。 # Chapter 2: Secret Contract Secret Contractは上記のスマートコントラクトのことであり、ここでは具体的にどのような仕様でオペレーターを含む全ノードがトランザクション元のユーザーを知らないまま、スマートコントラクトが実行されるのかを示す。これらのストレージ情報は次項目で図示されるマークルツリーで表現される。 ## Verkle Tree Verkle Tree の検証コスト https://vitalik.ca/general/2021/06/18/verkle.html https://scythe-trick-849.notion.site/Verkle-Tree-dddee862fd2b4486b01b6373ab75d986 各ノードのデータ構造は次のようになる。 | Node | variables | type | remarks | | :--: | :--: | :--: | :--: | | Internal node | commitment | Hash | 子ノードの vector commitment | | ^ | child nodes | Node[16~256] | 子ノードのリスト、添字に key となる値の深さ番目のバイトを配置する | | Leaf node | data | bytes | 任意のデータをバイト列にエンコードしたもの | ここで Key, Value となる値は次のようになる。 ### Commonly Shared Storage について | name | type | remarks | | :--: | :--: | :--: | | contract_address |address | 動作対象のコントラクトアドレス | | index_of_var | uint16 | そのコントラクトでその変数を何番目に定義したか | | mapping_key | Hash | `set`, `mapping` について key の Hash | | mapping_index | uint16 | `array`, `struct` についてindex(struct の場合は何番目に定義したか) | | key_storage | uint8 | (0): Commonly Shared Storge, (1): Asset Storage[contract state], (2): Asset Storage[user state] | | key_hashed | Hash | Hash((contract_address, index_of_variable, (mapping_key or mapping_index)*)) | | value | Bytes | その Primitive データをバイト列にエンコードしたもの | ### Asset Storage について | name | EOA state | contract state | type | remarks | | :--: | :--: | :--: | :--: | :--: | | contract_address | o | o | address | 動作対象のコントラクトアドレス | | owner_address | o | o | address | その Asset の所有者のアドレス | | index_of_var | o | o | uint16 | そのコントラクトでその変数を何番目に定義したか | | mapping_key | o | o | Hash | `set`, `mapping` について key の Hash | | mapping_index | o | o | uint16 | `array`, `struct` についてindex(struct の場合は何番目に定義したか) | | key_storage | o | o | uint8 | (0): Commonly Shared Storge, (1): Asset Storage[contract state], (2): Asset Storage[user state] | | key_user | o | | address | owner_address | | key_hashed | o | | Hash | Hash((contract_address, index_of_variable, (mapping_key or mapping_index)*)) | | key_hashed_with_owner | | o | Hash | Hash((contract_address, owner_address, index_of_variable, (mapping_key or mapping_index)*)) | | value | o | o | Bytes | その Primitive データをバイト列にエンコードしたもの | EOA user state について key1 と key2 の間の internal node までがオペレータが保有する。その先の node についてはそのユーザのみが保有する。実態としての木構造は次のようになる。 ```graphviz digraph hierarchy { nodesep=1.0 // increases the separation between nodes node [color=Red,fontname=Courier,shape=box] //All nodes will this shape and colour edge [color=Blue, style=solid] //All the lines look like this Root->{AssetStorage_EOA AssetStorage_Contract CommonlySharedStorage} [label = "key_storage"]; AssetStorage_EOA -> {user1_root, user2_root, user3_root} [label = "key_user"] user1_root -> {value0, value1} [label = "key_hashed"] user2_root -> {value2, value3} [label = "key_hashed"] user3_root -> {value4} [label = "key_hashed"] AssetStorage_Contract -> {value5, value6} [label = "key_hashed_with_owner"] CommonlySharedStorage -> {value7, value8} [label = "key_hashed"] } ```  ### Transaction シークレットコントラクトを実現するトランザクションを実現するためにはその発信者を特定できなくする必要がある。例えば、ERC20 においてある署名者の権限で操作を行った残高がその署名者の残高であることは Allowance などのを使用しない限り明白である。次のように、トランザクションを構成することによってオペレータが署名者やアドレスの情報無しにコントラクトを実行することができる。 | name | type | remarks | |:--------------------:|:------------------:|:----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | User | User | Userインタフェース参照 | | Latest Trees | bytes | onetimeAddress の最終更新履歴を示すSMTと全体のステートの Verkle Tree | | SignedTransaction | TransactionPayload | TransactionPayloadインタフェース参照 | | SignedTransactionZKP | Hash | 上記の署名済みの valid なトランザクションを署名者の情報無しに証明する。 $$C_{verifySignedTx}((txHash,onetimeAddress),(publicKey, signature)) \to \{true,false\}$$ $$zkProve((txHash,onetimeAddress), (publicKey, signature), C_{verifySignedTx}) \to zkProof_{verifySignedTx}$$ ここでのCは txHash の signature が publicKey が検証できるか否かの真偽値を返す回路。 | **Userインタフェース** | name | type | remarks | |:-----------:|:-------:|:----------------------------------------------------------------------------------------------- | | public_key | bytes | ユーザの公開鍵 | | private_key | bytes | ユーザの秘密鍵 | | nonce | uint256 | メッセージの再送を防ぐための Nonce, トランザクションを実行するたび各ユーザごとに increment する | **TransactionPayloadインタフェース** | name | type | remarks | |:-----------:|:-------:|:----------------------------------------------------------------------------------------------- | | Contract address | address | 実行したいコントラクトアドレスを指定する | | Data | bytes | コントラクトアドレスに呼び出し関数とその引数の情報 | | Onetime address | address | 秘密鍵とnonceから一意に生成されるワンタイムアドレス。 秘密鍵の保有者のみが自分のワンタイムアドレスであることがわかる。 `Hash((secretKey, nonce)) ⇒ prefix 20byte` | | User state value | map(bytes => bytes) | [contract address + contract 内で宣言された index] => value となるようなの Trie 辺のリスト | | User state zk proof | Hash | そのコントラクトを実行するために必要な asset storage の value について、その資産の保有者の名前無しで asset の値が value 以上であることを証明する。 $$ C_{proveUserStateValue}((userStateValue, onetimeAddress, latestTreeRoots),\\ (userStateProof, user)) \to \{true,false\}$$ $$ zkProve((userStateValue, onetimeAddress, latestTreeRoots),\\ (userStateProof, user), C_{proveUserStateValue}) \to zkProof_{proveUserStateValue}$$ ここで、Cは userStateProof からその user が確かに userStateValue と同等の value を保有している時 true を返す回路 さらに、Cは onetimeAddress が secretKey と nonce から導かれるアドレスであることも検証する。 userStateValue は asset storage の user 情報を含まない - 例<ul><li>int256 a = balanceOf[msg.sender]</li><li>→ a = userStateValue;</li><li>balanceOf[msg.sender] -= 10</li><li>→ state diff = -10;</li></ul>| | signature | bytes | TransactionPayload をユーザの秘密鍵で署名したもの | 上記構造では簡略化のため、ガスに関連するParamは扱わない。それに伴い、ネイティブトークンの概念を削除しすべての資産は ERC20 の形式で記述する。実態として、ユーザは SignedTransactionZKP と TxPayload をオペレータに提出するその時の公開される情報は以下となる。 - TxPayload - ContractAddress - Data - OnetimeAddress - UserStateValue - UserStateValue の zkProof - SignedTransactionZKP オペレータは上記の情報を元にトランザクションを実行し、asset の変更があった場合にその state diff をブロードキャストする。また、その state diff を StateDiffTree に挿入する。 StateDiffTree はある state diff が実行済みの tx から出力されているかを検証するために利用する。 ## APPENDIX - about C_{verifyUserStateValue} - ### verifyUserStateValue - Public input - UserStateValue - 実行するスマートコントラクトで参照する自身の Asset storage の Value のリスト - [ (key([contract address + contract 内で宣言された index]), value) ] = [ (byte32, [byte32]) ] の (Key, Value) のタプルのリスト - onetimeAddress - ユーザの秘密鍵と nonce から一意に導かれるアドレス - `Hash( (secretKey, nonce) )` - LatestTreeRoots - [Hash] - onetimeAddress の最終更新履歴を示すSMTと全体のステートの Verkle Tree の検証に必要な各ルートハッシュ - Private input - userStateProof - UserStateValue と Previous StateDiff を証明するための Sibling のリストとそのユーザについて最新の変更が適応された以降の rootHash を持つ - User State Sibling - ユーザ root hash より上についての sibiling - [ Sibling node hash ] = [ byte32 ] - User State internal siblings - ユーザ root hash までの sibiling のリスト. 全ての User State Value, Previous State Diff について持つ - [ key, [ Sibling node hash ] ] = [ byte32, [byte32 ] ] - **このあたり Verckle Tree を使うことで削減できるかも？** - nonce - そのユーザが送るトランザクションが何回目かを示す値(uint32) - secretKey - ユーザの秘密鍵 - Previous StateDiff - 前回の Tx についての StateDiff - その diff が発生した TransactionHash = bytes32 - Diff - ContractAddress = address - Data = [bytes32] - Value(diff) = [byte32] - onetimeAddress - address - 前回の oneTimeAddress から検索して取得する ### verifySignedTx - Public input - txHash - Hash - TxPayloadのハッシュ - oneTimeAddress - address - Private input の秘密鍵/公開鍵のペアを縛る。 - Private input - publicKey - bytes - ユーザの公開鍵　 - secretKey - bytes - ユーザの秘密鍵 - signature - bytes - 秘密鍵で txHash を署名したもの - nonce - number - 破綻しないやつを入れる。(onetimeAddress をたまたま衝突させられないので) ### Algorithm - 1個前の oneTimeAddress が使われている且つ今回の oneTimeAddress が使わていないこと or nonce が 0 であることの検証 1. nonce === 0 を検証、異なる場合次の処理を行う 2. `Hash( (secretKey, nonce-1) ).prefix(20)` が transactor として存在することを address Merkle Tree[Exit に使うもの参照] を用いて inclusion proof を作成し検証。 3. oneTimeAddress が transactor として存在しないことを address Merkle Tree[Exit に使うもの参照] を用いて non-inclusion-proof を作成し検証。 4. 使用する rootHash については上記が検証可能なものであれば何でも良い。 - ← この理由は、operator が oneTimeAddress が重複するトランザクションについては弾くからである。 - 前回の TxHash について Diff を解決していることの検証 - Previous StateDiff が自身の User State 内に含まれていることを user State Proof を用いて検証する。 - Previous StateDiff の持つ `onetimeAddress = Hash( (secretKey, nonce-1))` であることを検証 - SMT 上の Previous StateDiff について inclusion proof を検証. - SMT の root proof から User State Root との inclusion proof を検証. - onetimeAddress が secretKey と nonce から導かれるアドレスであることの検証 - oneTimeAddress = Hash( (secretKey, nonce) ).prefix(20) であることを検証 - userStateProof から user が確かに userStateValue と同等の value を保有していることの検証 - 各 userStateValue について user State Internal Proof を用いて user Root Hash と一致するか検証 - user Root Hash が user State Proof を用いて root Hash と一致するか検証 ## オペレータの検証 - latestTreeRoots が過去に存在する trees root かを検証する。 - oneTimeAddress が重複して使われていないかを検証する。 - 各zkProofにおける publicInput の onetimeAddress が同一かを検証する。 - 上記の zkProof 2点を検証する。シーケン図参照: https://hackmd.io/eYGLs-vMTjSuiAl9ueTzjw?view#Transaction%E3%82%92%E5%8F%97%E3%81%91%E5%8F%96%E3%82%8B ## User State Update ユーザはトランザクションを発行した後に、その変更結果を自身の User state に反映させる必要がある。二重支払いや自身の残高証明で不正ができないようにするため、次のような Proof を提出する必要がある。 $$C_{verifyUpdateDiff}(newUserMerkleRoot, (userState,stateDiff)) \to \{true,false\}$$ $$zkProve(newUserMerkleRoot, (userState, stateDiff), C_{verifyUpdateDiff}) \to zkProof_{verifyUpdateDiff}$$ ここで StateDiff を次のように定義する。 - StateDiff - その diff が発生した TransactionHash - onetimeAddress or receiveAddress - Diff - ContractAddress - Data - Value(diff) オペレータは実行されたトランザクションによって返された Diff を使用して、UserState を更新したことを検証したい。この時、オペレータは UserState のルートハッシュを変更する必要があるためユーザアドレスの情報が必要となる。そのため、対となる StateDiff の情報をオペレータから隠す必要がある。この回路では現在の userState と stateDiff が一意に対になっていることを検証し、更新を適用した結果である userMerkleRoot を出力する。stateDiff が未解決であることの証明は userState 内で解決済み stateDiff を SMT に保存して non-inclusion-proof することでできる。 zkp は userState を元に上記の回路を適用した結果が userMerkleRoot であることを証明する。このzkp をオペレータに提出する。実際に、オペレータに送られる情報は次のようになる。 - newUserMerkleRoot - currentUserMerkleRoot - userAddress - stateDiffRoot - zkProof ### Received Transaction Received Transaction(残高が増加するパターン)についてはステートの反映をいつ行っても良い。自分が送った Transaction(残高が減少する可能性のあるパターン)については、ステートの反映を行わなければ次のTransaction を送ることができない。**具体的には、新たなトランザクションを生成する際に、前回のTransactionHashについて Diff を解決していることを証明する必要がある。(最初の Transaction については行わない)** また、Receive Address は `Hash(secret_key, 負の値).prefix(20)` で表現されデフォルトで `Hash(secret_key, -1).prefix(20)` を Receive Address とする。 ## APPENDIX - details of UpdateStateDiff - ### about C_{verifyUpdateStateDiff} - Public input - userAddress - address - state を変更するユーザのアドレス - newUserStateRoot - 反映後のユーザーマークルルート - byte32 - stateDiffRoot - Hash - state diff の全体集合のルート - private input で指定した state diff root が確かに存在することを縛る。 - Private input - User State - ユーザの State 情報 - secretKey - bytes - ユーザ秘密鍵 - nocne - number - これらの情報から userAddress と public input の userAddress と同一かを縛る。 - また receive address or onetime address と同一かを縛る。 - receive address or onetime address は　state diff の inclusion-proof で中身を縛られているので変更はできない。(たまたまHashが一致する何かを作らなければならないので) - State Diff - その diff が発生した TransactionHash - Byte32 - Diff - [(Contract Address + その contract 内で宣言された index, Diff)] - [(byte32, [byte32])] - targetAddress - address - 受け取り側の場合は receive address, tx 送信者の場合は onetime address を持つ - State Diff Proof - State Diff SMT の inclusion-proof ### Algorithm - StateDiff が StateRoot に含まれていることを検証 - userAddress が secretKey と対になっていることを検証 - receive address or onetime address が `Hash(secretKey, nonce).prefix(20)` になっていることを検証 - userState と stateDiff が一意に対になっていることを検証 1. userState 内で stateDiff を管理する SMT を持つ 2. これらは辺に Diff が発生した TxHash , 葉に StateDiff の中身(のHash) を持つ 3. 受け取った State Diff について non-inclusion proof を行う - stateDiff を適用した結果が newUserMerkleRoot であることを検証 1. Simulator( userSate, stateDiff ) => newUserState を動かす 2. Simulator の仕様についてさらに後述 - 一般的な Merkle Tree に Diff を適用するアルゴリズム - O(Diff の数 * log(Node数)) 程度 3. newUserSatate について Merkle root hash を計算する #### 返り値 - currentUserStateRoot - 反映前のユーザーマークルルート - byte32 - currentUserStateProof - ユーザ root hash より上についての sibiling - [ Sibling node hash ] = [ byte32 ] ### オペレータの検証 - currentUserStateProof で用いられる rootHash が最新の StateDiff が適用されたものであることを検証 - 用いれた rootHash 以降に変更を要求したユーザの merkle root が変更されていないかをチェック(Exit tree 参照) - diffRoot が過去存在していたことを検証 - 上記の zkProof を検証 ```mermaid sequenceDiagram participant U as User participant O as Operator autonumber O ->> U : return UserStateDiff U ->> U : merge StateDiff U ->> O : submit UserState O ->> O : verify ZKProof O ->> O : verify ValidRootHash O ->> O : merge UserStateDiff to newUserStateRoot O ->> U : return result ``` # Chapter 3: Exit Safety ## 1. 定義 exitとはLayer2でトラブルがあったり、何らかの理由でL1に資金を移動したい場合に行う動作のことである。本zkRollupでは、exitには２種類あり、オペレーターがexitに必要な作業を手伝ってくれるパターンと、ユーザー自身のみで行うexitである。前者は4.1.1で手法Aとして紹介し、後者は4.2.1で手法Bとして紹介する。 ## 2. 前提 exitするために必要な情報は主に2つである。`EOA Uer State`と、`Last　Updated　Block　Height`が必要である。 exitの前提として前述の情報をいつでも検閲なく取り出せる必要がある。 ### 2.1 EOA User State ユーザーの資産の情報をまとめたMerkle Treeのことである。オペレーターから暗号化された`EOA User State`を受け取る際に、L2のブロック高と EOA　User Stateを証明できるMerkle proofを受け取って保存しておく。`EOA user state`の、保存場所は２箇所ある。１箇所目はユーザーの鍵で`EOA User State`を暗号化し分散ストレージに保存する。２箇所目はユーザーのローカルのウォレットである。 ### 2.2 One Time Address List ユーザに使用された`One Time Address`を管理するSparse Merkle Tree(以下SMT)の構造について記述する。KeyがOne Time Address、ValueがTrueとなるようSMTに保存する。ユーザのStateにupdateがあるごとにL1のCalldataに載せ、SMTのMerkle Rootはストレージに書き込む。またL1にブロックをコミットする際にそのブロックでのOne Time Address Listをhashにしたものと、zkpでone time address listをhashしたものが一致するかを検証する必要がある。 | name | type | remarks | | :--: | :--: | :--: | | key | bytes32 | One Time Address | |value| bool | true| ### 2.3 Cotract Address Mapping L2の資産をL1に引き出すときに、L2のコントラクトのアドレスからL1のコントラクトアドレスやL1ネイティブな資産家どうかを引けるようなMappingが必要になる。 | name | type | remarks | | :--: | :--: | :--: | | key | bytes32 | L2 Contract Address | |value| struct | L1 Contract Address(address), isL1Netive(bool)| #### L1ネイティブなERC20の場合 L1上で先にERC20等の資産を発行している場合は、オペレーターがブリッジをし初回のみERC20をcreate2でdeployしmintする。2回目以降はmintのみを実行する。またL2からL1にブリッジする場合はL2のコントラクトに預けるときにburnし、L1でtransferする。 ```mermaid sequenceDiagram actor T as Transactor participant L1 as L1 Contract participant O as Operator participant L2 as L2 Contract actor T2 as Transactor autonumber T ->> L1 : deposit O ->> L1 : get(deposit status) L1 ->> O : Result O ->> L2 : deploy contract with Create2 O ->> L2 : mint ERC20 Note right of L2: few month later T2 ->> T2 : zkp(has balance) T2 ->> O : exit(proof) O ->> O : verify(proof) O ->> L2 : burn ERC20 L2 ->> O : status O ->> L1 : commit(proof) L1 ->> T : transfer(assets) ``` #### L2ネイティブなERC20の場合 L2上でERC20等の資産を先に発行しexitする場合は、L1のexitコントラクトの中で初回のみERC20をcreate2でdeployしmintする。2回目以降はmintのみを実行する。またL1からL2にブリッジするときはL1でERC20をburnし、L2でオペレーターがブリッジコントラクトで預かっていたERC20をtransferする。 ```mermaid sequenceDiagram actor D as Deployer actor T2 as Transactor2 participant L2 as L2 Contract participant O as Operator participant L1 as L1 Contract actor T as Transactor autonumber D ->> L2 : Deploy ERC20 O ->> L2 : Get status L2 ->> O : Result O ->> L1 : save L2 address Note right of L1: few month later T ->> L1 : exit L1 ->> L1 : deploy ERC20 with create2 L1 ->> T : mint ERC20 Note right of L1: few month later T ->> L1 : burn ERC20 O ->> L1 : get status L1 ->> O : status O ->> L2 : transfer ERC20 L2 ->> T2 : transfer ERC20 ``` ## 3. exit手法 ### 3.1.1 手法A(オペレーターがexitをするモデル、通常のexitはこちら) まずexitしたいユーザーは自分のローカルに`EOA user state`があるか確認し、ない場合は分散ストレージから取得する。exitする資産を指定し自分の`EOA User State`の資産の量を減らし、exitする資産の量(public input)を証明できるZKPをクライアントサイドでProveする。 $C_{proveUserStateChange}((onetimeAddress, amount), (currentUserMerkleRoot, newUserMerkleRoot, ,merkleProof,nonce, keyHashed,privateKey)) \to \{true, false\}$ **zkp input** | name | type | visibility| remarks | | :--: | :--: | :--: | :--: | | currentUserMerkleRoot | bytes32 | private |現在のEOA User StateのMerkle Root | | newUserMerkleRoot | bytes32 | private |Exitした後のEOA User StateのMerkle Root | | onetimeAddress | address | public | Userの1回きりしか使えないアドレス | |nonce| uint|public|Userがtxを発行した回数| |keyHashed| bytes32| private| 自分の資産の場所を示すKey| |amount| uint256| public| 自分のkeyHashedにある資産の量| |merkleProof| bytes| private| 自分のkeyHashedの資産がEOA User StateのRootに含まれていることを証明するためのProof| |privateKey|bytes32(?)| private| 秘密鍵| exitしたいユーザーは生成したProofをオペレーターに渡しexitを実行する。一定期間ごとにオペレータがL2のブロックを生成し回路のインプットとなるMerkle rootや、txをまとめたものや、exitするための情報(user address, contract address, amount)がpublic inputとして出力される。このタイプのexit txは普通のL2のtxと同様に処理される。オペレーターは集約されたL2 TransactionをinputとしてZKPのProveを実行する。 $C_{proveRollupState}((currentMerkleRoot, newMerkleRoot), (zkEVMStateProofs, zkEVMExecutionProofs, exitProofs)) \to \{true, false\}$ **zkp input** | name | type | visibility| remarks | | :--: | :--: | :--: | :--: | | currentMerkleRoot | bytes32 | public |現在の全体のStateのMerkle Root | | newMerkleRoot | bytes32 | public |次のブロックの全体StateのMerkle Root | | zkEVMStateProofs | bytes | private | zkEVMが実行する際にアクセスするStateが確かに正しいというProofたち。 | | zkEVMExecutionProofs | bytes | private | 確かにbyteコード通りにzkEVMを実行したというProofたち。 | |exitProofs|bytes| private| exitに必要なProofたち。| オペレーターがProofをL1にコミットすることで、exitとL2の状態遷移が実行される。exitにかかるfeeはuserから徴収する。またこのexit手法によってL2のプライバシーがL1にも引き継がれ、L2のアドレスとL1のアドレスが紐づけられることはない。Tornado.cashと同等のプライバシーを得ることができる。 ```mermaid sequenceDiagram actor T as Transactor participant O as Operator participant P as Prover participant L1 as L1 Contract autonumber T ->> T : zkp(has balance) T ->> O : exit(proof) O ->> O : verify(proof) O ->> O : change(state) P ->> O : get(zkp input) O ->> P : zkp input P ->> P : zkp(state channge correct) P ->> L1 : commit(proof) L1 ->> L1 : verify(zkp) L1 ->> T : transfer(assets) ``` ### 3.1.2手法Aに対する考えられる攻撃オペレーターが検閲をして、exitのtxを除外したProofを作ることができる。手法Bではオペレーターが検閲したことを考え、自分でL1に直接exit proofをコミットすることを考える。 ### 3.2.1 手法B(Livenessも必要ないモデル) 前提として手法Bのexitは、freeze modeと呼ばれる一定期間オペレーターによる状態遷移が行われなかった状態のみに許可される。通常時はexitによってstateの遷移が行われるとオペレーターが実行中の状態遷移ZKPが中断されてしまうので、これは許可されない。まずexitしたいユーザーは自分のローカルにあるEOA User Stateか、ない場合は分散ストレージからEOA User Stateを取得する。またLayer2の現在のブロックのOne Time Address Listも取得する。EOA User Stateを元に、自分のuserStateRootがuserStateMerkleRootに含まれていことを証明する。このinclusion Proofにより、そのブロック(userStateMerkleRoot)時点で、自分が資産を持っていたことが証明できる。 $C_{proveUserState}((userStateMerkleRoot, amount, keyHashed), (userStateMerkleProof, userStateMerkleRoot, merkleProof)) \to \{true, false\}$ **zkp input** | name | type | visibility| remarks | | :--: | :--: | :--: | :--: | | userStateMerkleRoot | bytes32 | public | exit前のEOA User StateのMerkle Root | | userStateMerkleProof | bytes32 | private | exit前のEOA User StateのMerkle Proof | |amount| uint256| public| 自分のkeyHashedの資産の量| |keyHashed| bytes32| public| 自分の資産の場所を示すKey| | userStateMerkleRoot | bytes32 | private |現在のEOA User StateのユーザーのMerkle Root | |merkleProof| bytes| private| 自分のkeyHashedの資産がEOA User StateのRootに含まれていることを証明するためのProof| 次に、One Time Address Listの情報を元に、hash(privateKey + nonce + 1)のonetime addressがSMTの中に含まれていないことを証明する。この証明により、提出されたEOA user stateが過去のブロック高から最新ブロック高まで更新されていないことを証明できる。 $C_{proveNoUpdateUserState}((smtRoot, smtProof), ( privateKey, nonce)) \to \{true, false\}$ | name | type | visibility| remarks | | :--: | :--: | :--: | :--: | | smtRoot | bytes32 | public | Sparse Merkle TreeのRoot | |smtProof| uint256| public| one time addressからRootまでを証明するために必要なsibling| | privateKey | bytes32 | private |現在のEOA User StateのMerkle Root | |nonce| bytes| private| 自分のkeyHashedの資産がEOA User StateのRootに含まれていることを証明するためのProof| この2つのProofをinputとするL1のexitコントラクトを実行するとexitが実行される。また同じkeyHashedを使用したexitが2回行われることを防ぐため、`keccak256(userStateRoot, keyHashed)` はL1コントラクトのmappingで管理し、同じuserStateRootとkeyHashedが2度使われてないことを検証する必要がある。 ```mermaid sequenceDiagram participant O as Operator participant L1 as L1 Contract actor T as Transactor autonumber O ->> O : go offline in XX Hours L1 ->> L1 : freeze mode T ->> L1 : get SMT L1 ->> T : SMT T ->> T : zkp1(UserState) T ->> T : zkp2(NoUpdateUserState) T ->> L1 : withdraw(proof1, proof2) L1 ->> L1 : verify(zkp1, zkp2) L1 ->> T : transfer(assets) ``` # Chapter 4: Precommit and Main Commit zkRollupは、十分に短いL1へのコミットメント間隔(10分など)を採用することで、即時のファイナリティを得ることが実現できる。しかし短い間隔にするとガスコストは高くなるので、即時のファイナリティとガスコストはトレードオフの関係にある。具体的にはzkのペアリング検証には200kを超えるガスが必要となり(groth16の場合)、これはzkRollupの手数料の大きな負担になる。これを解決するために次の手法を提案する。 ### Recursive ZK finalize zk verificationを使用しないコミットメントは、プリコミットとして扱う。 ```mermaid flowchart LR pre-commit --> id2[pre-commit] --> id3[pre-commit] --> id4>main commit] --> id5[pre-commit] --> id6[pre-commit] ``` メインコミットは、前回のメインコミット(チェックポイント)から最新のプリコミットまでを、再帰的なzkで検証する必要がある。プリコミットではzkRollupのロジックが正しいのかを検証する回路を用いる。メインコミットでは再帰的にプリコミットのproofが正しいのかを検証する回路を用いる。 ### プリコミット中のexitについて Verifyされるまでは状態遷移がfinalizeされないので、プリコミットを導入するとexitできるタイミングが通常より限定される。6時間ごとにメインコミットでverifyすることを仮定すると、それまでのプリコミットの間はexitできない。緊急を要する場合、ペアリング検証コストをユーザーが負担することにより、いつでもexitすることができる。 ### 個々のprecommitにおけるデータ構造 $ZkProof = ZkProve_{updateState}((currentMerkleRoot, newMerkleRoot, onetimeAddressRoot, globalStateRoot, CAUserStateRoot, OnetimeAddressListRoot, StateDiffRoot), (transactions)) \to \{true, false\}$ | name | type | storage | remarks | |:----------------------:|:----------------:| -------- |:------------------------------------------------------:| | Root | Hash | storage | storage 情報のルートハッシュ | | GlobalStateRoot | Hash | calldata | Global user state のルートハッシュ | | CAUserStateRoot | Hash | calldata | Contract Account user state のルートハッシュ | | EOAUserStateRoots | [address,Hash][] | calldata | 変更があった EOA user state のアドレスとルートハッシュ | | OneTimeAddressListRoot | Hash | calldata | 変更があった OnetimeAddress のSMTのルートハッシュ | | StateDiffRoot | Hash | calldata | StateDiffのSMTのルートハッシュ | | OnetimeAddressUpdates | address[] | calldata | Tx を発行した onetimeAddress のリスト | | ZkProof | bytes | calldata | ロールアップの状態遷移のProof | | ZkProofHash | bytes32 | calldata | ZkProofのKeccak-256 | ### Main commitにおけるデータ構造 $RecursiveZkProof = ZkProve_{recursiveBlockFinalize}((currentMerkleRoot, newMerkleRoot, onetimeAddressRoot, globalStateRoot, CAUserStateRoot, OnetimeAddressListRoot, StateDiffRoot, zkProofs), ()) \to \{true, false\}$ **RecursiveZkProof作成時に必要なデータ** | name | type | remarks | |:----:|:----:|:-------:| | zkProofs | bytes[] | 前回のMain Commitから最新ブロックまでのZkProof。 | **Main commit時に必要なデータ** | name | type | storage | remarks | |:----------------------:|:----------------:| -------- |:------------------------------------------------------:| | Root | Hash | storage | storage 情報のルートハッシュ | | GlobalStateRoot | Hash | calldata | Global user state のルートハッシュ | | CAUserStateRoot | Hash | calldata | Contract Account user state のルートハッシュ | | EOAUserStateRoots | [address,Hash][] | calldata | 変更があった EOA user state のアドレスとルートハッシュ | | OneTimeAddressListRoot | Hash | calldata | 変更があった OnetimeAddress のSMTのルートハッシュ | | StateDiffRoot | Hash | calldata | StateDiffのSMTのルートハッシュ | | OnetimeAddressUpdates | address[] | calldata | Tx を発行した onetimeAddress のリスト | | RecursiveZkProof | bytes | calldata | 前回のMain Commitから最新ブロックまでの再帰的なZkProof | | RecursiveZkProofHash | bytes | calldata | RecursiveZkProofのkeccak-256 | # Chapter 5: Interoperability to Lightinig Network 本項ではオペレーターへのLightning Networkを通した手数料支払について解説する。 ## 基本モデルユーザーはまずトランザクションのデータをオペレーターに対して提示し、見積もられる計算量やストレージ使用量に合わせたInvoiceをユーザーに提示する。ユーザーはDiffと一緒にこのInvoiceを受け取り、Lightning Networkで支払う。オペレーターは支払いを確認した後トランザクションを処理する。 ```mermaid sequenceDiagram actor U as User participant O as Operator participant T as Totoro Network autonumber U --> O : Send Tx Data O --> U : Send Invoice and diff U --> O : Pay Network fee via LN O --> T : Execute Tx ``` ただし、この方式ではユーザーが支払ったあと、オペレーターがトランザクションを処理することについて保証されていない。ユーザーが支払った場合、きちんとトランザクションが処理されることについて保証される方式について以下で解説する。 ## トラストレスに手数料支払をおこなうための条件上記のようにトラストレスに支払いが可能であるための条件を考える。 Lightning Networkでの支払いにおいて、Txの処理の有無に応じた払い戻しはできないため、もしオペレーターが処理を行わなかった場合についてはLightning Networkではなく本ネットワークもしくはL1チェーン上での補償を行う必要がある。そのため、オペレーターは補償を行うチェーンに対してなんらかの資産をステークし、オペレーターに不正があった場合、そのチェーンを通して補償させる必要がある。また、その場合ユーザー側の支払いの遅延などによってオペレーターが不利益を被らないようにする必要がある。そのうえ、Lightning Networkの支払いについては正常に行われている必要がある。以上の点を踏まえて以下の6点をトラストレスな手数料支払に必要な条件と定義する。 1. InvoiceのPreimageは支払いが完了するまで判明してはいけない 2. InvoiceがそのTxに対する正しいInvoiceであることはユーザーが支払うまでに検証可能でないといけない 3. ただしいメッセージ交換が行われている場合、オペレーターリーダーが交代するまでにすべての通信が必ず完了し、その後のメッセージはすべて無効である 4. オペレーターは支払いを受けたのであれば必ずTxが発行可能な状況でなければならない 5. Txを実行しなかった場合、確実に補償を請求できる 6. Txを実行した場合、確実に補償を請求できない ## 支払い方式今回提案する手法においてはオペレーターはInvoiceと同時にユーザーのOneTimeAddressを含んだinvoiceの署名をユーザーに提出することを要求する。 (この際に利用する鍵はリーダー交代時にL1に提出する) これを確認した後、ユーザーは手数料をLightning Networkで支払う。また、この際利用されるInvoiceは現在リーダーであるオペレーターがリーダーを交代するまでに期限切れしないといけない。 #### シーケンス図 - sigPubkey = Public key for signature - sigPrivkey = Private key for signatures ```mermaid sequenceDiagram actor U as User participant O as Operator participant T as Totoro Network participant F as L1 Chain autonumber O --> F : Submit sigPubkey U --> O : Throw Tx data O --> O : Calc gas fee O --> U : Return receipt, invoice, siblings O --> U : Return OPSIG = Sig(Hash(Prefix + Hash(invoice) + OneTimeAddress, Sig(L1Address, L1Privkey)), sigPrivkey) U --> U : Validate Invoice U --> O : Pay Fee through LN O --> T : Execute Transaction with invoice hash ``` ### OperatorがTxを処理しない場合この場合、ユーザーはL1に対して補償をClaimすることができる。その際、ユーザーはLNの支払いによって獲得したInvoiceのPreimageを提出する必要がある。 Preimageとinvoiceおよびオペレーターが提出した署名、そして使用する予定であったOneTimeAddressを提出する。 #### シーケンス図 - sigPubkey = Public key for signature - sigPrivkey = Private key for signatures ```mermaid sequenceDiagram actor U as User participant O as Operator participant T as Totoro Network participant F as L1 Chain autonumber O --> F : Stake Token(WBTC or ETH) O --> F : Submit sigPubkey U --> O : Throw Tx data O --> O : Calc gas fee O --> U : Return receipt, invoice O --> U : Return OPSIG = Sig(Prefix + Hash(Hash(invoice) + OneTimeAddress), sigPrivkey) U --> U : Validate Invoice U --> O : Pay Fee through LN O --> O : Hold Tx O --> O : Leader Changed U --> F : Submit OneTimeAddress, Invoice, OPSIG, preimage F --> F : Check if Operator is lazy F --> O : Slash Lazy OP's stake O --> U : Transfer staking token ``` ## Claimの具体的な方式補償のClaimは二段階の方式から成り立っている。 ### 1. オペレーター署名の確認このフェーズではまず指定されたオペレーターが提出した公開鍵（前述のsigPubkey）を参照し、すでにリーダーから交代されていることを確認する。そののち、提出された署名が正しくInvoiceのハッシュとOneTimeAddressのハッシュであることおよびPreImageがInvoiceに対して正しいことを確認する。 ### 2. OneTimeAddressのNon Inclusion Proof 対象のオペレーターがリーダーの間に提出された、Diffが出現したOneTimeAddressのSMTすべてに対して、ユーザーのOneTimeAddressが含まれていないことをNon Inclusion Proofによって証明する。もしSMTに含まれていた場合は該当トランザクションは処理されているため、Claimは通らなくなる。 ```mermaid sequenceDiagram actor U as User participant F as L1 Chain participant O as Operator autonumber O --> F : Submit sigPubkey O --> F : Submit SMTs of OneTimeAddress O --> O : Change Leader Operator U --> F : Submit (LeaderID, OPSIG, Invoice, Preimage, OneTimeAddress) F --> F : Check if leader is already changed F --> F : Validate PreImage F --> F : Validate OPSIG with LeaderPubkeys[LeaderID] F --> F : Check if OneTimeAddress is not included in SMTs F --> U : Transfer Staking Token ``` ## セキュリティおよび各種攻撃手法への対応まず、手数料支払を行うための6つの条件を満たしているかについて検討する。 1. InvoiceのPreimageは支払いが完了するまで判明してはいけない => Operetorが漏らさない限り、支払い完了時までPreImageは伝えられず、この点は満たしている 2. InvoiceがそのTxに対する正しいInvoiceであることはユーザーが支払うまでに検証可能でないといけない => OPSigにはOneTimeAddressが含まれているため、該当Txに対する正しいInvoiceであるかどうかは署名およびInvoiceの内容を確認することで検証できる。 3. ただしいメッセージ交換が行われている場合、オペレーターリーダーが交代するまでにすべての通信が必ず完了し、その後のメッセージはすべて無効である => オペレーターとユーザーの間のメッセージの交換はLightning Networkでの送金で最後であり、Invoiceの有効期限（すなわちリーダー交代前）までに完了する 4. オペレーターは支払いを受けたのであれば必ずTxが発行可能な状況でなければならない => 最初にTxのデータを受け取るため、支払いさえ行われれば常にTxを発行できる状態になっている 5. Txを実行しなかった場合、確実に補償を請求できる => Lightning Network支払いで得たPreImageとオペレーターの署名があり、なおかつOneTimeAddressがSMTに乗っていない（＝Txが実行されていない）場合は確実にClaimできる 6. Txを実行した場合、確実に補償を請求できない => SMTに当該OneTimeAddressが乗っているため検証が通らない。 ### その他の攻撃手法と対策 #### オペレーター側からの攻撃 - **Feeを過大に請求される** => Invoiceを確認して支払わない選択をすれば良い (ただし、正しいFeeのInvoiceがかならず請求されるわけではない) #### ユーザー側からの攻撃 - **LNの支払いをしない** => Preimageを保有していないのでProofが通らない - **Operatorが交代してから支払い、Preimageを入手しようとする** => Invoiceの有効期限が切れているのでしはらいがFailする - **リーダー交代ギリギリにユーザーが支払う** => Invoiceの有効期限に交代まで猶予のある時間を設定すれば良い - **安いtxで見積もりし安いinvoiceゲットし、別の手数料が高いtxを投げてくる** => 最初に提出したTxDataから変更ができないようにすれば良い。 - **ステーク量 >= spamにかかる手数料**が成り立つのであれば常にDoSの可能性がある - IPもバレてしまっている - 普通のブロックチェーンと違い、ブロック生成者だとバレてるのが辛い - アプリ層だけのDoSではなく、ネットワーク層でのDoSもあり得そう => 解決策 ## この方式におけるメリット - ZKEVM内と紐付かないでgasが支払われ、手数料に関してZK側で処理をおこなわないため、シンプルな実装になりConstraints数の増加も発生しない。 - User <=> Operator間の通信が増加しない - ClaimはL1チェーン上で完結するため、ZKネットワークの実装が複雑にならない ## 注意点 - リーダーの交代はあるtimestampをもってかならず交代されなければならない - OneTimeAddressは必ず使い捨てであり、それはなんらかの都合でRevertされた場合でも使用されたアドレスはその後使われない必要がある(もし使いまわしてしまうとOperatorがTxを処理しない => その後別のTxを同じOneTimeAddressで処理する状態になった場合、前者をClaimすることが不可能になる) - オペレーターの交代直前にTPSが大きく落ちるため対策が必要。 - ブロックリミットでtxがこれ以上入らないのにtxを受け取ってしまうとスラッシュされる(そもそもL2にブロックリミットはあるだろうか？) ###### tags: `Yellow paper`