En un capítulo anterior, mostramos que multiplicar las sumas de los elementos de los vectores $\mathbf{a}$ y $\mathbf{G}$ calcula la suma de los términos del producto exterior, es decir, $\sum \mathbf{a}\otimes\mathbf{G}=\sum\mathbf{a}\sum\mathbf{G}$. También mostramos que el producto exterior “contiene” el producto interior a lo largo de su diagonal principal.

Para “extraer” el producto interior $\langle\mathbf{a},\mathbf{G}\rangle$, se deben restar del producto exterior todos los términos que no forman parte del producto interior, es decir, la región sombreada en color púrpura a continuación:

Hay $\mathcal{O}(n^2)$ de estos términos, por lo que hacer esto directamente no es eficiente.

Sin embargo, observe que podemos “llenar el producto exterior” de la manera que se muestra en la siguiente animación:

En la animación anterior, después de que el probador envía los términos fuera de la diagonal, el probador pliega tanto $\mathbf{G}$ como $\mathbf{a}$, reduciendo su longitud a la mitad.

Al final, después de haber plegado $\mathbf{a}$ y $\mathbf{G}$ $\log n$ veces, el tamaño de los vectores es 1. Cuando $n=1$, el producto exterior es igual al producto interior y simplemente revelamos ambos vectores, que serán de tamaño constante.

Resumen – y cómo se relaciona esto con el algoritmo del capítulo anterior

Anteriormente, mostramos cómo probar que conocemos la apertura de un compromiso $P$ enviando $n/2$ elementos en lugar de $n$. A modo de resumen:

El probador compromete el vector $\mathbf{a}$ en $P$ como $P = \langle\mathbf{a},\mathbf{G}\rangle$. Luego, el probador envía los términos fuera de la diagonal $L=a_1G_2 + a_3G_4 + \dots a_{n-1}G_n$ y $R = a_2G_1 + a_4G_3 + \dots a_nG_{n-1}$. El verificador responde con $u$ y el probador pliega el vector $\mathbf{a}$ sobre $u$ como $\mathbf{a}'=\mathsf{fold}(\mathbf{a},u)=[a_1u+a_2u^{-1}, a_3u+a_4u^{-1}, \dots, a_{n-1}u+a_nu^{-1}]$ y envía $\mathbf{a}'$ al verificador. Dado que $\mathbf{a}'$ tiene una longitud de $n/2$, hemos reducido a la mitad el tamaño de los datos que se transmitirán.

El verificador luego comprueba que $\langle\mathsf{fold}(\mathbf{G},u^{-1}),\mathbf{a}'\rangle\stackrel{?}=Lu^2+P+Ru^{-2}$

La intención original de este algoritmo era probar que conocemos el compromiso en $P$ demostrando que sabemos que la suma del producto interior $P$ y los términos fuera de la diagonal $L$ y $R$ es igual a la suma de los elementos de los productos exteriores de las particiones por pares de $\mathbf{a}$ y $\mathbf{G}$.

Si aplicamos recursivamente este algoritmo, obtenemos el algoritmo $\log n$ descrito al principio de este capítulo.

