arkworks-rs / poly-commit

A Rust library for polynomial commitments
Apache License 2.0
326 stars 128 forks source link

Fix default check combinations #123

Closed mmagician closed 1 year ago

mmagician commented 1 year ago

Description

The trait-default implementation of check_combinations was incorrect. This was not detected because all of the implemented schemes have a custom implementation of this method. We are going to use the default method in Ligero though.

Description of the bug(s):

  1. The key in poly_evals: BTreeMap was of type (query_label, point), whereas the first element in the key tuple should have been a poly_label. This was causing map access here to fail with MissingEvaluation.
    • poly_query_set was keyed only with poly_label, but held multiple query values with the same poly_label. Iterating over its keys was be done in an arbitrary order.
    • The array we zip it with, evals, is returned calling values() on BTreeMap, the values are returned sorted by key of type (poly_label, point).
    • So the two constructed arrays were potentially in non-matching orders. To address this, we map the iterated poly labels as (poly_label, point), and collect first, so before it gets combined with a sorted vector of evaluations, it will itself get sorted on the correct key (poly_label, point). (2 might seem obvious in retrospect)

As mentioned, this is impossible to validate against the current codebase where all PCS have a custom implementation. To showcase the bug, I've sandwiched the actual fix in between 2 commits, where I first remove the custom impl from marlin_pc and later add it back after the fix. To verify the fix, you can check out 57ac1abc265928c58e1624a82b89c1bf490d724d, and run cargo test marlin::marlin_pc::tests::full_end_to_end_equation_test -> should fail. Then checkout the fix commit dcffaecc6b621174db3048811183b3960bd12f0d, run the same command, and verify the tests pass now.


Before we can merge this PR, please make sure that all the following items have been checked off. If any of the checklist items are not applicable, please leave them but write a little note why.

mmagician commented 1 year ago

Hmm I might have messed something up, I converted to draft for now

mmagician commented 1 year ago

Ok, I was a bit rash on squashing two loops into one - it turns out we need to first collect before zipping to ensure correct ordering by the new key. Ready now ✅

Pratyush commented 1 year ago

By the way @mmagician, in a separate PR, do you mind adding comments explaining what this code is doing? (Since you touched this code most recently you have the best idea.)