Validation Protocol

In recent years, there has been a tendency to transfer computing from relatively low-performance computing devices to more efficient computing systems. Several factors contributed to this.

1. During the 2000s, research projects: SETI @ Home , Folding @ Home , Mersenne Number ( GIMPS ), etc. - used free computing resources on volunteer computers . The big problem for these projects was dishonest participants - those who modified the client software in such a way as to return a similar correct result without performing the necessary calculations only to increase their rating in the system. The fight against such fraud was carried out with the help of redundancy of calculations: the same task was sent to several clients, and the results were checked after returning.
2. The cheaper services of cloud computing services led to the fact that many companies refused to buy and maintain their own computing system in favor of buying working time from cloud computing services. Often critical applications are transferred to the calculation, so it is important to avoid errors in the calculation. In addition, the cloud computing service has the obligation to correctly calculate even non-important tasks, errors in which the client most likely will not notice, and the client must be sure that all the results calculated by the service are correct.
3. The proliferation of mobile devices such as smartphones and netbooks , where a low-performance device often has a need to work with computationally complex applications such as cryptography or photo manipulation, as well as the correctness of their result.

An important requirement for the implementation of the protocol of verifiable calculations in all the above cases is that the client should verify the correctness of the result using much less resources compared to the task itself. ^[one]

Verification by replication

• Audit-based scheme ^[2]

A scheme is proposed in which a client or a randomly selected other participant in the system needs to recount the result of some work performed by another participant. All participants in the calculations are given a rating. The rating of the participant increases if he returns the correct result, and decreases if incorrect. In addition, a participant who finds an error with another participant is awarded. Such a scheme is disadvantageous for customers with a small amount of computing resources, and requires at least some part of reliable or at least not conspired participants.

• Using crypto processors

The use of separate secure coprocessors for calculations requires their high resistance to unauthorized access ( Tamper resistance ), which makes such processors very expensive. The widespread use of the Trusted Platform Module to protect software because of their low relatively secure cost coprocessors has led to the fact that they have virtually no protection against unauthorized access ^[1] .

Using Interactive Evidence

comes down to the concept of . The PCP theorem states that any proof can be redone in polynomial time to one that can be probabilistically verified by reading only the constant number of bits of this proof, while the proof verification algorithm uses only the logarithmic number of random bits. Thus, the participant needs to prepare a proof, and the client can check only some places (in particular, a constant number of bits of evidence). However, this check can be very difficult for the client from a computational point of view ^[1] .

Jeneiro, Gentry, and Parno defined the protocol of checked computations as a protocol between two participants: the client and the executor - to calculate the function F: {0,1} ⁿ → {0,1} ^m . This diagram consists of three steps:

• Preliminary processing

At this step, the client calculates some supporting information about the function F. Part of this information is public and sent to the executors, the other part is secret and remains on the client.

This stage may take time comparable to the time of the direct calculation of the function F. But this time is not significant with a large number of calculations, since this stage is performed only once.

• Input preparation

In this step, the client calculates some supporting input information. Some of this information is public and sent to the performers, another part is secret and remains on the client.

• Calculation of the result and its verification

Using public information about the function and the input data sent by the client, he calculates the encoded result and returns it to the client. Having received the encoded result, the client uses the stored secret information to decode the result, and receives either the actual result of applying the function or a special value indicating the incorrectness of the calculations performed by the executor.

This protocol minimizes the interaction of the client and the performer with up to two messages.

The article ^[1] gives an example of a scheme based on the protocol of confidential computing ^[3] . Andrew Yao and homomorphic encryption .

VC = (KeyGen, ProbGen, Compute, Verify) consists of four steps:

1. KeyGen (F, λ) → (PK, SK) : The random key generator generates public and private keys using the parameter λ . The public key encodes function F and is sent to the executor.
2. ProbGen _SK (x) → (σ _x , τ _x ) : The input data is encrypted in two quantities: open σ _x and closed τ _x with SK . The open value of σ _{x is} sent to the executor to calculate F (x) , while the closed value remains with the client.
3. Compute _PK (σ _x ) → σ _y : The contractor computes σ _y , the encrypted value of the function y = F (x) , using the PK public key and the encrypted input σ _x .
4. Verify _SK (τ _x , σ _y ) → y ∪ ⊥ : The verification algorithm converts the encoded result of the encoded σ _y executor into a real result F using both private keys: SK and τ _x . This corresponds to y = F (x) if σ _y represents the correct result F of x , or the result ⊥ .