Si tenemos un Pedersen vector commitment $A$ que contiene un compromiso para un vector $\mathbf{a}$ como $A = a_1G_1 + a_2G_2+\dots + a_nG_n$, podemos probar que conocemos la apertura enviando $\mathbf{a}$ al verificador, quien comprobaría que $A \stackrel{?}= a_1G_1 + \dots + a_nG_n$. Esto requiere enviar $n$ elementos al verificador (asumiendo que $\mathbf{a}$ tiene una longitud de $n$).

En el capítulo anterior, mostramos cómo hacer esto con zero knowledge. En este capítulo, mostraremos cómo probar el conocimiento de una apertura enviando menos de $n$ elementos, pero sin la propiedad de zero knowledge.

Motivación

La técnica que desarrollamos aquí será un componente fundamental para probar un cálculo válido de un producto interno (inner product) con una prueba de tamaño $\log n$, donde $n$ es la longitud de los vectores.

En el capítulo anterior, mostramos cómo probar que ejecutamos el producto interno correctamente, pero sin revelar los vectores o el resultado. Sin embargo, la prueba tiene un tamaño de $\mathcal{O}(n)$ debido al paso en el que el probador envía $\mathbf{l}_u$ y $\mathbf{r}_u$.

La subrutina de este artículo será importante para reducir el tamaño de la prueba. Este artículo no se centra en zero knowledge porque el algoritmo discutido anteriormente ya tiene esta propiedad. Es decir, $\mathbf{l}_u$ y $\mathbf{r}_u$ no eran secretos desde un principio, por lo que no hay necesidad de ofuscarlos.

Planteamiento del problema

Dado un vector base acordado $\mathbf{G}=[G_1,\dots,G_n]$, el probador entrega al verificador un Pedersen vector commitment $A$, donde $A$ es un compromiso no cegador (non-blinding commitment) a $\mathbf{a}$, es decir $A = \langle[a_1,\dots,a_n],[G_1,\dots,G_n]\rangle$, y desea probar que conoce la apertura de este compromiso enviando menos de $n$ términos, en lugar de enviar el vector completo $[a_1,\dots,a_n]$.

Una prueba menor que $n$

Reducir el tamaño de la prueba se basa en tres ideas clave:

Idea clave 1: El producto interno $\langle \mathbf{a},\mathbf{b}\rangle$ es la diagonal del producto externo (outer product)

La primera idea clave que aprovecharemos es que el producto interno es la diagonal del producto externo (outer product). En otras palabras, el producto externo “contiene” al producto interno en cierto sentido. El producto externo, en el contexto de vectores 1D, es una matriz 2D formada multiplicando cada elemento del primer vector 1D por todos los elementos del segundo vector. Por ejemplo:

Esto podría parecer un paso en la dirección equivocada porque el producto externo requiere $\mathcal{O}(n^2)$ pasos para calcularse. Sin embargo, la siguiente idea clave muestra que es posible calcular indirectamente el producto externo en un tiempo de $\mathcal{O}(1)$.

Idea clave 2: La suma del producto externo es igual al producto de la suma de los vectores originales

Una segunda observación es que la suma de los términos del producto externo es igual al producto de la suma de los vectores. Es decir,

Para nuestro ejemplo de los vectores $[a_1,a_2]$ y $[b_1,b_2]$ esto sería

Gráficamente, esto puede visualizarse como el área del rectángulo con dimensiones $(a_1 + a_2) \times (b_1 + b_2)$ teniendo la misma “área” que $a_1 \times b_1 + a_1 \times b_2 + a_2 \times b_1 + a_2 \times b_2$

En nuestro caso, el vector $\mathbf{b}$ es realmente el vector base de puntos de la curva elíptica, por lo que estamos diciendo que

Nota que nuestro Pedersen commitment original

está incrustado en los términos recuadrados del producto externo:

Por lo tanto, al multiplicar entre sí las sumas de las entradas del vector, también calculamos la suma del producto externo.

Dado que el producto interno es la diagonal del producto externo, hemos calculado indirectamente el producto interno multiplicando entre sí las sumas de las entradas de los vectores. Para probar que conocemos el producto interno, necesitamos probar que también conocemos los términos del producto externo que no forman parte del producto interno.

Para vectores de longitud $2$, llamemos a las partes del producto externo que no forman parte del producto interno el producto no diagonal (off-diagonal product).

A continuación, marcamos los términos que componen el producto no diagonal con $\square$ y los términos que componen el producto interno con $\blacksquare$:

Ahora podemos plantear formalmente la identidad en la que confiaremos en adelante. Si $n=2$, entonces:

