Bitcoin Forum

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

When I first read this proposal (https://bitcointalk.org/index.php?topic=45211.msg538756#msg538756), 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.  (https://en.bitcoin.it/wiki/Transactions#Transfer_to_Bitcoin_address)
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 (https://blockexplorer.com/) 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 (https://en.bitcoin.it/wiki/Transactions)

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

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.

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.

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.


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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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

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.

Summary of a discussion that happened in IRC chat this afternoon (http://bitcoinstats.com/irc/bitcoin-dev/logs/2011/10/02/3#l1877161):

There are 10 no-op opcodes that are explicitly for expansion:
  https://github.com/bitcoin/bitcoin/blob/master/src/script.h#L150 (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:
 New clients see:
 
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?

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.


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.

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.

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.

One thing I don't like about this but can't solve is that it changes the incentive structure for non-standard transactions.

Today if you try to issue a transaction that no one will forward or mine it just doesn't work and then you say "oh well" and spend your coin another way.

In the brave new OP_EVAL future, you spend coin to a script hash and then only later learn that mining the transaction spending it is difficult.  Instead of saying "oh well" you're out the funds until you can convince someone to mine the transaction... and you only discover this after your funds are tied up.

Presumably we'll be smart with the software and not allow the UI to issue transactions that won't work but I'm still concerned that this may increase the number of large burdensome transactions in the blockchain.   On the other hand, because only the input script will be large there may be some increased helpful pruning potential.

It might help a little if we made public key recovery (which we now have code for as part of Sipa's signing support) something that OP_EVAL scripts could use, at least scripts spending "must provide four signatures" wouldn't be quite so large.

I must credit sipa as first raising this issue as far as I know.

There's a bit of a problem with rolling out OP_EVAL using this idea and I believe it may create a more dangerous block chain split than casascius' alternative proposal whereby OP_CHECKSIG gets renamed and re-imagined as a slightly hacked OP_EVAL.

It's true that old clients will be accepting of blocks creating and spending OP_EVAL transactions. This is the advantage you mention.

However, old clients will also be accepting of blocks which contain transactions which incorrectly attempt to spend OP_EVAL transactions with a null scriptSig. As you mentioned in the IRC, the old clients see these OP_EVAL transactions as ones which anyone can redeem.

Miners would be best placed to watch out for transactions in which a null scriptSig can satisfy the scriptPubKey and then include transactions spending them in their blocks. This checking could be implemented now in anticipation of OP_EVAL being introduced in the fashion you propose and the exploit could be fully automated and require no time-consuming user intervention. This means that the bitcoin developers would have little time to react before the fraudulent transactions become confirmed. Clients (and miners) using the new version would reject these blocks but they would at least initially be a minority. People may opt not to upgrade to the new client as it would be easy to portray the new client's behaviour in negative terms. The effect of the above exploit would be to have a block chain split in which the latest clients who are supposedly doing the right thing may end up on the losing side. It would be bad for the public perception of bitcoin if an upgrade voluntarily precipitated a completely optional disaster along these lines.

I think it's more practical for people running old clients to bear the risk of failing to keep their software current. The policy towards incompatible changes will have to decide how much risk is acceptable and how long a time users are guaranteed to be safe running a particular version.

Bitcoin is lacking an effective and reliable mechanism for safely performing block chain splits. The worst-case scenario is one in which mining pools say they have updated their software and patch their clients to look like they are updated but then their software is actually designed maliciously to exploit the incompatibility of the new clients. If a client deployment strategy can cope with this situation then it can probably cope with anything.

Before introducing an incompatible client, I think it's wise to ensure that the existing clients have robust detection of block chain splits.
In particular, if a client sees a succession of what it thinks is invalid blocks with a high difficulty, then instead of banning the peer for misbehaviour, the client should disallow transactions (until overridden) and advise the user that an upgrade may be required.

Another way to limit the financial damage from an exploited rollout would be initially only to allow new incompatible transactions of infinitesimal value; where both the transaction and any change are both suitably small. This limit would increase in some fashion over time unless perhaps a "shutdown" transaction were broadcast which would disable the new behaviour. This shutdown switch could be removed in a subsequent version when no exploits appear and sufficient confidence has been reached. Also, there would have to be an initial prohibition against spending new style transactions into old style transactions.

Also, instead of enabling a feature after a certain block number, it could be introduced after seeing a block containing a particular magic transaction. This protects against the situatuion in which the miners (or the rest of the network) fail to upgrade as quickly as expected.

ByteCoin

That makes me think of one other random idea:  if a client notices the production of new blocks has taken a drastic drop (e.g. it's dropped by more than 90% and been more than 48 hours), it ought to say, "OK, something might be wrong right now.  Check for any significant Bitcoin news and to make sure this is the latest version before continuing to make transactions."

Wow, so many great ideas!

RE: There is already code to warn the user if they are on a minority chain more than 6 blocks long-- see GetWarnings():

It just warns, it doesn't stop you from generating/sending transactions. Perhaps if the longer fork is more than 120 blocks ahead it should.

ByteCoin: we can prevent the scenario you describe (generate a block with a NOP1/EVAL transaction whose validity is different in old and new clients) by:
1. Requiring that EVAL transactions be valid if the EVAL is interpreted as a no-op.  New clients can replace EVALs with no-ops and re-evaluate them to make sure that is true.
2. Waiting until a majority of hashing power has upgraded before turning on EVAL.

gmaxwell:  I really like the idea of implementing key recovery to save space in the block chain. It can also be done in a backwards-compatible way if only CHECKSIGs "hidden inside" of EVALs support it (CHECKSIG would be aware of whether it was being executed inside of an OP_EVAL, and if it was it could use a compressed version of the public key instead of the full public key).

All the ideas about figuring out what percentage of miners have upgraded:  seems like that deserves its own discussion thread.

As scripts inside OP_EVAL can have different semantics from the original, we can use it to short-circuit introduce a new version of the script language.

I've written a draft for a new version here: https://gist.github.com/1262449

Rationale for the changes:

• Using the altstack for signatures avoids the need for bookkeeping on the stack in scripts that do complex checking (the altstack contains the data from scriptSig, the normal stack is used for evaluation)
• Using ECDSA pubkey recovery (https://bitcointalk.org/index.php?topic=6430.0), we avoid encoding public keys in the block chain
• Low-level signature checking can be used to implement signed message checks in script, or more custom signature schemes
• A shorthand operation for the most common case (send to address) makes normal scripts shorter

If such comprehensive changes are being considered then I suggest that the default option should be that the signatures for a transaction should not influence the transaction hash. This would allow transactions spending unsigned transactions to be signed, which is a crucial step in some contracts. Also, the signature data could be pruned from the block chain for transactions occurring at sufficient depth or before a checkpoint. This would effect considerable space savings as the signature data is probably the only data that doesn't compress.

Another improvement would be the introduction of the Bernstein signature scheme with a similar security parameter to the existing ECDSA but a much faster verification. Transactions using the cheaper signatures could get a discount on the fees or be allowed more sigOps. To be clear, the scheme I'm thinking of is "A secure public-key signature system with extremely fast verification" (http://cr.yp.to/papers/sigs.ps) from about 2000.

With regards to key recovery, a 2 bit hint can be used to accellerate the process. Alternatively, a single hint value could be assumed and it would be the responsibility of the signer to redo the signing operation until the assumed hint value is correct.

ByteCoin

... but isn't it the signatures that give each transaction its unique identity?  I may be wrong, but without the signature hashes I think you can get two different transactions (two transactions that are exactly the same as far as scriptPubKeys, but spend different outputs) that hash to the same value, which would cause all sorts of problems, including replay attacks re-using old signatures.


Interesting... too radical a change for right now, in my opinion.  (I think Pieter's proposal is too radical a change for right now, too... I'm on the fence about whether OP_EVAL is too radical a change, but I think the advantages outweigh the risks).


Pieter's proposal is <signature+2bits>

In an effort to keep discussion on track, I split the discussion of Lamport versus Bernstein signature schemes into its own thread.

So: can anybody think of any potential attacks that would be enabled by having a standard form:

... spent by providing:

The simplest <serialized script> would be <pubkey> CHECKSIG.


Things that occur to me or were brought up in the IRC discussion:

• Denial-of-service if <serialized script> is allowed to contain OP_EVAL.
  
  Proposal on the table is to completely disallow recursion, which eliminates that threat.  I'm tempted to allow limited recursion (max 2 levels deep maybe) because it would allow some really cool things to be done in the future....
  
• Stealing coins because old miners/clients will not verify the signature hidden inside <serialized script>.
  
  If 50+% of the hashing power on the network support OP_EVAL, then transactions that pass the <scripthash> check but fail the signature check inside the <serialized script> would be accepted as valid by old miners and clients, but would fail to confirm because they would be rejected by the majority of miners.
  
  That CANNOT be used to trick exchanges or people using old software, because the old software will not recognize the new script form, and will simply ignore the transaction-- you will not get "0/unconfirmed" OP_EVAL transactions displayed in old versions of Bitcoin. Wrong again!  See casacius' excellent response.
  
• Creating or modifying <serialized scripts>
  
  Maybe there's an attack waiting to happen because an attacker could trigger a buffer overflow bug by doing something like:
  <safe serialized script>  119 OP_ADD  OP_EVAL
  But if there is a buffer overflow bug in an implementation's transaction script interpreter, then an attacker can almost certainly just send a "tx" message containing a non-OP_EVAL script that triggers the bug. OP_EVAL certainly does mean one more thing for an implementation to get right, but it isn't actually very hard to implement if you're already able to validate "tx" messages.
  

Any other attacks anybody can think of? If implementations are strict in which transaction forms they'll accept as "valid AND mine (counts towards my wallet balance)", but liberal in what transaction forms they'll accept as "valid, but I can't spend it" then it seems to me the risks are small.

The threat isn't that someone could send an OP_EVAL transaction directly to an old version of Bitcoin... rather, they would send two transactions.  They would construct a transaction that fakespends the OP_EVAL transaction to a temporary address, and then a standard transaction from the temporary address to the victim's address.  The old versions of Bitcoin would display the second transaction afaik, though updated miners would reject them both.

My view: the current Bitcoin design has been carefully reviewed and found to be strong. People like Kaminsky have tried their best and not discovered any issues.

Major structural design changes like OP_EVAL invalidate all those assurances and put Bitcoin back at square one. I'm not seeing the benefit. Disk space is cheap, and pruning would reclaim far more than shrinking transactions by a small amount. Lightweight clients don't even care.

If there are going to be changes to the basic design of the system, it'd be better to actually fork the chain and make people choose between the old/new rulesets. Old users would find transactions no longer confirm and peers disconnect them. Weird hacks like reusing a NOP risk silently invalidating the security properties of earlier versions without those users realizing, something none of those people would have anticipated.

The Bitcoin design Satoshi left has a ton of mileage left in it. There are surely more important problems to solve than a slightly better scripting system. A working bitcoin: URI handler would be a good start.

Just wanted to make sure it was clear that the purpose of OP_EVAL is not to save disk space.  It's to enable transactions to normal Bitcoin addresses that require a multi-sig script to be respent, without burdening the sender of the coins with the logistical challenge of providing that script to the block chain.  The multi-sig script significantly enhances security, because it enables arrangements where no one party (other than the owner) and/or no one machine has all of the key material in one place necessary to spend coins when they are received.  And, as you're surely aware, the reports of rampant Bitcoin theft have been a dark cloud that repels people from bitcoin.  This is a serious solution to that.

If Satoshi didn't intend for anything like this to be added, he wouldn't have had a reason to implement a scripting engine in the first place.  Transactions would just have "inputs" and "outputs" and nothing more.

He wouldn't have included NOP1 through NOP10, either.

I file this under "Satoshi is a genius, part 9,432".  It gives a smooth upgrade path using the same blockchain if ECDSA or SHA256 start to get fragile.

Attacking old clients by sending them coins with "will-never-be-satisfied-but-they-can't-tell-that" inputs is a concern-- it is basically the Finney attack, but anybody will be able to try to pull it off and there is no time constraint.

However, I think the benefits of being able to send to a truly secure address FAR outweigh the risks, I don't think it will be difficult to get people to upgrade to a newer, more secure client, and accepting 0- or 1-confirmation transactions is always a bad idea.

I also think you're exaggerating the impact-- OP_EVAL does not invalidate all of the security review that has been done so far, especially if the scripting language being EVAL'ed is unchanged from what we have today.

(PS: the latest git-head QT bitcoin contains a working bitcoin URI handler)

I think this is an important point. Currently the analysis that we do is rather ad-hoc and reliant on us thinking of various exploits and how to prevent them. What we should do, as Mike implies is to look at what security guarantees the existing system provides and then systematically check that any proposed changes do not unexpectedly compromise those guarantees.

From the information given, and from the implementation of OP_EVAL that I imagine, I'm having trouble thinking of the assurances that are invalidated by OP_EVAL.

Could you please provide more details Mike?

ByteCoin

It invalidates the assurances because it changes in an unintuitive way the basic Bitcoin protocols. This is more about perception rather than reality. The current design has been shown to be strong. Even if you provide a sound argument for why OP_EVAL does not introduce any other holes, everyone who has already convinced them of Bitcoins correctness now has to go back and convince themselves again. Look how long and complicated the first post is! If this is implemented, everyone working with the system needs to go and read/understand it.

This is a huge cost that must be justified with huge benefits, but there are none.

Let me go through the proposed advantages one by one (I did this on IRC already):


As far as I know, most complex script types are used for contracts, which have multi-step protocols anyway. The whole concept of an "address" wasn't emphasized much in the original Bitcoin release, send-to-IP was seen by Satoshi as the most likely way to make payments, because it allowed for negotiation (obtaining a new key automatically).

I don't think addresses for arbitrarily complex transactions will ever be useful. Show me 3 complete, well specified use cases for this where a static address is the best solution (over files or protocols) and I might change my mind. Even for one-to-one payments a protocol is normally a better solution because you want a new key for each payment.


See above. Most likely addresses will eventually go away and not be seen by end users except in unusual circumstances. If you think like a product designer, addresses should not be as prominent as they are today - they're opaque binary strings meaningful only to machines, and presenting them in base58 doesn't change that. It's bad UI to have them so visible.


Senders should never be burdened with fees, period, because it's not the sender who cares about double spends. That this is how the protocol works today is a technical detail, not how you'd actually design things from the users perspective.

The simplest solution to this problem is not to completely change the scripting system. It's for senders to send a transaction directly to the recipient, who can then attach another one including a fee of their own choosing and transmit both. A change to the priority calculation rules to recursively calculate fees of dependents would mean that miners include several free transactions in order to claim the fee on the last one.

In this way, a group that trusts each other (like a family) can potentially trade coins without any fees at all, even post-inflation, because none of them need the networks help to avoid double spends. It means some changes to how Bitcoin users do things (sending payments as files rather than being given an address) but nothing particularly revolutionary. It'd solve a bunch of UX problems at the same time, like automatically labelling transactions.

If you don't want two transactions where today there'd be only one, have inputs be signed with SIGHASH_ALL | SIGHASH_ANYONECANPAY so the recipient can add their own input before broadcasting it. But implementing transaction pruning means two transactions instead of one doesn't boil down to any more disk space over the long run because the first transaction will get pruned away.

I think there are some premature assumptions about how two-factor coins will work here. It'd help if somebody wrote a full design doc containing not just the changes to IsStandard() but how everything else is supposed to work too. Gavin mentioned a third party service provider/website that holds one of two keys, and sends you an SMS to confirm payment. Once you start to think about this in detail, it becomes clear that it to protect you against a compromised host the SMS must contain a human-readable description of the recipient and not an address, otherwise the virus can simply pick an address of its own choosing and replace the one you intend to pay with that one. It couldn't change the amount you want to pay as presumably that'd be included in the SMS, but if it waits around until you decide to make a big payment it could probably steal a lot.

So fixing the identity problem should really come before fancy scripting language changes. But I don't see much talk about doing that, even though it's a much simpler task.

There are a few different issues here.

The first is the initiation of transactions. The OP_EVAL proposal above implies an address type of the form Base58(XXX + v), corresponding to a txout <OP_DUP OP_HASH160 <XXX> OP_EQUAL OP_EVAL>. This seems to be the primary reason for advocating OP_EVAL, and I'm not sure it should be. It is very powerful, but I keep believing that secondary protocols that negotiate a transaction output are the way to go (see this proposal (https://gist.github.com/1237788) for an idea). There may be some legitimate advantages as well though; Gregory had an example where hashed OP_EVAL scripts could be used to increase anonymity in case of OR-based outputs.

The second is the introduction of a new script language. By retrofitting OP_NOP1 as OP_EVAL, it does not necessarily need a block chain fork, and we have the ability to modify the semantics of the language. This has massive possibilities, and should be dealt with very carefully. This is independent from the introduction of a new address type - a simple <<script2> OP_EVAL> txout script can be used, with <script2> a txout script obtained through any means. I did a proposal for improvements to the script language here (https://gist.github.com/1262449), but much more discussion is necessary before we do such a thing. Casascius' idea of two conflicting transactions makes me worry though - that may be enough to not use the OP_NOP-based mechanism at all.

RE: 0-confirmation OP_EVAL transactions:

I think I'm doubly-wrong.

OP_EVAL transactions are non-standard to old clients, so they are dropped before being added to the memory pool.  Old clients will not relay them, old miners that follow the IsStandard rules won't put them in blocks.

When a transaction comes in that depends on a transaction that is not in the block chain or memory pool, it is shunted into the orphan transaction pool, and isn't listed by listtransactions or show up in the GUI until all of its inputs are satisfied.

The risk would be a rogue miner putting invalid OP_EVAL transactions into blocks, which would trick old clients into showing transactions that depend on them as 0/ or 1/unconfirmed.


RE: "but bitcoin addresses are UGLY and the WRONG way to do it!"

Okey dokey.  If I recall correctly, people were saying exactly the same thing about URLs 10 years ago (...google... yup (http://www.useit.com/alertbox/990321.html)).

If your argument is OP_EVAL is possibly insecure... it seems to me it is much easier to reason about the security of OP_EVAL than to reason about the security of URI schemes or schemes for passing around a transaction to be signed or using SIGHASH_ANYONECANPAY.

I agree that protocols for passing around either transactions or signatures are needed, I just don't think agreeing on what those protocols aught to be will happen anytime soon (how much you want to bet there will be a protocol buffers versus JSON debate that rages on for at least six months?)

RE: writing up a full design doc: I've always admired the IETF's "rough consensus and running code" approach to standards-making, so I'll be happy to write up a full design doc after I've got running code.  Actually trying to IMPLEMENT multisignature transactions has taught me a whole lot about what will work in practice and what won't.


Finally, to try (in vain, probably) to focus discussion:  The use cases I care about are:

1. A user running bitcoin on a device that gets infected by malware. I want them to be able to subscribe to some service that will provide transaction confirmation for any outgoing bitcoin transactions above a certain amount per day (like my bank does with my ATM card).

2. And I want them to be able to have a 'master wallet key' stored in physical form in their safe-deposit box so they can recover their wallet if they forget their passphrase or lose all their backups.

OP_EVAL appeals to me because I can see EXACTLY how to make those use-cases work with minor variations to the infrastructure we have today for performing bitcoin payments.

Except there's a huge problem in your logic: you're not thinking with portalsBitcoins...

Let's take your supermarket cashier. What if they never needed to give change and weren't authorized to provide refunds? Would businesses instead decide that a dropbox for the money instead of a register would be better? Say, then, that managers were allowed to give refunds. It would make sense to give the managers a key to each dropbox. However, managers also often steal, too. So, the manager could only open the box if a cashier or another manager was there (in case a manager was subing for a cashier), thus the need for multi-sig transactions. Each dropbox can be emptied into the owner's account nightly. As you can see, this meets an existing business need without exposing the money to the front-line cashier and making the customer worry about semantics.

Next, let's take your wonderful check example. It's the closest thing we have to what we're actually talking about.

When you give an OP_EVAL address, that is exactly what you're doing. However, you're missing a crucial point: While it's true that the organization puts the procedures in place internally for accessing the funds, what's stopping some random employee from going to the bank to withdraw all the money anyway? The answer is: the bank itself. How does the bank know who can withdraw funds? Because you told them who could withdraw funds written out to the organization's name. OP_EVAL is the same. The customer doesn't need to worry about what names to put on the check, just the organization's name. Yet, that name maps to only certain people that can access the funds, not the entire organization.

Where I stand: I like OP_EVAL as a feature, but agrees with Mike's concerns.

Thoughts:
1. I want the technology(bitcoin network itself) to caress less of the human element as possible, in addition I feel these things can cared for not part of the network such as the Mastery Key, escrow generally suffers from the same problem imo, but that's more subjective.

2. Any big changes, especially on this level needs better communication between possibly the major pool administrators and the miner population to insure the changes propagate through the network and that people upgrade as needed, again this is another human element of the problem.

until proper and failsafe ways and upgrade method are introduced, I'm in the "hold off on radical changes" club.

Whats been proposed here is a generic mechanism that would be useful even if we only had machine to machine transactions.  I'm not seeing how other mechanisms can provide what op_eval provides, especially not without having more parties to trust.  Can you elaborate further on this point?

There have been a number of proposals that would make this more safe to deploy, e.g. using a flag in the coinbase to perform a majority vote of hashpower to decide the height to enable the feature.  Someone obviously needs to talk to some of the bigger miners and see if they have other concerns that need to be addressed but I don't see why a hashpower vote isn't sufficient, since the feature is non-forking.

I pulled a Satoshi and decided to implement OP_EVAL to make sure it would actually work.
  https://github.com/gavinandresen/bitcoin-git/tree/op_eval (https://github.com/gavinandresen/bitcoin-git/tree/op_eval)

Not ready for pulling, expect rebasing/tweaking/changing. But it is fully working on the testnet.
(example transaction here (http://blockexplorer.com/testnet/tx/f5eb769eff73a4781b600064ac16dff54e039994e7dedb77903a19b5edec1fc7))

The code puts "OP_EVAL" in the coinbase of generated blocks, so the rest of the network can see how many miners support it.

I gathered contact information for the top ten mining pools last week; when there is rough consensus on the details, I'll contact them to see if they have concerns and/or are willing to support OP_EVAL.

I started writing up BIPs for the various pieces of OP_EVAL, I'll post them soon.

Draft BIPs, comments very welcome:

https://github.com/gavinandresen/bitcoin-git/wiki/BIP-OP_EVAL (https://github.com/gavinandresen/bitcoin-git/wiki/BIP-OP_EVAL)
https://github.com/gavinandresen/bitcoin-git/wiki/BIP-Bitcoin-Address-01 (https://github.com/gavinandresen/bitcoin-git/wiki/BIP-Bitcoin-Address-01)
https://github.com/gavinandresen/bitcoin-git/wiki/BIP-M-of-N-Standard-Transactions (https://github.com/gavinandresen/bitcoin-git/wiki/BIP-M-of-N-Standard-Transactions)

Why allow recursion? Is there a use-case for this?

Yes. Although there might be a way of accomplishing the same thing without recursion:

Use case:

Imagine we want, in the future, to support "this" OR "that" transactions.  Where "this" and "that" are themselves possibly complex multisignature or escrow or whatever transactions.

Most straightforward way might be a new standard transaction that looks like:


So you'd redeem it by putting one script or the other on the stack (along with the signatures needed by the script).

So.... maybe you want to recurse so that the IF/ELSE script is itself part of a standard, single-hash OP_EVAL, so you can use a newfangled bitcoin address to send to it.  That would look like:


I am NOT proposing an IF/ELSE "this or that" standard script type; I think there is plenty of enough work to do to actually make secure wallets and in-the-chain escrow work.  But supporting limited recursion for non-standard or future transactions seems easy and safe...

(terminology footnote:  calling scriptSig+scriptPubKey "transactions" isn't accurate, the transaction is the bigger thing, but I'm not sure what else to call them; I hope y'all follow what I'm saying)

ByteCoin has mentioned (https://bitcointalk.org/index.php?topic=20955.msg264038#msg264038) flaws with the current address checksum method. Address version 1 could maybe use a better scheme from the start.

Scripts executed by OP_EVAL could use a fixed version of OP_CHECKMULTISIG that doesn't eat an extra stack item. Some disabled opcodes could also be enabled.

Someone could probably design such an error correcting code with better performance (e.g. strong resistance to near misses)— but the implementation would be non-trivial... Not that sha256 is trivial, but people already have it available.  This may make people who want e.g. JS validation of addresses a bit irritated.

You don't have to switch hash functions, just increase the number of bits you include in the checksum.

Yuck.  And _still_ not get complete resistance to common typos.

32bits is already enough to detect all cases of up to to _5_ errored characters (and even correct fewer errors, if you want... as well as detecting many but not all cases of other errors).  This gets you immunity to many typos as well as all simple transpositions.  This is better than you're going to get even with increasing the hash size further. (figuring out the handling of dropped/doubled characters is harder, but the encoding should just be made constant length, which would make that easier to detect and easier to validate)

I don't know nuthin about error-detecting checksums, but I think the time it would take to implement it and argue about it would be better spent on more user-friendly, secure ways of making bitcoin payments. I haven't heard of even a single case of "I manually typed in a bitcoin address and the coins got lost because I made an undetected transposition error."

That's kinda my point. Even if this were a problem (I have yet to see or think up a practical exploit), you could just add a few extra bytes instead of wasting time researching and implementing a true error-detecting checksum.

Somehow I suspect that ByteCoin had to do a programmatic brute force search to come up with two valid addresses that differ by one character.  (And incidentally, I strongly doubt he can receive bitcoins at either of them, nor could he find a pair of Bitcoin addresses differing by 1 character that he could receive at both of).

The pure odds of a typo being uncaught, if I understand it right, is 1 / 2^32... someone would have to be extremely unlucky to lose their bitcoins to a typo.

Looking at the pure odds is misleading because for any given address the detectable errors might be all the impossible to type errors while the undetectable errors might be all the easy ones.  So sure, 1/2^32 overall, but in reality it takes the form of some addresses that are harder than that to mistype and a great many which are much easier than that to mistype.  This is why people almost always use CRC's rather than randomized hashes when the check data is as small as 32 or 64 bits.  Randomly distributed, 32 bits is not much protection and you can usually say something about the likely errors.

I don't see how to make an attack out of it— you could search for an address that was easily mistyped quite quickly e.g. with vanitygen  but finding a pair seems kind of implausible to me.

On reflection, the code for this would be simpler than I thought because you only need code for an encoder if you're not interested in recovering corrupted addresses only validating against errors. If we were using base 32 or 64 I'd already have code for it and it would only be a couple of lines and a small table. I'll give it a try this week and post a proposal if I get something I think sounds attractive... on a different thread. Sorry for feeding the tangent here.

Personally, I'd like to see the checksum being done with error correcting codes, like reed-solomon codes. Not because it improves error detection but because it allows for automatic error recovery. 4 bytes of reed-solomon code would be enough to fix up to 2 bytes of error in the address. Error detection would be guaranteed for up to 4 bytes of error.

the base-58 encoding slightly degrades the effectiveness in some cases, though. With base-58 encoding, it's entirely possible to get 2 byte error in the decoded content with an error in just one unlucky position in the base-58 encoded string.

This is not all that important for the functioning of the system but it would be more user friendly for those who have to type the address in manually for whatever reason. This way, the system could handle a typo or two without requiring the user to retype the address. To me, this looks like a choice to the same direction as choosing base-58 encoding instead of base-64 was.

- Joel

Individual base58 characters don't map to sections of bits, so any error would change every single byte in the decoded data. Some special error correcting code is need here; I don't think normal ones apply if base58 is used.

You can do the RS code over the digits directly. It's so much nicer if the base is a 2^n however. :(  E.g. if we were using a base 64 the implementation of the encoder (/checker) would be just a few lines of code and a table.

Ah, that's good. When I was looking around for different RS implementations, I saw it written somewhere that it requires base 2^n. Good to know this isn't the case. I'm looking forward to seeing your code :)

- Joel

Actually, I am quite disturbed with implications of shifting the burden of fees to the receiver (as transaction fees are at least partially dependent on conditions that only the sender is exposed to, such as for instance whether the sender's balance is made up of a bajillion of tiny 0.5 BTC inputs)

I'll PM theymos so that he can convince me without turning this topic into a rehash of something he might have already discussed and explained in detail


In my very humble opinion, giving "new and exciting" types of BTC transactions a different address type (either as "catch-all" for all innovative transactions or have a separate address type for each "officially supported" new transaction type,) to avoid confusion and help people grok new and fairly complicated functionality more easily.

Methinks that different addresses for exotic transactions will actually increase usability, especially for "the kind of person" who only lives in GUI and won't touch the  user manual :) unless ABSOLUTELY necessary

With OP_EVAL, the fees for inputs will stay with the sender, while the fees for the output are moved to the receiver (who'll pay them when he uses them as inputs). So what OP_EVAL does is make everyone responsible for their own stuff.

fair enough, now i understood what what was meant with that feature. This will enable all merchants treat sub cent amounts like any other quantity, not having to take fees into consideration.

Ah, now IC the rational core of the concern, no need to bother theymos :)

However... How does the receiver get to know what his fees will be like ?

Let's say I want you to send me an escrow-OP_EVAL transaction. I want you to send, like... oh, 5 BTC.

It would be very unkosher if there would be no way for me to know in advance what fee to expect "on my end" after the escrow authority signs stuff (oh noes, it ated 3 BTC out of 5!  :D )

I expect it'll be dependent on the size of the transaction needed to use the OP_EVAL output. That has to be known in advance, otherwise you can't create a spendable OP_EVAL output. Of course, the actual fees will depend on the democratic (well, more or less) decisions from the miners.

Well, as long as it essentially ends up being dependent on something deterministic - like "output"'s size, it should be fine.

I'd still prefer "new and brave" transactions to use a different address format though.

Then every merchant will have to update clients whenever users want to use a new transaction type. With OP_EVAL, a merchant could keep running the same version for years (assuming there are no bugs) and still send transactions using the latest scripts.

It also improves decentralization, since there will be no need to coordinate assignment of address version numbers. (And there are only 256 address version numbers to assign -- too few to cover all scripts.)

People who request an OP_EVAL transaction will know exactly how many extra bytes it will take to redeem the transaction. They shouldn't be surprised by fees.

Pardon if I am being slow, but does OP_EVAL allow for crafting new and wonderful transaction type through RPC ?

I thought that every new exotic transaction implemented by this way will still require one to implement it in the code and compile...


Quite frankly, the implications of having more than 10 (let alone more than 256) distinct transaction types, each with unique "quirks" in operation, are disturbing.

The GUI will end up being like a fighter jet cockpit, for one.

I'd still like to have at least two distinct address forms, one for "simpleton" transactions (like what we have now), another for everything else, just to make demarcation between "basic" functionality and "advanced user features" more explicit. Because you know, people have trouble grokking Paypal interface (and bitcoin GUI), and having them away from getting involved with complicated 5-party signing schemes until they really know what they are doing would be wise.
 

With all due respect, you overestimate the average user.

No, OP_EVAL allows the person paying to pay the recipient (who has provided the address) by any transaction type imaginable. That is, even without any support for the particular transaction type in the payer's wallet. That's because OP_EVAL makes it unnecessary for the wallet software to understand the output.


Because OP_EVAL encodes the transaction type in the address itself, no-one ever needs to receive transaction types they don't support. So wallet software can pick and choose. With OP_EVAL the wallet software creator is free to choose which transactions it can handle and ignore others (because, well, you just won't give out any addresses for transactions you don't support).

Important thing to note here is the separation of wallet and node. Node needs to be able to handle the scripts of any transactions that are possible. However, wallet software doesn't have this need.

Well, Gavin explained in #bitcoin-dev that the plan is actually to have two addresstypes, one for "vanilla" old-timer transactions, and another as catch-all for "advanced" OP_EVAL stuff, which is something I am quite fine with.

Now, the transaction type pluralism is mildly disturbing. People manage to terribly screw up (and whine) with just one transaction type exposed to them and supported on all client soft, I can only imagine the magnitude of chaos when there is a whole load of divergent transaction types with affinity to a particular type of wallet software.

Good thing BTC is not a corporation. We'd have to hire entire India and most of Ukraine for tech support :D

The average user won't have to worry about it. If you enable the feature where a second device is required for spending, the client will just start giving you addressversion-1 addresses. You won't notice any other change, since the client will handle everything.

I think you slightly misunderstand me here. I definitely can see multisigns being fairly user-transparent and friendly.

256+ "exotic" transaction types ? not so much. But I guess it is best to start discussing the issue when a lot of "exotic" stuff starts popping up.

As long as exotica goes to a separate addresstype and Auntie can keep sending coins the old way, oblivious to the "pro stuff", I am okay.

Bump.

I know the proposal has been withdrawn, but I wondered if people thought OP_EVAL should be implemented some day, perhaps far in the future.

Most if not all of the real world use cases for OP_EVAL are handled by P2SH.

Is OP_EVAL functional on testnet?

Pay-to-script-hash (P2SH) is functional on testnet and mainnet.  OP_EVAL has long been superceded and discarded.