Tangle

Imagem sobre Grafos Aciclicos Dirigidos

Tangle é uma tecnologia de registro distribuído (em Inglês, distributed ledger) com arquitetura baseada em grafos acíclicos dirigidos (DAG), diferentemente de sua tecnologia oriunda, Blockchains, que é caracterizada por ser uma cadeia de blocos com tamanho finito, que podem apenas ser produzidos (e validados) em intervalos de tempo discretos regulares. Sendo assim, a arquitetura das Blockchains resultam num gargalo de produção (de blocos) o que leva a altas taxas de transação que devem ser pagas à mineradores. Foi então em meados de 2014, em forúms do Nxt e do Bitcointalk, que começaram a ser discutidas as primeiras ideias acerca dos registros distribuídos baseados em DAGs, com o principal objetivo de eliminar as taxas e o gargalo de produção presente em Blockchains, criando um ambiente homogêneo onde usuários são quem verificam as transações da rede.

Em sua forma inicial ainda existiam algumas questões que precisavam ser abordadas pela nova tecnologia, como por exemplo: Onde o próximo bloco/transação deve ser adicionado? E como/quando uma transação será considerada como confirmada (ideia consenso da rede)? Foi depois de intensa discussão e pensamento que surgiu o projeto conhecido como IOTA com uma nova tecnologia denominada de Tangle capaz de resolver as questões levantadas. Nesse sistema, cada transação (representada por um nó do grafo) precisa aprovar duas transações anteriores. O consenso pode ser provido de forma distribuída, como sugerido no artigo original da tecnologia, utilizando algoritmos Markov Chain Monte Carlo (MCMC).

Princípios Fundamentais

Gargalo de produção da blockchain e da tangle

A decisão de utilizar um grafo acíclico dirigido, em vez de uma Blockchain, permite maior escalabilidade, quando comparada com sua oriunda, pois Blockchains possuem um limite de transações inerentes. Isso se da pois caso o tamanho dos blocos seja muito grande ou a taxa de emissão de novos blocos muito pequena, novos forks acontecerão com frequência. Quando um fork não-intencional desse tipo acontece, diversos novos blocos são adicionados a cadeia (chain) em tempos similares, e a rede precisa decidir entre eles. A Tangle pode ser vista como uma alternativa a Blockchains que prioriza disponibilidade acima de consistência seguindo o Teorema CAP.

Com a utilização de DAGs também se sabe que forks vão acontecer com frequência, entretanto, um fork não precisa ser único. Ramificações divergentes podem ser "fundidos" (merged) desde que sejam consistentes entre eles. Dessa forma, a taxa de emissão de transações é limitada apenas pela latência de comunicação entre os usuários da rede.

Validações

A Tangle é uma DAG, onde vértices representam transações e arestas representam validações. Pela forma a qual a Tangle é definida, para um usuário realizar uma transação, ele antes precisa validar duas transações anteriores. Transações adicionadas na rede, e que ainda não foram validadas, são chamadas de tips; idealmente novas transações devem validar diretamente uma tip e consequentemente validar de maneira indireta todas as transações que precedem a tip em questão. Com isso essa tecnologia elimina a necessidade de se separar os usuários da rede pela função a qual exercem, em outras palavras, não existe distinção entre quem valida e quem gera transações, chamados, respectivamente, de mineradores e usuários comuns no caso das Blockchains. Adicionalmente, por não precisar beneficiar a "classe" dos mineradores, a Tangle elimina as taxas de transação.

Esse princípio de ajuda, onde quanto maior a utilização de uma rede Tangle maior a quantidade de transações validadas, é um dos, se não o principal fator, que permite a Tangle atingir sua alta taxa de escalabilidade.

Validação Indireta

Validação direta de X em A e indireta de Y e B em A.

