Vitalik Buterin
@vitalik.eth
110 Following
289602 Followers
24 replies
71 recasts
418 reactions
39 replies
51 recasts
368 reactions
16 replies
25 recasts
207 reactions
81 replies
54 recasts
418 reactions
48 replies
56 recasts
379 reactions
172 replies
541 recasts
2678 reactions
79 replies
124 recasts
1041 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 19 replies
29 recasts
256 reactions
44 replies
23 recasts
327 reactions
19 replies
76 recasts
390 reactions
26 replies
113 recasts
531 reactions
29 replies
156 recasts
702 reactions
14 replies
54 recasts
312 reactions
7 replies
41 recasts
206 reactions
23 replies
38 recasts
332 reactions
13 replies
82 recasts
371 reactions
6 replies
14 recasts
145 reactions
1 reply
3 recasts
56 reactions
16 replies
84 recasts
339 reactions
4 replies
5 recasts
55 reactions