Skip to main content

Analysis of a New Zero-Knowledge Proof Vulnerability: Missing Polynomial Normalization after Arithmetic Operations

ZEROBASE(formerly Salus) has added a new type of ZK vulnerability to the zk-bug-tracker library of 0xPARC, Missing Polynomial Normalization after Arithmetic Operations. This vulnerability has been reviewed by Kyle Charbonnet, the Ethereum Foundation’s PSE security team leader. This vulnerability can break assumptions and lead to erroneous computations, or cause denial of service attacks through rust panic. To better understand this vulnerability, we will illustrate with a specific example in the Zendoo library. Everyone, please stay vigilant about this vulnerability.

Background​

In code, polynomials are represented in the form of vectors. That is, the polynomial a0+a1x+⋯+an−1xn−1+anxna_0 + a_1 x + \cdots + a_{n-1} x^{n-1} + a_n x^n is represented as \[a_0,a_1,...,a_{n-1},a_n\]. In the ZK proof system, it is necessary to normalize polynomials, that is, to adjust the coefficient of the highest order term of the polynomial to non-zero. For instance, \[1,2,0]\ is adjusted to \[1,2\] to achieve a normalized polynomial representation.

Normalizing the polynomial is necessary. If not normalized, the system would incorrectly store the polynomial's highest degree, i.e., it would be greater than its actual highest degree. For example, for \[1,2,0\], if it is not normalized, its highest degree would be incorrectly stored as 22, while the actual is 11. When generating proofs based on non-normalized polynomials, incorrect polynomial implementations will cause the ZK proof system to panic, making it impossible to generate proofs.

Case Study​

The lack of polynomial normalization after arithmetic operations is a common vulnerability in the implementation of the ZK proof system. Here, we use the code in the Zendoo library for fast Fourier transform (FFT) of dense polynomials as an example to illustrate the vulnerability of lack of polynomial normalization after arithmetic operations.

The add() function is used to perform addition operations on two dense polynomials (self and other). The result of the addition (result) is also a dense polynomial, which needs to be normalized. However, this function only normalizes the result at the last branch (lines 19-21). The function assumes by default that the result calculated in the first three branches is normalized, but this is not reasonable. For example, when self is \[1,2,3\] and other is \[1,2,-3\], the third branch (lines 7-12) is satisfied, meaning the two polynomials, self and other have the same highest degree, which is 22. The result after the calculation at the third branch is \[2,4,0\], but it is not normalized.

Non-normalized polynomials will produce errors in subsequent calculations. The specific implementation code is as follows:

1. fn add(self, other: &'a DensePolynomial<F>) -> DensePolynomial<F> {
2.     if self.is_zero() {
3.         other.clone()
4.     } else if other.is_zero() {
5.         self.clone()
6.     } else {
7.         if self.degree() >= other.degree() {
8.             let mut result = self.clone();
9.             for (a, b) in result.coeffs.iter_mut().zip(&other.coeffs) {
10.                *a += b
11.            }
12.            result
13.        } else {
14.            let mut result = other.clone();
15.            for (a, b) in result.coeffs.iter_mut().zip(&self.coeffs) {
16.                *a += b
17.            }
18.            // If the leading coefficient ends up being zero, pop it off.
19.            while result.coeffs.last().unwrap().is_zero() {
20.                result.coeffs.pop();
21.            }
22.            result
23.        }
24.    }
25.}

Moreover, in this code, the lack of polynomial normalization is not only after the addition algorithm. Before the addition operation, self and other as input parameters for the add() function, are not checked whether they are normalized polynomial representations. Or rather, it is not clear whether the functions that construct self and other are built according to the normalization method. The degree() function is used to return the exponent of the highest degree term of the polynomial. In the add() function, non-normalized self and other will cause rust panics when calling the degree() function.

For example, if self is a non-normalized polynomial 1+2x+0x21+2x+0x^2, i.e., the vector \[1,2,0\], the coefficient of its highest degree term is 00. When other is also a non-zero polynomial, it satisfies the third branch of the add() function, and degree() function is called with self. In the degree() function, it enters the else branch. In the else branch there is an assert! macro that ensures the coefficient of the highest degree of the polynomial is not 00. If it is 00, the expression "self.coeffs.last().mapor(false, |coeff| !coeff.iszero())" returns false. That is, the last element of the self vector, the coefficient of the highest term of the polynomial, is 00, and false is returned. At this point, the assert! macro will panic.

Rust panics can lead to a DOS attack on the ZK proof system. Attackers can create a large number of non-normalized polynomials and continuously call the add() function. Since these inputs will cause the program to panic, it will repeatedly stop and restart. This consumes extensive computational and network resources, thereby affecting the use of the system by legitimate users, constituting a DOS attack.

// Returns the degree of the polynomial.
1. pub fn degree(&self) -> usize {
2.     if self.is_zero() {
3.         0
4.     } else {
5.         assert!(self.coeffs.last().map_or(false, |coeff| !coeff.is_zero()));
6.         self.coeffs.len() - 1
7.     }
8. }

Summary​

The new ZK vulnerability added by ZEROBASE in the zk-bug-tracker repository of 0xPARC, namely Missing Polynomial Normalization after Arithmetic Operations, is universal. In ZK proof systems, special attention is needed to avoid this vulnerability. It can cause computational errors in the ZK proof system, or make the system susceptible to DOS attacks. Normalization can be achieved by calling the truncate_leading_zeros() function before returning the results of arithmetic operations. Additionally, constructing normalized polynomials based on the from_coefficients_vec() function is also necessary.

Addressing this vulnerability, the ZEROBASE team advises ZK project developers to normalize polynomials both during construction and after performing arithmetic operations, in order to maintain the completeness of the ZK proof system. Furthermore, it is strongly recommended that developers seek comprehensive security audits from professional security audit companies before launching their projects to ensure their safety. If you need assistance, feel free to contact ZEROBASE(formerly Salus).

References​