# The "Top of the Hypercube" Encoding Explained
*Images in this note are extracted from Dmitry Khovratovich's slides but errors are mine.*

This note provides a detailed explanation of the "Top of the Hypercube" encoding, a novel technique for creating more efficient hash-based signatures.

- Paper: https://eprint.iacr.org/2025/889

## The Basics: Signatures, Hypercubes, and Cost

To understand the innovation, we first need to understand the fundamentals of Winternitz-style one-time signatures.

### How Winternitz Signatures Work

1. **Key Generation**: A secret key consists of $v$ random secret values, $sk_1, \dots, sk_v$. Each secret is hashed repeatedly (e.g., $w-1$ times) to create a hash chain. The end of each chain forms the public key, $pk = (pk_1, \dots, pk_v)$.
2. **Encoding**: A message $m$ is converted by an **encoding function** into a vector of coordinates, $x = (x_1, \dots, x_v)$. Each coordinate $x_i$ is a number between $1$ and $w$.
3. **Signing**: To sign, the signer reveals the intermediate hash value at position $x_i-1$ for each chain. The signature is $\sigma = (H^{x_1-1}(sk_1), \dots, H^{x_v-1}(sk_v))$.
4. **Verification**: A verifier takes the signature parts $\sigma_i$ and hashes them the remaining $w-x_i$ times. If $H^{w-x_i}(\sigma_i) = pk_i$ for all chains, the signature is valid.


### The Hypercube and Verification Cost

The set of all possible coordinate vectors forms a structure called a **hypercube**. Imagine it as a grid where each axis represents one of the $v$ hash chains, and each point on an axis represents a position from $1$ to $w$. The dimension of this hypercube, $v$, determines the **signature size**, while the length of each axis, $w$, is the length of the hash chains.

The most critical metric is the **verification cost**: the total number of hash operations a verifier must perform. This cost is directly tied to the encoded coordinates $x = (x_1, \dots, x_v)$:

$$\text{Verification Cost} = \sum_{i=1}^{v} (w - x_i)$$

The paper simplifies this by visualizing the hypercube as an oval shape and grouping points into **layers** based on their "distance from the top," where this distance *is* the verification cost.

$$d = \text{Verification Cost} = v \cdot w - \sum_{i=1}^{v} x_i$$

- **Top of the Hypercube (Low `d`)**: This region contains points with a *high* sum of coordinates (like $(w, w, \dots, w)$). As shown in the figure, these points are "at the top" and have the lowest distance $d$. They are the **most efficient** because they require the fewest verification hashes.
- **Bottom of the Hypercube (High `d`)**: This region contains points with a *low* sum of coordinates (like $(1, 1, \dots, 1)$). They are "at the bottom" and have the highest distance $d$, making them the **least efficient** and most costly to verify.


### The Security Rule: Incomparability

A crucial security property is **incomparability**. An encoding is incomparable if for any two distinct messages $m_1$ and $m_2$ with encodings $x$ and $x'$, neither $x \le x'$ nor $x' \le x$ is true. This means an attacker who sees the signature for $x$ cannot use it to forge a signature for $x'$, because they would need to *reverse* a hash on at least one chain.

A simple way to guarantee incomparability is to ensure all possible encodings lie on the **same layer** of the hypercube.

## The Problem with Traditional Encodings

Previous methods focused on mapping messages to the **middle layer** of the hypercube.

- **Why the Middle Layer?** The middle layer is the largest one, meaning it can represent the most unique messages for a given signature size ($v$) and chain length ($w$). This approach is optimal for minimizing signature size.
- **The Drawback**: The middle layer has a high verification cost. It is far from the "top of the hypercube" and is computationally expensive to verify.

This creates a rigid trade-off: you could have small signatures that are slow to verify, or fast-to-verify signatures that are very large.


## The New Idea: A Counterintuitive Solution

The "Top of the Hypercube" approach breaks this old trade-off with a clever, counterintuitive strategy:

> Instead of using a small hypercube and mapping to its inefficient middle layer, we use a **much larger hypercube** and map messages **only to its most efficient top layers**.

This seems wasteful, as most of the hypercube goes unused, but it dramatically reduces the average verification cost without increasing signature size or compromising security.

### How It Works: From Message to Hypercube Vertex

The process of converting a message into an efficient coordinate vector involves a clever, multi-step mapping. It's designed to take a random hash output and reliably land it in the low-cost "top" region of the hypercube.

#### Step 1: Hashing the Message

First, the message is combined with randomness and passed through a standard cryptographic hash function (like Poseidon2). This produces a single, very large, and unpredictable integer. This number is our starting point.

#### Step 2: Mapping the Hash to the Top Layers

This is the core of the algorithm. The goal is to transform the large random integer into a specific vertex located in one of the top $D$ layers of the hypercube.

1. **Define the Target Space**: The algorithm first considers its target: the set of all points in layers 0 through $D$. It calculates the total number of vertices in this space, let's call this size $\ell_{[0:D]}$.

2. **Generate a Uniform Index**: The large integer from the hash function is reduced modulo $\ell_{[0:D]}$. This mathematical operation produces a new integer, an `index`, that falls between $0$ and $\ell_{[0:D]}-1$. This step ensures that our random hash is now uniformly mapped to a unique position within our desired high-efficiency zone.

3. **Locate the Specific Layer and Offset**: Now that we have a single `index` for the entire top region, we need to find which specific layer it belongs to. Since we know the size of each individual layer, the algorithm can determine this precisely. For example, if layer 0 has 10 vertices and layer 1 has 50, an `index` of 35 must fall within layer 1. This step identifies the exact layer $d$ and the vertex's local position (its `offset` or `remainder`) within that layer.

4. **Convert to Coordinates**: Finally, a deterministic mapping algorithm takes the layer $d$ and the `offset` and converts them into the final coordinate vector $x = (x_1, \dots, x_v)$. This mapping is a bijection, meaning every `(layer, offset)` pair corresponds to exactly one unique vertex, and vice-versa.

This entire procedure is a non-uniform mapping that concentrates all hash outputs into the most desirable, low-cost region of the hypercube, as proven to be optimal by the underlying mathematical analysis.

:::info
**A Complete Walkthrough: Mapping an Index to a Vertex**

This example provides a concrete illustration of the deterministic algorithm that maps a single integer (`index`) to a specific coordinate vector (`vertex`) within the hypercube.

### **Step 1: Defining the Hypercube and Its Layers**

First, we establish the parameters of our space.
- **Hypercube Parameters**: Dimension $v=2$ and base $w=3$.
- **Coordinate Space**: The set of all vectors of length 2 with values from $\{0, 1, 2\}$.
- **Target Region**: We will map our index into the top 3 layers (layers 0, 1, and 2).

We begin by enumerating all 9 vertices, calculating their cost $d = (w-1)v - \sum x_i = 4 - \sum x_i$, and grouping them into layers. This allows us to create a lookup table with the size of each layer and the cumulative size of all layers up to that point.

| Layer (d) | Vertices (Coordinates) | Layer Size ($\ell_d$) | Cumulative Size | Global Index Range |
| :--- | :--- | :---: | :---: | :---: |
| **0** | `(2, 2)` | 1 | 1 | `0` |
| **1** | `(1, 2)`, `(2, 1)` | 2 | 3 | `1 - 2` |
| **2** | `(0, 2)`, `(1, 1)`, `(2, 0)` | 3 | 6 | `3 - 5` |
| **3** | `(0, 1)`, `(1, 0)` | 2 | 8 | `6 - 7` |
| **4** | `(0, 0)` | 1 | 9 | `8` |

The total size of our target region (layers 0 to 2) is **6**.

### **Step 2: Deriving the Index from the Hash**

Assume that the initial message hash, after being reduced modulo 6 (the size of our target region), gives us the following integer:
- **`index = 4`**

Our task is to find the unique coordinate vector that corresponds to this index.

### **Step 3: Locating the Vertex from the Index**

This is a two-part process: first finding the correct layer, then the precise offset within that layer.

**A. Finding the Layer**

We use the `Cumulative Size` column from our table to determine which layer contains the `index = 4`.

- The cumulative size of Layer 1 is 3. Since our `index = 4` is greater than 3, the vertex is not in Layer 0 or 1.
- The cumulative size of Layer 2 is 6. Since our `index = 4` is less than or equal to 6, the vertex must be in **Layer $d=2$**.

**B. Finding the Offset**

The `offset` is the vertex's local position within its layer, starting from 0. It is calculated by subtracting the total size of all preceding layers from the `index`.

- Size of preceding layers (0 and 1) = $1 + 2 = 3$.
- `offset` = `index` - (size of preceding layers)
- `offset` = $4 - 3 = \mathbf{1}$

The location is now precisely defined: **layer 2, offset 1**.

### **Step 4: Converting the Location to Coordinates**

To get the final coordinate vector, we select the vertex at the calculated offset from the list of vertices in that layer. Assuming a canonical (e.g., lexicographical) ordering for the vertices within a layer:

- The vertices in Layer 2 are: `[ (0, 2), (1, 1), (2, 0) ]`
- The vertex at `offset = 1` is the second one in this ordered list.

**Final Result**: The process has deterministically mapped the input `index = 4` to the output coordinate vector **(1, 1)**.

:::

### Ensuring Incomparability (The Three Variants)

The process above produces a point in one of the top $D$ layers. If $D > 0$ (meaning the output can be in multiple layers), the points might be comparable, which is a security risk. To fix this, we need a checksum.

- **TSL (Top Single Layer)**: This is the simplest and often most effective variant. It sets $D=0$, forcing the mapping into a **single** top layer, $L_{d_0}$. Since all outputs are in one layer, the encoding is automatically incomparable and **needs no checksum**.
- **TL1C (Top Layers with 1-Chain Checksum)**: This variant allows mapping to a few top layers (i.e., $D > 0$). It restores incomparability by adding a simple, single-value checksum (like the layer number itself) to the signature.
- **TLFC (Top Layers with Full Checksum)**: This is the most general variant, also for $D > 0$. It uses a longer, multi-part checksum to encode the layer number, which can be slightly more efficient for very large signatures but is often less practical due to the overhead.


## Conclusion

The "Top of the Hypercube" encoding is a significant step because it fundamentally improves the **size-versus-speed tradeoff** for hash-based signatures.

By targeting the most efficient layers of a larger-than-necessary hypercube, it achieves a **20% to 50% reduction in verification hashes** compared to traditional methods, while keeping the signature size and security level the same. This makes it an ideal candidate for systems like Ethereum, where efficient, post-quantum secure signatures are critical for future scalability and security.