Prueba de rango

Last updated on Nov 20, 2024

Una prueba de rango en el contexto de los argumentos de producto interno es una prueba de que el escalar $v$ ha sido comprometido en $V$ y $v$ es menor que $2^n$ para algún número entero no negativo $n$ .

Este artículo muestra cómo el documento de Bulletproofs construye dicha prueba. La idea a alto nivel es que si podemos demostrar que un vector $\mathbf{a}_L$ consiste solo de unos y ceros y que $\mathbf{a}_L$ es la representación binaria de $v$ , entonces $v$ debe ser menor que $2^n$ . Esto es análogo a decir que un número que cabe en un entero sin signo de 8 bits debe ser menor que 256.

La ventaja de usar Bulletproofs para pruebas de rango es que la prueba de rango se puede construir directamente sin la necesidad de un circuito aritmético.

Monero utiliza las Pruebas de Rango de Bulletproofs (el algoritmo presentado aquí) para garantizar que la suma de las transacciones no sea negativa (en un campo finito, los números negativos son los elementos mayores que $p/2$ , ya que son los inversos aditivos de los elementos menores o iguales a $p/2$ , donde $p$ es el orden del campo).

Este artículo es parte de una serie sobre ZK Bulletproofs.

Notación

$\mathbf{0}^n$ es un vector de dimensión $n$ de solo ceros.

$\mathbf{1}^n$ es un vector de dimensión $n$ de solo unos.

$\mathbf{2}^n$ es un vector de dimensión $n$ $[1,2,4,8,...,2^{n-1}]$

$\mathbf{y}^n$ es un vector de dimensión $n$ $[1, y, y^2, y^3, ..., y^{n-1}]$

$\mathbf{y}^{-n}$ es un vector de dimensión $n$ $[1, y^{-1}, y^{-2}, ..., y^{-(n-1)}]$

Nota que $\mathbf{y}^n\circ\mathbf{y}^{-n}=\mathbf{1}^n$ .

Descripción general de la prueba de rango

Demostrar que $V$ es un compromiso a un escalar con un valor menor que $2^n$ requiere demostrar lo siguiente:

$\mathbf{a}_L$ es binario (solo contiene los valores $0$ y $1$ ).
El producto interno $\langle \mathbf{a}_L,\mathbf{2}^n\rangle=v$ .

El segundo punto es fácil de demostrar, hacemos una prueba de producto interno normal y luego revelamos que $\mathbf{2}^n$ es uno de los vectores en el compromiso, o hacemos que el verificador construya el compromiso de $\mathbf{2}^n$ por sí mismo. Sin embargo, demostrar que $\mathbf{a}_L$ es binario sin un circuito aritmético requiere un par de trucos algebraicos.

Cuatro trucos útiles

El documento de Bulletproofs utiliza implícitamente cuatro trucos algebraicos que es mejor enseñar explícitamente antes de ver directamente el algoritmo de la prueba de rango.

1. Demostrar que $\mathbf{a}_L$ es binario

La afirmación de que $\mathbf{a}_L$ es binario es equivalente a las siguientes dos aseveraciones:

$\mathbf{a}_R = \mathbf{a}_L-\mathbf{1}^n$
$\mathbf{a}_L \circ \mathbf{a}_R = \mathbf{0}^n$

Por ejemplo, si $\mathbf{a}_L = [1,0,0,1]$ entonces $\mathbf{a}_R=[0,-1,-1,0]$ .

En este caso, $\mathbf{a}_L \circ\mathbf{a}_R=\mathbf{0}^n$ porque

[1,0,0,1] \circ [0,-1,-1,0] = [0,0,0,0] = \mathbf{0}^n

Ahora considera un caso donde $\mathbf{a}_L$ no es binario, por ejemplo $[2, 1, 0, 0]$ . $\mathbf{a}_R$ será $[1,0,-1,-1]$ . El producto de Hadamard de $\mathbf{a}_L$ y $\mathbf{a}_R$ será $[2,0,0,0] \neq \mathbf{0}^n$ .

De manera más general, si $\mathbf{a}_L$ tiene una entrada no binaria, a esa entrada se le restará $1$ , y la entrada resultante en $\mathbf{a}_R$ será distinta de cero. Cuando se calcula el producto de Hadamard, en ese índice particular, tanto $\mathbf{a}_L$ como $\mathbf{a}_R$ serán distintos de cero y el producto será distinto de cero, lo que significa que $\mathbf{a}_L \circ \mathbf{a}_R \neq \mathbf{0}^n$ .

Sin embargo, si una entrada particular en $\mathbf{a}_L$ es $1$ , entonces $\mathbf{a}_R$ será $0$ en ese índice, por lo que el producto de Hadamard en ese índice también será cero.

Finalmente, si una entrada particular en $\mathbf{a}_L$ es $0$ , entonces $\mathbf{a}_R$ será $-1$ en ese índice y su producto elemento por elemento seguirá siendo cero en ese índice.

Por lo tanto, si $\mathbf{a}_L$ es binario y $\mathbf{a}_R$ se calcula como $\mathbf{a}_R = \mathbf{a}_L-\mathbf{1}$ , entonces $\mathbf{a}_L \circ \mathbf{a}_R = \mathbf{0}^n$ .

2. Demostrar que un vector es todo ceros

Supongamos que deseamos demostrar que el compromiso de Pedersen $A$ contiene un vector cero. Creamos el compromiso de Pedersen $A = \langle\mathbf{a},\mathbf{G}\rangle + \alpha B$ y deseamos demostrarle a un verificador que $\mathbf{a}=\mathbf{0}^n$ .

Podría parecer suficiente enviar simplemente el término de cegado $\alpha$ , pero para que nuestra solución sea más componible, no queremos revelar el término de cegado porque eso podría afectar otros compromisos que hemos creado.

