# Accumulation scheme
- describe accumulator
- describe decision routine
- inefficient for verifier
- describe update routine
- efficient for verifier

---------
**new_instance**:
- $P_0$, the commitment to $p_0(X)$
- $x_0$, the challenge at which $p_0(X)$ is evaluated
- $v_0$, the claimed evaluation of $p_0(x_0)$
- IPA proof $\pi_0$ for the statement "$P_0$ is a commitment to $p_0(X)$, and $p_0(x_0) = v_0$."
- challenges $\{u_i\}^0$
- $G_0$, the purported commitment to $g_0(X) = g(X, \{u_i\}^0)$
- cross-terms $\{L_i\}_0, \{R_i\}_0$
----------

----------
**prev_acc**:
- $P_1$, the commitment to $p_1(X)$
- $x_1$, the challenge at which $p_1(X)$ is evaluated
- $v_1$, the claimed evaluation of $p_1(x_1)$
- IPA proof $\pi_1$ for the statement "$P_1$ is a commitment to $p_1(X)$, and $p_1(x_1) = v_1$."
- challenges $\{u_i\}^1$
- $G_1$, the purported commitment to $g_1(X) = g(X, \{u_i\}^1)$
- cross-terms $\{L_i\}_1, \{R_i\}_1$
----------

----------
**new_acc**:
- derive a random $\alpha$ from $(g_0, G_0, g_1, G_1)$
- define $p(X) = g_0(X) + \alpha \cdot g_1(X)$
- accumulate into $P := G_0 + [\alpha]G_1$, a commitment to $p(X)$
- derive a challenge point $x$ from $(P, p(X))$
- compute $p(x) = v$
- construct IPA proof $\pi$ for the statement $p(x) = v$
- challenges $\{u_i\}$
- $G$, the purported commitment to $g(X,\{u_i\})$
- cross-terms $\{L_i\}, \{R_i\}$
----------

----------
**accumulation verifier**:
- IPA check of $\pi_0$ (excluding the linear-time computation $\langle \mathbf{s}_0, \mathbf{G} \rangle$)
- IPA check of $\pi_1$ (excluding the linear-time computation $\langle \mathbf{s}_1, \mathbf{G} \rangle$)
- check that $P := G_0 + [\alpha]G_1$
- check that $v = p(x) = g_0(x) + \alpha \cdot g_1(x)$
- $g_0(z)$ takes $O(\log(d))$ field operations to compute
- $g_1(z)$ takes $O(\log(d))$ field operations to compute
----------

----------
**decider**: fully checks $\pi$
- This includes the linear-time check that $G = \langle \mathbf{s}, \mathbf{G} \rangle$, where $\mathbf{G}$ are random bases from setup, and $\mathbf{s}$ is the $\{u_i\}$'s arranged in binary counting order
----------

## Questions
1. Why does the computation of $g(X)$ only take $O(\log(d))$ field operations?
Answer: See Eqn 3 in the [Halo paper](https://eprint.iacr.org/2019/1021.pdf)

2. Why is opening $g(X)$ at a random $x$ not enough to convince us that $G$ is a valid commitment to $g(X)$?
Answer: Each invocation of the inner product argument results in a new unchecked $G$ value. We can check it again with a new inner product argument (including $G$ values from other instances as well in the process if we'd like) but that will result in a single new $G$ value ultimately anyway. Eventually we need to check at least one $G$ value outside the circuit in the decision routine.

## notes from sean

The inner product argument accumulator looks like

$$
(G \in \mathbb{G}, \{u_j\}^k \in \mathbb{F})
$$

and the decision routine is $G \stackrel{?}{=} \text{Commit}(g(X, \{ u_j\}^k ))$ via MSM, where $g$ is a succinct public polynomial.

---------
The polynomial evaluation accumulator looks like

$$
(P \in \mathbb{G}, x \in \mathbb{F}, v \in \mathbb{F})
$$

and the decision routine is $P \stackrel{?}{=} \text{Commit}(p(X))$ where $p(x) = v$ which requires knowledge of $p$ (which might not be succinct and is likely completely random).

Update routine (common input are $\ell$ accumulators of the form $(P_i, r_i)$):

* Verifier samples $\mu$
* Prover sends $P' = \text{Commit}(p'(X))$ where $p'(X) = \sum\limits_{i = 0}^{\ell} \frac{a_i(X)}{X - r_i} \mu^i$
* Verifier samples $x$
* Prover sends $S$ (a commitment to a random polynomial that has a root at $x$)
* Ask prover for $a_i(x)$ for all $i$
* Verifier samples $y$
* todo

A polynomial evaluation accumulator can be transformed into an inner product argument accumulator when the prover has access to $p$, via the inner product argument.

------

PLONK protocol for halo2 can be broken apart so that the verification routine returns a "polynomial evaluation accumulator" which can be optionally processed through the polynomial commitment to obtain a "inner product argument accumulator".