# intmax ZKP circuit 仕様

## とりあえず思いついたことをメモ

* STARK の recursion は, Kate based な PLONK と異なり, 同じ楕円曲線上で計算することが可能らしい. つまり, 1 階の recursion ができれば何階層でもできる.
* バッチ回路の各要素は, トランザクションではなく 1つの diff. そこで, diff_index という概念を導入する. 1 つのトランザクションは 複数の diff を持つ場合があるので, それらを個々に検証する. トランザクションが最大でいくつの diff を生むかどうかに関わらず, 回路の大きさを一定に保つことができる. ただし, 確実にすべての diff をまとめたことを検証する必要がある.
* トランザクションは, 自分と共有ストレージのみを参照するようなものしか表せない.

## Rollup Algorithm

###

- Tx = `([u8; 20], u8, Vec<u8>)` : `contractAddress`, `functionSignature`, `calldata` の組
- SignedTx = `Bn256::Fr`
- SignerPublicKey = `EdwardsPoint<Bn256>`
- OldSharedStates = `Vec<(Fr, Fr)>` : `(key, value)` の集合
- NewSharedStates = `Vec<(Fr, Fr)>` : `(key, value)` の集合
- UserStateDiffs = `Vec<(Fr, Fr)>` : `(hashed_key, diff)` の集合
- OldUserStates = `Vec<(Fr, Fr)>` : `(hashed_key, value)` の集合
- SharedStatesProofs = `SparseMerkleProof<Bn256::Fr>`
- OldSharedStateRoot = `Bn256::Fr`
- NewSharedStateRoot = `Bn256::Fr`
- UserStatesProofs = `SparseMerkleProof<Bn256::Fr>`
- OldUserStateRoot = `Bn256::Fr`
- StatesProofs = `SparseMerkleProof<Bn256::Fr>`
- OldStateRoot = `Bn256::Fr`
- NewStateRoot = `Bn256::Fr`

- verify_signature(SignedTx, SignerPublicKey, Tx) -> ()
- EdDSA 署名の検証
- calc_state_diffs(Tx, OldSharedsStates) -> (UserStateDiffs, NewSharedsStates)
- 計算
- check_user_state_diffs(UserStateDiffs, OldUserStates, UserStateProofs, OldUserStateRoot) -> (NewUserStateRoot)
- sparse Merkle proof の検証
- leaf を楕円 ElGamal 暗号の暗号文（64 bytes）にして, update の時は差分を暗号化したものを渡してもらい準同型の性質を利用して計算する. （差分は暗号化しない状態で渡すこともできる）<!-- $(B \in \mathbb{G}, x \in \mathbb{F}_{s})$ -->
- check_state_diffs(OldUserStateRoot, NewUserStateRoot, StateProofs, OldStateRoot) -> (NewStateRoot)
- sparse Merkle proof の検証
- check_shared_state_diffs(OldSharedStates, New
sStates, SharedStateProofs, OldSharedStateRoot) -> (NewSharedStateRoot)
- sparse Merkle proof の検証

graph TD;
SignedTx-->verify_signature;
SignerPublicKey-->verify_signature;
Tx-->verify_signature;
Tx-->calc_state_diffs;
OldSharedStates-->calc_state_diffs;
calc_state_diffs-->UserStateDiffs;
OldUserStates-->check_user_state_diffs;
UserStateDiffs-->check_user_state_diffs;
UserStateProofs-->check_user_state_diffs;
OldUserStateRoot-->check_user_state_diffs;
check_user_state_diffs-->
NewUserStateRoot;
StateProofs-->check_state_diffs;
OldUserStateRoot-->check_state_diffs;
NewUserStateRoot-->check_state_diffs;
OldStateRoot-->check_state_diffs;
check_state_diffs-->NewStateRoot;
calc_state_diffs-->NewSharedStates;
OldSharedStates-->check_shared_state_diffs;
NewSharedStates-->check_shared_state_diffs;
SharedStateProofs-->check_shared_state_diffs;
OldSharedStateRoot-->check_shared_state_diffs;
check_shared_state_diffs-->NewSharedStateRoot;

## L2 contract

### ERC721

`mapping(uint256 => address) public holder`
`mapping(address => mapping(uint256 => bool)) private isOwned`
`function _transfer(uin256 tokenId, address sender, address receiver)`

- transfer: `require(msg.sender == sender)`
- mint: `sender = address(0)`, `require(msg.sender == admin)`
- burn: `receiver = address(0)`, `require(msg.sender == sender)`

### ERC20

`mapping(address => uint256) private balance`
`function _transfer(address sender, address receiver)`

- transfer: `require(msg.sender == sender)`
- mint: `sender = address(0)`, `require(msg.sender == admin)`
- burn: `receiver = address(0)`, `require(msg.sender == sender)`