[Cbor] Re: Determinism of ordereded maps / arbitrary tags (Was: Two dup detection questions)

[Laurence Lundblade <[e-mail]>]

It was good to get this out on the table and clear. I plan to add this to the serialization document:

In the basic generic data model, maps are unordered (see RFC 8949, Section 5.6). Applications MUST NOT rely on any particular key ordering, even if the data was produced using deterministic serialization. A CBOR library is not required to preserve the order of keys when decoding a map, and the underlying programming language may not preserve map order either— for example, Go provides no ordering guarantees for maps. The sole purpose of map sorting in deterministic serialization is to ensure reproducibility of the encoded byte stream, not to provide any semantic ordering of map entries. If an application requires a map to be ordered, it is responsible for applying its own sorting.

LL



> On Dec 3, 2025, at 1:21 PM, Vadim Goncharov <[e-mail]> wrote:
> 
> On Tue, 2 Dec 2025 11:49:56 -0800
> Laurence Lundblade <[e-mail]> wrote:
> 
>> Q: Why does dup detection operate on data mode values (and sorting doesn’t)?
>> 
>> I think the answer is that the application makes use of the map keys in a
>> critical way — to distinguish data items like a person’s last name from
>> their shoe size. The application probably doesn’t have access to the
>> serialized form of the map key. It doesn’t want access to it either — the
>> point of CBOR is to serialize/deserialize data so applications don’t have to
>> worry about it.
>> 
>> This contrasts to map sorting where the important thing is that they are in
>> the same order, not so much what that order actually is.
> 
> Well, strictly speaking, application may want it's own sorting order, e.g. due
> to collation selected, so it's too, not only dup detection. It is just hard to
> imagine application directly depending on map sort order in *serialized* form,
> for it to be important, as maps are declared as "unordered" (some
> constrained/streaming impls which do not have resources for sorting in
> memory?).
> 
> However, if/when we will be discussing extensions like ordered maps (or more
> generally, tables), then questions of collation and sort order become
> meaningful to (deterministic) serialization: when contents of such data
> structure will be in tag instead of bstr, determinism (or not) of this inner
> part "infects" evaluation of whether "outer" part is deterministic ot not.
> I.e. this will be significant to GOAL of that deterministic encoding, for what
> purpose it is deterministic - compare, hashing... - because underlying array
> may well have deterministic encoding by more general/relaxed rules of outer
> part.
> 
> This kinda parallels the NaN tag bstr situation, but there wrapping to bstr
> was simple; and for determinism rules of arbitrary tags I don't know.
> 
> -- 
> WBR, @nuclight
> 
> _______________________________________________
> CBOR mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]