get_D() and get_y() in Curve StableSwap

Este artículo muestra algebraicamente paso a paso cómo se deriva el código para get_D() y get_y() a partir del invariante de StableSwap.

Dado el invariante de StableSwap:

An^n\sum x_i +D=An^nD+\frac{D^{n+1}}{n^n\prod x_i}

Hay dos operaciones matemáticas frecuentes que deseamos realizar con él:

Calcular $D$ dados valores fijos para $A$ , y las reservas $x_1,\dots,x_n$ . Ten en cuenta que $n$ , el número de monedas que soporta el pool, se fija en el momento en que se despliega el pool. Esto es lo que hace la función get_D().
Dado $D$ , deseamos aumentar el valor de una de las reservas $x_i$ a un nuevo valor $x_i'$ y averiguar cuánto necesita disminuir otra reserva $x_j$ para mantener la ecuación equilibrada. Esto es lo que hace la función get_y(). Aquí “y” significa $x_i'$ .

Estas operaciones se llaman get_D() y get_y(), respectivamente, en Curve StableSwap.

El objetivo de `get_D()`

En Curve V1 (StableSwap), D se comporta de manera similar a k en Uniswap V2 — cuanto mayor sea D, mayores serán las reservas y más “hacia afuera” estará la curva de precios. D cambia — y necesita ser recalculado — después de que se añade o se retira liquidez, o si una comisión cambia el balance del pool. Para esto sirve la función get_D(). Dadas las reservas actuales del pool, calcula D.

Si un pool de Curve contiene dos tokens, x e y, el invariante de StableSwap es

4A(x + y) + D = 4AD+\frac{D^3}{4xy}

El “factor de amplificación” A, para nuestros propósitos, puede ser tratado como una constante.

El objetivo de `get_y()`

La función get_y() se utiliza durante un intercambio (swap). De manera similar a k en Uniswap V2, D debe mantenerse constante durante un swap (ignorando las comisiones). Específicamente, dado un nuevo valor para x, calcula el valor de y que mantiene la ecuación equilibrada. Por lo tanto, es una subrutina importante para averiguar “si meto esta cantidad de token x en el pool, ¿qué cantidad de token y se puede sacar?”

Curve puede contener más de 2 tokens en el pool (por ejemplo, 3pool contiene USDT, USDC y DAI). Curve identifica las monedas por un índice en un array. Así que, en este caso, x e y se refieren a monedas particulares en ese array. En este contexto, get_y() significa cambiar el balance de un token particular x, manteniendo los otros balances constantes, pero permitiendo que otro token y cambie de valor. Luego, dado un cambio particular en x, calcula cómo cambia y para mantener el invariante equilibrado.

El invariante para n tokens es:

An^n\sum x_i +D=An^nD+\frac{D^{n+1}}{n^n\prod x_i}

Para mayor simplicidad, utilizaremos $S$ en lugar de sumatoria y $P$ en lugar de productoria en el resto del artículo, de modo que el invariante se convierte en:

An^nS + D = ADn^n+\frac{D^{n+1}}{n^nP}

Donde $S$ es la suma de los balances de los tokens ( $x_0 + x_1 + … + x_n$ ), $P$ es el producto de los balances ( $x_0x_1...x_n$ ), y $x_i$ es el balance del token i.

En el whitepaper, $S$ se escribe como $\sum x_i$ y $P$ se escribe como $\prod x_i$ . La ecuación del whitepaper se replica a continuación:

An^n\sum x_i + D=ADn^n+\frac{D^{n+1}}{n^n\prod x_i}

Utilizaremos $S$ y $P$ en lugar de la notación de suma y producto.

Asumimos que los pools pueden contener un número arbitrario $n$ de tokens, por lo que las fórmulas reflejarán eso. En la práctica, sin embargo, $n$ debe ser pequeño, de lo contrario el término $D^{n+1}$ es susceptible de sufrir un overflow.

Calculando $D$ con `get_D()`

En get_D(), se nos presenta un conjunto de balances x_0, x_1, ..., x_n y debemos calcular D.

No es posible despejar algebraicamente

An^nS + D = ADn^n+\frac{D^{n+1}}{n^nP}

