We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
Crash in time based gas price strategies
* Version: 4.5.0
* Python: 3.6
* OS: osx


### What was wrong?

My script to check the gas price calculation crashes after the update to web3 4.5:
```
python test_gas_price.py                                                                     0:13:21
RPC: 252000000
Traceback (most recent call last):
  File "test_gas_price.py", line 14, in <module>
    print('Slow', w3.eth.generateGasPrice())
  File "/Users/paul/Work/venv-raiden/lib/python3.6/site-packages/web3/eth.py", line 385, in generateGasPrice
    return self.gasPriceStrategy(self.web3, transaction_params)
  File "/Users/paul/Work/venv-raiden/lib/python3.6/site-packages/web3/gas_strategies/time_based.py", line 160, in time_based_gas_price_strategy
    sample_size=sample_size,
  File "/Users/paul/Work/venv-raiden/lib/python3.6/site-packages/eth_utils/functional.py", line 22, in inner
    return callback(fn(*args, **kwargs))
  File "/Users/paul/Work/venv-raiden/lib/python3.6/site-packages/web3/gas_strategies/time_based.py", line 79, in _compute_probabilities
    reverse=True,
  File "/Users/paul/Work/venv-raiden/lib/python3.6/site-packages/web3/gas_strategies/time_based.py", line 67, in _aggregate_miner_data
    percentile(gas_prices, percentile=15))
  File "/Users/paul/Work/venv-raiden/lib/python3.6/site-packages/web3/utils/math.py", line 5, in percentile
    raise ValueError("Expected a sequence of at least 3 integers, got {0}".format(values))
ValueError: Expected a sequence of at least 3 integers, got {41000000000, 26000000000}
```

The code is the following:
```py
from web3.auto import w3

from web3 import middleware
from web3.gas_strategies.time_based import medium_gas_price_strategy, fast_gas_price_strategy, slow_gas_price_strategy
from web3.gas_strategies.rpc import rpc_gas_price_strategy

w3.middleware_stack.add(middleware.time_based_cache_middleware)
w3.middleware_stack.add(middleware.latest_block_based_cache_middleware)
w3.middleware_stack.add(middleware.simple_cache_middleware)

w3.eth.setGasPriceStrategy(rpc_gas_price_strategy)
print('RPC:', w3.eth.generateGasPrice())
w3.eth.setGasPriceStrategy(slow_gas_price_strategy)
print('Slow', w3.eth.generateGasPrice())
w3.eth.setGasPriceStrategy(medium_gas_price_strategy)
print('Medium:', w3.eth.generateGasPrice())
w3.eth.setGasPriceStrategy(fast_gas_price_strategy)
print('Fast:', w3.eth.generateGasPrice())
```


### How can it be fixed?

It should crash and return a proper gas price.


