OP_EVAL proposal

[ByteCoin]

I must credit jimrandomh for this quote which put me on the right track.

Now suppose that instead of publishing an address that's the hash of my public key, I could instead publish an address that's the hash of an arbitrary script. Then, if I want to spend the coins along, I make a transaction containing both the script - which turns out to be a function that says I need some combination of signatures - and also the signatures that make the script return true. This seems like the right way to handle multi-key addresses.

When I first read this proposal, it sounded to me like casascius was proposing a special scripting language for use with OP_CHECKSIGEX within the existing scripting language. This sounded inelegant; much better to have one scripting language we can use for everything. However I missed the point casascius was trying to make. Here's my version of the same idea using a new opcode OP_EVAL.

At the moment, most scriptPubKeys look like "OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG".
It's easy to see that to satisfy this scriptPubKey you need to supply a scriptSig containing a signature and a public key.
When you send someone your address, it's taken by the current client as an instruction to build a scriptPubKey of the above type when making a payment to that address. This means that one just needs to distribute a shorter public key hash to receive payments rather than the longer public key.
When blockexplorer sees a transaction with the above scriptPubKey it knows that only a public key with the specified hash can be used to satisfy it and hence it's possible to calculate the "balance" of an address.

We could introduce a new address type of the same length (but with incremented version number) and the new opcode. Use of the new address would mean that the intended scriptPubKey would look like "OP_DUP OP_HASH160 <scriptHash> OP_EQUALVERIFY OP_EVAL".
In order to spend the transaction, the holder of that address has to construct a scriptSig which probably looks like "<sig> <script>" where <script> can be treated as a number (OP_DUP'd and OP_HASH160'd) but when OP_EVAL'd expands into a script.

So to duplicate the functionality of the current system, the new address encodes the hash of "<pubKey> OP_CHECKSIG".
Someone sending to that address looks at the version number and knows to construct a scriptPubKey of "OP_DUP OP_HASH160 <scriptHash> OP_EQUALVERIFY OP_EVAL" where scriptHash is decoded from the address in the same way that the pubKeyHash is decoded from current addresses.
To redeem the transaction the address holder supplies the scriptSig of "<sig> <script>" where <script> encodes "<pubKey> OP_CHECKSIG".  Following the explanation of the transaction wiki page

Stack	#	Script	#	Description
Empty	#	<sig> <script> OP_DUP OP_HASH160 <scriptHash> OP_EQUALVERIFY OP_EVAL	#	scriptSig and scriptPubKey are combined.
<sig> <script>	#	OP_DUP OP_HASH160 <scriptHash> OP_EQUALVERIFY OP_EVAL	#	Constants are added to the stack.
<sig> <script><script>	#	OP_HASH160 <scriptHash> OP_EQUALVERIFY OP_EVAL	#	Top stack item is duplicated.
<sig> <script><scriptHashA>	#	<scriptHash> OP_EQUALVERIFY OP_EVAL	#	Top stack item is hashed.
<sig> <script><scriptHashA><scriptHash>	#	OP_EQUALVERIFY OP_EVAL	#	Constant added.
<sig> <script>	#	OP_EVAL	#	Equality is checked between the top two stack items.
<sig>	#	<pubKey> OP_CHECKSIG	#	Script is popped and decoded.
<sig><pubKey>	#	OP_CHECKSIG	#	Constant added.
true	#	empty	#	Signature is checked for top two stack items.

Obviously if the new address encoded the hash of "<pubKey2> CHECKSIGVERIFY <pubKey1> CHECKSIG" then one would have to supply a scriptPubKey of "<sig1> <sig2> <script>" where <script> encodes "<pubKey2> CHECKSIGVERIFY <pubKey1> CHECKSIG" as mentioned above. This would mean that knowledge of two private keys would be needed.
So the above scheme is easily extendable to all multisignature messages.

In order for IsStandard() to still restrict transaction types, it would have to do whitelist template matching on the results of the OP_EVAL.
BlockExplorer could easily be tweaked to show transactions to new addresses.
 
Advantages

• Addresses for arbitraritly complex transactions are fixed forever. No more new address types need be introduced.
• Addresses need only be same length as the current ones, forever.
• Transactions sending to multisignature addresses in this scheme are the same length as normal. This addresses theymos' concern that senders shouldn't be burdened with extra fees from longer scriptPubKeys. Instead, for more complex transactions, the scriptSig is longer which means that the owner of the address bears the cost of potentially increased fees.

On preview - Gavin Andresen has come up with something very similar. I think they are probably functionally identical but my proposal uses only one keyword and I think it will be easier to code than BEGIN & END_DIGEST. Also, in both our schemes the increased length of more complex transactions is in the scriptSig.

I think my proposal might be superior to Gavin's in that it more easily allows both constants and opcodes to be specified whereas Gavin's proposal involves hashing things on the stack and opcodes don't go on the stack, they operate on stack items.