para $D$ . En su lugar, necesitamos aplicar el método de Newton para resolverlo numéricamente. Para hacerlo, creamos una función $f(D)$ , la cual es 0 cuando la ecuación está equilibrada.

0 =ADn^n+\frac{D^{n+1}}{n^nP}-D-An^nS

0 =\frac{D^{n+1}}{n^nP}+ADn^n-D-An^nS

\color{green}{f(D)=\frac{D^{n+1}}{n^nP}+An^nD-D-An^nS}

y calculamos la derivada $f'(D)$ con respecto a $D$ como:

f'(D) = \frac{(n+1)D^n}{n^nP}+An^n-1

Fórmula del Método de Newton

Podemos despejar iterativamente $D$ utilizando:

D_\text{next}=D-\frac{f(D)}{f'(D)}

Será útil expresar $f'(D)$ con $D$ en el denominador. Primero multiplicamos la parte superior e inferior de la fracción izquierda que define $f'(D)$ por $D$ .

f'(D) = \frac{\frac{(n+1)D^{n+1}}{n^nP}}{D}+An^n-1

Y luego combinamos $f'(D)$ en una sola fracción:

\begin{align*} f'(D) &= \frac{\frac{(n+1)D^{n+1}}{n^nP}}{D}+\frac{(An^n-1)D}{D}\\f'(D) &=\color{red}{\frac{\frac{(n+1)D^{n+1}}{n^nP}+(An^n-1)D}{D}} \end{align*}

Podemos reescribir el método de Newton para tener un denominador común:

\begin{align*} D_\text{next}&=D-\frac{f(D)}{f'(D)}&&\text{// Método de Newton}\\ &=D\frac{f'(D)}{f'(D)}-\frac{f(D)} {f'(D)} &&\text{// multiplicar } D \text{ por }\frac{f'(D)}{f'(D)}\\ &=\frac{\color{violet}{D}\color{red}{f'(D)}-\color{green}{f(D)}}{\color{red}{f'(D)}}&&\text{// combinar por denominador común} \end{align*}

Al sustituir el $f(D)$ y $f'(D)$ anteriores en la fórmula reescrita del método de Newton obtenemos:

=\frac{\color{violet}{D}\color{red}{\frac{(n+1)\frac{D^{n+1}}{n^nP}+(An^n-1)D}{D}}-\color{green}{(\frac{D^{n+1}}{n^nP}+An^nD-D-An^nS)}}{\color{red}{\frac{(n+1)\frac{D^{n+1}}{n^nP}+(An^n-1)D}{D}}}

Dado que reorganizamos $f'(D)$ para tener $D$ en el denominador, el término $\color{violet}D\color{red}f'(D)$ se cancelará perfectamente:

=\frac{\color{violet}{\cancel{D}}\color{red}{\frac{(n+1)\frac{D^{n+1}}{n^nP}+(An^n-1)D}{\cancel{D}}}-\color{green}{(\frac{D^{n+1}}{n^nP}+An^nD-D-An^nS)}}{\color{red}{\frac{(n+1)\frac{D^{n+1}}{n^nP}+(An^n-1)D}{D}}}

=\frac{(n+1)\frac{D^{n+1}}{n^nP}+(An^n-1)D-\color{green}{(\frac{D^{n+1}}{n^nP}+An^nD-D-An^nS)}}{\frac{(n+1)\frac{D^{n+1}}{n^nP}+(An^n-1)D}{D}}

Distribuimos todos los términos para eliminar los paréntesis en el numerador:

=\frac{\frac{D^{n+1}}{n^nP}+\frac{nD^{n+1}}{n^nP}+An^nD-D-\frac{D^{n+1}}{n^nP}-An^nD+D+An^nS}{\frac{(n+1)\frac{D^{n+1}}{n^nP}+(An^n-1)D}{D}}

Esto conduce a muchas cancelaciones

=\frac{\cancel{\frac{D^{n+1}}{n^nP}}+\frac{nD^{n+1}}{n^nP}+\cancel{An^nD}-\cancel{D}-\cancel{\frac{D^{n+1}}{n^nP}}-\cancel{An^nD}+\cancel{D}+An^nS}{\frac{(n+1)\frac{D^{n+1}}{n^nP}+(An^n-1)D}{D}}\\

=\frac{\frac{nD^{n+1}}{n^nP}+An^nS}{\frac{(n+1)\frac{D^{n+1}}{n^nP}+(An^n-1)D}{D}}

Multiplicamos el numerador y el denominador por $D$

=\frac{(An^nS+n{\frac{D^{n+1}}{n^nP}})D}{(An^n-1)D+(n+1){\frac{D^{n+1}}{n^nP}}}

Si definimos $D_p$ como

D_p=\frac{D^{n+1}}{n^nP}

y sustituimos $D_p$ obtenemos

=\frac{(An^nS+n\boxed{\frac{D^{n+1}}{n^nP}})D}{(An^n-1)D+(n+1)\boxed{\frac{D^{n+1}}{n^nP}}}

D_\text{next}=\frac{(An^nS+D_pn)D}{(An^n-1)D+(n+1)D_p}

Comparación con el código fuente original

Esto coincide exactamente con lo que hay en el código de Vyper:

Captura de pantalla de get_D() con el código anotado

La variable $D_p$ se definió como:

D_P: uint256 = D # D_P = S

for _x in xp:
    D_P = D_P * D / (_x * N_COINS)

xp es el número de tokens, por lo que el bucle se ejecutará n veces. Por lo tanto, tenemos a $D$ multiplicado por sí mismo n veces en el denominador

D_p=\frac{D^{n+1}}{n^n\prod_{i=1}^nx_i}

Calculando `y` con `get_y()`

La idea es que forzamos a uno de los $x_i$ a tomar un nuevo valor (el código llama a esto x) y calculamos el valor correcto para otro $x_j$ (donde $i \neq j)$ de tal manera que la ecuación se mantenga equilibrada. El balance de los otros tokens permanece inalterado. A $x_j$ se le denomina $y$ .

Aunque un pool de StableSwap podría tener múltiples tokens, solo es posible intercambiar dos de esos tokens a la vez usando get_y().

De nuevo, tenemos el mismo invariante

An^nS + D = ADn^n+\frac{D^{n+1}}{n^nP}

$D$ , $A$ , y $n$ son fijos, pero estaremos cambiando dos de los valores en $S$ y $P$

\begin{align*} S &= x_0+x_1+...+x_n\\ P &= x_0x_1...x_n \end{align*}

Por lo tanto, necesitamos ajustar la fórmula un poco, ya que $S$ y $P$ contienen los valores que estamos calculando.

$S'$ será la suma de todos los balances excepto el nuevo balance del token $x_i$ que estamos intentando despejar
$P$ será el producto de los balances de todos los tokens, excepto el del que estamos intentando despejar.

En otras palabras,

\begin{align*} S &= S'+y \\ P &= P'y \end{align*}

Para mantener la consistencia con el código, llamaremos $y$ al token cuyo nuevo balance estamos intentando calcular.

Entonces la fórmula se convierte en

An^n(S'+y) + D = ADn^n+\frac{D^{n+1}}{n^nP'y}

De nuevo, derivamos un $f(y)$ que es 0 cuando la ecuación está equilibrada, y su derivada con respecto a y

\begin{align*}f(y) &= \color{green}{ADn^n+\frac{D^{n+1}}{n^nP'y}-An^n(S'+y) - D}\\f'(y)&=\color{red}{\frac{-D^{n+1}}{n^nP'y^2}-An^n}\end{align*}

