Tracking issue: Historic Data Access

[LHerskind]

This tracking issue lays out the high-level overview of the solution, 
but redirects more detailed views to its individual issues if required.

Motivation for issue

• Many historic trees to keep up to date
• Need data specific to a block with global variables (Tracking issue: Global Variables #824)
• Statements about individual historic transactions (and not notes) are painful
• Unclear how kernel vk tree root could practically be updated if needed
• Private functions require "access-control-storage"

Connecting the dots from:

• https://hackmd.io/YgCvGLQzTq2GZVUnj5SIUA
• https://hackmd.io/XCwXNEnvRzigGKCHTf2CRw
• https://hackmd.io/CEmdmUSNRlaWyY0hwMESBQ
• https://hackmd.io/Qgh1H6fdRYim_nkPQgd_XQ
• https://hackmd.io/_UnW4qCUTlSQh5RBkRHY4Q
• Tracking issue: Global Variables #824
• https://docs.aztec.network/aztec/how-it-works/private-public-execution#a-note-on-l2-access-control
• https://discourse.aztec.network/t/accessing-historic-public-state-from-private-functions/241

---

Currently the circuits take multiple historic tree roots as public inputs.

aztec-packages/yarn-project/circuits.js/src/structs/kernel/combined_constant_data.ts

Lines 10 to 32 in 72524f8

	export class PrivateHistoricTreeRoots {
	constructor(
	/**
	* Root of the private data tree at the time of when this information was assembled.
	*/
	public privateDataTreeRoot: Fr,
	/**
	* Root of the nullifier tree at the time of when this information was assembled.
	*/
	public nullifierTreeRoot: Fr,
	/**
	* Root of the contract tree at the time of when this information was assembled.
	*/
	public contractTreeRoot: Fr,
	/**
	* Root of the l1 to l2 messages tree at the time of when this information was assembled.
	*/
	public l1ToL2MessagesTreeRoot: Fr,
	/**
	* Root of the private kernel vk tree at the time of when this information was assembled.
	*/
	public privateKernelVkTreeRoot: Fr, // future enhancement
	) {}

Each of these inputs require that the sequencer provides a merkle-path to prove inclusion in each of the historic roots trees for every transaction. Furthermore, to keep these historic roots trees up to date, we need to provide the root rollup circuit with sibling paths such that it can insert the new roots in these historic root trees.

Blocks tree

To reduce the overhead in the root rollup and reduce public inputs in the base rollup we suggest to replace the historic roots trees with a single "blocks tree".

The leafs in the blocks tree is to be part of the L2 block header that regards the new block output (so all the current historic roots), as well as global variables specific to the block (chainid, version, timestamps etc).

A new block is to be inserted into the blocks tree at every L2 block (block 3 will be at index 3 etc). See visualization below.

The kernel need to output a single block "root" that it is using for the historic data that the kernel requires, and the sequencer can then provide the single merkle path for inclusion of this block in the blocks tree. The work required by the base rollup circuit increases by a few hashes to hash up the contents of the block, but as the block is "small" it requires only few additional hashes.

Kernel VK Tree Root

The Kernel VK Tree Root which is used for verifying the kernels are current part of the historic trees without a way to be changed over time. To support upgrades in the future, I suggest that the values should be passed in from the L1 state transitioner contract, such that the root can be upgraded through contract upgrade instead.

Transaction and receipt trees

Including transaction and receipt trees similar to Ethereum allows users to more easily prove that commitments spent in a "current" transaction originated from tx 1, 2, 3. Practically this could be done based on block sizes without the tree, but much less convenient.

Reasoning behind having two separate trees mainly stems from efficiency, as a leaf in a combined tree might have large pre-image that grow the complexity of the application unnecessarily if only one of the two is needed.

Grandfather tree and getHistoricBlock(blockNumber)

With the blocks tree, we are able to use a specific block as base for our proving. However, it requires help from the sequencer to produce the path for the specified block in the tree. Therefor the block needs to be shared as public input (just the leaf hash), such that the sequencer knows what to generate (exactly as historic roots now). However, this need for assistance puts an upper bound on the practical amount of historic blocks we can query in applications.

Say we have an application where we prove provenance of our notes, e.g., note a generate by tx x, note b by tx y and note c by tx z. Most likely we will need to span different blocks, which put a bound on the number of notes that can be collapsed by this application.

If we borrow the idea from historic roots trees, we can create a separate tree whose leafs are historic roots from the blocks tree. A "historic blocks tree roots tree", referred to as the grandfather tree for brevity.

Every leaf in this Grandfather tree is a historic root from the blocks tree, and includes the values of all blocks before it. Meaning that the leaf at index 3 in the Grandfather tree contains blocks 0, 1, 2, 3.

By having the kernel provide a historic blocks tree root (a leaf in the Grandfather tree), and exposing it to the execution context for the underlying application, an application can access as many historic blocks it desires as long as they are included in the leaf provided.

It now becomes a burden of the application rather than the kernel to "open" the commitments down to the individual transactions (the kernel only see 1 extra root).

Without the grandfather tree, the kernel should as earlier described accept $n$ historic blocks as public input which put an unnecessary upper bound on access to historic data available and increased the burden of applications that does not use this data.

For ergonimics of development. Noir could make the historic blocks accessible as context.getHistoricBlock(blockNumber) similar to blockhash(uint256 blockNumber) in Ethereum and use an oracle to provide the merkle paths.

Access control storage

Enforcing access control is as alluded to in the docs with current storage options an unoptimal experience.

In Accessing historic public state from private functions the idea of a slowly updating tree ("slow-poke") is suggested as a way to support public historic values that are accessible from secret functions and can be used for access control, with the requirement that the root of the slow tree used as public input to the proof MUST be the newest (invalidating pending transactions requiring slow-poke at epoch updates). The idea requires an additional public input and should be explored further to decide if it is the best available option.

Issues

Refactoring

Preview Give feedback

1. Replace historic roots trees with blocks tree #3532
   +0
   

New Functionality

Preview Give feedback

1. Use historic roots from noir #2572
   1 of 1
   +0
   

Historic Blocks Tree (Grandfather Tree) Subtasks

Preview Give feedback

1. feat(blocks_tree): Introduce interfaces for the blocks tree #1160
   +0
2. feat(blocks_tree): Add blocks tree checking to smart contract #1161
   +0
3. feat(blocks_tree): add blocks tree calculations to circuits #1162
   +0
   
4. feat(blocks_tree): refactor - replace historic trees with blocks tree #1163
   +0
   
5. feat(grandfather): Add the grandfather #3206
   0 of 3
   S-needs-discussion +1
   
6. feat(grandfather): Snapshotted trees #3207
   S-blocked S-needs-discussion +2
   

Transactions Tree Subtasks

Preview Give feedback

1. feat(tx_tree): Introduce interfaces for the transactions tree #1442
   +0
2. feat(tx_tree): Add transactions tree checking to the smart contract #1443
   +0
3. feat(tx_tree): Build blocks transaction tree within the root rollup. #1444
   +0
4. feat(tx_tree): Create an e2e test reading historical state via the transaction tree #1445
   +0

[LHerskind]

Spoke with @benesjan about this today, and looked at these issues.

• The grandfather tasks is not fully completed.
  • The rollup circuits seems to be checking that the block-hash is in the set of historic trees, but this is just the bottom layer of the grandfather. We need one more tree. See feat(grandfather): Add the grandfather #3206
• To power of the grandfather comes from historic access to multiple blocks, but without a nice snapshotting mechanism, this is really tricky from dev side as you essentially need the "views" of the trees at different points in time. See feat(grandfather): Snapshotted trees #3207

@dbanks12 or @iAmMichaelConnor probably want to jump in on some of the stuff for #3206, and maybe on snapshotting from #3207

[LHerskind]

Extra diagram we did this morning.

[benesjan]

@LHerskind I think it would be useful to have consistent terminology here because it's easy to confuse blocks tree with the tree which is in the block itself.

That is I would never refer to the historic access tree as blocks tree and I would always just refer to it as a HAT 🎩

[LHerskind]

By making the block refer to the previous root itself, we can have the grandfather tree checks handled implicitly as part of the block inclusion checks (the checks that ensure all the other trees also match). This is partially done in the code, with the main hurdle left that the hash of the block don't address the blocks tree, so you can atm lie about it and then prove inclusion because the element is skipped. @benesjan will you address?

[benesjan]

@LHerskind on it #3482

[LHerskind]

The first version is covered, and most restructuring tasks moved to #3533. Closing the issue for now.