Topic: Pieter and Greg, Bech32, please (Read 1057 times)

Sorry, I missed this question at the time but thought it was sad to have not followed up on it. -- For posterity:

Yes, however we didn't have to jointly make all the decisions at once.

We searched all the possible BCH codes of the relevant size for the ones which the most character errors (5), among those we selected the ones with the lowest false acceptance rate for just beyond 5 errors, then searched the remaining ties (codes that were equally good for character errors) to find the one that was the best at bit errors (which could guarantee detecting up to 6 arbitrarily placed bit errors).

While these searches were ongoing, we used the NIST data make a machine search check all 58905 possible selections of 4 excluded characters out of 36 which had the least internal character confusion, assuming that the input was all uppercase or lower case.  It made a decision that I wouldn't have guessed by hand-- e.g. excluding both 1 and i but actually looking at the result confirmed it was a good choice.  B can be confused a lot of ways: B looks like 8 and 3, b looks like p or lo, etc.  Other guesswork versions looked a lot worse when compared objectively.  I don't doubt you could make a somewhat different decision with a different metric or using better input data... but you could also do a lot worse, as I found just from informally picking the chacters to exclude after looking at the NIST data.

[There was an earlier version of the search before we implemented all the NIST data that wanted to exclude 'B', 'L', 'O', 'Q', which I found pretty amusing, but was ultimately relieved that we wouldn't have to convince anyone that we hadn't intentionally targeted the name of a former developers ICO mill company ...]

For most applications the HRP should be fixed by context (e.g. you don't have a reason intentionally input an arbitrary altcoin address into your bitcoin wallet), which means that any charset error (like entering 1s) can be immediately highlighted in the UI with zero false positives (I am highly dubious about auto-fixing anything since a detectable error may signify carelessness which could result in other non-detectable errors).

Finally we non-exhaustively searched the space of 32! permutations to find a permutation that mapped the remaining most likely character confusions to single bit errors.  E.g.  q and g are in the charset and differ by only a single bit.  likewise c/e, r/t, e/6, 7/l, q/p, S/5, n/m, n/h (the obviousness of these examples depends on your font...), and many other confusable pairs. This mapping means that likely errors for users get mapped to fewer bit errors and since the error detecting code was chosen to have improved detection for single bit errors this means improved detection for errors users are likely to make.   This is an optimization with only a small effect, but it is one with fairly low marginal cost since virtually any encode/decode implementation would already use a table due to the missing characters-- just as existing base58 (and base64) (de)coders do. Given that a table is being used, the choice of the order is essentially arbitrary so we were free to choose it to optimize the performance of the error detecting code. I doubt an implementation that includes signing (taking tens of kb of code) would care much about saving a few bytes bytes by using a slow branchy alternative rather than just a simple table in read only memory.

The code searches and permutation searches were computationally expensive but we didn't have to do the product of their efforts, only the sum because they could be searched independently and combined (and the charset search wasn't terribly expensive).  Pieter has code for all these searches in his ezbase32 repository...

I wish to reply further (also to cellard’s last post above); for now, simply to address one issue:


They did.  Did you read what gmaxwell said upthread?  Red highlights are here added.



IIUC, the “CPU decades” must have crunched alphabets with the NIST visual similarity data referenced in BIP 173 and the error-correcting code to find the alphabet which, per available data, would have the lowest statistical likelihood of undetected or unrecoverable bit errors.  (gmaxwell, am I correct in this inference?)  Those data were originally gathered from humans; and the resulting address format was tested with humans.

It is a rule in UI/UX design that you never ask people what they subjectively prefer, because they don’t actually know what works better for them.  Instead, you test performance.  How long does an average user take to transcribe an address in a particular format?  How many errors are made on average?  These are objective measures.  According to the foregoing, all discussed upthread, this was done with Bech32.

---

P.S., try playing around with Bech32.  It’s really an awesome format for pseudorandom bitstrings.  I’m currently trying to apply it elsewhere, too.

Seeing this thread impels me to two comments.

Kudos to you for your early and continuing visions of crypto.

Regarding address formats. I'm seeing a lot of engineering-level discussion but better would be to simply toss samples at test groups and have them type them in, gather comments and so forth. Or just leave things along. But hey, whatever. The market will decide, sooner or later.

True. I forgot that random letters have a magnetic quality that pulls the two halves of the letter b (but not d) apart, making it confusing like this. And the research probably shows that 1 and l don’t have this problern, loecause they are all one piece. Good call

It could.


Except that (especially when crowded by a number of random characters on each side) "b" can look a LOT like "lo".  Even more so with certain typeface selections.

I might take a little liberty here, after running across this:

(from https://blockstream.com/team/greg-maxwell )

I am going to submit that the idea to start introducing Bitcoin addresses that contain both the number 1 and lowercase l together, the majority of the time (71% by my calculation), is broken from a UX perspective.  It is as fashionable as tomato soup on a dress shirt.  At the risk of sounding redundant, this is a regression from Satoshi that will be observable to the majority of users who ever make use of a bitcoin address.

If I ever propose any sort of amendment to BIP 173, it will be to formally suggest the usage of the letter "b" in place of "l", either before this spec gets serious traction for Bitcoin.  I would further specify that if not implemented in Bitcoin, it remains a proposed recommendation for alt coin implementers to enjoy a free gimme gift to help differentiate their coin as a superior UX experience that will be salient to even the most casual users.

Presumably, B could be said to look like an 8, and that's the only reason I can imagine that "b" is on the list of exclusions.  But since the spec strongly encourages the usage of lowercase except where technical constraints dictate otherwise, it would seem like allowing "b" is a far better choice for a spec that clearly spells out visual dissimilarity as a valued attribute in the chosen character selection.

What does it take for me to formally propose fixing this and put my OCD-like energy to work improving this here?

Im not sure what I like more. The strings separated by 4 characters remind me of the usual bank account and credit card numbers which usually are separated in chunks of 4 by the GUI even if you paste the entire number without any gaps which is what I think is your idea. So this could help most people to make it more readable and spot any mistakes faster.

But for some reason I think I can discern shapes easier in the 6 char chunks where the address is divided in less chunks which for some reason I think my brain takes less effort due less chunks.. anyway, I guess this could be be switchable in options, to make it customizable to everyone's appeal.

Well, I suppose that different people will have differing comfort levels on that point; and it also sounds as if you have more practical experience with such than I do.  I know it drives me crazy, as well as effectually doubling the spoken length of the alphabetic parts.

Thanks again for the feedback.

ive used the military alphabet for years in poor voice quality communications. it works well. but its not hard to say "caps alfa, niner, lower bravo caps charlie" for mixed case either.

Thanks for the feedback.  I agree; that’s easiest for me, too.

Now, how would you find that to read aloud to someone else using a radio alphabet?  Whether an official standard radio alphabet, or your own ad hoc choices of words to unambigously represent letters.  Please try it, by yourself or with a friend.  Also imagine what it would be like to read or hear this in word-letters over the phone, perhaps over a bad mobile or VoIP connection with some dropouts.

I’ve tried doing this aloud, though only to myself thus far.  The ease of reading these out without case distinction is why I nickname these “Bravo Charlie Addresses”, an idea I had earlier in this thread; we now intersect with a topic about which I’ve been preparing to otherwise post.


That won’t work so well with the old-style addresses.

this one (4 character chunks) seems easiest.

Here is a good GUI idea, which I’ve had before for displaying hashes:  Subtly break the long pseudorandom-looking string into chunks using something between a hair-space (U+200A) and a punctuation space (U+2008).  The space should not be too large—just enough for subtle visual breakup of the string.  In my experience, the chunks should each be about four characters.  The particulars really depend on the display font, and also the alphabet of the “pseudorandom” string.

Of course, copy/paste of the string must not be affected.  The extra space is display formatting only, not the actual addition of characters to the string.

In the forum font, with very little typographic control of what I can post, how does this look to you?  (Warning:  I added actual Unicode U+2009 THIN SPACE; do not copypaste the display text, though the link URI is unaffected.)


Rebroken into evenly divisible, larger chunks:


With this address length, that can be done two different ways.  N.b. all Bitcoin address lengths can vary.


Which of those do you find easiest on the eyes?  I myself deem the four-character chunks to be visually optimal.  That also seems a de facto standard in printing account numbers, tracking numbers, and the like.

I used to have a set of LaTeX macros to do this for high-quality typesetting and deadtree printing of hashes; thus I can attest, it much enhances readability.  I think I may also have worked out a way to do it in HTML/CSS without any adding spaces on copypaste.

Additional implementation note:  Wallet GUIs should filter out any Unicode space-class characters from a pasted string, in case other software did this wrongly—or in case somebody added spacing characters by hand, as here.

Implementers, please do this!  I mean generally, not only for Bech32.

i am the same, its easier to read the address with mixed case as i find its easier to visually break it into "chunks" of 3-5 characters i can check. these chunks can be anywhere in the address, as its pretty much wherever patterns catch my eye. i check several of these "chunks" before sending.

all uppercase just looks like one big.. well, something. but its actually harder to read and check for me.

This is an interesting UX observation.  I would guess that it’s a not uncommon practice.

That may or may not be a reasonable heuristic for defending against malware generally seen in the wild; I wouldn’t know either way, since I prefer simply to not be infected by malware which could anyway open my wallet, steal all my funds, and then encrypt and ransom all my files.  But even under the best assumptions, it should not be considered a reliable technique.  For a targeted attack, if I don’t get my maths wrong, generating a “vanity address” which matches the first and last four characters of a specific address should require about 58^7 ≈ 2^41 work.  (The 7 is because the initial character is fixed.  Actually, I think I see a stupid bug in what I just said; but it’s unimportant to fix.  You get the point.)


I’m glad to hear it!  Bravo Charlie addresses are the future.  As for the address with “3”, well—that’s nothing new; it’s simply an old-style address with a version byte of 0x05, indicating a P2SH address which in this case happens to have the script hash for a Segwit P2WPKH script (0x0014).  The 0x05 makes the address consistently start with a “3” due to the vagaries of Bitcoin’s base58 encoding.  Old-style addresses which start with a “1” have a version byte of 0x00, followed by the key hash.  Both old-style addresses then end with a 32-bit checksum of truncated double-SHA256, and then the whole thing is base58-encoded.

Quote from: cellard on December 24, 2017, 01:30:41 PM

I just hope trolls don't start a campaign to tell noobs how "bc1" is the new bcash format address or something (looks like bcash side enjoys making things confusing otherwise they would have choosen their own address format since day 1)

Well, sometimes, I “troll” back.  Behold my new Bech32 vanity tip address!

bc1qcash96s5jqppzsp8hy8swkggf7f6agex98an7h

I made that yesterday, in preparation for some Bech32 advocacy which I have not yet posted.  I enjoy the fact that you can only send real money to this, not those fake scamcoins which are making awful news lately.  You know.  The forked-up b-trash which sadistically inflicts on users a circumstance which will foreseeably cause loss of funds, per all the threads on this forum crying, “Help!  I sent BTC to a BCH address!” or vice versa.  My Bech32 “cash” address will create no problems here.  It is only for genuine Bitcoin cash.

Personally, and I may be weird, but I find easier to discern shapes if there is variety of caps on and off, a string of all caps off seems to same-ish to me.

As far as actually trying to memorize things... who does that? I just look at the first 3 or 4 characters of the address, and look at the last 3 or 4  characters of the address, when I paste the address in the "send" section of a wallet, when im about to send, mostly to confirm that im not infected with these type of malware that pastes an attacker's address instead of yours. So looking at the first and last couple of characters gets the job done for me at least (which is why I think caps on and off make it easier to stop any differences). I don't think a sophisticated way to only change characters in the middle of the address where most people don't look at is possible, or is it? because that would be a hell of a malware.

Anyway, im ok with both formats. The one that starts with 3 sucks, bech32 is better and the bc1 distinction is easy to spot and easy to discern from legacy addresses. BTCxx ... not sure about that one, the 1 is a good looking separator to me, if there is no 1, something seems missing.

btc1 would be cool too, but that's 4 characters...

Overall im not sure. I think bc1 should do the job just fine. I just hope trolls don't start a campaign to tell noobs how "bc1" is the new bcash format address or something (looks like bcash side enjoys making things confusing otherwise they would have choosen their own address format since day 1)

casascius, I wrote my below conclusion before I stepped away for awhile (and gmaxwell showed up).  I didn’t post it, because I wanted to first cook up a vanity address to add some “wow”; unfortunately that’s not done, per below.  But I’m glad to see that things seem to be coming together here.

gmaxwell, sorry, I should have made clear that I’ve read BIP 173 and assumed familiarity therewith.  Otherwise, I would have mentioned the NIST data, instead of obliquely referring to “the research it cites”.  I do appreciate your explanations of the Bech32 rationales, with tantalizing hints of what went on behind the scenes of that production.  Also I hope you caught my sarcasm, which can oft be dry as liquid helium; of course I’m not seriously complaining about the look-up table!

I suggest that perhaps, you should perhaps list to your rationales that Bech32 addresses can be read off efficiently and unambiguously with with standard radio alphabets.  In similar circumstances, I find this can be indispensable for communicating over the phone.  The version zero witness for my money is Bravo Charlie One Quebec...  It may also be wise to rebrand them with a nickname as Bravo Charlie One Addresses (or simply “Bravo Charlie Addresses”, to avoid confusion with version zero so-called “1-addresses”; the word triplet also sounds snappier).

---

Unfortunately, I stepped out of the discussion just when it picked up.  Real life seized me away, after my attempt to find something suitably impressive for casascius hit an unfortunate snag of GNU Autohell; but I now have an airgapped CPU grinding away.  The following are just some quick tests.  Nested P2WPKH-in-P2SH and Bech32, a direct comparison:  Ain’t Bech32 pretty?


N.b. that I am in general leery of vanity addresses.  They do restrict the keyspace, at least theoretically; and by grabbing human focus with a false impression of readability, they’re tantamount to an invitation to spoofing.  But being flesh and blood, I also understand the attraction (and the marketing angle).  I also realize that due to the error correction, Bech32 strings don’t have the same uniform distribution properties as the old addresses (gmaxwell, please correct me if I’m wrong there!); from this perspective, I think that’s actually a benefit.

Also, ever since this discussion started, the idea of writing Bech32 in uppercase has been growing on me.  Directly compared, which looks better to you, casascius?  For that matter, which would be more pleasing when engraved in shiny metal?

---

Actually, I didn’t know what you meant beyond your words; and I’ve spent so much time lately shooting down the “still stuck with 1MB blocks” myth on this forum that I keep that code snippet (plus a formatted piece of BIP 141) ready for copypaste.

I think the biggest help for users right now is to get them using Segwit addresses.  I’ve been trying.  I’ve been handing out explanations of how to generate backward-compatible P2SH-nested addresses on the m/49'/0'/0' derivation path with Electrum 3 (so as to actually receive money while people slowly upgrade), launching my flamethrower at anti-Segwit agitprop and FUD which is so stupid that it would be comical if it weren’t so disgusting, and above all:  Shouting at the top of my lungs about how people can discount their own fees right now by using Segwit addresses.

All those people crying to you about fees—do their addresses start with a “1”?

You’re passionate about Bitcoin, casascius, and you’re passionate about users.  For the individual, so much of the current fee pain can be assuaged immediately by simply moving away from “1-addresses”—and when everybody gets onboard, the whole network will benefit as the effectual block capacity grows to Segwit’s potential.  Bitcoin is always that way:  Aligning the common good with the selfish interest of each individual, so that the latter pushes the former.  People still using 1-addresses are hurting the network; and in paying higher fees, they are suffering the natural consequences of their disproportionate capacity impact on the community.  If your transactions weigh more, byte for byte, then you pay for it!  I suggest that pushing Segwit adoption would be a good means to act on your desire to engage and help people who are struggling with fees, and also to do good for the health of the network.

---

Damn straight.  (Your sig, too.)

Satoshi’s Bitcoin was real run-and-gun cypherpunk code.  AFAIK, the initial versions were not even portable between platforms.  “Cypherpunks write code”; and the important part is that he encapsulated his brilliant idea in a functioning public alpha about two months after announcing his paper.  Talk is cheap; action can change the world.

Of course that was not the end, but only the beginning.  Satoshi jump-started the movement of cryptography-based digital currency after the very idea had been then moribund for a decade—conference talks and idle dreams notwithstanding.  And he did more:  Whether or not foresaw his own results, he created ex nihilo a social organism of a kind which has never before existed.

One of my own secret dreams is to hack up some code implementing a brilliant idea no one else had, then let people such as gmaxwell and sipa pour “a lot of testing with both people and machines, several CPU decades” into some small area where I personally happen to lack perfectly omniscient expertise.  For now, I can keep dreaming.

---

Well, enjoy your Bitcoin Porsche and a small slice of cake.  We’re in for a wild ride—but when has it not been?  Someday, a few old men will look back on the Coin Wars back around ’15–18.  I’m not overconfident of what they’ll remember; but I am confident, nevertheless.

I happen to like Core, but they are not Bitcoin.  They provide only the necessary prerequisite:  Reliable software which can keep safe the exchange value equivalent of hundreds of billions of dollars in value throughout the Bitcoin ecosystem.  Beyond that, you ought know as well as anybody that code alone can’t solve people problems.

Bitcoin is a sociological phenomenon.  Now we see the latest battle in an ongoing political war.  What fights for Bitcoin is—Bitcoin.  The thing is running headless, just as it’s supposed to do.  Bitcoinum nullius est.  It’s a decentralized social organism which belongs to nobody, with nobody in control.  It derives its value from its nature as such.  It fends off enemies by the power of multitudes who believe in it—and the many who have much to lose—many of whom are otherwise enemies with each other; all of whom agree on only one thing, Bitcoin.  Core (as L. cor) could stop the heart of Bitcoin by caving in, or ceasing technological improvements.  But this is beyond Core, you, me, or anybody else involved.

For Bitcoin owns; it is not owned.  I don’t mean the monetary component, in the sense of people who are owned by their wealth.  I refer to the sociological phenomenon.  Bitcoin owns.  You know what I mean.  Each and all of you know exactly what I mean.

Yeah. It feels to me like that’s what I did and that’s not what I wanted.  I am sorry for that.

If you can change l to a b, and let the prefix part be valid when capitalized while the data part is lowercase, and maybe put the T in the BC prefix (so as to not encourage 2-letter currency codes), you will have my enthusiasm even if the 1 remains a separator.

Bitmain didn't come up with Bitcoin cash until months after this specification was done, and didn't make the name public until even later... if there was any intention of confusion there it could only have been on the part of bitmain and their contractors.  Similarly, B2X named themselves BTC1 long after.  Unfortunately we cant do anything about altcoins using intentionally confusing names and labels.

Last character of the HRP has to be completely out of the data charset. making it all case sensitive would reintroduce the mixed case errors (though not as bad if it was only the first chars, but just as you complained: special rules don't help the users if they don't know them)... and then you can't do things like have it optionally in all caps which is nice in some contexts, and can be pretty visually attractive too.

Yes, there certainly was that effect, I was really kind of gut punched by your post and was sort of thinking you'd turned into a bcash shill -- acknowledging it absolves it.  I'm sorry for being a bit quick to judge there. Don't be a stranger.

What???  Let's not continue discussing it then.  I don't own any alt coins other than ones I acquired incidentally, like physical litecoins and some XRP from a giveaway and whatever has been bestowed upon me from forks.  I refused all efforts to persuade me to make physical altcoins of any kind.  Let's assume my loyalty is to Bitcoin Core and I'm interested in its success.  My effort in asking for your attention might make more sense.

If you feel you have earned the privilege of shortening the letter T out of BTC to keep it from being worse, then I'm just going to agree with you, because I've done nothing to earn the privilege to be the one who decides which is better or whether to take it out.


assuming, of course, that I'm an altcoin pusher.  If I felt that "BC" was political and I was wrong, then I made a guess and I was wrong.  Bitcoin Cash having the same initials is an unfortunate coincidence that might make such a wrong guess seem reasonable.  I would have wanted to see BTCxxxx instead of bc1xxxx but it's your proposal and not mine.  I am indeed a bit blind, that's why 1 and L's are so problematic for people like me sometimes.


no, I saw it.  He already knows I probably mean with witness data excluded and the difference isn't going to round the current fee back to any level that makes it reasonable to give someone some bitcoin rather than an altcoin to play with or test cryptocurrency for the first time.

I am sorry that popping up with "constructive criticism" out of the blue without much in the way of reintroduction or community engagement probably seems more confrontational in the absence of regular positive contributions to the project's development.  I'm actually sad because I'm embarrassed to be explaining $30 transaction fees to people and no way to avoid them other than switching to altcoins or trusting in scalability solutions still not ready for prime time, so I'm motivated to show up and whine a little about the factor common to both issues: the plausible appearance of neglect to basic user experience.  I accept that the risk with my approach is that my input will likely be completely disregarded, and I appreciate that you've paid what seems like quality attention to what I felt was worth saying.