Independent K. R. Davis Internet-Draft D. Brown Intended status: Standards Track Cisco Systems Expires: 12 October 2026 10 April 2026 A Sortable Base64 Alphabet draft-brown-davis-base64-sort-01 Abstract This document details a formal specification for a new Base64 alphabet which follows the US-ASCII ordering and sorts the same as binary. This serves as an alternative variant to Base64 and Base64url when lexicographically sortable outputs are required. The alphabet re-uses the Base64url special characters and is designed to be compatible with existing Base64 implementations, while providing a new option for applications that require sorted output. About This Document This note is to be removed before publishing as an RFC. The latest revision of this draft can be found at https://raw.githubusercontent.com/kyzer-davis/base64-sort-ietf- draft/refs/heads/main/draft-brown-davis-base64-sort.md. Status information for this document may be found at https://datatracker.ietf.org/doc/draft-brown-davis-base64-sort/. Discussion of this document takes place on the Revise Universally Unique Identifier Definitions (uuidrev) Working Group mailing list (mailto:uuidrev@ietf.org), which is archived at https://mailarchive.ietf.org/arch/browse/uuidrev/. Subscribe at https://www.ietf.org/mailman/listinfo/uuidrev/. Source for this draft and an issue tracker can be found at https://github.com/kyzer-davis/base64-sort-ietf-draft. 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/. Davis & Brown Expires 12 October 2026 [Page 1] Internet-Draft base64-sort April 2026 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 12 October 2026. Copyright Notice Copyright (c) 2026 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. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Conventions and Definitions . . . . . . . . . . . . . . . . . 3 3. The Alphabet . . . . . . . . . . . . . . . . . . . . . . . . 3 3.1. Padding . . . . . . . . . . . . . . . . . . . . . . . . . 5 4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5. Security Considerations . . . . . . . . . . . . . . . . . . . 5 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 5 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 5 7.1. Normative References . . . . . . . . . . . . . . . . . . 5 7.2. Informative References . . . . . . . . . . . . . . . . . 6 Appendix A. Changelog . . . . . . . . . . . . . . . . . . . . . 6 Appendix B. Test Vectors . . . . . . . . . . . . . . . . . . . . 7 B.1. Encoding . . . . . . . . . . . . . . . . . . . . . . . . 7 B.2. Decoding . . . . . . . . . . . . . . . . . . . . . . . . 8 Appendix C. Industry Tests . . . . . . . . . . . . . . . . . . . 8 C.1. Programming Language Results . . . . . . . . . . . . . . 9 C.2. Database Test Results . . . . . . . . . . . . . . . . . . 9 C.3. Conclusion . . . . . . . . . . . . . . . . . . . . . . . 10 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 Davis & Brown Expires 12 October 2026 [Page 2] Internet-Draft base64-sort April 2026 1. Introduction Base64 ([RFC4648], Section 4) and Base64url ([RFC4648], Section 5) have been widely implemented and tested across the industry; however, if one requires a lexicographically sortable output they will need to use either Base32hex, Base36, or [Base58]. There is no standardized sortable Base64 alphabet. Since the Base64 alphabets from RFC4648 see far more industry usage than the other previously mentioned alphabets there is a real need and requirement for a sortable Base64 Alphabet in the industry. See: [RFC4648_Usage_Report] for the breakdown of RFC citations for RFC4648 alphabets. This gap was made further apparent while examining Base64 usage with Universally Unique IDentifiers (UUIDs) defined in [RFC9562] to create [new-uuid-encoding-techniques-ietf-draft] which asserts that UUIDv6 and UUIDv7 benefit greatly from lexicographically sortable alphabets like Base64 Sortable. This document serves as a standards-track RFC to provide a new alphabet that follows the US-ASCII ([RFC20]) ordering, re-uses the Base64url special characters and sorts the same as binary. This document is created to serve as a reference for new libraries and for future RFCs to cite. 2. Conventions and Definitions The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here. 3. The Alphabet This Base64 Sortable alphabet, which can be referenced as "Base64sort" or sometimes "Base64lex", is a variant of the Base64url alphabet ([RFC4648], Section 5). While it utilizes the same set of 64 URL-safe characters as Base64url, its fundamental distinction lies in the assignment of values to these characters by aligning the character values with their US-ASCII ([RFC20]) ordering to ensure that the encoded output sorts lexicographically in the same order as the underlying binary data. Davis & Brown Expires 12 October 2026 [Page 3] Internet-Draft base64-sort April 2026 Specifically, the numeric characters (0-9) have been moved before the uppercase and lowercase characters while the special symbol characters, hyphen (-) and underscore (_), are placed at the beginning and middle of the alphabet as they appear in the US-ASCII character set. Table 1 details the alphabet characters along with their respective decoding and encoding values. +=====+========+=====+==========+=====+==========+=====+==========+ |Value|Encoding|Value| Encoding |Value| Encoding |Value| Encoding | +=====+========+=====+==========+=====+==========+=====+==========+ |0 |- |16 | F |32 | V |48 | k | +-----+--------+-----+----------+-----+----------+-----+----------+ |1 |0 |17 | G |33 | W |49 | l | +-----+--------+-----+----------+-----+----------+-----+----------+ |2 |1 |18 | H |34 | X |50 | m | +-----+--------+-----+----------+-----+----------+-----+----------+ |3 |2 |19 | I |35 | Y |51 | n | +-----+--------+-----+----------+-----+----------+-----+----------+ |4 |3 |20 | J |36 | Z |52 | o | +-----+--------+-----+----------+-----+----------+-----+----------+ |5 |4 |21 | K |37 | _ |53 | p | +-----+--------+-----+----------+-----+----------+-----+----------+ |6 |5 |22 | L |38 | a |54 | q | +-----+--------+-----+----------+-----+----------+-----+----------+ |7 |6 |23 | M |39 | b |55 | r | +-----+--------+-----+----------+-----+----------+-----+----------+ |8 |7 |24 | N |40 | c |56 | s | +-----+--------+-----+----------+-----+----------+-----+----------+ |9 |8 |25 | O |41 | d |57 | t | +-----+--------+-----+----------+-----+----------+-----+----------+ |10 |9 |26 | P |42 | e |58 | u | +-----+--------+-----+----------+-----+----------+-----+----------+ |11 |A |27 | Q |43 | f |59 | v | +-----+--------+-----+----------+-----+----------+-----+----------+ |12 |B |28 | R |44 | g |60 | w | +-----+--------+-----+----------+-----+----------+-----+----------+ |13 |C |29 | S |45 | h |61 | x | +-----+--------+-----+----------+-----+----------+-----+----------+ |14 |D |30 | T |46 | i |62 | y | +-----+--------+-----+----------+-----+----------+-----+----------+ |15 |E |31 | U |47 | j |63 | z | +-----+--------+-----+----------+-----+----------+-----+----------+ Table 1: The Base64sort Alphabet as table The Alphabet as a continuous text input can be found in Figure 1. Davis & Brown Expires 12 October 2026 [Page 4] Internet-Draft base64-sort April 2026 -0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz Figure 1: The Base64sort Alphabet as text 3.1. Padding Base64sort follows the same padding logic as Base64url ([RFC4648], Section 5). That is, padding MAY be used with Base64sort. Although the equal sign (=) padding character is positioned between the numeric characters and the uppercase letters in the US-ASCII character set; it does not cause any issues with sorting since the padding is always in the right-most, least significant position of the encoded string. Note that this assumes the sorted data is either entirely all padded or un-padded encodings. Mixing padded and un-padded encodings in the same sorted set may lead to unexpected results since the padding character would be treated as a significant character in the sort order. Implementations MAY utilize a padding character that is not part of the Base64sort alphabet and does not interfere with sorting, such as a tilde (~), to maintain the integrity of the sort order of mixed datasets while still indicating padding. 4. Decoding The decoding process for Base64sort follows the principles outlined in ([RFC4648], Section 5), for decoding Base64url. 5. Security Considerations This document has no security considerations. 6. IANA Considerations This document has no IANA actions. 7. References 7.1. Normative References [RFC20] Cerf, V., "ASCII format for network interchange", STD 80, RFC 20, DOI 10.17487/RFC0020, October 1969, . Davis & Brown Expires 12 October 2026 [Page 5] Internet-Draft base64-sort April 2026 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . 7.2. Informative References [Base58] Bitcoin, "Bitcoin Base58 Encoding", commit fae71d3, November 2008, . [new-uuid-encoding-techniques-ietf-draft] Davis, K., "Alternate UUID Encoding Methods", n.d., . [RFC4648_Usage_Report] "RFC4648 Alphabet Usage Report", commit de0a2760, November 2025, . [RFC9562] Davis, K., Peabody, B., and P. Leach, "Universally Unique IDentifiers (UUIDs)", RFC 9562, DOI 10.17487/RFC9562, May 2024, . Appendix A. Changelog draft-00: * Initial Release draft-01: * Update frontmatter venue and Alt encoding link Davis & Brown Expires 12 October 2026 [Page 6] Internet-Draft base64-sort April 2026 Appendix B. Test Vectors The following test vectors start with a base of those found in [RFC4648] and then include additional values for testing the new alphabet and its sorting properties. B.1. Encoding +=============+==================+==========================+ | Input | Encoded Data | Input Type | +=============+==================+==========================+ | f | OV | Text | +-------------+------------------+--------------------------+ | fo | Oaw | Text | +-------------+------------------+--------------------------+ | foo | Oaxj | Text | +-------------+------------------+--------------------------+ | foob | OaxjNV | Text | +-------------+------------------+--------------------------+ | fooba | OaxjNa3 | Text | +-------------+------------------+--------------------------+ | foobar | OaxjNa4m | Text | +-------------+------------------+--------------------------+ | test | S5KnS- | Text | +-------------+------------------+--------------------------+ | Hello World | H5KgQ5wVKqxmQ5F | Text | +-------------+------------------+--------------------------+ | - | AF | Hyphen | +-------------+------------------+--------------------------+ | 0 | B- | Digit | +-------------+------------------+--------------------------+ | _ | Mk | Underscore | +-------------+------------------+--------------------------+ | A | FF | Uppercase Letter | +-------------+------------------+--------------------------+ | a | NF | Lowercase Letter | +-------------+------------------+--------------------------+ | = | EF | Equal Sign | +-------------+------------------+--------------------------+ | ~ | UV | Tilde | +-------------+------------------+--------------------------+ | 0123456789 | B23mBnFpCYRsDF== | Input with Equal Padding | +-------------+------------------+--------------------------+ | 0123456789 | B23mBnFpCYRsDF~~ | Input with Tilde Padding | +-------------+------------------+--------------------------+ Table 2: Base64 Sortable Encode Table Davis & Brown Expires 12 October 2026 [Page 7] Internet-Draft base64-sort April 2026 B.2. Decoding +==================+==============+ | Input | Decoded Data | +==================+==============+ | OV | f | +------------------+--------------+ | Oaw | fo | +------------------+--------------+ | Oaxj | foo | +------------------+--------------+ | OaxjNV | foob | +------------------+--------------+ | OaxjNa3 | fooba | +------------------+--------------+ | OaxjNa4m | foobar | +------------------+--------------+ | S5KnS- | test | +------------------+--------------+ | H5KgQ5wVKqxmQ5F | Hello World | +------------------+--------------+ | AF | - | +------------------+--------------+ | B- | 0 | +------------------+--------------+ | Mk | _ | +------------------+--------------+ | FF | A | +------------------+--------------+ | NF | a | +------------------+--------------+ | EF | = | +------------------+--------------+ | UV | ~ | +------------------+--------------+ | B23mBnFpCYRsDF== | 0123456789 | +------------------+--------------+ | B23mBnFpCYRsDF~~ | 0123456789 | +------------------+--------------+ Table 3: Base64 Sortable Decode Table Appendix C. Industry Tests To validate the lexicographical sortability of the Base64sort alphabet in common computing environments, a series of tests were conducted across various programming languages and database systems. Davis & Brown Expires 12 October 2026 [Page 8] Internet-Draft base64-sort April 2026 The objective was to observe how a mixed list of characters from the proposed alphabet would sort using their default string comparison mechanisms. C.1. Programming Language Results Tests were performed using Python, C, C++, Java, JavaScript, Delphi/ Object Pascal, Perl, and Go. In these languages, a list containing a subset of the Base64sort alphabet characters (A, a, b, 7, 3, B, C, c, E, z, -, _) was sorted. The results consistently demonstrated sorting according to the US- ASCII character order: -, 3, 7, A, B, C, E, _, a, b, c, z. This indicates that the chosen character set and their relative ASCII values are respected by the default string sorting algorithms in these environments. However, C# and Visual Basic exhibited a different sorting behavior, placing _ before 3 and sorting uppercase letters after their lowercase counterparts (e.g., a before A). This suggests that their default string comparison routines may employ locale-aware or cultural sorting rules rather than strict ordinal (ASCII) comparison. C.2. Database Test Results Database tests were conducted on PostgreSQL, MongoDB, and Redis. With PostgreSQL, when using ORDER BY val ASC, the default collation resulted in underscore (_) appearing before the hyphen (-), and lowercase letters before uppercase letters. However, explicitly specifying ORDER BY val COLLATE "C" (which enforces a C locale, often equivalent to strict ASCII ordering) produced the desired sort order: -, 3, 7, A, B, C, E, _, a, b, c, z. MongoDB's default sort behavior for the test set aligned with the desired US-ASCII order, matching the results observed in most programming languages. Redis's SORT ... ALPHA command also showed a deviation, placing _ before 3 and lowercase letters before uppercase, similar to the default SQL, C#, and Visual Basic results. Davis & Brown Expires 12 October 2026 [Page 9] Internet-Draft base64-sort April 2026 C.3. Conclusion The testing confirms that the Base64 Sortable alphabet generally achieves its goal of producing lexicographically sortable output when standard US-ASCII or C-locale string comparison rules are applied. Implementers should be aware that some programming languages and database systems may employ locale-aware or alternative default collation rules that can alter the sort order. To ensure consistent binary-equivalent sorting, explicit specification of ordinal or C-locale collation may be necessary in environments where such options are available. Authors' Addresses Kyzer R. Davis Cisco Systems Email: kydavis@cisco.com, kyzer.davis@outlook.com Dillon Brown Cisco Systems Email: dillbrow@cisco.com Davis & Brown Expires 12 October 2026 [Page 10]