Subject: [Cbor] Packed CBOR and dictionaries

From: Jim Schaad <[email-masked]>
Date: Thu, 27 Aug 2020 00:57:07 -0700

In the past two weeks packed CBOR has come up in two different contexts and
I have started trying to think how I would write a compression routine that
would be reasonable quick but still give good results.  Part of the question
that I keep running into is the fact that the use of a dictionary is going
to change how I approach this.  I may find that I want to put dictionary
entries into the prefix or shared section of the packed structure depending
on how far down in the dictionary the entries are.  

*  Should we be doing an equivalent draft to CBOR packed about how to use
dictionaries?  I think that having a standard dictionary expansion is going
to be important.

* Should the dictionary expansion be separate or part of this draft?  I am
not sure how I want to address this.  If you have a dictionary w/ 50,000
entries in it, that is going to change how things should be done.  It may
also be that one might want to use a dictionary entry for something that
might otherwise be encoded as a prefix and the prefix might not be needed
anymore.

* When building a dictionary, do I only want to do compete substitutions, or
it be recommended that prefixes also be encoded into the dictionary.  This
would mean that if dictionaries are treated completely separately that a
prefix encoding is needed there as well, but that encoding might be to a
substitution in the prefix section of the packed data followed by a prefix
using the packed encoding.

Being able to do packed is going to be of importance for doing CoRAL, but
just as important is being able to do dictionaries.  Dictionaries do have
the downside that if they are not referenced internal to the structure then
from a security point of view they can be problematic as the
signed/encrypted CBOR byte stream is no longer self-contained.  This is not
a problem for packed CBOR as long as the packing does not cross the security
boundary.

Jim

---

From: Michael Richardson <[email-masked]>
Date: Fri, 28 Aug 2020 14:20:38 -0400

I feel that the WG should adopt the document already.

    > might otherwise be encoded as a prefix and the prefix might not be needed

Once the dictionary is larger than 512, I guess 131072 is the next size.
That uses four-byte references, and so the dictionary ought to provide at
least four-byte substitutions, right?
Otherwise, we'd be expanding rather then compressing.
It seems that a (C,Python,etc.) array is probably always appropriate as the internal
datastructure to perform lookups into the dictionary. It shouldn't require a
sparse array, ever, should it?

    > a problem for packed CBOR as long as the packing does not cross the security

Agreed.

--
Michael Richardson <[email-masked]>, Sandelman Software Works
 -= IPv6 IoT consulting =-

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 28 Aug 2020 20:40:03 +0200

OK, I think we need to answer a few questions first.

Is there only ever one dictionary that is being referenced?
Or can you reference multiple?

(An alternative to referencing multiple is creating a way to merge dictionaries, however that might also create combinatorial explosion.)

How are shared items/prefixes from the packed data items merged with the ones from the dictionary/ies to the number space actually used for referencing?

How are dictionaries identified (URI, hint pulling from context, digest, any combination of that)?

I have a design that is based on specific answers for all these questions, but I’d like to hear what others think before pushing that.

Grüße, Carsten

---

From: Jim Schaad <[email-masked]>
Date: Fri, 28 Aug 2020 12:00:15 -0700

-----Original Message-----
From: Michael Richardson <[email-masked]> 
Sent: Friday, August 28, 2020 11:21 AM
To: Jim Schaad <[email-masked]>; [email-masked];
[email-masked]
Subject: Re: [Cbor] Packed CBOR and dictionaries

[JLS] The WG was promised an updated draft that dealt with a couple of
issues before the adoption call was made.

Once the dictionary is larger than 512, I guess 131072 is the next size.
That uses four-byte references, and so the dictionary ought to provide at
least four-byte substitutions, right?
Otherwise, we'd be expanding rather then compressing.
It seems that a (C,Python,etc.) array is probably always appropriate as the
internal datastructure to perform lookups into the dictionary. It shouldn't
require a sparse array, ever, should it?

[JLS] That raises a different question.  At one point when I was emailing
Klaus about the fact that dictionaries in CoRAL are only defined to use
positive integers, there was some discussion that the negative values would
be for a more application specific version of a dictionary.   That would
make it 256 and 65,XXX.

