Internet-Draft | Packed CBOR | September 2024 |
Bormann & Gütschow | Expires 6 March 2025 | [Page] |
The Concise Binary Object Representation (CBOR, RFC 8949 == STD 94) 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) can work well for CBOR encoded data items, their disadvantage is that the recipient needs to decompress the compressed form to make use of the 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 recipient.¶
The present version (-13
) is a refresh of the implementation
draft -12
with minor editorial improvements.¶
This note is to be removed before publishing as an RFC.¶
Status information for this document may be found at https://datatracker.ietf.org/doc/draft-ietf-cbor-packed/.¶
Discussion of this document takes place on the CBOR Working Group mailing list (mailto:[email protected]), which is archived at https://mailarchive.ietf.org/arch/browse/cbor/. Subscribe at https://www.ietf.org/mailman/listinfo/cbor/.¶
Source for this draft and an issue tracker can be found at https://github.com/cbor-wg/cbor-packed.¶
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 6 March 2025.¶
Copyright (c) 2024 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.¶
The Concise Binary Object Representation (CBOR, [STD94]) 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 [RFC1951] can work well for CBOR encoded data items, their disadvantage is that the recipient needs to decompress the compressed form to make use of the 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 recipient.¶
This document defines the Packed CBOR format by specifying the transformation from a Packed CBOR data item to the original CBOR data item; it does not define an algorithm for a packer. Different packers can differ in the amount of effort they invest in arriving at a minimal packed form; often, they simply employ the sharing that is natural for a specific application.¶
Packed CBOR can make use of two kinds of optimization:¶
item sharing: substructures (data items) that occur repeatedly in the original CBOR data item can be collapsed to a simple reference to a common representation of that data item. The processing required during consumption is limited to following that reference.¶
argument sharing: application of a function with two arguments, one of which is shared. Data items (strings, containers) that share a prefix or suffix, or more generally data items that can be constructed from a function taking a shared argument and a rump data item, can be replaced by a reference to the shared argument plus a rump data item. For strings and the default "concatenation" function, the processing required during consumption is similar to following the argument reference plus that for an indefinite-length string.¶
A specific application protocol that employs Packed CBOR might allow both kinds of optimization or limit the representation to item sharing only.¶
Packed CBOR is defined in two parts: Referencing packing tables (Section 2) and setting up packing tables (Section 3).¶
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 [BCP14] (RFC2119) (RFC8174) when, and only when, they appear in all capitals, as shown here.¶
A CBOR data item that is intended to be expressed by a packed data item; the result of all reconstructions.¶
A CBOR data item that involves packed references (packed CBOR).¶
A shared item reference or an argument reference.¶
A reference to a shared item as defined in Section 2.2.¶
A reference that combines a shared argument with a rump item as defined in Section 2.3.¶
The data item contained in an argument reference that is combined with the argument to yield the reconstruction.¶
An argument reference that uses the argument as the left-hand side and the rump as the right-hand side.¶
An argument reference that uses the rump as the left-hand side and the argument as the right-hand side.¶
A tag used in an argument reference for the argument (straight references) or the rump (inverted references), causing the application of a function indicated by the function tag in order to reconstruct the data item.¶
The pair of a shared item table and an argument table.¶
The packing tables in effect at the data item under consideration.¶
The result of applying a packed reference in the context of given packing tables; we speak of the reconstruction of a packed reference as that result.¶
The definitions of [STD94] apply. Specifically: The term "byte" is used in its now customary sense as a synonym for "octet"; "byte strings" are CBOR data items carrying a sequence of zero or more (binary) bytes, while "text strings" are CBOR data items carrying a sequence of zero or more Unicode code points (more precisely: Unicode scalar values), encoded in UTF-8 [STD63].¶
Where arithmetic is explained, this document uses the notation familiar from the programming language C, except that ".." denotes a range that includes both ends given, in the HTML and PDF versions, subtraction and negation are rendered as a hyphen ("-", as are various dashes), and superscript notation denotes exponentiation. For example, 2 to the power of 64 is notated: 264. In the plain-text version of this specification, superscript notation is not available and therefore is rendered by a surrogate notation. That notation is not optimized for this RFC; it is unfortunately ambiguous with C's exclusive-or and requires circumspection from the reader of the plain-text version.¶
Examples of CBOR data items are shown in CBOR Extended Diagnostic Notation (Section 8 of RFC 8949 [STD94] in conjunction with Appendix G of [RFC8610] ➔ possibly update to [I-D.ietf-cbor-edn-literals]).¶
This section describes the packing tables, their structure, and how they are referenced.¶
At any point within a data item making use of Packed CBOR, there is an active set of packing tables that applies.¶
There are two packing tables in an active set:¶
Without any table setup, these two tables are empty arrays. Table setup can cause these arrays to be non-empty, where the elements are (potentially themselves packed) data items. Each of the tables is indexed by an unsigned integer (starting from 0). Such an index may be derived from information in tags and their content as well as from CBOR simple values.¶
Table setup mechanisms (see Section 3) may include all information needed for table setup within the packed CBOR data item, or they may refer to external information. This information may be immutable, or it may be intended to potentially grow over time. This raises the question of how a reference to a new item should be handled when the unpacker uses an older version of the external information.¶
If, during unpacking, an index is used that references an item that is
unpopulated in (e.g., outside the size of) the table in use, this MAY be treated as an
error by the unpacker and abort the unpacking.
Alternatively, the unpacker MAY provide the special value
1112(undefined)
(the simple value >undefined< as per Section 5.7 of RFC 8949 [STD94], enclosed in the tag 1112) to the application and leave the
error handling to the application.
An unpacker SHOULD document which of these two alternatives has been
chosen.
CBOR based protocols that include the use of packed CBOR
MAY require that unpacking errors are tolerated in some positions.¶
The argument table serves as a common table that can be used for argument references, i.e., for concatenation as well as references involving a function tag.¶
When referencing an argument, a distinction is made between straight and inverted references; if no function tag is involved, a straight reference combines a prefix out of the argument table with the rump data item, and an inverted reference combines a rump data item with a suffix out of the argument table.¶
straight reference | table index |
---|---|
Tag 6(rump) | 0 |
Tag 224..255(rump) | 0..31 |
Tag 28704..32767(rump) | 32..4095 |
Tag 1879052288..2147483647(rump) | 4096..268435455 |
inverted reference | table index |
---|---|
Tag 216..223(rump) | 0..7 |
Tag 27647..28671(rump) | 8..1023 |
Tag 1811940352..1879048191(rump) | 1024..67108863 |
Argument data items are referenced by using the reference data items in Table 2 and Table 3.¶
The tag number of the reference is used to derive a table index (an unsigned integer) leading to the "argument"; the tag content of the reference is the "rump item".¶
When reconstructing the original data item, such a reference is replaced by a data item constructed from the argument data item found in the table (argument, which might need to be recursively unpacked first) and the rump data item (rump, again possibly needing to be recursively unpacked).¶
Separate from the tag used as a reference, a tag ("function tag") may be involved to supply a function to be used in resolving the reference. It is crucial not to confuse reference tag and, if present, function tag.¶
A straight reference uses the argument as the provisional left-hand side and the rump data item as the right-hand side. An inverted reference uses the rump data item as the provisional left-hand side and the argument as the right-hand side.¶
In both cases, the provisional left-hand side is examined. If it is a tag ("function tag"), it is "unwrapped": The function tag's tag number is used to indicate the function to be applied, and the tag content is kept as the unwrapped left-hand side. If the provisional left-hand side is not a tag, it is kept as the unwrapped left-hand side, and the function to be applied is concatenation, as defined below. The right-hand side is taken as is as the unwrapped right-hand side.¶
If a function tag was given, the reference is replaced by the result of applying the indicated unpacking function with the left-hand side as its first argument and the right-hand side as its second. The unpacking function is defined by the definition of the tag number supplied. If that definition does not define an unpacking function, the result of the unpacking is not valid.¶
If no function tag was given, the reference is replaced by the left-hand side "concatenated" with the right-hand side, where concatenation is defined as in Section 2.4.¶
As a contrived (but short) example, if the argument table is
["foobar", h'666f6f62', "fo"]
, each of the following straight (prefix)
references will unpack to "foobart"
: 6("t")
, 225("art")
,
226("obart")
(the byte string h'666f6f62' == 'foob' is concatenated
into a text string, and the last example is not an optimization).¶
Note that table index 0 of the argument table can be referenced both with tag 6 and tag 224, however tag 6 with an integer content is used for shared item references (see Table 1), so to combine index 0 with an integer rump, tag 224 needs to be used. The preferred encoding uses tag 6 if that is not necessary.¶
Taking into account the encoding and ignoring the less optimal tag
224, there is one single-byte straight (prefix)
reference, 31 (25-
20) two-byte references, 4064
(212-
25) three-byte references, and 26843160
(228-
212) five-byte references for straight references.
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 inverted (suffix) references are one quarter of those, except
that there is no single-byte reference and 8 two-byte references.¶
The concatenation function is defined as follows:¶
If both left-hand side and right-hand side are arrays, the result of the concatenation is an array with all elements of the left-hand-side array followed by the elements of the right-hand side array.¶
If both left-hand side and right-hand side are maps, the result of
the concatenation is a map that is initialized with a copy of the
left-hand-side map, and then filled in with the members of the
right-hand side map, replacing any existing members that have the
same key.
In order to be able to remove a map entry from the left-hand-side
map, as a special case, any members to be replaced with a value of
undefined
(0xf7) from the right-hand-side map are instead removed,
and right-hand-side members with the value undefined
are never
filled in into the concatenated map.¶
If both left-hand side and right-hand side are one of the string types (not necessarily the same), the bytes of the left-hand side are concatenated with the bytes of the right-hand side. Byte strings concatenated with text strings need to contain valid UTF-8 data. The result of the concatenation gets the type of the unwrapped rump data item; this way a single argument table entry can be used to build both byte and text strings, depending on what type of rump is being used.¶
If one side is one of the string types, and the other side is an array, the result of the concatenation is equivalent to the application of the "join" function (Section 4.1) to the string as the left-hand side and the array as the right-hand side. The original right-hand side of the concatenation determines the string type of the result.¶
Other type combinations of left-hand side and right-hand side are not valid.¶
This specification uses up a large number of Simple Values and Tags, in particular one of the rare one-byte tags and two thirds of the one-byte simple values. Since the objective is compression, this is warranted only based on a 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 packing references described in Section 2 assume that packing tables have been set up.¶
By default, both tables are empty (zero-length arrays).¶
Table setup can happen in one of two ways:¶
By the application environment, e.g., a media type. These can define tables that amount to a static dictionary that can be used in a CBOR data item for this application environment. Note that, without this information, a data item that uses such a static dictionary can be decoded at the CBOR level, but not fully unpacked. The table setup mechanisms provided by this document are defined in such a way that an unpacker can at least recognize if this is the case.¶
By one or more table-building tags enclosing the packed content. Each tag is usually defined to build an augmented table by adding to the packing tables that already apply to the tag, and to apply the resulting augmented table when unpacking the tag content. Usually, the semantics of the tag will be to prepend items to one or more of the tables. (The specific behavior of any such tag, in the presence of a table applying to it, needs to be carefully specified.)¶
Note that it may be useful to leave a particular efficiency tier alone and only prepend to a higher tier; e.g., a tag could insert shared items at table index 16 and shift anything that was already there further along in the array while leaving index 0 to 15 alone. Explicit additions by tag can combine with application-environment supplied tables that apply to the entire CBOR data item.¶
Packed item references in the newly constructed (low-numbered) parts of the table are usually interpreted in the number space of that table (which includes the, now higher-numbered, inherited parts), while references in any existing, inherited (higher-numbered) part continue to use the (more limited) number space of the inherited table.¶
Where external information is used in a table setup mechanism that is not immutable, care needs to be taken so that, over time, references to existing table entries stay valid (i.e., the information is only extended), and that a maximum size of this information is given. This allows an unpacker to recognize references to items that are not yet defined in the version of the external reference that it uses, providing backward and possibly limited (degraded) forward compatibility.¶
For table setup, the present specification only defines two simple table-building tags, which operate by prepending to the (by default empty) tables.¶
Two tags are predefined by this specification for packing table setup. They are defined in CDDL [RFC8610] as in Figure 1:¶
(This assumes the allocation of tag numbers 113 ('q') and 1113 for these tags.)¶
The array given as the first element of the content of tag 113 ("Basic-Packed-CBOR") is prepended to both the tables for shared items and arguments that apply to the entire tag (by default empty tables). The arrays given as the first and second element of the content of the tag 1113 ("Split-Basic-Packed-CBOR") are prepended to the tables for shared items and arguments, respectively, that apply to the entire tag (by default empty tables). As discussed in the introduction to this section, references in the supplied new arrays use the new number space (where inherited items are shifted by the new items given), while the inherited items themselves use the inherited number space (so their semantics do not change by the mere action of inheritance).¶
The original CBOR data item can be reconstructed by recursively replacing shared and argument references encountered in the rump by their reconstructions.¶
In Section 5.3.2 of RFC 8949 [STD94], the validity of tags is defined in terms of type and value of their tag content. The CBOR Tag registry ([IANA.cbor-tags] as defined in Section 9.2 of RFC 8949 [STD94]) allows recording the "data item" for a registered tag, which is usually an abbreviated description of the top-level data type allowed for the tag content.¶
In other words, in the registry, the validity of a tag of a given tag number is described in terms of the top-level structure of the data carried in the tag content. The description of a tag might add further constraints for the data item. But in any case, a tag definition can only specify validity based on the structure of its tag content.¶
In Packed CBOR, a reference tag might be "standing in" for the actual tag content of an outer tag, or for a structural component of that. In this case, the formal structure of the outer tag's content before unpacking usually no longer fulfills the validity conditions of the outer tag.¶
The underlying problem is not unique to Packed CBOR. For instance, [RFC8746] describes tags 64..87 that "stand in" for CBOR arrays (the native form of which has major type 4). For the other tags defined in this specification, which require some array structure of the tag content, a footnote was added:¶
[...] The second element of the outer array in the data item is a native CBOR array (major type 4) or Typed Array (one of tag 64..87)¶
The top-down approach to handle the "rendezvous" between the outer and inner tags does not support extensibility: any further Typed Array tags being defined do not inherit the exception granted to tag number 64..87; they would need to formally update all existing tag definitions that can accept typed arrays or be of limited use with these existing tags.¶
Instead, the tag validity mechanism needs to be extended by a bottom-up component: A tag definition needs to be able to declare that the tag can "stand in" for, (is, in terms of tag validity, equivalent to) some structure.¶
E.g., tag 64..87 could have declared their equivalence to the CBOR major type 4 arrays they stand in for.¶
A tag definition MAY declare Tag Equivalence to some existing structure for the tag, under some conditions defined by the new tag definition. This, in effect, extends all existing tag definitions that accept the named structure to accept the newly defined tag under the conditions given for the Tag Equivalence.¶
A number of limitations apply to Tag Equivalence, which therefore should be applied deliberately and sparingly:¶
Tag Equivalence is a new concept, which may not be implemented by an existing generic decoder. A generic decoder not implementing tag equivalence might raise tag validity errors where Tag Equivalence says there should be none.¶
A CBOR protocol MAY specify the use of Tag Equivalence, effectively limiting the protocol's full use to those generic encoders that implement it. Existing CBOR protocols that do not address Tag Equivalence implicitly have a new variant that allows Tag Equivalence (e.g., to support Packed CBOR with an existing protocol). A CBOR protocol that does address Tag Equivalence MAY be explicit about what kinds of Tag Equivalence it supports (e.g., only the reference tags employed by Packed CBOR and certain table setup tags).¶
There is currently no way to express Tag Equivalence in CDDL. For Packed CBOR, CDDL would typically be used to describe the unpacked CBOR represented by it; further restricting the Packed CBOR is likely to lead to interoperability problems. (Note that, by definition, there is no need to describe Tag Equivalence on the receptacle side; only for the tag that declares Tag Equivalence.)¶
The registry "CBOR Tags" [IANA.cbor-tags] currently does not have a way to record any equivalence claimed for a tag. A convention would be to alert to Tag Equivalence in the "Semantics (short form)" field of the registry.Needs to be done for the tag registrations here.¶
In the registry "CBOR Simple Values" [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 [STD94] apply.¶
Loops in the Packed CBOR can be used as a denial of service attack, see Section 2.5.¶
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 be packed into the CBOR data item depicted in Figure 3, 308 bytes, only employing item sharing. With support for argument sharing and the record function tag 114, the data item can be packed into 298 bytes as depicted in Figure 4. Note that this particular example does not lend itself to prefix compression, so it uses the simple common-table setup form (tag 113).¶
The (JSON-compatible) CBOR data structure below has been packed with shared item and (partial) prefix compression only and employs the split-table setup form (tag 1113).¶
CBOR packing was part of the original proposal that turned into CBOR, but did not make it into [RFC7049], the predecessor of RFC 8949 [STD94]. Various attempts to come up with a specification over the years did not proceed. In 2017, Sebastian Käbisch proposed investigating compact representations of W3C Thing Descriptions, which prompted the author to come up with what turned into the present design.¶
This work was supported in part by the German Federal Ministry of Education and Research (BMBF) within the project Concrete Contracts.¶