Multiset checks with multiplicities and LogUp

This note picks up where the previous one on multiset checks left off. The main motivation for this note is to support a variation on multiset checks where we can encode how many times we expect an element to show up in the set (i.e. the multiplicity) without having that element showing up that many times. Specifically, the multiset check with multiplicities equation is

$$\prod _{i=1}^{n-1}\prod _{j=1}^k(\alpha -a_{ij}{)}^{m_{a_{ij}}}=\prod _{i=1}^{n-1}\prod _{j=1}^k(\alpha -b_{ij}{)}^{m_{b_{ij}}}$$

For example, if

$m_{a_{23}}=2$, then the term

$(\alpha -a_{23})$ in the equation is repeated twice:

$(\alpha -a_{23})\cdot (\alpha -a_{23})$. Hence, the value

$a_{23}$ would appear once in the

$\{a_{ij}\}$ multiset, but would need to appear twice in the

$\{b_{ij}\}$ multiset (or equivalently, only once, but with an associated multiplicity of

$2$). Note also that setting a multiplicity value to

$m_{a_{ij}}=0$ has the effect of "turning off" the associated

$(\alpha -a_{ij})$ term.

This is especially useful for range checks, which the Miden VM docs have a good introduction about.

The problem with multiplicities

Adding multiplicities creates challenges when implementing the new equation in STARKs, as it makes the running product column discussed in the previous note no longer viable. Specifically, the transition constraint for the running product column

$p$ would need to be:

$$p[i+1]=p[i]\times \prod _{j=1}^k\frac{(\alpha -a_{ij}{)}^{m_{a_{ij}}}}{(\alpha -b_{ij}{)}^{m_{b_{ij}}}}.$$

The right-hand side equation is not a polynomial, since both

$m_{a_{ij}}$ appears in the exponent position, and is itself a polynomial (and similarly for

$m_{b_{ij}}$). LogUp was designed to solve that problem.

LogUp

The core idea of LogUp is relatively simple. It involves applying the logarithm to both sides of the multiset check with multiplicities equation, followed by a derivative.

Note that the logarithm and the derivative are concepts defined over the real numbers. The paper goes into the formalism of how to formally think about these operations over finite fields, which we will take for granted in this note.

Start with the multiset check with multiplicities equation,

$$\prod _{i=1}^{n-1}\prod _{j=1}^k(\alpha -a_{ij}{)}^{m_{a_{ij}}}=\prod _{i=1}^{n-1}\prod _{j=1}^k(\alpha -b_{ij}{)}^{m_{b_{ij}}},$$

apply the logarithm to both sides (and a few logarithm rules),

$$\begin{array}{rl}\log \prod _{i=1}^{n-1}\prod _{j=1}^k(\alpha -a_{ij}{)}^{m_{a_{ij}}}& =\log \prod _{i=1}^{n-1}\prod _{j=1}^k(\alpha -b_{ij}{)}^{m_{b_{ij}}}\\ \sum _{i=1}^{n-1}\sum _{j=1}^k\log ((\alpha -a_{ij}{)}^{m_{a_{ij}}})& =\sum _{i=1}^{n-1}\sum _{j=1}^k\log ((\alpha -b_{ij}{)}^{m_{b_{ij}}})\\ \sum _{i=1}^{n-1}\sum _{j=1}^k{m}_{a_{ij}}\log (\alpha -a_{ij})& =\sum _{i=1}^{n-1}\sum _{j=1}^k{m}_{b_{ij}}\log (\alpha -b_{ij}),\end{array}$$

and then apply the derivative to both sides (where

$x$ will stand for the "current" and "next" row, the inputs to

$a_{ij}$ and

$b_{ij}$)

$$\begin{array}{rl}\frac{d}{dx}\sum _{i=1}^{n-1}\sum _{j=1}^k{m}_{a_{ij}}\log (\alpha -a_{ij})& =\frac{d}{dx}\sum _{i=1}^{n-1}\sum _{j=1}^k{m}_{b_{ij}}\log (\alpha -b_{ij})\\ \sum _{i=1}^{n-1}\sum _{j=1}^k{m}_{a_{ij}}\frac{d}{dx}\log (\alpha -a_{ij})& =\sum _{i=1}^{n-1}\sum _{j=1}^k{m}_{b_{ij}}\frac{d}{dx}\log (\alpha -b_{ij})\\ \sum _{i=1}^{n-1}\sum _{j=1}^k\frac{m_{a_{ij}}}{(\alpha -a_{ij})}& =\sum _{i=1}^{n-1}\sum _{j=1}^k\frac{m_{b_{ij}}}{(\alpha -b_{ij})}.\end{array}$$

And that's it! The final form of the LogUp equation is

$$\sum _{i=1}^{n-1}\sum _{j=1}^k\frac{m_{a_{ij}}}{(\alpha -a_{ij})}=\sum _{i=1}^{n-1}\sum _{j=1}^k\frac{m_{b_{ij}}}{(\alpha -b_{ij})}$$

Implementing LogUp in STARKs

LogUp in STARKs is going to look very similar to standard multiset checks: we will implement a running sum auxiliary column instead of a running product. Let's see how that would work. But first, we need to rearrange the LogUp equation slightly by subtracting the right-hand side on both sides:

$$\begin{array}{rl}\sum _{i=1}^{n-1}\sum _{j=1}^k\frac{m_{a_{ij}}}{(\alpha -a_{ij})}-\sum _{i=1}^{n-1}\sum _{j=1}^k\frac{m_{b_{ij}}}{(\alpha -b_{ij})}& =0\\ \sum _{i=1}^{n-1}(\sum _{j=1}^k\frac{m_{a_{ij}}}{(\alpha -a_{ij})}-\frac{m_{b_{ij}}}{(\alpha -b_{ij})})& =0\end{array}$$

Our running sum column

$s$ is going to be built similarly to the running product column for multiset checks. The first row will always contain

$0$, and each new row will start with the previous row's value, add

$\sum _{j=1}^k\frac{m_{a_{ij}}}{(\alpha -a_{ij})}$, and subtract

$\sum _{j=1}^k\frac{m_{b_{ij}}}{(\alpha -b_{ij})}$:

Row	$s$
1	0
2	$\sum _{j=1}^k\frac{m_{a_{0j}}}{\alpha -a_{0j}}-\frac{m_{b_{0j}}}{\alpha -b_{0j}}$
3	$\sum _{i=1}^2\sum _{j=1}^k\frac{m_{a_{ij}}}{(\alpha -a_{ij})}-\frac{m_{b_{ij}}}{(\alpha -b_{ij})}$
4	$\sum _{i=1}^3\sum _{j=1}^k\frac{m_{a_{ij}}}{(\alpha -a_{ij})}-\frac{m_{b_{ij}}}{(\alpha -b_{ij})}$
$\dots$	$\dots$
$n-1$	$\sum _{i=1}^{n-2}\sum _{j=1}^k\frac{m_{a_{ij}}}{(\alpha -a_{ij})}-\frac{m_{b_{ij}}}{(\alpha -b_{ij})}$
$n$	$\sum _{i=1}^{n-1}\sum _{j=1}^k\frac{m_{a_{ij}}}{(\alpha -a_{ij})}-\frac{m_{b_{ij}}}{(\alpha -b_{ij})}$

Boundary constraints

In the boundary constraints, we make sure that the first and last row of

$s$ contain

$0$:

$$s[1]=s[n]=0$$

Transition constraint

Then, the transition constraint needs to ensure that every row

$i$ (except the last) is built by taking the value in the previous row, add in

$\sum _{j=1}^k\frac{m_{a_{ij}}}{(\alpha -a_{ij})}$, and subtract out

$\sum _{j=1}^k\frac{m_{b_{ij}}}{(\alpha -b_{ij})}$:

$$s[i+1]=s[i]+(\sum _{j=1}^k\frac{m_{a_{ij}}}{(\alpha -a_{ij})})-(\sum _{j=1}^k\frac{m_{b_{ij}}}{(\alpha -b_{ij})}).$$

However, the current form is not a valid polynomial expression. We need to rearrange the equation so that we remove the division operations for equivalent multiplications:

$$\begin{array}{rl}& s[i+1](\prod _{j=1}^k\alpha -a_{ij})(\prod _{j=1}^k\alpha -b_{ij})=\\ & s[i](\prod _{j=1}^k\alpha -a_{ij})(\prod _{j=1}^k\alpha -b_{ij})\\ & +\sum _{j=1}^k{m}_{a_{ij}}\prod _{e\ne j}(\alpha -a_{ie})\prod _{e=1}^k(\alpha -b_{ie})\\ & -\sum _{j=1}^k{m}_{b_{ij}}\prod _{e\ne j}(\alpha -b_{ie})\prod _{e=1}^k(\alpha -a_{ie})\end{array}$$

This equation is a little difficult to parse, but it is simply the result of multiplying out all the denominators on both sides. For example, if

$k=1$, then the equation would look like:

$$\begin{array}{rl}& s[i+1](\alpha -a_{i0})(\alpha -b_{i0})=\\ & s[i](\alpha -a_{i0})(\alpha -b_{i0})+m_{a_{i0}}(\alpha -b_{i0})-m_{b_{i0}}(\alpha -a_{i0})\end{array}$$

Ultimately, the running sum column implementing LogUp achieved what the running product column could not: a polynomial transition constraint.

Transition constraint degree

LogUp is a good choice for use cases that can't do without representing multiplicities. However, as we'll see, we pay with a higher transition constraint degree. Specifically, the transition constraint degree is the maximum of

$$\begin{array}{rl}& 1+\sum _{j=1}^k(\mathrm{deg}{a}_{ij}+\mathrm{deg}{b}_{ij}),\\ & \mathrm{\forall }j,\mathrm{deg}{m}_{a_{ij}}+\sum _{e\ne j}\mathrm{deg}{a}_{ie}+\sum _{e=1}^k\mathrm{deg}{b}_{ie},\mathrm{and}\\ & \mathrm{\forall }j,\mathrm{deg}{m}_{b_{ij}}+\sum _{e\ne j}\mathrm{deg}{b}_{ie}+\sum _{e=1}^k\mathrm{deg}{a}_{ie}.\end{array}$$

The biggest difference with the running product column transition constraint degree (other than the fact that we now have multiplicities) is that now the degree of the

$a_{ij}$'s and the

$b_{ij}$'s add together.

Hence, the rule of thumb is that between a standard multiset check and LogUp, prefer to use a standard multiset check when possible to lower the transition constraint degree.