One Tensor Commitment for Tables of Every Height

§ Abstract

We commit every table of a multi-table AIR proof in one tensor commitment: one Merkle tree per oracle whose leaf hashes every table’s part of a codeword column, one fold vector, one set of $t$ opened columns, and one sumcheck that reduces every table’s evaluation claims to a shared point. Committed separately, $T$ tables pay $T$ fold vectors and $T$ query sets of $t = 287$ columns each. A table of $2^n$ rows sits on a grid of $2^c$ columns: a shorter table packs $2^{c-n}$ of its columns into one message row, a taller one keeps $2^{n-c}$ grid rows, and zero extension to a common height makes the pool a single table, whose proximity error is the single-table error with $\Sigma + m - 1$ batched units for $\Sigma$ slot roles and $m$ masters. Four rules carry the construction, and for each we give the forgery or the inconsistency its violation admits. The evaluation argument is sound with its error stated in full: an accepting verifier reads, for every table, the evaluations of the columns decoded from the one commitment. The split $c$ minimizes an integer byte count that charges the blind claims of packed tables, and both parties derive it from absorbed data. Merkle leaves without salts need $t + 1$ random support cells per row: at $t$ cells every unopened leaf of a tree without blind rows is a function of the witness and the verifier’s view, and at $t + 1$ every unopened symbol is uniform given that view; the openings, the fold vector and both Merkle trees are then simulatable without the witness. In Hekate’s zero-knowledge mode, against separate commitments, proof size changes by $-36$ to $-56$% on ML-KEM-768, ML-DSA and AES and by $-88$% on RSA-2048.

§ 1 Introduction

A proof over $T$ AIR tables can open all of them with one fold vector and one set of queried columns. We commit every table of a proof in one Merkle tree per oracle and reduce every table’s evaluation claims with one sumcheck.

The setting is a tensor polynomial commitment in the style of Ligero and Brakedown (Ames et al. 2023; Golovnev et al. 2021) over the binary tower $\mathbb{F}_{2^{128}}$ (Cantor 1989), with a Reed-Solomon row code evaluated by the additive FFT (Lin, Chung, and Han 2014) and claims on bit-packed columns reduced by ring-switching (Diamond and Posen 2024). Each table carries its own ZeroCheck, and LogUp buses (Haböck 2022) connect the tables. Every table then owes evaluation claims on its committed columns at points of its own height.

Committed separately, table $i$ pays a Merkle root, a fold vector of $S + 2^{c_i}$ field elements for its own split $c_i \le n_i$, and $t$ opened columns with their Merkle multiproof. For the seven tables of an ML-DSA-65 verification this layout produced a zero-knowledge proof of $2\,959$ KiB.

In the pool, a split $c$ fixes one grid of $2^c$ columns for every table. A table of $2^n$ rows with $n \ge c$ keeps $2^{n-c}$ grid rows; a table with $n < c$ packs $2^{c-n}$ of its columns side by side into one message row, and the $c - n$ bits that select a column become variables of the evaluation sumcheck. One leaf hashes every table’s digest of one codeword column. One sumcheck over $v = \max(c, \max_i n_i)$ variables carries every table, a table with fewer variables entering the remaining rounds through the factor $\mathrm{eq}(z, 0)$. After zero extension the pool is one table of $2^v$ rows whose slots vanish above their table’s height (Lemma 3), and its proximity error is the single-table error on that shape (Section 5).

Four rules carry the construction (Section 4): the slot challenge $\eta$ follows every table’s claims, every master carries its own power of the line challenge $\lambda$, a finished table is extended by $\mathrm{eq}(z, 0)$ and never by a constant, and a short table’s block bits are sumcheck variables. The split minimizes an integer byte count (Section 6). Leaf hiding needs one support cell more than the query count (Section 7): at $S = t$ an unopened leaf of a tree without blind rows is a function of the witness, which a guess can test against the root.

Three theorems carry the security. Theorem 2 is completeness. Theorem 6 binds every claim of every table to the columns decoded from the pool’s commitment, with error $\varepsilon_{\mathrm{prox}} + ((1 + \rho)/2)^t$ for the commitment and terms without the factor $W$ for the batching; Lemma 4 derives $\varepsilon_{\mathrm{prox}}$ from the curve bound of (Ben-Sasson et al. 2020) and the interleaving and tensor bounds of (Diamond and Gruen 2024). Theorem 14 simulates the openings, the fold vector and both Merkle trees without the witness in the random oracle model.

In Hekate’s zero-knowledge mode the pool changes proof size by $-36$ to $-56$% on ML-KEM-768, ML-DSA and AES and by $-88$% on RSA-2048 (Section 8).

Batching polynomials of one length under one commitment is the interleaved setting of Ligero and Brakedown, and the proximity bounds are those of (Ben-Sasson et al. 2020) and (Diamond and Gruen 2024). Matrices of differing heights are committed under one Merkle tree in FRI stacks (The Plonky3 Authors 2026) and in S-two, whose whitepaper shows cross-domain correlated agreement for multi-table circle FRI (Carmon et al. 2026), and claims on columns of differing heights are reduced inside the sumcheck by a jagged reduction (Hemo et al. 2025; Duan 2026). Beneath that reduction, SP1 Hypercube cuts the trace into columns of one fixed height and commits them as one interleaved batch in the manner of Ligero (Succinct Labs 2026); Binius64 lifts each shorter oracle to the common variable count by zero padding, the lift carrying the factor $\mathrm{eq}(0, \cdot)$ on the high variables, and batches the lifted oracles in one sumcheck and one BaseFold (The Binius Developers 2026, secs. 5.3-5.4). Here the heights are resolved in the layout: a tall table keeps its grid rows, a short one packs its columns into one message row, zero extension in place makes the pool one interleaved codeword, and one fold vector, one query set and one proximity term cover every table. New here are the layout for tables of different heights under one fold vector, its soundness and hiding proofs, the four rules with the attacks their violations admit, the split objective, the support requirement for unsalted leaves, and the measurements. The per-table ZeroCheck and LogUp arguments are unchanged and outside this note. The outer argument of (Kochergin 2026), which proves the verifier’s predicate on one-time-padded scalars, runs only in zero-knowledge mode, and we assume its soundness and zero-knowledge.

