Re: [Cbor] [core] draft-ietf-cbor-7049bis

Hi,

(chair-hat on) I would really like to hear the opinion of the working group on this one.
Please make sure you read through the mail thread and express your thoughts.

Thanks,
Francesca

> -----Original Message-----
> From: core [mailto:core-bounces@ietf.org] On Behalf Of Carsten Bormann
> Sent: den 17 september 2017 20:08
> To: Jim Schaad <ietf@augustcellars.com>
> Cc: cbor@ietf.org; core@ietf.org WG <core@ietf.org>
> Subject: Re: [core] draft-ietf-cbor-7049bis - Change suggested
> Canonicalization
> 
> Hi Jim,
> 
> I do share your frustration a bit, because I do believe the canonical map key
> sorting order is one of the very few things we didn’t quite get right about RFC
> 7049.  The question about fixing this really is procedurally, can we fix it, and
> what is the impact on people who are now using the old order.
> 
> > I complained that this was not a good sorting order before RFC 7049 was
> published, so this is not a new issue.  I wish that I could find the mails from
> the time as my memory was that you said we could discuss it on the next
> version which is what I am trying to do.
> 
> I must admit I don’t remember that discussion (it would have been more
> than four years in the past) and my mail program apparently doesn’t either.
> 
> (My mail program does remember errata report 4409 from July 2015, where
> you did propose another sorting order.)
> 
> >> Why do you think the values need to be in there, too?
> >> Map keys must be different, so the value never can have an effect,
> >
> > That is from below - where you could have multiple duplicate keys.  It is
> very possible people will do this even if it is not a valid encoding.
> 
> The reason why 7049 does not outright make emitting duplicate keys a
> conformance issue is that, in a streaming implementation, it is hard to check
> for duplicate keys.  That argument does not apply to an implementation that
> has to sort map member keys to achieve a canonical encoding.  So, while
> creating canonical encoding, the implementation can also check for key
> duplication and raise an error if that happens.
> 
> >> Now, if it were mid-2013, I would just agree with you, change the
> >> draft, and ask the WG (at the time appsawg) whether there are any
> further comments.
> >
> > Given that you did not agree with me at the time when I raised this issue, I
> would disagree with this statement.
> 
> Well, I probably should have said “knowing what I know now” (i.e., the
> degree of POLS violation that the current rules pose) I would agree with you.
> (At the time, the definition we now have in RFC 7049 appeared to be
> expedient.)
> 
> >> Unfortunately, CBOR has been out there, we are on the way to an
> >> Internet STD, and the current canonicalization is what’s implemented
> >> (at least in a couple of places).  If we change this, we have to take
> >> canonicalization out from the STD and put it into a separate specification.
> >> We could decide to do this, but I’m not sure that this helps.  (We’ll
> >> also have the CER vs. DER situation again.)
> >
> > I do not believe that changing this would in any way stop the advancement
> to STD.
> 
> Now that (i.e., just going ahead and changing things here) is an interesting
> thought.
> 
> One problem with that is that in the IETF, the IESG is the gating function, and
> it is sufficient for a single member of the IESG to disagree with this thought to
> hold up the process.
> 
> > This section is completely non-normative there is not a single normative
> statement in the entire section. Nor is the set of rules complete given that
> there are two paragraphs at the end which have additional rules that "might"
> need to be added.  Making this one change would not alter the fact that it is
> non-normative and incomplete.
> 
> Filling in those blanks might be another argument for going ahead and
> writing a separate document about canonicalized CBOR instead.
> 
> > There is a possible multiple encoding issue that may come, but that is
> already implicit in the text of this section.  The current text reads "Those
> protocols are free to define what they mean by a canonical format and what
> encoders and decoders are expected to do." Which means that multiple
> encodings are already not only possible but probably.  I think that we can get
> this fixed now and go forward with an obsoleted suggested canonicalization
> and be fine.
> >
> > The suggested algorithm is far easier to understand, easier to get right and
> also has some advantages where one can do the canonicalization without
> having to do the encoding first.
> >
> > int CompareNodes(node1, node2)
> >   if node1.majorMode != node2.majorMode then return node1.majorMode
> - node2.majorMode;
> >   if node1.majorMode has a length field and node1.length != node2.length
> then return node1.length - node2.length;
> >   return compare node1 and node2 values - this is major mode dependent.
> >
> > With the current method, you need to do a lot more work to try and get
> things in the correct order if you have any mixing of major modes, which is
> now very common place despite the statement that this is probably a bad
> practice.
> 
> Indeed, this is one thing we have learned since 2013: There are quite good
> reasons for mixing major types in the keys of a single map.
> 
> > If you have to emit all of the keys, sort them and then remember the
> original order to emit the values, it is harder than concatenating the entire
> thing and then emitting the values after doing the sort.  You are going to
> need to keep some type of more complex structure - and thus more code- to
> do the emission in the generic case.  Yes for a small fixed set of keys this is
> not necessary but I do not believe that is where a good canonicalization
> routine is going to be needed.
> 
> Here is my implementation of a pre-canonicalizer for maps from the cbor-
> canonical gem (the type “Hash” in Ruby is an order-preserving map, so we
> can do all this entirely at the data model level):
> 
>       def cbor_pre_canonicalize
>         Hash[collect {|k, v|
>                       k = k.cbor_pre_canonicalize
>                       v = v.cbor_pre_canonicalize
>                       cc = k.to_cbor # already canonical
>                       [cc.size, cc, k, v]}.sort.collect{|s, cc, k, v| [k, v]}]
>       end
> 
> A sorting rule that is entirely based on (byte-wise) lexical ordering would
> enable pre-sorting on types — there often would be no need to generate the
> entire key encoding for sorting.  But then, you have to generate them
> anyway, so the additional overhead is mostly a matter of memory
> allocation/copying.
> 
> Here is an (untested) implementation of what I think you are proposing:
> 
>       def cbor_pre_canonicalize
>         Hash[collect {|k, v|
>                       k = k.cbor_pre_canonicalize
>                       v = v.cbor_pre_canonicalize
>                       cc = k.to_cbor # already canonical
>                       [cc, k, v]}.sort.collect{|cc, k, v| [k, v]}]
>       end
> 
> I.e., the size of the key encoding is removed from the list of things to sort for.
> 
> > I strongly urge that this change be done even if it might hurt backwards
> compatibility and the sooner we make the decision to do it the better as it
> reduces the number of people who will do it wrong.
> 
> Now whether we should do this or not is a good question for the CBOR WG
> to look at.
> 
> (I’ve added the WG back to the recipient list.)
> 
> Grüße, Carsten
> 
> 
> _______________________________________________
> core mailing list
> core@ietf.org
> https://www.ietf.org/mailman/listinfo/core

Re: [Cbor] [core] draft-ietf-cbor-7049bis - Change suggested Canonicalization