Subject: Re: [Cbor] Canonical CBOR

From: Burt Harris <[email-masked]>
Date: Wed, 6 Jun 2018 02:26:22 +0000

Other than one of two crypto-related protocols Carsten mentioned, I'm unaware of any protocol requiring canonical CBOR.   While don't disagree that examining existing CBOR based designs is appropriate, I think they are few enough to be insufficient today, and crypto is itself a special case, one of the few that seem like the _might_ benefit from some standard form for functional reasons     But where is that true?   

Looking outside the CBOR scope, consider Unicode.   There are multiple ways to represent letters with accents.   Being a native English speaker, it has only been a curiosity for me, but let's look how Unicode deals with the matter, as described in [TR 15](http://www.unicode.org/reports/tr15/.)   The TR describes not one, but several "Unicode normalization forms." 

This permits applications and protocols above the presentation level to choose to implement normalization convention using standardized terminology, without dictating a single standard.   RFC-7049 canonicalization can remain a thing long after we publish CBOR bis, CBOR tre, etc.   The original RFC is forever, and references to it don't change because we might rethink something, and implementations are free to implement an normalization option-selection mechanism if its important to the implementor.

But this is entirely different from UTF-8's saying that overlong encodings are forbidden (which is similar to RFC-7049's rule for canonicalizing integers.) Both are not opinionated, they eliminate only something that is less efficient.   Similarly, all the UTF-* encodings forbid unpaired surrogate code points, which used to be perfectly legal in UCS-2 (UTF-16's predecessor).   So is "compatability" a strong argument for blocking progress?   I don't think so.    Window-32 was widely deployed, supported UCS-2 rather than UTF-16, and Microsoft adapted.  (I should know, I worked there.)  

But what is really interesting is section 11.1 of Unicode TR 15.   It says:

> 11.1 Stability of Normalized Forms
> 
> For all versions, even prior to Unicode 4.1, the following policy is followed:
> A normalized string is guaranteed to be stable; that is, once normalized, a string is normalized 
> according to all future versions of Unicode.
> 
> More precisely, if a string has been normalized according to a particular version 
> of Unicode and contains only characters allocated in that version, it will qualify as 
> normalized according to any future version of Unicode.

The policy is reasonable, but there is more than one way to achieve it.  Applying this to CBOR for example, Since RFC-7049 specified a somewhat surprising map serialization order, one way would be to stay stuck on that order, but no I don't think that's a good solution at all.   To see the other approach I suggest we need substitute "map" (or better yet "object")  in each place where the above policy says "string".   So if the default rule is "preserve the serialized order of maps" rather than "sort maps to normalize them", any existing serialized map stays normal in whatever normalization was applied at the time the map was created.    We don't have to preserve the old 
normalization if the map is modified, that's a higher-level concern, at the application (semantic) protocol layer rather than at the presentation (syntax) layer.    Without layered protocols, we get stuck in a quagmire of 
unseparated concerns.   

It seems quite clear to me that CBOR the spec is a presentation layer protocol, just like character encodings and graphics formats.  A CBOR implementation however may have a mixture of presentation layer and application layer concerns, but that does NOT mean that every implementation should behave the same when implementing application-level concern like canonicalization.   The fact that a particular implementation r CBOR-titled presentation layer RFC was opinionated about application-level concerns does not justify mixing of concerns, it illustrates why efforts should be made to separate them.

When people argue for canonicalization by saying that  that testing by binary comparison of serialization output is a reason for canonicalization another implementation are totally unconvincing to me.    There are alternatives to binary comparison on virtually every platform I've looked at recently, typically called deep comparison or deep-equal.   That solves the comparison problem at the application level rather than the serialization level.

JavaScript for example applies extreme simplicity for it's built-in comparison of maps (objects):

> Comparing x === y, where x and y are values, return true or false. Comparing 
> x === y, where x and y are objects, returns true if x and y refer to the same object. 
> Otherwise, returns false even if the objects appear identical.

Deep compare is simply a normal function that defines a different way of comparing objects.  By making this an application concern, rather than building it into the language, JavaScript allows other ways that might (for example) ignore Unicode canonicalization (expensive) or assume some specific canonicalized rule when comparing strings, or use case insensitive string comparisons.

There are two special case where JavaScript defines something other than the "leave it in the order you found it" rule:

	0. Sparse arrays.  Any object can be a sparse array in JavaScript.  The index values for sparse arrays are limited to non-negative integers, just like normal arrays.   So non-negative integers sort to the beginning in ascending order.   Negative integers are not allowed as sparse array indexes, so they are treated as strings.   If you think of object as a hash table, this does not make a lot of sense. 

	1.  Normal objects (strings as keys).   Generally kept in the order they were added.   Once, a long time ago there could be a glitch in order if you used the JavaScript delete as a command, but that's a legacy holdover now, all modern JavaScript fixes this.  

	2. Instances of the Symbol class.   The reason Symbol keys are sorted last is that they represent private information, information that should NOT be converted in serialization.   A serializer or reserialize should typically skip past all other symbol keys and wrap-up the job.   (Symbols didn't exist in earlier versions of JavaScript, so putting them last in key sort order makes sense.

So, if we can get over CBOR calling CBOR maps "maps", and deal with the reality that CBOR maps always have some order when serialized, it might make sense now why I think we should allow (not require) that maps carry an order, but say that applications SHOULD NOT compare values based on that key order.   By saying that the presentation layer SHOULD preserve key order, we enable using it as an optimization to handle special cases like sparse arrays.

Sorry if this contains typos or seems disorganized.    I'm very tired for unrelated reasons.

---

From: Burt Harris <[email-masked]>
Date: Wed, 6 Jun 2018 02:58:30 +0000

The other design example to consider as an anti-pattern is of course ASN-1.    Of all the different "encoding rules", about half are complications added by trying to force canonical into the rules and failing to separate concerns of encoding from canonicalization.    That turned into a mess, with a lack of interoperability in some if not many cases.   I gave up on ASN-1 due more than when I realized how much energy was being put into designing "encoding rules" based on guess and opinion rather than focus on clarity of one easily described and implemented encoding.    Enough said (I hope.)

-----Original Message-----
From: Burt Harris 
Sent: Tuesday, June 5, 2018 7:26 PM
To: [email-masked]
Cc: 'Carsten Bormann' <[email-masked]>
Subject: Re: [Cbor] Canonical CBOR

But what is really interesting is section 11.1 of Unicode TR 15.   It says:

> A normalized string is guaranteed to be stable; that is, once 
> normalized, a string is normalized according to all future versions of Unicode.
> 
> More precisely, if a string has been normalized according to a 
> particular version of Unicode and contains only characters allocated 
> in that version, it will qualify as normalized according to any future version of Unicode.

JavaScript for example applies extreme simplicity for it's built-in comparison of maps (objects):

> Comparing x === y, where x and y are values, return true or false. 
> Comparing x === y, where x and y are objects, returns true if x and y refer to the same object.