Deterministically generating a string from object

[kevinburke]

There are a few different contexts where it can be useful to generate a string representation of an object. The basic idea is that the same in-memory representation of the object should always yield the same string.

• You may want to use an object as a cache key.
• You may want to generate a MAC for an object, for example for use with JSON Web Tokens.
• You may want to store an object to disk or to the database in a way that it can be re-created in memory later.

For each of these use cases, a serialization function should generate the same string, or Buffer, for the same object. Generating different strings could lead you to incorrectly conclude the object changed.

The most common serialization technique - used for example by the node-jsonwebtoken is to call JSON.stringify. However, JSON.stringify does not guarantee deterministic output. The latest ECMA spec for JSON.stringify says that it should produce the same order as Object.keys, which should produce the same order as for ... in, which uses Object.[Enumerate] to enumerate object keys. [[Enumerate]] is a) deprecated, and b) the specification contains this note:

The mechanics and order of enumerating the properties is not specified but must conform to the rules specified below.

It would be nice if there were any function in the standard library that could convert an object to a string in a deterministic way. This could be solved in any of the following ways:

• Declaring that Node's JSON.stringify will always produce the same string output for the same object input. JSON.stringify is controlled by an ECMA specification, and V8, so I'm not sure that this is feasible.

• Adding a new API to either crypto or util that takes an Object as input and generates a string, guaranteeing it will generate the same output across Node versions.

• Documenting that some existing API, for example, Buffer.from(object), util.format(fmt, object) with some format string, will always generate the same string for the same object (and different strings for different objects).

I guess there is some question of what "the same" means - roughly, I would think two objects that are equal as defined by something like Lodash's isEqual function should generate the same string, and objects that fail an isEqual check should generate different strings.

[tarqd]

Does this meet your criteria: https://www.npmjs.com/package/fast-stable-stringify ?

[TimothyGu]

In the latest ECMAScript spec JSON.stringify (through SerializeJSONProperty) calls SerializeJSONObject, which then calls EnumerableOwnProperties, which then calls the [[OwnPropertyKeys]] internal method on an object. The order of the result returned from [[OwnPropertyKeys]] is well-defined.

2. ... own property key P of O that is an integer index, in ascending numeric index order ...
3. ... own property key P of O that is a String but is not an integer index, in ascending chronological order of property creation ...
4. ... own property key P of O that is a Symbol, in ascending chronological order of property creation ...

In other words, JSON.stringify is now, per spec, fully deterministic.

BTW you should always reference the latest draft for ECMAScript and other web standards, instead of an old snapshot of it (ES2015 in your case). In fact, the nondeterministic [[Enumerate]] no longer exists, and everything has been switched over to the deterministic [[OwnPropertyKeys]] in ES2016.

[kevinburke]

So then to use JSON.stringify to generate a deterministic string, I would need to ensure that the Object is created with the keys inserted in the same order every time...

[bnoordhuis]

Use https://github.com/substack/json-stable-stringify, it sorts keys before stringifying the object.

I don't think this is a feature that belongs in core. Solutions exist and since there are many ways to skin this cat, you'll never be able to please everyone. It's better left to user-land modules.

[bnoordhuis]

Since no collaborators spoke out in favor of this feature, I'll go ahead and close this out.

[cyberphone]

This is another deterministic solution:
https://tools.ietf.org/html/draft-rundgren-json-canonicalization-scheme-05

[BridgeAR]

Node.js actually already includes such feature: util.inspect(obj, { sort: true }). That is however only deterministic in case the same Node.js version is used. Otherwise the output might deviate (even for different minor version changes, even if unlikely).

And if you want to use a determinstic JSON.stringify I recommend to use https://github.com/BridgeAR/safe-stable-stringify/. It's the fastest implementation I know of.