scroll-tech / scroll-tech/ceno

batch open multiple `q`

Open
#1,334 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Rust
Stars
153
Forks
43
Avg merge
3d 13h
Merged PRs (30d)
4

Description

Motivation

In our zkvm, we have two sets of matrices to commit:

  1. preprocessed trace matrices: we commit it in the setup phase.
  2. witness trace matrices: they vary from instance to instance (only known at proving time)

Therefore we need to open two giga mles ($q_f$, $q_w$). Assume the preprocessed set has $K_f$ polynomials, the witness set has $K_w$ polynomials.

prover
  1. sample $c_f \in E^{k_f}$, $v_f = \sum_i \textrm{eq}(c_f, i) * C_i^f * f_i(z_r[..s])$;
  2. sample $c_w \in E^{k_w}$, $v_w = \sum_i \textrm{eq}(c_w, i) * C_i^w * w_i(z_r[..s])$;
  3. run jagged sumcheck for $v_f, q_f$ to get proof $\pi_f^1$ and then run jagged assist sumcheck to get proof $\pi_f^2$.
  4. run jagged sumcheck for $v_w, q_w$ to get proof $\pi_w^1$ and then run jagged assist sumcheck to get proof $\pi_w^2$.
  5. invoke inner PCS to batch open $q_f(z_f)$ and $q_w(z_w)$ to get a inner PCS opening proof $\pi$.
verifier
  1. sample $c_f \in E^{k_f}$, $v_f = \sum_i \textrm{eq}(c_f, i) * C_i^f * f_i(z_r[..s])$;
  2. sample $c_w \in E^{k_w}$, $v_w = \sum_i \textrm{eq}(c_w, i) * C_i^w * w_i(z_r[..s])$;
  3. verify jagged sumcheck proof $\pi_f^1$ and jagged assist sumcheck proof $\pi_f^2$;
  4. verify jagged sumcheck proof $\pi_w^1$ and jagged assist sumcheck proof $\pi_w^2$;
  5. verify inner PCS opening proof $\pi$.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

No files, tests, or entry points are named. Start by mapping the existing prover and verifier opening flow, then compare it with the two-set sequence described here. Done means supporting batched openings for both q_f and q_w, including their sumcheck, assist sumcheck, and inner PCS proofs.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
cryptography
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.