Skip to main content

Cryptography

Signing transfers on blockchains require multi-party computation (MPC) protocols for two operations:

  • Key generation
  • Signing (in ECDSA and Schnorr variants)

Generally, we prefer protocols which are both easy to understand conceptually, as well as easy to implement and audit in software.

Key generation​

The input to distributed key generation (DKG) is the selection of participants (for instance, all signing nodes) and the threshold required to operated with the key. The output is a public key, together with private key shares for participating nodes. We expose the corresponding public verifying keys as "shares" in our key resource data, as this allows verifying signature shares individually - before combining the shares and verifying against the combined public key.

We currently use the PedPop protocol from FROST (KG20), which combines Pedersen's distributed key generation (DKG) Ped92 with proofs of possession. It allows generating keys for any threshold and any number of participants on any elliptic curve. We intend to replace this protocol with a DKG that is provably secure in the Universal Composability framework Canetti00 ("UC-secure").

Signing​

From a distributed threshold signing protocol we require that, in principal, it allows prepared signatures (or "presignatures"). These are cryptographic objects that are only missing the message to be signed, can be prepared in advance ("offline"), such that in the online signing step no communication among signing nodes is required.

Schnorr signing​

Newer blockchains tend to use the simpler Schnorr signing algorithm - older blockchains do not, as this algorithm was encumbered by a patent which expired in February 2010. For example, Solana and Aptos, but also more recently Bitcoin with the recent Taproot upgrade (BIP 340). For these, we use the FROST protocol KG20. It is a simple 2-round protocol. We may replace this protocol with Lindell's 3-round protocol Lindell22, which has the advantage of being UC-secure.

ECDSA signing​

Many blockchains, for example Ethereum, continue to use the Elliptic Curve Digital Signature Algorithm (ECDSA), which is significantly harder to implement with a threshold MPC protocol. The reason being that it lacks an "additivity" property that Schnorr signatures have. Essentially, DSA (in particular DSA on elliptic curves) was created to circumvent the Schnorr patent, and added this technical complication.

From a high-level perspective, there are three approaches to threshold ECDSA signing:

Homomorphic Encryption. This line of research uses (somewhat) homomorphic encryption to convert between multiplicative and additive shares, the current culmination is CGGMP21. The great downside of this is having to require participants to "prove everything under the sun", which certainly does not fulfill our requirement of being a "simplest" protocol.

Oblivious Transfer. This line of research uses Gilboa's bitwise multiplication from Gilboa99 to calculate the share multiplications via oblivious transfer, the current culmination is Doerner, Kondi, Lee and shelat (2019). The downside in this case is a large amount of communication overhead, which is tempered by being able to do it in advance.

Trusted Setup. Don Beaver observed that, if one has available the shares of two random secrets together with the shares of their product (as so-called "Beaver triple"), then the product of two secrets can be derived by "consuming" a Beaver triple and performing some simple algebra. This allows "distributing any elliptic curve based protocol" ST19, as another observation by Don Beaver shows that inversion can be constructed once multiplication is constructed.

We currently use this third approach. It has the advantage of extreme conceptual and implementation simplicity. Practically, Beaver triples can be created efficiently in great numbers and replenished if necessary. Essentially the same protocol was designed concurrently as Cait-Sith, and previously in DKOSS19.

Nevertheless, we intend to replace our approach with DKLs23 once there is peer review for the work of these authors, as it is both straightforward to implement, and removes the trusted setup requirement.