summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorErik Aronesty <erik@q32.com>2018-07-09 12:33:01 -0400
committerbitcoindev <bitcoindev@gnusha.org>2018-07-09 16:33:06 +0000
commit13fac4fa15ffa8f1fb2603a784f746359aed79e8 (patch)
treecd0e7eaa516806d2182638817392470c416a9cc8
parent77fe5c7dd01c7f8983e4b85927c9ba10f3b9c6fa (diff)
downloadpi-bitcoindev-13fac4fa15ffa8f1fb2603a784f746359aed79e8.tar.gz
pi-bitcoindev-13fac4fa15ffa8f1fb2603a784f746359aed79e8.zip
Re: [bitcoin-dev] Multiparty signatures
Diffstat
-rw-r--r--d3/d9447756a055c67183efca4101bd790c803434263
1 files changed, 263 insertions, 0 deletions
diff --git a/d3/d9447756a055c67183efca4101bd790c803434 b/d3/d9447756a055c67183efca4101bd790c803434
new file mode 100644
index 000000000..491812dc8
--- /dev/null
+++ b/d3/d9447756a055c67183efca4101bd790c803434
@@ -0,0 +1,263 @@
+Return-Path: <earonesty@gmail.com>
+Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
+ [172.17.192.35])
+ by mail.linuxfoundation.org (Postfix) with ESMTPS id 4A128D5D
+ for <bitcoin-dev@lists.linuxfoundation.org>;
+ Mon, 9 Jul 2018 16:33:06 +0000 (UTC)
+X-Greylist: whitelisted by SQLgrey-1.7.6
+Received: from mail-wr1-f53.google.com (mail-wr1-f53.google.com
+ [209.85.221.53])
+ by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 95F8878D
+ for <bitcoin-dev@lists.linuxfoundation.org>;
+ Mon, 9 Jul 2018 16:33:03 +0000 (UTC)
+Received: by mail-wr1-f53.google.com with SMTP id g6-v6so2735911wrp.0
+ for <bitcoin-dev@lists.linuxfoundation.org>;
+ Mon, 09 Jul 2018 09:33:03 -0700 (PDT)
+DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
+ h=mime-version:sender:in-reply-to:references:from:date:message-id
+ :subject:to:cc;
+ bh=BOoo02vh90v4RkLcjyw5VvBuMVCvbdJ96wsoKKAUd9A=;
+ b=JDra/zHR1qpgWnuz24ylTZ19Yx/6TEuXxaNB2nwl2IyZyaAtx0bWzFzvi9ixQiZZKa
+ 0O2F6dF/g5yKwS1Xmum5BUb0d6/vXP4C5cgsyeIzzh0kieEBhGUFjlrNXJfOSobcai1g
+ h4vvvzePn1ekORMZ0MrveMVYr80igcc6AvKXiPqocrUEOTw27Rz4eAAJ3DHgyDq83QL8
+ DHLsSRbZMzgfAXxDBj49Z6owg3g1JwjI8AqTFCv3kUZMEJmvtTfgkmY+iTFDSaGUjwTi
+ aVlqPcUbJisexqBp61zGammh600/Zq8iy7QiFKAj+XeVnULBRGekHyZLLYGr8na5K1+i
+ poXw==
+DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
+ d=q32-com.20150623.gappssmtp.com; s=20150623;
+ h=mime-version:sender:in-reply-to:references:from:date:message-id
+ :subject:to:cc;
+ bh=BOoo02vh90v4RkLcjyw5VvBuMVCvbdJ96wsoKKAUd9A=;
+ b=tSLLo4Btvsx4ZKNbwSSB+XJkEwNHe06UCPnl7bI0DDdKE4KejcUROIiY/bWJIR/XAg
+ dKenJe7fLqgqfe4WRO1ZIrixn63lI2xnXHpVG690PeT0xGcRyqR2kvclMLKmMUphs8pq
+ YbIAECrOLYK9KUiGHWJjuDX2IHSJG4Mk2UBu8DOodpObsQRVum8Yy13YG3Cusu+0p32V
+ oEBHqzULylU2R38FU+qTpZB71tLrfV02YSKkig4icF3KX4C5wONqPv4ygeorjSsfcyhD
+ JBx2HxyNgM17BqyUfmRBhmOeeWCif8qfvPRdlfjyMU2sFBukt4zSlI1VbqY4GwR8+kR4
+ zoIw==
+X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
+ d=1e100.net; s=20161025;
+ h=x-gm-message-state:mime-version:sender:in-reply-to:references:from
+ :date:message-id:subject:to:cc;
+ bh=BOoo02vh90v4RkLcjyw5VvBuMVCvbdJ96wsoKKAUd9A=;
+ b=ElNoHyJutWu1yp3IlRxSFKEKLWEiUD5mJ0Lp9I0RNljyuwa36qObFsQnRiXMrn+IFH
+ 6C0OEbgUksBm0dWqjFOg5FHB7oMTbvLEPZJ2aBzKbcnhjsmDA42sikmFGrJNLxQOOqXC
+ OCpr8JxvVgMIcYNKLmcYfaW1F8FKgm2HWl9LSptA90BPe159hPpGi3emK+VI6hqu4tUt
+ Zw9i+uy6b+SN0qC/NS2KYD71ElB2cwPhxw8IbOf/h958AxdArRyChJqLaJCKtPO+yTMn
+ cBYNR9yhVQJ34gbCPvmQkFcP0eL5Ttufp34t0MEAuGFCR7XBPPiPcaf43u7zNYDXTnwh
+ tfJA==
+X-Gm-Message-State: APt69E19KoVGm8kpJ5vMmMFSAADCpXeqoe33Z96kOYIV2GnHT0pDZQwr
+ Ahzne+LZhUMw5S+BA9FMinr7H96kEnXlYpU8u7o+0FM=
+X-Google-Smtp-Source: AAOMgpe5SJ8s8Y3Jd3JU+XbivDDzKxOEuB43ZN/8YCE6tORyAQFbbvhHSJeYQ4yRnmgqHoTPN22+Spxb63R0NPTT1ys=
+X-Received: by 2002:adf:9d1c:: with SMTP id
+ k28-v6mr16251762wre.29.1531153982115;
+ Mon, 09 Jul 2018 09:33:02 -0700 (PDT)
+MIME-Version: 1.0
+Sender: earonesty@gmail.com
+Received: by 2002:a1c:b786:0:0:0:0:0 with HTTP;
+ Mon, 9 Jul 2018 09:33:01 -0700 (PDT)
+In-Reply-To: <CAAS2fgSmA02s6Vdk_FYv6NJ4smLBgxnuT4jRYU44G7=bbzv2MA@mail.gmail.com>
+References: <CAJowKgLrSe77sqO2iB7mYboo_HW=YjO4=AFdv7L5FUi2vygMiQ@mail.gmail.com>
+ <08201f2292587821e6d23f6cc201d95e6e5ad2cd.camel@timruffing.de>
+ <CAAS2fgSPUc7xRq36rZ9BVLjUTdd152Fgho4sjJXLhfrc71vPMw@mail.gmail.com>
+ <CAJowKgL-nRcruXhWdGWrT4x+oV7i3jYST2Wa3bF5m6iT_mOyMw@mail.gmail.com>
+ <CAPg+sBjdu4mnda-P0y7Ddu-rN7a1GiUt0hY_wYGsy_bJLKOYMA@mail.gmail.com>
+ <CAJowKgLSQZ1LrZayDi7EFc-NSfK_AD+zBdyaF7jBeQRP7tOwYQ@mail.gmail.com>
+ <CAPg+sBizrx20XShpeZRvZd4bfq1=E+MFUDmSC9X-xK1CSbV5kQ@mail.gmail.com>
+ <CAJowKg+=7nS4gNmtc8a4-2cu1uCOPqxjfchFwDVqUciKNMUYWQ@mail.gmail.com>
+ <CAJowKgJ3K=wmCEtoZXJZhrnnA8XJcHYg788KP+7MCeP4Mxf-0w@mail.gmail.com>
+ <CAAS2fgSmA02s6Vdk_FYv6NJ4smLBgxnuT4jRYU44G7=bbzv2MA@mail.gmail.com>
+From: Erik Aronesty <erik@q32.com>
+Date: Mon, 9 Jul 2018 12:33:01 -0400
+X-Google-Sender-Auth: XGgsM8lAxD4xafvg61uBCXqgVgA
+Message-ID: <CAJowKgJjQ8EGgbCurOSjTh8ij42_BVeD6dE0y67tzN0Zop3pyg@mail.gmail.com>
+To: Gregory Maxwell <greg@xiph.org>
+Content-Type: multipart/alternative; boundary="000000000000336246057093912d"
+X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
+ DKIM_VALID, FREEMAIL_FROM, HTML_MESSAGE,
+ RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
+X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
+ smtp1.linux-foundation.org
+X-Mailman-Approved-At: Mon, 09 Jul 2018 16:34:09 +0000
+Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
+Subject: Re: [bitcoin-dev] Multiparty signatures
+X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
+X-Mailman-Version: 2.1.12
+Precedence: list
+List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
+List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
+ <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
+List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
+List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
+List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
+List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
+ <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
+X-List-Received-Date: Mon, 09 Jul 2018 16:33:06 -0000
+
+--000000000000336246057093912d
+Content-Type: text/plain; charset="UTF-8"
+
+> More closely than what?
+
+More closely than musig.
+
+In fact there's no need to distribute the hash at all if you have the first
+round, you can leave the schnorr construction... thanks for the feedback.
+I literally can't think about this stuff without someone asking questions.
+
+1. For those who asked, the construction from section 7.1 of this paper
+describes how to use lagrange interpolation in a group context:
+ http://crypto.stanford.edu/~dabo/papers/homprf.pdf
+
+2. Using shamir interpolation is cleaner than the additive multisig
+
+3. Taking your comments into consideration, I think it's possible to remove
+the point multiplication instead of a hash and stick to Schnorr "as is",
+and still cut out all but one online round:
+
+OK, so this is a new Multisig variant of schnorr with fewer rounds... I
+know this is possible, I just needed to have that back and forth... sorry:
+
+For sake of terminology and typing in ascii, I'm using ^ to mean "point
+multiplcation"
+
+Each party:
+
+1. Has a public g^x
+2. Computes and broadcasts g^k' ... where k' is a random number
+3. Computes r = g^k using lagrange interpolation (see
+http://crypto.stanford.edu/~dabo/papers/homprf.pdf)
+4. Computes H(r || M), as per standard schnorr
+5. Computes s' = k' - xe , as per standard schnorr .. except k' is a "share"
+6. Publish (s', e)
+
+Verification:
+
+With m of n share-signatures:
+
+1. Use lagrange interpolation on m of n s' shares to get s
+2. Standard schnorr verification
+
+- Erik
+
+
+
+
+On Mon, Jul 9, 2018 at 11:59 AM, Gregory Maxwell <greg@xiph.org> wrote:
+
+> On Mon, Jul 9, 2018 at 3:02 PM, Erik Aronesty via bitcoin-dev
+> <bitcoin-dev@lists.linuxfoundation.org> wrote:
+> > with
+> > security assumptions that match the original Schnorr construction more
+> > closely,
+>
+> More closely than what?
+>
+
+--000000000000336246057093912d
+Content-Type: text/html; charset="UTF-8"
+Content-Transfer-Encoding: quoted-printable
+
+<div dir=3D"ltr">&gt;
+
+<span style=3D"font-size:12.8px;text-decoration-style:initial;text-decorati=
+on-color:initial;float:none;display:inline">More closely than what?</span><=
+div class=3D"gmail-m_8217130892002629636gmail-yj6qo" style=3D"font-size:12.=
+8px;text-decoration-style:initial;text-decoration-color:initial"></div><br =
+class=3D"gmail-m_8217130892002629636gmail-Apple-interchange-newline"><div>M=
+ore closely than musig.=C2=A0 =C2=A0</div><div><br></div><div>In fact there=
+&#39;s no need to distribute the hash at all if you have the first round, y=
+ou can leave the schnorr construction... thanks for the feedback.=C2=A0 I l=
+iterally can&#39;t think about this stuff without someone asking questions.=
+</div><div><br></div><div>1. For those who asked, the construction from sec=
+tion 7.1 of this paper describes how to use lagrange interpolation in a gro=
+up context:</div><div>=C2=A0 =C2=A0 =C2=A0 =C2=A0 <a href=3D"http://crypto.=
+stanford.edu/~dabo/papers/homprf.pdf">http://crypto.stanford.edu/~dabo/pape=
+rs/homprf.pdf</a><br></div><div><br></div><div>2. Using shamir interpolatio=
+n is cleaner than the additive multisig</div><div><br></div><div>3. Taking =
+your comments into consideration, I think it&#39;s possible to remove the p=
+oint multiplication instead of a hash and stick to Schnorr &quot;as is&quot=
+;, and still cut out all but one online round:</div><div><br></div><div>OK,=
+ so this is a new Multisig variant of schnorr with fewer rounds... I know t=
+his is possible, I just needed to have that back and forth... sorry:<br></d=
+iv><div><br></div><div>
+
+<div style=3D"font-size:small;text-decoration-style:initial;text-decoration=
+-color:initial">For sake of terminology and typing in ascii, I&#39;m using =
+^ to mean &quot;point multiplcation&quot;</div><div><br></div>Each party:<b=
+r class=3D"gmail-Apple-interchange-newline"></div><div><br></div><div>1. Ha=
+s a public g^x=C2=A0</div><div>2. Computes and broadcasts g^k&#39; ... wher=
+e k&#39; is a random number</div><div>3. Computes r =3D g^k using lagrange =
+interpolation (see=C2=A0
+
+<span style=3D"font-size:small;background-color:rgb(255,255,255);text-decor=
+ation-style:initial;text-decoration-color:initial;float:none;display:inline=
+"><a href=3D"http://crypto.stanford.edu/~dabo/papers/homprf.pdf">http://cry=
+pto.stanford.edu/~dabo/papers/homprf.pdf</a>)</span></div><div><span style=
+=3D"font-size:small;background-color:rgb(255,255,255);text-decoration-style=
+:initial;text-decoration-color:initial;float:none;display:inline">4. Comput=
+es H(r || M), as per standard schnorr</span></div><div><span style=3D"font-=
+size:small;background-color:rgb(255,255,255);text-decoration-style:initial;=
+text-decoration-color:initial;float:none;display:inline">5. Computes s&#39;=
+ =3D k&#39; - xe
+
+<span style=3D"text-decoration-style:initial;text-decoration-color:initial;=
+float:none;display:inline">, as per standard schnorr .. except k&#39; is a =
+&quot;share&quot;</span></span></div><div><span style=3D"font-size:small;ba=
+ckground-color:rgb(255,255,255);text-decoration-style:initial;text-decorati=
+on-color:initial;float:none;display:inline"><span style=3D"text-decoration-=
+style:initial;text-decoration-color:initial;float:none;display:inline">6. P=
+ublish (s&#39;, e)</span></span></div><div><span style=3D"font-size:small;b=
+ackground-color:rgb(255,255,255);text-decoration-style:initial;text-decorat=
+ion-color:initial;float:none;display:inline"><span style=3D"text-decoration=
+-style:initial;text-decoration-color:initial;float:none;display:inline"><br=
+></span></span></div><div><span style=3D"font-size:small;background-color:r=
+gb(255,255,255);text-decoration-style:initial;text-decoration-color:initial=
+;float:none;display:inline"><span style=3D"text-decoration-style:initial;te=
+xt-decoration-color:initial;float:none;display:inline">Verification:</span>=
+</span></div><div><span style=3D"font-size:small;background-color:rgb(255,2=
+55,255);text-decoration-style:initial;text-decoration-color:initial;float:n=
+one;display:inline"><span style=3D"text-decoration-style:initial;text-decor=
+ation-color:initial;float:none;display:inline"><br></span></span></div><div=
+><span style=3D"font-size:small;background-color:rgb(255,255,255);text-deco=
+ration-style:initial;text-decoration-color:initial;float:none;display:inlin=
+e"><span style=3D"text-decoration-style:initial;text-decoration-color:initi=
+al;float:none;display:inline">With m of n share-signatures:</span></span></=
+div><div><span style=3D"font-size:small;background-color:rgb(255,255,255);t=
+ext-decoration-style:initial;text-decoration-color:initial;float:none;displ=
+ay:inline"><span style=3D"text-decoration-style:initial;text-decoration-col=
+or:initial;float:none;display:inline"><br></span></span></div><div><span st=
+yle=3D"font-size:small;background-color:rgb(255,255,255);text-decoration-st=
+yle:initial;text-decoration-color:initial;float:none;display:inline"><span =
+style=3D"text-decoration-style:initial;text-decoration-color:initial;float:=
+none;display:inline">1. Use lagrange interpolation on m of n s&#39; shares =
+to get s</span></span></div><div><span style=3D"font-size:small;background-=
+color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:=
+initial;float:none;display:inline"><span style=3D"text-decoration-style:ini=
+tial;text-decoration-color:initial;float:none;display:inline">2. Standard s=
+chnorr verification</span></span></div><div><br></div><div>- Erik</div><div=
+><span style=3D"font-size:small;background-color:rgb(255,255,255);text-deco=
+ration-style:initial;text-decoration-color:initial;float:none;display:inlin=
+e"><span style=3D"text-decoration-style:initial;text-decoration-color:initi=
+al;float:none;display:inline"><br></span></span></div><div><span style=3D"f=
+ont-size:small;background-color:rgb(255,255,255);text-decoration-style:init=
+ial;text-decoration-color:initial;float:none;display:inline"><span style=3D=
+"text-decoration-style:initial;text-decoration-color:initial;float:none;dis=
+play:inline"><br></span></span></div><div><br></div></div><div class=3D"gma=
+il_extra"><br><div class=3D"gmail_quote">On Mon, Jul 9, 2018 at 11:59 AM, G=
+regory Maxwell <span dir=3D"ltr">&lt;<a href=3D"mailto:greg@xiph.org" targe=
+t=3D"_blank">greg@xiph.org</a>&gt;</span> wrote:<br><blockquote class=3D"gm=
+ail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-le=
+ft:1ex"><span class=3D"">On Mon, Jul 9, 2018 at 3:02 PM, Erik Aronesty via =
+bitcoin-dev<br>
+&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@li=
+sts.<wbr>linuxfoundation.org</a>&gt; wrote:<br>
+&gt; with<br>
+&gt; security assumptions that match the original Schnorr construction more=
+<br>
+&gt; closely,<br>
+<br>
+</span>More closely than what?<br>
+</blockquote></div><br></div>
+
+--000000000000336246057093912d--
+
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-13 11:06:59 +0000