A practical proposal for Multidimensional Gas Metering

Execution Layer Research
14

Maybe a sensible way to deal with storage costs is to assume Moore’s law, i.e. something like “the cost of storing a word halves every 2 years”. That results in a geometric series with base \frac12, which converges to 2 when the number of iterations diverges to +\infty (see proof below).

Based on that, the cost of storing a word forever is the cost of storing it for 2 years multiplied by 2. That’s easy to estimate because you can take the cost of a disk with a certain capacity on GCP or AWS for a year, multiply it by 4, and divide it by the number of words that fit in that capacity.

Bonus point: double the cost further to account for Merkle hashes (see the rationale at the bottom).

Generic geometric series:

\begin{aligned} S_n &= \sum_{i = 0}^n{\alpha^i} \\ S_{n + 1} &= S_n + \alpha^{n + 1} \\ S_{n + 1} &= 1 + \alpha \cdot S_n \end{aligned}
\begin{aligned} S_n + \alpha^{n + 1} &= 1 + \alpha \cdot S_n \\ S_n \cdot (1 - \alpha) &= 1 - \alpha^{n + 1} \\ S_n &= \frac{1 - \alpha^{n + 1}}{1 - \alpha} \end{aligned}

When n diverges and \alpha \in (0, 1):

\lim_{n \to +\infty} \frac{1 - \alpha^{n + 1}}{1 - \alpha} = \frac{1}{1 - \alpha}

With \alpha = \frac12 that becomes 2.

In order to account for the Merkle hashes: in this thread I explained why Ethereum’s MPTs tend to resemble a complete 16-ary tree when the number of leaves diverges.

The number of leaves of a complete 16-ary tree with height h is 16^h, while the total number of nodes is a geometric series with \alpha = 16 and n = h.

Let N be the number of leaves and M the total number of nodes:

\begin{aligned} N &= 16^h \\ M &= \sum_{i = 0}^h{16^i} = \frac{16^{h + 1} - 1}{15} \end{aligned}

Then each leaf (i.e. each stored value) contributes with \frac{M}{N} hashes:

\frac{M}{N} = \frac{16^{h + 1} - 1}{15} \cdot \frac{1}{16^h} = \frac{16^{h + 1} - 1}{16^h} \cdot \frac{1}{15}

When h \to +\infty:

\begin{aligned} & \lim_{h \to +\infty} \frac{16^{h + 1} - 1}{16^h} \cdot \frac{1}{15} = \\ =& \frac{1}{15} \cdot \lim_{h \to +\infty} 16 \cdot \frac{16^h - \frac{1}{16}}{16^h} = \\ =& \frac{1}{15} \cdot 16 \cdot 1 = \frac{16}{15} \end{aligned}

That is the average extra cost of the Merkle hashes of each leaf expressed in number of hashes, and it’s roughly equal to 1. Adding it to the cost of each stored word means roughly doubling the cost of the word itself.