Skip to main content

2019 | OriginalPaper | Buchkapitel

Tight Proofs of Space and Replication

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

search-config
loading …

Abstract

We construct a concretely practical proof-of-space (PoS) with arbitrarily tight security based on stacked depth robust graphs and constant-degree expander graphs. A proof-of-space (PoS) is an interactive proof system where a prover demonstrates that it is persistently using space to store information. A PoS is arbitrarily tight if the honest prover uses exactly N space and for any \(\epsilon > 0\) the construction can be tuned such that no adversary can pass verification using less than \((1-\epsilon ) N\) space. Most notably, the degree of the graphs in our construction are independent of \(\epsilon \), and the number of layers is only \(O(\log (1/\epsilon ))\). The proof size is \(O(d/\epsilon )\). The degree d depends on the depth robust graphs, which are only required to maintain \(\varOmega (N)\) depth in subgraphs on 80% of the nodes. Our tight PoS is also secure against parallel attacks.
Tight proofs of space are necessary for proof-of-replication (PoRep), which is a publicly verifiable proof that the prover is dedicating unique resources to storing one or more retrievable replicas of a specified file. Our main PoS construction can be used as a PoRep, but data extraction is as inefficient as replica generation. We present a second variant of our construction called ZigZag PoRep that has fast/parallelizable data extraction compared to replica generation and maintains the same space tightness while only increasing the number of levels by roughly a factor two.

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!

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!

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!

Fußnoten
2
For practical parameters, the Ren and Devadas construction has a space gap larger than 1/2. For example, it requires a graph of degree at least 40 in order to achieve a space gap of less than 2/3.
 
3
There is experimental evidence that a simple DRG construction with concretely small constant degree (even degree 2) has this property on a graph of size \(N = 2^{20}\) [3].
 
4
Asymptotically, this is close to the optimal proof complexity achievable for any PoS based on graph labeling that has an \(\epsilon \) space gap. If the prover claims to be storing n labels and the proof queries less than \(1/\epsilon \) then a random deletion of an \(\epsilon \) fraction of these labels evades detection with probability at least \((1 - \epsilon )^{1/\epsilon } \approx 1/e\).
 
5
In prior uses of the red-black pebbling game to analyze proofs of space, it sufficed to consider parallel black pebbling complexity because replacing red pebbles with “free” black pebbles only increases the adversary’s power. Our more refined analysis requires analyzing the weaker adversary who is restricted to a maximum number of red pebbles on each level of the graph, enforced by the construction.
 
6
The distinction between expander edges and all other edges is important in the analysis. In particular, the expander edges are between the same index nodes in every layer and differ only in their directionality.
 
Literatur
3.
Zurück zum Zitat Alwen, J., Blocki, J., Harsha, B.: Practical graphs for optimal side-channel resistant memory-hard functions. In: CCS (2017) Alwen, J., Blocki, J., Harsha, B.: Practical graphs for optimal side-channel resistant memory-hard functions. In: CCS (2017)
6.
Zurück zum Zitat Chung, F.R.K.: On concentrators, superconcentrators, generalizers, and nonblocking networks. Bell Syst. Tech. J. 58, 1765–1777 (1979)MathSciNetCrossRef Chung, F.R.K.: On concentrators, superconcentrators, generalizers, and nonblocking networks. Bell Syst. Tech. J. 58, 1765–1777 (1979)MathSciNetCrossRef
12.
Zurück zum Zitat Boneh, D., Corrigan-Gibbs, H., Schechter, S.: Balloon hashing: a provably memory-hard function with a data-independent access pattern. In: Asiacrypt (2016) Boneh, D., Corrigan-Gibbs, H., Schechter, S.: Balloon hashing: a provably memory-hard function with a data-independent access pattern. In: Asiacrypt (2016)
15.
Zurück zum Zitat Vadhan, S., Reingold, O., Wigderson, A.: Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In: FOCS (2000) Vadhan, S., Reingold, O., Wigderson, A.: Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In: FOCS (2000)
17.
Zurück zum Zitat Graham, R.L., Erdös, P., Szemeredi, E.: On sparse graphs with dense long paths. In: Computers & Mathematics with Applications (1975) Graham, R.L., Erdös, P., Szemeredi, E.: On sparse graphs with dense long paths. In: Computers & Mathematics with Applications (1975)
18.
Zurück zum Zitat Pietrzak, K.: Proofs of catalytic space. Cryptology ePrint Archive # 2018/194 (2018) Pietrzak, K.: Proofs of catalytic space. Cryptology ePrint Archive # 2018/194 (2018)
Metadaten
Titel
Tight Proofs of Space and Replication
verfasst von
Ben Fisch
Copyright-Jahr
2019
DOI
https://doi.org/10.1007/978-3-030-17656-3_12