Skip to main content

Discrete Calculus for DeFi Math

ยท 6 min read
Eric Forgy

Hello everyone and welcome to the CavalRe! ๐Ÿค 

In this article, I present a primer on discrete calculus with the intention of helping us analyze DeFi protocols running on blockchains, which are inherently discrete in nature.

Blockchain as a State Machineโ€‹

The Ethereum yellow paper describes the Ethereum blockchain as a state machine with the state of the world denoted by ฯƒt\sigma_t. Given a transaction Tt,t+1T_{t,t+1}, the state is updated to a new state ฯƒt+1\sigma_{t+1} by the Ethereum state transition function ฮฅt,t+1\Upsilon_{t,t+1} denoted by

ฯƒt+1=ฮฅt,t+1(ฯƒt,Tt,t+1).\sigma_{t+1} = \Upsilon_{t,t+1}(\sigma_t,T_{t,t+1}).

It is important to note the inherent discreteness of this process. There is no state between ฯƒt\sigma_t and ฯƒt+1.\sigma_{t+1}. A transaction takes you from some initial state to some final state with nothing in between and repeats indefinitely with every new transaction.

This discreteness has implications for how we should analyze blockchain protocols such as automated market makers (AMMs) so we will enhance our toolbox for dealing with this discreteness in the remainder of this article.

Node Functionsโ€‹

Every blockchain needs to start with some initial state created by some kind of genesis event. Therefore, it makes sense to restrict tt to be a natural number N\N with the initial state denoted ฯƒ0.\sigma_0. A node function is simply a function

f:Nโ†’R,f: \N\to\R,

where R\R denotes real numbers. Let et\mathbf{e}^t denote a special function whose value is given by

