On Constraint Satisfiability

Setup

Let $\mathbb{F}$ be a finite field of prime order $p$ such that $2^k \vert (p-1)$ for some integer $k \geq 1$. Set $N = 2^k$, and let $G = \langle g \rangle \subseteq \mathbb{F}^*$ be a multiplicative subgroup of order $N$. Every subgroup of $G$ is generated by some power of $g$, so we can completely describe the subgroup structure as:

$$\{ 1 \} \subset \langle g^{2^{k-1}} \rangle \subset \langle g^{2^{k-2}} \rangle \subset \ldots \subset \langle g^{2} \rangle \subset G,$$

where each subgroup has order $2^i$, for $i=0,1,\ldots,k$.

The vanishing polynomial over a set $S \subseteq \mathbb{F}$, denoted $V_S$, is the polynomial whose roots are precisely the elements of $X$. For example, it is easy to see that $V_{\mathbb{F}^*}(X) = X^{p-1} - 1$ and more generally that $V_G(X) = X^N - 1$ for any cyclic group $G$ or order $N$.

We say that a polynomial $p$ of degree $n$ is sparse if it can be evaluated at any point of $\mathbb{F}$ in $O(\log{n})$ operations. Vanishing polynomials over any cyclic group are sparse, as well as the vanishing polynomials over sets of size $O(\log{n})$.

Subdomain Constraints

We consider the problem of proving algebraic constraints over a fixed, known evaluation domain. Concretely, given a finite multiplicative group $G \subset \mathbb{F}^*$ of order $N$, we aim to prove the validity of constraints over the entire domain $G$, as well as over specific deterministic (non-random) subsets $H \subset G$.

A constraint $C$ is a multivariate polynomial $C \in \mathbb{F}[X_1, \dots, X_s]$, where each variable $X_i$ represents a polynomial over $\mathbb{F}$ of degree strictly less than $N$, evaluated over the domain $G$. We write $\deg(C)$ to denote the degree of $C$ after substituting each $X_i$ with the corresponding polynomial.

From now on, we assume that constraints are non-trivial over $G$, i.e. that $\deg(C) > N$.

This framework is motivated by the need to efficiently express and enforce common classes of constraints arising in algebraic trace systems, namely trace boundaries, periodic constraints, and row selectors. More precisely:

• Trace Boundaries. Constraints that are enforced only at specific boundary points of the trace, typically the first and/or last row.
• Periodic Constraints. Constraints that hold over a periodic subset of the trace, corresponding to a repeating structural pattern.
• Row Selectors. Constraints that are enforced at a predetermined set of rows within the trace, not necessarily contiguous or periodic.

Subdomain Constraints in STARKs

In STARKs, proving that a constraint is satisfied over $G$ (i.e., evaluates to zero over $G$) is usually done by reducing the problem of constraint satisfiability to a low-degree test as follows. Given a set of constraints $\{C_1, \dots, C_t\}$, we compute the following rational function using a verifier-supplied random field element $\beta$:

$$C(X_1, \dots, X_s) := \frac{1}{V_G(X)}\left( \sum_{i=1}^{t} \beta^{i-1} \cdot C_i(X_1, \dots, X_s)\right).$$

In the honest setting, $V_G$ divides each $C_i$ as polynomials, so $C$ is a polynomial of degree $d = \max\{\deg(C_1) - N, \dots, \deg(C_t) - N\}$. The problem reduces to proving that $C$ is a polynomial of degree at most $d$.

Now, what happens when we aim to prove a constraint $C$ that is satisfied over a subset $H$ of $G$? A common approach is:

1. Define an auxiliar polynomial $f$ that “encodes” $H$, that is $f(x) = 1$ if $x \in H$ and $f(x) = 0$ if $x \in G \backslash H$.
2. Define $\hat{C} := f \cdot C$, transforming the original constraint to one satisfied over $G$.
3. Prove the satisfiability of $\hat{C}$ over $G$ instead of the one of $C$ over $H$.

