SequenceHash: Multihashing for the rest of us

Opal Wright

October 02, 2026

cryptography, zero-knowledge, open-source

Page content

Wait, “multihashing”?

Enter SequenceHash

What does SequenceHash offer?Unambiguous input encoding

Length-extension prevention

Built-in customization strings

MAC mode

How does SequenceHash work?

How do I use it?

Sounds cool. What about SequenceMAC?Some notes on key size

What about extensible output functions (XOFs)?

What if I want to write my own implementation?

Some minor caveats

Multihashing is one of those cryptographic tasks that’s easy not to think about too much. This is unfortunate, because multihashing is a common stumbling point when cryptographers try to use hashes.

As part of our goal to “fix software, not bugs,” Trail of Bits is introducing SequenceHash and its sister function SequenceMAC, a pair of related hash constructions that bring secure multihashing to developers using hash functions other than Keccak. We hope SequenceHash and SequenceMAC will help cryptographers avoid attacks that take advantage of ambiguous input encodings. The specification is open source, and is now a part of the Community Cryptography Specification Project (C2SP).

SequenceHash and SequenceMAC behave similarly to NIST’s TupleHash, but have the advantage of not being tied to a single hash function. They also don’t require developers to implement fiddly computations that aren’t byte-aligned. Instead, SequenceHash and SequenceMAC work out of the box with nearly any secure cryptographic hash function you care to use, including SHA256/384/512, BLAKE, and RIPEMD. SequenceMAC supports keys 32 bytes or longer (up to the ridiculous limit of ${2}^{128}-1$ bytes).

(It’s worth noting: SequenceHash and SequenceMAC rely on the security of the underlying hash for their own security. SequenceHash and SequenceMAC can’t magically make MD4 or SHA0 secure again. For the purposes of this document, it’s assumed that you have chosen a reasonable hash function like SHA256, not CRC32.)

To make SequenceHash and SequenceMAC easy to use, we’re releasing three initial implementations of SequenceHash and SequenceMAC: one each in Rust, Go, and Python. We’re also releasing a large set of test vectors that cover multiple hash functions and include intermediate values to help developers debug and verify their implementations.

Yeah, it’s a weird term, but the idea is pretty simple. “Multihashing” means “hashing a bunch of values together.” If you’ve ever read a cryptography paper, and there’s a step that says something like “compute the shared authenticator N=Hash(X, Y, Z, A, B),” that’s multihashing. You need to create a hash that incorporates the inputs X, Y, Z, A, and B. Unfortunately, the simple “solution” of concatenating the inputs and hashing the result can lead to serious security problems.

For example, consider what happens when you hash three inputs using “raw” SHA256:

import hashlib

hasher = hashlib.new('sha256') hasher.update(b'Test 0') hasher.update(b'Test 1') hasher.update(b'Test 2') print(hasher.hexdigest()) hasher = hashlib.new('sha256') hasher.update(b'Test 0Test 1') hasher.update(b'Test 2') print(hasher.hexdigest()) hasher = hashlib.new('sha256') hasher.update(b'Test 0') hasher.update(b'') hasher.update(b'Test 1Test 2') print(hasher.hexdigest())

This produces the following output:

4fce0a9940a42b5c9d1bcbfc9a6ddd6de20d731d584a0acf5bda6de86483641c 4fce0a9940a42b5c9d1bcbfc9a6ddd6de20d731d584a0acf5bda6de86483641c 4fce0a9940a42b5c9d1bcbfc9a6ddd6de20d731d584a0acf5bda6de86483641c

Even though inputs are fed in through separate calls, they’re not separated from the perspective of the hash function—under the hood, the inputs are just concatenated.

As with many things in cryptography, multihashing is harder than you think. That’s a big problem because multihashing is a critical component of one of the most important tools in zero-knowledge proofs: the Fiat-Shamir transform. When you get multihashing wrong, you introduce the risk of forgeries into your zero-knowledge proofs. Given that zero-knowledge proofs play a major role in cryptocurrency nowadays, that sort of mistake is sometimes measured in millions of dollars.

But Fiat-Shamir transforms aren’t the only place where you might want to use multihashing. It’s not uncommon to need to hash a collection of related objects, where both the objects and the collection are variable in size. Think of authenticating the files in an archive, grouping multiple cryptocurrency transactions into a single hash, or hashing something as “simple” as somebody’s name.

Multihashing is also used when generating cryptographic commitments to values. In some protocols, one party must perform calculations using secret values, only to reveal them to other parties for later verification. Often, this is done by hashing the secret value along with a random “blinding” value and broadcasting the result to other parties as the commitment. If the boundary between the secret value and the blinding value isn’t clear, a “commitment” can sometimes be opened several different ways.

Unfortunately, nobody seems to have landed on a consistent, standard solution to this problem. Instead, across the open-source ecosystem and in our private audits, we find developers solving the problem in wildly different ways. Some of these solutions are insecure, like using separator characters that can also appear in the inputs. Others encode their data in a way that makes their separators unambiguous, but the encoding is unnecessarily complex and introduces subtle timing risks. Think of stuff like Base64-encoding byte strings and separating the results with dollar signs. We often see situations where some hash inputs are length-encoded, but not all. It’s the wild west out there.

