Cânone de Conhecimento Zero

Nota do Editor: A criptografia a16z teve uma longa série do “armas”, do nosso Cânone DAO ano passado para o nosso Cânon NFT antes (e antes disso nosso original Cânone de Criptografia) — certifique-se de se inscrever em nosso boletim semanal web3 para mais atualizações, bem como outros recursos selecionados.

Soluçoa seguir, selecionamos um conjunto de recursos para quem busca entender, aprofundar e construir com todas as coisas conhecimento zero: tecnologias poderosas e fundamentais que detêm as chaves para a escalabilidade do blockchain e representam o futuro dos aplicativos que preservam a privacidade e inúmeras outras inovações que estão por vir. Se você tiver sugestões de peças de alta qualidade para adicionar, avise-nos @a16zcrypto.

Os sistemas de prova de conhecimento zero existem há décadas: sua introdução por Shafi Goldwasser, Silvio Micali e Charles Rackoff em 1985 teve um efeito transformador no campo da criptografia e foi reconhecido pelo ACM Turing Award concedido a Goldwasser e Micali em 2012. Como este trabalho – incluindo sua mudança da teoria para a prática e aplicações em criptografia/web3 hoje – está sendo feito há décadas, também compartilhamos pela primeira vez em nossa série de cânones uma parte dois (por enquanto, incluída aqui abaixo): uma lista de leitura anotada por Justin Thaler, seguindo a parte um abaixo.

Agradecimentos: Obrigado também a Michael Blau, Sam Ragsdale e Tim Roughgarden.

Fundações, antecedentes, evoluções

Alguns desses artigos também são mais sobre criptografia em geral (nem todo conhecimento zero em si), incluindo problemas ou avanços importantes que são abordados por provas de conhecimento zero hoje: como garantir privacidade e autenticação em redes abertas.

Novas direções em criptografia (1976)
por Whitfield Diffie e Martin Hellman
https://ee.stanford.edu/~hellman/publications/24.pdf

Um método para obter assinaturas digitais e sistemas criptográficos de chave pública
por Ronald Rivest, Adi Shamir, Leonard Adelman
https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=856E21BC2F75800D37FD611032C30B9C?doi=10.1.1.40.5588&rep=rep1&type=pdf

Protocolos para criptosistemas de chave pública (1980)
por Ralph Merkle
http://www.merkle.com/papers/Protocols.pdf

Comunicações seguras em canais inseguros (1978)
por Ralph Merkle
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

Uso de curvas elípticas em criptografia (1988)
por Victor Miller
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

A complexidade do conhecimento de sistemas de prova interativos (1985)
por Shafi Goldwasser, Silvio Micali, Charles Rackof
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

Computacionalmente provas de som (2000)
por Silvio Micali
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

Da resistência extraível à colisão a argumentos sucintos e não interativos de conhecimento [SNARKs], e de volta (2011)
por Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
https://eprint.iacr.org/2011/443.pdf

Argumento eficiente de conhecimento zero para correção de um embaralhamento (2012)
por Stephanie Bayer e Jens Groth
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Conhecimento zero sucinto não interativo para uma arquitetura von Neumann (2013)
por Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer e Madars Virza
https://eprint.iacr.org/2013/879.pdf

Integridade computacional segura escalável, transparente e pós-quântica (2018)
por Eli Ben-Sasson, Iddo Bentov, Yinon Horesh e Michael Riabzev
https://eprint.iacr.org/2018/046.pdf

Argumentos de conhecimento zero de moeda pública com (quase) despesas mínimas de tempo e espaço (2020)
por Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum e Pratik Soni
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

Visões gerais e introduções

Provas, argumentos e conhecimento zero — Uma visão geral da computação verificável e provas e argumentos interativos, protocolos criptográficos que permitem a um provador fornecer uma garantia a um verificador de que o provador executou um cálculo solicitado corretamente, incluindo conhecimento zero (onde as provas não revelam nenhuma informação além de sua própria validade) . Os argumentos Zk têm uma infinidade de aplicações em criptografia e deram um salto da teoria para a prática na última década.
por Justin Thaler
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

