En este artículo, presentamos algunos trucos algebraicos útiles para los productos internos que serán de utilidad para derivar pruebas de rango (range proofs) y codificar circuitos como productos internos más adelante. Cada regla estará acompañada de una demostración sencilla.
Notación
Las variables en negrita, como a, denotan un vector. Las variables sin negrita, como v, denotan un escalar. El operador ∘ es el producto de Hadamard (multiplicación elemento por elemento) de dos vectores, es decir, [a1,…,an]∘[b1,…,bn]=[a1b1,…,anbn]. Usamos las abreviaturas “lhs” y “rhs” para referirnos al lado izquierdo (“left-hand side”) y al lado derecho (“right-hand side”) de una ecuación, respectivamente. Un “sumando” es un elemento de una suma, por ejemplo, si a+b=c, entonces a y b se llamarían sumandos. El vector 1 es un vector de puros unos, es decir, [1,1,…,1]. Se asume implícitamente que todos los vectores tienen la misma longitud n, a menos que se indique lo contrario.
Regla 1: Un producto interno donde uno de los vectores es una suma de vectores se puede expandir
Supongamos que estamos calculando un producto interno donde uno de los vectores es una suma de dos vectores, por ejemplo ⟨a+b,c⟩. Podemos dividir esto en la suma de dos productos internos:
⟨a+b,c⟩=⟨a,c⟩+⟨b,c⟩
Demostración:
El lhs se puede escribir como
i=1∑n(ai+bi)ci
El rhs se puede escribir como
i=1∑naici+i=1∑ncibi=i=1∑n(aici+cibi)=i=1∑n(ai+bi)ci
Regla 2: Los productos internos con términos comunes se pueden combinar
Los dos productos internos en el lhs a continuación tienen un vector común c. Por lo tanto, se pueden combinar:
⟨a,c⟩+⟨b,c⟩=⟨a+b,c⟩
Esta es realmente la Regla 1 con el lhs y el rhs intercambiados.
La demostración es la misma que para la Regla 1.
Regla 3: Mover vectores al otro lado del producto interno
Un producto interno se puede reescribir como el vector 1 con el producto de Hadamard de los vectores originales:
⟨a,b⟩=⟨1,a∘b⟩
Demostración:
⟨a,b⟩⟨1,a∘b⟩i=1∑naibi=i=1∑naibi=i=1∑n1∗(aibi)=i=1∑n1∗(aibi)
Regla 4: Podemos sumar vectores a uno de los términos del producto interno para forzar a que dos productos internos tengan términos comunes
Supongamos que estamos sumando un producto interno ⟨x,b+c⟩ y un producto interno ⟨y,b⟩, y la suma de los productos internos es v. Nótese que tienen componentes diferentes, por lo que no podemos sumarlos con la Regla 2. Sin embargo, la siguiente igualdad
⟨x,b+c⟩+⟨y,b⟩=v
se puede escribir como
⟨x+y,b+c⟩=v+⟨y,c⟩
En el escenario anterior, podemos sumar ⟨y,c⟩ a ambos lados.
⟨x,b+c⟩+⟨y,b⟩+⟨y,c⟩⟨x,b+c⟩+⟨y,b⟩+⟨y,c⟩=v+⟨y,c⟩=v+⟨y,c⟩
Ahora tenemos términos y comunes que podemos combinar usando la Regla 2:
⟨x,b+c⟩+⟨y,b⟩+⟨y,c⟩⟨x,b+c⟩+⟨y,b+c⟩⟨x,b+c⟩+⟨y,b+c⟩=v+⟨y,c⟩=v+⟨y,c⟩=v+⟨y,c⟩
Ahora que hemos forzado a los dos productos internos a tener el término común ⟨b+c⟩ en el lhs, podemos combinarlos en un solo vector usando la Regla 2 nuevamente:
⟨x,b+c⟩+⟨y,b+c⟩⟨x+y,b+c⟩⟨x+y,b+c⟩=v+⟨y,c⟩=v+⟨y,c⟩=v+⟨y,c⟩
Por lo tanto,
⟨x,b+c⟩+⟨y,b⟩=v
se puede reescribir como
⟨x+y,b+c⟩=v+⟨y,c⟩
Regla 5: Sumar dos productos internos con vectores no relacionados
Podemos sumar ⟨a1,b1⟩+⟨a2,b2⟩ (que no tienen vectores en común) y obtener:
⟨a1,b1⟩+⟨a2,b2⟩=⟨a1+a2,b1+b2⟩−⟨a1,b2⟩−⟨a2,b1⟩
Demostración:
⟨a1,b1⟩+⟨a2,b2⟩⟨a1,b1⟩+⟨a2,b2⟩+⟨a1,b2⟩⟨a1,b1⟩+⟨a2,b2⟩+⟨a1,b2⟩⟨a1,b1⟩+⟨a2,b2⟩+⟨a1,b2⟩+⟨a2,b1⟩⟨a1,b1⟩+⟨a2,b2⟩+⟨a1,b2⟩+⟨a2,b1⟩⟨a1,b1⟩+⟨a2,b2⟩+⟨a1,b2⟩+⟨a2,b1⟩⟨a1,b1⟩+⟨a2,b2⟩=⟨a1,b1⟩+⟨a2,b2⟩=⟨a1,b1⟩+⟨a2,b2⟩+⟨a1,b2⟩=⟨a1,b1⟩+⟨a1+a2,b2⟩=⟨a1,b1⟩+⟨a1+a2,b2⟩+⟨a2,b1⟩=⟨a1+a2,b1⟩+⟨a1+a2,b2⟩=⟨a1+a2,b1+b2⟩=⟨a1+a2,b1+b2⟩−⟨a1,b2⟩−⟨a2,b1⟩sumar ⟨a1,b2⟩ a ambos ladoscombinar los teˊrminos b2sumar ⟨a2,b1⟩ a ambos ladoscombinar los teˊrminos b1combinar el lado derechorestar ⟨a1,b2⟩+⟨a2,b1⟩
La demostración ilustra que a veces puede resultar útil ser creativo al encontrar productos internos para sumar a ambos lados de la ecuación.
Regla 6: Los escalares se pueden llevar dentro y fuera de un producto interno
z⋅⟨a,b⟩=⟨z⋅a,b⟩=⟨a,z⋅b⟩
La demostración de esta afirmación se deja como ejercicio para el lector. Como pista, los términos constantes se pueden introducir y sacar de una sumatoria.
Este tutorial es parte de nuestra serie sobre ZK Bulletproofs.