Zip+ with polylogarithmic proofs and verifier (Basefold/WHIR version of Zip+)

[albert-garreta]

[latifkasuli]

Did some design-space homework. Sharing the route map with the main obstruction and the path that looks most promising.

Notation: q_iprs = 2^16 + 1 is the small IPRS construction prime used for twiddle lifts, and m is the random post-commitment projection prime.

The load-bearing structural observation is that IPRS appears to have a Basefold-shaped folding structure. In a radix-2 view, centered lifts satisfy iota(-a) = -iota(a), so the pseudo-NTT butterflies pair twiddles as (t_j, -t_j). That matches the shape of the invertible diagonal-block interface Basefold folding needs, and each folding level should again be an IPRS code, MDS over Q by Lemma 7.2 / Theorem 7.3.

Two caveats make this a lemma to prove rather than something I would treat as already established: the implementation is radix-8, and lifting does not commute for free with reassociation into radix-2 stages. The precise statement probably needs to be invertibility/distance for the lifted 8x8 butterfly blocks at each level.

Route 1: fold directly over Q.

This looks structurally plausible, but probably value-negative. The paper has several ingredients: Theorem A.8 gives per-round MCA over Q for any linear code and finite challenge set, and the Appendix-B compiler already has the out-of-domain machinery. But a real protocol would still need an explicit foldability plus round-by-round soundness lemma, including per-round bitsize side conditions in the spirit of Remark 2.17.

The bit-growth model is the discouraging part. If we target roughly 100-bit total soundness after a per-round union bound, A.7’s n / (epsilon |R|) term pushes challenges to roughly 130 bits for n ~= 2^23. A division-free fold over Q then grows entries by about one challenge-width per radix-2-equivalent round, plus twiddle/clearing overhead. With roughly 20 rounds and around 100 queries, final entries are on the order of thousands of bits, and proofs look roughly MB-scale at N = 2^20. That is worse than the current Brakedown-style flat protocol.

I also looked for prior art that would rescue this direction. I did not find a Merkle-code IOPP that folds over Z or Q while controlling coefficient growth. The closest-looking works seem not to transfer directly: Basefold over Galois rings, eprint 2025/1767, works over a finite ring so this growth issue never appears; LatticeFold’s decompose-then-fold approach relies on homomorphic commitments rather than Merkle commitments.

Route 2: commit over Z, then project and fold over F_m.

This seems like the promising direction. Keep the integer Merkle commitment exactly as today, draw m post-commitment as usual, then run the folding IOPP over F_m on phi_m of the committed word. Growth disappears, and folding with lifted challenges commutes with phi_m, so the projected transcript is an honest finite-field folding transcript. Later folded oracles would be field oracles over F_m, while the initial oracle remains bound to the original integer commitment.

The conditional ladder, as I understand it, is:

If the projected IPRS code keeps distance/MCA at every folding level, which looks like Question 7.5 strengthened per level, then this should support a field-Basefold-style IOPP with no coefficient growth.

Full WHIR/STIR is a further step. Mod q_iprs, the code is genuinely RS, but q_iprs is only 17 bits. Mod m != q_iprs, the lifted encoder is not automatically an RS evaluation map, so the RS domain-shifting/query-reduction machinery needs either a proof of RS-compatible structure for projected IPRS, or a switch to a fresh RS/F_m commitment with a consistency argument binding it to the integer commitment, in the style of FRI-Binius, eprint 2024/504.

Side notes:

• Resolving Q7.4, Johnson-bound MCA over Q, would independently cut the flat protocol’s query count, even without folding.
• The grinding from Add proof-of-work grinding; bind combined_row into Fiat-Shamir #210 should port naturally, since per-round PoW is standard in this family.
• The cross-type batching question from Batched Zip+ for all three types of trace columns #184 becomes ordinary pre-fold claim batching in this design, so it may be cleanest to fold that discussion into this issue.

Is project-then-fold the direction you had in mind? I can work out the per-level Q7.5 numerics, the radix-8 foldability lemma, or a concrete round-by-round spec if useful.

[albert-garreta]

Thanks Latif. Neither approach would work. The first because of the bit growth. The second because projection destroys the capacity to make a soft range check on the bit-size of the committed witness.

I'm currently working on an AI implementation of our solution (not published anywhere yet). Once I'm settled with a design that works reasonably well I'll share more details so that we can turn it into a production-grade implementation.

cc @frozenspider

[latifkasuli]

Thanks Latif. Neither approach would work. The first because of the bit growth. The second because projection destroys the capacity to make a soft range check on the bit-size of the committed witness.

I'm currently working on an AI implementation of our solution (not published anywhere yet). Once I'm settled with a design that works reasonably well I'll share more details so that we can turn it into a production-grade implementation.

cc @frozenspider

Thanks, that makes sense, I'd missed that the integer combined-row check is also doing the soft bit-size duty (Remark 2.17), and once folding runs only through `F_m`, large representatives collapse mod `m`, so that information is unrecoverable downstream. I'll hold off on the Q7.5/radix-8 threads unless they turn out to be useful inside your design.

When the design is settled, happy to help turn it into a production implementation, transcript/oracle interface, parameter accounting, and benchmarks against the flat protocol.

[albert-garreta]

Thanks! What's your telegram and email? If you want I can invite you to a meeting with @frozenspider where I'll go over the design

[latifkasuli]

Thanks! What's your telegram and email? If you want I can invite you to a meeting with @frozenspider where I'll go over the design

Thanks, sounds good. I’d be happy to join.

Telegram: @latifkasuli

[albert-garreta]

@latifkasuli Telegram asks me to be premium to message you. Can you write me at @alb_g ?