Hi all,

I have been working on membership proofs (One-out-of-Many, Lelantus, Tiptych, Arcturus, etc) and have come up with an optimization that greatly improves batch verification performance in any membership proof derived from Groth & Kohlweiss’s One-out-of-Many proof scheme.

I have an early paper (very early, still missing benchmarks and concrete numbers) describing the improvement here:

I have a benchmark demonstrating 60% verification speedup for a batch of 100 proofs with set size of 4096:

I think this optimization could be very useful to Lelantus, so I wanted to share. I welcome any feedback/comments/criticisms. Feel free to create an issue or PR on Github. I will check this forum occasionally, but it will be quicker to reach me via email (see any Cargo.toml file on my github) or via GitHub issue/PR.

I still need to finish up the paper, as well as add sample code and build out more benchmarks. Please treat this paper/github as early proof of concept only.