# EthParis conviction math

## Introduction

The source idea / function is:

$$
y_i = x + \alpha y_0
$$

where $y$ is conviction, $x$ is the token balance, which is constant between contract interactions, and $\alpha$ is a constant that controls the decay.

The discrete implementation is not suitable for smart contracts as it requires a loop. The next section plays with the function to find a continous function that suits the discrete behaviour specified by the function above.

## Computing a direct function

> The previous function requires iteration to find the value a specific timestep $i$. Iteration is not adequate code for running on Ethereum, so this section explains how to find a direct formula for the source function above.

If one extends the source function above to multiple steps:

$y_3 = x + \alpha y_2$
$y_2 = x + \alpha y_1$
$y_1 = x + \alpha y_0$

combining those three steps:

$$
y_3 = \alpha^3 y_0 + \alpha^2 x + \alpha^2 x + x
$$

which equals

$$
y_n = \alpha^n y_0 + x \sum_{i=0}^{n-1} \alpha^{i}
$$

using sumation identities, the latter summation equals to (substituting $n$ by $t$):

$$
y_t = \alpha^t y_0 + x \frac{1-\alpha^t}{1-\alpha}
$$

## Function analysis

The equation above let's you compute the conviction at any point in time $n$ with one single operation. Let's analyze it a bit tho. Since $0<\alpha<1$, the first term is an exponential decay. The second term is an "upper" exponential decay, that asymptotes to $x/(1-\alpha)$.

| Assumption | Equation | Sample plot, $\alpha=0.5$ |
| -------- | -------- | -------- |
| $y_0 = 0$ | $y_t = x \frac{1-\alpha^t}{1-\alpha}$ | 
| $x = 0$ | $y_t = \alpha^t y_0$ |  |

The parameters $y_0$ and $x$ control the weight of each term, so the conviction may increase or decrease. Let's compute their value at which conviction stays constant.

$$
\frac{dy}{dn} = \frac{\alpha^n ((\alpha-1) y_0 + x) ln(\alpha)}{\alpha-1}
$$

There are multiple solutions for $\frac{dy}{dn} = 0$:
- $\alpha = 0$
- $\alpha = 1$
- $x = y_0 (1 - \alpha)$

Each term of the above function is an exponential decay. When $x = 0$ the resulting equation could be rewritten as:

$$
y(t) = N_0 e^{-\lambda t}
$$
$$
\lambda = -ln(\alpha)
$$

We can compute the half life of the exponential decay, which in our case would mean the time it takes for conviction to reach half the max value.

$$
t_{1/2} = \frac{ln(2)}{\lambda} = -\frac{ln(2)}{ln(\alpha)}
$$

## Conclusion

### Continuous formula

The discrete function defining conviction at step $i$

$$
y_i = x + \alpha y_0
$$

is equivalent to (if $x$ is constant)

$$
y_t = \alpha^t y_0 + x \frac{1-\alpha^t}{1-\alpha}
$$

## Solidity implementation

Since $0<\alpha<1$, \alpha is a decimal number and must be amplified: $\alpha_D = \alpha*D$, where $D$ is a big enough integer.

$$
y_t = \frac{1}{D^t} [\alpha_D^t y_0 + xD \frac{D^t-\alpha_D^t}{D-\alpha_D}]
$$

[proof](https://www.wolframalpha.com/input/?i=1%2F(d%5En)*((a*d)%5En*y+%2B+x*d*(d%5En-(d*a)%5En)%2F(d-a*d)))

Two factors influence the error of the integer approximation.
- $D$ has to be big enough so $floor(a*D) - a*D = 0$
- $x$ must be very big. Approximately for $x=1e1$ there are errors of around 1%, for $x=1e3$ errors of 0.01% and for $x=1e18%$ errors of 1e-14%

// Predefined params
pragma solidity >=0.4.22 <0.6.0;
contract ConvictionComputation {
    uint D = 10;
    uint aD = 9;
    // Sample state
    uint y0 = 0;
    uint x = 1e18;
    function conviction(uint t) public view returns (uint) {
        uint Dt = D**t;
        uint aDt = aD**t;
        uint y = (aDt * y0 + (x*D*(Dt-aDt))/(D-aD)) / Dt;
        return y;
    }
}

Running the above `conviction` function with `t = 15` on the [Remix IDE](https://remix.ethereum.org/#optimize=true&version=soljson-v0.5.1+commit.c8a2cb62.js) costed **1314 gas** (execution cost). The actual implementation would require 2 state modifications (`y0` and `x`) adding `5000 * 2` of gas cost.

### Parameters behaviour

The parameter $\alpha$ controls how many times a staked token amount $x$ is multiplied $k$ after and infinite amount of time $t->\infty$:

| $k = \frac{1}{1-\alpha}$ |  |
| -------- | -------- |

Also, $\alpha$ controls the time it takes for conviction to reach $k/2$:

| $t_{1/2} = -\frac{ln(2)}{ln(\alpha)}$ |  |
| -------- | -------- |

To show some real numbers, below are results for some values of $\alpha = 0.9$.

| $\alpha$ | $k$ | $t_{1/2}$ |
| -------- | -------- | -------- |
| $0.1$ | $1.\overline{1}$ | $~0.3$
| $0.5$ | $2$ | $1$ |
| $0.9$ | $10$ | $~6.57$ |
| $0.99$ | $100$ | $~68.97$ |

## Additive behaviour

> **NOTICE**: The total initial conviction must be 0 for the above equality to be true.

The cool thing about the function above is that the individual conviction curves of multiple stakers are equal to the convition curve of all their token amounts summed :heart_eyes:.

$$
y(x1 + x2 + x3) = y(x1) + y(x2) + y(x3)
$$

That's great because wether a conviction curve has 1 or 1000 contributions, computing a conviction value point will cost the same. The graph below shows three conviction curves for three token staking timeseries:



> Notice: that the lines $y(x1+x2+x3)$ (green) and $y1+y2+y3$ (brown) are overlapped.

To illustrate, this is how different $\alpha$ values affect the above token staking timeseries:

| $\alpha=0.5$ | $\alpha=0.9$ | $\alpha=0.99$ |
| -------- | -------- | -------- |
|  |  | 
|

Source files: http://ge.tt/38pvq1v2