Skip to main content

Questions tagged [snarks]

SNARKS (short non-interactive arguments of knowledge) are space efficient zero-knowledge proof that do not require input from a verifier.

Filter by
Sorted by
Tagged with
10 votes
1 answer
1k views

Why invent new hash functions for zero-knowledge proofs?

Recently, new hash functions were invented. Their primary purpose is serving the needs of zero-knowledge proof systems. I'm talking about Poseidon-256, Starkad-256, etc. See the paper. What is the ...
Paul Miller's user avatar
7 votes
2 answers
2k views

How to construct a circuit in zkSNARK

I have a few questions about how to use zk-snark. Since the basic logic of using zk-snark is: using a circuit to represent a problem, generate an R1CS from the circuit, transform R1CS to QAP and then ...
Mkotori's user avatar
  • 95
6 votes
3 answers
3k views

Why it is said that “zk-SNARKs need a trusted setup” to work?

What is the meaning of a "trusted setup" in this context? It is often said all around that zk-STARKs and Bulletproofs does not require a trusted setup. How do zk-STARKs and Bulletproofs ...
Diving's user avatar
  • 161
6 votes
1 answer
1k views

Which is the relation between Zero-Knowledge Proofs of Knowledge and circuits?

With the risen popularity of Zero-Knowledge Proofs of Knowledge (ZKPoKs) such as Pinocchio, Groth16 and Sonic, to name some ZKPoKs that are popularly known as zk-SNARKs, I got engaged to understand ...
Bean Guy's user avatar
  • 742
6 votes
1 answer
716 views

Arithmetic Circuits to R1CS. Do we consider addition gates or not?

Here is Ariel Gabizon's Blog for the process of converting Arithmetic Circuits into R1CS - https://electriccoin.co/blog/snark-explain5/ Here, he writes We assume multiplication gates have exactly two ...
user93353's user avatar
  • 2,245
5 votes
1 answer
1k views

CRS vs SRS in zk-SNARK

Are Common Reference String (CRS) and Structured Reference String (SRS) is the same in preprocessing phase of zk-SNARK? Is there any difference between them?
blockByblock's user avatar
4 votes
2 answers
312 views

What would be the degree (or range of the degree) of the polynomial used in real life zkSnarks as used in blockchains?

I am reading this explanation of zkSnarks written by Maksym Petkus - Why and How zk-SNARK Works They work through the concept of zkSnarks using a polynomial which the prover knows & he has to ...
user93353's user avatar
  • 2,245
4 votes
1 answer
124 views

Why does the challenge need to be prime in Wesolowski's succinct argument of $y=x^{e}$?

In Wesolowski's VDF (verifiable delay function) a prover produces a pair $(x, y)$ and needs to argue to the verifier that the pair satisfies $y = x^e \pmod N$ for some $e$ computable to both. The ...
MERTON's user avatar
  • 181
4 votes
2 answers
276 views

Can zksnark prove DLP?

Can one use zksnark to prove the knowledge of a discrete logarithm? In another word, can zksnark (R1CS) encode exponentiation?
Sean's user avatar
  • 83
4 votes
1 answer
447 views

Definition of Circuit Satisfiability In The Context of zk-SNARKs

