[Cryptography] economics of multi-party zkSNARK public parameters

[Jan Carlsson]

This paper:

  Secure Sampling of Public Parameters for Succinct Zero Knowledge Proofs
  Eli Ben-Sasson, Alessandro Chiesa, Matthew Green, Eran Tromer, Madars Virza
  2015 IEEE Symposium on Security and Privacy

presents a multi-party protocol for generating zkSNARK keys. An arithmetic
circuit which calculates the key is mapped to all parties. This extended
circuit reduces inputs from all parties to generate a key. During the joint
evaluation, parties do not reveal their secrets.

Question: Does the protocol make economic sense?
Answer:   It does, with some caveats.

  Let s = P(sabotage), the probability any party sabotages the protocol.
  Let h = P(honest), the probability any party is honest.
  Let N = number of parties in the protocol.

The protocol is not a threshold scheme. Majority does not rule. One honest
party ensures security. One malicious party sabotages the protocol.

Then by conditional probability:

  P(!sabotage) = (1-s)^N

  P(security | !sabotage) = 1 - (1-h)^N

  P(success)
    = P(security AND !sabotage)
    = P(security | !sabotage) * P(!sabotage)
    = (1 - (1-h)^N) * (1-s)^N

Decentralized trust means protocol success with the largest number of
parties. However, more parties also increases the chance of a saboteur.
This "saboteur hazard" dominates cost.

The programming problem is then:

  maximize N
  constrained by P(N) = P(success) >= B = acceptable minimum

Let's assume we live in a world where most people are honest. (Honesty means
a party follows the protocol and never cheats in the future.) We worry about
saboteurs only. Then:

  P(success) ~= (1-s)^N

and we require:

  (1-s)^N >= B

so:

  N < ln(B)/ln(1-s)

Let's try a few values:

  B = 0.9 (90% protocol success probability)
  s = 0.01, N < 10.5
  s = 0.05, N < 2.1

  B = 0.5 (50% protocol success probability)
  s = 0.01, N < 69
  s = 0.05, N < 13.5
  s = 0.10, N < 6.6
  s = 0.20, N < 3.1

  B = 0.1 (10% protocol success probability)
  s = 0.01, N < 229.1
  s = 0.05, N < 44.9
  s = 0.10, N < 21.9
  s = 0.20, N < 10.3
  s = 0.50, N < 3.3

For B = 0.1 (10%), we need 22 trials to match B = 0.9 (90%) when s = 0.01:

  (1 - 0.1)^22 = 0.098 ~= 0.1 = 1 - 0.9

The number of parties is 229 for B = 0.1 and 229/22 = 10 for B = 0.9.

This gives a sense of how decentralized the protocol can be and still work
economically. Decentralization depends on the time budget. Expected protocol
time complexity is linear in the number of parties assuming constant
saboteur hazard.

In the real world, I would expect saboteur hazard to be worse as historical
hazard rates in finance. Saboteurs become stronger as the number of parties
increases. Linear models are crude approximations to reality.

Note that storage and communication costs are ignored here. The number of
rounds is also ignored. These costs are dominated by the saboteur hazard.