# How to prove that a line belongs to a final hash without knowing/re-hashing all other lines?

Let's suppose :

• I have a record/database (D) of 754 lines and each line correspond to a SHA256 hash.(Hn)
• I hash all this record to a final and unique SHA256 hash like this : 1a3e6af379316c6b863318f9e23ad0588d7d845ea92f316779f36167fd359fb0 (F)
• I know H34 (single entry of D) which is 9370d1f5ab2fe94f685039fc8a2bb8ec3c2a3b100f20e58f261933b72f3bbd56.

How to prove that a single hash (H34) belongs to the database (D), or was hashed to give the final hash (F), without knowing all the other hash composing the database ? So ∀i∈[0,n], Hi∈D or Hi => F ?

I looked at SNARK solutions, but I don't have a simple understanding on how it could apply to this specific case.

• Are you looking for some kind of accumulator?
– fgrieu
Commented Nov 24, 2022 at 12:13
• Yes exactly. Thanks ! Commented Nov 24, 2022 at 12:36

Short answer: (1) Build a Merkle tree over your database and (2) give a Merkle path to the entry you want to prove is in the database.

SNARKs are great, but are a big hammer that's completely unnecessary here.

Cryptographic accumulators (RSA, bilinear) are great too, but will be much more expensive computationally & tricker to implement.

## An example with a small database

Let $$H : \{0,1\}^* \rightarrow \{0,1\}^{256}$$ denote a hash function with 256-bit output (e.g., SHA3-256) and let $$H(x)$$ denote the hash of an arbitrary blob of data $$x$$.

Suppose you have 8 entries in your database: $$f_1,f_2,\dots,f_8$$.

You can build a Merkle tree by "recursively" hashing your files like this:

Next, give the root $$h_{1,8}$$ of the tree to the verifier.

Next, suppose you want to convince this verifier, who has the root (i.e., the source of truth), that the 3rd file $$f_3$$ is in the database.

Give him $$f_3$$ itself and the Merkle proof for $$f_3$$:

Note that the Merkle proof consists of the sibling nodes along the path from $$f_3$$'s leaf to the root.

The verifier can easily fill in the blanks in the picture above, by "hashing up the tree" and checking that the root he obtains when doing this is the same as $$h_{1,8}$$.