A standard theorem is that boolean circuit satisfiability is NP-complete (shown in CLRS, for example). I am interested in what these statements formally mean. From CLRS, I can cite that $$\text{...
cadaniluk's user avatar
  • 229
4 votes
1 answer
106 views

Make sure of Quadratic Arithmetic Program validity

In the process of learning zk-SNARKs, I'm faced with this problem: I understand why if the prover sends a polynomial $P$ that can be divided by $T$, the target polynomial, the prover knows a valid ...
upavloff's user avatar
3 votes
1 answer
187 views

PLONK: Why is the quotient polynomial multiplied by different powers of a challenge?

From the PLONK paper. Page 29, Round 3 The paper doesn't explain the need or the use of the quotient challenge $\alpha$. I understand why each of the polynomials is multiplied by $\frac {1}{Z_H}$ but ...
user93353's user avatar
  • 2,245
3 votes
1 answer
71 views

What does preprocessed polynomial mean in the context of PLONK?

The PLONK paper uses the term preprocessed polynomial a lot of times. For e.g. page 14 The protocol definition includes a set of preprocessed polynomials $g1, . . . , g_l \in F<d[X]$ Page 20 ...
user93353's user avatar
  • 2,245
3 votes
1 answer
97 views

How do I construct a recursive polynomial as required in PLONK?

I am going through Dan Boneh's video on PLONK - https://www.youtube.com/watch?v=LbpPCN-f_XA&t=952s At around 19 minutes, he gets to the Prod Check Gadget. Background: $\omega \in F_p$ is the ...
user93353's user avatar
  • 2,245
3 votes
1 answer
225 views

libsnark generator toxic waste

I'm looking through the test and examples of libsnark, let's take for example here: https://github.com/christianlundkvist/libsnark-tutorial/blob/master/src/test-gadget.cpp at line 19 there's: ...
T. Rossi's user avatar
  • 177
3 votes
1 answer
691 views

IS zk-SNARK not suitable for constructing anonymous authentication scheme?

zk-SNARK was a powerful tool for privacy-respecting e-cash. However, recent years, in the literatures about anonymous authentication scheme, such as group signatures, anonymous credential, blind ...
X.H. Yue's user avatar
  • 392
3 votes
0 answers
64 views

Arithmetic Circuit to Square Arithmetic Program (SAP)

I'm trying to figure out how to convert a circuit into a Square Arithmetic Program (SAP). This is to eventually use it for zk-SNARKs such as Groth16. I do however understand how to convert arithmetic ...
Dontmilkme's user avatar
2 votes
2 answers
246 views

A field element as the exponent of a group element

The R1CS constraints are expressed over finite fields. Many proofing systems, such as zk-SNARK, use prover keys such as $g^{\alpha^0}, g^{\alpha^1}, ..., g^{\alpha^n}$ where $\alpha$ is a field ...
Sean's user avatar
  • 99
2 votes
1 answer
181 views

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

From the PLONK paper. On Page 31, Point 6 Compute the Lagrange Polynomial Evaluation $L_1(\zeta) = \frac{\omega(\zeta^n - 1)} {n(\zeta- \omega)}$ I don't think this formula is correct. We have $n$ ...
user93353's user avatar
  • 2,245
2 votes
1 answer
114 views

Is the permuation check range in the PLONK Paper incorrect?

From the PLONK paper. On pages 19 & 20, the paper describes the prescribed permutation check in PLONK. ---------------------------------------------------------------------------------------------...
user93353's user avatar
  • 2,245
2 votes
1 answer
109 views

PLONK Product Check Proof. Why is the 2nd condition required?

I am going through Dan Boneh's video on PLONK - https://www.youtube.com/watch?v=LbpPCN-f_XA&t=952s At around 19 minutes, he gets to the Prod Check Gadget. Background: $\omega \in \mathbb F_p$ is ...
user93353's user avatar
  • 2,245
2 votes
1 answer
192 views

GKR Protocol - is it one Sum-Check per layer or is it one Sum-Check per gate?

I am reading about GKR protocol from Justin Thaler's book - Proofs, Arguments & Zero Knowledge On Page 59, In the first message, $P$ tells $V$ the (claimed) output(s) of the circuit. The protocol ...
user93353's user avatar
  • 2,245
2 votes
1 answer
433 views

What is the difference between those two KZG Polynomial Commitment Schemes?

In short what are the differences (pros & cons) between multiplying by powers of Tau (from this lecture https://youtu.be/tAdLHQVW) and raising to powers of Tau (from this lecture https://youtu.be/...
ShAr's user avatar
  • 160
2 votes
1 answer
42 views

How to prove that a line belongs to a final hash without knowing/re-hashing all other lines?

Let's suppose : I have a record/database (D) of 754 lines and each line correspond to a SHA256 hash.(Hn) I hash all this record to a final and unique SHA256 hash like this : ...
JeremyDEX's user avatar
2 votes
1 answer
443 views

Generic name for R1CS vs. AIR

In the zero-knowledge cryptography nomenclature, we have multiple representations of arbitrary computation suitable for submission to various proof backends (e.g. Groth16). Two specific examples ...
jmcph4's user avatar
  • 121
2 votes
1 answer
53 views

Can we pad witness of bulletproof and dory to be exponential size?

Bulletproof and dory reduce the witness size by a half during each interaction, until the witness is compressed to be only one element. But what about the witness is not precisely exponential size? ...
Walker's user avatar
  • 61
2 votes
1 answer
100 views

Pinocchio protocol: Is this equation meaning polynomial's dot product or multiplication?

In Pinocchio paper, I'm confused by the equation in section 2.2.1. (image below) Is the product of two polynomials $v_0(x)+\sum(cv(x))$ and $w_0(x)+\sum(c_w(x))$ of dot product or just a simple ...
crypton's user avatar
  • 23
2 votes
1 answer
631 views

Examples of flattening code to create an R1CS

When preparing logic for use in a zkSnark, one needs to first "flatten" the code so it can be written as a series of constraints. I'm finding it hard to find examples of doing this. For instance, how ...
simbro's user avatar
  • 263
2 votes
0 answers
95 views

PLONK: Rationale Behind Specific Polynomial Evaluations in Round 4

In round 4, protocol evaluates a(zeta), b(zeta), c(zeta), Sσ1(zeta), Sσ2(zeta). I know linearisation trick in round 5 implies the identity of other terms. Can we ...
Paul Yu's user avatar
  • 156
2 votes
0 answers
42 views

Question about Ligero protocol

I have a question for those that might be familiar with the ligero protocol: Ligero In this protocol to be using an MPC in the head paradigm: described here. However, in the description of their ...
miraunpajaro's user avatar
2 votes
0 answers
159 views

It is possible to verify the computation of a hash function without actually proving it in zero knowledge?

Let me first introduce the context: Let's say that we have a hash function evaluation: $$h = H(x, y),$$ where $x$ and $y$ are the public and the private input of the hash function $H$, respectively. ...
Bean Guy's user avatar
  • 742
2 votes
0 answers
233 views

Efficiently prove the correctness of Paillier encryption in or "outside" a zk-SNARK

I'm working with a zk-SNARK library [1] that allows me to prove the correctness of arbitrary arithmetic circuits, and I now want to use these zk-SNARKs to prove that some Paillier [2] ciphertext $c$ ...
rogermb's user avatar
  • 21
1 vote
1 answer
388 views

Difference between a Polynomial Opening & a Polynomial Commitment

Going through the literature led me to think I understood the difference between these two things, but thinking about I am not actually certain. Could you help me correct my definitions of these two ...
Sandstar's user avatar
  • 155
1 vote
1 answer
103 views

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

I am going through Dan Boneh's video on PLONK - https://www.youtube.com/watch?v=LbpPCN-f_XA&t=952s At around 19 minutes, he gets to the Prod Check Gadget. Background: $\omega \in \mathbb F_p$ is ...
user93353's user avatar
  • 2,245
1 vote
1 answer
218 views

Why is the SHA256 in libsnark so slow?

When I use the merkle proof example of libsnark, I find that it takes more time to calculate the merkle tree than to calculate the proof. As shown in the log below, it takes 0.04s to calculate a ...
ZhuJerry's user avatar
1 vote
1 answer
384 views

Why Zk-SNARKs are Argument of Knowledge if a Knowledge Extractor exists?

From what I know, proving the existance of a Knowledge Extractor implies perfect soundness. So why in zk-SNARKs (and similar) we talk about Arguments of Knowledge, where the soundness property is only ...
Andrea Farneti's user avatar
1 vote
1 answer
384 views

Hash and (MAC) based signatures using zk-SNARK

I was wondering if we could use any general symmetric key MAC, a collision resistant hash $H$ and zk-SNARK (or any general NIZK scheme) to construct a signature scheme. I have a MAC key $k$, which is ...
Manish Adhikari's user avatar
1 vote
1 answer
113 views

GKR Protocol - does it matter which gate in each layer the SumCheck Protocol is run on?

I am reading about GKR protocol from Justin Thaler's book - Proofs, Arguments & Zero Knowledge Page 61, Lemma 4.7 $W_i(z) = \sum_{b,c \in \lbrace 0,1 \rbrace^{k_{i+1}}} add_i (z,b,c)\cdot (W_{i+1}(...
user93353's user avatar
  • 2,245
1 vote
1 answer
103 views

Recursive snarks with a genus-2 no-cycle hyperelliptic curve?

Any hyperelliptic curve having base field characteristic dividing group order? A subgroup of order equal to the basefield characteristic, a large prime? Having hard DLP in that subgroup? Having ...
Vadym Fedyukovych's user avatar
1 vote
1 answer
49 views

Any SuperSingular curve or similar with Fp = Fq which is not badly broken unless big field orders are used?

AFAIK, SuperSingular curves appear to be broken by MOV: A. J. Menezes, T. Okamoto and S. A. Vanstone, "Reducing elliptic curve logarithms to logarithms in a finite field," in IEEE ...
CPereez19's user avatar
  • 325
1 vote
1 answer
164 views

Question about the PLONK permutation check

From the PLONK paper. On pages 19 & 20, the paper describes the prescribed permutation check in PLONK. In the last step of the proof, these are the checks a) $L_1(a)(Z(a) - 1) = 0$ b) $Z(a)f'(a) =...
user93353's user avatar
  • 2,245
