Igloo: Smart contract implementation of Frost Key Gen ceremonies

Most on-chain implementations of multi-signature threshold signature schemes, such as that used by Gnosis Safe, generally follow the same pattern; a threshold number of validated signers must submit an ECDSA signature to the multisig contract. This implementation while simple and effective, has one major drawback, as the number of signers increase the size of the signature list increases and therefore the gas cost associated with the signature. This can be a major problems for several systems that regularly have to submit multisig data on chain, such as bridges that use a networks of validators to attests to events that have occurred on different chains at a high frequency or oracles that need to also have to attest to data at a high frequency.

The 2019 paper Frost: Flexible Round-Optimized Schnorr Threshold Signatures introduced a scheme that provides a method for threshold generation of signatures. The scheme is based on Schnorr signatures and allows for a threshold number of signers to produce a single schnorr signature that can be verified cheaply on chain. In essence this means that the amount of gas required to submit a signature is constant, no matter how many signers are involved. Unlike standard multi-signature contracts, whose gas usage is linearly dependent on the number of signers, threshold signature schemes like Frost have a constant gas cost no matter the number of signers. Notably, the specific subset of signers used to create an individual signature in Frost is also not determinable from the resultant signature, providing an avenue to privacy to signers who choose to participate in a signature (although this is not applicable in the case of Igloo).

Schnorr signatures are a type of Elliptic Curve signature that fortunately, due to a trick pointed out in this post from Vitalik, can be verified with essentially a single ECDSA verification operation they are relatively efficient to validate on chain.

An individual Schnorr signature is composed as follows.

To verify a schnorr signature, the verifier computes the challenge $c$ as above and then checks that:

Schnorr signatures can be computed in theory using any valid elyptic curve, however, the most common curve used in practice is the secp256k1 curve, which is the same curve used by Bitcoin and Ethereum. For the rest of this post, we will assume that the secp256k1 curve is being used.

During the Frost key generation ceremony, the secret $x$ is split among $n$ participants using Pedersen’s DKG which is based upon Shamir Secret Sharing, see here for details on Shamir Secret Shares. Each participant holds a secret value $x_i$ such that a valid signature can be produced by any $t$ participants, without any participant revealing their secret value. The resultant signature is a completely valid Schnorr Signature as explained above.

This all sounds great, threshold signatures with unlimited participants that can produce a signature that can be verified with a single ECDSA verification. However, Frost signatures do have one minor drawback, before messages can be signed, all valid signers must first perform a ceremony to generate partial secrets and the shared Public Key. The state generated in this ceremony must be available to signers whenever they want to sign a message. This makes the Frost ceremony ideal to do on-chain. Since it only has to be performed once, the gas cost of the ceremony is materialized over time, additionally by performing the ceremony on-chain, participants are guaranteed to have access to the ceremony state at all times by querying an on-chain contract. While performing the ceremony off-chain does have the disadvantage that the participants related to the resultant public key are made public, we gain the benefit of being able to use the chain as a means to sync and collaborate, a channel which is always accessible to all participants.

Igloo - A Frost Key Generation Ceremony Contract: Igloo is an implementation of a contract designed to host such a ceremony. Each contract deployment is designed to host a single ceremony, performing as many of the checks required in each round of the ceremony on-chain as possible with the goal of reducing client complexity. The final output of the ceremony allows each participant to derive their partial secret and the shared public key, which can then be used to sign messages using the Frost signing scheme.

This blog posts gives an overview of the design of the Igloo project, the code and more details can be found here https://github.com/max-wickham/Igloo.

Implementing Igloo

Each deployment of the Igloo contract is designed to host a single Frost ceremony. The contract is designed to be as simple as possible, with each round of the ceremony being implemented as a separate function. The contract also implements a number of checks to ensure that the ceremony is being performed correctly and that participants are following the protocol.

To perform all of the elyptic curve arithmatic that will be needed the crysol library is used, (credit to MerklePlant and the other authors). This library provides a set of functions for performing elliptic curve operations, such as point addition and scalar multiplication, all on the secp256k1 curve.

It is recommended to have some background understanding of eliptic curves and schnorr signatures before using Igloo. This post wont go into detail into the underlying maths used, there are plenty of existing resources that explain Frost signatures, instead we’ll discuss the basic design of the contract and how it implements the ceremony.

• ECC: https://cryptobook.nakov.com/asymmetric-key-ciphers/elliptic-curve-cryptography-ecc
• Schnorr Signatures: https://conduition.io/cryptography/schnorr/
• Frost: https://conduition.io/cryptography/frost-byok/

Contract Code

Contract State

The Igloo contract is initialized upon deployment with the following parameters:

• Participants: An array of addresses that are allowed to participate in the ceremony.
• Threshold: The threshold number of participants required to produce a signature.

For the rest of this post $n$ will be used to denote the number of participants and $t$ will be used to denote the threshold number of participants required to produce a signature.

At construction we also initialize a struct to store all of the state required during and after the ceremony. The ceremony itself is broken into three rounds, this means part of the state variable is used to maintain a record of the current round each participant is in. In order to keep a record of what participants have completed each round, we use an array of booleans used as a flag to mark if a participant has completed a specific round.

This boolean array actually presents an obvious gas optimization, as solidity uses a byte to represent a boolean, one storage slot can store 32 participant flags. In the future this may be updated to use a bit flag which would allow 256 participants per slot, but for now simplicity of implementation was prioritized. Additionally, it should also mention it may be possible to remove this flag entirely, as all the information needed to check if a participant has completed a round can be derived from the other state variables, but again for simplicity of implementation (and readability) this was not done.

/// @notice Session stores the state of a key generation ceremony.
struct Session {
    // -- Starting state --
    SessionState round;
    // -- Round 1 --
    Point[][] commitments; // (n x t) Commitments to polynomial coefficients.
    Sigma[] sigmas; // (n) Proof of knowledge of first coefficient.
    Point[] sessionChannelKeys; // (n) Public channel encryption keys `(A = aG)`, `a` is kept secret by participant.
    uint commitmentsCount; // Number of participants who have submitted commitments.
    bool[] commitmentsSubmitted; // (n) Marked true if a participant has completed this stage.
    // -- Round 2 --
    FunctionOutput[][] encryptedFunctionOutputs; // (n x n) Encrypted function outputs,
    // f_i(j) = decrypt(encryptedFunctionOutputs[i][j])
    uint functionOutputCount;
    bool[] functionOutputsSubmitted; // (n) Marked true if a participant has completed this stage.
    // -- Round 3 --
    uint validationCount;
    bool[] validatedFunctionOutputs; // (n) Marked true if a participant has validated the receiving function outputs
}

When querying what the current round the contract is in we can define two types of state, one at a global level and one at a participant level. For instance if the contract is currently in Round 1, the global state should be Round 1, but if an individual participant has completed this round, their state should be pending Round 2 until every participant has also completed Round 1. For this reason we define two separate enums, one for the global state and one for the participant state.

    /// @notice SessionState is used to track the round of the key generation ceremony.
    enum SessionState {
        ROUND_1,
        ROUND_2,
        ROUND_3,
        ACTIVE,
        DEPRECATED,
        FAILED
    }

    /// @notice ParticipantState is used to track the round state of a
    ///         participant in the key generation ceremony.
    enum ParticipantState {
        ROUND_1,
        PENDING_ROUND_2,
        ROUND_2,
        PENDING_ROUND_3,
        ROUND_3,
        PENDING_ACTIVE,
        ACTIVE
    }

We can then also define two view functions to read this state. The individual state of a single participant is dependent on the global state we can’t just maintain a record of the participant state. If we were to do this, when the final participant completed a round we would have to update every participant’s state, which would be gas inefficient. Instead we can derive the participant state from the global state and the flags that are maintained in the session struct.

/// @inheritdoc IIgloo
function state() public view returns (SessionState) {
    return _session.round;
}

/// @inheritdoc IIgloo
function state(uint participantIndex)
    public
    view
    returns (ParticipantState)
{
    SessionState round = _session.round;

    // If round one check if already submitted
    if (round == SessionState.ROUND_1) {
        if (_session.commitmentsSubmitted[participantIndex]) {
            return ParticipantState.PENDING_ROUND_2;
        }
        return ParticipantState.ROUND_1;
    }

    // If round 2 check if already submitted
    if (_session.round == SessionState.ROUND_2) {
        if (_session.functionOutputsSubmitted[participantIndex]) {
            return ParticipantState.PENDING_ROUND_3;
        }
        return ParticipantState.ROUND_2;
    }

    // If round 3 check if already submitted
    if (_session.round == SessionState.ROUND_3) {
        if (_session.validatedFunctionOutputs[participantIndex]) {
            return ParticipantState.PENDING_ACTIVE;
        }
        return ParticipantState.ROUND_3;
    }

    // Only other available option is ACTIVE.
    return ParticipantState.ACTIVE;
}

Authentication

Whenever a participant submits data to complete a specific contract round, we need to require that the participant is one of the participants defined at contract deployment. To optimize this we can define the idea of a participant index, which is the index of the participant in the participants array. This allows us to use a single index to authenticate a participant, rather than having to check the address against the participants array each time. (It should be noted here when perform the maths required for frost, participant indexes start at 1, however, the contract “participantIndex” starts at 0. For this reason when the clients perform some off-chain computations using participant indexes they must add 1 to this value).

To simplify adding participant level authentication to each function we define a modifier that checks the participant index submitted matches the msg.sender address.

    modifier checkParticipant(uint participantIndex) {
        if (_participants[participantIndex] != msg.sender) {
            revert InvalidParticipantIndex(
                participantIndex, _participants[participantIndex], msg.sender
            );
        }
        _;
    }

Since specific functions in the contract should only be called when the participant is in a specific state we can also define a similar modifier to check the participant state. This allows us to ensure that participants are only able to submit data when they are in the correct state for that round of the ceremony.

    modifier checkState(uint participantIndex, ParticipantState round) {
        ParticipantState actualRound = state(participantIndex);
        if (actualRound != round) {
            revert InvalidParticipantState(msg.sender, round, actualRound);
        }
        _;
    }

Round 1

At the beginning of the ceremony the Igloo contract is in Round 1. In this round each participant must secretly generate $t$ random values which will act as coefficients to a polynomial function. The participants must then submit a commitment to the polynomial coefficients they have generated to the contract, by generating the corresponding elliptic curve point for each coefficient.

In addition to the array of elliptic curve points the participants must as submit a proof of knowledge of the first coefficient and in the function below “Sigma” represents this proof. The contract itself verifies this proof of knowledge meaning other participants do not have to verify it themselves.

The final value that participants need to submit is an elliptic curve point that they know the corresponding scalar to. This will be explained later, but is used to provide a private communication channel between individual participants.

Round 1 Function:

The function upon receiving these values, updates its internal state then validates the proof of knowledge of the first coefficient. If the proof is valid, it updates the session state to reflect that this participant has completed Round 1. If all participants have completed Round 1, the session state is updated to Round 2 and the public key is computed from the commitments submitted by each participant. This again means the public key computation does not need to be performed by each participant, they can simply query the contract for the public key once it has been computed.

To prove knownledge of the first coefficient, the participant computes the following.

The contract validates this proof by checking that:

A public function participantChallenge is provided by the contract to calculate the challenge $c_i$ for a given commitment and random value $R$. This is used by the participants to compute the challenge when generating their proof of knowledge.

The following function is used by participants to submit their commitments, proof of knowledge and channel key.

/// @inheritdoc IIgloo
    function shareCommitments(
        uint participantIndex,
        Point[] calldata commitment,
        Sigma memory sigma,
        Point calldata channelKey
    )
        public
        checkParticipant(participantIndex)
        checkState(participantIndex, ParticipantState.ROUND_1)
    {
        // Number of commitments should equal threshold (t)
        require(commitment.length == threshold, "len(commitment) != threshold");

        // Store the commitment at the participant index.
        _session.commitments[participantIndex] = commitment;

        // Store the sigma value, used to prove knowledge of the scalar used
        // to generate commitment[0].
        _session.sigmas[participantIndex] = sigma;

        // Store the channel key used by other participants to encrypt their
        // functions computed on this participants index.
        _session.sessionChannelKeys[participantIndex] = channelKey;

        // Set commitments submitted to true, marking that this participant has completed
        // this step.
        _session.commitmentsSubmitted[participantIndex] = true;

        Point memory G = LibSecp256k1.G().intoPoint();

        // Verify the proof of knowledge of the first coefficient using sigma.
        // R + c_i * A_i_0 = mu * G

        // First find the challenge c_i
        uint challenge =
            participantChallenge(msg.sender, commitment[0], sigma.R);

        // Then require R + c_i * A_i_0 = mu * G
        require(
            sigma.R.toProjectivePoint().add(
                commitment[0].toProjectivePoint().mul(challenge)
            ).toPoint().eq(G.toProjectivePoint().mul(sigma.mu).toPoint()),
            "Sigma not verified"
        );

        emit SharedCommitment(msg.sender, commitment, sigma, channelKey);

        // Increase the commitment counter by 1 to keep track of how many
        // participants have completed this stage.
        _session.commitmentsCount += 1;

        // Check if this is the final participant to submit.
        if (_session.commitmentsCount == _participants.length) {
            // Set the session Round to ROUND_2.
            _session.round = SessionState.ROUND_2;

            // Compute the public key that will be the result of the ceremony.
            // Equal to the sum of all 0 index commitments.
            ProjectivePoint memory publicKeyProjectivePoint =
                PointsLib.ProjectiveIdentity();
            for (uint i; i < _participants.length; i++) {
                publicKeyProjectivePoint = publicKeyProjectivePoint.add(
                    _session.commitments[i][0].toProjectivePoint()
                );
            }

            Point memory publicKeyPoint = publicKeyProjectivePoint.toPoint();
            PublicKey memory key = LibSecp256k1.publicKeyFromFelts(
                publicKeyPoint.x, publicKeyPoint.y
            );
            _publicKey = key;

            emit CommitmentsShared(key);
        }
    }

Round 2

Once every participant has submitted their commitments, the contract moves to Round 2. In this round each participant must compute a function $f_i(j)$ using the coefficients they submitted in Round 1 for every value of j in range $[1,n]$. The function is defined as:

Where $a_{ik}$ is the $k$ th coefficient whose commitment was submitted by participant $i$ in Round 1.

Each function output needs to be shared with the corresponding participant $j$ privately, so that only participant $j$ can decrypt the function output. To do this each participant must encrypt their function output using the channel key they received from participant $j$ in Round 1.

The following method is performed by the participants to perform this encryption. This method is based on ElGamal Encryption, which by sharing a secret between the participants and then by adding this secret to the function output (mod the curve order) we can ensure that only the participant who has the corresponding channel secret key can decrypt the function output.

(Note, instead of modular addition the XOR operation could be used. This method would actually be equivalent, just using the $2^{256}-1$ instead of the curve order for the modulus).

/// @notice Function output stores the output of participant i's polynomial
///         evaluated at participant j's index.
///
/// @dev To Encrypt:
///        1. Generate random curve point M
///        2. Generate k such that 1 < k < q
///        3. C1 = k * G
///        4. C2 = M + k * A_j (A_j is the receivers channel key)
///        4. encryptedOutput = (M.x + output) % q
///
/// @dev To Decrypt:
///        1. M = C2 - a_jC1 (a_j is the receivers secret key such that A = aG)
///        2. output = (encryptedOutput - M.x)  % q (output should be the senders polynomial
///           evaluated on the receivers index (j))
struct FunctionOutput {
    uint eOutput;
    Point C1;
    Point C2;
}

It should be noted that the use of this method of encryption is not defined in the original Frost paper and is specific to the Igloo implementation. The encryption itself here is very simple, but this should be sufficient as we are only encryption a single (essentially random) number smaller than the order of the curve.

Round 2 Function:

The Round 2 function is simpler than that of Round 1 in that less checks are required and instead state is simply updated.

function shareFunctionOutputs(
    uint participantIndex,
    FunctionOutput[] calldata encryptedFunctionOutputs
)
    public
    checkParticipant(participantIndex)
    checkState(participantIndex, ParticipantState.ROUND_2)
{
    // Ensure the number of function outputs is equal to the number of participants.
    require(
        encryptedFunctionOutputs.length == _participants.length,
        "len(outputs) != len(participants)"
    );

    // Mark that this participant has completed this stage.
    _session.functionOutputsSubmitted[participantIndex] = true;

    // Store the function outputs.
    _session.encryptedFunctionOutputs[participantIndex] =
        encryptedFunctionOutputs;

    // Increase the function output counter to keep track of how many participants have
    // completed this stage.
    _session.functionOutputCount += 1;

    emit SharedFunctionOutputs(msg.sender, encryptedFunctionOutputs);

    // If all participants have completed this stage increase the session state
    // to ROUND_3.
    if (_session.functionOutputCount == _participants.length) {
        _session.round = SessionState.ROUND_3;

        emit FunctionOutputsShared();
    }
}

Round 3

Once every participant has completed Round 2, the contract moves to Round 3. In this round each participant must validate the function outputs they received from other participants in Round 2 off chain. This is done by decrypting the function output using their secret key and checking that the output matches the expected value according to the following formula:this

If this equation holds for every participant index then the participant should submit the Round 3 function.

/// @inheritdoc IIgloo
function validateFunctionOutputs(uint participantIndex)
    public
    checkParticipant(participantIndex)
    checkState(participantIndex, ParticipantState.ROUND_3)
{
    // Mark that this participant has completed this stage.
    _session.validatedFunctionOutputs[participantIndex] = true;

    // Increase the validation count to keep track of how many participants
    // have completed this stage.
    _session.validationCount += 1;

    emit ValidatedFunctionOutputs(msg.sender);

    // If all participants have completed this stage then mark the final key as active.
    if (_session.validationCount == _participants.length) {
        _session.round = SessionState.ACTIVE;
        emit FunctionOutputsValidated();
    }
}

Completing the Ceremony

Once every participant has completed Round 3, the ceremony is complete and the contract state is set to ACTIVE. At this point the public key can be used to sign messages using the Schnorr signature scheme, with a threshold number of participants required to produce a valid signature.

The participants can each compute their partial secrets using the state generated throughout the ceremony that can be queried from the contract. The details of how to compute the partial secret are left out of scope for this post, but can be found in the project repo or in the Frost paper.

Ceremony Deprecation and Failure

If at any point during the ceremony a participant detects that the ceremony is not being performed correctly, they can fail the ceremony by calling the failKeyGeneration function. This will set the session state to FAILED and prevent any further actions from being taken on the contract.

If the ceremony has already completed and the public key is active, participants can deprecate the key by calling the deprecateKey function. This will set the session state to DEPRECATED and prevent any further actions from being taken on the contract.

Whenever participants use the key created through this ceremony they should check the session state to ensure that the key is still active and has not been deprecated or failed.

Contract Deployment

Due to the large code size of deploying the Igloo contract a proxy pattern is used to save on deployment gas costs. A solidity script is provided in the project repo to deploy the contract using a proxy factory, this requires that the proxy factory and the implementation contract are deployed already on the respective chain.

Example Client

In addition to the Igloo contract itself, an example client can also be found in the project repo. This client was implemented in Rust as is designed to demonstrate how all the required off-chain steps must be performed to complete the ceremony. It should be noted, just like the contract itself, the client is in no way production ready and is only intended to be used as an example.

The client when run is provided the address of the Igloo contract and an RPC URL. The client then continuously poles at some interval the relevant participant state, and if required performs the next round. If the key is currently active the client will exit. Utility commands are also provided to check the state of the contract and to deprecate the key.

One interesting design note from the client is the deterministic generation of secret values. During the ceremony the participants must keep track of some private variables, such as the function coefficients and the channel keys. If these variables were randomly generated the client would have to store them permanently somewhere, which kind of negates the entire point of this contract, as the client cannot derive its partial secret simply from querying the contract state. To get around this the client deterministically generates these values using its private key and different hash functions. The hash functions all include the contract address and chainId and it is hoped this information is sufficient to prevent replay attacks. However, some more thought needs to be put into this to ensure this deterministic method does’t open up some new attack vectors.

Final Notes

As has already been discussed the Igloo contract is designed to perform as much of the Frost Key generation ceremony on chain as is possible. The only check that can’t really be performed on chain is the validation of the function outputs in Round 3. Some time was spent thinking about how this could be done on chain but no simple method was found. This could in theory be done with a ZK proof, but with would require a lot of gas and would be quite complex to implement.

An important side effect of performing the checks on chain is that if participants are to rely on the contract to perform the checks, they should run their own node to ensure that the contract is being executed correctly. (If a participant really does not want to do this, their client implementation must perform the checks off chain to ensure security).

Moving forward a new version of Igloo may be released with more gas optimizations and a fully completed testing suite but for now the project remains, while functional, still in a very early stage.

In the future such a contract could be integrated into a more complex authentication system. For instance, a smart contract could maintain the address of the current active ceremony contract for a group of participants, and then when queried by down stream contracts provide the corresponding Schnorr Public Key. Down stream contracts could then receive the Frost generated Schnorr signature created by the participants and validate this against the public key maintained by the ceremony contract.