Optimal Trade-Off for Merkle Tree Traversal View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2007

AUTHORS

Piotr Berman , Marek Karpinski , Yakov Nekrich

ABSTRACT

In this paper we describe optimal trade-offs between time and space complexity of Merkle tree traversals with their associated authentication paths, improving on the previous results of Jakobsson, Leighton, Micali, and Szydlo (Jakobsson et al., 03) and Szydlo (Szydlo, 04). In particular, we show that our algorithm requires 2 logn/log(3)n hash function computations and storage for less than (logn/log(3)n + 1)loglogn + 2 logn hash values, where n is the number of leaves in the Merkle tree. We also prove that these trade-offs are optimal, i.e. there is no algorithm that requires less than O(logn/logt) time and less than O(tlogn/logt) space for any choice of parameter t ≥ 2.Our algorithm could be of special use in the case when both time and space are limited. More... »

PAGES

150-162

Book

TITLE

E-business and Telecommunication Networks

ISBN

978-3-540-75992-8
978-3-540-75993-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-75993-5_13

DOI

http://dx.doi.org/10.1007/978-3-540-75993-5_13

DIMENSIONS

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


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/14", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Economics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1402", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Economics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Dept.of Computer Science and Engineering, The Pennsylvania State University, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Dept.of Computer Science and Engineering, The Pennsylvania State University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, University of Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Computer Science, University of Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, University of Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Computer Science, University of Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nekrich", 
        "givenName": "Yakov", 
        "id": "sg:person.014556642366.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014556642366.63"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2007", 
    "datePublishedReg": "2007-01-01", 
    "description": "In this paper we describe optimal trade-offs between time and space complexity of Merkle tree traversals with their associated authentication paths, improving on the previous results of Jakobsson, Leighton, Micali, and Szydlo (Jakobsson et al., 03) and Szydlo (Szydlo, 04). In particular, we show that our algorithm requires 2 logn/log(3)n hash function computations and storage for less than (logn/log(3)n\u2009+\u20091)loglogn\u2009+\u20092 logn hash values, where n is the number of leaves in the Merkle tree. We also prove that these trade-offs are optimal, i.e. there is no algorithm that requires less than O(logn/logt) time and less than O(tlogn/logt) space for any choice of parameter t\u2009\u2265\u20092.Our algorithm could be of special use in the case when both time and space are limited.", 
    "editor": [
      {
        "familyName": "Filipe", 
        "givenName": "Joaquim", 
        "type": "Person"
      }, 
      {
        "familyName": "Coelhas", 
        "givenName": "Helder", 
        "type": "Person"
      }, 
      {
        "familyName": "Saramago", 
        "givenName": "Monica", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-75993-5_13", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-75992-8", 
        "978-3-540-75993-5"
      ], 
      "name": "E-business and Telecommunication Networks", 
      "type": "Book"
    }, 
    "keywords": [
      "special use", 
      "choice", 
      "parameter t", 
      "logn/", 
      "function computation", 
      "optimal", 
      "space complexity", 
      "Jakobsson", 
      "tree traversal", 
      "Szydlo", 
      "previous results", 
      "algorithm", 
      "path", 
      "space", 
      "values", 
      "time", 
      "computation", 
      "Leighton", 
      "results", 
      "cases", 
      "complexity", 
      "traversal", 
      "number", 
      "use", 
      "Micali", 
      "hash value", 
      "trees", 
      "storage", 
      "number of leaves", 
      "Merkle tree", 
      "leaves", 
      "paper", 
      "authentication path", 
      "hash function computations"
    ], 
    "name": "Optimal Trade-Off for Merkle Tree Traversal", 
    "pagination": "150-162", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1035132748"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-75993-5_13"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-75993-5_13", 
      "https://app.dimensions.ai/details/publication/pub.1035132748"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:22", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_416.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-75993-5_13"
  }
]
 

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/978-3-540-75993-5_13'

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/978-3-540-75993-5_13'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-75993-5_13'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-75993-5_13'


 

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

