Rewarded force-close mechanism to eliminate stale allocations

Governance & GIPs Graph Improvement Proposals (GIP)
1

Zombie Indexers are hurting the protocol, but it’s too gas expensive and there’s almost nothing to gain for someone to force-close stale allocations. Wouldn’t it make sense to give a reward to whoever closes stale allocations? Think like Maker liquidations. The cleaning job would be done by Searchers! (“Searchers” is a term used by Flashbots to describe the role of searching for and submitting liquidations, arbitrage, and other forms of MEV. “Keepers” is another good term and they have a similar role to Searchers but in the Keep3r Network.)

Q1: Where would the reward come from?

A1: It could be paid from the delinquent Indexer’s allocation stake. To initiate the conversation, we propose that 100% of the Indexer’s allocation stake be paid to the Searcher who force-closes a stale allocation.

Q2: If the force-close reward were to be paid from the Indexer’s allocation stake, wouldn’t this be a way to move GRT from a vesting contract (the delinquent account) into an account where the GRT would be liquid (the MEV reward account)? Or, If a malicious participant suspects that their vesting contract would be revoked (as may be the case here if they are not serving queries) then wouldn’t they be motivated to extract any fraction of their unvested stake using this method?

A2: It is highly unlikely that a malicious Indexer will be able to take advantage of force-close. The expiration date of allocations is publicly known as soon as an allocation is opened. Furthermore, the value of force-closing a potential future stale allocation is known as soon as the allocation is opened. The moment an allocation expires, Searchers will compete to submit force-close transactions. These transactions will result in a GRT reward to the Searcher during the same block that the force-close transaction is submitted. This reward can be atomically swapped for ETH using a decentralized exchange (DEX) like Uniswap. That ETH can be used to pay for transaction priority. In other words, this is capital-free MEV that can be performed in a single transaction. Because it’s capital-free, this will result in aggressive MEV competition, with most of the GRT being deposited into a DEX GRT-ETH pool, and most of the ETH being spent on transaction ordering priority.

Q3: Can you quantify the impact of stale allocations?

A3: We can estimate the reduction of indexing rewards that honest Indexers have experienced historically because of the existence of stale allocations. To estimate this, we would need to identify all instances where a delinquent Indexer was allocated to a subgraph deployment at the same time an honest indexer closed their allocation on that deployment. We’d then add up the indexing rewards the honest Indexers actually collected during those circumstances. We’d then subtract that number from the sum of indexing rewards that honest Indexers would have received had the delinquent Indexer not been allocated when the honest Indexer closed.

7 Likes
2

@Brandon suggested I also consider penalties that are proportional to the amount of harm caused by stale Indexers. I’ll refer to the extreme penalty given above as the “annihilation penalty”. I give three more options below.

Note: In A2 in my initial post, I claim that force-closing can be performed using a “capital-free” strategy, but I should have said it can be performed using a “low-risk” strategy. The Searcher still needs enough ETH in their account to cover the base fee of the transaction (tx). Additionally, Flashbots blocks are occassionally uncled and signed txs in those blocks are included by other miners with no successful execution guarantees. These are nuances that need to be better understood. That being said, this GIP does not require the existence or use of Flashbots to work.

Constant penalty

Send the Searcher enough GRT to cover their gas cost plus a fraction of the stale Indexer’s allocated stake as a reward. E.g.,

 Transfer 1000 + .1*(allocated stake - 1000) GRT to Searcher

1,000 GRT (converted to ETH) is an estimate for the gas cost of force-closing an allocation. That number and the 10% penalty should be considered placeholders that will be changed based on further discussion here and updated in the future based on fluctuating ETH-GRT rates. The gas cost amount of GRT should be high enough to avoid frequent updates.

Linear penalty

If we want to be even gentler on the violator, then we can make the penalty scale relative to how late the violator is:

 Transfer 1000 + .1*(epochs late/27)*(allocated stake - 1000) GRT to Searcher

where epochs late starts at 0 on the epoch the stale Indexer’s allocation expires. This function will cover only the cost of gas on the day the transaction expires - no penalty. But, starting at epochs late = 1, a linearly increasing penalty will be included. The stale Indexer has 28 days to close their allocation before the full penalty takes place. Of course, we should expect to see the stale allocation force-closed immediately, if 1,000 GRT (converted to ETH) is above the amount of gas needed to execute the force-close function.

Exact penalty

In my initial post, A3 gives a way to estimate the impact that stale allocations have had on all other honest Indexers. We can also use that method to get a penalty based on the “exact cost” the stale Indexer had on a single stale allocation:

 Transfer 1000 + exact cost GRT to Searcher

To assign exact cost we calculate the sum of indexing rewards that honest Indexers would receive if they were to all close their allocations at the block the stale Indexer’s allocation expired. We would then calculate the sum of rewards that honest Indexers would have received had the stale Indexer not been allocated on this subgraph deployment - this number will be higher than the first sum. We then subtract the first sum from the second sum to arrive at the exact cost. All of these calculations would need to be done on-chain and I think it’s the most expensive of the penalty options listed.

4 Likes
3

Here is a sketch of a Flashbots-oriented contract that we could write, deploy, and make available for any Searcher to call:

  1. Calls The Graph’s closeAllocation() function and aborts if an error is returned.
  2. Optionally swaps some of the GRT reward returned by closeAllocation() into ETH. This could be useful if the GRT reward is high and the Searcher is anticipating that they will need to use a significant amount of ETH (more than they currently have available in their account) to pay for tx priority.
  3. Uses coinbase.transfer() to send ETH to pay for Flashbots tx priority.
  4. Returns the remainder of the GRT to the Searcher as profit.
5 Likes
4

I like the idea. One additional modification to the Staking contract would be to make it so closeAllocation can be called by anyone instead of just any of the delegators.

A milder version of this would be, instead of slashing the indexer, just distribute rewards (if any) to the searcher. Good thing is that is not too harsh on an indexer having issues to close those allocations, however, if the penalty is too mild it might not be enough deterrent, and in some cases I guess rewards can just be too small to compensate the searcher.

You can see here Dune Analytics the number of allocations that are currently over max epochs.

6 Likes
5

Depending on the incentives, I would imagine this would become quickly bot dominated (which I don’t think is a bad thing).

6 Likes
6

I generally feel positive about this idea, but the vesting contract problem is a serious issue. The rebuttal (that the reward would go to a bot) misses a crucial point - there is no recourse for the harmed entity: the grantor. One possible workaround would be to have two phases where in the first phase anyone can close with 0x0 and there is a second phase where the penalty increases over time. The reason this may work is that the grantor of a vesting contract could revoke and then call 0x0 to retrieve their funds, preventing others from obtaining them.

Re: “distribute rewards (if any) to the searcher”. It’s important for the economics of the protocol that rewards are not distributed without a valid PoI. Limiting this functionality to Indexers who submit a PoI backed by a proportional slashable stake may work (eg: to close their allocation and open yours at the same time)

Keep in mind that for the MIPs program we want to keep long-lived micro-allocations open to avoid paying gas fees.

I’m generally disappointed with the focus on indexing rewards, not limited to this thread but across the board. If query fees dominate the revenue stream for an indexer, stale allocations such as these are not much of a concern. I’d rather focus limited time on solving any problem related to queries than allocations - which without queries are pointless.

The simplest solution may just be to allow anyone to close an allocation with 0x0 after it has expired. Allow indexers which are motivated to open their own allocations to do so, or dApp developers who are dissatisfied with service, or whatever. Then get back to queries.

7 Likes
7

there is no recourse for the harmed entity: the grantor

This is an important point.

Perhaps this proposal should simply focus on allowing anyone to close stale allocations with minimal impact on the stale Indexer. I.e., we don’t give rewards to the Searcher nor do we slash the stale Indexer’s allocated stake.

As @ari pointed out, this will require a modification to the Staking contract to allow closeAllocation to be called by anyone.

Then, when a Searcher force-closes a stale allocation, we can transfer a “small” amount of GRT from the stale Indexer to the Searcher. It needs to be just enough to cover the cost of closeAllocation. Of course, without oracles, we don’t know the exact amount, so we will need it to have some buffer to deal with base fee and GRT-ETH fluctuations.

(We could charge the exact amount of GRT to the stale Indexer. This could be done using the BASEFEE opcode, a flash loan, Chainlink for an ETH-GRT oracle, and a few DEX swaps. But that would cost the stale Indexer much more than the flat price of GRT.)

8

We could charge the exact amount of GRT to the stale Indexer. This could be done using the BASEFEE opcode, a flash loan, Chainlink for an ETH-GRT oracle, and a few DEX swaps.

@Sam Is it actually possible to determine the exact cost of closeAllocation() from within a contract if the assumption is that Flashbots could be used to submit the tx? If a Flashbots searcher could opt to pay the miner through coinbase transfers and/or gas fees, a contract could determine the base fee (via the BASEFEE opcode), but I’m not sure the contract can determine the value of the coinbase transfer and/or priority fee ahead of time to calculate the amount of GRT that should be taken from the stale allocation.

