Advanced Digital Signatures

Certificates

A certificate is one issuing key signing a message containing another certified key, which attests to some properties or relationship about the certified key.

Certificates

Issuing keys do not necessarily have unilateral certification capabilities, although some do.

For example, the certificate transparency protocol for TLS certificates helps protect against compromised Certificate Authorities.

Certificates in Web3

We are building systems that don't have a "Certificate Authority". But we can still use certificates in some niche instances.

Multi-Signatures

We often want signatures that must be signed by multiple parties to become valid.

• Require some threshold of members to agree to a message
• Protect against key loss

Types of Multi-Signature

Verifier Enforced Multiple Signatures

We assume that there is some verifier, who can check that some threshold of individual keys have provided valid signatures.

This could be a trusted company or third party. For our purposes, it's a blockchain.

Verifier Enforced Multiple Signatures

Multiple signatures enforced by a verifier generally provide a good user experience, as no interaction is required from the participants.

Cryptographic Threshold Multi-Sigs

Cryptographic multi-signatures can be achieved purely on the signer side (without support from the verifier). This makes more compact signatures compatible with legacy systems.

Cryptographic Non-Threshold Multi-Sigs

Sometimes we do not need a threshold represented in a public key. But we want a succinct way to demonstrate that multiple parties have signed a message.

Key Generation - Threshold

Threshold multi-signature schemes require that all signers run a distributed key generation (DKG) protocol that constructs key shares.

The secret encodes the threshold behavior, and signing demands some threshold of signature fragments.

This DKG protocol breaks other useful things, like hard key derivation.

Key Generation - Non-Threshold

In non-threshold multi-signatures, signatures from individual public keys are aggregated.

Each participant can choose their own key to use for the multi-signature.

Schnorr Multi-Sigs

Schnorr signatures are primarily used for threshold multi-sig.

• Fit legacy systems nicely, and can reduce fees on blockchains.
• Reduce verifier costs in bandwidth & CPU time, so great for certificates.
• Could support soft key derivations.

Schnorr Multi-Sigs

However, automation becomes tricky.

We need agreement upon the final signer list and two random nonce contributions from each prospective signer, before constructing the signature fragments.

BLS Signatures

BLS signatures are especially useful for aggregated (non-threshold) multi-signatures (but can be used for threshold as well).

Signatures can be aggregated without advanced agreement upon the signer list, which simplifies automation and makes them useful in consensus.

Verifying individual signatures is slow, but verifying aggregated ones is relatively fast.

(Coming to Substrate soon.)

BLS Signatures

Allows multiple signatures generated under multiple public keys for multiple messages to be aggregated into a single signature.

BLS Signatures

However...

• DKGs remain tricky (for threshold).
• Soft key derivations are typically insecure for BLS.
• Verifiers are hundreds of times slower than Schnorr, due to using pairings, for a single signature.
• But for hundreds or thousands of signatures on the same message, aggregated signature verification can be much faster than Schnorr.

Schnorr and BLS Summary

Schnorr & BLS multi-signatures avoid complicating verifier logic, but introduce user experience costs such as:

• DKG protocols
• Reduced key derivation ability
• Verification speed

Ring Signatures

• Ring signatures prove the signer lies within some "anonymity set" of signing keys, but hide which key actually signed.
• Ring signatures come in many sizes, with many ways of presenting their anonymity sets.
• Anonymous blockchain transactions typically employ ring signatures.

Next Lesson

• Exotic Primitives
• Hash functions and data structures