snarkify / sirius

A Plonkish folding framework for Incrementally Verifiable Computation (IVC).
MIT License
119 stars 17 forks source link

refactor(plonk): `is_sat` & `is_sat_relaxed` #202

Closed cyphersnake closed 6 months ago

cyphersnake commented 6 months ago

Motivation These functions were written very much in C, but not in Rust. Let me know if I've gone overboard, however now I at least understand the order of errors and calculations, as well as the error context being conveyed a bit better.

Overview

NonZeroUsize

Use NonZeroUsize type for mismatch count in errors

SomeToErr

An auxiliary some-to-err crate is used to shorten the construct

if let Some(err) = expr {
    return Err(err);
}

to

expr.err_or(())?

CountToNonZero

An auxiliary count-to-non-zero crate is used to shorten the construct

let count = iter.count();
if count != 0 {
    return Err(Error::Mismatch {
        count: NonZeroUsize::new(count).unwrap(),
    });
}

to

iter
    .count_to_non_zero()
    .map(|count| Error::Mismatch { count })
    .err_or(())?;

Better collect of par iter

par_iter
    .map(|d| func(d))
    .collect::<Result<Vec<F>, _>>()
    .map(|v| v.into_iter().filter(|v| F::ZERO.ne(v)).count())?;

to

par_iter
    .map(|d| {
        fund(d).map(|res| if res == 0 { 0 } else { 1 })
    })
    .try_reduce(
        || 0,
        |mismatch_count, is_missed| Ok(mismatch_count + is_missed),
    )

We save memory with this approach and don't do a double pass