et(tโ€ฒ)={1ifย t=tโ€ฒ,0otherwise.\mathbf{e}^t(t') = \begin{cases} 1 &\text{if } t = t',\\ 0 &\text{otherwise.} \end{cases}

Any node function f:Nโ†’Rf:\N\to\R can be expressed as a linear combination of these functions, i.e.

f=โˆ‘tโˆˆNftet,f = \sum_{t\in\N} f_t \mathbf{e}^t,

where ftโˆˆRf_t\in\R is the value of ff at tt. The basis functions can be multiplied

etetโ€ฒ={etifย t=tโ€ฒ,0otherwise\mathbf{e}^t \mathbf{e}^{t'} = \begin{cases} \mathbf{e}^t &\text{if } t = t',\\ 0 &\text{otherwise} \end{cases}

which extends to the product of arbitrary node functions f,g:Nโ†’Rf,g:\N\to\R intuitively as

fg=โˆ‘tโˆˆNftgtet.f g = \sum_{t\in\N} f_t g_t \mathbf{e}^t.

The product of two node functions is commutative, i.e. fg=gf.f g = g f.

Edge Functionsโ€‹

The natural numbers N\N can be thought of as a simple directed graph. In the context of blockchain, the state ฯƒt\sigma_t would then reside on the node t,t, whereas the transaction Tt,t+1T_{t,t+1} would reside on the directed edge between states ฯƒt\sigma_t and ฯƒt+1\sigma_{t+1} as illustrated below.

Directed graph

Letting dNd\N denote the set of edges between natural numbers when thinking of N\N as a directed graph, define functions et,t+1:dNโ†’R\mathbf{e}^{t,t+1}: d\N\to\R by

et,t+1(tโ€ฒ,tโ€ฒ+1)={1ifย t=tโ€ฒ,0otherwise.\mathbf{e}^{t,t+1}(t',t'+1) = \begin{cases} 1 &\text{if } t = t',\\ 0 &\text{otherwise.} \end{cases}

We can then define a general discrete edge function TT as a linear combination

T=โˆ‘tโˆˆNTt,t+1et,t+1,T = \sum_{t\in\N} T_{t,t+1} \mathbf{e}^{t,t+1},

where Tt,t+1T_{t,t+1} is the value of TT on the edge (t,t+1).(t,t+1).

Multiplication of an edge function by a node function on the left can be defined in terms of basis functions via

etetโ€ฒ,tโ€ฒ+1={et,t+1ifย t=tโ€ฒ,0otherwise.\mathbf{e}^t \mathbf{e}^{t',t'+1} = \begin{cases} e^{t,t+1} &\text{if } t = t',\\ 0 &\text{otherwise.} \end{cases}

In other words, the product is zero unless the node coincides with the beginning of the edge. Similarly, multiplication of an edge function by a node function on the right can be defined in terms of basis functions via

et,t+1etโ€ฒ={et,t+1ifย t+1=tโ€ฒ,0otherwise.\mathbf{e}^{t,t+1} \mathbf{e}^{t'} = \begin{cases} e^{t,t+1} &\text{if } t+1 = t',\\ 0 &\text{otherwise.} \end{cases}

In other words, the product is zero unless the node coincides with the end of the edge. In general we have

fT=โˆ‘tโˆˆNftTt,t+1et,t+1f T = \sum_{t\in\N} f_t T_{t,t+1} \mathbf{e}^{t,t+1}

and

Tf=โˆ‘tโˆˆNft+1Tt,t+1et,t+1T f = \sum_{t\in\N} f_{t+1} T_{t,t+1} \mathbf{e}^{t,t+1}

so that the product of node functions and edge functions is noncommutative, i.e. fTโ‰ Tf.f T \neq T f.

Discrete Differentialsโ€‹

There is a special "unit" node function

1=โˆ‘tโˆˆNet1 = \sum_{t\in\N} \mathbf{e}^t

that satisfies 1f=f1=f1 f = f 1 = f and 1T=T1=T.1 T = T 1 = T. Similarly, there is a special "graph" edge function

G=โˆ‘tโˆˆNet,t+1.G = \sum_{t\in\N} \mathbf{e}^{t,t+1}.

With the graph edge function, we can define the differential of a node function ff via

df:=[G,f],d f := [G,f],

where [G,f]=Gfโˆ’fG[G,f] = G f - f G denotes the commutator, i.e.

df=โˆ‘tโˆˆN(ฮ”f)t,t+1et,t+1,d f = \sum_{t\in\N} (\Delta f)_{t,t+1} \mathbf{e}^{t,t+1},

with

(ฮ”f)t,t+1:=ft+1โˆ’ft.(\Delta f)_{t,t+1} := f_{t+1} - f_t.

It follows from the properties of the commutator that

[G,fg]=[G,f]g+f[G,g][G,f g] = [G,f] g + f [G,g]

which gives rise to the discrete product rule

d(fg)=(df)g+f(dg).d(f g) = (d f) g + f (d g).

Although the product of node functions on the left-hand side is commutative, the products on the right-hand side are noncommutative so the order they are written matters. We could have also written the discrete product rule as

d(gf)=(dg)f+g(df).d(g f) = (d g) f + g (d f).

This means that when dealing with discrete node and edge functions, as we must with blockchain protocols, we have a degree of freedom in how we decompose terms in the discrete product rule.

Let us introduce a new general notation

{A,B}k=kAB+(1โˆ’k)BA,\{A,B\}_k = k A B + (1-k) B A,

where 0โ‰คkโ‰ค10\le k\le 1 and we have

{A,B}k={B,A}1โˆ’k.\{A,B\}_k = \{B,A\}_{1-k}.

When the product is commutative, as it is with node functions f,g,f,g, we have

{f,g}k=fg=gf\{f,g\}_k = f g = g f

and it is straightforward to show that the general expression for the discrete product rule is given by

d(fg)={df,g}k+{f,dg}k.d(f g) = \{d f,g\}_k + \{f, d g\}_k.

For numerical implementation, we'll need to expand the above into components and we get:

{df,g}k=โˆ‘tโˆˆN(ฮ”f)t,t+1(Ekg)t,t+1et,t+1\{d f,g\}_k = \sum_{t\in\N} (\Delta f)_{t,t+1} (E_k g)_{t,t+1} \mathbf{e}^{t,t+1}

and

{f,dg}k=โˆ‘tโˆˆN(E1โˆ’kf)t,t+1(ฮ”g)t,t+1et,t+1,\{f, d g\}_k = \sum_{t\in\N} (E_{1-k} f)_{t,t+1} (\Delta g)_{t,t+1} \mathbf{e}^{t,t+1},

where

(Ekf)t,t+1=(1โˆ’k)ft+kft+1(E_k f)_{t,t+1} = (1-k) f_t + k f_{t+1}

so that the discrete product rule may be expressed in components as

ฮ”(fg)t,t+1=ฮ”ft,t+1Ekgt,t+1+E1โˆ’kft,t+1ฮ”gt,t+1.\Delta(f g)_{t,t+1} = \Delta f_{t,t+1} E_k g_{t,t+1} + E_{1-k} f_{t,t+1} \Delta g_{t,t+1}.

The value of kk has no impact on the sum. It merely impacts the way the discrete product rule decomposes into the two terms. As we will see in subsequent articles, this degree of freedom stemming from the inherent discreteness of a blockchain has important implications for AMM design.

Closer look ๐Ÿง: Note on Symmetries

One kind of symmetry was already noted above, namely

{A,B}k={B,A}1โˆ’k.\{A,B\}_k = \{B,A\}_{1-k}.

There is another related kind of symmetry given by

(Ekf)t,t+1=(E1โˆ’kf)t+1,t(E_k f)_{t,t+1} = (E_{1-k} f)_{t+1,t}

and

(ฮ”f)t,t+1=โˆ’(ฮ”f)t+1,t.(\Delta f)_{t,t+1} = -(\Delta f)_{t+1,t}.

In other words, if the direction of time is reversed so that tt and t+1t+1 are swapped, then we can simply replace kk with 1โˆ’k1-k in the discrete product rule. This means that:

  • The discrete product rule for k=0k=0 is equivalent to the discrete product rule for k=1k=1 with time reversed;
  • The discrete product rule for k=1k=1 is equivalent to the discrete product rule for k=0k=0 with time reversed; and
  • The discrete product rule for k=1/2k=1/2 is the same whether forward in time or time reversed.

We will see this again when looking at self financing in DeFi protocols.