Wednesday, June 12, 2019

[qxwnszxh] Improving Bitcoin base 58

Bitcoin base 58 omits numeral zero and capital letter O because they look alike in some many fonts: 0O.  Similarly, it omits lowercase letter L and capital letter i: lI.  However, in many serif fonts the numeral 1 and lowercase letter L also look alike (1l), so numeral 1 ought to have been eliminated also, resulting in base 57.

However in base 58, with lowercase L not present, we know that anything that looks like a lowercase L must be numeral 1, because lowercase L is not possible.

However, similar logic could have kept exactly one of numeral zero and capital O, resulting in base 59.

With lowercase L eliminated, one can also keep capital i.  If it's a sans serif font and it looks like a lowercase L, then it's actually a capital i.  If it's a serif font and it looks like a lowercase L, then it's a numeral 1.  This gets us to base 60. Its smooth factorization might be useful somehow.

There are fonts in which the numeral 2 and capital letter Z look alike, 2Z, taking us back down to 59.

General problem: given sets indicating elements which look alike (sets may overlap), select at most one element (possibly zero) from each set to maximize the total number selected.  Many sets may contain just one element and not overlap with any other sets (these cases are easy).  For our example, selecting lowercase L would have led to a suboptimal total selection.

No comments :