nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Fast-to-Finalize Nakamoto-Like Consensus

verfasst von : Shuyang Tang, Sherman S. M. Chow, Zhiqiang Liu, Joseph K. Liu

Erschienen in: Information Security and Privacy

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

As the fundamental component of blockchains, proof-of-work (PoW) scheme has been widely leveraged to provide consensus for maintaining a distributed public ledger. However, the long confirmation time, and hence the slow finality rate, is far from satisfactory. Alternative paradigms with performance improvement emerge. Nevertheless, there are fewer attempts in modifying the PoW mechanism itself.

We find that the slow finality rate in PoW is caused by using only one bit to measure the computational power, namely, whether the attained hash value is smaller than a given target. In this paper, we first propose Demo-of-Work (DoW), a generalized PoW which assigns the computational work with a score depending on the hash value. We also treat the bitcoin blockchain as a global “clock” to attain synchronization for ensuring that each participant takes part in DoW for roughly the same time interval for ensuring fairness. With these two tools, we construct an alternative blockchain called AB-chain which provides a significantly faster finality rate when compared with the existing PoW-based blockchains, without sacrificing communication complexity or fairness.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel -subgaussian Random Variables in Cryptography

Nächstes Kapitel A Flexible Instant Payment System Based on Blockchain

Nur mit Berechtigung zugänglich

For improving throughput, many sharding protocols are also proposed (e.g., see [9]).

Potential function is a term borrowed from the Physics literature. The existing PoW is a special case of DoW, whose potential function assigns one to all hashes smaller than a predetermined parameter, and zero to others.

The cost is hard to be measured by any specific quantity, so we measure it with complexity.

There are other works which analyze or evaluate blockchain or blockchain-based cryptocurrencies. For example, Bitcoin backbone [13] has shown common prefix and chain quality, two basic properties of the bitcoin protocol. There is also model for formally analyzing the security and performance of various cryptocurrencies [14].

\(|\varphi _{\mathcal {L}}((\alpha +\beta )T) - (\varphi _{\mathcal {L}}(\alpha T)+\varphi _{\mathcal {L}}(\beta T))|\) is non-negligible for certain \(0<\alpha ,\beta <1\).

It is not exactly the mathematical expectation, but it simplifies descriptions.

A coherence on experimental results even with “noise” from such a difference further justifies the reliability of our finality model and the experiment.

We are showing that the Nakamoto chain can be regarded as one instantiation of our model. We are not competing with Nakamoto blockchain in this part.

Abraham, I., Malkhi, D., Nayak, K., Ren, L., Spiegelman, A.: Solidus: an incentive-compatible cryptocurrency based on permissionless byzantine consensus. arXiv CoRR abs/1612.02916 (2016)

Andrychowicz, M., Dziembowski, S.: PoW-based distributed cryptography with no trusted setup. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 379–399. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_19CrossRef

Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Secure multiparty computations on bitcoin. In: 2014 IEEE Symposium on Security and Privacy, SP 2014, Berkeley, CA, USA, 18–21 May 2014, pp. 443–458 (2014)

Bentov, I., Gabizon, A., Zuckerman, D.: Bitcoin beacon. arXiv CoRR abs/1605.04559 (2016)

Bentov, I., Kumaresan, R.: How to use bitcoin to design fair protocols. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 421–439. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_24CrossRef

Bissias, G., Levine, B.N.: Bobtail: a proof-of-work target that minimizes blockchain mining variance (draft). arXiv CoRR abs/1709.08750 (2017)

Boyen, X., Carr, C., Haines, T.: Blockchain-free cryptocurrencies: a framework for truly decentralised fast transactions. Cryptology ePrint Archive, Report 2016/871 (2016)

Bünz, B., Goldfeder, S., Bonneau, J.: Proofs-of-delay and randomness beacons in ethereum. In: IEEE Security & Privacy on the Blockchain (IEEE S&B) (2017)

