Los Bulletproofs ZKP permiten a un probador demostrar el conocimiento de un producto interno con una prueba de tamaño logarítmico. Los Bulletproofs no requieren una configuración de confianza (trusted setup).

En los capítulos anteriores, mostramos cómo demostrar el conocimiento de un producto interno sin revelar los vectores ni el producto interno, aunque con una prueba de tamaño $\mathcal{O}(n)$ donde $n$ es la longitud del vector. También mostramos cómo demostrar el conocimiento de un producto interno utilizando datos de tamaño logarítmico, pero sin la propiedad de conocimiento cero.

En este capítulo, combinamos los algoritmos para demostrar el algoritmo ZK de Bulletproofs.

(Este trabajo es parte de una serie sobre ZK Bulletproofs).

Planteamiento del Problema

El probador y el verificador acuerdan dos vectores base de curva elíptica $\mathbf{G}$ y $\mathbf{H}$ de longitud $n$ y los puntos de curva elíptica $Q$ y $B$. Las relaciones de logaritmo discreto entre todos estos puntos son desconocidas.

El probador tiene los vectores $\mathbf{a}$ y $\mathbf{b}$ con un producto interno $v$. El probador compromete $\mathbf{a}$ y $\mathbf{b}$ en $A$ como $A =\langle\mathbf{a},\mathbf{G}\rangle + \langle\mathbf{b},\mathbf{H}\rangle + \alpha B$ donde $\alpha$ es un término de ocultamiento (blinding term). El probador compromete $V = \langle\mathbf{a},\mathbf{b}\rangle Q + \gamma B$.

El probador envía $(A, V)$ al verificador y tiene como objetivo demostrar que $\mathbf{a}$ y $\mathbf{b}$ están comprometidos en $A$ y que su producto interno está comprometido en $V$. El verificador no descubre los vectores ni el producto interno.

El tamaño de la prueba debe ser $\mathcal{O}(\log n)$.

El Algoritmo ZK de Bulletproofs

El probador genera escalares aleatorios $\set{\alpha, \beta,\gamma,\tau_1,\tau_2}$ y vectores aleatorios $\set{\mathbf{s}_L,\mathbf{s}_R}$ y calcula los compromisos:

El probador prepara (pero no envía) polinomios de vectores:

$A$ es un compromiso a los términos constantes del polinomio de vectores, $S$ es un compromiso a los términos lineales y $V$ es un compromiso al producto interno.

El probador crea compromisos a los coeficientes de $t(x)$ de la siguiente manera:

Tenga en cuenta que $V$ es un compromiso al coeficiente constante de $t(x)$, y $T_1$ y $T_2$ son compromisos a los coeficientes lineal y cuadrático de $t(x)$, respectivamente.

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

El verificador responde con un valor aleatorio $u$.

Luego, el probador evalúa los polinomios en $u$ y crea pruebas de que fueron evaluados correctamente:

Anteriormente, el probador transmitía $(\mathbf{l}_u, \mathbf{r}_u, t_u, \pi_{lr}, \pi_t)$ para que el verificador pudiera comprobar que:

pero esto tendría un tamaño lineal debido a los vectores $\mathbf{l}_u$ y $\mathbf{r}_u$. En su lugar, el probador compromete $\mathbf{l}_u$ y $\mathbf{r}_u$ como:

y envía $(C, t_u, \pi_{lr}, \pi_t)$.

Podemos reorganizar las dos primeras comprobaciones del verificador de la siguiente manera:

Observe que si establecemos $P = A + Su -\pi_{lr}B$, entonces este es el mismo planteamiento del problema que demostrar que $P$ contiene compromisos a dos vectores $\mathbf{l}_u$ y $\mathbf{r}_u$ con respecto a los vectores base $\mathbf{G}$ y $\mathbf{H}$, y que $\mathbf{l}_u$ y $\mathbf{r}_u$ tienen un producto interno de $t_u$. Por lo tanto, podemos reutilizar la prueba de tamaño logarítmico de conocimiento de la apertura de un compromiso a $P$.

