6
votes
Accepted
Why invent new hash functions for zero-knowledge proofs?
Let us see an example of how cryptographic hash functions are used in Zero-Knowledge Proof Systems. Following code written in Zokrates DSL Toolbox is an example of computing a Hash using Zero-...
- 343
5
votes
Accepted
What would be the degree (or range of the degree) of the polynomial used in real life zkSnarks as used in blockchains?
Circuit (polynomial) sizes in deployed zkSNARKs. Multiple projects apply zkSNARKSs (e.g., mainly Groth16 or Plonk) in production. The degree of the polynomial slightly depends on the applied poly-IOP ...
- 1,164
4
votes
Accepted
CRS vs SRS in zk-SNARK
There has been variants of definition in the literature, but I would say the zkproof.org's effort to standardize these terminology is a good reference. See page 82 here
I recall there's some ...
- 221
4
votes
Accepted
Why does the challenge need to be prime in Wesolowski's succinct argument of $y=x^{e}$?
Actually [2] does have an explanation:
The reason
we cannot choose $c$ uniformly in some interval, but must choose it from $\mathrm{Primes}(k)$, is because a
random $c$ in $\{1, \ldots, 2^k\}$ has a ...
- 181
3
votes
Why is the SHA256 in libsnark so slow?
Creating a depth 20 tree will require $2^{20}-2^{21}$ hash function evaluations and this will certainly take on the order of processor-hours of resources. Validating a claimed value for a single node ...
- 21.2k
3
votes
Accepted
Which is the relation between Zero-Knowledge Proofs of Knowledge and circuits?
Why are arithmetic circuits interesting in the zero-knowledge world?
There are two main models of general computation: Circuits and Turing-Machines.
Describing the computation path of turing machines ...
- 45.6k
3
votes
Accepted
A field element as the exponent of a group element
If $\alpha \in \mathbb{F}_p$ i.e., the field is a prime field then the exponents are integers modulo $p-1$ since a primitive element $\alpha$ generates the multiplicative group $\mathbb{F}_p^{\ast}$ ...
- 21k
3
votes
Why it is said that “zk-SNARKs need a trusted setup” to work?
Zero-knowledge protocols act (very roughly) in three steps.
Setup
Prove
Verify
(1) needs to be carried out once, and after this setup phase is complete, (2) and (3) can usually be repeated ...
- 2,290
3
votes
Hash and (MAC) based signatures using zk-SNARK
This is a valid paradigm for building a signature scheme, although a secure commitment scheme should be used to commit to $k$ instead of just using $H(k)$ as the public key. This type of construction ...
- 27.5k
3
votes
Accepted
Difference between a Polynomial Opening & a Polynomial Commitment
A Polynomial Commitment is a cryptographic object that binds a party, typically the prover, to a single polynomial. This object could be
an elliptic curve point, such as in KZG or Bulletproofs
en ...
- 1,420
3
votes
Accepted
How to construct a circuit in zkSNARK
is there any specific definition or feature for the problem, and could all problems, which can be verified, be converted into circuits and use zk-snark to generate proofs?
Problem should be in NP ...
- 327
3
votes
Accepted
PLONK Product Check Proof. Why is the 2nd condition required?
The correct checks are
1) $t(\omega^{k-1}) = 1$
and
2) $t(\omega\cdot x) - t(x)\cdot f(\omega \cdot x) = 0$ for all $x \in \Omega$
The prover is supplying values in a black box way. The second ...
- 21k
3
votes
Accepted
PLONK Prod Check Proof - why does it have to be proven upto the last element of the set? It should be enough to prove it upto last but one element
At $x=\omega^{k-1}$ the 2nd equation is $$t(\omega^k) = t(\omega^{k-1}) \cdot f(\omega^k)$$ which, knowing that $\omega^k = 1$ and assuming 1) is satisfied, i.e. $t(\omega^{k-1})=1$, it converts to $$...
- 722
3
votes
Accepted
Is the permuation check range in the PLONK Paper incorrect?
The argument in the paper is correct. Verifying (a) confirms that $Z(g)=1$, verifying
$$Z(a)f'(a)=g'(a)Z(a\mathbf g)$$
for $a=\mathbf g,\mathbf g^2,\mathbf g^3\ldots \mathbf g^{n-1}$ then inductively ...
- 21.2k
3
votes
Accepted
What does preprocessed polynomial mean in the context of PLONK?
Pre-processing means part of the one-time initial set up computation of the system prior to the generation of any proofs. This set-up phase is allowed to use considerably more resources.
If we look to ...
- 21.2k
3
votes
Accepted
PLONK: Why is the quotient polynomial multiplied by different powers of a challenge?
The quotient challenge is necessary for soundness. In particular, if the prover wants to show that there exists quotients $q_1=f_1/z_H$, $q_2=f_2/z_H$, and $q_3=f_3/z_H$. To do so, it can instead send ...
- 929
2
votes
Accepted
libsnark generator toxic waste
The line:
default_r1cs_ppzksnark_pp::init_public_params();
is used to specify the public parameters used by the proving system ($\mathbb{G}_1, \mathbb{G}_2, \...
2
votes
Accepted
Fixed variable in Groth16
Your thinking is correct!
In the GGPR13 paper (see Definition 11 in section 7.1 ) quadratic arithmetic programs were introduced for proving arithmetic circuit satisfiability. The key idea was that ...
2
votes
Accepted
Can zksnark prove DLP?
final_exp_gadget<>() of libsnark could be a practical example to tune for DLP.
The idea is, "final exponentiation" is a part of Ate pairing, that is verified as a part of check_e_equals_e_gadget<...
- 2,287
2
votes
How to construct a circuit in zkSNARK
To answer your first question,
the feature of problem is usually from NP Class where you compute in Non-deterministic Polynomial(NP) time, but verifying the computation should take less than or equal ...
2
votes
Construction of R1CS vs QAP
In the original Pinocchio [GGPR13], the authors didn't use R1CS at all.
As a ZKP friendly computational representation, R1CS was proposed later that year in [BCGTV13] Appendix E. The reduction from an ...
- 221
2
votes
Accepted
Definition of Circuit Satisfiability In The Context of zk-SNARKs
Suppose $L$ is an NP language, and its witness checking algorithm is $R$, so that $L = \{ x \mid \exists w : R(x,w) = 1 \}$.
Here is how I can prove to you that $x \in L$:
Generate a circuit $C$ such ...
- 11.7k
2
votes
Accepted
zkSnarks: Why does the target polynomial $t(s)$ need to be kept a secret if it's known to both prover & verifier?
While the polynomial $t(x)$ itself is known, the specific evaluation at $s$, $t(s)$, is not known.
In the interactive version, the prover computes $g^p$ and $g^h$ in "encrypted space" as the ...
- 1,573
2
votes
Accepted
zkSNARKS: If we are already using Homomorphic Encryption/Hiding, why is the shift by $\delta$ required for Zero Knowledge?
Zero-knowledge means zero knowledge, that we learn literally nothing except the validity of the proof.
Even if we don't learn $p, p'$ and $h$ themselves, we still learn $g^p$ which we could not have ...
- 1,573
2
votes
Why it is said that “zk-SNARKs need a trusted setup” to work?
Roughly answering! In a zero knowledge proof, prover (P) wants to prove to verifier (V) that she knows witness (w) for a statement (s) without disclosing any information (zero information) about the ...
- 327
2
votes
Accepted
Why Zk-SNARKs are Argument of Knowledge if a Knowledge Extractor exists?
Knowledge soundness can indeed be computational or statistical. There are some classical example, if you want some illustration: the Sigma protocol for correct opening of the Damgard-Fujisaki ...
- 18.9k
2
votes
How to prove that a line belongs to a final hash without knowing/re-hashing all other lines?
Short answer: (1) Build a Merkle tree over your database and (2) give a Merkle path to the entry you want to prove is in the database.
SNARKs are great, but are a big hammer that's completely ...
- 1,003
2
votes
Accepted
Arithmetic Circuits to R1CS. Do we consider addition gates or not?
I've answered a similar question on this here
As you've correctly observed, Buterin's example is simplified and does not account for the optimisations that are possible with R1CS. If you want to ...
- 413
2
votes
What is the difference between those two KZG Polynomial Commitment Schemes?
Both represent the same thing. The first one uses the additive notation & the 2nd one uses the multiplicative notation. That is the only difference.
KZG actually uses an Elliptic Curve Group, so ...
- 2,167
2
votes
Accepted
How do I construct a recursive polynomial as required in PLONK?
To construct $t(X)$, you can use the Lagrange interpolation method.
Suppose $F=GF(17)$ and $w=4$ is an $4^{th}$ roots of unity in $F$. (I'm taking your example from this post )
Now $f(X)=3X^2+4X+7$ ...
- 61
Only top scored, non community-wiki answers of a minimum length are eligible