Las combinaciones lineales aleatorias son un truco común en los algoritmos de pruebas de conocimiento cero para permitir que $m$ comprobaciones de igualdad se verifiquen probabilísticamente con una única comprobación de igualdad. Supongamos que tenemos $m$ productos internos que intentamos demostrar. En lugar de crear $m$ pruebas, creamos una combinación lineal aleatoria de las igualdades y demostramos eso.

Igualdad de los compromisos de Pedersen

Primero, consideremos cómo podríamos demostrar la igualdad de múltiples compromisos de Pedersen.

Si tenemos puntos de curva elíptica $G$ y $B$ con logaritmos discretos desconocidos, y términos de cegamiento $\alpha$ y $\beta$, podemos construir compromisos de Pedersen $L$ y $R$ donde

$L = aG + \alpha B$
$R = bG + \beta B$

El verificador puede comprobar si $a = b$ si el probador proporciona la diferencia en los términos de cegamiento. El verificador no puede simplemente comprobar $L = R$ porque, por lo general, los términos de cegamiento no serán iguales entre sí, es decir, $\alpha \neq \beta$.

Si el probador desea convencer al verificador de que $a$ y $b$ están comprometidos en $L$ y $R$ respectivamente, pero sin revelar $a$ y $b$, el probador puede calcular

$\pi = \alpha - \beta$

Y entregar $\pi$ al verificador. El verificador calcula

$L \stackrel{?}{=} R + \pi B$

Internamente, esto se expande a

$(aG + \alpha B) = (bG + \beta B) + (\alpha - \beta) B$

Todos los términos de cegamiento se cancelarán dejando $aG \stackrel{?}{=} bG$.

Pero supongamos que el probador desea establecer la igualdad para varios compromisos, es decir, $L_1 = L_2, L_2 = R_2, ..., L_m = R_m$. La solución ingenua es enviar $m$ términos de cegamiento $\pi_1,...,\pi_m$ y el verificador ejecutará $m$ comprobaciones de igualdad. Esto requerirá enviar $m$ elementos del campo ($\pi_1,...,\pi_m$) y el algoritmo del verificador se ejecutará en un tiempo de $\mathcal{O}(m)$.

Por qué el probador no puede simplemente sumar todos los compromisos

Supongamos que tenemos $l_1, l_2, r_1, r_2$ con compromisos $L_1, L_2, R_1, R_2$ respectivamente. Supongamos también que el probador quiere demostrar que $l_1 = r_1$ y $l_2 = r_2$ sin revelarlos.

La siguiente comprobación no es segura:

donde $\pi$ es la diferencia en los términos de cegamiento. Como contraejemplo, consideremos el caso donde $l_1 = 1, r_1 = 2, l_2 = 2, r_2 = 1$. Las sumas están equilibradas, pero la afirmación original es incorrecta.

Combinaciones lineales aleatorias

Sin embargo, si se requiere que el probador demuestre que

para un valor aleatorio $z$ que no pueden predecir, entonces el esquema es seguro.

Específicamente, el probador y el verificador ejecutan el siguiente algoritmo:

Prueba de igualdad aleatorizada

Configuración

El probador y el verificador acuerdan los puntos de curva elíptica $G$ y $B$, donde los logaritmos discretos son desconocidos.

El probador envía los compromisos

El probador genera los términos de cegamiento $\alpha_1, \alpha_2, \beta_1, \beta_2$ y crea los compromisos de Pedersen

$L_1 = l_{1}G + \alpha_1 B$
$R_1 = r_{1}G + \beta_1 B$
$L_2 = l_{2}G + \alpha_2 B$
$R_2 = r_{2}G + \beta_2 B$

y envía $(L_1, L_2, R_1, R_2)$ al verificador.

El verificador elige un $z$ aleatorio

El verificador elige un elemento aleatorio del campo $z$ y lo envía al probador.

El probador calcula la diferencia en los términos de cegamiento

El probador calcula $\pi = \alpha_1+\alpha_2\cdot z-\beta_1-\beta_2\cdot z$ y envía $\pi$ al verificador.

Comprobación de verificación final

El verificador comprueba que

Análisis de seguridad

Si $l_1 = r_1$ y $l_2 = r_2$, entonces la ecuación estará equilibrada independientemente de la elección de $z$, asumiendo que el probador calculó $\pi$ correctamente.

Ahora supongamos que $l_1\neq r_1$ o $l_2 \neq r_2$. El probador aún no podrá producir un $\pi$ válido porque hacerlo requeriría resolver los logaritmos discretos de $G$ y $B$.

Generalizando a $m$ comprobaciones

Si tenemos $m$ comprobaciones de igualdad, $L_1 = R_1, L_2 = R_2, ..., L_m = R_m$, el verificador podría enviar $m$ elementos aleatorios $z_1,\dots,z_m$ y el probador podría proporcionar $\pi$ tal que

$L_1 + L_2z_1 + L_3z_2 + ... L_mz_{m-1} \stackrel{?}{=}R_1 + R_2z_1+R_3z_2+\dots+R_mz_{m-1} + \pi B$

Sin embargo, esto requiere que el verificador envíe $m$ elementos, lo que conduce a una sobrecarga de comunicación lineal. La sobrecarga de comunicación se puede reducir a una constante si el verificador solo envía $z$ y el probador y el verificador separan los compromisos mediante potencias sucesivas de $z$:

$L_1 + L_2z + L_3z^2 + ... L_mz^{m-1} \stackrel{?}{=}R_1+R_2z+R_3z^2\dots+R_mz^{m-1} + \pi B$

Análisis de seguridad

El lado izquierdo y el lado derecho son ambos polinomios de grado $m-1$. Si no son iguales entre sí, entonces se intersectan en un máximo de $m-1$ puntos por el Schwartz Zippel Lemma. Si $m\ll p$ donde $p$ es el orden del campo finito, entonces nuevamente la probabilidad de que $z$ sea un punto de intersección es insignificante.

Combinaciones lineales aleatorias de productos internos

Podemos generalizar la técnica anterior para combinar múltiples productos internos.

Supongamos que tenemos dos productos internos

$\langle \mathbf{a}_L, \mathbf{a}_R\rangle = v_1$ y $\langle \mathbf{a}_L, \mathbf{a}_W\rangle=v_2$

Debido a que los dos productos internos comparten un término común, es algebraicamente posible combinarlos de la siguiente manera:

$\langle\mathbf{a}_L, \mathbf{a}_R + \mathbf{a}_W\rangle = v_1 + v_2$

Sin embargo, esto no es seguro desde una perspectiva de solidez porque es posible que $\langle \mathbf{a}_L, \mathbf{a}_R\rangle \neq v_1$ y $\langle \mathbf{a}_L, \mathbf{a}_W\rangle\neq v_2$ pero $\langle\mathbf{a}_L, \mathbf{a}_R + \mathbf{a}_W\rangle = v_1 + v_2$.

Como es de esperar, podemos resolver esto utilizando una combinación lineal aleatoria.

Solo necesitamos crear una prueba de producto interno para un único producto interno en lugar de dos. Es crucial que el probador reciba $z$ después de haber enviado los compromisos relevantes, pero dejamos los detalles exactos para el próximo capítulo cuando veamos un ejemplo de un algoritmo que utiliza esta técnica: las pruebas de rango.

Este tutorial es parte de una serie sobre ZK Bulletproofs.