Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
A Simpler Variant of Universally Composable Security for Standard Multiparty Computation Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Proofs of Space

verfasst von : Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, Krzysztof Pietrzak

Erschienen in: Advances in Cryptology -- CRYPTO 2015

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto’92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system.
In this work, we put forward an alternative concept for PoWs – so-called proofs of space (PoS), where a service requestor must dedicate a significant amount of disk space as opposed to computation. We construct secure PoS schemes in the random oracle model (with one additional mild assumption required for the proof to go through), using graphs with high “pebbling complexity” and Merkle hash-trees. We discuss some applications, including follow-up work where a decentralized digital currency scheme called Spacecoin is constructed that uses PoS (instead of wasteful PoW like in Bitcoin) to prevent double spending.
The main technical contribution of this work is the construction of (directed, loop-free) graphs on N vertices with in-degree \(O(\log \log N)\) such that even if one places \(\varTheta (N)\) pebbles on the nodes of the graph, there’s a constant fraction of nodes that needs \(\varTheta (N)\) steps to be pebbled (where in every step one can put a pebble on a node if all its parents have a pebble).

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 Bloom Filters in Adversarial Environments
Nächstes Kapitel Quantum Homomorphic Encryption for Circuits of Low T-gate Complexity
Fußnoten
1
The hashed \(\mathsf{Email}\) should also contain the receiver of the email, and maybe also a timestamp, so that the sender has to search for a fresh \(\sigma \) for each receiver, and also when resending the email at a later point in time.
 
2
One of our constructions will achieve the optimal \(I=\varTheta (N)\) bound, our second construction achieves \(I=O(N\log \log N)\).
 
3
And initialising this space requires \(O(N\log (N))\) time.
 
4
There are two mechanisms to incentivise mining: miners who solve a PoW get some fixed reward, this is currently the main incentive, but Bitcoin specifies that this reward will decrease over time. A second mechanism are transactions fees.
 
5
There are some differences, the bounds in [4] are somewhat worse as they use hard-to-pebble graphs with worse parameters, and [32] do not use a Merkle hash-tree to make the computation of the verifier independent of N.
 
6
We use the expression “local input/output” instead the usual “private input/output”, because in our protocols no values will actually be secret. The reason to distinguish between the parties’ inputs is only due to the fact that \({\mathsf P}\)’s input will be very large, whereas we want \({\mathsf V}\) to use only small storage.
 
7
In a PoS, we want the prover \({\mathsf P}\) to run in time much less than its storage size. For this reason, we must model our parties as random access machines (and not, say Turing machines), where accessing a storage location is assumed to take constant (or at most polylogarithmic) time.
 
8
Our construction is based on a hash-function \({\mathcal H}\), which will be part of \(\mathsf{prm}\) and we require to be collision resistant. As assuming collision resistance for a fixed function is not meaningful [43], we must either assume that the probability of Eq. (1) is over some distribution of identities \(\mathsf{id}\) (which can then be used as a hash key), or, if we model \({\mathcal H}\) as a random oracle, over the choice of the random oracle.
 
9
As explained in the introduction, \({\mathsf P}\)’s running time I during initialization must be at least linear in the size N of the storage. Our construction basically match this \(I=\varOmega (N)\) lower bound as mentioned in Footnote 2.
 
10
The number q of queries in this phase is unbounded, except for the huge exponential \(2^{L/3}\) bound on the total number of oracle queries made during the entire experiment by all parties mentioned above.
 
