Better gas price engine algorithm

[pipermerriam]

Depends on #494

What needs to be done?

The algorithm used by https://ethgasstation.info/ is pretty solid for determining gas prices. Lets implement something similar

How can it be done?

Implement a new gas price engine (see #494 ) that uses the following algorithm to compute gas prices.

The algorithm will be configured with the following parameters:

• Let N be the number of historical blocks that should be sampled.
• Let P be a number between [0-1] which represents the probability for gas price estimation. 0 meaning 0% probability and 1 meaning 100% probability.
• Let D be the desired maximum wait time in seconds for the transaction to be mined.

We then compute the following information by fetching data from the blockchain.

• Let A be the average block time for the last N blocks.
• Let M be the set of miners from the last N blocks.

For each miner in M compute:

• Let m.totalBlock be the number of blocks mined by a given miner.
• Let m.minPrice be the minimum gas price accepted for all transactions in all blocks mined by the given miner.
• Let g_max be the maximum gas price for all m.minPrice from the set of miners M.
• Let g_min be the minimum gas price for all m.minPrice from the set of miners M.

Now we compute B, the maximum wait time in blocks using the formula int(ceiling(D / A)).

Now we can use our computed data from the miners to compute the set of probabilities that a transaction will be included at each miner's min price. For a miner x let h be the total number of blocks mined by all miners where m.minPrice <= x.minPrice. The probability is computed using the formula (1 - (N - h)/N) ** B. Using this formula we can compute the set of probabilities p0, p1, ... for each miner. Note that each probability p0 corresponds to a miner m0. We also assume that these probabilities are ordered such that p0 < p1, p1 < p2, ....

Now compute the following values.

• Let p_max be the maximum probability from the set of probabilities p0, p1, ....
• Let p_min be the minimum probability from the set of probabilities p0, p1, ....

Now, to compute the gas price for a transaction to be included within B blocks with probability P as follows.

• If P > p_max, the gas price is g_max
• If P < p_min, the gas price is g_min

Otherwise, we find the location within p0, p1, ... such that pn <= P <= pn+1. The desired gas price can then be computed as follows.

If pn == pn+1 then the desired gas price is mn.minPrice. Otherwise...

• Let p_left be pn
• Let p_right be pn+1
• Let g_left be mn.minPrice
• Let g_right be mn+1.minPrice

(P - p_right)/(p_left - p_right) * (g_left - g_right) + g_right

Below is an example implementation of this formula in python.

import operator
import collections
import math

from web3 import Web3

from cytoolz import (
    groupby,
    sliding_window,
)

from eth_utils import (
    to_tuple,
)

#w3 = Web3(Web3.IPCProvider())
w3 = Web3(Web3.HTTPProvider('https://mainnet.infura.io'))


MinerData = collections.namedtuple('MinerData', ['miner', 'num_blocks', 'min_gas_price'])
Probability = collections.namedtuple('Probability', ['gas_price', 'prob'])

#SAMPLE_SIZE = 100
SAMPLE_SIZE = 10
ALLOWED_WAIT = 60
PROBABIITY = 95


def get_avg_block_time(w3, sample_size):
    latest = w3.eth.getBlock('latest')
    oldest = w3.eth.getBlock(latest.number - sample_size)
    return (latest.timestamp - oldest.timestamp) / sample_size


def get_raw_miner_data(w3, sample_size):
    latest = w3.eth.getBlock('latest', full_transactions=True)
    blocks = [latest] + [w3.eth.getBlock(latest.number - i, full_transactions=True) for i in range(sample_size - 1)]

    for block in blocks:
        for transaction in block.transactions:
            yield (block.miner, block.hash, transaction.gasPrice)


@to_tuple
def aggregate_miner_data(raw_data):
    data_by_miner = groupby(1, raw_data)

    for miner, miner_data in data_by_miner.items():
        _, block_hashes, gas_prices = map(set, zip(*miner_data))
        yield MinerData(miner, len(set(block_hashes)), min(gas_prices))


@to_tuple
def compute_probabilities(miner_data, wait_blocks, sample_size):
    """
    Computes the probabilities that a txn will be accepted at each of the gas
    prices accepted by the miners.
    """
    miner_data_by_price = tuple(sorted(
        miner_data,
        key=operator.attrgetter('min_gas_price'),
        reverse=True,
    ))
    for idx in range(len(miner_data_by_price)):
        min_gas_price = miner_data_by_price[idx].min_gas_price
        num_blocks_accepting_price = sum(m.num_blocks for m in miner_data_by_price[idx:])
        inv_prob_per_block = (sample_size - num_blocks_accepting_price) / sample_size
        probability_accepted = 1 - inv_prob_per_block ** wait_blocks
        yield Probability(min_gas_price, probability_accepted)


def compute_gas_price(probabilities, desired_probability):
    first = probabilities[0]
    last = probabilities[-1]

    if desired_probability >= first.prob:
        return first.gas_price
    elif desired_probability <= last.prob:
        return last.gas_price

    for left, right in sliding_window(2, probabilities):
        if desired_probability < right.prob:
            continue
        elif desired_probability > left.prob:
            raise Exception('Invariant')

        adj_prob = desired_probability - right.prob
        window_size = left.prob - right.prob
        position = adj_prob / window_size
        gas_window_size = left.gas_price - right.gas_price
        gas_price = int(math.ceil(right.gas_price + gas_window_size * position))
        return gas_price
    else:
        raise Exception('Invariant')


def get_gas_price(probability=PROBABIITY, allowed_wait=ALLOWED_WAIT, sample_size=SAMPLE_SIZE):
    avg_block_time = get_avg_block_time(w3, sample_size=sample_size)
    print('AVG BLOCK TIME:', avg_block_time)
    wait_blocks = int(math.ceil(ALLOWED_WAIT / avg_block_time))
    print('WAIT BLOCKS:', wait_blocks)

    raw_data = get_raw_miner_data(w3, sample_size=sample_size)
    miner_data = aggregate_miner_data(raw_data)

    probabilities = compute_probabilities(miner_data, wait_blocks, sample_size=sample_size)
    print('PROBABIITIES:', probabilities)

    gas_price = compute_gas_price(probabilities, PROBABIITY / 100)
    print('GAS PRICE (wei)', gas_price)
    print('GAS PRICE (gwei)', Web3.fromWei(gas_price, 'gwei'))

[ethgasstation]

Hi All- you might be interested in looking as this code- its a much simpler version of the ethgasstation.info code - it works pretty well and is easy for anyone to run https://github.com/ethgasstation/gasstation-express-oracle

[lolminer]

Hey!
Thanks for your note and code.
I'm trying understand how it works and can't understand why in your note

probability = (1 - (sample_size - num_blocks_accepting_price) / sample_size) ** wait_blocks

but in code it seems to be

probability = 1 - ((sample_size - num_blocks_accepting_price) / sample_size) ** wait_blocks

It seems to be mistake in note, rather then code

[pipermerriam]

@lolminer thanks for finding this. The error is in the code actually. Fixed here #615

[KarinaMojsievich]

Could you please tell me what is this formula? Did you get it yourself or is it a ready one?
(1 - (N - h)/N) ** B

[pipermerriam]

@KarinaMojsievich it's something I worked out on a whiteboard. I don't recall the exact specifics. You'd have to read my post from above and figure it out.

[carver]

@raniama please do not spam a bunch of locations with the same question. See the links in my last response to you.