Uma evolução de modelos para provas de conhecimento zero — Uma revisão de provas de conhecimento zero, onde Meiklejohn (University College London, Google) analisa os aplicativos que estão impulsionando seu desenvolvimento, os diferentes modelos que surgiram para capturar essas novas interações, as construções que podemos realizar e o trabalho deixou de fazer.
por Sarah Meiklejohn
https://www.youtube.com/watch?v=HO97kVMI3SE

Sessões de quadro branco ZK - módulos introdutórios
com Dan Boneh et al.
https://zkhack.dev/whiteboard/

Segurança e privacidade para criptografia com zkps — pioneirismo na prova de conhecimento zero na prática; o que são zkps e como eles funcionam… incluindo “demo” de palco ao vivo
por Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

Principais tópicos de tecnologia, explicados — incluindo definições e implicações de conhecimento zero em geral
por Joe Bonneau, Tim Roughgarden, Scott Kominers, Ali Yahya, Chris Dixon
https://web3-with-a16z.simplecast.com/episodes/hot-research-summer-blockchain-crypto-tech-topics-explainers-overviews-seminar-videos

Como a próxima camada de privacidade consertará uma web quebrada
por Howard Wu
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

Introdução ao zkSNARKs
com Howard Wu, Anna Rose
https://zeroknowledge.fm/38-2/

Por que e como o zk-SNARK funciona: uma explicação definitiva
por Maksym Petkus
https://arxiv.org/pdf/1906.07221.pdf

Uma introdução às provas de conhecimento zero
por Fredrik Harrysson e Anna Rose
https://www.zeroknowledge.fm/21 [+ resumo escrito em outro lugar SUA PARTICIPAÇÃO FAZ A DIFERENÇA]

Zk-SNARKs: sob o capô
por Vitalik Buterin
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
parte 1, parte 2, parte 3

Velocidade descentralizada — em avanços em provas de conhecimento zero, hardware descentralizado
por Elena Burger
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

Pesquisa zk de ponta — com pesquisador zk na Ethereum Foundation
com Mary Maller, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/232-2/

Explorando a pesquisa zk — com o diretor de pesquisa da DFINITY; também atrás de avanços como Groth16
com Jens Groth, Anna Rose, Kobi Gurkan
https://zeroknowledge.fm/237-2/

SNARK pesquisa e pedagogia — com um dos cofundadores da ZCash e Starkware
com Alessandro Chiesa, Anna Rose
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

Mergulhos profundos, guias de construtores

Fundamentos de provas probabilísticas — um curso com 5 unidades de provas interativas e mais
por Alessandro Chiesa
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

STARKs - parte I, II, III
por Vitalik Buterin
https://vitalik.ca/general/2017/11/09/starks_part_1.html
https://vitalik.ca/general/2017/11/22/starks_part_2.html
https://vitalik.ca/general/2018/07/21/starks_part_3.html

Anatomia de um STARK — um tutorial de seis partes explicando a mecânica de um sistema à prova STARK
por Alan Szepieniec
https://aszepieniec.github.io/stark-anatomy/

Projeto SNARK, parte 1 — pesquisa, uso em rollups, mais
por Justin Thaler
https://www.youtube.com/watch?v=tg6lKPdR_e4

Projeto SNARK, parte 2 — rollups, desempenho, segurança
por Justin Thaler
https://www.youtube.com/watch?v=cMAI7g3UcoI

Medindo o desempenho SNARK — frontends, backends, mais
por Justin Thaler
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

Entendendo o PLONK
https://vitalik.ca/general/2019/09/22/plonk.html

O sistema à prova de conhecimento zero PLONK — série de 12 vídeos curtos sobre como o PLONK funciona
por David Wong
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

De AIRs a RAPs — como funciona a aritmetização no estilo PLONK
por Ariel Gabizon
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

Verificações de vários conjuntos em PLONK e Plookup
por Ariel Gabizon
https://hackmd.io/@arielg/ByFgSDA7D

Projeto Halo2 — do ECC
https://zcash.github.io/halo2/design.html

Plonky2
https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf

Aplicativos e tutoriais: prova de conceitos, demonstrações, ferramentas, mais

Zk aplicado - recursos de aprendizagem
por 0xPARC
https://learn.0xparc.org/materials/intro

