Questions tagged [snarks]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
29 views

Verifiable computation examples where verification is much faster than re-execution

Verifiable computation (VC) has been practical since Pinocchio and the field has evolved significantly since. What are some of the best examples today where computation is significantly faster than ...
user avatar
0 votes
0 answers
19 views

Pinocchio protocol: what if no extractability check

In Pinocchio protocol, prover submits extractability terms below so that counterfeiting fake proof is infeasible under q-PKE assumption. But, I don't understand why it is even necessary. What kind of ...
user avatar
  • 23
2 votes
1 answer
40 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 ...
user avatar
  • 23
1 vote
1 answer
77 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 ...
user avatar
1 vote
0 answers
45 views

Extractor in knowledge-soundness vs extractor in witness-extended emulation

In the knowledge soundness definition page 8 of Groth16, it says: The extractor gets full access to the adversary’s state, including any random coins. My question is why full access? Why we just don't ...
user avatar
  • 315
0 votes
0 answers
61 views

Can a circuit in a zk-SNARK be reversed-engineered?

The definition of zk-SNARK involves not leaking any information from the prover-verifier interaction, but what about leaking information from the circuit itself? e.g., could there be a circuit to ...
user avatar
  • 1
0 votes
0 answers
10 views

What do we mean by "Efficient Computing" of a Span Program (SP)?

I'm reading "Quadratic Span Programs and Succinct NIZKs without PCPs" and I'm having trouble understanding the "Efficiency" of a span program. I can see that a span program cannot ...
user avatar
1 vote
0 answers
85 views

What is required to verify a zk-SNARK?

I am trying to verify a zk-SNARK from a solidity contract offline, in Rust. This is the verifying contract that checks the proof in the solidity side. And this is the transaction that carries the ...
user avatar
0 votes
1 answer
63 views

zkSNARKs: Doing the setup for the Single Variable Operand Polynomial

I am reading this explanation of zkSnarks written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf My question is about Section 4.6.1 Setup construct the respective operand ...
user avatar
  • 1,637
0 votes
0 answers
45 views

'NIZK arguments for quadratic arithmetic programs' of '[Groth16] On the Size of Pairing-based Non-interactive Arguments'

I wonder about the CRS of NIZK argument. I think [A]$_1$, [B]$_2$, [C]$_1$ is calculated using CRS. Instead of calculating A, B, C first and then calculating [A]$_1$, [C]$_1$, [B]$_2$. May I know if ...
user avatar
1 vote
1 answer
56 views

Proof of knowledge of constant discrete log in the bilinear setting

Consider a pairing $\mathbb{e}: \mathbb{G}_1\times \mathbb{G}_2\longrightarrow \mathbb{G}_T$ with generators $g_1$, $g_2$ for $\mathbb{G}_1$, $\mathbb{G}_2$ respectively. The groups $\mathbb{G}_1$, $\...
user avatar
1 vote
1 answer
131 views

zkSnarks: Ensuring that a variable has a single value across all the operations it is used in

I am reading this explanation of zkSnarks written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf In section 4.5, the pdf explains how to represent the following operations $...
user avatar
  • 1,637
1 vote
1 answer
76 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 ...
user avatar
  • 1,637
1 vote
1 answer
78 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 ...
user avatar
  • 1,637
1 vote
1 answer
71 views

zkSNARKS: What prevents the prover from chosing a different polynomial than the one he is expected to know

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf Here the Prover knows a polynomial of degree 3, 2 of the solutions of the ...
user avatar
  • 1,637
1 vote
2 answers
60 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 ...
user avatar
  • 1,637
0 votes
0 answers
36 views

Proving the output of a generic function

Is there any generic construction to prove the correctness of the output of a function? In other words, is there a general way to produce a witness for the statement $y = f(x)$? More formally, let $f: ...
user avatar
  • 1,341
1 vote
1 answer
107 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 ...
user avatar
0 votes
0 answers
62 views