Como citado anteriormente, existem dois tipos de validações numa rede Tangle: validações diretas e indiretas. Como os nós da DAG representam transações e as arestas representam validações diretas, falta apenas definir como funcionam as validações indiretas. Uma transação valida indiretamente uma outra transação se existe um caminho direcionado de tamanho pelo menos 2 (dois).

Incentivo

Todos querem ser ajudados por outros, mas poucos se preocupam em ajudar os outros antes. Para resolver essa questão sem introduzir um incentivo financeiro (taxas de transação), é necessário mudar a perspectiva do que pode ser um incentivo. Na Tangle o incentivo é simplesmente não ser prejudicado por outros, ou seja, ajude outros e outros irão lhe ajudar; entretanto, caso você escolha não ajudar outros, outros também não irão lhe ajudar.

Quando lidamos com seres humanos, ninguém pode garantir que isso seja seguido, porém, no ambiente da Internet das Coisas (IoT), podemos assumir que a grande maioria dos participantes irão seguir a estratégia de aprovação recomendada.

Adicionalmente, nós da rede calculam algumas estatísticas sobre quantas transações são recebidas por um nó vizinho, dessa forma, alguns nós podem ser ignorados pelos seus vizinhos quando mostrarem "preguiça" em relação a propagação de transações. Dessa forma, todos os nós continuam trabalhando mesmo quando não criam transações com tanta frequência.

Transações

Como citado anteriormente, para qualquer transação virar um nó do grafo (entrar na rede), o usuário que submete a transação deve confirmar duas transações anteriores. É evidente que para a rede progredir, as transações a serem validadas devem ser as, também citadas, tips (transações que ainda não foram validadas). Entretanto, devido a latência na comunicação, como é possível garantir que uma transação não tenha sido validada por um outro usuário pouco tempo atrás?

É com esse intuito que foram desenvolvidas estratégias de aprovação. Infelizmente, não é possível forçar que todos os usuários da rede selecione as tips quando precisar validar transações novas e não-contraditórias. Na verdade um usuário que não se preocupe em ajudar os outros pode facilmente escolher duas transações antigas e aprová-las sempre que precisar sem precisar fazer o trabalho pesado de validar a consistência de algumas tips e, dessa forma, adicionar novas informações no sistema. O que acontece é que, se todos os participantes da rede se comportarem de tal forma, então nenhuma nova transação será aprovada (nem mesmo a criada pelo usuário "malicioso") e a rede vai efetivamente parar. Sendo assim, é necessário que exista uma espécie de incentivo para que os participantes colaborem e aprovem transações recentes.

O usuário/nó com o intuito de enviar uma nova transação, tendo passado pela primeira etapa de escolher duas outras transações para aprovar, deve checar se as transações não são conflitantes; transações conflitantes não devem ser aprovadas.

Por fim, para que o nó emita uma transação valida, ele precisa resolver um quebra-cabeça criptográfico (em inglês, cryptographic puzzle). O desafio consiste em encontrar um valor de nonce cuja hash da concatenação desse nonce com alguma informação da transação aprovada tenha uma forma em particular. Como um exemplo, podemos olhar para o desafio criptográfico do Bitcoin, onde a hash final deve conter um número predefinido de zeros à esquerda.

Transação Gênesis

Outra característica que vale a pena ser comentada é a existência da transação gênesis, que é validado direta- ou indiretamente por todos os futuros vértices da rede. A criação de novos tokens, de uma criptomoeda baseada na Tangle, só é possível nesse vértice inicial, impossibilitando a emissão de novos tokens no futuro, criando um efeito de deflação, similar ao de sua tecnologia oriunda, a Blockchain.

Peso da Transação

O peso de uma transação é proporcional à quantidade de trabalho investido pelo nó gerador. Na atual implementação da IOTA, a criptomoeda que introduziu a Tangle, o peso de uma transação pode apenas assumir valores $v$, tal que, $v=3^{n}$, onde $n$ é um inteiro positivo pertencente a um intervalo não-vazio de valores aceitáveis.

