Approaches to hashing CUE values

[lorrrrrrrenzo]

Hello,

I am doing some work around lattice caching and record-keeping, and the ability to generate reproducible hash values for a given CUE value would go a long way towards easing both efforts. My initial research suggests the use of hashstructure, used by Terraform extensively, with cue.Value or ast.Expr objects as a good initial approach.

What are some considerations that I should keep in mind as I begin this investigation, especially concerning hash stability (acknowledging that CUE has not yet reached v1)? I also have hopes that such a function could be added to the CUE Go package in the future, but that's a future conversation.

Thanks!

[lorrrrrrrenzo]

I need to put this through more thorough testing, but the following code is an initial approach that appears to work well enough. At its core is a conversion of a cue.Value into an ast.Node through its Syntax() method, which is then passed into hashstructure.Hash().

package cue_hasher

import (
	"hash/fnv"
	"strconv"

	"cuelang.org/go/cue"
	"github.com/mitchellh/hashstructure/v2"
)

var cueSyntaxOptions = []cue.Option{
	cue.All(),
	cue.Concrete(false),
	cue.DisallowCycles(false),
	cue.Docs(true),
	cue.Hidden(true), // https://github.com/cue-lang/cue/issues/3771
	cue.Raw(),
}

var hashStructureOptions = &hashstructure.HashOptions{
	IgnoreZeroValue: false,
	Hasher:          fnv.New64a(), // not strictly needed -- default is fnv.New64()
}

func Hash(val cue.Value) (string, error) {
	return HashString(val)
}

func HashString(val cue.Value) (string, error) {
	valHash, err := HashUint(val)
	if err != nil {
		return "", err
	}
	return strconv.FormatUint(valHash, 16), nil
}

func HashUint(val cue.Value) (uint64, error) {
	syn := val.Syntax(cueSyntaxOptions...)

	valHash, err := hashstructure.Hash(syn, hashstructure.FormatV2, hashStructureOptions)
	if err != nil {
		return 0, err
	}
	return valHash, nil
}

[infogulch]

You may need to think about canonicalization. i.e. equivalent structures that happen to be ordered differently. This will affect the hash, but the object is the same, somewhat defeating the point of using hashes. I think there has been discussion in this repo about this property under the name topological sorting (?), but I'm not sure what the status is.

[lorrrrrrrenzo]

Thanks for the tip about topological sorting. I was able to find this discussion from a few years ago asking for something similar, and found the toposort package.

toposort and its in-project dependencies (most notably adt.*) are all in internal packages, suggesting that a short-term solution will require manipulating the AST in a ast.Node. In the long term I can see the case for adding a func TopoSort() Option for cue.Syntax(), though that is obviously up for discussion.

[myitcv]

Thanks for raising this for discussion, @lorrrrrrrenzo and apologies for the delay in replying here after my initial response on Slack.

One question that immediately comes to mind is, would you want your hash to be stable with respect to order of inputs?

i.e. that:

a: 5
b: 4

should has to the same value as:

b: 4
a: 5

If so, then I think you want to normalise the result via something like sorting of identifiers, rather than toposort.

Another question/thought: are the configurations you are talking about here concrete or incomplete? I'm assuming, given the discussion about cue.Value, that you are referring (exclusively) to the latter. That being the case, it feels like normalising a configuration by loading to a cue.Value, sorting the structure to normalise for order of inputs, "rendering" the result via cue.Value.Syntax with https://pkg.go.dev/cuelang.org/go/cue#InlineImports set, and then simply hashing the resulting bytes via https://pkg.go.dev/crypto/sha256 might well be sufficient.

cc @cuematthew for thoughts re toposort and sort fields.

[lorrrrrrrenzo]

Thanks for the response @myitcv.

My interest is stability with respect to the resolved value, both concrete and incomplete. In the example you provided, I would like for the hash result to be the same in both cases: the order should be immaterial. How they are split between files in a given module should also be immaterial (e.g. a module defined in both foo/a.cue and foo/b.cue).

I reached for cue.Value.Syntax since that was the most available and sensible in my opinion, but I'm not particularly attached to it and will take a recommended alternative.

When I looked at this weeks ago, effectively sorting the result of cue.Value.Syntax did not seem intuitive. If you or someone from your team can provide guidance there on the best way to approach that task, I can give it another shot.

It might be helpful to share that I have in mind how Dhall handles hashing and how it is used within that ecosystem. From their language tour:

These integrity checks are resilient to cosmetic changes in the imported expression, meaning that the hash of an expression does not change if you make behavior-preserving changes to that expression, such as 1) Adding/removing comments, 2) Refactoring the code

The hash is resilient to behavior-preserving changes because the integrity check is a “semantic” integrity check, meaning that it is a hash of a canonical encoding of the program’s syntax tree and not a hash of the program’s source code. Also, the program is interpreted before hashing so that the hash is insensitive to program indirection.

[cuematthew]

I think val.Syntax is the right way to go - I believe this is what CUE's own command line uses to convert CUE values back to an AST before final formatting and printing. As such, it does follow toposort and the various other flags available.

I think what you actually want is a full lexicographical sort. For that, you need the CUE_DEBUG=sortfields env var. This will completely disregard all ordering information from CUE sources, and instead will sort fields of every struct lexicographically. Toposort, which is the default currently, will indeed be influenced by the order of fields in your source CUE, and as such, the output (and hence hash) will change cosmetically if your CUE source undergoes changes which are semantic-preserving but reorder fields.