The distributed prover

This chapter describes a distributed variant of the Akita prover: how the witness is split across many machines, which parts of one folding step are local, and the single protocol change — keeping a per-machine folded response — that lets the machines avoid shuffling large witnesses between each other. The machines can be separate GPUs, accelerators, or nodes; nothing below is specific to GPUs.

What "distributed-prover friendly" means

We hold the design to three concrete criteria:

1. Distributable witness. The witness $\mathbf{s}$ can be split across independent machines so that each machine owns and processes only its share.
2. Low cross-machine communication. Machines must not exchange large payloads. Only short commitment vectors and small round-polynomial messages may cross the interconnect; the large per-machine witnesses stay put.
3. Net speed-up. The resulting scheme must stay efficient enough that the per-machine work plus the small aggregation actually realises the parallel speed-up the hardware promises.

Throughout, assume $\mathcal{M}=2^N$ machines $P_0,\dots ,P_{\mathcal{M}-1}$ (take $N=3$, so $\mathcal{M}=8$ machines). We divide the witness into $\mathcal{M}$ contiguous block ranges. When the number of live blocks is not divisible by $\mathcal{M}$, a machine owns either the floor or the ceiling of the average; when there are fewer blocks than machines, some ranges are empty.

Setup: partitioning the witness

We spell the design out in the single-opening case (one opening point $\mathbf{r}$, one commitment, one committed slot). Let $N$ be the exact number of live source ring elements, choose $M:=2^{r_{\mathsf{pos}}}$ positions per block, and set $B:=\lceil N/M\rceil$. The block-index Boolean domain has size $B_{\mathsf{dom}}:=2^{r_{\mathsf{blk}}}=nextpow2(B)$, but only the prefix $[B]$ is live. Reshape the coefficient table into $B$ blocks ${\mathbf{f}}_i\in R_q^M$, padding only the final block when $M\nmid N$. The opening point induces the inner evaluation vector $\mathbf{a}\in R_q^M$ and the live block vector $\mathbf{b}\in R_q^B$, and the evaluation is $F(\mathbf{r})={\mathbf{b}}^{\top }[{\mathbf{a}}^{\top }{\mathbf{f}}_1,\dots ,{\mathbf{f}}_B]$.

We partition the block index set $[B]$ into contiguous ranges $[B]={\mathcal{I}}_0\bigsqcup \cdots \bigsqcup {\mathcal{I}}_{\mathcal{M}-1}$, where ${\mathcal{I}}_j:=\{i\in [B]:\lfloor jB/\mathcal{M}\rfloor \le i<\lfloor (j+1)B/\mathcal{M}\rfloor \}$, and assign ${\mathcal{I}}_j$ to machine $P_j$. For $B=10$ and $\mathcal{M}=4$, these ranges are $[0,2),[2,5),[5,7),[7,10)$. This is the canonical proportional partition owned by WitnessLayout. Larger index spaces are always partitioned at the block level: for any $k\ge 1$ the block partition induces $[kB]={\mathcal{I}}_0^{[k]}\bigsqcup \cdots \bigsqcup {\mathcal{I}}_{\mathcal{M}-1}^{[k]}$.

The public key is still the three uniformly random matrices $\mathbf{A}\in R_q^{n_A\times M\delta }$, $\mathbf{B}\in R_q^{n_B\times B{n}_A\delta }$, and $\mathbf{D}\in R_q^{n_D\times B\delta }$ with $\delta :=\lceil {\log }_{b}q\rceil$. All three are prefix views of one seed-expanded matrix, so every machine regenerates the same public columns locally — no setup is broadcast. In the distributed setting we view them column-blocked, $\mathbf{B}=[{\mathbf{B}}_0\mid \cdots \mid {\mathbf{B}}_{\mathcal{M}-1}]$ and $\mathbf{D}=[{\mathbf{D}}_0\mid \cdots \mid {\mathbf{D}}_{\mathcal{M}-1}]$, where ${\mathbf{B}}_j,{\mathbf{D}}_j$ hold exactly the columns indexed by $P_j$'s blocks, and we restrict the block vector as ${\mathbf{b}}^{\top }=[{\mathbf{b}}_0^{\top }\mid \cdots \mid {\mathbf{b}}_{\mathcal{M}-1}^{\top }]$.

Component-by-component locality

We now walk each component of one folding step and check it against the three criteria.

The outer commitment $\mathbf{u}$

