Freivald's Algorithm
Articles based on Justin Thaler's Proofs, Arguments, and Zero-Knowledge
In the previous article we looked at how we can use Reed-Solomon encoding to create a probabilistic protocol that reduces the communication cost of verifying data equality between two independent parties. We did this by treating the subject data as a vector of coefficients to a univariate polynomial.
It turns out that we can also use Reed-Solomon encoding to reduce the computational cost of certain algorithms. Freivald’s algorithm is one such algorithm which can be used to verify that the result of a matrix multiplication is correct in less time than the fastest known deterministic algorithm.
Freivald’s Algorithm
We have three n × n matrices - A, B, and C. The matrices are over a finite field Fp where p > n². We want to verify that C = A⋅B in a more efficient manner than the fastest known deterministic algorithm which runs in worse than O(n²) time.
The algorithm starts by selecting a random element, r, from the finite field, Fp. We then produce a vector of field elements, x, which will allow us to treat the rows of the matrices as univariate polynomials1:
We then want to evaluate the following which will allow us to conclude that C is (probably) equal to A⋅B:
Why does this perform better than just evaluating A⋅B - C = 0? Because multiplying a matrix by a vector yields a vector:
Observe that the resulting vector looks like a univariate polynomial. Again, if you prefer to think in code, you can use this as a playground:2
use ndarray::{arr2, Array1};
fn main() {
// A and B
let a = arr2(&[[4, 0, 0], [0, 3, 0], [0, 0, 2]]);
let b = arr2(&[[1, 0, 0], [0, 2, 0], [0, 0, 3]]);
// C = A . B
let c = arr2(&[[4, 0, 0], [0, 6, 0], [0, 0, 6]]);
// Select a random r and generate x = (r^0, r^1, r^2)
let n = 3u32;
let r = 2u32;
let x: Array1<_> = (0..n).map(|i| r.pow(i)).collect();
// Check that Cx = A . B x
let cx = c.dot(&x);
let bx = b.dot(&x);
let abx = a.dot(&bx);
assert_eq!(cx, abx);
}The matrix and vector multiplication operation can be thought of as performing Reed-Solomon encoding of every row of the matrix. Whereas in the previous article we reduced a vector into a single field element, in Freivald’s algorithm, we are reducing some number of matrices into vectors of field elements. Both techniques can be thought of as reducing the problem of comparing large data sets to a comparison of Reed-Solomon fingerprints because both are subject to the same probabilities. This is to say that the Schwartz-Zippel Lemma for the special case of univariate polynomials applies here:
Two unequal polynomials of degree at most n, with coefficients in some finite field Fp, can evaluate to the same field element from the same input for at most n values in Fp.
Applying this lemma to our problem means that if C is not in fact equal to A⋅B, then the chance that the polynomials represented by Cx and A⋅Bx evaluate to the same field element is (n-1)/p.3 So if Cx and A⋅Bx end up being equal, we have a 1-(n-1)/p probability of correctly concluding that C = A⋅B. By ensuring that p is sufficiently large, we can increase our chance of correctness to a sufficient degree.
As such, we can view Freivald’s algorithm as a probabilistic proof system where the proof is the matrix C and the verification procedure is the evaluation of Cx = A⋅Bx which has O(n²) time complexity.
To conclude, we have now observed two probabilistic techniques that reduce runtime and communication costs of algorithms by transforming input data into distance-amplified encodings. This distance amplification moves the problem space into a domain of sufficiently high order such that the probabilities involved in the Schwartz-Zippel lemma allow us to efficiently verify equality of two arbitrarily sized values from the input domain.
So far, we have treated elements from our input vector as coefficients to a polynomial over a finite field:
Which can be Reed-Solomon encoded over a finite field for the purpose of distance amplification:
In the next article, we will look at an alternate approach which instead treats these elements as evaluations of a univariate polynomial over some canonical set of inputs. We will then explore how Lagrange interpolation can be used to derive this univariate polynomial for the purposes of our proof systems.
The vector x should remind you of the hash function from our Reed-Solomon fingerprint algorithm in the previous article.
This example involves only small matrices that are not over a finite field for the sake of illustrating the matrix arithmetic involved.