In this Github issue about Ctx8 ergonomics it is proposed that we should have a built-in method to compute the hashes of Simplicity values. Currently, to do this you must manually destructure your object into basic Simplicity types and then invoke jets (one for each size of data) which update a sha256 engine. This is verbose, error-prone, and also invites high-level design mistakes regarding “what data gets hashed in what order” because it distracts the programmer with minutiae.
It would be much better if we could just write hash(value) regardless of the type of value.
But what exactly should this hash builtin do? (it is a builtin, not a function, because it must be polymorphic over its input type and SimplicityHL functions do not support this).
Well, we want this builtin to be a “secure hash function”. For our purposes, this means that no two distinct values are ever encoded as the same bits when feeding them into the hash engine. If we achieve this property, and we model SHA256 as a random oracle, then we automatically get all the security properties we might want: collision resistance, first and second preimage resistance, binding and hiding, etc. The question of “how do we encode data to be hashed” is a thorny one and not unique to Simplicity. The Rust Hash trait attempts to achieve this, for example. (Although Rust fails, even within the stdlib; it distinguishes &str strings from &[u8] bytestrings by suffixing a fix 0xff byte, meaning that a &str can be encoded the same way as a (&[u8], u8). If it’s okay that values of different types are encoded the same way, then why bother with the 0xff? Incoherent. So clearly this is not an easy property for even large software projects to properly define.)
An abvious way to implement hash is to just break apart the data into individual pieces and then hash that, like users are doing manually. Essentially “lower the value to its base Simplicity type, then encode that in the ‘compact encoding’ used by the Bit Machine”. Like with Rust’s Hash, this achieves our goal as long as we always use a fixed datatype (though often in surprising ways; the obvious way to encode a variable-length bytestring is to length-prefix it, but Simplicity instead breaks it into a series of optional power-of-two-length arrays).
But “collision resistant assuming a fixed type” is not sufficient. Bitcoin’s consensus code has multiple issues related to interpreting a hash of one object as a hash of a differently-typed object. CVE-2012-2459 (hashing a single SHA256 hash the same as a pair of SHA256 hashes) comes to mind, as does the issue solved by the Great Consensus Cleanup wherein a 64-byte transaction may be hashed the same as two transaction hashes. In both cases, nodes that are unaware of the bug may disagree on the contents of a given block, even if they agree on its hash. So clearly this is not an easy property for projects to achieve even when it’s critical to their security model.
However, we have the benefit of experience, and the knowledge that there is a standard way to prevent this class of bugs/attacks. We just need to domain-separate the hashes using BIP-0340 tagged hashes where the domain separation is per-type. Domain-separating by Simplicity type is easy: we already have a unique type identifier, the TMR, that we can just use as a tagged hash. Unfortunately, Simplicity does not distinguish between (u4, u4) and u8, for example, let alone types like Distance(u16) and Duration(u16). This is bad, and particularly bad because “structurally equal” types like these are the most likely to have values that might be confused for each other.
So we instead need to domain-separate by SimplicityHL type, and here’s where things get tricky. Currently SimplicityHL’s type system is really bad. It also supports only structural typing, so you can’t define newtypes which the compiler considers distinct, and it also conflates things like (u4, u4) and u8. It just adds a couple things iike lists and arrays to Simplicity’s bare-bones type system. So before we can domain-separate our hashes, we need a type identifier, and before we can define a type identifier, we need a coherent notion of what types are even distinct. The current “everything is the same if it’s shaped the same” situation is obviously untenable, but what will a better solution look like?
It’s easy enough to define a TMR-like hash for the built-in SimplicityHL types (which are essentially just the Simplicity types plus list and array) and further tweak it to distinguish built-in names like u16 from the (u8, u8)s that comprise them, and Distance(u16)/Duration(16). But what should we do with enums, enum variants, and other user-defined types? Clearly we do not want two types to get the the same hash if they come from different libraries, even if they have the same structure and even if they have the same name. But we also want the same type from the same library to always get the same hash. This requires we define “same type” and “same library” (or rather, “same module”) in a way where all users agree.
Again, Rust has little to offer us: its notion of the “same library” is actually that of “semver-compatible libraries” which are defined by the dtolnay/semver crate in weird and surprising ways. Cargo then lays on further rules for incompatibility based on the source of the crate (and registry sources have their own complex rules which don’t include any code signing or namespacing or anything), and allows these things to be overridden locally with [patch] and other methods. And then it takes this stew of ad-hoc rules and feeds them all into some hash that it gives to rustc which then separates the rlibs based on it. So we will need a different approach to modules.
Summing up: we need to define a coherent notion of type identity, which first requires we define a coherent notion of module identity. (And the latter is a whole separate discussion.) Until we do this, we can’t in-good-conscious offer a convenient API for hashing SimplicityHL values.