Are zk-STARKs a Sigma protocol? Is the communication interactive? And other doubts

I've heard that STARKS are not a non-interactive protocol, if so: What is (briefly) the mechanism they use to operate? Can they be considered a Sigma protocol? Why SNARKs are not interactive, instead?...
user avatar
1 vote
0 answers
102 views

Why the Kate Commitment and the Algebraic Group Model is used a lot in zk-SNARKs proving system since 2019?

I am engaged in the research of zk-SNARKs. After I read some papers about zk-SNARKs, I realize the Kate Commitment and the Algebraic Group Model is used a lot since 2019. They are used in Sonic, Plonk,...
user avatar
2 votes
2 answers
172 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 ...
user avatar
  • 75
2 votes
0 answers
104 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. ...
user avatar
  • 511
0 votes
0 answers
18 views

Does libsnark support generation of a trusted setup/public parameters via MPC?

Secure Sampling of Public Parameters for Succinct Zero Knowledge Proofs states: We design, build, and evaluate a multi-party protocol for securely sampling encodings of random evaluations of certain ...
user avatar
  • 227
4 votes
1 answer
87 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{...
user avatar
  • 227
0 votes
0 answers
138 views

How does one construct a SNARK circuit for proving the knowledge of a SHA256 pre-image?

Usually one explains how the R1CS/QAPs and SNARKs work using examples of circuits with multiplication and addition nodes, and constructing polynomials from that is relatively straightforward. SHA-2 ...
user avatar
4 votes
1 answer
244 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 ...
user avatar
  • 511
1 vote
1 answer
57 views

ZK-SNARK basics: knowing t(x), what prevents the prover from creating random h(x) to forge L, R, and O

After reading a number of ZK-SNARK explainers from here, here, and here, I still don't understand a few things. The setup of the algorithm uses QAP to calculate polynomial P(x) = L(x) * R(x) - O(x), ...
user avatar
  • 13
2 votes
1 answer
273 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 ...
user avatar
  • 186
5 votes
3 answers
1k 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 ...
user avatar
  • 151
4 votes
1 answer
289 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?
user avatar
1 vote
1 answer
253 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 ...
user avatar
1 vote
1 answer
403 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 ...
user avatar
  • 11
0 votes
1 answer
150 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 ...
user avatar
  • 135
2 votes
0 answers
142 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$ ...
user avatar
  • 21
4 votes
1 answer
536 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 ...
user avatar
  • 65
1 vote
1 answer
179 views

Conditional decryption

Is it possible for one party to encrypt some data and have another party (unknown to the first party) view that original data if a certain condition is met? I cannot find any information about this ...
user avatar
  • 11
3 votes
1 answer
134 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: ...
user avatar
  • 177
1 vote
0 answers
138 views

two-to-one hash in libsnark, what is it "exactly"?

I'm reviewing this test which prepares a zero knowledge proof of the preimage of an hash: https://github.com/mariogemoll/libsnark-tutorial/blob/sha256/src/test-knowledge-of-preimage.cpp In my (wrong) ...
user avatar
  • 177
1 vote
0 answers
46 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 ...
user avatar
  • 386
4 votes
2 answers
171 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?
user avatar
  • 83
6 votes
1 answer
678 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 ...
user avatar
1 vote
1 answer
275 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 ...
user avatar
  • 223
1 vote
1 answer
281 views

Converting R1CS to QAP - checking the last step

from reading Vitalik Buterin's excellent post on creating a QAP from an R1CS, I understood to translate a function into three groups of vectors, the number of vectors being the number of "gates" or ...
user avatar
  • 223
0 votes
2 answers
101 views

Is security of zk-SNARKS related to the size of the arithmetic circuit they evaluate?

In the context of zk-SNARKS, we are given an arithmetic circuit $C$, public outputs $y_1, \ldots, y_n = \mathbf{y}$ and some public inputs $x_1, \ldots, x_ℓ$. The prover wants to prove knowledge of ...
user avatar
  • 386