# ZK PoC Profiling Results and Summary

## PoC Motivaiton and Spec
- [Slides](https://docs.google.com/presentation/d/1rmj1-bE6KzWI9AIf5af8XJejFJPBtnhUjZpKJrH7YVA/edit?usp=sharing)
- [Repo](https://github.com/iotaledger/trie.go/tree/poc_32bytes)
- Elliptic Curve: BN254
- Hash: MiMC
- Proving system: Groth16/Plonk+KZG

## The Scope of The PoC
- What we have
- We have the IOTA [trie.go](https://github.com/iotaledger/trie.go), a generic Go library for implementations of tries (radix trees), state commitments and proofs of inclusion.
- We have open-sourced ZK libraries which can be experimented
- [libsnark](https://github.com/scipr-lab/libsnark)
- [jsnark](https://github.com/akosba/jsnark)
- [bellman](https://github.com/zkcrypto/bellman)
- [ZoKrates](https://github.com/JacobEberhardt/ZoKrates)
- [Snarky](https://github.com/o1-labs/snarky)
- [Circom](https://github.com/iden3/circom)
- [Circomlib](https://github.com/iden3/circomlib)
- [ZEXE](https://github.com/scipr-lab/zexe)
- [ZkEVM](https://github.com/interstellar/slingshot/tree/main/zkvm)
- [gnark](https://github.com/ConsenSys/gnark)
- [RISC-ZERO](https://github.com/risc0/risc0)
- We can implement a PoC to investigate the ZK techniques based on integrating the existing IOTA libraries and open-sourced ZK libraries, and provide ZK-friendly design insights based on the PoC.
- What we cannot do
- Implement the PoC with a mature IOTA smart contract
- Implement our own proof system and the associated ZK libraries
- Implement our own zkEVM
- What we can do
- To answer the question that why do we consider zk-friendliness in designing the L1 smart contract
- Explore and investigate ZK-friendly design constraints/considerations
- What we have done
- We implemented a ZK PoC based on
- gnark
- trie.go
- We implemented the gnark circuits and integrated the tries with bases 2, 16, and 256
- We implemented severals test cases with Groth16 and Plonk proof systems
- We profiled the test cases which includes the following items
- Setup of the proof system
- Proof generation
- Verifications
- Account updates
- Signature of one transfer
- Proofs of inclusions of the transfer
- State updates of the receiver/transmitter
- We profiled the CPU and Memory usage in different test cases, collected the details, and provided a summary
- We provided ZK-friendly design considerations based on the PoC
- What insights this PoC provide
- Most of time and memory (>90%) in the ZK process are spent on ECC calculation
- The curve impacts the CPU/memory usage
- For the gnark circuit, the number of inputs/outpus and the depth of trie/tree are fixed.
- The size of depth will impact the circuit size, computation time, and memory
- In the example provided by gnark , the default data structure to store the proofs are `complete binary tree`
- Which guarantees the minimum size of tree depth
- To store the same amount of proofs, the depth of a binary trie >= the depth of a complete binary tree
- Although 16/256-based trie can reduce the size of depth
- The overhead of using 16/256 trie is not affordable due to too many children for each node
- The 16-to-1/256-to-1 multiplexer is too costly
- To reduce the circuit size, memory, and CPU time in the whole ZK process
- Design the minimum requirements of data to be proved/stored
- Other design considerations for optimization
- The data structure and the stored data size will impact the circuit size heavily
- Early termination should be considered to reduce the computation time of the circuit
- Instead of using MiMC hashing and bn256, using KZG with a suitable curve pair might be helpful to reduce the circuit size and the computation time (By Evaldas)
- What is the future work
- For considering ZK rollup and learning from a relatively mature ZK rollup technique, ZKsync, which is claimed to be open-sourced soon, is a good candidate to start from (suggested by Wolfgang). By investigating the ZKsync, we might have more concrete knowledge to decide what ZK techniques should look like and how it would be adopted in IOTA

## Profiling Details (Function Flows and Simulation Time)

### CPU Profiling Results
| Profiling Case | Steps |
| --------------------- | -------------------------------------------------------------------------------------------------------------------------------------- |
| CircuitUpdateAccount | Verifies the accounts updates by the circuit (Includes Nonce, total balance amount, balance amount of receiver/sender) |
| CircuitSignature | Verifies the signature of one transfer |
| CircuitInclusionProof | 1) Create the transfer and sign it 2) Update the state from the received transfer 3) Verifies the proofs of inclusion of the transfer |

#### Groth16
| Test Case | 32B-Rollup2 | 32B-Rollup16 | 33B-Rollup2 | 33B-Rollup16 |
| ------------------------- | ----------- | ------------ | ----------- | ------------ |
| CircuitSignature (s) | 1.37 | 1.36 | 1.46 | 1.30 |
| CircuitInclusionProof (s) | 20.07 | 28.60 | 38.20 | 95.64 |
| CircuitUpdateAccount (s) | 0.26 | 0.26 | 0.28 | 0.26 |

| Test Item | 32B-Rollup2 | 32B-Rollup16 | 33B-Rollup2 | 33B-Rollup16 | Run Only Once |
| ------------------------- | ----------- | ------------ | ----------- | ------------ | ------------- |
| Setup (s) | 15.69 | 27.17 | 33.93 | 91.96 | Yes |
| Proof Generation (s) | 2.09 | 1.93 | 3.45 | 15.16 | No |
| Verification (s) | 0.0035 | 0.0011 | 0.015 | 0.00153 | No |

#### Plonk + KZG
| Test Case | 32B-Rollup2 | 32B-Rollup16 | 33B-Rollup2 | 33B-Rollup16 |
| ------------------------- | ----------- | ------------ | ----------- | ------------ |
| CircuitSignature (s) | 1.85 | 1.92 | 1.94 | 1.90 |
| CircuitInclusionProof (s) | 24.10 | 31.33 | 47.21 | 120.91 |
| CircuitUpdateAccount (s) | 0.38 | 0.38 | 0.39 | 0.39 |

| Test Item | 32B-Rollup2 | 32B-Rollup16 | 33B-Rollup2 | 33B-Rollup16 | Run Only Once |
| ------------------------- | ----------- | ------------ | ----------- | ------------ | ------------- |
| Setup (s) | 17.12 | 18.11 | 36.14 | 67.3 | Yes |
| Proof Generation (s) | 6.839 | 9.63 | 14.05 | 36.57 | No |
| Verification (s) | 0.0002 | 0.004 | 0.000258 | 0.00284 | No |
#### Details
- [32-Byte Trie with rollup-2 PoC](https://cloudfil.es/QQKBuUOLnW5)
- [32-Byte Trie with rollup-16 PoC](https://cloudfil.es/Jt3PCQ1FGXA)
- [33-Byte Trie with rollup-2 PoC](https://cloudfil.es/KsNCjp75SYr)
- [33-Byte Trie with rollup-16 PoC](https://cloudfil.es/9Z7UCt0Y3h1)

#### Total Test cases, 1 Core
- Total test cases include the following items
- 1 CircuitUpdateAccount case
- 1 CircuitSignature case
- 2 CircuitInclusionProof cases
- Most execution time (~95%) is consumed by ECC (Elliptic Curve Cryptography) calculation
- The ECC executions are performed in parallel
- Circuit compiling and parsing time consumes < 1 min
- The profiling time including both Plonk+KZG and Groth16
- Plonk+KZG is faster than Groth16 by around 20%

| Item | 32B-Rollup2 | 32B-Rollup16 | 33B-Rollup2 | 33B-Rollup16 |
| ------------------- | ----------- | ------------ | ----------- | ------------ |
| Total Execution (s) | 395.82 | 502.52 | 743.72 | 1591.09 |

### Memory Profiling Results

#### Memory Size (Groth16/Plonk+KZG)
| Item | Size (Byte) |
| ---------------- | ----------- |
| Validity Proof | 16 |
| Verification Key | 16 |
| Witness | 8 |

#### Details
- [32-Byte Trie with rollup-2 PoC](https://cloudfil.es/wZUfXSeMehH)
- [32-Byte Trie with rollup-16 PoC](https://cloudfil.es/2C7wd80GVPy)
- [33-Byte Trie with rollup-2 PoC](https://cloudfil.es/ZomdNdnpZ3Q)
- [33-Byte Trie with rollup-16 PoC](https://cloudfil.es/jzcGWKOtL8F)

#### Total Test cases
- Total test cases include the following items
- 1 CircuitUpdateAccount case
- 1 CircuitSignature case
- 2 CircuitInclusionProof cases
- Most memories are consumed when compiling the circuit (~35%)
- Validator might be able to compile the circuit in a local computer

| Item | 32B-Rollup2 | 32B-Rollup16 | 33B-Rollup2 | 33B-Rollup16 |
| ---------------------- | ----------- | ------------ | ----------- | ------------ |
| Total Used Memory (MB) | 8166.38 | 12538.07 | 14343.78 | 41147.8 |

# Notes (Enhanced by The Wolfgang's suggestions)
1. [x] Add notation (col) for single/multiple run
2. [x] Split the test case and detailed profiling results
3. [x] Plonk is associated with KZG