OP_EVAL proposal

[Gavin Andresen]

Draft BIPs, comments very welcome:

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-M-of-N-Standard-Transactions

[maaku]

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

[Gavin Andresen]

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 <hash160> EQUAL
IF
  OP_EVAL      "evaluate the this"
ELSE
 DUP HASH160 <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:  <signatures> <this_or_that_script> <IF/ELSE script>
scriptPubKey:  DUP HASH160 <hash of IF/ELSE script> 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)

[theymos]

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.

[gmaxwell]

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.

[maaku]

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

[gmaxwell]

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)

[Gavin Andresen]

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

[maaku]

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.

[casascius]

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.

[gmaxwell]

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.

[jojkaart]

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

[forrestv]

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.

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.

[gmaxwell]

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.

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.

[jojkaart]

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

[Lolcust]

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.[/li][/list]

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

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

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

[jojkaart]

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

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.

[paraipan]

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

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.

[Lolcust]

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

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.

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

[jojkaart]

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

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.