docs: Yellow paper rollup circuits and state update

[LHerskind]

PR looking to fix #3148, #3149 and #3150. Very much a work in progress currently.

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): 230 (-38%)
• note_trial_decrypting_time_in_ms (8): 17.3 (-36%)
• note_trial_decrypting_time_in_ms (32): 59.6 (+47%)

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 ceb2ed26 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,972	868,208	3,449,444
l1_rollup_execution_gas	842,059	3,595,316	22,204,813
l2_block_processing_time_in_ms	2,200 (-7%)	8,587 (+2%)	35,013
note_successful_decrypting_time_in_ms	308 (-3%)	930 (+2%)	3,338 (+1%)
note_trial_decrypting_time_in_ms	⚠️ 17.3 (-36%)	⚠️ 59.6 (+47%)	201
l2_block_building_time_in_ms	20,107	80,098	322,290 (+1%)
l2_block_rollup_simulation_time_in_ms	16,577	66,178	266,275 (+1%)
l2_block_public_tx_process_time_in_ms	3,499	13,850	55,764 (+1%)

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	25,292 (+2%)	47,774
note_history_successful_decrypting_time_in_ms	2,345 (+8%)	4,382 (+4%)
note_history_trial_decrypting_time_in_ms	169 (+5%)	⚠️ 230 (-38%)
node_database_size_in_bytes	3,637,830	3,929,646
pxe_database_size_in_bytes	29,748	59,307

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	199	43,109	20,441
private-kernel-ordering	115 (+1%)	25,833	9,689
base-rollup	2,956	667,692	873
root-rollup	92.2 (+9%)	4,072	881
private-kernel-inner	260	64,516	20,441
public-kernel-private-input	172 (+1%)	25,203	20,441
public-kernel-non-first-iteration	169 (+1%)	25,245	20,441
merge-rollup	10.9 (+1%)	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	10,323	25,938

[LHerskind]

Took a quick view, can look deeper later.

[benesjan]

Nice writeup. Feel free to merge it once you apply my suggestions.

[benesjan]

Suggested change

For most chain this is not required since they are always executing on the head of the chain. However, since private execution rely on proofs generated by the user they don't have the current head and must be based on historic state. By including all prior headers (which include commitments to the state) the Archive allows us to easily prove that the historic state that a transaction is proven upon was valid.

For most chain this is not required since they are always executing on the head of the chain. However, since private execution relies on proofs generated by the user they don't have the current head and must be based on historic state. By including all prior headers (which include commitments to the state) the Archive allows us to easily prove that the historic state that a transaction is proven upon was valid.

[sklppy88]

Very cool, this definitely helped my understanding. Have some (opinionated) suggestions, but no need to heed them all.

[sklppy88]

Suggested change

	Furthermore, since the Headers include a snapshot of the Archive at the time of insertion, as well as commitments to the block content and global variables, we can use it to prove statements about the state at any given block or even transactions that occurred at specific blocks.
	Furthermore, since the Headers include a snapshot of the Archive at the time of insertion, as well as commitments to the block content and global variables, we can use it to prove assertions about the state at any given block or even about transactions that occurred at specific blocks.

[LHerskind]

A statement is essentially a collection of assertions. e.g., that X happened is a statement, but you are using assertions to constrain it

[sklppy88]

Suggested change

	- Merges two merge rollup proofs
	- Merges two merge rollup proofs at the top layer

Maybe?

[LHerskind]

The root becomes the top, you can take merges from earlier, but it is a bit odd to do since you would just reduce your block size after you already built it 🤷

[sklppy88]

Suggested change

	The root rollup circuit is our top circuit, it apply the state changes passed through its children and the cross-chain messages. It is the one that will communicate with the [validating light node](./../contracts/index.md).
	The root rollup circuit is our top circuit, it apply the state changes passed through its children and the cross-chain messages. It is the rollup that will communicate with the [validating light node](./../contracts/index.md).

Maybe ?

[sklppy88]

This is a bit awkward, I think

[LHerskind]

The refer to another doc or sentence in here?

[sklppy88]

It doesn't allow me to comment on line 194, but

Beware, that while we speak of messages, we are practically passing around only their **hashes** to reduce cost. The `version` value of the `L2Actor` is the version of the rollup, intended to be used allow specifying what version of the rollup the message is intended for or sent from.

I do not understand 'to be used allow specifying', maybe rework ?

[sklppy88]

Same but on line 196
'cheap on both L1 and L2, we' -> Maybe a linking word between L2, and we

[LHerskind]

Oh, ye can see. Will be fixing it after including the other fixes.

[sklppy88]

This is a bit hard to understand, but could be on me though !

[LHerskind]

Probably me. Will look at it.

[iAmMichaelConnor]

Suggested change

To support this, we construct a single proof for the entire block, which is then verified by the validating light node. This single proof is constructed by recursively merging proofs together in a binary tree structure. This structure allows us to keep the workload of the individual proof small, while making it very parallelizable. This works very well for case where we want many actors to be able to participate in the proof generation.

To support this, we construct a single proof for the entire block, which is then verified by the validating light node. This single proof is constructed by recursively merging proofs together in a binary tree structure. This structure allows us to keep the workload of each individual proof small, while making it very parallelizable. This works very well for the case where we want many actors to be able to participate in the proof generation.

[iAmMichaelConnor]

Suggested change

	The tree structure is outlined below, but the general idea is that we have a tree where all the leaves are transactions (kernel proofs) and through $\log n$ steps we can then "compress" them down to just a single root proof. Note that we have three (3) different types of "merger" circuits, namely:
	The tree structure is outlined below, but the general idea is that we have a tree where all the leaves are transactions (kernel proofs) and through $\log (n)$ steps we can then "compress" them down to just a single root proof. Note that we have three (3) different types of "merger" circuits, namely:

[iAmMichaelConnor]

It's likely that each base rollup will only verify 1 kernel proof, now. @sirasistant @LeilaWang did we decide this yet?

[iAmMichaelConnor]

Suggested change

	:::warning TODO
	Reconsider `ContractDeploymentData` in light of the newer (still being finalised) contract deployment flow
	:::

[iAmMichaelConnor]

Suggested change

	class CombinedAccumulatedData {
	aggregation_object: AggregationObject
	read_requests: List~Fr~
	pending_read_requests: List~Fr~
	note_hashes: List~Fr~
	nullifiers: List~Fr~
	nullified_note_hashes: List~Fr~
	l2_to_l1_messages: List~Fr~
	private_call_stack: List~CallRequest~
	public_call_stack: List~CallRequest~
	start_public_data_root: Fr
	end_public_data_root: Fr
	}
	class CombinedAccumulatedData {
	aggregation_object: AggregationObject
	read_requests: List~Fr~
	pending_read_requests: List~Fr~
	note_hashes: List~Fr~
	nullifiers: List~Fr~
	nullified_note_hashes: List~Fr~
	l2_to_l1_messages: List~Fr~
	private_call_stack: List~CallRequest~
	public_call_stack: List~CallRequest~
	start_public_data_root: Fr
	end_public_data_root: Fr
	contracts: List~NewContractData~
	public_update_requests: List~PublicDataUpdateRequest~
	public_reads: List~PublicDataRead~
	logs: List~Logs~
	}

For readability of the diagrams (and to align with how class diagrams are coventionally drawn), I'd strongly recommend including all class items in the box (like I've suggested with this code snippet) (throughout the diagrams of the yellow paper) and also doing the nice callouts to the sub-classes that you've done.

[iAmMichaelConnor]

I'm now trying to read the diagram (hosted on local host). It's actually very difficult to read the diagram without all the class items being listed in the class - so I stand by this recommendation/request :)

[iAmMichaelConnor]

struct L1Actor { // What's an "actor" in this context?
    address: actor,
    uint256: chainId,
}
struct L2Actor {
    bytes32: actor,
    uint256: version,
}
struct L1ToL2Msg {
    L1Actor: sender,
    L2Actor: recipient,
    bytes32: content,
    bytes32: secretHash, // 
    uint32 deadline, // is this an L1 block number or L2 block number, or a timestamp?
uint64 fee,

[iAmMichaelConnor]

Suggested change

	Beware, that while we speak of messages, we are practically passing around only their **hashes** to reduce cost. The `version` value of the `L2Actor` is the version of the rollup, which is intended to be used to specifying what version of the rollup the message is intended for or sent from. This waw, multiple rollup instances can use the same inbox/outbox contracts.
	Beware, that while we speak of messages, we are practically passing around only their **hashes** to reduce cost. The `version` value of the `L2Actor` is the version of the rollup, which is intended to be used to specify which version of the rollup the message is intended for or sent from. This waw, multiple rollup instances can use the same inbox/outbox contracts.

waw

Typo?

[iAmMichaelConnor]

Suggested change

	Compute on L1 is expensive, but storage is extremely expensive! To reduce overhead, we trade storage for computation and only commit to the messages and then "open" these for consumption later. However, since computation also bears significant we need to use a hash function that is relatively cheap on L1, while still being doable inside a snark. For this purpose a modded SHA256 was chosen, modded here meaning that it fits the output value into a single field element using the modulo operator.
	Compute on L1 is expensive, but storage is extremely expensive! To reduce overhead, we trade storage for computation and only commit to the messages and then "open" these for consumption later. However, since computation also bears significant we need to use a hash function that is relatively cheap on L1, while still being doable inside a snark. For this purpose a modded SHA256 was chosen, modded here meaning that it fits the output value into a single field element using the modulo operator.
	:::warning TODO
	Double-check with the crypto team whether this (modulo) is secure.
	:::

[LHerskind]

https://forum.aztec.network/t/proposal-forcing-the-sequencer-to-actually-submit-data-to-l1/426/13

[iAmMichaelConnor]

I thought you had some nice ideas, and were pushing for us to enable an L2 contract to send a message to any L1 contract? Are there still some outstanding problems?

[LHerskind]

It is altered in the rest, think I just it like this in the comment such that it was easier to see 🤷

[iAmMichaelConnor]

Having read the doc, I'm still confused about the inbox/outbox terminology.
There's:

• a box for sending L1 to L2 messages that lives on L1
• a box for storing/consuming L2 to L1 messages that lives on L1
• a box for storing/consuming L1 to L2 messages that lives on L2
• a box for sending L2 to L1 messages that lives on L2.

It's not clear which direction is "in" and which is "out". "L2 inbox" is ambiguous: is it an inbox that lives on L2, or is it an inbox on L1 for messages going to L2, or?
The first arrow in the diagram is an arrow from a portal "send msg to L2" which goes to the inbox on L1. That's confused me.

The names aren't conveying enough information to my brain.

[LHerskind]

See it as "Mike" being the state transitioner. If Alice want to send messages to someone inside the rollup, she gotta go through Mike first. Therefore, she put a message from L1 into Mikes Inbox (L1 inbox). The sequencer Steven comes by and see that Alice's message had a nice fee, so he decided that it belongs in the next block. By order of Steven, Mike will take the message from his inbox, and "send" it to the contract on L2, thereby putting it in his outbox.

If Bob on L2 want to send a message out, he will put in into Mikes L2 Inbox, and Mike will then put it into his outbox on L1.

Mike is a special guy, so he is the only one that have prober inbox and outbox, the rest just rely on him for passing messages around.