Subject: [Cbor] Packed CBOR review

From: Brendan Moran <[email-masked]>
Date: Wed, 16 Jun 2021 09:21:46 +0000

As promised, here is my review of draft-ietf-cbor-packed.

Overall, I have few comments and I am confident that this draft will improve compactness of cbor structures—at least the ones I care about—with little overhead.

I don’t see any explanation of how to handle hierarchical packing. This would resolve the issue on Page 7.

      |  ISSUE: Not sure that we want to use the efficiencies of
      |  overriding, but having default values supplied out of a
      |  dictionary to be overridden by a rump sounds rather handy.
      |  Note that there is no way to remove a map entry from the table.

My take on this issue is: handle this the same way as hierarchical packing.

I do have a proposal for hierarchical packing. It’s a single, simple rule: References overflow from any table to a parent table. This means that the parser holds a stack of packing tables. Any time it encounters a reference, it attempts to apply that reference to the topmost table in the stack, deducting the size of the table from the reference and traversing the stack to the next table in the stack each time the reference is larger than the number of elements in the table.

Example:

Raw data:
{
    "label1" : "value1",
    "label2" : "value2",
    "label3" : "value3”
}

Compressed:

51([
    [],
    ["label"],
    [],
    51(
        [
            [],
            ["value"],
            [],
            {
               225("1") : 6("1"),
               225("2") : 6("2"),
               225("3") : 6("3")
            }
        ]
    )
])

If the outer table were implicit:

[
    [],
    ["value"],
    [],
    {
       225("1") : 6("1"),
       225("2") : 6("2"),
       225("3") : 6("3")
    }
]

I would also propose adding another element to the table: an identifier for a pre-shared reference table:

[
    “MyTable”,
    [],
    ["value"],
    [],
    {
       225("1") : 6("1"),
       225("2") : 6("2"),
       225("3") : 6("3")
    }
]

Best Regards,
Brendan

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 16 Jun 2021 15:07:55 +0200

> I would also propose adding another element to the table: an identifier for a pre-shared reference table:

I’m wondering what the allocation mechanics for such an identifier would be.

Let me go through a few cases and explain how I would handle it.

* IANA

Pro: can be very compact.  
Con (pro as well): high threshold, limited set.

Solution: allocate a tag for the identifier, either wrapping a tag 51 or replacing it (in particular if not all tables need to be advanced).

Task: We probably should define how to define such a tag.

* Context

Pro: can be embedded nicely.
Con: Wherever the context comes from (e.g., referencing standard) needs to make sure the reference is unambiguous.

Task: Not sure what we can do here, except maybe giving an example.

* URI

Pro: Free for all.
Con: Hard to control.

There will need to be some security and assurance of non-mutability on the data that URI describes.
Preferred URI scheme would be ni:, but see next.

Task: Define URI import tag; shape of data structure that should be used (almost, but not entirely, like tag 51).

* Hash

Pro: No-brainer
Con: Can’t find the dictionary unless I already know it.
Hashes are large (at least when secure).

Task:
Define Hash import tag, shape of data structure that is being hashed (see above).

Apparently, in all cases it would be good to have a single data structure shape pre-defined for pre-populating the tables (“dictionary”).

Grüße, Carsten

---

From: Brendan Moran <[email-masked]>
Date: Thu, 17 Jun 2021 09:08:18 +0000

> On 16 Jun 2021, at 14:07, Carsten Bormann <[email-masked]> wrote:
>

We can have our cake and eat it too. I don’t see a reason not to support all of these choices.

> Define Hash import tag, shape of data structure that is being hashed (see above).

If we simply use a different type in each case, the encoding is unambiguous:

Basic-Packed-CBOR = #6.51([ ?dictionary-reference, [*shared], [*prefix], [*suffix], rump])
rump = any
prefix = any
suffix = any
shared = any

dictionary-reference /= standard-reference
dictionary-reference /= uri-reference
dictionary-reference /= hash-reference
dictionary-reference /= context-reference

standard-reference = uint
uri-reference = tstr
hash-reference = bstr
context-reference = null

> Apparently, in all cases it would be good to have a single data structure shape pre-defined for pre-populating the tables (“dictionary”).

I can see two possibilities here:

1) just use the existing structure:

Packed-CBOR-Dictionary = [ ?reference, [*shared], [*prefix], [*suffix]]

2) eliminate any distinction between the different tables; leave that to the packing table.

Packed-CBOR-Dictionary = [?reference, [*fragment]]

