FROST signing for BIP340-compatible Threshold Signatures (BIP draft)

Abstract

This document proposes a standard for the Flexible Round-Optimized Schnorr Threshold (FROST) signing protocol. The standard is compatible with BIP340 public keys and signatures. It supports tweaking, which allows deriving BIP32 child keys from the group public key and creating BIP341 Taproot outputs with key and script paths.

Copyright

This document is licensed under the 3-clause BSD license.

Introduction

This document proposes the FROST signing protocol based on the FROST3 variant (see section 2.3) introduced in ROAST[RRJSS22], instead of the original FROST[KG20]. Key generation for FROST signing is out of scope for this document. However, we specify the requirements that a key generation method must satisfy to be compatible with this signing protocol.

Many sections of this document have been directly copied or modified from BIP327 due to the similarities between the FROST3 and MuSig2 signature schemes.

Motivation

The FROST signature scheme [KG20,CKM21,BTZ21,CGRS23] enables t-of-n Schnorr threshold signatures, in which a threshold t of some set of n signers is required to produce a signature. FROST remains unforgeable as long as at most t-1 signers are compromised, and remains functional as long as t honest signers do not lose their secret key material. It supports any choice of t as long as 1 ≤ t ≤ n.¹

The primary motivation is to create a standard that allows users of different software projects to jointly control Taproot outputs (BIP341). Such an output contains a public key which, in this case, would be the group public key derived from the public shares of threshold signers. It can be spent using FROST to produce a signature for the key-based spending path.

The on-chain footprint of a FROST Taproot output is essentially a single BIP340 public key, and a transaction spending the output only requires a single signature cooperatively produced by threshold signers. This is more compact and has lower verification cost than signers providing n individual public keys and t signatures, as would be required by an t-of-n policy implemented using OP_CHECKSIGADD as introduced in (BIP342). As a side effect, the numbers t and n of signers are not limited by any consensus rules when using FROST.

Moreover, FROST offers a higher level of privacy than OP_CHECKSIGADD: FROST Taproot outputs are indistinguishable for a blockchain observer from regular, single-signer Taproot outputs even though they are actually controlled by multiple signers. By tweaking a group public key, the shared Taproot output can have script spending paths that are hidden unless used.

There are threshold-signature schemes other than FROST that are fully compatible with Schnorr signatures. The FROST variant proposed below stands out by combining all the following features:

• Two Communication Rounds: FROST is faster in practice than other threshold-signature schemes [GJKR03] which requires at least three rounds, particularly when signers are connected through high-latency anonymous links. Moreover, the need for fewer communication rounds simplifies the algorithms and reduces the probability that implementations and users make security-relevant mistakes.
• Efficiency over Robustness: FROST trades off the robustness property for network efficiency (fewer communication rounds), requiring the protocol to be aborted in the case of any misbehaving participant.
• Provable security: FROST3 with an idealized key generation (i.e., trusted setup) has been proven existentially unforgeable under the one-more discrete logarithm (OMDL) assumption (instead of the discrete logarithm assumption required for single-signer Schnorr signatures) in the random oracle model (ROM).

Design

• Compatibility with BIP340: The group public key and participant public shares produced by a compatible key generation algorithm MUST be plain public keys in compressed format. In this proposal, the signature output at the end of the signing protocol is a BIP340 signature, which passes BIP340 verification for the BIP340 X-only version of the group public key and a message.
• Tweaking for BIP32 derivations and Taproot: This proposal supports tweaking group public key and signing for this tweaked group public key. We distinguish two modes of tweaking: Plain tweaking can be used to derive child group public keys per BIP32.X-only tweaking, on the other hand, allows creating a BIP341 tweak to add script paths to a Taproot output. See tweaking the group public key below for details.
• Non-interactive signing with preprocessing: The first communication round, exchanging the nonces, can happen before the message or the exact set of signers is determined. Once the parameters of the signing session are finalized, the signers can send partial signatures without additional interaction.
• Partial signature independent of order: The output of the signing algorithm remains consistent regardless of the order in which participant identifiers and public shares are used during the session context initialization. This property is inherent when combining Shamir shares to derive any value.
• Third-party nonce and partial signature aggregation: Instead of every signer sending their nonce and partial signature to every other signer, it is possible to use an untrusted third-party aggregator in order to reduce the communication complexity from quadratic to linear in the number of signers. In each of the two rounds, the aggregator collects all signers' contributions (nonces or partial signatures), aggregates them, and broadcasts the aggregate back to the signers. A malicious aggregator can force the signing session to fail to produce a valid Schnorr signature but cannot negatively affect the unforgeability of the scheme.
• Partial signature verification: If any signer sends a partial signature contribution that was not created by honestly following the signing protocol, the signing session will fail to produce a valid Schnorr signature. This proposal specifies a partial signature verification algorithm to identify disruptive signers. It is incompatible with third-party nonce aggregation because the individual nonce is required for partial verification.
• Size of the nonce: In the FROST3 variant, each signer's nonce consists of two elliptic curve points.

Overview

Implementers must make sure to understand this section thoroughly to avoid subtle mistakes that may lead to catastrophic failure.

Optionality of Features

The goal of this proposal is to support a wide range of possible application scenarios. Given a specific application scenario, some features may be unnecessary or not desirable, and implementers can choose not to support them. Such optional features include:

• Applying plain tweaks after x-only tweaks.
• Applying tweaks at all.
• Dealing with messages that are not exactly 32 bytes.
• Identifying a disruptive signer after aborting (aborting itself remains mandatory). If applicable, the corresponding algorithms should simply fail when encountering inputs unsupported by a particular implementation. (For example, the signing algorithm may fail when given a message which is not 32 bytes.) Similarly, the test vectors that exercise the unimplemented features should be re-interpreted to expect an error, or be skipped if appropriate.

Key Generation

We distinguish between two public key types, namely plain public keys, the key type traditionally used in Bitcoin, and X-only public keys. Plain public keys are byte strings of length 33 (often called compressed format). In contrast, X-only public keys are 32-byte strings defined in BIP340.

FROST generates signatures that are verifiable as if produced by a single signer using a secret key s with the corresponding public key. As a threshold signing protocol, the group secret key s is shared among all MAX_PARTICIPANTS participants using Shamir's secret sharing, and at least MIN_PARTICIPANTS participants must collaborate to issue a valid signature.
  MIN_PARTICIPANTS is a positive non-zero integer lesser than or equal to MAX_PARTICIPANTS
  MAX_PARTICIPANTS MUST be a positive integer lesser than the secp256k1 curve order.

