[Bitcoin-development] Detecting OP_EVAL scriptPubKeys that are to you

[Bitcoin-development] Detecting OP_EVAL scriptPubKeys that are to you

[Mike Hearn]

scriptPubKeys that use OP_EVAL contain a hash of a script. If I
understand correctly, that means to detect a transaction in a block
that is relevant to your wallet, that means you need to pre-calculate
every possible hash that might appear.

For the case of a single payment, that's not a problem. It means for
each key you now have to check for:

 - raw key
 - key hash
 - hash of script that contains key hash
 - hash of script that contains raw key

which isn't so bad.

What is the complexity like when multi-signing comes into the picture?
I *think* it's not an issue for the use cases currently envisioned,
but being unable to "see into" a script could complicate things later.

Specifically: for a wallet protection service, you have to make sure
the WPS keys are matched 1:1 with your own private keys. You must
never mix them up otherwise you have to check the block chain for the
cross-product. Deterministic wallets are one way to achieve that
without compromising privacy.

For escrow contracts, using OP_EVAL means you cannot detect them
unless the sender has told you the pubkey they are going to use,
because otherwise you can't recreate the hashed script. Escrow
protocols require some out of band communication anyway in order to
set up the escrow key, so this isn't inherently a problem.

Are there any use cases where you will want to recognize transactions
to you, where you can't predict the full script contents?

Re: [Bitcoin-development] Detecting OP_EVAL scriptPubKeys that are to you

[Gavin Andresen]

On Tue, Oct 25, 2011 at 6:49 AM, Mike Hearn <mike@plan99.net> wrote:
> scriptPubKeys that use OP_EVAL contain a hash of a script. If I
> understand correctly, that means to detect a transaction in a block
> that is relevant to your wallet, that means you need to pre-calculate
> every possible hash that might appear.

You could do it that way...  but that would be inefficient.

You give the hash to whoever is paying you, and store the hash -->
script  mapping when you do that (assuming you're not using a
deterministic wallet; if you are, you probably just increment a
counter in the wallet).

The only use case I can think of where you'd want to check for every
possible hash is if you lose your wallet, you have a wallet backup
that has your private keys in it, but DOES NOT have the hash -->
script mapping(s).

For use cases involving other people, that's probably not a problem--
you could ask them to tell you what public keys are involved, and then
add them back in to the wallet (the RPC interface I settled on for
m-of-n txns is an "addmultisigaddress" that takes the "m" and an array
of "n" public keys, creates the script, adds the hash-->script mapping
to the wallet, and returns the hash).

For use cases where all the keys belong to you... either a good,
automatic, in-the-cloud-backup or the equivalent of "-rescan" is
needed to recover in case the mappings are lost.

-- 
--
Gavin Andresen

Re: [Bitcoin-development] Detecting OP_EVAL scriptPubKeys that are to you

[Gregory Maxwell]

On Tue, Oct 25, 2011 at 9:21 AM, Gavin Andresen <gavinandresen@gmail.com> wrote:
> You give the hash to whoever is paying you, and store the hash -->
> script  mapping when you do that (assuming you're not using a
> deterministic wallet; if you are, you probably just increment a
> counter in the wallet).

If anyone finds that solution unsatisfying, consider— It's already the
case that I could take one of your disclosed public keys and create an
infinite series of secondary keys out of it for which only you could
decode, and the only way for you to find them in the blockchain would
be to have performed the same procedure and made a note of the
addresses you're watching for.

... or really, more simply I could generate a private key on your
behalf and send funds there. ("What do you mean you didn't get the
funds? I sent them to the private key defined by the cryptographic
hash of the lyrics of your favorite song!")

So it's already the case that if I didn't get your address from you
(or through a negotiation with you), I can't expect you to receive
them.

Re: [Bitcoin-development] Detecting OP_EVAL scriptPubKeys that are to you

[Alan Reiner]

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

On Tue, Oct 25, 2011 at 10:49 AM, Gregory Maxwell <gmaxwell@gmail.com>wrote:

> On Tue, Oct 25, 2011 at 9:21 AM, Gavin Andresen <gavinandresen@gmail.com>
> wrote:
> > You give the hash to whoever is paying you, and store the hash -->
> > script  mapping when you do that (assuming you're not using a
> > deterministic wallet; if you are, you probably just increment a
> > counter in the wallet).
>
> If anyone finds that solution unsatisfying, consider— It's already the
> case that I could take one of your disclosed public keys and create an
> infinite series of secondary keys out of it for which only you could
> decode, and the only way for you to find them in the blockchain would
> be to have performed the same procedure and made a note of the
> addresses you're watching for.
>
>
(1) As I understand it, OP_EVAL is being proposed as an *optional* tool for
multi-signature transactions.  It sounds like to me, that you can still use
the regular OP_CHECKMULTISIG if you are concerned about these things.  If
you're dealing with too many parties with questionable reliability that they
will notify you of transacitons that include you, I don't see anything wrong
with declaring that you'd only prefer dealing with OP_CMS transactions and
not OP_EVAL (besides some grumbling from them that their way is "better").
Either way, they're screwing themselves, too, if they want to include you on
transactions and don't notify you as such (kind of defeats the purpose of
multi-sig txs).

