This repository contains an educational implementation of Semaphore circuits using Halo2. One may find it useful as a more complex complement to the SimpleExample in the Halo2 book.
This implementation is for educational purposes and contains bugs. For a higher quality Semaphore implementation in Halo2, see Andrija Novakovic's work.
- Basic implementation of Semaphore circuits in Halo2.
- Utilizes the Merkle tree gadget by young-rocks without alterations.
The circuit size is dominated by the Poseidon circuits. Each layer of the merkle tree adds rows to the circuit. A tree of height 48 (281,474,976,710,656 leafes) fits into 2^11 rows. The next smaller circuit with 2^10 rows would only be able to support 2^24 (16,777,216) leafes i.e. identities in the anonymity set. Halo2 allows to use more columns instead of rows to trade off prover time against verifier time.
- Basic understanding of the arithmetization step in zero-knowledge proofs.
- Familiarity with Rust programming language.
My prior knowledge includes implementing vanilla plonk and plonk with lookups. These experiences, although not necessary, were beneficial in understanding and working with Halo2.
- Read sections 1 and 2 of the Halo2 book.
- Go through Errol Drummond's Halo2 Tutorial.
- Attend 0xparc's Halo2 learning group lectures.
- Build a basic circuit using more than one chip in Halo2.
- Revisit the Halo2 book and lectures to reinforce your understanding.
- Experiment with the circuit-layout printer to optimize the number of rows.
main.rscontains a basic example to get started. Modify and execute it to see how the implementation works.