Escrito por Robin Linux Tradutor: Denlink Community Translation Group
Resumo
BitVM é um paradigma de computação usado para expressar contratos Bitcoin Turing-completos. Isso não requer nenhuma mudança nas regras de consenso da rede Bitcoin. Ao contrário de realizar cálculos em Bitcoin, eles são simplesmente verificados, semelhante a rollups otimistas. O provador declara que uma determinada função avalia certas entradas para uma determinada saída. Se a alegação for falsa, o verificador pode fazer uma prova concisa de fraude e penalizar os provadores. Usando este mecanismo, qualquer função computável pode ser verificada no Bitcoin.
Prometer um programa grande em um endereço Taproot requer muita computação e comunicação off-chain, mas sua pegada na cadeia é pequena. Desde que as duas partes trabalhem em conjunto, podem realizar cálculos fora da cadeia arbitrariamente complexos e com estado, sem deixar quaisquer vestígios na cadeia. A aplicação em cadeia só é exigida em caso de litígio.
1 Introdução
Por design, a funcionalidade de contrato inteligente do Bitcoin é limitada a operações básicas, como assinaturas, bloqueios de tempo e bloqueios de hash. O BitVM cria um novo espaço de design para contratos Bitcoin mais expressivos e computação off-chain. As aplicações potenciais incluem jogos como xadrez, Go ou poker, bem como verificação de prova de validade em contratos Bitcoin. Além disso, pode ser possível fazer a ponte entre o Bitcoin e cadeias externas, construir mercados de previsão ou simular novos opcodes.
A principal desvantagem do modelo apresentado aqui é que ele só funciona com duas configurações, o provador e o verificador. Outra limitação é que, para provadores e verificadores, é necessária muita computação e comunicação off-chain para executar o programa. No entanto, estas questões parecem promissoras para serem abordadas com mais investigação. Neste trabalho, nos concentramos apenas nos principais componentes de um BitVM de duas partes.
2 Esquema
Com os otimistas Rollups 1[2] [3] e a proposta MATT (Merkelize All The Things) 2 Da mesma forma, nossos sistemas são baseados em protocolos de prova de fraude e desafio-resposta. No entanto, o BitVM não requer nenhuma alteração nas regras de consenso do Bitcoin. Os primitivos subjacentes são relativamente simples. É baseado principalmente em bloqueios de hash, bloqueios de tempo e grandes árvores de raiz.
O provador submete o programa pouco a pouco à cadeia, mas validar tudo on-chain consumiria recursos de computação excessivos, de modo que o verificador executa uma série de desafios elaborados para falsificar sucintamente as falsas alegações do provador. Juntos, o provador e o verificador pré-assinam uma série de desafios – responder às transações para resolver quaisquer disputas mais tarde.
O modelo visa simplesmente ilustrar que essa abordagem permite a computação universal no Bitcoin. Para aplicações práticas, devemos considerar modelos mais eficientes.
O protocolo é simples: primeiro, o provador e o verificador compilam o programa em um circuito binário gigante. O provador envia o circuito para um endereço Taproot com um script folha para cada porta lógica nesse endereço. Além disso, eles pré-assinam uma série de transações para apoiar jogos de desafio-resposta entre provadores e verificadores. Agora que eles trocaram todos os dados necessários, eles podem transferir seu depósito on-chain para o endereço Taproot gerado.
Isso ativa o contrato e eles podem começar a trocar dados off-chain para acionar mudanças de estado no circuito. Se o provador fizer quaisquer afirmações falsas, o verificador pode receber o seu depósito. Isto garante que os atacantes perderão sempre os seus depósitos.
Compromisso de Valor de 3 Bits
O compromisso de valor de bits é o componente mais básico deste sistema. Ele permite que o provador defina o valor de um determinado bit para "0" ou "1". Em particular, permite que o provador defina o valor de uma variável entre diferentes scripts e UTXOs. Isso é crítico porque dimensiona o tempo de execução dividindo o tempo de execução da máquina virtual do Bitcoin em várias transações.
A promessa contém dois valores de hash, hash0 e hash1. Em um ponto posterior, o provador define o valor do bit para "0" revelando preimage0 (a pré-imagem de hash0) ou para "1" revelando preimage1 (a pré-imagem de hash1). Se, em algum momento, eles revelarem tanto a pré-imagem0 quanto a pré-imagem1, o validador pode usá-las como prova de fraude e receber o depósito do provador. A isto chama-se uma afirmação contraditória. Ser capaz de punir declarações contraditórias é o que torna um compromisso vinculativo – é um "compromisso baseado em incentivos".
A combinação de promessas de valor de bits com timelocks permite que os validadores forcem o provador a decidir sobre o valor de um determinado bit dentro de um determinado período de tempo.
Figura 1: Implementação de um compromisso de valor de bitsFigura 1: Implementação de um compromisso de 1 bit. Para desbloquear este script, o provador deve revelar uma das pré-imagens de hash0 ou hash1. Neste exemplo de execução, o provador revela hash1 e define o valor do bit como "1". Podemos replicar essa promessa para impor um valor específico em scripts diferentes.
PARA SIMPLIFICAR, A PARTIR DAQUI, VAMOS SUPOR QUE EXISTE UM OPCODE CHAMADO OP BITCOMMITMENT, QUE É UMA ABREVIAÇÃO PARA O SCRIPT ACIMA. O opcode consome dois hashes e uma pré-imagem com hash. Com base no hash que corresponde à pré-imagem, ele coloca um valor de bit na pilha.
4 Promessas de porta lógica
Qualquer função computável pode ser representada como um circuito booleano. A porta NAND é uma porta lógica universal, de modo que qualquer função booleana pode ser composta por elas. Para manter o nosso modelo simples, mostramos como a nossa abordagem funciona com portas NAND simples. Além disso, mostramos como combinar portas arbitrariamente. Tudo isto prova que o BitVM pode representar qualquer circuito.
A realização da promessa do portão NAND é simples. Ele contém promessas de dois bits representando duas entradas e um compromisso de bit representando saídas. O script calcula o valor NAND das duas entradas para garantir que ele corresponda aos bits de saída prometidos.
Figura 2: Compromisso de porta para operações NAND Figura 2: Compromisso de porta para operações NAND. A execução desse script precisa revelar os valores das promessas de bits A, B e C de modo que A NAND B = C seja verdadeiro.
(Aqui, para simplificar, vamos supor que exista um opcode chamado OP NAND.) NA VERDADE, ELE NÃO EXISTE, MAS PODE SER FACILMENTE IMPLEMENTADO USANDO OP BOOLAND E OP NOT. ）
5 Circuito binário promete
Na seção anterior, definimos o compromisso da porta NAND. Podemos representar qualquer circuito combinando promessas de portão. Cada passo da execução é cometido em Tapleaf. Todos eles são mesclados no mesmo endereço Taproot para que o provador possa executar qualquer porta no circuito. A execução do gate requer que o provador abra a promessa de porta correspondente e defina valores para seus bits de entrada e saída.
Taptree pode se tornar enorme e ter um bilhão de scripts Tapleaf, mas sua pegada on-chain é pequena.
Figura 3: Um circuito de exemplo aleatório Figura 3: Um circuito de exemplo aleatório com 8 portas NAND diferentes e 4 entradas A, B, C e D. Usando bilhões de portões, essencialmente qualquer função pode ser definida.
Figura 4Figura 4: Para cada portão, o endereço Taproot do provador contém um script de folha com a promessa de porta correspondente. Isso permite que o provador defina os valores de entrada do circuito a qualquer momento (aqui A, B, C e D).
##6 Desafios e Respostas
Não basta comprometer-se com um circuito. A fim de refutar alegações erradas, o verificador deve poder contestar a declaração do provador. Isso pode ser conseguido pré-assinando uma série de transações durante a configuração. Estas transações respondem a → desafios →→ respondem a →... maneira ligada. Se uma das partes deixar de participar, após um período de tempo limite, a outra parte vence o desafio e pode receber os depósitos de ambas as partes. Desde que ambas as partes trabalhem juntas, elas podem trabalhar juntas para resolver qualquer contrato através de uma assinatura 2 de 2. Os seguintes mecanismos só são necessários em caso de fraude.
Figura 5: Uma série de transações pré-assinadasFigura 5: Uma série de transações pré-assinadas para executar várias rodadas de desafios e respostas. Esta sequência é gerada durante a configuração.
Vicky escolhe um desafio abrindo um cadeado de hash em sua folha de toque. Isso desbloqueará um Tap específico para Paul e o forçará a executá-lo. O roteiro força Paul a revelar a promessa de porta do desafio de Vicky. Ao repetir esse processo por várias rodadas de consultas, você pode refutar rapidamente quaisquer afirmações inconsistentes.
Se o provador parar de cooperar off-chain com o validador, o validador precisa de uma maneira de forçar o provador a agir on-chain. O validador consegue isso desbloqueando o bloqueio de hash: cada NAND Tapleaf no UTXO do provador só pode ser gasto se o provador souber a pré-imagem mantida pelo certificador. Assim, o provador pode provar que um dado Tapleaf funciona corretamente, revelando suas entradas e saídas, mas apenas se o verificador "desbloqueá-lo" revelando a pré-imagem do hash que protege esse Tapleaf. Ao aplicar uma pesquisa binária, os validadores podem identificar rapidamente o erro do provador após apenas algumas rodadas de desafios e respostas.
Figura 6: Após cada resposta, Vicky pode penalizar o comportamento ambíguo. Se Paul expõe dois valores conflitantes a uma variável, Vicky imediatamente vence o desafio e é autorizada a receber seu depósito. Vicky prova a ambiguidade de Paulo ao revelar qualquer uma das duas protoimagens prometidas por seus bits.
7 Entrada e saída
O provador pode definir a entrada revelando a promessa de bit correspondente. O ideal é que revelem compromissos off-chain para minimizar a ocupação on-chain. Em um caso não cooperante, os validadores podem forçar os provadores a revelar suas entradas on-chain.
Grandes quantidades de dados podem ser processadas através da troca antecipada de encriptação. Desta forma, o provador pode revelar a chave de desencriptação num momento posterior.
A entrada de várias partes também é possível. As portas podem ter pequenos compromissos de ambos os lados.
8 Limitações e Outlook
É ineficiente representar funções em circuitos NAND simples. Usando opcodes mais avançados, os programas podem ser representados de forma mais eficiente. Por exemplo, o Bitcoin Script suporta a adição de números de 32 bits, por isso não precisamos de circuitos binários. Também podemos ter promessas de bits maiores, por exemplo, 32 bits em um único hash. Além disso, o tamanho do script pode chegar a cerca de 4 MB. Assim, podemos implementar muito mais do que uma instrução NAND em cada script folha.
O modelo aqui apresentado limita-se a duas partes. No entanto, pode ser possível ter canais bidirecionais e vinculá-los para formar uma rede semelhante à Lightning Network. Explorar ambas as configurações pode render possibilidades de generalização interessantes. Por exemplo, podemos explorar uma topologia em estrela de 1 a n para uma rede. Outra questão de pesquisa é se podemos aplicar nosso modelo a uma configuração n-to-n e criar fábricas de canais mais complexas. Além disso, podemos combinar nossos sistemas com diferentes protocolos off-chain, como a Lightning Network ou Rollups.
Outras direções de pesquisa incluem memória entre aplicativos, como fazer declarações sobre dados arbitrários gravados na cadeia ou circuitos programáveis off-chain, ou seja, máquinas virtuais off-chain. Técnicas de amostragem mais sofisticadas, semelhantes às STARKs, também podem ser aplicadas, para examinar circuitos em um único turno.
O próximo grande marco é a conclusão de um projeto e implementação BitVM concreto, bem como Tree++, uma linguagem de alto nível para escrever e depurar contratos Bitcoin.
9 Conclusão
Bitcoin é Turing-completo em certo sentido, como a codificação de provas de fraude em grandes Taptrees verifica a execução de qualquer programa. Uma grande limitação deste modelo é que ele só funciona no caso de ambas as partes. Espera-se que a generalização possa ser feita em trabalhos futuros.
Agradecimentos
Um agradecimento especial a Super Testnet e Sam Parker, que sempre acreditaram que o Bitcoin não será Turing-complete.
Referências
[1] Pesquisa Ethereum. Rollups otimistas. 2022.
[2] Salvatore Ingala. Merkleize todas as coisas. , 2022.
Recursos
[1] Equipa de Tradução:
[2] Rollups otimistas 1:
[3] MATT 提案(Merkelize Todas as Coisas)2:
Ver original
Esta página pode conter conteúdo de terceiros, que é fornecido apenas para fins informativos (não para representações/garantias) e não deve ser considerada como um endosso de suas opiniões pela Gate nem como aconselhamento financeiro ou profissional. Consulte a Isenção de responsabilidade para obter detalhes.
BitVM: Calcule qualquer coisa em Bitcoin
Escrito por Robin Linux Tradutor: Denlink Community Translation Group
Resumo
BitVM é um paradigma de computação usado para expressar contratos Bitcoin Turing-completos. Isso não requer nenhuma mudança nas regras de consenso da rede Bitcoin. Ao contrário de realizar cálculos em Bitcoin, eles são simplesmente verificados, semelhante a rollups otimistas. O provador declara que uma determinada função avalia certas entradas para uma determinada saída. Se a alegação for falsa, o verificador pode fazer uma prova concisa de fraude e penalizar os provadores. Usando este mecanismo, qualquer função computável pode ser verificada no Bitcoin.
Prometer um programa grande em um endereço Taproot requer muita computação e comunicação off-chain, mas sua pegada na cadeia é pequena. Desde que as duas partes trabalhem em conjunto, podem realizar cálculos fora da cadeia arbitrariamente complexos e com estado, sem deixar quaisquer vestígios na cadeia. A aplicação em cadeia só é exigida em caso de litígio.
1 Introdução
Por design, a funcionalidade de contrato inteligente do Bitcoin é limitada a operações básicas, como assinaturas, bloqueios de tempo e bloqueios de hash. O BitVM cria um novo espaço de design para contratos Bitcoin mais expressivos e computação off-chain. As aplicações potenciais incluem jogos como xadrez, Go ou poker, bem como verificação de prova de validade em contratos Bitcoin. Além disso, pode ser possível fazer a ponte entre o Bitcoin e cadeias externas, construir mercados de previsão ou simular novos opcodes.
A principal desvantagem do modelo apresentado aqui é que ele só funciona com duas configurações, o provador e o verificador. Outra limitação é que, para provadores e verificadores, é necessária muita computação e comunicação off-chain para executar o programa. No entanto, estas questões parecem promissoras para serem abordadas com mais investigação. Neste trabalho, nos concentramos apenas nos principais componentes de um BitVM de duas partes.
2 Esquema
Com os otimistas Rollups 1[2] [3] e a proposta MATT (Merkelize All The Things) 2 Da mesma forma, nossos sistemas são baseados em protocolos de prova de fraude e desafio-resposta. No entanto, o BitVM não requer nenhuma alteração nas regras de consenso do Bitcoin. Os primitivos subjacentes são relativamente simples. É baseado principalmente em bloqueios de hash, bloqueios de tempo e grandes árvores de raiz.
O provador submete o programa pouco a pouco à cadeia, mas validar tudo on-chain consumiria recursos de computação excessivos, de modo que o verificador executa uma série de desafios elaborados para falsificar sucintamente as falsas alegações do provador. Juntos, o provador e o verificador pré-assinam uma série de desafios – responder às transações para resolver quaisquer disputas mais tarde.
O modelo visa simplesmente ilustrar que essa abordagem permite a computação universal no Bitcoin. Para aplicações práticas, devemos considerar modelos mais eficientes.
O protocolo é simples: primeiro, o provador e o verificador compilam o programa em um circuito binário gigante. O provador envia o circuito para um endereço Taproot com um script folha para cada porta lógica nesse endereço. Além disso, eles pré-assinam uma série de transações para apoiar jogos de desafio-resposta entre provadores e verificadores. Agora que eles trocaram todos os dados necessários, eles podem transferir seu depósito on-chain para o endereço Taproot gerado.
Isso ativa o contrato e eles podem começar a trocar dados off-chain para acionar mudanças de estado no circuito. Se o provador fizer quaisquer afirmações falsas, o verificador pode receber o seu depósito. Isto garante que os atacantes perderão sempre os seus depósitos.
Compromisso de Valor de 3 Bits
O compromisso de valor de bits é o componente mais básico deste sistema. Ele permite que o provador defina o valor de um determinado bit para "0" ou "1". Em particular, permite que o provador defina o valor de uma variável entre diferentes scripts e UTXOs. Isso é crítico porque dimensiona o tempo de execução dividindo o tempo de execução da máquina virtual do Bitcoin em várias transações.
A promessa contém dois valores de hash, hash0 e hash1. Em um ponto posterior, o provador define o valor do bit para "0" revelando preimage0 (a pré-imagem de hash0) ou para "1" revelando preimage1 (a pré-imagem de hash1). Se, em algum momento, eles revelarem tanto a pré-imagem0 quanto a pré-imagem1, o validador pode usá-las como prova de fraude e receber o depósito do provador. A isto chama-se uma afirmação contraditória. Ser capaz de punir declarações contraditórias é o que torna um compromisso vinculativo – é um "compromisso baseado em incentivos".
A combinação de promessas de valor de bits com timelocks permite que os validadores forcem o provador a decidir sobre o valor de um determinado bit dentro de um determinado período de tempo.
Figura 1: Implementação de um compromisso de valor de bitsFigura 1: Implementação de um compromisso de 1 bit. Para desbloquear este script, o provador deve revelar uma das pré-imagens de hash0 ou hash1. Neste exemplo de execução, o provador revela hash1 e define o valor do bit como "1". Podemos replicar essa promessa para impor um valor específico em scripts diferentes.
PARA SIMPLIFICAR, A PARTIR DAQUI, VAMOS SUPOR QUE EXISTE UM OPCODE CHAMADO OP BITCOMMITMENT, QUE É UMA ABREVIAÇÃO PARA O SCRIPT ACIMA. O opcode consome dois hashes e uma pré-imagem com hash. Com base no hash que corresponde à pré-imagem, ele coloca um valor de bit na pilha.
4 Promessas de porta lógica
Qualquer função computável pode ser representada como um circuito booleano. A porta NAND é uma porta lógica universal, de modo que qualquer função booleana pode ser composta por elas. Para manter o nosso modelo simples, mostramos como a nossa abordagem funciona com portas NAND simples. Além disso, mostramos como combinar portas arbitrariamente. Tudo isto prova que o BitVM pode representar qualquer circuito.
A realização da promessa do portão NAND é simples. Ele contém promessas de dois bits representando duas entradas e um compromisso de bit representando saídas. O script calcula o valor NAND das duas entradas para garantir que ele corresponda aos bits de saída prometidos.
Figura 2: Compromisso de porta para operações NAND Figura 2: Compromisso de porta para operações NAND. A execução desse script precisa revelar os valores das promessas de bits A, B e C de modo que A NAND B = C seja verdadeiro.
(Aqui, para simplificar, vamos supor que exista um opcode chamado OP NAND.) NA VERDADE, ELE NÃO EXISTE, MAS PODE SER FACILMENTE IMPLEMENTADO USANDO OP BOOLAND E OP NOT. ）
5 Circuito binário promete
Na seção anterior, definimos o compromisso da porta NAND. Podemos representar qualquer circuito combinando promessas de portão. Cada passo da execução é cometido em Tapleaf. Todos eles são mesclados no mesmo endereço Taproot para que o provador possa executar qualquer porta no circuito. A execução do gate requer que o provador abra a promessa de porta correspondente e defina valores para seus bits de entrada e saída.
Taptree pode se tornar enorme e ter um bilhão de scripts Tapleaf, mas sua pegada on-chain é pequena.
Figura 3: Um circuito de exemplo aleatório Figura 3: Um circuito de exemplo aleatório com 8 portas NAND diferentes e 4 entradas A, B, C e D. Usando bilhões de portões, essencialmente qualquer função pode ser definida.
##6 Desafios e Respostas
Não basta comprometer-se com um circuito. A fim de refutar alegações erradas, o verificador deve poder contestar a declaração do provador. Isso pode ser conseguido pré-assinando uma série de transações durante a configuração. Estas transações respondem a → desafios →→ respondem a →... maneira ligada. Se uma das partes deixar de participar, após um período de tempo limite, a outra parte vence o desafio e pode receber os depósitos de ambas as partes. Desde que ambas as partes trabalhem juntas, elas podem trabalhar juntas para resolver qualquer contrato através de uma assinatura 2 de 2. Os seguintes mecanismos só são necessários em caso de fraude.
Vicky escolhe um desafio abrindo um cadeado de hash em sua folha de toque. Isso desbloqueará um Tap específico para Paul e o forçará a executá-lo. O roteiro força Paul a revelar a promessa de porta do desafio de Vicky. Ao repetir esse processo por várias rodadas de consultas, você pode refutar rapidamente quaisquer afirmações inconsistentes.
Se o provador parar de cooperar off-chain com o validador, o validador precisa de uma maneira de forçar o provador a agir on-chain. O validador consegue isso desbloqueando o bloqueio de hash: cada NAND Tapleaf no UTXO do provador só pode ser gasto se o provador souber a pré-imagem mantida pelo certificador. Assim, o provador pode provar que um dado Tapleaf funciona corretamente, revelando suas entradas e saídas, mas apenas se o verificador "desbloqueá-lo" revelando a pré-imagem do hash que protege esse Tapleaf. Ao aplicar uma pesquisa binária, os validadores podem identificar rapidamente o erro do provador após apenas algumas rodadas de desafios e respostas.
7 Entrada e saída
O provador pode definir a entrada revelando a promessa de bit correspondente. O ideal é que revelem compromissos off-chain para minimizar a ocupação on-chain. Em um caso não cooperante, os validadores podem forçar os provadores a revelar suas entradas on-chain.
Grandes quantidades de dados podem ser processadas através da troca antecipada de encriptação. Desta forma, o provador pode revelar a chave de desencriptação num momento posterior.
A entrada de várias partes também é possível. As portas podem ter pequenos compromissos de ambos os lados.
8 Limitações e Outlook
É ineficiente representar funções em circuitos NAND simples. Usando opcodes mais avançados, os programas podem ser representados de forma mais eficiente. Por exemplo, o Bitcoin Script suporta a adição de números de 32 bits, por isso não precisamos de circuitos binários. Também podemos ter promessas de bits maiores, por exemplo, 32 bits em um único hash. Além disso, o tamanho do script pode chegar a cerca de 4 MB. Assim, podemos implementar muito mais do que uma instrução NAND em cada script folha.
O modelo aqui apresentado limita-se a duas partes. No entanto, pode ser possível ter canais bidirecionais e vinculá-los para formar uma rede semelhante à Lightning Network. Explorar ambas as configurações pode render possibilidades de generalização interessantes. Por exemplo, podemos explorar uma topologia em estrela de 1 a n para uma rede. Outra questão de pesquisa é se podemos aplicar nosso modelo a uma configuração n-to-n e criar fábricas de canais mais complexas. Além disso, podemos combinar nossos sistemas com diferentes protocolos off-chain, como a Lightning Network ou Rollups.
Outras direções de pesquisa incluem memória entre aplicativos, como fazer declarações sobre dados arbitrários gravados na cadeia ou circuitos programáveis off-chain, ou seja, máquinas virtuais off-chain. Técnicas de amostragem mais sofisticadas, semelhantes às STARKs, também podem ser aplicadas, para examinar circuitos em um único turno.
O próximo grande marco é a conclusão de um projeto e implementação BitVM concreto, bem como Tree++, uma linguagem de alto nível para escrever e depurar contratos Bitcoin.
9 Conclusão
Bitcoin é Turing-completo em certo sentido, como a codificação de provas de fraude em grandes Taptrees verifica a execução de qualquer programa. Uma grande limitação deste modelo é que ele só funciona no caso de ambas as partes. Espera-se que a generalização possa ser feita em trabalhos futuros.
Agradecimentos
Um agradecimento especial a Super Testnet e Sam Parker, que sempre acreditaram que o Bitcoin não será Turing-complete.
Referências
[1] Pesquisa Ethereum. Rollups otimistas. 2022.
[2] Salvatore Ingala. Merkleize todas as coisas. , 2022.
Recursos
[1] Equipa de Tradução:
[2] Rollups otimistas 1:
[3] MATT 提案(Merkelize Todas as Coisas)2: