Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Stronger Security for Reusable Garbled Circuits, General Definitions and Attacks Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Bitcoin as a Transaction Ledger: A Composable Treatment

Authors : Christian Badertscher, Ueli Maurer, Daniel Tschudi, Vassilis Zikas

Published in: Advances in Cryptology – CRYPTO 2017

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Bitcoin is one of the most prominent examples of a distributed cryptographic protocol that is extensively used in reality. Nonetheless, existing security proofs are property-based, and as such they do not support composition.
In this work we put forth a universally composable treatment of the Bitcoin protocol. We specify the goal that Bitcoin aims to achieve as a ledger functionality in the (G)UC model of Canetti et al. [TCC’07]. Our ledger functionality is weaker than the one recently proposed by Kiayias, Zhou, and Zikas [EUROCRYPT’16], but unlike the latter suggestion, which is arguably not implementable given the Bitcoin assumptions, we prove that the one proposed here is securely UC realized under standard assumptions by an appropriate abstraction of Bitcoin as a UC protocol. We further show how known property-based approaches can be cast as special instances of our treatment and how their underlying assumptions can be cast in (G)UC without restricting the environment or the adversary.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter The Bitcoin Backbone Protocol with Chains of Variable Difficulty
next chapter Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol
Footnotes
1
In the original Bitcoin heuristic “deep enough” is defined as six blocks, whereas in these works it is defined as linear in an appropriate security parameter.
 
2
We formulate a weakened guarantee, which we then amplify using digital signatures.
 
3
Note that making the set of parties dynamic means that the adversary needs to be informed about which parties are currently in the computation so that he can chose how many (and which) parties to corrupt.
 
4
Although we allow no communication between functionalities, we will allow functionalities to communicate with global setups. (They can use the interface of global setups to additional honest parties, which is anyway open to the environment.)
 
5
In [16] this mechanism is referred to as “broadcast”; here, we use multicast to make explicit the fact that this primitive is different from a standard Byzantine-agreement-type broadcast, in that it does not guarantee any consistency for a malicious sender.
 
6
In the latter case the activation goes to the environment by default.
 
7
This is inevitable since we assume non-private communication, where the adversary sees any message as soon as it is sent, even if the sender and receiver are honest.
 
8
E.g., in [19] the adversary is allowed to permute the contents of the buffer.
 
9
In Bitcoin, \(\texttt {txid} \) would be the hash-pointer corresponding to this transaction. Note that the generic ledger can capture explicit guarantees on the ability or disability to link transactions, as this crucially depends on the concrete choice of an ID mechanism.
 
10
For technical reasons described in Sect. 4.1, \(\varDelta \) rounds in the protocol correspond to \(2\varDelta \) clock-ticks.
 
11
Recall that in the general ledger description, \(\textsf {Validate} \) might depend on some associated metadata; although this might be useful to capture alternative blockchains, it is not the case for Bitcoin.
 
12
Note that when a party registers to a local functionality such as the network or the random oracle it does not lose its activation token. This is a subtle point to ensure that the real and ideal worlds are in-sync regarding activations.
 
13
The parameters are the ones introduced in this section: a lower bound on honest mining power (per round) \(\alpha \), an upper bound on adversarial mining power (per round) \(\beta \), the total mining power (per round) \(\textsf {T} _{mp}\), the network delay \(\varDelta \), the difficulty parameter \(\textsf {D} \) (that influences the probability of a successful PoW), and finally a value \(\lambda >1\) describing the required gap between honest and dishonest mining power.
 
14
The flat model means that every party gets the same number of hash queries in every round.
 
15
In a recent paper, the authors of [16] propose an analysis of Bitcoin for a variable number of parties. Capturing the appropriate assumptions for this case, as a wrapper in our composable setting, is part of future work.
 
