feat: Goblin translator non-native field relation (Goblin Translator part 6)

[Rumata888]

This PR adds the last of the Goblin translator relations (the non-native field relation) to the codebase. It also adds consistency tests.

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_history_trial_decrypting_time_in_ms (10): 215 (+41%)

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 db3fa62e 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	222,912	867,776	3,447,908
l1_rollup_execution_gas	841,999	3,594,884	22,203,277
l2_block_processing_time_in_ms	1,039 (+2%)	4,081 (+4%)	15,583 (+1%)
note_successful_decrypting_time_in_ms	340 (+1%)	1,043	4,018 (+2%)
note_trial_decrypting_time_in_ms	41.0 (+5%)	108	138 (+1%)
l2_block_building_time_in_ms	9,013 (+1%)	35,879 (+1%)	158,408 (+1%)
l2_block_rollup_simulation_time_in_ms	6,659 (+2%)	26,450 (+1%)	105,834 (+1%)
l2_block_public_tx_process_time_in_ms	2,314 (+1%)	9,304	51,859

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	11,776 (-3%)	22,490 (+2%)
note_history_successful_decrypting_time_in_ms	2,443 (-5%)	4,763 (-1%)
note_history_trial_decrypting_time_in_ms	122 (-1%)	⚠️ 215 (+41%)
node_database_size_in_bytes	1,662,182	1,200,902
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	47.8	61,697	18,841
private-kernel-ordering	23.4 (-2%)	24,233	8,089
base-rollup	854	639,797	811
root-rollup	40.7 (+7%)	4,072	1,097
private-kernel-inner	43.3 (-1%)	81,504	18,841
public-kernel-private-input	47.9	41,455	18,841
public-kernel-non-first-iteration	31.2 (-2%)	41,497	18,841
merge-rollup	0.870 (+7%)	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,508

[codygunton]

Ok, I had a look through and think that the relations are computed as advertised. Nice work. I left a few comments. The most important is about how you initialize some things in the relation parameters.

Some other things:

• As I read this I reformatted some comments to help me process. I pushed those changes. Do you mind having a look at that? We can revert if you don't like it.
• The relation could use some logic tests, not just a consistency test, to convince someone that it is doing what it is intended to do, rather than to show it matches some other inscrutible huge formulas. If you don't have time to write this could you leave a TODO issue in Bb repo?
• For expediency I can see why you added stuff to the relation parameters, but it looks pretty hacky to me--is there not more appropriate place? The VMs should probably get some additional state structure that is uniform across them. Maybe now is not the time... could you please look for for a different and more robust solution as you work on the Public VM?
• The term "shift" is pretty overloaded here: it refers to a shift of execution trace but also of the degrees of the binary basis limbs. Prob it's too late to fix, just noting it was confusing.
• Ditto for the z's--why not just z_lo = z_lo_lo + shift * z_lo_hi? I had trouble checking part of the logic due to the naming there being the opposite of what I'd expect.

[codygunton]

I think these are not guaranteed to initialize to zero, rather, I think you might be only initializing the first element to zero. Cf "aggregate initialization" in C++ docs.

[Rumata888]

Yes, probably (I'm used to this working in C, but it is better to be safe, since we don't have an MSAN workflow yet)

[codygunton]

Can you explain in the block comment how this Lagrange polynomial is to be used?

[Rumata888]

Added

[codygunton]

I don't understand this "wide limb" terminology, could you briefly explain somewhere in there?

[Rumata888]

In a nutshell, its' because we are computing products of limbs and storing that product in there, so it's no longer 68 bits. I added the explanation in the block.

[Rumata888]

Ok, I had a look through and think that the relations are computed as advertised. Nice work. I left a few comments. The most important is about how you initialize some things in the relation parameters.

Some other things:

• As I read this I reformatted some comments to help me process. I pushed those changes. Do you mind having a look at that? We can revert if you don't like it.
• The relation could use some logic tests, not just a consistency test, to convince someone that it is doing what it is intended to do, rather than to show it matches some other inscrutible huge formulas. If you don't have time to write this could you leave a TODO issue in Bb repo?
• For expediency I can see why you added stuff to the relation parameters, but it looks pretty hacky to me--is there not more appropriate place? The VMs should probably get some additional state structure that is uniform across them. Maybe now is not the time... could you please look for for a different and more robust solution as you work on the Public VM?
• The term "shift" is pretty overloaded here: it refers to a shift of execution trace but also of the degrees of the binary basis limbs. Prob it's too late to fix, just noting it was confusing.
• Ditto for the z's--why not just z_lo = z_lo_lo + shift * z_lo_hi? I had trouble checking part of the logic due to the naming there being the opposite of what I'd expect.

1. I like this formatting more, will try to use with clang format for other stuff
2. The logic tests are in correctness and require flavor to merge in. For all other relations the values are filled out by hand, for the non-native relation I used the circuit builder output. Once I merge the flavor, I can add correctness
3. Since we can't compress all the inputs like we do with our general circuits, I had to use the relation parameters. We do need a special structure that will be easier to customise and wouldn't have to be the same for all the different flavors. Or maybe we need to simply define relation parameters in the flavor. It doesn't really make sense for them to be shared.
4. I would prefer to use "_next" with polynomials. While we shift the polynomial, what we actually care about are the values in sumcheck and this is just the next value. And in non-native operations the shift is exactly the binary shift, so it is hard to change that name.
5. We call them k1 and k1 in split_into_endomorphism_scalars, they are called k1 and k2 in the Guide to elliptic cryptography by Hankerson, but for some reason they were called z1, z2 in the Pepe paper. But the point is that they are not slices of some scalar z, so we are using z1, z2