Halo is a widely discussed zero-knowledge proof system known for its efficiency, recursive capabilities, and transparent setup. One of its core building blocks is the polynomial commitment scheme, which supports transparent parameters and enables logarithmic-size opening proofs. In this post, I’ll break down how this polynomial commitment scheme works, walk through a simple example to verify its correctness, and share some understandings on its design rationale.

The paper of Halo is titled "Recursive Proof Composition without a Trusted
Setup", the full version of this paper is at: https://eprint.iacr.org/2019/1021.

## Basic concepts
First, what is a Polynomial Commitment (PC) scheme?

In a PC scheme, a prover commits to a polynomial to a verifier. The commitment has the following features:

* Binding: The committed polynomial is fixed and cannot be changed later.
* Opening evaluation: The prover can later provide an opening proof showing the polynomial evaluates to a given value at a specific point.
* Succinctness: The verifier can check this proof more efficiently than evaluating the full polynomial directly.
* Hiding (optionally): The commitment can optionally hide the polynomial from the verifier or adversaries, depending on the use case.

## Syntax and Workflow
The general syntax for a PC scheme include four algorithms, which are separately Setup, Commit, Open, and Verify.

The setup algorithm is run by a trusted party or multi-party computation if the setup algorithm generates some secret randomness (trapdoor). If the setup algorithm does not generate any trapdoor, it is called a transparent setup then anyone can run this algorithm. The prover runs the commit algorithm to commit a polynomial, and the prover runs the open algorithm to prove that the commited polynomial evaluated to a specfic result at a certain point. The verifier runs the verify algorithm to check if the opening proof is valid.

* $\sigma \leftarrow {\sf Setup}(\lambda, d)$: The ${\sf Setup}$ algorithm takes input a security parameter $\lambda$ and a variable $d$, outputs a common reference string $\sigma$. $d$ indicates that the polynomial to be commited has a maximum degree $d-1$ and maximum $d$ coefficients.
* ${\sf com} \leftarrow {\sf Commit}(\sigma, p(X))$: The ${\sf Commit}$ algorithm takes input the common reference string $\sigma$, and a polynomial $p(X)$ to be commited, outputs a commitment ${\sf com}$.
* $\pi \leftarrow {\sf Open}(\sigma, {\sf com}, p(X), x, y)$: The ${\sf Open}$ algorithm takes input the common reference string $\sigma$, a commitment ${\sf com}$, a polynomial $p(X)$, a point $x$, and an evaluation result $y$ such that $p(x) = y$, outputs a opening proof $\pi$.
* $0/1 \leftarrow {\sf Verify}(\sigma, {\sf com}, \pi, x, v)$: The ${\sf Verify}$ algorithm takes input the common reference string $\sigma$, a commitment ${\sf com}$, a opening proof $\pi$, a point $x$ and a evaluation result $y$, outputs 1 if the proof $\pi$ is valid, or outputs 0 otherwise.

## The Halo PC scheme
Then for the PC scheme in Halo, it can be described by following the above syntax:

### Notation
Boldface variable names: vectors ($\mathbf{a}, \mathbf{b}, \mathbf{G}, ...$).
$g^a$ or $[a]g$: A single scalar.
$g^a \cdot g^b$ or $[a]g + [b]g$: A scalar multiplication.
$\langle \mathbf{a}, \mathbf{b} \rangle$: The inner product $a_1 b_1 + a_2 b_2 + \cdots a_n b_n$ of scalar vectors $\mathbf{a}, \mathbf{b} \in \mathbb{F}^{n}$.
$\langle \mathbf{a}, \mathbf{G} \rangle$: The multi-scalar multiplication $[a_1]g_1 + [a_2]g_2 + \cdots [a_n]g_n$ or $g_1^{a_1}g_2^{a_2} \cdots g_n^{a_n}$ of a scalar vector $\mathbf{a} \in \mathbb{F}^{n}$ and a vector or group elements $\mathbf{G} \in \mathbb{G}^n$
$\mathbf{a}_{lo}, \mathbf{b}_{lo}, \mathbf{G}_{lo}$: The first half of elements in vector $\mathbf{a}, \mathbf{b}, \mathbf{G}$ respectively.
$\mathbf{a}_{hi}, \mathbf{b}_{hi}, \mathbf{G}_{hi}$: The second half of elements in vector $\mathbf{a}, \mathbf{b}, \mathbf{G}$ respectively.

### Setup algorithm
$\sigma \leftarrow {\sf Setup}(\lambda, d)$:
Assume $d$ is the power of 2 and $𝑑=2^𝑘$, so $k = {log} \ d$.
Choose a group $\mathbb{G}$ of prime order $𝑝$, choose $\mathbb{F}_p$ as the scalar field of $\mathbb{G}$.
Choose a hash function $\mathcal{H}: \{0, 1\}^* \rightarrow \mathbb{Z}_p$.
Pick random group generators $\mathbf{G} =(𝑔_1,…,𝑔_𝑑) \in \mathbb{G}$ and $h \in \mathbb{G}$.
Output $𝜎=(\mathbb{G},\mathbb{F}_p, \mathcal{H}, \mathbf{𝐆}, h)$.

### Commit algorithm
${\sf com} \leftarrow {\sf Commit}(\sigma, p(X))$:
$\mathbf{a} = (𝑎_1,…,𝑎_𝑑)$, pick random $𝑟 \leftarrow 𝔽_𝑝$.
Compute $𝑃 = \langle \mathbf{a}, \mathbf{G} \rangle + [𝑟]h = 𝑔_1^{𝑎_1}𝑔_2^{𝑎_2} \cdots 𝑔_𝑑^{𝑎_𝑑} ℎ^𝑟$.
Output ${\sf com} = 𝑃$.

### Open algorithm
$\pi \leftarrow {\sf Open}(\sigma, {\sf com}, p(X), x, y)$:
$\mathbf{a} = (𝑎_1,…,𝑎_𝑑)$, compute $\mathbf{b} = (1, x, x^2, …, x^{d-1})$.
Compute $p(x) = \langle \mathbf{a}, \mathbf{b} \rangle = v$, pick random $w \leftarrow \mathbb{G}$.
Compute $P' = P + [v]w = 𝑔_1^{𝑎_1}𝑔_2^{𝑎_2} \cdots 𝑔_𝑑^{𝑎_𝑑} ℎ^𝑟 w^v$.
Let $\mathbf{G}_0 = \mathbf{G}$, $\mathbf{a}_0 = \mathbf{a}$, $\mathbf{b}_0 = \mathbf{b}$, perform $k$ rounds of inner product opening:
Round $i = [0, k -1]$:
* Pick random $l_i, r_i \in \mathbb{F}_p$. Compute the following:
* $L_i = \langle \mathbf{a}^{lo}_k, \mathbf{G}^{hi}_k \rangle + [l_i]h + [\langle \mathbf{a}^{hi}_k, \mathbf{b}^{lo}_k \rangle]w$,
* $R_i = \langle \mathbf{a}^{hi}_k, \mathbf{G}^{lo}_k \rangle + [r_i]h + [\langle \mathbf{a}^{lo}_k, \mathbf{b}^{hi}_k \rangle]w$,
* $u_i = \mathcal{H}({\sf transcript}_i)$,
* $\mathbf{a}_{k+1} = \mathbf{a}^{hi}_k \cdot u^{-1}_i + \mathbf{a}^{lo}_k \cdot u_i$,
* $\mathbf{b}_{k+1} = \mathbf{b}^{lo}_k \cdot u^{-1}_i + \mathbf{b}^{hi}_k \cdot u_i$,
* $\mathbf{G}_{k+1} = \mathbf{G}^{lo}_k \cdot u^{-1}_i + \mathbf{G}^{hi}_k \cdot u_i$.

Compute $r' = \sum^{k-1}_{i=0}l_i u^2_i + r + \sum^{k-1}_{i=0}r_i u^{-2}_i$.
Pick $d_1, d_2 \leftarrow \mathbb{F}_p$, Compute the following:
$R = [d_1] (\mathbf{G}_k + [\mathbf{b}_k]w) + [d_2]h$,
$c = \mathcal{H}({\sf transcript}_k)$,
$z_1 = d_1 - \mathbf{a}_k \cdot c, z_2 = d_2 - r' \cdot c$.
Output $\pi = (\{L_i, R_i, u_i\}_{i \in [0, k-1]}, w, R, c, z_1, z_2)$.

