{"id":14696,"date":"2022-11-21T21:29:57","date_gmt":"2022-11-21T21:29:57","guid":{"rendered":"https:\/\/crowdfundjunction.com\/blog\/frost-flexible-round-optimized-schnorr-threshold-signatures-by-coinbase-the-coinbase-blog\/"},"modified":"2022-11-21T21:29:57","modified_gmt":"2022-11-21T21:29:57","slug":"frost-flexible-round-optimized-schnorr-threshold-signatures-by-coinbase-the-coinbase-blog","status":"publish","type":"post","link":"https:\/\/crowdfundjunction.com\/blog\/frost-flexible-round-optimized-schnorr-threshold-signatures-by-coinbase-the-coinbase-blog\/","title":{"rendered":"FROST: Flexible Round-Optimized Schnorr Threshold Signatures | by Coinbase | The Coinbase Blog"},"content":{"rendered":"<p><b>(Originally posted on : Bitcoin in The Coinbase Blog on Medium )<\/b><br \/>\n<\/p>\n<div>\n<figure class=\"gp gr jw jx jy jz gl gm paragraph-image\">\n<div role=\"button\" tabindex=\"0\" class=\"ka kb do kc ce kd\">\n<div class=\"gl gm jv\"><picture><source srcset=\"https:\/\/miro.medium.com\/max\/640\/1*iICst8Q2_LjwWuxYxajw1g.webp 640w, https:\/\/miro.medium.com\/max\/720\/1*iICst8Q2_LjwWuxYxajw1g.webp 720w, https:\/\/miro.medium.com\/max\/750\/1*iICst8Q2_LjwWuxYxajw1g.webp 750w, https:\/\/miro.medium.com\/max\/786\/1*iICst8Q2_LjwWuxYxajw1g.webp 786w, https:\/\/miro.medium.com\/max\/828\/1*iICst8Q2_LjwWuxYxajw1g.webp 828w, https:\/\/miro.medium.com\/max\/1100\/1*iICst8Q2_LjwWuxYxajw1g.webp 1100w, https:\/\/miro.medium.com\/max\/1400\/1*iICst8Q2_LjwWuxYxajw1g.webp 1400w\" sizes=\"(min-resolution: 4dppx) and (max-width: 700px) 50vw, (-webkit-min-device-pixel-ratio: 4) and (max-width: 700px) 50vw, (min-resolution: 3dppx) and (max-width: 700px) 67vw, (-webkit-min-device-pixel-ratio: 3) and (max-width: 700px) 65vw, (min-resolution: 2.5dppx) and (max-width: 700px) 80vw, (-webkit-min-device-pixel-ratio: 2.5) and (max-width: 700px) 80vw, (min-resolution: 2dppx) and (max-width: 700px) 100vw, (-webkit-min-device-pixel-ratio: 2) and (max-width: 700px) 100vw, 700px\" type=\"image\/webp\"\/><source data-testid=\"og\" srcset=\"https:\/\/miro.medium.com\/max\/640\/1*iICst8Q2_LjwWuxYxajw1g.jpeg 640w, https:\/\/miro.medium.com\/max\/720\/1*iICst8Q2_LjwWuxYxajw1g.jpeg 720w, https:\/\/miro.medium.com\/max\/750\/1*iICst8Q2_LjwWuxYxajw1g.jpeg 750w, https:\/\/miro.medium.com\/max\/786\/1*iICst8Q2_LjwWuxYxajw1g.jpeg 786w, https:\/\/miro.medium.com\/max\/828\/1*iICst8Q2_LjwWuxYxajw1g.jpeg 828w, https:\/\/miro.medium.com\/max\/1100\/1*iICst8Q2_LjwWuxYxajw1g.jpeg 1100w, https:\/\/miro.medium.com\/max\/1400\/1*iICst8Q2_LjwWuxYxajw1g.jpeg 1400w\" sizes=\"(min-resolution: 4dppx) and (max-width: 700px) 50vw, (-webkit-min-device-pixel-ratio: 4) and (max-width: 700px) 50vw, (min-resolution: 3dppx) and (max-width: 700px) 67vw, (-webkit-min-device-pixel-ratio: 3) and (max-width: 700px) 65vw, (min-resolution: 2.5dppx) and (max-width: 700px) 80vw, (-webkit-min-device-pixel-ratio: 2.5) and (max-width: 700px) 80vw, (min-resolution: 2dppx) and (max-width: 700px) 100vw, (-webkit-min-device-pixel-ratio: 2) and (max-width: 700px) 100vw, 700px\"\/><img alt=\"\" class=\"ce ke kf c\" width=\"700\" height=\"350\" loading=\"eager\" role=\"presentation\"\/><\/picture><\/div>\n<\/div>\n<\/figure>\n<p id=\"1924\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\">By <a class=\"au le\" href=\"https:\/\/www.linkedin.com\/in\/daniellinfeng\/\" rel=\"noopener ugc nofollow\" target=\"_blank\">Daniel Zhou<\/a><\/p>\n<p id=\"e49b\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\"><a class=\"au le\" href=\"https:\/\/tools.ietf.org\/pdf\/draft-irtf-cfrg-frost-01.pdf\" rel=\"noopener ugc nofollow\" target=\"_blank\"><strong class=\"ki iz\">FROST<\/strong><\/a><strong class=\"ki iz\"> is a round-optimal threshold Schnorr signature protocol. Here we introduce why Coinbase decided to use FROST, what FROST is, and what we discovered while evaluating FROST.<\/strong><\/p>\n<p id=\"c6a0\" class=\"pw-post-body-paragraph kg kh iy ki b kj md kl km kn me kp kq kr mf kt ku kv mg kx ky kz mh lb lc ld ir ga\">In order to improve efficiency of Coinbase\u2019s threshold-signing systems, we decided to explore the FROST threshold Schnorr signature protocol, which features the following advantages over other Schnorr-based threshold signature protocols <a class=\"au le\" href=\"http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.83.6830&amp;rep=rep1&amp;type=pdf#page=389\" rel=\"noopener ugc nofollow\" target=\"_blank\">[GJKR03<\/a>, <a class=\"au le\" href=\"https:\/\/www.researchgate.net\/profile\/Willy-Susilo\/publication\/242499559_Information_Security_and_Privacy_13th_Australasian_Conference_ACISP_2008_Wollongong_Australia_July_7-9_2008_Proceedings\/links\/00b495314f3bcaaa46000000\/Information-Security-and-Privacy-13th-Australasian-Conference-ACISP-2008-Wollongong-Australia-July-7-9-2008-Proceedings.pdf#page=426\" rel=\"noopener ugc nofollow\" target=\"_blank\">SS01<\/a>]:<\/p>\n<p id=\"aa53\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\"><strong class=\"ki iz\">Low round complexity <\/strong>in both the distributed key-generation and signing phases. The distributed key generation phase can be completed in 2 rounds. The signing phase can be completed in less or equal to 3 rounds depending on whether we use a signature aggregator role and a preprocessing stage. That is,<\/p>\n<ul class=\"\">\n<li id=\"85e4\" class=\"mi mj iy ki b kj kk kn ko kr mk kv ml kz mm ld mn mo mp mq ga\">1-round signing with a trusted signature aggregator and a preprocessing stage.<\/li>\n<li id=\"8d73\" class=\"mi mj iy ki b kj mr kn ms kr mt kv mu kz mv ld mn mo mp mq ga\">2-round signing with a trusted signature aggregator, but no preprocessing stage.<\/li>\n<li id=\"80ec\" class=\"mi mj iy ki b kj mr kn ms kr mt kv mu kz mv ld mn mo mp mq ga\">3-round signing <em class=\"mw\">without<\/em> a trusted signature aggregator and no preprocessing stage.<\/li>\n<\/ul>\n<p id=\"4bc0\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\"><strong class=\"ki iz\">Concurrent security. <\/strong>The signing phase is secure when performed concurrently. That is, an unlimited number of signature operations can be performed in parallel. In contrast with other threshold Schnorr signature protocols, there are existing Schnorr-based threshold signature protocols, such as <a class=\"au le\" href=\"http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.83.6830&amp;rep=rep1&amp;type=pdf#page=389\" rel=\"noopener ugc nofollow\" target=\"_blank\">[GJKR03<\/a>, <a class=\"au le\" href=\"https:\/\/www.researchgate.net\/profile\/Willy-Susilo\/publication\/242499559_Information_Security_and_Privacy_13th_Australasian_Conference_ACISP_2008_Wollongong_Australia_July_7-9_2008_Proceedings\/links\/00b495314f3bcaaa46000000\/Information-Security-and-Privacy-13th-Australasian-Conference-ACISP-2008-Wollongong-Australia-July-7-9-2008-Proceedings.pdf#page=426\" rel=\"noopener ugc nofollow\" target=\"_blank\">SS01<\/a>], that have the same round complexity, but they suffer from limited concurrency to protect against the attack of Drijvers et al. [<a class=\"au le\" href=\"https:\/\/eprint.iacr.org\/2018\/417.pdf\" rel=\"noopener ugc nofollow\" target=\"_blank\">DEF19<\/a>]. This attack was originally proposed in a Schnorr multi-signature <em class=\"mw\">n<\/em>-out-of-<em class=\"mw\">n <\/em>setting, but it also applies similarly in a threshold <em class=\"mw\">t<\/em>-out-of-<em class=\"mw\">n<\/em> setting with the same parameters for an adversary that controls up to <em class=\"mw\">t-1<\/em> participants. We refer readers to section 2.6 of the <a class=\"au le\" href=\"https:\/\/tools.ietf.org\/pdf\/draft-irtf-cfrg-frost-00.pdf\" rel=\"noopener ugc nofollow\" target=\"_blank\">FROST draft \u2014 version 0<\/a> for more details. To prevent this attack without limiting concurrency, FROST binds each participant\u2019s response to a specific message as well as the set of participants and their set of elliptic curve (EC) points used for that particular signing operation. In doing so, combining responses over different messages or EC point pairs results in an invalid signature, thwarting attacks such as those of Drijvers, et al.<\/p>\n<p id=\"bc81\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\"><strong class=\"ki iz\">Secure against dishonest majority.<\/strong> FROST is secure against adversaries which control up to <em class=\"mw\">t-1<\/em> signers in the signing phase.<\/p>\n<p id=\"4212\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\"><strong class=\"ki iz\">Simple cryptographic building blocks and assumptions.<\/strong> FROST is built upon the threshold Shamir secret sharing and Feldman verifiable secret sharing schemes and it relies only on the discrete logarithm assumption.<\/p>\n<p id=\"69e3\" class=\"pw-post-body-paragraph kg kh iy ki b kj md kl km kn me kp kq kr mf kt ku kv mg kx ky kz mh lb lc ld ir ga\">Before we introduce how FROST works, we first recall how the standalone Schnorr signature works.<\/p>\n<p id=\"0713\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\">A Schnorr digital signature algorithm is a triple of algorithms: <em class=\"mw\">(KeyGen, Sign, Verify)<\/em>.<\/p>\n<p id=\"f4b9\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\">Let <em class=\"mw\">G<\/em> be a group generator of a cyclic group with prime order p, and let <em class=\"mw\">H<\/em> be a cryptographic hash function mapping to the field <em class=\"mw\">Z<\/em>\u209a<em class=\"mw\">* <\/em>. A Schnorr signature is generated over a message <em class=\"mw\">m<\/em> by the following steps:<\/p>\n<p id=\"22d5\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\"><em class=\"mw\">KeyGen -&gt; (sk, vk)<\/em><\/p>\n<ul class=\"\">\n<li id=\"9056\" class=\"mi mj iy ki b kj kk kn ko kr mk kv ml kz mm ld mn mo mp mq ga\">Randomly sample the secret key <em class=\"mw\">sk &lt;- Z<\/em>\u209a.<\/li>\n<li id=\"0b29\" class=\"mi mj iy ki b kj mr kn ms kr mt kv mu kz mv ld mn mo mp mq ga\">Return <em class=\"mw\">(sk, vk = sk * G)<\/em>.<\/li>\n<\/ul>\n<p id=\"c731\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\"><em class=\"mw\">Sign(sk, m) -&gt; sig<\/em><\/p>\n<ul class=\"\">\n<li id=\"86e2\" class=\"mi mj iy ki b kj kk kn ko kr mk kv ml kz mm ld mn mo mp mq ga\">Randomly sample a secret nonce <em class=\"mw\">k &lt;- Z<\/em>\u209a.<\/li>\n<li id=\"8245\" class=\"mi mj iy ki b kj mr kn ms kr mt kv mu kz mv ld mn mo mp mq ga\"><em class=\"mw\">R = k * G<\/em><\/li>\n<li id=\"c3ed\" class=\"mi mj iy ki b kj mr kn ms kr mt kv mu kz mv ld mn mo mp mq ga\"><em class=\"mw\">c = H(m, R)<\/em><\/li>\n<li id=\"bc33\" class=\"mi mj iy ki b kj mr kn ms kr mt kv mu kz mv ld mn mo mp mq ga\"><em class=\"mw\">z = k + sk * c (mod p)<\/em><\/li>\n<li id=\"f83b\" class=\"mi mj iy ki b kj mr kn ms kr mt kv mu kz mv ld mn mo mp mq ga\">Return signature <em class=\"mw\">sig = (z, c)<\/em><\/li>\n<\/ul>\n<p id=\"23df\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\"><em class=\"mw\">Verify(vk, m, sig) -&gt; true\/false<\/em><\/p>\n<ul class=\"\">\n<li id=\"d873\" class=\"mi mj iy ki b kj kk kn ko kr mk kv ml kz mm ld mn mo mp mq ga\">Parse <em class=\"mw\">sig = (z\u2019, c\u2019)<\/em><\/li>\n<li id=\"c62b\" class=\"mi mj iy ki b kj mr kn ms kr mt kv mu kz mv ld mn mo mp mq ga\"><em class=\"mw\">R\u2019 = z * G -c * vk<\/em><\/li>\n<li id=\"3cdf\" class=\"mi mj iy ki b kj mr kn ms kr mt kv mu kz mv ld mn mo mp mq ga\"><em class=\"mw\">c\u2019 = H(m, R\u2019)<\/em><\/li>\n<li id=\"eabf\" class=\"mi mj iy ki b kj mr kn ms kr mt kv mu kz mv ld mn mo mp mq ga\">Return true if <em class=\"mw\">c = c\u2019<\/em>, otherwise return false.<\/li>\n<\/ul>\n<p id=\"7a42\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\">We call <em class=\"mw\">(sk, vk)<\/em> the secret and verification keys respectively. We call <em class=\"mw\">m<\/em> the message being signed and <em class=\"mw\">sig<\/em> the Schnorr digital signature.<\/p>\n<p id=\"e659\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\">FROST is a <em class=\"mw\">threshold<\/em> Schnorr signature protocol that contains two important components. First, <em class=\"mw\">n<\/em> participants run a <strong class=\"ki iz\">distributed key generation (DKG)<\/strong> protocol to generate a common verification key; at the end, each participant obtains a private secret key share and a public verification key share. Afterwards, any <em class=\"mw\">t-out-of-n<\/em> participants can run a <strong class=\"ki iz\">threshold signing<\/strong> protocol to collaboratively generate a valid Schnorr signature. The figure below gives a high-level sketch of how FROST works in the case of <em class=\"mw\">t = 3<\/em> and <em class=\"mw\">n = 5<\/em>.<\/p>\n<figure class=\"my mz na nb gx jz gl gm paragraph-image\">\n<div role=\"button\" tabindex=\"0\" class=\"ka kb do kc ce kd\">\n<div class=\"gl gm mx\"><picture><source srcset=\"https:\/\/miro.medium.com\/max\/640\/0*nw6uhbACMFbtMX4U 640w, https:\/\/miro.medium.com\/max\/720\/0*nw6uhbACMFbtMX4U 720w, https:\/\/miro.medium.com\/max\/750\/0*nw6uhbACMFbtMX4U 750w, https:\/\/miro.medium.com\/max\/786\/0*nw6uhbACMFbtMX4U 786w, https:\/\/miro.medium.com\/max\/828\/0*nw6uhbACMFbtMX4U 828w, https:\/\/miro.medium.com\/max\/1100\/0*nw6uhbACMFbtMX4U 1100w, https:\/\/miro.medium.com\/max\/1400\/0*nw6uhbACMFbtMX4U 1400w\" sizes=\"(min-resolution: 4dppx) and (max-width: 700px) 50vw, (-webkit-min-device-pixel-ratio: 4) and (max-width: 700px) 50vw, (min-resolution: 3dppx) and (max-width: 700px) 67vw, (-webkit-min-device-pixel-ratio: 3) and (max-width: 700px) 65vw, (min-resolution: 2.5dppx) and (max-width: 700px) 80vw, (-webkit-min-device-pixel-ratio: 2.5) and (max-width: 700px) 80vw, (min-resolution: 2dppx) and (max-width: 700px) 100vw, (-webkit-min-device-pixel-ratio: 2) and (max-width: 700px) 100vw, 700px\" type=\"image\/webp\"\/><source data-testid=\"og\" srcset=\"https:\/\/miro.medium.com\/max\/640\/0*nw6uhbACMFbtMX4U 640w, https:\/\/miro.medium.com\/max\/720\/0*nw6uhbACMFbtMX4U 720w, https:\/\/miro.medium.com\/max\/750\/0*nw6uhbACMFbtMX4U 750w, https:\/\/miro.medium.com\/max\/786\/0*nw6uhbACMFbtMX4U 786w, https:\/\/miro.medium.com\/max\/828\/0*nw6uhbACMFbtMX4U 828w, https:\/\/miro.medium.com\/max\/1100\/0*nw6uhbACMFbtMX4U 1100w, https:\/\/miro.medium.com\/max\/1400\/0*nw6uhbACMFbtMX4U 1400w\" sizes=\"(min-resolution: 4dppx) and (max-width: 700px) 50vw, (-webkit-min-device-pixel-ratio: 4) and (max-width: 700px) 50vw, (min-resolution: 3dppx) and (max-width: 700px) 67vw, (-webkit-min-device-pixel-ratio: 3) and (max-width: 700px) 65vw, (min-resolution: 2.5dppx) and (max-width: 700px) 80vw, (-webkit-min-device-pixel-ratio: 2.5) and (max-width: 700px) 80vw, (min-resolution: 2dppx) and (max-width: 700px) 100vw, (-webkit-min-device-pixel-ratio: 2) and (max-width: 700px) 100vw, 700px\"\/><img alt=\"\" class=\"ce ke kf c\" width=\"700\" height=\"477\" loading=\"lazy\" role=\"presentation\"\/><\/picture><\/div>\n<\/div><figcaption class=\"nc bl gn gl gm nd ne bm b bn bo cn\"><strong class=\"bm lh\">(3, 5) \u2014 FROST DKG + Threshold Signing Overview<\/strong><\/figcaption><\/figure>\n<p id=\"428a\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\">In the following context, we introduce FROST distributed key generation and threshold signing in more technical details.<\/p>\n<p id=\"055f\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\"><strong class=\"ki iz\">FROST \u2014 distributed key generation (DKG)<\/strong>. The secret signing key in Schnorr signature is an element in the field <em class=\"mw\">Z<\/em>\u209a. The goal of this phase is to generate long-lived secret key shares and a joint verification key. This phase is run by <em class=\"mw\">n<\/em> participants. FROST builds its own key generation phase upon Pedersen\u2019s DKG [<a class=\"au le\" href=\"http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.83.6830&amp;rep=rep1&amp;type=pdf#page=389\" rel=\"noopener ugc nofollow\" target=\"_blank\">GJKR03<\/a>], in which it uses both Shamir secret sharing and Feldman\u2019s verifiable secret sharing schemes as subroutines. In addition, FROST also requires each participant to demonstrate knowledge of their own secret by sending to other participants a zero-knowledge proof, which itself is a Schnorr signature. This additional step protects against <a class=\"au le\" href=\"https:\/\/cseweb.ucsd.edu\/~mihir\/papers\/bbs.pdf\" rel=\"noopener ugc nofollow\" target=\"_blank\">rogue-key attacks<\/a> in the setting where <em class=\"mw\">t \u2265 n\/2<\/em>.<\/p>\n<p id=\"cd7c\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\">At the end of the DKG protocol, a joint verification key <em class=\"mw\">vk<\/em> is generated. Also, each participant <em class=\"mw\">P<\/em>\u1d62 holds a value <em class=\"mw\">(i, sk<\/em>\u1d62<em class=\"mw\">)<\/em> that is their long-lived secret share and a verification key share <em class=\"mw\">vk<\/em>\u1d62<em class=\"mw\"> = sk<\/em>\u1d62<em class=\"mw\">*G<\/em>. Participant <em class=\"mw\">P<\/em>\u1d62\u2019s verification key share <em class=\"mw\">vk<\/em>\u1d62<em class=\"mw\"> <\/em>is used by other participants to verify the correctness of <em class=\"mw\">P<\/em>\u1d62\u2019s signature shares in the signing phase, while the verification key <em class=\"mw\">vk<\/em> is used by external parties to verify signatures issued by the group.<\/p>\n<p id=\"b003\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\"><strong class=\"ki iz\">FROST \u2014 threshold signing<\/strong>. We now introduce the signing protocol for FROST. This phase builds upon known techniques that employ additive secret sharing and share conversion to non-interactively generate the nonce for each signature. This phase also leverages binding techniques to avoid known forgery attacks without limiting concurrency.<\/p>\n<p id=\"0e32\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\">Our implementation is slightly adapted from the <a class=\"au le\" href=\"https:\/\/tools.ietf.org\/pdf\/draft-komlo-frost-00.pdf\" rel=\"noopener ugc nofollow\" target=\"_blank\">FROST draft<\/a>. In our implementation, we opted to <strong class=\"ki iz\">not<\/strong> use the signature aggregator role. Instead, each participant is a signature aggregator. This design is more secure: all the participants of the protocol verify what others have computed to achieve a higher level of security and reduce risk. In contrast with other open source libraries, as far as we know, we are the first to implement FROST <em class=\"mw\">without<\/em> the signature aggregator role. Furthermore, we have chosen <strong class=\"ki iz\">not<\/strong> to do the (one-time) preprocessing stage in order to speed up the implementation. In the preprocessing stage, each participant prepares a fixed number of EC point pairs for further use, which is run for a single time for multiple threshold signing phases. However, we take this stage as an additional round and only prepare a single pair of EC points, which means we run it every time for each threshold signing phase. In more detail, there are two major differences between our implementation and the original draft.<\/p>\n<p id=\"3017\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\">First, the signature aggregator, as described in the draft, validates messages that are broadcast by cosigners and computes the final signature. In our implementation, we do <strong class=\"ki iz\">not<\/strong> use such a role. Instead, each participant simply performs a broadcast in place of a signature aggregator performing coordination. Note that FROST can be instantiated without such a signature aggregator as stressed in the draft. Also, implementing it in a <em class=\"mw\">decentralized<\/em> way is more appropriate to Coinbase\u2019s <em class=\"mw\">multiparty computation<\/em> approach.<\/p>\n<p id=\"1bce\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\">Second, the protocol in the draft uses a preprocessing stage prior to signing, where each participant <em class=\"mw\">P<\/em>\u1d62 samples a sequence number, say <em class=\"mw\">Q<\/em>, of single-use nonces <em class=\"mw\">(d<\/em>\u1d62\u2c7c<em class=\"mw\">, e<\/em>\u1d62\u2c7c<em class=\"mw\">)<\/em>, computes and broadcasts pairs of public points <em class=\"mw\">(D<\/em>\u1d62\u2c7c<em class=\"mw\"> = d<\/em>\u1d62\u2c7c<em class=\"mw\">*G, E<\/em>\u1d62\u2c7c<em class=\"mw\"> = e<\/em>\u1d62\u2c7c<em class=\"mw\">*G)<\/em> for further use in subsequent signing rounds, where <em class=\"mw\">j = 1\u2026.Q<\/em>. This preprocessing stage is a once-for-all stage. That is, each participant can prepare a fixed number of EC point pairs, say <em class=\"mw\">Q<\/em>, and broadcast them to the signature aggregator, then the signature aggregator distributes these EC point pairs to all participants for further use. Once these pairs of EC points are used up, then these participants should run another preprocessing stage. Since we opted to not use such a signature aggregator role in our implementation, we have chosen instead to let each participant generate a single pair of EC points <em class=\"mw\">(D<\/em>\u1d62<em class=\"mw\">, E<\/em>\u1d62<em class=\"mw\">)<\/em>. Therefore, there is <strong class=\"ki iz\">no preprocessing stage<\/strong> in our implementation and thus there are 3 rounds in our threshold signing phase instead of 2. Also note that whether our implementation contains the preprocessing stage or not simply depends on how many EC point pairs are generated in signing round 1. If each participant generates a <em class=\"mw\">Q<\/em> number of EC point pairs in the signing round 1, then this round can be viewed as the preprocessing stage and our implementation becomes a 2-round signing protocol.<\/p>\n<p id=\"d871\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\">We describe how these three signing rounds work and give some technical details.<\/p>\n<p id=\"d759\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\"><strong class=\"ki iz\">Signing Round 1<\/strong>. Each participant <em class=\"mw\">P<\/em>\u1d62 begins by generating a single private nonce pair <em class=\"mw\">(d<\/em>\u1d62<em class=\"mw\">, e<\/em>\u1d62<em class=\"mw\">)<\/em> and corresponding pair of EC points <em class=\"mw\">(D<\/em>\u1d62<em class=\"mw\">, E<\/em>\u1d62<em class=\"mw\">)<\/em> and broadcasts this pair of points to all other participants. Each participant stores these pairs of EC points received for use later. Signing rounds 2 and 3 are the actual operations in which <em class=\"mw\">t-out-of-n<\/em> participants cooperate to create a valid Schnorr signature.<\/p>\n<p id=\"6b5a\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\"><strong class=\"ki iz\">Signing Round 2<\/strong>. To create a valid Schnorr signature, any <em class=\"mw\">t<\/em> participants work together to execute this round. The core technique behind this round is <strong class=\"ki iz\">t-out-of-t additive secret sharing<\/strong>. This technique creates the secret nonce <em class=\"mw\">k = SUM(k<\/em>\u1d62<em class=\"mw\">)<\/em>, which is the same value generated in the single-party Schnorr signing algorithm, and each <em class=\"mw\">k<\/em>\u1d62 is the share computed by participant <em class=\"mw\">P<\/em>\u1d62. To do this, each participant prepares the set of pairs of EC points <em class=\"mw\">B = (D<\/em>\u2081<em class=\"mw\">, E<\/em>\u2081<em class=\"mw\">)\u2026\u2026(D<\/em>\u209c<em class=\"mw\">, E<\/em>\u209c<em class=\"mw\">)<\/em> received in round 1, and then computes <em class=\"mw\">k<\/em>\u1d62<em class=\"mw\"> = d<\/em>\u1d62<em class=\"mw\">+e<\/em>\u1d62<em class=\"mw\">*r<\/em>\u1d62 , where <em class=\"mw\">r<\/em>\u1d62<em class=\"mw\">=H(i, m, B)<\/em> and <em class=\"mw\">H<\/em> is a hash function whose outputs are in the field <em class=\"mw\">Z<\/em>\u209a. Computing <em class=\"mw\">r<\/em>\u1d62 is important since it works as a <em class=\"mw\">binding value<\/em> for each participant to prevent the <a class=\"au le\" href=\"https:\/\/eprint.iacr.org\/2018\/417.pdf\" rel=\"noopener ugc nofollow\" target=\"_blank\">forgery attack<\/a>. Then each participant computes the commitment <em class=\"mw\">R<\/em>\u1d62<em class=\"mw\">=D<\/em>\u1d62<em class=\"mw\">+E<\/em>\u1d62<em class=\"mw\">*r<\/em>\u1d62 such that it binds the message <em class=\"mw\">m<\/em>, the set of signing participants and each participant\u2019s EC points to each signature share, such that signature shares for one message cannot be used for another. This prevents the forgery attack because attackers cannot combine signature shares across distinct signing operations or permute the set of signers or published points for each signer. The commitment for the set of signers is then simply <em class=\"mw\">R = SUM(R<\/em>\u1d62<em class=\"mw\">)<\/em>. As in single-party Schnorr signatures, each participant computes the challenge <em class=\"mw\">c = H(m, R)<\/em>.<\/p>\n<p id=\"d28b\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\">Having computed the challenge <em class=\"mw\">c<\/em>, each participant is able to compute the response <em class=\"mw\">z<\/em>\u1d62 to the challenge using the single-use nonces <em class=\"mw\">(d<\/em>\u1d62<em class=\"mw\">, e<\/em>\u1d62<em class=\"mw\">)<\/em> and the long-term secret shares <em class=\"mw\">sk<\/em>\u1d62, which are <em class=\"mw\">t-out-of-n<\/em> (degree <em class=\"mw\">t-1<\/em>) Shamir secret shares of the group\u2019s long-lived key <em class=\"mw\">sk<\/em>. One main observation that FROST leverages is that if <em class=\"mw\">k<\/em>\u1d62 are additive shares of <em class=\"mw\">k<\/em>, then each <em class=\"mw\">k<\/em>\u1d62<em class=\"mw\">\/L<\/em>\u1d62 are <em class=\"mw\">t-out-of-n<\/em> Shamir shares of <em class=\"mw\">k<\/em>, where <em class=\"mw\">L<\/em>\u1d62 is the Lagrange coefficient for participant <em class=\"mw\">P<\/em>\u1d62. That is, <em class=\"mw\">L<\/em>\u1d62<em class=\"mw\"> = prod(i\/(j-i)), where j = 1,\u2026,t, j \u2260i. <\/em>This observation is due to the work by Benaloh and Leichter [<a class=\"au le\" href=\"https:\/\/link.springer.com\/chapter\/10.1007\/0-387-34799-2_3\" rel=\"noopener ugc nofollow\" target=\"_blank\">BL88<\/a>] and the work by Cramer, Damgaard and Ishai [<a class=\"au le\" href=\"https:\/\/link.springer.com\/chapter\/10.1007\/978-3-540-30576-7_19\" rel=\"noopener ugc nofollow\" target=\"_blank\">CDI05<\/a>]. They present a non-interactive mechanism for participants to locally convert additive shares generated via the Benaloh and Leichter t-out-of-n secret sharing construction to Shamir\u2019s polynomial form. FROST uses the simplest t-out-of-t case of this transformation. Thus <em class=\"mw\">k<\/em>\u1d62<em class=\"mw\">\/L<\/em>\u1d62<em class=\"mw\">+sk<\/em>\u1d62<em class=\"mw\">*c<\/em> are degree <em class=\"mw\">t-1<\/em> Shamir secret shares of the correct response <em class=\"mw\">z = k+sk*c<\/em> for a plain (single-party) Schnorr signature. Using share conversion again and the value each participant has computed (namely, <em class=\"mw\">k<\/em>\u1d62<em class=\"mw\"> = d<\/em>\u1d62<em class=\"mw\">+e<\/em>\u1d62<em class=\"mw\">*r<\/em>\u1d62), we get that <em class=\"mw\">z<\/em>\u1d62<em class=\"mw\">=d<\/em>\u1d62<em class=\"mw\">+e<\/em>\u1d62<em class=\"mw\">*r<\/em>\u1d62<em class=\"mw\">+L<\/em>\u1d62<em class=\"mw\">*sk<\/em>\u1d62<em class=\"mw\">*c<\/em> are <em class=\"mw\">t-out-of-t<\/em> additive shares of <em class=\"mw\">z<\/em>. At the end of signing round 2, each participant broadcasts <em class=\"mw\">z<\/em>\u1d62 to other participants.<\/p>\n<p id=\"657e\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\"><strong class=\"ki iz\">Signing Round 3<\/strong>. After receiving <em class=\"mw\">z<\/em>\u1d62 from all other participants, each participant checks the consistency of these reported <em class=\"mw\">z<\/em>\u1d62, with their pair of EC points <em class=\"mw\">(D<\/em>\u1d62<em class=\"mw\">, E<\/em>\u1d62<em class=\"mw\">)<\/em> and their verification key share <em class=\"mw\">vk<\/em>\u1d62. This can be done by checking the equation <em class=\"mw\">z<\/em>\u1d62<em class=\"mw\">*G = R<\/em>\u1d62<em class=\"mw\">+c*L<\/em>\u1d62<em class=\"mw\">*vk<\/em>\u1d62. Once all <em class=\"mw\">z<\/em>\u1d62 are valid, then each participant computes <em class=\"mw\">z = SUM(z<\/em>\u1d62<em class=\"mw\">)<\/em> and output <em class=\"mw\">(z, c) <\/em>as the final Schnorr signature. This signature will verify properly to any party unaware that FROST was used to generate the signature, and can check it with the standard single-party Schnorr verification equation with <em class=\"mw\">vk<\/em> as the verification key. As we have mentioned, we do not use the signature aggregator role in our implementation. Thus, each participant works as a signature aggregator. Therefore, we let each participant <em class=\"mw\">self-verify<\/em> its own signature before outputting it.<\/p>\n<p id=\"6b5d\" class=\"pw-post-body-paragraph kg kh iy ki b kj md kl km kn me kp kq kr mf kt ku kv mg kx ky kz mh lb lc ld ir ga\">We referred to some known FROST implementations: two Rust implementations \u2014 one by <a class=\"au le\" href=\"https:\/\/github.com\/ZcashFoundation\/redjubjub\/blob\/main\/src\/frost.rs\" rel=\"noopener ugc nofollow\" target=\"_blank\">ZCash foundation<\/a> and another by <a class=\"au le\" href=\"https:\/\/github.com\/isislovecruft\/frost-dalek\" rel=\"noopener ugc nofollow\" target=\"_blank\">frost-dalek <\/a>\u2014 but they are not appropriate to our tech stack. One <a class=\"au le\" href=\"https:\/\/github.com\/taurusgroup\/frost-ed25519\" rel=\"noopener ugc nofollow\" target=\"_blank\">Golang implementation<\/a> is from the Taurus group, but unfortunately this Go implementation is not ready for production use and has not been externally audited. As a result, we decided to implement the protocol in-house.<\/p>\n<p id=\"3310\" class=\"pw-post-body-paragraph kg kh iy ki b kj kk kl km kn ko kp kq kr ks kt ku kv kw kx ky kz la lb lc ld ir ga\">One feature of FROST signing is that each participant must know Lagrange coefficients for each participant in order to compute <em class=\"mw\">z<\/em>\u1d62. This is uncommon in other threshold signature protocols that use Feldman verifiable secret sharing as a sub-protocol, so there are few existing Go libraries to support THIS. Most existing libraries support generating secret shares, polynomials, and their interpolation, but do not support Lagrange coefficient computation. To fill in this technical gap, we implemented participants\u2019 Lagrange coefficients given <em class=\"mw\">arbitrary<\/em> <em class=\"mw\">t<\/em> participant IDs as input. Before running the threshold signing protocol, it takes input IDs of the <em class=\"mw\">t<\/em> participants and generates all Lagrange coefficients. As the FROST draft suggests, we assign these coefficients to each participant before signing to improve performance.<\/p>\n<p id=\"1f81\" class=\"pw-post-body-paragraph kg kh iy ki b kj md kl km kn me kp kq kr mf kt ku kv mg kx ky kz mh lb lc ld ir ga\">FROST is a flexible, round-optimized Schnorr threshold signature scheme that minimizes the network overhead of producing Schnorr signatures in a threshold setting while allowing for unrestricted parallelism of signing operations and only a threshold number of signing participants. We introduce FROST, highlight its features, and describe it in a fully decentralized approach (i.e., without any third-party signature aggregator). This post exposes what Coinbase discovered while evaluating and implementing the FROST protocol and we look forward to adding it to our suite of threshold signing services.<\/p>\n<\/div>\n<p><a href=\"https:\/\/medium.com\/the-coinbase-blog\/frost-flexible-round-optimized-schnorr-threshold-signatures-b2e950164ee1?source=rss----c114225aeaf7--bitcoin\">Source link <\/a><br \/>\n<br \/><\/p>\n","protected":false},"excerpt":{"rendered":"<p>(Originally posted on : Bitcoin in The Coinbase Blog on Medium ) By Daniel Zhou FROST is a round-optimal threshold Schnorr signature protocol. Here we introduce why Coinbase decided to use FROST, what FROST is, and what we discovered while evaluating FROST. In order to improve efficiency of Coinbase\u2019s threshold-signing systems, we decided to explore [&hellip;]<\/p>\n","protected":false},"author":20,"featured_media":14697,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0},"categories":[32],"tags":[],"_links":{"self":[{"href":"https:\/\/crowdfundjunction.com\/blog\/wp-json\/wp\/v2\/posts\/14696"}],"collection":[{"href":"https:\/\/crowdfundjunction.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/crowdfundjunction.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/crowdfundjunction.com\/blog\/wp-json\/wp\/v2\/users\/20"}],"replies":[{"embeddable":true,"href":"https:\/\/crowdfundjunction.com\/blog\/wp-json\/wp\/v2\/comments?post=14696"}],"version-history":[{"count":0,"href":"https:\/\/crowdfundjunction.com\/blog\/wp-json\/wp\/v2\/posts\/14696\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/crowdfundjunction.com\/blog\/wp-json\/wp\/v2\/media\/14697"}],"wp:attachment":[{"href":"https:\/\/crowdfundjunction.com\/blog\/wp-json\/wp\/v2\/media?parent=14696"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/crowdfundjunction.com\/blog\/wp-json\/wp\/v2\/categories?post=14696"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/crowdfundjunction.com\/blog\/wp-json\/wp\/v2\/tags?post=14696"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}