Analyze the algorithmic complexity of the gemini protocol

[wenjin1997]

Analyze the algorithmic complexity of the gemini protocol, including:

• Prover's cost
• Verifier's cost
• Proof size

[wenjin1997]

Gemini

The Gemini protocol has many versions.

Geminin Protocol - Optimized 1

The complexity analysis of the protocol corresponds to the Python code in bcho_pcs.py.

Prover's cost:

Verifier's cost:

Proof size:

$$ (n + 1) \cdot \mathbb{G}_1 + (2n + 1) \mathbb{F}_p $$

[wenjin1997]

Gemini Protocol - Optimized 2

Use fri query technique to optimized.

Prover's cost:

Verifier's cost:

Proof size:

$$ (n + 1) \cdot \mathbb{G}_1 + (n + 1) \cdot \mathbb{F}_p $$

[wenjin1997]

Gemini Optimized 1 vs. Optimized 2

When we use the FRI query technique to optimize the Gemini protocol, we find that:

• Optimized 2 has a smaller proof size, requiring less $n \cdot \mathbb{F}_p$ than Optimized 1.
• However, the Optimized 2 protocol incurs higher verifier costs, adding

• In terms of prover costs, these two protocols are quite similar.

[wenjin1997]

The detailed complexity analysis of the protocol is presented here.