Paper 2020/1568

Compact Certificates of Collective Knowledge

Silvio Micali, Leonid Reyzin, Georgios Vlachos, Riad S. Wahby, and Nickolai Zeldovich


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. IEEE S&P 2021
digital signaturesproof systemsimplementationblockchainconsensus
Contact author(s)
rsw @ cs stanford edu
reyzin @ cs bu edu
2021-03-30: revised
2020-12-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Silvio Micali and Leonid Reyzin and Georgios Vlachos and Riad S.  Wahby and Nickolai Zeldovich},
      title = {Compact Certificates of Collective Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1568},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.