feat(nifs): impl `Protogalaxy::prove`

[cyphersnake]

Motivation Part of #266

Overview Implement Protogalaxy::prove

Note Since the tests involve refactoring existing code to test Vanilla (circuit reuse), I'll separate them into a separate PR

[cyphersnake]

I forgot to mention yesterday that I would like to validate:

• RelaxedPlonkTrace.U.E_commitment - just multiplies by l_0 every time, without any change. It looks like it could just be ignored for this fs.

• The pdf states that the accumulator is a commit from witness. We do it at the sps level, and ck is not used at all within prove. Is this correct?

[chaosma]

I forgot to mention yesterday that I would like to validate:

• RelaxedPlonkTrace.U.E_commitment - just multiplies by l_0 every time, without any change. It looks like it could just be ignored for this fs.

Ah, so the E_commitment is no longer needed and can be removed from protogalaxy's RelaxedPlonkInstance. It's role is replaced by e^* in the paper:

$$e^*=F(\alpha)L_0(\gamma)+Z(\gamma)K(\gamma)$$

• The pdf states that the accumulator is a commit from witness. We do it at the sps level, and ck is not used at all within prove. Is this correct?

Yeah, since it's already commited in sps, we don't need to commit anything and the _ck can be removed from the parameter list of fn prove

[cyphersnake]

Ah, so the E_commitment is no longer needed and can be removed from protogalaxy's RelaxedPlonkInstance. It's role is replaced by e^* in the paper:

Maybe we can just use E_commitment as e*? In this case it will be easy to support both of folding scheme in one moment. Maybe with rename + doc comment

[chaosma]

Ah, so the E_commitment is no longer needed and can be removed from protogalaxy's RelaxedPlonkInstance. It's role is replaced by e^* in the paper:

Maybe we can just use E_commitment as e*? In this case it will be easy to support both of folding scheme in one moment. Maybe with rename + doc comment

It's a little bit tricker. Because the E_commiment is a point on ECC. And e^* is a field element. You cannot reuse the type here.

[cyphersnake]

It's a little bit tricker. Because the E_commiment is a point on ECC. And e^* is a field element. You cannot reuse the type here.

Oh, yes, you are right. If we ever support a prod with two or more FSs, then we should put E_commitment also on the level of the accumulator structure, so that all the special data for each FS would be in clear places