Usually in an IP, the prover (Bob) has to answer questions from the verifier (Alice), and Alice chooses her questions by flipping a coin. If the Bob doesn’t really know the answer, he’ll get caught cheating with high probability.
So now the trick: Bob starts generates his initial answer. Then he hashes it (“commits” in the jargon), and uses the hash as “Alice’s first coin flip”. Then he answers the question for that flip, hashes the whole thing for “Alice’s second coin flip”… etc.
Bob does this say, 100 times, and then sends the whole simulated conversation to Alice. Alice can verify that he didn’t cheat by checking the intermediate hashes.
The whole thing depends on the ability to not control the result of the hash function, so it’s vital to use a cryptographically secure one.
It "feels" much easier to generate random non-solutions and check if the random questions happen to pass, though. Is it really all there is to it? You increase the number of questions to compensate and that's the whole scheme? Wouldn't the responses be a ludicrous amount of data?
Yes, basically. The hard work happens in constructing the interactive proof to ensure that you can’t reneg on the earlier steps.
All the proofs that I know of allow one to get lucky with probability about .5 in each round. When you do an interactive proof with 100 rounds, you have a 2^-100 chance of getting away with cheating.
When you go non-interactive with 100 rounds, an adversary could cheat by trying about 2^100 proofs. So you replace a stronger guarantee with a weaker one, but 2^100 is a pretty big barrier.
(I just looked and the Wikipedia page and it’s very confusing fwiw)
The trick is called the Fiat-Shamir transform, and you're right, it does require more questions to get an equivalent security level, precisely because you can try a large number of random non-solutions without anyone catching you doing it.
But the number of questions you need to compensate grows only a little.
For example, interactively if you ask for Merkle tree proof that selected leaf values have a particular property, you only have to ask for about k leaves to get probability 1-(2^-k) that you'd catch a dishonest prover who had committed a Merkle root with less than half the leaves having the property.
Non-interactively, a dishonest prover could secretly grind attempts, say 2^g times, and then you'd have a lower probability of catching them, approximately 1-(2^(g-k)). But g can't be all that large, so you can increase k to compensate without making the proof much larger.
You.can also require certain hashes to have a fixed prefix, like Bitcoin mining, forcing every prover to have to grind 2^p times. This reduces the effective g that a dishonest prover can achieve, allowing k to be smaller for the same security, so allowing the non-interactive proof to be smaller. At the cost of honest provers having to grind.
There is a trick to convert an IP to a non-IP.
Usually in an IP, the prover (Bob) has to answer questions from the verifier (Alice), and Alice chooses her questions by flipping a coin. If the Bob doesn’t really know the answer, he’ll get caught cheating with high probability.
So now the trick: Bob starts generates his initial answer. Then he hashes it (“commits” in the jargon), and uses the hash as “Alice’s first coin flip”. Then he answers the question for that flip, hashes the whole thing for “Alice’s second coin flip”… etc.
Bob does this say, 100 times, and then sends the whole simulated conversation to Alice. Alice can verify that he didn’t cheat by checking the intermediate hashes.
The whole thing depends on the ability to not control the result of the hash function, so it’s vital to use a cryptographically secure one.
It "feels" much easier to generate random non-solutions and check if the random questions happen to pass, though. Is it really all there is to it? You increase the number of questions to compensate and that's the whole scheme? Wouldn't the responses be a ludicrous amount of data?
Yes, basically. The hard work happens in constructing the interactive proof to ensure that you can’t reneg on the earlier steps.
All the proofs that I know of allow one to get lucky with probability about .5 in each round. When you do an interactive proof with 100 rounds, you have a 2^-100 chance of getting away with cheating.
When you go non-interactive with 100 rounds, an adversary could cheat by trying about 2^100 proofs. So you replace a stronger guarantee with a weaker one, but 2^100 is a pretty big barrier.
(I just looked and the Wikipedia page and it’s very confusing fwiw)
The trick is called the Fiat-Shamir transform, and you're right, it does require more questions to get an equivalent security level, precisely because you can try a large number of random non-solutions without anyone catching you doing it.
But the number of questions you need to compensate grows only a little.
For example, interactively if you ask for Merkle tree proof that selected leaf values have a particular property, you only have to ask for about k leaves to get probability 1-(2^-k) that you'd catch a dishonest prover who had committed a Merkle root with less than half the leaves having the property.
Non-interactively, a dishonest prover could secretly grind attempts, say 2^g times, and then you'd have a lower probability of catching them, approximately 1-(2^(g-k)). But g can't be all that large, so you can increase k to compensate without making the proof much larger.
You.can also require certain hashes to have a fixed prefix, like Bitcoin mining, forcing every prover to have to grind 2^p times. This reduces the effective g that a dishonest prover can achieve, allowing k to be smaller for the same security, so allowing the non-interactive proof to be smaller. At the cost of honest provers having to grind.
This is Fiat-Shamir, right?
Correct. I didn’t remember the name, so thanks!