Secure Challenge Derivation in ZisK

Thanks to Alexandre Belling for pointing me in the right direction in the Lattice world.

Many relational arguments employed in ZisK, such as the permutation argument in PlonK or the lookup argument in LogUp, require the Prover $\mathcal{P}$ to commit to a set of polynomials and subsequently demonstrate that these commitments satisfy a system of algebraic constraints at a specific evaluation point, the challenge. In the interactive setting, the challenge is sampled uniformly at random and issued by the verifier $\mathcal{V}$. In the non-interactive setting, the standard Fiat–Shamir heuristic is applied: the challenge is derived by hashing the committed polynomials along with additional transcript data required for the soundness of the protocol.

The derivation of challenges becomes substantially more delicate in a distributed setting, where the proof of an argument is jointly generated by multiple provers $\mathcal{P}_i$. Specifically, in ZisK, relational arguments are reduced to univariate sumcheck protocols whose evaluation polynomials must be consistently instantiated across all provers. Hence, all provers must operate with an identical challenge value: if provers were to proceed with different evaluation points, the resulting constraints would be incoherent and verification would fail trivially. This necessitates a mechanism to derive a single canonical challenge from the joint set of commitments, and to make it consistently available to all provers before the protocol can proceed.

Being slightly more technical, let $\{\mathcal{P}i\}_{i=1}^J$ denote the participating provers. The process unfolds as follows:

1. Each prover $\mathcal{P}_i$ computes a commitment $c_i \in D$ to its local set of polynomials, where $D$ denotes the commitment domain.
2. An accumulator party $A$ (assumed honest, see below) iteratively combines the commitments via an accumulator function $\text{acc}: D^k \to D$ which compresses blocks of $k$ commitments into a single value, until all $J$ commitments have been processed.
3. The resulting accumulator value defines the common challenge $\alpha$, which is broadcast to all provers.

For clarity, we omit through all this post transcript elements such as public parameters $\text{pp}$ and auxiliary data, which in practice must also be included to guarantee protocol soundness.

The accumulator $\text{acc}$ is required to satisfy:

• Efficiency: $\text{acc}$ should be computable in (poly)time, with cost proportional to $k$.
• Incrementality: Accumulation should support streaming, i.e., intermediate accumulations should depend only on commitments observed so far, without recomputing from scratch.
• Security: The derived challenge $\alpha$ should be computationally indistinguishable from a uniformly random challenge under the standard model assumptions, i.e., it should inherit the pseudorandomness guarantees of Fiat–Shamir.

In ZisK, the accumulator is itself embedded inside proof aggregation. Thus, the aggregation constraints guarantee that $\text{acc}$ is applied correctly, allowing us to assume honesty of $A$.

We now turn to the cryptographic primitive that enables efficient, incremental, and secure accumulation: multiset hashing.

Multiset Hashing

Multiset hashing, introduced by Clarke et al. [Cla03] and rooted in the incremental hashing paradigm of Bellare and Micciancio [BM96], provides exactly the required functionality: it supports incremental computation of a hash value over dynamically growing multisets. They are incremental in the sense that, when new members of the multiset are known, the hash can be updated in time proportional to the new members. Multiset hashes must satisfy a stronger notion of security than those for standard hashes: multiset collision-resistance; which says that it must be hard to find two different multisets that produce the same hash.

Formally, a multiset hash function is a map $H \colon \mathcal{M}(\{0,1\}^*) \to \mathbb{G}$ where $\mathcal{M}(\cdot)$ denotes multisets and $(\mathbb{G},\oplus)$ is a commutative group, satisfying:

• Multiset Homomorphism: Given two multisets $S, T \in \mathcal{M}(\{0,1\}^*)$, we have that $H(S \cup T) = H(S) \oplus H(T).$
• Multiset Collision-Resistance: It is computationally infeasible to find multisets $S, T \in \mathcal{M}(\{0,1\}^*)$ such that $S \neq T$ and still $H(S) = H(T)$.

Bellare and Micciancio introduced for sets (and later generalized for multisets by Clarke et. al.) the idea of taking a collision-resistance hash-to-group function $h \colon \{0,1\}^* \to \mathbb{G}$ and definining the multiset hash function $H$ over, e.g., an additive group $(\mathbb{G}, +)$ as:

$$H(S) = m_{s_1}h(s_1) + \dots + m_{s_J}h(s_{J}),$$

for multiset $S = \{s_1^{(m_{s_1})}, \dots, s_{J}^{(m_{s_J})}\}$, where $x^{(m_x)}$ denotes that string $x$ appears $m_x$ times in $S$; i.e., $m_x$ is the multiplicity of $x$.

Notice that multiset homomorphism follows directly from the definition.

Clarke et. al. showed that if $(\mathbb{G}, +)$ is taken to be addition over $\mathbb{Z}_p$ then one could prove multiset collision-resistance for a sufficiently large $p$. The problem is that this constructions requires a to append a secret key to the construction that does not fit within our scenario. Moreover, Clarke et. al. only considered Wagner attack [Wag02] on their security analysis, but refinements of the attack has appeared since then, e.g. [Sha08], that worsens its efficiency.