There are tools specific to Fiat-Shamir transforms, like Merlin and our own decree, but they don’t work so well for general multihashing.

The most widely known standard for multihashing is TupleHash, defined in NIST SP 800-185. To be clear, TupleHash is great. It solves the multihashing problem in a straightforward way (length-prefix encoding), and it handles inputs of effectively unlimited size (if you’re regularly hashing more than ${2}^{2040}-1$ bits of input, Trail of Bits wants to party with you and your disrespect for physics). As a bonus, it naturally operates as an XOF. If TupleHash is available for you, it’s a great tool.

TupleHash has a downside, though: it’s only defined to work with Keccak, the function that underpins SHA3. If you replace Keccak with another hash function, several of the important security features (like length-extension resistance) can go away. If you don’t have a Keccak implementation handy, you’re out of luck. Given that SHA3 and Keccak adoption have been pretty lackluster over the last decade, that leaves a lot of cryptographers out in the cold. This is especially true in the government contracting sector, where CNSA 2.0 has mandated SHA384 and SHA512 for nearly everything.

This is a problem that cries out for a standardized solution. It calls for a complete specification. It begs for ready-to-use implementations available in multiple languages.

SequenceHash is a hash-agnostic multihashing construct, similar to the way HMAC is a hash-agnostic MAC construct. You can use SequenceHash with your favorite hash functions, including the entire SHA2 family, BLAKE, RIPEMD, and more.

SequenceHash offers four key features that prevent your hashed values from being mixed, extended, or replayed across contexts.

Given two inputs $\left({A,\ B}\right)$, you are guaranteed that there is no other sequence of inputs $\left({{I}{1},\ldots ,{I}{t}}\right)$, for any length $t$, that will result in the same input to the underlying hash function.

In other words, the values you hash are guaranteed to be “semantically distinct.” There’s no chance of playing games with the beginnings and endings of inputs, and there’s no opportunity to mix up parts of $A$ with $B$ or vice versa.

SequenceHash helps cryptographers follow the Horton principle: you are hashing what you mean, and meaning what you hash.

Several popular hash functions, including SHA256 and SHA512, are vulnerable to length extension attacks. If Alice has a secret value $A$ and sends $H\left({A}\right)$ to Bob, then Bob can craft a value $B$ such that he can compute $H\left({A||B}\right)$, even though he doesn’t know $A$.

SequenceHash doesn’t have that issue. It uses a double-hash construction that prevents Bob from learning the information he needs to compute $H\left({A||B}\right)$.

If you’re developing cryptographic protocols, it’s often important to bind hashed values to a particular step in the protocol, or to a specific instance of the protocol, in order to prevent replay attacks or other problems related to reusing values.

SequenceHash makes this easy with built-in customization strings. Assuming you’re using a good hash function, applying SequenceHash or SequenceMAC to the same inputs with different customization strings will lead to unrelated outputs, allowing you to easily and predictably bind your hashes to particular uses. If you don’t need a customization string, don’t worry. They’re completely optional.

As an added bonus, the customization strings are incorporated only into the outer layer of the double-hash construction. If you need to hash the same value with multiple customization strings, the inner hash can be reused!

One final cool feature of SequenceHash is that it has a keyed mode, SequenceMAC. SequenceMAC is structurally similar to HMAC, and offers the same features as SequenceHash: unambiguous encoding, customization strings, and length-extension protection. It also incorporates metadata about the key and customization strings to prevent the key pseudocollision issues present in HMAC.

Like TupleHash, SequenceHash uses length encoding to unambiguously encode its inputs. However, SequenceHash uses a simplified encoding. Instead of writing the number of bits to be hashed as a variable-length integer, SequenceHash encodes the number of bytes into a fixed-length, 128-bit integer. SequenceHash uses a length-suffix encoding for inputs. Like the length-prefix encoding system used by TupleHash, length-suffix encoding is unambiguous; however, suffix encoding allows implementers to develop streaming APIs when they need to support hashing data with length that isn’t known ahead of time.

We chose a 128-bit length encoding for simplicity of implementation on 32- and 64-bit systems (padding with zeroes is easy), and because a ${2}^{128}-1$ byte limit exceeds all practical considerations for the time being and the foreseeable future. Two of the most popular hash functions in use today, SHA256 and SHA512, limit their inputs to ${2}^{61}$ and ${2}^{125}$ bytes, respectively, meaning that a ${2}^{128}-1$-byte limit exceeds the specified limits of the most popular underlying hash functions, anyway. If you’re pushing the edges of SequenceHash, you’ve already blown past the limits of SHA256 and SHA512.

We use byte counts for simplicity. Nearly all hashing today is performed in software on strings of 8-, 16-, 32-, or 64-bit values. Systems using non-byte-length strings are very rare nowadays, and we believe it should be up to implementers of such systems to provide their own byte padding if they want to use SequenceHash.

Like HMAC, SequenceHash uses a double-hash construction to prevent length extension attacks. This structure also allows us to support a keyed variant, SequenceMAC, which accepts keys up to ${2}^{128}-1$ bytes in length.

One downside of the original HMAC construction is that it’s subject to what are known as “key pseudocollisions.” HMAC keys can be any length, but if they’re longer than a certain cutoff value (that depends on the hash), they get hashed before use