Skip to main content
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-...
Gokul Alex's user avatar
5 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 ...
Alex Xiong's user avatar
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 ...
István András Seres's user avatar
4 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 ...
Alan's user avatar
  • 1,460
4 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 ...
SEJPM's user avatar
  • 46.2k
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 ...
MERTON's user avatar
  • 181
3 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 ...
Geoffroy Couteau's user avatar
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}$ ...
kodlu's user avatar
  • 22.8k
3 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 ...
Hypatia's user avatar
  • 365
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 ...
Ruben De Smet's user avatar
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 ...
Yehuda Lindell's user avatar
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 ...
Hypatia's user avatar
  • 365
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 ...
Daniel S's user avatar
  • 24.1k
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 ...
kodlu's user avatar
  • 22.8k
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 $$...
Bean Guy's user avatar
  • 752
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 ...
Daniel S's user avatar
  • 24.1k
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 ...
Daniel S's user avatar
  • 24.1k
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 ...
Wilson's user avatar
  • 929
3 votes
Accepted

PLONK's computation of the first Lagrange polynomial at $\zeta$

Given the subgroup $H=\lbrace 1, \omega, \omega^2, \omega^3, ..., \omega^{n-1}\rbrace$ of order $n$, the Lagrange basis of this subgroup is given by the set of polynomials $\lbrace L_i \rbrace_{i=1}^n$...
Marc Ilunga's user avatar
  • 3,338
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, \...
Zachary Ratliff's user avatar
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 ...
sunfishstanford's user avatar
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<...
Vadym Fedyukovych's user avatar
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 ...
Alex Xiong's user avatar
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 ...
Verified Anon's user avatar
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 ...
Mikero's user avatar
  • 13.5k
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 ...
meshcollider's user avatar
  • 1,583
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 ...
meshcollider's user avatar
  • 1,583
2 votes

Generic name for R1CS vs. AIR

I'd say, R1CS, PLONK and AIR are 3 different arithmetic circuit / constraints systems ("backends"). All of these characterize NP and work using arithmetic over finite prime fields. Other ...
oberstet's user avatar
  • 447
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 ...
Alin Tomescu's user avatar
  • 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 ...
Lev's user avatar
  • 468

Only top scored, non community-wiki answers of a minimum length are eligible