Research zkSNARKS blocker: Proving key size and bootstrapping

[oskarth]

Problem

Proving key size is ~110mb for Semaphore. Assuming this is embedded on mobile device, it bloats the APK a lot. Current APK size is ~30mb and even that might be high for people with limited bandwidth.

Acceptance criteria

Either drastically reduced key size, or some strategy for getting it after that gives a reasonable UX and.

Details

See https://github.com/vacp2p/research/blob/master/zksnarks/semaphore/src/hello.js#L100-L106

-rw-r--r--. 1 oskarth oskarth 110M Oct 31 18:39 myCircuit.vk_proof
-rw-r--r--. 1 oskarth oskarth 3.0K Oct 31 18:39 myCircuit.vk_verifier

Possible solutions

1. Reduce key size

Don't know what this would entail or to what extent it is possible, needs to be researched. Some thoughts from Barry here:

That supports 224 group members, for smaller groups the key is smaller If we get to 224 unique devices we can optimise in a few ways to get this down. We can use better hash functions and reduce the cost We can also drop the security to 80 bits and halve the key size.

2. Get key after install

E.g. strategy to download proof key after install. This becomes a UX problem where you have to download a "big" file to get started messaging. This might be mitigated with basic rate limiting etc, but requires more thought.

3. Use different ZKP technology

The tradeoffs might look different. Didn't find anything regarding proof key size after a cursory search.

[barryWhiteHat]

https://github.com/vacp2p/research/issues/7#issuecomment-551397635 will help.

Also you should decide how many unique devices you want to support. One possible solution is to partition into group of 2^16 but this hurts privacy.

[oskarth]

Basically we have to minimize the number of constraints to minimize here. We can half the number of constraints by getting ride of blake2 / pedersen. And half again by reducing security to 80 bits. And half again by replacing mimc with rescue and having 11 leaves on each layer. Instead of binary mt we have a 11-ary merkle tree :)

[barryWhiteHat]

@kobigurk we want to do semaphore RLN

If we make a proof where 90% of the circuit , witness are the same are there any optimizaitons / precomputations that we can do to save on proving time / compress the proving key?

[oskarth]

We can also gzip the key, this should compress key size by ~80% (to verify)

[kobigurk]

We can also gzip the key, this should compress key size by ~80% (to verify)

gzip does reduce a lot, you can check out MicroMix to see an example.

[kobigurk]

@kobigurk we want to do semaphore RLN

If we make a proof where 90% of the circuit , witness are the same are there any optimizaitons / precomputations that we can do to save on proving time / compress the proving key?

I think any change in inputs would at least require the recomputation of H, off the top of my head I don't see a way around it. In this case, though, you could think of doing something like Gepetto/LegoSNARK to have two separate proofs and pay a bit more in verification time (you could batch verify to help with the costs maybe).

Curious - how come 90% are the same? Seems like an interesting situation.

[oskarth]

@andremedeiros @rasom @rachelhamlin what are your thoughts on maximum APK size? I.e. if we get amazing privacy preserving spam protection, how much are we willing to pay for it?

Assuming current APK is 30mb, I'd say 50% would be within range of acceptable. I.e. 15-20mb extra. Any other thoughts on this? Do we have data for how total data size changes over time?

[burdges]

Did you consider a group signature scheme here? I'd think threshold certifying group membership. Or maybe a group VRF?

As a rule, group signatures depend upon really annoying infrastructure, like a threshold signing DKG and threshold certifying group membership, but you already have some blockchain, so maybe that's actually preferable under your situation? All the crypto works out fast and cheap compared with SNARKs, probably similar verification costs.

[rachelhamlin]

@oskarth evidently APK size can negatively, and not insignificantly, impact install rates.

For every 6 MB increase to an APK’s size, we see a decrease in the install conversion rate of 1%.

I appreciate the privacy benefits of zkSNARKS, but in this particular context, is the end goal (privacy protecting) spam prevention?

[barryWhiteHat]

It's 3.9 mb for 2^32 identity set

[oskarth]

That's a big improvement, and seems quite reasonable! Closing this one.