Machine $P_j$ stores its blocks $\{{\mathbf{f}}_i:i\in {\mathcal{I}}_j\}$ and performs the ordinary inner commit on each, restricted to its block set. For every $i\in {\mathcal{I}}_j$ it digit-decomposes the block witness ${\mathbf{s}}_i:={\mathbf{G}}_{b,M}^{-1}({\mathbf{f}}_i)\in R_q^{M\delta }$, computes the inner commitment ${\mathbf{t}}_i:=\mathbf{A}{\mathbf{s}}_i\in R_q^{n_A}$, and digitises it to ${\hat{\mathbf{t}}}_i:={\mathbf{G}}_{b_1,n_A}^{-1}({\mathbf{t}}_i)$. Writing ${\hat{\mathbf{t}}}^{(j)}:=({\hat{\mathbf{t}}}_i{)}_{i\in {\mathcal{I}}_j}$ for the inner-commitment digits it owns, $P_j$ uses only its column block ${\mathbf{B}}_j$ to form the partial outer commitment

$${\mathbf{u}}_j:={\mathbf{B}}_j{\hat{\mathbf{t}}}^{(j)}\in R_q^{n_B}.$$

The raw relation image is then the sum $\mathbf{u}={\sum }_{j=0}^{\mathcal{M}-1}{\mathbf{u}}_j$. The large local witnesses ${\hat{\mathbf{t}}}^{(j)}$ never leave $P_j$; only the short $n_B$-vectors ${\mathbf{u}}_j$ are summed. The aggregation machine negative-binary decomposes that sum through the two F maps and publishes only the 128-byte payload $p_F$ (criteria 1 and 2).

The opening commitment $\mathbf{v}$ and the claim $y$

The opening side is computed the same way. For every $i\in {\mathcal{I}}_j$, $P_j$ computes the local block evaluation $e_i:=⟨\mathbf{a},{\mathbf{f}}_i⟩$, digitises it to ${\hat{\mathbf{e}}}_i:={\mathbf{G}}_{b,1}^{-1}(e_i)\in R_q^{\delta }$, and — using only its column block ${\mathbf{D}}_j$ — forms the partial opening commitment ${\mathbf{v}}_j:={\mathbf{D}}_j{\hat{\mathbf{e}}}^{(j)}\in R_q^{n_D}$, with ${\hat{\mathbf{e}}}^{(j)}:=({\hat{\mathbf{e}}}_i{)}_{i\in {\mathcal{I}}_j}$. The global opening relation image is $\mathbf{v}={\sum }_j{\mathbf{v}}_j$. The aggregation machine compresses that sum through the two H maps and publishes only the 128-byte payload $p_H$. Each machine also forms its partial claim $y_j:={\sum }_{i\in {\mathcal{I}}_j}{b}_i{e}_i$, and the claimed evaluation is $y=F(\mathbf{r})={\sum }_j{y}_j$.

So the raw $\mathbf{u}$, raw $\mathbf{v}$, and $y$ all follow the same pattern: each machine does the same inner/outer/opening computation as the single-machine prover, but only on its own blocks. The machines aggregate only the small relation images and scalar claims; one aggregation machine derives the shared compression digits and public terminal payloads.

The folded response $\mathbf{z}$ — the hard part

After the verifier samples the folding challenges, the single-machine prover would form one global folded response

$$\mathbf{z}=\sum _{i=1}^B{c}_i{\mathbf{s}}_i\in R_q^{M\delta }.$$

But each machine only holds the blocks in ${\mathcal{I}}_j$, so it can only compute a partial fold ${\mathbf{z}}_j:={\sum }_{i\in {\mathcal{I}}_j}{c}_i{\mathbf{s}}_i\in R_q^{M\delta }$ from its partial challenges ${\mathbf{c}}^{(j)}=\{c_i{\}}_{i\in {\mathcal{I}}_j}$. Crucially, each ${\mathbf{z}}_j$ lives in the full ambient dimension $R_q^{M\delta }$ — the same size as the entire folded witness. Summing the ${\mathbf{z}}_j$ into one global $\mathbf{z}$ would require an all-reduce of this large folded-witness payload across every machine, which directly violates criterion 2.

The protocol change. Instead of reconciling the ${\mathbf{z}}_j$, we keep them separate. Each ${\mathbf{z}}_j$ becomes its own piece of the next-level witness: machine $P_j$ carries forward its own ${\mathbf{z}}_j$ and never exchanges it. In effect, the next recursive witness now contains $\mathcal{M}$ folded responses instead of one, and the machines need no $\mathbf{z}$-interaction at all.

Security accounting for the shared response

