Repository: nexus-xyz/nexus-zkvm
File: vm/src/circuit/r1cs.rs (Rust)

Code before:
                for i in 0..v.len() {
                    if v[i] != ZERO {
                        println!("{} * {}", v[i], self.w[i]);
                    }
                }
                println!("C");
                let v = &self.c[i];
                for i in 0..v.len() {
                    if v[i] != ZERO {
                        let mut rv = format!("{i}");
                        for (n, j) in &self.vars {
                            if *j == i {
                                rv.clone_from(n);
                            }
                        }
                        println!("{} * {} (name {})", v[i], self.w[i], rv);
                    }
                }
            }
        }

        (0..x.len()).all(|i| x[i] * y[i] == z[i])
    }
}

fn unique_values<Elm: Eq>(set: &[Elm]) -> bool {
    for (i, vi) in set.iter().enumerate() {
        for vj in set[0..i].iter() {
            if vi == vj {
                return false;
            }
        }
    }
    true
}

pub fn member(cs: &mut R1CS, name: &str, k: u32, set: &[u32]) {
    debug_assert!(set.len() > 1);
    debug_assert!(set.contains(&k));
    debug_assert!(unique_values(set));

    // Compute constant that comes from evaulating
    // (x - s0)(x - s1)...(x - s{n - 1}) / (x - sk)
    // at the point sk
    let C = |k: u32| -> F {
        let mut c = ONE;
        for &x in set {
            if x != k {
                c *= F::from(k) - F::from(x);
            }
        }

Review comment (bug):
I know this code will only be invoked on debug builds so performance doesn't matter all that much, but you can do this in `O(n)` rather than `O(n^2)` by using a `HashSet`.

Code after:
                let v = &self.b[i];
                for i in 0..v.len() {
                    if v[i] != ZERO {
                        println!("{} * {}", v[i], self.w[i]);
                    }
                }
                println!("C");
                let v = &self.c[i];
                for i in 0..v.len() {
                    if v[i] != ZERO {
                        let mut rv = format!("{i}");
                        for (n, j) in &self.vars {
                            if *j == i {
                                rv.clone_from(n);
                            }
                        }
                        println!("{} * {} (name {})", v[i], self.w[i], rv);
                    }
                }
            }
        }

        (0..x.len()).all(|i| x[i] * y[i] == z[i])
    }
}

fn unique_values<Elm: Eq + Hash>(set: &[Elm]) -> bool {
    let mut seen = HashSet::new();
    for v in set.iter() {
        if !seen.insert(v) {
            return false;
        }
    }
    true
}

pub fn member(cs: &mut R1CS, name: &str, k: u32, set: &[u32]) {
    debug_assert!(set.len() > 1);
    debug_assert!(set.contains(&k));
    debug_assert!(unique_values(set));

    // Compute constant that comes from evaulating
    // (x - s0)(x - s1)...(x - s{n - 1}) / (x - sk)
    // at the point sk
    let C = |k: u32| -> F {
        let mut c = ONE;
        for &x in set {
            if x != k {
                c *= F::from(k) - F::from(x);
            }
        }