# KZG Multiopen

## Overview

The Multiopen stage of Halo2 proof generation consists of composing a set of numerator polynomials from linear combination of sets of input polynomials, dividing a set of roots out of each numerator, and reducing the resulting quotients into a single polynomial via another linear combination.

## GPU Implementation

The linear combination steps of multiopen are trivially implemented on the GPU by summing the corresponding coefficients of each input polynomial in parallel. The polynomial division operation is more complex but can be cast as a modified prefix-scan operation for which highly efficient GPU solutions are readily available.

## Performance

The following table outlines the performance improvements yielded with just the cuSnark KZG Multiopen employed, showing the (CPU baseline) and accelerated results for the different proof stages in a set of proofs of various sizes. Times are in seconds, obtained on a AMD EPYC 7702 64-Core Processor with 4x NVIDIA GeForce RTX 3090 (24 GB) GPUs.

<table><thead><tr><th width="249">Proof Stage</th><th width="247">2^20 rows, 1135 columns</th><th>2^25 rows, 5 columns</th></tr></thead><tbody><tr><td>Initialization</td><td>(6.04) 6.06 </td><td>(1.40) 1.39 </td></tr><tr><td>Generate Instance</td><td>(0.05) 0.05 </td><td>(1.05) 1.06 </td></tr><tr><td>Generate Advice</td><td>(381.78) 381.82 </td><td>(6.68) 6.66 </td></tr><tr><td>Generate Lookups</td><td>(57.99) 58.43 </td><td>(2.10) 2.11 </td></tr><tr><td>Commit Permutations</td><td>(146.59) 146.91 </td><td>(23.72) 25.28 </td></tr><tr><td>Eval_h</td><td>(1069.09) 1071.40 </td><td>(66.58) 66.95 </td></tr><tr><td>Compute Evaluations</td><td>(9.81) 9.95 </td><td>(35.79) 35.91 </td></tr><tr><td>Multiopen</td><td>(18.71) 7.67</td><td>(28.82) 1.71</td></tr><tr><td>Total</td><td>(1690.05) 1682.28</td><td>(166.15) 141.06</td></tr></tbody></table>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://docs.snarkify.io/high-performance-zkp/zkevm-halo2-gpu-prover/kzg-multiopen.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.