Questions tagged [snarks]
SNARKS (short non-interactive arguments of knowledge) are space efficient zero-knowledge proof that do not require input from a verifier.
62
questions
2
votes
1
answer
39
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/...
- 126
4
votes
1
answer
78
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 ...
- 91
1
vote
0
answers
37
views
About SNARKs general recipes (regarding required assumptions)
I'm following ZK MOOC: https://zk-learning.org/
After some previous readings about these topics, I was believing to have understood that, stated that non-interactivity isn't attainable in standard/...
- 645
3
votes
0
answers
42
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 ...
- 31
0
votes
1
answer
53
views
What is the need to convert simple polynomial to QAP in zk-SNARKs?
From Vitalik Buterin's Blogpost - Quadratic Arithmetic Programs: from Zero to Hero.
In the blog, a cubic equation:x**3 + x + 5 == 35 is chosen. It has been assumed ...
6
votes
1
answer
169
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 ...
- 2,249
4
votes
1
answer
89
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 ...
- 181
4
votes
2
answers
152
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 ...
- 2,249
5
votes
0
answers
310
views
How the mimc bug from circomlib was safely exploited in practice?
Several years ago, there was an unenforced constraint on verification in the cirmcomlib library : a tool for building projects using ZsNarks. The error allowed to forge cryptographic nullifiers/proofs ...
- 175
1
vote
0
answers
24
views
zk snark desgined for Exponentiation computation
I know that there are papers for both theoretic and practical zk snark computation. And most of them could support general computations. i.e: support multiplication and addition
But what I am ...
- 109
2
votes
1
answer
40
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 : ...
- 41
0
votes
0
answers
53
views
How to add unused public signals in circom
In my usecase, i want to attach a public key to a proof generated by a circom circuit. If my circuit is like follows:
...
1
vote
1
answer
137
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 ...
- 111
0
votes
0
answers
44
views
How to validate a proving key and verification key are generated correctly in SNARKs?
If Alice does the trusted setup, how does Bob validate the proving key and verification key are well formed, i.e., they are actually a pair derived from the said circuit and same toxic waste? Alice ...
- 145
0
votes
0
answers
68
views
Compiling a ZK-SNARK into a Signature of Knowledge by way of FS/BCS transformations
In a sigma protocol, a well known transformation to a signature is Fiat-Shamir, where message derived randomness is mixed into the randomness of the challenge. A natural example is Schnorr signatures. ...
- 373
0
votes
1
answer
57
views
Privacy-conserving prover delegation in ZKP
If a user cannot generate a proof locally for a large circuit in SNARK in his phone or browser, he can delegate it to a server. However, he has to tell the witness to the server(s), which violates the ...
- 145
0
votes
0
answers
22
views
Is it possible to reuse someone else's PLONK reference string?
So PLONK has "universal updateable public parameters". Does that mean that you can copy it from someone else as long as the max degree is sufficient?
For example, Dusk Network updates the ...
- 121
1
vote
0
answers
164
views
Creating a basic SHA256 hasher in Circom
I want to create a SHA256 hasher in Circom so I can validate that a person knows the pre-image of a SHA256 hash without revealing the pre-image. This is my current code but it doesn't work:
...
0
votes
1
answer
278
views
Simplest recursive SNARK working example
I have been doing some research into recursive SNARKs. But I haven't found a working code example such as this one using Zokrates or this one using snarkjs. Anyone knows one such example, say, for ...
- 145
2
votes
0
answers
32
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 ...
- 243
0
votes
1
answer
44
views
Unsolveability of the quintic on SNARK
All examples I find on SNARKs show polynomials of up to degree 3 or 4 but what about polynomials of degree over 5, what is the mechanism that allow SNARK not to be affected by the unsolvability of the ...
- 101
1
vote
0
answers
52
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 ...
- 145
0
votes
0
answers
28
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 ...
- 23
2
votes
1
answer
63
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 ...
- 23
1
vote
1
answer
155
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 ...
- 11
1
vote
0
answers
100
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 ...
- 335
0
votes
0
answers
157
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 ...
- 1
0
votes
0
answers
14
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 ...
1
vote
0
answers
259
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 ...
- 111
0
votes
1
answer
82
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 ...
- 2,249
1
vote
1
answer
81
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$, $\...
- 190
1
vote
1
answer
146
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 - https://arxiv.org/pdf/1906.07221.pdf
In section 4.5, the pdf explains how to represent the following operations
$a$ x $b = r1$
$...
- 2,249
1
vote
1
answer
112
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 ...
- 2,249
1
vote
1
answer
187
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 ...
- 2,249
1
vote
1
answer
107
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 - https://arxiv.org/pdf/1906.07221.pdf
Here the Prover knows a polynomial of degree 3, 2 of the solutions of the polynomial are 3 &...
- 2,249
1
vote
2
answers
158
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 ...
- 2,249
1
vote
0
answers
48
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: ...
- 1,365
1
vote
1
answer
239
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 ...
- 131
1
vote
0
answers
143
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,...
- 11
2
votes
2
answers
214
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 ...
- 57
2
votes
0
answers
126
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.
...
- 593
4
votes
1
answer
222
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{...
- 227
0
votes
0
answers
228
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 ...
- 145
4
votes
1
answer
598
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 ...
- 593
1
vote
1
answer
98
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), ...
- 13
3
votes
1
answer
479
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 ...
- 316
6
votes
3
answers
2k
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 ...
- 161
4
votes
1
answer
689
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?
- 229
1
vote
1
answer
317
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 ...
- 561
1
vote
1
answer
825
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 ...
- 11