Aztec Emulated Field and Group Operations for Efficient Large Number Arithmetic

<style> .markdown-body code, .markdown-body tt { color: #eee; background-color: rgba(20, 230, 230, 0.36); } /* a, .open-files-container li.selected a { color: #5EB7E0; } */ </style>  --- This note aims to detail our thoughts on a particular [short post](/@arielg/B13JoihA8) from researchers at Aztec, the team behind the original PLONK zk-SNARKs. Due to the original post's short form, some of the details are not altogether clear to us. It requires some leaps of logic or creativity in certain parts. Therefore, the explainations in this note might be a bit misleading in parts and should be taken with a grain of salt.Nevertheless, we will take the burden of possibility of being mistaken and write out what we understood from the original post.  Further, the methods in these notes (or methods similar to them) are implemented in the following repository, [https://github.com/privacy-scaling-explorations/halo2wrong](https://github.com/privacy-scaling-explorations/halo2wrong), to create efficient circuits for ECDSA verification algorithm which uses large fields. --- Motivation --- In some circuits such as DSA, we are frequently interested in representing modulo arithmetic over a large prime field, equations of the sort $a\cdot b = r \text{ mod } p$ where $p$ is a large prime. Typically, a witness $(a,b,r,q,p)$ is produced and the integer constraint $a\cdot b = q\cdot p + r$ is included as part of the polynomial commitment. Using non-native arithmetic discussed in this note, we can replace these types of constraints with (multiple) constraints over smaller numbers. Therefore, our goal in this note is to emulate certain expensive constraints in a different way. --- Setup --- Let us consider the setting and the naive approach. We are given a prime number $p$. We are interested in building a circuit for $a\cdot b \text{ mod } p$. The input variables $a,b$ must be in the range $[0, p)$. Otherwise, we would simply use the equivalent modulo statement with smaller numbers $(a \text{ mod } p)\cdot (b \text{ mod } p) \text{ mod } p$. We are interested in finding a non-negative integer $r$ s.t. $a\cdot b = r \text{ mod } p$ and $r$ is the smallest such number, which means $r$ is in the range $[0, p)$ as well. Given a candidate for $r$, we wish to build a constraint that ensures $r$ matches $(a,b,p)$. This would require us to introduce an advice variable $q$ (to show the existence of) that satisfies $a\cdot b = q\cdot p + r$, which is a unique positive number. Since $a\cdot b < p^2$ and the least value $r$ can take is $0$, $a\cdot b - r = q\cdot p < p^2$. This would imply $q$ is in the same range $[0, p)$. Therefore, all the relevant variables aside from $p$ itself are in the same range, $a,b,q,r\in [0, p)$. If we are willing to deal with values in the range $[0, p^2)$ in our circuit constraints, we can simply ensure that $a\cdot b - q \cdot p - r = 0$. However, this may not be desirable if $p$ is a large prime in the order of $2^{256}$ for example. In the rest of this note, we build the same constraint in a different way, circumventing the computation of $a\cdot b$ or $q\cdot p$ for a given $(a,b,q,p,r)$. --- Native Field Constraint --- We begin by considering a method to ensure $a\cdot b - q\cdot p -r = 0 \text{ mod } n$ for a prime $n < p$ without computing $a\cdot b$ or $q\cdot p$. Since the above equality implies $(a \mod n) \cdot (b \mod n) - (q \text{ mod } n)\cdot (p \text{ mod } n) - (r \text{ mod } n) = 0 \text{ mod } n$, we can write it with new variables $\{a_n, b_n, q_n, p_n, r_n\}$ s.t. $a = a_n \text{ mod } n$ etc. respectively. In order to accomplish this, we consider a new set of constraints with advice variables $\{v_a, v_b, v_q, v_p, v_r\}$, \begin{align} v_a \cdot n + a_n = a \tag{1} \\ v_b \cdot n + b_n = b \tag{2} \\ v_q \cdot n + q_n = q \tag{3} \\ v_p \cdot n + p_n = p \tag{4} \\ v_r \cdot n + r_n = r \tag{5} \\ \end{align}Based on $\{a_n, b_n, q_n, p_n, r_n\}$, we can simply re-write the additional *overall constraint* as $a_n\cdot b_n - q_n\cdot p_n - r_n = 0 \text{ mod } n$ or in an integer constraint form as, \begin{align} v_\text{overall} \cdot n = a_n\cdot b_n - q_n\cdot p_n - r_n. \tag{6} \end{align}Note that $a_n\cdot b_n - q_n\cdot p_n - r_n$ itself does not need to be $0$, unlike $a\cdot b - q\cdot p -r$. These are all integer constraints over numbers smaller than $n$ besides $\{a, b, q, p, r\}$. $\{a, b, q, p, r\}$ appear in constraints in Eq. 1-5 on their own without any multiplications with other numbers. Therefore, these constraint could be computed efficiently with small numbers. For a given $(a,b,q,p,r,v_a, v_b, v_q, v_p, v_r,v_\text{overall})$ that follows constraints in Eq. 1-6, it is guaranteed that $a\cdot b - q\cdot p -r = 0 \text{ mod } n$. However, $a\cdot b - q \cdot p - r = 0$ is not guaranteed. In order to satisfy $a\cdot b - q \cdot p - r = 0$, we will need the additional constraints we introduce in the next section.  --- Constraint decomposition in modulo $2^T$ ring, where $p<2^T$ --- In the following, $p' = -p \text{ mod } 2^T$ or more concretely $p'=2^T-p$. It is easy to see that $a \cdot b - q \cdot p = a \cdot b + q \cdot p' \mod 2^T$. Assume $T$ is a given integer that is a multiple of $4$. We will write integers such as $a,b$ in binary notation as a concatenation of multiple bit subsections, sometimes called limbs, as follows. Consider limbs of size $B=T/4$. Then an integer $a \in [0, 2^{T}-1]$ could be written as $4$ limbs, $a = [a_3, a_2, a_1, a_0]$, each of which is a number $a_i \in [0, 2^{B}-1]$ that can be represented as a sequence of $B$ bits, with $a = \sum_{i=0:3} a_i \cdot 2^{iB}$. Given $a,b, q, p' \in [0, 2^{T}-1]$, we can write the following equation for $a \cdot b + q \cdot p'$, \begin{align} a \cdot b + q \cdot p' &\text{ mod } 2^T = [a_3, a_2, a_1, a_0] \cdot [b_3, b_2, b_1, b_0] + [q_3, q_2, q_1, q_0] \cdot [p'_3, p'_2, p'_1, p'_0] \\ =& (a_0 \cdot b_0 + q_0 \cdot p'_0)\cdot 2^{0B} + \tag{7}\\ & (a_1 \cdot b_0 + a_0 \cdot b_1 + q_1 \cdot p'_0 + q_0 \cdot p'_1)\cdot 2^{1B} +\tag{8}\\ & (a_2 \cdot b_0 + a_0 \cdot b_2 + a_1 \cdot b_1 + q_2 \cdot p'_0 + q_0 \cdot p'_2 + q_1 \cdot p'_1)\cdot 2^{2B} + \tag{9}\\ & (a_3 \cdot b_0 + a_0 \cdot b_3 + a_1 \cdot b_2 + a_2 \cdot b_1 + q_3 \cdot p'_0 + q_0 \cdot p'_3 + q_1 \cdot p'_2 + q_2 \cdot p'_1)\cdot 2^{3B} \tag{10}\\ =& \hspace{0.05in} t_0\cdot 2^{0B} + t_1\cdot 2^{1B} + t_2\cdot 2^{2B} + t_3\cdot 2^{3B} \end{align} Note that we do not have terms that involve $a_3 \cdot b_3$ in these equations, even though they would appear in $a \cdot b + q \cdot p'$. The reason for this is simple: the term that involves $a_3 \cdot b_3$ would be $a_3 \cdot b_3 \cdot 2^{(3+3)B}$ and since $3+3 \ge 4$, this number is divisible by $2^T = 2^{4B}$ and is zero modulo $2^T$. The same is true for any $a_i \cdot b_j$ and $q_i \cdot p'_j$ with $i+j \ge 4$. This leaves us $10$ different terms for $a\cdot b$ (and $10$ terms for $q\cdot p'$) that are grouped together by the index sum $i+j \in \{0, 1, 2, 3\}$ in each line of Eq. 7-10 respectively. Once we group them in this way, we can factor out $2^{(i+j)B}$ in each line, according to the position $(i,j)$ of the limbs of the original numbers involved in the multiplications. Based on this grouping, we can create intermediate variables $t_{i+j} \in \{t_0, t_1, t_2, t_3\}$, \begin{gather} a \cdot b + q \cdot p' \text{ mod } 2^T = t_3\cdot 2^{3B} + t_2\cdot 2^{2B} + t_1\cdot 2^{1B} + t_0\cdot 2^{0B} \end{gather}which can take values in the following ranges: \begin{gather} t_0 \in [0, 2^{2B+1}-1]\\ t_1 \in [0, 2^{2B+2}-1]\\ t_2 \in [0, 2^{2B+3}-1]\\ t_3 \in [0, 2^{2B+3}-1] \end{gather}If the number of elements in each sum $t_i$ is represented by $v_i$, the formula for the range for each sum can be given as $t_i \in [0, 2^{2B+\lceil\log_2 v_i\rceil}-1]$. The exponent $2B + \lceil\log_2 v_i\rceil$ for the bound above will be explained through $t_2$. \begin{align} t_2 = a_2 \cdot b_0 + a_0 \cdot b_2 + a_1 \cdot b_1 + q_2 \cdot p'_0 + q_0 \cdot p'_2 + q_1 \cdot p'_1 \end{align}As we can see, it consists of a summation of $6$ terms where each element is the multiplication of two numbers in the range $[0, 2^{B}-1]$. When we multiply two such numbers, we end up with a number in the range $[0, 2^{2B+1}-1]$. $+1$ in $2^{2B+1}$ comes from the fact that there might be an additional carry bit after the multiplication. Further, when we add $6$ such numbers, we end up with a number in the range $[0, 6(2^{2B+1}-1)]$. This range can be (minimally) expanded above to a bit friendly range $[0, 2^{\lceil\log_2 6\rceil}\cdot 2^{2B}-6+5] = [0, 2^{2B+\lceil\log_2 6\rceil}-1]$ that encompasses $[0, 6(2^{2B+1}-1)]$. Let $t=t_3\cdot 2^{3B} + t_2\cdot 2^{2B} + t_1\cdot 2^{1B} + t_0\cdot 2^{0B}$. Note that $t$ itself does not need to be less than $2^T = 2^{4B}$. Its calculation only throws away some parts of $a \cdot b + q \cdot p'$ that do not contribute to the modulo result but not all. Therefore, if $a \cdot b + q \cdot p' = r \mod 2^T$ with $r < 2^T$, it is not guaranteed that $t = r$. However, the last $T$ bits of $t$ are certainly going to equal $r$ (the reason a power of two such as $2^T$ is convenient). ![](https://i.imgur.com/lTSbjC0.png) Further, if we consider the $B$-bit limb decomposition, $r = [r_3, r_2, r_1, r_0]$, $r_0$ is the last $B$ bits of $y_0=t_0+0$, i.e. $y_0-r_0 = z_0\cdot 2^B$ for some non-negative integer $z_0$. Similarly, $r_1$ is the last $B$ bits of $y_1= t_1 + z_0$ with $y_1-r_1 = z_1\cdot 2^B$. We can write the all the limbs of $r$ in a similar fashion: \begin{align} y_0&=t_0+0, \hspace{0.24in} y_0-r_0 = z_0\cdot 2^B\\ y_1&= t_1 + z_0, \hspace{0.2in} y_1-r_1 = z_1\cdot 2^B\\ y_2&= t_2 + z_1, \hspace{0.2in} y_2-r_2 = z_2\cdot 2^B\\ y_2&= t_3 + z_2, \hspace{0.2in} y_3-r_3 = z_3\cdot 2^B \end{align}Removing the intermediate variables $y$, we get \begin{align} t_0+0-r_0 &= z_0\cdot 2^B \tag{11}\\ t_1 + z_0-r_1 &= z_1\cdot 2^B \tag{12}\\ t_2 + z_1-r_2 &= z_2\cdot 2^B \tag{13}\\ t_3 + z_2-r_3 &= z_3\cdot 2^B.\tag{14} \end{align}  In this section, we have demonstrated a sets of integer constraints in Eq. 11-14 that can be used to ensure $a\cdot b + q\cdot p' = r \mod 2^T$, which also ensures $a\cdot b - q\cdot p - r = 0 \mod 2^T$. Note that we accomplish this without ever computing $a\cdot b$ or $q\cdot p$ but by working directly with their $B$-bit limbs in the constraints. To summarize, for a given $([a_3, a_2, a_1, a_0], [b_3, b_2, b_1, b_0], [q_3, q_2, q_1, q_0], [p'_3, p'_2, p'_1, p'_0],$ $[r_3, r_2, r_1, r_0],t_3, t_2, t_1, t_0, z_3, z_2,z_1,z_0)$ that satisfies the constraints in Eq. 11-14, along with constraints that ensures $p'=2^T-p$, \begin{align} p'_0 + p_0 + 0 = 2^B \tag{15} \\ p'_1 + p_1 + 1 = 2^B \tag{16} \\ p'_2 + p_2 + 1 = 2^B \tag{17} \\ p'_3 + p_3 + 1 = 2^B \tag{18} \end{align} it is guaranteed that $a\cdot b - q\cdot p -r = 0 \mod 2^T$ (but not $a\cdot b - q\cdot p - r = 0$ on their own). We finally note that constraints from the previous section in Eq. 1-6 can be written in the $B$-bit limb form as well, to match the constraints in this section.  --- **A different version from the original post**: The above is our version of how we would do this constraint decomposition. A different version of this that combines a pair of limbs $[r_3, r_2]$ and $[r_1, r_0]$ into the constraints is given below (the original formulation in the [blog post that this note is based on](/@arielg/B13JoihA8)). \begin{gather} u_0 = (t_1\cdot 2^{B} + t_0) - (r_1\cdot 2^{B} + r_0) \\ u_0 + 0 = v_0 \cdot 2^{2B}\\ u_1 = (t_3\cdot 2^{B} + t_2) - (r_3\cdot 2^{B} + r_2) \\ u_1+v_0 = v_1 \cdot 2^{2B} % v_1 = \frac{u_1+v_0}{2^{2B}} = \frac{u_1+\frac{u_0}{2^{2B}}}{2^{2B}} = \frac{u_1\cdot 2^{2B} + u_0}{2^{4B}}\\ % v_1 = \frac{(t_3-r_3)\cdot 2^{3B} + (t_2-r_2)\cdot 2^{2B} + (t_1-r_1)\cdot 2^{B} + (t_0-r_0)}{2^{T}} = \frac{(t_3, t_2, t_1, t_0)-(r_3, r_2, r_1, r_0)}{2^{T}} \end{gather} In the image below, we demostrate this idea. ![](https://i.imgur.com/mc6qtZ4.png) It is hard to tell what we gain from this particular formulation, which was given in the original post instead of our formulation above. There are $4$ constraints in each case and in the latter, there are multiplications with $2^{2B}$ which makes the numbers such as $u_0$ and $u_1$ quite a bit larger. We believe our formutation should be more efficient but it is difficult to be certain. --- Applying the Chinese Remainder Theorem --- We have shown constraints that allow us to restrict $(a,b,q,p,r)$ such that $a\cdot b - q\cdot p -r = 0 \mod n$ and $a\cdot b - q\cdot p -r = 0 \mod 2^T$. However, these do not guarantee that $a\cdot b - q\cdot p -r = 0$ without the modulo as $a\cdot b - q\cdot p -r = 0 \mod n$ is valid when $a\cdot b - q\cdot p -r$ is $\ge n$ and a multiple of $n$. Similarly, $a\cdot b - q\cdot p -r \ge 2^T$ and is a multiple of $2^T$ is allowed (this is a distinct possibility since $a\cdot b \in [0, p^2 \approx 2^{252})$). Therefore, individually, these constraints do not ensure $a\cdot b - q\cdot p -r = 0$. However, since $n$ and $2^T$ are coprimes ($n$ is a prime $>2$), i.e. $\text{gcd}(n, 2^T)=1$, we can invoke the constant-case CRT, which states, \begin{align} a\cdot b - q\cdot p - r = 0 \mod n \hspace{0.3in}\wedge\hspace{0.3in} & a\cdot b - q\cdot p - r = 0 \mod 2^T \\ \longleftrightarrow \hspace{0.3in} & a\cdot b - q\cdot p - r = 0 \mod (n\cdot 2^T) \end{align}Therefore, satisfying these constraints jointly means that $a\cdot b - q\cdot p - r = 0 \mod (n\cdot 2^T)$ is also satisfied. Does this guarantee that $a\cdot b - q\cdot p - r = 0$? Not necessarily, as it could be that $a\cdot b - q\cdot p -r \ge n\cdot 2^T$ and is a multiple of $n\cdot 2^T$. However, if we chose $(n, T)$ large enough s.t. this is not possible, then satisfying these constraints jointly *will* mean that $a\cdot b - q\cdot p - r = 0$. In order to accomplish this, we need to enforce $a\cdot b - q\cdot p -r < n \cdot 2^T$ by choosing $(n,T)$ s.t. $p^2< n\cdot 2^T$, as we already know the allowed ranges of variables, $a,b,q,r \in [0, p)$. We know that $n < p$. Therefore, it must be true that $2^T> p$. Therefore, $T$ must be large enough to satisfy $p^2< n\cdot 2^T$ but at the same time, it needs to be small enough that $B=T/4$ is sufficiently small to justify the multitude of constraints that involve numbers in the range $[0, 2^B)$.