waxwing on Nostr: One thing I'm noticing over time from reading about different ZKP (or just succinct ...
One thing I'm noticing over time from reading about different ZKP (or just succinct proof) systems is how often two patterns/tricks come up:
one is: represent a composite claim about numbers by random-combination: say you want to prove A is zero and B is zero, you construct A + alpha * B, where alpha has to be unpredictably random - but that's what hash functions + fiat shamir transform can do for you easily. This is seen in basically every construction ever; if nothing else, it's used to make verification faster by batching proofs together.
the second one is something many of us learnt in school with a concrete example: to add up a long list of consecutive numbers, the trick is to take the first and last, then the second and penultimate, then the third and third-from-last etc. as pair, because all of those pairs have the same total. So the general form of this is "pair off items in a list to make a list that's half as long *and* has some special property", and then repeat that until a huge list becomes just a single value.
I've just seen this in FRI as well as it being in bulletproofs and Halo etc. (sometimes called 'recursive' proof technique but that's misleading because that's really something else; that's proofs that prove other proofs are correct :)). The FRI one is interesting because they choose even/odd as the "splitting" function that reduces to half size.
one is: represent a composite claim about numbers by random-combination: say you want to prove A is zero and B is zero, you construct A + alpha * B, where alpha has to be unpredictably random - but that's what hash functions + fiat shamir transform can do for you easily. This is seen in basically every construction ever; if nothing else, it's used to make verification faster by batching proofs together.
the second one is something many of us learnt in school with a concrete example: to add up a long list of consecutive numbers, the trick is to take the first and last, then the second and penultimate, then the third and third-from-last etc. as pair, because all of those pairs have the same total. So the general form of this is "pair off items in a list to make a list that's half as long *and* has some special property", and then repeat that until a huge list becomes just a single value.
I've just seen this in FRI as well as it being in bulletproofs and Halo etc. (sometimes called 'recursive' proof technique but that's misleading because that's really something else; that's proofs that prove other proofs are correct :)). The FRI one is interesting because they choose even/odd as the "splitting" function that reduces to half size.