§ 2 Notation and the row code

Throughout, $\mathbb{F}= \mathbb{F}_{2^{128}}$, built as a tower of quadratic extensions (Cantor 1989), and $|\mathbb{F}| = 2^{128}$. For $a, x \in \mathbb{F}^n$ put $\mathrm{eq}(a, x) = \prod_j (a_j x_j + (1 + a_j)(1 + x_j))$. A table of $2^n$ rows commits each column $f$ as the multilinear polynomial in $n$ variables that agrees with $f$ on $\{0,1\}^n$, and $\tilde f(a) = \sum_{x \in \{0,1\}^n} \mathrm{eq}(a, x) f(x)$ is its value at $a$.

Fix a split $c$ and put $L = 2^c$. A message is a pair $(\xi, d)$ with a support $\xi \in \mathbb{F}^S$, uniform in zero-knowledge mode, and data $d \in \mathbb{F}^L$. Its codeword is the polynomial $\sum_{k < S} \xi_k X_k + \sum_{k < L} d_k X_{S+k}$ evaluated on an $\mathbb{F}_2$-subspace of $W$ points, where $X_0, X_1, \ldots$ is the novel polynomial basis of (Lin, Chung, and Han 2014) over a Cantor basis, $\deg X_k = k$. The code has length $W = 2L$ when $S \le L$ and the query term below reaches 100 bits at that length. At $S = 288$ and $t = 287$ the term reads 82 bits at $c = 10$ and 100.1 at $c = 11$: a grid with $c \le 10$ takes $L$ support cells at $W = 4L$, and every deployed split has $c \ge 12$. The row code is Reed-Solomon of dimension $S + L$ and length $W$, hence MDS, with minimum distance $W - S - L + 1$.

A table of $2^n$ rows with $n \ge c$ stores a column $f$ on $R = 2^{n-c}$ grid rows: grid row $g \in \{0,1\}^{n-c}$ holds $f(x, g)$ for $x \in \{0,1\}^c$. The columns of a table are grouped into slots, one slot per column here, and each pair of a slot and a grid row is one message with its own support. The encoded messages form a matrix of $W$ columns, and the commitment is a Merkle tree over those columns.

The verifier batches a table’s claims into at most two master claims. Each unit $u$ of the table, a committed column or a ring-switched group of bit columns, carries a power $\eta^{\sigma(u)}$ of a slot challenge $\eta$, and a slot’s coefficient $\kappa_{k,s}$ in master $k$ is the sum of the powers of its units assigned to $k$. Master $k$ is $M_k = \sum_s \kappa_{k,s} D_s$, $D_s$ the multilinear polynomial of slot $s$, and a sumcheck reduces the table’s batched claims to the values $\mu_k = M_k(r)$ at one point $r$. The prover sends a fold vector $$q = \sum_{k} \lambda^k \sum_{s} \kappa_{k,s} \sum_{g} \mathrm{eq}(r_{\mathrm{hi}}, g)\, (\xi_{s,g}, d_{s,g}),$$ where $r_{\mathrm{hi}}$ are the last $n - c$ coordinates of $r$ and $r_{\mathrm{lo}}$ the first $c$. The verifier checks the line $\langle d_q, \mathrm{eq}(r_{\mathrm{lo}}, \cdot) \rangle = \sum_k \lambda^k \mu_k$ on the data part $d_q$ of $q$, draws $t$ columns $j$, and checks that the encoding of $q$ at $j$ equals the same combination of the opened symbols, with their Merkle paths.

The single-table analysis bounds two terms. The query term is $-t \log_2((1 + \rho)/2)$ bits with $\rho = (S + L)/W$ (Golovnev et al. 2021, App. B, Thm. 7). The proximity error is $(\theta + U - 1) W/|\mathbb{F}|$, with $\theta = \log_2 R$ the depth of the tensor over grid rows (Diamond and Gruen 2024) and $U - 1$ the degree of the batching curve over $U$ units (Ben-Sasson et al. 2020, Thm. 1.5); Lemma 4 proves this form for the pool and Section 5 counts $U$.

Interleaved codes and proximity gaps.

Write $C$ for the row code and $e = \lfloor (W - S - L)/2 \rfloor$ for its unique decoding radius. For a matrix $\mathcal{U} \in \mathbb{F}^{N \times W}$ let $d^N(\mathcal{U}, C^N)$ be the least number of columns on which $\mathcal{U}$ differs from a matrix whose every row is a codeword; $\mathcal{U}$ is $e$-close if $d^N(\mathcal{U}, C^N) \le e$, and then that matrix is unique, each row of $\mathcal{U}$ lying within $e$ of one codeword, and we call it the decoding of $\mathcal{U}$. Two bounds carry Section 5, both in this unique-decoding regime. The curve bound (Ben-Sasson et al. 2020, Thm. 1.5): for words $u_0, \ldots, u_l \in \mathbb{F}^W$, if $\Pr_z[d(\sum_{i \le l} z^i u_i, C) \le e] > l W/|\mathbb{F}|$ over $z \in \mathbb{F}$, then the matrix with rows $u_0, \ldots, u_l$ is $e$-close. The tensor bound: by (Diamond and Gruen 2024, Thms. 1 and 2) every interleaving $C^N$ has the proximity gap for affine lines of $C$, with false-witness bound $W$, and by (Diamond and Gruen 2024, Thm. 3) applied to $C^N$ it has tensor-style gaps with the same parameters: for matrices $\mathcal{U}_0, \ldots, \mathcal{U}_{2^\vartheta - 1} \in \mathbb{F}^{N \times W}$, if $\Pr_r[d^N(\sum_g \mathrm{eq}(r, g)\, \mathcal{U}_g, C^N) \le e] > \vartheta W/|\mathbb{F}|$ over $r \in \mathbb{F}^\vartheta$, then the matrix that stacks the $\mathcal{U}_g$ is $e$-close.