En su lugar, el probador envía $A$ al verificador, y el verificador responde con un vector lleno de valores aleatorios $\mathbf{r}$ . El probador ahora debe demostrar que

\langle\mathbf{a},\mathbf{r}\rangle = 0

Nota que esta es una prueba probabilística. Es posible, con probabilidad insignificante, que $\langle\mathbf{a},\mathbf{r}\rangle=0$ para $\mathbf{a}\neq\mathbf{0}^n$ , pero no es posible que el probador falsifique tal $\mathbf{a}$ porque no sabe de antemano cuál será $\mathbf{r}$ .

Sin embargo, transmitir $\mathbf{r}$ requiere una sobrecarga de comunicación $\mathcal{O}(n)$ , por lo que, en su lugar, el verificador solo envía un único elemento aleatorio $y$ y el probador calcula $\mathbf{y}^n$ y utiliza $\mathbf{y}^n$ como el vector aleatorio.

Luego, el probador demuestra que $\langle\mathbf{a},\mathbf{y}^n\rangle=0$ .

3. Demostrar que un producto interno tiene la forma $\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle$ donde el verificador elige $y$ y el probador calcula $\mathbf{y}^n$

Aún no tenemos un mecanismo para demostrar que $\mathbf{a}_L\circ\mathbf{a}_R=\mathbf{0}^n$ , ya que es un producto de Hadamard, no un producto interno. Sin embargo, afirmar que el vector $\mathbf{a}_L\circ\mathbf{a}_R$ es idénticamente $\mathbf{0}^n$ es lo mismo que afirmar que $\langle\mathbf{a}_L\circ\mathbf{a}_R,\mathbf{y}^n\rangle=0$ . Según las reglas del producto interno, podemos mover $\mathbf{a}_R$ al otro lado del producto interno y ahora tenemos $\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle=0$ .

El verificador recibirá compromisos para $\mathbf{a}_L$ y $\mathbf{a}_R$ , no para $\mathbf{a}_R\circ\mathbf{y}^n$ . Dependerá del verificador construir un compromiso para $\mathbf{a}_R\circ\mathbf{y}^n$ de modo que esté convencido de que el probador usó $\mathbf{a}_R\circ\mathbf{y}^n$ como el segundo vector en el producto interno.

El truco clave en el que confiamos es que el probador utiliza los vectores base $\mathbf{G}$ y $\mathbf{H}$ para comprometer sus vectores, pero el verificador usa $\mathbf{G}$ y $\mathbf{H}\circ\mathbf{y}^{-n}$ .

Cuando el probador envía la evaluación $\mathbf{r}_u$ , el probador debe asegurarse de que los términos $\mathbf{y}^n$ se cancelarán con $\mathbf{y}^{-n}$ en el vector base del verificador $\mathbf{y}^{-n}\circ\mathbf{H}$ .

Específicamente, el probador construye los compromisos

\begin{align*} A &= \langle\mathbf{a}_L,\mathbf{G}\rangle+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B\\ S &= \langle\mathbf{s}_L,\mathbf{G}\rangle+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B \end{align*}

Y envía $(A, S)$ al verificador. No es necesario comprometer y enviar $V$ porque en este caso es cero.

Los polinomios del probador serán

\begin{align*} \mathbf{l}(x)&=\mathbf{a}_L + \mathbf{s}_Lx\\ \mathbf{r}(x)&=\mathbf{a}_R\circ\mathbf{y}^n + \boxed{\mathbf{s}_R\circ\mathbf{y}^n}x \end{align*}

Crucialmente, el probador ha multiplicado con el producto de Hadamard a $\mathbf{s}_R$ por $\mathbf{y}^n$ . Anteriormente, $\mathbf{r}(x)$ se calculaba como $\mathbf{r}(x)=\mathbf{a}_R\circ\mathbf{y}^n + \mathbf{s}_Rx$ (sin el $\mathbf{y}^n\circ\mathbf{s}_R$ ). Esto permitirá más adelante que todos los términos $\mathbf{y}^n$ se cancelen cuando el verificador calcule el compromiso $\langle\mathbf{r}_u,\mathbf{y}^{-n}\circ\mathbf{H}\rangle$ . Internamente, $\mathbf{r}_u$ es $(\mathbf{a}_R+\mathbf{s}_Ru)\circ\mathbf{y}^n$ , por lo que el $\mathbf{y}^n$ se cancelará cuando el verificador calcule $\langle(\mathbf{a}_R+\mathbf{s}_Ru)\circ\mathbf{y}^n,\mathbf{y}^{-n}\circ\mathbf{H}\rangle$ , es decir:

\begin{align*} &\langle(\mathbf{a}_R+\mathbf{s}_Ru)\circ\mathbf{y}^n,\mathbf{y}^{-n}\circ\mathbf{H}\rangle\\ &=\langle(\mathbf{a}_R+\mathbf{s}_Ru),\mathbf{y}^n\circ\mathbf{y}^{-n}\circ\mathbf{H}\rangle\\ &=\langle(\mathbf{a}_R+\mathbf{s}_Ru),\mathbf{1}^n\circ\mathbf{H}\rangle\\ &=\langle(\mathbf{a}_R+\mathbf{s}_Ru),\mathbf{H}\rangle \end{align*}

Sin embargo, el probador aún no puede calcular $\mathbf{l}(x)$ ni $\mathbf{r}(x)$ porque el verificador todavía no ha enviado $y$ . Por lo tanto, después de recibir $(A, S)$ , el verificador envía $y$ y el probador calcula $\mathbf{y}^n$ y calcula el polinomio $t(x)$ :

t(x)=\langle\mathbf{l}(x),\mathbf{r}(x)\rangle=\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle+t_1x+t_2x^2

donde

\begin{align*} t_1&=\langle\mathbf{a}_L,\mathbf{s}_R\circ\mathbf{y}^n\rangle + \langle\mathbf{s}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle\\ t_2&=\langle\mathbf{s}_L,\mathbf{s}_R\circ\mathbf{y} ^n\rangle \end{align*}

