# exit
###### tags: `Yellow paper` `exit`
## 1. 定義
exitとはLayer2でトラブルがあったり、何らかの理由でL1に資金を移動したい場合に行う動作のことである。本zkRollupでは、exitには２種類あり、オペレーターがexitに必要な作業を手伝ってくれるパターンと、ユーザー自身のみで行うexitである。前者は3.1.1で手法Aとして紹介し、後者は3.2.1で手法Bとして紹介する。
## 2. 前提
exitするために必要な情報は主に2つである。`EOA Uer State`と、`Last Updated Block Heights`が必要である。
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に載せておく。また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, assetPath,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を発行した回数|
|assetPath| bytes32| private| 自分の資産の場所を示すKey|
|amount| uint256| public| 自分のassetPathの資産の量|
|merkleProof| bytes| private| 自分のassetPathの資産が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がMerkleRootに含まれているかを証明する。このinclusion Proofにより、過去のブロック(pastMerkleRoot)に、自分が資産を持っていたことが証明できる。
$C_{proveUserState}((pastMerkleRoot, amount, assetPath), (userStateMerkleRoot, merkleProof)) \to \{true, false\}$
**zkp input**
| name | type | visibility| remarks |
| :--: | :--: | :--: | :--: |
| pastMerkleRoot | bytes32 | public | 過去のMerkleRoot |
|amount| uint256| public| 自分のassetPathの資産の量|
|assetPath| bytes32| public| 自分の資産の場所を示すKey|
| userStateMerkleRoot | bytes32 | private |現在のEOA User StateのMerkle Root |
|merkleProof| bytes| private| 自分のassetPathの資産が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| 自分のassetPathの資産がEOA User StateのRootに含まれていることを証明するためのProof|
この2つのProofをinputとするL1のexitコントラクトを実行するとexitが実行される。
:::warning
Recursive ZKが可能であればRecursiveした方がガス代が安くなると思います。
:::
また同じassetPathを使用したexitが2回行われることを防ぐため、`keccak256(userStateRoot, assetPath)` はL1コントラクトのmappingで管理し、同じuserStateRootとassetPathが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)
```
## MEMO
### 一生exitできないケース(?)
2で一度update stateを実行しているが、4でbobに送金しているので、6でverifyされてもaliceはブロック高16ではexitすることができない。
:::danger
もし、16ブロック目にfreeze modeになったら、aliceは**一生exitできない。**
過去のステートでexitしようとしても、4でonetime address listにリストアップされてしまうので、n + 1のonetime address listのnon inclusion proofが通らなくなってしまう。
仮にeixtすることを許してしまうと、bobへの送金とexitで二重支払いになってしまう。
**ちなみにこれはオンチェーンコミットとかプリコンセンサスは全く関係ない。普通に起こりうる事象。**
:::
```mermaid
sequenceDiagram
autonumber
10 Pre ->> 10 Pre : alice => bob
11 Pre ->> 11 Pre : alice udpate state
12 Verify ->> 12 Verify : bob => charlie
13 Pre ->> 13 Pre : alice => bob
14 Pre ->> 14 Pre : bob => charlie
15 Verify ->> 15 Verify : verify
11 Pre ->> 16 Pre : alice cannot exit
```
### ^の解決策？
オンチェーンで再帰的なzkによって検証すれば大丈夫かもしれない。
- 前提
- state diffが取得できる
- user state rootとそれを構成するleafを所持している
- 自分のuser state rootまでのProofがある
- state diffの解決を証明するzkp
- 自分の資産を証明するzkp
- onetime address listのSMTの中にアドレスがないことを証明するzkp
Sign in with Wallet
Connect another wallet