It might be interesting to have "sparse" dictionaries.  Consider that you
might want all of the URLs without a fragment to occur at a smaller section
that the same set of all URLs with fragments.  This means that you can get
smaller compressions for CoRAL vocabulary that does not include all of the
possible values using just the base URL.

Jim

Agreed.

--
Michael Richardson <[email-masked]>, Sandelman Software Works  -=
IPv6 IoT consulting =-

---

From: Jim Schaad <[email-masked]>
Date: Fri, 28 Aug 2020 12:20:50 -0700

-----Original Message-----
From: Carsten Bormann <[email-masked]> 
Sent: Friday, August 28, 2020 11:40 AM
To: Michael Richardson <[email-masked]>
Cc: Jim Schaad <[email-masked]>; [email-masked]; [email-masked]
Subject: Re: [Cbor] Packed CBOR and dictionaries

Is there only ever one dictionary that is being referenced?
Or can you reference multiple?
[JLS] I believe that the correct answer is either one or two.  The ability to reference more than two seems to be more problematic than it is worthwhile.  Allowing for the ability to reference two allows for the option of using "the" global CoRAL dictionary plus a more application specific dictionary containing lots of problem details information.  Two also allows for easy identification as you can use negative vs non-negative as the differentiation between them. 

[JLS] I have a (currently) slight preference for allowing two, but it is definitely not a hill I would die on.

How are shared items/prefixes from the packed data items merged with the ones from the dictionary/ies to the number space actually used for referencing?
[JLS] I was not planning on packing dictionaries.  Hmmmmmmm  Seems slightly problematic as items are added to the dictionary.

How are dictionaries identified (URI, hint pulling from context, digest, any combination of that)?
[JLS]  For cryptographic purposes it needs to be a digest.  That does cause problems with versioning however. One of the interesting question is does an application need to be able to pull down a new dictionary or does it only deal with dictionaries that it is pre-loaded with.   Not doing so means that dictionary version negotiation is needed (see previous mails on dictionaries in CoRAL -- https://mailarchive.ietf.org/arch/msg/t2trg/oVWf3x2ighHiU7b7K-xJte7jC_c/ is an example).  Doing so means that you might get surprises about not being able to get the dictionary that you need.  Naming for use and naming for negotiation might be different identifiers. 

[JLS] Sounds good 
Jim

Grüße, Carsten

---

From: Michael Richardson <[email-masked]>
Date: Fri, 28 Aug 2020 17:56:15 -0400

> Or can you reference multiple?

I've read the thread and I think that there are three places to look.
Please correct me I'm wrong.

1) included in the packed CBOR.
2) included in specifically referenced dictionary (yes, by hash)
3) included in an application specific dictionary defined at the RFC-level.
   (what Klaus was doing with CoRAL, I think)

I had previously thought that (3) was just a rather static, compiled-in
version of (2), and only one or the other would be invoked.

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 29 Aug 2020 00:08:06 +0200

> 1) included in the packed CBOR.

Yes, but I’m not sure that this is a “dictionary” in the sense of being separate from the prefix and shared item tables.  Is that what you mean?

> 2) included in specifically referenced dictionary (yes, by hash)

A hash is not really a reference.  It is an identifier that can be used to check that you have referenced the right thing, so you can sign the whole item.  Like in RFC 6920, that identifier could be augmented with a reference.

A hash also is expensive, on the order of several dozen bytes, so see below.

>   (what Klaus was doing with CoRAL, I think)

I would generalize this a bit.  There may be some context that explains where to get the dictionary for.  To be able to sign such a packed item, there would need to be an immutable relationship between a context hint in the packed item and a dictionary (possibly identified by the hash of that).  An IANA registry can be used to maintain such a relationship.

> version of (2), and only one or the other would be invoked.

I think we need to enable these dictionaries to evolve, so static, compiled-in may be true, but new versions of formats that employ packed items should be able to make use of new static, compiled-in dictionaries.  (The dictionary defined in RFC 3485 was never updated, but that is probably more about the deployment of SigComp.)

Grüße, Carsten