Bitcoin Forum
December 06, 2016, 12:08:05 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  
Poll
Question: Should Bitcoin clients tolerate typos in addresses?
No, just reject them - 2 (8.3%)
No, but tell the user why it's being rejected - 16 (66.7%)
Yes, accept them-- ideally with a warning - 3 (12.5%)
Yes, accept them silently - 2 (8.3%)
Yes, let's make these "standard" base58 - 1 (4.2%)
Total Voters: 24

Pages: [1]
  Print  
Author Topic: Typo-tolerant base58 for Bitcoin clients  (Read 1227 times)
Luke-Jr
Legendary
*
expert
Offline Offline

Activity: 2086



View Profile
October 05, 2011, 03:23:08 PM
 #1

One of my pull requests for bitcoin{d,-qt} makes it tolerate typo'd base58 data-- specifically, zero and uppercase 'o' are treated as a lowercase 'o'; and lowercase 'L', pipe, and exclamation point are treated as a one.

Gavin thinks such a change needs a consensus, so please vote. Smiley

Edit: Please note: this would only tolerate typos when it is certain to be correct. It does not make guesses that could be wrong. There is a checksum to prevent that.

Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481026085
Hero Member
*
Offline Offline

Posts: 1481026085

View Profile Personal Message (Offline)

Ignore
1481026085
Reply with quote  #2

1481026085
Report to moderator
Bitcoin Oz
Hero Member
*****
Offline Offline

Activity: 700


Wat


View Profile WWW
October 05, 2011, 03:28:20 PM
 #2

I voted no but send people a warning. If you've ever used an iphone you'd understand how retarded autocorrect is.   Tongue


Luke-Jr
Legendary
*
expert
Offline Offline

Activity: 2086



View Profile
October 05, 2011, 03:48:00 PM
 #3

I voted no but send people a warning. If you've ever used an iphone you'd understand how retarded autocorrect is.   Tongue
That doesn't apply here. If the correction is wrong, it still won't work. That's what the checksum is for.

ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
October 05, 2011, 04:04:48 PM
 #4

It does not make guesses that could be wrong. There is a checksum to prevent that.

This is impossible in general as the checksum does not guarantee the invalidity of an address that differs by the smallest amount from a valid address.

For instance
https://blockexplorer.com/address/1ByteCoinAddressesMatch1kpCWNXmHKW
https://blockexplorer.com/address/1ByteCoinAddressesMatch1kpCxNXmHKW
are both valid addresses even though they differ by only one character.

Similar collisions can be found for omitting one character.

If a new address type is introduced, I suggest the adoption of a shorter error detecting code which provides some guarantees.

If the correction function only results in the replacement of an invalid character with the corresponding valid character then the problem is not relevant. However, if the address contains a lowercase "L" then there's some uncertainty whether it should be converted into "1" or "L" and potentially both might result in valid addresses. I suppose the validity of both interpretations could be checked but this would complicate matters and finding a full set of test cases for the code would not be trivial.

ByteCoin
Luke-Jr
Legendary
*
expert
Offline Offline

Activity: 2086



View Profile
October 05, 2011, 04:10:49 PM
 #5

If the correction function only results in the replacement of an invalid character with the corresponding valid character then the problem is not relevant.
This is correct.

ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
October 05, 2011, 04:26:25 PM
 #6

If the correction function only results in the replacement of an invalid character with the corresponding valid character then the problem is not relevant.
This is correct.

Ok.

When you see "l", how do you choose whether to change it to "L" or "1" and why?

ByteCoin
Luke-Jr
Legendary
*
expert
Offline Offline

Activity: 2086



View Profile
October 05, 2011, 04:28:10 PM
 #7

When you see "l", how do you choose whether to change it to "L" or "1" and why?
It always uses "1", because "l" looks like "1", not "L". I'm assuming the error is in reading it off some print.

When you see "O", how do you choose whether to change it to "0" or "o" and why?
"0" is not valid. Both "O" and "0" are interpreted as "o".

