search

ipld / js-ipld-dag-cbor

JavaScript implementation of the IPLD dag-cbor format.
MIT License
53 stars 26 forks source link

Ensure that CBOR always produces the same objects (sort map keys) #19

Closed dignifiedquire closed 7 years ago

dignifiedquire commented 8 years ago

According to https://tools.ietf.org/html/rfc7049#section-3.9

The keys in every map must be sorted lowest value to highest. Sorting is performed on the bytes of the representation of the key data items without paying attention to the 3/5 bit splitting for major types. (Note that this rule allows maps that have keys of different types, even though that is probably a bad practice that could lead to errors in some canonicalization implementations.) The sorting rules are:

  *  If two keys have different lengths, the shorter one sorts
     earlier;

  *  If two keys have the same length, the one with the lower value
     in (byte-wise) lexical order sorts earlier.

all keys in maps need to be sorted. Looking at https://github.com/hildjj/node-cbor/blob/master/src/encoder.coffee#L238-L260 it does not look like this is currently happening.

victorb commented 8 years ago

Not sure if I understand this correctly, but objects (maps) in JS are not sorted. You cannot guarantee that the order will stay the same in JS-land

dignifiedquire commented 8 years ago

They need to be sorted manually when generating the raw cbor object.

hildjj commented 7 years ago

This is a feature request for supporting canonical output as an option, not a bug. I'm happy to add that feature request to the backlog.

daviddias commented 7 years ago

We need to prioritise this, @hildjj has a point, but we need CBOR to be canonical so that every objects generates the same hash, across language implementations.

@hildjj do you have a ETA for this feature? Need any help getting it done?

hildjj commented 7 years ago

I may have some time to work on this in the next couple of days. I would take a PR, but it will need to be off by default with an option to enable, have full support for canonicalization, and a good set of tests.

hildjj commented 7 years ago

I just sent myself a PR: https://github.com/hildjj/node-cbor/pull/36

Let me sit with this for a day or two, so I can see if there's a better way to solve canonicalizing floats. What I have is a massive hack that I barely understand.

daviddias commented 7 years ago

closing this one as it is solved now. Thank you @hildjj :D