RFC 8785: JSON Canonicalisation Scheme

[achamayou]

There is now an RFC describing a canonicalised variant of JSON, of particular interest to users who want to sign and verify JSON-serialised payloads. It seems to me that many aspects of the specification are a matter of configuring/calling nlohmann::json, but a few require slightly more adjustment (ordering in particular).

So I have a couple of questions:

1. Is anyone looking at this already?
2. Is there appetite for this to be a feature in the library itself, as opposed to a wrapper?

Any other thoughts on the topic are also welcome :)

[nlohmann]

I was not yet aware of that RFC. In general, we have no proper way to configure the serialization function dump - there are already a lot of issues on configuring more aspects, but adding yet another bool to dump's interface would not be a good idea.

Independent of how to solve this issue (be it with a configuration struct or any other idea), I think supporting RFC 8785 could be a good addition to this library. As first step, it would be good to know which requirements need to be met, and where the library's default behavior deviates.

@achamayou Are you interested in working on this issue?

[achamayou]

@nlohmann yes, I am. I agree that it does makes sense to start from the spec and compare with the library's defaults and/or range of configurable behaviour, I'd be happy to do that. Is appending to this discussion the best way to do that?

[nlohmann]

I think the easiest way could be to start a branch/PR with the spec as Markdown file.

Maybe, also an implementation as a non-member function, like

// include/nlohmann/detail/rfc8785.hpp
namespace nlohmann
{
namespace detail
{

template<BasicJsonType>
std::string rfc8785(const BasicJsonType& j)
{
    // there you go
}

}
}

could be started. I think you won't need access to private members - maybe later to improve performance. This function can then be checked against the examples from the spec. Once we understood what aspects differ from the library's behavior, we need to find a way to just configure this in a future dump function.

[achamayou]

@nlohmann thank you for the suggestions, I will get started.

[krahenbuhl]

this would be a super nice feature, did you or anyone have a chance to start on this @achamayou or is it on the roadmap @nlohmann ?

[nlohmann]

I am happy to see PRs, but I am not going to implement it myself.

[achamayou]

@krahenbuhl @nlohmann sorry, I haven't, we ended up using a different format than JSON and I've not found enough spare time.

