
Vitalik Buterin
@vitalik.eth
110 Following
321768 Followers
82 replies
100 recasts
860 reactions
1 reply
3 recasts
21 reactions

A fun math aside, on the idea of splitting a large zk proving workload between multiple provers.
Suppose you have N provers, and you have a proving workload that you split into N parts (so, one part per prover). You require provers to pre-register, but registration is open-access.
Suppose you have a constant fault rate (eg. 1/5 of registered provers fail). Provers expect to complete in one round (eg. 3s). If one prover fails, other provers have to come in and re-prove that load. How many rounds does it take for the entire workload to get proven?
Answer: log*(N)
(yes, that's the iterated-log function)
Why:
In the first round, you go from N unproven workloads to N/5 unproven workloads
In the second round, each remaining workload gets assigned 5 provers, so per-workload failure rate becomes 1 in 5^5. So you go to N / 5 / 5^5 unproven workloads
In the third round, each remaining workload gets assigned ~5^5 provers, so failure rate is 1 in 5^(5^5). So you go to N / 5 / 5^5 / 5^(5^5) unproven workloads 22 replies
23 recasts
239 reactions
0 reply
0 recast
2 reactions
0 reply
0 recast
1 reaction
3 replies
0 recast
4 reactions
1 reply
0 recast
1 reaction
1 reply
0 recast
9 reactions
0 reply
0 recast
3 reactions
3 replies
1 recast
36 reactions
48 replies
28 recasts
316 reactions
1 reply
0 recast
2 reactions
40 replies
45 recasts
315 reactions
1 reply
0 recast
2 reactions
1 reply
0 recast
2 reactions
11 replies
34 recasts
234 reactions
11 replies
34 recasts
234 reactions
25 replies
76 recasts
485 reactions
38 replies
114 recasts
590 reactions
45 replies
173 recasts
858 reactions