[EPIC] Implementation of Validators Balance Proof

[Dimo99]

Objective: https://hackmd.io/@metacraft-labs/DendrETH-for-liquid-staking-protocols

Subtasks:

• Create a commitment mapper SHA256 -> Poseidon for the validators #160

• We already have a naive version of validator_balances.circom circuit: Validator balances circom circuit #161
  Changes to Circom Circuit: We will adapt the circom circuit for validator balances to operate with Poseidon hashes, which are computationally cheaper than SHA256. It would require an alteration to the circuit to operate recursively, and we will need to assess the time requirement for the calculation of the validator balances. Considering recursion costs, it might be more efficient to compute some calculations in plonky2 and then validate plonky2 within the final circom circuit along with a few other elements.

• We will also consider using Plonky2's Starky, which offers fast performance for SHA256 (SHA256 Prover Comparison). This sounds like a very promising route as similar scheme is explained here: https://youtu.be/-pucWUDn5Hw?list=PLj80z0cJm8QErn3akRcqvxUsyXWC81OGq

• We have also examined PIL-STARK, developed by J. Baylina, the creator of circom, and used in Polygon's ZK EVM. It may be useful to also try to test the sha256 proofs performance with it.
  Some resources for it:

  • https://youtu.be/0IZ8-tYaNJM
  • https://youtu.be/ZwG3UI_iDAs
  • https://youtu.be/639DZpIC0Fc
  • https://www.notion.so/zkEVM-Audit-Education-Session-11-15-11-22-86d60daceadb438f85908817f7082611
  • https://polygon.technology/blog/pil-zk-tooling-is-now-open-source