# Secret Contract ###### tags: `Yellow paper` `secret contract` 本 zkRollup により副次的にプライベートスマートコントラクトの実行が可能となる。具体的には、オペレータがトランザクションを実行する際にその署名者の情報を見る事なくそれを行う。本章ではそれを実現するための幾つかの追加のアイディアについて記述する。 ## Shared storage and asset storage シークレットコントラクトを実現するためには、ユーザの資産を扱うストレージが秘匿化されていなければならない。そのために、storage を "shared storage" と "asset storage" の二種類に分けて考える。shared storage はすべてのユーザが参照可能なステートであり、オペレータが分散ストレージを介してそのステートを保持する。 また、一般的な Ethereum 上のステートと同様にコントラクトロジックに従い誰でも閲覧/変更することができる。shared storage に保存されている state を "global state" と呼ぶ。asset storage は資産を管理するストレージである。一般に ERC20やERC721 の balanceOf が asset storage で表現される。さらに asset storage に保存されている EOA のステートを EOA user state と呼び、コントラクトのステートを CA user state と呼ぶ。EOA user state は資産の保有者のみがローカルでそのステートを保持する。CA user state は commonly shared storage と同様に一般に公開され、さらに commit 時に L1 に calldata として提出される。 CA user state のみを calldata に刻む理由はn章で説明する Exit のために必要だからである。 Global state を分散ストレージに保存していることを証明するために、複数のノードがそのストレージを保有していることの証明を提出したことをL1 に commit する再の検証条件に加える。 ### Calldata に必要な情報 | name | type | remarks | | :--: | :--: | :--: | | Root | Hash | storage 情報のルートハッシュ | | GlobalStateRoot | Hash | Global user state のルートハッシュ | | CAUserStateRoot | Hash | Contract Account user state のルートハッシュ | | EOAUserStateRoots | [address,Hash][] | 変更があった EOA user state のアドレスとルートハッシュ | | OnetimeAddressUpdates | address[] | Tx を発行した onetimeAddress のリスト | これらのストレージ情報は次項目で図示されるマークルツリーで表現される。 ## 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"] } ``` <!--使わない可能性大なので一時的コメントアウト ## Merkle Patricia Tree マークルパトリシアツリーは Ethereum で使われている状態を管理する永続木構造である。状態の検索・追加・削除がそれぞれ O(logN) で可能であり、また履歴の復元がO(1)でできる。 本 zkRollup では、マークルパトリシアツリーに入れる要素を階層的に配置する。commonly shared storage については、contract address + key を中間ノードとして value を leaf に持つ一般的な手法を使用する。しかし、asset storage については、key に必ず address を持つため、頂点から owner address を中間ノードにして辺を辿り次に contract address を中間ノードとして value を leaf に持つ。また、EOA user state については owner address をたどった時点の merkle root のみをオペレータが保有しその先はそのアドレスの保有者のみがローカルで保持する。 evm OPCODE SSTORE について Asset storage については ASSTORE を、そうでないものについては CSSTORE を使用する。 - ASLOAD : Transactor によって証明された StateValue から読み込む - ASSTORE : 返却する StateDiff に Data, ASLOAD した Value との増減値 - CSSTORE : SSTORE と同様 - CSLOAD : SLOAD と同様 https://takenobu-hs.github.io/downloads/ethereum_evm_illustrated.pdf Storage [Key 1, Value1] = [256 bits, 256 bits] asset storage として宣言されたものについては User state = Address →(account state) -> [contract address + contract 内で宣言された順番] → value. の順で Tree に配置する。 検証のzkProve 作成コスト削減のため👇を使用する。 https://vitalik.ca/general/2021/06/18/verkle.html */ --> ### Transaction シークレットコントラクトを実現するトランザクションを実現するためにはその発信者を特定できなくする必要がある。例えば、ERC20 においてある署名者の権限で操作を行った残高がその署名者の残高であることは Allowance などのを使用しない限り明白である。次のように、トランザクションを構成することによってオペレータが署名者やアドレスの情報無しにコントラクトを実行することができる。 | name | << | << | type | remarks | | :--: | :--: | :--: | :--: | :-- | | User | | | | | | | public_key | | bytes | ユーザの公開鍵 | | | private_key | | bytes | ユーザの秘密鍵 | | | nonce | | uint256 | メッセージの再送を防ぐための Nonce, トランザクションを実行するたび各ユーザごとに increment する | | Latest Trees | | | | onetimeAddress の最終更新履歴を示すSMTと全体のステートの Verkle Tree | | SignedTransaction | | | | | | | TransactionPayload | | | Contract address | address | 実行したいコントラクトアドレスを指定する | | | | Data | bytes | コントラクトアドレスに呼び出し関数とその引数の情報 | | | | Onetime address | address | 秘密鍵とnonceから一意に生成されるワンタイムアドレス。<br />秘密鍵の保有者のみが自分のワンタイムアドレスであることがわかる。<br />`Hash((secretKey, nonce)) ⇒ prefix 20byte` <br /> | | | | User state value | map(bytes => bytes) | [contract address + contract 内で宣言された index] => value となるようなの Trie 辺のリスト | | | | User state zk proof | Hash | そのコントラクトを実行するために必要な asset storage の value について、その資産の保有者の名前無しで asset の値が value 以上であることを証明する。 <br /> $$ C_{proveUserStateValue}((userStateValue, onetimeAddress, latestTreeRoots),\\ (userStateProof, user)) \to \{true,false\}$$<br /> $$ zkProve((userStateValue, onetimeAddress, latestTreeRoots),\\ (userStateProof, user), C_{proveUserStateValue}) \to zkProof_{proveUserStateValue}$$<br />ここで、Cは userStateProof からその user が確かに userStateValue と同等の value を保有している時 true を返す回路<br />さらに、Cは onetimeAddress が secretKey と nonce から導かれるアドレスであることも検証する。<br />userStateValue は asset storage の user 情報を含まない<br />- 例<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 をユーザの秘密鍵で署名したもの | | SignedTransactionZKP | | | Hash | 上記の署名済みの valid なトランザクションを署名者の情報無しに証明する。<br /> $$C_{verifySignedTx}((txHash,onetimeAddress),(publicKey, signature)) \to \{true,false\}$$<br />$$zkProve((txHash,onetimeAddress), (publicKey, signature), C_{verifySignedTx}) \to zkProof_{verifySignedTx}$$<br />ここでのCは txHash の signature が publicKey が検証できるか否かの真偽値を返す回路。| 上記構造では簡略化のため、ガスに関連する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 と一致するか検証 ### Client algorithm ```python= def make_tx(user, contract_address, data): onetime_address = make_ontime_address(user) # fetch latest trees from operator. trees include state tree and address tress. trees = operator.fetch_latest_trees() user_state_proof = make_user_state_proof(user, trees.state_tree) user_state_value = make_user_state_value(contract_address, data) zk_proof = zk_prove((user_state_value, onetime_address, trees), (user_state_proof, user), prove_user_state_diff) tx_payload = { contract_address, data, nonce: user.nonce, onetime_address, user_state_value, user_state_zk_proof: zk_proof, } tx_hash = Hash(tx_payload) signature = user.sign(tx_hash) signed_zkp = zk_prove((tx_hash, onetime_address), (user.public_key, signature, user.secret_key, user.nonce), verify_signed_tx) return (tx_payload, signed_zkp) def make_ontime_address(user): onetime_address = Hash(user.secret_key, user.nonce).prefix(20) return onetime_address def make_user_state_proof(user, tree): return tree.make_proof(user.address. user.state_tree.root) def make_user_state_value(contract_address, data): contract = operator.fetch_contract(contract_address) # simulate contract and build state_value return client.zkEVM.make_state_value(contract, data) def circuit prove_user_state_diff( (user_state_value, onetime_address, trees), (user_state_proof, user)): if user.nonce == 0: and not verify_used_onetime_address(onetime_address, trees.address_tree, user) and not verify_resolve_previous_diff(user): return false if not verify_onetime_address(onetime_address, user): return false return verify_user_state_value(user_state_proof, trees.state_tree, user) def circuit verify_used_onetime_address(onetime_address, address_tree, user): prev_onetime_address = Hash(user.secret_key, user.nonce - 1).preifx(20) prev_proof = address_tree.inclusion_proof(prev_onetime_address) current_non_proof = address_tree.non_inclusion_proof(onetime_address) return address_tree.verify(prev_proof) and address_tree.verify(current_non_proof) def circuit verify_resolve_diff(user): prev_onetime_address = Hash(user.secret_key, user.nonce - 1).preifx(20) if not user.prev_state_diff.address == prev_ontime_address: return False diff_proof = user.diff_STM.inclusion_proof(user.prev_state_diff) state_proof = user.state_tree.inclusion_proof(user.diff_STM.root)) return user.diff_SMT.verify(diff_proof) and user.state_tree.verify(state_proof) def circuit verify_onetime_address(onetime_address, user): return onetime_address == Hash(user.secret_key, user.nonce).prefix(20) def circuit verify_user_state_value(user_state_proof, tree, user): value_proofs = user_state_proof.inclusion_proofs(user_state_values) return user_state_proof.verify(value_proofs) and tree.verify(user_state_proof) def circuit verify_signed_tx((tx_hash, onetime_address), (public_key, signature, private_key, nonce)): if onetime_address == Hash(privateKey, nonce).prefix(20): # standart function of verify signature from pubkey, sign and message. return verify_signature(public_key, signature, tx_hash) return False ``` ### オペレータの検証 - 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 を計算する ### Client algorithm ```python= def merge_state_diff(user, state_diff): # fetch latest state tree from operator latest_trees = operator.fetch_latest_trees() state_tree = latest_trees.state_tree diff_tree = latest_trees.diff_tree diff_proof = diff_tree.inclusion_proof(state_diff) current_user_state_root = user.state_tree.root current_user_state_proof = tree.make_proof(user.state_tree.root) new_user_state = user.state_tree.merge(state_diff) zk_proof = zk_prove((user.address, new_user_state.root, diff_tree.root), (user.state_tree, state_diff, diff_proof), verify_merge_state_diff) return (zk_proof, current_user_state_proof, new_user_state.root) def circuit verify_merge_state_diff( (user_address, new_user_state_root, diff_root), (user_state, state_diff, diff_proof)): proof = user_state.diff_SMT.non_inclusion_proof(state_diff.tx_hash) # `inclusion_verify` means check diff_root includes state_diff if not inclusion_verify(diff_root, state_diff): return False # `generate_public_key` means generate public key from secrete key if not generate_public_key(user_state.secret_key).prefix(20): return False if not state_diff.target_address == Hash(user_state.secret_key).prefix(20): return False if not user_state.verify(proof) return False new_diff_smt_root = user_state.diff_SMT.insert(state_diff) user_state = user_state.upsert("diff", new_diff_smt_root) user_state = user_state.merge(state_diff) return user_state.root == new_root ``` #### 返り値 - currentUserStateRoot - 反映前のユーザーマークルルート - byte32 - currentUserStateProof - ユーザ root hash より上についての sibiling - [ Sibling node hash ] = [ byte32 ] ### オペレータの検証 - currentUserStateProof で用いられる rootHash が最新の StateDiff が適用されたものであることを検証 - 用いれた rootHash 以降に変更を要求したユーザの merkle root が変更されていないかをチェック(Exit tree 参照) - diffRoot が過去存在していたことを検証 - 上記の zkProof を検証 ```mermaid sequenceDiagram actor U as User participant O as Operator autonumber O ->> U : returnUserStateDiff(stateDiff) U ->> U : mergeStateDiff(stateDiff) U ->> O : submitUserState(zkProof, currentUserStateProof, newUserStateRoot, diffRoot) O ->> O : verifyZKProof(zkProof) O ->> O : verifyValidRootHash(currentUserStateProof, difffRoot) O ->> O : mergeUserStateDiff(newUserStateRoot) O ->> U : Response: result ```