Digital Signatures and Authentication
To prevent spamming, false identity and data tampering, Topos leverages digital signatures to ensure certificates are attributed to the right originators, i.e., the subnets that submit them to prove and ensure that integrity is retained during their propagation. As seen previously, signatures are included with certificates and hence can be validated prior to verifying the certificate validity using the public key of the associated subnet.
A basic digital signature allows an individual entity to sign a message. However, in blockchain environments, we tend to distribute trust among a group of participants rather than a single entity. While multi-signatures give the signing authority to a predefined group of entities, in threshold signatures any group of signers of sufficiently large cardinality are able to sign valid messages.
Authentication is achieved in the Topos ecosystem via our ICE-FROST Threshold Signature Scheme.
Threshold Signatures: ICE-FROST
To allow a non-unary and dynamic set of signers to sign certificates against a static public key, Topos makes use of ICE-FROST, an in-house customization of the FROST threshold signature scheme.
(t, n)-threshold signature scheme is a multi-party digital signature protocol such that any honest subset of
n signers with cardinality at least
t is able to successfully create a valid signature.
A desired property of threshold signature schemes is robustness in the sense that the protocol can tolerate cheating of a limited number of participants. A robust scheme will run successfully despite cheating participants, if the number of such is below the given limit. If this goal is guaranteed to be attained after at most a bounded number of re-runs of the protocol, we refer to the property as semi-robustness. Our customizations augment FROST with robustness in the distributed key generation phase. The robustness is achieved via the exact identification and exclusion of a cheating entity during the key generation. Identifying cheaters further can conclude in preventing cheating if suitable punishments are predicted. The protocol also has two additional important properties that are tailored for our Topos design, namely:
i) achieving semi-robustness during signing by appropriate choice of the set of the signers, besides taking advantage of the cheating identification property during key generation, and
ii) allowing a blockchain network to distribute a static long-running verification key with respect to which different sets of signers can produce signatures. This allows the verification key associated with each subnet to stay static while the set of signers can vary easily. This is a key feature of subnets, i.e., dynamic networks whose participating nodes arbitrarily join and leave.
ICE-FROST in Topos
ICE-FROST is used in Topos for signing certificates. The main purpose of signing is authenticating the subnet creating the certificate and verifying its integrity, i.e., ensuring that it was not altered while in transit. The number of signers required to generate a valid signature with ICE-FROST can be freely chosen by the subnet. A malicious party would then need to control more than the threshold to sign a certificate committing to an arbitrary state that honest signers disagree with, or to equivocate on two conflicting certificates.
In practice, we expect most subnets to run a BFT consensus mechanism, so we recommend a threshold greater than one third of the total number of validators.
A greater threshold value increases security at the cost of availability: if there isn't enough honest signers to reach the threshold, then the subnet might be unable to sign the certificate.
When a subnet registration takes place, the initial set of signers runs the initial DKG phase, as a result of which they obtain a static ICE-FROST verification key that is required to verify certificate signatures. This verification key is included in the subnet's registration certificate and remains static for the lifetime of the given subnet. Since the verification key is designed to be static, the redistribution of shares does not change the group signing and verification keys. Note that both the initial and redistribution phases are dealerless.
The generated signature has format identical to a regular Schnorr signature (even though it is generated by a group of signers instead of individual ones), hence can be verified by any entity capable of verifying Schnorr signatures. Therefore, checking the certificate signature before processing the certificate is very fast and effectively prevents spamming if an adversary sends multiple certificates with invalid signatures.
ICE-FROST Protocol Outline
In this section, we will provide an outline of ICE-FROST.
Schnorr Signature Algorithm
Schnorr signature algorithm is a digital signature algorithm. FROST and ICE-FROST are both based on Schnorr, hence we will briefly describe it here.
Schnorr signatures are constructed based on the Sigma protocol structure. Sigma protocols consist of three message transmissions between a prover and a verifier; i) the prover sends a commitment value to the verifier, ii) the verifier sends a uniformly random challenge to the prover, and iii) the prover answers to the challenge using some public function, and a witness. The prover is the signer in the Schnorr signature scheme and the witness is the secret key held by the signer that is kept secret using the discrete log hardness assumption. The signature scheme is made and used non-interactively using Fiat-Shamir transform that is using the output (digest) of a hash function with input of the commitment, witness and the message instead of the challenge value.
Distributed Key Generation (DKG): Initial Run
ICE-FROST distributed key generation protocol is based on the DKG algorithm of Pedersen, which is a distributed secret sharing scheme, constructed over Shamir's Secret Sharing. All participants of the DKG algorithm securely distribute their randomly chosen secrets among other participants. Since no participant is trusted prior to execution of the protocol, a verifiable secret sharing scheme is used that allows participants to verify if the received share is consistent with others. Verifiability is achieved by enforcing each participant to commit to its chosen secret (and to the corresponding polynomial that is used for secret sharing) and broadcasting the commitment values at the beginning of the protocol. After successful sharing of secrets, participants interpolate their received shares to compute their private signing share. The group's public verification key is calculated using the publicly broadcasted commitments.
To enable cheating identifiability in ICE-FROST, each participant chooses a pair of ephemeral public and private keys for each secret dealing and publishes the public key and proof of knowledge of the corresponding private key. In order to securely send shares to each participant, a Diffie-Hellman (DH) key agreement is run to establish a secret key between the sender and receiver of the given share. This key is used to securely encrypt the share that is sent out to the corresponding receiver. If a participant cheats by sending out an inconsistent share, the receiver will catch it using the initially published commitment. However, since shares are transmitted in the encrypted form, the receiver of the malformed share has to reveal the mutually established DH key, as well as proof of its correctness, to convince other participants that it has received a malformed share. If the receiver lies and accuses an honest participant of sending a malformed share, it will be caught itself after other participants check its complaint using the revealed DH key.
Participants' shares are updated by running the key update protocol which is a redistribution of secret shares to provide each shareholder with a fresh signing share while allowing new participants to join or the old ones to leave the protocol. Even if the set of participants stays the same, it is recommended to run the key update protocol every once in a while (e.g., every six hours) to maintain the security of distributed keys. To redistribute the secret key, each participant distributes its secret signing share using the described DKG. If required, the set of participants and the scheme's parameters (the threshold and the total number of participants) can be updated during each run of the key update protocol, while still preserving the static key.
As mentioned above, in a Schnorr signature scheme, the signer initially generates a commitment to a random nonce and sends it to the verifier. In a threshold Schnorr signature scheme, the nonce generation (as well as the private/public key generation) should be made distributed such that any set of at least
t participants can generate a valid nonce and corresponding commitment. The distributed nonce can be generated by running a separate round of DKG algorithm. However, in order to avoid adding an extra round to the protocol and achieve a round-optimized protocol, the nonce and its commitment can be generated during a preprocessing round. For this, each participant generates a list of single-use private nonce pairs and corresponding public commitment shares. Each entry of the list will be used for signing one message and once all are used, the preprocessing round will re-run.
A group of signers with at least
t members is randomly selected to generate the
(t, n)-threshold signature. However, the generation of a valid signature requires the cooperation of at least
t honest participants. If a participant cheats during signing and uses an unmatching signing key, it will be detected. At this point, the signing protocol will run from the beginning but exclude the cheating participant. As long as the initially chosen set of signers contains enough honest signers, the signing protocol will successfully generate a valid signature (semi-robustness property). To ensure semi-robustness or achieve it with high probability, a large enough set of signers (or even all of the participants) should be chosen, at the cost of more communication between participants and a heavier protocol.
After the random set of signers is selected, they will fetch each other's commitments that have been published and stored during the preprocessing round. Each participant checks the validity of the obtained values and calculates a binding value to the message and the group of signers. Then, each one of them derives another commitment value that binds the message, the set of signing participants, and each participant's commitment to each signature share. This latter commitment will be used to calculate the group's commitment value. The challenge value of Schnorr's signature will then be generated by applying a hash function on the group's commitment value, public verification key and message. Each participant responds to the challenge, using its committed nonces (from preprocessing) and their signing key share. Every participant then checks the validity of responses and, if they all passed, adds all the responses to generate the group's threshold signature. All honest participants will end up with the same valid signature. Note that if any of the checks during signing fails, the signing phase will have to be re-run from the beginning, excluding the set of discovered malicious signers.
Benefits of ICE-FROST over FROST
The main benefits of ICE-FROST over its predecessor FROST are:
- Robustness of the key generation phase, meaning that we are guaranteed to obtain a verification key and/or redistribute the shares, without aborting the protocol.
- Providing optional semi-robustness for the signing protocol. Each subnet can trade efficiency with the size of the set of signers for semi-robustness guarantee. The more signers means the heavier protocol but an increased guarantee of successfully generating a valid signature.
- Provable identifiability of cheating entities, who are either sending malformed shares or making false accusations.
- Redistribution feature of shares, which allows the group public key to be static, meaning that it could be used for as long as required by the group.
Future Work and Next Steps
ICE-FROST, as previously mentioned, has a robust distributed key generation phase. The next step is to make the signing phase robust as well. At the moment, it is semi-robust, due to the fact that it will need to be re-run if at least one of the signers is malicious. Given that the malicious participants are excluded in the next run and re-runs, the signature is still generated. Thus, a logical next step is to make signing run only once per certificate. This will most likely come at a cost. Thus, we see this next step as an additional option, rather than a replacement of the current one.
Notice that having both options available would not cause any interoperability issues, as the final signature in any case will be a Schnorr signature with respect to the given group public key and hence can still be verified by any entity with ability to verify Schnorr signatures.