Um ambiente de desenvolvimento online para zkSNARKs — zkREPL, um novo conjunto de ferramentas para interagir com a pilha de ferramentas Circom no navegador
por Kevin Kwok
https://zkrepl.dev (+ tópico explicativo SUA PARTICIPAÇÃO FAZ A DIFERENÇA)

Programas aritméticos quadráticos de zero a herói
por Vitalik Buterin
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

Em zkEVMs
com Alex Gluchowski e Anna Rose
https://zeroknowledge.fm/175-2/

Diferentes tipos de zkEVMs
por Vitalik Buterin
https://vitalik.ca/general/2022/08/04/zkevm.html

Aprendizado de máquina ZK — tutorial e demonstração para colocar uma rede neural em um SNARK
por Horace Pan, Francis Ho e Henri Palacci
https://0xparc.org/blog/zk-mnist

Em idiomas ZK
com Alex Ozdemir e Anna Rose
https://zeroknowledge.fm/172-2/

Dark Forest — aplicando criptografia zk a jogos — um jogo RTS (estratégia em tempo real) totalmente descentralizado e persistente
https://blog.zkga.me/announcing-darkforest

ZKPs para engenheiros — uma olhada nos ZKPs da Floresta Negra
https://blog.zkga.me/df-init-circuit

Um mergulho no conhecimento zero
com Elena Nadolinkski, Anna Rose, James Prestwich
https://zeroknowledge.fm/182-2/

zkDocs: Compartilhamento de informações de conhecimento zero
por Sam Ragsdale e Dan Boneh
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Airdrops criptográficos que protegem a privacidade com zero provas de conhecimento
por Sam Ragsdale
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

Cerimônias de configuração confiáveis ​​na cadeia -
por Valeria Nikolaenko e Sam Ragsdale
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Regulamentos de criptografia, finanças ilícitas, privacidade e muito mais – inclui seção sobre conhecimento zero em contextos regulatórios/de conformidade; diferença entre tecnologias de “preservação de privacidade” versus tecnologias ofuscantes
com Michele Korver, Jai Ramaswamy, Sonal Chokshi
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

Outros recursos

boletim informativo zkMesh — um boletim informativo mensal compartilhando as últimas tecnologias de preservação de privacidade descentralizada, desenvolvimento de protocolo de privacidade e sistemas de conhecimento zero
https://zkmesh.substack.com/

Podcast Zero Conhecimento — sobre os mais recentes aplicativos zk research & zk e especialistas que criam tecnologia de privacidade habilitada para criptografia
com Ana Rosa
https://zeroknowledge.fm/

…uma lista de leitura comentada, por tópico e cronologia, por Justin Thaler:

SNARKs de PCPs lineares (também conhecidos como SNARKs com configuração específica de circuito)

Argumentos eficientes sem PCPs curtos (2007)
por Yuval Ishai, Eyal Kushilevitz e Rafail Ostrovsky

Antes de cerca de 2007, SNARKs foram projetados principalmente através do Kilian-mica paradigma, de pegar uma prova probabilisticamente verificável (PCP) “curta” e “compilá-la criptograficamente” em um argumento sucinto via hashing de Merkle e a transformação Fiat-Shamir. Infelizmente, PCPs curtos são complicados e impraticáveis, ainda hoje. Este artigo (IKO) mostrou como usar a criptografia homomórfica para obter argumentos interativos sucintos (não transparentes) de PCPs “longos, mas estruturados”. Estes podem ser muito mais simples do que PCPs curtos, e os SNARKs resultantes têm provas muito mais curtas e verificação mais rápida. Esses argumentos foram inicialmente reconhecidos como tendo potencial de eficiência prática, e refinados e implementados, em Pepper. Infelizmente, os argumentos do IKO têm um provador de tempo quadrático e uma cadeia de referência estruturada de tamanho quadrático, portanto, eles não são dimensionados para grandes cálculos.

Programas de extensão quadrática e NIZKs sucintos sem PCPs (2012)
por Rosario Gennaro, Craig Gentry, Bryan Parno e Mariana Raykova

Este artigo inovador (GGPR) reduziu os custos de prova da abordagem da IKO de quadrático no tamanho do circuito para quase linear. Com base em trabalhos anteriores de Groth e Lipmaa, também forneceu SNARKs por meio de criptografia baseada em emparelhamento, em vez de argumentos interativos como em IKO. Ele descreveu seus SNARKs no contexto do que agora é conhecido como problemas de satisfação de restrição de rank 1 (R1CS), uma generalização da satisfatibilidade de circuitos aritméticos.

