Protocol: Waku's Rate-Limiting Nullifier for privacy preserving spam protection

[mratsim]

For privacy preserving p2p economic spam protection the Waku team designed rate-limiting nullifiers.

• Writeup: https://vac.dev/rln-relay
• Paper: https://github.com/vacp2p/research/blob/master/rln-research/Waku_RLN_Relay.pdf
• Specs:
  • https://hackmd.io/tMTLMYmTR5eynw2lwK9n1w?view#RLN
  • https://rfc.vac.dev/spec/17/
• Discussions:
  • https://ethresear.ch/t/semaphore-rln-rate-limiting-nullifier-for-spam-prevention-in-anonymous-p2p-setting/5009
  • https://forum.vac.dev/t/vac-3-zk/97
  • https://ethresear.ch/t/rln-incentives-for-p2p-networks/8085
• Benchmarks: Research zkSNARKS blocker: Benchmark and optimize proof time vacp2p/research#7
• PoC: https://github.com/kilic/rln

Prerequisites:

• BN254_Snarks curve
• WASM build
• Shamir's Secret Sharing
• Poseidon hash function: https://eprint.iacr.org/2019/458.pdf
• Merkle Tree/Trie
• Groth16
• Hashing to BN curves (?), there is a hash_to_field but the use case doesn't seem to be fully hashing to elliptic curve (https://github.com/kilic/rln/blob/7ac7418/src/hash_to_field.rs)
• ARM assembly for phones (stretch goal)

Note, the PoC is based on https://github.com/matter-labs/pairing (Zcash pairing "community edition") which uses ff "Community edition" which does support MULX/ADCX/ADOX assembly: https://github.com/matter-labs/ff/blob/aca3a18/ff_derive/src/asm/impls_4.rs, hence the following speedup of Constantine over pairing_ce are NOT due to the use of Assembly since the low-level playing field is even.

Pairing_CE cargo +nightly bench with fixes from matter-labs/pairing#8 (s/use pairing::/use pairing_ce::/g and s/G1::one()/<G1 as GenericCurveProjective>::one()/g, etc)

Constantine nimble bench_summary_bn254_snarks_clang

On the costliest operations, Constantine is 2.56x faster on G1 scalar mul, 8.95x faster on G2 scalar mul and 2.97x faster for pairing.
As the difference is algorithmic (described in optimizations.md, WASM would also benefit from those.