Pebbling and Proofs of Work View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Cynthia Dwork , Moni Naor , Hoeteck Wee

ABSTRACT

We investigate methods for providing easy-to-check proofs of computational effort. Originally intended for discouraging spam, the concept has wide applicability as a method for controlling denial of service attacks. Dwork, Goldberg, and Naor proposed a specific memory-bound function for this purpose and proved an asymptotically tight amortized lower bound on the number of memory accesses any polynomial time bounded adversary must make. Their function requires a large random table which, crucially, cannot be compressed.We answer an open question of Dwork et al. by designing a compact representation for the table. The paradox, compressing an incompressible table, is resolved by embedding a time/space tradeoff into the process for constructing the table from its representation. More... »

PAGES

37-54

Book

TITLE

Advances in Cryptology – CRYPTO 2005

ISBN

978-3-540-28114-6
978-3-540-31870-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11535218_3

DOI

http://dx.doi.org/10.1007/11535218_3

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1021929123


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Microsoft Research, Silicon Valley Campus", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Microsoft Research, Silicon Valley Campus"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dwork", 
        "givenName": "Cynthia", 
        "id": "sg:person.016065712157.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016065712157.59"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Weizmann Institute of Science", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Weizmann Institute of Science"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Naor", 
        "givenName": "Moni", 
        "id": "sg:person.07776170271.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of California, Berkeley", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "University of California, Berkeley"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wee", 
        "givenName": "Hoeteck", 
        "id": "sg:person.011724333061.15", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011724333061.15"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "We investigate methods for providing easy-to-check proofs of computational effort. Originally intended for discouraging spam, the concept has wide applicability as a method for controlling denial of service attacks. Dwork, Goldberg, and Naor proposed a specific memory-bound function for this purpose and proved an asymptotically tight amortized lower bound on the number of memory accesses any polynomial time bounded adversary must make. Their function requires a large random table which, crucially, cannot be compressed.We answer an open question of Dwork et al. by designing a compact representation for the table. The paradox, compressing an incompressible table, is resolved by embedding a time/space tradeoff into the process for constructing the table from its representation.", 
    "editor": [
      {
        "familyName": "Shoup", 
        "givenName": "Victor", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11535218_3", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-28114-6", 
        "978-3-540-31870-5"
      ], 
      "name": "Advances in Cryptology \u2013 CRYPTO 2005", 
      "type": "Book"
    }, 
    "keywords": [
      "proof of work", 
      "time/space tradeoff", 
      "Dwork et al", 
      "number of memory", 
      "service attacks", 
      "compact representation", 
      "polynomial time", 
      "space tradeoffs", 
      "computational effort", 
      "wide applicability", 
      "table", 
      "representation", 
      "adversary", 
      "spam", 
      "Naor", 
      "Dwork", 
      "proof", 
      "tradeoff", 
      "denial", 
      "attacks", 
      "open question", 
      "pebbling", 
      "method", 
      "memory", 
      "applicability", 
      "concept", 
      "random table", 
      "work", 
      "efforts", 
      "et al", 
      "number", 
      "process", 
      "time", 
      "function", 
      "purpose", 
      "Goldberg", 
      "questions", 
      "al", 
      "paradox", 
      "check proofs", 
      "specific memory-bound function", 
      "memory-bound function", 
      "large random table", 
      "incompressible table"
    ], 
    "name": "Pebbling and Proofs of Work", 
    "pagination": "37-54", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1021929123"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11535218_3"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11535218_3", 
      "https://app.dimensions.ai/details/publication/pub.1021929123"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:18", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_317.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11535218_3"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/11535218_3'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/11535218_3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11535218_3'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11535218_3'


 

This table displays all metadata directly associated to this object as RDF triples.

