path: root/ee/639ccfe4871400c0673989066bcbc44a77a89f

Return-Path: <bram@chia.net>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 02A1710A3
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 28 Mar 2018 03:19:51 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f45.google.com (mail-wm0-f45.google.com [74.125.82.45])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id F36785E1
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 28 Mar 2018 03:19:49 +0000 (UTC)
Received: by mail-wm0-f45.google.com with SMTP id r82so2380872wme.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 27 Mar 2018 20:19:49 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=chia-net.20150623.gappssmtp.com; s=20150623;
	h=mime-version:in-reply-to:references:from:date:message-id:subject:to
	:cc; bh=sWkS5qjelctbzUSDXZvXUk2oz7ubalVCWmQxkip4JSQ=;
	b=QFbmPJc/yL/GdgV+JCxpMDufoPsSzsVWlPBdksn0jVkJ5GkZrmfaAHkz0bPjv5fHbu
	j9YvfUaE5lnPai7aQCGBRNfjQhjFwLwLacwhygPGOqLdOz+HXu/CGFKCFSQGIHYixPwi
	IjHXxrZqCi+q61yN9pZmuZjF6ZaAy80g69kNxlT0rAcpC5z3Wll9evgnhaZOwE7UIjZY
	7kfK5nVh7wn1quVilRcTA/1+gGunXDHZOTy2m/mkKsg7wiVerTzMiikMdTGXJlzOykE9
	yoo25yI0qowuphURPKNpu9ppDeQvRfDJfSOo3n/6V1oVEX1OT/ydZnVQGi9cxFwzHKKO
	umZw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:mime-version:in-reply-to:references:from:date
	:message-id:subject:to:cc;
	bh=sWkS5qjelctbzUSDXZvXUk2oz7ubalVCWmQxkip4JSQ=;
	b=jbhJjJ2UopvXhqhfHuyZW1cmscglrdrxrOsyZEgz0wlChFXDFTbRkbPJIUg6YJ3lUJ
	3Ulj7RcntjcCiDVHieoimn6GVJc2yB0NZrZwr+1c+6HtMRKOnNWgtnrVziGOEt6oCpPo
	eYZYY6Fdk5vRyKv6nlY6W7rP0UIgg6Ptx6cOONVuAEYO31sWG+4bUx2ZKlAnykwKYs0x
	NLuntZynaQSCTmtTAllcAZRk1QzK4IlfA02lMC48SAYdEjHqMdRaH4losSobOBlaqrWX
	R9yBlTx4stQOZwqVvlxlE745KP6Cc28DjVDzGF3vZvoDiP9r+36T3GH8qrpO8/O8kNsg
	QD/Q==
X-Gm-Message-State: AElRT7FJBnfvTivJ1DxZFQ9zWFJuVGshK3sJ8sYm76s8/tODsBy646lr
	WtwDJ3ZMfY9KE+Sq6gH+GEB9NMXwCbmGotAA/s06L+tvq0g=
X-Google-Smtp-Source: AIpwx4/rImW2Pz1Z5e+SOMR/Dvboc1oVieJHzMO+/xI+NaYwDPhCgucihNL/r1kVvTBWQpPUVfyuoPIvjBxLQGPFAQ4=
X-Received: by 10.28.175.140 with SMTP id y134mr733230wme.139.1522207188593;
	Tue, 27 Mar 2018 20:19:48 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.28.29.78 with HTTP; Tue, 27 Mar 2018 20:19:48 -0700 (PDT)
X-Originating-IP: [65.204.128.202]
In-Reply-To: <20180327063433.GA24123@erisian.com.au>
References: <CAHUJnBAQwLfmvLyApcw8dKz1u8xX1KmdjiUmzSHXyw7npWUXHQ@mail.gmail.com>
	<20180327063433.GA24123@erisian.com.au>
From: Bram Cohen <bram@chia.net>
Date: Tue, 27 Mar 2018 20:19:48 -0700
Message-ID: <CAHUJnBBkXvFwgJH7OYkR1FWCCgerMH4SaUGv2kN3c54vqZFomg@mail.gmail.com>
To: Anthony Towns <aj@erisian.com.au>
Content-Type: multipart/alternative; boundary="001a11444cd2c03cf90568707ab2"
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, 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: Wed, 28 Mar 2018 03:59:43 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Soft-forks and schnorr signature aggregation
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: Wed, 28 Mar 2018 03:19:51 -0000

