Complexity Factor

[PaulRBerg]

Context

This idea was introduced by me here as a solution to @IaroslavMazur's question about whom to charge for the gas-intensive restructuring of subgraphs.

The goal is to come up with a design that distributes the computational cost more equitably across subgraph participants, while not making it prohibitively expensive for any particular user (especially new users).

Spec

Each user is assigned a Complexity Factor $cf$ that is related to the subgraph the user is part of. As a refresher, being part of a subgraph means having an incoming or outgoing streaming rate that is greater than zero.

When calculating the base fee of a user $U$, the SabVM will perform these steps:

• Add the Minimum Transaction Fee, which is 21,000 gas
• Obtain the user's Complexity Factor $u_{cf}$
  • If $U$ does not belong to any subgraph, $u_{cf}=1$
• Multiply the Minimum Transaction Fee by $u_{cf}$

Because the time complexity of traversing subgraphs is linear, the Complexity Factor can also grow linearly. Each new user and each new stream will increase the Complexity Factor by a constant value $0.005$. Examples:

• Subgraph with 2 users and 1 stream: $cf = 1.01$
• Subgraph with 100 users and 120 steams: $cf = 2.095$
• Subgraph with 1000 users and 1500 streams: $cf = 12.495$

---

Notes

• Note that the user itself is excluded from the total count. This is why 2 user and 1 stream produce $1.01$ and not $1.015$.
• The exact value of the constant by which Complexity Factor grows will be adjusted with time as we perform more benchmarking and simulation.
• In vanilla EVM, the Minimum Transaction Fee is identical to the "base fee"; in SabVM, that is not the case because of the Complexity Factor.
• It remains to be seen what model we will choose for incorporating the L1 data fee into the L2 gas fees. I'm currently inclined to choose Optimism's approach since this leads to parity with Ethereum (21,000 gas for transferring ETH).

Open Problems

Cardinalities

The design proposed herein assumes an SS cardinality. While it should be possible to make this work for Many Subgraphs per Account, more research is needed to validate these alternative designs.

Free Rider

There's a potential 'free rider' concern with users who trigger massive subgraph updates, and then no user submits a follow-up transaction, ever. The SabVM nodes would, in effect, provide a temporary subsidy to the subgraph participants.

However, this sounds low-risk:

1. Users are naturally incentivized to move their money around.
2. All that a potential attacker should be able to do is grief the network. There should be no way to extract profits out of this set-up.

Of course, more research and more benchmarking are required to validate these conclusions.

Comments

CC @sablier-labs/sabvm.

Related:

• Whom should we charge for the eventual gas-intensive rebalancing? #63
• Subgraph manipulation at the end of each block #123

[IaroslavMazur]

Thank you for putting all this information in one place!

---

Each new user and each new stream will increase the Complexity Factor by a constant value 0.005.

Given that a new user can only join the subgraph via a stream, I believe we should only take the active streams into account when calculating the Complexity Factor of the subgraph.

---

In vanilla EVM, the Minimum Transaction Fee is identical to the "base fee"; in SabVM, that is not the case because of the Complexity Factor.

Given that the CF will equal 1 for any tx signer who is not a part of a Subgraph, we can say that the Minimum Transaction Fee in SabVM will be 21,000 gas, as well.

---

It remains to be seen what model we will choose for incorporating the L1 data fee into the L2 gas fees. I'm currently inclined to choose Optimism's approach since this leads to parity with Ethereum (21,000 gas for transferring ETH).

I've just looked at how Optimism handles the L2/L1 fees. Basically, it estimates how much persisting your L2 tx on Ethereum will eventually cost (the L1 data fee) - and adds the respective amount of ETH (in a non-negotiable way) to the L2 execution fee (which you can control, by configuring the amount of wei you're willing to pay for each unit of gas).

However, I don't understand why you said that this approach "leads to parity with Ethereum (21,000 gas for transferring ETH)".
Could you elaborate, please? How does the way the L1 data fee is charged during the L2 tx execution affect the parity (or the lack of it) with Ethereum?

[PaulRBerg]

we should only take the active streams into account when calculating the Complexity Factor of the subgraph

Yes.

Given that the CF will equal 1 for any tx signer who is not a part of a Subgraph, we can say that the Minimum Transaction Fee in SabVM will be 21,000 gas, as well.

Correct. That was a misconception on my part.

I don't understand why you said that this approach ... Could you elaborate, please?

All I meant to say is that Optimism doesn't use a funky gas model like Arbitrum, which bakes the L2 data fee into a single value. A simple ETH transfer on Arbitrum costs 35-70k.

Relevant article: Understanding Arbitrum 2-Dimensional Fees.

[IaroslavMazur]

All I meant to say is that Optimism doesn't use a funky gas model like Arbitrum, which bakes the L2 data fee into a single value. A simple ETH transfer on Arbitrum costs 35-70k.

Relevant article: Understanding Arbitrum 2-Dimensional Fees.

Gotcha now, thanks for explaining!