--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `web3/gas_strategies/time_based.py`
Content:
```
1 import collections
2 import math
3 import operator
4 
5 from eth_utils import (
6     to_tuple,
7 )
8 
9 from web3.exceptions import (
10     ValidationError,
11 )
12 from web3.utils.math import (
13     percentile,
14 )
15 from web3.utils.toolz import (
16     curry,
17     groupby,
18     sliding_window,
19 )
20 
21 MinerData = collections.namedtuple(
22     'MinerData',
23     ['miner', 'num_blocks', 'min_gas_price', 'low_percentile_gas_price'])
24 
25 Probability = collections.namedtuple('Probability', ['gas_price', 'prob'])
26 
27 
28 def _get_avg_block_time(w3, sample_size):
29     latest = w3.eth.getBlock('latest')
30 
31     constrained_sample_size = min(sample_size, latest['number'])
32     if constrained_sample_size == 0:
33         raise ValidationError('Constrained sample size is 0')
34 
35     oldest = w3.eth.getBlock(latest['number'] - constrained_sample_size)
36     return (latest['timestamp'] - oldest['timestamp']) / constrained_sample_size
37 
38 
39 def _get_raw_miner_data(w3, sample_size):
40     latest = w3.eth.getBlock('latest', full_transactions=True)
41 
42     for transaction in latest['transactions']:
43         yield (latest['miner'], latest['hash'], transaction['gasPrice'])
44 
45     block = latest
46 
47     for _ in range(sample_size - 1):
48         if block['number'] == 0:
49             break
50 
51         # we intentionally trace backwards using parent hashes rather than
52         # block numbers to make caching the data easier to implement.
53         block = w3.eth.getBlock(block['parentHash'], full_transactions=True)
54         for transaction in block['transactions']:
55             yield (block['miner'], block['hash'], transaction['gasPrice'])
56 
57 
58 def _aggregate_miner_data(raw_data):
59     data_by_miner = groupby(0, raw_data)
60 
61     for miner, miner_data in data_by_miner.items():
62         _, block_hashes, gas_prices = map(set, zip(*miner_data))
63         yield MinerData(
64             miner,
65             len(set(block_hashes)),
66             min(gas_prices),
67             percentile(gas_prices, percentile=15))
68 
69 
70 @to_tuple
71 def _compute_probabilities(miner_data, wait_blocks, sample_size):
72     """
73     Computes the probabilities that a txn will be accepted at each of the gas
74     prices accepted by the miners.
75     """
76     miner_data_by_price = tuple(sorted(
77         miner_data,
78         key=operator.attrgetter('low_percentile_gas_price'),
79         reverse=True,
80     ))
81     for idx in range(len(miner_data_by_price)):
82         low_percentile_gas_price = miner_data_by_price[idx].low_percentile_gas_price
83         num_blocks_accepting_price = sum(m.num_blocks for m in miner_data_by_price[idx:])
84         inv_prob_per_block = (sample_size - num_blocks_accepting_price) / sample_size
85         probability_accepted = 1 - inv_prob_per_block ** wait_blocks
86         yield Probability(low_percentile_gas_price, probability_accepted)
87 
88 
89 def _compute_gas_price(probabilities, desired_probability):
90     """
91     Given a sorted range of ``Probability`` named-tuples returns a gas price
92     computed based on where the ``desired_probability`` would fall within the
93     range.
94 
95     :param probabilities: An iterable of `Probability` named-tuples sorted in reverse order.
96     :param desired_probability: An floating point representation of the desired
97         probability. (e.g. ``85% -> 0.85``)
98     """
99     first = probabilities[0]
100     last = probabilities[-1]
101 
102     if desired_probability >= first.prob:
103         return first.gas_price
104     elif desired_probability <= last.prob:
105         return last.gas_price
106 
107     for left, right in sliding_window(2, probabilities):
108         if desired_probability < right.prob:
109             continue
110         elif desired_probability > left.prob:
111             # This code block should never be reachable as it would indicate
112             # that we already passed by the probability window in which our
113             # `desired_probability` is located.
114             raise Exception('Invariant')
115 
116         adj_prob = desired_probability - right.prob
117         window_size = left.prob - right.prob
118         position = adj_prob / window_size
119         gas_window_size = left.gas_price - right.gas_price
120         gas_price = int(math.ceil(right.gas_price + gas_window_size * position))
121         return gas_price
122     else:
123         # The initial `if/else` clause in this function handles the case where
124         # the `desired_probability` is either above or below the min/max
125         # probability found in the `probabilities`.
126         #
127         # With these two cases handled, the only way this code block should be
128         # reachable would be if the `probabilities` were not sorted correctly.
129         # Otherwise, the `desired_probability` **must** fall between two of the
130         # values in the `probabilities``.
131         raise Exception('Invariant')
132 
133 
134 @curry
135 def construct_time_based_gas_price_strategy(max_wait_seconds,
136                                             sample_size=120,
137                                             probability=98):
138     """
139     A gas pricing strategy that uses recently mined block data to derive a gas
140     price for which a transaction is likely to be mined within X seconds with
141     probability P.
142 
143     :param max_wait_seconds: The desired maxiumum number of seconds the
144         transaction should take to mine.
145     :param sample_size: The number of recent blocks to sample
146     :param probability: An integer representation of the desired probability
147         that the transaction will be mined within ``max_wait_seconds``.  0 means 0%
148         and 100 means 100%.
149     """
150     def time_based_gas_price_strategy(web3, transaction_params):
151         avg_block_time = _get_avg_block_time(web3, sample_size=sample_size)
152         wait_blocks = int(math.ceil(max_wait_seconds / avg_block_time))
153 
154         raw_miner_data = _get_raw_miner_data(web3, sample_size=sample_size)
155         miner_data = _aggregate_miner_data(raw_miner_data)
156 
157         probabilities = _compute_probabilities(
158             miner_data,
159             wait_blocks=wait_blocks,
160             sample_size=sample_size,
161         )
162 
163         gas_price = _compute_gas_price(probabilities, probability / 100)
164         return gas_price
165     return time_based_gas_price_strategy
166 
167 
168 # fast: mine within 1 minute
169 fast_gas_price_strategy = construct_time_based_gas_price_strategy(
170     max_wait_seconds=60,
171     sample_size=120,
172 )
173 # medium: mine within 10 minutes
174 medium_gas_price_strategy = construct_time_based_gas_price_strategy(
175     max_wait_seconds=600,
176     sample_size=120,
177 )
178 # slow: mine within 1 hour (60 minutes)
179 slow_gas_price_strategy = construct_time_based_gas_price_strategy(
180     max_wait_seconds=60 * 60,
181     sample_size=120,
182 )
183 # glacial: mine within the next 24 hours.
184 glacial_gas_price_strategy = construct_time_based_gas_price_strategy(
185     max_wait_seconds=24 * 60 * 60,
186     sample_size=720,
187 )
188
```

Path: `web3/utils/math.py`
Content:
```
1 def percentile(values=None, percentile=None):
2     """Calculates a simplified weighted average percentile
3     """
4     if values in [None, tuple(), []] or len(values) < 3:
5         raise ValueError("Expected a sequence of at least 3 integers, got {0}".format(values))
6     if percentile is None:
7         raise ValueError("Expected a percentile choice, got {0}".format(percentile))
8 
9     sorted_values = sorted(values)
10 
11     rank = len(values) * percentile / 100
12     if rank > 0:
13         index = rank - 1
14     else:
15         index = rank
16 
17     if index % 1 == 0:
18         return sorted_values[int(index)]
19     else:
20         fractional = index % 1
21         integer = int(index - fractional)
22         lower = sorted_values[integer]
23         higher = sorted_values[integer + 1]
24         return lower + fractional * (higher - lower)
25
```

Path: `web3/exceptions.py`
Content:
```
1 import datetime
2 import time
3 
4 
5 class BadFunctionCallOutput(Exception):
6     """
7     We failed to decode ABI output.
8 
9     Most likely ABI mismatch.
10     """
11     pass
12 
13 
14 class BlockNumberOutofRange(Exception):
15     '''
16     block_identifier passed does not match known block.
17     '''
18     pass
19 
20 
21 class CannotHandleRequest(Exception):
22     """
23     Raised by a provider to signal that it cannot handle an RPC request and
24     that the manager should proceed to the next provider.
25     """
26     pass
27 
28 
29 class InvalidAddress(ValueError):
30     """
31     The supplied address does not have a valid checksum, as defined in EIP-55
32     """
33     pass
34 
35 
36 class NameNotFound(ValueError):
37     """
38     Raised when a caller provides an Ethereum Name Service name that
39     does not resolve to an address.
40     """
41     pass
42 
43 
44 class StaleBlockchain(Exception):
45     """
46     Raised by the stalecheck_middleware when the latest block is too old.
47     """
48     def __init__(self, block, allowable_delay):
49         last_block_date = datetime.datetime.fromtimestamp(block.timestamp).strftime('%c')
50         message = (
51             "The latest block, #%d, is %d seconds old, but is only allowed to be %d s old. "
52             "The date of the most recent block is %s. Continue syncing and try again..." %
53             (block.number, time.time() - block.timestamp, allowable_delay, last_block_date)
54         )
55         super().__init__(message, block, allowable_delay)
56 
57     def __str__(self):
58         return self.args[0]
59 
60 
61 class UnhandledRequest(Exception):
62     """
63     Raised by the manager when none of it's providers responds to a request.
64     """
65     pass
66 
67 
68 class MismatchedABI(Exception):
69     """
70     Raised when an ABI does not match with supplied parameters, or when an
71     attempt is made to access a function/event that does not exist in the ABI.
72     """
73     pass
74 
75 
76 class FallbackNotFound(Exception):
77     """
78     Raised when fallback function doesn't exist in contract.
79     """
80     pass
81 
82 
83 class ValidationError(Exception):
84     """
85     Raised when a supplied value is invalid.
86     """
87     pass
88 
89 
90 class NoABIFunctionsFound(AttributeError):
91     """
92     Raised when an ABI doesn't contain any functions.
93     """
94     pass
95 
96 
97 class NoABIEventsFound(AttributeError):
98     """
99     Raised when an ABI doesn't contain any events.
100     """
101     pass
102
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/web3/exceptions.py b/web3/exceptions.py
--- a/web3/exceptions.py
+++ b/web3/exceptions.py
@@ -99,3 +99,11 @@
     Raised when an ABI doesn't contain any events.
     """
     pass
+
+
+class InsufficientData(Exception):
+    """
+    Raised when there are insufficient data points to
+    complete a calculation
+    """
+    pass
diff --git a/web3/gas_strategies/time_based.py b/web3/gas_strategies/time_based.py
--- a/web3/gas_strategies/time_based.py
+++ b/web3/gas_strategies/time_based.py
@@ -7,6 +7,7 @@
 )
 
 from web3.exceptions import (
+    InsufficientData,
     ValidationError,
 )
 from web3.utils.math import (
@@ -60,11 +61,15 @@
 
     for miner, miner_data in data_by_miner.items():
         _, block_hashes, gas_prices = map(set, zip(*miner_data))
+        try:
+            price_percentile = percentile(gas_prices, percentile=20)
+        except InsufficientData:
+            price_percentile = min(gas_prices)
         yield MinerData(
             miner,
             len(set(block_hashes)),
             min(gas_prices),
-            percentile(gas_prices, percentile=15))
+            price_percentile)
 
 
 @to_tuple
diff --git a/web3/utils/math.py b/web3/utils/math.py
--- a/web3/utils/math.py
+++ b/web3/utils/math.py
@@ -1,8 +1,14 @@
+from web3.exceptions import (
+    InsufficientData,
+)
+
+
 def percentile(values=None, percentile=None):
     """Calculates a simplified weighted average percentile
     """
-    if values in [None, tuple(), []] or len(values) < 3:
-        raise ValueError("Expected a sequence of at least 3 integers, got {0}".format(values))
+    if values in [None, tuple(), []] or len(values) < 1:
+        raise InsufficientData(
+            "Expected a sequence of at least 1 integers, got {0!r}".format(values))
     if percentile is None:
         raise ValueError("Expected a percentile choice, got {0}".format(percentile))
 
@@ -11,6 +17,8 @@
     rank = len(values) * percentile / 100
     if rank > 0:
         index = rank - 1
+        if index < 0:
+            return sorted_values[0]
     else:
         index = rank

{"golden_diff": "diff --git a/web3/exceptions.py b/web3/exceptions.py\n--- a/web3/exceptions.py\n+++ b/web3/exceptions.py\n@@ -99,3 +99,11 @@\n     Raised when an ABI doesn't contain any events.\n     \"\"\"\n     pass\n+\n+\n+class InsufficientData(Exception):\n+    \"\"\"\n+    Raised when there are insufficient data points to\n+    complete a calculation\n+    \"\"\"\n+    pass\ndiff --git a/web3/gas_strategies/time_based.py b/web3/gas_strategies/time_based.py\n--- a/web3/gas_strategies/time_based.py\n+++ b/web3/gas_strategies/time_based.py\n@@ -7,6 +7,7 @@\n )\n \n from web3.exceptions import (\n+    InsufficientData,\n     ValidationError,\n )\n from web3.utils.math import (\n@@ -60,11 +61,15 @@\n \n     for miner, miner_data in data_by_miner.items():\n         _, block_hashes, gas_prices = map(set, zip(*miner_data))\n+        try:\n+            price_percentile = percentile(gas_prices, percentile=20)\n+        except InsufficientData:\n+            price_percentile = min(gas_prices)\n         yield MinerData(\n             miner,\n             len(set(block_hashes)),\n             min(gas_prices),\n-            percentile(gas_prices, percentile=15))\n+            price_percentile)\n \n \n @to_tuple\ndiff --git a/web3/utils/math.py b/web3/utils/math.py\n--- a/web3/utils/math.py\n+++ b/web3/utils/math.py\n@@ -1,8 +1,14 @@\n+from web3.exceptions import (\n+    InsufficientData,\n+)\n+\n+\n def percentile(values=None, percentile=None):\n     \"\"\"Calculates a simplified weighted average percentile\n     \"\"\"\n-    if values in [None, tuple(), []] or len(values) < 3:\n-        raise ValueError(\"Expected a sequence of at least 3 integers, got {0}\".format(values))\n+    if values in [None, tuple(), []] or len(values) < 1:\n+        raise InsufficientData(\n+            \"Expected a sequence of at least 1 integers, got {0!r}\".format(values))\n     if percentile is None:\n         raise ValueError(\"Expected a percentile choice, got {0}\".format(percentile))\n \n@@ -11,6 +17,8 @@\n     rank = len(values) * percentile / 100\n     if rank > 0:\n         index = rank - 1\n+        if index < 0:\n+            return sorted_values[0]\n     else:\n         index = rank\n", "issue": "Crash in time based gas price strategies\n* Version: 4.5.0\r\n* Python: 3.6\r\n* OS: osx\r\n\r\n\r\n### What was wrong?\r\n\r\nMy script to check the gas price calculation crashes after the update to web3 4.5:\r\n```\r\npython test_gas_price.py                                                                     0:13:21\r\nRPC: 252000000\r\nTraceback (most recent call last):\r\n  File \"test_gas_price.py\", line 14, in <module>\r\n    print('Slow', w3.eth.generateGasPrice())\r\n  File \"/Users/paul/Work/venv-raiden/lib/python3.6/site-packages/web3/eth.py\", line 385, in generateGasPrice\r\n    return self.gasPriceStrategy(self.web3, transaction_params)\r\n  File \"/Users/paul/Work/venv-raiden/lib/python3.6/site-packages/web3/gas_strategies/time_based.py\", line 160, in time_based_gas_price_strategy\r\n    sample_size=sample_size,\r\n  File \"/Users/paul/Work/venv-raiden/lib/python3.6/site-packages/eth_utils/functional.py\", line 22, in inner\r\n    return callback(fn(*args, **kwargs))\r\n  File \"/Users/paul/Work/venv-raiden/lib/python3.6/site-packages/web3/gas_strategies/time_based.py\", line 79, in _compute_probabilities\r\n    reverse=True,\r\n  File \"/Users/paul/Work/venv-raiden/lib/python3.6/site-packages/web3/gas_strategies/time_based.py\", line 67, in _aggregate_miner_data\r\n    percentile(gas_prices, percentile=15))\r\n  File \"/Users/paul/Work/venv-raiden/lib/python3.6/site-packages/web3/utils/math.py\", line 5, in percentile\r\n    raise ValueError(\"Expected a sequence of at least 3 integers, got {0}\".format(values))\r\nValueError: Expected a sequence of at least 3 integers, got {41000000000, 26000000000}\r\n```\r\n\r\nThe code is the following:\r\n```py\r\nfrom web3.auto import w3\r\n\r\nfrom web3 import middleware\r\nfrom web3.gas_strategies.time_based import medium_gas_price_strategy, fast_gas_price_strategy, slow_gas_price_strategy\r\nfrom web3.gas_strategies.rpc import rpc_gas_price_strategy\r\n\r\nw3.middleware_stack.add(middleware.time_based_cache_middleware)\r\nw3.middleware_stack.add(middleware.latest_block_based_cache_middleware)\r\nw3.middleware_stack.add(middleware.simple_cache_middleware)\r\n\r\nw3.eth.setGasPriceStrategy(rpc_gas_price_strategy)\r\nprint('RPC:', w3.eth.generateGasPrice())\r\nw3.eth.setGasPriceStrategy(slow_gas_price_strategy)\r\nprint('Slow', w3.eth.generateGasPrice())\r\nw3.eth.setGasPriceStrategy(medium_gas_price_strategy)\r\nprint('Medium:', w3.eth.generateGasPrice())\r\nw3.eth.setGasPriceStrategy(fast_gas_price_strategy)\r\nprint('Fast:', w3.eth.generateGasPrice())\r\n```\r\n\r\n\r\n### How can it be fixed?\r\n\r\nIt should crash and return a proper gas price.\r\n\n", "before_files": [{"content": "import collections\nimport math\nimport operator\n\nfrom eth_utils import (\n    to_tuple,\n)\n\nfrom web3.exceptions import (\n    ValidationError,\n)\nfrom web3.utils.math import (\n    percentile,\n)\nfrom web3.utils.toolz import (\n    curry,\n    groupby,\n    sliding_window,\n)\n\nMinerData = collections.namedtuple(\n    'MinerData',\n    ['miner', 'num_blocks', 'min_gas_price', 'low_percentile_gas_price'])\n\nProbability = collections.namedtuple('Probability', ['gas_price', 'prob'])\n\n\ndef _get_avg_block_time(w3, sample_size):\n    latest = w3.eth.getBlock('latest')\n\n    constrained_sample_size = min(sample_size, latest['number'])\n    if constrained_sample_size == 0:\n        raise ValidationError('Constrained sample size is 0')\n\n    oldest = w3.eth.getBlock(latest['number'] - constrained_sample_size)\n    return (latest['timestamp'] - oldest['timestamp']) / constrained_sample_size\n\n\ndef _get_raw_miner_data(w3, sample_size):\n    latest = w3.eth.getBlock('latest', full_transactions=True)\n\n    for transaction in latest['transactions']:\n        yield (latest['miner'], latest['hash'], transaction['gasPrice'])\n\n    block = latest\n\n    for _ in range(sample_size - 1):\n        if block['number'] == 0:\n            break\n\n        # we intentionally trace backwards using parent hashes rather than\n        # block numbers to make caching the data easier to implement.\n        block = w3.eth.getBlock(block['parentHash'], full_transactions=True)\n        for transaction in block['transactions']:\n            yield (block['miner'], block['hash'], transaction['gasPrice'])\n\n\ndef _aggregate_miner_data(raw_data):\n    data_by_miner = groupby(0, raw_data)\n\n    for miner, miner_data in data_by_miner.items():\n        _, block_hashes, gas_prices = map(set, zip(*miner_data))\n        yield MinerData(\n            miner,\n            len(set(block_hashes)),\n            min(gas_prices),\n            percentile(gas_prices, percentile=15))\n\n\n@to_tuple\ndef _compute_probabilities(miner_data, wait_blocks, sample_size):\n    \"\"\"\n    Computes the probabilities that a txn will be accepted at each of the gas\n    prices accepted by the miners.\n    \"\"\"\n    miner_data_by_price = tuple(sorted(\n        miner_data,\n        key=operator.attrgetter('low_percentile_gas_price'),\n        reverse=True,\n    ))\n    for idx in range(len(miner_data_by_price)):\n        low_percentile_gas_price = miner_data_by_price[idx].low_percentile_gas_price\n        num_blocks_accepting_price = sum(m.num_blocks for m in miner_data_by_price[idx:])\n        inv_prob_per_block = (sample_size - num_blocks_accepting_price) / sample_size\n        probability_accepted = 1 - inv_prob_per_block ** wait_blocks\n        yield Probability(low_percentile_gas_price, probability_accepted)\n\n\ndef _compute_gas_price(probabilities, desired_probability):\n    \"\"\"\n    Given a sorted range of ``Probability`` named-tuples returns a gas price\n    computed based on where the ``desired_probability`` would fall within the\n    range.\n\n    :param probabilities: An iterable of `Probability` named-tuples sorted in reverse order.\n    :param desired_probability: An floating point representation of the desired\n        probability. (e.g. ``85% -> 0.85``)\n    \"\"\"\n    first = probabilities[0]\n    last = probabilities[-1]\n\n    if desired_probability >= first.prob:\n        return first.gas_price\n    elif desired_probability <= last.prob:\n        return last.gas_price\n\n    for left, right in sliding_window(2, probabilities):\n        if desired_probability < right.prob:\n            continue\n        elif desired_probability > left.prob:\n            # This code block should never be reachable as it would indicate\n            # that we already passed by the probability window in which our\n            # `desired_probability` is located.\n            raise Exception('Invariant')\n\n        adj_prob = desired_probability - right.prob\n        window_size = left.prob - right.prob\n        position = adj_prob / window_size\n        gas_window_size = left.gas_price - right.gas_price\n        gas_price = int(math.ceil(right.gas_price + gas_window_size * position))\n        return gas_price\n    else:\n        # The initial `if/else` clause in this function handles the case where\n        # the `desired_probability` is either above or below the min/max\n        # probability found in the `probabilities`.\n        #\n        # With these two cases handled, the only way this code block should be\n        # reachable would be if the `probabilities` were not sorted correctly.\n        # Otherwise, the `desired_probability` **must** fall between two of the\n        # values in the `probabilities``.\n        raise Exception('Invariant')\n\n\n@curry\ndef construct_time_based_gas_price_strategy(max_wait_seconds,\n                                            sample_size=120,\n                                            probability=98):\n    \"\"\"\n    A gas pricing strategy that uses recently mined block data to derive a gas\n    price for which a transaction is likely to be mined within X seconds with\n    probability P.\n\n    :param max_wait_seconds: The desired maxiumum number of seconds the\n        transaction should take to mine.\n    :param sample_size: The number of recent blocks to sample\n    :param probability: An integer representation of the desired probability\n        that the transaction will be mined within ``max_wait_seconds``.  0 means 0%\n        and 100 means 100%.\n    \"\"\"\n    def time_based_gas_price_strategy(web3, transaction_params):\n        avg_block_time = _get_avg_block_time(web3, sample_size=sample_size)\n        wait_blocks = int(math.ceil(max_wait_seconds / avg_block_time))\n\n        raw_miner_data = _get_raw_miner_data(web3, sample_size=sample_size)\n        miner_data = _aggregate_miner_data(raw_miner_data)\n\n        probabilities = _compute_probabilities(\n            miner_data,\n            wait_blocks=wait_blocks,\n            sample_size=sample_size,\n        )\n\n        gas_price = _compute_gas_price(probabilities, probability / 100)\n        return gas_price\n    return time_based_gas_price_strategy\n\n\n# fast: mine within 1 minute\nfast_gas_price_strategy = construct_time_based_gas_price_strategy(\n    max_wait_seconds=60,\n    sample_size=120,\n)\n# medium: mine within 10 minutes\nmedium_gas_price_strategy = construct_time_based_gas_price_strategy(\n    max_wait_seconds=600,\n    sample_size=120,\n)\n# slow: mine within 1 hour (60 minutes)\nslow_gas_price_strategy = construct_time_based_gas_price_strategy(\n    max_wait_seconds=60 * 60,\n    sample_size=120,\n)\n# glacial: mine within the next 24 hours.\nglacial_gas_price_strategy = construct_time_based_gas_price_strategy(\n    max_wait_seconds=24 * 60 * 60,\n    sample_size=720,\n)\n", "path": "web3/gas_strategies/time_based.py"}, {"content": "def percentile(values=None, percentile=None):\n    \"\"\"Calculates a simplified weighted average percentile\n    \"\"\"\n    if values in [None, tuple(), []] or len(values) < 3:\n        raise ValueError(\"Expected a sequence of at least 3 integers, got {0}\".format(values))\n    if percentile is None:\n        raise ValueError(\"Expected a percentile choice, got {0}\".format(percentile))\n\n    sorted_values = sorted(values)\n\n    rank = len(values) * percentile / 100\n    if rank > 0:\n        index = rank - 1\n    else:\n        index = rank\n\n    if index % 1 == 0:\n        return sorted_values[int(index)]\n    else:\n        fractional = index % 1\n        integer = int(index - fractional)\n        lower = sorted_values[integer]\n        higher = sorted_values[integer + 1]\n        return lower + fractional * (higher - lower)\n", "path": "web3/utils/math.py"}, {"content": "import datetime\nimport time\n\n\nclass BadFunctionCallOutput(Exception):\n    \"\"\"\n    We failed to decode ABI output.\n\n    Most likely ABI mismatch.\n    \"\"\"\n    pass\n\n\nclass BlockNumberOutofRange(Exception):\n    '''\n    block_identifier passed does not match known block.\n    '''\n    pass\n\n\nclass CannotHandleRequest(Exception):\n    \"\"\"\n    Raised by a provider to signal that it cannot handle an RPC request and\n    that the manager should proceed to the next provider.\n    \"\"\"\n    pass\n\n\nclass InvalidAddress(ValueError):\n    \"\"\"\n    The supplied address does not have a valid checksum, as defined in EIP-55\n    \"\"\"\n    pass\n\n\nclass NameNotFound(ValueError):\n    \"\"\"\n    Raised when a caller provides an Ethereum Name Service name that\n    does not resolve to an address.\n    \"\"\"\n    pass\n\n\nclass StaleBlockchain(Exception):\n    \"\"\"\n    Raised by the stalecheck_middleware when the latest block is too old.\n    \"\"\"\n    def __init__(self, block, allowable_delay):\n        last_block_date = datetime.datetime.fromtimestamp(block.timestamp).strftime('%c')\n        message = (\n            \"The latest block, #%d, is %d seconds old, but is only allowed to be %d s old. \"\n            \"The date of the most recent block is %s. Continue syncing and try again...\" %\n            (block.number, time.time() - block.timestamp, allowable_delay, last_block_date)\n        )\n        super().__init__(message, block, allowable_delay)\n\n    def __str__(self):\n        return self.args[0]\n\n\nclass UnhandledRequest(Exception):\n    \"\"\"\n    Raised by the manager when none of it's providers responds to a request.\n    \"\"\"\n    pass\n\n\nclass MismatchedABI(Exception):\n    \"\"\"\n    Raised when an ABI does not match with supplied parameters, or when an\n    attempt is made to access a function/event that does not exist in the ABI.\n    \"\"\"\n    pass\n\n\nclass FallbackNotFound(Exception):\n    \"\"\"\n    Raised when fallback function doesn't exist in contract.\n    \"\"\"\n    pass\n\n\nclass ValidationError(Exception):\n    \"\"\"\n    Raised when a supplied value is invalid.\n    \"\"\"\n    pass\n\n\nclass NoABIFunctionsFound(AttributeError):\n    \"\"\"\n    Raised when an ABI doesn't contain any functions.\n    \"\"\"\n    pass\n\n\nclass NoABIEventsFound(AttributeError):\n    \"\"\"\n    Raised when an ABI doesn't contain any events.\n    \"\"\"\n    pass\n", "path": "web3/exceptions.py"}], "after_files": [{"content": "import collections\nimport math\nimport operator\n\nfrom eth_utils import (\n    to_tuple,\n)\n\nfrom web3.exceptions import (\n    InsufficientData,\n    ValidationError,\n)\nfrom web3.utils.math import (\n    percentile,\n)\nfrom web3.utils.toolz import (\n    curry,\n    groupby,\n    sliding_window,\n)\n\nMinerData = collections.namedtuple(\n    'MinerData',\n    ['miner', 'num_blocks', 'min_gas_price', 'low_percentile_gas_price'])\n\nProbability = collections.namedtuple('Probability', ['gas_price', 'prob'])\n\n\ndef _get_avg_block_time(w3, sample_size):\n    latest = w3.eth.getBlock('latest')\n\n    constrained_sample_size = min(sample_size, latest['number'])\n    if constrained_sample_size == 0:\n        raise ValidationError('Constrained sample size is 0')\n\n    oldest = w3.eth.getBlock(latest['number'] - constrained_sample_size)\n    return (latest['timestamp'] - oldest['timestamp']) / constrained_sample_size\n\n\ndef _get_raw_miner_data(w3, sample_size):\n    latest = w3.eth.getBlock('latest', full_transactions=True)\n\n    for transaction in latest['transactions']:\n        yield (latest['miner'], latest['hash'], transaction['gasPrice'])\n\n    block = latest\n\n    for _ in range(sample_size - 1):\n        if block['number'] == 0:\n            break\n\n        # we intentionally trace backwards using parent hashes rather than\n        # block numbers to make caching the data easier to implement.\n        block = w3.eth.getBlock(block['parentHash'], full_transactions=True)\n        for transaction in block['transactions']:\n            yield (block['miner'], block['hash'], transaction['gasPrice'])\n\n\ndef _aggregate_miner_data(raw_data):\n    data_by_miner = groupby(0, raw_data)\n\n    for miner, miner_data in data_by_miner.items():\n        _, block_hashes, gas_prices = map(set, zip(*miner_data))\n        try:\n            price_percentile = percentile(gas_prices, percentile=20)\n        except InsufficientData:\n            price_percentile = min(gas_prices)\n        yield MinerData(\n            miner,\n            len(set(block_hashes)),\n            min(gas_prices),\n            price_percentile)\n\n\n@to_tuple\ndef _compute_probabilities(miner_data, wait_blocks, sample_size):\n    \"\"\"\n    Computes the probabilities that a txn will be accepted at each of the gas\n    prices accepted by the miners.\n    \"\"\"\n    miner_data_by_price = tuple(sorted(\n        miner_data,\n        key=operator.attrgetter('low_percentile_gas_price'),\n        reverse=True,\n    ))\n    for idx in range(len(miner_data_by_price)):\n        low_percentile_gas_price = miner_data_by_price[idx].low_percentile_gas_price\n        num_blocks_accepting_price = sum(m.num_blocks for m in miner_data_by_price[idx:])\n        inv_prob_per_block = (sample_size - num_blocks_accepting_price) / sample_size\n        probability_accepted = 1 - inv_prob_per_block ** wait_blocks\n        yield Probability(low_percentile_gas_price, probability_accepted)\n\n\ndef _compute_gas_price(probabilities, desired_probability):\n    \"\"\"\n    Given a sorted range of ``Probability`` named-tuples returns a gas price\n    computed based on where the ``desired_probability`` would fall within the\n    range.\n\n    :param probabilities: An iterable of `Probability` named-tuples sorted in reverse order.\n    :param desired_probability: An floating point representation of the desired\n        probability. (e.g. ``85% -> 0.85``)\n    \"\"\"\n    first = probabilities[0]\n    last = probabilities[-1]\n\n    if desired_probability >= first.prob:\n        return first.gas_price\n    elif desired_probability <= last.prob:\n        return last.gas_price\n\n    for left, right in sliding_window(2, probabilities):\n        if desired_probability < right.prob:\n            continue\n        elif desired_probability > left.prob:\n            # This code block should never be reachable as it would indicate\n            # that we already passed by the probability window in which our\n            # `desired_probability` is located.\n            raise Exception('Invariant')\n\n        adj_prob = desired_probability - right.prob\n        window_size = left.prob - right.prob\n        position = adj_prob / window_size\n        gas_window_size = left.gas_price - right.gas_price\n        gas_price = int(math.ceil(right.gas_price + gas_window_size * position))\n        return gas_price\n    else:\n        # The initial `if/else` clause in this function handles the case where\n        # the `desired_probability` is either above or below the min/max\n        # probability found in the `probabilities`.\n        #\n        # With these two cases handled, the only way this code block should be\n        # reachable would be if the `probabilities` were not sorted correctly.\n        # Otherwise, the `desired_probability` **must** fall between two of the\n        # values in the `probabilities``.\n        raise Exception('Invariant')\n\n\n@curry\ndef construct_time_based_gas_price_strategy(max_wait_seconds,\n                                            sample_size=120,\n                                            probability=98):\n    \"\"\"\n    A gas pricing strategy that uses recently mined block data to derive a gas\n    price for which a transaction is likely to be mined within X seconds with\n    probability P.\n\n    :param max_wait_seconds: The desired maxiumum number of seconds the\n        transaction should take to mine.\n    :param sample_size: The number of recent blocks to sample\n    :param probability: An integer representation of the desired probability\n        that the transaction will be mined within ``max_wait_seconds``.  0 means 0%\n        and 100 means 100%.\n    \"\"\"\n    def time_based_gas_price_strategy(web3, transaction_params):\n        avg_block_time = _get_avg_block_time(web3, sample_size=sample_size)\n        wait_blocks = int(math.ceil(max_wait_seconds / avg_block_time))\n\n        raw_miner_data = _get_raw_miner_data(web3, sample_size=sample_size)\n        miner_data = _aggregate_miner_data(raw_miner_data)\n\n        probabilities = _compute_probabilities(\n            miner_data,\n            wait_blocks=wait_blocks,\n            sample_size=sample_size,\n        )\n\n        gas_price = _compute_gas_price(probabilities, probability / 100)\n        return gas_price\n    return time_based_gas_price_strategy\n\n\n# fast: mine within 1 minute\nfast_gas_price_strategy = construct_time_based_gas_price_strategy(\n    max_wait_seconds=60,\n    sample_size=120,\n)\n# medium: mine within 10 minutes\nmedium_gas_price_strategy = construct_time_based_gas_price_strategy(\n    max_wait_seconds=600,\n    sample_size=120,\n)\n# slow: mine within 1 hour (60 minutes)\nslow_gas_price_strategy = construct_time_based_gas_price_strategy(\n    max_wait_seconds=60 * 60,\n    sample_size=120,\n)\n# glacial: mine within the next 24 hours.\nglacial_gas_price_strategy = construct_time_based_gas_price_strategy(\n    max_wait_seconds=24 * 60 * 60,\n    sample_size=720,\n)\n", "path": "web3/gas_strategies/time_based.py"}, {"content": "from web3.exceptions import (\n    InsufficientData,\n)\n\n\ndef percentile(values=None, percentile=None):\n    \"\"\"Calculates a simplified weighted average percentile\n    \"\"\"\n    if values in [None, tuple(), []] or len(values) < 1:\n        raise InsufficientData(\n            \"Expected a sequence of at least 1 integers, got {0!r}\".format(values))\n    if percentile is None:\n        raise ValueError(\"Expected a percentile choice, got {0}\".format(percentile))\n\n    sorted_values = sorted(values)\n\n    rank = len(values) * percentile / 100\n    if rank > 0:\n        index = rank - 1\n        if index < 0:\n            return sorted_values[0]\n    else:\n        index = rank\n\n    if index % 1 == 0:\n        return sorted_values[int(index)]\n    else:\n        fractional = index % 1\n        integer = int(index - fractional)\n        lower = sorted_values[integer]\n        higher = sorted_values[integer + 1]\n        return lower + fractional * (higher - lower)\n", "path": "web3/utils/math.py"}, {"content": "import datetime\nimport time\n\n\nclass BadFunctionCallOutput(Exception):\n    \"\"\"\n    We failed to decode ABI output.\n\n    Most likely ABI mismatch.\n    \"\"\"\n    pass\n\n\nclass BlockNumberOutofRange(Exception):\n    '''\n    block_identifier passed does not match known block.\n    '''\n    pass\n\n\nclass CannotHandleRequest(Exception):\n    \"\"\"\n    Raised by a provider to signal that it cannot handle an RPC request and\n    that the manager should proceed to the next provider.\n    \"\"\"\n    pass\n\n\nclass InvalidAddress(ValueError):\n    \"\"\"\n    The supplied address does not have a valid checksum, as defined in EIP-55\n    \"\"\"\n    pass\n\n\nclass NameNotFound(ValueError):\n    \"\"\"\n    Raised when a caller provides an Ethereum Name Service name that\n    does not resolve to an address.\n    \"\"\"\n    pass\n\n\nclass StaleBlockchain(Exception):\n    \"\"\"\n    Raised by the stalecheck_middleware when the latest block is too old.\n    \"\"\"\n    def __init__(self, block, allowable_delay):\n        last_block_date = datetime.datetime.fromtimestamp(block.timestamp).strftime('%c')\n        message = (\n            \"The latest block, #%d, is %d seconds old, but is only allowed to be %d s old. \"\n            \"The date of the most recent block is %s. Continue syncing and try again...\" %\n            (block.number, time.time() - block.timestamp, allowable_delay, last_block_date)\n        )\n        super().__init__(message, block, allowable_delay)\n\n    def __str__(self):\n        return self.args[0]\n\n\nclass UnhandledRequest(Exception):\n    \"\"\"\n    Raised by the manager when none of it's providers responds to a request.\n    \"\"\"\n    pass\n\n\nclass MismatchedABI(Exception):\n    \"\"\"\n    Raised when an ABI does not match with supplied parameters, or when an\n    attempt is made to access a function/event that does not exist in the ABI.\n    \"\"\"\n    pass\n\n\nclass FallbackNotFound(Exception):\n    \"\"\"\n    Raised when fallback function doesn't exist in contract.\n    \"\"\"\n    pass\n\n\nclass ValidationError(Exception):\n    \"\"\"\n    Raised when a supplied value is invalid.\n    \"\"\"\n    pass\n\n\nclass NoABIFunctionsFound(AttributeError):\n    \"\"\"\n    Raised when an ABI doesn't contain any functions.\n    \"\"\"\n    pass\n\n\nclass NoABIEventsFound(AttributeError):\n    \"\"\"\n    Raised when an ABI doesn't contain any events.\n    \"\"\"\n    pass\n\n\nclass InsufficientData(Exception):\n    \"\"\"\n    Raised when there are insufficient data points to\n    complete a calculation\n    \"\"\"\n    pass\n", "path": "web3/exceptions.py"}]}