En el contexto de las pruebas de conocimiento nulo (zero-knowledge proofs), un circuito aritmético es un sistema de ecuaciones que modela un problema en NP.

Un punto clave de nuestro artículo sobre P vs NP es que cualquier solución a un problema en P o NP puede ser verificada modelando el problema como un circuito booleano.

Luego, convertimos nuestra solución para el problema original en un conjunto de valores para las variables booleanas (llamado el witness o testigo) que hace que el circuito booleano devuelva verdadero.

Este artículo se basa en el enlazado arriba, así que por favor léalo primero.

Circuitos aritméticos como alternativa a los circuitos booleanos

Una desventaja de usar un circuito booleano para representar una solución a un problema es que puede ser verboso al representar operaciones aritméticas, como la suma o la multiplicación.

Por ejemplo, si queremos expresar $a + b = c$ donde $a = 8, b = 4, c = 12$, debemos transformar $a$, $b$ y $c$ en números binarios. Cada bit en el número binario corresponderá a una variable booleana distinta. En este ejemplo, supongamos que necesitamos 4 bits para codificar $a$, $b$ y $c$, donde $a₀$ representa el bit menos significativo (LSB) y $a₃$ representa el bit más significativo (MSB) del número $a$, como se muestra a continuación:

• a₃, a₂, a₁, a₀
  • $a = 1000$
• b₃, b₂, b₁, b₀
  • $b = 0100$
• c₃, c₂, c₁, c₀
  • $c = 1100$

(No necesita saber cómo convertir un número a binario por ahora, explicaremos el método más adelante en el artículo).

Una vez que tenemos $a$, $b$ y $c$ escritos en binario, podemos escribir un circuito booleano cuyas entradas sean todos los dígitos binarios $(a₀, a₁, …, c₂, c₃)$. Nuestro objetivo es escribir dicho circuito booleano, de tal manera que el circuito devuelva verdadero (true) si y solo si $a + b = c$.

Esto resulta ser más complicado de lo esperado, como lo demuestra el gran circuito a continuación, que modela $a + b = c$ en binario. Por brevedad, no mostramos la derivación. Solo mostramos la fórmula para ilustrar lo verboso que puede llegar a ser un circuito así:

Copy
((a₄ ∧ b₄ ∧ c₄) ∨ (¬a₄ ∧ ¬b₄ ∧ c₄) ∨ (¬a₄ ∧ b₄ ∧ ¬c₄) ∨ (a₄ ∧ ¬b₄ ∧ ¬c₄)) ∧

((a₃ ∧ b₃ ∧ ((a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀)))) ∨
 (¬a₃ ∧ ¬b₃ ∧ ((a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀)))) ∨
 (¬a₃ ∧ b₃ ∧ ¬((a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀)))) ∨
 (a₃ ∧ ¬b₃ ∧ ¬((a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))))) ∧

((a₂ ∧ b₂ ∧ ((a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))) ∨
 (¬a₂ ∧ ¬b₂ ∧ ((a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))) ∨
 (¬a₂ ∧ b₂ ∧ ¬((a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀)))) ∨
 (a₂ ∧ ¬b₂ ∧ ¬((a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))))) ∧

((a₁ ∧ b₁ ∧ c₀) ∨ (¬a₁ ∧ ¬b₁ ∧ c₀) ∨ (¬a₁ ∧ b₁ ∧ ¬c₀) ∨ (a₁ ∧ ¬b₁ ∧ ¬c₀)) ∧

((a₀ ∧ b₀ ∧ c₀) ∨ (¬a₀ ∧ ¬b₀ ∧ c₀) ∨ (¬a₀ ∧ b₀ ∧ ¬c₀) ∨ (a₀ ∧ ¬b₀ ∧ ¬c₀)) ∧

¬ ((a₄ ∧ b₄) ∨
     (b₄ ∧ (a₃ ∧ b₃) ∨ (b₃ ∧ (a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))) ∨
     (a₃ ∧ (a₂ ∧ b₂) ∨ (b₂ ∧ (a₁ ∧ b₁) ∨ (b₁ ∧ c₀) ∨ (a₁ ∧ c₀))))

El punto es que, si estamos restringidos a entradas booleanas y operaciones booleanas básicas (AND, OR, NOT), la construcción de circuitos puede volverse complicada y tediosa rápidamente para problemas básicos, especialmente cuando involucran aritmética.

En contraste, sería más simple representar números directamente dentro de un circuito. En lugar de modelar la suma con una fórmula booleana, usamos directamente la suma y la multiplicación en esos números.

Este artículo demuestra que también es posible modelar cualquier problema en P o NP con un circuito aritmético.

Circuitos aritméticos

Un circuito aritmético es un sistema de ecuaciones que usa solo suma, multiplicación e igualdad. Al igual que un circuito booleano, comprueba que un conjunto propuesto de entradas sea válido, pero no calcula una solución.

