Research statement

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:

As part of the dissertation, three hypothesis are posed: