电路可满足性问题(Circuit Satisfiability Problem,简称 CSAT)是一种计算机科学中的决策问题,它属于 NP 完全问题的一种。电路可满足性问题的定义是:给定一个由逻辑门(如 AND、OR、NOT 等)组成的布尔电路,判断是否存在一组输入值,使得电路的输出为真。

电路可满足性问题的难度在于,电路的规模和复杂度可能非常大,而要找到一组满足条件的输入值,可能需要穷举所有可能的组合,这是非常耗时的。目前,还没有找到一种有效的算法,能在多项式时间内解决电路可满足性问题。

CAST 零知识问题

Bob 让 Alice 计算一个程序P对输入x的结果,但Bob不直接运行程序。

为让Bob相信结果一定是y,Alice的方法是:

  1. 拍摄整个计算过程,但这不现实。

  2. Bob将程序P转换成算术电路。Alice计算这个电路,记录每个门的输入输出值。

  3. Alice将记录结果交给Bob。Bob检查每门输入输出是否满足基本运算(例如加法), thus可以验证Alice没有作弊。

这张纸包含算术电路P的一个解solution,让Bob可以在不重复计算的情况下验证正确性。