Neste artigo falarei sobre DAG (Directed Acyclic Graph) e a súa aplicación en libros de contas distribuídas, e compararémolo coa cadea de bloques.
DAG non é nada novo no mundo das criptomoedas. Quizais escoitou falar del como unha solución aos problemas de escalabilidade da cadea de bloques. Pero hoxe non falaremos de escalabilidade, senón do que fai que as criptomoedas sexan diferentes a todo o demais: a descentralización, a falta de intermediarios e a resistencia á censura.
Tamén che mostrarei que DAG é realmente máis resistente á censura e non hai intermediarios para acceder ao libro.
Nas cadeas de bloques que coñecemos, os usuarios non teñen acceso directo ao propio libro. Cando queres engadir unha transacción ao libro maior, tes que "pedir" ao produtor do bloque (tamén coñecido como "mineiro") que o faga. Son os mineiros os que deciden que transacción engadir ao seguinte bloque e cal non. Son os mineiros os que teñen acceso exclusivo aos bloques e o dereito a decidir cuxa transacción será aceptada para a súa inclusión no libro maior.
Os mineiros son intermediarios entre vostede e o libro maior distribuído.
Na práctica, xeralmente un pequeno número de grupos de mineiros controlan colectivamente máis da metade da potencia informática da rede. Para Bitcoin estes son catro grupos, para Ethereum - dous. Se conflúen, poden bloquear as transaccións que queiran.
Durante os últimos anos propuxéronse moitas variacións das cadeas de bloques, diferenciándose nos principios de elección dos produtores de bloques. Pero os propios produtores de bloques non van a ningún lado, seguen "parados na barreira": cada transacción debe pasar polo produtor de bloques e, se non o acepta, a transacción, de feito, non existe.
Este é un problema inevitable coa cadea de bloques. E se queremos solucionalo, temos que cambiar radicalmente o deseño e desfacernos completamente de bloques e produtores de bloques. E en lugar de construír unha cadea de bloques, conectaremos as propias transaccións, incluíndo os hash de varios anteriores en cada transacción. Como resultado, obtemos unha estrutura coñecida en matemáticas como un gráfico acíclico dirixido - DAG.
Agora todos teñen acceso directo ao rexistro, sen intermediarios. Cando quere engadir unha transacción ao libro maior, simplemente engádea. Seleccionas varias transaccións dos pais, engades os teus datos, asinas e envías a túa transacción aos compañeiros da rede. Listo. Non hai ninguén que che impida facelo, polo que a túa transacción xa está no libro maior.
Esta é a forma máis descentralizada e a proba de censura de engadir transaccións ao libro maior sen intermediarios. Porque todos simplemente engaden as súas transaccións ao rexistro sen pedir permiso a ninguén.
Os DAG pódense considerar a terceira etapa na evolución dos rexistros. Primeiro había rexistros centralizados, onde unha das partes controlaba o acceso a eles. Despois viñeron as cadeas de bloques, que xa tiñan varios controladores que rexistraban as transaccións no libro. E, finalmente, non hai controladores en absoluto no DAG; os usuarios engaden as súas transaccións directamente.
Agora que temos esta liberdade, non debería levar ao caos. Debemos ter un acordo sobre o estado do rexistro. E este acordo, ou consenso, normalmente significa acordo en dúas cousas:
- Que pasou?
- En que orde pasou isto?
Podemos responder facilmente á primeira pregunta: unha vez que se engadiu unha transacción creada correctamente ao libro maior, produciuse. E punto. A información sobre isto pode chegar a todos os participantes en diferentes momentos, pero finalmente todos os nodos recibirán esta transacción e saberán que ocorreu.
Se fose unha cadea de bloques, os mineiros decidirían o que pasa. O que o mineiro decida incluír nun bloque é o que pasa. Todo o que non inclúe no bloque non pasa.
Nas cadeas de bloques, os mineiros tamén resolven un segundo problema de consenso: a orde. Poden ordenar as transaccións dentro do bloque como queiran.
Como determinar a orde das transaccións nun DAG?
Só porque o noso gráfico está dirixido, xa temos algo de orde. Cada transacción refírese a unha ou varias transaccións anteriores. Os pais, pola súa banda, refírense aos seus pais, etc. Obviamente, os pais aparecen antes que as transaccións dos fillos. Se se pode acceder a algunha das transaccións mediante transicións de ligazóns entre pais e fillos, coñecemos exactamente a orde entre as transaccións nesa cadea de transaccións.
Pero a orde entre as transaccións non sempre se pode determinar só a partir da forma do gráfico. Por exemplo, cando dúas transaccións están en ramas paralelas do gráfico.
Para resolver a ambigüidade nestes casos, confiamos nos chamados provedores de pedidos. Tamén lles chamamos "testemuñas". Estes son usuarios comúns cuxa tarefa é enviar constantemente transaccións á rede de forma ordenada, é dicir. de xeito que se poida acceder a cada unha das súas transaccións anteriores mediante transicións ao longo das ligazóns entre pais e fillos. Os provedores de pedidos son usuarios de confianza e toda a rede confía neles para non infrinxir esta regra. A fin de racionalmente confía neles, esiximos que cada provedor de pedidos sexa unha persoa ou organización coñecida (non anónima) e teña algo que perder se incumpre as regras, como a reputación ou o negocio baseado na confianza.
Os provedores de pedidos son elixidos polos usuarios e cada usuario inclúe unha lista dos seus provedores de confianza en cada transacción que envía á rede. Esta lista está formada por 12 provedores. Este é un número suficientemente pequeno para que unha persoa poida verificar a identidade e a reputación de cada un deles, e suficiente para garantir que a rede siga funcionando en caso de problemas inevitables cunha minoría de provedores de pedidos.
Esta lista de provedores varía de usuario a usuario, pero as listas de transaccións veciñas poden diferir ata un provedor.
Agora que temos provedores de pedidos, podemos illar as súas transaccións nun DAG e ordenar todas as demais transaccións arredor da orde creada por eles. É posible crear tal algoritmo (ver. para detalles técnicos).
Pero a orde de toda a rede non se pode determinar ao instante; necesitamos tempo para que os provedores de pedidos envíen un número suficiente das súas transaccións para verificar a orde final das transaccións pasadas.
E, dado que a orde só está determinada polas posicións das transaccións dos provedores no DAG, todos os nodos da rede recibirán todas as transaccións tarde ou cedo e chegarán á mesma conclusión sobre a orde das transaccións.
Entón, temos acordo sobre o que consideramos que pasou: ocorreu calquera transacción que acabe no DAG. Tamén temos acordo sobre a orde dos eventos: isto é evidente das relacións das transaccións ou dedúcese da orde das transaccións enviadas polos provedores de pedidos. Así que temos consenso.
Temos esta versión de consenso en Obyte. Aínda que o acceso ao libro de Obyte está completamente descentralizado, o consenso sobre a orde das transaccións aínda está centralizado porque 10 de cada 12 provedores están controlados polo creador (Anton Churyumov), e só dous deles son independentes. Buscamos candidatos dispostos a converterse nun dos provedores de pedidos independentes para axudarnos a descentralizar o pedido do libro maior.
Recentemente, apareceu un terceiro candidato independente disposto a instalar e manter un nodo provedor de pedidos: a Universidade de Nicosia.
Agora como controlamos o dobre gasto?
Segundo as regras, se se atopan dúas transaccións gastando a mesma moeda, gaña a transacción que aparece primeiro na orde final de todas as transaccións. O segundo está invalidado polo algoritmo de consenso.
Se é posible establecer a orde entre dúas transaccións que gastan a mesma moeda (a través de conexións entre pais e fillos), todos os nodos rexeitan inmediatamente ese intento de duplicar o gasto.
No caso de que a orde non sexa visible a partir das relacións dos pais entre dúas transaccións deste tipo, ambas acéptanse no libro maior e teremos que esperar ao consenso e ao establecemento da orde entre elas utilizando os provedores de pedidos. Entón, a transacción anterior gañará e a segunda non será válida.
Aínda que a segunda transacción non é válida, aínda permanece no rexistro porque xa ten transaccións posteriores que se refiren a ela, o que non infrinxiu nada e non sabía que esta transacción sería inválida no futuro. En caso contrario, teriamos que eliminar o pai de boas transaccións posteriores, o que violaría o principio principal da rede: calquera transacción correcta é aceptada no libro maior.
Esta é unha regra moi importante que permite que todo o sistema sexa resistente aos intentos de censura.
Imaxinemos que todos os provedores de pedidos colaboran nun intento de "censurar" unha transacción específica. Poden ignoralo e nunca elixilo como "nai" para as súas transaccións, pero iso non é suficiente, a transacción aínda pode incluírse indirectamente como a nai dalgunha outra transacción emitida por calquera usuario da rede que non estea en connivencia. Co paso do tempo, tal transacción recibirá cada vez máis fillos, netos e bisnetos de usuarios comúns, crecendo como unha bola de neve, e todos os provedores de pedidos acordados tamén terán que ignorar estas transaccións. Finalmente, terán que censurar toda a rede, o que equivale a sabotaxe.
Deste xeito, o DAG segue sendo resistente á censura aínda que haxa connivencia entre os provedores de pedidos, superando así a cadea de bloques resistente á censura na que non podemos facer nada se os mineiros deciden non incluír ningunha das transaccións. E isto despréndese da propiedade principal de DAG: a participación no rexistro é completamente independente e sen intermediarios, e as transaccións son irreversibles.
Fonte: www.habr.com