Verifiable Computing and Commitments
With the rise in popularity of mobile devices, there has been an increased interest in the types of processes that these devices can perform. Additionally, the complexity of the tasks that individuals may need to run on traditional hardware could require more resources than a desktop computer has. As a result, the necessity for methods of outsourcing the execution of tasks has become essential.
What is Verifiable Computing?
Verifiable computing is the study of outsourcing computations so that the validity of the claimed computation can be assured. To explain by example:
Victor has a calculation that he needs performed. However, the computers he has access to are not powerful enough to run this task. On the other hand, Peggy has access to computing facilities that can perform the computation, so Victor agrees to pay Peggy for use of her computing facilities. However, it is economically advantageous for Peggy to send Victor a random output instead of actually using expensive computer time. Verifiable computing assures Victor that Peggy does, in fact, perform the correct computation. Additionally, the output could be corrupted through communication issues; this problem is caught through the same check.
High Probability Verification
The party that performs the computation is outsourced to a subject known as the Prover; the Prover is proving that the claimed output is correct. The Verifier is the party that will validate the Prover’s claim. Informally, the Prover and the Verifier are named Peggy and Victor, respectively.
In terms of classical complexity theory, non-deterministic polynomial time (NP) problems seemingly satisfy this objective. Informally speaking, NP problems are ones that are difficult to solve but easy to check. Given a polynomial, it may be difficult to find zeros of the polynomial; this is evident from the variety of techniques taught in mathematics courses. However, to check a claim that x = 5 is a zero of a polynomial, it is sufficient to just evaluate the polynomial at x = 5.
In practice, the verification check for NP problems would be more expensive than desirable. Moreover, not all computations that a Verifier may wish to outsource are NP problems. As a result, it is desirable to relax the validation check. Instead of verifying that the claimed result is in fact a solution, it is possible to decrease verification time by only validating that the solution is correct with high probability.
Classical Example
A classical example of verifiable computing involves matrix multiplication. Specifically, the Prover claims that C is the result of multiplying matrices A and B; for simplicity we assume that A and B are both n x n matrices. That is, C = AB.
The best known algorithm for matrix multiplication is O(n^2.3728596). However, if the Verifier selects a random vector x, the Verifier can check Cx = ABx in O(n^2). This method is called Frevald’s algorithm.
It is worth noting that while it is possible for the Verifier to pick x so that Cx = ABx when C is not the product AB, it is very unlikely as x is randomly chosen.
Commitment Schemes
Reducing computational complexity for the Verifier is critical in practice. However, it is necessary that an algorithm prevents a malicious Prover from convincing the Verifier of a lie. To do this, verifiable computing algorithms leverage cryptographic primitive-commitment schemes.
An important use of commitment schemes is to lock the Prover’s claim in. Specifically, this prevents the Prover from changing their claim as they go. This is ensured by the property of a commitment scheme known as binding. That is, it should be difficult for the Prover to find two inputs with the same commitment.
Commitment schemes are secured cryptographically by relying on problems that are assumed to be difficult. For cryptographic hash functions it is assumed that collisions are difficult to find, and for groups of (large) prime order the discrete logarithm is difficult. These problems ensure the integrity of the verifiable computing algorithm.
For a given task, algorithms can be devised using a commitment scheme to translate the verifiable computing checks to that of an identity equation(s) using commitments generated by the commitment scheme. Moreover, the commitment scheme leverages the intractability of certain problems to protect the Prover and the Verifier.
General Framework of Verifiable Computing
Verifiable computing algorithms often have multiple interactions between the Prover and the Verifier. These rounds can be summarized as commitments from the Prover and challenges from the Verifier. The Verifier’s challenges are random values that affect the Prover’s next commitments.
The challenges are necessary to make sure that the Prover cannot devise a solution that would pass the final check, an identity that follows if the Prover’s claim is valid.
Non-interactive Verification
In the literature, algorithms are often presented as an interaction between the Prover and the Verifier. However, this is not practical due to the amount of communication. Moreover, for applications such as validating new blocks on a blockchain, multiple parties run these checks. As such, it is often of interest to have a non-interactive protocol that anyone can check while retaining the confidence in the validity of the claim.
This is achieved by means of a technique called Fiat-Shamir heuristic. The Verifier’s challenges are replaced by hashed values. Since hashes are binding, and appear random, any party can be confident when verifying a result using a non-interactive protocol.
Summary
Verifiable computing is a powerful tool that ensures that outsourced computations, with high probability, are correct. Commitment schemes can be used to translate the verification check to an identity with group operations. This ensures that the computation is secured by cryptographically hard problems.
Space and Time is working to have SQL queries outsourced to a Proving party and validated by the Verifier.
