O que é um zk-STARK e como funciona?

O que é um zk-STARK?

Um zk-STARK é uma forma criptográfica de provar que um cálculo está correto, sem que quem verifica a proof tenha de executar novamente o cálculo completo. Graças à propriedade de zero-knowledge, determinados dados usados no cálculo podem, além disso, permanecer ocultos.

A sigla significa Zero-Knowledge Scalable Transparent ARgument of Knowledge. Isto soa técnico, mas os componentes são fáceis de explicar:

• Zero-Knowledge: pode provar que algo está correto sem revelar a informação secreta subjacente.
• Scalable: mesmo em cálculos grandes, a proof pode ser verificada de forma relativamente eficiente.
• Transparent: não é necessária uma trusted setup. Ou seja, não tem de ocorrer previamente uma configuração especial na qual surja informação secreta que depois tenha de ser destruída em segurança.
• Argument of Knowledge: uma proof válida mostra que o autor dispõe da informação necessária para executar corretamente o cálculo. Por isso, é extremamente difícil falsificar uma proof válida de forma arbitrária.

Em criptomoeda, isto é especialmente útil quando grandes cálculos são executados fora da blockchain. Um sistema pode, por exemplo, processar muitas transações off-chain e depois enviar uma proof para a blockchain. A blockchain não precisa então de executar novamente cada cálculo, mas apenas de verificar se a proof apresentada é válida.

Exemplo: Suponha que milhares de transações são processadas fora da Ethereum. Em vez de executar novamente todas essas transações na Ethereum, um sistema pode gerar uma única zk-STARK que prova que todo o lote foi processado de acordo com as regras. A Ethereum precisa então apenas de verificar essa proof.

A base dos STARKs foi descrita em 2018 por Eli Ben-Sasson, Iddo Bentov, Yinon Horesh e Michael Riabzev. O sistema foi concebido para tornar grandes cálculos verificáveis de forma eficiente, sem trusted setup.

Pontos principais

• Um zk-STARK prova que um cálculo foi executado corretamente sem o repetir na íntegra.
• Zero knowledge pode ocultar dados de entrada privados, mas não está automaticamente presente em todas as aplicações STARK.
• Os STARKs não precisam de uma trusted setup com parâmetros secretos.
• Em rollups, muitas transações off-chain podem ser verificadas numa blockchain com uma única validity proof.
• A técnica pode ser usada tanto para escalabilidade de blockchain como para cálculos verificáveis fora da criptomoeda.

Como funciona um zk-STARK?

Um zk-STARK transforma um grande cálculo numa forma muito mais eficiente de verificar. A parte que executa o cálculo, o prover, cria depois uma proof criptográfica. O verifier verifica essa proof sem executar novamente o cálculo original completo.

Em termos simples: o prover faz o trabalho computacional pesado e o verifier confirma, com vários controlos criptográficos e matemáticos, se o resultado está correto.

Em linhas gerais, funciona assim:

1. O cálculo é convertido em regras matemáticas: Primeiro, define-se a que regras cada passo do cálculo tem de obedecer. Nos STARKs, isto acontece muitas vezes através de uma chamada Algebraic Intermediate Representation (AIR). Pode ver isto como uma descrição matemática do que é e não é permitido durante o cálculo.

2. O prover regista todos os passos de cálculo: O prover executa o cálculo e cria uma chamada execution trace. Isto pode ser visto como uma grande tabela onde são registados os diferentes passos do cálculo.

3. Os dados são registados criptograficamente: O prover processa estes dados matematicamente e regista-os com cryptographic commitments, por exemplo com uma Merkle tree. Desta forma, o prover não pode alterar os dados arbitrariamente mais tarde.

4. O verifier verifica uma seleção dos dados: Em seguida, são realizados controlos em pontos imprevisíveis. O verifier confirma, entre outras coisas, se os dados correspondem aos commitments registados anteriormente e se as regras matemáticas do cálculo foram seguidas. Os STARKs utilizam para isso, entre outras coisas, uma técnica chamada FRI. Esta permite verificar de forma eficiente se as funções matemáticas usadas têm a forma correta, sem verificar todos os dados individualmente.

5. A proof é verificada: Se todos os controlos forem bem-sucedidos, o verifier tem uma forte garantia criptográfica de que o cálculo foi executado corretamente. Para isso, não é necessário executar novamente o cálculo completo. Quando usado numa blockchain, o prover pode enviar a proof final para um smart contract. Esse contrato verifica a proof e aceita o novo resultado apenas quando esta é válida. A StarkWare, por exemplo, utiliza verificadores on-chain na Ethereum para verificar proofs STARK.

Exemplo: Suponha que um rollup processa 1.000 transações fora da Ethereum. O rollup executa todos os cálculos e depois cria uma proof que demonstra que as transações foram processadas de acordo com as regras. A Ethereum não precisa então de executar novamente todas essas 1.000 transações. Em vez disso, um smart contract verifica a proof. Se esta for válida, o novo estado do rollup pode ser aceite.

