Paper 2007/433

An (Almost) Constant-Effort Solution-Verification Proof-of-Work Protocol based on Merkle Trees

Fabien Coelho

Abstract

Proof-of-work schemes are economic measures to deter denial-of-service attacks: service requesters compute moderately hard functions that are easy to check by the provider. We present such a new scheme for solution-verification protocols. Although most schemes to date are probabilistic unbounded iterative processes with high variance of the requester effort, our Merkle tree scheme is deterministic, with an almost constant effort and null variance, and is computation-optimal.

Note: Updated and clarified wrt comments received at AfricaCrypt. Include (nice) color pictures which were not possible in LNCS.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. AfricaCrypt 2008
Contact author(s)
iacr org @ coelho net
History
2008-06-22: last of 2 revisions
2007-11-24: received
See all versions
Short URL
https://ia.cr/2007/433
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/433,
      author = {Fabien Coelho},
      title = {An (Almost) Constant-Effort Solution-Verification Proof-of-Work Protocol based on Merkle Trees},
      howpublished = {Cryptology ePrint Archive, Paper 2007/433},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/433}},
      url = {https://eprint.iacr.org/2007/433}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.