1. Notation

​ We denote by $\mathbb{F}$ to a finite field of prime order $p$ and ${\mathbb{F}}^{\times }$ to its respective multiplicative group and define $k$ to be the biggest non-negative integer such that $2^k|(p-1)$. We also write $\mathbb{K}$ to denote a finite field extension of $\mathbb{F}$, of size $p^e$ , $e\ge 2$. Furthermore, we write $\mathbb{F}[X]$ (resp. $\mathbb{K}[X]$) for the ring of polynomials with coefficients over $\mathbb{F}$ (resp. $\mathbb{K}$) and write ${\mathbb{F}}_{<d}[X]$ (resp. ${\mathbb{F}}_{<d}[X]$) to denote the set of polynomials of degree lower than $d$.

2.Multiset Equality

The details and examples can be found in Permutation argument.

Grand Product

​ let $\mathrm{G}=⟨g⟩$ is a cyclic subgroup of ${\mathbb{F}}^{\times }$ of order n.

​ Given two vectors $f=(f_1,\cdots ,f_n)$ and $t=(t_1,\cdots ,t_n)$ in ${\mathbb{F}}^n$, a multiset equality argument, denoted $f\doteq t$, is used for checking that $f$ is equal to $t$ as multisets (or equivalently, that $f$ and $t$ are a permutation of each other). The protocol that instantiates the multiset equality arguments works by computing the following grand product polynomial $Z\in {\mathbb{K}}_{<n}[X]$: $$Z(g^i)=\{\begin{array}{l}1,\text{if}i=1\\ {\prod }_{j=1}^{i-1}\frac{f_j+\gamma }{t_j+\gamma },\text{if}i=2,\cdots ,n\end{array}\text{\hspace{1em}(1)}$$ where $\gamma \in \mathbb{K}$ is the value sent from the verifier.

Soundness of Multiset Equality

Lemma 1: Fix two vectors $f=(f_1,\cdots ,f+n)$ and $t=(t_1,\cdots ,t_n)$ in ${\mathbb{F}}^n$. If the following holds with probability larger than ${\epsilon }_{MulEq}(n):=n/|\mathbb{K}|$ over a random $\gamma \in \mathbb{K}$: $$\prod _{j=1}^n(f_i+\gamma )=\prod _{i=1}^n(t_i+\gamma )\text{\hspace{1em}(2)}$$ Then $f\doteq t$. As a consequence of Lemma 1, the identities that must be checked by the verifier for $x\in \mathrm{G}$ are the following:

$$\begin{array}{rl}& L_1(x)\cdot (Z(x)-1)=0\\ & Z(x\cdot g)\cdot (t(x)+\gamma )=Z(x)\cdot (f(x)+\gamma )\end{array}\text{\hspace{1em}(3)}$$ where $f,t\in {\mathbb{F}}_{<n}[X]$ are the polynomials resulting from the interpolation of $\{f_i{\}}_{i\in [n]}$ and$\{t_i{\}}_{i\in [n]}$ over $\mathrm{G}$,respectively.

​ The commitment polynomial is the grand product polynomial $Z\in {\mathbb{K}}_{<n}[X]$. and the two constraints is express in Eq $(3)$.

3.Connection

​ The protocol for a connection argument and the definitions and results we provide next are adapted from GWC19. The details and examples can be found in Connection argument.

​ Given some vectors $f_1,\cdots ,f_k\in {\mathbb{F}}^n$ and a partition $\mathcal{T}=\{T_1,\cdots ,T_s\}$ of the set $[kn]$, a connection argument, denoted $(f_1,\cdots ,f_k)\propto \{T_1,\cdots ,T_s\}$, is used to check that the partition $\mathcal{T}$ divides the field elements $\{f_{i,j}{\}}_{i\in [k],j\in [n}]$ into sets with the same value. More specifically, if we define the sequence $f_{(1)},\cdots ,f_{(kn)}\in \mathbb{F}$ by:

$$f_{((i-1)n+j)}:=f_{i,j}\text{\hspace{1em}(4)}$$ for each $i\in [k],j\in [n]$, then we have $f_{(l1)}=f_{(l2)}$ if and only if $l_1,l_2$ belong to the same block of $\mathcal{T}$.

​ In order to express the partition $\mathcal{T}$ within a grand product polynomial, we define a permutation $\sigma :[kn]\to [kn]$ as follows: $\sigma$ is such that for each block ${\mathcal{T}}_i$ of $\mathcal{T}$, σ(T ) contains a cycle going over all elements of ${\mathcal{T}}_i$ . Then, the protocol that instantiates the connection arguments works by computing the following grand product polynomial $Z\in {\mathbb{K}}_{<n}[X]$:

$$Z(g^i)=\{\begin{array}{l}1,\text{if}i=1\\ {\prod }_{l=1}^k{\prod }_{j=1}^{i-1}\frac{f_{l,j}+\gamma \cdot ((l-1)\cdot n+j)+\delta }{f_{l,j}+\gamma \cdot \sigma ((l-1)\cdot n+j)+\delta )},\text{if}i=2,\cdots ,n\end{array}\text{\hspace{1em}(5)}$$ where $\gamma ,\delta \in \mathbb{K}$ are the values sent from the verifier.

​ The definition of the previous polynomial is based on the following lemma, a proof of which can be found in Claim A.1. of GWC19.

Lemma 2 Fix $f_1,\cdots ,f_k\in {\mathbb{F}}^n$ and a partition $\mathcal{T}=\{T_1,\cdots ,T_s\}$ of the set $[kn]$. If the following holds with probability larger than ${\epsilon }_{Con}(n):=kn/|\mathbb{K}|$ over a randoms $\gamma ,\delta \in \mathbb{K}$: $$\prod _{l=1}^k\prod _{j=1}^n(f_{l,j}+\gamma \cdot ((l-1)\cdot n+j)+\delta )=\prod _{l=1}^k\prod _{j=1}^n(f_{l,j}+\gamma \cdot \sigma ((l-1)\cdot n+j)+\delta )\text{\hspace{1em}(6)}$$ ​ As a consequence of Lemma 2, the identities that must be checked by the verifier for $x\in \mathrm{G}$ are the following: $$\begin{array}{rl}& L_1(x)\cdot (Z(x)-1)=0,\\ & Z(x\cdot g)\cdot \prod _{l=1}^k(f_l(x)+\gamma \cdot S_{{\sigma }_l}(x)+\delta )=Z(x)\cdot \prod _{l=1}^k(f_l(x)+\gamma \cdot S_{I{D}_l}(x)+\delta ),\end{array}\text{\hspace{1em}(7)}$$ where $S_{I{D}_i}(g^j)=(i-1)\cdot n+j$ is the polynomial mapping G-elements to indexes in [kn] and $S_{{\sigma }_i}(g^j)=\sigma ((i-1)\cdot n+j)$ is the polynomial defined by $\sigma$​. For more details see GWC19.

​ The commitment polynomial is the grand product polynomial $Z\in {\mathbb{K}}_{<n}[X]$. and the two constraints is express in Eq $(7)$.

4.inclusion

​ The protocol for an inclusion argument and the definitions and results we provide next is adapted from the well-known Plookup protocol GW20, with the “alternating method” provided in [PFM+22](https://eprint.iacr.org/ 2022/086). The details and examples can be found in Inclusion argument.

​ Given two vectors $\mathrm{f}=(f_1,\cdots ,f_n)$ and $\mathrm{t}=(t_1,\cdots ,t_n)$ in ${\mathbb{F}}^n$ , a inclusion argument, denoted $\mathrm{f}\in \mathrm{t}$, is used for checking that the set A formed with the values $\{f_i{\}}_{i\in [n]}$ is contained in the set B formed with the values $\{t{\}}_{i\in [n]}$ . Notice that $|A|,|B|\le n$.

​ In the protocol, the prover has to construct an auxiliary vector $s=(s_1,\cdots ,s_{2n})$ containing every element of f and t where the order of appearance is the same as in $t$. The main idea behind the protocol is that if $f\in t$, then f contributes to s with repeated elements. To check this fact, a vector $\Delta s$ is defined as follows: $$\Delta s=(s_1+\gamma s_2,s_2+\gamma s_3,\cdots ,s_{2n}+\gamma s_1)\text{\hspace{1em}(8)}$$ ​ Then, the protocol essentially checks that $\Delta s$ is consistent with the elements of f, t and s. To do so, the vector s is split into two vectors $h_1,h_2\in {\mathbb{F}}^n$. In the protocol described in GW20, $h_1$ and $h_2$ contain the lower and upper halves of s, while in our protocol in [PFM+22](https://eprint.iacr.org/ 2022/086), we use $h_1$ to store elements with odd indexes and $h_2$ for even indexes, that is: $$h_1=(s_1,s_3,s_5,\cdots ,s_{2n-1})\text{and}{h}_2=(s_2,s_4,s_6,\cdots ,s_{2n})\text{\hspace{1em}(9)}$$ ​ With this setting in mind, the grand product polynomial is defined as: $$Z(g^i)=\{\begin{array}{l}1,\text{if}i=1\\ (1+\gamma {)}^{i-1}{\prod }_{j=1}^{i-1}\frac{(\delta +f_j)(\delta (1+\gamma )+t_j+\gamma t_{j+1})}{(\delta (1+\gamma )+s_{2j-1}+\gamma s_{2j})(\gamma (1+\gamma )+s_{2j}+\gamma s_{2j+1})},\text{if}i=2,\cdots ,n\end{array}\text{\hspace{1em}(10)}$$ where $\gamma ,\delta \in \mathbb{K}$ are the values sent from the verifier.

​ The definition of the previous polynomial is based on the following lemma, which is a slight modification of Claim 3.1. of GW20.

Lemma 3 (Soundness of Inclusion). Fix three vectors $f=(f_1,\cdots ,f_n),t=(t_1,\cdots .,t_n)$ and $s=(s_1,\cdots ,s_{2n})$ with elements in $\mathbb{F}$. If the following holds with probability larger than ${\epsilon }_{Inc}(n):=\frac{(4n-2)}{|\mathbb{K}|}$over randoms $\gamma ,\delta \in \mathbb{K}$: $$(1+\gamma {)}^n\prod _{i=1}^n(\gamma +f_i)\prod _{i=1}^{n-1}(\delta (1+\gamma )+t_i+\gamma t_{i+1})=\prod _{i=1}^{2n-1}(\delta (1+\gamma )+s_i+\gamma s_{i+1})\text{\hspace{1em}(11)}$$ then $f\in t$ and $s$ is the sorted by $t$ concatenation of $f$ and $t$.

​ As a consequence of Lemma 3, the identities that must be checked by the verifier for $x\in \mathrm{G}$ are the following: $$\begin{array}{rl}& L_1(x)(Z(x)-1)=0,\\ & Z(x\cdot g)=Z(x)\frac{(1+\gamma )(\delta +f(x))(\delta (1+\gamma )+t(x)+\gamma t(gx))}{(\delta (1+\gamma )+h_1(x)+\gamma h_2(x))(\delta (1+\gamma )+h_2(x)+\gamma h_1(x\cdot g))}\end{array}\text{\hspace{1em}(12)}$$ where $f,t\in {\mathbb{F}}_{<n}[X]$ are the polynomials resulting from the interpolation of $\{f_i{\}}_{i\in [n]}$ and $\{t_i{\}}_{i\in [n]}$ over $\mathrm{G}$, respectively; $h_1$ and $h_2\in {\mathbb{F}}_{<n}[X]$ are the polynomials resulting from the interpolation of the values defined in Eq$(8)$ over $\mathrm{G}$.

​ The commitment polynomial is the grand product polynomial $Z\in {\mathbb{K}}_{<n}[X]$ and $h_1$ and $h_2\in {\mathbb{F}}_{<n}[X]$ . and the two constraints is express in Eq $(12)$.

5.From Vector Arguments to Simple Arguments

​ Let’s explain first how we reduce vector inclusions or multiset equalities to simple (i.e., involving only one polynomial on each side) inclusions or multiset equalities.

Definition 1 (Vector Arguments). Given polynomials $f_i,t_i\in {\mathbb{K}}_{<n}[X]$ for $i\in [N]$, a vector inclusion, denoted $(f_1,\cdots ,f_N)\in (t_1,\cdots ,t_N)$, is the argument in which for all $x\in \mathrm{G}$ there exists some $y\in \mathrm{G}$ such that: $$(f_1(x),\cdots ,f_N(x))=(t_1(x),\cdots ,t_N(x))\text{\hspace{1em}(13)}$$ ​ A vector multiset equality, denoted $(f_1,\cdots ,f_N)\doteq (t_1,\cdots ,t_N)$, is the argument in which for all $y\in \mathrm{G}$ there exists exactly one $x\in \mathrm{G}$ for which Eq$(13)$ holds. That is, (vector) multiset equalities define a bijective mapping.

​ To reduce the previous vector arguments to simple ones, we make use of a uniformly sampled element $\alpha \in \mathbb{K}$. Namely, instead of trying to generate an argument for the vector relation, we define the following polynomials: $$F^{\prime }(x):=\sum _{i=1}^N{\alpha }^{i-1}{f}_i(X),T^{\prime }(x):=\sum _{i=1}^N{\alpha }^{i-1}{t}_i(X),\text{\hspace{1em}(14)}$$ and proceed to prove the relation $F^{\prime }\in T^{\prime }$ or $F^{\prime }\doteq T^{\prime }$ . Notice that both $F^{\prime }$ and $T^{\prime }$ are in general polynomials with coefficients over the field extension $\mathbb{K}$ even if every coefficient of $f_i$, $t_i$ is precisely over the base field $\mathbb{F}$.

​ The previous reduction leads to the following result.

Lemma 4. Given polynomials $f_i,t_i\in {\mathbb{K}}_{<n}[X]$ for $i\in [N]$ and $F^{\prime },T^{\prime }\in {\mathbb{K}}_{<n}[X]$ as defined by Eq.$(14)$, if $F^{\prime }\in T^{\prime }$ (resp. $F^{\prime }\doteq T^{\prime }$), then$(f_1,\cdots ,f_N)\in (t_1,\cdots ,t_N)$ (resp.$(f_1,\cdots ,f_N)\doteq (t_1,\cdots ,t_N)$) except with probability $n\cdot (N-1)/|\mathbb{K}|$ over the random choice of $\alpha$.

6.From Selected Vector Arguments to Simple Arguments

​ Now, let’s go one step further by the introduction of selectors. Informally speaking, a selected inclusion (multiset equality) is an inclusion (multiset equality) not between the specified two polynomials $f$ , $t$, but between the polynomials generated by the multiplication of $f$ and $t$ with (generally speaking) independently generated selectors. We generalize to the vector setting.

Definition 2 (Selected Vector Arguments). We are given polynomials $f_i,t_i\in {\mathbb{K}}_{<n}[X]$ for $i\in [N]$. Furthermore, we are also given two polynomials $f^{sel},t^{sel}\in {\mathbb{K}}_{<n}[X]$ whose range over the domain $\mathrm{G}$ is {0,1}. That is, $f^{sel}$ and $t^{sel}$ are selectors. A selected vector inclusion, denoted $f^{sel}\cdot (f_1,\cdots ,f_N)\in t^{sel}\cdot (t_1,\cdots ,t_N)$, is the argument in which for all $x\in \mathrm{G}$ there exists some $y\in \mathrm{G}$ such that: $$f^{sel}(x)\cdot (f_1(x),\cdots ,f_N(x))\in t^{sel}(y)\cdot (t_1(y),\cdots ,t_N(y))\text{\hspace{1em}(15)}$$ where $f^{sel}(x)\cdot (f_1(x),\cdots ,f_N(x))$ denotes the component-wise scalar multiplication between the field element $f^{sel}(x)$ and the vector $(f_1(x),\cdots ,f_N(x))$​.

​ A selected vector multiset equality, denoted $f^{sel}\cdot (f_1,\cdots ,f_N)\doteq t^{sel}\cdot (t_1,\cdots ,t_N)$. is the argument in which for all $y\in \mathrm{G}$ there exists exactly one $x\in \mathrm{G}$ for which Eq. (15) holds.

Remark 1. Note that if $f^{sel}=t^{sel}=1$, then Eq. (15) is reduced to (13); if $f^{sel}=t^{sel}=0$ then the argument is trivial; and if either $f^{sel}$ or $t^{sel}$ is equal to the constant 1, then we remove the need for $f^{sel}$ or $t^{sel}$ respectively.

​ To reduce selected vector inclusion to simple ones, we proceed in two steps. First, we use the reduction shown in Eq.$(14)$ to reduce the inner vector of polynomials to a single one. This process outputs polynomials $F^{\prime },T^{\prime }\in {\mathbb{K}}_{<n}[X]$ . Second, we make use of another uniformly sampled $\beta \in \mathbb{F}$ as follows. Namely, we define the following polynomials: $$\begin{array}{rl}& T(X):=t^{sel}(X)(T^{\prime }(X)-\beta )+\beta ,\\ & F(X):=f^{sel}(X)(F^{\prime }(X)-T^{\prime }(X))+T^{\prime }(X),\end{array}\text{\hspace{1em}(16)}$$ and proceed to prove the relation $F\in T$​.

​ Importantly, the presentation “re-ordering” in Eq. $(16)$ is relevant: if $\beta$ had been introduced in the definition of $F$ instead, then there would be situations in which we would end up having $\beta$​ as an inclusion value and therefore the inclusion argument not being satisfied even if the selectors are correct. See Example 1 to see why this is relevant.

Example 1. Choose $N=1,n=2^3$​ . We compute the following values:

Notice how $F\in T$. However, if we would have instead defined $F$, $T$ as $F(X)=f^{sel}(X)[F’(X)-\beta ]+\beta$ and $T(X)=t^{sel}(X)[T’(X)-F(X)]+F(X)$ then we would end up having $\beta$ as a inclusion value, which implies that $F\notin T$ even though $f_1$, $t_1$ and $f^{sel}$, $t^{sel}$ are correct.

To reduce selected vector multiset equalities to simple ones, we follow a similar process as with selected vector inclusions. We also first use the reduction in Eq.$(14)$ to reduce the inner vector argument to a simple one, but then we define the following polynomials: $$\begin{array}{rl}& T(X):=t^{sel}(X)(T^{\prime }(X)-\beta )+\beta \\ & F(X):=f^{sel}(X)(F^{\prime }(X)-\beta )+\beta \end{array}\text{\hspace{1em}(17)}$$ and proceed to prove the relation $F\in T$ . Here, we have been able to first define $F$ since we are dealing with multiset equalities instead of inclusions.

​ Similarly to Lemma 4, we obtain the following result. by observing that $\beta$ do not grow the total degree of polynomials $F,T$ (either from Eq. $(16)$ or Eq. $(17)$ ) over variables $\alpha ,\beta$.

​ We generalize to selected vector arguments the protocols for (simple) inclusion arguments and multiset equality arguments explained in Section 2 and 4 by incorporating the reduction strategies explained in this section. Therefore, we give next the soundness bounds for these protocols.

Lemma 5. Given polynomials $f_i,t_i\in {\mathbb{K}}_{<n}[X]$ for $i\in [N]$ and selectors $f^{sel},t^{sel}\in {\mathbb{K}}_{<n}[X]$, we obtain:

1. Inclusion Protocol. Let $T\in {\mathbb{K}}_{<2n-1}[X]$ and $F\in {\mathbb{K}}_{<3n-1}[X]$ as defined by Eq.$(16)$. The prover sends oracle functions $[f_i],[t_i],[f^{sel}],[t^{sel}]$ for $i\in [N]$ to the verifier in the first round, who responds with uniformly sampled $\alpha ,\beta \in \mathbb{K}$. Enlarge the set of identities that must be checked by the verifier in the inclusion protocol of Section 4 with:

$$\begin{array}{rl}& f^{sel}(x)(f_{sel}(x)-1)=0,\\ & t^{sel}(x)(t^{sel}(x)-1)=0,\end{array}\text{\hspace{1em}(18)}$$

for all $x\in \mathrm{G}$, i.e., the verifier checks that polynomials $f^{sel},t^{sel}$ are valid selectors.

2. Multiset Equality Protocol. Let $F,T\in {\mathbb{K}}_{<2n-1}[X]$ as defined by Eq.$(17)$. The prover sends oracle functions $[f_i],[t_i],[f^{sel}],[t^{sel}]$ for $i\in [N]$ to the verifier in the first round, who responds with uniformly sampled $\alpha ,\beta \in \mathbb{K}$. Enlarge the set of identities that must be checked by the verifier in the multiset equality protocol of Section 2 with: $$\begin{gathered} f^{sel}(x)(f_{sel}(x)-1)=0, \\ {t}^{sel}(x)(t^{sel}(x)-1)=0,\text{\hspace{1em}(19)} \end{gathered}$$ for all $x\in \mathrm{G}$.

Example 2. Say that for all $x\in \mathrm{G}$ the prover wants to prove that he knows some polynomials $t{r}_1,t{r}_2,t{r}_3,t{r}_4,t{r}_5\in {\mathbb{F}}_{<n-1}[X]$ such that: $$\begin{gathered} t{r}_1\in t{r}_3, \\ t{r}_3\doteq t{r}_4, \\ (t{r}_2,t{r}_1,t{r}_5)\propto (S_{{\sigma }_1},S_{{\sigma }_2},S_{{\sigma }_3}),\text{\hspace{1em}(20)} \end{gathered}$$ Following the previous section and this section, the polynomial constraint system $(20)$ gets transformed to the following one, so that for all $x\in \mathrm{G}$: $$\begin{gathered} L_1(x)(Z_1(x)-1)=0, \\ {Z}_1(gx)=Z_1(x)\frac{(1+\beta )(\gamma +{\text{tr}}_1(x))(\gamma (1+\beta )+{\text{tr}}_3(x)+\beta {\text{tr}}_3(gx))}{(\gamma (1+\beta )+h_{1,1}(x)+\beta h_{1,2}(x))(\gamma (1+\beta )+h_{1,2}(x)+\beta h_{1,1}(gx))} \\ {L}_1(x)(Z_2(x)-1)=0, \\ {Z}_2(gx)=Z_2(x)\frac{(\gamma +{\text{tr}}_3(x))}{(\gamma +{\text{tr}}_4(x))}, \\ {L}_1(x)(Z_3(x)-1)=0, \\ {\text{im}}_1(x)=({\text{tr}}_1(x)+\beta k_{1}x+\gamma )({\text{tr}}_5(x)+\beta k_{2}x+\gamma ), \\ {\text{im}}_2(x)=({\text{tr}}_1(x)+S_{{\sigma }_2}(x)+\gamma )({\text{tr}}_5(x)+S_{{\sigma }_3}(x)+\gamma ), \\ {Z}_3(gx)=Z_3(x)\frac{({\text{tr}}_2(x)+\beta x+\gamma ){\text{im}}_1(x)}{({\text{tr}}_2(x)+S_{{\sigma }_1}(x)+\gamma ){\text{im}}_2(x)},\text{\hspace{1em}(21)} \end{gathered}$$ where we notice that the only type of argument that sometimes need to be adjusted is the connection argument.

7.On the Quotient Polynomial

We obtain a single random value $\alpha \in \mathbb{K}$ and define the quotient polynomial as a random linear combination of the rational functions $q_i$ as follows: $$Q(X)=\sum _{i=0}^{\ell }{\alpha }^{i-1}{q}_i(X)\text{\hspace{1em}(22)}$$ ​ Note that we use powers of a uniformly sampled value $\alpha$ instead of sampling one value per constraint. Importantly, the soundness bound of this alternative version is linearly increased by the number of

constraints ℓ, so we might assume from now on that $\ell$ is sublinear in $|\mathbb{K}|$ to ensure the security of protocols.

8. Controlling the Constraint Degree with Intermediate Polynomials

​ In the vanilla STARK protocol, the initial set of constraints that one attest to compute the proof over is of unbounded degree. However, when one arrives at the point after computing the quotient polynomial $Q$, it should be split into polynomials of degree lower than $n$ to ensure the same redundancy is added as with the trace column polynomials $t{r}_i$ for a sound application of the FRI protocol. In this section, we explain an alternative for this process and propose the split to happen “at the beginning” and not “at the end” of the proof computation.

​ Therefore, we will proceed with this approach assuming that the arguments in Section 2-4 are included among the initial set of constraints. The constraints imposed by the grand products polynomials $Z_i$​ of multiset equalities and inclusions are of known degree: degree 2 for the former and degree 3 for the latter. Based on this information, we will propose a splitting procedure that allows for polynomial constraints up to degree 3 but will split any exceeding it.

​ Say the initial set of polynomial constraints $C=C_1,\cdots .,C_{\ell }$ contain a constraint of total degree greater or equal to 4. For instance, say that we have $C=C_1,C_2$ with: $$\begin{array}{rl}& C_1(X_1,X_2,X_3,X_1^{\prime },X_2^{\prime },X_3^{\prime })=X_1\cdot X_2\cdot X_2^{\prime }\cdot X_3^{\prime }-X_3^3,\\ & C_2(X_1,X_2,X_3,X_1^{\prime },X_2^{\prime },X_3^{\prime })=X_2-7\cdot X_1^{\prime }+X_3^{\prime },\end{array}\text{\hspace{1em}(23)}$$ Now, instead of directly computing the (unbounded) quotient polynomial $Q$ and then doing the split, we will follow the following process:

1. Split the constraints of degree $t\ge 4$ into $\lceil t/3\rceil$ constraints of degree lower or equal than 3 through the introduction of one formal variable and one constraint per split.

2. Compute the rational functions $q_i$ . Notice the previous step restricts the degree of the $q_i$ ‘s to be lower than 2$n$.

3. Compute the quotient polynomial $Q\in {\mathbb{F}}_{<2n}[X]$ and then split it into (at most) two polynomials $Q_1$ and $Q_2$ of degree lower than $n$ as follows: $$Q(X)=Q_1(X)+X^n\cdot Q_2(X)\text{\hspace{1em}(24)}$$ where $Q_1$ is obtained by taking the first $n$ coefficients of $Q$ and $Q_2$ is obtained by taking the last $n$ coefficients (filling with zeros if necessary).

   Remark 2*.* Here, we might have that $Q_2$ is identically equal to 0. This is in contrast with the technique used for the split in Vanilla STARK, where the quotient polynomial $Q$ is distributed uniformly across each of the trace quotient polynomials $Q_i$ .

This process will “control” the degree of $Q$ so that it will be always of a degree lower than 2$n$.

​ Following with the example in Eq. $(23)$, we rename $C_2$ to $C_3$ and introduce the formal variable $Y_1$ and the constraint: $$C_2(X_1,X_2,X_3,X_1^{\prime },X_2^{\prime },X_3^{\prime })=X_1\cdot X_2-Y_1\text{\hspace{1em}(25)}$$ ​ Now, to compute the rational functions $q_i$ , we have to compose $C_2$ not only with the trace column polynomials ${\text{tr}}_i$ but also with additional polynomials corresponding with the introduced variables $Y_i$ . We will denote these polynomials as ${\text{im}}_i$ and refer to them as intermediate polynomials.

​ Hence, the set of constraints in $(23)$ gets augmented to the following set: $$\begin{array}{rl}& C_1(X_1,X_2,X_3,X_1^{\prime },X_2^{\prime },X_3^{\prime },Y_1)=Y_1\cdot X_2^{\prime }\cdot X_3^{\prime }-X_3^3,\\ & C_2(X_1,X_2,X_3,X_1^{\prime },X_2^{\prime },X_3^{\prime },Y_1)=X_1\cdot X_2-Y_1,\\ & C_3(X_1,X_2,X_3,X_1^{\prime },X_2^{\prime },X_3^{\prime },Y_1)=X_2-7\cdot X_1^{\prime }+X_3^{\prime },\end{array}\text{\hspace{1em}(26)}$$ where we include the variable $Y_1$ in $C_3$ for notation simplicity. Note that now what we have is two constraints of degree lower than 3, but we have added one extra variable and constraint to take into account.

​ Discussing more in-depth the tradeoff generated between the two approaches, we have for one side that deg($Q$) = ${\text{max}}_i\{\text{deg}(q_i)\}={\text{max}}_i\{\text{deg}(C_i)(n-1)-|G|\}$. Denote by $i_{\text{max}}$ the index of the $q_i$ where the maximum is attained. Then, the number of polynomials $S$ in the split of $Q$ is equal to: $$\lceil \frac{\text{deg}(Q)}{n}\rceil =\lceil \frac{\text{deg}(C_{i_{\text{max}}})(n-1)-|G|}{n}\rceil =\text{deg}(C_{i_{\text{max}}})+\lceil -\frac{|G|}{n}\rceil$$ which is equal to either deg($C_{i_{\text{max}}}$) − 1 or deg($C_{i_{\text{max}}}$).

​ We must compare this number with the number of additional constraints (or polynomials) added in our proposal. So, on the other side, we have that the overall number ofconstraints $\tilde{\ell }$ is: $$\sum _{i=1}^{\ell }\lceil \frac{\text{deg}(C_i)}{3}\rceil$$ With $\tilde{\ell }\ge \ell$.

​ We conclude that the appropriate approach should be chosen based on the minimum value between $\tilde{\ell }\ge \ell$ and $S$.

Example 3. To give some concrete numbers, let us compare both approaches using the following set of constraints: $$\begin{array}{rl}& C_1(X_1,X_2,X_3,X_4,X_1^{\prime })=X_1\cdot X_2^2\cdot X_3^4\cdot X_4-X_1^{\prime },\\ & C_2(X_1,X_2,X_3)=X_1\cdot X_2^3+X_3^3,\\ & C_3(X_2,X_3,X_4,X_2^{\prime })=X_2^3\cdot X_3\cdot X_4+X_2^{\prime },\end{array}\text{\hspace{1em}(27)}$$ ​ In the vanilla STARK approach, we obtain $S=8$. On the other side, using the early splitting technique explained before, by substituting $X_1\cdot X_2^2$ by $Y_1$ and $X_2\cdot X_3\cdot X_4$ by $Y_2$ we transform the previous set of constraints into an equivalent one having all constraints of degree less or equal than 3. This reduction only introduces 2 additional constraints: $$\begin{array}{rl}& C_1(X_1^{\prime },Y_1,Y_2)=Y_1^2\cdot Y_2-X_1^{\prime },\\ & C_2(X_2,X_3,Y_1)=Y_1\cdot X_2+X_3^3,\\ & C_3(X_2,X_2^{\prime },Y_2)=Y_2\cdot X_2^2+X_2^{\prime },\\ & C_4(X_1,X_2,Y_1)=Y_1-X_1\cdot X_2^2,\\ & C_5(X_2,X_3,X_4,Y_2)=Y_2-X_2\cdot X_3\cdot X_4,\end{array}\text{\hspace{1em}(28)}$$ ​ Henceforth, the early splitting technique is convenient in this case, introducing 3 new polynomials instead of the 7 that proposes the vanilla STARK approach.