El probador se compromete con los coeficientes $t_1$ y $t_2$ como

\begin{align*} T_1&=t_1G+\tau_1B\\ T_2&=t_2G+\tau_2B \end{align*}

y envía $(T_1, T_2)$ al verificador. El verificador responde con $u$ y el probador evalúa los polinomios vectoriales $\mathbf{l}(x)$ y $\mathbf{r}(x)$ :

\begin{align*} \mathbf{l}_u&= \mathbf{a}_L+\mathbf{s}_Lu\\ \mathbf{r}_u&= \mathbf{a}_R\circ\mathbf{y}^n+(\mathbf{s}_R\circ\mathbf{y}^n)u\\ t_u&=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\ \pi_{lr}&=\alpha + \beta u\\ \pi_t&=\tau_1u+\tau_2u^2 \end{align*}

Nota que $\pi_t$ solo incluye los términos de cegado para $t_1$ y $t_2$ . En la implementación anterior, $\pi_t$ se calculaba como $\gamma + \tau_1u+\tau_2u^2$ , donde $\gamma$ es el término de cegado para $V$ , que también es el coeficiente constante del polinomio $t(x)$ .

No hay término de cegado $\gamma$ porque no hay compromiso con $V$ , es decir, $v$ no es secreto (es $0$ ). El probador envía $(\mathbf{l}_u, \mathbf{r}_u, t_u, \pi_{lr}, \pi_t)$ y el verificador comprueba que:

\begin{align*} t_u&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\ A+Su&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{G}\rangle+\langle\mathbf{r}_u,\mathbf{y}^{-n}\circ\mathbf{H}\rangle+\pi_{lr}B\\ t_uG&\stackrel{?}{=} T_1 u + T_2 u^2 - \pi_t B\\ \end{align*}

La primera diferencia crucial es que el compromiso con $\mathbf{r}_u$ se hace con respecto al vector base $\mathbf{y}^{-n}\circ\mathbf{H}$ en lugar de $\mathbf{H}$ por las razones discutidas anteriormente.

Segundo, $t_uG\stackrel{?}{=} T_1 u + T_2 u^2 - \pi_t B$ no tiene un compromiso constante. Normalmente, la ecuación es $t_uG\stackrel{?}{=} \boxed{V}+T_1 u + T_2 u^2 - \pi_t B$ , pero $V$ es un compromiso con $0$ en este caso.

En general, si $V$ contiene valores conocidos por el verificador, el verificador puede construir el compromiso con $V$ como mostramos en la siguiente sección.

4. Demostrar un producto interno cuando interviene una constante pública aditiva

Como se aludió en la sección anterior, el verificador puede reconstruir compromisos si conoce el vector subyacente.

Por ejemplo, supongamos que estamos demostrando que

$\langle\mathbf{a}_L + \mathbf{j},\mathbf{a}_R\circ\mathbf{y}^n + \mathbf{k}\rangle=vz$

donde $\mathbf{j}$ y $\mathbf{k}$ son vectores conocidos por el verificador y $z$ es un escalar conocido por el verificador de antemano. A diferencia de $\mathbf{y}^n$ , estos vectores y escalar se conocen antes de que comience la prueba. Nota que en este ejemplo $\mathbf{k}$ no está multiplicado por Hadamard con $\mathbf{y}^n$ .

El probador aún se compromete solo a los valores secretos $\mathbf{a}_L$ , $\mathbf{a}_R$ y $v$ como de costumbre:

\begin{align*} A &= \langle\mathbf{a}_L,\mathbf{G}\rangle+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B\\ S &= \langle\mathbf{s}_L,\mathbf{G}\rangle+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B\\ V &= vG + \gamma B \end{align*}

Como de costumbre, los polinomios $\mathbf{l}(x)$ y $\mathbf{r}(x)$ son tales que el término constante es el vector del producto interno original y los términos lineales son $\mathbf{s}_L$ y $\mathbf{s}_R$ . Al recibir $y$ del verificador, el probador calcula $\mathbf{y}^n$ y crea, pero no evalúa, $\mathbf{l}(x)$ y $\mathbf{r}(x)$ :

\begin{align*} \mathbf{l}(x)&=\underbrace{\mathbf{a}_L + \mathbf{j}}_\text{vector izquierdo} + \mathbf{s}_Lx\\ \mathbf{r}(x)&=\underbrace{\mathbf{a}_R\circ\mathbf{y}^n + \mathbf{k}}_\text{vector derecho} + \boxed{\mathbf{s}_R\circ\mathbf{y}^n}x \end{align*}

Nota que $\mathbf{k}$ no está multiplicado por Hadamard con $\mathbf{y}^n$ , pero el término lineal $\mathbf{s}_R$ sí lo está. Mostraremos cómo maneja esto el verificador más adelante.

Por ahora, calculamos $t(x)$ como

t(x)=vz+t_1x+t_2x^2

donde

\begin{align*} t_1&=\langle\mathbf{a}_L+\mathbf{j},\mathbf{s}_R\circ\mathbf{y}^n\rangle + \langle\mathbf{s}_L,\mathbf{a}_R\circ\mathbf{y}^n+\mathbf{k}\rangle\\ t_2&=\langle\mathbf{s}_L,\mathbf{s}_R\circ\mathbf{y} ^n\rangle \end{align*}

Nota que el término constante en $t(x)$ es $vz$ y no $v$ . Los compromisos se calculan como

\begin{align*} T_1 &= t_1G+\tau_1B\\ T_2 &= t_2G+\tau_2B\\ \end{align*}

y se envían al verificador, quien luego envía el valor aleatorio $u$ .

El probador calcula:

\begin{align*} \mathbf{l}_u&= \mathbf{a}_L\circ\mathbf{y}^n+\mathbf{j}+(\mathbf{s}_L\circ\mathbf{y}^n)u\\ \mathbf{r}_u&= \mathbf{a}_R\circ\mathbf{y}^n+\mathbf{k}+\mathbf{s}_Ru\\ t_u&=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\ \pi_{lr}&=\alpha + \beta u\\ \pi_t&=vz+\tau_1u+\tau_2u^2 \end{align*}

Nota que el término constante en $\pi_t$ es $\gamma z$ . El probador envía $(\mathbf{l}_u,\mathbf{r}_u,t_u,\pi_{lr},\pi_t)$ . Finalmente, el verificador calcula:

\begin{align*} t_u&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\ A+Su+\underbrace{\langle\mathbf{j,\mathbf{G}}\rangle}_{\text{compromiso de } \mathbf{j} \text{ en } \mathbf{l}(x)}+\underbrace{\langle\mathbf{k},\mathbf{y}^{-n}\circ\mathbf{H}\rangle}_{\text{compromiso de } \mathbf{k} \text{ en } \mathbf{r}(x)}&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{G}\rangle+\langle\mathbf{r}_u,\mathbf{y}^{-n}\circ\mathbf{H}\rangle+\pi_{lr}B\\ t_uG&\stackrel{?}{=} Vz+ T_1 u + T_2 u^2 - \pi_t B\\ \end{align*}

$\mathbf{l}_u$ y $\mathbf{r}_u$ contienen $\mathbf{j}$ y $\mathbf{k}$ respectivamente, pero $A$ y $S$ no. Por lo tanto, el verificador calcula compromisos para esos vectores y los suma a los compromisos $A$ y $S$ . En el caso de $\mathbf{k}$ , el vector base $\mathbf{y}^{-n}\circ\mathbf{H}$ hará que $\mathbf{k}$ se convierta en $\mathbf{k}\circ\mathbf{y}^{-n}$ , por lo que el compromiso debe calcularse con respecto a $\mathbf{y}^{-n}\circ\mathbf{H}$ . Finalmente, el término de cegado $\pi_t$ contiene $vz$ , pero $V$ no contiene $z$ . Por lo tanto, el probador debe multiplicar $V$ por $z$ .

Al calcular $\langle\mathbf{j},\mathbf{G}\rangle$ , $\langle\mathbf{k},\mathbf{y}^n\circ\mathbf{H}\rangle$ y $Vz$ , el verificador puede estar seguro de que el cálculo del producto interno realmente incluyó esos términos.

Para demostrar que $V$ es un valor menor que $2^n$ tenemos tres cosas que probar:

el producto interno $\langle \mathbf{a}_L,\mathbf{2}^n\rangle = V$ , es decir, $\mathbf{a}_L$ es la representación binaria de $v$
$\mathbf{a}_R=\mathbf{a}_L-\mathbf{1}$
$\mathbf{a}_L \circ \mathbf{a}_R = \mathbf{0}$

Las dos últimas afirmaciones no están directamente en la forma de un producto interno. Sin embargo, podemos modificarlas ligeramente para lograr esto. Lo que realmente estamos diciendo es que los vectores

$\mathbf{a}_R - \mathbf{a}_L+\mathbf{1}$
$\mathbf{a}_L\circ\mathbf{a}_R$

son ambos $\mathbf{0}^n$ . Podemos usar el truco de una sección anterior para demostrar que son cero. Es decir, el probador necesita establecer que

\langle\mathbf{a}_L\circ\mathbf{a}_R,\mathbf{y}^n\rangle=\mathbf{0}

\langle \mathbf{a}_R - \mathbf{a}_L+\mathbf{1},\mathbf{y}^n\rangle=\mathbf{0}

donde $\mathbf{y}^n$ es el vector aleatorio derivado del valor $y$ enviado por el verificador.

El documento original de Bulletproofs modifica ligeramente la primera afirmación de la siguiente manera para que podamos usar el tercer truco de la sección anterior:

\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle=\mathbf{0}

Por lo tanto, el probador tiene tres productos internos que establecer:

$\langle \mathbf{a}_L,\mathbf{2}^n\rangle = v$
$\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle=\mathbf{0}^n$
$\langle\mathbf{a}_L -\mathbf{1}^n- \mathbf{a}_R,\mathbf{y}^n\rangle=\mathbf{0}^n$

Combinar tres productos internos en uno

Los tres productos internos se pueden combinar en uno solo usando una combinación lineal aleatoria con la aleatoriedad $z$ proporcionada por el verificador.

z^2 \cdot \langle \mathbf{a_L}, 2^n \rangle + z^1 \cdot \langle \mathbf{a_L} - \mathbf{1}^n - \mathbf{a_R}, \mathbf{y}^n \rangle + z^0\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = z^2 \cdot v + z^1\cdot\mathbf{0}^n+z^0\cdot\mathbf{0}^n

z^2 \cdot \langle \mathbf{a_L}, 2^n \rangle + z \cdot \langle \mathbf{a_L} - \mathbf{1}^n - \mathbf{a_R}, \mathbf{y}^n \rangle + \langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = z^2 \cdot v

Con un poco de álgebra de producto interno muy pesada, podemos combinar todos los productos internos de la siguiente manera. Mostramos la derivación en el apéndice.

\left\langle \mathbf{a_L} - z \cdot \mathbf{1}^n, \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n \right\rangle = z^2 \cdot v + (z - z^2) \cdot \langle \mathbf{1}^n, y^n \rangle - z^3 \langle \mathbf{1}^n, 2^n \rangle

Los términos en los recuadros de abajo contienen valores conocidos por el verificador, por lo que construiremos nuestro algoritmo de verificación para comprobar explícitamente esos valores. Es decir, el verificador calculará los compromisos para los valores en los términos recuadrados, no el probador:

