AztecProtocol / barretenberg

Apache License 2.0
126 stars 77 forks source link

Scrutinize TOTAL_LENGTH_ADJUSTMENTS for log deriv lookup relation #1036

Open ledwards2225 opened 2 weeks ago

ledwards2225 commented 2 weeks ago

As far as I can, the log derivative lookup relation should require

static constexpr std::array<size_t, 2> TOTAL_LENGTH_ADJUSTMENTS{
    2, // inverse construction sub-relation
    1  // log derivative lookup argument sub-relation
};

However, using 1 for both seems to work. Note: because of the way the relation re-uses some arithmetic, currently the two adjustment factors have to agree, otherwise we end up doing operations with unlike univariates. So technically we would need to do

static constexpr std::array<size_t, 2> TOTAL_LENGTH_ADJUSTMENTS{
    2, // inverse construction sub-relation
    2  // log derivative lookup argument sub-relation
};

Its worth noting that the degrees described in the relations are in general an upper bound and can be smaller in practice. For example, this could happen in the lookup relation for a given row if we're folding two instances that both have q_lookup==1 at that row. In this case the univariate q_lookup is not linear but constant thus will not increase the degree of the relation. For this reason, I explicitly added protogalaxy tests that fold circuits that are inhomogeneous w/r/t to lookups, but they still pass. Am I just miscounting degrees in the relation? What's going on?