ByteCoin

[1715231800]

1715231800

[1715231800]

1715231800

[Gavin Andresen]

I like OP_EVAL better than BEGIN...ENDDIGEST.

[casascius]

I like OP_EVAL better than BEGIN...ENDDIGEST.

I don't see the difference between this and my proposal, except for using the symbol name OP_EVAL and saying it's a new opcode, rather than simply a rename of the OP_CHECKSIG opcode, and the use of the full scripting system rather than a boolean subset.  It is otherwise pretty much identical.

If the opcode were renamed, and a <script> consisting of just a pubkey just meant "check signature for this pubkey", then there would be no need to increment the version number.  All existing Bitcoin transactions would already be forward-compatible with the change.  I believe changing the version number and making all new bitcoin addresses start with a "2" will cost us added complexity in the view of the user, and that's not a resource cost to take lightly.

Either way, I still like it.  It would still work just fine as a new opcode.  If you pick this plan, my only hope is that the version number in the bitcoin address isn't incremented.  It should be possible to do this without changing it - if everyone has to switch to a new client anyway, then normal transactions might as well contain OP_EVAL as well.

[theymos]

I also like OP_EVAL the best. This concept is a really fantastic idea.

I'm still bothered by the fact that this will make brute-force attacks much easier (though probably still impossible). It might be a good idea to require OP_EVALed scripts to contain at least one SigOp or add another parameter to OP_EVAL that allows the sender to state the number of required SigOps.

[ByteCoin]

I don't see the difference between this and my proposal, except for ... the use of the full scripting system rather than a boolean subset.

True. The fact that it uses the existing scripting system probably makes it easier to implement and considerably reduce the number of test cases to provide code coverage. I am happy to disclaim any credit for the idea if that is desired.

You are right in that OP_CHECKSIG could just be reimplemented so that it effectively does OP_EVAL and appends a OP_CHECKSIG (see postscript) to the decoded script. It would have the advantage of being instantly compatible. I finally understand what you were talking about. In my defense, when you talked about redefining OP_CHECKSIG it sounded very sketchy. I will read your posts more carefully in future.

I'm still bothered by the fact that this will make brute-force attacks much easier (though probably still impossible). It might be a good idea to require OP_EVALed scripts to contain at least one SigOp or add another parameter to OP_EVAL that allows the sender to state the number of required SigOps.

IsStandard() will probably ensure that OP_EVAL'ed scripts match known whitelisted types with at least one SigOp. So it's not open season on non-standard transaction types yet.  

One disadvantage is that the IsStandard() check will now apply when you're trying to redeem the coins rather than when you're trying to send them. Unfortunately, this means that if IsStandard fails, you probably can't redeem them (short of breaking the hash) until IsStandard is changed. This could result in some distress.

ByteCoin

PS. Obviously the appended OP_CHECKSIG would have to be renamed something else to avoid recursion! This is merely a matter of giving your version of OP_EVAL the number of OP_CHECKSIG and having a new opcode which really just evaluates a sig against a pubkey.

PPS Nope, you're right again. It's no good always having OP_EVAL append an OP_REALCHECKSIG to the decoded script. The case when the decoded script is just a pubKey needs to be recognized and an OP_REALCHECKSIG needs to be appended only in that case for back-compatibility purposes. The special behaviour and the reasons for it would take quite a bit of explaining in the code comments.

[casascius]

I will join the bandwagon and say OP_EVAL is good.  I'm not concerned about being credited for it - I will be far more thrilled to see it happen, and I am pleased that a consensus is building around implementing something that will ultimately achieve the originally stated goal: automatically multi-sig safe transactions without changing the format of the bitcoin address.  This is big, because it ultimately will lead to a scenario where we can offer real Bitcoin security with a straight face.

[genjix]

Ya joking?

A scripting system inside a scripting system. Hacks on hacks on hacks will lead to a messier protocol than FTP is now.

Well, it seems good at first glance. But fast-tracking this into the block-chain is probably not a wise idea. There's no rush so it might be prudent to think of this as something for 2 years time or later. Bitcoin is not exploding tomorrow, so there's no big loss from holding off on momentous changes like these.

https://en.bitcoin.it/wiki/BIP_0001

That's a good place to start. Re-enabling parts of the old scripting system in a controlled manner is a good idea. Adding new operations- not so much *right* now.

[theymos]

There's no need to fast-track it, but it's one of several things that should be included next time the block chain needs to be forked (which could very well be years from now).

What's messy is having senders worry about new transaction types that recipients want to use. This seems pretty elegant to me.

[maaku]

I am 100% for DIGEST160 stuff. (Along a similar vein, CHECKSIG should have been four opcodes from the start: LOADTX (to stack), DIGEST, SIGN, and VERIFY, and we could use better escaping than CODESEPARATOR provides.) It would solve problems now while a better, more general solution is being hashed (hah!) out.


But be very wary of an OP_EVAL. Allowing execution of data is extraordinarily powerful, and extraordinarily difficult to secure. Attackers could do things like cause infinite loops, or rewrite a TX script to always pass. The semantics of eval() are notoriously difficult to pin down.

That said, my company is implementing a bitcoin-like crypto-token system featuring Lisp as the scripting language (with eval, lambdas, macros, and all), and I was primarily responsible for the decision to do so. So I both speak from experience in warning of its danger and difficulty, and simultaneously as a strong advocate for it, if done right.

[Pieter Wuille]

It seems I misunderstood part of the original suggestion.

Still, a few remarks:

• OP_EVAL sounds like a very elegant way of increasing the script language's power, with some nice possibilities like explained above.
• I agree we need to be extremely careful about this - the data accepted by a txout script being evaluates should always be protected by some form of hash script. One can argue that this is the responsibility of the sender to create a good script, though.
• Enabling an operation like OP_EVAL implies removing the IsStandard() test, as it essentially allows any script to bypass the test anyway. I'm in favor of relaxing IsStandard() and enabling more operations, but we need solid unit tests to verify that all involved scripts/operations verify fine.
• I do like the fact that using a hash-protected eval()ed script is not encouraged without the payee asking so (even if I know you have addresses A and B, there is no reason for me to expect that an OP_EVAL script with hash equal to the hash of script that checks for A AND B will be detected by your client as a spend to you
• I don't like the fact that we're using a static string for even more complex txout templates, it risks accidental reuse, is impossible to refuse once the string is published, and is hard to track. IMHO, the right solution for cases were more complex scripts are wanted is directly negotiating them with the receiver.

[Gavin Andresen]

RE: be wary of OP_EVAL:

Agreed, we need to think hard about whether or not attackers could Do Evil Things like create an innocuous little script that pushed an infinite amount of data onto the stack or something  (lets see... Serialized(<OP_DUP OP_DUP OP_EVAL>) OP_DUP OP_EVAL would do that...).  Disallowing recursion (no OP_EVALs allowed in the OP_EVAL data) would, I think, prevent all of that mischief.

RE: OP_EVAL means no more IsStandard:  I agree with ByteCoin.  A ScriptSig would be IsStandard if it's ScriptPubKey was IsStandard, and if it's ScriptPubKey was the generic OP_EVAL form then the last value pushed by the ScriptSig would also have to pass the IsStandard test (deserialized into a Script).

RE: data should always be protected by a hash script:  I think the answer is "don't be an idiot" and "use standard transaction types that have been banged on / thought through."

RE: sender/recipient negotiating a transaction: I think that may become the most common way of creating a transaction, but I don't think it will ever be the only way.

[jimrandomh]

Well, it seems good at first glance. But fast-tracking this into the block-chain is probably not a wise idea. There's no rush so it might be prudent to think of this as something for 2 years time or later. Bitcoin is not exploding tomorrow, so there's no big loss from holding off on momentous changes like these.

Actually, I think this is considerably more urgent than that. Right now, it's impossible to safely hold corporate-scale amounts of money in Bitcoin, because corporations can't trust any one person with unrestricted spending power. Botnets have started introducing wallet-harvesting as a standard feature, and the encrypted wallets are not a defense because they had password-keylogging was a standard feature already. Every large theft deals major damage to Bitcoin's reputation, and if it takes too long to add security features, the damage will be irreparable.

There is going to be an unavoidable delay between hammering out the details of this proposal/group of proposals, and introduction on testnet; another delay between introduction on testnet and introduction to the main client; and then another delay between introduction to the main client and activation in the blockchain to allow miners time to get up to date. These delays are important, but remember that the thing we want to maximize is thought, not time; and there are better ways to get more people thinking about these issues than just waiting. Once the details are hammered out and there's a testnet implementation (which I see little reason *not* to rush; it's only testnet), then it'll be time to summon as much security-researcher attention to it as possible.

[genjix]

Right now, it's impossible to safely hold corporate-scale amounts of money in Bitcoin, because corporations can't trust any one person with unrestricted spending power.

OP_CHECKMULTISIG makes it possible to have a transaction that requires several signatures (need 2 of 3 sigs from A, B, C). This proposal is to allow finer grained logic for when a payment is redeemed (A and B's sigs or just C).

[Gavin Andresen]

Once the details are hammered out and there's a testnet implementation (which I see little reason *not* to rush; it's only testnet), then it'll be time to summon as much security-researcher attention to it as possible.

I agree. Security is really high on the priority list; I'd like to see secured bitcoin addresses in people's forum signatures within a year. I'm sure one of the alternate blockchains will take this idea and run with it, so much of the hammering-out will happen there.