\left\langle \mathbf{a_L} - \boxed{z \cdot \mathbf{1}^n}, \mathbf{y}^n \circ \mathbf{a_R} + \boxed{\mathbf{y}^n\cdot z + z^2 \cdot 2^n }\right\rangle = \boxed{z^2} \cdot v + \boxed{(z - z^2) \cdot \langle \mathbf{1}^n, y^n \rangle - z^3 \langle \mathbf{1}^n, 2^n \rangle}

Para ahorrar espacio, el documento de Bulletproofs se refiere al término $(z - z^2) \cdot \langle \mathbf{1}^n, y^n \rangle - z^3 \langle \mathbf{1}^n, 2^n \rangle$ como $\delta(y,z)$ , por lo que el producto interno se puede escribir como

\left\langle \mathbf{a_L} - z \cdot \mathbf{1}^n, \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n \right\rangle = z^2 \cdot v + \delta(y,z)

Nota que $\delta(y,z)$ es un valor que el verificador puede calcular.

Algoritmo de prueba de rango

El probador elige $v$ y su representación binaria $\mathbf{a}_L$ y calcula $\mathbf{a}_R = \mathbf{a}_L - \mathbf{1}$ .

Luego, el probador elige aleatoriamente el término de cegado $\alpha$ y calcula el compromiso combinado de $\mathbf{a}_L$ y $\mathbf{a}_R$ usando los vectores base $\mathbf{G}$ y $\mathbf{H}$ como

A = \langle\mathbf{a}_L,\mathbf{G}\rangle+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B

Luego, el probador elige los términos lineales de los polinomios vectoriales que están por crearse, $\mathbf{l}(x)$ y $\mathbf{r}(x)$ , como $\mathbf{s}_L$ y $\mathbf{s}_R$ , y se compromete a ellos

S = \langle\mathbf{s}_L,\mathbf{G}\rangle+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B

El probador compromete el producto interno en $V$ con respecto a un $G$ de logaritmo discreto desconocido (no relacionado con $\mathbf{G}$ ):

V = vG+\gamma B

El probador envía $(A, S, V)$ al verificador.

El verificador responde con valores aleatorios $(y, z)$ que el probador utilizará para combinar los tres productos internos en uno solo.

\left\langle \mathbf{a_L} - z \cdot \mathbf{1}^n, \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n \right\rangle = z^2 \cdot v + \delta(y,z)

La parte izquierda del producto interno $\mathbf{a}_L-z\cdot\mathbf{1}$ será el término constante de $\mathbf{l}(x)$ y $\mathbf{y}^n \circ\mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n$ será el término constante de $\mathbf{r}(x)$ .

Por lo tanto, construimos $\mathbf{l}(x)$ como

\mathbf{l}(x)=\underbrace{\mathbf{a}_L-z\cdot\mathbf{1}}_\text{término constante}+\mathbf{s}_Lx

y construimos $\mathbf{r}(x)$ como

\mathbf{r}(x)=\underbrace{\mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n}_\text{término constante}+\mathbf{y}^n\circ\mathbf{s}_Rx

Nota que multiplicamos elemento por elemento a $\mathbf{s}_Rx$ con $\mathbf{y}^n$ por las razones que discutimos en la parte 3 de la sección de prerrequisitos anterior.

El probador ahora puede construir $t(x) = \langle\mathbf{l}(x),\mathbf{r}(x)\rangle$ con coeficiente constante $t_0$ , coeficiente lineal $t_1$ y coeficiente cuadrático $t_2$ como:

\begin{align*} t_0 &= \left\langle \mathbf{a_L} - z \cdot \mathbf{1}^n, \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n \right\rangle\\ t_1 &= \langle(\mathbf{a}_L-z\cdot\mathbf{1}),\mathbf{y}^n\circ\mathbf{s}_R\rangle+\langle\mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n,\mathbf{s_L}\rangle\\ t_2 &= \langle\mathbf{s}_L,\mathbf{y}^n\circ\mathbf{s}_R\rangle \end{align*}

donde $t(x) = t_0 + t_1x + t_2x^2$

El probador envía los compromisos de $t_1$ y $t_2$ como

\begin{align*} T_1 &= t_1G+\tau_1B\\ T_2 &= t_2G+\tau_2B \end{align*}

No hay necesidad de comprometerse con $t_0$ ; observa que es exactamente el producto interno que estamos tratando de probar, por lo que el verificador ya tiene el compromiso como $V$ .

El verificador envía la aleatoriedad $u$ y el probador calcula

\begin{align*} \mathbf{l}_u &= \mathbf{l}(u) \\ \mathbf{r}_u &= \mathbf{r}(u) \\ t_u &= \mathbf{t}(u)\\ \pi_{lr} &=\alpha+\beta u\\ \pi_t &= z^2\gamma + \tau_1u + \tau_2u^2\\ \end{align*}

Nota que el término constante de $\pi_t$ se multiplica por $z^2$ para reflejar el término $z^2\cdot v$ del producto interno original.

Luego, el verificador calcula un nuevo vector base $\mathbf{H}_{\mathbf{y}^{-1}}=\mathbf{y}^{-n}\circ\mathbf{H}$ y ejecuta las siguientes comprobaciones:

$t_u \stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{r}_u \rangle$

$A + Su + \boxed{\langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle} + \boxed{\langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle}\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H}_{y^{-1}} \rangle + \pi_{lr} B$

$t_uG+\pi_tB=V\boxed{z^2}+\boxed{\delta(y,z)}\cdot G+T_1u+T_2u^2$

Recuerda que el probador no comprometió los vectores completos que usó para el lado izquierdo y derecho del producto interno, sino solo $\mathbf{a}_L$ y $\mathbf{b}_L$ . El resto de los vectores eran vectores públicos aditivos conocidos por el verificador, por lo que el verificador reconstruyó los compromisos con los vectores al construir compromisos para los términos constantes y sumándolos al compromiso de los vectores secretos suministrados por el probador.

