Re: [Cbor] Proposal for Deterministic CBOR (dCBOR) discussion at May 17th meeting

[Carsten Bormann <[e-mail]>]

Hi Christopher,

Thank you for this proposal.

I will be on vacation on the 17th (from this Friday), so I’ll send some comments ahead on the list.

> ## Numerical Reduction
> 
> Proposal: All numbers MUST be reduced to the smallest possible representation. Failure to do so is a well-formness error.

(I don’t think we want to change the term “well-formedness”.  I’d say this is a validity error.)

I went ahead and implemented what I think this is in the cbor-dcbor gem.

  gem install cbor-dcbor

and go play.

Here are a few examples (*):

$ irb -rcbor-dcbor

>> 0.to_dcbor.hexs
=> "00"
>> 1.to_dcbor.hexs
=> "01"
>> 1.0.to_dcbor.hexs
=> "01"
>> 1.1.to_dcbor.hexs
=> "fb 3f f1 99 99 99 99 99 9a"
>> 1.5.to_dcbor.hexs
=> "f9 3e 00"

So we see the usual problems that decimal fractions only hit the short binary numbers by accident.  (Asking the application to find the closest number that is encodable as a float16, as in 
>> 1.099609375.to_dcbor.hexs
=> "f9 3c 66"
would probably require the application to care about the encoding length plus have a good understand what precision is actually desired.)

>> (2**31).to_dcbor.hexs
=> "1a 80 00 00 00"
>> (2**32-1).to_dcbor.hexs
=> "1a ff ff ff ff"
>> (2**32).to_dcbor.hexs
=> "c2 45 01 00 00 00 00"

shows the transition from 1+4-byte ints (major type 0) to 1+1+4-byte bignums (tag 2, major type 2 inside).

>> (2**48-1).to_dcbor.hexs
=> "c2 46 ff ff ff ff ff ff"
>> (2**48).to_dcbor.hexs
=> "1b 00 01 00 00 00 00 00 00"

shows the transition back from 1+1+6 bignums to 1+8 ints.

Now there is an interesting interaction with floating point numbers here:

>> (2**31).to_f.to_dcbor.hexs
=> "1a 80 00 00 00"
>> (2**31-1).to_f.to_dcbor.hexs
=> "1a 7f ff ff ff"
>> (2**32-1).to_f.to_dcbor.hexs
=> "1a ff ff ff ff"
>> (2**32).to_f.to_dcbor.hexs
=> "fa 4f 80 00 00”
>> (2**33-1).to_f.to_dcbor.hexs
=> "c2 45 01 ff ff ff ff”
>> (2**33).to_f.to_dcbor.hexs
=> "fa 50 00 00 00"
>> (2**40-1).to_f.to_dcbor.hexs
=> "c2 45 ff ff ff ff ff”
>> (2**40).to_f.to_dcbor.hexs
=> "fa 53 80 00 00"
>> (2**48-1).to_f.to_dcbor.hexs
=> "c2 46 ff ff ff ff ff ff"
>> (2**48).to_f.to_dcbor.hexs
=> "fa 57 80 00 00”
>> (2**48+1).to_f.to_dcbor.hexs
=> "1b 00 01 00 00 00 00 00 01"
>> (2**48+2**25).to_f.to_dcbor.hexs
=> "fa 57 80 00 01"

I think this needs pretty strong test vectors, but was trivial to implement.

> * This includes the reference implementation at https://cbor.me 

(Another flag for this can easily be added.)

> * Some integer values (such as 1099511627775 [0xffffffffff]) can actually be larger than BIGNUM equivalents!

Which the above PoC code correctly handles.

> Alternative: The alternative would be to mandate that floats remain unchanged, which trends away from the suggestions in §4.2 of RFC 8949 for moving data to the shortest encoding possible and has the possibility of damaging determinism, but which matches some current implementations:
>    * Floats MUST be maintained as Floats, but otherwise all numbers MUST be reduced to the smallest possible representation. Failure to do so is a well-formness error.

This rule again creates tag2/tag3 numbers for unsigned values of 2**32 to 2**48-1.

> ## Adding dCBOR Support to Flagship Implementations and Tools
> 
> Proposal: Add a "deterministic" flag to existing implementations and tools such as https://cbor.me and QCBOR.

(The code behind cbor.me already has a “deterministic” flag which should be easy to export to the GUI.)

> * Requires work to implement, test, document, and maintain

I spent some 50 minutes on this so far (including this mail) :-)

> ## Bringing the dCBOR specification under purview of the CBOR Working Group and putting it on a track to RFC status.
> […]
> 
> * Would require active participation from the CBOR WG.

Indeed, we’d need to find out who else is interested in such a set of additional rules.

Note that there is a whole universe of potential additional rules in the tags, e.g. should 0("2013-03-21T20:04:00.000Z”) be converted to 0("2013-03-21T20:04:00Z”)?  Maybe even 0("2013-03-21T20:04Z”)?
What about float vs. int for tag 1?

Grüße, Carsten


(*)  Add this convenience function:

class String
  def hexs
    bytes.map{|x| "%02x" % x}.join(" ")
  end
end

to your .irbrc to play these examples.