Remove explicit terminal values

[jan-ferdinand]

Once all tables pad to the same height (#10), terminals do not need to be sent to the verifier explicitly. Instead, a cross-table terminal check akin to the currently existing cross-table initial check can be performed.

The main advantage of this approach is the removal of random initials while retaining zero knowledge. Because the terminal is never learned by the verifier, it cannot leak any information. Consequently, the running product (respectively, running evaluation) can always start with 1 (respectively, 0).

A minor advantage of this approach is a marginally decreased proof size.

[jan-ferdinand]

Upon further thought, this might not actually decrease but increase proof size, because a new quotient is being computed, of which correct addition to the combination codeword needs to be proven using Merkle authentication paths.

[jan-ferdinand]

Upon even further thought, the cross-table terminal quotient simply replaces the currently existing cross-table initial quotient. They are of the same size. Thus, the proof does indeed shrink.

[aszepieniec]

If I understand correctly, this suggestion would replace every pair of table-specific terminal constrains parameterized by the terminal, with one cross-table unparameterized terminal-equality constraint.

That alone saves quotients. However, why not merge all terminal-equality constraints into one with random linear weights supplied by the verifier?

[jan-ferdinand]

Yes, that makes perfect sense. In summary, we replace

1. the currently existing cross-table initial constraints, and
2. the currently existing terminal constraints for running products and running evaluations (sometimes called “running sums”)

with one verifier-randomized cross-table terminal-equality constraint.