# Moderate refund removal alternatives
This document lays out some possible options for alternatives to EIP 3298 (removal of refunds) that try to preserve some of the legitimate goals and positive incentives that refunds provide.
### Why perhaps not total removal?
Total removal is the simplest option and it accomplishes the desired effects, but it also has some downsides that have been [identified by the community](https://ethereum-magicians.org/t/eip-3298-removal-of-refunds/5430). The two strongest critiques of total removal of refunds that I have seen are:
#### Zero -> nonzero -> zero storage use patterns
There are two major examples of this:
* Mutex locks on contracts, where before contract A calls contract B, it first flips a storage slot to some nonzero value. When contract A itself is called, it checks that that storage slot is empty; if it is not, the call fails. This prevents re-entrancy. When the call finishes, the storage slot is flipped back to zero.
* Approving an ERC20 token for exactly the desired amount and then immediately spending that amount.
#### Incentive to leave 1 token
When you spend your entire ERC20 balance of some type of token, the storage slot representing the balance drops to zero. But if there is any chance, however remote, that you will receive that type of token again, there is an incentive to leave 1 token of the smallest denomination in your balance so that if the balance gets increased again it counts as nonzero -> nonzero instead of zero -> nonzero, saving you 15000 gas.
Today, there is a strong countervailing incentive not to do this: decreasing your balance fully to zero gives you a 15000 gas refund. But removing refunds removes this incentive, increasing the risk that many users will opt to leave 1 small-denomination token behind whenever they clear balance, bloating storage.
### Proposals
#### 1. Refunds only for `0 = orig = new != current`
We add a 15000 gas refund _only_ in the case where all three of the following conditions are true:
* The original value of the storage slot (meaning, before tx execution began) is zero
* The current value is nonzero
* The new value (that the SSTORE is setting that slot to) is zero
This preserves the low cost of the mutex use case and the approve-and-send use case. Because every 15000 gas refund can be mapped to a prior 15000 gas surcharge for filling the same storage slot, this proposal also preserves the invariant that the amount of gas spent _on execution_ in a block cannot exceed the gas limit. A block may _appear_ to spend more than the gaslimit, but this would only be because some of that gas is the 15000 gas surcharge for filling an empty storage slot, which increases storage size if not reverted but does not contribute to short-term block processing time.
#### 2. Extension of (1): add a further refund for _any_ `orig = new != current`
We add a refund of `SSTORE_RESET_GAS` (equal to `2900` today, `= 5000 - COLD_SLOAD_COST` as of EIP 2929) if a storage slot is reset to its original value (meaning, `new = orig` but `current != orig`). If `orig = 0`, the above 15000 refund is applied on top for a total refund of 17900.
The reasoning here is that if, at the end of a transaction execution, the storage value in the cache equals the storage value in the trie, the trie does not need to be modified; it only needs to be read. Hence, it suffices to only charge gas for the reading (`COLD_SLOAD_COST`) and not the writing.
This will make mutexes and approve-and-send behaviors _even cheaper_, because on net they would only cost 2200 gas (`COLD_SLOAD_COST + 100`), down from the current ~5100.
#### 3. Charge less for `0 = new != orig = current`
We preserve some incentive to change a storage slot value to zero, by reducing the gas cost if `orig = current != new = 0` by `CLEAR_INCENTIVE_GAS = 1000`.
#### 4. Comprehensive revamp of storage rules
As an alternative to (1, 2, 3), we could also make a more comprehensive cleaning-up of storage cost mechanics. For each storage slot, we currently already store whether or not it has been _accessed_. We extend this to two flags: `accessed` and `modified`. We add four costs:
`COLD_SLOAD_COST = 2000`
`MODIFICATION_COST = 2900`
`UNZEROING_COST = 17900`
`CLEAR_INCENTIVE_GAS = 1000`
The "base cost" of `SLOAD` is 100 and `SSTORE` is 100. We charge additional costs according to the following rules:
* If the storage slot is _not_ `accessed` and it gets `SLOAD`ed or `SSTORE`d, charge an additional `COLD_SLOAD_COST` gas and set `accessed = True`
* If the storage slot is _not_ `modified`, and it gets `SSTORE`d to a value other than its original value, charge an additional `UNZEROING_COST` if the original (meaning, at the start of the transaction) value is zero or `MODIFICATION_COST` if the original value is nonzero, and set `modified = True`
At the end of a transaction execution:
* If `modified = True` but the new value is the same as the original value, refund `UNZEROING_COST` if the original value was zero or `MODIFICATION_COST` if the original value was nonzero
* If `modified = True`, the original value is nonzero, and the new value is zero, refund [`CLEAR_INCENTIVE_GAS`](https://ethresear.ch/t/a-minimal-state-execution-proposal/4445)
This proposal also satisfies the goal that every refund of `UNZEROING_COST` or `MODIFICATION_COST` corresponds to some previous event during that same transaction execution where that same cost was charged, and that previous event _involves the same storage slot_. This prevents gastokens, and ensures that gas spent on execution is bounded to the gaslimit.

One powerful technique when working with polynomials is taking a set of evaluations of that polynomial and using that directly to compute an evaluation at a different point. For example, if $P(x)$ is a degree-100 polynomial, you can use the evaluations $P(0), P(1) ... P(100)$ to directly compute $P(101)$, or $P(1247130)$, in $O(N)$ time, without ever reconstructing the polynomial. This post describes how this is done. See also, this earlier and more detailed paper by Oxford researchers on the topic: https://people.maths.ox.ac.uk/trefethen/barycentric.pdf General technique Let $P(x)$ be the polynomial, and $x_1 ... x_N$ as the set of points for which we have evaluations of $P(x)$. Call these evaluations $y_1 ... y_N$. Think of $P(x)$ as a linear combination $\sum_i y_i L_i(x)$, where $L_i(x)$ is the polynomial that equals 1 at $x_i$ and 0 at all the other x-coordinates in the set. Now, let us explore how these $L_i$ can be computed. Each $L_i(x)$ can be expressed as:

6/4/2024Two paths to a solution exist, and have existed for a long time: weak statelessness and state expiry: State expiry: remove state that has not been recently accessed from the state (think: accessed in the last year), and require witnesses to revive expired state. This would reduce the state that everyone needs to store to a flat ~20-50 GB. Weak statelessness: only require block proposers to store state, and allow all other nodes to verify blocks statelessly. The good news is that recently, there have been major improvements on both of these paths, that greatly reduce the downsides to both: Some techniques for how a ReGenesis-like epoch-based expiry scheme can be adapted to minimize resurrection conflicts Piper Merriam's work on transaction gossip networks that add witnesses to be stateless-client-friendly, and his work on distributed state storage and on-demand availability Verkle trees, which can reduce worst-case witness sizes from ~4 MB to ~800 kB (this is definitely small enough, because existing worst-case blocks that are full of calldata are already 12.5M / 16 ~= 780 kB and we have to handle those anyway). See slides, doc, code.

6/4/2024Out of scope Data availability sampling and other sharding-related changes Light client processing The merge Revamp effective balance / current balance accounting Remove the current concept of effective vs current balance. Instead, keep (i) the balance inside the validator struct, and (ii) a counter of "duties fulfilled". Accounting for (ii) would be very simple: did you get the correct source? Add 1. Correct target? Add 1. Timely? Add 1. Every 256 epochs (can be staggered), we update the validator balance based on the duties fulfilled count, and reset the duties fulfilled count. The inactivity leak is also implemented at this stage. Note that this comes at the cost of some coarseness: if an inactivity leak starts halfway through a period, offlineness before and after the start of the leak is equally penalized (if we want to remove this entirely, we could also have two duties counters, one for leaking periods and one for non-leaking periods).

5/18/2024Along with proof of stake, the other central feature in the eth2 design is sharding. This proposal introduces a limited form of sharding, called "data sharding", as per the rollup-centric roadmap: the shards would store data, and attest to the availability of ~250 kB sized blobs of data. This availability verification provides a secure and high-throughput data layer for layer-2 protocols such as rollups. To verify the availability of high volumes of data without requiring any single node to personally download all of the data, two techniques are stacked on top of each other: (i) attestation by randomly sampled committees, and (ii) data availability sampling (DAS). ELI5: randomly sampled committees Suppose you have a big amount of data (think: 16 MB, the average amount that the eth2 chain will actually process per slot, at least initially). You represent this data as 64 "blobs" of 256 kB each. You have a proof of stake system, with ~6400 validators. How do you check all of the data without (i) requiring anyone to download the whole thing, or (ii) opening the door for an attacker who controls only a few validators to sneak an invalid block through? We can solve the first problem by splitting up the work: validators 1...100 have to download and check the first blob, validators 101...200 have to download and check the second blob, and so on. The validators in each of these subgroups (or "committees") simply make a signature attesting that they have verified the blob, and the network as a whole only accepts the blob if they have seen signatures from the majority of the corresponding committee. But this leads to a problem: what if the attacker controls some contiguous subset of validators (eg. 1971....2070)? If this were the case, then even though the attacker controls only ~1.5% of the whole validator set, they would dominate a single committee (in this case, they would have ~70% of committee 20, containing validators 2001...2100), and so they would be able to control the committee and push even invalid/unavailable blobs into the chain. Random sampling solves this by using a random shuffling algorithm to select the committees. We use some hash as the seed of a random number generator, which we then use to randomly shuffle the list [1..6400]. The first 100 values in the shuffled list are the first committee, the next 100 are the second committee, etc.

5/18/2024
Published on ** HackMD**

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up