(2) I think it's unnecessary to discuss cases where you somehow lose your
mappings but not your private keys.  In order for OP_EVAL scripts to work,
the subscripts/mappings are *just as important* as your regular private
keys.  They should be kept in your wallet forever just like your private
keys--and thus you lose none of them or all of them.  The only real
difference is that they aren't sensitive like your private keys, so they
don't have to be encrypted.

(3) There should most definitely be a button on the main client that allows
you to "Add OP_EVAL script" or something along those lines (maybe something
with a less obscure name).  We need to make it as easy as possible for
someone to add such a script/mapping to their wallet.  Although, this
invites a breach of one of my core rules of user interfaces:  if the
functionality is dependent on the user performing some regular maintenance
task, you better be prepared for all users to fail at doing it.  Even
diligent users are going to forget/mess-up sometimes.  If failure at
performing this task results in breaking the client or losing money, we
should avoid promoting that usage paradigm.

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

Re: [Bitcoin-development] Detecting OP_EVAL scriptPubKeys that are to you

[Michael Grønager]

I think it is a very important feature to be able to extract transaction to/from you only from your private keys. In the standard transactions this is easily accomplished - in the case you only want to find the addr to tx mapping:

   vector<pair<opcodetype, vector<unsigned char> > > vSolution;
   if (!Solver(scriptPubKey, vSolution))
       return 0;

   BOOST_FOREACH(PAIRTYPE(opcodetype, vector<unsigned char>)& item, vSolution)
   {
       vector<unsigned char> vchPubKey;
       if (item.first == OP_PUBKEY)
           // encode the pubkey into a hash160
           return Hash160(item.second);
       else if (item.first == OP_PUBKEYHASH)
           return uint160(item.second);                
   }

This possibility is used today in:
* blockexplorer
* bitcoin-js
* my own tiered implementation for thin clients

I agree that you can of course always construct payment schemes to hide payments (hashes from classic novels, sending the private key off line etc), but I consider those either exotic or on purpose hidden, and hence they are not really a problem, nor an argument that this feature does not really exist today.

So, if we introduce a standard (multikey) payment that hides the address (or makes it overly complicated to extract it) it will be a major problem for the projects that I listed above. 

I will post a more detailed technical comment reflecting directly on the BIPs, but the wiki is currently down and I need to re-read the BIPs first.

Cheers,

Michael


On 25/10/2011, at 18:47, Alan Reiner wrote:

> On Tue, Oct 25, 2011 at 10:49 AM, Gregory Maxwell <gmaxwell@gmail.com> wrote:
> On Tue, Oct 25, 2011 at 9:21 AM, Gavin Andresen <gavinandresen@gmail.com> wrote:
>> You give the hash to whoever is paying you, and store the hash -->
>> script  mapping when you do that (assuming you're not using a
>> deterministic wallet; if you are, you probably just increment a
>> counter in the wallet).
> 
> If anyone finds that solution unsatisfying, consider— It's already the
> case that I could take one of your disclosed public keys and create an
> infinite series of secondary keys out of it for which only you could
> decode, and the only way for you to find them in the blockchain would
> be to have performed the same procedure and made a note of the
> addresses you're watching for.
> 
> 
> (1) As I understand it, OP_EVAL is being proposed as an *optional* tool for multi-signature transactions.  It sounds like to me, that you can still use the regular OP_CHECKMULTISIG if you are concerned about these things.  If you're dealing with too many parties with questionable reliability that they will notify you of transacitons that include you, I don't see anything wrong with declaring that you'd only prefer dealing with OP_CMS transactions and not OP_EVAL (besides some grumbling from them that their way is "better").   Either way, they're screwing themselves, too, if they want to include you on transactions and don't notify you as such (kind of defeats the purpose of multi-sig txs).
> 
> (2) I think it's unnecessary to discuss cases where you somehow lose your mappings but not your private keys.  In order for OP_EVAL scripts to work, the subscripts/mappings are *just as important* as your regular private keys.  They should be kept in your wallet forever just like your private keys--and thus you lose none of them or all of them.  The only real difference is that they aren't sensitive like your private keys, so they don't have to be encrypted.
> 
> (3) There should most definitely be a button on the main client that allows you to "Add OP_EVAL script" or something along those lines (maybe something with a less obscure name).  We need to make it as easy as possible for someone to add such a script/mapping to their wallet.  Although, this invites a breach of one of my core rules of user interfaces:  if the functionality is dependent on the user performing some regular maintenance task, you better be prepared for all users to fail at doing it.  Even diligent users are going to forget/mess-up sometimes.  If failure at performing this task results in breaking the client or losing money, we should avoid promoting that usage paradigm.
> 
> ------------------------------------------------------------------------------
> The demand for IT networking professionals continues to grow, and the
> demand for specialized networking skills is growing even more rapidly.
> Take a complimentary Learning@Cisco Self-Assessment and learn 
> about Cisco certifications, training, and career opportunities. 
> http://p.sf.net/sfu/cisco-dev2dev_______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Re: [Bitcoin-development] Detecting OP_EVAL scriptPubKeys that are to you

[Gregory Maxwell]

On Wed, Oct 26, 2011 at 4:58 AM, Michael Grønager <gronager@ceptacle.com> wrote:
> I think it is a very important feature to be able to extract transaction to/from you only from your private keys. In the standard transactions this is easily accomplished - in the case you only want to find the addr to tx mapping:

The additional material _IS_ then part of the private key. It's not
something seperate. Its something you need to know in order to author
the address.  This was fundamentally my argument. Not that you could
hide information, but that information was already hidden.

Right now under conventional uses I can't identify all the
transactions that land in your wallet, because I don't know the keys
it contains. With the proposal it's the same situation.

> This possibility is used today in:
> * blockexplorer
> * bitcoin-js
> * my own tiered implementation for thin clients
[snip]
> So, if we introduce a standard (multikey) payment that hides the address (or makes it overly complicated to extract it) it will be a major problem for the projects that I listed above.

These projects will be able to use the _same_ procedure to extract the
identifying information. Except now instead of
ripemd160(sha256(pubkey)) it will be more like ripemd160(sha256([some
extra bytes generated by the wallet holder]||pubkey)) that you
extract.  If the former is not a problem for these applications, why
is the latter?

Re: [Bitcoin-development] Detecting OP_EVAL scriptPubKeys that are to you

[Gavin Andresen]

On Wed, Oct 26, 2011 at 4:58 AM, Michael Grønager <gronager@ceptacle.com> wrote:
> I think it is a very important feature to be able to extract transaction to/from you only from your private keys.

Why? If somebody is sending me bitcoins, then they'll have to get
either an address or one or more public keys from me. OP_EVAL just
lets me give them a short address that represents an arbitrary number
of keys combined in an arbitrary way.

