Map serialization stability and interoperability

[roman-khimov]

Background
I think it's important for us to have 1:1 relation between any stack item and its binary serialized representation. Contracts do routinely serialize and save their data into the storage and then get this data back from it. While this data resides in storage in serialized form we may use it for projects like NeoResearch/neo-storage-audit or to compute state hash (as in #1383).

Strict stable format is also important for alternative node implementations because to ensure correctness and proper interoperability they may compare their storage with C# node (either using storage audit data or by computing state hash and comparing it then). Also related: #1027.

Problem description
The problem is that Map stack item can be correctly serialized in various ways depending on its element order. Deserialization from this various binary representations would yield the same result, but binary strings would still be different.

Map serialization was initially added in #215 and was done as a simple loop over Dictionary-based dictionary, and even though later (#342) it was changed to make a reverse loop it still is using standard Dictionary enumerator, which has the following note in the documentation:

For purposes of enumeration, each item in the dictionary is treated as a KeyValuePair<TKey,TValue> structure representing a value and its key. The order in which the items are returned is undefined.

So strictly speaking current C# code may serialize Map in any order giving different binary representations. Luckily, it doesn't do so (or otherwise neo-storage-audit wouldn't be possible), but still the resulting binary depends on some .NET library implementation details and even in .NET these details may change with future versions of the platform.

Unfortunately, things are way worse for non-.NET node implementations, there is no way to reliably reproduce the same element order which makes it impossible to reproduce the same binary for Map stack item. And it's especially dangerous for efforts like #1383, where different nodes are supposed to compute the same storage hash.

Do you have any solution you want to propose?
I think we should define some order relationship between items and make serialization sort them before outputting the binary.

Neo Version

• Neo 2
• Neo 3

It's probably too late to fix this for Neo 2, but Neo 3 can definitely solve this problem.

Where in the software does this update applies to?

• Storage
• Smart contracts
• VM

[erikzhang]

https://github.com/neo-project/neo-vm/blob/288caa6850d914b520cb9c310738d2c9873145d8/src/neo-vm/Types/Map.cs#L13

Map is using the OrderedDictionary.

[roman-khimov]

Wow, somehow I missed neo-project/neo-vm#259 and actually had a very old copy of neo-vm tree locally which was still using Dictionary. OK, catching up with these changes too, thanks. Sorry for the noise.