Kate, Zaverucha and Goldberg introduced a constantsized polynomial commitment scheme in 2010^{1}. We refer to this scheme as KZG and quickly introduce it below.
Prerequisites:
 Cyclic groups of prime order and finite fields $\Zp$
 Pairings (or bilinear maps)
 Polynomials
Trusted setup
To commit to degree $\le \ell$ polynomials, need $\ell$SDH public parameters: \((g,g^\tau,g^{\tau^2},\dots,g^{\tau^\ell}) = (g^{\tau^i})_{i\in[0,\ell]}\)
Here, $\tau$ is called the trapdoor. These parameters should be generated via a distributed protocol^{2}$^,$^{3}$^,$^{4} that outputs just the $g^{\tau^i}$’s and forgets the trapdoor $\tau$.
The public parameters are updatable: given $g^{\tau^i}$’s, anyone can update them to $g^{\alpha^i}$’s where $\alpha = \tau + \Delta$ by picking a random $\Delta$ and computing: \(g^{\alpha^i} = \left(g^{\tau^i}\right)^{\Delta^i}\)
This is useful when you want to safely reuse a pregenerated set of public parameters, without trusting that nobody knows the trapdoor.
Commitments
Commitment to $\phi(X)=\sum_{i\in[0,d]} \phi_i X^i$ is $c=g^{\phi(\tau)}$ computed as:
\[c=\prod_{i\in[0,\deg{\phi}]} \left(g^{\tau^i}\right)^{\phi_i}\]Since it is just one group element, the commitment is constantsized.
Evaluation proofs
To prove an evaluation $\phi(a) = y$, a quotient polynomial is computed in $O(d)$ time:
\[q(X) = \frac{\phi(X)  y}{X  a}\]Then, the constantsized evaluation proof is:
\[\pi = g^{q(\tau)}\]Note that this leverages the polynomial remainder theorem.
Verifying an evaluation proof
A verifier who has the commitment $c=g^{\phi(\tau)}$, the evaluation $y=\phi(a)$ and the proof $\pi=g^{q(\tau)}$ can verify the evaluation in constanttime using two pairings:
\begin{align}
e(c / g^y, g) &= e(\pi, g^\tau / g^a) \Leftrightarrow\\
e(g^{\phi(\tau)y}, g) &= e(g^{q(\tau)}, g^{\taua}) \Leftrightarrow\\
e(g,g)^{\phi(\tau)y} &= e(g,g)^{q(\tau)(\taua)}\\
\phi(\tau)y &= q(\tau)(\taua)
\end{align}
This effectively checks that $q(X) = \frac{\phi(X)  y}{Xa}$ by checking this equality holds for $X=\tau$. In other words, it checks that the polynomial remainder theorem holds at $X=\tau$.
Batch proofs
One can prove multiple evaluations $(\phi(e_i) = y_i)_{i\in I}$ for arbitrary points $e_i$ using a constantsized KZG batch proof $\pi_I = g^{q_I(\tau)}$, where:
\begin{align}
\label{eq:batchproofrel}
q_I(X) &=\frac{\phi(X)R_I(X)}{A_I(X)}\\
A_I(X) &=\prod_{i\in I} (X  e_i)\\
R_I(e_i) &= y_i,\forall i\in I\\
\end{align}
$R_I(X)$ can be interpolated via Lagrange interpolation in $O(\vert I\vert\log^2{\vert I\vert})$ time^{5} as:
\begin{align} R_I(X)=\sum_{i\in I} y_i \prod_{j\in I,j\ne i}\frac{X  e_j}{e_i  e_j} \end{align}
$A_I(X)$ can be computed in $O(\vert I \vert \log^2{\vert I \vert})$ time via a subproduct tree in $O(\vert I\vert\log^2{\vert I\vert})$ time^{5}, as depicted below (for $\vert I \vert = 8$). The computation proceeds downwards, in the direction of the arrows, with the $(Xe_i)$ monomials being computed first.
Each node in the subproduct tree multiplies the polynomials stored in its two children nodes. This way, the root polynomial will be exactly $A_I(X)$. If FFTbased multiplication is used, the time to compute a subproduct tree of size $n$ is:
\begin{align}
T(n) &= 2T(n/2) + O(n\log{n})\\
&= O(n\log^2{n})
\end{align}
Observation 1: I believe computing $A_I(X)$ faster for arbitrary points $e_i$ is not possible, but I would be happy to be contradicted!
Observation 2: In practice, the algorithms for computing $R_I(X)$ and $A_I(X)$ efficiently would require FFTbased techniques for polynomial division and multiplication, and FFTs are fastest when the finite field $\Zp$ is endowed with $d$th roots of unity for sufficiently high $d$, on the order of the degrees of $R_I(X)$ and $A_I(X)$.
Verifying a batch proof
The verifier who has the commitment $c$, the evaluations $(e_i, y_i)_{i\in I}$ and a batch proof $\pi_I=g^{q_I(\tau)}$ can verify them as follows.
 First, he interpolates the accumulator polynomial \(A_I(X)=\prod_{i\in I} (Xe_i)\) as discussed above. Then, commits to in $O(\vert I \vert)$ time: \begin{align} a &= g^{A_I(\tau)} \end{align}
 Second, he interpolates $R_I(X)$ s.t. $R_I(e_i)=y_i,\forall i \in I$ as discussed above. Then, commits to in $O(\vert I \vert)$ time: \begin{align} r &= g^{R_I(\tau)} \end{align}
 Third, he checks Equation \ref{eq:batchproofrel} holds at $X=\tau$ using two pairings: $e(c / r, g) = e(\pi_I, a)$.
Note that:
\begin{align}
e(g^{\phi(\tau)} / g^{R_I(\tau)}, g) &= e(g^{q_I(\tau)}, g^{A_I(\tau)})\Leftrightarrow\\
e(g^{\phi(\tau)  R_I(\tau)}, g) &= e(g,g)^{q_I(\tau) A_I(\tau)}\Leftrightarrow\\
\phi(\tau)  R_I(\tau) &= q_I(\tau) A_I(\tau)
\end{align}
Aggregation of proofs
For now, we discuss proof aggregation in a different blog post on building vector commitments (VCs) from KZG.
Applications
There are many cryptographic tools one can build using polynomial commitment schemes such as KZG.
Here’s a few we’ve blogged about in the past:
 Cryptographic accumulators
 Vector Commitments (VC) schemes with $O(\log{n})$sized proofs or with $O(1)$sized proofs
 Range proofs
Acknowledgements
Many thanks to Shravan Srinivasan and Philipp Jovanovic for really helping improve this post.

Polynomial commitments, by Kate, Aniket and Zaverucha, Gregory M and Goldberg, Ian, 2010, [URL] ↩

Secure Sampling of Public Parameters for Succinct Zero Knowledge Proofs, by E. BenSasson and A. Chiesa and M. Green and E. Tromer and M. Virza, in 2015 IEEE Symposium on Security and Privacy, 2015 ↩

A Multiparty Protocol for Constructing the Public Parameters of the Pinocchio zkSNARK, by Bowe, Sean and Gabizon, Ariel and Green, Matthew D., in Financial Cryptography and Data Security, 2019 ↩

Scalable Multiparty Computation for zkSNARK Parameters in the Random Beacon Model, by Sean Bowe and Ariel Gabizon and Ian Miers, 2017, [URL] ↩

Fast polynomial evaluation and interpolation, by von zur Gathen, Joachim and Gerhard, Jurgen, in Modern Computer Algebra, 2013 ↩ ↩^{2}