The way to factor in the cost of closeAllocation() seems to be the described workflow where closeAllocation() sends the caller the GRT which can then be swapped into ETH to cover a coinbase.transfer() - the searcher would then simulate locally before sending a bundle to determine whether the amount of GRT will be sufficient to cover the bundle gas price that it wants to bid. But, the calculation of the amount of GRT wouldn’t have as inputs the bundle gas price.

One possible workaround would be to have two phases where in the first phase anyone can close with 0x0 and there is a second phase where the penalty increases over time. The reason this may work is that the grantor of a vesting contract could revoke and then call 0x0 to retrieve their funds, preventing others from obtaining them.

@That3Percent IIUC grantor would only be able to retrieve its funds if it also participates as a searcher and out bids all other searchers for tx priority to call closeAllocation() right? So, the grantor wouldn’t necessarily have a guarantee here.

FWIW looks like Maker’s Liquidation 2.0 module uses a DAI reward with a constant component that is meant to cover gas costs and that is adjustable via governance as well as a component that grows linearly with the debt size of a vault so it could be worthwhile to take a look at how that incentive structure has fared for the system thus far.

1 Like
9

The guarantee comes from the fact that there is a period of time where anyone can close the allocation without slashing or collecting a reward. During that period the grantor would close the allocation. If someone else races them, that’s fine because no funds are slashed during the period.

In any case, I don’t think this line is the strongest of the alternative designs put forward here. Here are the ones I believe are in the best spot maximizing effectiveness per simplicity:

A: Remove the restriction that only delegators can use 0x0 to close an allocation for no reward
B: Allow another indexer to collect the minted reward by submitting a PoI and simultaneously opening an allocation

1 Like
10

This is an implementation of option A, removing the restriction that only delegators can close after the max allocation period.

2 Likes
11

I like option A from Zac the simplicity and because it removes a hurdle (being a delegator) to call that function that anyone should be able to call.

Some extra data. You can see that most of the stale allocations are concentrated on a few indexers.

A
A1382×760 56.1 KB

Additionally, most of the allocations are under the 28 days period, a considerable amount close to the limit and a few over 28 days, even some to extremes like > 190 days. Those are skewing any average we calculate.

B
B1378×762 43.7 KB

2 Likes
12

Thanks for driving this discussion @Sam!

Proposed Modified Design

Just to clarify my recommended changes to the design you mentioned. I suggest two separate sets of payments when an allocation is closed late. Both of these should be paid from the offending Indexer’s stake as opposed to any protocol issuance of new tokens:

  • Damages Awarded to Indexers. This is simply the amount of indexing rewards that the allocation would have been entitled to if it had been closed honestly. It should be distributed to all other Indexers currently allocated, proportional to their allocation amount.
  • Keeper Reward. Should be distributed to anyone who closes the stale allocation. This amount should increase linearly from 0 to 100% of an Indexer’s stake over a set period of time. Assuming Keepers are rational utility maximizers and that anyone can be a Keeper, we should expect that the stale allocation is closed as soon as the Keeper Reward exceeds the gas costs of closing the stale allocation (no need to try and compute the gas cost or set via a protocol parameter).

If the Indexer themselves closes the stale allocation with a valid PoI before a Keeper managers to close it, then I suggest there be no penalty and the Indexer claims indexing rewards as per usual.

These penalties/rewards should only be enacted on subgraphs that are eligible for indexing rewards (i.e., haven’t had them disabled by the Subgraph Oracle).

Rationale

I believe the goal of this mechanism should be to make honest Indexers indifferent to the possible effects of lazy Indexers. To achieve such a goal, it is only necessary to make the honest Indexers whole, as opposed to trying to be as punitive as possible on a lazy Indexer, who could in theory be closing their allocations late for innocuous reasons.

I also don’t think the protocol should pay Keepers any more than is strictly necessary to cover the transaction costs (gas and operational) of closing the stale allocations. A linearly ascending Keeper reward accomplishes this.

Possible extensions

Submitting so-called “Zero PoIs” (PoIs consisting of 0x0000…) also skews the incentives to honest Indexers on a subgraph.

I think it’s worth considering also applying this penalty any time a zero PoI is submitted on a subgraph that is eligible for indexing rewards, even if submitted by the Indexer whose allocation it is.

