# Space and Time's ZK coprocessor

By [TheirsMeta.eth](https://paragraph.com/@theirsmeta) · 2024-09-30

---

![](https://storage.googleapis.com/papyrus_images/e328edaadc504954a10c34d33f0b5c221b46cb0d8c157ac928dac8035866875a.png)

可验证计算的背景和定义
-----------

随着移动设备的普及和计算任务复杂性的增加，outsourcing计算执行变得越来越重要。可验证计算（Verifiable Computing）是研究如何外包计算任务，同时确保计算结果正确性的一门学科。

可验证计算的基本概念
----------

1.  **证明者（Prover）**：执行计算的一方，通常被称为Peggy。
    
2.  **验证者（Verifier）**：验证计算结果正确性的一方，通常被称为Victor。
    

高概率验证
-----

传统的NP问题虽然符合"难解易验证"的特性，但实际验证过程仍可能过于耗时。因此，可验证计算采用高概率验证的方法，通过放宽验证标准来提高效率。

经典例子：矩阵乘法验证
-----------

通过Frevald算法，验证者可以在O(n^2)的时间复杂度内高概率地验证n x n矩阵乘法的结果，而不是直接进行O(n^2.3728596)复杂度的矩阵乘法。

承诺方案（Commitment Schemes）
------------------------

承诺方案是可验证计算算法中的关键组成部分，主要用于：

1.  锁定证明者的声明，防止其在验证过程中更改声明。
    
2.  利用加密学中的难题（如离散对数问题）来保证算法的安全性。
    

可验证计算的一般框架
----------

1.  证明者提供承诺（commitments）。
    
2.  验证者提出挑战（challenges）。
    
3.  证明者根据挑战提供新的承诺。
    
4.  最终通过身份等式检查结果的有效性。
    

非交互式验证
------

为了减少通信开销并适应区块链等应用场景，可以使用Fiat-Shamir启发式方法将交互式协议转换为非交互式协议。这种方法用哈希值替代验证者的挑战，使得任何人都能独立验证结果。

Space and Time项目的应用
-------------------

Space and Time项目正在努力将SQL查询外包给证明方，并由验证方进行验证。这一应用展示了可验证计算在数据库查询领域的潜力。

结论
--

可验证计算是一种强大的工具，能够以高概率确保外包计算的正确性。通过使用承诺方案，可以将验证过程转化为基于群运算的身份等式，从而利用加密学中的难题来保证计算的安全性。这一技术在各种需要外包计算的场景中都有广泛的应用前景，尤其是在确保数据完整性和计算正确性至关重要的领域。

官网：

[https://spaceandtime.io](https://spaceandtime.io)

---

*Originally published on [TheirsMeta.eth](https://paragraph.com/@theirsmeta/space-and-time-s-zk-coprocessor)*