1 vote
1 answer
169 views

How exactly bilinear pairing multiplication in the exponent of g is used in zk-SNARK polynomial verification step?

I am reading this explanation of zkSnark written by Maksym Petkus - https://arxiv.org/pdf/1906.07221.pdf In page 24, the zk-SNARK of polynomial is explained. In setup phase, the proving and ...
INDUKURI MANI VARMA 21911012's user avatar
1 vote
1 answer
182 views

zkSnarks: Why does the target polynomial $t(s)$ need to be kept a secret if it's known to both prover & verifier?

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf The example used here is that there is a polynomial of degree 3 which the ...
user93353's user avatar
  • 2,245
1 vote
1 answer
303 views

zkSNARKS: If we are already using Homomorphic Encryption/Hiding, why is the shift by $\delta$ required for Zero Knowledge?

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf From Section 3.5 Because verifier can extract knowledge about the unknown ...
user93353's user avatar
  • 2,245
1 vote
2 answers
342 views

zkSNARKS - unable to understand the usage of polynomial to verify some condition

From Vitalik Buterin's Blogpost - An approximate introduction to how zk-SNARKs are possible From the sub-topic "Comparing a polynomial to itself", I understood till here In other words, any ...
user93353's user avatar
  • 2,245
1 vote
1 answer
1k views

Construction of R1CS vs QAP

I have been following the medium post of Vitalik, where he shows step by step how to convert program --> Circuit --> R1CS --> QAP. I am aware of the Pinocchio protocol, where they utilize the ...
emrsrb's user avatar
  • 11
1 vote
1 answer
129 views

Fixed variable in Groth16

In the paper On the Size of Pairing-based Non-interactive Arguments by Jens Groth, it is always referred in the equations to satisfy that $a_0 = 1$ and the others $a_1, ..., a_m \in \mathbb{F}$. I am ...
Binou's user avatar
  • 408
1 vote
1 answer
78 views

Question about P and NP problem

There is a definition for NP shown below. Could anyone please explain why "By restricting the definition of NP to witness strings of length zero, we capture the same problems as those in P."?...
fa william's user avatar
1 vote
1 answer
96 views

Amplifying the completeness and soundness of a proof scheme

A (interactive) proof system for a language $\mathcal{L}$ is defined by two algorithms $\mathcal{P}$, a prover, and $\mathcal{V}$, an efficient verifier, with the following requirements: Completeness:...
vxek's user avatar
  • 467
1 vote
1 answer
83 views

Practical feasibility of proving a plaintext hash relationship with a zk-SNARK

I am interested in the practicality of using generic SNARK techniques to prove the following relation. Let E and E' be two ...
884d88baaa's user avatar