path: root/d3/d9447756a055c67183efca4101bd790c803434

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--