[Bitcoin-development] Pay to MultiScript hash:

[Bitcoin-development] Pay to MultiScript hash:

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 1524 bytes --]

Hey all,

I had an idea for a new transaction type. The base idea is that it is
matching on script hashes much like pay to script hash, but checks for one
of N scripts.

A motivating case is for "permission groups". Let's say I want to have a
single "root user" script, a 2 of 3 group, and a 2 of 2 group able to spend
a utxo. This would allow for any one of these permission groups to spend.

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:

OP_HASH160 [20-byte-hash-value 1]...[20-byte-hash-value N] OP_N
OP_MULTISCRIPTHASHVERIFY


could be spent with

...signatures... {serialized script}


​And the alternative formulation: (more complex!)​

​OP_HASH160 OP_DUP [20-byte-hash-value 1]​
​ OP_IF OP_EQUAL​
​ OP_VERIFY OP_ELSE   <OP_DUP  [20-byte-hash-value 2]​​  OP_IF......>
OP_ENDIF​



Of course, the permission group example is just one use case, there could
be other interesting combinations as well
​.


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


Looking forward to your feedback -- the idea is a bit preliminary, but I
think it could be exciting.

Best,

Jeremy




-- 
Jeremy Rubin

[-- Attachment #2: Type: text/html, Size: 3176 bytes --]

Re: [Bitcoin-development] Pay to MultiScript hash:

[Jeff Garzik]

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.

Re: [Bitcoin-development] Pay to MultiScript hash:

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 2986 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 7287 bytes --]

Re: [Bitcoin-development] Pay to MultiScript hash:

[Jeff Garzik]

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/

Re: [Bitcoin-development] Pay to MultiScript hash:

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 6893 bytes --]

* 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

[-- Attachment #2: Type: text/html, Size: 10495 bytes --]

Re: [Bitcoin-development] Pay to MultiScript hash:

[Gregory Maxwell]

On Wed, Jul 16, 2014 at 10:56 AM, Jeremy <jlrubin@mit.edu> wrote:
> Hey all,
> I had an idea for a new transaction type. The base idea is that it is
> matching on script hashes much like pay to script hash, but checks for one
> of N scripts.

This seems strictly less flexible and efficient than the Merkelized
Abstract Syntax Tree construction, though perhaps slightly easier to
implement it wouldn't be any easier to deploy.

Something like this was very recently proposed on this list (by Tier
Nolan), you might want to see the "Selector Script" thread.