SU Tree: alternative implementation using historic blocks and 'max blocknum' global

[iAmMichaelConnor]

A version of the slow updates tree can be achieved by reading from some historic block, and exposing a max_block_num as a public input.

The max_block_num would need to be checked against the current block number, by the sequencer (in the rollup circuit). If current_block_num < max_block_num, the tx should revert*.

If multiple functions all make use of the max_block_num public input, and in particular if each function outputs a different max_block_num, then the kernel circuit should compute and forward the minimum to the next kernel/rollup iteration.

max_block_num is a generally useful 'global' to expose; it's not just useful in the context of slow updates.

Note: by exposing max_block_num, it leaks information. Observers might be able to glean which su tree has been used. (E.g. if an implementation of a su tree used epoch lengths of 17, the su contract would expose max_block_num values in multiples of 17, which are arguably very distinguishable). Ideally, many apps would all make use of the same su tree, with a common epoch length - perhaps a power of 2. Standardisation efforts would be needed in the community to agree on a select few trees.
To further-reduce the leakage of max_block_num, all txs could output some nonzero value, making sure it's far enough in the future not to 'bite'.

We should also research the implications of txs which can 'expire'. Does it lead to censorship attacks, or an extra burden on sequencers?

* We need to decide whether such a tx would be able to be included by the sequencer at all.

Tagging @PhilWindle @benesjan @LHerskind @spalladino in particular for thoughts.

[spalladino]

• We need to decide whether such a tx would be able to be included by the sequencer at all.

I vote for making the tx outright invalid in that case, so it doesn't consume gas for the user.

[PhilWindle]

• We need to decide whether such a tx would be able to be included by the sequencer at all.

I vote for making the tx outright invalid in that case, so it doesn't consume gas for the user.

Agree with this. Surely too easy to grief users otherwise. Wait for their txs to expire before executing them.

As for whether it adds a burden on sequencers, as long as the block number is very easily identifiable then I don't think it should.

[LHerskind]

How is the value set? Is it set by the user directly or should it be by the function calls based on other user input?

If set by the user, functions could compute the "epoch" of their updates tree based on that value directly. e.g., say input max_block_num = 49 and you have epochs of length 10, then active_epoch = 49 / 10 = 4. Which would only be provable if occuring after block 40, since the index would otherwise be out of bounds.

If set by the function, we could do it the opposite direction. User is passing in active_epoch = 4 and then computing the max_block_num = active_epoch * 10 + 9 = 49. It then output it as a kernel value.

From the description the second option seems like the one we go with. Second option can also emulate direct by user by just forwarding the value.

---

I think having it drop the tx for this kind of check is acceptable. Also, it means that you can provide some quite nice guarantees for stuff like trading, e.g., let the user pass in the value and simple forward it the kernel. Then a user can to a swap from A -> B where they have a short life-time etc, similar to what you have in uniswap etc, just without the fee 🤷

[spalladino]

How is the value set? Is it set by the user directly or should it be by the function calls based on other user input?

In my mind the user (well, the pxe) injects the current L2 block number, and each function sets the max_block_num based on that value, its epoch length, and the current value of max_block_num (in case another function already set it).

If we have the user pass in the active_epoch, it means the user needs to know the epoch length used by each function they are interacting with, which is difficult.

[LHerskind]

In my mind the user (well, the pxe) injects the current L2 block number

Ah, ye we could just use an oracle, if you are giving a too early block it fails because the function call sets the max_block_num too low.

Any good ideas around what we should do for a "default" value? I'm thinking account contracts could essentially figure something out for themselves there, then kernels don't need to 🤷

[spalladino]

Any good ideas around what we should do for a "default" value? I'm thinking account contracts could essentially figure something out for themselves there, then kernels don't need to 🤷

I was going to write that the default should be "empty" (or max_fr), since if you don't hit a slow-updates tree in your tx, you don't really need to set a max_block_num value. But I just realised that we don't have a mechanism for cancelling txs. So if you send a tx but it doesn't get picked up immediately, it can potentially be run any time in the future. So maybe we do want a reasonable max_block_num default. Perhaps the equivalent to 2 hours?

[iAmMichaelConnor]

I was going to write that the default should be "empty" (or max_fr), since if you don't hit a slow-updates tree in your tx, you don't really need to set a max_block_num value

I mention briefly in the original description: "To further-reduce the leakage of max_block_num, all txs could output some nonzero value, making sure it's far enough in the future not to 'bite'."

By this I mean: it improves the network's function-privacy set if every tx outputs a sensible nonzero value.

(We should make a note that most private kernel public inputs should be nonzero, to improve the network's privacy set. E.g. if a tx doesn't need to do any reads, it should still output a valid, recent UTXO tree root, as a way of "being a good citizen".)

[iAmMichaelConnor]

@LHerskind @nventuro is this issue still relevant, or is it superseded by more recent slow update discussions?

[LHerskind]

@LHerskind @nventuro is this issue still relevant, or is it superseded by more recent slow update discussions?

Should be superseded by #4761 will close this one.