How to price operations in smart contracts

Time-based pricing

Blocks are proposed (or mined) sequantially. The protocol enforces a round length

$T$ in which all the operations must be completed before the next block can be proposed. This includes the time required to execute the transactions, as well the time required to propagate the block. In that sense, we impose no distinction between a computational operation such as addition or multiplication, and the propagation of a payload bit to all validators: both require some allocation of the total round length

$T$.

Let

$X=\{X_1,X_2,\dots ,X_N\}\in {\mathbb{Z}}_{\ge 0}^N$ be the set of variables that count the number of each operation.

Each operation

$i$ has a constant price in gas

$P_i\in {\mathbb{Z}}_{\ge 0}$, and each block has a gas limit

$G\in {\mathbb{Z}}_{\ge 0}$.

Gas Inequality: The protocol dictates that given a block, all operations from included transactions are summed up, and the inequality

$$P_1{X}_1+P_2{X}_2+\cdots +P_N{X}_N\le G$$

must hold.

For all

$i$, let

$t_i:{\mathbb{Z}}_{\ge 0}\to {\mathbb{Z}}_{\ge 0}$ map each variable to the time required to "execute" it (or the time that needs to be allocated for it). We assume

$t_i$ to be monotonically increasing, bijective and

$t_i(0)=0$ for all

$i$.

Time inequality: Sum of the times consumed by each operation should be less than or equal to the round length, i.e.

$$t_1(X_1)+t_2(X_2)+\cdots +t_N(X_N)\le T$$

Goal: To assign a price

$P_i$ to each operation

$i$ using

$T$,

$t_i$ and

$G$. The prices need to be assigned in a way to ensure that given gas inequality holds, time inequality also holds. This way, each block can be created, propagated and finalized on time.

Linear relationship between operation count and execution time

We assume that, time is consumed linearly with each new operation, i.e.

$t_i(X_i)={\alpha }_i{X}_i$ for all

$i$. Then time inequality becomes

$${\alpha }_1{X}_1+{\alpha }_2{X}_2+\cdots +{\alpha }_N{X}_N\le T.$$

We consider the scenarios that for a given

$j$,

$X_i=0$ for all

$i\ne j$. In each scenario, time inequality is reduced to

${\alpha }_j{X}_j\le T$, which gives us

$$max(X_j)=\frac{T}{{\alpha }_j}$$

Moreover, gas inequality is reduced to

$P_j{X}_j\le G$. This gives us

$P_{j}max(X_j)=G$ which we substitute the previous result to obtain

$$\boxed{{\displaystyle P_j={\alpha }_j\frac{G}{T}}}$$

Theorem: When gas inequality holds and

$P_i={\alpha }_i\frac{G}{T}$ for all

$i$, time inequality also holds.

Proof: We substitute

$P_i$'s in gas inequality

$${\alpha }_1\frac{G}{T}{X}_1+{\alpha }_2\frac{G}{T}{X}_2+\cdots +{\alpha }_N\frac{G}{T}{X}_N\le G$$

which simplifies to time inequality. Thus, if gas inequality holds, time inequality also holds.

$◼$

Example: Let us have a set of only two operations, txdata, corresponding to a byte of transaction payload, and compute, corresponding to a basic instruction such as MUL. As such, txdata relates to bandwidth and compute relates to processing power. Each operation consumes a certain portion of the round length, either with propagation delay or local computation.

Let us assume that 1 txdata consumes

${\alpha }_0=$ 5e-4s and 1 compute

${\alpha }_1=$ 1e-7s. Let the round length be

$T=$ 15s and block gas limit be

$G=$ 10,000,000 gas. Then the gas prices should be set to

$P_0={\alpha }_{0}G/T\approx 333$ and

$P_1={\alpha }_{1}G/T\approx 0.0667$.

We proceed by introducing some on-chain measurements: a transaction has

${\overline{X}}_0=$ 200 txdata and

${\overline{X}}_1=$ 50,000 compute on average. Then we can estimate the average number of transactions

$n$ per block. Time inequality should be satisfied:

$${\alpha }_{0}n{\overline{X}}_0+{\alpha }_{1}n{\overline{X}}_1\le T$$

This gives us

$$max(n)=\frac{T}{{\alpha }_0{\overline{X}}_0+{\alpha }_1{\overline{X}}_1}\approx 142$$

transactions per block on average. The respective throughputs are calculated as

${\varphi }_{\ast }=max(n){\overline{X}}_{\ast }/T$, giving us

${\varphi }_0\approx$ 1904 txdata/s and

${\varphi }_1\approx$ 476910 compute/s. That means, between blocks

$max(n){\alpha }_0{\overline{X}}_0\approx$ 14.3s (95%) of round length is consumed bytxdata and

$max(n){\alpha }_1{\overline{X}}_1\approx$ 0.7s (5%) by compute.

Nonlinear relationship between operation count and execution time

We generalize the idea from the previous section to the nonlinear case: if

$t_i$ is positive, monotonically increasing and bijective for all

$i$, then the price for each operation

$i$ can be derived from the limiting case where

$t_i$'s slope is maximum. The idea is to replace

$t_i$ with a linear function with the maximum slope, and use that function to make a conservative estimate of the price.

To this end, we solve an optimization problem for each

$i$ in the range

$[0,t_i^{-1}(T)]$, i.e. from zero to the maximum value

$X_i$ can take according to time inequality:

$$X_i^{\ast }=\underset{0\le X_i\le t_i^{-1}(T)}{\text{argmax}}\frac{d{t}_i}{d{X}_i}$$

We then assume linear functions

${\overline{\alpha }}_i{X}_i$ where

$${\overline{\alpha }}_i=\frac{d{t}_i}{d{X}_i}{|}_{X_i^{\ast }}$$

Since

$t_i$ is monotonically increasing, we can write

$$\begin{array}{}\text{(}\ast \text{)}& t_i(X_i)\le {\overline{\alpha }}_i{X}_i\mathrm{\forall }i.\end{array}$$

Then similar to the previous section, we can define the price for each

$i$ as

$$\boxed{{\displaystyle P_i={\overline{m}}_i\frac{G}{T}}}$$

Theorem: When gas inequality holds and

$P_i={\overline{\alpha }}_i\frac{G}{T}$ for all

$i$, time inequality also holds.

Proof: We substitute

$P_i$'s in gas inequality

$${\overline{\alpha }}_1\frac{G}{T}{X}_1+{\overline{\alpha }}_2\frac{G}{T}{X}_2+\cdots +{\overline{\alpha }}_N\frac{G}{T}{X}_N\le G$$

which simplifies to

$${\overline{\alpha }}_1{X}_1+{\overline{\alpha }}_2{X}_2+\cdots +{\overline{\alpha }}_N{X}_N\le T.$$

$(\ast )$ allows us to write

$$t_1(X_1)+t_2(X_2)+\cdots +t_N(X_N)\le {\overline{\alpha }}_1{X}_1+{\overline{\alpha }}_2{X}_2+\cdots +{\overline{\alpha }}_N{X}_N$$

Since RHS is less than or equal to

$T$, LHS must be too. Thus, if gas inequality holds, time inequality also holds.

$◼$

When execution time of an operation depends on other variables

In certain cases, the execution time of an operation may depend on other variables, for example size of the state trie.

TBD