揭秘新型零知識證明漏洞：算術運算後缺乏多項式標準化

Salus ｜2024-01-29 18:00

該漏洞會破壞假設並導致錯誤的計算，或導致透過rust panic 進行的拒絕服務攻擊。

作者：Salus Insights

Salus 在0xPARC 的zk-bug-tracker 庫中添加了一種新型的ZK 漏洞，算術運算後缺乏多項式標準化, 該漏洞由以太坊基金會PSE 安全團隊負責人Kyle Charbonnet 審核。該漏洞會破壞假設並導致錯誤的計算，或導致透過rust panic 進行的拒絕服務攻擊。為了更好地理解這個漏洞，我們將以Zendoo 函式庫中的一個具體實例進行說明。請大家對此類漏洞保持警惕。

1. 背景

在程式碼中，多項式被表示為向量的形式。即，多項式a0+a1x+...+an-1xn-1+an*xn 表示為[a0,a1,...,an-1,an]。在ZK 證明系統中，需要對多項式進行標準化操作，即將多項式的最高次項的係數調整為非零。例如，將[1,2,0]調整為[1,2]才是標準化的多項式表示法。

對多項式進行標準化操作是必要的。如果不進行標準化，系統會錯誤地儲存多項式的最高次數，即它會大於其實際的最高次數。例如，對於[1,2,0]，如果不進行標準化操作，它的最高次數會被錯誤地儲存為2，而實際上是1。基於非標準化的多項式生成證明時，錯誤的多項式實作將會使得ZK 證明系統panic，導致無法產生證明。

2. 案例分析

算術運算後缺乏多項式標準化，漏洞屬於ZK 證明系統實作上的通用性漏洞。以下，我們以Zendoo 函式庫中用於快速傅立葉變換（FFT）的密集多項式（dense polynomials）實現的程式碼為例，說明其中存在的算術運算後缺乏多項式標準化的漏洞。

add() 函數是用來對兩個密集多項式（self 和other）進行加法運算的，加法運算的結果（result）也是一個密集多項式，這需要進行標準化。然而，該函數僅在最後一個分支處對result 進行了標準化操作（19-21 行）。這個函數預設在前三個分支出計算得到的result 就是標準化的，但這是不合理的。例如，當self 是[1,2,3]，other 是[1,2,-3]，此時滿足第三個分支（7-12 行），即self 和other 這兩個多項式最高次數相等，都是2。而在第三個分支處計算後的result 是[2,4,0]，並未對其進行標準化操作。

非標準化的多項式在之後的計算過程中會產生誤差。具體的實作程式碼如下：

揭秘新型零知識證明漏洞：算術運算後缺乏多項式標準化

而且，在這段程式碼中，不只是在加法演算法後缺乏多項式標準化。在加法運算前，self 和other 作為add() 函數的入參，也並沒有檢查他們是否是標準化的多項式表示。或者說，建構self 和other 的函數是否是按照標準化的方法進行建構的，也未可知。 degree() 函數用來傳回多項式的最高次項的指數。在add() 函數中，非標準化的self 和other 在呼叫degree() 函數時會引起rust panic。

舉個例子，self 是非標準化的多項式1+2x+0x2，即向量[1,2,0]，其最高次項的係數為0。當other 也不是零多項式時，滿足add() 函數的第三個分支，以self 來呼叫degree() 函數。在degree() 函數中進入else 分支。在else 分支中有一個assert! 宏，用來確保多項式的最高次數的係數不為0。若為0，self.coeffs.last().map_or(false, |coeff| !coeff.is_zero()) 表達式結果為false。即self 向量的最後一個元素，即多項式的最高次項的係數為0，並傳回false。此時，assert! 宏會panic。

Rust panic 會導致ZK 證明系統遭受DOS 攻擊。攻擊者可以透過建構大量的非標準化多項式，並且不斷呼叫add() 函數。由於這些輸入會導致程式panic，所以程式會不斷地停止並重新啟動。這將佔用大量的運算和網路資源，從而影響到其他正常用戶的使用，這就構成了一種DOS 攻擊。

揭秘新型零知識證明漏洞：算術運算後缺乏多項式標準化

3. 總結

Salus 在0xPARC 的zk-bug-tracker 函式庫中加入的新型ZK 漏洞，即算術運算後缺乏多項式標準化，是具有通用性的。在ZK 證明系統中，我們需要特別注意避免該漏洞。此漏洞會造成ZK 證明系統的運算錯誤，或使系統遭受DOS 攻擊。可以在傳回算術運算結果之前呼叫truncate_leading_zeros()函數進行標準化操作，同時，基於from_coefficients_vec()函數來建構標準化的多項式也是必要的。

針對此漏洞，Salus 團隊提醒ZK 專案方，在建構多項式時和執行多項式操作之後對其進行標準化，以免破壞ZK 證明系統的完整性。同時，強烈建議專案方在專案上線之前，尋求專業的安全審計公司進行充分的安全審計，確保專案安全。