124 TRIPLES      23 PREDICATES      70 URIs      63 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11535218_3 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N42831799473b4ac486b6bf8be6393cdd
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description We investigate methods for providing easy-to-check proofs of computational effort. Originally intended for discouraging spam, the concept has wide applicability as a method for controlling denial of service attacks. Dwork, Goldberg, and Naor proposed a specific memory-bound function for this purpose and proved an asymptotically tight amortized lower bound on the number of memory accesses any polynomial time bounded adversary must make. Their function requires a large random table which, crucially, cannot be compressed.We answer an open question of Dwork et al. by designing a compact representation for the table. The paradox, compressing an incompressible table, is resolved by embedding a time/space tradeoff into the process for constructing the table from its representation.
7 schema:editor N139f17df3d73477ebcfb8df737ed6ffd
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Ne6a2911967ea46a48abe464b99d3b5f1
12 schema:keywords Dwork
13 Dwork et al
14 Goldberg
15 Naor
16 adversary
17 al
18 applicability
19 attacks
20 check proofs
21 compact representation
22 computational effort
23 concept
24 denial
25 efforts
26 et al
27 function
28 incompressible table
29 large random table
30 memory
31 memory-bound function
32 method
33 number
34 number of memory
35 open question
36 paradox
37 pebbling
38 polynomial time
39 process
40 proof
41 proof of work
42 purpose
43 questions
44 random table
45 representation
46 service attacks
47 space tradeoffs
48 spam
49 specific memory-bound function
50 table
51 time
52 time/space tradeoff
53 tradeoff
54 wide applicability
55 work
56 schema:name Pebbling and Proofs of Work
57 schema:pagination 37-54
58 schema:productId N7e7fe09e17cb4041babe81e3b3d3ec79
59 N8b5558b0d8c84bf3b2058c6286cfe6b4
60 schema:publisher N743d7df47545439e8ce54b6f56fb7ea9
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021929123
62 https://doi.org/10.1007/11535218_3
63 schema:sdDatePublished 2022-01-01T19:18
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher N4efa33874fe342ddb2911afe32679295
66 schema:url https://doi.org/10.1007/11535218_3
67 sgo:license sg:explorer/license/
68 sgo:sdDataset chapters
69 rdf:type schema:Chapter
70 N139f17df3d73477ebcfb8df737ed6ffd rdf:first Nfc7fe2c0b77f4899a04c1adbf669dda2
71 rdf:rest rdf:nil
72 N42831799473b4ac486b6bf8be6393cdd rdf:first sg:person.016065712157.59
73 rdf:rest N5748d42db5dc41669501cdf470f7e022
74 N4efa33874fe342ddb2911afe32679295 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 N5748d42db5dc41669501cdf470f7e022 rdf:first sg:person.07776170271.83
77 rdf:rest Ne18e295ed20a42b1872422a136efeff7
78 N743d7df47545439e8ce54b6f56fb7ea9 schema:name Springer Nature
79 rdf:type schema:Organisation
80 N7e7fe09e17cb4041babe81e3b3d3ec79 schema:name dimensions_id
81 schema:value pub.1021929123
82 rdf:type schema:PropertyValue
83 N8b5558b0d8c84bf3b2058c6286cfe6b4 schema:name doi
84 schema:value 10.1007/11535218_3
85 rdf:type schema:PropertyValue
86 Ne18e295ed20a42b1872422a136efeff7 rdf:first sg:person.011724333061.15
87 rdf:rest rdf:nil
88 Ne6a2911967ea46a48abe464b99d3b5f1 schema:isbn 978-3-540-28114-6
89 978-3-540-31870-5
90 schema:name Advances in Cryptology – CRYPTO 2005
91 rdf:type schema:Book
92 Nfc7fe2c0b77f4899a04c1adbf669dda2 schema:familyName Shoup
93 schema:givenName Victor
94 rdf:type schema:Person
95 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
96 schema:name Information and Computing Sciences
97 rdf:type schema:DefinedTerm
98 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
99 schema:name Computation Theory and Mathematics
100 rdf:type schema:DefinedTerm
101 sg:person.011724333061.15 schema:affiliation grid-institutes:grid.47840.3f
102 schema:familyName Wee
103 schema:givenName Hoeteck
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011724333061.15
105 rdf:type schema:Person
106 sg:person.016065712157.59 schema:affiliation grid-institutes:None
107 schema:familyName Dwork
108 schema:givenName Cynthia
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016065712157.59
110 rdf:type schema:Person
111 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
112 schema:familyName Naor
113 schema:givenName Moni
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
115 rdf:type schema:Person
116 grid-institutes:None schema:alternateName Microsoft Research, Silicon Valley Campus
117 schema:name Microsoft Research, Silicon Valley Campus
118 rdf:type schema:Organization
119 grid-institutes:grid.13992.30 schema:alternateName Weizmann Institute of Science
120 schema:name Weizmann Institute of Science
121 rdf:type schema:Organization
122 grid-institutes:grid.47840.3f schema:alternateName University of California, Berkeley
123 schema:name University of California, Berkeley
124 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...