In particular, FROST signing assumes each participant is configured with the following information:

• An identifier id, which is a positive non-zero integer in the range [1, MAX_PARTICIPANTS] and MUST be distinct from the identifier of every other participant.
• A secret share secshare_id, which is a positive non-zero integer lesser than the secp256k1 curve order. This value represents the i-th Shamir secret share of the group secret key s. In particular, secshare_id is the value f(id) on a secret polynomial f of degree (MIN_PARTICIPANTS - 1), where s is f(0).
• A Group public key group_pk, which is point on the secp256k1 curve.
• A public share pubshare_id, which is point on the secp256k1 curve.

Note

The definitions for the secp256k1 curve and its order can be found in the Notation section.

As key generation for FROST signing is beyond the scope of this document, we do not specify how this information is configured and distributed to the participants. Generally, there are two possible key generation mechanisms: one involves a single, trusted dealer (see Appendix D of FROST RFC draft), and the other requires performing a distributed key generation protocol (see BIP FROST DKG draft).

For a key generation mechanism to be compatible with FROST signing, the participant information it generates MUST successfully pass both the ValidateGroupPubkey and ValidatePubshares functions (see Key Generation Compatibility).

Important

It should be noted that while passing these functions ensures functional compatibility, it does not guarantee the security of the key generation mechanism.

General Signing Flow

FROST signing is designed to be executed by a predetermined number of signer participants, referred to as NUM_PARTICIPANTS. This value is a positive non-zero integer that MUST be at least MIN_PARTICIPANTS and MUST NOT exceed MAX_PARTICIPANTS. Therefore, the selection of signing participants from the participant group must be performed outside the signing protocol, prior to its initiation.

Whenever the signing participants want to sign a message, the basic order of operations to create a threshold-signature is as follows:

First broadcast round: The signers start the signing session by running NonceGen to compute secnonce and pubnonce.² Then, the signers broadcast their pubnonce to each other and run NonceAgg to compute an aggregate nonce.

Second broadcast round: At this point, every signer has the required data to sign, which, in the algorithms specified below, is stored in a data structure called Session Context. Every signer computes a partial signature by running Sign with the participant identifier, the secret share, the secnonce and the session context. Then, the signers broadcast their partial signatures to each other and run PartialSigAgg to obtain the final signature. If all signers behaved honestly, the result passes BIP340 verification.

Both broadcast rounds can be optimized by using an aggregator who collects all signers' nonces or partial signatures, aggregates them using NonceAgg or PartialSigAgg, respectively, and broadcasts the aggregate result back to the signers. A malicious aggregator can force the signing session to fail to produce a valid Schnorr signature but cannot negatively affect the unforgeability of the scheme, i.e., even a malicious aggregator colluding with all but one signer cannot forge a signature.

Important

The Sign algorithm must not be executed twice with the same secnonce. Otherwise, it is possible to extract the secret signing key from the two partial signatures output by the two executions of Sign. To avoid accidental reuse of secnonce, an implementation may securely erase the secnonce argument by overwriting it with 64 zero bytes after it has been read by Sign. A secnonce consisting of only zero bytes is invalid for Sign and will cause it to fail.

To simplify the specification of the algorithms, some intermediary values are unnecessarily recomputed from scratch, e.g., when executing GetSessionValues multiple times. Actual implementations can cache these values. As a result, the Session Context may look very different in implementations or may not exist at all. However, computation of GetSessionValues and storage of the result must be protected against modification from an untrusted third party. This party would have complete control over the aggregate public key and message to be signed.

Nonce Generation

Important

NonceGen must have access to a high-quality random generator to draw an unbiased, uniformly random value rand'. In contrast to BIP340 signing, the values k₁ and k₂ must not be derived deterministically from the session parameters because deriving nonces deterministically allows for a complete key-recovery attack in multi-party discrete logarithm-based signatures.

The optional arguments to NonceGen enable a defense-in-depth mechanism that may prevent secret share exposure if rand' is accidentally not drawn uniformly at random. If the value rand' was identical in two NonceGen invocations, but any other argument was different, the secnonce would still be guaranteed to be different as well (with overwhelming probability), and thus accidentally using the same secnonce for Sign in both sessions would be avoided. Therefore, it is recommended to provide the optional arguments secshare, pubshare, group_pk, and m if these session parameters are already determined during nonce generation. The auxiliary input extra_in can contain additional contextual data that has a chance of changing between NonceGen runs, e.g., a supposedly unique session id (taken from the application), a session counter wide enough not to repeat in practice, any nonces by other signers (if already known), or the serialization of a data structure containing multiple of the above. However, the protection provided by the optional arguments should only be viewed as a last resort. In most conceivable scenarios, the assumption that the arguments are different between two executions of NonceGen is relatively strong, particularly when facing an active adversary.

In some applications, it is beneficial to generate and send a pubnonce before the other signers, their pubshare, or the message to sign is known. In this case, only the available arguments are provided to the NonceGen algorithm. After this preprocessing phase, the Sign algorithm can be run immediately when the message and set of signers is determined. This way, the final signature is created quicker and with fewer round trips. However, applications that use this method presumably store the nonces for a longer time and must therefore be even more careful not to reuse them. Moreover, this method is not compatible with the defense-in-depth mechanism described in the previous paragraph.

Instead of every signer broadcasting their pubnonce to every other signer, the signers can send their pubnonce to a single aggregator node that runs NonceAgg and sends the aggnonce back to the signers. This technique reduces the overall communication. A malicious aggregator can force the signing session to fail to produce a valid Schnorr signature but cannot negatively affect the unforgeability of the scheme.

In general, FROST signers are stateful in the sense that they first generate secnonce and then need to store it until they receive the other signers' pubnonces or the aggnonce. However, it is possible for one of the signers to be stateless. This signer waits until it receives the pubnonce of all the other signers and until session parameters such as a message to sign, participant identifiers, participant public shares, and tweaks are determined. Then, the signer can run NonceGen, NonceAgg and Sign in sequence and send out its pubnonce along with its partial signature. Stateless signers may want to consider signing deterministically (see Modifications to Nonce Generation) to remove the reliance on the random number generator in the NonceGen algorithm.

Identifying Disruptive Signers

The signing protocol makes it possible to identify malicious signers who send invalid contributions to a signing session in order to make the signing session abort and prevent the honest signers from obtaining a valid signature. This property is called "identifiable aborts" and ensures that honest parties can assign blame to malicious signers who cause an abort in the signing protocol.

