Lagrange interpolation over elements in finite field?

[yousefmoazzam]

Hi folks!

Firstly, many thanks to the contributors to the arkworks ecosystem, I've been playing with some of the crates in the project and it's been a fun experience 🙂

I've been working through this online book on zero knowledge programming where the code examples are in python, and I've been trying to test my understanding by doing analagous things in rust, using crates in the arkworks ecosystem when it seemed relevant.

I had a question about Lagrange interpolation of finite field elements to get the coefficients of a polynomial, and I was wondering if the community would be able to help me out a bit?

In the post in the online book on Lagrange interpolation, there's a small code snippet that I believe is doing something like:

• defining a finite field of 17 elements
• taking 4 elements in the field that we want to interpolate and find a polynomial which passes through all 4 points
• performing Lagrange interpolation on the 4 elements and getting back a polynomial
• then finally, checking that the interpolation was successful, by:
  • evaluating the interpolated polynomial at the 4 points which are the "x coordinate" of the 4 "y coordinates" which were interpolated
  • asserting that the result of the evaluations match the 4 values that we initially interpolated over

For reference, the python code snippet in the post I'm referring to is the following:

import galois
import numpy as np
GF17 = galois.GF(17)

xs = GF17(np.array([1,2,3,4]))
ys = GF17(np.array([4,8,2,1]))

p = galois.lagrange_poly(xs, ys)

assert p(1) == GF17(4)
assert p(2) == GF17(8)
assert p(3) == GF17(2)
assert p(4) == GF17(1)

Trying to follow the docs here, my best naive attempt so far at doing an analogous thing in rust using crates in the arkworks ecosystem was the following:

use ark_ff::fields::{Fp64, MontBackend, MontConfig};
use ark_poly::{
    univariate::DensePolynomial, DenseUVPolynomial, EvaluationDomain, GeneralEvaluationDomain,
    Polynomial,
};

#[derive(MontConfig)]
#[modulus = "17"]
#[generator = "1"]
pub struct FqConfig;
pub type Fq = Fp64<MontBackend<FqConfig, 1>>;

fn main() {
    const NO_OF_POLY_COEFFS: usize = 4;
    let small_domain = GeneralEvaluationDomain::<Fq>::new(NO_OF_POLY_COEFFS).unwrap();
    let x_values = vec![Fq::from(1), Fq::from(2), Fq::from(3), Fq::from(4)];
    let y_values = vec![Fq::from(4), Fq::from(8), Fq::from(2), Fq::from(1)];
    let coeffs = small_domain.ifft(&y_values);
    let poly = DensePolynomial::from_coefficients_vec(coeffs);
    for (x, y) in std::iter::zip(x_values, y_values) {
        assert_eq!(poly.evaluate(&x), y);
    }
}

#[cfg(test)]
mod tests {
    use super::main;

    #[test]
    fn verify() {
        main()
    }
}

However, I get an assertion error:

assertion `left == right` failed
  left: 4
 right: 2

and if I print the result of the evaluations I see that I get some values I didn't expect for the evaluation of the interpolated polynomial:

evaluating poly at 1 gives 4
evaluating poly at 2 gives 8
evaluating poly at 3 gives 4
evaluating poly at 4 gives 10

After browsing some of the issues, I know that part of why my code is incorrect is because I'm making the same error as in #921, but I admittedly don't understand the resolving comment for that issue. (I did start taking a look at how an IFFT can be used to compute the coefficients of a polynomial, but soon wondered if understanding that was overkill for what I'm wanting to get done, so decided to seek some help before going too far down that rabbit hole).

So, one part of this post was to ask if I could possibly get a bit more info on how that answer resolved the issue. Would I need to provide different values to evaluate the interpolated polynomial at to get what I want, rather than passing in the values in my x_values vector?

However, I did also want to step back and ask if I'm using the arkworks crates correctly to do Lagrange interpolation, am I using the right things to accomplish what I want? Or am I using the wrong tools fore the job? I did see the evaluate_all_lagrange_coefficients method which sort of sounds like what I'm looking for, but I didn't understand how to use it: I was expecting to be able to give it a vector of points/elements or something (like in the python example), so I was thrown-off when I saw that the method takes only one element as a parameter I think?

I hope my questions make some sense, please do let me know if I can clarify anything, and thanks in advance for any help! 🙂

[yousefmoazzam]

I've not fully figured this out, but have improved my understanding a bit, so I'll partially answer myself in case it could be of any help to anyone else.

I think I now understand the resolving comment in #921. In the context of my code example above:

• the y_values vector contains the field elements for which I want to find a polynomial that passes through
• if these field elements are considered as "output values" of some polynomial (that we don't know yet, it's not known until we interpolate), then the "input values" that are associated with those output values are the 4th roots of unity
  • 4th roots of unity because, given 4 evaluations, we can find a polynomial of maximum degree 3, which would require 4 coefficients to uniquely specify (the constant term being counted as a coefficient)
  • the use of the nth roots of unity in general as the evaluation points for the interpolated polynomial that we want to find is a consequence of how the FFT/IFFT algorithm makes use of roots of unity to achieve recursion in its divide and conquer approach
• once the interpolated polynomial has been computed, evaluating it at field elements 1, 2, 3, 4 and expecting them to be equal to the values which I originally interpolated is incorrect, because those values in y_values were assumed to be associated with the 4th roots of unity, not with the elements 1, 2, 3, 4
• evaluating the interpolated polynomial at the 4th roots of unity of the finite field with 17 elements (which are 1, 4, 16, 13) would instead be what yields the original values in the y_values vector that were interpolated

I know that I'm still missing something, because when I evaluate the interpolated polynomial at the 4th roots of unity (I assumed the ordering 1, 4, 16, 13 based on the ordering of the analogous 4th roots of unity over the complex numbers 1, i, -1, -i) I get two of the four coefficients of the polynomial slightly incorrect:

• python's galois library says the interpolated polynomial should be 11x^3 + 14x^2 + 4x + 9
• but the above rust code produces 13x^3 + 14x^2 + 2x + 9

But, things make more sense than before, which is good!

[yousefmoazzam]

Ok, back again to answer my own question a bit more in case it can help others to avoid making the same mistakes I did!

A silly mistake I made was the choice of generator for the finite field I defined. Somehow I mistook this as being generation of the field elements using the additive binary operator rather than the multiplicative binary operator in the field 🤦, and this mistake resulted in all four 4th roots of unity being calculated as 1. So, all four evaluations I gave were being interpreted as being at the same 4th root of unity 1, and this obviously messes with the interpolation being done to get the polynomial coefficients.

The only other issue I came across after that was that the roots of unity in the evaluation domain were ordered as going clockwise around the unit circle as opposed to my previous assumption of the ordering being counter-clockwise. Ie, the ordering of the roots of unity was 1, 13, 16, 4 (analogous to 1, -i, -1, i if thinking about the field being the complex numbers). This was checked by looking at what small_domain.elements().collect::<Vec<_>>() showed me as the elements in the evaluation domain.

The small program I ended up with to accomplish what I wanted is the following in case it's of use to anyone else: https://github.com/yousefmoazzam/circuits/blob/master/polynomial_playground/src/bin/simple_interpolation.rs.