A modo de recordatorio, aquí está el producto interno original con los valores conocidos por el verificador recuadrados:

\left\langle \mathbf{a_L} + \boxed{-z \cdot \mathbf{1}^n}, \mathbf{y}^n \circ \mathbf{a_R} + \boxed{\mathbf{y}^n\cdot z + z^2 \cdot 2^n }\right\rangle = \boxed{z^2} \cdot v + \boxed{\delta(y,z)}

Se anima al lector a verificar que los términos recuadrados (valores conocidos por el verificador) en el producto original fueron reconstruidos por el verificador en los términos recuadrados en el conjunto de comprobaciones de igualdad anteriores.

Al replicar una parte del cálculo del probador, el verificador asegura que el probador realmente llevó a cabo el cálculo tal como afirma.

Corrección del algoritmo de verificación

Ahora mostramos que las comprobaciones de verificación finales son idénticamente correctas si el probador fue honesto.

A continuación mostramos el álgebra exacta, pero intuitivamente el verificador está “reconstruyendo” el vector izquierdo en el producto interno $\mathbf{a_L} - z \cdot \mathbf{1}^n$ , el vector derecho en el producto interno $\mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n$ y la salida $z^2v+\delta(y,z)$ .

Al verificador no se le dan compromisos para $\mathbf{a_L} - z \cdot \mathbf{1}^n$ ni para $\mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n$ , sino para $\mathbf{a}_L$ y $\mathbf{a}_R$ . De manera similar, al verificador no se le da un compromiso para la salida $z^2v + \delta(y,z)$ , sino solo para $v$ .

Los términos aditivos y los términos multiplicados elemento por elemento con $\mathbf{y}^n$ deben ser reconstruidos por el verificador.

Corrección de $t_u = \mathbf{t}(u)$

Para la comprobación $t_u\stackrel{?} =\langle\mathbf{l}_u,\mathbf{r}_u\rangle$ , esto es verdadero por definición, ya que así es como el probador calculó $t_u$ .

Corrección de los comprometidos $\mathbf{l}(x)$ y $\mathbf{r}(x)$ con respecto a $A$ y $S$

Para
$A + Su + \langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H}_{y^{-1}} \rangle + \pi_{lr} B$

hacemos la siguiente sustitución:

$\underbrace{\langle\mathbf{a}_L,\mathbf{G}\rangle+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B}_A + \underbrace{(\langle\mathbf{s}_L,\mathbf{G}\rangle+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B)}_Su + \langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle\stackrel{?}{=} \langle \underbrace{\mathbf{a}_L-z\cdot\mathbf{1}+\mathbf{s}_Lu}_{\mathbf{l}_u}, \mathbf{G} \rangle + \langle \underbrace{\mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_Rx}_{\mathbf{r}_u}, \mathbf{H}_{y^{-1}} \rangle + \underbrace{(\alpha+\beta u)}_{\pi_{lr}} B$

Todos los términos $\mathbf{G}$ se cancelan de la siguiente manera:

$\cancel{\langle\mathbf{a}_L,\mathbf{G}\rangle}+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B + (\cancel{\langle\mathbf{s}_L,\mathbf{G}\rangle}+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B)u + \cancel{\langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle} + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \cancel{\langle \mathbf{a}_L-z\cdot\mathbf{1}+\mathbf{s}_L u, \mathbf{G} \rangle} + \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_R x, \mathbf{H}_{y^{-1}} \rangle + (\alpha+\beta u) B$

$\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B + (\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B)u + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_R x, \mathbf{H}_{y^{-1}} \rangle + (\alpha+\beta u) B$

Los términos de cegado relacionados con $B$ se cancelan de la siguiente manera:

$\langle\mathbf{a}_R,\mathbf{H}\rangle+\cancel{\alpha B} + (\langle\mathbf{s}_R,\mathbf{H}\rangle+\cancel{\beta B)u} + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_R x, \mathbf{H}_{y^{-1}} \rangle + \cancel{(\alpha+\beta u) B}$