Model.

The protocol is public-coin. The two roots fix the leaves of both trees, and we take the trees as binding to the committed symbols of every slot and grid row, the rows an extractor reads from the prover’s queries to $H$ when $H$ is a random oracle, with the collision term and the Fiat-Shamir compilation of the interactive protocol accounted as in (Ben-Sasson, Chiesa, and Spooner 2016; Golovnev et al. 2021). Section 5 extends those rows by zero rows to the matrix $\mathcal{P}$, and soundness is stated against it: Theorem 6 bounds the probability that the verifier accepts while some claim differs from the evaluation of the column decoded from $\mathcal{P}$, and the extractor of Corollary 8 outputs those columns. Hiding is honest-verifier: Theorem 14 gives a simulator of the pool’s part of the verifier’s view in zero-knowledge mode that reads no witness, with $H$ a random oracle and the one-time pad of the masked scalars uniform.

§ 3 The pool

The pool is every table of a proof in a fixed order, $T$ tables with $2^{n_i}$ rows each. The split $c$ is derived in Section 6; put $v = \max(c, \max_i n_i)$ and $v_i = \max(c, n_i)$. Table $i$ uses $R_i = 2^{\max(n_i - c, 0)}$ grid rows and packs $P_i = 2^{\max(c - n_i, 0)}$ columns per slot.

A table with $n_i \ge c$ is laid out as in Section 2. A table with $n_i < c$ has one grid row, and its slot holds $P_i$ columns side by side: column $(s, b)$ for $b \in \{0,1\}^{c - n_i}$ occupies positions $b \cdot 2^{n_i} + x$, and $D_s(x, b)$ is a multilinear polynomial in $c$ variables. A class of columns fills $\lceil \mathrm{count}/P_i \rceil$ slots, the last closed by zero blocks. In zero-knowledge mode table $i$ adds $K P_i$ whole blind columns, $K = 1$ in the deployed system, and its ring-switched units a blind of their own (Diamond 2025). The slot roles of every table are numbered by one index $\sigma$ running over the pool in table order, $\Sigma$ in all, and the pool has $m$ masters, one or two per table.

Every message of every table is encoded at the same width $W$. Leaf $j$ of the trace tree is $$H(\chi_{0,j} \,\|\, \cdots \,\|\, \chi_{T-1,j} \,\|\, \mathtt{0x02}), \qquad \chi_{i,j} = H(\mathrm{part}_{i,j} \,\|\, \mathtt{0x00}),$$ where $\mathrm{part}_{i,j}$ is the column-$j$ symbols of table $i$ over its slots and grid rows, and an inner node hashes its two children and 0x01. The verifier hashes $T + 1$ times per opened column. The LogUp helper columns $h$ of the bus-carrying tables form slots in a second tree of the same width, committed after the bus challenges; a pool with no bus has none. The fold vector and the queries cover both trees.

The transcript runs in this order.

1. The main table’s dimensions, then each chiplet’s in pool order, then the trace root; in zero-knowledge mode, the root of the one-time pad.

2. The LogUp challenges $\gamma, \beta$; every lookup bus’s maximal height, then each bus’s point; then the root of the $h$ tree.

3. For each table in pool order: its claimed bus sums, its ZeroCheck challenge and rounds, its $h$ evaluations and its column claims.

4. The slot challenge $\eta$; $\max_i (c - n_i)$ block challenges, of which table $i$ reads the first $c - n_i$ as $\rho_i$; the ring-switching challenge when a table carries ring units; the eval sumcheck; the masters $\tilde \mu_k$ in pool order; $\lambda$ when $m > 1$; the fold vector $q$; the $t$ query columns; both openings.

For table $i$ split $y \in \mathbb{F}^v$ as $y = (x, b, z)$ with $x \in \mathbb{F}^{n_i}$, $b \in \mathbb{F}^{v_i - n_i}$ and $z \in \mathbb{F}^{v - v_i}$; a tall table has no $b$, and a table with $v_i = v$ has no $z$. The eval sumcheck runs over $v$ variables, low variable first, on $$F(y) = \sum_i \mathrm{eq}(z, 0)\, \mathrm{eq}(\rho_i, b) \sum_{k \in K_i} \omega_k(x)\, M_k(x, b), \qquad\text{(1)}$$ where $K_i$ are the masters of table $i$ and $\omega_k$ are the public multilinear weights defined below. Its initial claim is $\sum_i \tau_i$, the batched value of every table’s claims, formed as follows.

