Everything in Dacite is built on a single operation: fuse. It combines two 256-bit hashes into a new 256-bit hash using nothing more than integer arithmetic. No SHA-256 at runtime, no hash function calls in the critical path — just six additions and a multiplication.
The idea originates from an HP Labs white paper on using upper triangular matrix multiplication to combine hashes associatively:
Haber, S. et al. (2017). Efficient and Secure Hash-Based Timestamps. HPE-2017-08. https://www.labs.hpe.com/techreports/2017/HPE-2017-08.pdf
The paper proposes representing hashes as upper triangular matrices and multiplying them. Matrix multiplication is associative but not commutative — exactly the properties needed for tree-shape-independent hashing. Dacite’s contribution is the specific 4×4 matrix over 64-bit cells, chosen based on empirical testing of degeneration behavior (see §1.8).
This chapter introduces fuse, its algebraic properties, and how it turns raw bytes into content addresses.
A Dacite hash is 256 bits, represented as four 64-bit unsigned integers in big-endian word order:
hash = [c0, c1, c2, c3]
Word c0 holds the most mixed bits (from fuse) and is used first for
HAMT navigation. Word c3 holds the least mixed bits.
Fuse takes two hashes and produces a third:
Input: a = [a0, a1, a2, a3]
b = [b0, b1, b2, b3]
Output: c = [c0, c1, c2, c3]
c0 = a0 + a3*b2 + b0 ← most bit mixing (single multiply)
c1 = a1 + b1
c2 = a2 + b2
c3 = a3 + b3 ← least bit mixing (simple addition)
All arithmetic wraps at 2^64. The total cost: 6 additions, 1 multiplication.
These properties are not incidental — the entire system depends on them:
fuse(a, fuse(b, c)) = fuse(fuse(a, b), c).
This means tree shape doesn’t affect the hash. A balanced tree and
a left-degenerate tree over the same leaf sequence produce the same
root hash.fuse(a, b) ≠ fuse(b, a) (for a ≠ b).
Order matters. [x, y] and [y, x] have different hashes.[0, 0, 0, 0] is a two-sided identity.
fuse(a, 0) = fuse(0, a) = a. Empty sequences hash to the identity.Associativity is the foundation of structural sharing. Consider a
sequence [a, b, c, d]. Its hash is:
fuse(fuse(fuse(a, b), c), d)
But because fuse is associative, any parenthesization gives the same result:
fuse(fuse(a, b), fuse(c, d)) — balanced tree
fuse(a, fuse(b, fuse(c, d))) — right-degenerate tree
This means two stores can organize the same data differently (different tree shapes for performance) and still agree on the root hash.
graph TD
subgraph "Left-degenerate tree"
L1["fuse"] --> L2["fuse"]
L1 --> Ld["d"]
L2 --> L3["fuse"]
L2 --> Lc["c"]
L3 --> La["a"]
L3 --> Lb["b"]
end
subgraph "Balanced tree"
B1["fuse"] --> B2["fuse"]
B1 --> B3["fuse"]
B2 --> Ba["a"]
B2 --> Bb["b"]
B3 --> Bc["c"]
B3 --> Bd["d"]
end
R["Same root hash"] -.-> L1
R -.-> B1
style R fill:#4a9,stroke:#333,color:#fff
Different tree shapes, same root hash. This is what makes finger trees possible — internal rebalancing never changes the identity of the sequence.
If fuse were commutative, [a, b] and [b, a] would hash the same.
Sequences would be indistinguishable from sets. Order-sensitive data
structures (vectors, strings) require that fuse(a, b) ≠ fuse(b, a).
graph LR
subgraph "fuse(a, b)"
AB["fuse"] --> A1["a"]
AB --> B1["b"]
end
subgraph "fuse(b, a)"
BA["fuse"] --> B2["b"]
BA --> A2["a"]
end
AB -. "≠" .-> BA
style AB fill:#4a9,stroke:#333,color:#fff
style BA fill:#a44,stroke:#333,color:#fff
Order matters: [a, b] and [b, a] produce different hashes.
Fuse forms a group over (ℤ/2^64)^4. Every hash has a unique inverse:
inv([a0, a1, a2, a3]) = [a3*a2 - a0, -a1, -a2, -a3]
Such that fuse(inv(a), a) = fuse(a, inv(a)) = [0, 0, 0, 0].
Cost: 1 multiply + 4 negations.
Given fused = fuse(a, b), if you know b, you can recover a:
unfuse(fused, b) = fuse(fused, inv(b)) = a
Strip from the left: fuse(inv(a), fused) = b.
Dacite doesn’t hash bytes directly with fuse. Instead, it uses a precomputed lookup table mapping each byte value (0–255) to a 256-bit hash:
byte_hash: byte → Hash (256 entries)
The default table is seeded using SHA-256:
byte_hash[i] = sha256(byte_array([i])). But any set of 256 distinct,
high-quality 32-byte values works. This decouples Dacite from any
specific hash function at runtime — SHA-256 is used once at build time
to generate the table, never again.
All data hashing reduces to table lookups and fuses:
fuse_bytes(bs) = reduce(unchecked_fuse, [0,0,0,0], map(byte_hash, bs))
fuse_str(s) = fuse_bytes(utf8_bytes(s))
Because fuse is associative:
fuse(fuse_str(a), fuse_str(b)) = fuse_str(a ++ b)
Composing fused results is equivalent to fusing the concatenation. This is both a feature (tree nodes can combine child hashes) and a constraint (domain separators are needed between fields — see Chapter 2).
The byte hash table is a build-time constant, not stored inside the content-addressed space. The table’s own hash serves as a protocol identifier:
protocol_id = fuse_bytes(concat(table[0], table[1], ..., table[255]))
The table hashes itself: each row is 32 bytes, concatenated into 8,192
bytes, and fuse_bytes (which uses the table) produces the ID.
Two stores are compatible if and only if they share the same protocol ID. Implementations check this on first contact.
Fuse must reject inputs and outputs where the lower 32 bits are zero in all four words:
low_entropy?(h) =
(h[0] & 0xFFFFFFFF) == 0 AND
(h[1] & 0xFFFFFFFF) == 0 AND
(h[2] & 0xFFFFFFFF) == 0 AND
(h[3] & 0xFFFFFFFF) == 0
The checked fuse:
fuse(a, b):
REJECT if low_entropy?(a)
REJECT if low_entropy?(b)
result = unchecked_fuse(a, b)
REJECT if low_entropy?(result)
return result
An unchecked variant exists for internal use where inputs are known valid (e.g., combining measures within finger tree nodes).
The HP paper describes hash fusing using upper triangular matrices in general terms. The same 256-bit hash can be packed into matrices of different sizes depending on cell width:
| Cell size | Matrix size | Cells above diagonal |
|---|---|---|
| 8-bit | 9×9 | 36 (of which 32 used) |
| 16-bit | 7×7 | 21 (of which 16 used) |
| 32-bit | 5×5 | 10 (of which 8 used) |
| 64-bit | 4×4 | 6 (of which 4 used) |
The HP paper’s specific implementation used 8-bit cells in a 9×9 matrix. Larger cells mean fewer cells in the matrix, but each cell participates in more bit-mixing per multiply. This tradeoff matters for degeneration resistance — and as the experiments below show, the 8-bit choice degenerates surprisingly quickly.
Empirical testing (published at Clojure Civitas) revealed a critical difference between cell sizes. The test: take a hash h, fuse it with itself (“fold”), then fold the result with itself, and repeat. Each fold squares the hash: fold 1 = h², fold 2 = h⁴, fold n = h^(2^n). This measures resistance to the worst case — long runs of identical values.
| Cell size | Folds to zero (approx.) | Equivalent repeated fuses |
|---|---|---|
| 8-bit | ~8 | ~2^8 = 256 |
| 16-bit | ~16 | ~2^16 = 65,536 |
| 32-bit | ~32 | ~2^32 ≈ 4.3 billion |
| 64-bit | ~64 | ~2^64 ≈ 1.8 × 10^19 |
The exact fold count varies with the starting hash, but the relationship is statistical: folds to zero tracks the cell size in bits. Smaller samples showed values within a few folds of the cell size; a larger sample would pin down the distribution more precisely.
With 8-bit cells — the HP paper’s implementation choice — repeating the same hash roughly 256 times causes complete degeneration. With 64-bit cells, you’d need approximately 2^64 repetitions — far beyond any realistic data.
graph LR
H["h"] -->|"fold 1"| H2["h² = fuse(h,h)"]
H2 -->|"fold 2"| H4["h⁴ = fuse(h²,h²)"]
H4 -->|"fold 3"| H8["h⁸ = fuse(h⁴,h⁴)"]
H8 -->|"..."| HN["h^(2^n)"]
HN -->|"fold n"| Z["zero (degenerated)"]
style Z fill:#a44,stroke:#333,color:#fff
A separate experiment with random fuses (alternating between two random hashes) showed zero collisions across millions of fuses for all cell sizes. Degeneration is specific to low-entropy data — repeated fusing of the same value.
The 4×4 matrix with 64-bit cells won on all axes:
The low-entropy rejection check (§1.6) checks the lower 32 bits of each word. This means fuse rejects degenerate hashes after approximately 2^32 repeated fuses of the same value — well within the 64-bit cell’s ~2^64 capacity, providing a conservative safety margin that catches degeneration long before it reaches the theoretical limit.
The irreducible core — everything else derives from these:
| Function | Signature | Description |
|---|---|---|
fuse |
(Hash, Hash) → Hash |
Combine two hashes (checked) |
unchecked-fuse |
(Hash, Hash) → Hash |
Combine without low-entropy check |
inv |
Hash → Hash |
Compute the group inverse |
fuse-bytes |
bytes → Hash |
Hash a byte sequence via table lookup |
byte-hash-table |
byte → Hash |
The 256-entry lookup table |
low-entropy? |
Hash → bool |
Check if lower 32 bits are all zero |
Convenience functions that compose from the primitives:
| Function | Derivation | Description |
|---|---|---|
unfuse |
fuse(a, inv(b)) |
Strip right: recover left operand |
fuse-str |
fuse-bytes(utf8-encode(s)) |
Hash a UTF-8 string |
protocol-id |
fuse-bytes(concat(table[0..255])) |
The table’s self-hash |
fuse(a, fuse(b, c)) = fuse(fuse(a, b), c) — associativityfuse(a, b) ≠ fuse(b, a) for a ≠ b — non-commutativityfuse(a, [0,0,0,0]) = a — right identityfuse([0,0,0,0], a) = a — left identityfuse(a, inv(a)) = [0,0,0,0] — right inversefuse(inv(a), a) = [0,0,0,0] — left inversefuse(a, inv(b)) = unfuse(a, b) — unfuse is derivedfuse(inv(a), fuse(a, b)) = b — left recoveryfuse-bytes(a ++ b) = fuse(fuse-bytes(a), fuse-bytes(b)) — composabilityfuse rejects when low-entropy? is true for input or outputThis layer has zero dependencies — no I/O, no state, just integer arithmetic and a lookup table. It is the natural starting point for porting Dacite to a new language.
Hash fusion gives the rest of Dacite three guarantees:
The next chapter builds data structures on this foundation.