I agree with Gregory: it shouldn't matter if that address is
HASH(public key) or HASH(op_eval_script), the issues are the same (if
you lose or cannot re-create the key/script then you're in trouble).

Maybe I'm missing something; are you worried that blockexplorer won't
know that coins sent to HASH(op_eval_script) are actually a
complicated transaction until the coins are spent again?  I'd consider
that a feature, not a bug, because only the people involved in the
transaction need to know the details until after the transaction is
complete.

Feel free to contact me about your 'tiered implementation for thin
clients' -- I don't think OP_EVAL will make that significantly harder.

I also agree with Alan: using OP_EVAL is not mandatory, I'm proposing
that CHECKMULTISIG becomes a standard transaction type.

-- 
--
Gavin Andresen

Re: [Bitcoin-development] Detecting OP_EVAL scriptPubKeys that are to you

[Michael Grønager]

OK, let me try to explain what I see is the problem:

So far we the bitcoin addresses are (for all practical purposes) a one-to-one mapping between a pubkey and uint160. This mean that your wallet is defined solely by your privatekeys (from which you can extract pubkeys and then uint160 btc-addresses).

This also enables you to make a uint160 to tx mapping on a server (like on blockexplorer) and use a thin client to query for transactions just from a list of uint160 (whether it holds the private keys behind them or not).

In the case of a multisig transaction, lets say the 2of3 example, you could e.g. have all 3 corresponding uint160s but only one privkey, but still query the server and know the value of an asset of uint160s.

This, I find a nice and clean setup, where cryptographic keys can be mapped to assets.

If we now consider the OP_EVAL proposal. Here, a new use of the uint160, namely as a mapping of ripemd160(something extra and hash256(pubkey)) is introduced. This means that this clean mapping is broken. Your will have an extra "public key" being the "something extra", and there is no easy way to do the mapping from a list of private keys to public keys to uint160s that will result in the new condensed uint160, except if you also have the knowledge of the script that was used. 

I agree that it will work and I (and bitcoin-js and blockexplorer) can of change the concept of a wallet to also include scripts, but it breaks an intrinsic logic of uint160s and transactions that has so far been quite nice and clean.

So I also support checkmultisig to be the standard transaction type, but I do not appreciate the support of OP_EVAL.

Cheers,

Michael


On 26/10/2011, at 17:00, Gavin Andresen wrote:

> On Wed, Oct 26, 2011 at 4:58 AM, Michael Grønager <gronager@ceptacle.com> wrote:
>> I think it is a very important feature to be able to extract transaction to/from you only from your private keys.
> 
> Why? If somebody is sending me bitcoins, then they'll have to get
> either an address or one or more public keys from me. OP_EVAL just
> lets me give them a short address that represents an arbitrary number
> of keys combined in an arbitrary way.
> 
> I agree with Gregory: it shouldn't matter if that address is
> HASH(public key) or HASH(op_eval_script), the issues are the same (if
> you lose or cannot re-create the key/script then you're in trouble).
> 
> Maybe I'm missing something; are you worried that blockexplorer won't
> know that coins sent to HASH(op_eval_script) are actually a
> complicated transaction until the coins are spent again?  I'd consider
> that a feature, not a bug, because only the people involved in the
> transaction need to know the details until after the transaction is
> complete.
> 
> Feel free to contact me about your 'tiered implementation for thin
> clients' -- I don't think OP_EVAL will make that significantly harder.
> 
> I also agree with Alan: using OP_EVAL is not mandatory, I'm proposing
> that CHECKMULTISIG becomes a standard transaction type.
> 
> -- 
> --
> Gavin Andresen

Michael Gronager, PhD
Owner Ceptacle / NDGF Director, NORDUnet A/S
Jens Juels Gade 33
2100 Copenhagen E
Mobile: +45 31 62 14 01
E-mail: gronager@ceptacle.com

Re: [Bitcoin-development] Detecting OP_EVAL scriptPubKeys that are to you

[Gregory Maxwell]

(taking this a bit out of order)

On Thu, Oct 27, 2011 at 3:32 AM, Michael Grønager <gronager@ceptacle.com> wrote:
> OK, let me try to explain what I see is the problem:
[snip]
> This, I find a nice and clean setup, where cryptographic keys can be mapped to assets.

From my perspective that clean boundary remains: Functionally the
script is part of the cryptographic key.

[snip]
> except if you also have the knowledge of the script that was used.

Which you must.

I can see no functional difference than if you said of the current
system "except if you also have knowledge of the final 32 bits of the
ECC private key".

I don't see any reason to expect clients to identify funds without
knowing the information required— it's impossible. I mean, sure, you
_could_ bruteforce the final 32 bits of your private key— or you could
attempt to try the cartesian product of every key you have with every
key seen in the block chain for finding an op_eval script. But thats
unworkable, unnecessary, equally bad for all client types, and not
being suggested.  Under either system a coin is not yours unless you
know all of the right bits— knowing some is not good enough.

Could you suggest how else we could gain the advantages of op_eval
without it?   How can I secure my wallet under whatever scheme I like—
create a trust that requires multiparty signoff— and securely have
senders pay into it without expecting them all to handle some rare and
complicated procedure for sending to me? (Or a burdensome address
which serializes a script and a large amount of data into hundreds of
characters, and which still may be unable to represent the rules I
wish to have govern my account— and which the sender might mutate—
e.g. twiddling the threshold counts— and cause me great
problems/confusion)

[snip]
> So far we the bitcoin addresses are (for all practical purposes) a one-to-one mapping between a pubkey and uint160. This mean that your wallet is defined solely by your privatekeys (from which you can extract pubkeys and then uint160 btc-addresses).
[snip]
> I agree that it will work and I (and bitcoin-js and blockexplorer) can of change the concept of a wallet to also include scripts, but it breaks an intrinsic logic of uint160s and transactions that has so far been quite nice and clean.
>
> So I also support checkmultisig to be the standard transaction type, but I do not appreciate the support of OP_EVAL.

On the basis of the discussion here I now oppose checkmultisig as a
standard transaction type. (Sorry, I'm not trying to be a jerk if it
came off that way, I'm not opposing it simply because you support it:)

The advantage I saw of having it was faster deployment for the
explicit escrow cases that don't need to encode the payment rules in
an address (as is needed for wallet security and trusts)... but it
seems to me that there is a serious misunderstanding that there is a
bijection between hash160s and public keys, and one between ECC
private keys and spendable transactions, and that this bijection is
desirable or even essential to bitcoin.

I'm concerned that this misunderstanding will moot the flexibility of
the script system because every script that doesn't look like a direct
mapping of hash160->pubkey->payee will be regarded as _broken_— not
just useless to one app or another which could have simply chosen not
to generate those addresses— but actually incompatible with bitcoin,
as is basically being argued here— or, keeping in mind that people can
freely mine non-standard transactions, could this result in tools
which are rendered insecure by unexpected transaction types— Will a
system that thinks HASH160 = IDENTITY recognize that a script which
also requires an additional secret key on the stack is unspendable?

Keeping checkmultisig alone as a standard transaction, when it's
functionally a redundant subset of OP_EVAL  (and inferior because it
reduces the txn you can place in a block) could only further that
misunderstanding. :-/

Re: [Bitcoin-development] Detecting OP_EVAL scriptPubKeys that are to you

[Michael Grønager]

> Could you suggest how else we could gain the advantages of op_eval
> without it?   How can I secure my wallet under whatever scheme I like—
> create a trust that requires multiparty signoff— and securely have
> senders pay into it without expecting them all to handle some rare and
> complicated procedure for sending to me?

Yes - by the burdensome address ;) - which I am not sure I consider that much of a trouble, for practical uses... Anyway, it could just be added to the URI scheme and then it would still only be a click away.

> but it
> seems to me that there is a serious misunderstanding that there is a
> bijection between hash160s and public keys, and one between ECC
> private keys and spendable transactions, and that this bijection is
> desirable or even essential to bitcoin.

So far we had by the standard transactions a nice bijection, I do however, share your concern for other and more rich scripting... And here we need to make some choices! 
Do we want to keep this notion of transactions between addresses or do we want to start unfold the richness of the scripting - I am not sure we actually gain that much from OP_EVAL and the extra scripting. And what bothers me is that you then cannot define a set of data (be that key, scripts or whatever) from which you can obtain all possible txes send to you. If I e.g. looses this argument and want to donate a beer to each of you and Gavin, that I want you to drink together. I would make a "both of two" btc-addresses script transaction using OP_EVAL. And post it.
You would then not be able to know that you actually got a beer unless I told you so in a mail.

This means that we move from a setup where transactions needs not only to be asked for but also they need to be announced by the sender. I don't like this... 

Further, if you make a uint160 from a OP_EVAL script and post this as a bitcoin address - the user should then know that this was a special address - otherwise he would be sending money nowhere. I agree that this could be encoded into the bitcoin address using e.g. a 2... instead of a 3..., but as you mention yourself this is only the start of the OP_EVAL uses and hence you would need a whole series of strange numbering to define what script a specific address was referring to. 

At least it challenges my esthetics...

Cheers,

M

Re: [Bitcoin-development] Detecting OP_EVAL scriptPubKeys that are to you

[Gavin Andresen]

RE: buying me and Gregory a shared beer:

> I would make a "both of two" btc-addresses script transaction using OP_EVAL. And post it.
> You would then not be able to know that you actually got a beer unless I told you so in a mail.

But that transaction won't show up in my bitcoin wallet as bitcoins I can spend.

And even if my wallet DID show me "transactions that involve your keys
but that you can't spend," all I would know is there are N bitcoins
that I can only spend if I can somehow figure out that Gregory has
public key XYZ.

How would I know that unless you told me?

I think the right long-term solution is moving away from bitcoin
addresses as 'pay-to entity' and create an infrastructure where we're
paying people or organizations. But in the short term, I think there
are lots of benefits to creating a new type of bitcoin address built
on top of OP_EVAL that will be very easy for all of our existing
infrastructure to support.

-- 
--
Gavin Andresen

Re: [Bitcoin-development] Detecting OP_EVAL scriptPubKeys that are to you

[Michael Grønager]

> 
> How would I know that unless you told me?

At least you would have a hunch that something like that had happened as one of your addresses had been part of a transaction (at least in my setup it would pop up immediately...).

> 
> I think the right long-term solution is moving away from bitcoin
> addresses as 'pay-to entity' and create an infrastructure where we're
> paying people or organizations.

I am not sure what you mean by this - just recall that the semi anonymously feature of bitcoin is one of its key features.

> But in the short term, I think there
> are lots of benefits to creating a new type of bitcoin address built
> on top of OP_EVAL that will be very easy for all of our existing
> infrastructure to support.

Still, how do you solve the end less expansions of bitcoin addresses that each, depending of a leading 1, 2, 3... means a quite specific script inside the OP_EVAL ??? Its not esthetic...

Cheers,

M

> 
> -- 
> --
> Gavin Andresen