Table $i$ claims its columns at one point $a_i \in \mathbb{F}^{n_i}$, the point its ZeroCheck ended at, and at the next row: a column $f$ claims the pair $(\tilde f(a_i), \tilde f_{+}(a_i))$, $f_{+}(x) = f(x + 1)$ the column shifted by one row. A unit is a whole column $f$, or a group of $J \le 128$ bit columns $t_0, \ldots, t_{J - 1}$ that one column packs as $f = \sum_v \pi_v t_v$ over the tower basis $(\pi_v)$ of $\mathbb{F}$ over $\mathbb{F}_2$; a ring unit claims the $2J$ values $\tilde t_v(a_i)$ and $\tilde t_{v,+}(a_i)$. Every unit $u$ has a slot $s(u)$, a block $b(u)$ of that slot, a slot role $\sigma(u)$ and a master $k(u)$; the units of a slot fall into roles, ring roles and whole roles, each role holding at most one unit per block of the slot, and $\kappa_{k,s}$ sums $\eta^{\sigma}$ over the roles $\sigma$ of slot $s$ in master $k$. Blocks of a slot that hold no unit are zero columns. Once every table has claimed, the verifier draws $\eta$, the block challenges $\rho_i$ and, when ring units exist, $r'' \in \mathbb{F}^{\nu}$ with $\nu = \log_2 128 = 7$, and gives unit $u$ the value $$y_u = c_u + \eta^{\Sigma} c'_u \quad\text{or}\quad y_u = \sum_{v < J} \pi_v \bigl( \phi_{r''}(c_{u,v}) + \eta^{\Sigma} \phi_{r''}(c'_{u,v}) \bigr),$$ $c$ and $c'$ the claims at $a_i$ and at the next row, where $\phi_{r''}(x) = \sum_{w \in \{0,1\}^\nu} \mathrm{eq}(r'', w)\, \mathrm{bit}_w(x)$ batches the tower coordinates of $x \in \mathbb{F}$ and is $\mathbb{F}_2$-linear. Then $$\tau_i = \sum_{u \in i} \eta^{\sigma(u)}\, \mathrm{eq}(\rho_i, b(u))\, y_u .$$ The weight of the whole master of table $i$ is $\omega_k = \mathrm{eq}(a_i, \cdot) + \eta^{\Sigma} K(a_i, \cdot)$, where $K(a_i, \cdot)$ is the multilinear weight with $\sum_x K(a_i, x) f(x) = \tilde f_{+}(a_i)$ for every column $f$; the weight of the ring master is $\omega_k = \Phi_{r''}(\mathrm{eq}(a_i, \cdot)) + \eta^{\Sigma} \Phi_{r''}(K(a_i, \cdot))$, where $\Phi_{r''}(w)$ is the multilinear extension of $x \mapsto \phi_{r''}(w(x))$ on $\{0,1\}^{n_i}$, evaluated as in (Kochergin 2026). Each round polynomial has degree 2. At the final point $r = (r_x, r_b, r_z)$, read per table, the verifier checks $$F(r) = \sum_i \mathrm{eq}(r_z, 0)\, \mathrm{eq}(\rho_i, r_b) \sum_{k \in K_i} \omega_k(r_x)\, \mu_k \qquad\text{(2)}$$ against the masters the prover then sends, $\tilde \mu_k = \mathrm{eq}(r_z, 0)\, \mu_k$ for the master $k$ of table $i$ with $\mu_k$ the claimed value of $M_k(r_x, r_b)$. Let $r_{\mathrm{lo}}, r_{\mathrm{hi}}$ be the first $c$ and the last $v - c$ coordinates of $r$. The fold vector is $$q = \sum_s \Bigl( \sum_k \lambda^k \kappa_{k,s} \Bigr) \sum_{g < R_{i(s)}} \mathrm{eq}(r_{\mathrm{hi}}, g)\, (\xi_{s,g}, d_{s,g}), \qquad\text{(3)}$$ with $g$ read as a point of $\{0,1\}^{v-c}$, and the verifier checks the line $$\langle d_q, \mathrm{eq}(r_{\mathrm{lo}}, \cdot) \rangle = \sum_k \lambda^k \tilde \mu_k \qquad\text{(4)}$$ and, at each of the $t$ drawn columns $j$, that the encoding of $q$ equals the same combination (3) of the opened symbols of both trees.

Lemma 1. For an honest prover, (4) holds.

