search

0xPolygonZero / plonky2

Apache License 2.0
758 stars 281 forks source link

Implement CTL bundling #1439

Closed LindaGuiga closed 8 months ago

LindaGuiga commented 9 months ago

This PR bundles, within a CTL, the looking tables associated to the same STARK together. This is done using helper columns.

Even though this adds helper columns when there are only 1 or 2 looking tables to bundle together, we can almost halve the number of commited columns for large groups of looking tables. For example, MemoryStark has 136 looking tables coming from KeccakSponge reads, but we only have to commit to 69 polynomials (68 helper columns and 1 Z polynomial) with the bundling.

sonarcloud[bot] commented 8 months ago

Quality Gate Passed Quality Gate passed

Kudos, no new issues were introduced!

0 New issues
0 Security Hotspots
No data about Coverage
No data about Duplication

See analysis details on SonarCloud

LindaGuiga commented 8 months ago

Update: With the new optimization PRs, there is no additional column: when there are only 1 or 2 columns for a STARK, we do not create helper columns.

matthiasgoergens commented 4 months ago

Why so complicated? Why introduce a completely new helper, instead of just bundling eg every two lookups into a single partial sum?

Is opening a single z polynomial only, on the first row cheaper, than opening many of them on the first row?