Segundo o artigo que introduz a Tangle, na prática, é irrelevante saber como o peso de uma transação foi obtido. A ideia geral é que transações com maior peso são consideradas mais "importantes". Adicionalmente, a fim de evitar spamming e outros tipos de ataques, é considerado que não existe um nó/entidade na rede capaz de criar uma abundância de transações com pesos "aceitáveis" dentro de um curto período de tempo.

Peso Cumulativo

Estrutura da Tangle com pesos nas transações antes e depois da emissão de uma nova transação, X.

Outra noção presente na Tangle são pesos cumulativos, que são definidos como a soma do peso de uma transação $A$ com o peso de todas as transações que validam direta- ou indiretamente a transação $A$

Na figura ao lado vemos a estrutura da Tangle com os pesos das transações no canto inferior direito de cada caixa (que representa uma transação) e com os pesos cumulativos em negrito no canto superior esquerdo de cada caixa. Podemos ver como os pesos cumulativos modificam após a adição de uma nova transação $X$.

Tomando como base a transação $F$, diretamente validada por $B$ e $E$ e indiretamente validada por $A$ e $C$, o peso cumulativo de $F$, dado pela função $P'_{F}$ é dado por:

$P'_{F}=P_{F}+P_{B}+P_{E}+P_{A}+P_{C}$

onde a função $P$ representa o peso próprio da transação em questão, resultando em:

$P'_{F}=9=3+3+1+1+1$

Altura, Profundidade e Score

Tangle com pesos próprios para cada transação e com scores calculados para as transações A e C.

Na rede Tangle existem algumas outras variáveis adicionais, são elas:

• Altura, que representa o tamanho do maior caminho direcionado até a transação gênesis;
• Profundidade, que é o tamanho do maior caminho direcionado de uma tip até a transação em questão;
• Score é definido como a soma de todos os pesos próprios das transações validadas pela transação em questão com seu peso próprio.

Na figura ao lado, temos a transação $G$ com altura e profundidade sendo, respectivamente, 1 e 4, enquanto $D$ tem sua altura e profundidade definidas, respectivamente como 3 e 2. Podemos perceber que a profundidade de $G$ é dada pelo caminho $F,D,B,A$, sendo $A$ a tip com caminho mais longo que valida $G$.

Adicionalmente, na mesma figura, podemos perceber que $A$ e $C$ são as únicas tips na rede e que o score de $A$ é dado pela soma dos pesos próprios de $A,B,D,F$ e $G$ que é igual a $1+3+1+3+1=9$. Analogamente temos que o score de $C$ é igual a: $1+1+1+3+1=7$

Estratégias de Aprovação

É importante frizar que não existe nenhuma regra imposta sobre quais transações serão validadas/aprovadas pelo nó, o que existe é o argumento de que se uma grande quantidade de nós seguem uma regra de referência, então, para qualquer nó fixo da rede, é melhor seguir a mesma regra. Isso é especialmente válido no contexto de IoT, onde os nós são hardwares especializados com firmware pré-instalado.

Outro ponto importante a se notar é que a Tangle é assíncrona, ou seja, ela consegue tolerar transações conflitantes que foram criadas assincronamente. Em geral, os nós da rede não necessariamente enxergam as mesmas transações, entretanto, no caso de existirem transações conflitantes os nós devem decidir quais irão virar orfãos, ou seja, quais deixarão de ser validados de forma indireta, ao mesmo tempo que ambas as transações continuam na Tangle.

Resolvendo Transações Conflitantes

A principal regra que os nós usam para decidir entre duas transações conflitantes é rodar o algoritmo de seleção de tips diversas vezes e observar qual das duas transações tem maior probabilidade de ser aprovada indiretamente sepa tip selecionada. Por exemplo, se uma transação foi selecionada em 97 das 100 execuções do algoritmo de seleção de tips, então essa transação é confirmada com 97% de confidência