Cryptology ePrint Archive: Report 2007/433
An (Almost) Constant-Effort Solution-Verification Proof-of-Work Protocol based on Merkle Trees
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.
Category / Keywords: cryptographic protocols / proof-of-work solution-verification protocol Merkle-tree
Publication Info: AfricaCrypt 2008
Date: received 22 Nov 2007, last revised 22 Jun 2008
Contact author: iacr org at coelho net
Available format(s): PDF | BibTeX Citation
Note: Updated and clarified wrt comments received at AfricaCrypt.
Include (nice) color pictures which were not possible in LNCS.
Version: 20080622:111434 (All versions of this report)
Short URL: ia.cr/2007/433
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]