$\langle\mathbf{a}_R,\mathbf{H}\rangle + (\langle\mathbf{s}_R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_R u, \mathbf{H}_{y^{-1}} \rangle$

El $\mathbf{H}_{y^{-1}}$ se cancela con los términos $\mathbf{y}^n$ :

$\langle\mathbf{a}_R,\mathbf{H}\rangle + (\langle\mathbf{s}_R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{a}_R+z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle\mathbf{s}_R u, \mathbf{H} \rangle$

Dividimos los productos internos:

$\langle\mathbf{a}_R,\mathbf{H}\rangle + (\langle\mathbf{s}_R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{a}_R,\mathbf{H}\rangle+\langle z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle\mathbf{s}_R u, \mathbf{H} \rangle$

Cancelamos los términos que aparecen a ambos lados de la ecuación:

\cancel{\langle\mathbf{a}_R,\mathbf{H}\rangle} + (\langle\mathbf{s}_R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \cancel{\langle \mathbf{a}_R,\mathbf{H}\rangle}+\langle z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle\mathbf{s}_R u, \mathbf{H} \rangle

\cancel{(\langle\mathbf{s}_R,\mathbf{H}\rangle u)} + \langle z\cdot\mathbf{y}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=}\langle z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\cancel{\langle\mathbf{s}_R u, \mathbf{H} \rangle}

\langle z\cdot\mathbf{y}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\cancel{\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle} \stackrel{?}{=}\langle z\cdot\mathbf{1},\mathbf{H}\rangle+\cancel{\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle}

\langle z\cdot\mathbf{y}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=}\langle z\cdot\mathbf{1},\mathbf{H}\rangle

Movemos $\mathbf{y}^n$ al otro lado:

\langle z\cdot\mathbf{1},\mathbf{H}\rangle \stackrel{?}{=}\langle z\cdot\mathbf{1},\mathbf{H}\rangle

\cancel{\langle z\cdot\mathbf{1},\mathbf{H}\rangle} \stackrel{?}{=}\cancel{\langle z\cdot\mathbf{1},\mathbf{H}\rangle}

Corrección de la evaluación de $t(u)$

Para ver que

t_uG+\pi_tB=Vz^2+\delta(y,z)G+T_1u+T_2u^2

es correcta, podríamos sustituir los términos de la siguiente manera:

\underbrace{\langle \mathbf{l}_u, \mathbf{r}_u \rangle}_{t_u}G+\underbrace{(z^2\gamma + \tau_1u + \tau_2u^2)}_{\pi_t}B=\underbrace{(vG+\gamma B)}_{V}z^2+\delta(y,z)G+\underbrace{(t_1G+\tau_1B}_{T_1})u+\underbrace{(t_2G+\tau_2B)}_{T_2}u^2

con $\mathbf{l}_u$ , $\mathbf{r}_u$ , $t_1$ , $t_2$ :

\begin{align*} \mathbf{l}_u &= \mathbf{a_L} - z \cdot \mathbf{1}^n\\ \mathbf{r}_u &= \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n\\ t_1 &= \langle(\mathbf{a}_L-z\cdot\mathbf{1}),\mathbf{y}^n\circ\mathbf{s}_R\rangle+\langle\mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n,\mathbf{s_L}\rangle\\ t_2 &= \langle\mathbf{s}_L,\mathbf{y}^n\circ\mathbf{s}_R\rangle \end{align*}

Sin embargo, tal álgebra sería extremadamente desordenada. En su lugar, observamos que $z^2v+\delta(y,z)G$ es el término constante del producto interno del polinomio vectorial de $\langle\mathbf{l}(x),\mathbf{r}(x)\rangle$ . Para cancelar el término de cegado $\gamma B$ en $V$ , observa que $\pi_t$ contiene $z^2\gamma$ , por lo que esto se cancelará con el término gamma en $Vz^2 = (vG + \gamma B)z^2$ .

Dado que los compromisos de Pedersen son aditivamente homomórficos, el verificador simplemente puede calcular y sumar $\delta(y,z)G$ a $Vz^2$ para calcular el compromiso al término constante del polinomio $t(x)$ .

Prueba de rango de tamaño logarítmico

Podemos reducir el tamaño de la transmisión de datos enviando un compromiso $C$ a $\mathbf{l}_u$ y $\mathbf{r}_u$ y demostrando que los vectores comprometidos tienen un producto interno $t_u$ usando la prueba de tamaño logarítmico, y luego verificando que

A + Su + \langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle-\pi_{lr}B\stackrel{?}{=} C

t_u \stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{r}_u \rangle

con respecto a los vectores base $\mathbf{G}$ y $\mathbf{H}_{\mathbf{y}^{-1}}$ .

Uso del algoritmo de la prueba de rango para la suma de subconjuntos

El problema de la suma de subconjuntos pregunta, "dado un conjunto de números, ¿un subconjunto (posiblemente incluyendo todo el conjunto) suma $k$ ? Por ejemplo, si $k = 16$ y el conjunto es $\set{3,5,7,11}$ la respuesta es sí porque $5 + 11 = 16$ . Sin embargo, si $k=13$ , entonces la respuesta es no.

El problema de la suma de subconjuntos es NP-Complete, lo que significa que, de manera similar a un circuito booleano o circuito aritmético, puede representar cualquier problema en NP. Es decir, cualquier problema en NP puede reescribirse (la palabra técnica es “reducirse”) a una instancia de suma de subconjuntos.

Al reemplazar $\mathbf{2}^n$ por $[3,5,7,11]$ , podemos demostrar que conocemos una solución a una suma de subconjuntos sin revelar la respuesta. Específicamente, el probador sabría que $\mathbf{a}_L= [0,1,0,1]$ si $k=16$ . En general, una entrada de uno en $\mathbf{a}_L$ significa que incluimos ese elemento en el subconjunto y un cero significa que no está incluido en el subconjunto.

Por lo tanto, Bulletproofs son capaces de demostrar el conocimiento de cualquier testigo para cualquier problema en NP.

Apéndice: Derivación de la combinación de tres productos internos en uno

Comenzando con los tres productos internos

z^2 \cdot \langle \mathbf{a_L}, \mathbf{2}^n \rangle + z \cdot \langle \mathbf{a_L} - \mathbf{1}^n - \mathbf{a_R}, \mathbf{y}^n \rangle + \langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = z^2 \cdot v

mostramos cómo derivar el resultado final

\langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v+(z-z^2)\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^3\langle\cdot\mathbf{1}^n,\mathbf{2}^n\rangle

usando el álgebra de producto interno que aprendimos anteriormente.

El término central se puede dividir en productos internos separados:

z^2 \cdot \langle \mathbf{a_L}, \mathbf{2}^n \rangle + \boxed{z \cdot \langle \mathbf{a_L} - \mathbf{1}^n - \mathbf{a_R}, \mathbf{y}^n \rangle} + \langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = z^2 \cdot v

z^2 \cdot \langle \mathbf{a_L}, \mathbf{2}^n \rangle+\boxed{z\cdot\langle\mathbf{a}_L,\mathbf{y}^n\rangle+z\cdot\langle-\mathbf{1}^n,\mathbf{y}^n\rangle+z\cdot\langle-\mathbf{a}_R,\mathbf{y}^n\rangle}+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle=z^2\cdot v

Podemos mover los términos constantes $z$ dentro de los productos internos:

$\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle+\langle-\mathbf{a}_R,z\cdot\mathbf{y}^n\rangle+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v$
Movemos los valores conocidos por el verificador a la derecha:

$\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\boxed{\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle}+\langle-\mathbf{a}_R,z\cdot\mathbf{y}^n\rangle+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v$

\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\langle-\mathbf{a}_R,z\cdot\mathbf{y}^n\rangle+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v-\boxed{\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle}

Convertimos los términos $\mathbf{a}_R$ para que ambos sean $\mathbf{a}_R\circ\mathbf{y}^n$ :

\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\boxed{\langle-\mathbf{a}_R\circ\mathbf{y}^n,z\cdot\mathbf{1}^n\rangle}+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\boxed{\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle}+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+{\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle}+\boxed{\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle}= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle+\langle \mathbf{a_R} \circ \mathbf{y}^n,\mathbf{a_L} \rangle = z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

Combinamos los términos $\mathbf{a}_R\circ\mathbf{y}^n$ en uno:

\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\underbrace{\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle+\langle \mathbf{a_R} \circ \mathbf{y}^n,\mathbf{a_L} \rangle} = z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

\langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

Combinamos los dos términos $\mathbf{a}_L$ a la izquierda:

\langle \boxed{\mathbf{a_L}}, z^2\cdot\mathbf{2}^n \rangle+\langle\boxed{\mathbf{a}_L},z\cdot\mathbf{y}^n\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

\langle \mathbf{a_L}, z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

Dividimos el último término del lado izquierdo en dos productos internos:

$\langle \mathbf{a_L}, z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\boxed{\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L-z\cdot\mathbf{1}^n\rangle}= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle$

\langle \mathbf{a_L}, z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

Combinamos los términos $\mathbf{a}_L$ :

$\langle \boxed{\mathbf{a_L}}, z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n, \boxed{\mathbf{a}_L}\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle$

\langle \mathbf{a_L}, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle

Podemos usar la regla $\langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{b}, \mathbf{y}\rangle = v \rightarrow \langle \mathbf{x} + \mathbf{y}, \mathbf{b} + \mathbf{c}\rangle = v + \langle\mathbf{y},\mathbf{c}\rangle$ para combinar los términos que contienen $\mathbf{a}_R\circ\mathbf{y}^n$ . Aquí $\mathbf{b}$ es $\mathbf{a}_R\circ\mathbf{y}^n$ , $\mathbf{c}$ es $z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n$ , y $\mathbf{y}$ es $-z\cdot\mathbf{1}^n$ .

\langle \underbrace{\mathbf{a_L}}_\mathbf{x}, \underbrace{\mathbf{a}_R\circ\mathbf{y}^n}_\mathbf{b}+\underbrace{z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n}_\mathbf{c} \rangle+\langle\underbrace{\mathbf{a}_R\circ\mathbf{y}^n}_\mathbf{b},\underbrace{-z\cdot\mathbf{1}^n}_\mathbf{y}\rangle= \underbrace{z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle}_v

\langle \underbrace{\mathbf{a_L}}_\mathbf{x}-\underbrace{z\cdot\mathbf{1}^n}_\mathbf{y}, \underbrace{\mathbf{a}_R\circ\mathbf{y}^n}_\mathbf{b}+\underbrace{z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n}_\mathbf{c} \rangle= \underbrace{z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle}_v+\langle\underbrace{-z\cdot\mathbf{1}^n}_\mathbf{y},\underbrace{z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n}_\mathbf{c}\rangle

\langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle+\langle-z\cdot\mathbf{1}^n,z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n\rangle

Ahora descomponemos los términos del lado derecho:

\langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle+\langle-z\cdot\mathbf{1}^n,z\cdot\mathbf{y}^n\rangle+\langle-z\cdot\mathbf{1}^n,z^2\cdot\mathbf{2}^n\rangle

Sacamos los escalares de los productos internos de la derecha:

\langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v+z\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^2\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^3\langle\cdot\mathbf{1}^n,\mathbf{2}^n\rangle

Factorizamos $\langle\mathbf{1}^n,\mathbf{y}^n\rangle$ :

\langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v+(z-z^2)\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^3\langle\cdot\mathbf{1}^n,\mathbf{2}^n\rangle

Dado que $\delta(y,z)=(z-z^2)\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^3\langle\cdot\mathbf{1}^n,\mathbf{2}^n\rangle$ , tenemos:

\langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v+\delta(y,z)

Esto completa la derivación. $\blacksquare$

Prueba de rango

Notación

Descripción general de la prueba de rango

Cuatro trucos útiles

1. Demostrar que aL\mathbf{a}_LaL​ es binario

2. Demostrar que un vector es todo ceros

3. Demostrar que un producto interno tiene la forma ⟨aL,aR∘yn⟩\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle⟨aL​,aR​∘yn⟩ donde el verificador elige yyy y el probador calcula yn\mathbf{y}^nyn

4. Demostrar un producto interno cuando interviene una constante pública aditiva

Prueba de rango

Combinar tres productos internos en uno

Algoritmo de prueba de rango

Corrección del algoritmo de verificación

Corrección de tu=t(u)t_u = \mathbf{t}(u)tu​=t(u)

Corrección de los comprometidos l(x)\mathbf{l}(x)l(x) y r(x)\mathbf{r}(x)r(x) con respecto a AAA y SSS

Corrección de la evaluación de t(u)t(u)t(u)

Prueba de rango de tamaño logarítmico

Uso del algoritmo de la prueba de rango para la suma de subconjuntos

Apéndice: Derivación de la combinación de tres productos internos en uno

1. Demostrar que $\mathbf{a}_L$ es binario

3. Demostrar que un producto interno tiene la forma $\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle$ donde el verificador elige $y$ y el probador calcula $\mathbf{y}^n$

Corrección de $t_u = \mathbf{t}(u)$

Corrección de los comprometidos $\mathbf{l}(x)$ y $\mathbf{r}(x)$ con respecto a $A$ y $S$

Corrección de la evaluación de $t(u)$