High-level design for efficient exact-weight TSS

[tinker-michaelj]

Problem

A threshold signature scheme (TSS) uses an access structure to control what combinations of partial signatures count as a full signature.

The natural access structure for a proof-of-stake aBFT blockchain is:

• Partial signatures from any subset of nodes holding at least 1/3 of the stake count as a full signature.

Despite how obvious this condition is, it is extremely non-obvious how to construct a TSS with exact (e.g., 64-bit) party weights that efficiently implements this access structure.

This is because efficiency requires,

• A stable ledger identity that provers can trust no matter how the network's membership and partial keys have evolved during any period since adoption of the TSS in which aBFT security holds.
• Concise signatures whose size is independent of the size of the network.
• Fixed-cost and non-interactive verification of these signatures.

But given centuries of mathematical innovation, decades of cryptography research, and finally years of accumulated ingenuity by the Hashgraph cryptography team, such a TSS now exists.

We want a design document that captures how we will implement this efficient exact-weight TSS.

Solution

Create this design document.

Alternatives

No response