For simplicity in the parser, I’d be inclined to go with option 1 and just make the Packed-CBOR-Dictionary a packing table with no rump.

Best Regards,
Brendan

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 17 Jun 2021 11:24:03 +0200

> We can have our cake and eat it too. I don’t see a reason not to support all of these choices.

Absolutely — we then just need to design how each of these choices should look like.

> standard-reference = uint

I think I’d rather have

Table-Setup-Uri = #6.52([Uri-reference, any])
Etc.
But stacking the tags (and spending another array) costs three more bytes.

But maybe that stacking is most useful for 
Spiffy-Standard-A-Table-Setup = #6.4711(any)
Where 4711 is a tag allocated by spiffy standard A.
(Otherwise we’d need a separate registry for that uint, and that makes me shudder.)

In any case, stacking would allow stacking a couple standard references.

How would the hash reference specify the algorithm?
(I think CFRG would tell us that collision resistance between algorithms isn’t a well-defined property.)

I’m also not sure that a context-reference always is null, maybe the context supplies alternate tables…

(I’m always a little put off by optional array elements in a sequence, that gets into actual parsing quickly, but this one here may be OK.)

> Packed-CBOR-Dictionary = [ ?reference, [*shared], [*prefix], [*suffix]]

Probably.
Should that get a tag?

Grüße, Carsten

---

From: Henk Birkholz <[email-masked]>
Date: Thu, 17 Jun 2021 11:27:50 +0200

Hi Brendan,

quick reply with an upfront, overall +1. Small comments in-line

> We can have our cake and eat it too. I don’t see a reason not to support all of these choices.

That sounds absolutely reasonable to me!

>> Preferred URI scheme would be ni:, but see next.
Henk
> standard-reference = uint

Semantics look fine, not sure of the final structure though.

> For simplicity in the parser, I’d be inclined to go with option 1 and just make the Packed-CBOR-Dictionary a packing table with no rump.

We are really optimizing for bytes here, right? That should be 
significant decision factor. Then again, a tad bit more hierarchy here 
might provide great benefits?

> IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not…

Viele Grüße,

Henk

> _______________________________________________
> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor
>

---

From: Brendan Moran <[email-masked]>
Date: Thu, 17 Jun 2021 11:17:34 +0000

> On 17 Jun 2021, at 10:24, Carsten Bormann <[email-masked]> wrote:
>
>>

This only costs us a tag definition and it simplifies parsing. This is probably correct.

> But stacking the tags (and spending another array) costs three more bytes.

I think this decision depends a lot on what the expected model is. For a single dictionary reference, it’s pretty irrelevant, so we should pick whichever is more idiomatic. The issue is when your reference wants a reference.  For example, suppose I have two reference tables that share a lot of values: Table A and Table B. With stacking tags, I am forced to make a tradeoff: either duplicate data on the endpoint or increase the size of the transmitted data:

If Table A and Table B contain duplicate data:
Data-A = 52([“Table A”, …])

If Table C contains the common parts of Tables A and B:

Data-A = 52([“Table C”, 52([“Table A”, …])])

If every table is allowed to define a reference, this problem disappears, however it creates a new one: a compressor cannot select an arbitrary set of tables known by the decompressor and compose them in the optimal order.

> (I think CFRG would tell us that collision resistance between algorithms isn’t a well-defined property.)

We could possibly reuse SUIT digest definitions for this:
suit-digest = [algorithm-id : uint, digest: bstr]

If we use a second tag for the reference table setup, this is unambiguous.

Alternatively, cbor-wg or cose-wg could define tags for common digest algorithms.

> I’m also not sure that a context-reference always is null, maybe the context supplies alternate tables…

If that is the case, I suspect a context-reference should have its own tag as well.

>> Packed-CBOR-Dictionary = [ ?reference, [*shared], [*prefix], [*suffix]]

I don’t think it needs one, but feel free to convince me otherwise. Its use should always be explicit since it’s always known by a compressor or decompressor. It should always be in a map of reference/table pairs.

Best Regards,
Brendan

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 17 Jun 2021 13:23:30 +0200

> I don’t think it needs one, but feel free to convince me otherwise. Its use should always be explicit since it’s always known by a compressor or decompressor. It should always be in a map of refere…

Actually, I think this should get a media-type, and appropriate content-format numbers (and then it would work with file-magic as well).

Grüße, Carsten

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 17 Jun 2021 13:33:19 +0200

> Alternatively, cbor-wg or cose-wg could define tags for common digest algorithms.

I thought COSE did: https://datatracker.ietf.org/doc/draft-ietf-cose-hash-algs/
(in RFC editor queue; registrations already done) did this:

   | Name        | Value | Recommended |
   |-------------|-------|-------------|
   | SHA-1       |   -14 | Filter Only |
   | SHA-256/64  |   -15 | Filter Only |
   | SHA-256     |   -16 | Yes         |
   | SHA-384     |   -43 | Yes         |
   | SHA-512     |   -44 | Yes         |
   | SHA-512/256 |   -17 | Yes         |
   | SHAKE128    |   -18 | Yes         |
   | SHAKE256    |   -45 | Yes         |

Grüße, Carsten

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 17 Jun 2021 13:35:03 +0200

>   | Name        | Value | Recommended |

Sorry, didn’t read properly.
It defines COSE values, not tags…

Grüße, Carsten

---

From: Brendan Moran <[email-masked]>
Date: Thu, 17 Jun 2021 13:55:25 +0000

It would be nice if this had some CDDL so that I could reference it in other specifications.

Best Regards,
Brendan

> On 17 Jun 2021, at 12:33, Carsten Bormann <[email-masked]> wrote:
>
>

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 17 Jun 2021 16:11:05 +0200

> It would be nice if this had some CDDL so that I could reference it in other specifications.

That raises the overall question how IANA registries could be made available in CDDL.

This particular case is probably the most difficult one, as the "COSE Algorithms” registry combines various kinds of algorithms into one registry, so essentially one would like to make an SQL query over that :-)

SELECT Value 
  FROM IANA.cose#algorithms 
  WHERE recommended=“yes” and capabilities=“[]”

(Hmm, I don’t understand how the capabilities, are mapped in the current registry — the SHA-256 entry there says “[kty]” but draft-ietf-cose-hash-algs-09 says "[]”.  Is capabilities even a good way to select an algorithm?)

Grüße, Carsten

---

From: Christian Amsüss <[email-masked]>
Date: Fri, 18 Jun 2021 10:00:50 +0200

Hi,

> > I don’t think it needs one, but feel free to convince me otherwise.
> > Its use should always be explicit since it’s always known by a
> > compressor or decompressor. It should always be in a map of
> > reference/table pairs.
> 
> Actually, I think this should get a media-type, and appropriate
> content-format numbers (and then it would work with file-magic as
> well).

I agree, a content-format number would suffice.

I can't tell whether it should get a self-describing tag *too* or
whether the one that comes with the content format (in which the table
is wrapped in a bstr) suffices.

BR
c

-- 
To use raw power is to make yourself infinitely vulnerable to greater powers.
  -- Bene Gesserit axiom

---

From: Christian Amsüss <[email-masked]>
Date: Fri, 18 Jun 2021 10:05:47 +0200

> suit-digest = [algorithm-id : uint, digest: bstr]

When we already cater for URIs, we could just use RFC6920 URIs that do
express the used hash -- example:
ni:///sha-256;UyaQV-Ev4rdLoHyJJWCi11OHfrYv9E1aGQAlMO2X_-Q

That's annoying encoding and verbose, but CRIs could maybe (ok, it's a
big maybe) provide a compact serialization for them if [#5] happens.

BR
c

[#5]: https://github.com/core-wg/coral/issues/5

---

From: Christian Amsüss <[email-masked]>
Date: Fri, 18 Jun 2021 18:17:52 +0200

Hello CBOR group,

we've just spent some time discussing the use of packed CBOR in CoRAL,
and the current working assumptionis that we'll use the very same
mechanism.

That means we'll do some practical exploration with something similar to

> Table-Setup-Uri = #6.52([Uri-reference, any])

and see how it applies there.

One thing we'll probably keep of our older designs is the bounded
import: Previously we described our data source tables as lists of
(source, first-import, last-import) where the latter two are numeric and
allow picking just a slice of the external dictionary. This has two
benefits:

* It keeps the number of (efficient) low-number imports slow -- if you
  need two of here and two of there, you can express all of them in
  single bytes even though both dictionaries may contain 20 items each.

* It provides extensibility. That's even practical on non-extensible
  dicts (as a consumer might make sense of the document not knowing how
  many items are in there), and more so with extensible dicts (which of
  course can only be extensible by adding more entries but not by
  mutating earlier ones, that'd be a recipe for desaster).

Hoping for a frugal exchange of ideas and experiments
Christian