Pruebas de conocimiento cero (zk): ¿Qué son los zk-STARK y cómo funcionan?

1. ¿Qué es?

El sistema de prueba de reservas (PoR) zk-STARK emplea la teoría STARK, una solución matemática compleja. zk-STARK significa: Zero-Knowledge Scalable Transparent Argument of Knowledge, una tecnología de prueba cripto basada en la [idea] de Vitalik (https://vitalik.eth.limo/general/2022/11/19/proof_of_solvency.html) para hacer cumplir la integridad y la privacidad de los cálculos en blockchains. En este artículo, presentaremos cómo funciona y explicaremos el concepto matemático general, pero si estás interesado en profundizar más, echa un vistazo aquí o aquí.

¿Como funciona?

Figura 1. Tabla de seguimiento de ejecución y árbol de Merkle construidos para zk-STARK PoR

Paso 1: restricciones de construcción

Para demostrar la responsabilidad de nuestro exchange, presentamos tres afirmaciones:

Afirmación 1: Acumulamos los valores de cada usuario correctamente, incluido el valor de cada criptomoneda y el valor neto de cada usuario

Afirmación 2: El intercambio no ha creado un usuario virtual cuyo valor neto sea negativo para reducir la responsabilidad total del intercambio (un usuario individual que tenga saldos negativos es aceptable solo si su valor neto es superior a 0)

Afirmación 3: El valor total que el intercambio reclama representa a cada usuario, por lo que cada usuario debería poder verificar la inclusión de su valor neto en el valor total.

Para probar y verificar las afirmaciones anteriores, necesitamos crear restricciones como:

Afirmación 1: Restricción de Saldo Total (Restricción de un saldo total correcto)

uts: tamaño del rastro del usuario, que es el número de filas de rastros incluidos en los datos de cada usuario.

suma: saldo total del usuario

N: número de usuarios

Afirmación 2: Restricción no negativa (Restricción de patrimonio neto positivo)

Afirmación 3: Restricción de inclusión (Restricción de inclusión de todo el saldo de la cuenta del cliente)

De acuerdo con las restricciones anteriores, creamos una tabla de seguimiento para usar y verificar los saldos totales y la no negatividad a través de inspecciones de muestreo. Así es como se construye la tabla de seguimiento (por ejemplo, 3 usuarios cuyo valor máximo en USD es inferior a 4^6 = 4096):

1）Inicializamos una tabla con 32 filas y 5 columnas, y llenamos los valores e ID del usuario en

fila, donde k % 8 = 6, y

. Cada 8 filas es un bloque, y la información de activos del usuario ahora está en

detrás de cada bloque. El primer usuario recibe saldos 0 virtuales, por lo que podemos publicarlo para demostrar que la acumulación de valores no parte de un valor negativo.

2）Acumulamos valores de activos de usuario uno por uno y completamos el resultado en

filas donde k % 8 = 7, y

, que son las últimas filas de cada bloque

3）Seguimos dividiendo el valor total de cada usuario por 4 fila por fila de

detrás de cada bloque. Lo hacemos para mantener el valor neto del usuario no negativo comprobando si las primeras filas son cero para cada bloque. Si alguien tiene un valor neto negativo, la primera fila de su bloque no será cero porque un valor negativo (-x) resultará ser (p - x) en un campo finito

, que es un valor positivo muy grande.

4）Introducimos números aleatorios para cada usuario y llenamos los espacios en blanco en la tabla con 0

Paso 2: Extensión polinomial de bajo grado Utilizando las restricciones polinómicas anteriores, podemos obtener un polinomio de seguimiento computacional de longitud uts * N. Por razones de seguridad, realizamos el compromiso con el polinomio en un dominio de evaluación más grande, con el factor de amplificación del dominio como factor de_extensión.

En el caso anterior, podríamos calcular un polinomio p(x) a partir de I(x). Cuando usamos un factor de_extensión de 8, calcularemos otros 32(8-1)* puntos en p(x).

Dado que dos polinomios diferentes con grado D compartirán como máximo puntos D, un par de polinomios de ejemplo con un polinomio válido (que satisfaga las restricciones anteriores) y un polinomio falso con grado D (que no satisfaga las restricciones anteriores) compartirán como máximo puntos D. Eso significa que un polinomio falso tiene la posibilidad de

para pasar una inspección de muestreo aleatorio. Si hacemos la inspección de muestreo n veces, la probabilidad disminuirá a

.

Implementamos la extensión_factor predeterminado como 16 y el tiempo predeterminado de inspección de muestreo como 16, por lo que el nivel de seguridad será de 80 bits.

Paso 3: compromiso polinomial Calculamos el valor hash de la traza de cálculo y el saldo de usuario correspondiente, la identificación de usuario y el valor del polinomio de restricción correspondiente para cada fila, y generamos un árbol de Merkle. La raíz de Merkle es el valor de compromiso del polinomio.

Paso 4: generar prueba de muestreo Utilizando la raíz de Merkle como fuente aleatoria, muestreamos los datos. Para evitar la fuga de datos de rastreo de cálculo, evitamos los datos con un índice de *k ** extensión_factor durante el muestreo y generar la ruta de prueba de Merkle correspondiente al índice de muestreo.

Realizamos las inspecciones de muestreo para verificar si el polinomio comprometido es un polinomio válido que satisface las restricciones enumeradas en el Paso 1. Como se especifica en el Paso 2, los tiempos de las inspecciones de muestreo afectarán la posibilidad de que la manipulación o la manipulación tengan éxito.

Paso 5: generar prueba de bajo grado.

Podemos controlar la probabilidad de manipulación o alteración exitosa a través de la inspección de muestras. Sin embargo, existe una condición, como se mencionó en el Paso 2, de que debemos asegurarnos de que el grado del polinomio que se está verificando no sea mayor que el grado de un polinomio válido. Para mejorar la eficiencia de la prueba, combinamos linealmente todos los polinomios de restricción en un polinomio y generamos una prueba de bajo grado para el mismo. Los coeficientes de combinación también se generan utilizando la raíz de Merkle como fuente aleatoria.

Por ejemplo, si queremos probar que p0(x), p1(x) y p2(x) no son más de D grados, podemos generar 2 coeficientes aleatorios a partir de la raíz de Merkle generada en el Paso 3, y calcular el polinomio lineal l(x) como:

k0 = hash(raíz "0") k1 = hash(raíz "1") l(x) = k0 * p0(x) + k1 * p1(x) + p2(x)

Si se pudiera demostrar que l(x) no es mayor que D, entonces la probabilidad de que el grado de cualquiera de p0(x), p1(x) y p2(x) sea mayor que D será cercana a 0.

Paso 6: verificación del saldo total En primer lugar, verificamos la prueba de bajo grado generada en el Paso 5.

Luego se realiza una verificación abierta adicional en los datos muestreados generados en el Paso 4. Primero con el fin de verificar que los datos sean consistentes con el compromiso polinomial y segundo para verificar que los datos satisfagan las restricciones construidas en el Paso 1. Finalmente, se verifican los coeficientes de combinación del polinomio de prueba de bajo grado.

Paso 7: generar prueba de inclusión de usuario Para demostrar que un usuario específico está incluido en el importe total reclamado por el intercambio, proporcionamos el seguimiento calculado del usuario, el saldo del usuario, la identificación del mismo y un número aleatorio correspondiente al índice del usuario. También proporcionamos la ruta Merkle correspondiente a estos datos.

Paso 8: verificación del usuario de la prueba de inclusión El usuario verifica su saldo, ID, calcula el valor hash de los datos correspondientes a su índice y verifica el valor hash en el nodo hoja del árbol de Merkle usando la ruta de Merkle provista.

2. ¿Cómo realizar la autoverificación de Prueba de Reservas (PoR)?

2.1 Verificar la restricción de inclusión de zk-STARK

Teoría de la Verificación

Siguiendo el procedimiento STARK, calcularemos la tabla de seguimiento de ejecución de todos los activos del usuario como se muestra a continuación, y codificaremos la información de cada usuario como una tabla de seguimiento que se convierte en una hoja de árbol de Merkle, luego enviaremos las hojas a una raíz de Merkle que se publicará durante cada ronda de auditoría PoR.

Para verificar si tus activos están incluidos en la raíz, te proporcionaremos la ruta de Merkle para la verificación. Primero puedes calcular tu hoja mediante el hash de la información de sus activos, luego verifica si tu hoja es una hoja válida en el árbol Merkle y la raíz que publicamos.

Por ejemplo, en la Figura 1, el usuario con una identificación de id_k calculará hashk = hash("20" "15" "5" "id_k" "99821"), y los demás datos en el marco del cuadrado rojo serán la verificación de ruta de Merkle. Se proporciona una herramienta de código abierto para que los usuarios realicen esta verificación.

Dado que las hojas del árbol Merkle son hashes, ninguna información privada se filtrará a otros.

Cómo verificar:

1）Para verificar si el saldo de activos de tu cuenta se ha incluido como una hoja Merkle de zk-STARK, inicia sesión en tu cuenta OKX, visita "Auditorías" para ver auditorías recientes, haz clic en "Detalles" para ver tus datos de auditoría.

2）Obtén los datos que necesitas para la verificación manual haciendo clic en "Copiar datos".

3）Después de hacer clic en "Copiar datos", abre el editor de texto (por ejemplo, usando un cuaderno), luego pega y guarda la cadena JSON como un archivo. El archivo debe terminar con el nombre "_inclusión_prueba.json". La cadena JSON contiene el saldo de tu cuenta y una instantánea de la ruta Merkle, luego guarda el archivo en una nueva carpeta.

El texto JSON se muestra a continuación:

{ "lote_inclusión_prueba": { "lote_márbol_raíz": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5", "usuario_identificación": "47db1d296a7c146eab653591583a9a4873c626d8de47ae11393edd153e40f1ed", "total_valor": 138312291, "BTC": 2152907, "ETH": 909757, "USDT": 2319557, "número_aleatorio": "e7b7a5a6fdba87a58559aed4fca66fb63d3d9395ce0d51bda40fcd35893391ac", ruta_merkle": [ "5e3dd0ad776b15743076405d53e12af8fdac85c446bcc6c2eb8cab0e0e0c24f9", "9dd5fcb0f3835b10772a7baabe7a074ed0b6947f7284e2d7ce5a84c3b5b394da", "973186c5ea69bdc06c0c786cfae76173a89e0989bd759e1b2c37fdd317c70fe2", "0c7ea3dd9bc0a15019b9ace6cf003befa31133ee84728d21bf67aa984ef1b60a", "2adf4a58ccec7a44ed3a3f8bd365c61eac7d25c55524e69a31c6665769b7962a", "4cddf667adbfa51e1b999e39a2009dcc9786385d9f3e240919f763e4db6f3609", "4e841f9b5c2641759572fdfaf66c518b191e89b7a4745f179c046fef1eb9c374", "cc12d77e7d13ee3c57064697dfef230064efaaf5b6ccf22a5ef5b7a2602632ab", "ead6745e91b88021aeecddd8d014ea26ba26f42c4d5286ef8e196085d3757f62", "1a583279e243ddc0a36bf870b5af70f2e52f059faeb5f3757d0d1903770371e8", "5c1729384a2f2c8c434f3b34e99d6152aab42093c4f68aab638eaa212e799933", "e154c1011883b2cea377c6bc820a21ac01d9d792ce3e1f376f35c1b29df04167" ] }, "tronco_inclusión_prueba": { "tronco_márbol_raíz": "9b61d44f4f3de6b284d95a844dee9327d5e2091ac7e6b6f67ca10bd866617290", "lote_identificación": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5", "total_valor": 2007657936, "BTC": 18915744, "ETH": 21522734, "USDT": 21268768, "número_aleatorio": "c93d3517d691564f3cc8e1eee6634ba7e0f59125aa89cd6984677459ac5f8164", ruta_merkle": [ "1082ec62ad0bd2b2b2c38a08f4b0de2f9aa77b387c611b927d203deb9bc97376", "a57a391c137877993cd61ca4ad57bb1754bf8776fd207e630c362b8560fbb34b", "413cba43d7f7236b5ce21fe951583660277507250ecbabca6a1ac6e9ac66bb5b", "d87e2c64c34700195e322967ebbbb282810671320d083029fb9e46f92474d47b", "85438a308f8d668779dbdb462437434f8f9d551229e8ebb2235605fe18cf97f6", "d1cbf91c33b4cb0366877c4c805548401887f2a428c7297d0c4d97fa0f936cec", "147fccf20ff7010d2ba162333f62200dce116d337230ee73f7c8bc2abcba148e", "0901034401e6b6fa7de911d658ebc9b10c6a64c16a5450a22e390859ae87e1c4", "b2e3525d853749ca2edfa718cd4f12ba26a0f645dfb0d5512d42c67fc74d0a1a", "ad34d5acf98f7e6234d132d578f823e7bd8410d1850db76a55dd794ce388b2c2", "7e81326a45550eea02398a8459dbd5d73d6d90b58268ce4453231cf3077f4fdf", "239263d4cf31258c7910fe7abe8cc23d1b71cf73e796a958e60d3fafe095e49d", "bb44ebaed47333c967f79c48cb3e0106fe64f55411f94181daa4c55f2a563e43" ] } }

4. Descarga la herramienta de verificación de código abierto OKX zk-STARKValidator

5）Guarda la herramienta de verificación de código abierto OKX zk-STARKValidatory el archivo de cadena JSON juntos en la nueva carpeta del paso 3. En nuestro caso: colocamos la herramienta y el archivo de datos en la carpeta "Descargas", denominada "prueba de reserva" que se muestra a continuación:

6）Abre el zk-STARKValidator, este ejecutará automáticamente el archivo de cadena JSON que has guardado en la carpeta.

7）Comprueba el resultado

• Si supera la verificación, se mostrará el resultado "Validación de restricción de inclusión aprobada":

  

• Si no supera la verificación, se mostrará el resultado "Validación de restricción de inclusión fallida":

  

2.2 Verifica el saldo total de zk-STARK y la restricción no negativa

Cómo verificar:

Para verificar y probar que los activos que afirmamos tener son verdaderos y que ningún usuario tiene un patrimonio neto negativo, visita nuestros "Archivos de auditoría" y descarga los archivos "zk-STARK" en el Informe de responsabilidad, luego guárdalo en una nueva carpeta.

Descomprime el archivo descargado y habrá una carpeta de "datos de prueba de suma", que incluye miles de carpetas de sucursales y una carpeta troncal. Cada carpeta contiene dos archivos JSON llamados "suma_prueba.json" y 'suma_archivos value.json'.

Descarga la herramienta de verificación de código abierto OKX zk-STARKValidator

Guarda la herramienta de verificación de código abierto OKXzk-STARKValidator y la carpeta "datos de prueba de suma" juntos en la carpeta recién creada del paso 1. En nuestro caso: colocamos la herramienta y el archivo de datos en la carpeta "Descargas", denominada "prueba de reserva" que se muestra a continuación:

Abre el zk-STARKValidator, este ejecutará automáticamente el archivo "datos de prueba de suma" que has guardado en la carpeta.

Comprueba los resultados

Si supera la verificación, se mostrará el resultado "Suma total y restricción de validación no negativa superada":

Si no supera la verificación, se mostrará el resultado "Suma total y restricción de validación no negativa no superada":