[Search] [txt|xml|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00 01 02 03                                                   
Internet Engineering Task Force                                M. Sporny
Internet-Draft                                            Digital Bazaar
Intended status: Informational                         November 27, 2019
Expires: May 30, 2020


                       The Base58 Encoding Scheme
                        draft-msporny-base58-00

Abstract

   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.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on May 30, 2020.

Copyright Notice

   Copyright (c) 2019 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (https://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.







Sporny                    Expires May 30, 2020                  [Page 1]


Internet-Draft               Base58 Encoding               November 2019


Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
     1.1.  Requirements Language . . . . . . . . . . . . . . . . . .   3
   2.  The Base58 Alphabet . . . . . . . . . . . . . . . . . . . . .   3
   3.  The Base58 Encoding Algorithm . . . . . . . . . . . . . . . .   4
   4.  The Base58 Decoding Algorithm . . . . . . . . . . . . . . . .   4
   5.  Test Vectors  . . . . . . . . . . . . . . . . . . . . . . . .   5
   6.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .   5
   7.  Security Considerations . . . . . . . . . . . . . . . . . . .   5
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . .   5

1.  Introduction

   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, or encoding the data in a way
   that a human being can visually confirm the encoded data while
   reducing the opportunity to make a mistake.  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 human being, such as a developer or
   other human being, might need to work with the information.

   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 a different 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 translation.  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 for debugging or sharing
   purposes.  Fifth, unlike Base64, there is no 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 values larger
   than 256 bytes.  Finally, Base64 has eleven encoding variations that
   lead to miscommunication 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,



Sporny                    Expires May 30, 2020                  [Page 2]


Internet-Draft               Base58 Encoding               November 2019


   when encoding large amounts of data, it is 2% less efficient than
   base64.  Developers might avoid Base58 if a 2% increase in efficiency
   over large data sets is desired.

1.1.  Requirements Language

   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.

2.  The Base58 Alphabet

   The Base58 alphabet consists of the following characters:

   123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz

   Each byte value from 0 to 57 maps to the alphabet above in the
   following way:

   +-----+---------+-----+---------+------+----------+------+----------+
   | Byt | Charact | Byt | Charact | Byte | Characte | Byte | Characte |
   |  e  |    er   |  e  |    er   |      |    r     |      |    r     |
   +-----+---------+-----+---------+------+----------+------+----------+
   |  0  |    1    |  1  |    2    |  2   |    3     |  3   |    4     |
   |  4  |    5    |  5  |    6    |  6   |    7     |  7   |    8     |
   |  8  |    9    |  9  |    A    |  10  |    B     |  11  |    C     |
   |  12 |    D    |  13 |    E    |  14  |    F     |  15  |    G     |
   |  16 |    H    |  17 |    J    |  18  |    K     |  19  |    L     |
   |  20 |    M    |  21 |    N    |  22  |    P     |  23  |    Q     |
   |  24 |    R    |  25 |    S    |  26  |    T     |  27  |    U     |
   |  28 |    V    |  29 |    W    |  30  |    X     |  31  |    Y     |
   |  32 |    Z    |  33 |    a    |  34  |    b     |  35  |    c     |
   |  36 |    d    |  37 |    e    |  38  |    f     |  39  |    g     |
   |  40 |    h    |  41 |    i    |  42  |    j     |  43  |    k     |
   |  44 |    m    |  45 |    n    |  46  |    o     |  47  |    p     |
   |  48 |    q    |  49 |    r    |  50  |    s     |  51  |    t     |
   |  52 |    u    |  53 |    v    |  54  |    w     |  55  |    x     |
   |  56 |    y    |  57 |    z    |      |          |      |          |
   +-----+---------+-----+---------+------+----------+------+----------+

                       Table 1: Base58 Mapping Table

   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.




Sporny                    Expires May 30, 2020                  [Page 3]


Internet-Draft               Base58 Encoding               November 2019


3.  The Base58 Encoding Algorithm

   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:

   1.  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).

   2.  If 'encoding_flag' is set, multiply the current byte value by 256
       and add it to 'carry'.

   3.  Set the corresponding byte value in 'b58_bytes' to the value of
       'carry' modulus 58.

   4.  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.

4.  The Base58 Decoding Algorithm

   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:

   1.  Set 'carry' to the byte value associated with the input byte
       character.  If a mapping does not exist, return an error code.

   2.  While 'carry' does not equal zero and there are input bytes
       remaining:

       1.  Multiply the input byte value by 58 and add it to 'carry'.

       2.  Set the output byte value to 'carry' modulus 256.




Sporny                    Expires May 30, 2020                  [Page 4]


Internet-Draft               Base58 Encoding               November 2019


       3.  Set 'carry' to the value of 'carry' divided by 256.

   3.  Set the corresponding byte value in 'raw_bytes' to the value of
       'carry' modulus 58.

   4.  Set 'carry' to the value of 'carry' divided by 58.

5.  Test Vectors

   The following examples can be used as test vectors for the algorithms
   in this specification:

   The Base58 encoded value for "Hello World!" is:

   2NEpo7TZRRrLZSi2U

   The Base58 encoded value for "The quick brown fox jumps over the lazy
   dog." is:

   USm3fpXnKG5EUBx2ndxBDMPVciP5hGey2Jh4NDv6gmeo1LkMeiKrLJUUBk6Z

   The Base58 encoded value for 0x0000287fb4cd is:

   111233QC4

6.  Acknowledgements

   Thanks to Satoshi Nakamoto for inventing the Base58 encoding format
   and the Bitcoin community for popularizing its usage.

7.  Security Considerations

Author's Address

   Manu Sporny
   Digital Bazaar

   Email: msporny@digitalbazaar.com













Sporny                    Expires May 30, 2020                  [Page 5]