Skip to content

perf: investigate benefits of higher-degree constraints #372

@Nashtare

Description

@Nashtare

We currently rely for most scenarios on log_blowup: 3, because of the overhead of the number of queries induced by smaller blowup factors.

However all constraints are currently of degree 3 or less, which feels a bit wasteful with such a blowup factor.

Immediate applications of actually allowing larger constraint degrees are:

  • Poseidon2Perm table for KoalaBear (specifically): computing 2 rounds into one row, thanks to its degree-3 S-Box, would result in degree 9 constraints.
  • ALU table:
    • computing a "wide" Horner accumulation, i.e. batching 4 coefficients instead of 2 in the accumulator per operation. This would be of degree 5, i.e. fitting even with log_blowup: 2
    • additional operations: we already expose a 3rd operand for the MulAdd operation. With an additional selector (preprocessed), we could support MulMul for instance
    • better encoding of selectors for fewer columns

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions