/multi-party-sig

Implementation of protocols for threshold signatures

Primary LanguageGoApache License 2.0Apache-2.0

multi-party-sig

License

A Go implementation of multi-party threshold signing for:

  • ECDSA, using the "CGGMP" protocol by Canetti et al. for threshold ECDSA signing. We implement both the 4 round "online" and the 7 round "presigning" protocols from the paper. The latter also supports identifiable aborts. Implementation details are also documented in in docs/Threshold.pdf. Our implementation supports ECDSA with secp256k1, with other curves coming in the future.

  • Schnorr signatures (as integrated in Bitcoin's Taproot), using the FROST protocol. Because of the linear structure of Schnorr signatures, this protocol is less expensive than CMP. We've also made the necessary adjustments to make our signatures compatible with Taproot's specific point encoding, as specified in BIP-0340.

DISCLAIMER: Use at your own risk, this project needs further testing and auditing to be production-ready.

Features

  • BIP-32 key derivation. Parties can convert their shares of a public key into shares of a child key, as per BIP-32's key derivation spec. Only unhardened derivation is supported, since hardened derivation would require hashing the secret key, which no party has access to.
  • Constant-time arithmetic, via safenum. The CMP protocol requires Paillier encryption, as well as related ZK proofs performing modular arithmetic. We use a constant-time implementation of this arithmetic to mitigate timing-leaks
  • Parallel processing. When possible, we parallelize heavy computation to speed up protocol execution.

Usage

multi-party-sig was designed with the goal of supporting multiple threshold signature schemes. Each protocol can be invoked using one of the following functions:

Protocol Initialization Returns Description
cmp.Keygen(group curve.Curve, selfID party.ID, participants []party.ID, threshold int, pl *pool.Pool) *cmp.Config Generate a new ECDSA private key shared among all the given participants.
cmp.Refresh(config *cmp.Config, pl *pool.Pool) *cmp.Config Refreshes all shares of an existing ECDSA private key.
cmp.Sign(config *cmp.Config, signers []party.ID, messageHash []byte, pl *pool.Pool) *ecdsa.Signature Generates an ECDSA signature for messageHash.
cmp.Presign(config *cmp.Config, signers []party.ID, pl *pool.Pool) *ecdsa.PreSignature Generates a preprocessed ECDSA signature which does not depend on the message being signed.
cmp.PresignOnline(config *cmp.Config, preSignature *ecdsa.PreSignature, messageHash []byte, pl *pool.Pool) *ecdsa.Signature Combines each party's PreSignature share to create an ECDSA signature for messageHash.
doerner.Keygen(group curve.Curve, receiver bool, selfID, otherID party.ID, pl *pool.Pool) *doerner.Config Generates a new ECDSA private key shared among two participants
doerner.SignReceiver(config *ConfigReceiver, selfID, otherID party.ID, hash []byte, pl *pool.Pool) *ecdsa.Signature Generates a new ECDSA signature for a given message, using the Receiver's config
doerner.SignSender(config *ConfigSender, selfID, otherID party.ID, hash []byte, pl *pool.Pool) *ecdsa.Signature Generates a new ECDSA signature for a given message, using the Sender's config
frost.Keygen(group curve.Curve, selfID party.ID, participants []party.ID, threshold int) *frost.Config Generates a new Schnorr private key shared among all the given participants.
frost.KeygenTaproot(selfID party.ID, participants []party.ID, threshold int) *frost.TaprootConfig Generates a new Taproot compatible private key shared among all the given participants.
frost.Sign(config *frost.Config, signers []party.ID, messageHash []byte) *frost.Signature Generates a Schnorr signature for messageHash.
frost.SignTaproot(config *frost.TaprootConfig, signers []party.ID, messageHash []byte) *taproot.Signature Generates a Taproot compatibe Schnorr signature for messageHash.

In general, Keygen and Refresh protocols return a Config struct which contains a single key share, as well as the other participants' public key shares, and the full signing public key. The remaining arguments should be chosen as follows:

  • party.ID aliases a string and should uniquely identify each participant in the protocol.
  • curve.Curve represents the cryptogrpahic group over which the protocol is defined. Currently, the only option is curve.Secp256k1.
  • *pool.Pool can be used to paralelize certain operations during the protocol execution. This parameter may be nil, in which case the protocol will be run over a single thread. A new pool.Pool can be created with pl := pool.NewPool(numberOfThreads), and should be freed once the protocol has finished executing by calling pl.Teardown().
  • threshold defines the maximum number of participants which may be corrupted at any given time. Generating a signature therefore requires threshold+1 participants.
  • *ecdsa.PreSignature represents a preprocessed signature share which can be generated before the message to be signed is known. When the message does become available, the signature can be generated in a single round.

Each of the above protocols can be executed by creating a protocol.Handler object. For example, we can generate a new ECDSA key as follows:

var (
  // sessionID should be agreed upon beforehand, and must be unique among all protocol executions.
  // Alternatively, a counter may be used, which must be incremented after before every protocol start.
  sessionID []byte
  // group defines the cryptographic group over which
  group := curve.Secp256k1{}
  participants := []party.ID{"a", "b", "c", "d", "e"}
  selfID := participants[0] // we run the protocol as "a"
  threshold := 3 // 4 or more participants are required to generate a signature
)

pl := pool.NewPool(0) // use the maximum number of threads.
defer pl.Teardown() // destroy the pool once the protocol is done.

handler, err := protocol.NewMultiHandler(cmp.Keygen(group, selfID, participants, threshold, pl), sessionID)
if err != nil {
  // the handler was not able to start the protocol, most likely due to incorrect configuration.
}

More examples of how to create handlers for various protocols can be found in /example. Note that for two-party protocols like Doerner, a protocol.TwoPartyHandler should be created instead, to manage the back and forth messages required.

After the handler has been created, the user can start a loop for incoming/outgoing messages. Messages for other parties can be obtained by querying the channel returned by handler.Listen(). If the channel is closed, then the user can assume the protocol has finished.

func runProtocol(handler *protocol.Handler) {
  // Message handling loop
  for {
    select {

    // Message to be sent to other participants
    case msgOut, ok := <-handler.Listen():
      // a closed channel indicates that the protocol has finished executing
      if !ok {
        return
      }
      if msgOut.Broadcast {
        // ensure this message is reliably broadcast
      }
      for _, id := range participants {
        if msgOut.IsFor(id) {
          // send the message to `id`
        }
      }

    // Incoming message
    case msgIn := <- Receive():
      if !handler.CanAccept(msg) {
        // basic header validation failed, the message may be intended for a different protocol execution.
        continue
      }
      handler.Update(msgIn)
    }
  }
}

// runProtocol blocks until the protocol succeeds or aborts
runProtocol(handler)

// obtain the final result, or a possible error
result, err := handler.Result()
protocolError := protocol.Error{}
if errors.As(err, protocolError) {
  // get the list of culprits by calling protocolError.Culprits
}
// if the error is nil, then we can cast the result to the expected return type
config := result.(*cmp.Config)

If an error has occurred, it will be returned as a protocol.Error, which may contain information on the responsible participants, if possible.

When the protocol successfully completes, the result must be cast to the appropriate type.

Network

Most messages returned by the protocol can be transmitted through a point-to-point network guaranteeing authentication, integrity and confidentiality. The user is responsible for delivering the message to all participants for which Message.IsFor(recipient) returns true.

Some messages however require a reliable broadcast channel, which guarantees that all participants agree on which messages were sent. These messages will have their Message.Broadcast field set to true. The protocol.Handler performs an additional check due to Goldwasser & Lindell, which ensures that the protocol aborts when some participants incorrectly broadcast these types of messages. Unfortunately, identifying the culprits in this case requires external assumption which cannot be handled by this library.

Known Issues

Intellectual property

This code is copyright (c) Adrian Hamelink and Taurus SA, 2021, and under Apache 2.0 license.

On potential patents: the company that sponsored the development of the CMP protocol stated that it "will not be applying for patents on this technology."