# On Cost and Complexity of RLN

- [Parameters](#parameters)
- [Contract Setups](#contract-setups)
- [A. Pubkey map](#a-pubkey-map)
- [B. On chain availability](#b-on-chain-availability)
- [Maintaining dynamic tree](#maintaining-dynamic-tree)
- [Full Node](#full-node)
- [Ligth Node](#ligth-node)
- [Players](#players)
- [Analisys under pubkey-map strategy](#analisys-under-pubkey-map-strategy)
- [Analisys under calculation-on-chain strategy](#analisys-under-calculation-on-chain-strategy)

## References

* https://hackmd.io/tMTLMYmTR5eynw2lwK9n1w?both)
* https://github.com/vacp2p/research/pull/54
* https://github.com/vacp2p/specs/issues/242
* https://github.com/vacp2p/research/blob/rln-relay-research/merkle-tree-update/rln-research/merkle-tree-update.md

## Parameters

- `word` : cost of 32 bytes in calldata = 512 gas
- `store_word` : cost of stroing 32 bytes = 20k gas
- `base_fee` : 20k gas
- `hash` : poseidon hash cost 20k gas
- `depth` depth of the membership tree
- `b` : batch depth
- `B = 1 << b` : batch size

## Contract Setups

### A. Pubkey map

Pubkeys are stored on chain mapped to the incremental index. Tree calculations are performed off chain. Root of the tree and auth path of pubkeys are not available publicly.

| Method/Cost | Operation cost | Calldata cost | Estimate per pubkey |
| :-------------- | :------------------------ | :------------ | :------------------ |
| Single Deposit | `store_word` + `base_fee` | `word` | 40k |
| Batch Deposit | `store_word` \* `B` | `word` \* `B` | 20k |
| Single Withdraw | `hash` + `base_fee` | `word` | 40k |
| Batch Withdraw | `B` \* `hash` | `word` \* `B` | 20k |

Estimates are for `depth` = 32

### B. On chain availability

- Membership root is stored on chain.
- Auth path of updated user is verified (in withdrawals or slasing)

We have two variants here. First one is that we calculate the root and verify given auth paths in withdrawals on chain. And the other is that ZK proof of thoses operations are verified on chain. Both direction can be run in optimistic way.

#### B.1. Calculation on chain

- Inclusion checks and root update operations are performed in contract.
- Optimistic: inclusions checks and root update are subjected to fraud proof.

update = hash * depth
update_batch = hash * (depth - b) + hash * (B-1)
inclusion_check = hash * depth

| Method/Cost | Operation cost | Calldata cost | Estimate per pubkey |
| :-------------- | :--------------------------------- | :---------------------- | :------------------ |
| Single Deposit | `update` | `word` | 650k |
| Batch Deposit | `update_batch` | `word` \* `B` | 25k |
| Single Withdraw | `update` + `inclusion_check` | `word` \* `depth` | 1300k |
| Batch Withdraw | `update` + `inclusion_check` \*`B` | `word` + `depth` \* `B` | 1300k |

Estimates are for `depth` = 32, `B` = 128

#### B.2 Rollup

In rollups we require updated root and auth paths of depositor and withdrawer in calldata.

- ZK Rollup
- Optimistic: ZK verification is subjected to fraud proof

ZK verification cost: `cost_verzk` = 250k - 500k gas depends on the protocol.

| Method/Cost | Operation | Calldata | |
| :-------------- | :----------- | :------------------------- | :--- |
| Single Deposit | `cost_verzk` | `word` \* `depth` | 415k |
| Batch Deposit | `cost_verzk` | `word` \* `B` | 900 |
| Single Withdraw | `cost_verzk` | `word` \* `depth` | 415k |
| Batch Withdraw | `cost_verzk` | (`word` \* `depth`) \* `B` | 16k |

Estimate for `depth` = 32, `B` = 1024, `cost_verzk` = 400k

## Maintaining dynamic tree

We will analize off chain requirements in terms of bootstraping and maintaining.

Definitions we will use:

- `root`: root of the current merkle tree
- `leaf`: public key in the tree
- `node`: intermediate hash results between leafs and the root
- `self_auth_path`: authentication path of the member itself
- `member_index`: index of the member itself
- `state_index`: the first empty leaf index
- `witness`: authentication path of an any member
- `filled_subtrees`: roots of the filled subtrees

### Full Node

Full node stores whole tree (leafs and intermediate nodes).

#### Bootstrap

Node needs to process all deposit and withdraw transactions until `state_index`.

#### Maintain

Process any upcoming deposit and withdraw event

### Ligth Node

Ligth node maintains set of nodes which are `filled_subtrees` and `self_auth_path` where both are sized `depth`. So storage complexity is O(n)

#### Bootstrap:

| Bootstrap Strategy / Complexity | Computation |
| :------------------------------ | :---------- |
| Helped | O(n) |
| Unhelped | O(2^n) |

There are two ways to bootstrap a light node:

##### Unhelped Bootstrap

Process all deposit and withdrawal transactions from data stored in contracts or emitted from events. And derive `self_auth_path`, `filled_subtrees`.

Storage requirements are low whereas computation and bandwith requirements are high.

##### Helped Bootstrap

We should define another parameter here which is `start_index`

Case 1: `start_index < member_index < state_index`

Light node must be initialized with `filled_subtrees` which is the filled subtrees at index `start_index`. Then it sequencially processes deposit events with `leaf` and withdraw events with `leaf_index` and `witness` until the `state_index`. `self_auth_path` will be derived along this syncronization process.

Case 2: `member_index <= start_index <= state_index`

Light node must be initialized with `filled_subtrees` which is the filled subtrees **and** valid `self_auth_path` at index `start_index`. Then it sequencially processes deposit events with `leaf` and withdraw events with `leaf_index` and `witness` until the `state_index`. `self_auth_path` will be updated along this syncronization process.

We expect that helper data for bootstraping which is `filled_subtrees` at a specific index can be found from full nodes. Notice that deriving `filled_subtrees` at a specific index data from data stored in the contract or emitted from events is equivalent of bootstaping in unhelped way.

#### Maintain

We assume that a node have its valid `self_auth_path` and valid `filled_subtrees` and its local `state_index` is in line with the index in the contract.

Deposit: Process upcoming deposit events with `leaf` data. `self_auth_path`, `root`, `filled_subtrees` will be updated.

Witdrawals helped: we will need `leaf_index` and `witness` of withdrawing member. We expect this data is either available on chain (which is the case with Calculation-on-chain setup) or can be requested from a full node.

Withdrawals unhelped: If Pubkey-map approach is followed `witness` for slashed member is not available publicly. And we assume here we can't rely on other nodes for `witness`. So we still can calculate `witness` of a specific from pubkey map. However calculation complexity will be high.

| | Complexity |
| :---------------- | :--------- |
| Deposit | O(n) |
| Withdraw helped | O(n) |
| Withdraw unhelped | O(2^n) |

### Players

**Messenger (member)**: Messengers public key is stored in a leaf of the merkle tree. They create proofs using root of the tree and auth path of themselfes as inputs.

**Relayer**: Relayers verify signals and relays messages to the target. They are considered to be incentivized.

**Slasher**: Slashers search for duplicate nullifiers. They withdraws deposits of members whose private key is exposed.

**Registrar (Depositor)**: Registers public keys in single or in batch.

### Analisys under pubkey-map strategy

We must define two types of light node here. One is that only listens on-chain events and the other requires p2p networking.

| | Data availability requirement | Ligth node event only | Ligth node p2p |
| :-------- | :---------------------------- | :-------------------- | -------------- |
| Messenger | `root`, `self_auth_path` | false | true |
| Relayer | `root` | false | true |
| Slasher | none | - | - |
| Registrar | none | - | - |

Messenger needs to have an access to `root` and `self_auth_path` to create a valid proof. Relayer needs to have an access to `root`. Question is that who is incentivezed to maintain a full-node that can help relayers and messengers to be in sync?

### Analisys under calculation-on-chain strategy

Since witnesses used in withdraw and a hint (probably updated subtree) is given in calldata and subjected to a verification ligth nodes doesn't depend on p2p networking and master nodes in maintaining mode.

| In maintain mode | Data availability requirement | Ligth node |
| :--------------- | :---------------------------- | :------------------------------ |
| Messenger | `root`, `self_auth_path ` | true |
| Relayer | `root` | (root is available on contract) |
| Slasher | `root`, `witness` | false |
| Registrar | `root` | true |

TODO: bootstap mode