Um Estudo sobre o Uso de Replicação Máquina de Estados Paralelas na Implementação de Blockchains
Resumo
Replicação Máquina de Estados (RME) e blockchains possuem um objetivo em comum que é o de manter a consistência no estado de um serviço replicado. Porém, algumas diferenças fundamentais são encontradas entre estes modelos, como por exemplo a forma de manutenção e utilização do log de requisições. Além disso, a utilização de uma RME como um bloco de construção para blockchains impacta significativamente o desempenho do sistema devido principalmente ao modelo de execução sequencial das RMEs. Neste trabalho, apresentamos um estudo de caso que utiliza uma solução para RME que possibilita a execução paralela de uma parte das requisições/transações na implementação de blockchains. Através da implementação de um sistema de pagamento e a realização de uma série de experimentos, este trabalho mostra que, usando RMEs paralelas, a limitação anteriormente descrita pode ser minimizada, i.e., o desempenho do sistema é aumentado substancialmente.
Referências
Abraham, I., Malkhi, D., Nayak, K., Ren, L., and Spiegelman, A. (2017). Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus. In Proceedings of the 21st International Conference on Principles of Distributed Systems, Lisboa, Portugal.
Alchieri, E., Dotti, F., Mendizabal, O. M., and Pedone, F. (2017). Reconfiguring parallel state machine replication. In SRDS.
Alchieri, E., Dotti, F., and Pedone, F. (2018). Early scheduling in parallel state machine replica. In ACM SoCC.
Baliga, A., Subhod, I., Kamat, P., and Chatterjee, S. (2018). Performance evaluation of the quorum blockchain platform. arXiv preprint arXiv:1809.03421.
Bashir, I. (2017). Mastering blockchain. Packt Publishing Ltd.
Bessani, A., Alchieri, E., Sousa, J., Oliveira, A., and Pedone, F. (2020). From byzantine replication to blockchain: Consensus is only the beginning. In 2020 50th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 424–436.
Bessani, A., Sousa, J., and Alchieri, E. E. (2014). State machine replication for the masses with bft-smart. In 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, pages 355–362.
BitNodes (2021). Global bitcoin nodes distribution.
Buchman, E. (2016). Tendermint: Byzantine fault tolerance in the age of blockchains. PhD thesis.
Burgos, A., Alchieri, E., Dotti, F., and Pedone, F. (2021). Replicação máquina de estados paralelas com escalonamento híbrido. In Anais do 39º Simpósio Brasileiro de Redes de Computadores - SBRC 2021. SBC.
Burgos, A. and Batavia, B. (2018). O meio circulante na era digital. Banco Central do Brasil.
Cachin, C. et al. (2016). Architecture of the hyperledger blockchain fabric. In Workshop on distributed cryptocurrencies and consensus ledgers.
Cachin, C. and Vukolic, M. (2017). Blockchain consensus protocol in the wild (invited paper). In Proceedings of the 31th International Symposium on Distributed Computing, Vienna, Austria.
Castro, M. and Liskov, B. (1999). Practical Byzantine fault tolerance. In Proceedings of the 3rd Symposium on Operating Systems Design and Implementation, pages 173–186. USENIX Association.
Castro, M. and Liskov, B. (2002). Practical byzantine fault-tolerance and proactive recovery. ACM Transactions on Computer Systems, 20(4):398–461.
Défago, X., Schiper, A., and Urb´an, P. (2004). Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Computing Surveys, 36(4):372–421.
Escobar, I. A., Alchieri, E., Dotti, F. L., and Pedone, F. (2019). Boosting concurrency in parallel state machine replication. In Proc. 20th International Middleware Conference.
Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382.
Golan-Gueta, G., Abraham, I., Grossman, S., Malkhi, D., Pinkas, B., Reiter, M. K., Seredinschi, D., Tamir, O., and Tomescu, A. (2019). SBFT: a scalable decentralized trust infrastructure for blockchains. In Proceedings of the 49th IEEE/IFIP International Conference on Dependable Systems and Networks, Portland, OR, USA.
Greenspan, G. (2015). Multichain private blockchain-white paper. URl: http://www.multichain.com/download/MultiChain-White-Paper.pdf.
Guerraoui, R., Hamza, J., Seredinschi, D.-A., and Vukolic, M. (2019). Can 100 machines agree? CoRR, abs/1911.07966.
Hadzilacos, V. and Toueg, S. (1993). Fault-tolerant broadcasts and related problems. In Mullender, S., editor, Distributed Systems, pages 97–145. ACM Press/Addison-Wesley, New York, NY, USA.
Herlihy, M. and Wing, J. M. (1990). Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programing Languages and Systems, 12(3):463–492.
Kotla, R. and Dahlin, M. (2004). High throughput byzantine fault tolerance. In IEEE/IFIP Int. Conference on Dependable Systems and Networks.
Lamport, L. (1998). The part-time parliament. ACM Transactions on Computer Systems (TOCS), 16(2):133–169.
Lamport, L. et al. (2001). Paxos made simple. ACM Sigact News, 32(4):18–25.
Liu, J., Li, W., Karame, G. O., and Asokan, N. (2019). Scalable byzantine consensus via hardware-assisted secret sharing. IEEE Transactions on Computers, 68(1):139–151.
Nakamoto, S. (2008). A peer-to-peer electronic cash system. Bitcoin. – URL: https://bitcoin.org/bitcoin.pdf.
on Payment, C. and Systems, S. (2003). A glossary of terms used in payments and settlement systems.
Pass, R. and Shi, E. (2017). Hybrid Consensus: Efficient Consensus in the Permissionless Model. In Proceedings of the 31st International Symposium on Distributed Computing, Vienna, Austria.
Schneider, F. B. (1990). Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys, 22(4):299–319.
White, B., Lepreau, J., Stoller, L., Ricci, R., Guruprasad, S., Newbold, M., Hibler, M., Barb, C., and Joglekar, A. (2002). An integrated experimental environment for distributed systems and networks. In Symposium on Operating Systems Design and Implementation.
Wood, G. et al. (2014). Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper, 151(2014):1–32.
Alchieri, E., Dotti, F., Mendizabal, O. M., and Pedone, F. (2017). Reconfiguring parallel state machine replication. In SRDS.
Alchieri, E., Dotti, F., and Pedone, F. (2018). Early scheduling in parallel state machine replica. In ACM SoCC.
Baliga, A., Subhod, I., Kamat, P., and Chatterjee, S. (2018). Performance evaluation of the quorum blockchain platform. arXiv preprint arXiv:1809.03421.
Bashir, I. (2017). Mastering blockchain. Packt Publishing Ltd.
Bessani, A., Alchieri, E., Sousa, J., Oliveira, A., and Pedone, F. (2020). From byzantine replication to blockchain: Consensus is only the beginning. In 2020 50th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 424–436.
Bessani, A., Sousa, J., and Alchieri, E. E. (2014). State machine replication for the masses with bft-smart. In 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, pages 355–362.
BitNodes (2021). Global bitcoin nodes distribution.
Buchman, E. (2016). Tendermint: Byzantine fault tolerance in the age of blockchains. PhD thesis.
Burgos, A., Alchieri, E., Dotti, F., and Pedone, F. (2021). Replicação máquina de estados paralelas com escalonamento híbrido. In Anais do 39º Simpósio Brasileiro de Redes de Computadores - SBRC 2021. SBC.
Burgos, A. and Batavia, B. (2018). O meio circulante na era digital. Banco Central do Brasil.
Cachin, C. et al. (2016). Architecture of the hyperledger blockchain fabric. In Workshop on distributed cryptocurrencies and consensus ledgers.
Cachin, C. and Vukolic, M. (2017). Blockchain consensus protocol in the wild (invited paper). In Proceedings of the 31th International Symposium on Distributed Computing, Vienna, Austria.
Castro, M. and Liskov, B. (1999). Practical Byzantine fault tolerance. In Proceedings of the 3rd Symposium on Operating Systems Design and Implementation, pages 173–186. USENIX Association.
Castro, M. and Liskov, B. (2002). Practical byzantine fault-tolerance and proactive recovery. ACM Transactions on Computer Systems, 20(4):398–461.
Défago, X., Schiper, A., and Urb´an, P. (2004). Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Computing Surveys, 36(4):372–421.
Escobar, I. A., Alchieri, E., Dotti, F. L., and Pedone, F. (2019). Boosting concurrency in parallel state machine replication. In Proc. 20th International Middleware Conference.
Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382.
Golan-Gueta, G., Abraham, I., Grossman, S., Malkhi, D., Pinkas, B., Reiter, M. K., Seredinschi, D., Tamir, O., and Tomescu, A. (2019). SBFT: a scalable decentralized trust infrastructure for blockchains. In Proceedings of the 49th IEEE/IFIP International Conference on Dependable Systems and Networks, Portland, OR, USA.
Greenspan, G. (2015). Multichain private blockchain-white paper. URl: http://www.multichain.com/download/MultiChain-White-Paper.pdf.
Guerraoui, R., Hamza, J., Seredinschi, D.-A., and Vukolic, M. (2019). Can 100 machines agree? CoRR, abs/1911.07966.
Hadzilacos, V. and Toueg, S. (1993). Fault-tolerant broadcasts and related problems. In Mullender, S., editor, Distributed Systems, pages 97–145. ACM Press/Addison-Wesley, New York, NY, USA.
Herlihy, M. and Wing, J. M. (1990). Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programing Languages and Systems, 12(3):463–492.
Kotla, R. and Dahlin, M. (2004). High throughput byzantine fault tolerance. In IEEE/IFIP Int. Conference on Dependable Systems and Networks.
Lamport, L. (1998). The part-time parliament. ACM Transactions on Computer Systems (TOCS), 16(2):133–169.
Lamport, L. et al. (2001). Paxos made simple. ACM Sigact News, 32(4):18–25.
Liu, J., Li, W., Karame, G. O., and Asokan, N. (2019). Scalable byzantine consensus via hardware-assisted secret sharing. IEEE Transactions on Computers, 68(1):139–151.
Nakamoto, S. (2008). A peer-to-peer electronic cash system. Bitcoin. – URL: https://bitcoin.org/bitcoin.pdf.
on Payment, C. and Systems, S. (2003). A glossary of terms used in payments and settlement systems.
Pass, R. and Shi, E. (2017). Hybrid Consensus: Efficient Consensus in the Permissionless Model. In Proceedings of the 31st International Symposium on Distributed Computing, Vienna, Austria.
Schneider, F. B. (1990). Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys, 22(4):299–319.
White, B., Lepreau, J., Stoller, L., Ricci, R., Guruprasad, S., Newbold, M., Hibler, M., Barb, C., and Joglekar, A. (2002). An integrated experimental environment for distributed systems and networks. In Symposium on Operating Systems Design and Implementation.
Wood, G. et al. (2014). Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper, 151(2014):1–32.
Publicado
16/08/2021
Como Citar
BURGOS, Aldênio; ALCHIERI, Eduardo.
Um Estudo sobre o Uso de Replicação Máquina de Estados Paralelas na Implementação de Blockchains. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 22. , 2021, Uberlândia.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 57-70.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2021.17204.