### Verify algorithm
$0/1 \leftarrow {\sf Verify}(\sigma, {\sf com}, \pi, x, v)$:
Compute $P' = P + [v]w = 𝑔_1^{𝑎_1}𝑔_2^{𝑎_2} \cdots 𝑔_𝑑^{𝑎_𝑑} ℎ^𝑟 w^v$.
Recompute $u_i = \mathcal{H}({\sf transcript}_i)$ for $i \in [0, k-1]$ and $c = \mathcal{H}({\sf transcript}_k)$.
Compute the following:
$\mathbf{s}= (u^{-1}_{k-1}u^{-1}_{k-2} \cdots u^{-1}_{0}, u_{k-1}u^{-1}_{k-2} \cdots u^{-1}_{0}, u^{-1}_{k-1}u_{k-2} \cdots u^{-1}_{0}, u_{k-1}u_{k-2} \cdots u^{-1}_{0}, \cdots, u_{k-1}u_{k-2} \cdots u_{0}).$
$\mathbf{G}_k = \langle \mathbf{s}, \mathbf{G} \rangle$, $\mathbf{b}_k = \langle \mathbf{s}, \mathbf{b} \rangle$.
$Q = \sum^{k-1}_{i = 0} [u^2_i]L_i + P + \sum^{k-1}_{i = 0} [u^{-2}_i]R_i$.
Output 1 if $[c]Q + [z_1](\mathbf{G}_k + [\mathbf{b}_k]w) + [z_2]h = R$, output 0 otherwise.

## A Concrete Example for d = 4
The above scheme may look scary, so it will be easier check the details through a concrete example. Assume $d = 4$, then $k = log \ 4 = 2$. Assume the polynomial $p(X)$ to be committed has degree $4 - 1 = 3$, thus $\mathbf{G} = (g_1, g_2, g_3, g_4)$, $\mathbf{a} = (a_1, a_2, a_3, a_4)$, $\mathbf{b} = (b_1, b_2, b_3, b_4) = (1, x, x^2, x^3)$.

The setup algorithm outputs $𝜎=(\mathbb{G},\mathbb{F}_p, \mathcal{H}, \mathbf{𝐆} = (g_1, g_2, g_3, g_4), h)$.
The commit algorithm outputs ${\sf com} = P = \langle \mathbf{a}, \mathbf{G} \rangle + [𝑟]h = 𝑔_1^{𝑎_1}𝑔_2^{𝑎_2}g_3^{a_3}𝑔_4^{𝑎_4}ℎ^𝑟$.