They also propose to take $(\mathbb{G}, +)$ to be addition over $\mathbb{Z}_p^n$, the space of vectors of dimension $n$ with coefficients over $\mathbb{Z}_p$. In this setting, they show multiset collision-resistance by reducing to the SIS problem, a well-studied lattice-based problem. This latter construction, broadly named as $\text{LtHash}$, although less optimal than the previous one, does not require any secret key, so we’ll be focusing on it from now on.

Lattice-Based Multiset Hashing (LtHash)

Fix a positive integer $n$. Following Clarke et al., we instantiate $(\mathbb{G},+)$ as the additive group $\mathbb{Z}_p^n$. Define a base hash $h:\{0,1\}^*\to \mathbb{Z}_p^n$ (obtained, e.g., via iterative squeezing of a standard cryptographic hash). We define $\text{LtHash} \colon \mathcal{M}(\{0,1\}^*) \to \mathbb{Z}_p^n$ by:

$$\text{LtHash}(S) = \sum_{i=1}^{J} m_{s_i} \cdot h(s_i),$$

where $S = \{s_1^{(m_{s_1})}, \dots, s_{J}^{(m_{s_J})}\}$, the summation is taken by component-wise addition over $\mathbb{Z}_p$ and multiplication is the standard scalar multiplication over $\mathbb{Z}_p^n$.

Again, multiset homomorphism follows directly from the construction. Let us now turn to multiset collision-resistance.

Multiset Collision-Resistance

First, observe that if multiplicities are left unbounded over $\mathbb{Z}_p$, then $\text{LtHash}$ is not collision-resistant. Indeed, given a multiset $S$, take any string $y \notin S$ and form $T = S \cup \{y^{(p)}\}$. We have $T \neq S$ but $\text{LtHash}(T) = \text{LtHash}(S)$. To avoid such trivial collisions, we restrict our attention to $\mathcal{M}^{\leq B}(\{0,1\}^*)$, the family of multisets of cardinality at most $B \ll p$. This is an stronger assumption than requiring that every element in a multiset has multiplicity much lower than $p$, but it turns out to be sufficient for the ZisK scenario (more in the next section).

Collision-resistance of $\text{LtHash}$ can be related to the hardness of the Short Integer Solution (SIS) problem, a well-studied lattice problem believed to remain hard even against quantum adversaries.. For sets, an updated reduction is given in Theorem 2.3 of [2019/227], adapting Theorem 6.1 of [BM96] to modern models. Adapting this proof to the multiset setting as proven in Theorem 3 of [Cla03] follows directly.

At a high-level the relation goes as follows. For two multisets $S = \{s_1^{(m_{s_1})}, \dots, s_{J}^{(m_{s_J})}\}$, $T = \{t_1^{(m_{t_1})}, \dots, t_{K}^{(m_{t_K})}\}$ from $\mathcal{M}^{\leq B}(\{0,1\}^*)$ with $J,K > 0$, define the union set $U = \text{supp}(S) \cup \text{supp}(T) = \{u_1, \dots, u_L\}$. Clearly, $L > 0$. Now, define

$$A = \begin{bmatrix} h(u_1) \mid & \cdots & \mid h(u_L) \end{bmatrix} \in \mathbb{Z}_p^{n \times L}$$

and let $x \in \mathbb{Z}_p^{L}$ be such that $x_i = m_{u_i}^S - m_{u_i}^T$, where $m_{u}^X$ denotes the multiplicity of $u$ in the multiset $X$. Then, finding a multiset collision amounts to producing two multisets $S,T$ such that:

$$\sum_{i=1}^{J} m_{s_i} \cdot h(s_i) - \sum_{i=1}^{K} m_{t_i} \cdot h(t_i) = \overline{0} \iff Ax = \overline{0}.$$

Thus, since we assumed that both $S,T$ have sufficiently bounded cardinality and $h$ is a secure hash function, we obtain a (non-trivial) solution $m$ to the SIS instance with infinity norm bounded by $B$. Consequently, under the SIS hardness assumption, it should be infeasible to find collisions for $\text{LtHash}$.

Enforcing Bounded Cardinality

As explained before, we must ensure that the size of any multiset remains bounded. A simple and effective technique is to augment each vector embedding with an additional coordinate fixed to 1. This way, every accumulation inherently tracks the total multiplicity of its elements, providing a built-in mechanism to enforce cardinality limits.

Formally, define the augmented embedding $h'(x) = (h(x), 1) \in \mathbb{Z}_p^{n+1}$. Then, the $\text{LtHash}$ of a multiset $S = \{s_1^{(m_{s_1})}, \dots, s_{J}^{(m_{s_J})}\}$ is given by:

$$\text{LtHash}(S) = \sum_{i=1}^{J} m_{s_i} \cdot h'(s_i) = \left(\sum_{i=1}^{J} m_{s_i} \cdot h(s_i), \sum_{i=1}^{J} m_{s_i} \right).$$

The final coordinate now records the total multiplicity of the multiset. By requiring, within proof aggregation, that this coordinate stays strictly below a fixed bound $B$ (e.g., $2^{20}$), we guarantee that no multiset can exceed $B$ elements. This prevents adversaries from constructing long addition chains or otherwise bypassing the bounded-size assumption.

Concrete Parameters and Security

We use the tool Lattice Estimator to estimate the security of $\text{LtHash}$ against the best known attacks for the SIS problem.

By plugging in $n = 372$, $p = 2^{64} - 2^{32} + 1$ and $B = 2^{20}$:

from estimator import *

vector_size = 372
goldilocks = 2**64 - 2**32 + 1
bound = 2**20

params = SIS.Parameters(n=vector_size, q=goldilocks, length_bound=bound, norm=oo)
SIS.estimate(params)

we obtain:

lattice  :: rop: ≈2^134.3, red: ≈2^133.3, sieve: ≈2^133.3, β: 363, η: 373, ζ: 317, d: 1951, prob: 1, ↻: 1, tag: infinity

which is sufficient for our $128$-bit security objective

Application to Distributed Challenge Derivation in ZisK

We are now ready to describe how distributed challenge derivation is instantiated in ZisK. Let $n, m$ be positive integers, let $p = 2^{64} - 2^{32} + 1$ denote the Goldilocks prime, and let $h$ be the Poseidon2 hash function. ZisK builds on STARKs as its underlying proving system, where polynomial commitments are represented as the Merkle root of a tree containing all polynomial evaluations over a predefined domain over $\mathbb{Z}_p$. Since Poseidon2 is used in the commitment phase, we set each commitment $c_i$ to lie in the domain $D = \mathbb{Z}_p^4$.

For security, the challenge space must be chosen so that its size exceeds the target security parameter. As ZisK targets 128-bit security, we fix $\mathbb{Z}_p^3$ as the challenge space. Finally, we’ll be using the trick described in Section “Enforcing Bounded Cardinality” to bound the number of accumulations by $B$.

The distributed challenge $\alpha$ is computed collaboratively by provers $\{\mathcal{P}_i\}_{i=1}^{J}$ as follows:

1. Commit Phase. Each prover $\mathcal{P}_i$ computes its polynomial commitment $c_i \in \mathbb{Z}_p^4$ and sends it to the designated accumulator party $A$.

2. Initialization and First Accumulation. The accumulator is initialized at $\text{acc}_0 = 0$. Upon receiving the first batch of $k$ commitments $C = \{c_1, \dots, c_k\}$, the accumulator constructs the multiset $S = \{s_1^{(m_{s_1})}, \dots, s_{\ell}^{(m_{s_{\ell}})}\}$ from $C$. For each $s_i \in S$, the accumulator derives a vector embedding by iteratively hashing:

   $$h_{i,1} = h(s_i), \quad h_{i,2} = h(h_{i,1}), \ \dots,\ h_{i,n/4} = h(h_{i,n/4-1}),$$

   where each $h_{i,j} \in \mathbb{Z}_p^4$ and concatenating all intermediate values, yielding

   $$v_i = (h_{i,1}, \dots, h_{i,n/4}, 1) \in \mathbb{Z}_p^{n+1}.$$

   The accumulator then applies $\text{LtHash}$:

   $$\text{acc}_1 = \text{acc}_0 + \text{acc}(c_1, \dots, c_k) = \text{LtHash}(S) = \sum_{i=1}^{\ell} m_{s_i} \cdot v_i$$

3. Subsequent Accumulations. As additional batches of $k$ commitments are received, the accumulator repeats the above process, updating

   $$\text{acc}_i = \text{acc}_{i-1} + \text{acc}(\cdot).$$

4. Finalization. After processing all $J$ commitments (i.e., after $J/k$ accumulation rounds), the accumulator outputs the final value

   $$\text{acc} := \text{acc}_{J/k},$$

   which is broadcast to all provers ${\mathcal{P}_i}$. Each prover continues the protocol using the embedding of $\text{acc}$ into $\mathbb{Z}_p^3$ as the common challenge $\alpha$.

Efficiency, incrementality, and security follow directly from the properties of $\text{LtHash}$. Accumulation is fully parallelizable and can be performed in arbitrary order. Also, notice that input lengths can vary: $k' \neq k$ is permissible, which leads that multiple accumulators can be composed hierarchically. For example, two accumulators $A_1, A_2$ may independently process disjoint subsets $C_1, C_2$ of the commitments $C = \{c_1, \dots, c_{j}\}$, after which a final aggregation step combines their outputs.

Resources

• Bellare, Micciancio. A New Paradigm for Collision-Free Hashing: Incrementality at Reduced Cost. [BM96].
• David Wagner. A Generalized Birthday Problem. [Wag02]
• Clarke et al. Incremental Multiset Hash Functions and Their Application to Memory Integrity Checking. [Cla03].
• Andrew Shallue. An Improved Multiset Algorithm for the Dense Subset Sum Problem. [Sha08].
• Kevin Lewi et al. Securing Update Propagation with Homomorphic Hashing. [2019/227].