Prueba de propiedad para preservar la privacidad de los tokens de asistencia (PoA) mediante zk-SNARK

Jul 25 2022
Introducción Cuando haya encontrado este artículo, es posible que ya haya encontrado muchos artículos fascinantes que explican zk-SNARK. Si no lo has hecho, salta hasta el final donde enumero los más importantes para principiantes.

Introducción

Cuando haya encontrado este artículo, es posible que ya haya encontrado muchos artículos fascinantes que explican zk-SNARK. Si no lo has hecho, salta hasta el final donde enumero los más importantes para principiantes.

Mientras experimentaba con zk-SNARK, encontré varios obstáculos prácticos, cada uno de los cuales requería horas de revisiones de código y búsquedas en la web. Con lo siguiente quiero ahorrarte ese tiempo, para que puedas enfocarte directamente en la parte práctica. Por lo tanto, lo siguiente representa un tutorial práctico que pretende presentarle rápidamente los zk-SNARK y las posibles formas de aplicarlos. No explicaré qué son los zk-SNARK y cómo funcionan (y, sinceramente, no podría hacerlo con detalles muy precisos), pero intentaré brindarle información práctica que podría necesitar para entrar en el tema. Antes de que podamos comenzar, asegúrese de familiarizarse con SnarkJS , que será un componente clave del siguiente tutorial.

Motivación

A continuación, construimos un token de prueba de asistencia (PoA). Este token puede ser emitido por los organizadores del evento y luego reclamado por los participantes del evento para proporcionarles algo intangible como recordatorio. La parte interesante es que los usuarios pueden reclamar su Token PoA preservando la privacidad, sin tener que revelar su identidad. La clave es la tecnología zk-SNARK. Leí sobre este caso de uso específico en la publicación del blog de Vitalik sobre tokens Soulbound y pensé directamente en una posible implementación.

Este tutorial también puede servir como escaparate de mi reciente propuesta EIP sobre ERC-721 compatibles con zk-SNARK.

flujo de trabajo

Antes del evento:
Primero, los asistentes se registran para el evento y brindan su compromiso al organizador del evento. El compromiso c se genera tomando el hash del secreto s de un asistente y un valor anulador n , tal que c = h(s, n) . Durante el registro, tanto el secreto como el anulador permanecen privados.

Después del evento:
el emisor de los PoA crea un árbol merkle, fuera de la cadena: el tamaño del árbol merkle depende de la cantidad de tokens PoA que le gustaría crear. Las hojas del árbol merkle contienen los compromisos recibidos de los asistentes durante el registro.
Luego, el emisor crea un contrato de Token (código a continuación). El contrato de token es esencialmente un ERC721 extendido, sin embargo, eliminamos la funcionalidad de transferencia. Ya existen EIP para tokens vinculados a cuentas y vinculados a almas que aún se encuentran en una etapa de redacción, por lo tanto, utilizaremos un ERC721 adaptado . Ya existen EIP para tokens vinculados a cuentas ( EIP-4973 ) y tokens vinculados a almas ( EIP-5114).) que aún están en etapa de redacción, por lo que utilizaremos un ERC721 adaptado. Tan pronto como los tokens no transferibles se conviertan en un estándar, adoptaremos el contrato.

Este contrato debe contemplar las siguientes posibilidades:

  • Almacene una raíz Merkle inmutable en una variable de estado
  • Interactuar con un contrato Verifier que eventualmente verifica una prueba zk.
  • Merkle Root Hash — Entrada pública
  • Hash anulador: entrada pública
  • Dirección del destinatario: entrada pública
  • Secreto: entrada privada
  • Anulador — Entrada privada
  • PathElements — Entrada privada
  • PathIndices: entrada privada

Para probar la asistencia, el probador debe poder generar una prueba de merkle: el usuario demuestra su capacidad para recrear la ruta desde una hoja de merkle hasta la raíz utilizando las entradas proporcionadas. Esta técnica ya se ha aplicado en algunos otros proyectos, como TornadoCash o StealthDrop . Consulte los documentos para obtener más detalles, pero en resumen, un usuario proporciona su hoja (compromiso) y la ruta completa a la raíz (PathElements, incluidos los hashes). Luego, el usuario debe decirle al algoritmo si los elementos de ruta provistos están concatenados desde el lado izquierdo o derecho en cada nivel en el árbol merkle antes del hash. Esto se logra a través de una matriz (PathIndices) que contiene 0 y 1, que indican la dirección.

Tenga en cuenta que el secreto y el anulador de los usuarios permanecen privados durante todo el proceso.

Finalmente, el asistente puede ingresar la prueba generada en el contrato de Token discutido, que puede verificarlo. El usuario también ingresa el hash anulador y la dirección del destinatario en el contrato de Token.
Si la prueba es válida y el anulador aún no se ha canjeado, el PoA se emite a la dirección especificada por el usuario . Esta dirección puede no tener ninguna conexión con el participante real. Se debe proporcionar el hash anulador para evitar que los usuarios acumulen varias veces. Cada hash de anulador canjeado se almacena en el contrato.

