Pages:
Author

Topic: OP_EVAL proposal - page 3. (Read 13104 times)

vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
October 06, 2011, 05:14:50 PM
#31
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.

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.
legendary
Activity: 1526
Merit: 1134
October 06, 2011, 04:41:26 PM
#30
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.
vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
October 06, 2011, 03:32:09 PM
#29

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.


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.
legendary
Activity: 1652
Merit: 2301
Chief Scientist
October 06, 2011, 09:16:05 AM
#28
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:

Code:
DUP HASH160 EQUALVERIFY OP_EVAL
... spent by providing:
Code:

The simplest would be CHECKSIG.


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

  • Denial-of-service if 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 .

    If 50+% of the hashing power on the network support OP_EVAL, then transactions that pass the check but fail the signature check inside the 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

    Maybe there's an attack waiting to happen because an attacker could trigger a buffer overflow bug by doing something like:
     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.
legendary
Activity: 1652
Merit: 2301
Chief Scientist
October 05, 2011, 01:21:46 PM
#27
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.

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

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

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

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

Pieter's proposal is
sr. member
Activity: 416
Merit: 277
October 04, 2011, 06:53:42 PM
#26
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" 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
legendary
Activity: 1072
Merit: 1181
October 04, 2011, 04:38:16 PM
#25
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, 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
legendary
Activity: 1652
Merit: 2301
Chief Scientist
October 04, 2011, 08:51:43 AM
#24
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():
Quote
WARNING: Displayed transactions may not be correct!  You may need to upgrade, or other nodes may need to upgrade.

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.
vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
October 03, 2011, 09:31:47 PM
#23
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."
sr. member
Activity: 416
Merit: 277
October 03, 2011, 09:08:11 PM
#22
I must credit sipa as first raising this issue as far as I know.
If we did the obvious thing and used [a current OP_NOPx] for OP_EVAL, then, surprisingly, OP_EVAL would not necessarily cause a block chain split.

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

staff
Activity: 4284
Merit: 8808
October 03, 2011, 10:13:14 AM
#21
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.

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.
legendary
Activity: 1652
Merit: 2301
Chief Scientist
October 03, 2011, 08:43:53 AM
#20
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.
newbie
Activity: 2
Merit: 0
October 02, 2011, 11:40:04 PM
#19
Quote
    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.
vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
October 02, 2011, 10:28:41 PM
#18
Quote
    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.
newbie
Activity: 2
Merit: 0
October 02, 2011, 08:25:51 PM
#17
Quote
    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.

Quote
    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.
legendary
Activity: 1652
Merit: 2301
Chief Scientist
October 02, 2011, 03:42:32 PM
#16
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:
<...serialized script...>  DUP HASH160 EQUALVERIFY OP_NOP1
New clients see:
 
Code:
<...serialized script...>  DUP HASH160 EQUALVERIFY OP_EVAL

Old clients will consider the transaction valid as long as 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 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?
legendary
Activity: 905
Merit: 1012
October 02, 2011, 12:33:20 PM
#15
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_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.
legendary
Activity: 1652
Merit: 2301
Chief Scientist
October 02, 2011, 12:05:36 PM
#14
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.
legendary
Activity: 1232
Merit: 1076
October 02, 2011, 11:55:15 AM
#13
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).
newbie
Activity: 43
Merit: 0
October 02, 2011, 11:37:43 AM
#12
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.
Pages:
Jump to: