Prueba de conocimiento cero: construcción de circuito y ejemplo de prueba basado en libsnark

La jerarquía del código de la biblioteca libsnark es muy clara. libsnark también ofrece una imagen completa de los algoritmos relacionados con SNARK, varias relaciones, lenguaje, sistema de prueba. Para generar mejor los circuitos R1CS, libsnark abstrae la protoplaca y el dispositivo, lo cual es conveniente para que los desarrolladores construyan circuitos rápidamente. Antes de leer el código de muestra, lea detenidamente el análisis del código fuente de libsnark: Prueba de conocimiento cero: análisis del código fuente de libsnark

Lo único que lamento es que libsnark no dio un ejemplo completo de construcción de circuitos. Los principiantes que quieren construir sus propios circuitos están un poco confundidos al principio.

Para que sea más fácil para los principiantes escribir sus propios circuitos, un colega escribió un ejemplo de cómo construir un circuito basado en libsnark y generar y verificar el circuito:

https://github.com/StarLI-Trampilla/libsnark_sample

Los principiantes pueden desarrollar sus propios circuitos basados ​​en este ejemplo. Se elige un árbol de Merkle como ejemplo de circuito porque la estructura de datos del árbol de Merkle se usa mucho en la aplicación de pruebas de conocimiento cero.

Este ejemplo construye un circuito de verificación de un camino Merkle, genera y verifica pruebas. La profundidad del árbol merkle es 3 y el cálculo del árbol merkle utiliza la función hash sha256. La estructura del código es relativamente clara y main.cpp en el directorio merkle es la función principal. El merklecircuit.h bajo el directorio de circuitos es la implementación del circuito. Todo el proyecto está compilado con cmake.

El circuito se llama MerkleCircuit y se basa principalmente en dos dispositivos: merkle_authentication_path_variable y merkle_tree_check_read_gadget. merkle_authentication_path_variable proporciona una ruta en el árbol Merkle. merkle_tree_check_read_gadget comprueba que dado un nodo hoja, se puede calcular la raíz correcta.

Para implementar un circuito, implemente principalmente dos funciones de interfaz:

generate_r1cs_constraints: genera R1CS, el circuito es relativamente simple, solo deja que los dos dispositivos dependientes generen R1CS.

generar_r1cs_testigo - asigna valores a todas las variables. En este circuito, las variables que deben asignarse son raíz, hoja (nodo hoja), la ruta de Merkel que coincide con el nodo hoja y la información de la dirección correspondiente a la ruta de Merkel (es decir, la posición del nodo en cada capa). , izquierda o derecha) .

La parte más complicada de todo el circuito es el constructor del circuito, la aplicación de variables y la creación de dispositivos. Entre ellos, el punto clave es la función set_input_sizes. En el marco de libsnark, se utiliza un modelo simple para distinguir entre variables públicas y privadas. A través de la función set_input_sizes, establezca las primeras variables como variables públicas.

pb.set_input_sizes(root_digest->digest_size); es decir, la variable abierta de este circuito es el número de bits de raíz.

Después de determinar la implementación del circuito, observe la función principal, cómo generar y verificar la prueba.

Algunos tipos requeridos para el cálculo del árbol merkle se definen en la función principal:

El valor predeterminado de FieldT es el Fr de la curva elíptica bn256, y el cálculo del árbol de Merkle utiliza el algoritmo sha256.

Configuración 3.1

Implementó la función generate_read_keypair para generar pk/vk. Eche un vistazo más de cerca a la función generate_read_keypair, la lógica es simple y clara: construya MerkleCircuit, después de generar R1CS, llame a r1cs_gg_ppzksnark_generator para generar pk/vk.

pk se almacena en el archivo merkle_pk.raw y vk se almacena en merkle_vk.raw.

3.2 probar

La lógica de prueba primero construye un árbol de Merkle completo a partir de los parámetros de entrada y selecciona la ruta de Merkle en función de la entrada. La prueba es generada por la función generate_read_proof. La lógica de la función también es relativamente clara:

Construya MerkleCircuit y establezca el valor de cada variable después de generar R1CS. Luego genere una prueba a través de r1cs_gg_ppzksnark_prover.

3.3 Verificar

Sobre la base de conocer vk, prueba e información pública (raíz), llame a la interfaz de r1cs_gg_ppzksnark_verifier_strong_IC para completar la verificación. Esta es la lógica de la función verificar_lectura_prueba.

Antes de compilar, sincronice la biblioteca libsnark de la que depende el proyecto:

git submodule update --init --recursive4.1 compilar

mkdir build; cd build; cmake .. Una vez completada la compilación, el archivo ejecutable de merkle se generará en el directorio de merkle.

4.2 Configuración de confianza

./merkle setup4.3 generar prueba

./merkle prove [data1] [data2] [data3] [data4] [data5] [data6] [data7] [data8] [index]prove comando, debe proporcionar los 8 nodos de hoja del árbol merkle original de 3 capas y especificar la ruta correspondiente al nodo de hoja que debe certificarse (indicado por índice).

4.4 Verificación

./merkle verificar [raíz] Entre ellos, la información raíz es la información raíz impresa durante el proceso de generación en prueba (también información pública). Si se pasa la verificación, significa que hay una ruta merkle que puede generar root, aunque no hay información específica sobre la ruta.

Resumen:

El nivel de código de la biblioteca libsnark es muy claro, y el protoboard y el gadget están abstractos, lo que es conveniente para que los desarrolladores construyan circuitos rápidamente. Este artículo da un ejemplo de un circuito completo desarrollado en base a la biblioteca libsnark. El ejemplo implementa la verificación de una ruta Merkle de un árbol Merkle de 3 capas. Entre ellos, el árbol Merkle adopta la función hash de sha256.

Tags：

Intercambio de Ethereum