动机
验证者可能无法逐一把指数多个值相加,但它可以向一个不受限制的证明者索取一份简短的摘要,并在一个随机点上检验该摘要。和检验协议(sum-check protocol)针对有限域上的多项式,将这一想法精确化。其威力来自两个事实:一个次数有界的错误多项式恒等式只有很少的根;并且验证者是在看到证明者当前消息之后才选取每一个挑战。
定义 9.2.1
(和检验问题)
设 为大小为 的有限域,设 ,并设 对每个变量分别而言次数至多为 。验证者收到一个所声称的值 ,以及 的一个算术电路表示。问题是:是否有
其中求和在 中进行。
次数上界是问题承诺(promise)的一部分,或者通过语法次数证书(syntactic degree certificate)来验证;它不能仅靠对电路取样推断得出。概率分析先使用任意有限域上的理想均匀取样。在下面标准的固定公平随机比特交互证明推论中,我们限制 ,并用给定的不可约二元多项式表示:均匀的 比特串恰好给出均匀域元素。 上的例子说明理想域取样,而不是固定长度公平比特的精确取样器。我们假定域运算高效且 有多项式界,因此 个系数构成多项式大小的消息。
对于语法证书,给每个输入变量指派:对其自身为一次、对其他变量为零次;给常数指派零次。在加法门处,对两个输入端的上界取逐坐标最大值;在乘法门处,则将其相加。由归纳法可得到每个变量次数的一个上界。若所有输出的上界都至多为 ,则该承诺得到证明。由于相消可能使真实次数小于此上界,因此该检验是充分的而非必要的。
协议的一轮
令当前声称值为 。在第 轮中,在先前的随机挑战 已选定之后,证明者发送一个次数至多为 的一元多项式 的系数。验证者检验
若等式不成立,则拒绝。否则,它均匀地随机取一个新的 ,将该挑战发送给证明者,并令 。第 轮之后,验证者利用电路计算 ,并且当且仅当 等于该值时接受。系数个数多于 的消息会被拒绝,而不会被当作较低次数的多项式处理。
证明者可以具有无限的计算能力,并且可以在看到先前的挑战之后再选择后续的消息。但它在发送 之前无法看到 。验证者并不枚举 个布尔(Boolean)输入;它只在最后的随机点上对电路求值一次,并对这些消息进行多项式次数的域运算。
概念视角算法
每一轮都是化为少一个布尔变量的归约
记 ,于是 是所声称的和,而 。第 轮把声称“”换成声称“”。恒等式 正是检验 所验证的内容;随机的 则把 两个点换成一个点。经过 轮之后,声称只涉及 ,验证者可以自己计算。
例题 9.2.2
(F13 上一个诚实的二元变量记录)
设 ,。其布尔和为 。在第一轮中,诚实的多项式为
验证者检验 。若它的第一个挑战为 ,则新的声称值为 。第二个诚实消息为 ;它在零和一处的值之和为 。若 ,则最后的声称值为 ,与 中的 相符。
常见错误
(证明者的多项式不可信任)
验证者检查消息的长度以及所声称的求和关系,但它并不知道 就是诚实的部分和。不诚实的证明者可以发送任何被允许的多项式,且该多项式可以利用整个先前的记录来选择。可靠性必须对每一种这样的策略都成立,而不仅仅是针对偶然发生孤立算术错误的诚实证明者。
完备性与自适应可靠性
定理 9.2.3
(和检验的正确性)
若 是 的布尔和,则对于任意的挑战序列,诚实的证明者都能使验证者接受。若 是错误的,则每一种证明者策略使验证者接受的概率至多为 。
证明
(证明)
先证完备性。在第 轮中,诚实的证明者发送
当 时,该和只有一项,不再有剩余的布尔变量。每个 关于 的次数至多为 。当当前声称值正确时,按 或 拆分其余的布尔和,即得 。更新使 成为固定 之后正确的部分和。在最后一轮,它等于 ,因此验证者接受。
再证可靠性。固定任意一段记录,直到第 轮新的随机挑战之前的时刻为止,其中包括证明者所选择的多项式 。用同一公式定义真实的部分和多项式 。假设当前声称值 是错误的,但验证者的求和检验通过了。那么 不可能等于 ,否则它们在零和一处的值之和就会等于真实的前一个部分和。非零多项式 的次数至多为 ,在 中至多有 个根。因此,在以整个过去的记录为条件下,新的均匀随机元素 使该错误声称值变为正确的概率至多为 。
起初声称值是错误的。若它从未变为正确,则最后与 的比较会拒绝。要发生接受,必须存在某个第一轮,使得错误的声称值在该轮变为正确。无论自适应策略或先前的挑战如何,该事件在每一轮中的条件概率都至多为 。对至多 个可能的“第一轮”求和,得到接受概率至多为 。提前拒绝只会降低该概率。
证明透视
次数上界与消息次序在哪里起作用
这个论证只有一个想法和两项假设。想法是找出假的断言第一次变为正确的那一轮。只要断言 为假,诚实多项式 就不能通过检验,因为 是真实的部分和;所以通过检验的消息必与 不同, 是非零多项式。次数上界 把它的根数限制在 个以内。消息的次序使这些根在抽取 时已是固定的集合,因此无论先前的历史如何,均匀的 命中其中一个的概率至多为 。证明以对 轮中可能最先修复断言的一轮取并集界作结;若没有任何一轮做到,最后的断言仍为假,最终的电路求值就会拒绝。若取消次数上界, 可以有 个根:在 上,对 发送 ,在全部十二个非零挑战处都为零,下文的例子正说明这一点。
根的个数上界适用于非零的一元多项式,而不是直接适用于多元电路。固定先前的变量并对后面的布尔选择求和,使每一轮都化为一个一元的比较。该证明还用到了消息的顺序:若证明者可以在看到 之后再选择 ,则条件根计数的论证将不再适用。
反例模式
可预测的挑战让证明者作弊
有人可能以为挑战不必随机:验证者可以固定使用 。取 、、、,以及错误的声称 。证明者发送 。此时 ,而验证者最后的值为 ,于是以概率一接受了错误的声称。证明需要 均匀,并且在 确定之后才选取;证明者能够预测的挑战,并不比它先看到的挑战好。
例题 9.2.4
(域的大小控制可靠性界)
对于 、 以及 ,错误的和被接受的概率至多为 。这是针对每一个自适应证明者的上界,并不是说存在某个证明者恰好达到 。若在只有两个元素的域上使用相同的次数和轮数,则界 不会给出任何有用的可靠性保证。选取 可使该界至多为 。
多元根的上界
和检验的证明在每一轮中只需要一元根的上界。一个相关的多元结果在其他随机化恒等式检验中很有用。这里,总次数指的是所有非零单项式的指数之和的最大值。
命题 9.2.5
(有限域多项式恒等式界)
设 非零,且总次数至多为 。若 是大小为 的有限域 中相互独立的均匀元素,则
当 时,该界可能至少为一,此时它不提供有用的信息。
证明
(证明)
对变量个数作归纳。对于一个变量,该断言就是通常的结论:非零的 次多项式至多有 个根;非零常数没有根。对于归纳步骤,写
其中 。 中的每个单项式的总次数至多为 。由归纳假设, 在前 个随机值处为零的概率至多为 。若它不为零,则所得关于 的一元多项式是非零的 次多项式,在新取的最后一个值上为零的概率至多为 。将这两个界相加得到 。情形 也包含在内:一旦非零系数被固定,所得的常数没有根。
例题 9.2.6
(一个二元变量的零点集)
在 上,设 。它的总次数为二,当 或 时为零。这样的数对共有 个:交点 被重复计算了一次。其为零的概率为 ,低于一般的界 。该界不一定是精确的,并且非零多项式在某些随机输入上也可能取零而并不是零多项式。
针对自适应证明者的重复
若 ,则以新的独立挑战运行该协议 次,并且仅当每一次运行都接受时才接受,可得可靠性至多为 。证明者可以使其后续的消息适应所有先前的记录。尽管如此,以新一次运行之前的任意历史为条件,当前的错误声称值以及证明者由此产生的策略仍然满足同样的单次运行可靠性界。把到达并通过相继各次运行的条件概率相乘,即得该界。完备性依然完美,因为诚实的证明者通过每一次运行。通信量和验证者的时间增加 倍,因此在所述约定下,多项式次数的重复仍然是高效的。
例题 9.2.7
(一个乘积多项式)
设 ,在 上。其布尔和为一,因为只有 有贡献。第一个诚实消息为 。若验证者选取 ,则声称值变为五。第二个消息为 ,其在零和一处的值之和为五。取 ,验证者检验最后的值 。每个消息的次数为一,并且协议仅在最后的数对上对原电路求值。
为什么次数限制是必要的
命题 9.2.8
(一个高次数的作弊消息)
若不强制要求证明者消息满足次数上界,则即使真实多项式恒等于零,最后的随机求值也不一定能给出有用的可靠性保证。
证明
(以例子证明)
考虑 上的一个变量,令 ,并错误地声称 。不诚实的证明者发送 。它的初始检验通过,因为 。对于 中每个非零的 ,由拉格朗日(Lagrange)定理得 ,因此 。于是验证者以概率 接受,尽管真实的和为零。该消息的次数为十二,当允许的次数为 时会被拒绝。
例题 9.2.9
(域中的和并不自动等于整数计数)
设 是 上某个布尔公式在布尔输入上的指示多项式。若恰有三个布尔赋值满足该公式,则 中的和为 ,而不是整数三。和检验记录所验证的是所声称的域中的和。要恢复精确的整数计数,或者利用算术化来证明某个复杂度类的交互式刻画,还需要进一步的选择与论证。
命题 9.2.10
(承诺求和问题的一个交互式协议)
在所述的多项式消息约定下,对给定的二元扩域 ,若 且单变量次数界有效,则该承诺问题有一个使用固定公平随机比特的公开硬币交互协议,具有完美完备性且可靠性误差至多为 。
证明
(证明)
验证者在每个多项式消息之后发送一个由独立 比特均匀取样的域元素,然后对输入电路求值一次。系数列表在 轮中每轮的长度至多为 ,因此在所述的表示与大小界之下,通信量和验证者的时间是多项式的。完备性是精确的,而和检验定理将错误声称被接受的概率限制在 。这些结论适用于满足承诺的输入;验证者无法检验的域或次数承诺,不会被悄悄地当作任意良构的语言实例。
完整的定理 还使用了额外的算术化、量词以及次数控制的机制,这些在此处并未证明。和检验只是其中一个组成部分,而不是该刻画的独立证明。域的表示、高效取样、次数界以及多项式的消息长度,都是协议所述设定的一部分。
练习与解答
快速检查
(对于 上的 ,计算它在四个布尔数对上的和。)
在 处求 的值。
解答 · 答案
各值为 ,其和在 中为 。
快速检查
(为什么每一轮中诚实多项式的次数至多为 ?)
固定变量或对变量求和时,次数会如何变化?
解答 · 答案
固定先前的变量,并把其后的变量代入零或一,都不会增加余下变量的次数。把所得多项式相加,也不会增加它们的最大次数。
快速检查
(若虚假的当前声称通过了证明者的求和检验,为什么所发送的多项式必须不同于真实的部分和多项式?)
真实多项式在零与一处的值加起来是什么?
解答 · 答案
真实多项式在零与一处的值之和等于真实的上一个部分和。若当前声称为假,而所发送多项式的两个值之和等于它,则所发送的多项式不可能等于真实的多项式。
快速检查
(当 、 且域的大小为 时,可靠性界是多少?)
使用 。
解答 · 答案
界为 。
快速检查
(在高次数作弊的例子中,为什么验证者对每个非零挑战都接受?)
在 中计算 。
解答 · 答案
的每个非零元素都满足 ,所以 。最初的假求和检验是特意安排成通过的。
快速检查
(在 中验证一个和,能否得知满足赋值的确切整数个数?)
哪些个数在模二下取值相同?
解答 · 答案
不能。它只给出个数模二的结果。不同的个数,例如一与三,在 中的值相同。