feat: Protogalaxy folding of challenges

[codygunton]

We need to fold challenges as well. This means a refactor around how relation parameters are specified and relation degrees are calculated.

The RelationParameters class is now templated on a generic type T that could be a field or could be a Univariate class.

We need separate terminology for the length (==degree + 1) of a polynomial depending on whether we regard the challenges as constants or variables. I settled on "partial" and "total" since I think "partial degree" and "total degree" is what you'd expect in math. The way we calculate the total degree is to add some adjust ment factors. We only had to add these in three relations (the only three that make use of relation parameters). NB I focused only on relations for flavors where we intend to do folding.

If $f$ has length $l_f$ and $g$ has length $l_g$, then $f(g(X))$ has degree $(l_f-1)\cdot (l_g-1)$, hence its length is $(l_f - 1) \cdot (l_g - 1) + 1$. We need to calculate these of this form in cases now where the challenge parameters in $f$ are regarded as variable.

Since I had to refactor the relations, I do some light touching up of the relations for uniformity. I also move the Goblin Translator relations into a folder (like we already had for ECCVM) and move some of the Goblin relations that were contained in other relation files out into their own files.

I made some comments en route to calculating the total degree of the auxiliary relation. I leave those in since I think they'll be helpful later.

Checklist:

Remove the checklist to signal you've completed it. Enable auto-merge if the PR is ready to merge.

• If the pull request requires a cryptography review (e.g. cryptographic algorithm implementations) I have added the 'crypto' tag.
• I have reviewed my diff in github, line by line and removed unexpected formatting changes, testing logs, or commented-out code.
• Every change is related to the PR description.
• I have linked this pull request to relevant issues (if any exist).

[AztecBot]

Benchmark results

Metrics with a significant change:

• note_trial_decrypting_time_in_ms (8): 8.00 (-92%)

Detailed results

All benchmarks are run on txs on the Benchmarking contract on the repository. Each tx consists of a batch call to create_note and increment_balance, which guarantees that each tx has a private call, a nested private call, a public call, and a nested public call, as well as an emitted private note, an unencrypted log, and public storage read and write.

This benchmark source data is available in JSON format on S3 here.

Values are compared against data from master at commit 524cecf4 and shown if the difference exceeds 1%.

L2 block published to L1

Each column represents the number of txs on an L2 block published to L1.

Metric	8 txs	32 txs	128 txs
l1_rollup_calldata_size_in_bytes	45,444	179,588	716,132
l1_rollup_calldata_gas	223,020	868,256	3,449,768
l1_rollup_execution_gas	842,107	3,595,364	22,205,137
l2_block_processing_time_in_ms	1,955 (-3%)	7,520 (-1%)	29,576 (-1%)
note_successful_decrypting_time_in_ms	307 (+3%)	857 (-2%)	3,129 (-1%)
note_trial_decrypting_time_in_ms	⚠️ 8.00 (-92%)	64.0 (-20%)	134 (-1%)
l2_block_building_time_in_ms	13,157 (-1%)	52,404	208,184 (-1%)
l2_block_rollup_simulation_time_in_ms	11,842 (-1%)	47,188	187,173 (-1%)
l2_block_public_tx_process_time_in_ms	1,275	5,083	20,534

L2 chain processing

Each column represents the number of blocks on the L2 chain where each block has 16 txs.

Metric	5 blocks	10 blocks
node_history_sync_time_in_ms	21,458 (+1%)	41,994
note_history_successful_decrypting_time_in_ms	2,002	3,931 (+1%)
note_history_trial_decrypting_time_in_ms	120 (-1%)	144
node_database_size_in_bytes	1,628,798	1,096,427
pxe_database_size_in_bytes	27,188	54,187

Circuits stats

Stats on running time and I/O sizes collected for every circuit run across all benchmarks.

Circuit	circuit_simulation_time_in_ms	circuit_input_size_in_bytes	circuit_output_size_in_bytes
private-kernel-init	72.5 (+1%)	61,697	18,841
private-kernel-ordering	43.3	24,233	8,089
base-rollup	1,768	656,309	811
root-rollup	80.5 (-1%)	4,072	1,097
private-kernel-inner	52.7	81,504	18,841
public-kernel-private-input	41.4	41,455	18,841
public-kernel-non-first-iteration	26.4	41,497	18,841
merge-rollup	0.891 (-2%)	2,592	873

Miscellaneous

Transaction sizes based on how many contracts are deployed in the tx.

Metric	0 deployed contracts	1 deployed contracts
tx_size_in_bytes	8,723	27,240

[maramihali]

In my opinion, relation parameters folding should be done in the prover rather than instances because i believe it would make things more clear. But maybe I am not seeing the reasoning behind your choice of doing it prefolding.

I think the terminology partial and total combined with relation and subrelation gets sometimes confusing and I tried to highlight all the points where some clarification would be needed.

[maramihali]

was this include necessary here, i see it's also in other bench files that actually use relation parameters

[codygunton]

This file does use them on Line 26.

[maramihali]

my bad

[maramihali]

please explain what partial means here

[maramihali]

also, to be matching with the line above i'd use BATCHED_PARTIAL_RELATION_LENGTH

[codygunton]

But it's the "partial length of the batched relation" we're computing here, not the "batching of the partial relation length", so I think what I wrote is more meaningful.

[codygunton]

To avoid duplicating the same comments in every flavor file, I'll write descriptions of "total" versus "partial" in the comments that define the functions. That should be good enough, right? I think anybody who's curious would look there.

[maramihali]

yes, that makes sense, also did not realise the nuance until now, self note to take ordering into consideration in a name

[maramihali]

i find the usage of partial in the context of sumcheck a bit strange because in that case the partial degree is actually the total degree :-?

[maramihali]

Suggested change

	* univariate (i.e., sum them against an appropriate Lagrange basis) and then extended as needed during the
	* univariate (i.e., sum them against an appropriate univariate Lagrange basis) and then extended as needed during the

[maramihali]

how should I feel about double dereferencing?😅

[codygunton]

Ah, thanks for raising this yes what I did here was no good and I thought I'd left a TODO note to help me catch it. Will rework.

[maramihali]

why was there a 0 here?

[codygunton]

Becaue in practice it's extracted as the 0th type of a tuple type. Looking at it here again I thought it seemed a little odd. Can revert if you like.

[maramihali]

why capital?

[codygunton]

Fixed

[maramihali]

if this is regarding challenges as variables, shouldn't this be total length or am I misunderstanding something?

[codygunton]

Yeah I started with "full" and then decided "total" was better but I missed the renaming here, thanks.

[maramihali]

one refer

[maramihali]

:)