Bitcoin Forum
December 06, 2016, 04:22:12 PM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: « 1 2 [3] 4 »  All
  Print  
Author Topic: OP_EVAL proposal  (Read 10852 times)
Gavin Andresen
Legendary
*
qt
Offline Offline

Activity: 1652


Chief Scientist


View Profile WWW
October 19, 2011, 07:20:24 PM
 #41

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


How often do you get the chance to work on a potentially world-changing project?
1481041332
Hero Member
*
Offline Offline

Posts: 1481041332

View Profile Personal Message (Offline)

Ignore
1481041332
Reply with quote  #2

1481041332
Report to moderator
1481041332
Hero Member
*
Offline Offline

Posts: 1481041332

View Profile Personal Message (Offline)

Ignore
1481041332
Reply with quote  #2

1481041332
Report to moderator
1481041332
Hero Member
*
Offline Offline

Posts: 1481041332

View Profile Personal Message (Offline)

Ignore
1481041332
Reply with quote  #2

1481041332
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
maaku
Legendary
*
expert
Offline Offline

Activity: 905


View Profile
October 19, 2011, 08:06:19 PM
 #42

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

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
Gavin Andresen
Legendary
*
qt
Offline Offline

Activity: 1652


Chief Scientist


View Profile WWW
October 19, 2011, 09: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 <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)

How often do you get the chance to work on a potentially world-changing project?
theymos
Administrator
Legendary
*
expert
Offline Offline

Activity: 2492


View Profile
October 19, 2011, 09: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.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2016



View Profile
October 19, 2011, 10: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.

maaku
Legendary
*
expert
Offline Offline

Activity: 905


View Profile
October 19, 2011, 11:25:36 PM
 #46

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

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2016



View Profile
October 20, 2011, 12:42:19 AM
 #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)





Gavin Andresen
Legendary
*
qt
Offline Offline

Activity: 1652


Chief Scientist


View Profile WWW
October 20, 2011, 01:17:00 AM
 #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."

How often do you get the chance to work on a potentially world-changing project?
maaku
Legendary
*
expert
Offline Offline

Activity: 905


View Profile
October 20, 2011, 02:50:00 AM
 #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.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
casascius
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1344


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
October 20, 2011, 04:25:35 AM
 #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.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper wallets instead.
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2016



View Profile
October 20, 2011, 12:08:20 PM
 #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.
jojkaart
Member
**
Offline Offline

Activity: 97


View Profile
October 27, 2011, 03:08:13 PM
 #52

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
Hero Member
*****
expert
Offline Offline

Activity: 510


View Profile
October 27, 2011, 03:39:56 PM
 #53

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.

1J1zegkNSbwX4smvTdoHSanUfwvXFeuV23
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2016



View Profile
October 27, 2011, 03:53:24 PM
 #54

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. Sad  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
Member
**
Offline Offline

Activity: 97


View Profile
October 27, 2011, 04:01:24 PM
 #55

You can do the RS code over the digits directly. It's so much nicer if the base is a 2^n however. Sad  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 Smiley

- Joel
Lolcust
Member
**
Offline Offline

Activity: 112


Hillariously voracious


View Profile
November 07, 2011, 12:35:38 PM
 #56

    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 Smiley unless ABSOLUTELY necessary

    Geist Geld, the experimental cryptocurrency, is ready for yet another SolidCoin collapse Wink

    Feed the Lolcust!
    NMC: N6YQFkH9Gn9CTm4mpGwuLB5zLzqWTWFw67
    BTC: 15F8xbgRBA1XZ4hmtdFDUasroa2A5rYg8M
    GEG: gK5Lx6ypWgr69Gw9yGzE6dsA7kcuCRZRK
    jojkaart
    Member
    **
    Offline Offline

    Activity: 97


    View Profile
    November 07, 2011, 12:42:19 PM
     #57


    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
    Legendary
    *
    Offline Offline

    Activity: 924


    Firstbits: 1pirata


    View Profile WWW
    November 07, 2011, 12:49:27 PM
     #58


    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.

    BTCitcoin: An Idea Worth Saving - Q&A with bitcoins on rugatu.com - Check my rep
    Lolcust
    Member
    **
    Offline Offline

    Activity: 112


    Hillariously voracious


    View Profile
    November 07, 2011, 12:52:01 PM
     #59


    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 Smiley

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

    Geist Geld, the experimental cryptocurrency, is ready for yet another SolidCoin collapse Wink

    Feed the Lolcust!
    NMC: N6YQFkH9Gn9CTm4mpGwuLB5zLzqWTWFw67
    BTC: 15F8xbgRBA1XZ4hmtdFDUasroa2A5rYg8M
    GEG: gK5Lx6ypWgr69Gw9yGzE6dsA7kcuCRZRK
    jojkaart
    Member
    **
    Offline Offline

    Activity: 97


    View Profile
    November 07, 2011, 01:05:47 PM
     #60

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

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

    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.
    Pages: « 1 2 [3] 4 »  All
      Print  
     
    Jump to:  

    Sponsored by , a Bitcoin-accepting VPN.
    Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!