La identidad también se cumple si uno de los vectores es un vector de puntos de una curva elíptica (incluso si sus logaritmos discretos son desconocidos).

Para los casos donde $n > 2$, probar el conocimiento de un producto interno significa que el probador necesita convencer al verificador de que conoce el “área” de la región sombreada en púrpura a continuación.

Transmitir esta información de manera sucinta cuando $n > 2$ es más complicado, por lo que volveremos a esto más adelante.

En el caso de $n = 2$, el área son simplemente las no diagonales.

Idea clave 3: Si $n = 1$, entonces el producto interno es igual al producto externo

Un caso especial importante es cuando tenemos un vector de longitud $1$. En ese caso, el probador simplemente envía al verificador $\mathbf{a}$ (que tiene una longitud de $1$) y el verificador simplemente multiplica el único elemento de $\mathbf{a}$ por el único elemento de $\mathbf{G}$.

Bosquejo del algoritmo

Ahora podemos crear un primer borrador de un algoritmo para el caso $n=2$ que pruebe que hemos calculado el producto interno de $\mathbf{a}$ y $\mathbf{G}$, lo cual es equivalente a demostrar que conocemos el compromiso $A$.

La interacción entre el probador y el verificador es la siguiente:

1. El probador envía su compromiso $A = a_1G_1 + a_2G_2$ al verificador.
2. El probador suma todos los términos en $\mathbf{a}$ y envía esto como $a' = a_1 + a_2$ al verificador (ten en cuenta que la suma de los componentes de un vector es un escalar, por lo tanto, sumar los elementos de $\mathbf{a}$ da como resultado el escalar $a'$). Además, el probador calcula los términos no diagonales de $\mathbf{a} \otimes \mathbf{G}$ (es decir, $R = a_2G_1$, $L = a_1G_2$) y envía $L$ y $R$ al verificador.

Gráficamente, $L$ y $R$ pueden verse de la siguiente manera:

3. El verificador calcula indirectamente $\mathbf{a} \otimes \mathbf{G}$ al calcular $a'G'$ donde $G' = G_1 + G_2$ y verifica que

En forma expandida, la ecuación anterior es:

Nota que la verificación anterior es equivalente a la identidad vista previamente:

Error de seguridad: múltiples aperturas

Sin embargo, hay un problema de seguridad: el probador puede encontrar múltiples pruebas para el mismo compromiso. Por ejemplo, el probador podría elegir $L$ de forma aleatoria, y luego calcular

Para evitar esto, reutilizamos una idea similar de nuestra discusión sobre la multiplicación en zero knowledge: el probador debe incluir la aleatoriedad $u$ proporcionada por el verificador en su cálculo. También deben enviar $L$ y $R$ por adelantado, antes de recibir $u$, de modo que $L$ y $R$ no puedan seleccionarse “ventajosamente”.

La razón por la que el probador debe enviar $L$ y $R$ de forma individual, en lugar de la suma $L + R$, es que el probador es capaz de hackear el protocolo moviendo valor entre $L$ y $R$ sin restricciones. Es decir, dado que

el probador podría elegir algún punto de la curva elíptica $S$ y calcular unos fraudulentos $L'$ y $R'$ como

Necesitamos obligar al probador a mantener $L$ y $R$ separados.

Aquí está el algoritmo actualizado que corrige este error:

1. El probador y el verificador acuerdan un vector base $[G_1, G_2]$ donde los puntos son elegidos aleatoriamente y sus logaritmos discretos son desconocidos.