Literature
1.
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). doi:10.​1007/​978-3-662-48000-7_​19 CrossRef
2.
Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, Ł.: Fair two-party computations via bitcoin deposits. In: Böhme, R., Brenner, M., Moore, T., Smith, M. (eds.) FC 2014. LNCS, vol. 8438, pp. 105–121. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-44774-1_​8
3.
Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Secure multiparty computations on bitcoin. In: 2014 IEEE Symposium on Security and Privacy, pp. 443–458. IEEE Computer Society Press, May 2014
4.
Babaioff, M., Dobzinski, S., Oren, S., Zohar, A.: On bitcoin and red balloons. SIGecom Exch. 10(3), 5–9 (2011)CrossRef
5.
Backes, M., Hofheinz, D., Müller-Quade, J., Unruh, D.: On fairness in simulatability-based cryptographic systems. In: FMSE 2005 (2005)
6.
Badertscher, C., Maurer, U., Tschudi, D., Zikas, V.: Bitcoin as a transaction ledger: a composable treatment. Cryptology ePrint Archive, Report 2017/149 (2017)
7.
Ben-Sasson, E., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., Virza, M.: Zerocash: decentralized anonymous payments from bitcoin. In: 2014 IEEE Symposium on Security and Privacy, pp. 459–474. IEEE Computer Society Press, May 2014
8.
9.
10.
Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd FOCS, pp. 136–145. IEEE Computer Society Press, October 2001
11.
12.
Canetti, R., Shahaf, D., Vald, M.: Universally composable authentication and key-exchange with global PKI. In: Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.) PKC 2016. LNCS, vol. 9615, pp. 265–296. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49387-8_​11 CrossRef
13.
Coretti, S., Garay, J., Hirt, M., Zikas, V.: Constant-round asynchronous multi-party computation based on one-way functions. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 998–1021. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-53890-6_​33 CrossRef
14.
Eyal, I.: The miner’s dilemma. In: 2015 IEEE Symposium on Security and Privacy, pp. 89–103. IEEE Computer Society Press, May 2015
15.
Eyal, I., Sirer, E.G.: Majority is not enough: bitcoin mining is vulnerable. In: Christin, N., Safavi-Naini, R. (eds.) FC 2014. LNCS, vol. 8437, pp. 436–454. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-45472-5_​28
16.
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). doi:10.​1007/​978-3-662-46803-6_​10
17.
18.
Kiayias, A., Koutsoupias, E., Kyropoulou, M., Tselekounis, Y.: Blockchain mining games. In: EC (2016)
19.
Kiayias, A., Zhou, H.-S., Zikas, V.: Fair and robust multi-party computation using a global transaction ledger. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 705–734. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49896-5_​25 CrossRef
20.
Kumaresan, R., Bentov, I.: How to use bitcoin to incentivize correct computations. In: Ahn, G.-J., Yung, M., Li, N. (eds.) ACM CCS 2014, pp. 30–41. ACM Press, November 2014
21.
Kumaresan, R., Bentov, I.: Amortizing secure computation with penalties. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 418–429. ACM Press, October 2016
22.
Kumaresan, R., Moran, T., Bentov, I.: How to use bitcoin to play decentralized poker. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 15, pp. 195–206. ACM Press, October 2015
23.
Kumaresan, R., Vaikuntanathan, V., Vasudevan, P.N.: Improvements to secure computation with penalties. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 406–417. ACM Press, October 2016
24.
Lamport, L.: The part-time parliament. ACM Trans. Comput. Syst. 16(2), 133–169 (1998)CrossRef
25.
Lamport, L.: Paxos made simple, fast, and byzantine. In: OPODIS (2002)
26.
Lamport, L., Shostak, R.E., Pease, M.C.: The byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382–401 (1982)CrossRefMATH
27.
Miers, I., Garman, C., Green, M., Rubin, A.D.: Zerocoin: anonymous distributed e-cash from bitcoin. In: 2013 IEEE Symposium on Security and Privacy, pp. 397–411. IEEE Computer Society Press, May 2013
28.
29.
Pass, R., Seeman, L., Shelat, A.: Analysis of the blockchain protocol in asynchronous networks. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 643–673. Springer, Cham (2017). doi:10.​1007/​978-3-319-56614-6_​22 CrossRef
30.
Pass, R., Shi, E.: FruitChains: a fair blockchain. Cryptology ePrint Archive, Report 2016/916 (2016)
31.
Rabin, M.O.: Randomized byzantine generals. In: FOCS (1983)
32.
33.
34.
Metadata
Title
Bitcoin as a Transaction Ledger: A Composable Treatment
Authors
Christian Badertscher
Ueli Maurer
Daniel Tschudi
Vassilis Zikas
Copyright Year
2017
Book
Advances in Cryptology – CRYPTO 2017

Print ISBN: 978-3-319-63687-0

Electronic ISBN: 978-3-319-63688-7

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-63688-7_11

Premium Partner

    Image Credits