Sin embargo, también podríamos interpretar este procedimiento como una prueba de que conocemos la apertura del compromiso $P'$ donde $P'=(Lu^2+P+Ru^{-2})$ con respecto al vector base $\mathsf{fold}(\mathbf{G},u^{-1})$ de longitud $n'=n/2$. Podríamos probar de manera ingenua que conocemos la apertura de $P'$ enviando $\mathbf{a}'$ y con el verificador comprobando que $P'\stackrel{?}=\langle\mathbf{a'},\mathsf{fold}(\mathbf{G},u^{-1})\rangle$.

Pero en lugar de probar que conocemos la apertura de $P'$ enviando $\mathbf{a}'$, podemos aplicar recursivamente el algoritmo para probar que conocemos la apertura de $P'$ enviando un vector $\mathbf{a}{\prime\prime}$ de tamaño $n/4$. De hecho, podemos seguir iterando recursivamente hasta que $a^{\prime\dots\prime}$ sea de tamaño $n=1$.

La siguiente animación proporciona una intuición de lo que está sucediendo. La próxima sección describe la animación en detalle.

Para que este algoritmo funcione, la longitud de los vectores debe ser una potencia de dos. Sin embargo, si la longitud no es una potencia de dos, podemos rellenar los vectores con ceros hasta que la longitud sea una potencia de dos.

Probando que conocemos la apertura de $P$ con $\mathcal{O}(\log n)$ de datos

El algoritmo

El probador y el verificador acuerdan un vector base $\mathbf{G}$ de longitud $n$. El probador envía al verificador $P$, que es $\langle\mathbf{a},\mathbf{G}\rangle$. El probador desea convencer al verificador de que conoce la apertura de $P$ enviando únicamente datos de tamaño logarítmico.

El probador y el verificador luego participan en el siguiente algoritmo a continuación. Los argumentos después de | significan que solo son conocidos por el probador.

En la descripción del algoritmo a continuación, $n$ es la longitud de los vectores en la entrada, los cuales tienen todos la misma longitud.

$\texttt{prove\_commitments\_log}(P, \mathbf{G}, | \mathbf{a})$

Caso 1: $n = 1$

1. El probador envía $a$ y el verificador comprueba que $aG \stackrel{?}= P$ y el algoritmo termina.

Caso 2: $n > 1$

1. El probador calcula y envía al verificador $(L, R)$ donde
   
   $$\begin{align*} L &= a_1G_2 + a_3G_4 + \dots a_{n-1}G_n\\ R &= a_2G_1 + a_4G_3 + \dots a_nG_{n-1} \end{align*}$$
2. El verificador envía la aleatoriedad $u$
3. Tanto el probador como el verificador calculan:
   
   $$\begin{align*} \mathbf{G}'&=\mathsf{fold}(\mathbf{G},u^{-1})\\ P' &= Lu^2+P+Ru^{-2} \end{align*}$$
4. El probador calcula
   
   $$\mathbf{a}'=\mathsf{fold}(\mathbf{a},u)$$
5. $\texttt{prove\_commitments\_log}(P', \mathbf{G}', \mathbf{a}')$

Comentarios sobre el algoritmo

El probador está probando de forma recursiva que, dados los valores $P$ y $\mathbf{G}$, conoce el $\mathbf{a}$ tal que $P=\langle\mathbf{a},\mathbf{G}\rangle$. Ambas partes pliegan recursivamente $\mathbf{G}$ hasta que es un solo punto, y el probador pliega recursivamente $\mathbf{a}$ hasta que es un solo punto.

El probador transmite una cantidad constante de datos en cada iteración, y la recursión se ejecutará como máximo $\log n$ veces, por lo que el probador envía $\mathcal{O}(\log n)$ de datos.

Enfatizamos que este algoritmo no es de conocimiento cero porque en el caso $n=1$, el verificador aprende todo el vector. El verificador también podría enviar valores no aleatorios para $u$ para intentar aprender algo sobre $\mathbf{a}$.

Sin embargo, recuerde que nuestra motivación para este algoritmo es reducir el tamaño de la comprobación $t_u=\langle\mathbf{l}_u,\mathbf{r}_u\rangle$, y $\mathbf{l}_u$ y $\mathbf{r}_u$ no eran secretos desde el principio.

De hecho, no hemos mostrado cómo probar que conocemos el producto interior con datos de tamaño logarítmico, solo hemos mostrado que conocemos la apertura de un compromiso con datos de tamaño logarítmico. Sin embargo, es sencillo actualizar nuestro algoritmo para mostrar que conocemos el producto interior de dos vectores, como haremos más adelante en este artículo.

Tiempo de ejecución

El verificador lleva a cabo el cálculo $\mathbf{G}' = \mathsf{fold}(\mathbf{G}, u^{-1})$ $\log n$ veces, y el primer $\mathsf{fold}$ toma un tiempo de $\mathcal{O}(n)$. A primera vista, parece que el tiempo de ejecución del verificador es $\mathcal{O}(n \log n)$. Sin embargo, note que con cada iteración, $n$ se divide a la mitad, resultando en un tiempo de ejecución de $n + \frac{n}{2} + \frac{n}{4} + ... + 1 = 2n$, lo que lleva a un tiempo de ejecución general para el verificador de $\mathcal{O}(n)$.

Probando que conocemos el producto interior $\langle\mathbf{a},\mathbf{b}\rangle=v$

Ahora ajustamos el algoritmo anterior para probar que realizamos el producto interior entre dos vectores escalares, en lugar de un vector de elementos del campo y un vector de puntos de curva elíptica.

Específicamente, debemos probar que $P$ contiene un compromiso del producto interior $\langle\mathbf{a},\mathbf{b}\rangle$. Este producto interior es un escalar, por lo que hacemos un compromiso de Pedersen normal en lugar de un compromiso de vector. Para esto utilizamos un punto aleatorio de curva elíptica (con logaritmo discreto desconocido) $Q$. Por lo tanto, $P = \langle\mathbf{a},\mathbf{b}\rangle Q$.

Sin embargo, no podemos simplemente reutilizar nuestro algoritmo anterior porque el probador puede proporcionar múltiples aperturas para $P$. Por ejemplo, si $\mathbf{a} = [1,2]$ y $\mathbf{b} = [3,4]$, el probador también puede abrir con los vectores $\mathbf{a}' = [3,2]$ y $\mathbf{b}' = [1, 4]$.

Para crear una prueba segura de conocimiento de un producto interior, el probador también debe calcular y enviar un compromiso para $\mathbf{a}$ y $\mathbf{b}$.

La solución ingenua es ejecutar el algoritmo de compromiso dos veces. Las dos primeras veces son para probar que $\mathbf{a}$ y $\mathbf{b}$ están comprometidos correctamente en $P_1 = \langle\mathbf{a},\mathbf{G}\rangle$ y $P_2 =\langle\mathbf{b},\mathbf{H}\rangle$ y la tercera vez es para mostrar que $\langle\mathbf{a},\mathbf{b}\rangle Q=P_3$ se calculó correctamente. En la siguiente sección, mostramos cómo modificar nuestro algoritmo para calcular el producto interior cuando ambos vectores son elementos del campo.

Convirtiendo un producto interior escalar a un producto interior escalar-punto

Sea $\mathbf{Q}^n$ el vector que consiste en $n$ copias del punto $Q$, es decir,

Por lo tanto,

Note que $\langle\mathbf{a},\mathbf{b}\rangle Q$ es igual a $\langle\mathbf{a},\mathbf{b}\circ\mathbf{Q}^n\rangle$.

Es decir, podemos multiplicar cada entrada de $\mathbf{b}$ por $Q$ y tomar el producto interior de ese vector con $\mathbf{a}$ y el resultado será el mismo que $\langle\mathbf{a},\mathbf{b}\rangle Q$. Por ejemplo, si $\mathbf{a} = [1,2]$ y $\mathbf{b} = [3,4]$, entonces $\langle[1,2],[3,4]\rangle Q=(1\cdot 3+2\cdot 4)Q= \langle[1,2],[3Q,4Q]\rangle=1\cdot 3Q+2\cdot 4Q=11Q$.

A partir de ahí, podríamos probar lo siguiente:

1. $P_1 =\langle\mathbf{a},\mathbf{G}\rangle$
2. $P_2 =\langle\mathbf{b},\mathbf{H}\rangle$
3. $P_3 =\langle\mathbf{a},\mathbf{b}\circ\mathbf{Q}\rangle$

Una prueba en lugar de tres

Podemos hacerlo mejor que enviar tres compromisos y ejecutar el algoritmo tres veces.

Debido a que los puntos en $\mathbf{G}$, $\mathbf{H}$ y $Q$ tienen una relación de logaritmo discreto desconocida, pueden combinarse como un único compromiso $P = \langle\mathbf{a},\mathbf{G}\rangle +\langle\mathbf{b},\mathbf{H}\rangle + \langle\mathbf{a},\mathbf{b}\rangle Q = P_1 + P_2 + P_3$.

Reorganizaremos ligeramente el compromiso $P = \langle\mathbf{a},\mathbf{G}\rangle +\langle\mathbf{b},\mathbf{H}\rangle + \langle\mathbf{a},\mathbf{b}\rangle Q$ como $P = \langle\mathbf{a},\mathbf{G}\rangle+\langle\mathbf{a},\mathbf{b}\circ\mathbf{Q}^n\rangle +\langle\mathbf{b},\mathbf{H}\rangle$ para que el siguiente truco sea más evidente.

Para probar todo este compromiso a la vez, en lugar de tres productos interiores, observe que

donde $\oplus$ significa concatenación de vectores.

Efectivamente, estamos probando que comprometimos el vector $\mathbf{a}\oplus\mathbf{a}\oplus\mathbf{b}$ en la base vectorial de curva elíptica $\mathbf{G}\oplus\mathbf{Q}^n\oplus\mathbf{H}$.

En la práctica, no concatenamos realmente los vectores porque la longitud total generalmente no sería una potencia de dos. Más bien, calculamos los componentes $\mathbf{G}$, $\mathbf{H}$ y $\mathbf{b}\circ\mathbf{Q}^n$ por separado, pero calculamos $L$ y $R$ como si estuvieran concatenados.

Mostramos el algoritmo en la siguiente animación:

El algoritmo

Dado $v = \langle\mathbf{a},\mathbf{b}\rangle$ y el compromiso $P = vQ+\langle\mathbf{a},\mathbf{G}\rangle + \langle\mathbf{b},\mathbf{H}\rangle$ deseamos probar que $P$ está comprometido como se afirma. Es decir, $v$, $\mathbf{a}$ y $\mathbf{b}$ están comprometidos en $P$ y $\langle\mathbf{a},\mathbf{b}\rangle=v$.

$\texttt{prove\_commitments\_log}(P, \mathbf{G}, \mathbf{H},Q, |\mathbf{a}, \mathbf{b})$

Caso 1: $n = 1$

1. El probador envía $(a,b)$ y el verificador comprueba que $P \stackrel{?}= aG + bH + abQ$. El algoritmo termina.

Caso 2: $n > 1$

1. El probador calcula y envía al verificador $(L, R)$ que son simplemente los términos fuera de la diagonal de todos los vectores concatenados juntos (vea la animación de arriba):
   
   $$\begin{align*} L &= (a_1b_2 + a_3b_4 + \dots a_{n-1}b_n)Q+(a_1G_2 + a_3G_4 + \dots a_{n-1}G_n)+(b_2H_1 + b_4H_3 + \dots b_nH_{n-1})\\ R &= (a_2b_1 + a_4b_3 + \dots a_nb_{n-1})Q+(a_2G_1 + a_4G_3 + \dots a_nG_{n-1})+(b_1H_2 + b_3H_4 + \dots b_{n-1}H_n) \end{align*}$$
2. El verificador envía la aleatoriedad $u$.
3. Tanto el probador como el verificador calculan:
   
   $$\begin{align*} P' &= Lu^2+P+Ru^{-2}\\ \mathbf{G}'&=\mathsf{fold}(\mathbf{G}, u^{-1})\\ \mathbf{H}'&=\mathsf{fold}(\mathbf{H}, u)\\\\ \end{align*}$$
4. El probador calcula:
   
   $$\begin{align*} \mathbf{a}'&=\mathsf{fold}(\mathbf{a},u)\\ \mathbf{b}'&=\mathsf{fold}(\mathbf{b},u^{-1}) \end{align*}$$
5. $\texttt{prove\_commitments\_log}(P', G', H', \mathbf{a}', \mathbf{b}')$

Los siguientes ejercicios se pueden encontrar en nuestro ZK Bulletproofs GitHub Repo:

Ejercicio 1: Complete el código que falta a continuación para implementar el algoritmo para probar que $\mathbf{a}$ está comprometido en $\mathbf{G}$ para producir el punto $P$:

Copy
from py_ecc.bn128 import G1, multiply, add, FQ, eq, Z1
from py_ecc.bn128 import curve_order as p
import numpy as np
from functools import reduce
import random

def random_element():
    return random.randint(0, p)

def add_points(*points):
    return reduce(add, points, Z1)

# if points = G1, G2, G3, G4 and scalars = a,b,c,d vector_commit returns
# aG1 + bG2 + cG3 + dG4
def vector_commit(points, scalars):
    return reduce(add, [multiply(P, i) for P, i in zip(points, scalars)], Z1)

# these EC points have unknown discrete logs:
G_vec = [(FQ(6286155310766333871795042970372566906087502116590250812133967451320632869759), FQ(2167390362195738854837661032213065766665495464946848931705307210578191331138)),
     (FQ(6981010364086016896956769942642952706715308592529989685498391604818592148727), FQ(8391728260743032188974275148610213338920590040698592463908691408719331517047)),
     (FQ(15884001095869889564203381122824453959747209506336645297496580404216889561240), FQ(14397810633193722880623034635043699457129665948506123809325193598213289127838)),
     (FQ(6756792584920245352684519836070422133746350830019496743562729072905353421352), FQ(3439606165356845334365677247963536173939840949797525638557303009070611741415))]

# return a folded vector of length n/2 for scalars
def fold(scalar_vec, u):
    pass

# return a folded vector of length n/2 for points
def fold_points(point_vec, u):
    pass

# return (L, R)
def compute_secondary_diagonal(G_vec, a):
    pass

a = [4,2,42,420]

P = vector_commit(G_vec, a)

L1, R1 = compute_secondary_diagonal(G_vec, a)
u1 = random_element()
aprime = fold(a, u1)
Gprime = fold_points(G_vec, pow(u1, -1, p))

L2, R2 = compute_secondary_diagonal(Gprime, aprime)
u2 = random_element()
aprimeprime = fold(aprime, u2)
Gprimeprime = fold_points(Gprime, pow(u2, -1, p))

assert len(Gprimeprime) == 1 and len(aprimeprime) == 1, "final vector must be len 1"
assert eq(vector_commit(Gprimeprime, aprimeprime), add_points(multiply(L2, pow(u2, 2, p)), multiply(L1, pow(u1, 2, p)), P, multiply(R1, pow(u1, -2, p)), multiply(R2, pow(u2, -2, p)))), "invalid proof"

Ejercicio 2: Modifique el código anterior para implementar el algoritmo que prueba que $P$ contiene un compromiso para $\mathbf{a}$, $\mathbf{b}$ y $v$, y que $\langle\mathbf{a},\mathbf{b}\rangle=v$. Utilice el siguiente vector base para $\mathbf{H}$ y el punto de curva elíptica $Q$:

Copy
H = [(FQ(13728162449721098615672844430261112538072166300311022796820929618959450231493), FQ(12153831869428634344429877091952509453770659237731690203490954547715195222919)),
    (FQ(17471368056527239558513938898018115153923978020864896155502359766132274520000), FQ(4119036649831316606545646423655922855925839689145200049841234351186746829602)),
    (FQ(8730867317615040501447514540731627986093652356953339319572790273814347116534), FQ(14893717982647482203420298569283769907955720318948910457352917488298566832491)),
    (FQ(419294495583131907906527833396935901898733653748716080944177732964425683442), FQ(14467906227467164575975695599962977164932514254303603096093942297417329342836))]

Q = (FQ(11573005146564785208103371178835230411907837176583832948426162169859927052980), FQ(895714868375763218941449355207566659176623507506487912740163487331762446439))

Este tutorial es parte de una serie sobre Bulletproof ZKP.