The aggregate commitment-consistency rows act on ${\mathbf{z}}_{\Sigma }:={\sum }_j{\mathbf{z}}_j$. This preserves the algebraic identity of the ordinary fold, but it changes the weak-binding envelope. The digit range check is applied separately to every ${\mathbf{z}}_j$ using one common basis and one common digit depth $\delta$. Thus a large positive coefficient in one chunk cannot be hidden by a negative coefficient in another. If the digit basis is $b=2^{\ell }$, the exact difference interval for one chunk has diameter $b^{\delta }-1$, while the difference interval for ${\mathbf{z}}_{\Sigma }$ has diameter

$$C(b^{\delta }-1),$$

where $C=\mathcal{M}$ is the response-chunk count. With ${\kappa }_1$ denoting the physical $L_1$ mass of the folding challenge, the A-role collision target is

$$4{\kappa }_{1}C(b^{\delta }-1).$$

The planner, generated schedule, and verifier admission all derive this exact raw target and select an audited A-role cell no smaller than it. A matrix sized for one response cannot be reused for several response chunks. The current SIS table does not add a separate coverage axis for the chunk count, so a two- or four-chunk schedule may use a conservative next-higher cell rather than the tightest possible collision-bound search. Every chunk retains the same full-width ${\mathbf{z}}_j$ buffer—even an empty block range contributes a full-width zero response—whereas the local ${\hat{\mathbf{e}}}^{(j)}$ and ${\hat{\mathbf{t}}}^{(j)}$ ranges follow the actual number of blocks. The number of response chunks is therefore a protocol parameter, not merely a deployment choice. Production schedules expose only a small fixed set of counts, and verifier validation caps the count so that a malicious schedule cannot force arbitrarily fragmented setup evaluation.

Why only the first few rounds keep per-machine $\mathbf{z}$

Keeping a separate ${\mathbf{z}}_j$ per machine is not free, so we do it only for a constant number of leading rounds. Two reasons:

1. Proof size and fold depth. The $\mathcal{M}$ separate ${\mathbf{z}}_j$ enlarge the next witness relative to a single $\mathbf{z}$. Carrying that growth into the tail and final rounds would inflate the proof size and the number of fold levels, so those rounds keep the single-response protocol.
2. Where the cost actually is. Only the first few rounds are large enough to be worth distributing. Once the scheduled recursive folds have reduced the full witness, the remaining rounds are cheap and run fine on a single machine. This does not require the root fold itself to shrink the witness.

So the schedule fixes a constant number of distributed rounds. Those leading rounds retain one ${\mathbf{z}}_j$ per machine; the later rounds return to the single-response Akita protocol on one machine.

The next-round witness and the relation change

After the distributed rounds, each machine $P_j$ holds its own $({\hat{\mathbf{t}}}^{(j)},{\hat{\mathbf{e}}}^{(j)},{\mathbf{z}}_j,{\mathbf{r}}_j)$ and can proceed to the next round on its own. Supporting this requires changing the witness format and the relation matrix $\mathbf{M}$ so the relation is stated over the concatenation of the per-machine witnesses rather than over one global folded response. The rest of this chapter makes that change precise.

The per-machine partial root relation

Each machine holds its partial witness and the matching partial commitments, plus the fold of its own blocks. Over $R_q$, machine $P_j$ satisfies:

$$\begin{array}{rlrl}{\mathbf{B}}_j{\hat{\mathbf{t}}}^{(j)}& ={\mathbf{u}}_j& & \text{(partial outer-commitment)}\\ {\mathbf{D}}_j{\hat{\mathbf{e}}}^{(j)}& ={\mathbf{v}}_j& & \text{(partial opening-commitment)}\\ ({\mathbf{c}}^{(j)\top }\otimes {\mathbf{G}}_{b,1}){\hat{\mathbf{e}}}^{(j)}& =⟨\mathbf{a},{\mathbf{G}}_{b,|{\mathcal{I}}_j|}{\mathbf{z}}^{(j)}⟩& & \text{(partial folded-evaluation consistency)}\\ ({\mathbf{c}}^{(j)\top }\otimes {\mathbf{G}}_{b,n_A}){\hat{\mathbf{t}}}^{(j)}& =\mathbf{A}{\mathbf{z}}^{(j)}& & \text{(partial folded-commitment consistency)}\end{array}$$

Stacking these, $P_j$ has a local partial root relation

$$\left[\begin{array}{ccc}{\mathbf{D}}_j& 0& 0\\ 0& {\mathbf{B}}_j& 0\\ {\mathbf{c}}^{(j)\top }\otimes {\mathbf{G}}_{b,1}& 0& -{\mathbf{a}}^{\top }{\mathbf{G}}_{b,M}\\ 0& {\mathbf{c}}^{(j)\top }\otimes {\mathbf{G}}_{b,n_A}& -\mathbf{A}\end{array}\right]\left[\begin{array}{c}{\hat{\mathbf{e}}}^{(j)}\\ {\hat{\mathbf{t}}}^{(j)}\\ {\mathbf{z}}^{(j)}\end{array}\right]=\left[\begin{array}{c}{\mathbf{v}}_j\\ {\mathbf{u}}_j\\ 0\\ 0\end{array}\right].$$

