Polynomial commitment schemes
$$ \gdef\F{\mathbb{F}} \gdef\G{\mathbb{G}} \gdef\g{\mathrm{G}} \gdef\h{\mathtt{H}} \gdef\e{\mathrm{e}} $$
I will discuss polynomial commitment schemes for $n$term polynomials, so polynomials of degree at most $n1$.
A polynomial commitment scheme for $n$term polynomials two scheme has two operations. Given $f ∈ \F_{<n}[X]$ the operation $\mathrm{commit}(f)$ produces a commitment $c$ to $f$. Given commitments $c_i$ and evaluation points $(x_{i,j}, y_{i,j})$ the $\mathrm{open}$ operation proofs that $f_i(x_{i,j}) = y_{i,j}$.
KZG
Let $\G_1$, $\G_2$, $\G_3$ be elliptic curve groups with the same scalar field $\F$, generators $\g_1$, $\g_2$, $\g_3$ and a pairing $\e: \G_1 × \G_2 → \G_3$. For more background see here
KateZaveruchaGoldberg
https://cacr.uwaterloo.ca/techreports/2010/cacr201010.pdf
https://eprint.iacr.org/2020/081.pdf
https://eprint.iacr.org/2020/1536.pdf
Trusted set up
During the trusted setup ceremony a secret value $τ ∈ \F$ is selected and the following "powers of tau" are computed for $i ∈ [0,n)$
$$ \vec X = \begin{bmatrix} τ^0 & τ^1 & τ^2 & ⋯ \end{bmatrix} ⋅ \g_2 $$
These values $X_i$ are known as the common reference string (CRS). These can get quite large, for $n = 2^{20}$.
The CRS is update able. Given a new secret value $s ∈ \F$ the updated values are $X_i' = s^i ⋅ X_i$.
Note. The $X_i$ act as a monomial basis for polynomials which is convenient if the polynomial we want to commit to is in coefficient form. Often, we instead have the the polynomial in point form $(x_i, y_i)$. We can then construct a basis of Langrange functions over the $x_i$'s:
$$ X_i' = todo $$
 https://zfnd.org/conclusionofthepowersoftauceremony/ https://medium.com/aztecprotocol/aztechowtheceremonyworks9f021cf190d0