Este artigo também serviu como base teórica dos primeiros SNARKs a serem implementados comercialmente (por exemplo, em ZCash) e levou diretamente aos SNARKs que permanecem populares hoje (por exemplo, Groth16). As implementações iniciais dos argumentos do GGPR vieram Za'atar e Pinóquio, e variantes posteriores incluem SNARKs para C e BCTV. BCIOP forneceu uma estrutura geral que elucida essas transformações lineares de PCPs para SNARK (consulte também o Apêndice A de Za'atar) e descreve várias instanciações do mesmo.

Sobre o tamanho dos argumentos não interativos baseados em pareamento (2016)
por Jens Groth

Este artigo, coloquialmente conhecido como Groth16, apresentou um refinamento dos SNARKs da GGPR que atinge custos de verificação de concreto de última geração até hoje (as provas são 3 elementos de grupo, e a verificação é dominada por três operações de emparelhamento, pelo menos assumindo o público entrada é curta). A segurança é comprovada no modelo de grupo genérico.

SNARKs com configuração confiável universal

PlonK: Permutações sobre bases de Lagrange para argumentos não interativos ecumênicos de conhecimento (2019)
por Ariel Gabizon, Zachary Williamson e Oana Ciobotaru

Marlin: pré-processamento de zkSNARKs com SRS universal e atualizável (2019)
por Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely e Nicholas Ward

Tanto o PlonK quanto o Marlin substituem a configuração confiável específica do circuito no Groth16 por uma configuração universal. Isso vem à custa de provas 4x-6x maiores. Pode-se pensar no PlonK e no Marlin como tendo o trabalho específico do circuito durante a configuração confiável no Groth16 e predecessores e movendo-o para uma fase de pré-processamento que acontece depois de a configuração confiável, bem como durante a geração de provas SNARK.

A capacidade de processar circuitos arbitrários e sistemas R1CS dessa maneira às vezes é chamada de holografia ou compromissos de computação e também foi descrita em espartano (discutido posteriormente nesta compilação). Como mais trabalho acontece durante a geração de provas, os provadores do PlonK e do Marlin são mais lentos que o Groth16 para um determinado circuito ou instância R1CS. No entanto, ao contrário do Groth16, o PlonK e o Marlin podem funcionar com representações intermediárias mais gerais do que o R1CS.

Esquemas de compromisso polinomial, uma primitiva criptográfica chave em SNARKs

Compromissos de tamanho constante para polinômios e suas aplicações (2010)
por Aniket Kate, Gregory Zaverucha e Ian Goldberg

Este artigo introduziu a noção de esquemas de compromisso polinomial. Ele forneceu um esquema para polinômios univariados (comumente chamados de compromissos KZG) com compromissos de tamanho constante e provas de avaliação. O esquema usa uma configuração confiável (ou seja, string de referência estruturada) e criptografia baseada em pareamento. Ele permanece extremamente popular na prática hoje e é usado em SNARKs, incluindo PlonK e Marlin discutidos acima (e Groth16 usa técnicas criptográficas extremamente semelhantes).

Provas de proximidade rápidas do Oracle Reed-Solomon interativas (2017)
por Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev

Fornece uma prova interativa de oráculo (IOP) para testes Reed-Solomon — ou seja, prova que uma string confirmada está próxima da tabela de avaliação de um polinômio univariado. Combinado com o hash de Merkle e a transformação Fiat-Shamir, isso produz um esquema de compromisso polinomial transparente com provas de avaliação de tamanho polilogarítmico (consulte VP19 para detalhes). Hoje, este continua sendo o mais curto entre os esquemas de comprometimento polinomial plausivelmente pós-quântico.

Ligero: argumentos sublineares leves sem uma configuração confiável (2017)
por Scott Ames, Carmit Hazay, Yuval Ishai e Muthuramakrishnan Venkitasubramaniam