11
Let us stress that we do not claim that such an \(S_{\mathcal H}\) exists for every \({\tilde{{\mathsf P}}}\), one can easily come up with a prover where this is not the case (as we will show below). All we need is that for every \((N_0,N_1,T)\) prover \({\tilde{{\mathsf P}}}\), there exists another prover \({\tilde{{\mathsf P}}}'\) with (almost) the same parameters and advantage, that obeys our assumption.
An adversary with \(N_0=N_1=T=1\) not obeying our assumption is, e.g., a \({\tilde{{\mathsf P}}}\) that makes queries 0 and 1 and stores \(S={\mathcal H}(0)\oplus {\mathcal H}(1)\) in the first phase. In the second phase, \({\tilde{{\mathsf P}}}(S)\) picks a random \(b\leftarrow \{0,1\}\), makes the query b, and can write down \({\mathcal H}(b),{\mathcal H}(1-b)=S\oplus {\mathcal H}(b)\). Thus, \({\tilde{{\mathsf P}}}(S)\) can write \(2>N_0=1\) values \({\mathcal H}(0)\) or \({\mathcal H}(1)\) without quering them in the 2nd phase.
 
12
Potentially, \({\tilde{{\mathsf P}}}\) cannot open some values at all, but wlog. we assume that it can open every value in exactly one way.
 
13
We set the bound to 2N, so if we let N denote the number of vertices in the underlying graph, we must store \(2N-1\) values of the hash-tree.
 
Literatur
1.
Abadi, M., Burrows, M., Wobber, T.: Moderately hard and memory-bound functions. In: NDSS 2003. The Internet Society, February 2003
2.
Alwen, J., Serbinenko, V.: High parallel complexity graphs and memory-hard functions. In: Symposium on Theory of Computing, STOC 2015 (2015)
3.
4.
Ateniese, G., Bonacina, I., Faonio, A., Galesi, N.: Proofs of space: when space is of the essence. In: Abdalla, M., De Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 538–557. Springer, Heidelberg (2014)
5.
Ateniese, G., Burns, R.C., Curtmola, R., Herring, J., Kissner, L., Peterson, Z.N.J., Song, D.: Provable data possession at untrusted stores. In: Ning, P., De Capitani di Vimercati, S., Syverson, P.F. (eds.) ACM CCS 2007, pp. 598–609. ACM Press, October 2007
6.
7.
8.
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Ashby, V. (ed.) ACM CCS 1993, pp. 62–73. ACM Press, November 1993
9.
Bowers, K.D., Juels, A., Oprea, A.: Proofs of retrievability: theory and implementation. In: CCSW, pp. 43–54 (2009)
10.
Buhrman, H., Cleve, R., Koucký, M., Loff, B., Speelman, P.: Computing with a full memory: catalytic space. In: Symposium on Theory of Computing, STOC 2014, May 31 - June 03 2014, pp. 857–866, New York, NY, USA (2014)
11.
Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited (preliminary version). In: 30th ACM STOC, pp. 209–218. ACM Press, May 1998
12.
Canetti, R., Halevi, S., Steiner, M.: Mitigating dictionary attacks on password-protected local storage. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 160–179. Springer, Heidelberg (2006) CrossRef
13.
Di Pietro, R., Mancini, L.V., Law, Y.W., Etalle, S., Havinga, P.: Lkhw: a directed diffusion-based secure multicast scheme for wireless sensor networks. In: 2003 Proceedings of the International Conference on Parallel Processing Workshops, pp. 397–406 (2003)
14.
Douceur, J.R.: The sybil attack. In: Druschel, P., Kaashoek, M.F., Rowstron, A. (eds.) IPTPS 2002. LNCS, vol. 2429, pp. 251–260. Springer, Heidelberg (2002) CrossRef
15.
Dwork, C., Goldberg, A.V., Naor, M.: On memory-bound functions for fighting spam. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 426–444. Springer, Heidelberg (2003) CrossRef
16.
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) CrossRef
17.
Dwork, C., Naor, M., Wee, H.M.: Pebbling and proofs of work. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 37–54. Springer, Heidelberg (2005) CrossRef
18.
19.
Dziembowski, S., Kazana, T., Wichs, D.: Key-evolution schemes resilient to space-bounded leakage. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 335–353. Springer, Heidelberg (2011) CrossRef
20.
Dziembowski, S., Kazana, T., Wichs, D.: One-time computable self-erasing functions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 125–143. Springer, Heidelberg (2011) CrossRef
21.
Erdös, P., Graham, R.L., Szemerédi, E.: On sparse graphs with dense long paths. Technical report STAN-CS-75-504, Stanford University, Computer Science Department (1975)
22.
Franklin, K.M., Malkhi, D.: Auditable metering with lightweight security. In: Luby, M., Rolim, J.D.P., Serna, M. (eds.) FC 1997. LNCS, vol. 1318, pp. 151–160. Springer, Heidelberg (1997) CrossRef
23.
Goldwasser, S., Kalai, Y.T.: On the (in)security of the Fiat-Shamir paradigm. In: 44th FOCS, pp. 102–115. IEEE Computer Society Press, October 2003
24.
Golle, P., Jarecki, S., Mironov, I.: Cryptographic primitives enforcing communication and storage complexity. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 120–135. Springer, Heidelberg (2003) CrossRef
25.
Gratzer, V., Naccache, D.: Alien vs. quine. IEEE Secur. Priv. 5(2), 26–31 (2007)CrossRef
26.
Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols - a tight lower bound on the round complexity of statistically-hiding commitments. In: 48th FOCS, pp.669–679. IEEE Computer Society Press, October 2007
27.
28.
29.
Jakobsson, M., Juels, A.: Proofs of work and bread pudding protocols. In: Preneel, B. (ed.) Proceedings of the IFIP Conference on Communications and Multimedia Security, vol. 152, pp. 258–272. Kluwer (1999)
30.
Juels, A., Brainard, J.G.: Client puzzles: a cryptographic countermeasure against connection depletion attacks. In: NDSS 1999. The Internet Society, February 1999
31.
Juels, A., Kaliski Jr., B.S.: Pors: proofs of retrievability for large files. In: Ning, P., De Capitani di Vimercati, S., Syverson, P.F. (eds.) ACM CCS 07, pp. 584–597. ACM Press, October 2007
32.
Karvelas, N.P., Kiayias, A.: Efficient proofs of secure erasure. In: Abdalla, M., De Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 520–537. Springer, Heidelberg (2014)
33.
Lengauer, T., Tarjan, R.E.: Asymptotically tight bounds on time-space trade-offs in a pebble game. J. ACM 29(4), 1087–1130 (1982)MathSciNetCrossRefMATH
34.
Maurer, U.M., Renner, R.S., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21–39. Springer, Heidelberg (2004) CrossRef
35.
Merkle, R.C.: Method of providing digital signatures. US Patent 4309569, 5 January 1982
36.
37.
Micali, S., Rivest, R.L.: Micropayments revisited. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, pp. 149–163. Springer, Heidelberg (2002) CrossRef
38.
39.
40.
Paul, W.J., Tarjan, R.E., Celoni, J.R.: Space bounds for a game on graphs. Math. Syst. Theory 10(1), 239–251 (1976–1977)
41.
Perito, D., Tsudik, G.: Secure code update for embedded devices via proofs of secure erasure. In: Gritzalis, D., Preneel, B., Theoharidou, M. (eds.) ESORICS 2010. LNCS, vol. 6345, pp. 643–662. Springer, Heidelberg (2010) CrossRef
42.
Rivest, R.L., Shamir, A.: Payword and micromint: two simple micropayment schemes. In: CryptoBytes, pp. 69–87 (1996)
43.
Rogaway, P.: Formalizing human ignorance. In: Nguyên, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 211–228. Springer, Heidelberg (2006) CrossRef
44.
Savage, J.E.: Models of Computation: Exploring the Power of Computing, 1st edn. Addison-Wesley Longman Publishing Co. Inc., Boston (1997)
45.
Simon, D.R.: Findings collisions on a one-way street: can secure hash functions be based on general assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 334–345. Springer, Heidelberg (1998) CrossRef
46.
Von Ahn, L., Blum, M., Hopper, N.J., Langford, J.: CAPTCHA: Using hard AI problems for security. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 246–256. Springer, Heidelberg (2003)
47.
Waters, B., Juels, A., Halderman, J.A., Felten, E.W.: New client puzzle outsourcing techniques for dos resistance. In: Proceedings of the 11th ACM Conference on Computer and Communications Security, CCS 2004, pp. 246–256. ACM, New York (2004)
Metadaten
Titel
Proofs of Space
verfasst von
Stefan Dziembowski
Sebastian Faust
Vladimir Kolmogorov
Krzysztof Pietrzak
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
Buch
Advances in Cryptology -- CRYPTO 2015

Print ISBN: 978-3-662-47999-5

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

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-662-48000-7_29