Bitcoin revolutionized multiple fields. Being the first to solve the consensus problem in open-membership networks, created global deflationary currency, and enabled value transfer to those previously financially excluded. But most importantly, it created fundamentals for a platform of decentralized trust. Trust that used to be placed on a central authority, now–with Blockchain–can be decentralized on multiple parties or even removed thanks to recent advances in cryptography.
Blockchain technology, combined with zkSNARKs and fully homomorphic encryption, enables creating a secure, trustless private decentralized computational marketplace.
The computational marketplace can be used to outsource long-running tasks like compiling source code, training neural networks, rendering video, or performing CI/CD automation tasks in a trustless manner.
Verifiable computation allows efficient delegation of computation between distrusting parties. The computational complexity of preprocessing and verifying the result (performed by a client) is smaller than executing the task itself. Also, the computational complexity of the worker is quasilinear in the steps of the task. As a result, an asymmetric model of delegation of computation enables the creation of a computation marketplace.
Asymmetric model of computation allows one party (e.g., laptop) to delegate computation to another—more powerful—party (e.g., cloud server). An interesting problem arises when both parties distrust each other. The worker does not trust the task sent by the client, e.g., he can not know if the task will not run indefinitely (Halting problem). On the other hand, the client delegating his task does not trust the result returned by the worker.
The former problem has been solved by Ethereum by introducing a cryptocurrency and charging the client for each processor operation executed by the worker. The latter problem can be solved by re-executing the task on multiple workers and—by trusting that the majority of workers are honest—trusting the result returned by them. This approach is far from optimal because one task has to be executed by every worker in the network. Another approach is to execute the task by one server and guarantee correctness by introducing a bug-bounty that rewards nodes which—after re-execution—find an error. This approach has its own problem called the Verifier Dilemma. A relatively young branch of cryptography offers a construction called the zero-knowledge succinct non-interactive argument of knowledge (zkSNARK). In this model, a worker during the computation produces proof that certifies the correctness of execution. The proof is sufficient to convince the client that the computation was done correctly. Moreover, the verification requires significantly less computational effort than computing the task from scratch. The zero-knowledgeness guarantees that the worker learns nothing about the input and the output of the performed task, achieving privacy of the computation.
The technology behind verifiable computation struggles with its practical application. The overhead of producing such proof is often so high that proving even simple programs is infeasible. However, in 2016, the zkSNARK was used in a real-world system—the Zcash blockchain. Since then, several improvements have been proposed. Namely, universal and recursive SNARKs that allow proving arbitrary and long-running computations look promising for proving the research thesis.
My research tries to answer the following questions:
- Which specific zkSNARK is the most suitable for long-running computations?
- What are the main factors influencing preprocessing, proving, and verifying complexity, and how to optimize them?
- How different computational models can influence the preprocessing, proving, and verifying complexity?
- How can Blockchain be used to create a trustless peer-to-peer marketplace of computation? - Which Blockchain platform suits best for a marketplace of computation?
- Which consensus mechanism suits best for marketplace computation?
- How to assure security for both client and worker?
- What game theory techniques use to punish malicious actors and reward the honest ones.
- How to prevent frauds and Sybil attacks?
- How to prevent workers from learning anything about the performed work?
- What is the overhead of fully homomorphic encryption used for private computation, and how to optimize it?
As part of the dissertation, three hypothesis are posed:
- For a computationally weak client it’s more cost-efficient to outsource the computation of a function F with an input x to workers than renting computational power from centralized cloud providers.
- Both parties can distrust each other; the only trust required by the system is to the security of cryptography and lack of the byzantine agreement between blockchain nodes.
- The cost of producing a proof of the correct computation is quasilinear to the length of computation |F|, and the cost of verifying it is linear to the output size |y = F(x)|.
- The scheme guarantees privacy of both input x and output y, so that the worker can not learn anything about the input and the output of performed computation.