]>
The Base58 Encoding SchemeBitcoinsatoshin@gmx.comDigital Bazaarmsporny@digitalbazaar.com
General
Internet Engineering Task Forcebaseencodingbase58bitcoin
This document specifies the base 58 encoding scheme, including an introduction
to the benefits of the approach, the encoding and decoding algorithm,
alternative alphabets, and security considerations.
When trasmitting data, it can be useful to encode the data in a way that
survives lower fidelity transmission mechanisms. For example, encoding data
using a human alphabet in a way that a person can visually confirm the
encoded data can be more beneficial than encoding it in binary form.
The Base58 encoding scheme is similar to the Base64 encoding scheme in
that it can translate any binary data to a text string. It is different from
Base64 in that the conversion alphabet has been carefully picked to work well
in environments where a person, such as a developer or support technician,
might need to visually confirm the information with low error rates.
Base58 is designed with a number of usability characteristics in mind that
Base64 does not consider. First, similar looking letters are omitted such as 0
(zero), O (capital o), I (capital i) and l (lower case L). Doing so eliminates
the possibility of a human being mistaking similar characters for the wrong
character. Second, the non-alphanumeric characters + (plus), = (equals), and /
(slash) are omitted to make it possible to use Base58 values in all modern file
systems and URL schemes without the need for further system-specific encoding
schemes. Third, by using only alphanumeric characters, easy double-click or
double tap selection is possible in modern computer interfaces. Fourth, social
messaging systems do not line break on alphanumeric strings making it easier to
e-mail or message Base58 values when debugging systems. Fifth, unlike Base64,
there is no byte padding making many Base58 values smaller (on average) or the
same size as Base64 values for values up to 64 bytes, and less than 2% larger
for larger values. Finally, Base64 has eleven encoding variations that lead to
confusion among developers on which variety of Base64 to use. This specification
asserts that there is just one simple encoding mechanism for Base58, making
implementations and developer interactions simpler.
While Base58 does have a number of beneficial usability features, it is not
always a good choice for an encoding format. For example, when encoding large
amounts of data, it is 2% less efficient than base64. Base58 encoding also has
an average worst-case algorithm complexity that is O(n^2). For these reasons,
developers might want to avoid using Base58 for encoding byte strings that
are greater than 256 bytes in length.
This document specifies the base 58 encoding scheme, including an introduction
to the benefits of the approach, the encoding and decoding algorithm,
alternative alphabets, and security considerations.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119.
The Base58 alphabet consists of the following characters:
Each byte, interpreted as a decimal value, from 0 to 57 maps to the alphabet
above in the following way:
DecimalCharacterDecimalCharacter0129W1230X2331Y3432Z4533a5634b6735c7836d8937e9A38f10B39g11C40h12D41i13E42j14F43k15G44m16H45n17J46o18K47p19L48q20M49r21N50s22P51t23Q52u24R53v25S54w26T55x27U56y28V57z
Other application-specific alphabets for Base58, such as the Ripple alphabet
and the Flickr alphabet exist. Those alphabets, while valid in their own
application spaces, are not valid encoding formats for this specification and
MUST NOT be used. Supporting more than one Base58 encoding alphabet would
harm interoperability.
To encode an array of bytes to a Base58 encoded value, run the following
algorithm. All mathematical operations MUST be performed using integer
arithmetic. Start by initializing a 'zero_counter' to zero (0x0), an
'encoding_flag' to zero (0x0), a 'b58_bytes' array, a 'b58_encoding' array, and
a 'carry' value to zero (0x0). For each byte in the array of bytes and
while 'carry' does not equal zero (0x0) after the first iteration:
If 'encoding_flag' is not set, and if the byte is a zero (0x0), increment
the value of 'zero_counter'. If the value is not zero (0x0),
set 'encoding_flag' to true (0x1).
If 'encoding_flag' is set, multiply the current byte value by 256 and add it to
'carry'.
Set the corresponding byte value in 'b58_bytes' to the value of 'carry' modulus
58.
Set 'carry' to the value of 'carry' divided by 58.
Once the 'b58_bytes' array has been constructed, generate the final
'b58_encoding' using the following algorithm. Set the first 'zero_counter'
bytes in 'b58_encoding' to '1'. Then, for every byte in 'b58_array', map the
byte value using the Base58 alphabet in the previous section to its
corresponding character in 'b58_encoding'. Return 'b58_encoding' as the
Base58 representation of the input array of bytes.
To decode a Base58 encoded array of bytes to a decoded array of bytes, run
the following algorithm. All mathematical operations MUST be performed using
integer arithmetic. Start by initializing a 'raw_bytes' array, and a
'carry' value to zero (0x0). For each input byte in the array of input bytes:
Set 'carry' to the byte value associated with the input byte character. If
a mapping does not exist, return an error code.
While 'carry' does not equal zero and there are input bytes remaining:
Multiply the input byte value by 58 and add it to 'carry'.
Set the output byte value to 'carry' modulus 256.
Set 'carry' to the value of 'carry' divided by 256.
Set the corresponding byte value in 'raw_bytes' to the value of 'carry' modulus
58.
Set 'carry' to the value of 'carry' divided by 58.
The following examples can be used as test vectors for the algorithms in
this specification:
The Base58 encoded value for "Hello World!" is:
The Base58 encoded value for "The quick brown fox jumps over the lazy dog." is:
The Base58 encoded value for 0x0000287fb4cd is:
This section contains a variety of security considerations that implementers
using this specification are advised to consider before deploying this
technology in a production setting.
In general, when converting from a source base-encoding to a target
base-encoding, if the target encoding is not the a numerical power of the source
encoding, it is possible for the algorithm to degrade from linear algorithm
complexity into quadratic algorithm complexity. That is, converting from base-2
(binary) to base-32 or base-64 can be done with a worst-case algorithm
complexity of O(n) time, but converting from base-2 to base-58 has a worst-case
complexity of O(n^2). In short, base-58 does not work well for encoding large
byte values.
Implementers are urged to ensure that their production software imposes limits
on input size. Encoding values greater than 256 bytes in base58 is NOT
RECOMMENDED.
Thanks to Satoshi Nakamoto for inventing the Base58 encoding format and the
Bitcoin community for popularizing its usage.