Compact Certificates of Collective Knowledge

We introduce compact certificate schemes, which allow any party to take a large number of signatures on a message 𝑀, 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 𝑀, 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× smaller and 300-4000× cheaper to verify than a natural baseline approach.