Summary of performance

Here is a high-level summary. (Our publications provide detail. See especially this CACM article and Buffet.)

None of our systems (or the others in this area) have achieved true practicality yet.

There are two principal issues, for all of these projects:

(1) Costs to the verifier. To check that a remote computation was performed correctly, the verifier must incur a per-computation setup cost: this cost (which consists of CPU and network costs) amortizes over multiple instances of the same computation (potentially over all future instances), on different inputs. However, the cross-over point, in terms of when the setup cost is paid for, is quite high: tens or hundreds of thousands of instances of the same computation.

• This setup cost can be slashed (as in Allspice) or eliminated (as in CMT). Unfortunately, these solutions apply only to restricted classes of computations.
• Using the techniques of BCTV, the setup cost can be reused over all computations of the same size. However, the cost of these techniques is very high, and in practice, one would need to incur the setup cost thousands of times anyway (as explained in Buffet).
• Using other techniques of BCTV, the setup cost can be made independent of the computation. However, these techniques are primarily theory at this point; for example, the prover's computational costs are many orders of magnitude higher than the other works in the area.

(2) Costs to the prover. The CPU costs to the prover are currently immense: orders of magnitude (factors between a thousand and a million) more than simply executing the computation. An additional bottleneck is memory: the prover must materialize a transcript of a computation's execution.

As a consequence of the above costs, all projects in this area are currently limited to small-scale computations: programs that take several million steps, but not more.