Chow, S.S.M., Lai, Z., Liu, C., Lo, E., Zhao, Y.: Sharding blockchain (invited paper). In: The First IEEE International Workshop on Blockchain for the Internet of Things (BIoT) (2018, To appear)

10.

David, B., Gaži, P., Kiayias, A., Russell, A.: Ouroboros praos: an adaptively-secure, semi-synchronous proof-of-stake blockchain. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 66–98. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_3CrossRef

11.

Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 139–147. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-48071-4_10CrossRef

12.

Eyal, I., Gencer, A.E., Sirer, E.G., van Renesse, R.: Bitcoin-NG: a scalable blockchain protocol. In: 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016, Santa Clara, CA, USA, 16–18 March 2016, pp. 45–59 (2016)

13.

Garay, J., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol: analysis and applications. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 281–310. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_10CrossRef

14.

Gervais, A., Karame, G.O., Wüst, K., Glykantzis, V., Ritzdorf, H., Capkun, S.: On the security and performance of proof of work blockchains. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, 24–28 October 2016, pp. 3–16 (2016)

15.

Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: scaling byzantine agreements for cryptocurrencies. In: Proceedings of the 26th Symposium on Operating Systems Principles, Shanghai, China, 28–31 October 2017, pp. 51–68 (2017)

16.

Jakobsson, M., Juels, A.: Proofs of work and bread pudding protocols. In: Secure Information Networks: Communications and Multimedia Security, IFIP TC6/TC11 Joint Working Conference on Communications and Multimedia Security (CMS 1999), 20–21 September 1999, Leuven, Belgium, pp. 258–272 (1999)CrossRef

17.

Kumaresan, R., Bentov, I.: Amortizing secure computation with penalties. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, 24–28 October 2016, pp. 418–429 (2016)

18.

Liu, Z., Tang, S., Chow, S.S.M., Liu, Z., Long, Y.: Fork-free hybrid consensus with flexible proof-of-activity. Future Gener. Comp. Syst. 96, 515–524 (2019)CrossRef

19.

Meng, W., et al.: Position paper on blockchain technology: smart contract and applications. In: Au, M.H., et al. (eds.) NSS 2018. LNCS, vol. 11058, pp. 474–483. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-02744-5_35CrossRef

20.

Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008). www.bitcoin.org

21.

Pass, R., Shi, E.: Fruitchains: a fair blockchain. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, 25–27 July 2017, pp. 315–324 (2017)

22.

Pass, R., Shi, E.: Hybrid consensus: efficient consensus in the permissionless model. In: 31st International Symposium on Distributed Computing, DISC 2017, Vienna, Austria, 16–20 October 2017, pp. 39:1–39:16 (2017)

23.

Pass, R., Shi, E.: Rethinking large-scale consensus. In: 30th IEEE Computer Security Foundations Symposium, CSF 2017, Santa Barbara, CA, USA, 21–25 August 2017, pp. 115–129 (2017)

24.

Poon, J., Dryja, T.: The bitcoin lightning network: scalable off-chain instant payments (2016). https://lightning.network/lightning-network-paper.pdf

25.

Sompolinsky, Y., Lewenberg, Y., Zohar, A.: Spectre: a fast and scalable cryptocurrency protocol. Cryptology ePrint Archive, Report 2016/1159 (2016)

26.

Vukolic, M.: The quest for scalable blockchain fabric: Proof-of-work vs. BFT replication. In: Open Problems in Network Security - IFIP WG 11.4 International Workshop, iNetSec 2015, Zurich, Switzerland, 29 October 2015, pp. 112–125 (2015). Revised Selected PapersCrossRef

Titel: Fast-to-Finalize Nakamoto-Like Consensus
verfasst von: Shuyang Tang
Sherman S. M. Chow
Zhiqiang Liu
Joseph K. Liu
Verlag: Springer International Publishing
Buch: Information Security and Privacy
Print ISBN: 978-3-030-21547-7

Electronic ISBN: 978-3-030-21548-4

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-21548-4_15

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"