Score:2

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

ls flag

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.

Thanks in advance!

fgrieu avatar
ng flag
Are you looking for some kind of [accumulator](https://en.wikipedia.org/wiki/Accumulator_(cryptography))?
JeremyDEX avatar
ls flag
Yes exactly. Thanks !
Score:2
br flag

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}$.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.