Pages:
Author

Topic: OP_EVAL proposal - page 2. (Read 13102 times)

staff
Activity: 4284
Merit: 8808
October 20, 2011, 07:08:20 AM
#51
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.
vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
October 19, 2011, 11:25:35 PM
#50
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.
legendary
Activity: 905
Merit: 1012
October 19, 2011, 09:50:00 PM
#49
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.
legendary
Activity: 1652
Merit: 2301
Chief Scientist
October 19, 2011, 08:17:00 PM
#48
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."
staff
Activity: 4284
Merit: 8808
October 19, 2011, 07:42:19 PM
#47
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)





legendary
Activity: 905
Merit: 1012
October 19, 2011, 06:25:36 PM
#46
You don't have to switch hash functions, just increase the number of bits you include in the checksum.
staff
Activity: 4284
Merit: 8808
October 19, 2011, 05:08:30 PM
#45
ByteCoin has mentioned 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.

administrator
Activity: 5222
Merit: 13032
October 19, 2011, 04:18:17 PM
#44
ByteCoin has mentioned 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.
legendary
Activity: 1652
Merit: 2301
Chief Scientist
October 19, 2011, 04:04:22 PM
#43
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:

Code:
DUP HASH160 EQUAL
IF
  OP_EVAL      "evaluate the this"
ELSE
 DUP HASH160 EQUALVERIFY
 OP_EVAL       "... or evaluate the that"
ENDIF

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:

Code:
scriptSig:  
scriptPubKey:  DUP HASH160 EQUALVERIFY OP_EVAL

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)
legendary
Activity: 905
Merit: 1012
October 19, 2011, 03:06:19 PM
#42
Why allow recursion? Is there a use-case for this?
legendary
Activity: 1652
Merit: 2301
Chief Scientist
October 19, 2011, 08:54:26 AM
#40
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

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

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.



staff
Activity: 4284
Merit: 8808
October 19, 2011, 07:47:53 AM
#39
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.

full member
Activity: 121
Merit: 100
October 19, 2011, 02:49:43 AM
#38
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.


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.
legendary
Activity: 1204
Merit: 1015
October 07, 2011, 11:23:20 AM
#37
legendary
Activity: 1652
Merit: 2301
Chief Scientist
October 07, 2011, 07:41:26 AM
#36
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).

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.
legendary
Activity: 1072
Merit: 1181
October 07, 2011, 05:43:08 AM
#35
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_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 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 < OP_EVAL> txout script can be used, with a txout script obtained through any means. I did a proposal for improvements to the script language here, 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.



legendary
Activity: 1526
Merit: 1134
October 07, 2011, 03:42:15 AM
#34
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):

Quote
Addresses for arbitraritly complex transactions are fixed forever. No more new address types need be introduced.

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.

Quote
Addresses need only be same length as the current ones, forever.

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.

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.

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.
sr. member
Activity: 416
Merit: 277
October 06, 2011, 08:00:00 PM
#33
Major structural design changes like OP_EVAL invalidate all those assurances and put Bitcoin back at square one.

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
legendary
Activity: 1652
Merit: 2301
Chief Scientist
October 06, 2011, 06:06:47 PM
#32
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)
Pages:
Jump to: