Algoritmos de Consenso e Sistemas de Informação Distribuídos Transparentes (V.3, N.1, P.1, 2020)

Tempo estimado de leitura: 8 minute(s)

Divulgador da Ciência:  Prof. Dr. Carlo Kleber da Silva Rodrigues (CMCC/UFABC)

 

Um Sistema de Informação Distribuído (SID) pode ser caracterizado como um conjunto de processos concorrentes acessando recursos distribuídos, os quais podem ser compartilhados ou replicados, através de troca de mensagens em um ambiente de rede. Uma das características mais relevantes de um SID é possuir uma única base de dados lógica constituída por partições físicas geograficamente espalhadas e interconectadas por meio de redes de comunicação.

 Por sua vez, um Sistema de Informação Distribuído Transparente (SIDT) deve, de maneira geral, permitir o acesso às informações armazenadas. Esse requisito foi originado pela Lei nº 12.527/2011, a qual regulamentou o direito  de acesso às informações públicas. À época foram criados mecanismos formais que possibilitam, a qualquer pessoa, física ou jurídica, o recebimento de informações públicas dos órgãos e entidades.          

Essa Lei vale para os três Poderes da União, Estados, Distrito Federal e Municípios, inclusive para os Tribunais de Conta e Ministério Público. Entidades privadas sem fins lucrativos também são obrigadas a dar publicidade a informações referentes ao recebimento e à destinação dos recursos públicos recebidos.

Para a implementação das bases de dados dos SIDTs, as Tecnologias de Registros Distribuídos (do inglês, Distributed Ledger Technologies – DLTs) constituem uma das principais alternativas de solução apontada na literatura. Por sua vez, essas tecnologias possuem, como alicerce fulcral, o peremptório emprego de algoritmos de consenso, os quais permitem que partes desconhecidas entre si, e até mesmo de interesses concorrentes, cheguem a um acordo sobre o estado atual e passado das informações armazenadas na base de dados distribuída.

Para fins de mera exemplificação, cita-se que Blockchain e Tangle [Popov 2017] são dois tipos de DLTs. Blockchain se baseia na implementação de uma lista encadeada de blocos de transações (do inglês, blockchain). Esses blocos são adicionados à lista conforme são validados por meio de um processo matemático. Por sua vez, Tangle se baseia na implementação de um Grafo Acíclico Direcionado (do inglês, Directed Acyclic Graph − DAG), onde cada nó do DAG é uma transação. Para que a transação seja adicionada ao DAG, há um processo matemático, como na Blockchain, e ainda ocorre a validação de duas outras transações pré-existentes no DAG.

Como operam e quais são os principais tipos de algoritmos de consenso?

Como mencionado, os algoritmos de consenso permitem que partes desconhecidas entre si, e até mesmo de interesses concorrentes, cheguem a um acordo sobre o estado atual e passado das informações armazenadas na base de dados. Esses algoritmos buscam, assim, prover uma solução para o clássico Problema dos Generais Bizantinos.  

 No contexto de sistemas computacionais, as partes desconhecidas são pensadas como nós processadores independentes que estão interconectados por meio de uma rede de comunicação sob arquitetura P2P. Exigir a aprovação declarada individual de todos os nós para realizar a adição de uma nova informação à base de dados não é razoável, pois isso poderia naturalmente comprometer o desempenho global do sistema.

Existem duas principais abordagens para solucionar esta questão e cada uma delas origina um dado tipo de algoritmo de consenso. A primeira abordagem consiste em decidir sobre uma forma de provar que um nó (ou um conjunto de nós) pertencente a rede é suficientemente confiável para adicionar um bloco de informações à base de dados, considerando que a prova oferecida seja aceita e, se desejável, possível de ser verificada por todos os demais nós da rede. Esta abordagem origina os algoritmos proof-based consensus.

O algoritmo de consenso Proof of Work (PoW) é do tipo proof-based consensus. Este algoritmo foi utilizado na tecnologia Blockchain quando essa tecnologia foi proposta no ano de 2008. Sob o PoW, os nós mineradores precisam provar que realizaram um significativo esforço computacional, fornecendo a solução para um desafio criptográfico. Na literatura podem ser encontrados vários outros algoritmos do tipo proof-based consensus, com diferentes processos de mineração. Como exemplos, citam-se os seguintes: Proof of Stake (PoS), Proof of Burn (PoB), Proof of Space (PoSp), e Proof of Luck (PoL).

A outra abordagem para solucionar a questão do consenso é considerar que o nó a adicionar o bloco de informações é aquele que detém o apoio da maioria dos outros nós da rede, expressa por meio de uma votação. Neste caso, se um nó deseja adicionar um bloco à base de dados, i.e., deseja ser um minerador, o seguinte requisito deve ser atendido: o nó deve ter garantido que ao menos Q nós estão de acordo. O parâmetro Q é um limiar que varia dependendo do sistema, devendo corresponder a mais que 50% de todos os nós da rede. Esta ideia é a base para os algoritmos voting-based consensus. Os algoritmos Ripple, Stellar e Chain são alguns exemplos que seguem essa abordagem.

Os algoritmos proof-based consensus e voting-based consensus podem ser indistintamente utilizados em plataformas públicas, em consórcio ou mesmo privadas. As plataformas públicas consideram que a base de dados não está sob controle de nenhum grupo de indivíduos ou organizações. É permitida a participação de qualquer usuário interessado na utilização do sistema, inclusive no próprio processo de mineração dos blocos, gerando um alto grau de descentralização. Nas plataformas em consórcio, há um controle por parte de um grupo de organizações, as quais estabelecem regras para participação no sistema. Por fim, as plataformas privadas admitem o controle de exclusivamente uma única organização. Nesses dois últimos tipos, a descentralização é parcial, pois há um controle explícito da participação dos nós.

 Todavia, devido à intrínseca concepção de projeto, os algoritmos proof-based consensus têm sido mais empregados em sistemas de significativo número de participantes, enquanto que aqueles do tipo voting-based consensus são mais usados quando há um número restrito de participantes.

Pode-se sintetizar a compreensão acima com a seguinte afirmação: Quando há muitos participantes, é melhor ter representantes que provem ser suficientemente confiáveis para adicionar informações (por exemplo., proof-based consensus). Por outro lado, quando há poucos participantes, é melhor que a maioria sempre decida sobre as informações a serem adicionadas (por exemplo, voting-based consensus).

 

Fontes principais:

 

Aliaga, Y. E. M et al. (2018). Avaliação de mecanismos de consenso para blockchains em busca de nova estratégia mais eficiente e segura. In: Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais (SBSeg 2018), Natal, Rio Grande do Norte, Brasil.

Ioini, N. E. and Pahl, C.  (2018). A Review of Distributed Ledger Technologies. In: (eds.) On the Move to Meaningful Internet Systems. OTM 2018 Conferences. OTM 2018. Lecture Notes in Computer Science, vol 11230. Springer, Cham. Available at: https://link.springer.com/chapter/10.1007%2F978-3-030-02671-4_16 . Accessed on: June 13th, 2019.

Mata, R. Z. A; Rodrigues, C. K. S. (2018). Uma análise competitiva entre as tecnologias Tangle e Blockchain para Projetos de Aplicações IoT. In: Anais do 17º Workshop de Desempenho em Sistemas Computacionais e de Comunicação (WPerformance / CSBC 2018), julho, Natal, RN, Brasil.

Nguyen, G-T and Kim, K. (2018). A Survey about Consensus Algorithms used in Blockchain. Journal of Information Processing Systems, v. 14, n. 1, pp. 101-128.

Popov, S. (2018). The Tangle – Version 1.4.4. Disponível em: https://iota.org/IOTA_Whitepaper.pdf. Acessado em: 13 de junho, 2019.

Wang, W. et al. (2018). A Survey on Consensus Mechanisms and Mining Management in Blockchain Networks. CoRR, abs/1805.02707. Available at: http://arxiv.org/abs/1805.02707. Accessed on: June 13th, 2019.

 

Acesse às redes sociais do blog. Estamos no Twitter!

@Blog_UFABC

 

Você pode gostar...

Deixe um comentário

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Twitter
Blog UFABC Divulga Ciência