Cryptology ePrint Archive: Report 2020/1568
Compact Certificates of Collective Knowledge
Silvio Micali and Leonid Reyzin and Georgios Vlachos and Riad S. Wahby and Nickolai Zeldovich
Abstract: We introduce compact certificate schemes, which allow any party to take
a large number of signatures on a message $M$, by many signers of different
weights, and compress them to a much shorter certificate. This certificate
convinces the verifiers that signers with sufficient total weight signed
$M$, even though the verifier will not see---let alone verify---all of the
signatures. Thus, for example, a compact certificate can be used to prove
that parties who jointly have a sufficient total account balance have
attested to a given block in a blockchain.
After defining compact certificates, we demonstrate an efficient compact
certificate scheme. We then show how to implement such a scheme in
a decentralized setting over an unreliable network and in the presence
of adversarial parties who wish to disrupt certificate creation. Our
evaluation shows that compact certificates are 50--280$\times$ smaller
and 300--4000$\times$ cheaper to verify than a natural baseline approach.
Category / Keywords: cryptographic protocols / digital signatures, proof systems, implementation, blockchain, consensus
Date: received 15 Dec 2020, last revised 16 Dec 2020
Contact author: rsw at cs stanford edu, reyzin@cs bu edu
Available format(s): PDF | BibTeX Citation
Version: 20201217:095701 (All versions of this report)
Short URL: ia.cr/2020/1568
[ Cryptology ePrint archive ]