Proof. It suffices to show $\sum_{g < R_i} \mathrm{eq}(r_{\mathrm{hi}}, g) \langle d_{s,g}, \mathrm{eq}(r_{\mathrm{lo}}, \cdot) \rangle = \mathrm{eq}(r_z, 0) D_s(r_x, r_b)$ for each slot $s$ of table $i$. If $n_i \ge c$, then $r_{\mathrm{lo}} = r_x$ restricted to its first $c$ coordinates, and for $g < R_i$ the factor $\mathrm{eq}(r_{\mathrm{hi}}, g)$ splits as $\mathrm{eq}(r', g)\, \mathrm{eq}(r_z, 0)$, $r'$ the coordinates $c, \ldots, n_i - 1$ of $r$; the sum over $g$ and the inner product together evaluate $D_s$ at $r_x$. If $n_i < c$, then $R_i = 1$, $r_{\mathrm{lo}} = (r_x, r_b)$ and $\mathrm{eq}(r_{\mathrm{hi}}, 0) = \mathrm{eq}(r_z, 0)$, and the inner product is $D_s(r_x, r_b)$ by the layout of packed columns. Summing over slots with the coefficients of (3) gives $\sum_k \lambda^k \tilde \mu_k$. ◻

Theorem 2 (completeness). For an honest prover the verifier accepts.

Proof. Write $\langle \omega, f \rangle = \sum_{x} \omega(x) f(x)$ over the cube of the table. For a whole unit, $y_u = \tilde f(a_i) + \eta^{\Sigma} \tilde f_{+}(a_i) = \langle \omega_k, f \rangle$ by the definition of $K$. For a ring unit, $f(x) = \sum_v \pi_v t_v(x)$ with $t_v(x) \in \mathbb{F}_2$, and $\phi_{r''}$ is $\mathbb{F}_2$-linear, whence $$\sum_x \phi_{r''}(\mathrm{eq}(a_i, x))\, f(x) = \sum_v \pi_v\, \phi_{r''}\Bigl( \sum_x \mathrm{eq}(a_i, x)\, t_v(x) \Bigr) = \sum_v \pi_v\, \phi_{r''}(\tilde t_v(a_i)),$$ and likewise with $K(a_i, \cdot)$ and $t_{v,+}$; again $y_u = \langle \omega_k, f \rangle$. A unit of table $i$ in slot $s$ at block $b$ has $f = D_s(\cdot, b)$, a tall table having one block. Summing (1) over $\{0,1\}^v$, $\sum_z \mathrm{eq}(z, 0) = 1$, and since $\kappa_{k,s}$ sums $\eta^{\sigma}$ over the roles $\sigma$ of slot $s$ in master $k$ and a role’s units run over the blocks of its slot, the other blocks holding zero columns, $$\sum_{y} F(y) = \sum_i \sum_{k \in K_i} \sum_s \kappa_{k,s} \sum_b \mathrm{eq}(\rho_i, b) \langle \omega_k, D_s(\cdot, b) \rangle = \sum_i \sum_{u \in i} \eta^{\sigma(u)}\, \mathrm{eq}(\rho_i, b(u))\, y_u = \sum_i \tau_i .$$ The round polynomials of $F$ have degree at most 2 in each variable, and $F(r)$ is (2) with $\mu_k = M_k(r_x, r_b)$. The line is Lemma 1. The encoding is linear, and the encoding of $q$ at a column is the combination (3) of the rows’ symbols there. ◻

§ 4 Four rules

Each rule below is necessary. An interactive simulation over $\mathbb{F}$ with the deployed additive FFT, on four tables of $2^8$, $2^7$, $2^4$ and $2^3$ rows at $c = 6$, $S = 16$, $W = 512$ and 24 queries, exhibits the forgery or the inconsistency of each violation. The verifier of the final build rejected the forging provers of the first two rules in both modes.

1. The slot challenge $\eta$ follows the claims of every table. A prover that knows $\eta$ before it fixes the claims of one table moves two of them by $\delta_1, \delta_2$ with $\delta_1 \eta^{a_1} + \delta_2 \eta^{a_2} = 0$. The batched value $\tau_i$ is unchanged and every later check passes. The forging prover that drew $\eta$ from a copy of the transcript ahead of the last table’s claims was rejected, at the sumcheck in base mode and at the outer argument’s linear test in zero-knowledge mode, because the verifier draws $\eta$ after those claims.

2. Every master carries its own power $\lambda^k$. Under one pair $(1, \lambda)$ for the whole pool, a whole master of table $i$ and one of table $i'$ enter (4) with the same coefficient, and one claim error routed through the sumcheck into both masters cancels there in characteristic 2. The forging prover carried the drift through the eval rounds and moved the first and the last whole master; the verifier rejected it at the line.

3. A table with $v_i < v$ enters the rounds beyond $v_i$ through $\mathrm{eq}(z, 0)$. Carried as a constant $a$ instead, it contributes $\sum_{z \in \{0,1\}^{v - v_i}} a = 2^{v - v_i} a = 0$ to the initial claim: in characteristic 2 every shorter table drops out, and its claims go unchecked. In the simulation a forged claim on the $2^3$-row table left the target of the constant-padded sumcheck unchanged.

4. The block bits of a short table are sumcheck variables. Opened at its own point $(r_x, \rho_i)$, a short table’s master is another linear form on its slot than the one (4) applies to $q$, and the line fails for an honest prover. In the simulation the two points disagreed on one slot.

The root of the $h$ tree precedes the first ZeroCheck challenge of every table, the rule a single table already obeys, held across the pool.

The proof of Theorem 6 consumes the rules in order: rule 1 fixes the claim polynomial of step 6 before $\eta$, rule 2 separates the masters on the line in step 3, rule 3 is the identity $\sum_z \mathrm{eq}(z, 0) = 1$ that step 5 takes from Theorem 2, and rule 4 is the identity of Lemma 1 that step 3 applies to the decoded data.

§ 5 Soundness of the pool

To the verifier the pool is one table, and its proximity error is the single-table error with $U = \Sigma + m - 1$. Let $\mathcal{P}$ be the matrix with one row for each pair $(s, g)$ of a slot of the pool and a point $g \in \{0,1\}^{v - c}$, equal to the committed row of slot $s$ on grid row $g$, its $W$ symbols, when $g < R_{i(s)}$ and to zero otherwise.

Lemma 3. On the line and the column checks, the verifier of the pool runs the verifier of one table on $\mathcal{P}$, with grid depth $\theta = v - c$ and fold weights $\bigl( \sum_k \lambda^k \kappa_{k,s} \bigr) \mathrm{eq}(r_{\mathrm{hi}}, g)$, and every row of $\mathcal{P}$ outside the commitment is zero in every column.

Proof. A zero row is a codeword and adds nothing to any column. Summing the opened symbols over the committed rows, as the column check does, therefore equals summing over every row of $\mathcal{P}$. For an honest prover the rows of $\mathcal{P}$ encode the messages of (3), the encoding of $q$ is the fold of $\mathcal{P}$ by the stated weights, and by Lemma 1 the line (4) is the line of that table at $r$ with the zero-extended masters $\tilde \mu_k$. ◻

Write $q^\circ \in \mathbb{F}^W$ for the fold of $\mathcal{P}$ itself, whose entry $j$ is the combination (3) of the committed symbols at column $j$; the column check compares the encoding of $q$ with $q^\circ$ at the drawn columns. Each row of $\mathcal{P}$ carries the weight $w_s\, \mathrm{eq}(r_{\mathrm{hi}}, g)$ with $w_s = \sum_k \lambda^k \kappa_{k,s}$.

Lemma 4 (proximity). If $\mathcal{P}$ is not $e$-close, then $q^\circ$ is $e$-close with probability at most $$\varepsilon_{\mathrm{prox}} = (\theta + \Sigma + m - 2)\, W / |\mathbb{F}| \qquad\text{(5)}$$ over $\eta$, $r_{\mathrm{hi}}$ and $\lambda$.

Proof. Fold in three stages: $\mathcal{P}' \in \mathbb{F}^{\Sigma \times W}$ with rows $\mathcal{P}'_s = \sum_g \mathrm{eq}(r_{\mathrm{hi}}, g)\, \mathcal{P}_{s,g}$, the tensor fold of the $2^\theta$ matrices $(\mathcal{P}_{s,g})_s$; then $c_k = \sum_s \kappa_{k,s} \mathcal{P}'_s$ for each master $k$; then $q^\circ = \sum_k \lambda^k c_k$. Let $E_1$ be the event that $\mathcal{P}'$ is $e$-close, $E_2$ that the matrix with rows $c_0, \ldots, c_{m-1}$ is, and $E_3$ that $q^\circ$ is. The three challenges are uniform and independent whatever the prover sends between them, and $\mathcal{P}$ precedes them all.

Since $\mathcal{P}$ is not $e$-close, the tensor bound for $C^\Sigma$ with $\vartheta = \theta$ gives $\Pr[E_1] \le \theta W/|\mathbb{F}|$. Fix $r_{\mathrm{hi}}$ outside $E_1$. If the $c_k$ agree with codewords $v_k$ outside $e$ common columns, then $\sum_k c_k$ agrees with the codeword $\sum_k v_k$ there: $E_2$ implies that $\sum_k c_k$ is $e$-close; and $\sum_k c_k = \sum_s (\sum_k \kappa_{k,s}) \mathcal{P}'_s = \sum_{\sigma < \Sigma} \eta^{\sigma} \mathcal{P}'_{s(\sigma)}$ is a curve of degree $\Sigma - 1$ in $\eta$ whose coefficient words are rows of $\mathcal{P}'$, every row occurring since every slot holds a unit. By the curve bound, $\Pr_\eta[E_2] \le (\Sigma - 1) W/|\mathbb{F}|$, as a larger probability would make $\mathcal{P}'$ $e$-close. Fix $\eta$ outside $E_2$. Then $q^\circ$ is a curve of degree $m - 1$ in $\lambda$ with coefficient words $c_k$, and the curve bound gives $\Pr_\lambda[E_3] \le (m - 1) W/|\mathbb{F}|$. The union bound over the three stages is (5). ◻

Lemma 5 (column test). Let the $t$ columns be drawn uniformly and independently. If $q^\circ$ is not $e$-close, every column check passes with probability at most $((1 + \rho)/2)^t$. If $\mathcal{P}$ is $e$-close with decoding $\mathcal{P}^*$ and $q$ differs from the fold $q^*$ of the messages of $\mathcal{P}^*$ by the weights of (3), every column check passes with probability at most $((1 + \rho)/2)^t$.

Proof. The check at column $j$ reads $\mathrm{Enc}(q)_j = q^\circ_j$. In the first case $\mathrm{Enc}(q)$ is a codeword, from which $q^\circ$ differs on more than $e$ columns, and one check passes with probability at most $1 - (e + 1)/W \le (1 + \rho)/2$. In the second case let $A$ be the set of at most $e$ columns on which $\mathcal{P}$ and $\mathcal{P}^*$ differ. Outside $A$ the symbols of $\mathcal{P}$ are those of $\mathcal{P}^*$, and the combination of codewords is the codeword of the combined messages, whence $q^\circ_j = \mathrm{Enc}(q^*)_j$ for $j \notin A$. The distinct codewords $\mathrm{Enc}(q)$ and $\mathrm{Enc}(q^*)$ agree on at most $S + L - 1$ columns, and a check passes only on $A$ or on those columns, $e + S + L - 1 \le (1 + \rho) W/2$ in all. The $t$ draws are independent. ◻

Theorem 6 (soundness). Let $\mathcal{P}$ be the committed matrix, let the prover be arbitrary after the roots, let $\bar p = \max_i \max(c - n_i, 0)$, and let $\nu = 7$ when some table carries ring units and $\nu = 0$ otherwise. In base mode the verifier accepts while one of the following holds with probability at most $$\varepsilon_{\mathrm{pool}} = \varepsilon_{\mathrm{prox}} + \Bigl( \frac{1 + \rho}{2} \Bigr)^t + \frac{(m - 1) + 2v + (2\Sigma - 1 + \bar p + \nu)}{|\mathbb{F}|} :$$ (a) $\mathcal{P}$ is not $e$-close; (b) $\mathcal{P}$ is $e$-close with decoding $\mathcal{P}^*$ and a claim of some table differs from the value it names on $\mathcal{P}^*$, that is, for a whole unit $c_u \ne \tilde f^*(a_i)$ or $c'_u \ne \tilde f^*_{+}(a_i)$ and for a ring unit $c_{u,v} \ne \tilde t^*_v(a_i)$ or $c'_{u,v} \ne \tilde t^*_{v,+}(a_i)$, where $f^*$ is the unit’s column in $\mathcal{P}^*$ and $t^*_v$ its $v$-th tower coordinate.

Proof. Six steps, each charged once.

1. Let $\mathcal{P}$ not be $e$-close. By Lemma 4, $q^\circ$ is $e$-close with probability at most $\varepsilon_{\mathrm{prox}}$, and otherwise Lemma 5 rejects except with probability $((1 + \rho)/2)^t$. Henceforth $\mathcal{P}$ is $e$-close with decoding $\mathcal{P}^*$; its rows outside the commitment are zero (Lemma 3), and its messages define the decoded slot polynomials $D^*_s$, masters $M^*_k = \sum_s \kappa_{k,s} D^*_s$, columns $f^*_u$ and coordinates $t^*_{u,v}$.

2. If $q \ne q^*$, Lemma 5 rejects except with probability $((1 + \rho)/2)^t$. The matrix $\mathcal{P}$ is fixed; steps 1 and 2 are exclusive, and the query term is charged once. Henceforth $q = q^*$.

3. Put $\tilde\mu^*_k = \mathrm{eq}(r_z, 0)\, M^*_k(r_x, r_b)$. The identity in the proof of Lemma 1 holds for every message matrix; with $q = q^*$ the left side of the line (4) is $\sum_k \lambda^k \tilde\mu^*_k$. The masters $\tilde\mu_k$ precede $\lambda$; if some $\tilde\mu_k \ne \tilde\mu^*_k$, the line holds only at a root of the nonzero polynomial $\sum_k \lambda^k (\tilde\mu_k - \tilde\mu^*_k)$ of degree below $m$, probability at most $(m - 1)/|\mathbb{F}|$. Henceforth $\tilde\mu_k = \tilde\mu^*_k$ for every $k$.

4. Let $F^*$ be (1) with the masters $M^*_k$. With $\tilde\mu_k = \tilde\mu^*_k$ the final check (2) reads $F^*(r)$, and the verifier holds every round polynomial to degree 2. If $\sum_i \tau_i \ne \sum_{y \in \{0,1\}^v} F^*(y)$, the sumcheck accepts with probability at most $2v/|\mathbb{F}|$ (Lund et al. 1992). Henceforth $\sum_i \tau_i = \sum_y F^*(y)$.

5. Summing $F^*$ over $\{0,1\}^v$ as in the proof of Theorem 2 gives $\sum_y F^*(y) = \sum_i \tau^*_i + X$. Here $\tau^*_i = \sum_{u \in i} \eta^{\sigma(u)} \mathrm{eq}(\rho_i, b(u))\, y^*_u$ with $y^*_u$ the value $y_u$ takes on the true claims of $f^*_u$, the identity of a ring unit holding for the coordinates $t^*_{u,v}$ of any column of $\mathcal{P}^*$; and $$X = \sum_{\sigma} \eta^{\sigma} \sum_{b \notin U_\sigma} \mathrm{eq}(\rho_{i(\sigma)}, b)\, \langle \omega_{k(\sigma)}, D^*_{s(\sigma)}(\cdot, b) \rangle,$$ $U_\sigma$ the blocks that hold a unit of role $\sigma$, collects what $\mathcal{P}^*$ carries in the blocks an honest prover leaves zero.

6. The claims precede $\eta$, the $\rho_i$ and $r''$. The difference $\sum_i (\tau_i - \tau^*_i) - X$ is a polynomial in these challenges. Sorted by the monomials $\eta^{\sigma}$ and $\eta^{\Sigma + \sigma}$ and then by the block, its terms are $\mathrm{eq}(\rho_i, b)\, \Delta^0_u$ and $\mathrm{eq}(\rho_i, b)\, \Delta^1_u$ at a block $b$ holding the unit $u$ of role $\sigma$, and $-\mathrm{eq}(\rho_i, b)$ times the $\eta$-free part and the $\eta^{\Sigma}$ part of $\langle \omega_{k(\sigma)}, D^*_{s(\sigma)}(\cdot, b) \rangle$ at a block without one, where for a whole unit $\Delta^0_u = c_u - \tilde f^*_u(a_i)$ and $\Delta^1_u = c'_u - \tilde f^*_{u,+}(a_i)$, and for a ring unit $\Delta^0_u = \sum_v \pi_v\, \phi_{r''}(c_{u,v} - \tilde t^*_{u,v}(a_i))$ and $\Delta^1_u$ likewise with the next-row claims. A block holds at most one unit of a role, the $\mathrm{eq}(\rho_i, b)$ for distinct $b$ are linearly independent, $\phi_{r''}(x) = \sum_w \mathrm{eq}(r'', w)\, \mathrm{bit}_w(x)$ is the zero polynomial in $r''$ only at $x = 0$, and the $\pi_v$ are a basis. Hence the difference is the zero polynomial only when every $\Delta$ vanishes, that is, when every claim is true, and otherwise it has degree at most $2\Sigma - 1$ in $\eta$, at most $\bar p$ in the $\rho_i$ and at most $\nu$ in $r''$, and vanishes at the drawn challenges with probability at most $(2\Sigma - 1 + \bar p + \nu)/|\mathbb{F}|$. ◻

Remark 7. In zero-knowledge mode the claims, the masters, the round values and the line are one-time-padded, and the checks of steps 3, 4 and 6 are rows of the outer statement; Theorem 6 then holds with the soundness error of the outer argument (Kochergin 2026) added, under the assumption of the introduction.

Corollary 8 (extraction). With $H$ a random oracle, the extractor that reads the leaves of both trees from the prover’s oracle queries and decodes every row of $\mathcal{P}$ to radius $e$, by Berlekamp-Welch on the evaluation points of the row code, outputs columns whose evaluations at $a_i$ and at the next row, and those of their tower coordinates, are the claims of every accepting transcript, except with probability $\varepsilon_{\mathrm{pool}}$ and the collision term of the trees.

On the workloads of Table 1 the terms of $\varepsilon_{\mathrm{pool}}$ without the factor $W$ sum to less than $2^{-118}$, and the query term is unchanged from a single table: one code, one width $W$, $t$ columns. The per-table ZeroCheck and LogUp terms do not change.

Both parties compute the shape from absorbed data in integer arithmetic and reject one whose query or proximity term falls below 100 bits; the verifier holds the LogUp term, 106 to 128 bits on the workloads below, to the same floor. Table 1 lists the shape of each workload of Section 8 in zero-knowledge mode. The proximity term is the smaller on every row, 102 to 108 bits; the query term is 109 to 118.

Table 1: Shape and security bits of the pool in zero-knowledge mode, as the verifier logs them, $t = 287$, $S = 288$. $U = \Sigma + m - 1$; the proximity column is $128 - \log_2 W - \lceil \log_2 (v - c + U - 1) \rceil$.

§ 6 The split

The split $c$ minimizes an integer estimate of the bytes that depend on it: $$\mathrm{cost}(c) = 17 \cdot 2^c + t \sum_i 2^{\max(n_i - c, 0)}\, \ell_i(P_i) + 32 K \sum_i (P_i - 1). \qquad\text{(6)}$$ The first term is the data part of $q$, priced at 17 bytes per element, a one-byte bincode varint tag and 16 bytes; its support part, $S$ elements from $c = 11$, is not priced. The second is the opened symbols: $\ell_i(P)$ is the byte count of table $i$’s symbols on one grid row of one column, both trees, at $P$ columns per slot. The third is the claims on blind columns: each of the $K P_i$ blind columns of table $i$ sends two masked claims of 16 bytes, and the term counts the $K (P_i - 1)$ blinds beyond those of an unpacked table. In base mode $K = 0$.

The search runs over $1 \le c \le \max_i (n_i + p_i)$, $p_i$ the packing depth of table $i$’s widest class, and admits $c$ when it leaves room for the support, $2^c \ge S$, and when the shape of Section 5 clears 100 bits. Ties go to the narrower split. The inputs are the absorbed heights, the program and the configuration; nothing in the proof sets $c$.

Not counted: the Merkle multiproof, at most $t$ hashes per tree per unit of $c$, and the eval sumcheck, $2v$ elements; the masters and the remaining claims do not depend on $c$. With both added, the minimizer moves on no workload of Table 1 in either mode, and under that count the next split costs at least 18.6 KiB more.

The third term matters for small tables: a table of $2^4$ rows in a pool at $c = 16$ packs $P = 2^{12}$, and its $4\,096$ blind columns send 128 KiB of claims and $8\,192$ masked scalars to the outer argument. Every table of Table 1 has at least $2^9$ rows, and the term stays below 4 KiB per table there.

§ 7 Leaves and the support

Unsalted leaves need one support cell more than the query count. In zero-knowledge mode the verifier sees the fold vector $q$, data and support parts, the masters, and the opened symbols of at most $t$ distinct columns. Every other column reaches it only through its Merkle leaf, a hash with no salt. If an unopened column is a function of the witness and the view, a guess of the witness can be tested against the root.

Lemma 9. Let $S = t$. For every message $(\xi, d)$ and every column $j$, the symbol at $j$ is an affine function of $d$ and the symbols at the $t$ opened columns.

Proof. The symbol at a point $\alpha$ is $\sum_{k < S} \xi_k X_k(\alpha) + \sum_{k < L} d_k X_{S+k}(\alpha)$. Since $\deg X_k = k$, the $X_k$ with $k < S$ span the polynomials of degree below $S$, and a nonzero one has fewer than $S$ roots. The $S \times t$ matrix $(X_k(\alpha_j))$ over the opened points is therefore invertible at $S = t$, and $\xi$ is an affine function of $d$ and the opened symbols. Substituting it gives the symbol at $j$. ◻

At $S = t$, then, a tree whose rows carry no uniform data cell has every unopened leaf fixed by the witness and the view. The $h$ tree is such a tree: it carries no blind. The trace tree of a pool with one table, without ring units, on one grid row is another: there $q$ fixes the data of the one blind slot as $q$’s data part minus the witness terms, and Lemma 9 fixes the rest.

Lemma 10. Let $S \ge t + 1$, and let at least two messages carry nonzero weight in $q$. Given the view and every data cell, the symbol of any message at any unopened column is uniform.

Proof. With the data fixed, the view is linear in the supports $\xi_r$. Put $x_j = (X_k(\alpha_j))_{k < S}$ and let $A$ be the span of $x_{j'}$ over the opened columns $j'$. Polynomials of degree below $S \ge t + 1$ interpolate any $t + 1$ values, whence $x_j \notin A$ for an unopened $j$. The view determines $\langle \xi_r, a \rangle$ for every $r$ and $a \in A$, and $\sum_r w_r \xi_r$, $w$ the weights of $q$. Were $\langle \xi_r, x_j \rangle$ determined as well, it would equal $\sum_{r'} \langle \xi_{r'}, a_{r'} \rangle + \langle \sum_{r'} w_{r'} \xi_{r'}, u \rangle$ identically, every $a_{r'} \in A$. A message $r' \ne r$ with $w_{r'} \ne 0$ forces $u \in A$, and then $x_j = a_r + w_r u \in A$, a contradiction. ◻

In the pool every table has a data slot and a blind slot, and each weight of (3) is a nonzero polynomial of degree below $\Sigma + m + \theta$ in the challenges: the hypothesis fails with probability at most $2(\Sigma + m + \theta)/|\mathbb{F}|$.

Theorem 14 assembles the lemmas into a simulator. Index the committed rows of both trees by $r$, $N \ge 2$ in all, each with a support $\xi_r$ uniform in $\mathbb{F}^S$ and data $d_r$, the data of a blind row uniform too. The verifier opens $t' \le t$ distinct columns $j_1, \ldots, j_{t'}$; with $x_j$ as in Lemma 10 and $y_j = (X_{S+k}(\alpha_j))_{k < L}$, the symbol of row $r$ at column $j$ is $\langle \xi_r, x_j \rangle + \langle d_r, y_j \rangle$, $o_{r,l}$ denotes it at $j_l$, and $w_r$ is the weight of row $r$ in (3).

Lemma 11 (openings). For $t' \le S$ the opened symbols of a row are uniform in $\mathbb{F}^{t'}$ and independent of its data, and the rows are independent.

Proof. The $x_{j_1}, \ldots, x_{j_{t'}}$ are linearly independent, as in the proof of Lemma 10, and $\xi \mapsto (\langle \xi, x_{j_l} \rangle)_l$ is onto $\mathbb{F}^{t'}$: a uniform $\xi_r$ makes the opened symbols uniform whatever $d_r$. ◻

Lemma 12 (the fold). Let $S \ge t' + 1$, let $\bar x \in \mathbb{F}^S$ complete $x_{j_1}, \ldots, x_{j_{t'}}$ to a basis, and let $\eta \lambda \ne 0$. Given the opened symbols of every row, the data part $d_q$ of $q$ is uniform in $\mathbb{F}^L$, the coordinate $\langle \xi_q, \bar x \rangle$ of its support part is uniform in $\mathbb{F}$, the two are independent of each other and of the openings, and the remaining coordinates $\langle \xi_q, x_{j_l} \rangle = \sum_r w_r o_{r,l} - \langle d_q, y_{j_l} \rangle$ are determined by the openings and $d_q$.