Re: [Cbor] Handling duplicate map keys

[Jeffrey Yasskin <[e-mail]>]

On Sat, Nov 23, 2019 at 10:00 AM Laurence Lundblade <[e-mail]>
wrote:

> Here’s a rough proposed text:
>
> The protocol designer should make a choice for maps as to whether
> duplicates are allowed or not, particularly as to whether duplicates would
> cause security or functionality problems.
>
> The protocol designer should only require duplicate detection when
> necessary as it can have the following implications:
>
>    - Some generic decoders do not support duplicate detection because the
>    underlying facilities in their programming environment to represent maps
>    can’t detect duplicates
>    - Some generic decoders do not support duplicate detection because it
>    requires more code and is not required
>
>
>    - It requires more resources to implement: 1) memory to store all the
>    keys in the map, 2) more code, 3) more CPU time, as much as O(n^2). This is
>    particularly an issue with big maps in constrained environments.
>
> It is suggested that protocol designers require duplicate detection only
> no the particular maps for which there is an issue.
>
> Decoders will typically fall into one of these categories:
>
>    - Full duplicate detection
>    - Pass all items up to caller, allowing the caller to implement
>    duplicate detection or not
>    - No duplicate detection
>
> A generic decoder should identify which it is. Some may support more than
> one, selectable by configuration.
>
>
I don't think generic decoders are relevant here. Protocol implementations
often accumulate their input into a data structure even if they use a
streaming decoder to read the input. Any such protocol can detect
duplicates (of the keys it uses at all) for at most the cost of an extra
bit per field.

Here’s why.
>
> I see no value in take first or take last over duplicate detection. In all
> three all, the keys encountered must be recorded and processed. If the map
> is large this will take a lot of memory. In all cases there is some extra
> code and CPU. CPU time is worse than O(n), perhaps O(n^2). It doesn’t
> matter if the use case is streaming or not. It is the memory, code and CPU
> time that matter.  (Take last can only be implemented by decoding the whole
> map, as it is only after decoding the whole map that it can know it has
> encountered the last; in a way you cannot do the last for a streaming
> decoder).
>
> This is a guess — I don’t think map libraries that don’t support duplicate
> detection commonly support  take first. I suspect some do take first, some
> do take last and some do take random. To me that makes any mention of take
> first or take last in the specification not very valuable especially as it
> doesn’t have much memory, CPU or code advantage over duplicate detection.
>

I think you make a good point that if a protocol is going to specify "take
first", it can probably specify "error on duplicate key" for the same cost.
That might imply some much simpler text:

"Protocols based on CBOR SHOULD fail with an error if a map contains a
> duplicate key, except that if the key isn't used at all, they MAY ignore it
> instead. Protocols that do not reject duplicate keys MUST (?) document why
> the cost of rejecting duplicates is too high and why accepting them will
> not lead to security vulnerabilities. An array might be a better choice for
> such protocols."


Do we have any concrete examples of protocols or formats built on CBOR that
don't store anything while parsing their input? One of those might provide
a good example of a protocol that shouldn't reject duplicates.

Jeffrey