feat: shplemini claim batcher

[ledwards2225]

Implements ClaimBatcher for the Shplemini Verifier (more or less analogous to the prover's PolynomialBatcher, but its not a one to one due to the different nature of the prover and verifier in shplemini).

The idea here is again to isolate claim batching logic to a sub-class and to make it more straightforward to add new types of claims, e.g. k-shifted polynomials. With these updates, only the ClaimBatcher and the protocols that utilize k-shifts need to be updated, rather than an interface that's utilized across ~20 different files.

Note: I've again left out concatenations but its likely that they should be also be handled PolynomialBatcher/ClaimBatcher, despite having a slightly different structure.

[ledwards2225]

I prefer this std::optional container and if (container) to the if (container.size() > 0) syntax I used in the PolynomialBatcher. I think it makes the intent a bit more clear. (Or course right now all variants use both unshifted and shifted but eventually this will also contain k-shifts and concatenations which will only be used in certain protocols). If this stays as it is I'll plan to make that class match this one in that sense.

[maramihali]

I somehow prefer the has_unshifted() / has_shifted() pattern but no strong feelings. I'm worried this std::optional will get misused perhaps and we'll end up with the situation we had in sumcheck with the optional verified boolean.

[ledwards2225]

I hated that too but after some thorough googling I'm convinced that this is a very idomatic usage of optionals. I think the problem with the sumcheck use case was (1) it was a bad reason (just bc the prover and verifier shared a struct I think?) and (2) the external user had to know about the presence of optionals. Here its all encapsulated in the class and no one else has to know

[ledwards2225]

You'll notice that I used the arguably simpler designated initializer pattern for the ClaimBatcher. I opted not to do this for PolynomialBatcher because it requires a class be very simple (all public members, no explicitly defined constructors). The PolynomialBatcher requires more complicated initialization that sets metadata (full_batched_size) and initializes the batched polynomials, and this can only be done through an explicit constructor. Still, the lack of symmetry between these two somewhat analogous classes is annoying and I may try to find a way to make them resemble each other a bit more in a follow on.

[ledwards2225]

unrelated to this PR but while debugging something I discovered that this is entirely unused. Instead we use a VerifierCommitments object that is local to the relevant method.

[maramihali]

Thanks! Looks great, just left some thoughts

[maramihali]

i wonder whether we can somehow link the corresponding power of rho in here. I found myself several times checking whether the incorrect power could be the bug

[ledwards2225]

That would be nice I agree. I'll explore that when I'm adding the k-shifts here

[maramihali]

I somehow prefer the has_unshifted() / has_shifted() pattern but no strong feelings. I'm worried this std::optional will get misused perhaps and we'll end up with the situation we had in sumcheck with the optional verified boolean.

[maramihali]

maybe we can just name it scalar rather than batch_scalar as it's inferred from the way its used that the scalar is for batching

[ledwards2225]

yeah I generally agree. I hesitated beacuase scalar is just so generic but you're right, I'll change it

[maramihali]

maybe the multivariate_batching_challenge should just be called rho

[ledwards2225]

yeah this is the constant struggle I have with this code. Frankly a lot of it would be easier to read if all of the variables just used their math symbol name. I didn't want to make that change in some places but not others but I suppose since its isolated in this class I could do it

[ledwards2225]

changed to rho and rho_power

[maramihali]

this is great :)

[maramihali]

wonder whether negation here can be somehow encompassed in the functionality of claim_batcher

[ledwards2225]

I'll think about this when I think about the inclusion of rho / rho power in the batcher

[maramihali]

can't you do

.shifted = {commitments.get_to_be_shifted(), sumcheck_output.claimed_evaluations.get_shifted()}

does the ClaimBatch struct type need to be specified?

[ledwards2225]

I thought so too but it doesn't work in this case bc the parameters are std::optional. It seems like I could avoid it by explicitly initializing each input as optional but it ends up looking much worse