This process is correct but it incurs in an additional transformation from the natural context of the constraint to a generic one.

The alternative would to define the rational fraction as:

$$C(X_1, \dots, X_s) := \sum_{i=1}^{t} \beta^{i-1} \cdot \frac{C_i(X_1, \dots, X_s)}{V_{H_i}(X)},$$

where each $H_i \subseteq G$ is the satisfaction domain of $C_i$. This avoids auxiliary polynomials, but the verifier must evaluate the vanishing polynomials $V_{H_i}$ at some random points. Sparse vanishing polynomials are therefore required for efficient verification.

The optimal strategy is a combination of both approaches, finding subsets $H \subseteq G$ that admit sparse vanishing polynomials.

Finding Good Domains

We know show how trace boundaries, periodic constraints and row selectors can be described by a sparse vanishing polynomial, making them amenable to the strategy described in the previous section. We assume that rows are labelled by the exponent of the generating set $G = \langle g \rangle = \{g, g^2, \dots, g^N\}$.

Trace Boundaries

A trace boundary constraint is satisfied at one of:

1. The first row.
2. The last row.
3. All rows except the first.
4. All rows except the last.

The first two vanishing polynomials are as easy as $V_1(X) = X - g$ and $V_N(X) = X - g^{N}$, where we used the shorthand $V_i$ for $V_{\{g^i\}}$. The complements are the standard Lagrange polynomials:

$$V_{G\backslash g}(X) = \frac{g}{N} \cdot \frac{X^N - 1}{X - g}, \ \ \ \ V_{G\backslash g^N}(X) = \frac{g^N}{N} \cdot \frac{X^N - 1}{X - g^N},$$

i.e., $V_{G \backslash g^i}$ is the $i$-th Lagrange polynomial.

All of these are sparse.

Periodic Constraints

If we take $H$ to be a subgroup of $G$ or order $\ell$, then we have $V_H(X) = X^{\ell} - 1$. More generally, for a coset $\hat{H} = g^r\langle g^{N / \ell}\rangle$ with $g^r \in G \backslash H$, we have $V_{\hat{H}}(X) = X^{\ell} - g^{r \ell}$. These cases correspond to index sets of the form

$$I = \{r + k\cdot (N/\ell) \mid k = 0,\dots,\ell-1\}, \text{ with } r \in \{0,\dots,N-1\} \text{ and } \ell \vert N,$$

that is, arithmetic progressions modulo $N$ whose period $\ell$ divides $N$.

More generally, a union of $t$ cosets $\widehat{H} = \cup_{i=1}^t g^{r_i}H_i$, where each $H_i$ is a subgroup of order $\ell_i$ has vanishing polynomial $V_{\widehat{H}}(X) = \prod_{i=1}^t(X^{\ell_i} - g^{r_i\ell})$. As long as $O(\log{N})$, this polynomial is sparse. The corresponding index set is:

$$I = \bigcup_{i=1}^t\{r_i + k\cdot (N/\ell_i) \mid k = 0,\dots,\ell_i-1\}, \text{ with } r_i \in \{0,\dots,N-1\} \text{ and } \ell_i \vert N,$$

Row Selectors

Row selectors correspond to arbitrary predetermined subsets of the trace. Let $S \subseteq \{0, \dots, N-1\}$ denote the selected rows. The vanishing polynomial is $V_S(X) = \prod_{i \in S}(X - g^i)$.

• Sparse evaluation is possible if $S$ can be decomposed as a union of $O(\log{N})$ cosets of power-of-two subgroups, as discussed above.
• Otherwise, $V_S$ is dense and evaluating it requires $O(|S|)$ operations, which is inefficient for large $S$.

Thus, by carefully choosing subset $S$ aligned with subgroup structure, we can maintain evaluation efficiency for general row selectors, periodic constraints, and trace boundaries.