[Cryptography] speed of hashing inside zk-snark proof generation
cherry
cherry at rhocoin.org
Sun Nov 26 06:38:07 EST 2023
A zk-snark or a zk-stark proves that someone knows something, knows a
pile of data that has certain properties, without revealing that pile of
data.
A recursive snark proves that someone knows a pile of data that proves
that someone else knows a pile of data that has certain properties.
One wants to be able to prove that a transaction is valid because its
inputs were came from valid transactions, which were valid because their
inputs were valid transactions which were valid because ..
And to do this one must prove that a hash is the hash of data that has
certain properties, so that one can prove that the entire pre-image of a
potentially enormous Merkle dag represented by its root hash has certain
properties.
So the big job, what costs a lot of computing power, is to prove you
know a pre-image for a hash that has certain properties. Most of the
cost of proof generation is going to be proving that the publicly
visible hash corresponds to non public data.
And I am having trouble finding information on recursive snark
algorithms that tell me how fast the algorithm is at this task, how fast
the algorithm is at generating a zk-snark or snark that proves that its
public data, a hash, corresponds to a private pre-image that itself
contains hashes, and that the prover verified proofs about the recursive
pre-images that those hashes represented. This is the dominant cost,
and what else is in the pre-image does not matter much. The primary
costs of generating a proof are going to be proving the public hash of
the private preimage, and proving verification of the zk-snarks for the
hashes inside that pre-image.
And I cannot seem to find any information on how fast Nova performs this
job. The available information on Nova and hashes just does not seem to
talk about producing proofs about hashes and proofs about proofs of
verification of hashes.
Plonky had their own special hash that they could efficiently generate
proofs for. I cannot seem to find the equivalent for Nova. Maybe I am
looking in the wrong place.
More information about the cryptography
mailing list