Isto torna os zk-STARKs especialmente interessantes para a escalabilidade: muito trabalho computacional pode ocorrer fora da blockchain, enquanto a blockchain continua a poder verificar criptograficamente se o resultado está correto.

O que são zero-knowledge proofs?

Uma zero-knowledge proof permite provar que uma afirmação é verdadeira sem revelar a informação secreta por trás dessa afirmação.

Em termos simples: o prover mostra ao verifier que algo está correto, sem ter de partilhar todos os dados subjacentes.

Uma zero-knowledge proof tem três propriedades importantes:

• Completeness: se a afirmação for verdadeira e o prover executar tudo corretamente, o verifier pode aceitar a proof.
• Soundness: alguém que tente provar uma afirmação incorreta tem apenas uma probabilidade negligenciável de conseguir fazê-lo.
• Zero knowledge: o verifier não aprende informação secreta adicional, para além de que a afirmação é verdadeira.

Exemplo: Um sistema pode provar que um lote de transações foi processado de acordo com todas as regras, sem tornar públicos determinados dados privados dessas transações.

Num rollup, a afirmação pública pode, por exemplo, ser que uma nova state root resulta de uma sequência válida de transações. Que dados permanecem ocultos depende da forma como o sistema de proof e a aplicação foram concebidos.

É importante saber: uma validity proof não oferece automaticamente privacidade. Um sistema pode provar criptograficamente que as transações foram processadas corretamente, enquanto os dados das transações continuam públicos. Para haver privacidade, a propriedade de zero-knowledge tem de ser incorporada de forma deliberada no sistema.

Qual é o papel dos STARKs?

Os STARKs são o sistema de proof que permite provar e verificar grandes cálculos de forma eficiente, sem trusted setup.

A propriedade de zero-knowledge determina, nesse contexto, que informação pode permanecer oculta. A técnica STARK garante que o verifier pode verificar de forma eficiente se o cálculo foi executado de acordo com as regras.

Uma característica importante dos STARKs é que são transparent. Não é necessária uma trusted setup na qual sejam criados previamente parâmetros criptográficos secretos que depois tenham de ser destruídos em segurança. Em vez disso, o sistema baseia-se, entre outras coisas, em aleatoriedade pública e em funções hash criptográficas.

Os STARKs utilizam ainda técnicas como FRI, que permitem verificar de forma eficiente se a estrutura matemática por trás da proof está correta.

O termo Argument of Knowledge significa que um prover não pode simplesmente criar uma proof válida. Sob as suposições de segurança do sistema, o prover tem de dispor da informação necessária para executar corretamente o cálculo.

Para que são usados os zk-STARKs?

Os zk-STARKs são usados sobretudo para executar grandes cálculos fora de uma blockchain e depois provar, com uma única proof criptográfica, que o resultado está correto. Uma aplicação importante disto são os validity rollups.

Num rollup deste tipo, muitas transações são processadas fora da camada base. Depois, é enviada uma proof para a blockchain que demonstra que o novo estado surgiu do estado antigo de acordo com as regras.

Isto é útil porque a camada base não precisa de executar novamente todos os cálculos. Os custos de uma única proof podem assim ser distribuídos por um grande grupo de transações.

Um exemplo conhecido é o StarkEx. Este sistema utiliza STARK proofs para processar grandes quantidades de transações para aplicações como negociação, pagamentos, gaming e NFT's. As transações são agregadas, depois é criada uma proof e esta é verificada por um smart contract na Ethereum.

A tecnologia STARK também pode ser usada fora da criptomoeda. Em princípio, a técnica é adequada para situações em que se pretende provar que um grande cálculo foi executado corretamente sem que o verificador tenha de repetir todos os cálculos. Com zero knowledge, também podem permanecer ocultos determinados dados subjacentes.

Uma proof, por si só, não resolve tudo. Nos rollups, por exemplo, continua a ser importante onde os dados das transações estão disponíveis. Uma proof válida demonstra que o cálculo está correto de acordo com as regras definidas, mas não garante automaticamente a disponibilidade de todos os dados.

Que blockchains usam STARKs?

O exemplo mais conhecido de uma rede blockchain que utiliza STARK proofs é a Starknet. A Starknet é uma Layer 2 sobre a Ethereum que processa muitas transações fora da Ethereum e depois envia uma STARK proof para a Ethereum.

A Ethereum verifica esta proof para confirmar que o novo estado da Starknet foi calculado corretamente. Desta forma, a Ethereum não precisa de executar novamente, individualmente, todas as transações que ocorrem na Starknet.

Também o StarkEx utiliza STARK proofs, mas o StarkEx não é uma blockchain autónoma. É uma solução de scaling que permite a várias aplicações de criptomoeda processar grandes quantidades de transações fora da Ethereum e depois provar criptograficamente que os cálculos foram executados corretamente.

A própria Ethereum, portanto, não utiliza STARKs como mecanismo próprio de consenso ou de transações. A rede pode, no entanto, verificar STARK proofs apresentadas por aplicações e redes Layer 2 como a Starknet.

