# The features for Semaphore V4 ## Prove non-membership proof We should support non membership proof i.e user can prove they don't belong to a group. https://github.com/semaphore-protocol/semaphore/issues/176 ## Support aggregate/recursive proof? Discussing... # Implementation We will forcus to: *Prove time*, *proof size* and *verify time(verify cost)*. ## Merkle tree and snark This schema is very simple. We maintain the merkle which leaf node containt the information of user. We use zkSNARK(Groth16 or Plonk) to proving we know the merkle proof belong to merkle tree. The problem with merkle tree approach is we need to create prove hash function inside SNARK circuit and this action is required a heavy computation. Sha or Blake family is not good candidate. Poseidon hash or MiMc is SNARK-friendly and was using more recent in this schema. We will build merkle tree in **halo2** and **plonky2**. A both libs are writing in rust so we can compile to wasm and execute it on web env. Semaphore are using at web client this is the reason why we should to compare between **wasm version** and **js semaphore version**. ### Halo2 - PSE halo2(Plonkish + KZG) - zcash halo2(Plonkish + IPPA, support aggregate). ### Plonky2 - Plonkish - FRI comitment as backend - Recurive proof support ## Caulk Caulk is a new membership proof schema, paring-based cryptography. Caulk allow user create proof in O(log) and verify it in constant complexity. The problem with caulk is this only use for membership proof and with semaphore protocol this required more feature. Let think more about it. - Vector commitment. - Paring-base. - Build another semaphore feature on caulk. ## RSA Accumulators - Understand and benchmark # References - https://eprint.iacr.org/2019/1255.pdf - https://eprint.iacr.org/2022/621.pdf Note: We also have another schema we didn't details at here. I will update it later.