Add L1 -> L2 message tree

[Maddiaa0]

Add an L1 -> L2 message tree in the circuits for messages that are inserted. Should be implemented as an append only tree.

To be decided when to insert the messages, e.g., could be in root or at merge state depending on the compute bounds we have.

The input messages must be part of the public inputs hash as well.

See https://github.com/orgs/AztecProtocol/projects/22/views/17?filterQuery=+team%3A%22%F0%9F%A7%9A%E2%80%8D%E2%99%80%EF%B8%8F+Fairies%22+&pane=issue&itemId=25342143

---

Require updates to:

•  Circuits
• Contracts
• Typescript

[Maddiaa0]

Update:
There will be some new fields required inside the root rollup
RootRollupInputs

• l1_to_l2_messages: array
• new_l1_to_l2_message_tree_root_sibling_path: MembershipWitness[]
• new_historic_l1_to_l2_messge_tree_root_sibling_path: MembershipWitness[]

@iAmMichaelConnor
I am also deciding whether to include the following information in the rollup constants or within the root rollup inputs as it will increase proof size for every rollup, but is only required in the root:

• start_l1_to_l2_message_tree_snapshot: AppendOnlyTreeSnapshot
• start_historic_tree_l1_to_l2_message_tree_roots_snapshot: AppendOnlyTreeSnapshot

RootRollupPublicInputs

• start_l1_to_l2_messages_tree_snapshot: AppendOnlyTreeSnapshot
• end_l1_to_l2_messages_tree_snapshot: AppendOnlyTreeSnapshot
• start_tree_of_historic_l1_to_l2_messages_roots_snapshot: AppendOnlyTreeSnapshot
• end_tree_of_historic_l1_to_l2_messages_roots_snapshot: AppendOnlyTreeSnapshot
• l1_to_l2_messages_hash: array<fr, 2> (will be included in smart contract calculation)

Tasks to cover

• The root rollup circuit should do a subtree insertion of all of the l1 to l2 messages into the current l1 to l2 messages tree.
• It should then insert that calculated root into the historic tree
• Is should calculate the hash of appending all of the messages into one large string, this will ensure correct ordering of insertion into the tree and also enable the smart contract to validate the messages that were included within the rollup.

[iAmMichaelConnor]

I am also deciding whether to include the following information in the rollup constants or within the root rollup inputs as it will increase proof size for every rollup, but is only required in the root

Just summarising our chat from earlier. We went with putting this information in the root rollup inputs.
I guess (if you tilt your head sideways a bit) 'constants' could be interpreted as "stuff that will be passed through all iterations of the rollup circuits, untouched", and since this information is only being introduced for the final iteration of the rollup circuit, it doesn't quite fit into this definition (because there won't be multiple iterations). This is how I'll sleep easy tonight.