nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Inclusive Block Chain Protocols

verfasst von : Yoad Lewenberg, Yonatan Sompolinsky, Aviv Zohar

Erschienen in: Financial Cryptography and Data Security

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Distributed cryptographic protocols such as Bitcoin and Ethereum use a data structure known as the block chain to synchronize a global log of events between nodes in their network. Blocks, which are batches of updates to the log, reference the parent they are extending, and thus form the structure of a chain. Previous research has shown that the mechanics of the block chain and block propagation are constrained: if blocks are created at a high rate compared to their propagation time in the network, many conflicting blocks are created and performance suffers greatly. As a result of the low block creation rate required to keep the system within safe parameters, transactions take long to securely confirm, and their throughput is greatly limited.

We propose an alternative structure to the chain that allows for operation at much higher rates. Our structure consists of a directed acyclic graph of blocks (the block DAG). The DAG structure is created by allowing blocks to reference multiple predecessors, and allows for more “forgiving” transaction acceptance rules that incorporate transactions even from seemingly conflicting blocks. Thus, larger blocks that take longer to propagate can be tolerated by the system, and transaction volumes can be increased.

Another deficiency of block chain protocols is that they favor more connected nodes that spread their blocks faster—fewer of their blocks conflict. We show that with our system the advantage of such highly connected miners is greatly reduced. On the negative side, attackers that attempt to maliciously reverse transactions can try to use the forgiving nature of the DAG structure to lower the costs of their attacks. We provide a security analysis of the protocol and show that such attempts can be easily countered.

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 Secure High-Rate Transaction Processing in Bitcoin

Nächstes Kapitel VeriStream – A Framework for Verifiable Data Streaming

Nur mit Berechtigung zugänglich

For the sake of brevity, we do not go into the details of GHOST or of its Ethereum-variant, except where specifically relevant.

This is guaranteed only if the attacker has less than 50 % of the computational power in the network.

DAGs are already required by GHOST (although for different reasons), and Ethereum’s blocks currently reference parent blocks as well as “uncles” (blocks that share the same parent as their parent). Thus, this modification is quite natural.

It is important to note that the algorithm below describes a full traversal. More efficient implementations are possible if a previously traversed DAG is merely being updated (with methods similar to the unspent transaction set used in Bitcoin).

The Inclusive algorithm can also handle blocks that have some of their transactions rejected.

The total reward can be automatically adjusted to maintain a desired rate of money creation by a process similar to the re-targeting done for difficulty adjustments.

This assumption approximates well the situation in the real Bitcoin network, in which transactions propagate quickly relative to blocks.

To make this formal some work is needed: Let G(t) be the block DAG which consist of all blocks created up to time t. We require that the underlying chain selection rule F break ties between equally weighted leaves, in some predetermined perhaps arbitrary way. Denote by \(B_t\) the leaf of the main chain F(G(t)). Assume F converges, in the sense that a block in the main chain becomes less likely to be replaced, as time grows: \(B\in F(G(t))\Longrightarrow \lim \limits _{s\rightarrow \infty }\Pr (B\notin F(G(s)))=0\) (longest-chain and GHOST, for instance, satisfy this property). We can thus speak of the eventual- or limit-order “\(\prec \)” on all blocks in the history of the game, defined by \(A\prec A'\) if \(\exists t_0, \forall t>t_0: A\prec _{B_t} A'\) (see the discussion succeeding Algorithm 1 for the definition of \(\prec _{B_t}\)).

Note that \(k_{max}\ge b\), and that the existence of a root for \(G_{k_{max}}\) follows from the fact that f’s domain is [0, 1] hence this is also \(f^{-1}\)’s image.

Successful manipulations require strong attackers that are either highly connected, or have massive amounts of computational power.

Andresen, G.: O(1) block propagation. https://gist.github.com/gavinandresen/e20c3b5a1d4b97f79ac2

Babaioff, M., Dobzinski, S., Oren, S., Zohar, A.: On bitcoin and red balloons. In: The 13th ACM Conference on Electronic Commerce, pp. 56–73. ACM (2012)

Back, A., Corallo, M., Dashjr, L., Friedenbach, M., Maxwell, G., Miller, A., Poelstra, A., Timón, J., Wuille, P.: Enabling blockchain innovations with pegged sidechains (2014)

Bitcoinj: Working with micropayment channels. https://bitcoinj.github.io/working-with-micropayments

Chakrabarti, S., Topolyan, I.: A direct proof of the existence of sequential equilibrium and a backward induction characterization (2010)

Decker, C., Wattenhofer, R.: Information propagation in the bitcoin network. In: 13th IEEE International Conference on Peer-to-Peer Computing (P2P), Trento, Italy, September 2013

Eyal, Ittay, Sirer, Emin Gün: Majority is not enough: bitcoin mining is vulnerable. In: Christin, Nicolas, Safavi-Naini, Reihaneh (eds.) FC 2014. LNCS, vol. 8437, pp. 431–449. Springer, Heidelberg (2014)

Kreps, D.M., Wilson, R.: Sequential equilibria. Econometrica: J. Econometric Soc. 50, 863–894 (1982)MathSciNetCrossRefMATH

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

10.

Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory, Chap. 9. Cambridge University Press, Cambridge (2007) CrossRef

11.

Rosenfeld, M.: Analysis of hashrate-based double spending. arXiv preprint arXiv:1402.2009 (2014)

12.

Sompolinsky, Y., Zohar, A.: Secure high-rate transaction processing in bitcoin. In: Böhme, R., Okamoto, T. (eds.) FC 2015. LNCS, vol 8975, pp. 507–527. Springer, Heidelberg (2015)

13.

Wood, G.: Ethereum: a secure decentralised generalised transaction ledger (2014)

Titel: Inclusive Block Chain Protocols
verfasst von: Yoad Lewenberg
Yonatan Sompolinsky
Aviv Zohar
Verlag: Springer Berlin Heidelberg
Buch: Financial Cryptography and Data Security
Print ISBN: 978-3-662-47853-0

Electronic ISBN: 978-3-662-47854-7

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-662-47854-7_33

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"

Premium Partner