Difference between zk-SNARK and Verifiable Random Function

What is the difference between VRF (Verifiable Random Function, used in the ticket generation in expected consensus) and zk-SNARK (used in verifying seal sector)?
Both seems to be doing the same thing, verifying a statement by only giving the validity of the statement, and without leaking any secret variable.
I know this is a bit technical, but any thoughts will be appreciated. Thanks in advance!

I am interpreting this question as “What is the difference in filecoin’s use between the two primitives”. If the question is actually “What is the difference between the two primitives” wikipedia is a helpful place to start out.

These are two different primitives with different properties and different interfaces and so filecoin uses them differently. They are not doing the same thing in the system, and are not suitable replacements of each other in the system. Snarks are used in proofs of storage, an area I know little about, but very likely a satisfying answer to your question here is “the two primitives have different interfaces”. If you want to know more @porcuquine can help you understand in excruciating detail why snarks and not VRFs are suitable for use in proofs of storage.

VRFs have two uses in the protocol. (1) miners use a VRF to create some randomness (the block ticket) when mining a block and (2) scratch off a ticket from a past block in the chain in a deterministic but unpredictable way (see Algorand for a good idea of how we use this). Again most likely a satisfactory answer to your question is that VRFs have a different interface, the snark interface doesn’t output a random value anywhere.

Maybe you want to dive deeper and look into why we don’t implement VRF in terms of snark. Now I am no cryptographer so take this with a grain of salt, but if you follow the wikipedia VRF page to the linked introductory paper then you’ll notice on page 2 that VRFs were actually designed to address limitations in snarks.

One more note, the “VRF” we are using is actually made up of a simple signature scheme (AFAIK the same thing Algorand does). Just FYI that our construction probably departs significantly from what you’ll find if you read that paper thoroughly.

One final disclaimer that I’m not a cryptographer so please be skeptical of any above discussion of cryptographic primitive internals.

1 Like

Thanks for the insight! (I am also not a cryptographer myself so I have no idea on how to start reading the papers.)

Can’t recommend this free online book enough for getting started with cryptographic literacy, understanding of the typical formalisms and argument structures etc if you have the inclination: https://crypto.stanford.edu/~dabo/cryptobook/

2 Likes

slightly different answer:

A VRF is a zero knowlege proof of knowledge of a secret. You could implement a VRF using zk-SNARKS, but that would be a bit overkill as we have this really nice ‘proof of knowledge of a secret’ algorithm thats really fast called an asymmetric keypair signature (like RSA or ed25519 signatures).

For other things that we need to prove, there arent better algorithms that exist yet, so we have to fall back to using the super inefficient zkSNARKs

1 Like

Thanks for the answer. I was playing with Filecoin testnet by uploading and downloading files. They are extremely slow. I have a late 2014 Mac mini and uploading a 23B text file to it took 45 mins (from a separate Ubuntu VM), while downloading the file took 7 mins. I also noticed that the physical memory usage was 4-6GB while processing the upload. Could this be caused by construction and verification of the zk-SNARK proofs?