É importante saber: o uso de STARK proofs não significa automaticamente que as transações sejam privadas. A Starknet utiliza STARK validity proofs para provar que os cálculos foram executados corretamente, enquanto a privacidade zero-knowledge é uma propriedade separada.

Quais são as vantagens dos zk-STARKs?

Os zk-STARKs permitem verificar grandes cálculos de forma muito mais eficiente do que se cada participante tivesse de repetir todos os cálculos.

As principais vantagens são:

• Sem trusted setup: os STARKs não precisam de uma cerimónia prévia na qual informação criptográfica secreta é criada e depois tem de ser destruída em segurança.
• Verificação eficiente: o verifier pode verificar um grande cálculo sem repetir cada passo individualmente.
• Adequados para escalabilidade: uma única proof pode demonstrar a execução correta de um grande lote de transações, permitindo que as blockchains processem mais transações fora da camada base.
• Possibilidade de privacidade: quando o zero knowledge está incorporado no sistema, determinados dados privados podem permanecer ocultos enquanto o cálculo continua a poder ser verificado.
• Segurança baseada em hash: os STARKs baseiam-se, para a sua proving layer, em funções hash criptográficas em vez de pairings de curvas elípticas, que são usados em muitos sistemas SNARK clássicos.

Devido a esta abordagem baseada em hash, os STARKs são também frequentemente vistos como mais preparados para um futuro com computadores quânticos potentes. De facto, algoritmos quânticos conhecidos representam um problema maior para muitas construções de curvas elípticas do que para funções hash criptográficas bem escolhidas.

Isto não significa que todas as aplicações com STARKs sejam automaticamente totalmente resistentes à computação quântica. As funções hash utilizadas, os parâmetros, a implementação e outros componentes criptográficos do sistema continuam a ser importantes.

Quais são as limitações dos zk-STARKs?

Os zk-STARKs também têm desvantagens. Em especial, a criação de uma proof pode exigir muita capacidade computacional e memória. O trabalho pesado, portanto, não desaparece, mas é sobretudo transferido para o prover.

Além disso, as STARK proofs são, em geral, maiores do que as proofs de muitos sistemas zk-SNARK clássicos. Isto pode significar que é necessário processar mais dados quando uma proof é verificada numa blockchain.

Outras limitações são:

• Complexidade técnica: os programadores têm de converter corretamente os cálculos para uma forma que possa ser verificada pelo sistema de proof.
• Custos de geração da proof: criar proofs pode exigir muita capacidade computacional e, por isso, implicar custos.
• A proof apenas verifica as regras registadas: se a lógica da aplicação contiver um erro, uma proof válida apenas demonstra que essas regras incorretas foram seguidas corretamente.
• A privacidade não está automaticamente presente: um sistema baseado em STARK pode usar validity proofs sem manter os dados das transações em segredo.

Em suma: uma STARK proof pode provar de forma muito forte que um determinado cálculo foi executado de acordo com as regras registadas, mas não pode determinar se essas regras foram bem concebidas.

Qual é a diferença entre zk-STARKs e zk-SNARKs?

Os zk-STARKs e os zk-SNARKs têm o mesmo objetivo geral: provar de forma eficiente que um cálculo foi executado corretamente sem que o verifier tenha de executar novamente o cálculo completo.

A principal diferença está na técnica criptográfica utilizada para esse fim.

Uma vantagem importante dos zk-SNARKs é que, em muitos sistemas, as proofs podem ser muito pequenas. Isso torna-os atrativos quando a quantidade de dados a verificar on-chain deve ser a menor possível.

Os zk-STARKs têm, em geral, proofs maiores, mas não precisam de trusted setup e utilizam outras suposições criptográficas. Por isso, são especialmente atrativos para grandes cálculos e aplicações em que a transparência da configuração é importante.

Ainda assim, é importante não colocar todos os zk-SNARKs no mesmo saco. zk-SNARK é um termo genérico para vários sistemas de proof. Nem todos os SNARK usam a mesma criptografia e nem todas as variantes exigem o mesmo tipo de trusted setup.

Também em ambas as técnicas se aplica que uma validity proof não significa automaticamente privacidade. O zero knowledge tem de fazer parte do sistema de proof específico e da aplicação.

Conclusão

Um zk-STARK é uma técnica criptográfica que permite provar que um grande cálculo foi executado corretamente sem que o verifier tenha de executar novamente esse cálculo completo.

Isto torna os zk-STARKs especialmente interessantes para a escalabilidade de blockchain. Os rollups podem processar grandes quantidades de transações fora da camada base e depois demonstrar, com uma única proof, que o resultado está correto.

As principais vantagens são a configuração transparente sem trusted setup e a verificação eficiente de grandes cálculos. Em contrapartida, existem proofs maiores, muito trabalho computacional para o prover e complexidade técnica.

Os zk-STARKs são, portanto, sobretudo uma forma de tornar grandes cálculos eficientes e verificáveis criptograficamente. A privacidade pode fazer parte disto, mas não está automaticamente presente.