For the open algorithm, the prover first computes $P' = P + [v]w = 𝑔_1^{𝑎_1}𝑔_2^{𝑎_2}g_3^{a_3}𝑔_4^{𝑎_4}h^𝑟 w^v$.
Then the prover sets $\mathbf{G}_0 = \mathbf{G}$, $\mathbf{a}_0 = \mathbf{a}$, $\mathbf{b}_0 = \mathbf{b}$, and perform 2 rounds of inner product opening, i.e., round $i = 0$ and round $i = 1$.
At round $i = 0$:
* Pick $l_0, r_0 \in \mathbb{F}_p$. Compute the following:
* $L_0 = \langle \mathbf{a}^{lo}_0, \mathbf{G}^{hi}_0 \rangle + [l_0]h + [\langle \mathbf{a}^{hi}_0, \mathbf{b}^{lo}_0 \rangle]w = g_3^{a_1}g_4^{a_2} h^{l_0}w^{a_1b_3 + a_2b_4}$,
* $R_0 = \langle \mathbf{a}^{hi}_0, \mathbf{G}^{lo}_0 \rangle + [r_0]h + [\langle \mathbf{a}^{lo}_0, \mathbf{b}^{hi}_0 \rangle]w = g_1^{a_3}g_2^{a_4} h^{r_0}w^{a_3b_1 + a_4b_2}$,
* $u_0 = \mathcal{H}({\sf transcript}_0)$, ${\sf transcript}_0 = (P', L_0, R_0)$
* $\mathbf{a}_{1} = \mathbf{a}^{hi}_0 \cdot u^{-1}_0 + \mathbf{a}^{lo}_0 \cdot u_0 = (u_0 a_1 + u^{-1}_0 a_3, u_0 a_2 + u^{-1}_0 a_4)$,
* $\mathbf{b}_{1} = \mathbf{b}^{lo}_0 \cdot u^{-1}_0 + \mathbf{b}^{hi}_0 \cdot u_0 = (u^{-1}_0 b_1 + u_0 b_3, u^{-1}_0 b_2 + u_0 b_4)$,
* $\mathbf{G}_{1} = \mathbf{G}^{lo}_0 \cdot u^{-1}_0 + \mathbf{G}^{hi}_0 \cdot u_0 = (g^{u^{-1}_0}_1 g^{u_0}_3, g^{u^{-1}_0}_2 g^{u_0}_4)$.

At round $i = 1$:
* Pick $l_1, r_1 \in \mathbb{F}_p$. Compute the following:
* $L_1 = \langle \mathbf{a}^{lo}_1, \mathbf{G}^{hi}_1 \rangle + [l_1]h + [\langle \mathbf{a}^{hi}_1, \mathbf{b}^{lo}_1 \rangle]w = \left( g^{u^{-1}_0}_2 g^{u_0}_4 \right)^{u_0 a_1 + u^{-1}_0 a_3} h^{l_1} w^{(u_0 a_1 + u^{-1}_0 a_3) \cdot (u^{-1}_0 b_2 + u_0 b_4)},$
* $R_1 = \langle \mathbf{a}^{hi}_1, \mathbf{G}^{lo}_1 \rangle + [r_1]h + [\langle \mathbf{a}^{lo}_1, \mathbf{b}^{hi}_1 \rangle]w = \left( g^{u^{-1}_0}_1 g^{u_0}_3 \right)^{u_0 a_2 + u^{-1}_0 a_4} h^{r_1} w^{(u_0 a_2 + u^{-1}_0 a_4) \cdot (u^{-1}_0 b_1 + u_0 b_3)},$
* $u_1 = \mathcal{H}({\sf transcript}_1)$, ${\sf transcript}_1 = (P', L_0, R_0, u_0, L_1, R_1),$
* $\mathbf{a}_{2} = \mathbf{a}^{hi}_1 \cdot u^{-1}_1 + \mathbf{a}^{lo}_1 \cdot u_1 = (u_0 u_1 a_1 + u_0 u_1^{-1} a_2 + u_0^{-1} u_1 a_3 + u_0^{-1} u_1^{-1} a_4),$
* $\mathbf{b}_{2} = \mathbf{b}^{lo}_1 \cdot u^{-1}_1 + \mathbf{b}^{hi}_1 \cdot u_1 = (u_0^{-1} u_1^{-1} a_1 + u_0^{-1} u_1 a_2 + u_0 u_1^{-1} a_3 + u_0 u_1 a_4),$
* $\mathbf{G}_{2} = \mathbf{G}^{lo}_1 \cdot u^{-1}_1 + \mathbf{G}^{hi}_1 \cdot u_1 = (g_1^{u_0^{-1} u_1^{-1} a_1} g_2^{u_0^{-1} u_1 a_2} g_3^{u_0 u_1^{-1} a_3} g_4^{u_0 u_1 a_4})$.

After that, the prover computes $r' = \sum_{i=0}^{1}l_i u_i^2 + r + \sum_{i=0}^{1} r_i u_i^{-2} = u_0^2 l_0 + u_1^2 l_1 + r + u_0^{-2} r_0 + u_1^{-2} r_1$
then computes the Schnorr signature for zero-knowledge proving the value of $\mathbf{a}_2$ and $r'$:
$R = \left(g_1^{u_0^{-1} u_1^{-1} a_1} g_2^{u_0^{-1} u_1 a_2} g_3^{u_0 u_1^{-1} a_3} g_4^{u_0 u_1 a_4} w^{u_0^{-1} u_1^{-1} b_1 + u_0^{-1} u_1 b_2 + u_0 u_1^{-1} b_3 + u_0 u_1 b_4}\right)^{d_1}\cdot h^{d_2}$,
$c = \mathcal{H}({\sf transcript}_2)$, ${\sf transcript}_2 = (P', L_0, R_0, u_0, L_1, R_1, u_1, R),$
$z_1 = d_1 - \mathbf{a}_2 c, z_2 = d_2 - r' c.$
and finally outputs $\pi = (\{L_i, R_i, u_i\}_{i \in [0, 1]}, w, R, c, z_1, z_2).$

For the verify algorithm, the verifier first compute $P' = P + [v]w = 𝑔_1^{𝑎_1}𝑔_2^{𝑎_2}g_3^{a_3}𝑔_4^{𝑎_4}h^𝑟 w^v$.
Given $P', \{L_i, R_i, u_i\}_{i \in [0, 1]}$ the verifier can recompute all challenges $\{u_i\}_{i \in [0, 1]}$ and $c$.
Since $k = 2$ is public information, the verifier can obtain vector $\mathbf{s} = (u_0^{-1}u_1^{-1}, u_0^{-1}u_1, u_0u_1^{-1}, u_0u_1)$, and compute
$\mathbf{G}_2 = \langle \mathbf{s}, \mathbf{G} \rangle = g_1^{u_0^{-1} u_1^{-1} a_1} g_2^{u_0^{-1} u_1 a_2} g_3^{u_0 u_1^{-1} a_3} g_4^{u_0 u_1 a_4},$
$\mathbf{b}_2 = \langle \mathbf{s}, \mathbf{b} \rangle = u_0^{-1} u_1^{-1} b_1 + u_0^{-1} u_1 b_2 + u_0 u_1^{-1} b_3 + u_0 u_1 b_4,$
\begin{align}
Q & = \sum_{i=0}^1 [u_i^2] L_i + P' + \sum_{i=0}^1 [u_i^{-2}]R_i \\
& = (g_3^{a_1}g_4^{a_2} h^{l_0}w^{a_1b_3 + a_2b_4})^{u_0^2} \cdot \left(\left( g^{u^{-1}_0}_2 g^{u_0}_4 \right)^{u_0 a_1 + u^{-1}_0 a_3} h^{l_1} w^{(u_0 a_1 + u^{-1}_0 a_3) \cdot (u^{-1}_0 b_2 + u_0 b_4)}\right)^{u_1^2} \cdot \\
& \ \ \ \ \ \ 𝑔_1^{𝑎_1}𝑔_2^{𝑎_2}g_3^{a_3}𝑔_4^{𝑎_4}ℎ^𝑟 w^{a_1b_1 + a_2b_2 + a_3b_3 + a_4b_4} \cdot \\
& \ \ \ \ \ \ (g_1^{a_3}g_2^{a_4} h^{r_0}w^{a_3b_1 + a_4b_2})^{u_0^{-2}} \cdot \left(\left( g^{u^{-1}_0}_1 g^{u_0}_3 \right)^{u_0 a_2 + u^{-1}_0 a_4} h^{r_1} w^{(u_0 a_2 + u^{-1}_0 a_4) \cdot (u^{-1}_0 b_1 + u_0 b_3)}\right)^{u_1^{-2}} \\
& = g_1^{u_0^{-2}a_3 + u_1^{-2}a_2 + u_0^{-2}u_1^{-2}a_4 + a_1} \cdot g_2^{u_1^2a_1 + u_0^{-2}u_1^2a_3 + u_0^{-2}a_4 + a_2} \cdot g_3^{u_0^{2}a_1 + u_0^2u_1^{-2}a_2 + u_1^{-2}a_4 + a_3} \cdot g_4^{u_0^2a_2 + u_0^2u_1^2a_1 + u_1^2a_3} \cdot \\
& \ \ \ \ \ \ w^{u_0^2a_1b_3 + u_0^2a_2b_4 + u_1^2a_1b_2 + u_0^2u_1^2a_1b_4 + u_0^{-2}u_1^2a_3b_2 + u_1^2a_3b_4 + u_0^{-2}a_3b_1 + u_0^{-2}a_4b_2 + u_1^{-2}a_2b_1 + u_0^{2}u_1^{-2}a_2b_3 + u_0^{-2}u_1^{-2}a_4b_1 + u_1^{-2}a_4b_3} \cdot \\
& \ \ \ \ \ \ w^{a_1b_1 + a_2b_2 + a_3b_3 + a_4b_4} \cdot h^{u_0^2l_0 + u_1^2l_1 + r + u_0^{-2}r_0 + u_1^{-2} r_1}
\end{align}

If the schnorr signature is valid, i.e., $[c]Q + [z_1](\mathbf{G}_2 + [\mathbf{b}_2]w) + [z_2]h = R$,
then the equation $Q = [\mathbf{a}_2](\mathbf{G}_2 + [\mathbf{b}_2]w) + [r']h$ must hold.
In other words, we only need to show that if $Q = \langle \mathbf{a}_2, \mathbf{G}_2 \rangle + [\langle \mathbf{a}_2, \mathbf{b}_2 \rangle]w + [r']h$:
\begin{align}
\langle \mathbf{a}_2, \mathbf{G}_2 \rangle & = \left(g_1^{u_0^{-1} u_1^{-1}} g_2^{u_0^{-1} u_1} g_3^{u_0 u_1^{-1}} g_4^{u_0 u_1}\right)^{u_0u_1a_1 + u_0u_1^{-1}a_2 + u_0^{-1}u_1a_3 + u_0^{-1}u_1^{-1}a_4} \\
& = g_1^{a_1 + u_1^{-2}a_2 + u_0^{-2}a_3 + u_0^{-2}u_1^{-2}a_4} g_2^{u_1^2a_1 + a_2 + u_0^{-2}u_1^2a_3 + u_0^{-2}a_4} g_3^{u_0^2a_1 + u_0^2u_1^{-2}a_2 + a_3 + u_1^{-2}a_4} g_4^{u_0^2u_1^2a_1 + u_0^2a_2 + u_1^2a_3 + a_4}
\end{align}
We can se that $\langle \mathbf{a}_2, \mathbf{G}_2 \rangle$ is equal to the $g$ part of $Q$.
\begin{align}
\langle \mathbf{a}_2, \mathbf{b}_2 \rangle & = (u_0 u_1 a_1 + u_0 u_1^{-1} a_2 + u_0^{-1} u_1 a_3 + u_0^{-1} u_1^{-1} a_4) \cdot \\
& \ \ \ \ \ (u_0^{-1} u_1^{-1} a_1 + u_0^{-1} u_1 a_2 + u_0 u_1^{-1} a_3 + u_0 u_1 a_4) \\
& = a_1b_1 + u_1^2a_1b_2 + u_0^2a_1b_3 + u_0^2u_1^2a_1b_4 + u_1^{-2}a_2b_1 + a_2b_2 + u_0^2u_1^{-2}a_2b_3 + u_0^2a_2b_4 + \\
& \ \ \ \ \ u_0^{-2}a_3b_1 + u_0^{-2}u_1^2a_3b_2 + a_3b_3 + u_1^2a_3b_4 + u_0^{-2}u_1^{-2}a_4b_1 + u_0^{-2}a_4b_2 + u_1^{-2}a_4b_3 + a_4b_4
\end{align}
We can see that $[\langle \mathbf{a}_2, \mathbf{b}_2 \rangle]w$ is equal to the $w$ part of $Q$.
Since $r' = u_0^2 l_0 + u_1^2 l_1 + r + u_0^{-2} r_0 + u_1^{-2} r_1$, $[r']h$ is equal to the $h$ part of $Q$.
Thus, we show the opening proof is correct through $Q = \langle \mathbf{a}_2, \mathbf{G}_2 \rangle + [\langle \mathbf{a}_2, \mathbf{b}_2 \rangle]w + [r']h.$

## Insights and Understandings
* This PC scheme has a transparent setup because there are no secret randomness or trapdoor generated at the Setup algorithm, all the parameters in $\sigma$ are public.
* There is a degree bound $d-1$ for the commited polynomial, and we always set $d$ is a power of 2. If the degree of the polynomial is less than $d - 1$, we can pad 0s in vector $\mathbf{a}$ and $\mathbf{b}$, making their size equal to $d$.
* The Commit algorithm generates a Pederson-type vector commitment for the polynomial coefficients $\mathbf{a} = (a_1, ..., a_d)$, in which the original form for commiting a single value is $g^{a}h^r$. The $h^r$ term is to blind the commited term $g^a$, such that the adversary can get no information about $g^a$, thus it acheives the hiding property.
* The Open algorithm can be divided into two parts: (1) The $k$-round inner product argument for mixing up the $\mathbf{a}, \mathbf{b}, \mathbf{G}$ terms with random challenges, (2) The Schnorr-type zero-knowledge proof for demonstrating the knowledge of $\mathbf{a}_k$ and $r'$.
* For the first part of Open algorithm, the inner product argument reduces the size of vector $\mathbf{a}, \mathbf{b}, \mathbf{G}$ to half in each round. The resulting vector $\mathbf{a}_k, \mathbf{b}_k, \mathbf{G}_k$ each only has 1 element. Thus, the opening proof $\pi$ has $\mathcal{O}(log \ d)$ size, which satsifies the succincetness property.
* The random challenges $u_i$ are generated through the Fiat-Shamir transform to eliminate the interation between prover and verifier. Otherwise, the challenges need to be chosen by the verifier. The challenges $u_i$ play the role of binding prover messages in each round and preventing malicious manipulations from the prover.
* For the Verify algorithm, the verifier can always determine $\mathbf{s}$ based on the bound $d$ and the scheme construction. Given $\mathbf{G}$, $\mathbf{b}$ and $\mathbf{s}$, the verifier can compute $\mathbf{G}_k$ and $\mathbf{b}_k$. Without knowing $\mathbf{a}$ and $r$, the verifier can only verify $\mathbf{a}_k$ and $r'$ through the Schnorr signature $c, R, z_1, z_2$, along with $\mathbf{G}_k$, $\mathbf{b}_k$ and $Q$.