FRI 是鄰近性證明，而非低次測試

原文：https://building-babylon.net/2025/01/10/fri-is-a-proof-of-proximity-not-a-low-degree-test/

作者：Benjamin Wilson

譯者：Kurt Pan

（以下的思想實驗由我的同事 Ryan Cao 提出；錯誤與情緒化言辭皆由本人負責。）

FRI 通常被描述為「低次測試」，這讓人以為若多項式的次數很高，驗證者就應當以高機率拒絕。事實並非如此，下列簡單例子即可說明。實際上，次數最高的多項式反而最可能被驗證者誤判接受。真正成立的是：若求值向量遠離碼，FRI 驗證者才會以高機率拒絕；FRI 本質上是一種鄰近性證明。

設  為一個域， 且 。定義求值映射

對任意 ，令

為在  上、次數嚴格小於  的多項式之求值所構成的 Reed–Solomon 碼。

以下假設  為乘法群  的子群，且  為二的冪。次數上界  亦設為二的冪。對 ，設  為 FRI 的「折疊」（folding）操作（於係數域中）；令

為相應的求值域操作。可驗證對任何  與 ，皆有

FRI 透過驗證者提供的隨機挑戰值，反覆進行折疊。欲證明 「鄰近」碼 ，首先歸約到證明鄰近碼 ，如此往復，直到聲稱  鄰近 （常數向量組成的碼）。此時驗證者隨機抽查  個座標，若全部一致，即（以高機率）認定  鄰近其碼，從而推斷原始向量  亦鄰近最初的碼。證明 FRI 確為良好的鄰近性測試甚為繁複；然而，FRI 從未被設計為可靠的高次數檢測器。以下即示範其無法有效拒絕高次度多項式。

對每個 ，設 Lagrange 插值多項式

此多項式之次數為 ，亦即在給定求值域大小下達到最大次數。然而，其求值向量呈「單熱」（one‑hot）：

對零碼字的 Hamming 距離僅為 1，可謂在碼附近的極致，卻並不屬於碼。由上式（折疊公式）可得

亦即除非 （機率可忽略不計），折疊後向量與其碼  的 Hamming 距離仍為 1，但相對距離增加一倍（因求值域規模減半）。

設 。經  輪折疊後，（除極小概率外）仍僅在一處非零，其與常數碼  的相對距離為 ，即原始碼率 。驗證者接受的機率為 。由於實踐中  常極小（例如 ），而  又很小，此機率幾乎為 1。因此，把 FRI 稱為「低次測試」乃為誤導（雖普遍）──最大次數的  多項式常被 FRI 驗證者接受。原因在於其求值向量距碼極近；畢竟，FRI 只是一個鄰近性證明。