Semelhante ao FRI, este trabalho fornece um IOP para testes de Reed-Solomon, mas com comprimento de prova de raiz quadrada em vez de polilogarítmico. teórico trabalho mostrou que, trocando o código Reed-Solomon por um código de correção de erros diferente com codificação mais rápida, pode-se obter um provador de tempo linear que, além disso, funciona nativamente em qualquer campo. Esta abordagem foi aperfeiçoada e implementada em Travar e Orion, produzindo desempenho de provador de última geração.

À prova de balas: provas curtas para transações confidenciais e muito mais (2017)
por Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille e Greg Maxwell

Refinando o trabalho anterior por BCCGP, Bulletproofs fornece um esquema de compromisso polinomial transparente (na verdade, uma generalização chamada de argumento do produto interno) com base na dificuldade de calcular logaritmos discretos com tamanho de prova logarítmico, mas tempo de verificação linear. O esquema continua popular hoje devido à sua transparência e provas curtas (por exemplo, é usado em ZCash Orchard e Monero).

Dory: argumentos eficientes e transparentes para produtos internos generalizados e compromissos polinomiais (2020)
por Jonathan Lee

Dory reduz o tempo do verificador em Bulletproofs de linear para logarítmico, enquanto preserva a transparência e as provas de tamanho logarítmico (embora concretamente maiores do que Bulletproofs) e transparência. Usa pares e é baseado na suposição SXDH.

Provas interativas, provas interativas multi-provador e SNARKs associados

Delegação de computação: provas interativas para trouxas (2008)
por Shafi Goldwasser, Yael Tauman Kalai e Guy Rothblum

Antes deste artigo, as provas interativas de uso geral exigiam um tempo superpolinomial provador. Este artigo fornece um protocolo de prova interativa, comumente chamado de protocolo GKR, com um provador de tempo polinomial e um verificador de tempo quasilinear, para qualquer problema que possua um algoritmo paralelo eficiente (equivalentemente, a prova interativa se aplica a qualquer circuito aritmético com pequena profundidade).

Computação verificada prática com streaming de provas interativas (2011)
por Graham Cormode, Michael Mitzenmacher, Justin Thaler

Este artigo (às vezes chamado de CMT) reduziu o tempo do provador no protocolo GKR de quártico no tamanho do circuito para quase linear. Produziu a primeira implementação de uma prova interativa de uso geral. Uma linha de trabalhos subsequentes (Pimenta da Jamaica, Thaler13, Girafa e Libra) reduziu ainda mais o tempo de execução do provador, de quase linear para linear no tamanho do circuito.

vSQL: verificando consultas SQL arbitrárias em bancos de dados dinâmicos terceirizados (2017)
por Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos e Charalampos Papamanthou

Embora o título se refira a uma área de aplicação específica (bancos de dados), as contribuições deste artigo são mais gerais. Especificamente, observou-se que é possível obter argumentos sucintos para a satisfatibilidade do circuito combinando provas interativas com esquemas de comprometimento polinomial (para polinômios multilineares).

Later trabalho renderizado os argumentos de conhecimento zero e introduziu diferentes esquemas de compromisso para polinômios multilineares.

Spartan: zkSNARKs eficientes e de uso geral sem configuração confiável (2019)
por Srinath Setty

Obtém SNARKs para satisfatibilidade de circuito e R1CS combinando provas interativas multi-provador (MIPs) com esquemas de compromisso polinomial, com base em trabalhos anteriores em MIPs concretamente eficientes chamados Trevo. O efeito é obter SNARKs com provas mais curtas do que aquelas derivadas de provas interativas, como o protocolo GKR discutido acima. Análogo ao PlonK e ao Marlin, o Spartan também mostra como processar circuitos arbitrários e sistemas R1CS via pré-processamento e geração de provas SNARK.

Spartan usou um esquema de compromisso polinomial de hyrax. Trabalhos posteriores chamados Travar e Orion combine o MIP da Spartan com outros esquemas de compromisso polinomial para produzir os primeiros SNARKs implementados com um provador de tempo linear.

PCPs e IOPs curtos

PCPs curtos com complexidade de consulta Polylog (2005)
por Eli Ben-Sasson e Madhu Sudan

 Este trabalho teórico deu a primeira prova probabilisticamente verificável (PCP) com comprimento de prova quase linear no tamanho da computação a ser verificada e custo de consulta polilogarítmica (embora linear tempo de verificação). Após a transformação Kilian-Micali de PCPs em SNARKs, este foi um passo em direção a SNARKs com provador de tempo quase linear e verificador de tempo polilogarítmico.

