動機
驗證者可能無法逐一加總指數級數量的值,但它可以向不受限制的證明者索取一份簡短的摘要,並在隨機點上檢驗該摘要。求和檢驗協議(sum-check protocol)針對有限域上的多項式,將這個想法精確化。其威力來自兩項事實:次數有界的錯誤多項式恆等式只有少數根;以及驗證者是在看到證明者當前訊息之後,才選取每一個挑戰值。
定義 9.2.1
(求和檢驗問題)
設 為大小為 的有限域,設 ,並設 在每個變量上各自的次數至多為 。驗證者收到一個所聲稱的值 ,以及 的算術電路表示。問題是下式是否成立:
其中求和在 中進行。
次數上界屬於問題的承諾(promise),或由語法次數證書驗證;它不是僅靠對電路取樣而推斷出來的。概率分析先使用任意有限域上的理想均勻抽樣。在下面標準的固定公平隨機位元互動證明推論中,我們限制 ,並用給定的不可約二元多項式表示:均勻的 位元字串恰好給出均勻域元素。 上的例子說明理想域抽樣,而不是固定長度公平位元的精確抽樣器。我們假設域運算高效且 有多項式界,因此 個係數構成多項式大小的訊息。
對於語法證書,為每個輸入變量指定:在自身上的次數為一、在其他變量上的次數為零;並為常數指定次數零。在加法閘處,取兩個輸入上界的逐座標最大值;在乘法閘處,則將兩者相加。由歸納法可得到每個變量次數的上界。若所有輸出上界至多為 ,則該承諾得到證明。由於抵銷可能使真實次數小於此上界,因此這個檢驗是充分條件而非必要條件。
協議的一輪
設當前聲稱為 。在第 輪中,在先前的隨機挑戰值 已選定之後,證明者送出一個次數至多為 的單變量多項式 的係數。驗證者檢查
若等式不成立,則拒絕。否則,它均勻地取樣一個全新的 ,把該挑戰值送給證明者,並令 。在第 輪之後,驗證者利用電路計算 ,且恰好在 等於該值時接受。係數多於 個的訊息會被拒絕,而不會被當作較低次數的多項式處理。
證明者可以具有無限的計算能力,並且可以在看到先前的挑戰值之後才選擇後續的訊息。但它在送出 之前無法看到 。驗證者不會列舉 個布爾(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
(承諾求和問題的互動式協議)
在所述的多項式訊息約定下,對給定的二元擴域 ,若 且個別變量次數上界有效,則該承諾問題擁有使用固定公平隨機位元的公開擲幣互動協議,具有完美完備性且可靠性誤差至多為 。
證明
(證明)
驗證者在每個多項式訊息之後送出一個由獨立 位元均勻抽樣的域元素,然後對輸入電路求值一次。在 輪中,每輪的係數列表長度至多為 ,因此在所述的表示與大小界下,通訊量與驗證者時間皆為多項式。完備性是精確的,而求和檢驗定理將錯誤聲稱的接受概率上界定為 。這些結論適用於符合承諾的輸入;驗證者無法檢查的域或次數承諾,不會被悄悄地當作任意格式良好的語言實例。
完整的定理 使用了額外的算術化、量詞與次數控制機制,這裏並未予以證明。求和檢驗只是其中一個組成部分,而不是該刻劃的獨立證明。域的表示、高效取樣、次數上界以及多項式訊息長度,都是該協議所述設定的一部分。
練習與解答
快速檢查
(對於 上的 ,計算它在四個布爾數對上的和。)
在 處求 的值。
解答 · 答案
各值為 ,其和在 中為 。
快速檢查
(為何每一輪中誠實的多項式次數至多為 ?)
固定變量或對變量求和時,次數會如何變化?
解答 · 答案
固定先前的變量,並把其後的變量代入零或一,都不會增加餘下變量的次數。把所得多項式相加,亦不會增加它們的最大次數。
快速檢查
(若虛假的當前聲稱通過了證明者的求和檢驗,為何所發送的多項式必須不同於真實的部分和多項式?)
真實多項式在零與一的值加起來是甚麼?
解答 · 答案
真實多項式在零與一的值之和等於真實的上一個部分和。若當前聲稱為假,而所發送多項式的兩個值之和等於它,則所發送的多項式不可能等於真實的多項式。
快速檢查
(當 、 且域的大小為 時,可靠性界是多少?)
使用 。
解答 · 答案
界為 。
快速檢查
(在高次數欺騙的例子中,為何驗證者對每個非零挑戰值都接受?)
在 中計算 。
解答 · 答案
的每個非零元素都滿足 ,所以 。最初的假求和檢驗是特意安排成通過的。
快速檢查
(在 中驗證一個和,能否得知滿足賦值的確切整數個數?)
哪些個數在模二下取值相同?
解答 · 答案
不能。它只給出個數模二的結果。不同的個數,例如一與三,在 中的值相同。