Internet-Draft | Packed CBOR | February 2021 |
Bormann | Expires 13 August 2021 | [Page] |
The Concise Binary Object Representation (CBOR, RFC 8949) is a data format whose design goals include the possibility of extremely small code size, fairly small message size, and extensibility without the need for version negotiation.¶
CBOR does not provide any forms of data compression. CBOR data items, in particular when generated from legacy data models often allow considerable gains in compactness when applying data compression. While traditional data compression techniques such as DEFLATE (RFC 1951) work well for CBOR, their disadvantage is that the receiver needs to unpack the compressed form to make use of data.¶
This specification describes Packed CBOR, a simple transformation of a CBOR data item into another CBOR data item that is almost as easy to consume as the original CBOR data item. A separate decompression step is therefore often not required at the receiver.¶
This is a working-group draft of the CBOR working group of the IETF, https://datatracker.ietf.org/wg/cbor/about/. Discussion takes places on the github repository https://github.com/cbor-wg/cbor-packed and on the CBOR WG mailing list, https://www.ietf.org/mailman/listinfo/cbor.¶
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 13 August 2021.¶
Copyright (c) 2021 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 Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.¶
(TO DO, expand on text from abstract here; move references here and neuter them in the abstract as per Section 4.3 of [RFC7322].)¶
The specification defines a transformation from a Packed CBOR data item to the original CBOR data item; it does not define an algorithm for an actual packer. Different packers can differ in the amount of effort they invest in arriving at a minimal packed form.¶
Packed CBOR can employ two kinds of optimization:¶
A specific application protocol that employs Packed CBOR might allow both kinds of optimization or limit the representation to item sharing only.¶
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.¶
A shared item reference or an affix reference¶
A reference to a shared item as defined in Section 2.2¶
A reference that combines an affix item as defined in Section 2.3.¶
Prefix or suffix.¶
The triple of a shared item table, a prefix table, and a suffix table.¶
The result of applying a packed reference in the context of given Packing tables.¶
The definitions of [RFC8949] apply. The term "byte" is used in its now customary sense as a synonym for "octet". Where bit arithmetic is explained, this document uses the notation familiar from the programming language C (including C++14's 0bnnn binary literals), except that, in the plain text form of this document, the operator "^" stands for exponentiation.¶
Packed CBOR is defined in two parts: Referencing packing tables (this section) and setting up packing tables (Section 3).¶
At any point within a data item making use of Packed CBOR, there is a Current Set of packing tables that applies.¶
There are three packing tables in a Current Set:¶
Without any table setup, all these tables are empty arrays. Table setup can cause these arrays to be non-empty, where the elements are (potentially themselves packed) data items. In the abstract, each of the tables is indexed by an unsigned integer (starting from 0).¶
Prefix items are stored in the prefix table of the Current Set; suffix items are stored in the suffix table of the Current Set. We collectively call these items affix items; when referencing, which of the tables is actually used depends on whether a prefix or a suffix reference was used.¶
prefix reference | table index |
---|---|
Tag 6(suffix) | 0 |
Tag 225-255(suffix) | 1-31 |
Tag 28704-32767(suffix) | 32-4095 |
Tag 1879052288-2147483647(suffix) | 4096-268435455 |
suffix reference | table index |
---|---|
Tag 216-223(prefix) | 0-7 |
Tag 27647-28671(prefix) | 8-1023 |
Tag 1811940352-1879048191(prefix) | 1024-67108863 |
Affix data items are referenced by using the data items in Table 2 and Table 3. Each of these implies the table used (prefix or suffix), a table index (an unsigned integer) and contains a "rump item". When reconstructing the original data item, such a reference is replaced by a data item constructed from the referenced affix data item (affix, which might need to be recursively unpacked first) "concatenated" with the tag content (rump, again possibly recursively unpacked).¶
As a contrived (but short) example, if the prefix table is ["foobar",
"foob", "fo"]
, the following prefix references will all unpack to
"foobart"
: 6("t")
, 224("art")
, 225("obart")
(the last example
isn't really an optimization).¶
Taking into account the encoding, there is one single-byte prefix reference, 31 (25-20) two-byte references, 4064 (212-25) three-byte references, and 26843160 (228-212) five-byte references for prefixes. 268435455 (228) is an artificial limit, but should be high enough that there, again, is no practical limit to how many prefix items might be used in a Packed CBOR item. The numbers for suffix references are one quarter of those, except that there is no single-byte reference and 8 two-byte references.¶
This specification uses up a large number of Simple Values and Tags, in particular one of the rare one-byte tags and half of the one-byte simple values. Since the objective is compression, this is warranted if and only if there is consensus that this specific format could be useful for a wide area of applications, while maintaining reasonable simplicity in particular at the side of the consumer.¶
A maliciously crafted Packed CBOR data item might contain a reference loop. A consumer/decompressor MUST protect against that.¶
The current definition does nothing to help with packing CBOR sequences [RFC8742]; maybe it should.¶
The packing references described in Section 2 assume that packing tables have been set up.¶
By default, all three tables are empty (zero-length arrays).¶
Table setup can happen in one of two ways:¶
The present specification only defines a single tag for prepending to the (by default empty) tables.¶
A predefined tag for packing table setup is defined in CDDL [RFC8610] as in Figure 1:¶
(This assumes the allocation of tag number 51.)¶
The arrays given as the first, second, and third element of the content of the tag 51 are prepended to the tables for shared items, prefixes, and suffixes that apply to the entire tag (by default empty tables).¶
The original CBOR data item can be reconstructed by recursively replacing shared, prefix, and suffix references encountered in the rump by their expansions.¶
In the registry [IANA.cbor-tags], IANA is requested to allocate the tags defined in Table 4.¶
Tag | Data Item | Semantics | Reference |
---|---|---|---|
6 | integer, text string, byte string, array, map | Packed CBOR: shared/prefix | draft-ietf-cbor-packed |
225-255 | text string, byte string, array, map | Packed CBOR: prefix | draft-ietf-cbor-packed |
28704-32767 | text string, byte string, array, map | Packed CBOR: prefix | draft-ietf-cbor-packed |
1879052288-2147483647 | text string, byte string, array, map | Packed CBOR: prefix | draft-ietf-cbor-packed |
216-223 | text string, byte string, array, map | Packed CBOR: suffix | draft-ietf-cbor-packed |
27647-28671 | text string, byte string, array, map | Packed CBOR: suffix | draft-ietf-cbor-packed |
1811940352-1879048191 | text string, byte string, array, map | Packed CBOR: suffix | draft-ietf-cbor-packed |
In the registry [IANA.cbor-simple-values], IANA is requested to allocate the simple values defined in Table 5.¶
Value | Semantics | Reference |
---|---|---|
0-15 | Packed CBOR: shared | draft-ietf-cbor-packed |
The security considerations of [RFC8949] apply.¶
Loops in the Packed CBOR can be used as a denial of service attack, see Section 2.4.¶
As the unpacking is deterministic, packed forms can be used as signing inputs. (Note that if external dictionaries are added to cbor-packed, this requires additional consideration.)¶
The (JSON-compatible) CBOR data structure depicted in Figure 2, 400 bytes of binary CBOR, could lead to a packed CBOR data item depicted in Figure 3, ~309 bytes. Note that this particular example does not lend itself to prefix compression.¶
The (JSON-compatible) CBOR data structure below has been packed with shared item and (partial) prefix compression only.¶
CBOR packing was originally invented with the rest of CBOR, but did not make it into [RFC7049], the predecessor of [RFC8949]. Various attempts to come up with a specification over the years didn't proceed. In 2017, Sebastian Käbisch proposed investigating compact representations of W3C Thing Descriptions, which prompted the author to come up with essentially the present design.¶