Trabalho teórico posterior reduziu o tempo do verificador para polilogarítmico. Subseqüente o trabalho focado na prática refinou essa abordagem, mas PCPs curtos permanecem impraticáveis ​​hoje. Para obter SNARKs práticos, mais tarde trabalho virou-se para uma generalização interativa de PCPs chamada Provas interativas da Oracle (IOP). Esses esforços levaram e se basearam Sexta-feira , um esquema de compromisso polinomial popular discutido na seção de compromissos polinomiais desta compilação.

Outros trabalhos nesta categoria incluem ZKBooGenericName e seus descendentes. Estes não alcançam provas sucintas, mas têm bons fatores constantes e, portanto, são atraentes para provar pequenas afirmações. Eles levaram a famílias de assinaturas pós-quânticas, como Piquenique que têm sido otimizado in vários trabalho. O ZKBoo é apresentado seguindo um paradigma de design distinto chamado MPC na cabeça, mas produz um IOP.

SNARKs recursivos

Computação incrementalmente verificável ou provas de conhecimento implicam em eficiência de tempo/espaço (2008)
por Paulo Valente

Este trabalho introduziu a noção fundamental de computação incrementalmente verificável (IVC), na qual um provador executa uma computação e mantém em todos os momentos uma prova de que a computação até agora foi correta. Construiu IVC via composição recursiva de SNARKs. Aqui o solidez do conhecimento A propriedade de SNARKs é essencial para estabelecer a solidez de argumentos não interativos compostos recursivamente. Este artigo também forneceu um extrator de conhecimento extremamente eficiente para SNARKs derivados de PCP (de acordo com o paradigma Kilian-Micali).

Conhecimento zero escalável por meio de ciclos de curvas elípticas (2014)
por Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer e Madars Virza

Agora sobre o trabalho teórico, este trabalho utilizou a aplicação recursiva de uma variante do SNARK do GGPR, para fornecer a primeira implementação de IVC para uma máquina virtual simples (TinyRAM, do SNARKs para C papel).

Também introduziu a noção de ciclos de curvas elípticas, que são úteis para compor recursivamente SNARKs que fazem uso de criptografia de curva elíptica.

Composição de prova recursiva sem uma configuração confiável (2019)
por Sean Bowe, Jack Grigg e Daira Hopwood

Este trabalho (chamado Halo) estuda como compor recursivamente SNARKs transparentes. Isso é mais desafiador do que compor os não transparentes porque o procedimento de verificação em SNARKs transparentes pode ser muito mais caro.

Isso desencadeou então um linha of trabalho que culminou em sistemas como nova alcançando desempenho IVC de última geração, superior até mesmo ao obtido pela composição de SNARKs não transparentes como Groth16.

Aplicações

Zerocash: pagamentos anônimos descentralizados do Bitcoin (2014)
por Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

Com base em trabalhos anteriores, incluindo o Zeroco (e com Moeda Pinóquio como trabalho simultâneo), este artigo usa SNARKs derivados de GGPR para projetar uma criptomoeda privada. Levou a ZCash.

Gepeto: Computação Versátil Verificável (2014)
por Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno e Samee Zahur

Geppetto é indiscutivelmente anterior à explosão de interesse na execução privada de contratos inteligentes, tendo sido escrito cerca de um ano após a criação do Ethereum. Portanto, não é apresentado no contexto da execução de contratos inteligentes privados. No entanto, ele usa a recursão de profundidade limitada de SNARKs para permitir que um provador não confiável execute qualquer programa de computador privado (comprometido/assinado) em dados privados, sem revelar informações sobre o programa que está sendo executado ou os dados em que é executado. Assim, é um antecessor do trabalho em plataformas privadas de contratos inteligentes, como Zexe [Descrito abaixo].

ASICs verificáveis (2015)
por Riad Wahby, Max Howald, Siddharth Garg, abhi shelat, Michael Walfish

