DoS risk with concentrated identical termini

[PaulRBerg]

The problem is thus:

• Suppose that due to happenstance or ill intent, there are suddenly a bajillion identical termini in the mempool
  • Note: termini is plural for terminus, which is the deadline when a user's balance goes to zero
• A block, call it Foo, is mined with a timestamp equal to the termini
• The SabVM has to terminate a lot of streams
• How can the SabVM ensure that this doesn't lead to DoS and that Foo will be mined within a reasonable time?

My conversations with Peter Szilagyi let me believe that there is a similar risk with SELFDESTRUCT in the vanilla EVM. What would happen if a contract with a lot of stored state (such as Tether) would self-destruct? Deleting so much state from disk would take time, certainly more time than it takes to mine an EVM block.

More research needed.

Credits to @razgraf who pointed out this problem in offline conversations about SabVM, and to @IaroslavMazur who noticed it independently here.

Related: slide 12 in my Figma presentation

[IaroslavMazur]

To further complicate the matters: we can't do a part of the terminus-reaction/graph-restructuring/maintenance anytime before the terminus (to split the overall work in several batches), because any tx in the blocks starting from this time (when we're, supposedly, partially re-evaluating/re-structuring the graph) and until the block right at/past the terminus could, potentially, render all of this "preliminary" work 1) useless and 2) incorrect (e.g. by someone creating a Stream towards an address which would've, otherwise, become insolvent at the terminus time in question).

---

What would happen if a contract with a lot of stored state (such as Tether) would self-destruct?

Sounds like the Ethereum-like blockchains are, practically, living off of hope that no contract of such size will (intentionally or not) SELFDESTRUCT 😅

Do you happen to know Peter's take on this situation? If not, I'll ask this on StackExchange.

Also, now, I wonder how big of a factor this is for the efforts invested in the swift deprecation of the SELFDESTRUCT opcode.

[IaroslavMazur]

DoS when a contract with too much storage is SELFDESTRUCT-ed?

[PaulRBerg]

I asked Peter Szilagyi to lend us a hand

Aaaand we got an answer from him!

[razgraf]

The SELFDESTRUCT problem is similar in nature (too much state computation, too little time) and informative. Not sure though if it applies directly to our needs. Since we're building our own "storage" and system for stream termini I'm wondering if there's a way to handle hard state changes a bit different.

The specific thing I'm brainstorming on is:

The SabVM has to terminate a lot of streams

What if this termination wouldn't instantly result in an physical state change? Do we really have to physically terminate streams when solvencyOf(stream/owner) === 0?

What if we replicate our "hot/cold" status ideas from core and (1) we create a hot state for the stream (e.g. PREDICTED_AS_TERMINATED) and (2) a cold state (e.g. TERMINATED) which can be done again, by an incentivized state-optimizer-node at a later date.

[IaroslavMazur]

@razgraf, I really like the direction you're hinting at!

If we could "postpone" the workload required to clean the system following a Stream graph simplification, we could, indeed, "spread" it over the less intensive periods of activity on the chain, following the Big Termini.

@PaulRBerg, speaking of what we've discussed during our latest call, @razgraf's idea sounds similar to "soft deleting" the memory on a hard disk (i.e. just "marking" it as deleted, instead of literally resetting it all to zeroes). Curious to hear what your take on this is!

---

A comment: because a PREDICTED_AS_TERMINATED Stream would affect the whole subgraph it's "super-seeding", alongside the PREDICTED_AS_TERMINATED state, we'd also need to store the time/block at which the Stream entered this state, in order to properly calculate the balances of the subgraph Streams (i.e. for no assets to be considered "streamed" out of the "super-seeding" Stream following its transition into the PREDICTED_AS_TERMINATED state).

[PaulRBerg]

@razgraf and I dived deep into this idea in person at CSX. Sorry for not notifying you @IaroslavMazur, it's been an exceptional busy week.

Razvan has cut the Gordian knot. This cold<>warm state duality is the solution to the research problem. The quintessential insights are the following:

• Assume that the terminus of a user can be in the past, and add checks at the beginning of every opcode implementation. If a terminus is in the past, treat the user's balance as zero.
  • E.g. if someone queries BALANCEOF on a terminated account, the typical opcode logic wouldn't even run. The VM execution would return zero right away.
• Serialize the warm computations within blocks; parallelize the cold computations outside of blocks
• It is OK to perform redundant warm serial computations on top of the cold parallelized operations; users will pay gas for the former anyway

Now, let me explain the solution visually with a diagram:

---
title: Terminated SabVM Accounts
---
flowchart LR
    subgraph "`Warm: *Serialized in Blocks*`"
        u1((Alice))
        u1-. "createStream" .- a2
        u2((David))
        u2-. "balanceOf" .- d2
        a2[0xaa...]
        d2[0xdd...]
    end
    subgraph "`Cold: *Parallel to Blocks*`"
        a1[0xaa...]
        b1[0xbb...]
        c1[0xcc...]
        d1[0xdd...]
        e1[0xee...]
        f1[0xff...]
    end

Loading

---

"spread" it over the less intensive periods of activity on the chain

Actually, we will still try to prune the graph aggressively ASAP because it's in the interest of the chain to reduce state size. It's just that thanks to the cold<>warm duality, it is no longer necessary to clear all termini within the span of a single block. The operation can be performed in the background, in parallel with the standard block productions.

[IaroslavMazur]

One word of caution for this warm<>cold approach: even though we are able to postpone the actual removal of the terminated Streams from the physical memory of the SabVM nodes, we must still incorporate any funds already streamed via those Streams up until now/the moment of termination into the Static balance of the Recipients. Otherwise, this information will be lost, together with the Stream, once it's been deleted.

Besides, it feels like not doing the Dynamic -> Static balance cementing - because of the introduced inconsistency - could cause us trouble in some other areas of the system (don't have specific examples of this atm).

@PaulRBerg, @razgraf, do you agree?

[IaroslavMazur]

Just to make sure we're all on the same page here: it's completely legit to become insolvent in terms of an asset $X$, while continuing to be a part of a Stream graph streaming some asset $Y$, right?

if someone queries BALANCEOF on a terminated account, the typical opcode logic wouldn't even run

Having the above in mind, it'd be incorrect to refer to an account that has become insolvent in terms of the asset $X$, but has still got other assets, as a "terminated account".

At any rate, there's nothing to "terminate" about that account itself - it's "just" the outgoing Streams streaming the asset $X$ that will need to be "terminated".

---

add checks at the beginning of every opcode implementation. If a terminus is in the past, treat the user's balance as zero

Wasn't the "terminus" calculation & monitoring supposed to be outside the scope of the VM, though?

If VM would have to track this, then, even the simplest asset transfers could, potentially, lead to a helluva node storage update (e.g. a user transferring an infinitely small amount of an asset to another user, who is streaming the asset to a 3rd user, who is streaming it to a 4th user, etc.)

---

It is OK to perform redundant warm serial computations on top of the cold parallelized operations; users will pay gas for the former anyway

Could you, please, give a couple examples of the "redundant warm serial computations"?

---

@PaulRBerg, TIL one can Create Diagrams directly on GitHub.

Thanks for the insight!

---

The operation can be performed in the background, in parallel with the standard block productions.

Yup, this is what I meant, as well: the clean-up can be performed at any time, as long as it doesn't impact the production of new blocks & the responsiveness of the node in the network.

[PaulRBerg]

@IaroslavMazur I don't follow your word of caution. Pardon me if this isn't the case, but I don't think you have understood the proposal.

• When a stream is terminated via the Cold computation, Alice's static balance is updated.
• If Alice makes a Warm query at the same time while the Cold computation is performed, her static balance will also be updated.
• Alice's static balance will be updated twice in different parts of the code base, but this is OK because it prevents DoS overall.

---

it's completely legit to become insolvent in terms of an asset $X$ while continuing to be a part of a Stream graph streaming some asset $Y$, right?

Ofc.

---

it'd be incorrect to refer to an account that has become insolvent in terms of the asset $X$, but has still got other assets, as a "terminated account".

I disagree. It's a contextual thing, and for brevity reasons, it's perfectly fine to refer to the account as being terminated. The fact that the termination is related to a specific asset is implied.

To make an analogy: you are liquidated on Aave for holding ETH as collateral, but you might have other positions, e.g., WBTC, COMP. While the collateral is implied, it is your account that gets liquidated.

---

there's nothing to "terminate" about that account itself

Your balance is set to zero. If that's not what termination is, I don't what is.

Heck: terminating is a better fit when coupled to the word 'account' than when coupled to the term 'stream'. A better way to refer to terminating streams would be 'deleting streams' (as per the opcode).

---

Wasn't the "terminus" calculation & monitoring supposed to be outside the scope of the VM, though?

It will be both outside of the VM and inside the VM now (for warm accounts). Can you read the first paragraph in my reply and see if you understand it now?

---

If VM would have to track this, then, even the simplest asset transfers could, potentially, lead to a helluva node storage update

Welcome the UCG problem. Let's stick with the other thread for discussing this pernicious issue.

---

give a couple examples of the "redundant warm serial computations"?

See first paragraph above.

---

TIL one can Create Diagrams directly on GitHub.

Yeah, Mermaid is pretty cool. We used it extensively in our docs. See the diagram I made for representing stream statuses.

---

the clean-up can be performed at any time, as long as it doesn't impact the production of new blocks & the responsiveness of the node in the network.

Indeed.

Nitpick: you perhaps meant to say in order not to impact instead of as long as it doesn't impact. Parallelizing the computation is not a choice - we gotta do it to prevent DoS.

[PaulRBerg]

Follow-on question to @razgraf and @IaroslavMazur:

If the cold state will basically never be read in practice, then why bother with clearing the termini? Why not let them have stale values? For example, if my terminus was March 1, why should the SabVM client set it to zero?

One reason is clearing state size. Another is the accuracy of Archive node data.

What else?

[razgraf]

Interesting question. I'll think about it, but it's probably something where the implementation stage may offer the proper answer.

---

One adjacent idea is to give another purpose to the termini, in the context of state purging. Our state holds termini, but may also hold "stream" metadata (rate, parties etc.). A termini != 0 and in the past could mean:

• the account is insolvent
• the state may still hold metadata of terminated streams, which must be cleared

Once those are cleared, the termini could be set to 0 to allow for a fresh start. It's just a random idea that gives it dual purpose while also telling garbage collectors not to look here anymore.

[PaulRBerg]

Agree that marching on with the implementation will provide us with more clarity on this.

give another purpose to the termini

I'm against assigning multiple roles to the same VM property. It's the kind of thing that leads to spaghetti code, which is inevitable in a blockchain context anyway (due to immutability). Thus, we should strive to minimize it.

Besides that, multiple roles could lead to racing conditions: if a terminus is non-zero, is that because the node didn't have time to clear it, or because there is historical metadata?

The solution for metadata is simple - add a new flag hasMetadata. We can expand on this in a separate discussion.

[PaulRBerg]

Oh LOL, I know why we will want to clear the termini even if they won't be used in practice.

Clearing a terminus will necessarily be associated with a stream deletion, an operation which absolutely must be performed in order to keep UCG in check.

Since we have to perform that other operation anyway, we can clear the termini at the same time with that.

[razgraf]

That is what I was trying to say above regarding stream metadata (may have over engineered it in my point).

[PaulRBerg]

Very well then.

In this case, can we close this Research discussion?

[PaulRBerg]

Unfortunately, this cold<>state duality has (bad) implications for the efficiency of the subgraph traversal algorithm. Posted my findings here:

#123 (comment)

[PaulRBerg]

Massa is a non-EVM L1 that provides cron jobs via "autonomous" smart contracts that can self-execute themselves in the future.

They've also bumped into this the same problem of scheduled task congestion. From their docs:

As for normal operations, the number of autonomous operations that can be executed is limited, through a maximum amount of gas. In practice, it’s possible that your message isn’t executed at the slot that you want, but in a later slot, when there is enough space to include your message.