Paper 2020/1568

Compact Certificates of Collective Knowledge

Silvio Micali, Leonid Reyzin, Georgios Vlachos, 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.