Responses to some of the comments/concerns above

  1. Complexity of computing damages to honest Indexers. No need to overcomplicate this by trying to take the delta of what honest Indexers would have received with and without the lazy Indexer present. Since indexing rewards are distributed proportional to allocated stake, the damages are simply the indexing rewards that the lazy Indexer would have been entitled to.
  2. Complexity of estimating gas costs. Just increase Keeper reward linearly and let the free market take care of it.
  3. Risk to vesting contracts @ari informed me there are two types of vesting contracts in use in the ecosystem today: revocable and non-revocable:
    • Revocable vesting contracts don’t allow the recipient to use unvested tokens in the protocol, so no risks here.
    • Non-revocable vesting contracts do allow the recipient to use unvested tokens in the protocol, and the risk is that the penalty provides a way to accelerate vesting. I think this is also not a concern here, given that the bulk of the reward is likely to go to other honest Indexers on the subgraph and there isn’t a way to reliably exclude honest Indexers from participating on such a subgraph. It’s possible the lazy Indexer would be able to accelerate some vesting but at the expense of a large penalty. A similar dynamic already exists today where technically an Indexer could dispute themselves and receive a 50% Fisherman rewards to try and circumvent vesting, but at the cost of the other 50% being slashed.
  4. We should be focusing on query fees, not indexing rewards. I don’t see the two as mutually exclusive. Indexing rewards are an important mechanism for bootstrapping honest Indexer availability on a subgraph so they can serve queries. We’ve already seen several instances of lazy/ineffective Indexers overallocating on a subgraph and skewing the incentives such that query availability is degraded (i.e., Synthetix subgraphs and Pooltogether subgraphs).

Bikeshed

  • I prefer Keeper to Searcher because “Search” already feels overloaded in software contexts and The Graph is repeatedly compared to “the Google of Blockchains,” further overloading the search metaphor for us. Keeper, on the other hand, doesn’t have any conflicting meanings in a software context that I’m aware of.
4 Likes
13

I agree that Keeper is a closer term to what we would call a CronJob. Other protocols like Gelatto can setup automated task to call this function.

The linearly increasing reward sounds interesting so we don’t fix it and change it often and we also avoid any need of gas calculations.

@sam @Brandon where should this this reward come from? one possibility is to take it from the allocation, but should only consider the indexer stake, working the same way like a slashing penalty

One way it could work is:

  • closeAllocation is called by any account over the maxAllocationEpochs
  • Calculate the penalty with these two inputs:
a) time: epochs passed since <maxAllocationEpochs>
    
currentEpoch - createdAtEpoch + maxAllocationEpochs

b) allocationTimeoutPenaltyPerEpoch: <fixed amount>
  • Free the tokens in the Allocation
  • Bookkeep a reduction in the indexer stake by the penalty amount
  • Transfer the GRT to the function caller

Note: the penalty formula needs to be per epoch because we store the timestamp in that unit for the allocation, so that’s the smaller granularity we have

2 Likes
14

I would just take it from the Indexer’s entire pooled of owned stake, which would deplete their amount of available stake for future allocations, as well as their delegation capacity.

If we limit to taking from the Indexer’s allocated stake, there may be some instances where the linearly increasing Keeper reward is never sufficient to cover gas costs.

3 Likes
15

Wouldn’t this make the potential max punishment for “too long allocation” be higher than the (intended) max punishment for “serving wrong data” (a.k.a. “incorrect POI”) ?

1 Like
16

I believe that @Brandon’s Feb. 9th post and @ari’s Feb. 9 post provide good solutions to the main theme of this topic. I especially like the linearly increasing Keeper reward, and I think that will be easy to get a consensus on from the community.

Open topics

  • Brandon’s Feb. 9 proposal includes an extension to penalize any time Zero Proof of Indexing (PoI) is submitted when closing an allocation. We are uneasy with this extension because there are occasionally determinism bugs that are triggered after opening an allocation on a synced subgraph. Currently, we close such failed allocations with Zero PoI to avoid the risk of slashing or engaging in the arbitration process. Perhaps a compromise here is PR544 which requires a valid PoI when opening an allocation? (I do like this extension in principle. In 2021, we had 2.7% inflation vs. 3% target. In other words, Indexers earned 10% less indexing rewards than they should have. I believe we would have hit 3% inflation if this extension and the Damages Awarded to Indexers and Keeper Rewards existed. Once we eliminate determinism bugs, I am a fan of this extension.)
  • In today’s Indexer Office Hours, there was disagreement about the definition of “stale”. Our stance is that as soon as the 28th epoch is over, the allocation is “stale” and is eligible to be force-closed and damages collected. Other Indexers believe there should be a grace period beyond the 28th epoch.
  • @Koen raises an interesting question regarding the scale of Damages Awarded to Indexers. Could the damages exceed the cost of slashing?
  • What, if anything, should be done for the lazy Indexer’s unfortunate Delegators? If an Indexer were to self-delegate then any GRT compensation we give their Delegators potentially gives the lazy Indexer a way to accelerate vesting. What if we gave harmed Delegators an option for immediately redelegating to another Indexer and bypass the thawing period?
  • During Indexer Office Hours, someone asked about the gas required to execute the Damages Awarded to Indexers. Is this cost of concern to us? If there are many Indexers allocated to a single subgraph, it does seem like this will be expensive.
