Skip to content

Variable Encoding: Per-Entry Range Coding #168

@psivesely

Description

@psivesely

Summary

The major proof components including CIC leaf data, lifted evaluations (part of the new tensor-lifted Zip+ being integrated into the paper soon), and the CIC combined witness consists of integers whose ranges are determined by publicly known parameters. The range of any individual entry can be computed from the constraint system, the IPRS generator matrix, and the protocol challenges, yielding per-entry bounds tighter than the global worst-case bound $B$ used in the CIC soundness analysis.

Using fixed-width encoding is one of the reasons that generic .rar compression gives significant proof size reduction (zip: Reducing Proof Sizes for Hash-Based SNARGs notes some additional reasons including possibly unpruned Merkle paths). For uniform witnesses (where most entries are close to their bounds) per-entry serialization should be optimal, but this approach is witness-independent. When witness entries are substantially smaller than even the per-entry bounds, generic compression is still helpful. I believe per-entry serialization followed by generic compression could provide the smallest proof size across witness distributions, but how much of a difference it would make over just using .rar remains to be seen.

The leaf data stands to benefit the most from this because of both it's variation from the worst-case bound and total size, so I wrote out how that out in detail below and just sketch how we could use it in the other two areas mentioned above.

Per-entry range coding for leaf data

The IPRS codeword entry for oracle $j$, coefficient layer $i \in [d]$, at row $b_L \in {0,1}^{\mu_2}$ and column $p \in [n]$ is

$$v_j^{(i)}[b_L, p] = \sum_{b_R \in {0,1}^{\mu_1}} w_j^{(i)}(b_L, b_R) \cdot M[b_R, p].$$

For a given witness element type, the range of coefficients is typically a fixed integral subset (e.g., ${0, \ldots, 2^{B_0} - 1}$ for $B_0$-bit unsigned values). This range is invariant across coefficient layers $i$ within its support, but when the witness polynomial has degree strictly less than $d$, coefficient layers beyond the degree are identically zero and do not contribute.

Since both the witness coefficient ranges and the generator matrix entries $M[b_R, p]$ are publicly known, the verifier can compute tight per-entry bounds

$$\check{\beta}^{(i)}_{b_L, p} = \sum_{b_R} \min\bigl(\min S^{(i)}(b_L, b_R) \cdot M[b_R, p],\ \max S^{(i)}(b_L, b_R) \cdot M[b_R, p]\bigr),$$

$$\hat{\beta}^{(i)}_{b_L, p} = \sum_{b_R} \max\bigl(\min S^{(i)}(b_L, b_R) \cdot M[b_R, p],\ \max S^{(i)}(b_L, b_R) \cdot M[b_R, p]\bigr),$$

where $S^{(i)}(b_L, b_R) \subseteq \mathbb{Z}$ is the publicly known range of $w_j^{(i)}(b_L, b_R)$. The $\min/\max$ over the product accounts for sign changes in $M[b_R, p]$: when $M[b_R, p] < 0$, the extremes of $S$ contribute in reverse order. The codeword entry satisfies

$$v_j^{(i)}[b_L, p] \in \lbrace\check{\beta}^{(i)}_{b_L, p}, \ldots, \hat{\beta}^{(i)}_{b_L, p}\rbrace,$$

and each entry is encoded in

$$\lceil \log(\hat{\beta}^{(i)}_{b_L,p} - \check{\beta}^{(i)}_{b_L,p} + 1) \rceil \text{ bits.}$$

bits.

Lifted evaluation and combined witness encoding

Analogous per-entry bounds can be derived for the batched lifted evaluation $\hat{\alpha}^{(g)}$ and the CIC combined witness $\mathbf{w}^\star$. Each coefficient of $\hat{\alpha}^{(g)}$ is a sum of products of lifted eq-factors and witness entries, where the number of contributing terms varies across coefficient positions (fewer near the edges of the degree range, more near the center). The combined witness entries $\mathbf{w}^{\star}[b_R]$ are defined by

$$\mathbf{w}^{\star}[b_R] = \sum_{j,i} \zeta_{j,i} \mathbf{w}_j^{(i)}(b_R)$$

and are often dominated by the $\lambda$-bit challenges $\zeta_{j,i}$, so per-position witness bounds provide only a marginal improvement over fixed-width encoding at the global bound $\lambda + \lceil\log(dJ)\rceil + B_0$.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions