Tudo o que você precisa saber sobre gráficos acíclicos direcionados (DAGS)

Grafos acíclicos direcionados são uma categoria geral na teoria dos grafos, ciência da computação e matemática que constituem essencialmente uma ordenação topológica onde vértices (por exemplo, nós, tarefas ou eventos) são acoplados a arestas (setas direcionadas, relações de dependência ou transações) de forma assíncrona (os nós não podem retornar a si mesmos, mas o fluxo vai em uma direção, ou seja, direcionado).

Gráfico DAG

Um DAG multitree. Fonte: Wikipedia

Os DAGs são aplicados na modelagem de muitos tipos de informações onde as coleções de eventos devem ser representadas em como elas influenciam umas às outras (estruturas probabilísticas em Redes bayesianas, registros de dados históricos, sistemas de controle de revisão distribuída, etc.)

Isso se afasta do paradigma da tecnologia blockchain em que a malha blockchain opera encadeando sequências planas de listas e agrupando-as em blocos. Com o blockchain, cada bloco faz referência ao anterior e o inclui, o que leva a gargalos quando muitas transações começam a chegar com muita frequência.

Isso torna difícil chegar a um consenso sobre blocos válidos (o notório problema de escalabilidade). Em um ambiente estruturado de DAG, não há limite teórico no rendimento da transação, pois as transações são diretamente vinculadas em vez de agrupadas e serializadas em uma única via.

O projeto técnico do DAG também permite uma gama mais ampla de algoritmos que podem ser aplicados e, portanto, maior flexibilidade. Existem alguns projetos baseados em DAG por aí, todos muito diferentes uns dos outros e dignos de nota, todos tendo construído sua base de código do zero (em oposição a outro hack de base de código Bitcoin).

Aqui estão algumas propriedades comuns que eles compartilham:

  • Aciclicidade: O tempo flui em uma direção. As transações mais recentes fazem referência às mais antigas, mas não o contrário. Nos ciclos, o grupo de tarefas depende umas das outras (se houvesse ciclos, não haveria ordenação topológica). Em um DAG, cada nó depende dos anteriores que fazem referência a ele. Isso permite que as transações possam ser executadas localmente ou mesmo off-line e processadas, confirmadas ou finalizadas em pontos posteriores.
  •  Latência: A velocidade de execução e os tempos de confirmação não são limitados pelo tamanho do bloco, mas pela largura de banda entre os pares em comunicação. Não há limite teórico para o quanto o sistema pode escalar.
  • Feeless (“pré-minado”): Fornecimento fixo, sem mineração envolvida. Cada emissor de transação é simultaneamente um validador, ou então há representantes ou testemunhas envolvidos em casos de conflitos ou disputas. Isso permite micro e nano transações que limitam o impacto ambiental.
  • Transações de valor zero: Por exemplo. mensagens ou transações sem valor, quer exijam ou não assinaturas digitais e se encaixem em um Pacote UDP.
  • Remoção de banco de dados: Chamado de poda no Nano e instantâneo no IOTA. Esse mecanismo ainda não existe com Byteballs. Ele permite manter o banco de dados reduzido e nós diferentes podem salvar apenas o histórico em que estão interessados ​​ou que são relevantes para eles.

A tecnologia DAG já foi usada em várias criptomoedas à medida que os desenvolvedores buscam ativamente alternativas para a arquitetura atual do blockchain. Abaixo, veremos a tecnologia subjacente de três das mais conhecidas criptomoedas baseadas em DAG.

Nano

Logotipo da Nano

Nano (anteriormente Raiblocks) começou em dezembro de 2014 (fundador Colin LeMahieu liderando o desenvolvimento do protocolo principal) quando o white paper e a implementação beta foram publicados pela primeira vez, tornando-se uma das primeiras criptomoedas baseadas em DAG.

Uma moeda pura focada na entrega de pagamentos peer-to-peer confiáveis ​​e rápidos e transferências de câmbio rápidas para arbitragem, Nano “faz uma coisa e a faz certo” (um lema que reflete Princípio KISS).

O Nano faz uso de uma arquitetura peculiar (denominada block-lattice) que de certa forma se assemelha a uma Lightning Network de dentro para fora. Em outras palavras, ao invés de manter a jurisdição de um blockchain global que é ramificado em cadeias laterais, o Nano já é uma topologia de rede onde cada conta tem seu próprio blockchain (cadeia de contas).

Cada um deles é equivalente ao histórico de transações / saldo da conta e cada cadeia de contas só pode ser atualizada pelo proprietário da conta. Isso também torna responsabilidade de todos quais outras cadeias de bloqueio ele escolhe para realizar transações e fazer negócios.

Este é um recurso de design chave no Nano, onde o acordo de tempo de execução é substituído por um acordo de tempo de design, onde todos concordam por meio da assinatura, verificando que apenas o proprietário da conta pode modificar sua própria cadeia.

A abordagem minimalista do Nano parece se alinhar com as normas da filosofia UNIX, conforme resumido por Doug McIlroy no Bell System Technical Journal assim:

  1. Faça com que cada programa execute bem uma coisa. Para fazer um novo trabalho, crie de novo, em vez de complicar programas antigos, adicionando novos “recursos”.
  2. Espere que a saída de cada programa se torne a entrada de outro programa ainda desconhecido. Não sobrecarregue a saída com informações estranhas. Evite formatos de entrada estritamente colunares ou binários. Não insista em contribuições interativas.
  3. Projete e construa software, até mesmo sistemas operacionais, para serem testados o quanto antes, de preferência em semanas. Não hesite em jogar fora as peças desajeitadas e reconstruí-las.
  4. Use ferramentas em vez de ajuda não qualificada para aliviar uma tarefa de programação, mesmo se você tiver que desviar para construir as ferramentas e esperar jogar algumas delas fora depois de terminar de usá-las.

Visão geral do protocolo Nano

Visão geral do protocolo Nano

Nano TPS. Fonte: youtube.com

Seguindo a filosofia UNIX, o protocolo Nano é extremamente leve, adequando-se ao tamanho mínimo do pacote de transmissão UDP necessário. O User Datagram Protocol é usado para comunicar rapidamente mensagens muito curtas, garantindo apenas a integridade dos dados. É capaz de funcionar em hardware de baixo consumo de energia ou legado com recursos mínimos, visando ser ideal para o uso diário prático (para comprar café em vez de armazenar valor).

O consenso no Nano é obtido quando os usuários escolhem contas representativas para votar em caso de uma disputa. A votação de consenso é acionada apenas no caso de transações maliciosas e nós representativos com saldos de conta mais elevados são ponderados de forma mais favorável.

Isso dá incentivos aos titulares de Nano para participarem da manutenção da integridade do razão. Da mesma forma, no caso de um fork, a gênese precisa ser refeita e a partir daí tudo se redistribui. Isso é o que torna essas ocorrências bastante improváveis. Os representantes são explicados com mais detalhes no documentação e uma lista de representantes (atualmente mais de 3.000) pode ser encontrada aqui.

Entre os desenvolvedores contribuintes (Nano é amplamente voltado para a comunidade) está também o engenheiro de software do PayPal, Daniel Brain, que construiu um checkout simples para Nano isso torna a implementação rápida e fácil para os comerciantes. Além disso, os comerciantes maiores podem configurar seus próprios nós para lidar com cargas de transações.

Em relação ao fornecimento, o Nano é “pré-minerado”, pois a conta de gênese inicial contém o saldo fixo total (de 133.248.290) que é então distribuído entre outras contas que compõem a topologia da cadeia DAG.

O saldo do gênesis é mantido em um armazenamento refrigerado em um cofre e os blocos passam do gênesis para uma conta de destino a cada uma vez por semana, para minimizar o número de blocos vivos não distribuídos. A distribuição no início ocorria por meio de uma torneira pública onde é necessário resolver captchas como Prova de Trabalho (PoW) um mecanismo anti-spam.

Curiosamente, grande parte da resolução do captcha inicial foi realizada por venezuelanos (o aumento de pesquisas na Venezuela pode ser visto em tendências do Google), o que fez com que muitos XRB distribuídos passassem para as mãos de alguns dos mais pobres que, de outra forma, não teriam acesso à criptografia.

Byteball

Byteball

Byteball (Bytes) é outra criptomoeda baseada em DAG desenvolvida por Anton Churyumov (graduado pela Universidade Russa de Pesquisa Nuclear) que foi lançada em 25 de dezembro de 2016. Byteball se concentra em pagamentos condicionais e contratos legíveis por humanos realizando ações simples de forma interativa (ou seja, humana contratos e acordos inteligentes legíveis por meio de chatbots de atestado e oráculos on-chain).

Em contraste, os contratos inteligentes Ethereum são mais complexos e legíveis pelo programador, visando uma lógica de negócios estrita do tipo institucional, enquanto Byteball se destina ao uso diário mais imediato.

Os dados armazenados no DAG da Byteball permitem que os usuários protejam os dados uns dos outros, anexando-os a unidades de dados anteriores criadas por outros usuários e as taxas são proporcionais à quantidade de recursos consumidos, neste caso igual ao tamanho da transação em bytes. Esta barreira de entrada é o mecanismo anti-spam de Byteball e reflete aproximadamente a utilidade de armazenamento para o usuário e o custo de armazenamento para a rede.

A moeda nativa do Byteball também são bytes e parte da taxa vai para os supervisores da rede chamados de testemunhas. Paga-se um valor fixo de 1 byte da moeda para armazenar 1 byte de dados de transação.

As testemunhas são indivíduos publicamente identificáveis ​​com identidade do mundo real que carimbam cada transação garantindo a integridade da cadeia principal. Pode-se escolher entre eles na interface da carteira da mesma forma que seleciona seus representantes na carteira do Nano. Existem 12 testemunhas envolvidas em cada transação que ocorre.

A carteira também permite o envio de bytes para contas de e-mail ou através de aplicativos de bate-papo como WhatsApp ou Telegram. BlackBytes é a moeda complementar usada para transações P2P totalmente anônimas e não rastreáveis.

IOTA

IOTA Logo

IOTA nasceu originalmente de uma iniciativa de hardware (JINN) com o objetivo de produzir um microprocessador baseado em ternário fornecendo suporte de hardware para computação distribuída geral como a base fundamental para dispositivos IoT conectados e, eventualmente, alavancando tecnologias de IA.

JINN foi o primeiro anunciado em 23 de setembro de 2014 no fórum NXT e posteriormente evoluiu para IOTA levando à fundação da Fundação IOTA como uma organização sem fins lucrativos com sede em Berlim em 2017.

A base é dedicada ao desenvolvimento de padrões industriais e protocolos abertos necessários para a infraestrutura IoT como a espinha dorsal de uma economia máquina a máquina. Nesse esforço, o DAG da IOTA (chamado de “o emaranhado”) é fundamentalmente diferente de outras criptomoedas e não pode ser concebido da mesma maneira ou medido pelos mesmos padrões.

A abordagem necessariamente heterodoxa que a IOTA adota é relevante precisamente para o estado de coisas na IoT hoje e os problemas enfrentados com a proliferação massiva de vulnerabilidades entre dispositivos conectados que quadruplicaram apenas em 2017.

O emaranhado da IOTA constitui uma máquina abstrata de um rizomático tipo, “estabelecendo incessantemente conexões entre cadeias semióticas”. Serguei Popov, um Ph.D. em Matemática da Universidade de Moscou. e um dos principais fundadores do projeto IOTA Publicados um artigo de acompanhamento no dia 12 de maio.

Este analisou os aspectos teóricos do jogo de jogadores “egoístas” dentro do emaranhado, demonstrando em simulações a existência de um jogo “quase simétrico” Equilíbrio de Nash na dinâmica de como o emaranhado deve funcionar. Em outras palavras, como jogadores “egoístas” irão, no entanto, cooperar com a rede escolhendo estratégias de apego próximas ou semelhantes às “recomendadas”.

O Coordenador IOTA (Coo)

Coordenador IOTA

Fonte: iota.org

Em termos de coordenação de protocolo entre o Coo e os nós de entrada são um processo bidirecional. Como o Coo emite as transações de marco de valor zero da mesma maneira em que os nós, de certo modo, policiam o Coo para seguir as regras definidas de cooperação, sincronizando as transações com esses marcos.

O emaranhado com valor DAG da IOTA gera um estocástico espaço de “inconsistência” aleatória na superfície. Em seguida, ele executará amostragens de distribuição de probabilidade em um modelo baseado em treinamento para alcançar consistência em toda a rede.

Isso é feito em uma malha autossustentável de redes oportunistas que se conectam e interagem potencialmente em mecanismos comumente compartilhados e princípios definidos por protocolo. Na verdade, isso ocorre por necessidade situacional ou demanda de um recurso específico, uma vez que os sub-emaranhados podem se desprender e religar dinamicamente ao emaranhado principal.

Na estrutura de dados única do emaranhado, não há blocos construídos sequencialmente em blocos anteriores de dados de transação, mas em vez disso, cada transação deve concatenar dois outros de entrada para verificar e verificar. Isso irá acoplar funções de usuário e mantenedor (“minerador”) ao invés de separar funções em contingentes heterogêneos cujos interesses podem nem sempre coincidir.

Isso também permite o processamento simultâneo de transações (em vez de uma por uma) em um vórtice de uma rede cada vez maior de conexões que diminui exponencialmente os tempos de confirmação. Também não há atrasos de transações não confirmadas devido a restrições de tamanho de bloco.

Na lógica de design subjacente da IOTA, a velocidade é favorecida em relação à consistência, ao mesmo tempo que permite escalabilidade ilimitada (ou seja, a velocidade é uma função do tamanho da rede) e o consenso é direcionado como uma inferência direta de captura-puxar-enredar (em vez de verificar-validar- hash-append) com instantâneos periódicos eliminando saldos zero reciclados.

O modo de seleção de dicas (a dica é uma transação de entrada) para verificar a autenticidade das transações de entrada as executa em relação a todo o histórico do emaranhado e, quando uma transação entra no emaranhado, ela o faz no modo de ramificação. Isso significa que ele vai esperar para ser selecionado novamente pelo mesmo processo, pois acumula confiabilidade e fica incorporado mais profundamente na rede.

Estabelecendo Consenso

Usando o coordenador, a presente definição de consenso é simples: qualquer transação referenciada por um marco (uma transação de valor zero) é confirmada, e as outras não. Isso é extremamente importante na fase de crescimento da infância da rede, caso contrário, um invasor pode começar a superar o ritmo da rede. Ao atacar a rede, eles podem começar a gastar o dobro, referenciando suas próprias transações, criando um subemaranhado de parasitas e se infiltrando na rede.

O token IOTA exclusivo, neste caso, adquire seu verdadeiro valor apenas dentro de seu próprio sistema circulatório orgânico para o qual foi projetado especificamente. Isso acontece apenas quando o próprio emaranhado está maduro o suficiente e é capaz de se defender organicamente de ataques. Isso só acontecerá depois de acumular massa crítica suficiente do peso total das transações referenciadas para garantir a Cadeia de Markov passeios aleatórios funcionarão como pretendido.

Visualização IOTA Tangle

Visualização do emaranhado IOTA. Fonte: Steemit.

Os métodos de Markov Chain Monte Carlo, como tais, são uma categoria de algoritmos usados ​​na análise de dados Bayesiana que calcula modelos que requerem integrações em milhares de parâmetros desconhecidos em relação a distribuições de probabilidade de alta dimensão complicadas.

A análise de dados bayesiana em geral tem se mostrado particularmente útil na solução de problemas complexos onde há grande incerteza inerente que precisa ser quantificada. É potencialmente o método mais eficiente em termos de informações para se ajustar a um modelo estatístico, mas também o mais intensivo em termos de computação.

Também é interessante notar que em abril de 2017, Serguei Popov e o Prof. Gideon Samid do Instituto de Tecnologia de Israel (e um membro da Fundação IOTA recentemente ingressou) publicou recentemente um papel sobre o assunto.

Nele, eles propuseram substituir a complexidade pseudo-aleatória das funções hash criptográficas usadas atualmente por uma mais simples computacionalmente e verdadeiramente aleatória. Isso, é claro, só faria sentido à luz do microprocessador mencionado acima e uma rede grande o suficiente (emaranhado) no futuro.

Uma visão geral rápida do protocolo IOTA também pode ser encontrada aqui.

Moedas com base em DAG lavráveis

Mesmo que o Nano e o IOTA sejam pré-minerados e de fornecimento fixo, existem opções para minerar Monero e obter XRBs ou iotas no navegador (principalmente para fins de teste no desenvolvimento de aplicativos).

Existem, entretanto, criptomoedas baseadas em DAG que permitem mineração acessível e distribuída. Um deles é Burstcoin, um projeto que começou em 2014 derivado do NXT na época (mas também construído em sua própria base de código) que garante a consistência criptográfica das transações por meio de um algoritmo de consenso de Prova de Capacidade (usando disco rígido de baixo consumo e baixo custo unidades).

Semelhante à rede relâmpago, Burst constitui um blockchain principal para armazenamento absoluto / contabilidade e ramificação de canais de transação estruturada DAG de propósito geral (uma camada chamada Dymaxion) para propagação e verificação que são validadas na cadeia principal.

Cada canal pode ser aberto com parâmetros e propriedades personalizados, como duração definida, meta-moeda própria apoiada por Burst, grau de anonimato, tamanho da rede, etc..

Existe um torneira pública fornecido e o Burst é negociável na Poloniex e Bittrex.

Punhal (XDAG) é outro projeto lançado recentemente (mainnet foi implantado em 5 de janeiro de 2018) que permite a mineração de CPU / GPU e algo semelhante a outras arquiteturas, blocos de pares, transações e endereços em uma única unidade.

Resumo

No geral, todos os três ecossistemas DAG são suficientemente diferentes uns dos outros em seus objetivos, objetivos e utilidade, apesar de algumas sobreposições. No entanto, eles compartilham algumas propriedades comuns. Uma das críticas frequentemente levantadas é que os DAGs são “centralizados”.

É importante refletir um pouco e definir a semântica do que as palavras implicam em diferentes contextos (descentralizado, distribuído, etc.). Devemos então examinar todos os componentes de uma infraestrutura de rede e, em seguida, considerar quais elementos são centralizados, descentralizados, ou quais funções são delegadas onde, etc. e como tudo isso se conecta.

Todos os três projetos DAG podem ser considerados descentralizáveis, uma vez que essa propriedade depende de um uso e adoção mais amplos e, portanto, indivíduos e partes dispostos a assumir determinados papéis. Atualmente, o Nano é organizado em torno de um punhado de hubs representativos, Byteball depende de um punhado de testemunhas para supervisionar a cadeia principal e o IOTA é executado / treinado por um Coordenador Central (a Fundação IOTA) que garante o fluxo de atividades de acordo com o protocolo.

Os incentivos com DAGs não são tanto o lucro imediato derivado da mineração PoW, mas sim um incentivo substancial de redução de custos que naturalmente atrai certas empresas e negócios que têm interesse nas redes enquanto resolvem um problema de negócios para eles.

Imagem em destaque via Fotolia

Mike Owergreen Administrator
Sorry! The Author has not filled his profile.
follow me