# Protogalaxy multiplications in the ECCVM

## Problem statement

The ECCVM is designed (before protogalaxy) to efficiently perform multi-scalar multiplications.

The Protogalaxy folding verifier performs multiple *single* multiplications. From the pg protocol, the Verifier computes (page 9 of [pg paper](https://eprint.iacr.org/2023/1106.pdf)):

$$
\phi^\star = \phi + \sum_{i \in k} L_i(\gamma)(\phi_i - \phi)
$$

Where $\phi$ represents a committed transcript i.e. all witness and selector commitments.

This doc is my thoughts on how to most efficiently represent this computation in the ECCVM, given its strengths and limitations.

## Notation

For simplicity we assume that $k=1$ but the logic in this document should apply for $k=2$.

Let us assume we have $v$ polynomial commitments contained in each transcript.

We will abuse notation in this document by representing the polynomials associated with $\phi_1 - \phi$ as $[P_1], \ldots [P_v]$.

We assume the cost of additions, subtractions and equality checks are negligible compared to multiplications.

**The key question**: how to most efficiently perform the computations $L_1(\gamma)[P_1], \ldots, L_1(\gamma)[P_v]$

## ECCVM cost model

A multiscalar multiplication of $v$ 128-bit scalar multipliers requires $32$ rows to perform point doublings, and $32 \lceil\frac{v}{4}\rceil$ rows to perform point additions (up to 4 point additons per row).

For 256-bit scalar multipliers, the cost is $32 \lceil \frac{v}{2}\rceil$ rows for point additions and $32$ rows for point doublings.

# Broke: basic method

We independently compute $L_1(\gamma)\cdot[P_1], ..., L_1(\gamma)\cdot[P_t]$

Cost: v32 doublings, v32 additions = $64v$ ECCVM rows

# Woke: random linear combinations

Ok so here's the plan: we combine every multiplication statement into 1 statement via random linear combinations.

Generate 128-bit random variables (via hashing) $\alpha_1, \ldots, \alpha_v$.

For all $i \in [1, \ldots, v]$, let $[Q_i] = L_1(\gamma) [P_i]$ (the scalar mul results).

In the ECCVM, we evaluate the relation:

$$
\sum_{i=1}^v (L_1(\gamma) [P_i] - [Q_i])\alpha_i = 0
$$

Cost is 1 MSM of size 2v, where v scalar multipliers are 128-bits and v scalar multipliers are 256-bits.

This equates to $32$ double rows and $32 \lceil \frac{3v}{4}\rceil$ addition rows.

Assuming $v$ is large enough that $\lceil \frac{3v}{4}\rceil \approx \frac{3v}{4}$, the total cost is:

$32 + 24v$ rows

For woke to beat woke, we require $64v > 32 + 24v$ which implies $v > 0.8$. v has to at least be 1 so this method will be faster.

## Bespoke: short scalar multipliers

Same as the woke method but we rearrange into two multiscalar multiplications that each have 128-bit scalar multipliers (plus an extra scalar mul):

$$
L_0(\gamma) \sum_{i = 1}^{v} \alpha_i [P_i] = \sum_{i=1}^v \alpha_i [Q_i]
$$

We can split this into 3 separate multiplications:

1. $[X] = \sum_{i=1}^v \alpha_i [P_i]$
2. $[Y] = \sum_{i=1}^v \alpha_i [Q_i]$
3. $[Z] = L_0(\gamma)[X]$

Then validate that $[X] = [Z]$.

The scalar multipliers in 1, 2 are 128-bit which halves the number of point additions.

Cost: 1 128-bit MSM of size-v ($32 \lceil\frac{v}{4}\rceil$ additions, $32$ doublings)
Cost: 1 128-bit MSM of size-v ($32 \lceil\frac{v}{4}\rceil$ additions, $32$ doublings)
Cost: 1 256-bit MSM of size-1 ($32$ additions, $32$ doublings)

Total cost: 128 + 64 $\lceil\frac{v}{4}\rceil$ rows

Assuming $v$ is sufficiently large that $\lceil\frac{v}{4}\rceil \approx \frac{v}{4}$, this reduces to $128 + 16v$ rows.

## Which method is better?

For bespoke to beat woke, we need $24v + 32 > 128 + 16v$, i.e. $v > 12$. Honk has well over 32 polynomials so this is the fastest method of computing the protogalaxy folding scalar multiplications.

### A note on hashing

Using Poseidon2, a hash costs 70 constraints. Splitting the hash output two 128-bit scalars will cost ~22 constraints in Honk (i.e. 50 constraints per scalar). I am making an assumption that the ~50 constraints per 128-bit challenge is negligible compared to the cost savings in the ECCVM, but this probably needs further analysis.