> For the complete documentation index, see [llms.txt](https://valargroup.gitbook.io/shielded-vote-docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://valargroup.gitbook.io/shielded-vote-docs/appendices/pir-efficient-merkle-path-retrieval.md).

# PIR-Efficient Merkle Path Retrieval

This document is really intended for internal @valargroup team as written right now. I do not have enough context laid out for others.

We use [YPIR](https://github.com/menonsamir/ypir) (SimplePIR variant) off of the paper team's codebase. Why? We have blazingly fast simplePIR schemes, however they require large query sizes and a massive Database Hint. YPIR has no DB hint, and low bandwidth per query.

### Specification for Private Key Lookup in a Sorted Merkle Tree

**Version:** 0.3 — Draft **Date:** 2026-02-23

***

### 1. Problem Statement

A server holds a Merkle tree over **N ≈ 50 million leaves** (≤ 2²⁶), each committing to a range of keys. A client wants to privately retrieve the Merkle authentication path for a given key inside of a key-range. Retrieving this merkle path means fetching 26 sibling hashes needed to verify the leaf against the root, without revealing which key it is querying.

The client could download all 50 million nullifiers itself, and hash them, but that would be dumb. We will use PIR to make this a small number of hashes, and bandwidth overhead.

We are in a regime of data size, that our server query processing times are relatively negligible.

We are using a relatively slower hash function (Poseidon), as this must be checked inside of a ZKP. So its also a design goal to have the client do few hash functions. We'd be happy with < 1000 hashes, but we really achieve < 100.

#### Sentinel invariant

The circuit that verifies authentication paths requires all gap widths to be less than 2²⁵⁰. To guarantee this, the tree must include **17 sentinel nullifiers** at positions `k × 2²⁵⁰` for k = 0, 1, …, 16. These sentinels partition the full field into gaps that satisfy the circuit constraint. The PIR export process injects these sentinels before building ranges and the tree.

#### YPIR (SimplePIR) characteristics

The implementation uses YPIR's SimplePIR mode. The server precomputes a per-database hint that the client downloads once per session. Query bandwidth is scheme-parameter dependent and significantly larger than the row payload itself; the dominant cost is the encrypted query and response, not the plaintext data.

| Parameter                | Value                      |
| ------------------------ | -------------------------- |
| Tier 1 server processing | \~0.5s per query (AVX-512) |
| Tier 2 server processing | \~1.6s per query (AVX-512) |
| Row payload (Tier 1)     | 24,512 bytes               |
| Row payload (Tier 2)     | 12,224 bytes               |

#### Design target

Use **2 direct PIR queries** plus a small plaintext payload to retrieve a full 26-hash authentication path. No hash-map or ORAM overhead.

***

### 2. Constants and Sizes

| Symbol | Value        | Description                          |
| ------ | ------------ | ------------------------------------ |
| K      | 32 bytes     | Key size                             |
| V      | 64 bytes     | Value size (or payload per leaf)     |
| H      | 32 bytes     | Hash output size (Poseidon)          |
| L      | V = 64 bytes | Leaf record size                     |
| D      | 26           | Tree depth (root at 0, leaves at 26) |

A **leaf** is a 64-byte record: 32-byte key ‖ 32-byte value. The leaf hash is computed as `Hash(key ‖ value)` and is not stored separately.

An **internal node** is a 32-byte hash: `Hash(left_child ‖ right_child)`.

#### Raw tree size

| Component      | Count                | Size each | Total                         |
| -------------- | -------------------- | --------- | ----------------------------- |
| Leaves         | 2²⁶ = 67,108,864     | 64 bytes  | 4,294,967,296 bytes (4.00 GB) |
| Internal nodes | 2²⁶ − 1 = 67,108,863 | 32 bytes  | 2,147,483,616 bytes (2.00 GB) |
| **Total**      |                      |           | **≈ 6.00 GB**                 |

***

### 3. Architecture: 11 + 8 + 7

The 26-layer tree is split into three tiers:

```
Depth 0  ──────────────  root
  │
  │   TIER 0: Plaintext (11 layers)
  │   Depths 0–11
  │
Depth 11 ──────────────  2,048 subtree roots
  │
  │   TIER 1: PIR Query #1 (8 layers)
  │   Depths 11–19
  │
Depth 19 ──────────────  524,288 subtree roots
  │
  │   TIER 2: PIR Query #2 (7 layers)
  │   Depths 19–26
  │
Depth 26 ──────────────  leaves (up to 67,108,864)
```

Authentication path coverage:

| Tier               | Siblings provided | Depths   |
| ------------------ | ----------------- | -------- |
| Tier 0 (plaintext) | 11                | 1–11     |
| Tier 1 (PIR query) | 8                 | 12–19    |
| Tier 2 (PIR query) | 7                 | 20–26    |
| **Total**          | **26**            | **1–26** |

At each tier, the client must learn:

* The path to their desired key
  * All siblings along the path
* The index they must PIR into at the next layer

And for the leaf, you must learn the full data, and the full data of the sibling. (You compute the sibling hash yourself)

***

### 4. Tier 0: Plaintext (Depths 0–11)

#### Payload

The server publishes a single binary blob containing two sections, serialized in this order:

**Section 1 — Internal hashes at depths 0–10:**

All internal nodes from the root down to depth 10, serialized in breadth-first order.

Count: 2⁰ + 2¹ + ⋯ + 2¹⁰ = 2¹¹ − 1 = 2,047 hashes × 32 bytes = **65,504 bytes (64 KB)**

**Section 2 — Subtree records at depth 11:**

Each record is an interleaved pair: 32-byte `hash` ‖ 32-byte `min_key`.

| Field     | Size     | Purpose                                          |
| --------- | -------- | ------------------------------------------------ |
| `hash`    | 32 bytes | Merkle hash of the subtree rooted here           |
| `min_key` | 32 bytes | Smallest key in this subtree (for binary search) |

Count: 2¹¹ = 2,048 records × 64 bytes = **131,072 bytes (128 KB)**

**Total Tier 0 payload: 64 + 128 = 192 KB (196,576 bytes)**

#### Serialization layout

```
Bytes 0–65,503:        internal_nodes         2,047 × 32 B = 65,504 B
                       (BFS: 1 at depth 0, 2 at depth 1, ..., 1024 at depth 10)
Bytes 65,504–196,575:  subtree_records        2,048 × 64 B = 131,072 B
                       (each record: 32-byte hash ‖ 32-byte min_key)
                                               Total:        196,576 B
```

Node at depth `d`, index `i`: byte offset = `((2^d − 1) + i) × 32`.

Subtree record at index `s`: byte offset = `65,504 + s × 64`. Hash at offset `+0`, min\_key at offset `+32`.

#### Client procedure

1. **Binary search** the 2,048 `min_key` values in Section 2 to find subtree index `S₁ ∈ [0, 2047]` such that `min_key[S₁] ≤ target_key < min_key[S₁ + 1]`.
2. **Read 11 sibling hashes directly** from the blob:

   * Depth 11 sibling: read `hash` from Section 2 at index `S₁ XOR 1`.
   * Depths 1–10 siblings: read from Section 1 by walking the path determined by `S₁` upward through the BFS-indexed tree.

   Client hashing cost: **0** — all sibling hashes are available in plaintext. The client reads them directly; the ZKP circuit handles verification.

#### Caching

This payload is **independent of the queried key** and identical for all clients. It can be served via CDN or cached locally. It changes only when the tree is updated (once per governance round).

Its so small, we think this can even be bundled in the source code.

***

### 5. Tier 1: PIR Query #1 (Depths 11–19, Span = 8)

#### Database layout

| Property        | Value                               | Derivation               |
| --------------- | ----------------------------------- | ------------------------ |
| Rows            | 2¹¹ = 2,048                         | One per depth-11 subtree |
| Content per row | Full 8-layer subtree (depths 11–19) | See below                |

Each row contains a complete 8-layer subtree. The root of this subtree (the depth-11 node) is **not** included — the client already has it from Tier 0.

**Internal nodes** (relative depths 1–7, absolute depths 12–18):

| Relative depth | Node count | Cumulative   |
| -------------- | ---------- | ------------ |
| 1              | 2¹ = 2     | 2            |
| 2              | 2² = 4     | 6            |
| 3              | 2³ = 8     | 14           |
| 4              | 2⁴ = 16    | 30           |
| 5              | 2⁵ = 32    | 62           |
| 6              | 2⁶ = 64    | 126          |
| 7              | 2⁷ = 128   | 254          |
| **Total**      | **254**    | 2⁸ − 2 = 254 |

Internal node storage: 254 nodes × 32 bytes/node = **8,128 bytes**

**Leaf records** (relative depth 8, absolute depth 19):

These are not final tree leaves — they are the roots of the Tier 2 subtrees. Each record is an interleaved pair: 32-byte `hash` ‖ 32-byte `min_key`.

| Field     | Size                                                  |
| --------- | ----------------------------------------------------- |
| `hash`    | 32 bytes (subtree hash below this point)              |
| `min_key` | 32 bytes (smallest key in subtree, for binary search) |

Leaf count: 2⁸ = 256 Leaf storage: 256 records × (32 + 32) bytes/record = 256 × 64 = **16,384 bytes**

**Row total:** 8,128 + 16,384 = **24,512 bytes (23.9 KB)**

#### Database size

| Metric               | Derivation                    | Result                         |
| -------------------- | ----------------------------- | ------------------------------ |
| Raw                  | 2,048 rows × 24,512 bytes/row | 50,200,576 bytes ≈ **47.9 MB** |
| Padded to 32 KB rows | 2,048 rows × 32,768 bytes/row | 67,108,864 bytes = **64 MB**   |

#### Client procedure

1. Issue PIR query for **row S₁** (the subtree index from Tier 0).
2. **Binary search** the 256 `min_key` values at the bottom of the row to find sub-subtree index `S₂ ∈ [0, 255]`. Note: because records are interleaved `(hash, min_key)`, the binary search steps by stride 64, reading `min_key` at byte offset `8,128 + i × 64 + 32`.
3. **Read 8 sibling hashes directly** from the row — no hashing required:
   * 1 sibling at depth 19: the leaf record at index `S₂ XOR 1` (its `hash` field)
   * 7 siblings at depths 12–18: walk the 254 internal nodes from position `S₂` upward, reading the sibling hash at each level

***

### 6. Tier 2: PIR Query #2 (Depths 19–26, Span = 7)

#### Database layout

| Property        | Value                               | Derivation               |
| --------------- | ----------------------------------- | ------------------------ |
| Rows            | 2¹⁹ = 524,288                       | One per depth-19 subtree |
| Content per row | Full 7-layer subtree (depths 19–26) | See below                |

The subtree root (depth-19 node) is **not** included — the client has it from Tier 1.

**Internal nodes** (relative depths 1–6, absolute depths 20–25):

| Relative depth | Node count | Cumulative   |
| -------------- | ---------- | ------------ |
| 1              | 2¹ = 2     | 2            |
| 2              | 2² = 4     | 6            |
| 3              | 2³ = 8     | 14           |
| 4              | 2⁴ = 16    | 30           |
| 5              | 2⁵ = 32    | 62           |
| 6              | 2⁶ = 64    | 126          |
| **Total**      | **126**    | 2⁷ − 2 = 126 |

Internal node storage: 126 nodes × 32 bytes/node = **4,032 bytes**

**Leaf records** (relative depth 7, absolute depth 26 — the actual tree leaves):

Each record is an interleaved pair: 32-byte `key` ‖ 32-byte `value`.

| Field   | Size     |
| ------- | -------- |
| `key`   | 32 bytes |
| `value` | 32 bytes |

No separate hash field is needed; the leaf hash is computed as `Hash(key ‖ value)`.

Leaf count: 2⁷ = 128 Leaf storage: 128 leaves × (32 + 32) bytes/leaf = 128 × 64 = **8,192 bytes**

**Row total:** 4,032 + 8,192 = **12,224 bytes (11.9 KB)**

#### Empty-leaf padding

Partially-filled rows (where the real leaf count is less than 128) pad remaining entries with `key = p − 1` (the maximum field element, i.e. `-1` in the field) and `value = 0`. Using the max field element as the padding key ensures these entries sort after all real leaves, preserving the sorted invariant required by binary search. Padding with `key = 0` would break the binary search because zero sorts before real keys.

#### Database size

| Metric                  | Derivation                      | Result                                                      |
| ----------------------- | ------------------------------- | ----------------------------------------------------------- |
| Raw                     | 524,288 rows × 12,224 bytes/row | 6,408,896,512 bytes ≈ **5.97 GB**                           |
| — leaf data portion     | 524,288 × 8,192                 | 4,294,967,296 bytes = **4.00 GB** (= all 2²⁶ leaves × 64 B) |
| — internal node portion | 524,288 × 4,032                 | 2,113,929,216 bytes ≈ **1.97 GB** (= depths 20–25)          |
| Padded to 32 KB rows    | 524,288 × 32,768                | 17,179,869,184 bytes ≈ **16 GB**                            |

#### Client procedure

1. Compute Tier 2 row index: `S₁ × 256 + S₂` (the absolute depth-19 subtree index).
2. Issue PIR query for this row.
3. **Binary search** the 128 leaf keys to find the target key and retrieve its value. Because records are interleaved `(key, value)`, the search steps by stride 64, reading `key` at byte offset `4,032 + i × 64`.
4. **Read 7 sibling hashes directly** from the row:
   * 1 sibling at depth 26: the leaf at index `(target_position XOR 1)`. Compute its hash as `Hash(key ‖ value)` — this is the **only hash the client computes** during the PIR phase.
   * 6 siblings at depths 20–25: read from the 126 internal nodes by walking upward from the target leaf position.

***

### 7. Storage Accounting

#### Data stored across all tiers

| Data                          | Location    | Size            | Derivation         |
| ----------------------------- | ----------- | --------------- | ------------------ |
| Depths 0–10 internal hashes   | Tier 0      | 65,504 B        | (2¹¹ − 1) × 32     |
| Depth-11 hashes + keys        | Tier 0      | 131,072 B       | 2¹¹ × 64           |
| Depths 12–18 internal hashes  | Tier 1 rows | 16,646,144 B    | 2,048 × 254 × 32   |
| Depth-19 hashes + keys        | Tier 1 rows | 33,554,432 B    | 2,048 × 256 × 64   |
| Depths 20–25 internal hashes  | Tier 2 rows | 2,113,929,216 B | 524,288 × 126 × 32 |
| Depth-26 leaves (key + value) | Tier 2 rows | 4,294,967,296 B | 524,288 × 128 × 64 |
| **Total**                     |             | **≈ 6.02 GB**   |                    |

Note: This slightly exceeds the 6.00 GB raw tree because Tier 0 and Tier 1 store auxiliary `min_key` fields for binary search that aren't present in the raw tree. The extra ≈ 33 MB comes from these search keys (2,048 × 32 B in Tier 0 + 2,048 × 256 × 32 B in Tier 1).

#### Server storage summary

| Database           | Raw size      | Notes                         |
| ------------------ | ------------- | ----------------------------- |
| Tier 0 (plaintext) | 192 KB        | Cacheable, public             |
| Tier 1 (PIR)       | 47.9 MB       | 64 MB if padded to 32 KB rows |
| Tier 2 (PIR)       | 5.97 GB       | 16 GB if padded to 32 KB rows |
| **Total (raw)**    | **≈ 6.02 GB** |                               |

Whether the server stores raw or padded rows depends on the PIR scheme. YPIR operates on raw data and handles alignment internally via `FilePtIter` packing.

***

### 8. Bandwidth Summary

Bandwidth is scheme-dependent. With YPIR (SimplePIR), the client downloads a per-database hint once per session, then each query involves a large encrypted request and response. The dominant cost is the YPIR ciphertext overhead, not the plaintext row payload.

| Component                | Direction       | Size             |
| ------------------------ | --------------- | ---------------- |
| Tier 0 payload           | Server → Client | 192 KB           |
| Tier 1 hint (one-time)   | Server → Client | scheme-dependent |
| Tier 2 hint (one-time)   | Server → Client | scheme-dependent |
| PIR Query 1 (round trip) | Both            | scheme-dependent |
| PIR Query 2 (round trip) | Both            | scheme-dependent |

Tier 0 can be cached across sessions since it only changes when the tree is rebuilt.

***

### 9. Client Computation Summary

| Step      | Binary search   | Hashes computed       | Sibling hashes read |
| --------- | --------------- | --------------------- | ------------------- |
| Tier 0    | Over 2,048 keys | 0                     | 11                  |
| Tier 1    | Over 256 keys   | 0                     | 8                   |
| Tier 2    | Over 128 keys   | 1 (sibling leaf hash) | 7                   |
| **Total** |                 | **1**                 | **26**              |

All internal node hashes are served as plaintext (Tier 0 sends depths 0–10 directly; Tier 1 and Tier 2 rows contain pre-computed internal hashes). The client computes exactly **1 hash** total: the sibling leaf hash in Tier 2, computed as `Hash(key ‖ value)`. The ZKP circuit verifies the full authentication path against the root.

***

### 10. Row Serialization

#### Tier 0 layout (196,576 bytes)

```
Bytes 0–65,503:        internal_nodes             2,047 × 32 B = 65,504 B
                       (BFS: 1 at depth 0, 2 at depth 1, ..., 1024 at depth 10)
Bytes 65,504–196,575:  subtree_records[0..2047]   2,048 × 64 B = 131,072 B
                       (each record: 32-byte hash ‖ 32-byte min_key)
                                                   Total:        196,576 B
```

**Indexing:**

* Internal node at depth `d`, index `i`: byte offset = `((2^d − 1) + i) × 32`
* Subtree record at index `s`: byte offset = `65,504 + s × 64`
  * `hash` at offset `+0`, `min_key` at offset `+32`

#### Tier 1 row layout (24,512 bytes)

Internal nodes serialized in **breadth-first order** (depth 1 left-to-right, then depth 2, …, depth 7), followed by interleaved leaf records:

```
Bytes 0–8,127:        internal_nodes[0..253]     254 × 32 B = 8,128 B
                      (BFS: 2 at depth 1, 4 at depth 2, ..., 128 at depth 7)
Bytes 8,128–24,511:   leaf_records[0..255]       256 × 64 B = 16,384 B
                      (each record: 32-byte hash ‖ 32-byte min_key)
                                                  Total:      24,512 B
```

**BFS indexing:** Node at relative depth `d`, horizontal position `p` (0-indexed):

* Internal node byte offset: `((2^d − 2) + p) × 32` for d ∈ \[1, 7], p ∈ \[0, 2^d)
* Leaf record byte offset: `8,128 + p × 64` for p ∈ \[0, 256)
  * `hash` at offset `+0`, `min_key` at offset `+32`
* Sibling of position p at any depth: position `p XOR 1`
* Parent of position p: position `p >> 1` at depth `d − 1`

#### Tier 2 row layout (12,224 bytes)

```
Bytes 0–4,031:        internal_nodes[0..125]     126 × 32 B = 4,032 B
                      (BFS: 2 at depth 1, 4 at depth 2, ..., 64 at depth 6)
Bytes 4,032–12,223:   leaf_records[0..127]       128 × 64 B = 8,192 B
                      (each record: 32-byte key ‖ 32-byte value)
                                                  Total:      12,224 B
```

**Indexing:**

* Internal node byte offset: `((2^d − 2) + p) × 32` for d ∈ \[1, 6], p ∈ \[0, 2^d)
* Leaf record byte offset: `4,032 + i × 64` for i ∈ \[0, 128)
  * `key` at offset `+0`, `value` at offset `+32`
* Empty leaf records use `key = p − 1` (max field element), `value = 0`

***

### 11. Security Properties

* **Key privacy:** The server learns nothing about which key the client queries. Tier 0 is identical for all clients. Tier 1 and Tier 2 queries are protected by PIR.
* **Sorted-tree leakage:** Key boundaries (the `min_key` values in Tier 0) are public. This reveals the distribution of keys across 2,048 depth-11 subtrees but not which subtree any specific client queries.
* **No hash-map overhead:** The sorted tree enables binary search within each tier's plaintext data, eliminating the need for oblivious hash maps or cuckoo hashing.

***

### 12. Open Questions

1. **Tier 2 cache-line utilization** is 37.3%. The spare 20,544 bytes (32,768 − 12,224) per row could store neighboring subtree data as a guard band for approximate key positioning, or application-specific auxiliary data.
2. **Tree updates:** When leaves change, Tier 2 rows and all ancestor nodes are affected. Tier 1 rows change if any descendant leaf changes. Tier 0 always changes. Incremental update cost depends on the PIR scheme's preprocessing model.
3. **Query sequentiality:** The two PIR queries are inherently sequential — Query 2's row index depends on Query 1's result. Pipelining is not possible without speculation (e.g., querying multiple candidate Tier 2 rows).
4. **PIR scheme selection:** Tier 1's database (48–64 MB) is small enough for most schemes. Tier 2's database (6–16 GB) is the binding constraint; schemes with server-side preprocessing (e.g., SimplePIR, DoublePIR) are recommended.