lopeetall/gist:2446dee95d42e02371b73ba2380bfda0 Secret

## gistfile1.txt
LogUp uses three vectors in its argument: the witnesses to be looked up, the multiplicities counting how many times each entry in the table is looked up, and the lookup table itself.

$w = [w_1, w_2, ..., w_l]$ // witnesses
$m = [m_1, m_2, ..., m_n]$ // multiplicities
$t = [t_1, t_2, ..., t_n]$ // lookup table

$V_w(x) = (x-w_1)(x-w_2)...(x-w_l)$ is a vanishing polynomial encoding the witnesses to be looked up. The $w_i$ may not all be distinct from one another if some entry is looked up multiple times from the table.

$V_t(x) = (x-t_1)^{m_1}(x-t_2)^{m_2}...(x-t_n)^{m_n}$ is a vanishing polynomial encoding the lookup table with the multiplicities $m_i$ included to accommodate multiple lookups of the same value when needed. If some entry is never looked up, its multiplicity will be zero and its corresponding factor disappears from the vanishing polynomial (because it becomes 1).

The core argument of LogUp is that all the $w_i$ are in the table if and only if $V_w$ divides $V_t$. In fact, if constructed as above the two polynomials will be equal.

LogUp goes one step further and adds an optimization. Instead of checking equality of the vanishing polynomials as products you can check the equality of two corresponding sums instead. The sums happen to be the logarithmic derivatives of the vanishing polynomials. Logarithms change products into sums and change powers into scalar multiples.

The logarithmic derivative of $V_t(x)$ is $\frac{m_1}{x-t_1} + \frac{m_2}{x-t_2} + ... + \frac{m_n}{x-t_n}$. The multiplicities were exponents but now they have become scalars.

Logarithms are great when working with real or complex numbers, but some properties don't translate well to finite fields. In a finite field, an exponent is an *integer*, not an element of the finite field, so exponents don't interact well with filed elements when transformed into scalars.

In a field of characteristic $p$, $x^p = x$ for all $x$. If a suitable base $b$ is chosen we can compute the discrete log, $y = \log_b(x)$ as long as $x\ne 0$. But look at $\log_b(x^p)$. If you apply the usual rules for logarithms you might expect that $\log_b(x^p) = p\cdot \log_b(x)$, but this can't be true, because in a field of characteristic $p$ the right hand side of this equation is zero, but because $x^p = x$ it is also supposed to be $\log_b(x)$. So this rule does not apply universally in finite fields. The trouble arises when an exponent is $> p-2$.

So, if a multiplicity in a LogUp lookup argument exceeds $p-2$, the logarithmic derivative no longer makes sense. In particular, if a Prover attempted to look up the value $w$ $p$ times, the log derivative form of the both vanishing polynomials becomes zero, no matter what $w$ happens to be. This lets the Prover cheat and use values which are not entries in the table.

Preventing this is easy if $p$ is large. The Prover would not be able to construct their witness vector of $p$ elements if $p$ is 256 bits for instance. Since the field used in this puzzle had a relatively small characteristic it is feasible to construct a witness vector `vec![1<<15; 70937]` which breaks the protocol.
	LogUp uses three vectors in its argument: the witnesses to be looked up, the multiplicities counting how many times each entry in the table is looked up, and the lookup table itself.

	$w = [w_1, w_2, ..., w_l]$ // witnesses
	$m = [m_1, m_2, ..., m_n]$ // multiplicities
	$t = [t_1, t_2, ..., t_n]$ // lookup table

	$V_w(x) = (x-w_1)(x-w_2)...(x-w_l)$ is a vanishing polynomial encoding the witnesses to be looked up. The $w_i$ may not all be distinct from one another if some entry is looked up multiple times from the table.

	$V_t(x) = (x-t_1)^{m_1}(x-t_2)^{m_2}...(x-t_n)^{m_n}$ is a vanishing polynomial encoding the lookup table with the multiplicities $m_i$ included to accommodate multiple lookups of the same value when needed. If some entry is never looked up, its multiplicity will be zero and its corresponding factor disappears from the vanishing polynomial (because it becomes 1).

	The core argument of LogUp is that all the $w_i$ are in the table if and only if $V_w$ divides $V_t$. In fact, if constructed as above the two polynomials will be equal.

	LogUp goes one step further and adds an optimization. Instead of checking equality of the vanishing polynomials as products you can check the equality of two corresponding sums instead. The sums happen to be the logarithmic derivatives of the vanishing polynomials. Logarithms change products into sums and change powers into scalar multiples.

	The logarithmic derivative of $V_t(x)$ is $\frac{m_1}{x-t_1} + \frac{m_2}{x-t_2} + ... + \frac{m_n}{x-t_n}$. The multiplicities were exponents but now they have become scalars.

	Logarithms are great when working with real or complex numbers, but some properties don't translate well to finite fields. In a finite field, an exponent is an integer, not an element of the finite field, so exponents don't interact well with filed elements when transformed into scalars.

	In a field of characteristic $p$, $x^p = x$ for all $x$. If a suitable base $b$ is chosen we can compute the discrete log, $y = \log_b(x)$ as long as $x\ne 0$. But look at $\log_b(x^p)$. If you apply the usual rules for logarithms you might expect that $\log_b(x^p) = p\cdot \log_b(x)$, but this can't be true, because in a field of characteristic $p$ the right hand side of this equation is zero, but because $x^p = x$ it is also supposed to be $\log_b(x)$. So this rule does not apply universally in finite fields. The trouble arises when an exponent is $> p-2$.

	So, if a multiplicity in a LogUp lookup argument exceeds $p-2$, the logarithmic derivative no longer makes sense. In particular, if a Prover attempted to look up the value $w$ $p$ times, the log derivative form of the both vanishing polynomials becomes zero, no matter what $w$ happens to be. This lets the Prover cheat and use values which are not entries in the table.

	Preventing this is easy if $p$ is large. The Prover would not be able to construct their witness vector of $p$ elements if $p$ is 256 bits for instance. Since the field used in this puzzle had a relatively small characteristic it is feasible to construct a witness vector `vec![1<<15; 70937]` which breaks the protocol.