Score:1

Crypto

How can I prove the preimage of a hash that contains a number is bigger than x?

vrwim

5/20/23, 10:18 AM

So I want to create a zero-knowledge proving system for numbers (think loans and bank accounts, I want to prove my paycheck is more than x dollars per month).

I was thinking about using a zero-knowledge proof for the preimage of a hash. So let's say my employer hashes my paycheck in such a way (e.g. using merkle trees) that my net received is hashed individually. I can use a preimage proof to prove I know the preimage of the hash, but that does not get me anywhere. I want to prove the preimage of the hash is bigger than some set amount.

But that also is not very useful as I don't want to disclose the hash of my paycheck, because it's not difficult to hash all possible amounts (let's say 500.00-5000.00, that's only 450k options) and check if it's equal.

So what I thought about doing is append a random string to the amount, and hash that. Is there a way I can prove that a hash of a string containing a number is bigger than some amount? Or am I thinking about this the wrong way?

0 + 0

hash

zero-knowledge-proofs

Sam Jaques

5/20/23, 4:02 PM

Have you looked into range proofs: https://arxiv.org/abs/1907.06381?

knaccc

5/20/23, 5:30 PM

My answer here https://crypto.stackexchange.com/questions/96232/zkp-prove-that-18-while-hiding-age/97836#97836 shows how to use a Pedersen Commitment instead of a hash, and how to create a Schnorr-ring-signature-based range proof that proves the commitment is greater than or equal to a certain value

Score:-1

Crypto

mentallurg

5/20/23, 11:32 AM

One of criteria of a good hash functions is that it does not reveal any information about preimage. That's why the answer is: No, for a good hash function it is not possible to say anything about the preimage.

Suppose it would be possible. Suppose some hash function would really answer if the hashed number is bigger than the given one. Then it would be easy to find that number.

Use hash to check if the hashed number is bigger than 1 000 000.
If not bigger, take the median, 500 000. Use hash to check it the hashed number is bigger than 500 000.
If bigger, take median from the higher half, 750 000. If not bigger, take median from the lower half, 250 000. Etc. For 1 000 000 you will get the hashed number after just 20 steps, with precision +-1. If you do 7 more steps, you will know the number with precision 0.01.

0 + 0

vrwim

5/20/23, 11:58 AM

Okay but I want someone to prove to someone else that their paycheck is bigger than some value. They can take their knowledge of what's in the hash and use that to generate a proof. Those proofs won't be generated automatically, the user needs to sign it with the value only they know is in the hash. What should I use for this application?

Manish Adhikari

5/20/23, 4:03 PM

This answer is wrong. @vrwim Yes, you are right that it can be done. It should be possible be produce a zero knowledge proof that some value v encoded there is bigger than x for some known x without revealing anything else about x. You cannot binary search the value with that information alone because someone else cannot check whether it is bigger than some other value y as well or not unless the prover decides to prove that as well. The problem is obviously in NP and every problem in NP has a zero knowlege proof

Manish Adhikari

5/20/23, 4:15 PM

Best I know of for such proofs would be ZK SNARK over the boolean circuit for calculating the hash, It is very good for verification (the proof is short and has sublinear verification time w.r.t. witness size). Generating the proof takes some time because of the need to compile the hash program and some elliptic curve operations.

kelalaka

5/20/23, 6:07 PM

See https://www.wisdom.weizmann.ac.il/~oded/gmw1.html

mentallurg

5/20/23, 10:55 PM

@Manish Adhikari: Your comment is wrong. I think you have not understood the question. The question is **not** if ZP proof is possible. The question is if a **static** hash that was calculated by the prover **in advance** (without any interaction with verifier) can be used for ZK proof. It is impossible because of the reason I have described in the answer.

Manish Adhikari

5/21/23, 11:04 AM

OK, but I still don't see how the question is worded to mean what you say it means. I however admit that there are parts I don't get like how the employer gets into the equation

mentallurg

5/21/23, 3:39 PM

@ManishAdhikari: The OP is looking for a way to somehow compute a **single** hash, and do it **in advance**. ZK proof doesn't work in such way.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How can I prove the preimage of a hash that contains a number is bigger than x?

TH: ฉันจะพิสูจน์พรีอิมเมจของแฮชที่มีจำนวนมากกว่า x ได้อย่างไร

RO: Cum pot demonstra că preimaginea unui hash care conține un număr este mai mare decât x?

RU: Как я могу доказать, что прообраз хеша, содержащего число, больше x?

VI: Làm cách nào tôi có thể chứng minh tiền giả của hàm băm chứa một số lớn hơn x?

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.