Aborts are identifiable for an honest party if the following conditions hold in a signing session:

• The contributions received from all signers have not been tampered with (e.g., because they were sent over authenticated connections).
• Nonce aggregation is performed honestly (e.g., because the honest signer performs nonce aggregation on its own or because the aggregator is trusted).
• The partial signatures received from all signers are verified using the algorithm PartialSigVerify.

If these conditions hold and an honest party (signer or aggregator) runs an algorithm that fails due to invalid protocol contributions from malicious signers, then the algorithm run by the honest party will output the participant identifier of exactly one malicious signer. Additionally, if the honest parties agree on the contributions sent by all signers in the signing session, all the honest parties who run the aborting algorithm will identify the same malicious signer.

Further Remarks

Some of the algorithms specified below may also assign blame to a malicious aggregator. While this is possible for some particular misbehavior of the aggregator, it is not guaranteed that a malicious aggregator can be identified. More specifically, a malicious aggregator (whose existence violates the second condition above) can always make signing abort and wrongly hold honest signers accountable for the abort (e.g., by claiming to have received an invalid contribution from a particular honest signer).

The only purpose of the algorithm PartialSigVerify is to ensure identifiable aborts, and it is not necessary to use it when identifiable aborts are not desired. In particular, partial signatures are not signatures. An adversary can forge a partial signature, i.e., create a partial signature without knowing the secret share for that particular participant public share.³ However, if PartialSigVerify succeeds for all partial signatures then PartialSigAgg will return a valid Schnorr signature.

Tweaking the Group Public Key

The group public key can be tweaked, which modifies the key as defined in the Tweaking Definition subsection. In order to apply a tweak, the Tweak Context output by TweakCtxInit is provided to the ApplyTweak algorithm with the is_xonly_t argument set to false for plain tweaking and true for X-only tweaking. The resulting Tweak Context can be used to apply another tweak with ApplyTweak or obtain the group public key with GetXonlyPubkey or GetPlainPubkey.

The purpose of supporting tweaking is to ensure compatibility with existing uses of tweaking, i.e., that the result of signing is a valid signature for the tweaked public key. The FROST signing algorithms take arbitrary tweaks as input but accepting arbitrary tweaks may negatively affect the security of the scheme.⁴ Instead, signers should obtain the tweaks according to other specifications. This typically involves deriving the tweaks from a hash of the aggregate public key and some other information. Depending on the specific scheme that is used for tweaking, either the plain or the X-only aggregate public key is required. For example, to do BIP32 derivation, you call GetPlainPubkey to be able to compute the tweak, whereas BIP341 TapTweaks require X-only public keys that are obtained with GetXonlyPubkey.

The tweak mode provided to ApplyTweak depends on the application: Plain tweaking can be used to derive child public keys from an aggregate public key using BIP32. On the other hand, X-only tweaking is required for Taproot tweaking per BIP341. A Taproot-tweaked public key commits to a script path, allowing users to create transaction outputs that are spendable either with a FROST threshold-signature or by providing inputs that satisfy the script path. Script path spends require a control block that contains a parity bit for the tweaked X-only public key. The bit can be obtained with GetPlainPubkey(tweak_ctx)[0] & 1.

Algorithms

The following specification of the algorithms has been written with a focus on clarity. As a result, the specified algorithms are not always optimal in terms of computation and space. In particular, some values are recomputed but can be cached in actual implementations (see General Signing Flow).

Notation

The following conventions are used, with constants as defined for secp256k1. We note that adapting this proposal to other elliptic curves is not straightforward and can result in an insecure scheme.

• Lowercase variables represent integers or byte arrays.
  • The constant p refers to the field size, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F.
  • The constant n refers to the curve order, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141.
  • The constant num_participants refers to number of participants involved in the signing process, must be at least min_participants but must not be larger than max_participants.
• Uppercase variables refer to points on the curve with equation y² = x³ + 7 over the integers modulo p.
  • is_infinite(P) returns whether P is the point at infinity.
  • x(P) and y(P) are integers in the range 0..p-1 and refer to the X and Y coordinates of a point P (assuming it is not infinity).
  • The constant G refers to the base point, for which x(G) = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 and y(G) = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8.
  • Addition of points refers to the usual elliptic curve group operation.
  • Multiplication (⋅) of an integer and a point refers to the repeated application of the group operation.
• Functions and operations:
  • || refers to byte array concatenation.
  • The function x[i:j], where x is a byte array and i, j ≥ 0, returns a (j - i)-byte array with a copy of the _i_th byte (inclusive) to the _j_th byte (exclusive) of x.
  • The function bytes(n, x), where x is an integer, returns the n-byte encoding of x, most significant byte first.
  • The constant empty_bytestring refers to the empty byte array. It holds that len(empty_bytestring) = 0.
  • The function xbytes(P), where P is a point for which not is_infinite(P), returns bytes(32, x(P)).
  • The function len(x) where x is a byte array returns the length of the array.
  • The function has_even_y(P), where P is a point for which not is_infinite(P), returns y(P) mod 2 == 0.
  • The function with_even_y(P), where P is a point, returns P if is_infinite(P) or has_even_y(P). Otherwise, with_even_y(P) returns -P.
  • The function cbytes(P), where P is a point for which not is_infinite(P), returns a || xbytes(P) where a is a byte that is 2 if has_even_y(P) and 3 otherwise.
  • The function cbytes_ext(P), where P is a point, returns bytes(33, 0) if is_infinite(P). Otherwise, it returns cbytes(P).
  • The function int(x), where x is a 32-byte array, returns the 256-bit unsigned integer whose most significant byte first encoding is x.
  • The function lift_x(x), where x is an integer in range 0..2²⁵⁶-1, returns the point P for which x(P) = x⁵ and has_even_y(P), or fails if x is greater than p-1 or no such point exists. The function lift_x(x) is equivalent to the following pseudocode:
    • Fail if x > p-1.
    • Let c = x³ + 7 mod p.
    • Let y' = c^(p+1)/4 mod p.
    • Fail if c ≠ y'² mod p.
    • Let y = y' if y' mod 2 = 0, otherwise let y = p - y' .
    • Return the unique point P such that x(P) = x and y(P) = y.
  • The function cpoint(x), where x is a 33-byte array (compressed serialization), sets P = lift_x(int(x[1:33])) and fails if that fails. If x[0] = 2 it returns P and if x[0] = 3 it returns -P. Otherwise, it fails.
  • The function cpoint_ext(x), where x is a 33-byte array (compressed serialization), returns the point at infinity if x = bytes(33, 0). Otherwise, it returns cpoint(x) and fails if that fails.
  • The function hash_tag(x) where tag is a UTF-8 encoded tag name and x is a byte array returns the 32-byte hash SHA256(SHA256(tag) || SHA256(tag) || x).
  • The function count(lst, x), where lst is a list of integers containing x, returns the number of times x appears in lst.
  • The function has_unique_elements(lst), where lst is a list of integers, returns True if count(lst, x) returns 1 for all x in lst. Otherwise returns False. The function has_unique_elements(lst) is equivalent to the following pseudocode:
    • For x in lst:
      • if count(lst, x) > 1:
        • Return False
    • Return True
  • The function integer_ids(lst), where lst is a list of 32-byte array, returns a list of integers. The function integer_ids(lst) is equivalent to the following pseudocode:
    • res = []
    • For x in lst:
      • Fail if int(x) ≥ n or int(x) < 1
      • res.append(int(x))
    • Return res
  • The function concat_bytearrays(lst), where lst is a list of byte array elements, returns a single byte array. The function concat_bytearrays(lst) is equivalent to the following pseudocode:
    • res = empty_bytestring
    • For x in lst:
      • res = res || x
    • Return res
  • The function sorted(lst), where lst is a list of byte array elements, returns a list of byte array sorted based on the numerical values of its elements in ascending order, preserving the relative order of equal elements.
