# AutoPrice

## Background

### Control Mechanisms for Trustless Self-Governing Protocols

It is a feature of public blockchains, where a protocol parameter needs to adapt to certain conditions, but should not be controlled by a specific participant. The solution is to implement a mechanism where it auto-adjusts, according to quantifiable and objective conditions. The primary example is Bitcoin’s difficulty adjustment. There, variations in average block time are used to dynamically adjust Bitcoin’s block difficulty, every 2016 blocks. Owing to difficulty adjustment, Bitcoin blocks are mined every 10 minutes on average without any external control. Shifts in block time feed back into the difficulty parameter, which then dampens said shifts, creating a negative feedback loop. Here, Bitcoin's designer made use of elementary control theory, setting mean block time as a process variable and difficulty adjustment as the control action:


### Gas Price Volatility

Blockchains have a limited supply, and a vertical supply curve. For that reason, blockchain resources are subjected to very high price volatilities, once user demand surpasses platform capacity.

Let's consider Ethereum. Demand for gas isn’t distributed equally around the globe. Ethereum users exist in every inhabited continent, with the highest demand seen in East Asia, primarily China. Europe+Africa and the Americas seem to be on par in terms of demand. This results in predictable patterns that follow the peaks and troughs of human activity in each continent. The correlation between gas usage and price is immediately noticeable, demonstrated by a 5 day period from March 2019.


The grid marks the beginnings of the days in UTC, and the points in the graph correspond to hourly averages, calculated as:

- Average hourly gas usage per block = Total gas used in an hour / Number of blocks in an hour
- Average hourly gas price = Total fees collected in an hour / Total gas used in an hour

Price oscillations are caused by the daily demand cycle. When we average out daily chunks of data, we obtain the following profiles:


To learn more about gas price volatility in Ethereum, see this [blog post](https://solmaz.io/2019/10/21/gas-price-fee-volatility/).

Control mechanisms to stabilize gas prices have been proposed in Ethereum, such as [EIP-1559](https://github.com/ethereum/EIPs/blob/master/EIPS/eip-1559.md). In this proposal, the feedback loop is set in a way to adjust an in-protocol price floor. This time, the process variable is block fullness. The price floor adjusts dynamically according to block fullness to ensure that demand at a given time does not exceed supplied blockchain throughput. The proposed mechanism does not aim to neutralize long term volatility though---it aims to extract an objective gas price, increase market efficiency and bring only short-term stability to the gas price. The frequency of the control action is every ~13 seconds (Ethereum's block time), where the price can adjust by 1/8. For that reason, hour to hour and day to day volatilities remain.

What if we wanted the price to remain stable in the longer term, but also ensure that surges are infrequent enough not to affect the user experience?

## Long-term Gas Price Adjustment

The control mechanism admits the following parameters:

- `CONTROL_RANGE`: Number of blocks between two consecutive price adjustments.
- `TARGET_FULLNESS`: The reference fullness value the mechanism should correct to.
- `INITIAL_PRICE`: The initial value of the fixed gas price.
- `PRICE_ADJUSTMENT_RATE`: The rate at which price increases or decreases after an adjustment.
- `BLOCK_GAS_LIMIT`: The maximum amount of gas that can be used by transactions included in a block.

Once every `CONTROL_RANGE` blocks, the following algorithm updates the in-protocol fixed gas price:

# blocks: an array of the last CONTROL_RANGE blocks
# prev_price: previous fixed price

fullnesses = []
for b in blocks:
    fullnesses.append(b.get_gas_used()/BLOCK_GAS_LIMIT)

if median(fullnesses) > TARGET_FULLNESS:
    next_price = prev_price * (1 + PRICE_ADJUSTMENT_RATE)
else:
    next_price = prev_price / (1 + PRICE_ADJUSTMENT_RATE)

We believe that optimal values for above parameters exist, which can be found by a combination of simulations, econometrics and trial & error. Once set, the control mechanism would bring day to day gas price stability to the protocol.

## Simulations

The implementation of the simulations below can be found in [this git repository](https://github.com/CasperLabs/fee-market-simulator).

### Generating Demand

We treat the demand curve as a [cumulative distribution function](https://en.wikipedia.org/wiki/Cumulative_distribution_function), and use [inverse transform sampling](https://en.wikipedia.org/wiki/Inverse_transform_sampling) to generate prices for the transactions submitted by users. We then verify our method by superimposing the histogram of sampled prices with the original demand curve:


While simple, this method depends on the following assumption: Changes in demand are reflected by a shifting of the demand curve which doesn't have to be uniform. The exact behavior of the demand curve is often complex, and simple models may fail to capture the nuances of a given market. In our method, increased demand reflects as a uniform *scaling* of demanded quantity with respect to a given price. E.g. in the figure above, changes in demand would cause the blue line to be scaled uniformly and vertically around the horizontal axis.

### Modeling Number of Buyers (Users) per Block

Given a demand curve, we can sample as many prices as we want. To model the daily demand cycle realistically, we can use a certain model to set the number of available users in the market that bid for inclusion in a single block. Whether they would send a transaction or get it included would depend on

- whether the price is floating or fixed,
- and others' transactions and gas prices.

Below is a model which oscillates between 3000 and 7000 users per block.


### Simulating a Floating Gas Price

We try to reproduce the daily demand cycle with a system that allows the gas price to float. Samples from the demand curve determine the willingness-to-pay (WTP) values of the agents. The agents then look at the minimum price of the previous block as a benchmark to determine how much they will set their gas price. By default, agents who can afford it overbid the previous block's minimum price by a factor of `OVERBIDDING_RATE`.

- If `WTP <= min_price`, they don't submit a transaction, because they can't afford to get it included.
- If `min_price <= WTP < min_price*(1+OVERBIDDING_RATE)`, they submit a transaction with `WTP` as the gas price.
- If `WTP >= min_price*(1+OVERBIDDING_RATE)`, they submit a transaction with `min_price*(1+OVERBIDDING_RATE)` as the gas price.

With this strategy, we can run a simulation and plot the median gas price from each block to see how it evolves. We let the initial price be relatively low, to see if it eventually converges to the market price:


Here, most agents overbid in the first half of the first day, which results in an exponential trend, due to how they keep multiplying price with the same rate. The trend continues until some agents aren't able to afford getting their transactions included in blocks, after which we see the prices mimic the curve we have given above.

Since the agents who can't afford inclusion don't submit transactions, we initially see a drop in the number of transactions submitted per block, which then converges to a stable value.


Indeed, it converges to around 476, the maximum number of transactions that can exist in a block.

### Simulating Price Adjustment

We implement the price adjustment algorithm that we described above. This simulation is simpler than the floating price case in terms agent strategy, since agents have only one option: submit a transaction at the protocol enforced fixed gas price, or not, depending on whether they can afford it:

- If `WTP >= fixed_price`, they submit a transaction.
- Otherwise, they don't submit a transaction.

We run the simulations with the following parameters:

BLOCK_GAS_LIMIT = 10_000_000
TX_GAS_USED = 21_000
BLOCK_TIME = 600
BLOCKS_IN_DAY = floor(SECONDS_IN_DAY / BLOCK_TIME)
CONTROL_RANGE = BLOCKS_IN_DAY
TARGET_FULLNESS = 0.65
PRICE_ADJUSTMENT_RATE = 0.01

Block time is 10 minutes, because simulations take too long otherwise. The first 2 parameters are taken from Ethereum, which result in 476 transactions per block. We set the control range as 1 day, target a median fullness of 65%, and allow the price to adjust 1% at a time.

We use the same function as before to generate the number of users per block, and let it run for 40 days:


We set the initial price to 35, and see if it converges to the market price we observed in the previous simulation:


It indeed converges to ~39, the maximum price we have observed in the previous simulation! This is because of the median fullness value we are targeting, 0.65, is selected to ensure that blocks are roughly 100% full during the height of the demand, with the current degree of daily volatility. This is indeed the case, once the price stabilizes:


If we were to plot the process variable, we would see it converge to 0.65:


With price adjustment, transactions don't wait in the transaction pool and immediately get included. If we plot the size of the transaction pool versus time, we should see it converge to zero once the price stabilizes:


There are a few days where a few transactions don't get included immediately, but price adjustment did not claim to eliminate all surges in the first place. Price adjustment remove 99% of the surges, and the remaining 1% can be mitigated through other means, such as users being allowed to pay a premium to prioritize their transactions if the previous couple of blocks were completely full.

### Choosing Optimum Target Fullness

TBD

### Price Adjustment during a Long-Term Trend

In the previous example, price adjustment successfully absorbed the daily volatility of our toy blockchain. However, we also wonder what would have happened if there were a long-term trend, superimposed with the daily cycle.

To answer the question, we use the following demand versus time curve:


It's the same cycle as before, but in the longer term, it increases until maximum height is reached around 100 days, and then decreases with the same rate.

We see that price evolves parallel to the trend:


The price reaches a high of 54, after which it subsides and converges back to the usual 39. The important thing is, while we don't observe volatility during the day, the gas price automatically adjusts to new market conditions without an external actor deciding for it.

The size of the transaction pool shows us that price adjustment still prevents surges, even when there is a long-term trend with the demand.


# Accounting for Token Price Volatility

In the previous sections, we considered a closed economic system where the demand is independent of the price of the token (in fiat) used to pay for gas.

# Attacks and Manipulations

TBD

# Conclusion

We introduced a way for blockchain protocols to adjust prices of resources in a self-governing way, without the need for an external actor, and absorb most of the daily volatility. The mechanism uses block fullnesses as a process variable to adjust an in-protocol gas price. This eliminates short term surges, and allows the price to slowly adapt to new market conditions at the same time.

WIP