https://gitlab.com/tezos/tezos
Tip revision: 13952298705129c6de6139a940a2a20c90e6fa67 authored by Pierrick Couderc on 24 January 2024, 11:44:08 UTC
EVM/Bench: make erc1155 take more than 4M gas
EVM/Bench: make erc1155 take more than 4M gas
Tip revision: 1395229
polynomial-arithmetic.md
- Polynomial representation
```
a(X) = a_{n-1} * X^{n-1} + ... + a_1 * X + a_0
```
- The **coefficient** representation
- a **dense** representation stores zero coefficients explicitly and exponents implicitly
- e.g., `a = [a_0; a_1; ...; a_{n-1}]`
- a **sparse** representation doesn't store zero coefficients at all, but stores exponents explicitly
- e.g., `a = [(a_0, 0); (a_1, 1); ...; (a_{n-1}, n-1)]` where `a_i <> zero for i = 0..(n-1)`
- The **evaluation** representation `[a(one); a(g); a(g^2); ..; a(g^{n-1})]`, where
- `g` is a primitive `n`-th root of unity, i.e., `g^n = one` and `g^i <> one` for `i=1..(n-1)`
- domain = `[one; g; g^2; g^3; ..; g^{n-1}]`, `n > 0`
- Converting between the coefficient and evaluation representations of a polynomial `a`
- size of domain must be a power of two
- `evaluation_fft`: `[a_0; a_1; ...; a_{n-1}]` -> `[a(one); a(g); a(g^2); ..; a(g^{n-1})]`
- `interpolation_fft`: `[a(one); a(g); a(g^2); ..; a(g^{n-1})]` -> `[a_0; a_1; ...; a_{n-1}]`
- Some reading
- https://zcash.github.io/halo2/background/polynomials.html
- https://vitalik.ca/general/2019/05/12/fft.html
- https://dsprenkels.com/ntt.html
- https://maths-people.anu.edu.au/~brent/pd/mca-cup-0.5.9.pdf (Section 2.3)
- The degree of the polynomial is the highest exponent occurring in the polynomial
- e.g., if `a_{n-1} <> 0` then the degree of `a` is `(n-1)`
- **special case**: the degree of the zero polynomial is either left undefined, or is defined to be negative (usually, `-1`)
- Polynomial equality, `n >= m`
```
a_{n-1} ............... a_1 a_0 | a
b_{m-1} ... b_1 b_0 | b
```
```
a == b <==> (a_i = b_i for i = 0..(m-1) /\ a_i = zero for i = m..(n-1))
```
- Polynomial addition, `n >= m`
```
a_{n-1} ............... a_1 a_0 | a
b_{m-1} ... b_1 b_0 | b
------------------------------- |---
c_{n-1} ............... c_1 c_0 | c
```
```
c_i = a_i + b_i, for i = 0..(m-1)
c_i = a_i, for i = m..(n-1)
```
- Polynomial subtraction, `n >= m`
```
a_{n-1} ............... a_1 a_0 | a
b_{m-1} ... b_1 b_0 | b
------------------------------- |---
c_{n-1} ............... c_1 c_0 | c
```
```
c_i = a_i - b_i, for i = 0..(m-1)
c_i = a_i, for i = m..(n-1)
```
- Polynomial subtraction, `n < m`
```
a_{n-1} ... a_1 a_0 | a
b_{m-1} ............... b_1 b_0 | b
------------------------------- |---
c_{m-1} ............... c_1 c_0 | c
```
```
c_i = a_i - b_i, for i = 0..(n-1)
c_i = - b_i, for i = n..(m-1)
```
- Polynomial multiplication; **Requires for `mul`:** initialize `c` with zeros
```
a_{n-1} ........................ a_1 a_0 | a
b_{m-1} ....... b_1 b_0 | b
------------------------------------------------ |---
a_{n-1}*b_0 ................... a_1*b_0 a_0*b_0 | a*b_0
a_{n-1}*b_1 ....................... a_1*b_1 a_0*b_1 | a*b_1*X
.....
a_{n-1}*b_{m-1} ...................................a_0*b_{m-1} | a*b_{m-1}*X^{m-1}
----------------------------------------------------------------------------------- |---
c_{n+m-2} ......... c_{n-1} ............. c2 c_1 c_0 | c
```
```
c_{i+j} += a_i * b_j for i = 0..(n-1) and j = 0..(m-1)
```
- Multiplying a polynomial `a` by a scalar `b`
```
a_{n-1} ............... a_1 a_0 | a
b_0 | b
------------------------------- |---
c_{n-1} ............... c_1 c_0 | c
```
```
c_i = a_i * b_0 for i = 0..(n-1)
```
- Checking whether a polynomial is the zero polynomial
```
a_{n-1} ............... a_1 a_0 | a
```
```
a = poly_zero <==> a_i = zero for i = 0..(n-1)
```
- Polynomial evaluation
```
a(X) = a_{n-1} * X^{n-1} + .. + a_1 * X + a_0
```
can be computed as follows
```
a(X) = ((..(a_{n-1} * X + a_{n-2}) * X + ...) * X + a_1) * X + a_0
```
- Dividing a polynomial `a` by `(X^n + c)`. **Note** that by definition R(X) is either equal to zero or degree R(X) < n.
```
(X^n + c) * (b_{l-n-1} * X^{l-n-1} + .. + b_1 * X + b_0) + R(X) = a_{l-1} * X^{l-1} + .. + a_1 * X + a_0
```
**Case 1:** `l-n-1 >= n`, i.e., `l-1 >= 2n`
```
lhs: b_{l-n-1} * X^{l-1} + .. + b_1 * X^{n+1} + b_0 * X^n + c*b_{l-n-1} * X^{l-n-1} + .. + c*b_1 * X + c*b_0 + R(X)
X^{l-1} .... X^{l-n} | X^{l-n-1} ... X^n | X^{n-1} ... X^1 X^0
---------------------------------------------------------------------------
a_{l-1} ... a_{l-n} | a_{l-n-1} ... a_n | a_{n-1} ... a_1 a_0
---------------------------------------------------------------------------
`+` b_{l-n-1} ... b_{l-2n} | b_{l-2n-1} b_0 | 0 .... 0 0
`+` 0 .... 0 | c*b_{l-n-1} ... c*b_n | c*b_{n-1} ... c*b_1 c*b_0
`+` 0 .... 0 | 0 ... 0 | r_{n-1} ... r_1 r_0
---------------------------------------------------------------------------
```
- quotient
```
a_i = b_{i-n} for i in [l-n; l-1] <==> b_i = a_{i+n} for i in [l-2n; l-n-1]
a_i = b_{i-n} + c*b_i for i in [n; l-n-1] ==> b_{i-n} = a_i - c*b_i <==> b_i = a_{i+n} - c*b_{i+n} for i in [l-2n-1; 0]
```
- remainder R(X)
```
a_i = r_i + c*b_i for i in [0; n-1] ==> r_i = a_i - c*b_i for i in [0; n-1]
```
**Case 2:** `l-n-1 < n`, i.e., `l-1 < 2n` (but `n <= l-1`)
```
lhs: b_{l-n-1} * X^{l-1} + .. + b_1 * X^{n+1} + b_0 * X^n + c*b_{l-n-1} * X^{l-n-1} + .. + c*b_1 * X + c*b_0 + R(X)
X^{l-1} ..... X^n | X^{n-1} ... X^{l-n} | X^{l-n-1} ... X^1 X^0
------------------------------------------------------------------------------
a_{l-1} ..... a_n | a_{n-1} ... a_{l-n} | a_{l-n-1} ... a_1 a_0
------------------------------------------------------------------------------
`+` b_{l-n-1} ... b_0 | 0 ... 0 | 0 ... 0 0
`+` 0 .... 0 | 0 ... 0 | c*b_{l-n-1} ... c*b_1 c*b_0
`+` 0 .... 0 | r_{n-1} r_{l-n} | r_{l-n-1} ... r_1 r_0
------------------------------------------------------------------------------
```
- quotient
```
a_i = b_{i-n} for i in [n; l-1] <==> b_i = a_{i+n} for i in [0; l-n-1]
```
- remainder R(X)
```
a_i = r_i + c*b_i for i in [0; l-n-1] ==> r_i = a_i - c*b_i for i in [0; l-n-1]
r_i = a_i for i in [l-n; n-1]
```
- Multiplying a polynomial `a` by `(X^n + c)`
```
(X^n + c) * (a_{l-1} * X^{l-1} + .. + a_1 * X + a_0) = b_{l+n-1} * X^{l+n-1} + .. + b_2 * X^2 + b_1 * X + b_0
```
**Case 1:** `l-1 >= n`
```
lhs: a_{l-1} * X^{n+l-1} + .. + a_1 * X^{n+1} + a_0 * X^n + c*a_{l-1} * X^{l-1} + .. + c*a_1 * X + c*a_0
X^{l+n-1} ...| X^{l-1} .......X^n |... X^1 X^0
-----------------------------------------------------
b_{l+n-1} ...| b_{l-1} .......b_n |.... b_1 b_0
-----------------------------------------------------
`+` a_{l-1} .. | a_{l-n-1} .. a_0 | 0 0 ..... 0
`+` 0 .... 0 0 | c*a_{l-1} .. c*a_n |... c*a_1 c*a_0
-----------------------------------------------------
```
```
b_i = c*a_i for i in [0; n-1]
b_i = a_{i-n} + c*a_i for i in [n; l-1]
b_i = a_{i-n} for i in [l; l+n-1]
```
**Case 2:** `l-1 < n`
```
lhs: a_{l-1} * X^{n+l-1} + .. + a_1 * X^{n+1} + a_0 * X^n + c*a_{l-1} * X^{l-1} + .. + c*a_1 * X + c*a_0
X^{l+n-1} ... X^n | X^{n-1} ...... X^l | X^{l-1} ... X^1 X^0
--------------------------------------------------------------------
b_{l+n-1} ... b_n | b_{n-1} ...... b_l | b_{l-1} ... b_1 b_0
--------------------------------------------------------------------
`+` a_{l-1} .. a_0 | 0 0 ... 0 | 0 ... 0 0
`+` 0 .... 0 | 0 .... 0 | c*a_{l-1} .. c*a_1 c*a_0
--------------------------------------------------------------------
```
```
b_i = c*a_i for i in [0;l-1]
b_i = 0 for i in [l; n-1]
b_i = a_{i-n} for i in [n; l+n-1]
```
## Arithmetic of polynomials evaluated on `domain`
- Rescale evaluations
- `[g^0; g^1; ..; g^{k*n-1}]` -> `[g'^0; g'^1; ..; g'^{n-1}]`
- `step = k*n/n = k`
- `g'^j = g^{j*k}` for `j=0..(n-1)`
- [Proof: `g'^j = e^{2*j*pi*i/n} = e^{2*(j*k)*pi*i/k*n} = g^{j*k}`]
- `eval_out[j] = eval_in[j*step]`
- `composition_gx` computes `a(g^i*x)`, i.e., this is an evaluation of polynomial `a` at point `g^i*x`
- `x = g^k` ==> `a(g^i*g^k) = a(g^(i+k))`
- `eval_out[j] = eval_in[(j+i) % eval_len]`
- [Proof: as `g^eval_len = one`, `g^{j+i} = g^{(j+i) % eval_len}`]
- Addition of polynomials evaluated on `domain`
- `c(x) = a(x) + b(x) <==> eval_c[domain_i] = eval_a[domain_i * step_a] + eval_b[domain_i * step_b]`
- degree of c(x) = max(degree of a(x), degree of b(x))
- size of eval_c = min(size of eval_a, size of eval_b) [NOTE: degree of c(x) <= size of eval_c]
- step_a = size of eval_a / size of eval_c
- step_b = size of eval_b / size of eval_c
- Multiplication of a polynomial evaluated on `domain` by a scalar
- `c(x) = lambda * a(x) <==> eval_c[domain_i] = lambda * eval_a[domain_i]`
- degree of c(x) = degree of a(x)
- size of eval_c = size of eval_a
- Multiplication of polynomials evaluated on `domain`
- `c(x) = a(x) * b(x) <==> eval_c[domain_i] = eval_a[domain_i * step_a] * eval_b[domain_i * step_b]`
- degree of c(x) = degree of a(x) + degree of b(x)
- size of eval_c = min(size of eval_a, size of eval_b) [NOTE: degree of c(x) <= size of eval_c]
- step_a = size of eval_a / size of eval_c
- step_b = size of eval_b / size of eval_c
- `linear` computes `c(x) = lambda_0 * p_0(g^l_0*x) + lambda_1 * p_1(g^l_1*x) + .. + lambda_k * p_k(g^l_k*x) + constant`
```
c(g^0) = lambda_0 * p_0(g^l_0*g^0) + ... + lambda_k * p_k(g^l_k*g^0) + constant
c(g^1) = lambda_0 * p_0(g^l_0*g^1) + ... + lambda_k * p_k(g^l_k*g^1) + constant
...
c(g^{n-1}) = lambda_0 * p_0(g^l_0*g^{n-1}) + ... + lambda_k * p_k(g^l_k*g^{n-1}) + constant
```
- we don't go from `c(g^0)` to `c(g^{n-1})`, instead we accumulate the sum from `lambda_0 * p_0(g^l_0*x)` to `lambda_k * p_k(g^l_k*x)`
- degree of c(x) = max(degree of p_i(x))
- size of eval_c = min(size of eval_p_i) [NOTE: degree of c(x) <= size of eval_c]
- step_p_i = size of eval_p_i / size of eval_c
```
eval_c(domain_i) =
lambda_0 * eval_p_0((domain_i + l_0) * step_p_0 % eval_p_0_len)
+ lambda_1 * eval_p_1((domain_i + l_1) * step_p_1 % eval_p_1_len)
+ ...
+ lambda_k * eval_p_k((domain_i + l_k) * step_p_k % eval_p_k_len) + constant
```
- `mul` computes `c(x) = p_0(g^l_0*x)^m_0 * p_1(g^l_1*x)^m_1 * ... * p_k(g^l_k*x)^m_k`
```
c(g^0) = p_0(g^l_0*g^0)^m_0 * p_1(g^l_1*g^0)^m_1 * ... * p_k(g^l_k*g^0)^m_k
c(g^1) = p_0(g^l_0*g^1)^m_0 * p_1(g^l_1*g^1)^m_1 * ... * p_k(g^l_k*g^1)^m_k
...
c(g^{n-1}) = p_0(g^l_0*g^{n-1})^m_0 * p_1(g^l_1*g^{n-1})^m_1 * ... * p_k(g^l_k*g^{n-1})^m_k
```
- we don't go from `c(g^0)` to `c(g^{n-1})`, instead we accumulate the product from `p_0(g^l_0*x)^m_0` to `p_k(g^l_k*x)^m_k`
- degree of c(x) = `m_0 * degree of p_0 + ... + m_k * degree of p_k`
- size of eval_c = min (size of eval_p_i) [NOTE: degree of c(x) <= size of eval_c]
- step_p_i = size of eval_p_i / size of eval_c
```
eval_c(domain_i) =
eval_p_0((domain_i + l_0) * step_p_0 % eval_p_0_len)^m_0
* eval_p_1((domain_i + l_1) * step_p_1 % eval_p_1_len)^m_1
* ...
* eval_p_k((domain_i + l_k) * step_p_k % eval_p_k_len)^m_k
```