Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of mit.edu
	designates 18.9.25.14 as permitted sender) client-ip=18.9.25.14;
	envelope-from=jlrubin@mit.edu;
	helo=dmz-mailsec-scanner-3.mit.edu; 
MIME-Version: 1.0
In-Reply-To: <CAJHLa0OeetO3P6eBHOwN8SUN3ZpN07yWJ0vsGxupZLgcD1MEVQ@mail.gmail.com>
References: <CAD5xwhgyCOdJwnXw+YchptfXjtshDi_VVEGOjR-hG2qV=u6m2g@mail.gmail.com>
	<CAJHLa0OFEDQp5umz=6_LUx5oJJmiKJoF90W7nvJPv0CtML+ftA@mail.gmail.com>
	<CAD5xwhhwMyL20nAUXz-Vv6m5ucH7UQcGQLyrFadAvqy4QXkbZw@mail.gmail.com>
	<CAJHLa0OeetO3P6eBHOwN8SUN3ZpN07yWJ0vsGxupZLgcD1MEVQ@mail.gmail.com>
From: Jeremy <jlrubin@MIT.EDU>
Date: Thu, 17 Jul 2014 15:55:10 -0400
Message-ID: <CAD5xwhhUZXcJsQbxqidguYMsuTw6CvXMQyYjaZXUmytVARNk1A@mail.gmail.com>
To: Jeff Garzik <jgarzik@bitpay.com>
Content-Type: multipart/alternative; boundary=089e01494148daf6f004fe690533
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] Pay to MultiScript hash:
Precedence: list

--089e01494148daf6f004fe690533
Content-Type: text/plain; charset=UTF-8

* the general cost of any network-wide change, versus P2SH which is
already analyzed by devs, rolled out and working
* the cost of updating everybody to relay this new transaction type,
whereas P2SH Just Works already
fair -- I think that there may be a big benefit realizable with this kind
of system.

* cost of increasing rate of UTXO growth versus P2SH
This operation is similar in cost to multisig? Although I suppose there is
the proposal to make all multisigs p2sh

* the cost of P2SH output is predictable, versus less predictable outputs
 * "default public", versus P2SH's "default private"
-- Can you elaborate on these?

I think part of the problem is that there is low incentive for
development/cataloging  of these useful types of script because there isn't
a horizon on getting them broadcastable by nodes other than testnet? Even
with pay to script hash it is still currently relegated to a subset of
script types iirc (I think I'm wrong on this one maybe (hopefully) -- if
so, let's get writing!)?


Hmm... another idea... what about doing a p2sh with a switch statement, ie:

OP_HASH160 <script set hash> OP_EQUAL

payable by:

{signatures...} <scriptX> <<script1 hash>, <script2 hash>...<scriptN hash>
in sorted order> OP_DUP

And then executed like a normal p2sh transaction except before the
<scriptX> is run, the set of hashes is checked for set membership (can't
find a concise way to express this, but it should be doable within the
current framework of p2sh processing).

Which lets you select one of n scripts each 520 bytes long without bloating
the utxo pool more than a p2sh, the cost being purely on disk.

In theory, this could represent a space savings on disk longterm for
regular p2sh. ie, if I have two 2 of 3 groups I want to be able to spend,
this system would represent an overall space savings.


Adding some kind of "function-hash-pointer jump table / switch statement"
could be pretty cool in terms of space savings as well as allowing for more
complicated scripts to be built.


On Thu, Jul 17, 2014 at 2:21 AM, Jeff Garzik <jgarzik@bitpay.com> wrote:

> In a system like bitcoin, where the system has to keep running, you
> have to consider how to roll out upgrades, and the costs associated
> with that.
> * the general cost of any network-wide change, versus P2SH which is
> already analyzed by devs, rolled out and working
> * the cost of P2SH output is predictable, versus less predictable outputs
> * the cost of updating everybody to relay this new transaction type,
> whereas P2SH Just Works already
> * cost of increasing rate of UTXO growth versus P2SH
> * "default public", versus P2SH's "default private"
>
> It is true that publishing the script in the txout has the advantage
> of being easily audited by third parties scanning the blockchain, but
> in the interest of space efficiency you may accomplish the same thing
> by offering the script upon request out-of-band.  The script is
> hash-sealed by the P2SH address, enabling perfect proof.
>
> Don't have a transcript handy, but these things are usually logged and
> google-searchable.
>
> In any case, it would be nice to get together and start building a
> "cookbook" of useful scripts like the ones you've been describing.
> The power of bitcoin scripts is only beginning to be explored.  Use
> cases and examples are very helpful.
>
>
>
> On Thu, Jul 17, 2014 at 1:59 AM, Jeremy <jlrubin@mit.edu> wrote:
> > Additional costs would be in terms of A) chance of user error/application
> > error -- proposed method is much simpler, as well as extra bytes for
> control
> > flow ( 4 per script if I am counting right).
> >
> >
> > The costs on a normal script do seem slightly more friendly, except this
> > method allows for hidden-till-spent permission groups, as well as as
> smaller
> > blockchain bloat overall (if scriptSig script has to store the logic for
> all
> > the potential permission group, it will be a larger script  versus only
> > needing one permission group's script). An added benefit could also be in
> > blockchain analysis -- you can actively monitor the utxo pool for your
> known
> > associated scripts, whereas you couldn't for specialty scripts assembled
> per
> > group. Enables repeated spends with groups as a "cost object" w/o having
> to
> > recall all participants. ie, pay to the same perm groups as the other
> > employee did last time, but include me as a root this time.
> >
> >
> > Do you have a transcript of that chat by any chance? An interesting way
> to
> > do that would be to push the sigs onto the stack & have implicit orders,
> > then do expressions with their aliases, and then be able to assign
> "spending
> > groups".
> > ex:
> > code_sep
> > push script0
> > push script1
> > push script2
> > push script3
> > group_sep
> > mkgroup_2, 0,1      ; the id will be 4
> > mkgroup_3, 0,2,3   ; the id will be 5
> > mkUnionGroup_2, 4,5 ; the id will be 6
> > 2_of_3_group 0, 1, 2
> > mkIntersectionGroup_2 5, 6
> > complement_last  ; complements last group, mutation
> > del_group 1          ; deletes the group #1, groups then reindex after
> > deletion (maybe the group was useful base class).
> > etc...
> > multisig check perm groups (checks if any groups on stack are valid from
> > script)
> >
> >
> > or even something like adding a little SAT scripting language with an
> eval.
> >
> > push script0
> > push script1
> > push script2
> > push script3
> > push <a=(1 & 2 & 0), b=a-1, a | 3 | b >
> > eval
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > On Thu, Jul 17, 2014 at 12:52 AM, Jeff Garzik <jgarzik@bitpay.com>
> wrote:
> >>
> >> On Wed, Jul 16, 2014 at 1:56 PM, Jeremy <jlrubin@mit.edu> wrote:
> >> > Right now, this could be expressed multiple ways (ie, using an op_dup
> if
> >> > then else chain) , but all would incur additional costs in terms of
> >> > complicated control flows. Instead, I would propose:
> >>
> >> Can you quantify "additional costs in terms of complicated control
> flows"?
> >>
> >>
> >> > There is an implication in terms of increased utxo pool bloat, but
> also
> >> > an
> >> > implication in terms of increased txn complexity (each 20 byte hash
> >> > allows
> >> > for a 500 byte script, only one of the 500 byte scripts has to be
> >> > permanently stored on blockchain).
> >>
> >> When considering these costs, using a normal P2SH output + a script
> >> with OP_IF and friends seems more straightforward?
> >>
> >> Doing boolean logic with multisig groups is quite possible, e.g.
> >> "group AND group", "group OR (group AND group)" etc.  Definitely a
> >> valid use case.  I discussed how to do this on IRC with gmaxwell
> >> several months ago.  I call it "multi-multisig" for lack of a better
> >> name.
> >
> >
> >
> >
> > --
> > Jeremy Rubin
>
>
>
> --
> Jeff Garzik
> Bitcoin core developer and open source evangelist
> BitPay, Inc.      https://bitpay.com/
>


-- 
Jeremy Rubin

--089e01494148daf6f004fe690533
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_default" style=3D"font-family:arial,he=
lvetica,sans-serif;font-size:small;color:rgb(0,0,0)">* the general cost of =
any network-wide change, versus P2SH which is<br>
already analyzed by devs, rolled out and working<br>* the cost of updating =
everybody to relay this new transaction type,<br>
whereas P2SH Just Works already<br>fair -- I think that there may be a big =
benefit realizable with this kind of system.<br><br>
* cost of increasing rate of UTXO growth versus P2SH<br></div><div class=3D=
"gmail_default" style=3D"font-family:arial,helvetica,sans-serif;font-size:s=
mall;color:rgb(0,0,0)">This operation is similar in cost to multisig? Altho=
ugh I suppose there is the proposal to make all multisigs p2sh<br>


<br>
* the cost of P2SH output is predictable, versus less predictable outputs<b=
r>

</div><div class=3D"gmail_default" style=3D"font-family:arial,helvetica,san=
s-serif;font-size:small;color:rgb(0,0,0)">
* &quot;default public&quot;, versus P2SH&#39;s &quot;default private&quot;=
<br></div><div class=3D"gmail_default" style=3D"font-family:arial,helvetica=
,sans-serif;font-size:small;color:rgb(0,0,0)">-- Can you elaborate on these=
?<br>


</div>


<div class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-seri=
f;font-size:small;color:rgb(0,0,0)"><br>I think part of the problem is that=
 there is low incentive for development/cataloging=C2=A0 of these useful ty=
pes of script because there isn&#39;t a horizon on getting them broadcastab=
le by nodes other than testnet? Even with pay to script hash it is still cu=
rrently relegated to a subset of script types iirc (I think I&#39;m wrong o=
n this one maybe (hopefully) -- if so, let&#39;s get writing!)?<br>

<br><br><br></div>
<div class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-seri=
f;font-size:small;color:rgb(0,0,0)">Hmm... another idea... what about doing=
 a p2sh with a switch statement, ie:<br><br></div><div class=3D"gmail_defau=
lt" style=3D"font-family:arial,helvetica,sans-serif;font-size:small;color:r=
gb(0,0,0)">


OP_HASH160 &lt;script set hash&gt; OP_EQUAL<br><br></div><div class=3D"gmai=
l_default" style=3D"font-family:arial,helvetica,sans-serif;font-size:small;=
color:rgb(0,0,0)">payable by:<br><br></div><div class=3D"gmail_default" sty=
le=3D"font-family:arial,helvetica,sans-serif;font-size:small;color:rgb(0,0,=
0)">


{signatures...} &lt;scriptX&gt; &lt;&lt;script1 hash&gt;, &lt;script2 hash&=
gt;...&lt;scriptN hash&gt; in sorted order&gt; OP_DUP<br><br></div><div cla=
ss=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif;font-s=
ize:small;color:rgb(0,0,0)">


And then executed like a normal p2sh transaction except before the &lt;scri=
ptX&gt; is run, the set of hashes is checked for set membership (can&#39;t =
find a concise way to express this, but it should be doable within the curr=
ent framework of p2sh processing).<br>


</div><div class=3D"gmail_default" style=3D"font-family:arial,helvetica,san=
s-serif;font-size:small;color:rgb(0,0,0)"><br></div><div class=3D"gmail_def=
ault" style=3D"font-family:arial,helvetica,sans-serif;font-size:small;color=
:rgb(0,0,0)">


Which lets you select one of n scripts each 520 bytes long without bloating=
 the utxo pool more than a p2sh, the cost being purely on disk. <br><br></d=
iv><div class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-s=
erif;font-size:small;color:rgb(0,0,0)">

In theory, this could represent a space savings on disk longterm for regula=
r p2sh. ie, if I have two 2 of 3 groups I want to be able to spend, this sy=
stem would represent an overall space savings.<br></div><div class=3D"gmail=
_default" style=3D"font-family:arial,helvetica,sans-serif;font-size:small;c=
olor:rgb(0,0,0)">


<br><br></div><div class=3D"gmail_default" style=3D"font-family:arial,helve=
tica,sans-serif;font-size:small;color:rgb(0,0,0)">Adding some kind of &quot=
;function-hash-pointer jump table / switch statement&quot; could be pretty =
cool in terms of space savings as well as allowing for more complicated scr=
ipts to be built.<br>

</div><div class=3D"gmail_default" style=3D"font-family:arial,helvetica,san=
s-serif;font-size:small;color:rgb(0,0,0)"><br>
</div>
<div class=3D"gmail_extra"><br><br><div class=3D"gmail_quote">On Thu, Jul 1=
7, 2014 at 2:21 AM, Jeff Garzik <span dir=3D"ltr">&lt;<a href=3D"mailto:jga=
rzik@bitpay.com" target=3D"_blank">jgarzik@bitpay.com</a>&gt;</span> wrote:=
<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">In a system like bitcoin, where the system h=
as to keep running, you<br>
have to consider how to roll out upgrades, and the costs associated<br>
with that.<br>
* the general cost of any network-wide change, versus P2SH which is<br>
already analyzed by devs, rolled out and working<br>
* the cost of P2SH output is predictable, versus less predictable outputs<b=
r>
* the cost of updating everybody to relay this new transaction type,<br>
whereas P2SH Just Works already<br>
* cost of increasing rate of UTXO growth versus P2SH<br>
* &quot;default public&quot;, versus P2SH&#39;s &quot;default private&quot;=
<br>
<br>
It is true that publishing the script in the txout has the advantage<br>
of being easily audited by third parties scanning the blockchain, but<br>
in the interest of space efficiency you may accomplish the same thing<br>
by offering the script upon request out-of-band. =C2=A0The script is<br>
hash-sealed by the P2SH address, enabling perfect proof.<br>
<br>
Don&#39;t have a transcript handy, but these things are usually logged and<=
br>
google-searchable.<br>
<br>
In any case, it would be nice to get together and start building a<br>
&quot;cookbook&quot; of useful scripts like the ones you&#39;ve been descri=
bing.<br>
The power of bitcoin scripts is only beginning to be explored. =C2=A0Use<br=
>
cases and examples are very helpful.<br>
<div><div><br>
<br>
<br>
On Thu, Jul 17, 2014 at 1:59 AM, Jeremy &lt;<a href=3D"mailto:jlrubin@mit.e=
du" target=3D"_blank">jlrubin@mit.edu</a>&gt; wrote:<br>
&gt; Additional costs would be in terms of A) chance of user error/applicat=
ion<br>
&gt; error -- proposed method is much simpler, as well as extra bytes for c=
ontrol<br>
&gt; flow ( 4 per script if I am counting right).<br>
&gt;<br>
&gt;<br>
&gt; The costs on a normal script do seem slightly more friendly, except th=
is<br>
&gt; method allows for hidden-till-spent permission groups, as well as as s=
maller<br>
&gt; blockchain bloat overall (if scriptSig script has to store the logic f=
or all<br>
&gt; the potential permission group, it will be a larger script =C2=A0versu=
s only<br>
&gt; needing one permission group&#39;s script). An added benefit could als=
o be in<br>
&gt; blockchain analysis -- you can actively monitor the utxo pool for your=
 known<br>
&gt; associated scripts, whereas you couldn&#39;t for specialty scripts ass=
embled per<br>
&gt; group. Enables repeated spends with groups as a &quot;cost object&quot=
; w/o having to<br>
&gt; recall all participants. ie, pay to the same perm groups as the other<=
br>
&gt; employee did last time, but include me as a root this time.<br>
&gt;<br>
&gt;<br>
&gt; Do you have a transcript of that chat by any chance? An interesting wa=
y to<br>
&gt; do that would be to push the sigs onto the stack &amp; have implicit o=
rders,<br>
&gt; then do expressions with their aliases, and then be able to assign &qu=
ot;spending<br>
&gt; groups&quot;.<br>
&gt; ex:<br>
&gt; code_sep<br>
&gt; push script0<br>
&gt; push script1<br>
&gt; push script2<br>
&gt; push script3<br>
&gt; group_sep<br>
&gt; mkgroup_2, 0,1 =C2=A0 =C2=A0 =C2=A0; the id will be 4<br>
&gt; mkgroup_3, 0,2,3 =C2=A0 ; the id will be 5<br>
&gt; mkUnionGroup_2, 4,5 ; the id will be 6<br>
&gt; 2_of_3_group 0, 1, 2<br>
&gt; mkIntersectionGroup_2 5, 6<br>
&gt; complement_last =C2=A0; complements last group, mutation<br>
&gt; del_group 1 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0; deletes the group #1, =
groups then reindex after<br>
&gt; deletion (maybe the group was useful base class).<br>
&gt; etc...<br>
&gt; multisig check perm groups (checks if any groups on stack are valid fr=
om<br>
&gt; script)<br>
&gt;<br>
&gt;<br>
&gt; or even something like adding a little SAT scripting language with an =
eval.<br>
&gt;<br>
&gt; push script0<br>
&gt; push script1<br>
&gt; push script2<br>
&gt; push script3<br>
&gt; push &lt;a=3D(1 &amp; 2 &amp; 0), b=3Da-1, a | 3 | b &gt;<br>
&gt; eval<br>
&gt;<br>
&gt;<br>
&gt;<br>
&gt;<br>
&gt;<br>
&gt;<br>
&gt;<br>
&gt;<br>
&gt;<br>
&gt;<br>
&gt;<br>
&gt; On Thu, Jul 17, 2014 at 12:52 AM, Jeff Garzik &lt;<a href=3D"mailto:jg=
arzik@bitpay.com" target=3D"_blank">jgarzik@bitpay.com</a>&gt; wrote:<br>
&gt;&gt;<br>
&gt;&gt; On Wed, Jul 16, 2014 at 1:56 PM, Jeremy &lt;<a href=3D"mailto:jlru=
bin@mit.edu" target=3D"_blank">jlrubin@mit.edu</a>&gt; wrote:<br>
&gt;&gt; &gt; Right now, this could be expressed multiple ways (ie, using a=
n op_dup if<br>
&gt;&gt; &gt; then else chain) , but all would incur additional costs in te=
rms of<br>
&gt;&gt; &gt; complicated control flows. Instead, I would propose:<br>
&gt;&gt;<br>
&gt;&gt; Can you quantify &quot;additional costs in terms of complicated co=
ntrol flows&quot;?<br>
&gt;&gt;<br>
&gt;&gt;<br>
&gt;&gt; &gt; There is an implication in terms of increased utxo pool bloat=
, but also<br>
&gt;&gt; &gt; an<br>
&gt;&gt; &gt; implication in terms of increased txn complexity (each 20 byt=
e hash<br>
&gt;&gt; &gt; allows<br>
&gt;&gt; &gt; for a 500 byte script, only one of the 500 byte scripts has t=
o be<br>
&gt;&gt; &gt; permanently stored on blockchain).<br>
&gt;&gt;<br>
&gt;&gt; When considering these costs, using a normal P2SH output + a scrip=
t<br>
&gt;&gt; with OP_IF and friends seems more straightforward?<br>
&gt;&gt;<br>
&gt;&gt; Doing boolean logic with multisig groups is quite possible, e.g.<b=
r>
&gt;&gt; &quot;group AND group&quot;, &quot;group OR (group AND group)&quot=
; etc. =C2=A0Definitely a<br>
&gt;&gt; valid use case. =C2=A0I discussed how to do this on IRC with gmaxw=
ell<br>
&gt;&gt; several months ago. =C2=A0I call it &quot;multi-multisig&quot; for=
 lack of a better<br>
&gt;&gt; name.<br>
&gt;<br>
&gt;<br>
&gt;<br>
&gt;<br>
&gt; --<br>
&gt; Jeremy Rubin<br>
<br>
<br>
<br>
</div></div><span><font color=3D"#888888">--<br>
Jeff Garzik<br>
Bitcoin core developer and open source evangelist<br>
BitPay, Inc. =C2=A0 =C2=A0 =C2=A0<a href=3D"https://bitpay.com/" target=3D"=
_blank">https://bitpay.com/</a><br>
</font></span></blockquote></div><br><br clear=3D"all"><br>-- <br><div dir=
=3D"ltr">Jeremy Rubin</div>
</div></div>

--089e01494148daf6f004fe690533--