Aquí está la fórmula del método de Newton de nuevo:

y_\text{next}=y-\frac{f(y)}{f'(y)}

Después de sustituir $f(y)$ y $f'(y)$ en el método de Newton obtenemos:

y_\text{next}=y-\frac{\color{green}{ADn^n+\frac{D^{n+1}}{n^nP'y}-An^n(S'+y) - D}}{\color{red}{\frac{-D^{n+1}}{n^nP'y^2}-An^n}}

Sacamos el $-1$ del denominador

y_\text{next}=y--1\cdot\frac{ADn^n+\frac{D^{n+1}}{n^nP'y}-An^n(S'+y) - D}{\frac{D^{n+1}}{n^nP'y^2}+An^n}

y_\text{next}=y+\frac{ADn^n+\frac{D^{n+1}}{n^nP'y}-An^n(S'+y) - D}{\frac{D^{n+1}}{n^nP'y^2}+An^n}

Multiplicamos $y$ (en la caja a continuación) para tener un denominador común:

y_\text{next}=\boxed{y}+\frac{ADn^n+\frac{D^{n+1}}{n^nP'y}-An^n(S'+y) - D}{\frac{D^{n+1}}{n^nP'y^2}+An^n}

y_\text{next}=y\frac{\frac{D^{n+1}}{n^nP'y^2}+An^n}{\frac{D^{n+1}}{n^nP'y^2}+An^n}+\frac{ADn^n+\frac{D^{n+1}}{n^nP'y}-An^n(S'+y) - D}{\frac{D^{n+1}}{n^nP'y^2}+An^n}

Distribuimos $y$ en el término izquierdo

y_\text{next}=y\boxed{\frac{\frac{D^{n+1}}{n^nP'y^2}+An^n}{\frac{D^{n+1}}{n^nP'y^2}+An^n}}+\frac{ADn^n+\frac{D^{n+1}}{n^nP'y}-An^n(S'+y) - D}{\frac{D^{n+1}}{n^nP'y^2}+An^n}

y_\text{next}=\frac{\frac{D^{n+1}}{n^nP'y}+An^ny}{\frac{D^{n+1}}{n^nP'y^2}+An^n}+\frac{ADn^n+\frac{D^{n+1}}{n^nP'y}-An^nS'-An^ny - D}{\frac{D^{n+1}}{n^nP'y^2}+An^n}

Combinamos las sumas con un denominador común

y_\text{next}=\frac{ADn^n+2\frac{D^{n+1}}{n^nP'y}-An^nS' - D}{\frac{D^{n+1}}{n^nP'y^2}+An^n}

Creando una sustitución a partir del invariante original

Podría parecer que la ecuación no se puede simplificar más, pero si revisamos nuestro invariante original

An^n(S'+y) + D = ADn^n+\frac{D^{n+1}}{n^nP'y}

Podemos despejar $ADn^n$ y obtenemos

An^n(S'+y) + D = \boxed{ADn^n}+\frac{D^{n+1}}{n^nP'y}

An^n(S'+y) + D -\frac{D^{n+1}}{n^nP'y}= \boxed{ADn^n}

ADn^n=\boxed{-\frac{D^{n+1}}{n^nP'y}+An^n(S'+y) + D}

Y luego, si sustituimos $ADn^n$ en el numerador de nuestra última fórmula para $y_\text{next}$ , obtenemos

y_\text{next}=\frac{\boxed{ADn^n}+2\frac{D^{n+1}}{n^nP'y}-An^nS' - D}{\frac{D^{n+1}}{n^nP'y^2}+An^n}

y_\text{next}=\frac{\boxed{(-\frac{D^{n+1}}{n^nP'y}+An^n(S'+y) + D)}+2\frac{D^{n+1}}{n^nP'y}-An^nS' - D}{\frac{D^{n+1}}{n^nP'y^2}+An^n}

Ocurren muchas cancelaciones

y_\text{next}=\frac{-\frac{D^{n+1}}{n^nP'y}+\cancel{An^nS'}+An^ny + \cancel{D}+\cancel{2}\frac{D^{n+1}}{n^nP'y}-\cancel{An^nS'} - \cancel{D}}{\frac{D^{n+1}}{n^nP'y^2}+An^n}

Y nos quedamos con una ecuación mucho más pequeña

y_\text{next}=\frac{An^ny +\frac{D^{n+1}}{n^nP'y}}{\frac{D^{n+1}}{n^nP'y^2}+An^n}

Multiplicamos la parte superior e inferior por $\frac{y}{An^n}$

y_\text{next}=\frac{(An^ny +\frac{D^{n+1}}{n^nP'y})\frac{y}{An^n}}{(\frac{D^{n+1}}{n^nP'y^2}+An^n)\frac{y}{An^n}}

y_\text{next}=\frac{y^2 +\frac{D^{n+1}}{n^nP'An^n}}{\frac{D^{n+1}}{n^nP'y}\frac{1}{An^n}+y}

Volviendo a nuestro invariante, podemos despejar el término fraccionario en el denominador:

An^n(S'+y) + D = ADn^n+\boxed{\frac{D^{n+1}}{n^nP'y}}

\frac{D^{n+1}}{n^nP'y}=\boxed{An^n(S'+y) + D -ADn^n}

Luego podemos sustituir eso en la ecuación para ynext:

y_\text{next}=\frac{y^2 +\frac{D^{n+1}}{n^nP'An^n}}{\boxed{\frac{D^{n+1}}{n^nP'y}}\frac{1}{An^n}+y}

y_\text{next}=\frac{y^2 +\frac{D^{n+1}}{n^nP'An^n}}{\boxed{(An^n(S'+y) + D -ADn^n)}\frac{1}{An^n}+y}

Luego podemos distribuir $\frac{1}{An^n}$ y simplificar el denominador

y_\text{next}=\frac{y^2 +\frac{D^{n+1}}{n^nP'An^n}}{((S'+y) + \frac{D}{An^n} -D)+y}

y_\text{next}=\frac{y^2 +\frac{D^{n+1}}{n^nP'An^n}}{(S'+y + \frac{D}{An^n} -D)+y}

Simplificamos el denominador eliminando los paréntesis y sumando las dos $y$ juntas

y_\text{next}=\frac{y^2 +\frac{D^{n+1}}{n^nP'An^n}}{2y+S' + \frac{D}{An^n} -D}

En el código original, Curve define variables adicionales:

c = \frac{D^{n+1}}{n^nP'An^n}

b = S' + \frac{D}{An^n}

Después de la sustitución en la fórmula para $y_\text{next}$ , obtenemos:

y_\text{next}=\frac{y^2 +\boxed{\frac{D^{n+1}}{n^nP'An^n}}}{2y+\boxed{S' + \frac{D}{An^n}} -D}

y_\text{next}=\frac{y^2 +c}{2y+b -D}

Comparación con el código fuente original

Esto coincide exactamente con el código de Curve, como se ve en el recuadro morado a continuación:

captura de pantalla de get_y() anotada

Discrepancia entre Ann y Anⁿ

De manera un tanto confusa, el whitepaper de Curve usa el invariante $An^n$ pero la base de código usa Ann. Es decir, la base de código parece estar calculando A * n * n en lugar de A * n ** n. La razón de esta discrepancia es que la base de código almacena $A$ como $An^{n-1}$ . Dado que $n$ es fijo en el momento del despliegue, precalcular $n^{n-1}$ permite que el código evite calcular un exponente on-chain, lo cual es una operación más costosa.

Resumen

El invariante central de Curve no permite que las variables $D$ o $x_i$ se despejen de manera simbólica. En su lugar, los términos deben resolverse numéricamente.

Una de las lecciones de este ejercicio es que una buena manipulación algebraica es una técnica muy efectiva de optimización de gas. Los desarrolladores de Curve fueron capaces de calcular la fórmula del método de Newton que es mucho más reducida que simplemente insertar $f$ y su derivada y dejarlo así.

Citas y Agradecimientos

Los siguientes recursos fueron consultados al escribir este artículo:

StableSwap - efficient mechanism for Stablecoin liquidity, Michael Egorov, https://resources.curve.fi/pdf/curve-stableswap.pdf

Understanding the Curve AMM, Part -1: StableSwap Invariant, Atul Agarwal https://atulagarwal.dev/posts/curveamm/stableswap/

Curve Finance Discord, “chanho”

https://discord.com/channels/729808684359876718/729812922649542758/1126630568004698132

Curve - Code Explaind - get_y() | DeFi, Smart Contract Programmer https://www.youtube.com/watch?v=jAhKbxoeskQ

get_D() y get_y() en Curve StableSwap

El objetivo de get_D()

El objetivo de get_y()

Calculando DDD con get_D()

Fórmula del Método de Newton

Comparación con el código fuente original

Calculando y con get_y()

Creando una sustitución a partir del invariante original

Comparación con el código fuente original

Discrepancia entre Ann y Anⁿ

Resumen

Citas y Agradecimientos

El objetivo de `get_D()`

El objetivo de `get_y()`

Calculando $D$ con `get_D()`

Calculando `y` con `get_y()`