2 Likes
17

Sorry guys, that I reply only now, was quite busy :frowning: But it’s a really important topic, thanks @Sam that you starting it.
I traditionally disagree to punish anyone. I don’t think so, that it’s a good intention for network participants to get rewards by punishing someone.
But I agree, that possibility to close stale allocations for everyone (not only delegators) is a good idea.
Generally, I prefer to rearrange rewards from this particular allocation to someone who will close this allocation, but only with correct POI. If someone will close with 0x POI, rewards burn as it is right now.
We shouldn’t “slash” self-stake in these cases.

Main points from me:

  1. I totally agree with Zac. That current system is quite good, and if some Indexer wants to allocate to some subgraph to start getting rewards, but there are stale allocations, he\she can close allocation (get or not rewards), and it creates an opportunity for this Indexer to cover his expenses. From my point of view, even without rewards from stale allocations, it will be enough. And it requires minimal changes in code.
  2. I believe that we have a problem only with significant allocations, like 100k GRT and more. But there are a lot of allocations with 1-10k GRT and they don’t make any harm. In case of “slashing” for self-stake for “covering gas”, it will make sense to close even these allocations for farming rewards. I don’t think so, that it’s a good idea.
2 Likes
18

I agree with Zac about how this could be solved with more significant queries: more fluid and accurate signals for indexers as well as rebate pool motivation to stay within the maximum epoch limit

It makes sense to limit the keeper role to the indexer’s delegators, other indexers, and the subgraph owner (Does dApps know which indexer served them data?) OR, let closing stale allocations still cost something to the Keeper even after gas-cost compensation, and whoever’s incentive for rewards outweighs the cost can force-close.

Grace period is sort of iffy to determine. If an indexer relies on indexer software (which I hope they do) and there’s a subgraph that failed undeterministically such that agent cannot close, then how do we tell if an indexer has forgotten about it or if they are planning to manually grab the valid POIs?
This is where ‘grace period’ makes sense to me, but the indexer software do reallocation the epoch before it becomes stale and so the indexer would have 1 epoch to do manual allocation before ‘stale’

Some similar ideas here Allow multiple undelegation request from a delegator - #2 by That3Percent

nit-picking

=> currentEpoch - (createdAtEpoch + maxAllocationEpochs)?

Another thing I was wondering, if the indexer neglected all operations completely, all of their allocations are stale (say if the weighted average age > 28 epochs), maybe we can use the batch closeAllocationsMany to shut down all their stale allocations?

19

In my mind, there are two main benefits to keeping the slashing + keeper reward + Indexer damages:

  • Doesn’t require altruism (or introduce a griefing vector), as would be the case if we relied on other Indexers to cover the gas costs of closing stale allocations.
  • Makes Indexers indifferent to stale allocations, since they will receive damages, making interacting with the protocol more predictable.
  • Slowly leaks away value from Indexers that are not actively engaging in the protocol.

In theory, yes, but I believe that would mainly be the case when an Indexer allocated a very small amount. Also, I believe right now slashing for bad PoIs is actually based on an Indexer’s entire owned stake, though as you allude we’ve considered proposing that this change to be a % of allocated stake.

I’m in favor of a short grace period, of perhaps an epoch. That way we don’t punish Indexers who had their Indexer Agents configured to use the max allocation duration and then have technical issues at the last minute that require them to close the allocation manually.

1 Like
20

We can get around that by granting the other Indexer indexing rewards through submitting a PoI.

This may be a problem since some unknown amount of the allocated stake belongs to delegators. It may not be clear to the protocol how to do this accounting, leading to a potential negative balance for the indexer (a coin duplication for the withdrawn delegator and slashing indexer). This would happen when:

  1. A delegator delegates 1M GRT to Indexer A with 200K GRT
  2. The Indexer allocates 1.2M GRT to subgraph
  3. The delegator withdraws 1M GRT
  4. The allocation goes stale
  5. Indexer B slashes for 50%, taking 600K GRT from allocation, returning 500K GRT to Indexer A pool, and burning 100K GRT.

Indexer A pool has a balance of -600K GRT. If these 3 participants are colluding, they just minted 400K GRT for themselves.

Right now this sort of attack is not possible because the Delegator’s stake is protected.

1 Like