Este artigo considera o problema de como usar de forma segura e frutífera um ASIC fabricado em uma fundição não confiável (em 2015, havia apenas cinco países com fundições de ponta). A abordagem é fazer com que o ASIC rápido, mas não confiável, prove a exatidão de sua saída para um verificador que é executado em um ASIC mais lento, mas confiável. A solução é interessante desde que o tempo total de execução do sistema (ou seja, a soma dos tempos de execução do provador e do verificador mais quaisquer custos de transmissão de dados) seja menor que a linha de base ingênua: o tempo necessário para executar o cálculo completo no -mas confiável ASIC. Usando uma variante das provas interativas GKR/CMT/Allspice, o artigo realmente supera a linha de base ingênua para vários problemas fundamentais, incluindo transformações teóricas de números, correspondência de padrões e operações de curva elíptica. Este trabalho sugere que alguns sistemas de prova são mais adequados para implementação em hardware do que outros. A otimização de sistemas de prova para implementação de hardware agora está recebendo considerável por WhatsApp., mas ainda há muito a ser explorado.

Verificável Funções de atraso (2018)
por Dan Boneh, Joseph Bonneau, Benedikt Bünz e Ben Fisch

Introduziu a notação de funções de atraso verificáveis ​​(VDFs), uma primitiva criptográfica que é amplamente útil em aplicações blockchain, por exemplo, na mitigação de possível manipulação de protocolos de consenso de prova de participação. SNARKs (especialmente para Computação Incremental Verificável) oferecem uma rota para VDFs de última geração.

Zexe: habilitando a computação privada descentralizada (2018)
por Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra e Howard Wu

Zexe é um projeto para uma plataforma privada de contrato inteligente. Pode-se ver o Zexe como uma extensão do Zerocash (descrito acima). Zerocash permite que um único aplicativo seja executado on-chain (permitindo que os usuários transfiram tokens) enquanto protege a privacidade dos dados do usuário, por exemplo, para quem eles estão enviando tokens, recebendo tokens, a quantidade de tokens transferidos, etc. Zexe permite muitos diferentes aplicativos (contratos inteligentes) para serem executados no mesmo blockchain e interagirem entre si. As transações são executadas fora da cadeia e as provas de execução correta são postadas na cadeia. Não apenas a privacidade dos dados é protegida, mas também a privacidade das funções. Isso significa que a prova associada a cada transação nem mesmo revela a qual(is) aplicação(ões) a transação se refere. Uma contribuição de engenharia mais geral do Zexe é que ele introduziu o BLS12-377, um grupo de curvas elípticas que é útil para a composição eficiente de profundidade 1 de SNARKs baseados em pareamento.

Máquinas de estado replicadas sem execução replicada (2020)
por Jonathan Lee, Kirill Nikitin e Srinath Setty

Este é um dos poucos trabalhos acadêmicos sobre rollups para escalabilidade de blockchain. Não usa o termo rollups, porque é anterior ou contemporâneo ao conceito que está sendo introduzido fora da literatura acadêmica.

Front-ends (transformações eficientes de programas de computador para representações intermediárias, como satisfação de circuitos, R1CS e muito mais)

Reduções rápidas de RAMs para problemas de satisfação de restrições sucintas delegáveis (2012)
por Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin e Eran Tromer

De uma perspectiva moderna, este é um trabalho inicial sobre transformações práticas de programa de computador para circuito SAT para uma abstração de máquina virtual (VM). Com base em obras do final da década de 1970 até a década de 1990 (por exemplo, trabalho de Robson) este artigo descreve uma redução determinística da execução de uma VM para T etapas para a satisfatibilidade de um circuito de tamanho O(T*polylog(T)).

Documentos subsequentes, por exemplo, SNARKs para C e BCTV, continuou a desenvolver front-ends por meio de uma abstração de VM, e instanciações modernas incluem projetos como Cairo, RISC Zero e Polígono Miden.

Levando a computação verificada baseada em provas a alguns passos mais perto da praticidade (2012)
por Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg e Michael Walfish

Este artigo, conhecido como Ginger, é outra contribuição inicial para as técnicas práticas de front-end. Ginger introduziu gadgets para primitivas de programação geral, como expressões condicionais e lógicas, comparações e aritmética bit a bit via divisão de bits, aritmética primitiva de ponto flutuante, etc. restrições aritméticas (semelhante ao que agora é conhecido como R1CS), uma representação intermediária (IR) à qual um back-end SNARK pode ser aplicado.

