Matemática em Solidity (Parte 3: Porcentagens e Proporções)

Esse artigo é o terceiro de uma série de artigos sobre matemática em Solidity. Desta vez o tópico é: porcentagens e proporções.

Tradução de Mikhail Vladimirov feita por Christian Moura, artigo original disponível aqui.

Sumário

1 . Introdução

2 . Como podemos evitar um Overflow

3 . Como podemos evitar o problema do overflow fantasma mantendo a precisão

4 . Como podemos evitar o overflow fantasma completamente

5 . Podemos fazer isso mais barato

6 . Usar Números de Ponto Flutuante em Solidity

7 . Conclusão

Introdução

Matemática financeira começa com porcentagens. Quanto é x por cento de y? Quantos por cento de x é y? Todos nós sabemos as respostas: x por cento de y é x * y ÷ 100 e y é y * 100 ÷ x por cento de x. Isso é matemática de escola.

As fórmulas acima são casos particulares de solução de proporções. Em geral, proporção é uma equação na seguinte forma: a÷b=c÷d, e solucionar a proporção quer dizer achar um dos valores sabendo os outros três. Por exemplo, d pode ser achado a partir de a,b, e c assim: d=b×c÷a.

Sendo simples e direta em linguagens de programação convencionais, em Solidity esses cálculos simples são surpreendentemente desafiadores, como nós mostramos no artigo anterior. Há duas razões para isso: i) Solidity não tem suporte para frações; e ii) tipos numéricos em Solidity podem ter overflow.

Em Javascript, alguém pode calcular x*y÷z simplesmente fazendo: x*y/z. Em Solidity essa expressão não seria aceita em uma auditoria de segurança, pelo fato de uma multiplicação de um x ou y grandes o suficiente pode causar overflow e portanto resultar num cálculo incorreto. Usar SafeMath não ajuda muito, pois a transação poderia falhar mesmo se o resultado do cálculo coubesse em 256 bits. No artigo passado nós chamamos essa situação de “overflow fantasma”. Fazer a divisão antes da multiplicação como x/z*y ou y/z*x soluciona o problema do overflow fantasma, porém pode levar à degradação de precisão.

Nesse artigo nós descobrimos quais são as melhores maneiras que existem em Solidity para lidar com porcentagens e proporções.

Em direção da proporção completa

O objetivo nesse artigo é implementar em Solidity a seguinte função:

function mulDiv (uint x, uint y, uint z)
public pure returns (uint)

Que calcula x*y÷z, arredonda o resultado para baixo, e dá throw se z for zero ou o resultado não cabe em um uint.Vamos começar com a seguinte solução direta:

function mulDiv (uint x, uint y, uint z)
public pure returns (uint)
{
 return x * y / z;
}

Essa solução basicamente satisfaz a maioria dos requisitos: parece calcular x*y÷z, arredondar o resultado para baixo, e dar um throw caso z for zero. No entanto, existe um problema: o que ela de fato calcula é x*y mod2²⁵⁶÷z. É assim que um overflow de multiplicação funciona em Solidity. Quando o resultado da multiplicação não cabe em 256 bits, apenas os 256 primeiros bits do resultado são retornados. Para todos os valores pequenos de x e y, quando x*y<2²⁵⁶, não existe diferença, mas para x e y isso iria produzir resultados incorretos. Então a primeira questão é:

Como podemos evitar um Overflow

Spoiler: não deveríamos.

Uma maneira comum de evitar overflow de multiplicação em Solidity é usar a função mul da biblioteca SafeMath:

function mulDiv (uint x, uint y, uint z)
public pure returns (uint)
{
 return mul (x, y) / z;
}

Esse código garante o resultado correto, então agora todos os requisitos estão satisfeitos, certo? Não tão rápido.

O requisito é reverter caso o resultado não caibadentro de uint,e a implementação parece satisfazê-lo. No entanto, essa implementação também reverte quando x*y não cabe em um uintmesmo que o resultado final caiba. Nós chamamos essa situação de um overflow fantasma. No artigo anterior nós mostramos como solucionar o overflow fantasma a um custo de precisão, no entanto aquela solução não funciona aqui, nós queremos um resultado preciso.

E apenas reverter em um overflow fantasma não é uma opção, então

Como podemos evitar o problema do overflow fantasma mantendo a precisão

Spoiler: truques simples de matemática.

Vamos fazer as seguintes substituições: x=a×z+b e y=c×z+d, onde a, b, c, e d são inteiros e 0≤b<z e 0≤d<z. Então:

x×y÷z=
(a×z+b)×(c×z+d)÷z=
(a×c×z²+(a×d+b×c)×z+b×d)÷z=
a×c×z+a×d+b×c+b×d÷z

Valores a,b,c e d podem ser calculados como quocientes e restos dividindo x por y respectivamente.

Então,a função pode ser reescrita assim:

function mulDiv (uint x, uint y, uint z)
public pure returns (uint)
{
uint a = x / z; uint b = x % z; // x = a * z + b
    uint c = y / z; uint d = y % z; // y = c * z + d

    return a * b * z + a * d + b * c + b * d / z;
}

aqui nós usamos operações + e * simples por legibilidade, mas o código real deveria usar SafeMath para evitar overflow real, isto é, não fantasma.

Nessa implementação o overflow fantasma ainda é possível, mas apenas no último termo: b * d / z. No entanto, esse código é garantido funcionar corretamente quando z≤2¹²⁸ pois ambos, b e d são menores que z, portanto b*d é garantido caber em 256 bits. Então essa implementação poderia ser usada em casos onde z é conhecido e não excede 2¹²⁸. Um exemplo comum é multiplicação de ponto fixado com 18 decimais: x×y÷10¹⁸. Mas,

Como podemos evitar o overflow fantasma completamente

Spoiler: usamos números mais largos.

A raiz do problema do overflow fantasma é que uma multiplicação intermediária pode não caber em 256 bits. Então vamos usar um tipo maior. Solidity não dá suporte nativo a tipos numéricos maiores que 256 bits, então nós temos que emulá-los. Nós basicamente precisamos de duas operações: uint×uint→wide e wide÷uint→uint

O produto de dois inteiros sem sinal de 256 bits não pode exceder 512 bits, o tipo maior tem que ter pelo menos 512 bits, nós podemos emular um inteiro sem sinal de 512 bits em Solidity usando dois inteiros sem sinal de 256 bits guardando os bits mais à esquerda e mais a direita do inteiro de 512 bits respectivamente.

Então o código poderia ser assim:

function mulDiv (uint x, uint y, uint z)
public pure returns (uint)
{
 (uint l, uint h) = fullMul (x, y);
 return fullDiv (l, h, z);
}

Aqui a função FullMul multiplica dois inteiros sem sinal de 256 bits e retorna o resultado como um inteiro de 512 bits sem sinal dividido em duas partes de 256 bits. A função fullDiv divide o inteiro sem sinal de 512 bits, passado como duas partes de 256 bits,e retorna o resultado como um inteiro sem sinal de 256 bits.

Vamos implementar essas duas funções usando matemática de escola:

function fullMul (uint x, uint y)
public pure returns (uint l, uint h)
{
 uint xl = uint128 (x); uint xh = x >> 128;
 uint yl = uint128 (y); uint yh = y >> 128;

 uint xlyl = xl * yl; uint xlyh = xl * yh;
 uint xhyl = xh * yl; uint xhyh = xh * yh;

 uint ll = uint128 (xlyl);
 uint lh = (xlyl >> 128) + uint128 (xlyh) + uint128 (xhyl);
 uint hl = uint128 (xhyh) + (xlyh >> 128) + (xhyl >> 128);
 uint hh = (xhyh >> 128);

 l = ll + (lh << 128);
 h = (lh >> 128) + hl + (hh << 128);
}

e

function fullDiv (uint l, uint h, uint z)
public pure returns (uint r) {
 require (h < z);

 uint zShift = mostSignificantBit (z);
 uint shiftedZ = z;
 if (zShift <= 127) zShift = 0;
 else
 {
   zShift -= 127;
   shiftedZ = (shiftedZ - 1 >> zShift) + 1;
 }

 while (h > 0)
 {
   uint lShift = mostSignificantBit (h) + 1;
   uint hShift = 256 - lShift;

   uint e = ((h << hShift) + (l >> lShift)) / shiftedZ;
   if (lShift > zShift) e <<= (lShift - zShift);
   else e >>= (zShift - lShift);

   r += e;

   (uint tl, uint th) = fullMul (e, z);
   h -= th;
   if (tl > l) h -= 1;
   l -= tl;
 }

 r += l / z;
}

Aqui mostSignificantBité uma função que retorna a posição, a partir de zero, do bit mais significante do argumento. Essa função pode ser implementada como a seguir:

function mostSignificantBit (uint x) public pure returns (uint r) {
 require (x > 0);

 if (x >= 2**128) { x >>= 128; r += 128; }
 if (x >= 2**64) { x >>= 64; r += 64; }
 if (x >= 2**32) { x >>= 32; r += 32; }
 if (x >= 2**16) { x >>= 16; r += 16; }
 if (x >= 2**8) { x >>= 8; r += 8; }
 if (x >= 2**4) { x >>= 4; r += 4; }
 if (x >= 2**2) { x >>= 2; r += 2; }
 if (x >= 2**1) { x >>= 1; r += 1; }
}

O código acima é bem complicado e provavelmente deveria ser explicado, mas vamos pular as explicações por agora e focar numa pergunta diferente. O problema com esse código é que ele consome 2,5k gas por chamada da função mulDiv, o que é muito. Então,

Podemos fazer isso mais barato

Spoiler: Matemágica!

O código abaixo é baseado em achados matemáticos emocionantes descritos por Remco Bloemen. Por favor, aplauda seus artigos de “matemágica” se você gostar deste código.

Primeiramente, nós reescrevemos a função fullMul:

function fullMul (uint x, uint y)
public pure returns (uint l, uint h)
{
 uint mm = mulmod (x, y, uint (-1));
 l = x * y;
 h = mm - l;
 if (mm < l) h -= 1;
}

Isso economiza 250 gas por chamada de fullMul.

Então nós reescrevemos a função mulDiv:

function mulDiv (uint x, uint y, uint z)
public pure returns (uint) {
 (uint l, uint h) = fullMul (x, y);
 require (h < z);

 uint mm = mulmod (x, y, z);
 if (mm > l) h -= 1;
 l -= mm;

 uint pow2 = z & -z;
 z /= pow2;
 l /= pow2;
 l += h * ((-pow2) / pow2 + 1);

 uint r = 1;
 r *= 2 - z * r;
 r *= 2 - z * r;
 r *= 2 - z * r;
 r *= 2 - z * r;
 r *= 2 - z * r;
 r *= 2 - z * r;
 r *= 2 - z * r;
 r *= 2 - z * r;

 return l * r;
}

Essa implementação consome apenas 550 gas por invocação de mulDiv e pode ser mais otimizado. Cinco vezes melhor do que a abordagem de matemática de escola. Muito Bom! Mas alguém teria de ter PhD em matemática para escrever código dessa maneira, e nem todo problema tem uma solução matemágica. Coisas seriam muito mais simples se pudéssemos

Usar Números de Ponto Flutuante em Solidity

Como nós já dissemos no começo desse artigo, em JavaScript alguém poderia simplesmente escrever a * b /c e a linguagem lidaria com o resto. E se pudéssemos fazer o mesmo em Solidity?

Na verdade nós podemos. Enquanto a linguagem não suporte ponto flutuante, existem bibliotecas que suportam. Por exemplo, com a biblioteca ABDKMathQuad alguém pode escrever:

function mulDiv (uint x, uint y, uint z)
public pure returns (uint) {
 return
   ABDKMathQuad.toUInt (
     ABDKMathQuad.div (
       ABDKMathQuad.mul (
         ABDKMathQuad.fromUInt (x),
         ABDKMathQuad.fromUInt (y)
       ),
       ABDKMathQuad.fromUInt (z)
     )
   );
}

Não tão elegante como JavaScript, não tão barato como a solução matemágica (e ainda mais cara que a abordagem de matemática escolar), mas direto e bem preciso, pois os números de ponto flutuante usados aqui tem 33 decimais.

Mais da metade do consumo de gas dessa implementação é usado para converter valores uint em valores de ponto flutuante e vice-versa, e o cálculo de proporção sozinho consome mais ou menos 1,4k gas. Portanto, usar números de ponto flutuante por todo o smart contract pode ser significantemente mais barato que misturar inteiros e números de ponto flutuante.

Conclusão

Porcentagens e proporções podem ser desafiadoras em Solidity por causa de overflow e falta de suporte para frações. No entanto, vários truques matemáticos permitem resolver proporções corretamente e eficientemente.

Números de ponto flutuante suportados por bibliotecas podem deixar a vida mais fácil ao custo de gas e precisão.

No nosso próximo artigo nós vamos mais fundo na matemática financeira, pois o próximo tópico vai ser: juros compostos.

Outros artigos nesta série:

· Parte 1: Números
· Parte 2: Overflow

· Part 4: Juros Compostos
· Part 5: Exponenciação e Logaritmos