idnits 2.17.1 draft-msporny-base58-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (November 27, 2019) is 1612 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 1 error (**), 0 flaws (~~), 1 warning (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force S. Nakamoto 3 Internet-Draft Bitcoin 4 Intended status: Informational M. Sporny 5 Expires: May 30, 2020 Digital Bazaar 6 November 27, 2019 8 The Base58 Encoding Scheme 9 draft-msporny-base58-01 11 Abstract 13 This document specifies the base 58 encoding scheme, including an 14 introduction to the benefits of the approach, the encoding and 15 decoding algorithm, alternative alphabets, and security 16 considerations. 18 Status of This Memo 20 This Internet-Draft is submitted in full conformance with the 21 provisions of BCP 78 and BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF). Note that other groups may also distribute 25 working documents as Internet-Drafts. The list of current Internet- 26 Drafts is at https://datatracker.ietf.org/drafts/current/. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on May 30, 2020. 35 Copyright Notice 37 Copyright (c) 2019 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (https://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. 47 Table of Contents 49 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 50 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3 51 2. The Base58 Alphabet . . . . . . . . . . . . . . . . . . . . . 3 52 3. The Base58 Encoding Algorithm . . . . . . . . . . . . . . . . 4 53 4. The Base58 Decoding Algorithm . . . . . . . . . . . . . . . . 4 54 5. Test Vectors . . . . . . . . . . . . . . . . . . . . . . . . 5 55 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 5 56 7. Security Considerations . . . . . . . . . . . . . . . . . . . 5 57 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 5 59 1. Introduction 61 When trasmitting data, it can be useful to encode the data in a way 62 that survives lower fidelity transmission mechanisms. For example, 63 encoding data using a human alphabet in a way that a person can 64 visually confirm the encoded data can be more beneficial than 65 encoding it in binary form. The Base58 encoding scheme is similar to 66 the Base64 encoding scheme in that it can translate any binary data 67 to a text string. It is different from Base64 in that the conversion 68 alphabet has been carefully picked to work well in environments where 69 a person, such as a developer or support technician, might need to 70 visually confirm the information with low error rates. 72 Base58 is designed with a number of usability characteristics in mind 73 that Base64 does not consider. First, similar looking letters are 74 omitted such as 0 (zero), O (capital o), I (capital i) and l (lower 75 case L). Doing so eliminates the possibility of a human being 76 mistaking similar characters for the wrong character. Second, the 77 non-alphanumeric characters + (plus), = (equals), and / (slash) are 78 omitted to make it possible to use Base58 values in all modern file 79 systems and URL schemes without the need for further system-specific 80 encoding schemes. Third, by using only alphanumeric characters, easy 81 double-click or double tap selection is possible in modern computer 82 interfaces. Fourth, social messaging systems do not line break on 83 alphanumeric strings making it easier to e-mail or message Base58 84 values when debugging systems. Fifth, unlike Base64, there is no 85 byte padding making many Base58 values smaller (on average) or the 86 same size as Base64 values for values up to 64 bytes, and less than 87 2% larger for larger values. Finally, Base64 has eleven encoding 88 variations that lead to confusion among developers on which variety 89 of Base64 to use. This specification asserts that there is just one 90 simple encoding mechanism for Base58, making implementations and 91 developer interactions simpler. 93 While Base58 does have a number of beneficial usability features, it 94 is not always a good choice for an encoding format. For example, 95 when encoding large amounts of data, it is 2% less efficient than 96 base64. Developers might avoid Base58 if a 2% increase in efficiency 97 over large data sets is desired. 99 This document specifies the base 58 encoding scheme, including an 100 introduction to the benefits of the approach, the encoding and 101 decoding algorithm, alternative alphabets, and security 102 considerations. 104 1.1. Requirements Language 106 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 107 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 108 document are to be interpreted as described in RFC 2119. 110 2. The Base58 Alphabet 112 The Base58 alphabet consists of the following characters: 114 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz 116 Each byte value from 0 to 57 maps to the alphabet above in the 117 following way: 119 +-----+---------+-----+---------+------+----------+------+----------+ 120 | Byt | Charact | Byt | Charact | Byte | Characte | Byte | Characte | 121 | e | er | e | er | | r | | r | 122 +-----+---------+-----+---------+------+----------+------+----------+ 123 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 124 | 4 | 5 | 5 | 6 | 6 | 7 | 7 | 8 | 125 | 8 | 9 | 9 | A | 10 | B | 11 | C | 126 | 12 | D | 13 | E | 14 | F | 15 | G | 127 | 16 | H | 17 | J | 18 | K | 19 | L | 128 | 20 | M | 21 | N | 22 | P | 23 | Q | 129 | 24 | R | 25 | S | 26 | T | 27 | U | 130 | 28 | V | 29 | W | 30 | X | 31 | Y | 131 | 32 | Z | 33 | a | 34 | b | 35 | c | 132 | 36 | d | 37 | e | 38 | f | 39 | g | 133 | 40 | h | 41 | i | 42 | j | 43 | k | 134 | 44 | m | 45 | n | 46 | o | 47 | p | 135 | 48 | q | 49 | r | 50 | s | 51 | t | 136 | 52 | u | 53 | v | 54 | w | 55 | x | 137 | 56 | y | 57 | z | | | | | 138 +-----+---------+-----+---------+------+----------+------+----------+ 140 Table 1: Base58 Mapping Table 142 Other application-specific alphabets for Base58, such as the Ripple 143 alphabet and the Flickr alphabet exist. Those alphabets, while valid 144 in their own application spaces, are not valid encoding formats for 145 this specification and MUST NOT be used. Supporting more than one 146 Base58 encoding alphabet would harm interoperability. 148 3. The Base58 Encoding Algorithm 150 To encode an array of bytes to a Base58 encoded value, run the 151 following algorithm. All mathematical operations MUST be performed 152 using integer arithmetic. Start by initializing a 'zero_counter' to 153 zero (0x0), an 'encoding_flag' to zero (0x0), a 'b58_bytes' array, a 154 'b58_encoding' array, and a 'carry' value to zero (0x0). For each 155 byte in the array of bytes and while 'carry' does not equal zero 156 (0x0) after the first iteration: 158 1. If 'encoding_flag' is not set, and if the byte is a zero (0x0), 159 increment the value of 'zero_counter'. If the value is not zero 160 (0x0), set 'encoding_flag' to true (0x1). 162 2. If 'encoding_flag' is set, multiply the current byte value by 256 163 and add it to 'carry'. 165 3. Set the corresponding byte value in 'b58_bytes' to the value of 166 'carry' modulus 58. 168 4. Set 'carry' to the value of 'carry' divided by 58. 170 Once the 'b58_bytes' array has been constructed, generate the final 171 'b58_encoding' using the following algorithm. Set the first 172 'zero_counter' bytes in 'b58_encoding' to '1'. Then, for every byte 173 in 'b58_array', map the byte value using the Base58 alphabet in the 174 previous section to its corresponding character in 'b58_encoding'. 175 Return 'b58_encoding' as the Base58 representation of the input array 176 of bytes. 178 4. The Base58 Decoding Algorithm 180 To decode a Base58 encoded array of bytes to a decoded array of 181 bytes, run the following algorithm. All mathematical operations MUST 182 be performed using integer arithmetic. Start by initializing a 183 'raw_bytes' array, and a 'carry' value to zero (0x0). For each input 184 byte in the array of input bytes: 186 1. Set 'carry' to the byte value associated with the input byte 187 character. If a mapping does not exist, return an error code. 189 2. While 'carry' does not equal zero and there are input bytes 190 remaining: 192 1. Multiply the input byte value by 58 and add it to 'carry'. 194 2. Set the output byte value to 'carry' modulus 256. 196 3. Set 'carry' to the value of 'carry' divided by 256. 198 3. Set the corresponding byte value in 'raw_bytes' to the value of 199 'carry' modulus 58. 201 4. Set 'carry' to the value of 'carry' divided by 58. 203 5. Test Vectors 205 The following examples can be used as test vectors for the algorithms 206 in this specification: 208 The Base58 encoded value for "Hello World!" is: 210 2NEpo7TZRRrLZSi2U 212 The Base58 encoded value for "The quick brown fox jumps over the lazy 213 dog." is: 215 USm3fpXnKG5EUBx2ndxBDMPVciP5hGey2Jh4NDv6gmeo1LkMeiKrLJUUBk6Z 217 The Base58 encoded value for 0x0000287fb4cd is: 219 111233QC4 221 6. Acknowledgements 223 Thanks to Satoshi Nakamoto for inventing the Base58 encoding format 224 and the Bitcoin community for popularizing its usage. 226 7. Security Considerations 228 Authors' Addresses 230 Satoshi Nakamoto 231 Bitcoin 233 Email: satoshin@gmx.com 234 Manu Sporny 235 Digital Bazaar 237 Email: msporny@digitalbazaar.com