Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Research zkSNARKS blocker: Proving key size and bootstrapping #8

Closed
oskarth opened this issue Nov 8, 2019 · 11 comments
Closed

Research zkSNARKS blocker: Proving key size and bootstrapping #8

oskarth opened this issue Nov 8, 2019 · 11 comments

Comments

@oskarth
Copy link
Member

@oskarth oskarth commented Nov 8, 2019

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 2
24 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
Copy link

@barryWhiteHat barryWhiteHat commented Nov 8, 2019

#7 (comment) 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
Copy link
Member Author

@oskarth oskarth commented Nov 8, 2019

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
Copy link

@barryWhiteHat barryWhiteHat commented Nov 8, 2019

@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 oskarth changed the title Research zkSNARKS blocker: Proof key size and bootstrapping Research zkSNARKS blocker: Proving key size and bootstrapping Nov 8, 2019
@oskarth
Copy link
Member Author

@oskarth oskarth commented Nov 11, 2019

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

@kobigurk
Copy link

@kobigurk kobigurk commented Nov 11, 2019

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
Copy link

@kobigurk kobigurk commented Nov 11, 2019

@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
Copy link
Member Author

@oskarth oskarth commented Dec 9, 2019

@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
Copy link

@burdges burdges commented Dec 10, 2019

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
Copy link

@rachelhamlin rachelhamlin commented Dec 10, 2019

@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?

@decanus decanus added this to the zkSNARKS Feasibility milestone Apr 16, 2020
@barryWhiteHat
Copy link

@barryWhiteHat barryWhiteHat commented May 4, 2020

It's 3.9 mb for 2^32 identity set

@oskarth
Copy link
Member Author

@oskarth oskarth commented Sep 15, 2020

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

@oskarth oskarth closed this Sep 15, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
6 participants