To commit to a polynomial $P(X)$ we compute $P = P(τ) ⋅ \g_2$ using the basis.
One commitment, one value
To proof $P(x) = y$ we compute following is polynomial
$$ Q(X) = \frac{P(X)  y}{X  x} $$
The proof is $Q = Q(τ) ⋅ \g_2$.
To verify, compute $Z = (τ  x) ⋅ \g_2$ and $R = y ⋅ \g_2$
$$ \e(P  R, \g_2) = \e(Q, Z) $$
$$ \begin{aligned} \e(P  R, \g_2) &= \e(Q, Z) \\ \e(P(τ) ⋅ \g_2  y ⋅ \g_2, \g_2) &= \e(Q(τ) ⋅ \g_2, (τ  x) ⋅ \g_2) \\ (P(τ)  y) ⋅ \e(\g_2, \g_2) &= Q(τ) ⋅ (τ  x) ⋅ \e(\g_2, \g_2) \\ P(τ)  y &= Q(τ) ⋅ (τ  x) \\ \end{aligned} $$
Then due to the SchwarzSippl lemma it is cryptographically likely that $P(X)  y = Q(X) ⋅ (X  x)$.
Many commitments, many values
Given many commitments $P_i$ as above, for each we want to proof a set of values $P_i(x_{ij}) = y_{ij}$. Define $S_i = \set{x_{ij}}$, $S = \Union S_i$.
Zero polynomials
$$ Z_{\mathcal S}(X) = \prod_{s ∈ S} \p{X  s} $$
Lagrange polynomials
$$ L_{ij}(X) = \frac{Z_{S_i \setminus \set{x_j}}(X)}{Z_{S_i \setminus \set{x_j}}(x_j)} $$
Interpolating polynomials
$$ R_i(X) = \sum_j y_{ij} ⋅ L_{ij}(X) $$
The verifiers sends a random $u ∈ \F$.
The prover computes
$$ Q(X) = \sum_i u^i ⋅\frac{P_i(X)  R_i(X)}{Z_{S_i}(X)} $$
The prover sends $Q(τ) ⋅ \G_2$ The verifier checks
$$ \sum_i \e(u^i ⋅ (P_i  R_i), Z_{S \setminus S_i}(τ) ⋅ \g_2) = \e(Q, Z_S(τ) ⋅ \g_2) $$
Variant
$\bar S_i = S \setminus S_i$
The verifiers sends a random $u ∈ \F$.
Prover computers
$$ P(X) = \frac{1}{Z_{S}(X)} ⋅ \sum_i u^i ⋅ (P_i(X)  R_i(X)) ⋅ Z_{\bar S_i}(X) $$
this equals
$$ P(X) = \sum_i u^i ⋅ \frac{P_i(X)  R_i(X)}{Z_{S_i}(X)} $$
The prover sends $P(τ) ⋅ \G_2$. The verifier sends random $z ∈ \F$.
$$ L(X) = \sum_i u^i ⋅ (P_i(X)  R_i(z)) ⋅ Z_{\bar S_i}(z)  Z_S(z) ⋅ P(X) $$
and
$$ W(X) = \frac{L(X)}{Z_{\set z}(X)} $$
$$ W(X) = \frac{Z_S(z)}{Z_{\set z}(X)} ⋅\p{ \sum_i u^i ⋅ \frac{P_i(X)  R_i(z)}{Z_{S_i}(z)}  P(X) } $$
$$ W(X) = \frac{Z_S(z)}{Z_{\set z}(X)} ⋅ \sum_i u^i ⋅ \p{ \frac{P_i(X)  R_i(z)}{Z_{S_i}(z)}  \frac{P_i(X)  R_i(X)}{Z_{S_i}(X)} } $$
and sends $W(τ) ⋅ \G_2$.
The verifier computes
$$ F = \sum_i u^i ⋅ Z_{\bar S_i}(z) ⋅ \p{P_i  r_i(z) ⋅ \G_2}  Z_S(z) ⋅ W $$
and checks
$$ \e\p{F + z ⋅ W, \G_2} = \e\p{W, τ ⋅ \G_2} $$
$$ \begin{aligned} \e\p{F + z ⋅ W, \G_2} &= \e\p{W, τ ⋅ \G_2} \\ \sum_i u^i ⋅ Z_{\bar S_i}(z) ⋅ \p{P_i(τ)  r_i(z)}  Z_S(z) ⋅ W(τ) + z ⋅ W(τ) &= W(τ) ⋅ τ \\ \sum_i u^i ⋅ Z_{\bar S_i}(z) ⋅ \p{P_i(τ)  r_i(z)} &= W(τ) ⋅ τ + Z_S(z) ⋅ W(τ)  z ⋅ W(τ) \\ \sum_i u^i ⋅ Z_{\bar S_i}(z) ⋅ \p{P_i(τ)  r_i(z)} &= \p{τ  z + Z_S(z)} ⋅ W(τ) \\ \end{aligned} $$
FRI
Let $\h_{\mathcal S} : \mathcal I → \mathcal S$ be a hash function mapping some input set $\mathcal I$ to the output set $\mathcal S$. A superscript like $\h'$ is used to indicate two domain separated hash functions.
Inner product arguments
https://vitalik.ca/general/2021/11/05/halo.html
Halo turns the inner product argument from Bulletproofs into a polynomial commitment scheme.
Basically if we can commit to a vector $\vec p$ and proof $y = \inprod{\vec p}{\vec x}$ where $\vec x = \begin{bmatrix} 1, x, x^2, \dots \end{bmatrix}$.
Set up
Given elliptic curve group $\G$ with scalar field $\F$. Generate a common reference string of $G_i, H ∈ \G$ random elements.
Commit
Given a polynomial $P(X) = \sum_i c_i ⋅ X^i$, generate a random blinding factor $r ∈ \F$. The commitment is
$$ r ⋅ H + \sum_i c_i ⋅ G_i $$
Proof
To proof that $P(x) = v$:
The verifier sends a random $U ∈ \G$. Start with
$$ \begin{aligned} \vec a &= \begin{bmatrix} c_0, c_1, c_2, \dots \end{bmatrix} & \vec b &= \begin{bmatrix} 1, x, x^2, \dots \end{bmatrix} & \vec G &= \begin{bmatrix} G_0, G_1, G_2, \dots \end{bmatrix} \end{aligned} $$
The prover sends $L, R$ as
$$ \begin{aligned} L &= \inprod{\vec a_{\mathrm{lo}}}{\vec G_{\mathrm{hi}}} + l ⋅ H + \inprod{\vec a_{\mathrm{lo}}}{ \vec b_{\mathrm{hi}}} ⋅ U \\ R &= \inprod{\vec a_{\mathrm{hi}}}{\vec G_{\mathrm{lo}}} + r ⋅ H + \inprod{\vec a_{\mathrm{hi}}}{ \vec b_{\mathrm{lo}}} ⋅ U \\ \end{aligned} $$
The verifier issues a random $u ∈ \F$. The prover computes
$$ \begin{aligned} \vec a' &= \vec a_{\mathrm{hi}} ⋅ u^{1} + \vec a_{\mathrm{lo}} ⋅ u \\ \vec b' &= \vec b_{\mathrm{hi}} ⋅ u^{1} + \vec b_{\mathrm{lo}} ⋅ u \\ \vec G' &= \vec G_{\mathrm{hi}} ⋅ u^{1} + \vec G_{\mathrm{lo}} ⋅ u \\ \end{aligned} $$
TODO: Halo paper has hi, lo reversed for b, G.
Repeat until $\vec a$, $\vec b$ and $\vec G$ are a single element. The prover sends these over and the verifier computes
$$ Q = \sum_i u_i^2 ⋅L_i + P' + \sum_i u_i^{2} ⋅ R_i $$
and
$$ r' = \sum_i u_i^2 ⋅ l_i + P' + \sum_i u_i^{2} ⋅ r_i $$
and checks
$$ Q = a ⋅ G + r' ⋅ H + a ⋅ b ⋅ U $$
https://zcash.github.io/halo2/background/pcipa.html
https://zcash.github.io/halo2/design/provingsystem/innerproduct.html
https://eprint.iacr.org/2017/1066.pdf
https://eprint.iacr.org/2017/1132.pdf
https://eprint.iacr.org/2019/953.pdf
https://eprint.iacr.org/2019/1021.pdf
Aurora https://eprint.iacr.org/2018/828.pdf Section 8
Other schemes

Dory

Dark
References
https://vitalik.ca/general/2017/01/14/exploring_ecp.html
https://dankradfeist.de/ethereum/2020/06/16/katepolynomialcommitments.html
https://alinush.github.io/2020/05/06/kzgpolynomialcommitments.html#fn:KZG10e
https://arnaucube.com/blog/kzgcommitments.html
https://arnaucube.com/blog/kzgbatchproof.html
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf
https://eprint.iacr.org/2017/1132.pdf