Denote the block matrix by ${\mathbf{M}}_j$, the local witness by ${\mathbf{w}}_j:=({\hat{\mathbf{e}}}^{(j)},{\hat{\mathbf{t}}}^{(j)},{\mathbf{z}}^{(j)})$, and the right-hand side by ${\mathbf{h}}_j:=({\mathbf{v}}_j,{\mathbf{u}}_j,0,0)$, so the local relation is compactly ${\mathbf{M}}_j{\mathbf{w}}_j={\mathbf{h}}_j$.

The virtually shared root relation

The verifier never sees the local ${\mathbf{h}}_j$; it sees only the public output $\mathbf{h}=(\mathbf{v},\mathbf{u},0,0)$, whose entries are the sums of the partial values, $\mathbf{v}={\sum }_j{\mathbf{v}}_j$ and $\mathbf{u}={\sum }_j{\mathbf{u}}_j$. So instead of exposing the local right-hand sides, the machines jointly prove one virtually shared root relation. With $\mathbf{w}:=({\mathbf{w}}_0,\dots ,{\mathbf{w}}_{\mathcal{M}-1})$ and the horizontal concatenation $\mathbf{M}:=[{\mathbf{M}}_0\mid \cdots \mid {\mathbf{M}}_{\mathcal{M}-1}]$,

$$\mathbf{Mw}=\sum _{j=0}^{\mathcal{M}-1}{\mathbf{M}}_j{\mathbf{w}}_j=\sum _{j=0}^{\mathcal{M}-1}{\mathbf{h}}_j=\mathbf{h}.$$

The relation is virtually shared because no machine materialises the full witness $\mathbf{w}$ or the full matrix $\mathbf{M}$: $P_j$ holds only ${\mathbf{w}}_j$ and its column blocks ${\mathbf{B}}_j,{\mathbf{D}}_j$, while the verifier checks the single public right-hand side obtained by summing the partial commitments.

Ring-switch lift and next-level commitment

Each machine lifts its partial relation ${\mathbf{M}}_j{\mathbf{w}}_j={\mathbf{h}}_j$ from $R_q={\mathbb{Z}}_q[X]/(X^d+1)$ to ${\mathbb{Z}}_q[X]$: there is a unique quotient ${\mathbf{r}}_j\in ({\mathbb{Z}}_q^{<d}[X]{)}^n$, with $n=n_A+n_B+n_D+1$, such that

$${\mathbf{M}}_j{\mathbf{w}}_j={\mathbf{h}}_j+(X^d+1){\mathbf{r}}_j\text{over }{\mathbb{Z}}_q[X].$$

Summing the local identities, the global quotient is the coefficient-wise modular sum $\mathbf{r}={\sum }_j{\mathbf{r}}_j$, just as the global commitments are sums of the partial commitments. The aggregated quotient is digit-decomposed as $\hat{\mathbf{r}}:={\mathbf{G}}_{b,n}^{-1}(\mathbf{r})$, recovering the same ring-switch witness shape as the single-machine protocol — except the root witness stays written as the concatenation of the per-machine witnesses.

Let ${\mathbf{w}}^{\prime }:=(\mathbf{w}\Vert \hat{\mathbf{r}})$ be the extended witness. The lifted relation is ${\mathbf{M}}_{\mathrm{ext}}{\mathbf{w}}^{\prime }=\mathbf{h}$ over ${\mathbb{Z}}_q[X]$, with

$${\mathbf{M}}_{\mathrm{ext}}:=[\mathbf{M}\mid -(X^d+1)(I_n\otimes {\mathbf{g}}^{\top })],{\mathbf{g}}^{\top }:=(1,b,\dots ,b^{\delta -1}).$$

The extended witness is assembled into the coefficient table of the next-level multilinear polynomial: each machine $P_j$ contributes its segment ${\mathbf{w}}_j$, and a pre-assigned aggregation machine additionally contributes the quotient segment $\hat{\mathbf{r}}$. The machines then run the ordinary inner/outer commit at the next level's parameters on their assigned portions and sum the partial next-level relation images into one ${\mathbf{u}}^{\prime }$. The aggregation machine compresses ${\mathbf{u}}^{\prime }$ and retains the two shared F digit vectors. The verifier sees exactly the single-machine recursive interface: one 128-byte extended-witness payload and one next-level opening claim.