120 TRIPLES      22 PREDICATES      59 URIs      52 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-75993-5_13 schema:about anzsrc-for:14
2 anzsrc-for:1402
3 schema:author N5714bb71678f4b1bb24692a7b4407eff
4 schema:datePublished 2007
5 schema:datePublishedReg 2007-01-01
6 schema:description In this paper we describe optimal trade-offs between time and space complexity of Merkle tree traversals with their associated authentication paths, improving on the previous results of Jakobsson, Leighton, Micali, and Szydlo (Jakobsson et al., 03) and Szydlo (Szydlo, 04). In particular, we show that our algorithm requires 2 logn/log(3)n hash function computations and storage for less than (logn/log(3)n + 1)loglogn + 2 logn hash values, where n is the number of leaves in the Merkle tree. We also prove that these trade-offs are optimal, i.e. there is no algorithm that requires less than O(logn/logt) time and less than O(tlogn/logt) space for any choice of parameter t ≥ 2.Our algorithm could be of special use in the case when both time and space are limited.
7 schema:editor N0d2045f418df4419b029182a0a34a1fa
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N3679001e181e4e3b90acbdc0c4220505
11 schema:keywords Jakobsson
12 Leighton
13 Merkle tree
14 Micali
15 Szydlo
16 algorithm
17 authentication path
18 cases
19 choice
20 complexity
21 computation
22 function computation
23 hash function computations
24 hash value
25 leaves
26 logn/
27 number
28 number of leaves
29 optimal
30 paper
31 parameter t
32 path
33 previous results
34 results
35 space
36 space complexity
37 special use
38 storage
39 time
40 traversal
41 tree traversal
42 trees
43 use
44 values
45 schema:name Optimal Trade-Off for Merkle Tree Traversal
46 schema:pagination 150-162
47 schema:productId N9e727487693e4a66a55607160e5e49ff
48 Ncc29a9c25b744a859ce2a9d1e89c1a7c
49 schema:publisher N92757eeb1e184b108bce547558ec62ad
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035132748
51 https://doi.org/10.1007/978-3-540-75993-5_13
52 schema:sdDatePublished 2022-08-04T17:22
53 schema:sdLicense https://scigraph.springernature.com/explorer/license/
54 schema:sdPublisher Nc82ee357c5414b55ac7967f55702bc78
55 schema:url https://doi.org/10.1007/978-3-540-75993-5_13
56 sgo:license sg:explorer/license/
57 sgo:sdDataset chapters
58 rdf:type schema:Chapter
59 N0c6a1b0a80ad455cb3683b4faa721445 schema:familyName Coelhas
60 schema:givenName Helder
61 rdf:type schema:Person
62 N0d2045f418df4419b029182a0a34a1fa rdf:first Nacf2989d57d044d6b9886450794f7471
63 rdf:rest N60bf8dd8c6d54a11a910cab2c3fb4d3f
64 N19e7a24b44ca49af8a7e60aa201f536d rdf:first N30bd45f170e94b1b9d0081cf4ecfa688
65 rdf:rest rdf:nil
66 N30bd45f170e94b1b9d0081cf4ecfa688 schema:familyName Saramago
67 schema:givenName Monica
68 rdf:type schema:Person
69 N3679001e181e4e3b90acbdc0c4220505 schema:isbn 978-3-540-75992-8
70 978-3-540-75993-5
71 schema:name E-business and Telecommunication Networks
72 rdf:type schema:Book
73 N5714bb71678f4b1bb24692a7b4407eff rdf:first sg:person.01274506210.27
74 rdf:rest Nac73e86e7383443f8d3c79648beb912b
75 N60bf8dd8c6d54a11a910cab2c3fb4d3f rdf:first N0c6a1b0a80ad455cb3683b4faa721445
76 rdf:rest N19e7a24b44ca49af8a7e60aa201f536d
77 N92757eeb1e184b108bce547558ec62ad schema:name Springer Nature
78 rdf:type schema:Organisation
79 N9e727487693e4a66a55607160e5e49ff schema:name dimensions_id
80 schema:value pub.1035132748
81 rdf:type schema:PropertyValue
82 Nac73e86e7383443f8d3c79648beb912b rdf:first sg:person.011636042271.02
83 rdf:rest Nbf800ee17e964cd3a53829e3bdec5db7
84 Nacf2989d57d044d6b9886450794f7471 schema:familyName Filipe
85 schema:givenName Joaquim
86 rdf:type schema:Person
87 Nbf800ee17e964cd3a53829e3bdec5db7 rdf:first sg:person.014556642366.63
88 rdf:rest rdf:nil
89 Nc82ee357c5414b55ac7967f55702bc78 schema:name Springer Nature - SN SciGraph project
90 rdf:type schema:Organization
91 Ncc29a9c25b744a859ce2a9d1e89c1a7c schema:name doi
92 schema:value 10.1007/978-3-540-75993-5_13
93 rdf:type schema:PropertyValue
94 anzsrc-for:14 schema:inDefinedTermSet anzsrc-for:
95 schema:name Economics
96 rdf:type schema:DefinedTerm
97 anzsrc-for:1402 schema:inDefinedTermSet anzsrc-for:
98 schema:name Applied Economics
99 rdf:type schema:DefinedTerm
100 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
101 schema:familyName Karpinski
102 schema:givenName Marek
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
104 rdf:type schema:Person
105 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
106 schema:familyName Berman
107 schema:givenName Piotr
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
109 rdf:type schema:Person
110 sg:person.014556642366.63 schema:affiliation grid-institutes:grid.10388.32
111 schema:familyName Nekrich
112 schema:givenName Yakov
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014556642366.63
114 rdf:type schema:Person
115 grid-institutes:grid.10388.32 schema:alternateName Dept. of Computer Science, University of Bonn, Germany
116 schema:name Dept. of Computer Science, University of Bonn, Germany
117 rdf:type schema:Organization
118 grid-institutes:grid.29857.31 schema:alternateName Dept.of Computer Science and Engineering, The Pennsylvania State University, USA
119 schema:name Dept.of Computer Science and Engineering, The Pennsylvania State University, USA
120 rdf:type schema:Organization
 




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


...