# (こちらは一旦停止)IntMax1.0: Yellow Paper 全体 日本語
## 〜最もスケーラブルなzkRollupアルゴリズム〜
# 1) Oprator Node Spec
###### tags: `Yellow paper` `オペレータノード`
### 概要
SRUネットワークで動作するオペレータの処理を記載する。
### ガス見積もりとTx送信API
オペレータは、ユーザからのSignedTransactionZKPとTxPayloadを受け取りTxのGasを見積もる。Transactionの検証後に、lnのinvoiceを返却する。
#### POST `sru_estimateGas`
応答時間 300ms
#### Example
```bash
curl -X POST --data '{"jsonrpc":"1.0","method":"sru_estimateGas","params":[{see above}],"id":1}'
// Result
{
"id":1,
"jsonrpc": "1.0",
"gas": 2000000,
"invoice": "0x302038aeb0400...",
"opsig": "0x2948040..."
}
```
**TxPayloadインターフェイス**
| Field | Type | Value |
| --------------- | --- | ------------------------------------------------------------------------------------------------------------------------------------------------ |
| to | address | 実行したいコントラクトアドレスを指定する |
| data | bytes | コントラクトアドレスに呼び出し関数とその引数の情報 |
| nonce | uint | メッセージの再送を防ぐための Nonce, トランザクションを実行するたび各ユーザごとに increment する |
| from | address | 秘密鍵とnonceから一意に生成されるワンタイムアドレス |
| userStateValue | uint256 | [contract address + contract 内で宣言された index] => value となるような [bytes32] |
| zkProof | bytes | そのコントラクトを実行するために必要な asset storage の value について、その資産の保有者の名前無しで asset の値が value 以上であることを証明する |
**GetReceiptResponseインターフェイス**
| Field | Type | Value |
| ------- | ------- | ------------------------------------------------- |
| gas | uint256 | txにかかるgas代 |
| invoice | bytes | lnのinvoice |
| opsig | bytes32 | Sig(Hash(Prefix + Hash(invoice) + OneTimeAddress) |
**errorオブジェクトのインターフェイス**
| Field | Type | Value |
| ------- | --- | ------------------------------------------------ |
| message | string | エラーメッセージ |
| code | int | 発生したエラーに対応するエラーコード |
| data | map | それぞれのエラーごとに任意のオブジェクトを入れる |
**詳細フロー**
- OPSIG = Operator's Signature
1. オペレータは、Transactionを実行したいユーザからSignedTransactionZKPとTxPayloadを受け取る。
2. オペレータは、受け取ったTransactionの有効性を検証する。
3. オペレーターはGasを見積もり、LNのinvoiceを作成する。
4. オペレーターは`Hash(Prefix + Hash(invoice) + OneTimeAddress)`に署名する(OPSIG)。
6. オペレーターは、Pending状態でTransactionをTransaction Poolに保存する。
7. オペレーターは、レスポンスとしてGasのinvoiceとOPSIGを返す。
```mermaid
sequenceDiagram
actor U as User
participant O as Operator
autonumber
U ->> O : sendSignedTransaction(signedTransactionZKP, txPayload)
O ->> O : zkVerify(signedTransactionZKP, zkProof)
O ->> O : estimateGas(txPayload)
O ->> O : makeInvoice(OneTimeAddress)
O ->> O : sign(Hash(Prefix + Hash(invoice) + OneTimeAddress))
O ->> O : saveToTransactionPool(transaction)
O ->> U : Response: EstimateGasResult
```
### UserStateProof要求API
ExitのためにはuserStateRootがRootに含まれていることを証明する必要がある。そのためuserStateRootからMerkle Proofを取得するAPIを提供する。
### POST `sru_getUserStateProof`
応答時間 100ms
#### Example
```bash
curl -X POST --data '{"jsonrpc":"1.0","method":"sru_getUserStateProof","params":[{see above}],"id":1}'
// Result
{
"id":1,
"jsonrpc": "1.0",
"blockNumber": "20000",
"userStateProof" "0xe670ec64341771606e5....."
}
```
**GetUserStateProofPayloadインターフェイス**
| Field | Type | Value |
| ------------- | ------- | ------------------------ |
| userStateRoot | bytes32 | userStateProofのrootのhash |
**GetUserStateResponseインターフェイス**
| Field | Type | Value |
| -------------- | ------- | ----------------------- |
| blockNumber | uint256 | そのルートが更新されたblock高 |
| userStateProof | bytes | userStateのmerkle proof |
**errorオブジェクトのインターフェイス**
| Field | Type | Value |
| ------- | --- | ------------------------------------------------ |
| message | string | エラーメッセージ |
| code | int | 発生したエラーに対応するエラーコード |
| data | map | それぞれのエラーごとに任意のオブジェクトを入れる |
**シーケンス図**
```mermaid
sequenceDiagram
actor U as User
participant O as Operator
autonumber
U ->> O : GetUserStateProof(stateRoot)
O ->> U : Response: userStateProof
```
### stateDiff要求 API
stateDiffを取得するためのAPI。stateDiffはトークンを受け取ったり、user stateを変更するときに呼び出す必要がある。
### POST `sru_getStateDiff`
応答時間 300ms
#### Example
```bash
curl -X POST --data '{"jsonrpc":"1.0","method":"sru_getStateDiff","params":[{see above}],"id":1}'
// Result
{
"id":1,
"jsonrpc": "1.0",
"stateDiffs": {
// txHash
"0x203999eeab490..": {
"blockNumber": 30000,
// contract Address:
"0x32ead08d9b9...": [{
// bytes32
"data": "0xae93848298479..."
// int256
"value": "1384000000",
// bytes32
"keyHashed": "0x338839..."
},
...
]
}
...
}
}
```
**GetStateDiffPayloadインターフェイス**
txHash, addressのどちらか必須。
| Field | Type | Value |
| --------------- | --- | ------------------------------------------------------------------------------------------------------------------------------------------------ |
| txHash | bytes32 | stateDiffが欲しいtxのhash。|
| address | address | receiverアドレス。|
**GetStateDiffResponseインターフェイス**
| Field | Type | Value |
| ---------- | ------------------- | -------------- |
| stateDiffs | {txHash: stateDiff} | StateDiffのMap |
**StateDiffインターフェイス**
| Field | Type | Value |
| -------------- | ------------------- | -------------------- |
| blockNumber | uint256 | block高 |
| contractValues | {address: assetValues[]} | コントラクトごとの値 |
**AssetValuesインターフェイス**
| Field | Type | Value |
| ----- | ------- | -------------------- |
| data | bytes32 | 付随するデータ |
| value | bytes32 | コントラクトごとの値 |
| keyHashed | bytes32 | どの場所の値なのかというkey。 |
**errorオブジェクトのインターフェイス**
| Field | Type | Value |
| ------- | --- | ------------------------------------------------ |
| message | string | エラーメッセージ |
| code | int | 発生したエラーに対応するエラーコード |
| data | map | それぞれのエラーごとに任意のオブジェクトを入れる |
**シーケンス図**
```mermaid
sequenceDiagram
actor U as User
participant O as Operator
autonumber
U ->> O : getStateDiffs(txHash or address)
O ->> U : Response: stateDiffs
```
### L1コミットするために複数のTransactionをまとめる(Rollup)
オペレータは、複数のTransactionをまとめる(Rollupする)。
オペレータは、6時間ごとに前回rollupしたブロックに含まれる最後のブロックナンバーを渡しそれ以降に作成されたブロックのコミットデータを分散ストレージから取得する。
1. オペレータは、Transaction Poolから取得した全てのTransactionを検証する。
3. オペレータは、コミットデータから取得した全てのTransactionの有効性をZKによる検証によって行う。
4. オペレータは、検証後にTransactionをまとめてRollupする。
5. オペレータは、RollupしたTransactionを分散ストレージ上に送信し保存する。
6. 分散ストレージをポーリングしている外部の高い計算リソースを持ったサーバは、新しいRollupしたTransactionが分散ストレージに追加されると、それを取得する。
7. 外部の高い計算リソースを持ったサーバは、Rollupに取り込まれた全てのTransactionの有効性をZKによる検証によって確かめたというProofを作成する。
8. 外部の高い計算リソースサーバは続けて、作成したProofをOperatorに渡す。
9. Operatorは受け取ったProofを元に、Rollup TransactionをL1ブロックチェーンのSRUスマートコントラクトに投げ、Transactionハッシュを受け取る。
10. Operatorは、投げたTransactionのstatusのconfirm処理を行う。
**Transactionが不正な場合**
- どうする？除いて登録でいいのか。
```mermaid
sequenceDiagram
participant O as Operator
participant D as Distribute Storage
participant P as Prover
participant L as L1 Contract
autonumber
O ->> O : fetchCommits(prevBlockNumber)
O ->> O : verify(transacitons)
O ->> O : zkVerify(trasactions)
O ->> O : rollup(transactions)
O ->> D : saveRollupTransaction(rollupTransaction)
D ->> O : Response: rollupTransaction
O ->> P : requestMakeProof()
P ->> P : createProof(rollupTransaction)
P ->> O : sendProof(zkProof)
O ->> L : sendTrancaction(rollupTransaction, zkProof)
L ->> O : Response: transctionHash
O ->> L : confirmTransaction(transctionHash)
```
**RollupTrasactionのインターフェイス**
| Field | Type | Value |
| ------------ | --- | -------------------------------- |
| transactions | bytes | 対応するTransactionとProofの配列 |
### コントラクト実行時の返り値を返却する
オペレータは、ユーザが実行したSRUネットワーク上にデプロイされたコントラクトの関数の返り値を返却する。
**フロー**
- ユーザは、オペレータに実行したいコントラクトの関数を投げる。
- オペレータは、コントラクトの関数を実行する。
- オペレータは、取得した値をユーザに返却する。
#### POST `sru_call`
```bash
// Request
curl -X POST --data '{"jsonrpc":"1.0","method":"sru_call","params":[{see above}],"id":1}'
// Result
{
"id":1,
"jsonrpc": "1.0",
"result": "0x"
}
```
**Paramsインターフェイス**
| Field | Type | Value |
| --------------- | ------- | ------------------------------------------------------------------------------------------------------------------------------------------------ |
| from | address | 呼び出す人のアドレス|
| to | address | 実行したいコントラクトアドレスを指定する |
| Data | bytes | コントラクトアドレスに呼び出し関数とその引数の情報 |
**エラーが発生した場合**
コントラクト関数の実行時にエラーが起きた場合は、errorオブジェクトを返却する。
**errorオブジェクトのインターフェイス**
| Field | Type | Value |
| ------- | --- | ------------------------------------------------ |
| message | string | エラーメッセージ |
| code | int | 発生したエラーに対応するエラーコード |
| data | map | それぞれのエラーごとに任意のオブジェクトを入れる |
**シーケンス図**
```mermaid
sequenceDiagram
actor U as User
participant O as Operator
autonumber
U ->> O : callContractMethod(params)
O ->> O : callContractMethod(params)
O ->> U : Response: result
```
params: 実行したいコントラクトの関数に渡す引数
result: 実行したコントラクトの関数の返り値
# プリコミットメント
###### tags: `Yellow paper`
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することができる。
### メインコミットされればそれ以降exitできるケース
aliceは12ブロック以降state更新をしなければいつでもexitできる。bobはupdate stateを実行してないのでexitできない。
```mermaid
sequenceDiagram
autonumber
10 Pre ->> 10 Pre : alice => bob
11 Pre ->> 11 Pre : alice udpate state
11 Pre ->> 11 Pre : bob udpate state
12 Main ->> 12 Main : bob => charlie
13 Pre ->> 13 Pre : alice can exit
13 Pre ->> 13 Pre : bob cannot exit
```
# 3) Secret Smart 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 に刻む理由は4章で説明する 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 のアドレスとルートハッシュ |
| OneTimeAddressListRoot | Hash | 変更があった OnetimeAddress のSMTのルートハッシュ |
| StateDiffRoot | Hash | StateDiffのSMTのルートハッシュ |
| 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
```
### 通信プロトコルのシーケンス図
###### tags: `Yellow paper` `通信プロトコル`
### ユーザとオペレーター間通信
#### Transfer
```mermaid
sequenceDiagram
actor T as Transactor
participant O as Operator
participant P as Prover
participant L as L1 Contract
autonumber
T ->> T : zkp(verifyuserStateValue)
T ->> T : zkp(verifySignedTx)
T ->> O : transfer(zkp, tx)
O ->> O : verify(zkp)
O ->> O : aggregate tx
O ->> O : state change
P ->> O : get zkp input
O ->> P : zkp input
P ->> O: zkp(state)
O ->> L : commit block
```
#### Update User State Diff
```mermaid
sequenceDiagram
actor T as Transactor
participant O as Operator
participant P as Prover
participant L as L1 Contract
autonumber
T ->> T : zkp(verifyUpdateStateDiff)
T ->> O : updateUserStateDiff(zkp, newUserMerkleRoot)
O ->> O : verify(zkp)
O ->> O : aggregate tx
O ->> O : state change
P ->> O : get zkp input
O ->> P : zkp input
P ->> O: zkp(state)
O ->> L : commit block
```
#### Exit(normarl mode)
```mermaid
sequenceDiagram
actor T as Transactor
participant O as Operator
participant P as Prover
participant L as L1 Contract
autonumber
T -> T : zkp(proveUserStateChange)
T ->> O : exit(zkp)
O ->> O : verify(zkp)
O ->> O : aggregate tx
O ->> O : state change
P ->> O : get zkp input
O ->> P : zkp input
P ->> O: zkp(state)
O ->> L : commit block
L ->> T : transfer assets
```
#### ユーザーとL1ブロックチェーン間通信
#### Exit(freeze mode)
```mermaid
sequenceDiagram
actor T as Transactor
participant L as L1 Contract
autonumber
L ->> L : freeze mode
T ->> T : zkp(proveUserStateChange)
T ->> T : zkp(proveNoUpdateUserState)
T ->> L : exit(zkp)
L ->> T : transfer assets
```
## 4) Exit Safety Mechanism Spec
###### tags: `Yellow paper` `exit`
## 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を発行した回数|
|assetPkeyHashedath| 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がMerkleRootに含まれていことを証明する。このinclusion Proofにより、過去のブロック(pastMerkleRoot)に、自分が資産を持っていたことが証明できる。
$C_{proveUserState}((pastMerkleRoot, amount, keyHashed), (userStateMerkleRoot, merkleProof)) \to \{true, false\}$
**zkp input**
| name | type | visibility| remarks |
| :--: | :--: | :--: | :--: |
| pastMerkleRoot | bytes32 | public | 過去のMerkleRoot |
|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が実行される。
:::warning
Recursive ZKが可能であればRecursiveした方がガス代が安くなると思います。
:::
また同じ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)
```
# 分散ストレージ
###### tags: `Yellow paper` `分散ストレージ`
### 概要
SRUネットワークで必要なデータは、分散ストレージを利用し保存する。
### 分散ストレージとは
分散ストレージとは、複数のサーバがネットワークを経由してデータを分散し保存・共有しつつ処理することができる分散システムのことである。クライアントからは、データを透過的に利用することができる。
従来のデータストレージでは、セキュリティやパフォーマンスを保ったままのストレージのスケーリングが難しく、増え続けるデータに対し迅速に対応することに課題があった。
一方分散ストレージでは、データをサーバ間で分散して保持することができ、データが過大になった場合でも、シームレスにスケーリングすることができる。また単一障害点を回避する用途としても有用であり、高可用性と信頼性を必要とするシステムに向いている。
### 分散ストレージの使用背景と動機
SRUネットワークの高可用性と信頼性が、ネットワークを使用するサービスの全体に影響する、SRUネットワークは、一時もシステムが停止することなく正常に稼働する必要がある。SRUネットワーク上で増え続けるデータ需要に対し、パフォーマンスとセキュリティを保ったままスケーリングすることが求められる。
また、一度データが消失するとユーザの資産やサービスの資産の消失に繋がるため、安全で破損していないデータの提供を担保する必要があるため分散ストレージをデータの保存場所として使用する。
### 分散ストレージに保存するデータ種別
分散ストレージ上で保存するデータに関して、以下の4種類がある。それぞれのデータの特徴と保存期間は以下の通りである。
#### Proof
ゼロ知識証明用のproofデータを扱う。分散ストレージにアップロード後、1日間保存する。
`Proof`
| field | type | description |
| -------- | -------- | -------- |
| zkProof | `ZkProof` | zkVerify用のProof |
| publicInput | `PublicInput` | zkVerify用のPublicInput |
`ZkProof`
ゼロ知識証明用のProofのインターフェイスに沿う。
`PublicInput`
| filed | type | description |
| -------- | -------- | -------- |
| currentUserMerkleRoot | bytes32 | 反映前のユーザのマークルルート |
| currentUserStateProof | bytes32[] | ユーザのrootHashより上についてのsibiling |
| currentUserStateRoot | bytes32 | 反映後のユーザのマークルルート |
ex.
```
{
proof: {
zkProof: { x... },
publicInput: {
currentUserMerkleRoot: '0xe51feeeefd14f6876839129c74b73fc1f79701d2e3b65f099e875b9e64cf59f4',
currentUserStateProof: [
'0xe51feeeefd14f6876839129c74b73fc1f79701d2e3b65f099e875b9e64cf59f4',
'0xe51feeeefd14f6876839129c74b73fc1f79701d2e3b65f099e875b9e64cf59f4',
...
],
currentUserStateProof: '0xe51feeeefd14f6876839129c74b73fc1f79701d2e3b65f099e875b9e64cf59f4'
}
}
}
```
#### Commit
ブロック内のトランザクションによるストレージの差分情報を扱う。分散ストレージにアップロード後、7日間保存する。
#### OnetimeUserState
AssetStorageとして保持されている。SRUネットワーク上のユーザ資産を扱う。分散ストレージにアップロード後、永続保存する。このOnetimeUserStateを扱うユーザがマージを行うと消える。
```
[
('Contract Address + その contract 内で宣言された変数のindex', diff),
('Contract Address + その contract 内で宣言された変数のindex', diff)
]
```
## BackupUserState
AssetStorageに保存されているSRUネットワーク上のユーザ資産を扱う。通常の利用用途はないが、ユーザ自身がローカルのウォレットにバックアップしているEOAUserStateを失った場合備え、バックアップとして暗号化し分散ストレージ上に保存しておく。分散ストレージにアップロード後、EOAUserStateが更新がされるまで永続保存する。各ユーザが自身のEOAUserStateを更新する際に、分散ストレージ上のBackupUserStateも同様に更新する。
EOAUserStateはLeafにkeyをOwnerAddress、valueをContractAddressとそのコントラクトでの変数の定義位置を連結したハッシュ化したものを持つツリー構造であり、ツリーをそのまま分散ストレージに保存する。また外部分散ストレージへのコンテンツ識別子(CID)をローカルのデータベースに保存する。
オペレータのローカルのデータベースに保存するUserAddressと、バックアップ用として保存した外部分散ストレージのCIDのKey、Valueストア
| Key | Value |
| -------- | -------- |
| UserAddress(ユーザのアドレス) | CID(コンテンツ識別子) |
ex.
```
key: 0x65172bcb948583b197ca608d33f96d5ce35cb1def0a9c73bcf42aaf1dd972b55
value: QmbWqxBEKC3P8tqsKc98xmWNzrzDtRLMiMPL8wBuTGsMnR
```
#### GlobalState
CommonlySharedStorageに保存されている。SRUネットワーク上にデプロイされたコントラクトの状態を扱う。分散ストレージにアップロード後、永続的に保存する。GlobalUserStateはLeafにkeyをContractAddressとそのコントラクトでの変数の定義位置を連結したハッシュ化し、valueにbytes32のデータを持つツリー構造であり、ツリーをそのまま分散ストレージに保存する。また外部分散ストレージへのコンテンツ識別子(CID)をローカルのデータベースに保存する。
オペレータのローカルのデータベースに保存するBlockNumberとGlobalStateのKey, Valueストア
| Key | Value |
| -------- | -------- |
| BlockNumber | GlobalState |
```
key: 27017
value: GlobalState
```
オペレータのローカルのデータベースに保存するBlockNumberと、バックアップ用として保存した外部分散ストレージのCIDのKey、Valueストア
| Key | Value |
| -------- | -------- |
| BlockNumber | CID(コンテンツ識別子) |
ex.
```
key: 27017
value: QmbWqxBEKC3P8tqsKc98xmWNzrzDtRLMiMPL8wBuTGsMnR
```
### バックアップ用の外部分散ストレージへの保存とコンテンツ識別子
外部分散ストレージのGateway用に構築したノードを通して外部分散ストレージへのアップロードおよびダウンロードを行う。各オペレータは、外部分散ストレージへの保存したデータへのコンテンツ識別子(CID)をローカルのデータベースに保存する。永続的に保存するデータのみ、バックアップとして外部の分散ストレージ上に保存する。
### Verkle Treeによる分散ストレージの作成
オペレーター同士のストレージデータの同期時に、それぞれのオペレータのストレージに保存されている最新のBlockNumberを送信し合う。お互いどちらも持っている最新のBlockNumberのVerkle Treeで検証を開始する。以降Verkle Treeはどちらも持っている最新のものを指す。
Verkle Tree内からお互いにランダムに選択したリーフの値に対する、Proofを要求する。オペレータは、それぞれProofを受け取り検証を行う。お互いのProofの検証が正しい場合は、データの同期を行う。これによって、全てのオペレータノードが正しい同一のデータを持つことを担保した分散ストレージが作成できる。
```mermaid
sequenceDiagram
participant O1 as Operator1
participant O2 as Operator2
autonumber
O1 ->> O2 : checkCurrentBlockNumber()
O2 ->> O1 : Response: BlockNUmber
O1 ->> O2 : requestProof(leafData)
O2 ->> O1 : Response: Proof
O1 ->> O1 : verify(proof)
O2 ->> O1 : requestProof(leafNumber)
O1 ->> O2 : Response: Proof
O2 ->> O2 : verify(proof)
O1 ->> O2 : Sync(Array<leafData>)
O2 ->> O1 : Sync(Array<leafData>)
```
### 各種データ管理サービスクラスについて
それぞれのデータ種別ごとに、サービスクラスを作成する。それぞれのデータを管理するプログラムのことを便宜上サービスクラスと呼ぶ。SRUネットワークのbootstrap時にサービスクラスを初期化およびセットアップする。もしsnapshotから起動する場合は、セットアップ時にsnapshotのデータを読み込ませるためにsnapshotのデータを各サービスクラスに渡すこととする。
**errorオブジェクトのインターフェイス**
| Field | Value |
| -------- | -------- |
| message | エラーメッセージ |
| code | 発生したエラーに対応するエラーコード |
| data | それぞれのエラーごとに任意のオブジェクトを入れる |
## Proof service class
Proofを管理するサービスクラスである。
| 項目 | 値 |
| -------- | -------- |
| 保存期間 | 1日 |
#### データ構造
ローカルDBに保存している、blockNumberと対応するTxProofのKey, Valueデータ
| Key | Value |
| -------- | -------- |
| BlockNumber | TxProof |
ブロックナンバーと対応するTxProofのMapデータ
`TxProof`
```
Array<transactionHash, Proof>
```
> 備考として、CommitデータごとにTransactionに対応するProof一覧を取得する。
#### getProof(blockNumber: Int): `Array<TxProof>`
blockNumberを元に、TxProofをストレージから返却する。blockNumberに対応するTxProofがない場合は、エラータイプおよびエラーメッセージを返却する。
**ユースケース**
オペレータがTransactionをRollup時に、分散ストレージからblockNumberを元にProofを取得する。
**シーケンス図**
```mermaid
sequenceDiagram
participant O as Operator
participant D as Distribute Storage
autonumber
O ->> D : getProof(blockNumber)
D ->> O : Response: Array<TxProof>
```
#### saveProof(blockNumber: Int, proofs: `Array<TxProof>`): `Array<TxProof>`
対応するblockNumberとTxProofを渡しデータをストレージに保存する。ストレージの最新blockNumberがincrementされるようなIntのリクエストデータのみ受け付ける。レスポンスとして受け付けたTxProofを返却する。エラーが発生した場合は、エラータイプおよびエラーメッセージを返却する。
**ユースケース**
オペレータがオフチェーンコミット時に、ブロックに含まれるTransactionHashと対応するProofを分散ストレージに送信し保存する。
**シーケンス図**
```mermaid
sequenceDiagram
participant O as Operator
participant D as Distribute Storage
autonumber
O ->> D : saveProof(blockNumber, Array<TxProof>)
D ->> O : Response: Array<TxProof>
```
#### onDelete(blockNumber: Int)
publisherからのイベントをサブスクライブし、blockNumberを元にProofをローカルDBから削除する。エラーが発生した場合は、エラータイプおよびエラーメッセージを返却する。
**ユースケース**
DeletePublisherが、Proofを分散ストレージに保存してから1日後にProof Service Classに削除イベントをPublishする。
**シーケンス図**
```mermaid
sequenceDiagram
participant O1 as Operator(DeletePublisher service class)
participant O2 as Operator(Proof service class)
autonumber
O1 ->> O2 : emit("deleteProof", blockNumber)
O2 ->> O2 : onDelete(blockNumber)
```
#### Commit service class
Commitを管理するサービスクラスである。
| 項目 | 値 |
| -------- | -------- |
| 保存期間 | 7日 |
#### データ構造
ローカルDBに保存しているblockNumberと対応するCommitのKey、Valueデータ
| Key | Value |
| -------- | -------- |
| BlockNumber | Commit |
#### getCommits(prevBlockNumber: Int): `Array<Commit>`
prevBlockNumberから最新のblockNumber間での間の全てのCommitをストレージから返却する。
**ユースケース**
オペレータがTransactionをRollup時に、分散ストレージからCommitを取得する。
**シーケンス図**
```mermaid
sequenceDiagram
participant O as Operator
participant D as Distribute Storage
autonumber
O ->> D : getCommits(prevBlockNumber)
D ->> O : Response: Array<Commit>
```
#### getLatestCommit(): Commit
最新のCommitを返却する。初期化後に最新のCommitがまだ保存されていない場合は、エラータイプおよびエラーメッセージを返却する。
**ユースケース**
オペレータがオフチェーンコミット時に、最新のCommitを分散ストレージから取得する。
**シーケンス図**
```mermaid
sequenceDiagram
participant O as Operator
participant D as Distribute Storage
autonumber
O ->> D : getLatestCommit()
D ->> O : Response: Commit
```
### saveCommit(blockNumber: Int, commit: Commit): Commit
対応するblockNumberとCommitを渡しデータをストレージに保存する。ストレージ上の最新blockNumberがincrementされるようなIntのリクエストデータのみ受け付ける。レスポンスとして受け付けたCommitを返却する。エラーが発生した場合は、エラータイプおよびエラーメッセージを返却する。
**ユースケース**
オペレータがブロックを作成時に、分散ストレージにCommitを送信し保存する。
**シーケンス図**
```mermaid
sequenceDiagram
participant O as Operator
participant D as Distribute Storage
autonumber
O ->> D : saveProof(blockNumber, Commit)
D ->> O : Response: Commit
```
### onDelete(blockNumber: Int)
publisherからのイベントをサブスクライブし、blockNumberを元にCommitをローカルDBから削除する。エラーが発生した場合は、エラータイプおよびエラーメッセージを返却する。
**ユースケース**
DeletePublisherが、Commitを分散ストレージに保存してから7日後にCommit Service Classに削除イベントをPublishする。
**シーケンス図**
```mermaid
sequenceDiagram
participant O1 as Distribute Storage(DeletePublisher service class)
participant O2 as Distribute Storage(Commit service class)
autonumber
O1 ->> O2 : emit("deleteCommit", blockNumber)
O2 ->> O2 : onDelete(blockNumber)
```
### OnetimeUserState service class
OnetimeUserStateを管理するサービスクラスである。
| 項目 | 値 |
| -------- | -------- |
| 保存期間 | 永続 |
#### データ構造
ローカルDBに保存している、blockNumberと対応するOnetimeUserStateのKey, Valueデータ
| Key | Value |
| -------- | -------- |
| onetimeAddress | OnetimeUserState |
#### getOnetimeUserState(onetimeAddress: String): OnetimeUserState
onetimeAddressを元に、対応するOnetimeUserStateをストレージから返却する。blockNumberに対応するデータがない場合は、エラータイプおよびエラーメッセージを返却する。
**シーケンス図**
```mermaid
sequenceDiagram
participant O as Operator
participant D as Distribute Storage
autonumber
O ->> D : getOnetimeUserState(onetimeAddress)
D ->> O : Response: OnetimeUserState
```
#### saveOnetimeUserState(onetimeAddress: String, onetimeUserState: OnetimeUserState): OnetimeUserState
対応するblockNumberとOneTimeUserStateを渡しデータをストレージに保存する。ストレージの最新blockNumberがincrementされるようなIntのリクエストデータのみ受け付ける。レスポンスとして受け付けたにOneTimeUserStateを返却する。エラーが発生した場合は、エラータイプおよびエラーメッセージを返却する。
**ユースケース**
オペレータがオフチェーンコミット時に、userStateが変更になった場合にonetimeAddressごとに対応するOnetimeUserStateを分散ストレージに送信し保存する。
**シーケンス図**
```mermaid
sequenceDiagram
participant O as Operator
participant D as Distribute Storage
autonumber
O ->> D : saveOnetimeUserState(onetimeAddress, OnetimeUserState)
D ->> O : Response: OnetimeUserState
```
### BackupUserState service class
BackupUserStateを管理するサービスクラスである。
| 項目 | 値 |
| -------- | -------- |
| 保存期間 | 永続 |
### データ構造
ローカルDBに保存しているuserAddressと対応するBackupUserStateのKey、Valueデータ
| Key | Value |
| -------- | -------- |
| userAddress | BackupUserState |
### getBackupUserState(userAddress: String): BackupUserState
userAddressを元に、対応するBackupUserStateをストレージから返却する。userAddressに対応するデータがない場合は、エラータイプおよびエラーメッセージを返却する。
**ユースケース**
ユーザが自身のローカルWalletからuserStateを失ってしまった場合に、分散ストレージからBackupされている自身のUserStateを取得する。
**シーケンス図**
```mermaid
sequenceDiagram
actor U as User
participant O as Operator
participant D as Distribute Storage
autonumber
U ->> O : getBackupUserState(userAddress)
O ->> D : fetchBackupUserState(userAddress)
D ->> O : Response: BackupUserState
O ->> U : Response: BackupUserState
```
### saveBackupUserState(userAddress: String, backupUserState: BackupUserState): BackupUserState
対応するuserAddressとBackupUserStateを渡しデータをストレージに保存する。既にuserAddressと対応するBackupUserStateが存在する場合は、既存のBackupUserStateに上書きして保存をする。レスポンスとして受け付けたBackupUserStateを返却する。エラーが発生した場合は、エラータイプおよびエラーメッセージを返却する。
**シーケンス図**
```mermaid
sequenceDiagram
participant O as Operator
participant D as Distribute Storage
autonumber
O ->> D : saveBackupUserState(userAddress, BackupUserState)
D ->> O : Response: BackupUserState
```
### GlobalState service class
GlobalStateを管理するサービスクラスである。
| 項目 | 値 |
| -------- | -------- |
| 保存期間 | 永続 |
### データ構造
ローカルDBに保存している、blockNumberと対応するGlobalUserStateのKey, Valueデータ
| Key | Value |
| -------- | -------- |
| blockNumber | GlobalUserState |
### getGlobalState(blockNumber: Int): GlobalState
blockNumberを元に、GlobalStateを返却する。オペレータは、blockNumberに紐づくGlobalStateを分散ストレージから取得する。blockNumberに対応するGlobalStateがない場合は、エラータイプおよびエラーメッセージを返却する。
**ユースケース**
> TODO
**シーケンス図**
```mermaid
sequenceDiagram
participant O as Operator
participant D as Distribute Storage
autonumber
O ->> D : getGlobalState(blockNumber)
D ->> O : Response: GlobalState
```
#### getLatestGlobalState(): GlobalState
最新のGlobalStateを返却する。オペレータは、最新のblockNumberに紐づくGlobalStateを分散ストレージから取得する。最新のGlobalStateがまだ保存されていない場合は、エラータイプおよびエラーメッセージを返却する。
**ユースケース**
ユーザがTransctionを投げる時に、オペレーターはStateDiffを計算するために分散ストレージからGlobalStateを取得する。
**シーケンス図**
```mermaid
sequenceDiagram
participant O as Operator
participant D as Distribute Storage
autonumber
O ->> D : getLatestGlobalState()
D ->> O : Response: GlobalState
```
#### saveGlobalState(blockNumber: Int, globalState: GlobalState): GlobalState
対応するblockNumberとGlobalStateを渡しデータをストレージに保存する。ストレージの最新blockNumberがincrementされるようなIntのリクエストデータのみ受け付ける。レスポンスとして受け付けたGlobalStateを返却する。エラーが発生した場合は、エラータイプおよびエラーメッセージを返却する。
**ユースケース**
オペレータがオフチェーンコミット時に、globalStateが変更になった場合にblockNumberに対応するGlobalStateを分散ストレージに送信し保存する。
**シーケンス図**
```mermaid
sequenceDiagram
participant O as Operator
participant D as Distribute Storage
autonumber
O ->> D : saveGlobalStateCID(blockNumber, GlobalState)
D ->> O : Response: GlobalState
```
### DeletePublisher service class
各データ管理用のサービスクラスのデータ保存時に、deleteする時間と対象データのblockNumberをkeyにしたデータをTimeHashMapTableに刻む。
常にループしているHandler関数がTimeHashMapTableに刻まれたデータでdelete時間を過ぎているものがあれば、対象サービスクラスにdeleteイベントを流す。イベントpush後にTimeHashMapTableから行ったイベントのデータを取り除く。
**Proof削除用のTimeHashMapTableデータ**
```
deleteProofHashTable: Map<timestamp, blockNumber>
ex. { timestamp: 20017 }
```
**シーケンス図**
```mermaid
sequenceDiagram
participant O1 as Operator(DeletePublisher service class)
participant O2 as Operator(Proof service class)
autonumber
O1 ->> O2 : emit("deleteProof", blockNumber)
O2 ->> O2 : onDelete(blockNumber)
```
**Commit削除用のTimeHashMapTableデータ**
```
deleteCommitHashTable: Map<timestamp, blockNumber>
ex. { timestamp: 20017 }
```
**シーケンス図**
```mermaid
sequenceDiagram
participant O1 as Operator(DeletePublisher service class)
participant O2 as Operator(Commit service class)
autonumber
O1 ->> O2 : emit("deleteCommit", blockNumber)
O2 ->> O2 : onDelete(blockNumber)
```
### パフォーマンス
**パフォーマンス**
| 項目 | 値 |
| -------- | -------- |
| GETリクエスト | 5000 |
| POSTリクエスト | 1000 |
| 平均応答速度(GET) | 250millisecond |
分散ストレージへのGETリクエストへの応答速度は平均250millisecondとする。
リクエストの処理に関して、1秒あたり1000のPOST処理に対応させること。また、1秒あたり5000のGET処理に対応すさせること。分散のPOST処理に関しては、秒数あたりのリクエストが多い場合は、スループットの増加に伴い応答の平均速度に落ち着くように複数のリクエストをまとめたバルク処理を行う。
### サイズの制限
**サイズ制限**
| 項目 | 値 |
| -------- | -------- |
| アップロードMaxサイズ | 20GB |
分散ストレージのサイズに制限はないが、アップロードできるデータの制限を20GBとする。大きいデータの場合は、分割してアップロードすることとする。
### セキュリティとデータ取得権限
**ローカルDBへのアクセス権**
| 項目 | 値 |
| -------- | -------- |
| データの取得 | オペレータ |
| データの追加 | オペレータ |
| データの削除 | 内部のHandler処理のみ |
目的に応じて各種データにアクセスできる権限を制限する。ローカルDBからのデータの取得に関しては、オペレータのみ取得することができる。データの追加もオペレータのみ行うことができる。またデータの削除に関しては、外部から処理を呼び出すことはできず、内部の削除handlerでのみ実行することができる。
Sign in with Wallet
Connect another wallet