After the LUT optimisation the suffix table will be a significant factor.
Base on #60
Optimisation is described here: https://eprint.iacr.org/2025/1117.pdf
Relavent sections
- section 5.1: Gruen already implemented
- section 5.2: split optimisation. I believe it reuses the suffix table construction.
- appendix: shows a different construction than currently is implement. Experiment whether it is faster than current implementation.
Optimization-port audit — September 23, 2026
The existing GKR suffix table materializes the combined in-tree and tree-index domain. The current audit confirms this is the same split-table opportunity already owned by this issue, rather than a new degree-reduction task.
The additional implementation scope is to share in-tree equality weights across trees and apply each tree-index factor after local coefficient accumulation.
Sources
The target repository's existing relation, field encoding, coordinate order, and transcript contracts are authoritative. The current target implementation determines compatibility; the PoC implementation is reference-only and must be re-derived against those contracts.
In scope
- Document the target variable-order split z=(z_x,z_c) and derive eq(x,c;z)=eq(x;z_x)·eq(c;z_c), including round-to-round indexing.
- Retain only the two factors, reuse suffix construction where possible, and move tree-scale multiplication to aggregate coefficients.
- Preserve current equality-factor degree reduction, singular-coordinate behavior and coefficient reconstruction. Do not replace the transcript or proof grammar.
Out of scope: adding a second suffix-table issue, changing the GKR relation, or treating already-implemented Gruen/current-coordinate factoring as new work.
Potential impact
Factor-table storage/build is approximately O(2^k+2^s) instead of O(2^(k+s)) for k in-tree and s tree-index variables. Actual gains depend on reuse and shape; local accumulation and tree-scale work remain.
Done when
- Compare factor products, layer weights and all round coefficients with the dense suffix-table oracle across both coordinate splits and padding boundaries.
- Keep fixed-input GKR proof/transcript bytes identical; test equality coordinates 0 and 1 and ensure tampered round/closing/terminal claims still reject.
- Reject inconsistent dimensions and overflowed public geometry without out-of-range access.
- Benchmark table construction, retained bytes, coefficient accumulation and complete GKR under matched shapes and worker counts; distinguish this gain from lookup and lazy-layer changes.
Dependencies and coordination
Coordinate with #52. The GKR tracker #52 tracks the wider programme; this issue owns only the scoped implementation above.
After the LUT optimisation the suffix table will be a significant factor.
Base on #60
Optimisation is described here: https://eprint.iacr.org/2025/1117.pdf
Relavent sections
Optimization-port audit — September 23, 2026
The existing GKR suffix table materializes the combined in-tree and tree-index domain. The current audit confirms this is the same split-table opportunity already owned by this issue, rather than a new degree-reduction task.
The additional implementation scope is to share in-tree equality weights across trees and apply each tree-index factor after local coefficient accumulation.
Sources
The target repository's existing relation, field encoding, coordinate order, and transcript contracts are authoritative. The current target implementation determines compatibility; the PoC implementation is reference-only and must be re-derived against those contracts.
In scope
Out of scope: adding a second suffix-table issue, changing the GKR relation, or treating already-implemented Gruen/current-coordinate factoring as new work.
Potential impact
Factor-table storage/build is approximately O(2^k+2^s) instead of O(2^(k+s)) for k in-tree and s tree-index variables. Actual gains depend on reuse and shape; local accumulation and tree-scale work remain.
Done when
Dependencies and coordination
Coordinate with #52. The GKR tracker #52 tracks the wider programme; this issue owns only the scoped implementation above.