• Other:
  • Tuples are written by listing the elements within parentheses and separated by commas. For example, (2, 3, 1) is a tuple.

Key Generation Compatibility

Internal Algorithm PlainPubkeyGen(sk):⁶

• Input:
  • The secret key sk: a 32-byte array, freshly generated uniformly at random
• Let d' = int(sk).
• Fail if d' = 0 or d' ≥ n.
• Return cbytes(d'⋅G).

Algorithm ValidatePubshares(secshare_1..u, pubshare_1..u)

• Inputs:
  • The number u of participants involved in keygen: an integer equal to max_participants
  • The participant secret shares secshare_1..u: u 32-byte arrays
  • The corresponding public shares pubshare_1..u: u 33-byte arrays
• For i = 1 .. u:
  • Fail if PlainPubkeyGen(secshare_i) ≠ pubshare_i
• Return success iff no failure occurred before reaching this point.

Algorithm ValidateGroupPubkey(threshold, group_pk, id_1..u, pubshare_1..u):

• Inputs:
  • The number u of participants involved in keygen: an integer equal to max_participants
  • The number threshold of participants required to issue a signature: an integer equal to min_participants
  • The group public key group_pk: a 33-byte array
  • The participant identifiers id_1..u: u 32-byte arrays
  • The participant public shares pubshares_1..u: u 33-byte arrays
• Fail if threshold > u
• int_id_1..u = integer_ids(id_1..u); Fail if that fails
• For t = threshold..u:
  • For each combination of t elements from int_id_1..u:⁷
    • Let signer_id_1..t be the current combination of participant identifiers
    • Let signer_pubshare_1..t be their corresponding participant pubshares⁸
    • expected_pk = DeriveGroupPubkey(signer_id_1..t, signer_pubshare_1..t)
    • Fail if group_pk ≠ expected_pk
• Return success iff no failure occurred before reaching this point.

Key Derivation and Tweaking

Tweak Context

The Tweak Context is a data structure consisting of the following elements:

• The point Q representing the potentially tweaked group public key: an elliptic curve point
• The accumulated tweak tacc: an integer with 0 ≤ tacc < n
• The value gacc: 1 or -1 mod n

We write "Let (Q, gacc, tacc) = tweak_ctx" to assign names to the elements of a Tweak Context.

Algorithm TweakCtxInit(id_1..u, pubshare_1..u):

• Input:
  • The number u of participants available in the signing session with min_participants ≤ u ≤ max_participants
  • The participant identifiers of the signers _id_1..u: u 32-byte arrays with 1 ≤ int(id_i) ≤ max_participants < n
  • The individual public shares pubshare_1..u: u 33-byte arrays
• Let group_pk = DeriveGroupPubkey(id_1..u, pubshare_1..u); fail if that fails
• Let Q = cpoint(group_pk)
• Fail if is_infinite(Q).
• Let gacc = 1
• Let tacc = 0
• Return tweak_ctx = (Q, gacc, tacc).

Algorithm DeriveGroupPubkey(id_1..u, pubshare_1..u)

• inf_point = bytes(33, 0)
• Q = cpoint_ext(inf_point)
• For i = 1..u:
  • P = cpoint(pubshare_i); fail if that fails
  • lambda = DeriveInterpolatingValue(id_1..u, id_i)
  • Q = Q + lambda⋅P
• Return cbytes(Q)

Internal Algorithm DeriveInterpolatingValue(id_1..u, my_id):

• Fail if my_id not in id_1..u
• Fail if not _has_unique_elements(id_1..u)
• int_id_1..u = integer_ids(id_1..u); Fail if that fails
• Return DeriveInterpolatingValueInternal(int_id_1..u, int(my_id))

Internal Algorithm DeriveInterpolatingValueInternal(id_1..u, my_id):

• Let num = 1
• Let denom = 1
• For i = 1..u:
  • If id_i ≠ my_id:
    • Let num = num⋅id_i
    • Let denom = denom⋅(id_i - my_id)
• lambda = num⋅denom^-1 mod n
• Return lambda

Algorithm GetXonlyPubkey(tweak_ctx):

• Let _(Q, _, ) = tweak_ctx
• Return xbytes(Q)

Algorithm GetPlainPubkey(tweak_ctx):

• Let _(Q, _, ) = tweak_ctx
• Return cbytes(Q)

Applying Tweaks

Algorithm ApplyTweak(tweak_ctx, tweak, is_xonly_t):

• Inputs:
  • The tweak_ctx: a Tweak Context data structure
  • The tweak: a 32-byte array
  • The tweak mode is_xonly_t: a boolean
• Let (Q, gacc, tacc) = tweak_ctx
• If is_xonly_t and not has_even_y(Q):
  • Let g = -1 mod n
• Else:
  • Let g = 1
• Let t = int(tweak); fail if t ≥ n
• Let Q' = g⋅Q + t⋅G
  • Fail if is_infinite(Q')
• Let gacc' = g⋅gacc mod n
• Let tacc' = t + g⋅tacc mod n
• Return tweak_ctx' = (Q', gacc', tacc')

Nonce Generation

Algorithm NonceGen(secshare, pubshare, group_pk, m, extra_in):

• Inputs:
  • The participant’s secret share secshare: a 32-byte array (optional argument)
  • The corresponding public share pubshare: a 33-byte array (optional argument)
  • The x-only group public key group_pk: a 32-byte array (optional argument)
  • The message m: a byte array (optional argument)⁹
  • The auxiliary input extra_in: a byte array with 0 ≤ len(extra_in) ≤ 2³²-1 (optional argument)
• Let rand' be a 32-byte array freshly drawn uniformly at random
• If the optional argument secshare is present:
  • Let rand be the byte-wise xor of secshare and hash_FROST/aux(rand')¹⁰
• Else:
  • Let rand = rand'
• If the optional argument pubshare is not present:
  • Let pubshare = empty_bytestring
• If the optional argument group_pk is not present:
  • Let group_pk = empty_bytestring
• If the optional argument m is not present:
  • Let m_prefixed = bytes(1, 0)
• Else:
  • Let m_prefixed = bytes(1, 1) || bytes(8, len(m)) || m
• If the optional argument extra_in is not present:
  • Let extra_in = empty_bytestring
• Let k_i = int(hash_FROST/nonce(rand || bytes(1, len(pubshare)) || pubshare || bytes(1, len(group_pk)) || group_pk || m_prefixed || bytes(4, len(extra_in)) || extra_in || bytes(1, i - 1))) mod n for i = 1,2
• Fail if k₁ = 0 or k₂ = 0
• Let R_⁎,1 = k₁⋅G, R_⁎,2 = k₂⋅G
• Let pubnonce = cbytes(R_,1) || cbytes(R_⁎,2)
• Let secnonce = bytes(32, k₁) || bytes(32, k₂)¹¹
• Return (secnonce, pubnonce)

Nonce Aggregation

Algorithm NonceAgg(pubnonce_1..u, id_1..u):

• Inputs:
  • The number of signers u: an integer with min_participants ≤ u ≤ max_participants
  • The public nonces pubnonce_1..u: u 66-byte arrays
  • The participant identifiers id_1..u: u 32-byte arrays with 1 ≤ int(id_i) ≤ max_participants
• For j = 1 .. 2:
  • For i = 1 .. u:
    • Let _R_i,j = cpoint(pubnonce_i[(j-1)33:j_33]); fail if that fails and blame signer id_i for invalid pubnonce.
  • Let R_j = R_1,j + R_2,j + ... + R_u,j
• Return aggnonce = cbytes_ext(R₁) || cbytes_ext(R₂)

Session Context

The Session Context is a data structure consisting of the following elements:

• The number u of participants available in the signing session with min_participants ≤ u ≤ max_participants
• The participant identifiers of the signers _id_1..u: u 32-byte arrays with 1 ≤ int(id_i) ≤ max_participants < n
• The individual public shares pubshare_1..u: u 33-byte arrays
• The aggregate public nonce of signers aggnonce: a 66-byte array
• The number v of tweaks with 0 ≤ v < 2^32
• The tweaks tweak_1..v: v 32-byte arrays
• The tweak modes is_xonly_t_1..v : v booleans
• The message m: a byte array⁹

We write "Let (u, id_1..u, pubshare_1..u, aggnonce, v, tweak_1..v, is_xonly_t_1..v, m) = session_ctx" to assign names to the elements of a Session Context.

Algorithm GetSessionValues(session_ctx):

• Let (u, id_1..u, pubshare_1..u, aggnonce, v, tweak_1..v, is_xonly_t_1..v, m) = session_ctx
• Let tweak_ctx₀ = TweakCtxInit(id_1..u, pubshare_1..u); fail if that fails
• For i = 1 .. v:
  • Let tweak_ctx_i = ApplyTweak(tweak_ctx_i-1, tweak_i, is_xonly_t_i); fail if that fails
• Let (Q, gacc, tacc) = tweak_ctx_v
• Let ser_ids = concat_bytearrays(sorted(id_1..u))
• Let b = int(hash_{FROST/noncecoef}(ser_ids || aggnonce || xbytes(Q) || m)) mod n
• Let R₁ = cpoint_ext(aggnonce[0:33]), R₂ = cpoint_ext(aggnonce[33:66]); fail if that fails and blame nonce aggregator for invalid aggnonce.
• Let R' = R₁ + b⋅R₂
• If is_infinite(R'):
  • Let final nonce R = G (see Dealing with Infinity in Nonce Aggregation)
• Else:
  • Let final nonce R = R'
• Let e = int(hash_{BIP0340/challenge}((xbytes(R) || xbytes(Q) || m))) mod n
• Return (Q, gacc, tacc, b, R, e)

Algorithm GetSessionInterpolatingValue(session_ctx, my_id):

• Let _(u, id_1..u, _, _, _, _, ) = session_ctx
• Return DeriveInterpolatingValue(id_1..u, my_id); fail if that fails

Algorithm SessionHasSignerPubshare(session_ctx, signer_pubshare):

• Let _(u, _, pubshare_1..u, _, _, _, ) = session_ctx
• If signer_pubshare in pubshare_1..u
  • Return True
• Otherwise Return False

Signing

Algorithm Sign(secnonce, secshare, my_id, session_ctx):

• Inputs:
  • The secret nonce secnonce that has never been used as input to Sign before: a 64-byte array¹¹
  • The secret signing key secshare: a 32-byte array
  • The identifier of the signing participant my_id: a 32-byte array with 1 ≤ int(my_id) ≤ max_participants
  • The session_ctx: a Session Context data structure
• Let _(Q, gacc, , b, R, e) = GetSessionValues(session_ctx); fail if that fails
• Let k₁' = int(secnonce[0:32]), k₂' = int(secnonce[32:64])
• Fail if k_i' = 0 or k_i' ≥ n for i = 1..2
• Let k₁ = k₁', k₂ = k₂' if has_even_y(R), otherwise let k₁ = n - k₁', k₂ = n - k₂'
• Let d' = int(secshare)
• Fail if d' = 0 or d' ≥ n
• Let P = d'⋅G
• Let pubshare = cbytes(P)
• Fail if SessionHasSignerPubshare(session_ctx, pubshare) = False
• Let λ = GetSessionInterpolatingValue(session_ctx, my_id); fail if that fails
• Let g = 1 if has_even_y(Q), otherwise let g = -1 mod n
• Let d = g⋅gacc⋅d' mod n (See Negation of Secret Share When Signing)
• Let s = (k₁ + b⋅k₂ + e⋅λ⋅d) mod n
• Let psig = bytes(32, s)
• Let pubnonce = cbytes(k₁'⋅G) || cbytes(k₂'⋅G)
• If PartialSigVerifyInternal(psig, my_id, pubnonce, pubshare, session_ctx) (see below) returns failure, fail¹²
• Return partial signature psig

Partial Signature Verification

Algorithm PartialSigVerify(psig, id_1..u, pubnonce_1..u, pubshare_1..u, tweak_1..v, is_xonly_t_1..v, m, i):

• Inputs:
  • The partial signature psig: a 32-byte array
  • The number u of identifiers, public nonces, and individual public shares with min_participants ≤ u ≤ max_participants
  • The participant identifiers id_1..u: u 32-byte array with 1 ≤ int(id_i) ≤ max_participants
  • The public nonces pubnonce_1..u: u 66-byte arrays
  • The individual public shares pubshare_1..u: u 33-byte arrays
  • The number v of tweaks with 0 ≤ v < 2^32
  • The tweaks tweak_1..v: v 32-byte arrays
  • The tweak modes is_xonly_t_1..v : v booleans
  • The message m: a byte array⁹
  • The index i of the signer in the list of identifiers, public nonces, and individual public shares where 0 < i ≤ u
• Let aggnonce = NonceAgg(pubnonce_1..u); fail if that fails
• Let session_ctx = (u, id_1..u, pubshare_1..u, aggnonce, v, tweak_1..v, is_xonly_t_1..v, m)
• Run PartialSigVerifyInternal(psig, id_i, pubnonce_i, pubshare_i, session_ctx)
• Return success iff no failure occurred before reaching this point.

Internal Algorithm PartialSigVerifyInternal(psig, my_id, pubnonce, pubshare, session_ctx):

• Let _(Q, gacc, , b, R, e) = GetSessionValues(session_ctx); fail if that fails
• Let s = int(psig); fail if s ≥ n
• Fail if SessionHasSignerPubshare(session_ctx, pubshare) = False
• Let R_⁎,1 = cpoint(pubnonce[0:33]), R_⁎,2 = cpoint(pubnonce[33:66])
• Let Re_⁎' = R_⁎,1 + b⋅R_⁎,2
• Let effective nonce Re_⁎ = Re_⁎' if has_even_y(R), otherwise let Re_⁎ = -Re_⁎'
• Let P = cpoint(pubshare); fail if that fails
• Let λ = GetSessionInterpolatingValue(session_ctx, my_id)¹³
• Let g = 1 if has_even_y(Q), otherwise let g = -1 mod n
• Let g' = g⋅gacc mod n (See Negation of Pubshare When Partially Verifying)
• Fail if s⋅G ≠ Re_⁎ + e⋅λ⋅g'⋅P
• Return success iff no failure occurred before reaching this point.

Partial Signature Aggregation

Algorithm PartialSigAgg(psig_1..u, id_1..u, session_ctx):

• Inputs:
  • The number u of signatures with min_participants ≤ u ≤ max_participants
  • The partial signatures psig_1..u: u 32-byte arrays
  • The participant identifiers id_1..u: u 32-byte arrays with 1 ≤ int(id_i) ≤ max_participants
  • The session_ctx: a Session Context data structure
• Let _(Q, _, tacc, _, , R, e) = GetSessionValues(session_ctx); fail if that fails
• For i = 1 .. u:
  • Let s_i = int(psig_i); fail if s_i ≥ n and blame signer id_i for invalid partial signature.
• Let g = 1 if has_even_y(Q), otherwise let g = -1 mod n
• Let s = s₁ + ... + s_u + e⋅g⋅tacc mod n
• Return sig = xbytes(R) || bytes(32, s)

Test Vectors & Reference Code

We provide a naive, highly inefficient, and non-constant time pure Python 3 reference implementation of the group public key tweaking, nonce generation, partial signing, and partial signature verification algorithms.

Standalone JSON test vectors are also available in the same directory, to facilitate porting the test vectors into other implementations.

Caution

The reference implementation is for demonstration purposes only and not to be used in production environments.

Remarks on Security and Correctness

Modifications to Nonce Generation

Implementers must avoid modifying the NonceGen algorithm without being fully aware of the implications. We provide two modifications to NonceGen that are secure when applied correctly and may be useful in special circumstances, summarized in the following table.

	needs secure randomness	needs secure counter	needs to keep state securely	needs aggregate nonce of all other signers (only possible for one signer)
NonceGen	✓		✓
CounterNonceGen		✓	✓
DeterministicSign				✓

First, on systems where obtaining uniformly random values is much harder than maintaining a global atomic counter, it can be beneficial to modify NonceGen. The resulting algorithm CounterNonceGen does not draw rand' uniformly at random but instead sets rand' to the value of an atomic counter that is incremented whenever it is read. With this modification, the secret share secshare of the signer generating the nonce is not an optional argument and must be provided to NonceGen. The security of the resulting scheme then depends on the requirement that reading the counter must never yield the same counter value in two NonceGen invocations with the same secshare.

Second, if there is a unique signer who is supposed to send the pubnonce last, it is possible to modify nonce generation for this single signer to not require high-quality randomness. Such a nonce generation algorithm DeterministicSign is specified below. Note that the only optional argument is rand, which can be omitted if randomness is entirely unavailable. DeterministicSign requires the argument aggothernonce which should be set to the output of NonceAgg run on the pubnonce value of all other signers (but can be provided by an untrusted party). Hence, using DeterministicSign is only possible for the last signer to generate a nonce and makes the signer stateless, similar to the stateless signer described in the Nonce Generation section.

Deterministic and Stateless Signing for a Single Signer

Algorithm DeterministicSign(secshare, my_id, aggothernonce, id_1..u, pubshare_1..u, tweak_1..v, is_xonly_t_1..v, m, rand):

• Inputs:
  • The secret share secshare: a 32-byte array
  • The identifier of the signing participant my_id: a 32-byte array with 1 ≤ int(my_id) ≤ max_participants
  • The aggregate public nonce aggothernonce (see above): a 66-byte array
  • The number u of identifiers and participant public shares with min_participants ≤ u ≤ max_participants
  • The participant identifiers id_1..u: u 32-byte arrays
  • The individual public shares pubshare_1..u: u 33-byte arrays
  • The number v of tweaks with 0 ≤ v < 2^32
  • The tweaks tweak_1..v: v 32-byte arrays
  • The tweak methods is_xonly_t_1..v: v booleans
  • The message m: a byte array⁹
  • The auxiliary randomness rand: a 32-byte array (optional argument)
• If the optional argument rand is present:
  • Let secshare' be the byte-wise xor of secshare and hash_FROST/aux(rand)
• Else:
  • Let secshare' = secshare
• Let tweak_ctx₀ = TweakCtxInit(id_1..u, pubshare_1..u); fail if that fails
• For i = 1 .. v:
  • Let tweak_ctx_i = ApplyTweak(tweak_ctx_i-1, tweak_i, is_xonly_t_i); fail if that fails
• Let tweaked_gpk = GetXonlyPubkey(tweak_ctx_v)
• Let k_i = int(hash_{FROST/deterministic/nonce}(secshare' || aggothernonce || tweaked_gpk || bytes(8, len(m)) || m || bytes(1, i - 1))) mod n for i = 1,2
• Fail if k₁ = 0 or k₂ = 0
• Let R_⁎,1 = k₁⋅G, R_⁎,2 = k₂⋅G
• Let pubnonce = cbytes(R_⁎,2) || cbytes(R_⁎,2)
• Let d = int(secshare)
• Fail if d = 0 or d ≥ n
• Let signer_pubshare = cbytes(d⋅G)
• Fail if signer_pubshare is not present in pubshare_1..u
• Let secnonce = bytes(32, k₁) || bytes(32, k₂)
• Let aggnonce = NonceAgg((pubnonce, aggothernonce)); fail if that fails and blame nonce aggregator for invalid aggothernonce.
• Let session_ctx = (u, id_1..u, pubshare_1..u, aggnonce, v, tweak_1..v, is_xonly_t_1..v, m)
• Return (pubnonce, Sign(secnonce, secshare, my_id, session_ctx))

Tweaking Definition

Two modes of tweaking the group public key are supported. They correspond to the following algorithms:

Algorithm ApplyPlainTweak(P, t):

• Inputs:
  • P: a point
  • The tweak t: an integer with 0 ≤ t < n
• Return P + t⋅G

Algorithm ApplyXonlyTweak(P, t):

• Return with_even_y(P) + t⋅G

Negation of the Secret Share when Signing

During the signing process, the Sign algorithm might have to negate the secret share in order to produce a partial signature for an X-only group public key. This public key is derived from u public shares and u participant identifiers (denoted by the signer set U) and then tweaked v times (X-only or plain).

The following elliptic curve points arise as intermediate steps when creating a signature:
• P_i as computed in any compatible key generation method is the point corresponding to the i-th signer's public share. Defining d_i' to be the i-th signer's secret share as an integer, i.e., the d’ value as computed in the Sign algorithm of the i-th signer, we have:
  P_i = d_i'⋅G
• Q₀ is the group public key derived from the signer’s public shares. It is identical to the value Q computed in DeriveGroupPubkey and therefore defined as:
  Q₀ = λ_{1, U}⋅P₁ + λ_{2, U}⋅P₂ + ... + λ_{u, U}⋅P_u
• Q_i is the tweaked group public key after the i-th execution of ApplyTweak for 1 ≤ i ≤ v. It holds that
  Q_i = f(i-1) + t_i⋅G for i = 1, ..., v where
    f(i-1) := with_even_y(Q_i-1) if is_xonly_t_i and
    f(i-1) := Q_i-1 otherwise.
• with_even_y(Q_v) is the final result of the group public key derivation and tweaking operations. It corresponds to the output of GetXonlyPubkey applied on the final Tweak Context.

The signer's goal is to produce a partial signature corresponding to the final result of group pubkey derivation and tweaking, i.e., the X-only public key with_even_y(Q_v).

For 1 ≤ i ≤ v, we denote the value g computed in the i-th execution of ApplyTweak by g_i-1. Therefore, g_i-1 is -1 mod n if and only if is_xonly_t_i is true and Q_i-1 has an odd Y coordinate. In other words, g_i-1 indicates whether Q_i-1 needed to be negated to apply an X-only tweak:
  f(i-1) = g_i-1⋅Q_i-1 for 1 ≤ i ≤ v.
Furthermore, the Sign and PartialSigVerify algorithms set value g depending on whether Q_v needed to be negated to produce the (X-only) final output. For consistency, this value g is referred to as g_v in this section.
  with_even_y(Q_v) = g_v⋅Q_v.

So, the (X-only) final public key is
  with_even_y(Q_v)
    = g_v⋅Q_v
    = g_v⋅(f(v-1) + t_v⋅G)
    = g_v⋅(g_v-1⋅(f(v-2) + t_v-1⋅G) + t_v⋅G)
    = g_v⋅g_v-1⋅f(v-2) + g_v⋅(t_v + g_v-1⋅t_v-1)⋅G
    = g_v⋅g_v-1⋅f(v-2) + (sum_i=v-1..v t_i⋅prod_j=i..v g_j)⋅G
    = g_v⋅g_v-1⋅...⋅g₁⋅f(0) + (sum_i=1..v t_i⋅prod_j=i..v g_j)⋅G
    = g_v⋅...⋅g₀⋅Q₀ + g_v⋅tacc_v⋅G
  where tacc_i is computed by TweakCtxInit and ApplyTweak as follows:
    tacc₀ = 0
    tacc_i = t_i + g_i-1⋅tacc_i-1 for i=1..v mod n
  for which it holds that g_v⋅tacc_v = sum_i=1..v t_i⋅prod_j=i..v g_j.

TweakCtxInit and ApplyTweak compute
  gacc₀ = 1
  gacc_i = g_i-1⋅gacc_i-1 for i=1..v mod n
So we can rewrite above equation for the final public key as
  with_even_y(Q_v) = g_v⋅gacc_v⋅Q₀ + g_v⋅tacc_v⋅G.

Then we have
  with_even_y(Q_v) - g_v⋅tacc_v⋅G
    = g_v⋅gacc_v⋅Q₀
    = g_v⋅gacc_v⋅(λ_{1, U}⋅P₁ + ... + λ_{u, U}⋅P_u)
    = g_v⋅gacc_v⋅(λ_{1, U}⋅d₁'⋅G + ... + λ_{u, U}⋅d_u'⋅G)
    = sum_i=1..u(g_v⋅gacc_v⋅λ_{i, U}⋅d_i')*G.

Intuitively, gacc_i tracks accumulated sign flipping and tacc_i tracks the accumulated tweak value after applying the first i individual tweaks. Additionally, g_v indicates whether Q_v needed to be negated to produce the final X-only result. Thus, signer i multiplies its secret share d_i' with g_v⋅gacc_v in the Sign algorithm.

Negation of the Pubshare when Partially Verifying

As explained in Negation Of The Secret Share When Signing the signer uses a possibly negated secret share
  d = g_v⋅gacc_v⋅d' mod n
when producing a partial signature to ensure that the aggregate signature will correspond to a group public key with even Y coordinate.

The PartialSigVerifyInternal algorithm is supposed to check
  s⋅G = Re_⁎ + e⋅λ⋅d⋅G.

The verifier doesn't have access to d⋅G but can construct it using the participant public share pubshare as follows:
d⋅G
  = g_v⋅gacc_v⋅d'⋅G
  = g_v⋅gacc_v⋅cpoint(pubshare)
Note that the group public key and list of tweaks are inputs to partial signature verification, so the verifier can also construct g_v and gacc_v.

Dealing with Infinity in Nonce Aggregation

If the nonce aggregator provides aggnonce = bytes(33,0) || bytes(33,0), either the nonce aggregator is dishonest or there is at least one dishonest signer (except with negligible probability). If signing aborted in this case, it would be impossible to determine who is dishonest. Therefore, signing continues so that the culprit is revealed when collecting and verifying partial signatures.

However, the final nonce R of a BIP340 Schnorr signature cannot be the point at infinity. If we would nonetheless allow the final nonce to be the point at infinity, then the scheme would lose the following property: if PartialSigVerify succeeds for all partial signatures, then PartialSigAgg will return a valid Schnorr signature. Since this is a valuable feature, we modify FROST3 (which is defined in the section 2.3 of the ROAST paper) to avoid producing an invalid Schnorr signature while still allowing detection of the dishonest signer: In GetSessionValues, if the final nonce R would be the point at infinity, set it to the generator instead (an arbitrary choice).

This modification to GetSessionValues does not affect the unforgeability of the scheme. Given a successful adversary against the unforgeability game (EUF-CMA) for the modified scheme, a reduction can win the unforgeability game for the original scheme by simulating the modification towards the adversary: When the adversary provides aggnonce' = bytes(33, 0) || bytes(33, 0), the reduction sets aggnonce = cbytes_ext(G) || bytes(33, 0). For any other aggnonce', the reduction sets aggnonce = aggnonce'. (The case that the adversary provides an aggnonce' ≠ bytes(33, 0) || bytes(33, 0) but nevertheless R' in GetSessionValues is the point at infinity happens only with negligible probability.)

Backwards Compatibility

This document proposes a standard for the FROST threshold signature scheme that is compatible with BIP340. FROST is not compatible with ECDSA signatures traditionally used in Bitcoin.

Footnotes

1. While t = n and t = 1 are in principle supported, simpler alternatives are available in these cases. In the case t = n, using a dedicated n-of-n multi-signature scheme such as MuSig2 (see BIP327) instead of FROST avoids the need for an interactive DKG. The case t = 1 can be realized by letting one signer generate an ordinary BIP340 key pair and transmitting the key pair to every other signer, who can check its consistency and then simply use the ordinary BIP340 signing algorithm. Signers still need to ensure that they agree on a key pair. A detailed specification for this key sharing protocol is not in the scope of this document. ↩

2. We treat the secnonce and pubnonce as grammatically singular even though they include serializations of two scalars and two elliptic curve points, respectively. This treatment may be confusing for readers familiar with the MuSig2 paper. However, serialization is a technical detail that is irrelevant for users of MuSig2 interfaces. ↩

3. Assume a malicious participant intends to forge a partial signature for the participant with public share P. It participates in the signing session pretending to be two distinct signers: one with the public share P and the other with its own public share. The adversary then sets the nonce for the second signer in such a way that allows it to generate a partial signature for P. As a side effect, it cannot generate a valid partial signature for its own public share. An explanation of the steps required to create a partial signature forgery can be found in this document. ↩

4. It is an open question whether allowing arbitrary tweaks from an adversary affects the unforgeability of FROST. ↩

5. Given a candidate X coordinate x in the range 0..p-1, there exist either exactly two or exactly zero valid Y coordinates. If no valid Y coordinate exists, then x is not a valid X coordinate either, i.e., no point P exists for which x(P) = x. The valid Y coordinates for a given candidate x are the square roots of c = x³ + 7 mod p and they can be computed as y = ±c^(p+1)/4 mod p (see Quadratic residue) if they exist, which can be checked by squaring and comparing with c. ↩

6. The PlainPubkeyGen algorithm matches the key generation procedure traditionally used for ECDSA in Bitcoin ↩

7. This line represents a loop over every possible combination of t elements sourced from the int_ids array. This operation is equivalent to invoking the itertools.combinations(int_ids, t) function call in Python. ↩

8. This signer_pubshare_1..t list can be computed from the input pubshare_1..u list.
   Method 1 - use itertools.combinations(zip(int_ids, pubshares), t)
   Method 2 - For i = 1..t : signer_pubshare_i = pubshare_{signer_idi} ↩

9. In theory, the allowed message size is restricted because SHA256 accepts byte strings only up to size of 2^61-1 bytes (and because of the 8-byte length encoding). ↩ ↩² ↩³ ↩⁴

10. The random data is hashed (with a unique tag) as a precaution against situations where the randomness may be correlated with the secret signing key itself. It is xored with the secret key (rather than combined with it in a hash) to reduce the number of operations exposed to the actual secret key. ↩

11. The algorithms as specified here assume that the secnonce is stored as a 64-byte array using the serialization secnonce = bytes(32, k₁) || bytes(32, k₂). The same format is used in the reference implementation and in the test vectors. However, since the secnonce is (obviously) not meant to be sent over the wire, compatibility between implementations is not a concern, and this method of storing the secnonce is merely a suggestion.
    The secnonce is effectively a local data structure of the signer which comprises the value triple (k₁, k₂), and implementations may choose any suitable method to carry it from NonceGen (first communication round) to Sign (second communication round). In particular, implementations may choose to hide the secnonce in internal state without exposing it in an API explicitly, e.g., in an effort to prevent callers from reusing a secnonce accidentally. ↩ ↩²

12. Verifying the signature before leaving the signer prevents random or adversarially provoked computation errors. This prevents publishing invalid signatures which may leak information about the secret key. It is recommended but can be omitted if the computation cost is prohibitive. ↩

13. GetSessionInterpolatingValue(session_ctx, my_id) cannot fail when called from PartialSigVerifyInternal. ↩