Aunque los Tokens de PoA pueden no ser transferibles, todos pueden demostrar su asistencia a través del contrato de Token en cualquier momento.

Código

Contrato

Entonces, comencemos con la codificación... Primero, tenemos nuestro contrato de Token. En general, lo derivamos del estándar ERC-721 y le agregamos 4 variables de estado público. Primero, _root contiene el hash raíz de merkle del árbol de merkle generado. El _verifier contiene la dirección del contrato Verifier . El contrato Verifier se genera utilizando snarkjs. Los hashes de anuladores ya canjeados se almacenan en la matriz _nullifierHashes . La variable _tokenId representa un contador creciente.

// SPDX-License-Identifier: MIT
pragma solidity 0.8.8;
import "./verifier.sol";
import "./ERC721.sol";
contract zkExtension is ERC721 {
    bytes32 public _root;
    Verifier public _verifier;
    mapping(bytes32 => bool) public _nullifierHashes;
    uint256 private _tokenId;
constructor(
        string memory name_, 
        string memory symbol_, 
        bytes32 root_,
        Verifier verifier_
        )
        ERC721(name_, symbol_)
    {   
      _root = root_;
      _verifier = verifier_;
    }
function root() public view virtual returns (bytes32) {
    return _root;
  }
// @notice mints PoA to address if nullifierHash is unknown
  // Returns true for valid proofs
  function verify(uint[2] memory a_,
                  uint[2][2] memory b_,
                  uint[2] memory c_,
                  uint[3] memory input_,
                  bytes32 root_,
                  bytes32 nullifierHash_,
                  address recipient_) public returns (bool valid) 
      {
        // Check if right tree
        require(root_ == _root, "Wrong root");
        if (_verifier.verifyProof(a_,b_,c_,input_)) {
            if (!_nullifierHashes[nullifierHash_]) {
              _nullifierHashes[nullifierHash_] = true;
              _mint(recipient_, _tokenId);
              _tokenId += 1;
            }
            return true;
        }
        return false;
      }
}

Circuitos

Vayamos a los circuitos. Primero, usamos el lenguaje circom (Circom 2.0) para definir el circuito aritmético. La creación de circuitos es un proceso muy modular. Cada operación que usamos ya ha sido implementada en las plantillas de Circom 2.0 por otros. Voy a vincular las mejores implementaciones al final de este artículo. Nuestro circuito es bastante sencillo de implementar, porque podemos usar la plantilla MerkleTreeChecker existente , que ya ha sido empleada en TornadoCash, y adaptarla a nuestros requisitos. El circuito se usa para probar que cierta hoja está presente en el árbol merkle. Si es así, esto significa que el propietario del compromiso en realidad se incorporó al árbol merkle del emisor del PoA. En este ejemplo, los nivelesEl parámetro se establece en 1, lo que significa que nuestro árbol merkle consta de solo 2 hojas y la raíz.

pragma circom 2.0.2;
include "../merkle/merkleTree.circom";
include "../merkle/commitmentHasher.circom";
template Main(levels) {
    signal input root;
    signal input nullifierHash;
    signal input recipient; 
    signal input nullifier;
    signal input secret;
    signal input pathElements[levels];
    signal input pathIndices[levels];
    
    component hasher = CommitmentHasher();
    hasher.nullifier <== nullifier;
    hasher.secret <== secret;
    hasher.nullifierHash === nullifierHash;
    
    component tree = MerkleTreeChecker(levels);
    tree.leaf <== hasher.commitment;
    tree.root <== root;
    for (var i = 0; i < levels; i++) {
        tree.pathElements[i] <== pathElements[i];
        tree.pathIndices[i] <== pathIndices[i];
    }
    signal recipientSquare;
    recipientSquare <== recipient * recipient;
}
component main {public [root,nullifierHash,recipient]} = Main(1);

La plantilla de CommitmentHasher tiene el siguiente aspecto (es la misma que usa TornadoCash):

pragma circom 2.0.2;
include "../../node_modules/circomlib/circuits/bitify.circom";
include "../../node_modules/circomlib/circuits/pedersen.circom";
template CommitmentHasher() {
    signal input nullifier;
    signal input secret;
    signal output commitment;
    signal output nullifierHash;
component commitmentHasher = Pedersen(496);
    component nullifierHasher = Pedersen(248);
    component nullifierBits = Num2Bits(248);
    component secretBits = Num2Bits(248);
    nullifierBits.in <== nullifier;
    secretBits.in <== secret;
    for (var i = 0; i < 248; i++) {
        nullifierHasher.in[i] <== nullifierBits.out[i];
        commitmentHasher.in[i] <== nullifierBits.out[i];
        commitmentHasher.in[i + 248] <== secretBits.out[i];
    }
commitment <== commitmentHasher.out[0];
    nullifierHash <== nullifierHasher.out[0];
}

Como prometí, este será un tutorial práctico, por lo que también quiero compartir algunas líneas de código que se pueden usar para probar toda la configuración:

Necesitamos algún marco que nos permita generar un árbol Merkle para probar. La implementación del árbol Merkle debe admitir hashes MIMC, ya que también usamos hashes MIMC en nuestro circuito. Usamos la implementación de árbol de merkle fijo de TornadoCash para eso, que me pareció perfecto para este ejemplo.

Lo construimos usando Node v18.4.0:

const assert = require('assert')
const crypto = require('crypto')
const ethers = require('ethers')
const { mimcHash } = require('./mimc');
const circomlib = require('circomlib')
const MerkleTree = require('fixed-merkle-tree')
const leBuff2int = require("ffjavascript").utils.leBuff2int;
/** Generate random number of specified byte length */
const rbigint = nbytes => leBuff2int(crypto.randomBytes(nbytes))
/** Compute pedersen hash */
const pedersenHash = data => circomlib.babyJub.unpackPoint(circomlib.pedersenHash.hash(data))[0]
const mimcsponge = circomlib.mimcsponge
/** BigNumber to hex string of specified length */
function toHex(number, length = 32) {
  const str = number instanceof Buffer ? number.toString('hex') : BigInt(number).toString(16)
  return '0x' + str.padStart(length * 2, '0')
}
/**
 * Create deposit object from secret and nullifier
 */
function createDeposit({ nullifier, secret }) {
  const preimage = Buffer.concat([nullifier.leInt2Buff(31), secret.leInt2Buff(31)])
  const commitment = pedersenHash(preimage)
  const commitmentHex = toHex(commitment)
  const nullifierHash = pedersenHash(nullifier.leInt2Buff(31))
  const nullifierHex = toHex(nullifierHash).toString()
  return { nullifier, secret, preimage, commitment, commitmentHex, nullifierHash, nullifierHex }
}
console.log(rbigint(31));
note = createDeposit({
        nullifier: 70468531690246127597324659426162022323359627919521679359003215289346912273n,
        secret: 60468531690246127597324659426162022323359627919521679359003215289346912273n,
      })
console.log(note)
const my_commitment = note.commitment
const my_recipient = "0xAb5801a7D398351b8bE11C439e05C5B3259aeC9B"
// Merkle tree
const merkleTreeLevels = 1;
const merkleTreeCommitments = [my_commitment,my_commitment];
const getPath = address => {
  const merkleTree = new MerkleTree(merkleTreeLevels, 
                                    merkleTreeCommitments, 
                                  { hashFunction: mimcHash(123) });
  let index = merkleTreeCommitments.findIndex(leaf => leaf === address);
  if(index < 0) return null;
  const { pathElements, pathIndices } = merkleTree.path(index);
  return [merkleTree.root(), pathElements, pathIndices];
};
function Uint8Array_to_bigint(x) {
  var ret = 0n;
  for (var idx = 0; idx < x.length; idx++) {
    ret = ret * 256n;
    ret = ret + BigInt(x[idx]);
  }
  return ret;
}
const fromHexString = hexString => new Uint8Array(hexString.match(/.{1,2}/g).map(byte => parseInt(byte, 16)));
const intToHex = intString => ethers.BigNumber.from(intString).toHexString();
const hexStringTobigInt = hexString => {
  return Uint8Array_to_bigint(fromHexString(hexString));
};
function generateProofInputs(secret) {
  const val = getPath(secret);
  if (!val) return null;
  const [root, pathElements, pathIndices] = val;
  console.log("Hex root:", intToHex(root.toString()));
  const input = {
    root: root.toString(),
    nullifierHash: note.nullifierHash.toString(),
    pathElements: pathElements.map(x => x.toString()),
    pathIndices: pathIndices,
    secret: note.secret.toString(),
    nullifier: note.nullifier.toString(),
    recipient: hexStringTobigInt(my_recipient).toString()
  };
return input;
}
var commitment = my_commitment;
var inputs = generateProofInputs(commitment);
console.log("Inputs:",JSON.stringify(inputs));

Para proporcionarle directamente un input.json de ejemplo para jugar, consulte mi Github . Allí también encontrarás el código de todo el proyecto.

Finalmente, como prometí, permítanme brindarles algunos de los recursos más valiosos que usé para aprender sobre zkSNARK:

  1. https://consensys.net/blog/developers/introduction-to-zk-snarks/
  2. https://docs.tornado.cash/general/how-does-tornado.cash-work
  3. https://docs.tornado.cash/tornado-cash-classic/circuits
  4. https://blog.iden3.io/first-zk-proof.html
  5. https://vitalik.ca/general/2021/01/26/snarks.html
  6. https://vitalik.ca/general/2022/06/15/using_snarks.html
  7. https://github.com/nalinbhardwaj/stealthdrop
  8. https:///@imolfar/why-and-how-zk-snark-works-1-introduction-the-medium-of-a-proof-d946e931160
  1. https://github.com/iden3/snarkjs
  2. https://github.com/iden3/circom
  3. https://github.com/iden3/circomlib
  4. https://github.com/0xPARC/circom-ecdsa

© Copyright 2021 - 2022 | unogogo.com | All Rights Reserved