Ring-switch and row-batching

For ${\mathbf{M}}_{\mathrm{ext}}{\mathbf{w}}^{\prime }=\mathbf{h}$ the verifier samples the ring-switching challenge $\alpha \leftarrow {\mathbb{F}}_{q^k}$ and the row-batching point $\tau \leftarrow {\mathbb{F}}_{q^k}^{\lceil {\log }_{2}n\rceil }$. Viewing the machines as one virtual prover, both sides evaluate the extended matrix at $X=\alpha$, obtaining ${\mathbf{M}}_{\mathrm{ext}}(\alpha )$ and the target $\mathbf{h}(\alpha )$, i.e. $n$ row equations. Writing the extended matrix as ${\mathbf{M}}_{\mathrm{ext}}=[{\mathbf{M}}_0\mid \cdots \mid {\mathbf{M}}_{\mathcal{M}-1}\mid {\mathbf{M}}_{\Delta }]$ with the quotient block ${\mathbf{M}}_{\Delta }:=-(X^d+1)(I_n\otimes {\mathbf{g}}^{\top })$, the row equations at $X=\alpha$ become

$$\sum _{j=0}^{\mathcal{M}-1}{\mathbf{M}}_j(\alpha ){\mathbf{w}}_j(\alpha )+{\mathbf{M}}_{\Delta }(\alpha )\hat{\mathbf{r}}(\alpha )=\mathbf{h}(\alpha ).$$

The verifier batches the $n$ rows with the equality weights $\widetilde{\mathrm{eq}}(\tau ,i)$. For machine $P_j$ define its local $\tau$-weighted row combination $m_{\tau }^{(j)}(x):={\sum }_i\widetilde{\mathrm{eq}}(\tau ,i){\mathbf{M}}_j(\alpha )(i,x)$, and similarly $m_{\tau }^{(\Delta )}(x)$ for the quotient block; the batched target is $V_{\alpha }:={\sum }_i\widetilde{\mathrm{eq}}(\tau ,i)h_i(\alpha )$. Let $\tilde{\alpha }(y)$ be the multilinear extension of $(1,\alpha ,\dots ,{\alpha }^{d-1})$, and let ${\Omega }_j$, ${\Omega }_{\Delta }$ denote the next-level witness-table coordinates of ${\mathbf{w}}_j$ and $\hat{\mathbf{r}}$. The full batched claim is

$$\sum _{j=0}^{\mathcal{M}-1}\sum _{(x,y)\in {\Omega }_j}{\tilde{\mathbf{w}}}_j(x,y)\tilde{\alpha }(y)m_{\tau }^{(j)}(x)+\sum _{(x,y)\in {\Omega }_{\Delta }}\widetilde{\hat{\mathbf{r}}}(x,y)\tilde{\alpha }(y)m_{\tau }^{(\Delta )}(x)=V_{\alpha }.$$

Compared with the single-machine claim ${\sum }_{(x,y)}{\tilde{\mathbf{w}}}^{\prime }(x,y)\tilde{\alpha }(y)m_{\tau }(x)=V_{\alpha }$, the distributed claim simply partitions both witness-dependent factors. Machine $P_j$ owns a subset ${\Omega }_j$ of the next-level witness table and the matching restriction $m_{\tau }^{(j)}$ of the row-batched weight, so no machine materialises the full witness table or the full weight function. In the subsequent sum-check the same decomposition holds round by round: each machine computes the round-polynomial contribution for the coordinates it owns, and the machines aggregate only the small round-polynomial coefficients. The verifier sees the same batched claim as in the single-machine protocol.

Recap against the three criteria

• Distributable witness. The balanced block partition gives each machine a disjoint contiguous share, and every step — inner/outer/opening commit, the partial fold, the quotient lift, the next-level commit, and the sum-check — is computed per machine over its own blocks.
• Low communication. Only short objects ever cross machines: the $n_B/n_D$-sized partial commitments ${\mathbf{u}}_j,{\mathbf{v}}_j$, the scalar claims $y_j$, the coefficient-wise quotient sum, and the small per-round sum-check messages. The large items — the inner/opening digits and, decisively, the folded responses ${\mathbf{z}}_j$ — never leave their machine. Keeping a per-machine ${\mathbf{z}}_j$ is exactly the change that removes the one all-reduce that would otherwise dominate communication.
• Net speed-up. Per-machine ${\mathbf{z}}_j$ is kept only for the constant block of leading (large) rounds; afterward the prover reverts to the single-machine protocol, so the witness-growth and extra fold levels are bounded and the distributed parallelism translates into an end-to-end win.