Zero-knowledge consists of a lot of strange terminology and ideas that can seem strange and confusing. In this thread, we try to address some questions that someone may have for zero-knowledge related topics. This post is based on January’s zk call. The video to be posted.
Does ZK in a project description mean the project uses zero-knowledge?
Many projects use “ZK” to refer to cryptographic primitives usually associated to zero-knowledge. Specifically, succinct. E.g., a project may claim to be ZK without any privacy preserving features. Due to this, some projects label themselves as zkzk to indicate that they use succinct and zero-knowledge.
What is the difference between a proof and argument?
In zero-knowledge, proof does not refer to a mathematical proof. A proof/argument is data produced by the prover (possibly with input from the verifier) that Verifier uses to validate the proof’s claim.
Proof versus argument refers to the soundness security. Proof is statistically secure while argument is computationally secure. Statistical secure is stronger than computational. Papers tend to use these terms interchangeably.
What does succinct mean?
The short answer is: short proof and fast verification. But this is vague. Depending on the paper…
- Constant or polylogarithmic proof size
- Constant or polylogarithmic proof verification.
Justin Thaler suggests using \emph{sublinear} for practical reasons, and for the relation of SNARKs with sublinear algorithms. This makes Bulletproofs a SNARK.
What is the difference between SNARGs, SNARKs and STARKs?
-
SNARG = Succinct Non-interactive Argument
-
SNARK = Succinct Non-interactive Argument of Knowledge
-
STARK = Scalable Transparent Argument of Knowledge
-
Every SNARK is a SNARG.
-
STARKs do not have to be non-interactive. In practice, all STARKs are SNARKs. Thus, STARKs can kind of be viewed as a subset of SNARKs.
Are all ZKPs succinct?
- No.
- Depending on succinct definition, Bulletpoints is an example. The 3-colorability proof has linear verification time. Thus, by all definitions not succinct.
What is the difference between soundness and knowledge soundness?
- Short and not very satisfying answer: Soundness is a core property of interactive protocols and knowledge soundness is property of arguments of knowledge.
An argument of knowledge is a special kind of interactive protocol. E.g., every argument of knowledge is an (non/)interactive protocol.
Argument of knowledge adds a requirement that the Prover should possess knowledge of why a given statement is true. An interactive protocol limits the prover to demonstrating true statements.
- Soundness refers to the probability that a malicious Prover can successfully convince the Verifier of an untrue statement.
- Knowledge soundness refers to the probability that a malicious Prover can successfully convince the Verifier of a statement that they do not possess knowledge of why the statement is true.
These may seem similar, but there is a subtle and crucial difference. Each protocol uses a relation as its basis. A relation provides context for how a statement relates to some secret witness (the knowledge that the Prover claims to possess).
For Schnorr protocol: the relation is every group element with for some . E.g., the relation is the set of elements generated by (). However, Schnorr protocol usually takes as a group with prime order. Thus, . In this case, there is no possibility of the Prover picking a statement (related to the relation) that isn’t a true statement. Knowledge soundness is the probability that the Prover knows the specific related to the statement ().
What does “ZK is free” mean?
You may have seen or heard that adding ZK to a protocol is free. This refers to the ability to tack an hiding factor onto a commitment. The hiding factor conceals the original hidden data.
For example, take so that . We can commit to scalar as . However, the value can be found via brute force. The difficulty of doing this is dependent on the size of the group.
Pedersen commitment protects from brute force attacks by introducing a hiding factor: where and is a random scalar. This scalar prevents brute force, and can be used to conceal .
What is the difference between Circom and a zkVM?
Circom is a domain specific language (DSL) used to generate arithmetic circuits. Developers write the constraints using circom. Circom does not generate proofs. Rather, the circuits produced by circom is used by other libraries (e.g., Snarkjs).
A zkVM execute arbitrary programs to produce a proof. A developer writes their program for the zkVM. The zkVM converts the program to the desired constraints and circuit. These circuits are not (usually) arithmetic circuits but rather execution traces using some instruction set (ISA). At the end of te execution, a zkVM produces a proof that can be used to validate the execution.
Is Fiat-Shamir heuristic a safe method for converting an interactive protocol to non-interactive?
Unhelpful answer: Kind of…sort of…it depends.
- Weak Fiat-Shamir can open up the implementation to forgeries. This should never be used outside of signatures.
- An attack against Strong Fiat-Shamir has been developed against GKR, but unclear whether such an attack can be done in general (even for GKR).
- Multi-round application with (strong) Fiat-Shamir can lose bits of security.
What is the difference between group operation and scalar multiplication (exponentiation)?
- Group operation: For , }
- Scalar multiplication: For :
*
*
*
* - Square-and-multiply algorithm can be used for scalar multiplication (exponentiation). At worse, . For , scalar multiplication is at worst than group addition.