--001a11444cd2c03cf90568707ab2
Content-Type: text/plain; charset="UTF-8"

On Mon, Mar 26, 2018 at 11:34 PM, Anthony Towns <aj@erisian.com.au> wrote:

> On Wed, Mar 21, 2018 at 05:47:01PM -0700, Bram Cohen via bitcoin-dev wrote:
> > [...] Most unused opcodes should be reclaimed as RETURN_VALID,
> > but there should still be one OP_NOP and there should be a 'real'
> RETURN_VALID,
> > which (a) is guaranteed to not be soft forked into something else in the
> > future, and (b) doesn't have any parsing weirdness.
>
> What's the reason for those? I could see an argument for RETURN_VALID, I
> guess:
>
>   confA IF condB IF condC IF [pathA] RETURN_VALID ENDIF ENDIF ENDIF [pathB]
>
> is probably simpler and saves 3 bytes compared to:
>
>   1 condA IF condB IF condC IF [pathA] NOT ENDIF ENDIF ENDIF IF [pathB]
> ENDIF
>
> but that doesn't seem crazy compelling?


Mostly yes it's for that case and also for:

   condA IF RETURN_VALID ENDIF condb IF RETURN_VALID ENDIF condc

Technically that can be done with fewer opcodes using OP_BOOLOR but maybe
in the future there will be some incentive for short circuit evaluation

But there's also the general principle that it's only one opcode and if
there are a lot of things which look like RETURN_VALID there should be one
thing which actually is RETURN_VALID


> I don't see a reason to just keep one OP_NOP though.
>

Mostly based on momentum because there are several of them there right now.
If noone else wants to defend it I won't either.


> > By far the most expedient option is (e) cause a RETURN_VALID at parse
> time.
> > There's even precedent for this sort of behavior in the other direction
> with
> > disabled opcodes causing failure at parse time even if they aren't being
> > executed.
>
> You're probably right. That still doesn't let you implement intercal's
> COMEFROM statement as a new opcode, of course. :)
>

That can be in the hardfork wishlist :-)


> > A lot can be said about all the options, but one thing I feel like
> snarking
> > about is that if you get rid of IFs using MAST, then it's highly unclear
> > whether OP_DEPTH should be nuked as well. My feeling is that it should
> and that
> > strict parsing should require that the bottom thing in the witness gets
> > referenced at some point.
>
> I guess when passing the script you could perhaps check if each witness
> item could have been replaced with OP_FALSE or OP_1 and still get the
> same result, and consider the transaction non-standard if so?
>

Essentially all opcodes including OP_PICK make clear at runtime how deep
they go and anything below the max depth can be safely eliminated (or used
as grounds for rejecting in strict mode). The big exception is OP_DEPTH
which totally mangles the assumptions. It's trivial to make scripts which
use OP_DEPTH which become invalid with things added below the stack then go
back to being valid again with more things added even though the individual
items are never even accessed.


>
> > Hacking in a multisig opcode isn't a horrible idea, but it is very stuck
> > specifically on m-of-n and doesn't support more complex formulas for how
> > signatures can be combined, which makes it feel hacky and weird.
>
> Hmm? The opcode I suggested works just as easily with arbitrary formulas,
> eg, "There must be at least 1 signer from pka{1,2,3}, and 3 signers all
> up, except each of pkb{1,2,3,4,5,6} only counts for half":
>
>   0 pkb6 pkb5 pkb4 pkb3 pkb2 pkb1 pka3 pka2 pka1 9 CHECK_AGGSIG_VERIFY
>     (declare pubkeys)
>   0b111 CHECK_AGG_SIGNERS VERIFY
>     (one of pka{1,2,3} must sign)
>   0b001 CHECK_AGG_SIGNERS
>   0b010 CHECK_AGG_SIGNERS ADD
>   0b100 CHECK_AGG_SIGNERS ADD
>   DUP ADD
>     (pka{1,2,3} count double)
>   0b000001000 CHECK_AGG_SIGNERS ADD
>   0b000010000 CHECK_AGG_SIGNERS ADD
>   0b000100000 CHECK_AGG_SIGNERS ADD
>   0b001000000 CHECK_AGG_SIGNERS ADD
>   0b010000000 CHECK_AGG_SIGNERS ADD
>   0b100000000 CHECK_AGG_SIGNERS ADD
>     (pkb{1..6} count single)
>   6 EQUAL
>     (summing to a total of 3 doubled)
>
> Not sure that saves it from being "hacky and weird" though...
>

That is very hacky and weird. Doing MAST on lots of possibilities is always
reasonably elegant, and it only gets problematic when the number of
possibilities is truly massive.

It's also the case that BLS can support complex key agreement schemes
without even giving away that it isn't a simple single signature. Just
saying.

--001a11444cd2c03cf90568707ab2
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On M=
on, Mar 26, 2018 at 11:34 PM, Anthony Towns <span dir=3D"ltr">&lt;<a href=
=3D"mailto:aj@erisian.com.au" target=3D"_blank">aj@erisian.com.au</a>&gt;</=
span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8e=
x;border-left:1px #ccc solid;padding-left:1ex">On Wed, Mar 21, 2018 at 05:4=
7:01PM -0700, Bram Cohen via bitcoin-dev wrote:<br>
&gt; [...] Most unused opcodes should be reclaimed as RETURN_VALID,<br>
<span class=3D"">&gt; but there should still be one OP_NOP and there should=
 be a &#39;real&#39; RETURN_VALID,<br>
&gt; which (a) is guaranteed to not be soft forked into something else in t=
he<br>
&gt; future, and (b) doesn&#39;t have any parsing weirdness.<br>
<br>
</span>What&#39;s the reason for those? I could see an argument for RETURN_=
VALID, I guess:<br>
<br>
=C2=A0 confA IF condB IF condC IF [pathA] RETURN_VALID ENDIF ENDIF ENDIF [p=
athB]<br>
<br>
is probably simpler and saves 3 bytes compared to:<br>
<br>
=C2=A0 1 condA IF condB IF condC IF [pathA] NOT ENDIF ENDIF ENDIF IF [pathB=
] ENDIF<br>
<br>
but that doesn&#39;t seem crazy compelling?</blockquote><div><br></div><div=
><span style=3D"color:rgb(34,34,34);font-family:arial,sans-serif;font-size:=
small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:nor=
mal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;=
text-transform:none;white-space:normal;word-spacing:0px;background-color:rg=
b(255,255,255);text-decoration-style:initial;text-decoration-color:initial;=
float:none;display:inline">Mostly yes it&#39;s for that case and a</span>ls=
o for:=C2=A0</div><div><br></div><div>=C2=A0 =C2=A0condA IF RETURN_VALID EN=
DIF condb IF RETURN_VALID ENDIF condc</div><div><br></div><div>Technically =
that can be done with fewer opcodes using OP_BOOLOR but maybe in the future=
 there will be some incentive for short circuit evaluation</div><div><br></=
div><div>But there&#39;s also the general principle that it&#39;s only one =
opcode and if there are a lot of things which look like RETURN_VALID there =
should be one thing which actually is RETURN_VALID</div><div>=C2=A0</div><b=
lockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px =
#ccc solid;padding-left:1ex"> I don&#39;t see a reason to just keep one OP_=
NOP though.<br></blockquote><div><br></div><div>Mostly based on momentum be=
cause there are several of them there right now. If noone else wants to def=
end it I won&#39;t either.</div><div>=C2=A0</div><blockquote class=3D"gmail=
_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:=
1ex"><span class=3D"">&gt; By far the most expedient option is (e) cause a =
RETURN_VALID at parse time.<br>
&gt; There&#39;s even precedent for this sort of behavior in the other dire=
ction with<br>
&gt; disabled opcodes causing failure at parse time even if they aren&#39;t=
 being<br>
&gt; executed.<br>
<br>
</span>You&#39;re probably right. That still doesn&#39;t let you implement =
intercal&#39;s<br>
COMEFROM statement as a new opcode, of course. :)<br></blockquote><div><br>=
</div><div>That can be in the hardfork wishlist :-)</div><div>=C2=A0</div><=
blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px=
 #ccc solid;padding-left:1ex"><span class=3D"">&gt; A lot can be said about=
 all the options, but one thing I feel like snarking<br>
&gt; about is that if you get rid of IFs using MAST, then it&#39;s highly u=
nclear<br>
&gt; whether OP_DEPTH should be nuked as well. My feeling is that it should=
 and that<br>
&gt; strict parsing should require that the bottom thing in the witness get=
s<br>
&gt; referenced at some point.<br>
<br>
</span>I guess when passing the script you could perhaps check if each witn=
ess<br>
item could have been replaced with OP_FALSE or OP_1 and still get the<br>
same result, and consider the transaction non-standard if so?<br></blockquo=
te><div><br></div><div>Essentially all opcodes including OP_PICK make clear=
 at runtime how deep they go and anything below the max depth can be safely=
 eliminated (or used as grounds for rejecting in strict mode). The big exce=
ption is OP_DEPTH which totally mangles the assumptions. It&#39;s trivial t=
o make scripts which use OP_DEPTH which become invalid with things added be=
low the stack then go back to being valid again with more things added even=
 though the individual items are never even accessed.</div><div>=C2=A0</div=
><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1=
px #ccc solid;padding-left:1ex">
<span class=3D""><br>
&gt; Hacking in a multisig opcode isn&#39;t a horrible idea, but it is very=
 stuck<br>
&gt; specifically on m-of-n and doesn&#39;t support more complex formulas f=
or how<br>
&gt; signatures can be combined, which makes it feel hacky and weird.<br>
<br>
</span>Hmm? The opcode I suggested works just as easily with arbitrary form=
ulas,<br>
eg, &quot;There must be at least 1 signer from pka{1,2,3}, and 3 signers al=
l<br>
up, except each of pkb{1,2,3,4,5,6} only counts for half&quot;:<br>
<br>
=C2=A0 0 pkb6 pkb5 pkb4 pkb3 pkb2 pkb1 pka3 pka2 pka1 9 CHECK_AGGSIG_VERIFY=
<br>
=C2=A0 =C2=A0 (declare pubkeys)<br>
=C2=A0 0b111 CHECK_AGG_SIGNERS VERIFY<br>
=C2=A0 =C2=A0 (one of pka{1,2,3} must sign)<br>
=C2=A0 0b001 CHECK_AGG_SIGNERS<br>
=C2=A0 0b010 CHECK_AGG_SIGNERS ADD<br>
=C2=A0 0b100 CHECK_AGG_SIGNERS ADD<br>
=C2=A0 DUP ADD<br>
=C2=A0 =C2=A0 (pka{1,2,3} count double)<br>
=C2=A0 0b000001000 CHECK_AGG_SIGNERS ADD<br>
=C2=A0 0b000010000 CHECK_AGG_SIGNERS ADD<br>
=C2=A0 0b000100000 CHECK_AGG_SIGNERS ADD<br>
=C2=A0 0b001000000 CHECK_AGG_SIGNERS ADD<br>
=C2=A0 0b010000000 CHECK_AGG_SIGNERS ADD<br>
=C2=A0 0b100000000 CHECK_AGG_SIGNERS ADD<br>
=C2=A0 =C2=A0 (pkb{1..6} count single)<br>
=C2=A0 6 EQUAL<br>
=C2=A0 =C2=A0 (summing to a total of 3 doubled)<br>
<br>
Not sure that saves it from being &quot;hacky and weird&quot; though...<br>=
</blockquote><div><br></div><div>That is very hacky and weird. Doing MAST o=
n lots of possibilities is always reasonably elegant, and it only gets prob=
lematic when the number of possibilities is truly massive.</div><div><br></=
div><div>It&#39;s also the case that BLS can support complex key agreement =
schemes without even giving away that it isn&#39;t a simple single signatur=
e. Just saying.</div></div></div></div>

--001a11444cd2c03cf90568707ab2--