A vida passada e presente de MEERDAG

Prefácio

A perspectiva de desenvolvimento do blockchain 3.0 já foi muito discutida, entre as quais o DAG é considerado a nova geração mais promissora da tecnologia blockchain depois do Bitcoin e do Ethereum. Então, qual é a origem do blockchain DAG? Qual é o seu conceito técnico?

DAG e blockchain eram originalmente duas tecnologias diferentes, mas a combinação dos dois, o conceito de "DAG blockchain" e sua primeira aparição no centro das atenções, foi possível graças a dois israelenses, Yonatan Sompolinsky e Aviv Zohar, os pioneiros desse conceito pioneiro. .

O protocolo GHOST proposto por Aviv Zohar foi adotado pela Ethereum no estágio inicial. Este protocolo resolve os problemas de segurança causados ​​por garfos de corrente. A estrutura de dados do blockchain bifurcado evolui de uma única cadeia para uma cadeia de árvore. Mais tarde, Aviv Zohar propôs ainda o protocolo Inclusivo. Sob as regras do protocolo Inclusive, a estrutura de dados do blockchain evolui para um grafo acíclico direcionado (DAG). Com a exploração contínua do DAG pela DAGlabs, o conceito de estrutura BlockDAG e a arquitetura técnica foram gradualmente estabelecidos, durante os quais o protocolo SPECTRE, o protocolo PHANTOM e o protocolo GHOSTDAG foram lançados sucessivamente.

Qitmeer estava explorando protocolos de consenso que abordam a escalabilidade (disponibilidade) sem sacrificar a descentralização (tolerância a falhas de particionamento) e segurança (consistência) no início do projeto e descobriu que coincidia com a filosofia de design do BlockDAG.

Em sentido estrito, o BlockDAG pode ser entendido como uma estrutura técnica de um protocolo de consenso, que visa melhorar ainda mais a tecnologia DAG com alto desempenho de simultaneidade sob a premissa de garantir descentralização e segurança. O mecanismo de consenso PoW baseado em prova de trabalho pode garantir que a rede blockchain seja suficientemente descentralizada, portanto, minerar blocos para gerar blocos tornou-se um recurso técnico importante, por isso é chamado de BlockDAG.

A Equipe Qitmeer fez muitas otimizações em nível de engenharia para os algoritmos de consenso de GHOSTDAG e SPECTRE e criou um protocolo MeerDAG com suas próprias características, mantendo as vantagens de ambos os protocolos.

1. Estrutura básica do DAG

1.1 Como é um DAG?

Estamos todos muito familiarizados com a estrutura de dados da árvore Merkle. Dentro de cada bloco do Bitcoin, a árvore Merkle é utilizada para registrar as informações da transação, veja a imagem abaixo

Pode-se ver que a árvore Merkle pertence a uma estrutura de árvore direcionada, cada vértice na árvore pode apontar apenas para um vértice anterior e todos os dados têm uma direção de fluxo óbvia. A estrutura DAG permite que cada vértice aponte para vários vértices anteriores, e todo o fluxo de dados também tem uma direção óbvia. Outra estrutura de dados é um grafo direcionado. Ao contrário do DAG, um gráfico direcionado permite que os dados fluam de volta, e o fluxo de dados de toda a estrutura não é muito óbvio. Veja a imagem 2 para a diferença entre os três.

1.2 Blockchain é uma estrutura DAG especial

Depois de ter uma compreensão intuitiva da estrutura DAG, vamos entender por que o blockchain é considerado uma estrutura DAG especial?

Se os forks da blockchain estão relacionados à velocidade de geração de blocos e velocidade de transmissão. Quando a velocidade de produção do bloco exceder a velocidade de transmissão, vários blocos serão transmitidos ao mesmo tempo e ocorrerão bifurcações. Quanto mais garfos, pior a segurança. Para reduzir os forks, o Bitcoin encontra um equilíbrio entre desempenho e segurança: um bloco é gerado a cada dez minutos. Agora vamos supor que o tempo para cada bloco seja longo o suficiente para que nenhum novo bloco seja minerado antes que o bloco anterior seja transmitido. Então a estrutura dessa blockchain é uma única cadeia, veja a imagem 3

De fato, devido a atrasos na rede e outros motivos, inevitavelmente ocorrerão bifurcações, de modo que a estrutura real da blockchain será a mostrada na imagem 4, e apenas uma das cadeias principais válidas (branca) será selecionada por meio do princípio da cadeia mais longa do consenso do livro-razão. A informação da transação nos blocos restantes (vermelho) é inválida e não será adotada.

Agora deixe de lado o consenso do livro-razão, ou seja, ignore como selecionar uma cadeia principal eficaz. Do ponto de vista da estrutura de rede subjacente, uma estrutura típica de blockchain é mostrada na imagem 5 e uma estrutura DAG típica é mostrada na imagem 6.

Pode-se ver que a única diferença entre as duas estruturas é que o bloco DAG pode apontar para vários blocos anteriores, enquanto o blockchain pode apontar apenas para o único bloco anterior. Especificamente, o cabeçalho do bloco do blockchain pode conter apenas o valor de hash de um bloco, apontando para o único bloco pai; enquanto o cabeçalho do bloco sob a estrutura DAG pode conter os valores de hash de vários blocos, apontando para diferentes blocos anteriores. Como mostra a imagem 7.

Agora introduzimos o coeficiente de bifurcação K, que se refere ao número de bifurcações que a rede pode permitir.

Quando K=0, toda a rede não permite bifurcações, conforme a imagem 3.

Essa rede que não permite bifurcações é a blockchain.

Bitcoin atende a essa definição; embora o Ethereum tenha bifurcações de blocos tio, esses blocos tio são usados ​​apenas para julgar o peso da cadeia principal e não serão adicionados à cadeia principal no final (registros do bloco tio A informação da transação não está incluída na cadeia principal ), então o Ethereum também atende a essa definição.

O valor K da rede DAG deve ser um número inteiro maior que 0. Portanto, do ponto de vista estrutural, o DAG é uma extensão da estrutura do blockchain e o blockchain é um DAG especial e simplificado.

1.3 O impacto da estrutura DAG no desempenho

Simplificando, podemos considerar o DAG como uma estrutura de rede que permite bifurcações, e o número de bifurcações permitido é determinado pelo coeficiente de bifurcação K.

Então, o que exatamente significa uma rede que permite bifurcações? Isso significa que a velocidade de geração de blocos pode exceder a velocidade de transmissão. Por um lado, isso leva a mais transações empacotadas por unidade de tempo; por outro lado, quando um bloco A está sendo transmitido por toda a rede, outro bloco bifurcado B também está sendo transmitido por toda a rede e, finalmente, alguns nós confirmarão apenas A, outros nós confirmarão apenas B, então o DAG permite nós na rede para registrar diferentes informações ao mesmo tempo. A combinação desses dois aspectos faz com que o DAG apresente as características de alta simultaneidade e fraca sincronização.

O DAG é um tipo de contabilidade assíncrona, que pode melhorar muito a velocidade das informações de processamento da rede, ou seja, TPS.

O blockchain é uma rede de contabilidade síncrona forte, que exige que cada nó na rede registre as mesmas informações ao mesmo tempo. No entanto, esse requisito geralmente limita a capacidade da rede blockchain de processar informações, tornando o TPS relativamente baixo.

Portanto, a questão é: que tipo de consenso deve ser usado para essa rede de contabilidade assíncrona que permite bifurcações? No artigo anterior, mencionaremos em detalhes o mecanismo de consenso baseado em DAG. O mecanismo de consenso é dividido em consenso de bloco e consenso de ledger. O consenso de bloco do DAG pode ser o mesmo do blockchain. Por exemplo, POW também é usado. Como bifurcações são permitidas, o tempo de geração do bloco pode ser definido muito curto. O consenso do bloco também pode ser diferente do blockchain. Por exemplo, o projeto IOTA cancela diretamente o processo de embalagem e geração de blocos. Assim que uma transação ocorrer, ela será gravada na rede imediatamente (cada bloco no diagrama DAG não é um bloco, mas uma caneta. transação), obtendo assim a capacidade de processamento de transações em velocidade ultra-alta.

O consenso do ledger DAG é muito mais complexo que o blockchain. Como evitar que os nós façam o mal? Como filtrar quando há duas transações contraditórias? Como evitar "gastos duplos"? Com a complexidade da estrutura de rede subjacente, o consenso do livro-razão também recebe requisitos mais elevados. Ele será destacado nos próximos artigos.

1.4 TXDAG e BlockDAG

A diferença entre o BlockDAG generalizado (gráfico de blocos) e o TxDAG (DAG transacional, DAG transacional). Em termos gerais ou em termos de estruturas de dados, BlockDAG e TxDAG são apenas duas estruturas de dados diferentes. A diferença é que o primeiro irá empacotar múltiplas transações em blocos, e o ledger é organizado por blocos; enquanto o segundo não possui conceito de blocos, sendo o ledger composto por transações, que também pode ser entendido como apenas uma transação em um bloco. Como a transação possui muitas informações descritivas de transação comuns, ou seja, as informações do cabeçalho, essa parte da informação pode ser armazenada no bloco, e a transação só precisa salvar as diferentes partes da transação, para que o processo HASH (mineração) é ignorado e carregado diretamente na cadeia. Como o BlockDAG não apenas retém a alta simultaneidade do DAG,

1.5 Vantagens do DAG

Comparado com o blockchain, o DAG é na verdade a diferença entre um grafo e uma cadeia. Para uma cadeia, ela não pode lidar apenas com uma parte, porque há apenas um grau de entrada e um grau de saída da cadeia, e os nós da cadeia não podem ser divididos em vários nós para processar, mas é possível para gráficos, como os grafos podem ter vários graus de saída, os nós conectados por vários graus de saída podem ser processados ​​ao mesmo tempo.

Para a rede da cadeia, não é que a capacidade de processamento dos nós não seja forte, mas a estrutura da cadeia não pode ser calculada em paralelo, e o tempo perdido é principalmente tempo de espera: um é iniciar uma transação, que precisa ser sincronizada com todos os nós; o outro é o tempo de confirmação, quando há a confirmação de um nó que precisa ser sincronizado com toda a rede. Para o DAG, não existe esse problema. Quando a carteira inicia uma transação, ela não precisa esperar quantas transações ela possui antes. Ele só precisa passar por verificação parcial, transmissão de rede e outras verificações parciais, o que equivale a descentralizar a confirmação da transação. Os nós estão fazendo um trabalho semelhante aos quebra-cabeças, unindo suas próprias transações com as confirmadas por outros.

Portanto, conclui-se que o DAG apresenta as seguintes vantagens:

(1). Velocidade de transação rápida

Ao atingir o mesmo nível de descentralização e segurança que o Bitcoin e o Ethereum, o processamento local DAG e a liquidação paralela podem aumentar muito a velocidade da transação, fazendo com que o throughput da transação (TPS) e o atraso final sejam promovidos em mais de duas ordens de magnitude.

(2). Forte capacidade de expansão

Como o DAG suporta contabilidade assíncrona, os nós da rede podem processar novas transações em paralelo sem esperar pela sincronização de dados de outros nós, evitando desperdício de tempo, melhorando a eficiência das transações e permitindo que cada nó participante da contabilidade seja estendido rapidamente. Portanto, o DAG é muito adequado para projetos de pagamento, como micropagamento transfronteiriço e cenários de negócios financeiros inclusivos defendidos pela equipe Qitmeer.

(3). Mais difícil de modificar maliciosamente

Em comparação com a estrutura da cadeia, é muito mais difícil modificar maliciosamente em um DAG porque o DAG tem muitos graus de entrada e saída e, se um nó for modificado, os graus de entrada correspondentes deverão ser modificados.

2. Passado e Presente do MEERDAG

2.1 Origem da Tecnologia DAG

Em 2013, no bitcointalk.org, o famoso local de nascimento do blockchain, um estudioso da Universidade Hebraica de Israel com o ID Avivz78 propôs introduzir o conceito DAG como um algoritmo de consenso na estrutura do blockchain e criou o protocolo GHOST.

Depois que o protocolo GHOST foi proposto, Yonatan Sompolinsky propôs outra nova ideia em que os blocos recém-gerados apontam para todos os blocos finais bifurcados conhecidos, ou seja, um bloco tem vários pais, ponto em que

a cadeia de blocos muda de uma única cadeia para uma estrutura que consiste em várias cadeias bifurcadas juntas, e essa estrutura de cadeia é chamada de DAG (gráfico acíclico direcionado).

Em 2016, foi lançado o documento do protocolo técnico SPECTRE, que melhorou ainda mais os detalhes da arquitetura técnica, formou o protótipo do protocolo blockDAG de primeira geração e propôs a grande ideia de atraso de rede sem parametrização (ou adaptação de parâmetro de atraso).

Em 2018, DAGlabs lançou o protocolo PHANTOM. Resolvido o problema de que o protocolo SPECTRE não pode negociar classificação linear e continuou a otimizá-lo para formar o protocolo GHOSTDAG, que é o primeiro protocolo BlockDAG de nível industrial e também marca a maturidade do BlockDAG.

No final do documento do protocolo GHOSTDAG, Yonatan Sompolinsky imaginou um possível protocolo combinando GHOSTDAG + SPECTRE, mas não o apresentou em detalhes

3. Considerações sobre a seleção de tecnologia do MEERDAG

3.1 Pensamento sobre a seleção da tecnologia MEERDAG

No primeiro estágio da Qitmeer Network, Mecca Network, coincidiu com o aumento da exploração da tecnologia de expansão, confrontada com muitas soluções de expansão mainstream on-chain e off-chain, ao selecionar a tecnologia de cadeia pública Qitmeer, também enfrentou uma escolha difícil.

Em termos de seleção de tecnologia de expansão, a indústria geralmente enfrenta um problema de triângulo impossível. É impossível alcançar escalabilidade (escalabilidade), descentralização (descentralização) e segurança (segurança) ao mesmo tempo, e apenas dois dos três podem ser alcançados. A equipe Qitmeer naquela época também enfrentou esse problema. Depois de estudar muitas soluções de expansão, uma tecnologia chamada BlockDAG foi finalmente escolhida pela equipe.

3.2 Breve Introdução ao Protocolo SPECTRE

SPECTRE é um protocolo blockDAG que suporta confirmação rápida. O algoritmo de consenso do SPECTRE é um algoritmo de votação. Uma vez encontrada uma transação conflitante, o bloco que contém a transação conflitante será utilizado como candidato a aceitar os votos de todos os blocos, sendo um voto para cada bloco. A votação da SPECTRE tem um efeito de amplificação. Por exemplo, um bloco seguirá a maioria dos votos que concentrou no passado, então a velocidade de convergência é muito rápida, e uma pequena diferença no número de votos pode resultar em uma grande vantagem para o vencedor. Deixe os blocos honestos votarem nos blocos honestos, e os últimos blocos honestos darão poder de empilhamento anterior, para que ataques maliciosos falhem e a segurança da rede seja garantida.

O SPECTRE só pode garantir a confirmação rápida de blocos honestos. Para dois blocos conflitantes cujo tempo de liberação está próximo, o tempo de confirmação do SPECTRE é incerto. Este é o conceito de atividade fraca proposto pelo SPECTRE, ou seja, não se pode garantir que todos os blocos possam ser confirmados em um prazo razoável.

O SPECTRE é um protocolo de consenso baseado no sistema de transação. No sistema de transações, apenas os malfeitores podem criar transações de gasto duplo. Ou seja, as transações de gasto duplo não terão muito impacto nos blocos honestos. Além disso, fazer transações de gasto duplo é muito rigoroso no controle de tempo e é difícil causar ataques em circunstâncias normais. Portanto, a equipe Qitmeer acredita que o problema de atividade fraca do SPECTRE é aceitável em projetos reais.

3.3 Breve Introdução ao Protocolo GHOSTDAG

Como você pode ver no perfil do SPECTRE acima, o SPECTRE é muito bom para solucionar problemas de transações conflitantes e se defender contra ataques. Se um projeto for usado apenas para fins de pagamento como o Bitcoin, a confirmação rápida do protocolo SPECTRE é suficiente. Mas se você deseja integrar contratos inteligentes, o SPECTRE não pode fazê-lo.

Porque o SPECTRE só pode fazer uma classificação relativa de transações conflitantes (julgando a ordem das transações conflitantes), mas não pode fazer uma classificação absoluta para todos os blocos. Como a linguagem do contrato inteligente deve ser Turing completa, assim como escrevemos um programa de computador, precisamos executar várias operações em uma ordem estrita, portanto, a rede com a função de contrato inteligente tem uma característica: as transações na rede podem ser cronometrado Faça uma classificação linear (cronológica) uma após a outra.

Em resposta, Yonatan Sompolinsky projetou recentemente o protocolo GHOSTDAG para formar uma ordem linear para os blocos DAG. SPECTRE e GHOSTDAG são dois protocolos completos e independentes, não um complementando o outro.

O mecanismo de mineração do GHOSTDAG é o mesmo do SPECTRE, que irá gerar o mesmo tipo de estrutura DAG. A diferença é que o GHOSTDAG julga se o bloco é honesto ou malicioso analisando a conectividade do bloco, classifica os blocos de acordo com a classificação e gera um bloco DAG estrito. A ordem linear da transação conflitante é julgada pela ordem linear.

O protocolo GHOSTDAG não apenas permite que o DAG obtenha recursos de ordenação linear de transações, mas também resolve o problema de atividade fraca do protocolo SPECTRE. O protocolo GHOSTDAG também é o primeiro protocolo blockDAG que suporta ordenação linear de transações.

3.4 Protocolo MEERDAG

O possível protocolo combinando GHOSTDAG+SPECTRE que Yonatan Sompolinsky imaginou no final do documento do protocolo GHOSTDAG é mais sobre fornecer orientação em termos de ideias, e o foco está em demonstrar o rigor do algoritmo, que envolve muitas questões práticas de engenharia e precisa ser baseado no real A situação é constantemente praticada e testada, e um dos problemas mais típicos é o desempenho. Se for implementado diretamente de acordo com o algoritmo de referência no texto original, o desempenho é quase inaceitável.

A equipe Qitmeer considera que os cenários de aplicação subjacentes da cadeia pública são principalmente finanças inclusivas, transações de ativos digitais e gerenciamento da cadeia de suprimentos.

Considerando o mecanismo de recompensa de bloco e os requisitos de consenso do razão para recursos de classificação linear e, ao mesmo tempo, levando em consideração a velocidade de confirmação da transação que é mais importante para a experiência de troca de valor.

O conjunto azul (bloco honesto) do GHOSTDAG é mais difícil de estabilizar e o tempo de confirmação será muito maior que o do SPECTRE. No entanto, como a recompensa do bloco não requer muito tempo de confirmação, ela não afetará a rede. O protocolo GHOSTDAG é escolhido como o protocolo de consenso base e o protocolo SPECTRE é escolhido como o protocolo de consenso assistido.

MeerDAG, uma solução de consenso híbrida que combina SPECTRE e GHOSTDAG, é uma solução de dimensionamento BlockDAG que está em conformidade com as configurações clássicas de blockchain (aberto, justo, seguro, escalável) e é mais compatível com o modelo clássico de blockchain UTXO. Enquanto o blockchain clássico descarta todos os blocos fora da cadeia mais longa, o MeerDAG é um modelo cooperativo que retém o protocolo SPECTRE e mantém todos os blocos, para que possa atingir alto rendimento e fornecer alto rendimento real em nível de transação, bem como confirmação rápida da transação blockchain Serviços. Em segundo lugar, o BlockDAG é baseado na regra da cadeia mais pesada e pode atingir 51% de tolerância a falhas comparável ao Bitcoin. Além disso, a rede BlockDAG não possui nós especiais e não requer que os nós estejam online ou não. Na mineração,

Durante o período da Qitmeer Network Medina, a rede introduziu testes reais de ambiente de poder de computação. A equipe iterou continuamente o algoritmo PoW e melhorou a eficiência do algoritmo, reteve totalmente as vantagens do protocolo GHOSTDAG+SPECTRE e reduziu continuamente a dificuldade de implementação do protocolo na implementação de engenharia. Por exemplo: de acordo com a primeira versão dos papéis do Algoritmo GHOSTDAG, o cálculo de cones inversos precisa ser exaustivo e a complexidade do algoritmo é O(n^3). Após um grande número de testes de nível de engenharia, a complexidade é reduzida em duas ordens de grandeza para O(n), o que atende muito aos requisitos de usabilidade. Sob os requisitos básicos de garantia de segurança, descentralização e justiça, o desempenho do TPS é maximizado.

A Qitmeer Team combinou de forma inovadora o protocolo GHOSTDAG+SPECTRE para formar seu próprio protocolo MeerDAG característico, que se tornou o protótipo técnico da nova geração do BlockDAG. O posicionamento principal da rede subjacente BlockDAG da Qitmeer é servir como uma rede de circulação de valor. Na camada da Camada 2, ele combina o sistema de máquina virtual conectável acionado por MeerEVM para criar aplicativos de blockchain avançados e abraçar toda a ecologia de blockchain.

Referência:
[1] Do blockchain ao DAG (2) -- a estrutura básica do DAG,https://mp.weixin.qq.com/s/Mc2uEOLtT_Z3OMapNh1TGg
[2] De Blockchains a blockDAGs，https://www.youtube.com/watch?v=tk38AAV_whw
[3] Jeff Zhou: tecnologia blockchain assíncrona DAG de alta velocidade,https://www.jianshu.com/p/45d73e0e74ec
[4]GHOST, SPECTRE, PHANTOM Technicial Theory，https://mp.weixin.qq.com/s/nGR0ld73oXgs_p_MtDcv-Q
[5]Equipe Qitmeer – “Papel Técnico Qitmeer”