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

Original Publication (in the same form): IEEE S&P 2021

Date: received 15 Dec 2020, last revised 30 Mar 2021

Contact author: rsw at cs stanford edu,reyzin@cs bu edu

Available format(s): PDF | BibTeX Citation

Version: 20210330:194331 (All versions of this report)

Short URL: ia.cr/2020/1568