maaku
Legendary
*
expert
Offline Offline

Activity: 905


View Profile
October 05, 2011, 04:40:37 PM
 #8

I voted no but send people a warning. If you've ever used an iphone you'd understand how retarded autocorrect is.   Tongue
There's no reason to tell the user they're an idiot and can't read properly Wink

Thanks for the pull, Luke. That was on my list to fix as well.

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
ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
October 05, 2011, 04:41:35 PM
 #9

It always uses "1", because "l" looks like "1", not "L". I'm assuming the error is in reading it off some print.

This assumption is not safe. If a person is typing in a string they are reading from a piece of paper, when they read a "L" they have it in their heads as a letter "ell" and may type it as "l".


When you see "O", how do you choose whether to change it to "0" or "o" and why?
"0" is not valid. Both "O" and "0" are interpreted as "o".
"O" and "0" could be interepreted as the valid "Q" though....

ByteCoin
casascius
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1344


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


View Profile WWW
October 05, 2011, 04:45:37 PM
 #10

The Base58check coding scheme used in Bitcoin has enough redundancy (32 bits) that correcting simple typos is a viable option.  A "did you mean _____?" prompt with the differences highlighted/bold (similar to what Google does if it thinks there's a typo in your search) would be a good idea.  I can't think of any good reason why not to offer this.

Error correction would involve a simple brute force search that exhausted all possibilities within the space of likely simple typos, including (for example:) one letter changed, two adjacent letters transposed, capitalization reversed on 1 to n letters (n=3?), and insertions/deletions of one character.

An invalid character in "IlO0" could be simply substituted with the most similar looking character before proceeding with the remaining steps.  If a 0 was really a Q, the brute force search will catch it.

I would mainly suggest only offering this in the UI.  The RPC interface should never auto-correct, at most it should offer a correction suggestion in its failure message.

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.
maaku
Legendary
*
expert
Offline Offline

Activity: 905


View Profile
October 05, 2011, 04:50:09 PM
 #11

This assumption is not safe. If a person is typing in a string they are reading from a piece of paper, when they read a "L" they have it in their heads as a letter "ell" and may type it as "l".
Which is why most base-58 codes use only 'L'. Satoshi, for whatever reason, decided to roll his own. Regardless, case *matters* for bitcoin addresses, so it is highly unlikely that someone would type 'l' for 'L', but type everything else correctly...

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 05, 2011, 05:08:12 PM
 #12


I am guessing that you virtually engineered these addresses to be this close to one another with a brute-force search, and that you can't spend the bitcents sent to either of them.

With 32 bits of error correction, one in 4.2 billion errors is going to slip through the cracks.  Of course, if you make a program that is willing to try 4.2 billion (or more) times to find one, it's going to be able to find one.  In a practical sense, real typos that result in a valid address are going to be extremely rare, but a "did you mean" box would give the user control over that risk.

If an error correction scheme were adopted similar to the one I suggested, the odds of getting a wrong address go up considerably, mainly because the error correction algorithm will be searching a few tens of thousands of possible keys to find the right one.  But even then, 1-in-1000 odds are acceptable when the program is explicitly asking you to double-check its suggested correction.

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.
theymos
Administrator
Legendary
*
expert
Offline Offline

Activity: 2492


View Profile
October 05, 2011, 06:33:11 PM
 #13

Bitcoin shouldn't accept them automatically because people will then use the alternative characters in vanity addresses, and old clients (including many sites that verify addresses without using Bitcoin) won't be able to accept these "new" addresses.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
Luke-Jr
Legendary
*
expert
Offline Offline

Activity: 2086



View Profile
October 05, 2011, 06:40:13 PM
 #14

Bitcoin shouldn't accept them automatically because people will then use the alternative characters in vanity addresses, and old clients (including many sites that verify addresses without using Bitcoin) won't be able to accept these "new" addresses.
Well, that's the point of the final poll option-- that in a few years, these could be adopted as valid.

Pages: [1]
  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!