The main difficulty as I remember it when looking at it was the sorting of the keys, which need to be treated as arrays of UTF-16 code units (https://datatracker.ietf.org/doc/html/rfc8785#section-3.2.3), and because the library uses UTF-8 internally, this would require quite a slow conversion step.

The other item was the floating point serialization to string (https://datatracker.ietf.org/doc/html/rfc8785#section-3.2.2.3), which seemed to differ from what's already in the library, and would be a relatively substantial addition of code, judging from the reference implementations.

[krahenbuhl]

Thanks for pointing out the major potential items @achamayou

Small note: for sorting the keys the spec has the following note which makes me think we wouldn't have to convert to UTF-16 in the context of the nlohmann-json library and we could sort the strings as UTF-8 directly (nlohmann-json already assumes property names in UTF-8 from what I understand).

Note: For the purpose of obtaining a deterministic property order,
sorting of data encoded in UTF-8 or UTF-32 would also work, but the
outcome for JSON data like above would differ and thus be
incompatible with this specification. However, in practice, property
names are rarely defined outside of 7-bit ASCII, making it possible
to sort string data in UTF-8 or UTF-32 format without conversion to
UTF-16 and still be compatible with JCS. Whether or not this is a
viable option depends on the environment JCS is used in.

[achamayou]

@krahenbuhl unless I'm missing something, all this is saying is "ASCII is a common subset of UTF-8 and 16, and a lot of values are ASCII", so it is true that in many cases you can just sort UTF-8 sequences and get the correct result, but this is not a general implementation for the RFC.

I suppose you could do a sort() -> (sorted_sequence, contains_non_ascii), and cascade to the full implementation if contains_non_ascii.

[krahenbuhl]

You are right with respect to the specification.

However from what I understand from https://json.nlohmann.me/home/faq/ it seems that this nlohmann/json only correctly parse UTF-8 encoded files anyway. Do I interpret that right?

Only UTF-8 encoded input is supported which is the default encoding for JSON according to [RFC 8259](https://tools.ietf.org/html/rfc8259.html#section-8.1). Specifically:

[nlohmann]

It can parse UTF-16 and UTF-32, too, but all strings are encoded to UTF-8 internally.

[krahenbuhl]

I am taking a closer look. I don't think it'd be too hard to implement, however, one potentially blocking issue I can foresee is that we would need to bring in the code for IEEE double -> string conversion,

A reference implementation could be extracted from: https://github.com/ulfjack/ryu/tree/master/ryu
There is an alternate code in google v8 that could be extracted.

Licensing for RYU is dual Boost/Apache2, V8 - BSD. The produced section of code would need to retain the original licensing of the code we'd choose to use.

Before getting into it, I would like to have your opinion if merging a PR with such a thing would be something you'd be even willing to consider @nlohmann ?

[nlohmann]

What is the issue with the existing double-to-string conversion? From the copyright:

The class contains a slightly modified version of the Grisu2 algorithm from Florian Loitsch which is licensed under the MIT License (see above). Copyright © 2009 Florian Loitsch

[krahenbuhl]

So I did a quick experiment, using the table from https://datatracker.ietf.org/doc/html/rfc8785#appendix-B

Trying to round trip the "JSON Representation" values of the table with nlohmann json.
In the print out below,val_expected_str should be the same as val_nolhmanjson, which it isn't for some cases

My conclusion is that while Grisu2 is nice, it unfortunatly doesn't implement the standard formatting of double required by RFC8785.

{
  "data": [
    {
      "val_comment    ": "Zero",
      "val_expected_str": "0",
      "val_hexadecimal ": "0",
      "val_nolhmanjson ": 0
    },
    {
      "val_comment    ": "Minus zero",
      "val_expected_str": "0",
      "val_hexadecimal ": "8000000000000000",
      "val_nolhmanjson ": 0
    },
    {
      "val_comment    ": "Min pos number",
      "val_expected_str": "5e-324",
      "val_hexadecimal ": "1",
      "val_nolhmanjson ": 5e-324
    },
    {
      "val_comment    ": "Min neg number",
      "val_expected_str": "-5e-324",
      "val_hexadecimal ": "8000000000000001",
      "val_nolhmanjson ": -5e-324
    },
    {
      "val_comment    ": "Max pos number",
      "val_expected_str": "1.7976931348623157e+308",
      "val_hexadecimal ": "7fefffffffffffff",
      "val_nolhmanjson ": 1.7976931348623157e+308
    },
    {
      "val_comment    ": "Max neg number",
      "val_expected_str": "-1.7976931348623157e+308",
      "val_hexadecimal ": "ffefffffffffffff",
      "val_nolhmanjson ": -1.7976931348623157e+308
    },
    {
      "val_comment    ": "Max pos int    (1)",
      "val_expected_str": "9007199254740992",
      "val_hexadecimal ": "4340000000000000",
      "val_nolhmanjson ": 9007199254740992
    },
    {
      "val_comment    ": "Max neg int    (1)",
      "val_expected_str": "-9007199254740992",
      "val_hexadecimal ": "c340000000000000",
      "val_nolhmanjson ": -9007199254740992
    },
    {
      "val_comment    ": "~2**68         (2)",
      "val_expected_str": "295147905179352830000",
      "val_hexadecimal ": "4430000000000000",
      "val_nolhmanjson ": 2.9514790517935283e+20
    },
    {
      "val_comment    ": "",
      "val_expected_str": "9.999999999999997e+22",
      "val_hexadecimal ": "44b52d02c7e14af5",
      "val_nolhmanjson ": 9.999999999999997e+22
    },
    {
      "val_comment    ": "",
      "val_expected_str": "1e+23",
      "val_hexadecimal ": "44b52d02c7e14af6",
      "val_nolhmanjson ": 9.999999999999999e+22
    },
    {
      "val_comment    ": "",
      "val_expected_str": "1.0000000000000001e+23",
      "val_hexadecimal ": "44b52d02c7e14af7",
      "val_nolhmanjson ": 1.0000000000000001e+23
    },
    {
      "val_comment    ": "",
      "val_expected_str": "999999999999999700000",
      "val_hexadecimal ": "444b1ae4d6e2ef4e",
      "val_nolhmanjson ": 9.999999999999997e+20
    },
    {
      "val_comment    ": "",
      "val_expected_str": "999999999999999900000",
      "val_hexadecimal ": "444b1ae4d6e2ef4f",
      "val_nolhmanjson ": 9.999999999999999e+20
    },
    {
      "val_comment    ": "",
      "val_expected_str": "1e+21",
      "val_hexadecimal ": "444b1ae4d6e2ef50",
      "val_nolhmanjson ": 1e+21
    },
    {
      "val_comment    ": "",
      "val_expected_str": "9.999999999999997e-7",
      "val_hexadecimal ": "3eb0c6f7a0b5ed8c",
      "val_nolhmanjson ": 9.999999999999997e-07
    },
    {
      "val_comment    ": "",
      "val_expected_str": "0.000001",
      "val_hexadecimal ": "3eb0c6f7a0b5ed8d",
      "val_nolhmanjson ": 1e-06
    },
    {
      "val_comment    ": "",
      "val_expected_str": "333333333.3333332",
      "val_hexadecimal ": "41b3de4355555553",
      "val_nolhmanjson ": 333333333.3333332
    },
    {
      "val_comment    ": "",
      "val_expected_str": "333333333.33333325",
      "val_hexadecimal ": "41b3de4355555554",
      "val_nolhmanjson ": 333333333.33333325
    },
    {
      "val_comment    ": "",
      "val_expected_str": "333333333.3333333",
      "val_hexadecimal ": "41b3de4355555555",
      "val_nolhmanjson ": 333333333.3333333
    },
    {
      "val_comment    ": "",
      "val_expected_str": "333333333.3333334",
      "val_hexadecimal ": "41b3de4355555556",
      "val_nolhmanjson ": 333333333.3333334
    },
    {
      "val_comment    ": "",
      "val_expected_str": "333333333.33333343",
      "val_hexadecimal ": "41b3de4355555557",
      "val_nolhmanjson ": 333333333.33333343
    },
    {
      "val_comment    ": "",
      "val_expected_str": "-0.0000033333333333333333",
      "val_hexadecimal ": "becbf647612f3696",
      "val_nolhmanjson ": -3.3333333333333333e-06
    },
    {
      "val_comment    ": "Round to even  (4)",
      "val_expected_str": "1424953923781206.2",
      "val_hexadecimal ": "43143ff3c1cb0959",
      "val_nolhmanjson ": 1.4249539237812062e+15
    }
  ]
}

[nlohmann]

Can you share the code for this experiment? Right now I do not know how to reproduce it.

[krahenbuhl]

I made an error originally, there are less but still some discrepancies.
Here is the example code to reproduce the above: example.txt

[nlohmann]

Thanks a lot! I was not aware of these subtle differences. As JSON does not require the exact way numbers are serialized, it's understandable that it does not comply to the ECMAScript 2019 Language Specification.

[Ericson2314]

Any progress on this? I would be tempted to us this for Nix.

[berndoJ]

A recent use-case in one of my personal projects led me to look into adding RFC 8785 serialization support to this library. I think it would be a nice addition.

As already pointed out in this discussion, the two main difficulties of implementing RFC 8785 serialization for this library are the UTF-16 lexicographic key sorting and float-to-string conversion. To explore feasibility, I forked the library and put together a small proof-of-concept demonstrating one possible approach to both. You can find it here.

Let's break down the diffs of that PoC:

1. The sorting of the keys can be solved in a RFC-compliant way by on-the-fly conversion of UTF-8 to UTF-16. The implementation I propose (see rfc8785.hpp) does not blindly pre-convert to UTF-16 for sorting, instead it does the conversion during the sorting comparison if needed.
   This might be slower than the convert-first-then-sort solution for large non-ASCII key sets, but in the regular case this should not have too much overhead to normal sorting. That said, I may be over-complicating it here - feedback is welcome.

2. Float serialization according to the ECMAScript specs is less straight-forward. I first tried adapting the existing Grisu2 to_chars implementation, since most of the discrepancies found by @krahenbuhl are only matters of formatting. However, due to Grisu2 featuring different rounding behavior than the reference implementations, I don't think it will be easily possible to adapt it for RFC 8785. One example of the rounding-mismatch is the test-case for 1e+23.
   A possible solution, as already pointed out by @krahenbuhl, is to copy code from the RYU project - this is what I did for the PoC, although I modified the library a bit to output the correct formatting needed. Currently, I've just hacked in the float conversion directly into the serializer.

I checked the implementation against the test cases presented in the RFC and they seem to pass. You can find the test implemented here.

@nlohmann Given the additional code footprint required (primarily from adding another double-to-string implementation), would you still be interested in RFC 8785 support being added to the library? If so, I would be open to refining the implementation and creating a PR.