Semantic integrity hash affected by field order

[joneshf]

It looks like something changed to the way hashes work for records and unions. In an older version, the order of fields in records/unions would not change the hash. That seems to be in line with the standard. In more recent versions, the order of fields affects the hash produced.

dhall-hash 1.8.2

[nix-shell:~]$ dhall --version
1.8.2

[nix-shell:~]$ echo '{foo = 1, bar = 2}' | dhall-hash
sha256:6364e21a806e13b82afaa6ea927ae23e15bb53da2573292f085911396877cf3f

[nix-shell:~]$ echo '{bar = 2, foo = 1}' | dhall-hash
sha256:6364e21a806e13b82afaa6ea927ae23e15bb53da2573292f085911396877cf3f

[nix-shell:~]$ echo '<foo : Natural | bar : Natural>' | dhall-hash
sha256:657b73e8d23f4386ba6895247a6dda9c762c4beb35e6e8a3b0108d6d3888b91c

[nix-shell:~]$ echo '<bar : Natural | foo : Natural>' | dhall-hash
sha256:657b73e8d23f4386ba6895247a6dda9c762c4beb35e6e8a3b0108d6d3888b91c

dhall hash 1.16.1

$ echo '{foo = 1, bar = 2}' | stack exec dhall -- hash
sha256:83f262b95390c2c55b381d753802019bb3188a25ac5fbe3c8b3c00c47afd9534
$ echo '{bar = 2, foo = 1}' | stack exec dhall -- hash
sha256:6364e21a806e13b82afaa6ea927ae23e15bb53da2573292f085911396877cf3f
$ echo '<foo : Natural | bar : Natural>' | stack exec dhall -- hash
sha256:d188708d41b0db2981e50442bdd19ace258830e9e13fd1a3b6ec94b2224d8578
$ echo '<bar : Natural | foo : Natural>' | stack exec dhall -- hash
sha256:657b73e8d23f4386ba6895247a6dda9c762c4beb35e6e8a3b0108d6d3888b91c

Is this change intended? If so, we should update the spec to make that clearer.

[joneshf]

Also, it looks like the latest commit affects the hash as well.

dhall hash f134bbc

$ echo '{foo = 1, bar = 2}' | stack exec dhall -- hash             
sha256:923cded34fc8766011ac80e878252773513c702e05f65a3788a45a2f2479f7ca
$ echo '{bar = 2, foo = 1}' | stack exec dhall -- hash             
sha256:4b9647629a4c7f2e4eaf8e4846965a0e89895fa598ed821441fd299c4596fc38
$ echo '<foo : Natural | bar : Natural>' | stack exec dhall -- hash
sha256:b6b7e2aa1f5de9cd72ead45da922f5250d979afddeb5d42a7561d28ea8872d0c
$ echo '<bar : Natural | foo : Natural>' | stack exec dhall -- hash
sha256:5870bc11c151c60f1db7b811938612341a4ca6cfe4f4d16b3147538a36f75806

More clearly, hashing {bar = 2, foo = 1}:

• In 1.8.2 - sha256:6364e21a806e13b82afaa6ea927ae23e15bb53da2573292f085911396877cf3f
• In 1.16.1 - sha256:6364e21a806e13b82afaa6ea927ae23e15bb53da2573292f085911396877cf3f
• In f134bbc - sha256:4b9647629a4c7f2e4eaf8e4846965a0e89895fa598ed821441fd299c4596fc38

Is that also intentional? It's fine if it is, as breaking changes are inevitable. But, it might not be intentional.

[Gabriella439]

@joneshf: The change in the integrity check between version 1.16.1 and f134bbc is definitely expected because 1.16.1 is using the old non-standard algorithm for hashing expressions (i.e. hash the pretty-printed expression) and the new hashing algorithm based on the standardized binary encoding was introduced after version 1.16.1 (Specifically in #519) and will be first available in version 1.17.

However, the sensitivity to field ordering is not expected and is a violation of the spec, as you noted. I'll fix that.

[Gabriella439]

Thinking about this more, what I plan to do is to have the specification only require that β-normalization sorts fields, since that would in turn guarantee that semantic integrity checks sort fields (since a semantic integrity check is done post-αβ-normalization).

The reason for doing things this way is that binary encoding could in principle be used for things other than semantic integrity checks (i.e. perhaps you want to serialize an expression that has not been normalized and you want to preserve identifier names and field order). By specifying that normalization is required as part of β-normalization but not required as part of binary serialization we can preserve the ability to opt out of normalization when encoding expressions for alternate use cases. This is the same reason that binary serialization is specified for let expressions and imports even though they will never appear in a fully resolved and normalized expression.

[Gabriella439]

Here's the corresponding change to the standard: dhall-lang/dhall-lang#223

[Gabriella439]

Here's the matching change to the Haskell implementation: #552

[joneshf]

Wooo! Thanks for the quick fixes!

[Gabriella439]

@joneshf: You're welcome! 🙂