By Tim Ruffing, Elliott Jin, and Jonas Nick

Making Bitcoin and Liquid more private and more efficient is a fundamental goal of our research efforts at Blockstream Research. One particular way to achieve this goal is to make transactions of different kinds look as similar as possible on the blockchain: if it is not possible to distinguish transactions from multisig wallets, the Lightning Network, and other Layer 2 applications from regular payments, then it is much harder to analyze blockchain data and track the payments of users.

Our past contributions towards this goal include MuSig, MuSig-DN, and MuSig2, which allow expressing “n-of-n” multisig wallets (2-of-2, 3-of-3, …) with just a single BIP340 (Schnorr signature) public key that appears as if the wallet only consists of a single user who makes a regular on-chain payment. To achieve similar efficiency and privacy benefits for “t-of-n” multisig wallets (1-of-2, 2-of-3, 3-of-5, …), Chelsea Komlo (University of Waterloo and Zcash Foundation) and Ian Goldberg (University of Waterloo) proposed the FROST threshold signature scheme.

“t-of-n” multisig wallets are at the heart of Blockstream’s Liquid Network, which is a sidechain run by a distributed federation of functionaries. In particular, the functionaries are responsible for the operation of a federated wallet, which currently uses an “11-of-15” multisig and holds the bitcoins that have been pegged-in, i.e., transferred to the sidechain. Whenever a Liquid user would like to peg-out, i.e., transfer Liquid bitcoin (L-BTC) back to the Bitcoin main chain, the federation creates a transaction that sends bitcoin from the federated wallet to the user’s address. Bitcoin’s built-in support for 11-of-15 requires broadcasting all 15 public keys and all 11 signatures, which results in high fees. Using the FROST protocol would solve this issue. However, in order to sign the transaction with FROST, a quorum of 11 functionaries must coordinate and exchange multiple messages. If coordination fails, e.g., because network conditions are poor, a signer is offline, or actively disruptive, the protocol fails and must be restarted. This is suboptimal for automated signing software as used in the federated wallet because it would not reliably produce a signature even if a quorum of at least 11 signers is willing to sign.

ROAST (Robust Asynchronous Schnorr Threshold signatures) is our solution to this problem. ROAST is a simple wrapper around threshold signature schemes like FROST. It guarantees that a quorum of honest signers, e.g., the Liquid functionaries, can always obtain a valid signature even in the presence of disruptive signers when network connections have arbitrarily high latency. Our empirical performance evaluation shows that ROAST scales well to large signer groups, e.g., a 67-of-100 setup with the coordinator and signers on different continents. Even with 33 malicious signers that try to block signing attempts (e.g. by sending invalid responses or by not responding at all), the 67 honest signers can successfully produce a signature within a few seconds. For a more in-depth introduction and description of the protocol, read the full paper.

ROAST is a result of a research collaboration between Tim Ruffing (Blockstream), Viktoria Ronge (Friedrich-Alexander-Universität Erlangen-Nürnberg), Elliott Jin (Blockstream), Jonas Schneider-Bensch (CISPA Helmholtz Center for Information Security), and Dominique Schröder (Friedrich-Alexander-Universität Erlangen-Nürnberg).

We close with an excerpt from the paper, the tale of Frostland, which illustrates the communication steps required for FROST and the intuition behind ROAST.

Frostland

In the far country of Frostland, a democratic council is responsible for legislation. The constitution states that for a new bill to pass, a majority of t = 7 of n = 13 council members need to sign it. Readers not familiar with the Frostlandic culture might assume that the main difficulty in the democratic process is finding a majority in the council and that signing the bill is only a formality.

However, in Frostland, signing is a complicated task. Frostlanders are very proud of their aesthetic heritage. Each of the 13 council members owns a unique and beautiful watermark, and a bill is only valid if the paper it’s written on carries the watermarks of all signers (and no others).

The signing process is, therefore, as follows: Find a majority coalition of council members, manufacture a sufficient amount of paper carrying the watermarks of these council members (but no other council members’ watermarks), write the contents of the bill on the watermarked paper, and finally, collect signatures on the bill from exactly those members. However, if one of the members of the coalition fails to provide a signature during the final step, e.g., because she is out of the office for an indefinite period of time, the process stalls. In particular, it is not possible to ask another member to sign because the paper carries the disruptive member’s watermark (instead of the new member’s watermark). The only way to move forward is to start an entirely new signing process from scratch, which involves finding a new majority of council members and going through the cumbersome process of manufacturing paper with a new set of watermarks.

This peculiarity makes signing very complicated, and the council members employ a secretary whose task is to facilitate the process. Unfortunately for the secretary, it is not clear upfront which council members support a proposed bill. From time to time, members try to disrupt the signing process in an attempt to prevent other members from passing the bill and refuse to sign even though they have indicated support for a bill. In the worst case, it could even happen that all 13 council members claim to support the bill, but in fact, only 7 or fewer of them support it.

The poor secretary has multiple options: First, the secretary could choose a group of 7 council members who claim to support the bill, manufacture paper with their watermarks, prepare a single copy of the bill on that paper, and ask the chosen group to sign that copy. If any council members in the chosen group actively refuses to sign correctly (e.g., by giving a wrong signature) and thereby forces the signing to abort, the secretary can identify the disruptive members, fret about the dishonesty in the council, replace the disruptive members with other members, and prepare a new copy of the bill (which involves manufacturing new paper with different watermarks). However, the very bureaucratic rules in the constitution of Frostland mandate that each council member is given an indefinite amount of time to check a bill before signing or refusing it, and as a result, the entire signing procedure can take very long. Some particularly annoying council members sit in front of the bill for hours and hours, pretending to check that the copy has been prepared correctly, and the secretary cannot tell whether a given member will eventually sign or just keep sitting there forever. As a result, this procedure can take very long and even get stuck.

Alternatively, the secretary could prepare a separate copy of the bill for each group of 7 members and ask all supporting council members to sign each copy on which their watermark appears. While this procedure is guaranteed not to get stuck, the secretary, who is proficient in combinatorics, knows that the procedure is not suitable in practice because it requires him to prepare “n choose t” = “13 choose 7” = 1716 copies in total.

As a solution to this problem, the secretary uses the following procedure: In the beginning, all council members that signal support for the bill are asked to gather in the council building. The secretary maintains a list of all these members and whenever there are at least 7 members on the list (which is also the case in the beginning of the procedure), he calls a group of 7 members to his office, and strikes out their names on the list. He then obtains paper with the watermarks of those 7 members, writes a copy of the bill on that paper, and asks the council members in the group to sign it. Whenever a council member has completed signing the copy, they leave the office and wait for a new call while the secretary adds their name back to his list.

It is easy for the secretary to see that this procedure will succeed and not need too many copies of the bill: If at least 7 council members actually support the bill and behave honestly, then at any point in time, he knows that these 7 members will eventually sign their currently assigned copy and be re-added to the secretary’s list. Thus the secretary can always be sure that 7 members will be on his list again at some point in the future, and so the signing procedure will not get stuck. Moreover, since members are assigned a new copy only after correctly signing the previously assigned copy, each member can hold up the signing of at most one copy at a time. Thus, even the maximum of n − t = 13 − 7 = 6 disruptive council members can hold up the signing of at most 6 copies. At the very latest, the 7th copy of the bill will then be assigned only to honest council members who will complete the signing and produce a correctly signed bill.

Note: This blog was originally posted at https://medium.com/blockstream/roast-robust-asynchronous-schnorr-threshold-signatures-ddda55a07d1b