Op-queue aggregation: Prove shift

[ledwards2225]

The op queue aggregation or Merge protocol is responsible for proving proper aggregation of the op queue contributions of a single circuit with the previous aggregate op queue. This is done via the formula $[T_i] = [T_{i-1}] + [t_i^{shift}]$, where $T$ represents an aggregate quantity and $t_i^{shift}$ is the contribution from a single circuit, right shifted such that it is properly appended to the end of the aggregate op queue. This requires commitment to $t_i^{shift}$. We also need $t_i$ (unshifted) in the main Goblin Ultra Honk protocol, where we currently commit to it directly. Currently, we establish no connection between $t_i^{shift}$ and $t_i$. There are two options: (1) Continue to commit to both the shifted and unshifted versions but add a feature to the protocol that establishes the connection, or (2) Reuse the commitment $[t_i^{shift}]$ computed in the merge protocol to prove evaluations of $t_i$ in the main protocol. (Note: it has to be this way not vice-versa since we strictly need $[t_i^{shift}]$ to compute $[T_i]$). This latter solution is more efficient but would require adapting ZM to include multiple shift sizes (which should be possible).

[ledwards2225]

One way to handle this: Continue to commit to both $t_i$ and $t_i^{shift}$ but pass $[t_i]$ from the ultra proof to the merge protocol. Merge continues to commit to $t_i^{shift}$ only to compute $[T_i]$ but evaluates $t_i(\gamma)$ and sends $[t_i]$ to the verifier who can then check $T_i(\gamma) = T_{i-1}(\gamma) + \gamma^{M_{i-1}}t_i(\gamma)$. This maintains the inefficiency of committing to both $t_i$ and shift but handles the connection of the two protocols.

[codygunton]

@ledwards2225 I assume this will be resolved by the folding approach to the merge protocol. Is that right?

[ledwards2225]

@ledwards2225 I assume this will be resolved by the folding approach to the merge protocol. Is that right?

It will have to be handled in some other way if we go with the merge via relations approach but an analogous thing will arise. Its also definitely not a foregone conclusion that we'll go with that approach - I dont think anyone has a complete description.

[arielgabizon]

Regarding the latter option of only committing to $t_i^{shift}$.
I'm not sure we know to do that? Shifting left entails dividing the commitment by r^k
rather than multiplying. And I'm not sure that's sound cause for a cheating prover using a polynomial that doesn't start with k zeroes you get a rational function.

Seems the cost of committing to both shifted and non-shifted is small.
(Also, if I read correctly - you don't need to send the commitment to the shifted poly -
it's just a step in the computation of $T_i$)