Considerando que o artigo “Reduções Rápidas” e seus descendentes usam uma abordagem de “emulador de CPU” na produção de IRs (ou seja, o IR reforça que o provador executou corretamente um programa específico aplicando a função de transição da CPU para um número especificado de etapas) , Ginger e seus descendentes adotam uma abordagem mais semelhante ao ASIC, produzindo IRs adaptados ao programa de computador que o provador alega executar corretamente.

Por exemplo, bufê mostra que é possível lidar com fluxo de controle complexo no modelo ASIC, transformando tal fluxo de controle em uma máquina de estado finito adaptada ao programa que está sendo executado, e que essa abordagem pode ser significativamente mais eficiente do que construir um emulador de CPU de uso geral. xJsnark fornece uma construção eficiente para aritmética de multiprecisão, otimizações para RAMs e ROMs e expõe uma linguagem de alto nível semelhante a Java para um programador, que permanece popular hoje. CirC observa que a compilação de programas de computador para R1CS está intimamente relacionada a técnicas bem conhecidas de análise de programas e constrói um kit de ferramentas de construção de compiladores incorporando ideias de ambas as comunidades (“LLVM para representações semelhantes a circuitos”). Trabalhos anteriores que fazem contribuições para front-ends no estilo ASIC incluem Pinóquio e Geppetto.

O artigo “Reduções Rápidas” usava uma construção complicada e cara chamada “redes de roteamento” para os chamados verificação de memória (ou seja, garantir que o provador não confiável esteja mantendo corretamente a memória de acesso aleatório da VM durante a execução da VM cuja correção está sendo provada). Essa escolha foi feita porque trabalhos iniciais como este buscavam obter um PCP, o que exigia que o front-end fosse ambos não interativo e teoricamente seguro. Trabalho posterior chamado Despensa (antecessor do bufê trabalho mencionado acima) usou árvores Merkle no lugar de redes de roteamento, alcançando eficiência compilando uma função hash algébrica (ou seja, “SNARK-friendly”), devido a Ajtai, em restrições. Isso resultou em front-ends “computacionalmente seguros”. Hoje, há uma grande literatura de pesquisa sobre funções de hash compatíveis com SNARK, com exemplos incluindo Poseidon, MiMC, Concreto reforçado, ResgateE muito mais.

Técnicas de última geração para garantir que o provador esteja mantendo a RAM corretamente dependem dos chamados métodos de “impressão digital invariante de permutação” que remontam pelo menos a Lipton (1989) e usado para verificação de memória por Blum et ai. (1991). Essas técnicas envolvem inerentemente a interação entre um provador e um verificador, mas podem se tornar não interativas com a transformação Fiat-Shamir. Até onde sabemos, eles foram introduzidos na literatura sobre front-ends SNARK práticos por um sistema chamado vRAM.

Técnicas de impressão digital invariável de permutação agora são usadas em muitos front-ends e SNARKs para abstrações de máquinas virtuais, incluindo, por exemplo, Cairo. Ideias intimamente relacionadas reapareceram em contextos relacionados nas duas obras abaixo, que são amplamente utilizadas na prática hoje.

Provas de conhecimento zero em tempo quase linear para a execução correta do programa (2018)
por Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen e Mary Maller

Plookup: Um protocolo polinomial simplificado para tabelas de pesquisa (2020)
por Ariel Gabizon e Zachary Williamson

Os primeiros trabalhos em front-ends representavam operações “não aritméticas” (como verificações de intervalo, operações bit a bit e comparações de inteiros) dentro de circuitos e IRs relacionados, quebrando elementos de campo em bits, realizando as operações nesses bits e, em seguida, “empacotando” o resultado de volta em um único elemento de campo. Em termos do tamanho do circuito resultante, isso resulta em uma sobrecarga logarítmica por operação.

Os dois trabalhos acima (BCGJM e Plookup) fornecem técnicas influentes (baseadas nas chamadas “tabelas de pesquisa”) para representar de forma mais eficiente essas operações dentro de circuitos, em um sentido amortizado. Grosso modo, para algum parâmetro B escolhido pelo designer front-end, eles reduzem o número de portas necessárias para representar cada operação não aritmética no circuito por um fator logarítmico em B, ao custo do provador se comprometer criptograficamente com um valor extra vetor “conselho” de comprimento aproximadamente B.