2. El probador calcula y envía al verificador $(A, L, R)$:
   

   $$\begin{align*} A &= a_1G_1 + a_2G_2 && \text{// el vector commitment del que estamos probando conocimiento}\\ L &= a_1G_2 && \text{// término diagonal izquierdo}\\ R &= a_2G_1 && \text{// término diagonal derecho}\\ \end{align*}$$

3. El verificador responde con un escalar aleatorio $u$.

4. El probador calcula y envía $a'$:

5. El verificador, ahora en posesión de $(A, L, R, a', u)$ comprueba que:
   
   $$L + u A + u^2R \stackrel{?}= a'(u G_1 + G_2)$$

Internamente esto es:

lo cual es idénticamente correcto si el probador calculó correctamente $a'$, $L$ y $R$.

Nota que el verificador aplicó $u$ a $G_2$, mientras que el probador aplicó $u$ a $a_1$. Esto causa que los términos del producto interno original sean los coeficientes lineales del polinomio resultante.

El hecho de que $L$ y $R$ estén separados por $u^2$, el cual es controlado por el verificador, previene que un probador malicioso lleve a cabo el ataque descrito anteriormente. Es decir, el probador no puede mover valor de $R$ a $L$ porque el valor que mueve debe ser escalado por $u^2$, pero el probador debe enviar $L$ y $R$ antes de recibir $u$.

Una interpretación alternativa del algoritmo: reduciendo a la mitad la dimensión de $n$

El verificador solo está llevando a cabo una única multiplicación, $a'$ por $(uG_1 + G_2)$. A pesar de que comenzamos con vectores de longitud $2$, el verificador solo realiza $n/2=1$ multiplicaciones de puntos.

La operación $a_1 + a_2u$ convirtió un vector $\mathbf{a}$ de longitud $2$ en un vector de longitud $1$. Por lo tanto, tanto el probador como el verificador están construyendo conjuntamente un nuevo vector de longitud $1$ dados los vectores del probador y la aleatoriedad $u$ del verificador.

Dado que ambos han comprimido el vector original a un vector de longitud $1$, el verificador puede usar la identidad $\langle\mathbf{a}',\mathbf{G}'\rangle=\mathbf{a}'\otimes\mathbf{G}'$ cuando $n = 1$. Aquí, $\mathbf{a}' = a_1 + a_2u$ y $\mathbf{G'} = G_1u + G_2$.

Seguridad del algoritmo

Resumen del algoritmo

Como un breve resumen del algoritmo,

1. El probador envía $(A, L, R)$ al verificador.
2. El verificador responde con $u$.
3. El probador calcula y envía $a'$.
4. El verificador comprueba que:

Ahora veamos por qué el probador no puede hacer trampa.

El único “grado de libertad” que tiene el probador en el paso 3 es $a'$.

Para encontrar un $a'$ que satisfaga

el probador necesita conocer los logaritmos discretos de $G_1$ y $G_2$. Específicamente, tendría que resolver

donde

• $l$ y $r$ son los logaritmos discretos de $L$ y $R$
• $g_1$ y $g_2$ son los logaritmos discretos de $G_1$ y $G_2$ respectivamente, y $a$ es el logaritmo discreto de $A$.
• $l$ y $r$ son conocidos por el probador, ya que el probador produjo $L$ y $R$ en el paso 1.

Sin embargo, el probador no conoce los logaritmos discretos $g_1$ y $g_2$, por lo que no puede calcular $a'$.

La variable $a'$ tiene solo dos soluciones válidas

Solo hay dos valores válidos para $a'$ que satisfacen $L + uA + u^2R = a'(uG_1 + G_2)$. Nota que la ecuación $L + uA + u^2R$ forma un polinomio cuadrático con respecto a la variable $u$, y $a'(uG_1+G_2)$ forma un polinomio lineal. Según el Lema de Schwartz-Zippel, la ecuación tiene a lo sumo dos soluciones. Siempre y cuando el orden del campo sea $\gg 2$, la probabilidad de que el probador encuentre un $a'$ tal que resulte en un punto de intersección de $L + uA + u^2R = a'(uG_1 + G_2)$ es insignificante.

El enfoque del paper de Bulletproofs para inyectar aleatoriedad

En lugar de combinar $a_1$ y $a_2$ como $a_1 + a_2u$, el probador los combina como $a' = a_1u + a_2u^{-1}$ y el verificador hace $G' = u^{-1}G_1 + u G_2$. Nota que las potencias de los dos vectores se aplican en orden opuesto. Cuando calculamos el producto externo, los términos del producto interno verán cancelarse sus $uu^{-1}$:

Podría decirse que este enfoque es “más limpio”, por lo que lo usaremos en adelante.

Introduciendo $\mathsf{fold}(\mathbf{a},x)$

El cálculo $a_1x + a_2x^{-1}$ ocurre tan frecuentemente en Bulletproofs que resulta útil darle un nombre, al cual llamaremos $\mathsf{fold}(\mathbf{a},x)$. El primer argumento $\mathbf{a}$ es el vector que estamos plegando (folding), el cual debe ser de longitud par; si no lo es, lo rellenamos con un $0$. Fold divide el vector $\mathbf{a}$ de longitud $n$ en $n/2$ pares, y devuelve un vector de longitud $n/2$ de la siguiente manera:

Si hacemos $\mathsf{fold}(\mathbf{a},x^{-1})$ nos referimos a:

Cuando $n=2$, $\mathsf{fold}(\mathbf{a},x)$ es simplemente $a_1x+a_2x^{-1}$ y $\mathsf{fold}(\mathbf{a},x^{-1})=a_1x^{-1}+a_2x$.

Descripción del algoritmo con $\mathsf{fold}$

Ahora replanteamos el algoritmo usando el enfoque de inyección de aleatoriedad del paper de Bulletproofs:

1. El probador envía al verificador su compromiso de $\mathbf{a}$ como $A = a_1G_1 + a_2G_2$, junto con $L$ y $R$ calculados como
   
   $$\begin{align*} L &= a_1G_2 \\ R &= a_2G_1 \\ \end{align*}$$
2. El verificador responde con un escalar aleatorio $u$.
3. El probador calcula y envía $a'$
   
   $$a' = \mathsf{fold}(\mathbf{a},u) = a_1u + a_2u^{-1}$$
4. El verificador calcula:
   
   $$\begin{align*} P &= a'\cdot\mathsf{fold}(\mathbf{G},u^{-1})= a'\cdot(u^{-1} G_1 + uG_2)\\ P &\stackrel{?} = Lu^2 + A + u^{-2}R \end{align*}$$

Asumiendo que el probador fue honesto, la comprobación final internamente se expande a:

Cómo manejar los casos cuando $n > 2$

Asumiendo que el arreglo $\mathbf{a}$ tiene una longitud par (si no, podemos añadir un elemento cero para hacer que su longitud sea par), podemos particionar el arreglo en pares (pairwise-partition). A continuación se muestra un ejemplo de una partición en pares:

De manera similar, podemos particionar $\mathbf{G}$ en pares.

Cada uno de los sub-pares puede ser tratado luego como instancias del cálculo del producto interno usando el caso de $n=2$ anterior:

Podríamos entonces probar que conocemos los cuatro compromisos de $n=2$, es decir, $a_1G_1 + a_2G_2$, $a_3G_3 + a_4G_4$, $a_5G_5 + a_6G_6$ y $a_7G_7 + a_8G_8$, y esto sería equivalente a probar que conocemos la apertura del compromiso original.

Sin embargo, esto crearía cuatro términos $(L, R)$ adicionales por los pares que estamos probando, es decir, no habría ganancia de eficiencia en términos del tamaño de los datos que transmite el probador.

La solución ingenua (naive) sería que el probador comprometiera y enviara:

Gráficamente, esto puede verse de la siguiente manera:

Como una optimización (¡clave!), sumamos todos los términos $A_i$, $L_i$ y $R_i$ de cada uno de los pares para que se conviertan en los puntos únicos $A$, $L$, $R$. En otras palabras, el probador solo envía:

La operación descrita se muestra en la siguiente animación:

Seguridad de sumar todos los compromisos y las no diagonales

Una preocupación inicial con tal optimización es que dado que el probador está sumando más términos entre sí, hay más oportunidades para ocultar un cálculo deshonesto.

Ahora mostraremos que una vez que el probador envía $A$ (y $L$ y $R$), solo puede crear una única prueba de que conoce la apertura de $A$.

Observa que $L$ se calcula como $L = a_1G_2 + a_3G_4 +a_5G_6+a_7G_8$ y $R$ se calcula como $R = a_2G_1 + a_4G_3 +a_6G_5+a_8G_7$. No tienen ningún punto de curva elíptica en común. Por lo tanto, el probador no puede “mover valor” de $L$ a $R$ porque no conoce los logaritmos discretos de ninguno de los puntos. Efectivamente, $L$ es un Pedersen vector commitment de $[a_2, a_4, a_6, a_8]$ hacia el vector base $[G_1, G_3, G_5, G_7]$. La suposición de seguridad de un Pedersen vector commitment es que el probador solo puede producir una posible apertura de vector. “Mover valores” una vez que han enviado el compromiso significaría que el probador puede calcular un vector diferente a $[a_2, a_4, a_6, a_8]$ que produce el mismo compromiso. Pero eso contradice nuestra suposición de que un probador solo puede producir un único vector válido para un Pedersen commitment. Un argumento similar se puede hacer para $R$.

$A$ es la suma de cuatro Pedersen commitments (los compromisos a los vectores $[a_1, a_2]$, $[a_3, a_4]$, $[a_5, a_6]$, $[a_7, a_8]$). Sin embargo, el hecho de que varios Pedersen commitments se sumen es irrelevante desde una perspectiva de seguridad. No hay diferencia si los compromisos se calculan por separado y luego se suman, o si $A$ se calcula como un vector de $n = 8$. Considera que:

Por ejemplo, el probador podría “mover valor” de $a_1G_1$ a $a_2G_1$.

La única preocupación restante es que el probador pudiera mover valor de $a_1G_1$ en $A$ hacia $a_2G_1$ en $L$, ya que comparten un punto común en la curva elíptica. Sin embargo, esto es prevenido por el valor aleatorio $u$ del verificador, como se mostró anteriormente.

Por lo tanto, una vez que el probador envía $(A, L, R)$ calculado de la manera descrita en esta sección, solo puede crear una posible apertura, y en consecuencia, crear solo una posible prueba.

Probando que conocemos una apertura de $A$ mientras enviamos $n/2$ datos

1. El probador envía $A = \langle\mathbf{a},\mathbf{G}\rangle$ al verificador. El probador también envía $L = a_1G_2 + a_3G_4 + ... a_{n-1}G_n$ y $R = a_2G_1 + a_4G_3 + ... + a_nG_{n-1}$.
2. El verificador envía un valor aleatorio $u$.
3. El probador calcula $\mathbf{a}'=\mathsf{fold}(\mathbf{a},u)$ y envía $\mathbf{a}'$ al verificador.
4. El verificador comprueba que $Lu^2 + A + Ru^{-2} \stackrel{?}=\langle\mathbf{a}',\mathsf{fold}(\mathbf{G},u^{-1})\rangle$.

Dejamos como ejercicio para el lector desarrollar un ejemplo para comprobar que la verificación final es algebraicamente idéntica si el probador fue honesto. Sugerimos usar un ejemplo pequeño como $n=4$.

Otra interpretación más de $\mathsf{fold}$

$P$ es un compromiso al vector original $\mathbf{a}$ con respecto al vector base $\mathbf{G}$. $L$ es un compromiso al vector compuesto por las no diagonales izquierdas de los productos externos en pares, y $R$ es un compromiso a los componentes de las no diagonales derechas de los productos externos en pares.

La suma $Lu^2 + P + Ru^{-2}$ es en sí misma un vector commitment del vector $\mathsf{fold}(\mathbf{a},u)$ hacia la base $\mathsf{fold}(\mathbf{G}, u^{-1})$, que tiene un tamaño de $n/2$.

Mostramos la relación gráficamente a continuación:

Para probar que conocemos la apertura de un compromiso de tamaño $n/2$, simplemente podemos enviar el vector de tamaño $n/2$, que en este caso es $\mathsf{fold}(\mathbf{a},u)$.

Usando esta interpretación, el algoritmo está haciendo lo siguiente:

1. El probador envía $A = \langle\mathbf{a},\mathbf{G}\rangle$, $L$ y $R$.
2. El verificador envía $u$.
3. Ahora el verificador tiene un compromiso $A' = Lu^2 + A + Ru^{-2}$ con respecto al vector base $\mathsf{fold}(\mathbf{G},u^{-1})$.
4. El probador prueba que conoce la apertura de $A'$ enviando $\mathbf{a}' =\mathsf{fold}(\mathbf{a}, u)$.

Limitaciones en la velocidad de verificación

Dado que el verificador necesita calcular $\mathsf{fold}(\mathbf{G}, u^{-1})$, esto requerirá iterar sobre todo el vector $\mathbf{G}$, lo cual tomará un tiempo de $\mathcal{O}(n)$. Aunque el tamaño de la prueba puede ser más pequeño que los vectores originales, verificar la prueba seguirá tomando un tiempo lineal.

Resumen

Hemos mostrado cómo el probador puede demostrar que conoce una apertura de un Pedersen vector commitment $A$ enviando solo $n/2$ elementos ($\mathbf{a}$ plegado).

En el próximo capítulo, mostraremos cómo aplicar recursivamente este algoritmo para que el probador solo envíe $\mathcal{O}(\log n)$ elementos.

Ejercicio: Implementa el algoritmo descrito en este capítulo. Utiliza el siguiente código como punto de partida:

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
    # your code here

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

# return L, R as a tuple
def compute_secondary_diagonal(G_vec, a):
    pass
    # your code here

a = [9,45,23,42]

# prover commits
A = vector_commit(G_vec, a)
L, R = compute_secondary_diagonal(G_vec, a)

# verifier computes randomness
u = random_element()

# prover computes fold(a)
aprime = fold(a, u)

# verifier computes fold(G)
Gprime = fold_points(G_vec, pow(u, -1, p))

# verification check
assert eq(vector_commit(Gprime, aprime), add_points(multiply(L, pow(u, 2, p)), A, multiply(R, pow(u, -2, p)))), "invalid proof"
assert len(Gprime) == len(a) // 2 and len(aprime) == len(a) // 2, "proof must be size n/2"