Substring Matching Solution 1

This is a solution to a problem discussed at the 2025 research workshop. The goal is to prove that $X$ contains $y_1, \dots, y_k$ as substrings.

Complexity: The number of wires is proportional to:

$$|X| + \sum_{i=1}^k |y_i| + k.$$

---

Let $t \leftarrow \mathbb{F}$ be a random challenge.

Define

$$S[i] = \sum_{j=1}^{i} X[j] \cdot t^{j}$$

and for any string $y$,

$$\mathrm{RollingHash}(y) = \sum_{j=1}^{|y|} y[j] \cdot t^{j}.$$

Then for any substring $X[l+1 \dots r]$,

$$X[l+1 \dots r] = y \quad\Longleftrightarrow\quad S[r] - S[l] = t^{l+1} \cdot \mathrm{RollingHash}(y).$$

---

Idea

We have the values $S[0], \dots, S[n]$. For each $i$, we are given $S[l_i]$ and $S[r_i]$, and must check:

$$S[r_i] - S[l_i] \stackrel{?}{=} t^{l_i+1} \cdot \mathrm{RollingHash}(y_i).$$

If we could guarantee that all these $S[l_i], S[r_i]$ come from $\{ S[0], \dots, S[n] \}$, we could use a permutation check:

$$\prod_{i} (r - x_i) \stackrel{?}{=} \prod_{i} (r - y_i)$$

for random $r \in \mathbb{F}$.

---

Problem

There is no guarantee that the “accessed” values are actually among $S[0], \dots, S[n]$.

You can use merkle tree, and it results in $O(k \log n)$. but we want $O(k)$.

---

Solution

The idea is to use the same trick as this paper. Maintain version numbers for each $S[i]$.

1. Initialize:

$$\texttt{write} = [ (S[0],0), (S[1],0), \dots, (S[n],0) ], \quad \texttt{read} = [], \quad \texttt{version} = [0, 0, \dots, 0].$$

1. When accessing $S[u]$:

   1. Append $(S[u], \mathrm{version}[u] + 1)$ to write.
   2. Append $(S[u], \mathrm{version}[u])$ to read.
   3. Increment $\mathrm{version}[u]$ by 1.

2. At the end, append $(S[i], \mathrm{version}[i])$ for each $0 \le i \le n$ to read.

If the prover is honest, write will be a permutation of read.

---

Permutation check with versioning

Choose random $r_1, r_2, x \in \mathbb{F}$. Verify:

$$\prod_{(S,v) \in \texttt{read}} (S \cdot r_1 + v \cdot r_2 + x) \stackrel{?}{=} \prod_{(S,v) \in \texttt{write}} (S \cdot r_1 + v \cdot r_2 + x).$$

Since $r_1, r_2$ are chosen after the prover commits to read and write, the probability that a malicious prover passes this check without read being a true permutation of write is negligible.

---

Complexity: The number of wires is proportional to:

$$|X| + \sum_{i=1}^k |y_i| + k.$$