Notation:
The fold operation:
Given a polynomial

$h$ and

$u\in F$ we define

$$fold(h,u)=\overline{u}{h}_{even}+u{h}_{odd},$$
where

$\overline{u}=1-u$.
Crucial relation:
Given

$r,u\in F$ and polynomial

$h$, define

$\alpha =h(r),\overline{\alpha }=h(-r)$ and

$\beta =fold(h,u)(r^2)$. Then

$$\beta =\overline{u}\frac{\alpha +\overline{\alpha }}{2}+u\frac{\alpha -\overline{\alpha }}{2r}.$$

In our version of Gemini, we mostly use this equality in the reverse direction deriving

$h(r)$ from

$h(-r)$ and

$fold(h,u)(r^2)$. Precisely, we see from the above equation that

$$\alpha =\frac{(u-\overline{u}r)\overline{\alpha }+2r\beta }{(\overline{u}r+u)}$$

For brevity, we denote below this RHS by

$derive(u,\overline{\alpha },\beta )$

Let

$d=\log n$
Given this notation, we can concisely describe our optimized Gemini protocol:
(Sidenote: I think there are some confusing typos in the version here)

Given polynomial

$f$ of degree

$<n$ and opening point

$(u_0\dots ,u_{d-1})$ and the purported value

$v=ml(f)(u_0,\dots ,u_{d-1})$

1. We define for each
   $j\in [d]$
   $g_j=fold(g_{j-1},u_{j-1})$
2. $P$ sends commitments to
   $g_1,\dots ,g_{d-1}$
3. $V$ chooses random
   $r$
4. $P$ sends for
   $i\in [d-1]$,
   ${\overline{\alpha }}_i=g_i(-r^{2^i})$. And
   ${\overline{\alpha }}_0=f(-r)$.
5. $V$ sets
   ${\alpha }_d=v$
6. $V$ derives the values
   ${\alpha }_0,{\alpha }_1,\dots ,{\alpha }_{d-1}$ going "backwards" via
   
   $${\alpha }_i=derive(u_i,{\overline{\alpha }}_i,{\alpha }_{i+1})$$
7. Using shplonk
   $P$ proves to
   $V$ the correctness of
   $$f(r)={\alpha }_0,f(-r)={\overline{\alpha }}_0,g_1(-r^2)={\overline{\alpha }}_1,g_2(-r^4)={\overline{\alpha }}_2,\dots ,g_{d-1}(-r^{2^{d-1}})={\overline{\alpha }}_{d-1}$$

Soundness issue:

In the above we don't check

${\alpha }_1,\dots ,{\alpha }_{d-1}$ using shplonk.

We give an example of why these checks should be added and how we can open to the wrong value.

We use

$n=8$ so

$d=3$.
We fix any

$u=(u_0,u_1,u_2)$.
We take

$f=0$.
we show we can successfully open

$ml(f)(u)=v$ for any

$v$.
It will be convenient to use the notations

$g=g_1$,

$h=g_2$. Also, to start use a challenge

$r^{\prime }$ and set

$r=r^{\prime 2}$ (so that

$g$ is evaluated at

$r$ rather than

$r^2$)

We set

${\alpha }_0={\overline{\alpha }}_0={\alpha }_1=0$,
as an honest

$P$ would get when starting with

$f=0$.

we'll choose the coefficients of

$g,h$ via a system of linear equations so that,
when setting "honestly"

${\overline{\alpha }}_1=g(r),{\alpha }_2=h(r^2),{\overline{\alpha }}_2=h(-r^2)$

we get

$$derive(u_1,{\overline{\alpha }}_1,{\alpha }_2)=0={\alpha }_1$$

We denote by

$g_0,g_1,g_2,g_3$, and

$h_0,h_1$ the coefficients of

$g,h$ respectively.

Let's set

$\alpha ={\alpha }_1,\beta ={\alpha }_2,u=u_1$.
We have according to the derive formula:

$$(\overline{u}r+u)\alpha =(u-\overline{u}r)\overline{\alpha }+2r\beta$$

So it suffices for us that

$$(u-\overline{u}r)\overline{\alpha }+2r\beta =0$$
Equivalently

$$P(r):=(u-\overline{u}r)g(-r)+2rh(r^2)=0$$
Since

$r$ is chosen after

$g,h$ are committed we want to make

$P$ identically zero.

$P$ has degree four, and its coefficients are linear combinations of

$g_0,g_1,g_2,g_3,h_0,h_1$.
Explicitly, if

$P(X)=P_0+P_{1}X+P_2{X}^2+P_3{X}^3+P_4{X}^4$ then

calculation shows

$P_0=u{g}_0,P_1=2h_0-\overline{u}{g}_0-u{g}_1$,

$P_2=\overline{u}{g}_1+u{g}_2,P_3=2h_1-\overline{u}{g}_2-u{g}_3,P_4=\overline{u}{g}_3$

To zero out all coefficients of

$P$, we can thus set

$g_0=0,g_1=2h_0/u,g_2=-\overline{u}{g}_1/u=-\overline{u}2h_0/u^2$

$g_3=0,h_1=\overline{u}{g}_2/2=-{\overline{u}}^2{h}_0/u^2$

Note that

$h_0$ is still a free variable.

We choose

$h_0$ so that

$${\overline{u}}_2{h}_0+u_2{h}_1=v$$

$P$ will send commitments to

$g,h$, and the "honest" values

${\overline{\alpha }}_0=0,{\overline{\alpha }}_1=g(-r){\overline{\alpha }}_2=h(-r^2)$

The application of

$derive$ by

$V$ will set

${\alpha }_0=0=f(r^{\prime })$.

So all shplonk checks will pass. It follows that

$V$ will accept the proof for output

$v$.

Converging to the implemented version (case d=2)

(Written by Sergei before massive edit of the above, so might be out of context)

Say

$(u_0,u_1)$ is the evaluation point, and

$v$ the claimed evaluation

$ml(f)(u_0,u_1)$.
Then,

1. $P$ sends a commitment to
   $g_1$.
2. $V$ sends
   $r$.
3. $P$ sends the values
   ${\overline{\alpha }}_0=f(-r),{\overline{\alpha }}_1=g(-r^2)$.
4. $V$ computes
   
   $${\alpha }_1=g(r^2)=\frac{2r^2\cdot v-{\overline{\alpha }}_1(r^2(1-u_1)-u_1)}{r^2(1-u_1)+u_1}$$
   
   $${\alpha }_0=f(r)=\frac{2r\cdot {\alpha }_1-{\overline{\alpha }}_1(r(1-u_0)-u_0)}{r(1-u_0)+u_0}$$
5. KZG check the values
   ${\alpha }_0$,
   ${\overline{\alpha }}_0$, and
   ${\overline{\alpha }}_1$

Note that the honest prover sends a commitment to

$g=fold(f,u_0):=(1-u_0)f_{even}+u_0{f}_{odd}$