[maaku]

Well, when we release our blockchains and API in a few months, that will be a chance to play with eval().

RE: be wary of OP_EVAL:

Agreed, we need to think hard about whether or not attackers could Do Evil Things like create an innocuous little script that pushed an infinite amount of data onto the stack or something  (lets see... Serialized(<OP_DUP OP_DUP OP_EVAL>) OP_DUP OP_EVAL would do that...).  Disallowing recursion (no OP_EVALs allowed in the OP_EVAL data) would, I think, prevent all of that mischief.

That is essentially what we are doing for our first release, although it is like swatting a fly with a bazooka. It lets you still do what's been described in this thread so far, but removes nearly all of the other cool things eval() would allow. We've also added strong typing as well, which will let us in time replace the IsStandard() whitelist with a ProvablyDoesNotDoAnythingEvil() blacklist.

[Gavin Andresen]

Summary of a discussion that happened in IRC chat this afternoon:

There are 10 no-op opcodes that are explicitly for expansion:
  https://github.com/bitcoin/bitcoin/blob/master/src/script.h#L150

They are currently enabled, and do nothing.

If we did the obvious thing and used one of them for OP_EVAL, then, surprisingly, OP_EVAL would not necessarily cause a block chain split.  Why?

Old clients see:
 

Code:

<sig> <...serialized script...>  DUP HASH160 <hash> EQUALVERIFY OP_NOP1

New clients see:
 

Code:

<sig> <...serialized script...>  DUP HASH160 <hash> EQUALVERIFY OP_EVAL

Old clients will consider the transaction valid as long as <serialized_script> hashes to the correct value and is not OP_FALSE, because a script evaluates as valid if it leaves a non-false value on the top of the stack when it is done.

New clients will do full validation: the hash has to be right AND the <serialized script> has to be valid (has to leave a non-false value on the top of the stack).

So:  If upgraded clients and miners start producing transactions and blocks with OP_EVAL in them, they will be accepted by old clients and miners as valid.

That means OP_EVAL could be supported as soon as 50+% of the network hashing power upgraded, instead of requiring that 100% of the network (clients and miners) upgrade before a certain time or block.

Anybody want to volunteer to write a BIP that works through all the details?

[groffer]

    Addresses for arbitraritly complex transactions are fixed forever. No more new address types need be introduced.
    Addresses need only be same length as the current ones, forever. 

Not so fast.  In a multiparty transaction (e.g. 2-of-3 buyer/seller/mediator) you can't have just one party generate the script because the other party won't be protected against bogus scripts.  For example, the seller could generate a script/hash that doesn't really involve the mediator or buyer.  You have to at least pass around the HASH160 of the three pubkeys before you can settle on a script.

For a single party script (e.g. wallet security "a AND b OR c") this does simplify things a bit for the sender.

    Transactions sending to multisignature addresses in this scheme are the same length as normal. This addresses theymos' concern that senders shouldn't be burdened with extra fees from longer scriptPubKeys. Instead, for more complex transactions, the scriptSig is longer which means that the owner of the address bears the cost of potentially increased fees.

Delaying fees will not really make a real economic difference.   It's just a transaction cost and in an efficient market the price will adjust so that the outcome to all parties is the same.

[casascius]

    Addresses for arbitraritly complex transactions are fixed forever. No more new address types need be introduced.
    Addresses need only be same length as the current ones, forever. 

Not so fast.  In a multiparty transaction (e.g. 2-of-3 buyer/seller/mediator) you can't have just one party generate the script because the other party won't be protected against bogus scripts.  For example, the seller could generate a script/hash that doesn't really involve the mediator or buyer.  You have to at least pass around the HASH160 of the three pubkeys before you can settle on a script.

In a mediator scenario, payment instructions come from the mediator.  What the seller could generate wouldn't matter much.

[groffer]

    Addresses for arbitraritly complex transactions are fixed forever. No more new address types need be introduced.
    Addresses need only be same length as the current ones, forever. 

Not so fast.  In a multiparty transaction (e.g. 2-of-3 buyer/seller/mediator) you can't have just one party generate the script because the other party won't be protected against bogus scripts.  For example, the seller could generate a script/hash that doesn't really involve the mediator or buyer.  You have to at least pass around the HASH160 of the three pubkeys before you can settle on a script.

In a mediator scenario, payment instructions come from the mediator.  What the seller could generate wouldn't matter much.

If the mediator generates the script and you use the hash without checking the script then you would have to fully trust the mediator.

[Gavin Andresen]

If the mediator generates the script and you use the hash without checking the script then you would have to fully trust the mediator.

So in an escrow situation all three parties have to exchange public keys and agree on one particular way of putting them together into a Script that they all agree on (so they all agree on the Script's hash).  That seems OK-- the three parties have to exchange public keys before creating any transactions in any case.