Para esta prueba, no necesitamos la confidencialidad porque $\mathbf{l}_u$ y $\mathbf{r}_u$ ya se hicieron públicos de todos modos en el algoritmo anterior.

Ahora que el verificador tiene todos los datos necesarios, el probador participa en una prueba interactiva para demostrar que $C$ contiene los compromisos a $\mathbf{l}_u$ y $\mathbf{r}_u$ y que su producto interno es $t_u$:

Esa subrutina demostrará que $t_u\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle$ y $C\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H} \rangle$ sin tener que enviar $\mathbf{l}_u$ y $\mathbf{r}_u$. Además, solo envía datos de tamaño logarítmico. Tenga en cuenta que el algoritmo recursivo del capítulo anterior utiliza un compromiso $P = \langle \mathbf{a}, \mathbf{G} \rangle + \langle \mathbf{b}, \mathbf{H} \rangle + \langle\mathbf{a},\mathbf{b}\rangle Q$, por lo que el verificador necesita añadir la “porción $Q$” por sí mismo. Ahora el verificador puede estar seguro de que:

Finalmente, el verificador comprueba que:

Recuerde que $A$ y $S$ son compromisos a los términos constantes y lineales de los polinomios de vectores $\mathbf{l}(x)$ y $\mathbf{r}(x)$, respectivamente. La primera comprobación asegura que los vectores comprometidos en $C$ son evaluaciones de esos polinomios en $u$.

La segunda comprobación es para asegurar que $t(u)$ se evaluó correctamente, dados los compromisos de los coeficientes $V$, $T_1$ y $T_2$.

No interactividad mediante la Transformada de Fiat Shamir

En la práctica, este algoritmo se hace no interactivo a través de la Transformada de Fiat Shamir. En lugar de pedirle aleatoriedad al verificador, el probador genera aleatoriedad concatenando todos los datos que ha transmitido hasta el momento y calculando su hash. Luego, el verificador vuelve a calcular el hash de los datos para asegurarse de que el probador generó la aleatoriedad correctamente.

Es fundamental que el hash incluya todas las transmisiones de datos anteriores, de lo contrario la implementación tendrá una vulnerabilidad de corazón congelado (frozen heart vulnerability).

Próximos pasos

En la práctica, los problemas de interés práctico constan de múltiples productos internos. Por ejemplo, un Sistema de Restricciones de Rango 1 (Rank 1 Constraint System):

son en realidad $3n$ productos internos (por ejemplo, multiplicando $\mathbf{a}$ por las $n$ filas de $L$ y así sucesivamente para $R$ y $O$) y un único producto de Hadamard. Por lo tanto, será útil conocer algunos trucos matemáticos para combinar múltiples productos internos en uno solo, de modo que no tengamos que enviar $3n$ pruebas de Bulletproofs. Aprenderemos cómo lograr esto en nuestro próximo capítulo sobre combinaciones lineales aleatorias.

Además, algunos problemas útiles pueden codificarse directamente como un producto interno, notablemente la prueba de rango o el problema de suma de subconjuntos. En esas situaciones, podemos omitir la codificación del problema como un circuito aritmético y codificarlo directamente como un producto interno. Para aumentar la flexibilidad de nuestra representación de productos internos, así como para sentar las bases para entender las combinaciones lineales aleatorias, aprenderemos algo de álgebra de productos internos en el próximo capítulo.

Ejercicio: Combine los ejercicios anteriores para demostrar que $A =\langle\mathbf{a},\mathbf{G}\rangle + \langle\mathbf{b},\mathbf{H}\rangle + \alpha B$ donde $\mathbf{a}$ y $\mathbf{b}$ son vectores de longitud 4. Su prueba debe ser tanto sucinta como de conocimiento cero. Cree una prueba interactiva en aras de la simplicidad. Consulte este repositorio para los ejercicios.