随着移动设备的普及，人们对这些设备可以执行的处理类型越来越感兴趣。此外，个人可能需要在传统硬件上运行的任务的复杂性可能需要比台式计算机更多的资源。因此，外包任务执行方法的必要性变得至关重要。

可验证计算是对外包计算的研究，以便保证所声称的计算的有效性。举例说明：

维克多有一个需要执行的计算。然而，他所使用的计算机的功能不足以执行此任务。另一方面，佩吉可以使用可以执行计算的计算设施，因此维克多同意向佩吉支付使用她的计算设施的费用。然而，对于佩吉来说，向维克多发送随机输出而不是实际使用昂贵的计算机时间在经济上是有利的。可验证的计算让维克多确信佩吉确实执行了正确的计算。此外，输出可能会因通信问题而损坏；这个问题是通过同样的检查发现的。

执行计算的一方被外包给称为证明者的主体；证明者正在证明所声明的输出是正确的。验证者是验证证明者声明的一方。非正式地，证明者和验证者分别被命名为 Peggy 和 Victor。

就经典复杂性理论而言，非确定性多项式时间（NP）问题似乎满足了这一目标。通俗地说，NP问题是指难以解决但易于检查的问题。给定一个多项式，可能很难找到多项式的零点；这从数学课程中教授的各种技巧中可以明显看出。然而，要检查 x = 5 是多项式零的说法，只需在 x = 5 处计算多项式就足够了。

在实践中，NP 问题的验证检查成本会比预期的要高。此外，并非验证者希望外包的所有计算都是 NP 问题。因此，希望放宽验证检查。无需验证所要求的结果实际上是解决方案，而是可以通过仅验证解决方案以高概率正确来减少验证时间。

可验证计算的一个经典例子涉及矩阵乘法。具体来说，Prover声称C是矩阵A和B相乘的结果；为简单起见，我们假设 A 和 B 都是 nxn 矩阵。即C=AB。

最著名的矩阵乘法算法是 O(n^2.3728596)。然而，如果验证者选择随机向量 x，则验证者可以在 O(n^2) 中检查 Cx = ABx。这种方法称为 Frevald 算法。

值得注意的是，虽然当 C 不是 AB 的乘积时，验证者有可能选择 x 使得 Cx = ABx，但这种可能性很小，因为 x 是随机选择的。

降低验证者的计算复杂度在实践中至关重要。然而，有必要有一种算法可以防止恶意的证明者让验证者相信谎言。为此，可验证计算算法利用加密基元承诺方案。

承诺方案的一个重要用途是锁定证明者的声明。具体来说，这可以防止证明者随时更改其声明。这是通过称为约束力的承诺方案的属性来确保的。也就是说，证明者应该很难找到具有相同承诺的两个输入。

承诺方案通过依赖于被认为是困难的问题来以加密方式保证安全。对于密码散列函数，假设很难发现冲突，并且对于（大）素数阶组，离散对数是困难的。这些问题保证了可验证计算算法的完整性。

对于给定的任务，可以使用承诺方案来设计算法，以使用由承诺方案生成的承诺将可验证的计算检查转换为恒等式的检查。此外，承诺方案利用某些问题的棘手性来保护证明者和验证者。

可验证的计算算法通常在证明者和验证者之间有多种交互。这些轮次可以概括为证明者的承诺和验证者的挑战。验证者的挑战是影响证明者下一步承诺的随机值。

这些挑战是必要的，以确保证明者无法设计出能够通过最终检查的解决方案，如果证明者的主张有效，则随之而来的身份。

在文献中，算法通常被表示为证明者和验证者之间的交互。然而，由于通信量的原因，这是不切实际的。此外，对于验证区块链上的新块等应用程序，多方运行这些检查。因此，拥有一个任何人都可以检查的非交互式协议，同时保持对声明有效性的信心，通常是令人感兴趣的。

这是通过一种称为 Fiat-Shamir 启发式的技术来实现的。验证者的挑战被散列值取代。由于哈希值具有约束力并且看起来是随机的，因此任何一方在使用非交互式协议验证结果时都可以充满信心。

可验证计算是一种强大的工具，可以确保外包计算以高概率正确。承诺方案可用于将验证检查转换为具有组操作的身份。这确保了计算受到加密难题的保护。

Space and Time 正在努力将 SQL 查询外包给证明方并由验证方进行验证。