El siguiente es nuestro primer ejemplo de un circuito aritmético:

Copy
6 = x₁ + x₂
9 = x₁x₂

Decimos que un circuito booleano está satisfecho si tenemos una asignación a las variables de entrada que resulta en una salida verdadera (true). De manera similar, un circuito aritmético está satisfecho si hay una asignación a las variables tal que todas las ecuaciones sean verdaderas.

Por ejemplo, el circuito anterior se satisface con x₁ = 3, x₂ = 3 porque ambas ecuaciones en el circuito son verdaderas. Por el contrario, el circuito no se satisface con x₁ = 1, x₂ = 6 porque la ecuación 9 = x₁x₂ no es verdadera.

Por lo tanto, podemos pensar en un circuito aritmético de manera intercambiable con el conjunto de ecuaciones en el circuito. Un conjunto de entradas “satisface el circuito” si y solo si esas entradas hacen que todas las ecuaciones sean verdaderas.

Notación y terminología

Las variables en un circuito aritmético se denominan signals (señales) porque Circom, el lenguaje de programación que usaremos para escribir pruebas ZK, se refiere a ellas de esta manera.

Para expresar igualdad, usaremos el operador ===. Usamos esta notación porque Circom la utiliza para establecer que dos signals tienen el mismo valor, así que es mejor que nos acostumbremos a verla.

Hacemos hincapié en que === afirma que el lado izquierdo y el lado derecho son iguales. Por ejemplo, en el siguiente circuito:

c === a + b

no estamos sumando a y b para asignar el resultado a c. En su lugar, asumimos que los valores a, b y c se proporcionan como entradas, y estamos afirmando que se cumple una relación entre ellos. Esto tiene el efecto de restringir (constrain) la suma de a y b para que sea c.

Piense en c === a + b como algo completamente equivalente a assertEq(c, a + b). De manera similar, la expresión a + b === c * d es completamente equivalente a assertEq(a + b, c * d). En esencia, verificar estas ecuaciones en un circuito implica comprobar si se satisfacen ciertas condiciones (restricciones o constraints). El agente que demuestra la validez de su witness puede asignar cualquier valor a las signals. Sin embargo, su prueba (witness) solo se considerará válida si se cumplen todas las restricciones.

Por ejemplo, si un agente desea probar:

Copy
a === b + c + 3
a * u === x * y

debe suministrar (a, b, c, u, x, y) desde fuera del circuito y asignarlos a las signals en el circuito.

Recuerde, el código anterior es equivalente a:

Copy
assertEq(a, b + c + 3)
assertEq(a * u, x * y)

Un modelo mental útil para el circuito aritmético es que todas las signals se tratan como entradas sin salidas.

Para dejar claro el punto, proporcionamos una visualización en el siguiente video. Todas las signals son entradas, y === se usa para comprobar en lugar de asignar.

El circuito en el video podría haberse escrito como:

Copy
z + y === x
x + y === u

sin ningún cambio en su significado.

El circuito aritmético x === x + 1 no significa incrementar x. Es un circuito aritmético sin solución porque x no puede ser igual a x + 1. Por lo tanto, es imposible satisfacer la restricción.

Interpretación de circuitos aritméticos

Considere el siguiente circuito:

Copy
x₁(x₁ - 1) === 0
x₁x₂ === x₁

La primera restricción x₁(x₁ - 1) === 0 restringe los valores posibles de x₁ solo a 0 o 1. Cualquier otro valor para x₁ no satisfaría esta restricción.

En la segunda restricción x₁x₂ === x₁ tenemos dos escenarios posibles:

• Si x₁ = 1, entonces x₂ también debe ser 1, o la segunda restricción no podrá satisfacerse. Si x₁ = 1 y x₂ ≠ 1, entonces la segunda ecuación se convierte en 1 * x₂ === 1, lo cual solo puede satisfacerse si x₂ = 1, lo que crea un conflicto.
• Si x₁ = 0, entonces x₂ puede tener cualquier valor porque 0x₂ === 0 es trivial de satisfacer.

Las siguientes asignaciones a (x₁, x₂) son todos witnesses válidos:

• $(x₁, x₂) = (1, 1)$
• $(x₁, x₂) = (0, 2)$
• $(x₁, x₂) = (0, 1337)$
• $(x₁, x₂) = (0, 404)$

Recuerde que un sistema de ecuaciones puede tener muchas soluciones. De manera similar, un circuito aritmético también puede tener muchas soluciones. Sin embargo, por lo general, solo estamos interesados en verificar una solución dada. No necesitamos encontrar todas las soluciones para un circuito aritmético.

Circuito booleano vs aritmético

La siguiente tabla muestra en qué difieren los circuitos booleanos y los circuitos aritméticos, pero tenga en cuenta que sirven para el mismo propósito de validar un witness:

Aparte de la conveniencia de usar menos variables en algunas circunstancias, los circuitos aritméticos y los circuitos booleanos son herramientas que realizan el mismo trabajo: demostrar que usted tiene un witness para un problema en NP.

Volviendo al ejemplo inicial a + b = c

Revisemos nuestro ejemplo anterior: escribir un circuito booleano para representar la ecuación a + b = c, donde se nos da c = 12. Para un circuito booleano, necesitamos codificar a, b y c en binario, lo que requiere 4 bits cada uno (en este ejemplo). En total, tenemos 12 entradas al circuito. En comparación, el circuito aritmético solo requiere 3 entradas: a, b y c. La reducción en el número de entradas y el tamaño general del circuito es la razón por la que preferimos usar circuitos aritméticos para aplicaciones ZK.

Similitudes entre sistemas de ecuaciones y circuitos aritméticos

Los circuitos booleanos siempre tienen una expresión que devuelve verdadero o falso si el witness se satisface.

Por ejemplo, si tenemos un conjunto de signals $x$, $y$ y $z$, y deseamos restringir la suma de $x$ e $y$ para que sea $5$, entonces necesitamos una ecuación separada para eso. Cualquier forma en la que deseemos restringir $z$ tendría su propia ecuación separada.

Para demostrar que los circuitos aritméticos y los circuitos booleanos son equivalentes, más adelante mostraremos que cualquier circuito booleano se puede transformar en un circuito aritmético. Esto demuestra que se pueden usar de manera intercambiable con el propósito de demostrar que un agente tiene un witness para un problema en P o NP.

Todos los problemas P son un subconjunto de los problemas NP

Como se discutió en el capítulo anterior sobre P vs NP, todos los problemas P son un subconjunto de los problemas NP en términos de los requisitos de computación para validar un witness, por lo que en adelante solo nos referiremos a problemas NP, entendiendo que esto incluye a P.

Nuestra conclusión es que, si cualquier solución a un problema en NP se puede modelar con un circuito booleano, entonces cualquier solución a un problema en NP (o P) se puede modelar con un circuito aritmético.

Pero antes de demostrar su equivalencia, proporcionaremos ejemplos sobre cómo modelar las soluciones a problemas en NP para que tengamos una intuición de cómo se utilizan los circuitos aritméticos.

Ejemplos de circuitos aritméticos

En nuestro primer ejemplo, rehacemos nuestro problema de coloreo con 3 colores para Australia. En el segundo, demostramos cómo usar un circuito aritmético para probar que una lista está ordenada.

Ejemplo 1: Modelado del coloreo con 3 colores con un circuito aritmético

Cuando usamos un circuito booleano para modelar un coloreo con 3 colores (3-coloring), cada territorio tenía 3 variables booleanas (una para cada color) que indicaban si se le había asignado ese color al país. Luego agregamos restricciones para forzar a cada territorio a tener exactamente un color (restricciones de color) y restricciones para hacer cumplir que los territorios adyacentes no tuvieran el mismo color (restricciones de límite o boundary constraints).

Es más fácil modelar este problema usando circuitos aritméticos porque podemos asignar una sola signal a cada territorio con los valores posibles $\set{1, 2, 3}$ para modelar sus colores, en lugar de tres variables booleanas. Podemos asignar colores a los números arbitrariamente, como blue = 1, red = 2 y green = 3.

Para cada territorio, escribimos la restricción de color única como:

Copy
0 === (1 - x) * (2 - x) * (3 - x)

para hacer cumplir que cada territorio tenga exactamente un color. La restricción anterior solo se puede satisfacer si x es 1, 2 o 3.

Coloreo de Australia con 3 colores

Recuerde que Australia tiene seis territorios:

• WA = Australia Occidental (West Australia)
• SA = Australia Meridional (South Australia)
• NT = Territorio del Norte (Northern Territory)
• Q = Queensland
• NSW = Nueva Gales del Sur (New South Wales)
• V = Victoria

Decir WA = 1 es equivalente a decir “Colorea Australia Occidental de azul”. De manera similar, WA = 2 significa que se asignó el “rojo” a Australia Occidental, y WA = 3 significa que se asignó el “verde”.

Nuestra restricción de color (restringir cada territorio a ser azul, rojo o verde) para cada territorio se convierte en:

Copy
1) 0 === (1 - WA) * (2 - WA) * (3 - WA)
2) 0 === (1 - SA) * (2 - SA) * (3 - SA)
3) 0 === (1 - NT) * (2 - NT) * (3 - NT)
4) 0 === (1 - Q) * (2 - Q) * (3 - Q)
5) 0 === (1 - NSW) * (2 - NSW) * (3 - NSW)
6) 0 === (1 - V) * (2 - V) * (3 - V)

Ahora queremos hacer cumplir que los territorios vecinos no tengan el mismo color. Una forma de lograr esto es multiplicar las signals del territorio vecino y asegurarnos de que el producto sea uno “aceptable”. Considere la siguiente tabla para los territorios vecinos x e y:

Si dos signals (territorios vecinos) tienen el mismo número (color), entonces su producto será uno de $\set{1,4,9}$, los números en rojo de arriba. Si x e y están restringidos a ser 1, 2 o 3, y x e y no son iguales entre sí, entonces el producto xy será uno de $\set{2, 3, 6}$. Por lo tanto, si xy = 2 o xy = 3 o xy = 6, aceptamos la asignación porque significa que los dos vecinos tienen colores diferentes.

Para cada territorio vecino x e y, podemos usar la siguiente restricción para hacer cumplir que no sean iguales entre sí:

Copy
0 === (2 - xy) * (3 - xy) * (6 - xy)

La ecuación anterior se satisface si y solo si el producto xy es igual a 2, 3 o 6.

Las restricciones de límite se crean iterando a través de las fronteras y aplicando las restricciones de límite entre cada par de territorios vecinos, como ilustra el siguiente video:

Ahora mostramos las restricciones de límite:

Copy
Western Australia and South Australia:
7) 0 === (2 - WA * SA) * (3 - WA * SA) * (6 - WA * SA)

Western Australia and Northern Territory
8) 0 === (2 - WA * NT) * (3 - WA * NT) * (6 - WA * NT)

Northern Territory and South Australia
9) 0 === (2 - NT * SA) * (3 - NT * SA) * (6 - NT * SA)

Northern Territory and Queensland
10) 0 === (2 - NT * Q) * (3 - NT * Q) * (6 - NT * Q)

South Australia and Queensland
11) 0 === (2 - SA * Q) * (3 - SA * Q) * (6 - SA * Q)

South Australia and New South Wales
12) 0 === (2 - SA * NSW) * (3 - SA * NSW) * (6 - SA * NSW)

South Australia and Victoria
13) 0 === (2 - SA * V) * (3 - SA * V) * (6 - SA * V)

Queensland and New South Wales
14) 0 === (2 - Q * NSW) * (3 - Q * NSW) * (6 - Q * NSW)

New South Wales and Victoria
15) 0 === (2 - NSW * V) * (3 - NSW * V) * (6 - NSW * V)

Al combinar ambos, vemos el circuito aritmético completo para demostrar que tenemos un coloreo de 3 colores válido para Australia:

Copy
// color constraints
0 === (1 - WA) * (2 - WA) * (3 - WA)
0 === (1 - SA) * (2 - SA) * (3 - SA)
0 === (1 - NT) * (2 - NT) * (3 - NT)
0 === (1 - Q) * (2 - Q) * (3 - Q)
0 === (1 - NSW) * (2 - NSW) * (3 - NSW)
0 === (1 - V) * (2 - V) * (3 - V)

// boundary constraints
0 === (2 - WA * SA) * (3 - WA * SA) * (6 - WA * SA)
0 === (2 - WA * NT) * (3 - WA * NT) * (6 - WA * NT)
0 === (2 - NT * SA) * (3 - NT * SA) * (6 - NT * SA)
0 === (2 - NT * Q) * (3 - NT * Q) * (6 - NT * Q)
0 === (2 - SA * Q) * (3 - SA * Q) * (6 - SA * Q)
0 === (2 - SA * NSW) * (3 - SA * NSW) * (6 - SA * NSW)
0 === (2 - SA * V) * (3 - SA * V) * (6 - SA * V)
0 === (2 - Q * NSW) * (3 - Q * NSW) * (6 - Q * NSW)
0 === (2 - NSW * V) * (3 - NSW * V) * (6 - NSW * V)

Tenemos 15 restricciones, al igual que en el circuito booleano, pero con un tercio de la cantidad de variables (signals). En lugar de 3 variables booleanas para cada territorio, tenemos una signal para cada territorio. Para circuitos más grandes, esta reducción en complejidad y espacio puede ser sustancial.

Ejemplo 2: Probar que una lista está ordenada

Dada una lista de números [a₁, a₂, ..., aₙ], decimos que la lista está “ordenada” si aₙ ≥ aₙ₋₁ ≥ … a₃ ≥ a₂ ≥ a₁. En otras palabras, yendo de final a principio, los números no son crecientes.

Nuestro objetivo es escribir un circuito aritmético que verifique que la lista está ordenada.

Para hacer esto, necesitamos un circuito aritmético que exprese a ≥ b para dos signals. Esto resulta ser más complicado de lo que parece a simple vista porque los circuitos aritméticos solo permiten igualdad, suma y multiplicación, no comparación.

Pero supongamos que tuviéramos un circuito de “mayor o igual que”, llamémoslo GTE(a,b). Entonces construiríamos los circuitos para comparar cada par de elementos consecutivos de la lista: GTE(aₙ, aₙ₋₁), ..., GTE(a₃, a₂), GTE(a₂, a₁), y si todos se satisfacen, entonces la lista está ordenada.

Para comparar dos números decimales sin el operador $≥$, primero necesitamos un circuito aritmético que valide una representación binaria propuesta para el número, por lo que primero tomaremos un pequeño desvío sobre los números binarios.

Requisito previo: Codificación binaria

Escribimos los números binarios con el subíndice 2. Por ejemplo, 11₂ es 3 y 101₂ es 5. Cada uno de los unos y ceros se llama bit. Decimos que el bit más a la izquierda es el bit más significativo (MSB) y el bit más a la derecha es el bit menos significativo (LSB).

Como mostraremos en breve, durante la conversión a decimal, el bit más significativo se multiplica por el coeficiente más grande y el bit menos significativo se multiplica por el coeficiente más pequeño. Así que si escribimos un número binario de cuatro bits como b₃b₂b₁b₀, b₃ es el MSB y b₀ es el LSB.

El siguiente video ilustra la conversión de 1101₂ a 13:

Como se muestra en el video, un número binario de cuatro bits se puede convertir a un número decimal v con la siguiente fórmula:

v = 8b₃ + 4b₂ + 2b₁ + b₀

Esto también podría escribirse como:

v = 2³b₃ + 2²b₂ + 2¹b₁ + 2⁰b₀

Por ejemplo, 1001₂ = 9, 1010₂ = 10, y así sucesivamente. Para un número binario general de n bits, la conversión es:

v = 2ⁿ⁻¹b₃ + ... + 2¹b₁ + 2⁰b₀

Omitimos la discusión sobre cómo convertir un número decimal a binario. Por ahora, si el lector desea convertir a binario, puede usar la función integrada bin de Python:

Copy
>>> bin(3)
'0b11'
>>> bin(9)
'0b1001'
>>> bin(10)
'0b1010'
>>> bin(1337)
'0b10100111001'
>>> bin(404)
'0b110010100'

Podemos crear un circuito aritmético que afirme que “v es un número decimal con una representación binaria de cuatro bits b₃, b₂, b₁, b₀” usando el siguiente circuito:

Copy
8b₃ + 4b₂ + 2b₁ + b₀ === v

// force the "bits" to be zero or one
b₀(b₀ - 1) === 0
b₁(b₁ - 1) === 0
b₂(b₂ - 1) === 0
b₃(b₃ - 1) === 0

Las signals b₃, b₂, b₁, b₀ están restringidas para ser la representación binaria de v. Si b₃, b₂, b₁, b₀ no son binarias, o no son la representación binaria de v, entonces el circuito no podrá satisfacerse.

Observe que no hay ninguna asignación satisfactoria para las signals (v, b₃, b₂, b₁, b₀) donde v > 15. Es decir, si establecemos b₃, b₂, b₁, b₀ todos a 1, lo máximo que permiten las restricciones, entonces la suma será 15. No es posible sumar nada mayor. En ZK, a esto a veces se le llama range check (comprobación de rango) sobre v. El circuito anterior no solo demuestra la representación binaria de v, sino que también fuerza que v < 16.

Podemos generalizar esto al siguiente circuito que restringe $v < 2^n$ y también nos da la representación binaria de v:

Copy
2ⁿ⁻¹bₙ₋₁ +...+ 2²b₂ + 2¹b₁ + b₀ === v
b₀(b₀ - 1) === 0
b₁(b₁ - 1) === 0
//...
bₙ₋₁(bₙ₋₁ - 1) === 0

Decir que un número v está codificado con como máximo n bits es equivalente a decir que $v < 2^n$.

Para tener una idea de cómo cambia $2^n$ en función de $n$, considere la siguiente tabla:

Tenga en cuenta que el número $2^n$ en binario requiere 1 bit más para almacenarse que el valor $2^n - 1$. Al restringir la cantidad de bits con los que se codifica un número a $n$ bits, se fuerza a que ese número sea menor que $2^n$.

Es útil recordar la relación entre las potencias de $2$ y la cantidad de bits necesarios para almacenarlas.

• $2^n$ requiere $n + 1$ bits para almacenarse. Por ejemplo, $2^0=1_2$, $2^1 = 10_2$, $2^2=100_2$, $2^3=1000_2$ y así sucesivamente.
• $2^{n-1}$ es la mitad de $2^n$ y requiere $n$ bits para almacenarse.
• $2^n − 1$ requiere $n$ bits para almacenarse. Es el valor máximo que podemos almacenar con $n$ bits, cuando todos los bits se establecen en $1$.

Si tomamos un número $n$ y calculamos $2^n$, obtenemos un número de $n + 1$ bits con el bit más significativo en 1, y el resto en cero. $n = 3$ en los ejemplos a continuación:

$2^{n-1}$ es lo mismo que $2^n / 2$. Dado que está escrito como 2 a alguna potencia, sigue teniendo la misma “forma” de un número binario con un MSB de 1 y el resto en cero, pero requerirá $n$ bits para codificarse en lugar de $n + 1$ bits.

$2^n −1$ es un número de $n$ bits con todos los bits establecidos en uno.

Calcular ≥ en binario

Si trabajamos con números binarios de un tamaño fijo, $n$ bits, el número $2^{n-1}$ es especial porque podemos afirmar fácilmente que un número binario de $n$ bits es mayor o igual a $2^{n-1}$ (o menor que él). Llamamos a $2^{n-1}$ el “punto medio”. El siguiente video ilustra cómo comparar el tamaño de un número de $n$ bits con $2^{n-1}$:

Al comprobar el bit más significativo de un número de $n$ bits, podemos saber si ese número es mayor o igual a $2^{n-1}$ o menor que $2^{n-1}$.

Si calculamos $2^{n-1} + \Delta$ y observamos el bit más significativo de esa suma, podemos saber rápidamente si $\Delta$ es positivo o negativo. Si $\Delta$ es negativo, entonces $2^{n-1} + \Delta$ debe ser menor que $2^{n-1}$.

Detectar si $u \ge v$

Si reemplazamos $\Delta$ con $u - v$, entonces el bit más significativo de $2^{n-1} + (u - v)$ nos dice si $u ≥ v$ o $u < v$.

Prevenir el desbordamiento (overflow) en $2^{n-1} + (u - v)$

Si restringimos $u$ y $v$ para que se representen con un máximo de $n - 1$ bits, mientras que $2^{n-1}$ se representa con $n$ bits, entonces no pueden ocurrir underflow (subdesbordamiento) ni overflow (desbordamiento). Cuando tanto $u$ como $v$ se representan con un máximo de $n - 1$ bits, el valor absoluto máximo de $|u - v|$ es un número de $n - 1$ bits.

Vemos que $2^{n-1} + (u - v)$ no puede tener underflow en este caso, porque $2^{n-1}$ es al menos 1 bit más grande que $|u - v|$.

Ahora considere el caso de overflow. Sin pérdida de generalidad, para $n = 4$, es decir, números de cuatro bits, el punto medio es $2^{n-1} = 2^{4-1} = 8$ o $1000_2$. El valor máximo que puede contener $|u - v|$ en este caso, como un número de 3 bits, es $111_2$. Sumar $1000_2 + 111_2$ da como resultado $1111_2$, lo que no es un overflow.

Resumen del circuito aritmético para $u ≥ v$, cuando $u$ y $v$ son números de $n - 1$ bits

• Restringimos $u$ y $v$ para que sean números de un máximo de $n - 1$ bits.
• Creamos un circuito aritmético que codifica la representación binaria de $2^{n-1} + (u - v)$ usando $n$ bits.
• Si el bit más significativo de $2^{n-1} + (u - v)$ es 1, entonces $u \geq v$ y viceversa.

El circuito aritmético final para comprobar si $u \geq v$ es el siguiente. Fijamos $n = 4$, lo que significa que $u$ y $v$ deben estar restringidos a ser números de 3 bits. El lector interesado puede generalizar esto a otros valores de $n$:

Copy
// u and v are represented with at most 3 bits:
2²a₂ + 2¹a₁ + a₀ === u
2²b₂ + 2¹b₁ + b₀ === v

// 0 1 constraints for aᵢ, bᵢ
a₀(a₀ - 1) === 0
a₁(a₁ - 1) === 0
a₂(a₂ - 1) === 0
b₀(b₀ - 1) === 0
b₁(b₁ - 1) === 0
b₂(b₂ - 1) === 0

// 2ⁿ⁻¹ + (u - v) binary representation
2³ + (u - v) === 8c₃ + 4c₂ + 2c₁ + c₀

// 0 1 constraints for cᵢ
c₀(c₀ - 1) === 0
c₁(c₁ - 1) === 0
c₂(c₂ − 1) === 0
c₃(c₃ − 1) === 0

// Check that the MSB is 1
c₃ === 1

Afirmar que una lista está ordenada

Ahora que tenemos circuitos aritméticos para comparar pares de signals, repetimos este circuito para cada par secuencial en la lista y verificamos que esté ordenada.

Resumen de los ejemplos

Hemos mostrado cómo podemos crear un circuito aritmético que modele la solución a los problemas del capítulo anterior.

Ahora podemos generalizar esto para decir que podemos modelar cualquier problema en NP usando un circuito aritmético.

Cómo un circuito booleano puede ser modelado con un circuito aritmético

