Slow updates tree

[LHerskind]

The idea of slow update tree was first discussed in the forum here, but also have a more thorough description here

The Problem

When executing private functions, it can be very useful to read values that are rarely-changed without emitting a nullifier to ensure up to date

While emitting the nullifier ensures that the data is up to date, which is needed for safety (will elaborate in a second), it also means that only one interaction can really happen at a block unless the coordination is happening between the consumers of the data.

For spending funds, this is not really an issue, but say that you want to "read" a underlying token address from storage or to show that our address is not in a blacklist.

When doing this, we want to make sure that:

• The data is up to date
• Multiple transactions can be made simultaneously

If the value is never changing we could use "constants", but if the data is updatable we have other issues.

Say that we just used historic public data, e.g., we have a blacklist in public, and to send your transactions in private, you prove that you are not in the blacklist in the historic data.

You might see the issue here, since the user is providing the historic root for his proof, he could chose anything in the past allowing him to pick a root before he was added to the blacklist - thereby making the blacklist useless.

So what if we put the root of this list into private state. So they need to prove and nullify it. Well, everyone proving they are not in the list would nullify the data, thereby making any other "pending" tx fail because it would try to emit the same nullifier.

The Proposed solution

Intuition

One way to work around this, could be to have a slow updates tree. Essentially a "mapping" that is only updated every epoch (X minutes) and will work sorta similar to an immutable singleton in the way that you don't have to nullify it.

The root of this tree would be one of the public inputs, so if you are using an old one, your proof fails without emitting a nullifier.

A proof that was created before the current epoch and read from this tree would thereby be invalid. This ensures that only up to date proofs would be accepted - landing a tradeoff between how long a tx can sit in the mem-pool and having live data.

Implementation

There are really two roads to take for building this.

1. Enshrine it in the protocol
2. Build it as a noir-contract on Aztec

Enshrining it into the protocol gives the proposal more power, since coordinating updates to the tree can be handled by the sequencer, allowing us to have all contracts share one large tree, hiding what contract we read "slow" values from. It also ensures that the same "interface" is used, making it easier to make a consistent experience for the developer.

However, enshrining it also means that we need to change the kernel and rollup circuits and that changes to the scheme require a protocol upgrade 😅.

For the initial implementation, we will consider building it in noir, with early experiments in #2732.

Noir

To make it work in Noir, we abuse that it is possible to make a private -> public calls. Simply, we compute the root of the tree in private, and then check that it matches what is stored in public by adding a public call which assert this.

It makes the implementation for Aztec-labs quite a bit easier as we don't need to alter circuits, but simply a noir-contract.

However, since it is not native in the protocol, we need to juggle quite a bit of the tree-building ourselves. For the experiment, the tree leafs and its root are stored in public storage, and we require updates to provide sibling-paths for the updates. This means that multiple updates to the same tree in a block require knowledge of the other changes, which is not straightforward.

Therefore, the slow tree contract will have a map with individual trees per contract. This should greatly limit the number of failed updates due to path-changes since contracts should already be enforcing some kind of access control for doing this. Since we require access control to update the access control (🐔 & 🥚) we support both private and public updates.

The main benefit of doing a private update, would be that all the hashing to get the roots can be done in private where they will be less impacted by public-vm opcode pricing. (Its a cost optimization).

---

Currently the developer experience is not too great. Mainly as an effect of needing to provide multiple sibling-paths and other storage proof data to perform reads and updates making the flow more "this is the value and here is proof" rather than classic "read".

I think we can at least mitigate some of this issue by introducing additional oracles, but it relies on the wallet or PXE indexing public storage for certain contracts into trees to generate the matching paths etc.

Furthermore, the trees should be either sparse-trees or successor-trees (indexed trees) to make it easy to use for both inclusion and non-inclusion checks.

Tasks

Preview Give feedback

1. feat(slow updates tree): Minimal Noir implementation #2801
   +0
   
2. feat(slow updates tree): Add oracle to get read/update proofs into private functions with 0 inputs #2852
   +0
   
3. Figure about if we can efficiently compute the trees without enshrining into PXE
4. Build efficient non-membership proofs for slow updates tree #2794
   +0

[spalladino]

Thanks for taking this one @LHerskind! I think an important reason for enshrining is that we can make a tx ineligible for inclusion if it refers to an old slow tree root, as opposed to not-enshrining where it'd trigger a revert and consume user fees.

And another reason is that I want to use it for implementing contract classes :-P

[LHerskind]

And another reason is that I want to use it for implementing contract classes :-P

Anywhere I can read up on your idea?

[spalladino]

Long-form here, but I'll write something more succinct based on conversations with @iAmMichaelConnor later today.

Update: see Contract upgrades and shared private state.

[benesjan]

Has it already been figured out how the slow update tree update will be coordinated? Since sequencer can't be trusted and sequencer will have the knowledge of slow updates tree being updated (am I right here?) what would prevent sequencer from allowing users to move their funds right before they are blacklisted? Would we somehow try to enforce that the slow update tree update tx has to be included and included in the beginning of a block?

[LHerskind]

My issue description is not fully in detail here, but in the Discourse there is an idea that you essentially end up having "two" coexisting trees for different points in time, and then use a third storage value to jump between the two. That way, the sequencer coordination is only for merkle paths, similarly to what it is for nullifiers etc.

Essentially, you have before and after and then some next_change which is the point in time where you jump between these two. The jump does NOT require a transaction, but is based on how you read the value. Since the values are always read in public, they can utilise the current timestamp, e.g., they will say whether before or after is the "current" tree based on that time. I should probably make some diagrams for it.

If you look in the pr for #2801 there is a noir implementation that shows when these jumps are made. Because the change takes effect without a storage update, the sequencer don't got the power to do something before and after in the same block.

TL;DR: sequencers only used for race-condition coordination of updates to provide paths (if enshrined).

[LHerskind]

See #4761.