$$ \def\set#1{{#1}} \def\p#1{(#1)} \def\F{\mathbb{F}} \def\G{\mathbb{G}} \def\g{\mathrm{G}} \def\H{\mathsf{H}} \def\S{\mathcal{S}} \def\HF{\H_{\F}} \def\HG{\H_{\G}}

Worldcoin $10^9$ UBI Sybil resitance -> Iris based biometrics Privacy preserving proof of personhood WorldID <id.woldcoin.org> Semaphore EF PSE project. Circom.

$$ \def\F{\mathbb F} \def({\left (} \def){\right )} \def\norm#1{\left\vert #1 \right\vert} \def\set#1{\mathcal{#1}} $$ See the Plonk paper https://eprint.iacr.org/2019/953. Here follow some meditations on chapter 5 and appendix A.

Definition. (Fill function) A fill function $f$ specifies how much of a desired asset we can maximally get for a given amount of the provided asset. Lemma. (Monotonicity) Fill functions are monotonic. If a fill function provided more of the desired asset for fewer of the provided, we can simply provide it fewer. Problem. Given a maker asset amount $x$ and a set of fill functions $f_i$, we want to partition $x$ into $x_i$ to maximize. $$ g(x) = \max_{\vec x} , \sum_i f_i(x_i) \text{ subject to } \sum_i x_i \le x \text{ and } x_i \ge 0 $$

$$ \def\O{\mathcal O} \def\F{\mathbb F} $$ Context. We are given a prime field $\F_p$, a size parameter $n$ and the following: $\log_2 p > 250$ (the prime is of cryptographic size), $2^n ,\vert, p - 1$ (the field has roots of unity $\omega_n$). $n = 2^k < 2^{28}$ (we can realistically compute operations that ar $O(n \log n)$, but not $O(n ^2)$).

# Efficient patterns of zeros of certain polynomials ## Context In STARKs the computation is unrolled into a table: | $x$ | $P_1(x)$ | $P_2(x)$ | $\dots$ | $P_n(x)$ | |----|----|----|----|----| | $\omega^0$ | a | b | $\cdots$ | c | | $\omega^1$ | d | e | $\cdots$ | f | | $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ | $\vdots$ | | $\omega^{n-1}$ | g | h | $\cdots$ | i | Think of the columns as registers and the rows as sequential states in the computation. The columns in table are interpreted

# AIR Composibility ```rust struct AirComponent { trace: TraceTable, constraints: Vec<RationalExpression>, labels: Vec<(String, RationalExpression)> } ``` **Note.** Having labels on expressions allows direct labeling of trace cells using `Trace(i, j)`. But it also allows labeling derived values, for example if the constraints are written such that the 'real' value is the difference of two columns, the labeled output can be `Trace(i, j) - Trace(i, k)`. ## Trace generati

# L'Hospital rules in finite fields **Warning.** "I have only proved it correct, not tried it." $$ \def\F{\mathbb{F}} \def\diff#1{\frac{\delta}{\delta #1}} $$ Given $P,Q ∈ \F[X]$. Consider the fraction $$ \frac{P(X)}{Q(X)} $$ If this fraction is $\frac 00$ indeterminate in some value $𝛼 ∈ \F$, we can elliminate the zeros we found: $$ \frac{P(X)/(X - 𝛼)}{Q(X)/(X - 𝛼)} $$ If necessary we can repeat this untill the fraction is no longer indeterminate. In real numbers, there is an alterna

# Fast extrapolation from ⟨𝜔⟩ $$ \def\F{\mathbb F} $$ Given $P ∈ \F[X]$ with $\deg P < n$ and $𝜔$ a $n$-primitive root of unity. Evaluate $P$ on the subgroup generated by $𝜔$: $$ a_i = P(𝜔^i) $$ **Goal.** *Given only $a_i$ and arbitrary $z ∈ \F$, efficiently evaluate $P(z)$.* --- Observe the Lagrange basis for $⟨𝜔⟩$: $$ L_i(X) = c_i \frac{X^n - 1}{X-𝜔^i} $$ where $c_i$ is set such that $L_i(𝜔^j) = \delta_{ij}$ (i.e. one when $i=j$ and zero otherwise). Using [L'Hospital rule](https