Cualquier circuito booleano se puede modelar usando un circuito aritmético. Esto significa que podemos definir un proceso para convertir un circuito booleano B en un circuito aritmético A, de tal manera que un conjunto de entradas que satisfacen B se pueda traducir en un conjunto de signals que satisfacen A. A continuación, describimos los componentes clave de este proceso y analizamos un ejemplo de conversión de un circuito booleano específico en un circuito aritmético.

Supongamos que tenemos la siguiente fórmula booleana: out = (x ∧ ¬ y) ∨ z. Esta fórmula es verdadera si (x es verdadero AND y es falso) OR z es verdadero.

Codificamos x, y y z como signals del circuito aritmético y las restringimos para tener valores 0 o 1.

El siguiente circuito aritmético solo se puede satisfacer si x, y y z son cada uno 0 o 1.

Copy
x(x - 1) === 0
y(y - 1) === 0
z(z - 1) === 0

Ahora mostraremos cómo mapear los operadores de un circuito booleano a los operadores de un circuito aritmético, asumiendo que las variables de entrada han sido restringidas a 0 o 1.

Puerta AND

Traducimos el AND booleano t = u ∧ v a un circuito aritmético de la siguiente manera:

Copy
u(u - 1) === 0
v(v - 1) === 0
t === uv

t solo será 1 si tanto u como v son 1, por lo tanto, este circuito aritmético modela una puerta AND. Debido a las restricciones u(u - 1) = 0 y v(v - 1) = 0, t solo puede ser 0 o 1.

Puerta NOT

Traducimos el NOT booleano t = ¬u a un circuito aritmético de la siguiente manera:

Copy
u(u - 1) === 0
t === 1 - u

t es 1 cuando u es 0 y viceversa. Debido a la restricción u(u - 1) === 0, t solo puede ser 0 o 1.

Puerta OR

Traducimos el OR booleano t === u ∨ v a un circuito aritmético de la siguiente manera:

Copy
u(u - 1) === 0
v(v - 1) === 0
t === u + v - uv

Para ver por qué modela la puerta OR, considere la siguiente tabla:

Si u o v son 1, entonces t será al menos 1. Para evitar que t sea igual a 2 (lo cual es una salida inválida para un operador booleano), restamos uv, que será 1 cuando tanto u como v sean 1.

Observe que con todas las puertas anteriores, no necesitamos aplicar una restricción t(t - 1) === 0. La salida t está implícitamente restringida a ser 0 o 1 porque no hay ninguna asignación a las entradas que pueda dar como resultado un valor de 2 o mayor para t.

Transformación de out = (x ∧ ¬ y) ∨ z en un circuito aritmético

Ahora que hemos visto cómo traducir todas las operaciones permitidas de los circuitos booleanos a circuitos aritméticos, veamos un ejemplo de conversión de un circuito booleano a uno aritmético.

Crear las restricciones de 0 1

Copy
x(x - 1) === 0
y(y - 1) === 0
z(z - 1) === 0

Reemplazar ¬ y con el circuito aritmético para NOT

out = (x ∧ ¬ y) ∨ z

out = (x ∧ (1 - y)) ∨ z

Reemplazar ∧ con el circuito aritmético para AND

out = (x ∧ (1 - y)) ∨ z

out = (x(1 - y)) ∨ z

Reemplazar ∨ con el circuito aritmético para OR

out = (x(1 - y)) ∨ z

out = (x(1 - y)) + z - (x(1 - y))z

Nuestro circuito aritmético final para out = (x ∧ ¬ y) ∨ z es:

Copy
x(x - 1) === 0
y(y - 1) === 0
z(z - 1) === 0
out === (x(1 - y)) + z - (x(1 - y))z

Si lo deseamos, podríamos simplificar la última ecuación:

Copy
out === (x(1 - y)) + z - ((x(1 - y))z)
out === x - xy + z - ((x - xy)z)
out === x - xy + z - (xz - xyz)

out === x - xy + z - xz + xyz

También podríamos escribir el circuito aritmético de la siguiente manera sin cambiar el significado:

Copy
x² === x
y² === y
z² === z
out === x - xy + z - xz + xyz

Resumen

Si la solución a cada problema en NP se puede modelar con un circuito booleano y cada circuito booleano se puede transformar en un circuito aritmético equivalente, entonces se deduce que la solución a cada problema en NP se puede modelar con un circuito aritmético.

En la práctica, los desarrolladores de ZK prefieren usar circuitos aritméticos en lugar de circuitos booleanos porque, como se muestra en los ejemplos anteriores, generalmente requieren menos variables para realizar la misma tarea.

No hay necesidad de calcular un circuito booleano y luego transformarlo en un circuito aritmético. Podemos modelar la solución al problema NP con un circuito aritmético directamente.

Próximos pasos

Hemos pasado por alto dos detalles muy importantes en este artículo. Existen otros desafíos que deben abordarse. Por ejemplo:

• No discutimos qué tipo de datos (datatype) usamos para almacenar signals para el circuito aritmético y cómo manejamos el overflow durante la suma o la multiplicación.
• No tenemos forma de expresar el valor 2/3 sin perder precisión. Cualquier representación de coma fija o de coma flotante que elijamos tendrá problemas de redondeo.

Para manejar estos problemas, los circuitos aritméticos se calculan sobre campos finitos: una rama de las matemáticas donde toda suma y multiplicación se realiza módulo un número primo.

La aritmética de campos finitos tiene algunas diferencias sorprendentes con respecto a la aritmética regular introducidas por el operador módulo, por lo que el próximo capítulo las explorará en detalle.

Aprenda más con RareSkills

Aprenda más sobre las pruebas de conocimiento nulo (Zero Knowledge Proofs) en nuestro Libro ZK gratuito. Este tutorial es un capítulo de ese libro.

Problemas de práctica

1. Cree un circuito aritmético que tome las signals x₁, x₂, …, xₙ y se satisfaga si al menos una signal es 0.

2. Cree un circuito aritmético que tome las signals x₁, x₂, …, xₙ y se satisfaga si todas las signals son 1.

3. Un grafo bipartito es un grafo que se puede colorear con dos colores de tal manera que no haya dos nodos vecinos que compartan el mismo color. Diseñe un esquema de circuito aritmético para mostrar que tiene un witness válido de un coloreo con 2 colores (2-coloring) de un grafo. Pista: el esquema de este tutorial debe ajustarse antes de que funcione con un coloreo de 2 colores.

4. Cree un circuito aritmético que restrinja k para que sea el máximo de x, y o z. Es decir, k debe ser igual a x si x es el valor máximo, y lo mismo para y y z.

5. Cree un circuito aritmético que tome las signals x₁, x₂, …, xₙ, las restrinja a ser binarias y genere 1 como salida si al menos una de las signals es 1. Pista: esto es más complicado de lo que parece. Considere combinar lo que aprendió en los dos primeros problemas y usar la puerta NOT.

6. Cree un circuito aritmético para determinar si una signal v es una potencia de dos (1, 2, 4, 8, etc.). Pista: cree un circuito aritmético que restrinja otro conjunto de signals para codificar la representación binaria de v, luego coloque restricciones adicionales sobre esas signals.

7. Cree un circuito aritmético que modele el Problema de la suma de subconjuntos (Subset sum problem). Dado un conjunto de números enteros (asuma que todos son no negativos), determine si hay un subconjunto que sume un valor dado $k$. Por ejemplo, dado el conjunto $\set{3,5,17,21}$ y $k = 22$, hay un subconjunto $\set{5, 17}$ que suma $22$. Por supuesto, un problema de suma de subconjuntos no necesariamente tiene una solución.

   Pista

   
   Use un "interruptor" que sea 0 o 1 si un número es parte del subconjunto o no.

8. El problema del conjunto de cobertura (covering set problem) comienza con un conjunto $S = \set{1, 2, …, 10}$ y varios subconjuntos bien definidos de $S$, por ejemplo: $\set{1, 2, 3}$, $\set{3, 5, 7, 9}$, $\set{8, 10}$, $\set{5, 6, 7, 8}$, $\set{2, 4, 6, 8}$, y pregunta si podemos tomar como máximo $k$ subconjuntos de $S$ de manera que su unión sea $S$. En el problema de ejemplo anterior, la respuesta para $k = 4$ es verdadera porque podemos usar $\set{1, 2, 3}$, $\set{3, 5, 7, 9}$, $\set{8, 10}$, $\set{2, 4, 6, 8}$. Tenga en cuenta que para cada problema, los subconjuntos con los que podemos trabajar se determinan al principio. No podemos construir los subconjuntos nosotros mismos. Si nos hubieran dado los subconjuntos $\set{1,2,3}$, $\set{4,5}$ $\set{7,8,9,10}$, entonces no habría solución porque el número $6$ no está en los subconjuntos.

   Por otro lado, si nos hubieran dado $S = \set{1,2,3,4,5}$ y los subconjuntos $\set{1}, \set{1,2}, \set{3, 4}, \set{1, 4, 5}$ y nos preguntaran si se puede cubrir con $k = 2$ subconjuntos, entonces no habría solución. Sin embargo, si $k = 3$, entonces una solución válida sería $\set{1, 2}, \set{3, 4}, \set{1, 4, 5}$.

   Nuestro objetivo es probar para un conjunto dado $S$ y una lista definida de subconjuntos de $S$, si podemos elegir un conjunto de subconjuntos de tal manera que su unión sea $S$. Específicamente, la pregunta es si podemos hacerlo con $k$ o menos subconjuntos. Deseamos probar que sabemos qué $k$ (o menos) subconjuntos usar codificando el problema como un circuito aritmético.

Publicado originalmente el 23 de abril de 2024