Questions tagged [snarks]
SNARKS (short non-interactive arguments of knowledge) are space efficient zero-knowledge proof that do not require input from a verifier.
119
questions
3
votes
0
answers
47
views
Linear Verification time for zk-SNARKs?
I've come across this paper that benchmarks the efficiency of zk-SNARKs, zk-STARKs and Bulletproofs.
The table on page 8 states that the verification time for zk-SNARKs is linear in the size of the ...
- 111
0
votes
0
answers
43
views
What's the simplest and most instructive polynomial interactive oracle proof?
I'm writing my thesis about Zero-Knowledge Proofs and I'm trying to write a short and instructive introduction to zk-SNARKs at the moment (I have to stay within a certain limit of pages).
I introduced ...
- 111
2
votes
0
answers
18
views
Is Spartan prover time shorter than Groth16?
I want to know whether in zkSNARK implementations, Spartan has a shorter prover time than Groth16. I know this must depend on a variety of factors like the underlying curve or the complexity of the ...
- 31
1
vote
1
answer
46
views
How is succinct verification for transparent SNARKs possible?
I am a bit confused as to how succinct verification is possible with transparent SNARKs (i.e., SNARKs without trusted setup).
As I understand it, a transparent SNARK proof $\pi$ allows a verifier ...
- 315
1
vote
0
answers
19
views
Can FRI in STARK be used in Spartan?
Can FRI in STARK be applied to multilinear polynomials? I am reading the paper ''Spartan: Efficient and General-Purpose zkSNARKs without Trusted Setup'' which mentions that Spartan requires a ...
- 73
0
votes
0
answers
24
views
Symmetric encryption that can be 'split'
I'm looking for a cheap symmetric encryption scheme that can basically be used as a signature scheme in zkSNARK.
I need two parties to jointly sign/encrypt to a message and prove to a third party in ...
- 31
0
votes
0
answers
30
views
How can a cryptographic primitive make a SNARK a zk-SNARK?
I'm currently reading this book by Justin Thaler that describes the process of constructing a zk-SNARK:
"Argument systems are typically developed in a two-step process.
First, an information-...
- 111
3
votes
1
answer
67
views
Why do SNARKs operate on arithmetic circuits?
I'm currently writing my bachelor thesis about zero-knowledge proofs. Right now I'm working on introducing SNARK's and in my approach I'm following this course that's available on youtube. In the ...
- 111
0
votes
0
answers
75
views
Where is the UltraPLONK paper?
I'm looking for the paper for UltraPLONK, the extension to Turbo PLONK that Aztec released in 2020. I'm seeing references to it in other papers (but with no link to the actual paper) and in social ...
- 31
0
votes
0
answers
47
views
Format of the circom output files - is it documented?
In the circom documentation, I found file formats for their input files, but I cannot find documentation format for their json exported output file.
I ran the following circom commands till the end of ...
- 2,262
1
vote
0
answers
43
views
Given powers of tau ; the veryfying and the proving key, how can I find the point [f] resulting from the trusted setup in Groth16?
For each circuits, Groth16 requires to compute a point $f$ such as $f=s×G$. While revealing the scalar $s$ used for computing $f$ would allow to produce fake proofs, $f$ can be exposed to the public.
...
- 240
2
votes
2
answers
107
views
Groth16 - Since the Circuit Specific Trusted Setup requires knowledge of the QAP, how does it not leak knowledge?
In the Groth16 paper, Page 14, the terms below have to computed as part of the circuit specific trusted setup
$$ \left ( \frac{\beta u_i(x)+ \alpha v_i(x)+ w_i(x)}{\gamma} ^{\ell}_{
i=0}, \frac{\beta ...
- 2,262
1
vote
1
answer
94
views
Why do many ZKSnarks divide the Inputs into Public & Private Parts?
Many zkSNARKS (for e.g. Groth16) divide the Inputs into 2 parts - the public parts & the private parts. I understand how some of the stuff in the solution vector is known to both prover & ...
- 2,262
3
votes
1
answer
87
views
Why are the expressions divided by 2 random elements $\gamma$ & $\delta$ in Groth16?
In Groth16 Page 14
The prover does
$C = \frac {\sum_{i = l+1}^m a_i ( \beta u_i(x) + \alpha v_i(x) + w_i(x)) + h(x)t(x)}{\delta} + As + r\beta − rs\delta$
And the verifier
$A \cdot B = \alpha \cdot \...
- 2,262
4
votes
1
answer
87
views
Why is the first coefficient set to 1 in both GGPR13 & Groth16 SNARKS?
From GGPR13
Section 7.1, Page 42
($v_0(x) +\sum_{k=1}^m a_k \cdot v_k(x)) \cdot (w_0(x) +\sum_{k=1}^m a_k \cdot w_k(x)) - (y_0(x) +\sum_{k=1}^m a_k \cdot y_k(x))$
If you notice, the term $a_k$ is ...
- 2,262
2
votes
1
answer
83
views
Zero-Knowledge in PLONK paper in prover round 3. Shouldn't the degree be less than n?
From the PLONK paper.
On page 29, in the prover algorithm round 3, we divide the quotient polynomial into three polynomials of degree < n. But when we add the blinding terms we add $X^n$.
The ...
- 21
1
vote
0
answers
28
views
Question about sum check protocol O notations when applied to SAT
When reading book titled "Proofs, Arguments, and Zero-Knowledge" by Justin Thaler, i have a question about why the prover run time is as following graph show(at most), because Table 4.1 show ...
- 63
2
votes
1
answer
202
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."?...
- 63
0
votes
0
answers
53
views
Questions about groth16 paper "On the Size of Pairing-based Non-interactive Arguments"
i have many questions when reading groth16 paper "On the Size of Pairing-based Non-interactive Arguments" and the following are some of those. As the following graph shows.
1, What is "...
- 63
0
votes
0
answers
41
views
Hash-based Polynomial Commitment Scheme for Small Polynomials
I am building a SNARK project which needs to use PCS (polynomial commitment scheme). Because of some constraints, I want the field of PCS to have no additional structures and thus I only want to use ...
- 1
0
votes
0
answers
32
views
In groth16, how restricting public Inputs to the prime field instead of the snark scalar field can be used?
Recently such an overflow was fixed in snarkjs but given the small difference between the 2 and that it was restricted to the prime field anyway, how could this be exploited ?
- 240
0
votes
0
answers
64
views
Is the PLONK paper incorrect? [duplicate]
I'm having some confuses while implementing the PLONK by following the instruction in the Plonk paper. Could someone please help me with it?
In step 6th of the "Verifier preprocessed input" ...
0
votes
1
answer
38
views
GKR & Sum-check Protocol - how are the random numbers split across different variables?
I am reading about GKR protocol from Justin Thaler's book - Proofs, Arguments & Zero Knowledge
Section 4.6.5 - Page 64 - Description of GKR Protocol
$S_0$ is the number of gates in layer 0.
$k_0 = ...
- 2,262
1
vote
1
answer
146
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}(...
- 2,262
1
vote
0
answers
75
views
How secure is this hash combination function for merkle trees?
I am exploring the class of functions that I have seen called "hash combination functions". These functions are arguably distinct from hash functions, generally providing second-preimage ...
- 111
0
votes
1
answer
58
views
Can Cryptographic Proofs Directly Attest to Function Call Results?
In systems where computations are performed in remote or potentially untrusted environments(e.g. Ethereum NaaS providers such as Infura), how can we gain confidence in the accuracy of the results? ...
- 101
2
votes
1
answer
298
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 ...
- 2,262
0
votes
1
answer
76
views
Sumcheck Protocol: How to represent a matrix as an MLE which takes row & column numbers as parameters?
This is from Justin Thaler's book - Proofs, Arguments & Zero Knowledge
Page 43
For it to make sense to talk about multilinear extensions, we need to view the adjacency matrix $A$ not as a matrix, ...
- 2,262
0
votes
0
answers
41
views
can ownership proofs be added to circuits to make them zk-snark resistant to quantum proof forgery attacks?
According to my previous question the proofs cannot be broken by quantum computation, you cannot obtain the witness of the generated zk-snark proof.
link to my previous question.
Now if the concern is ...
- 3
0
votes
1
answer
93
views
can secrets be deciphered from the proofs generated with ZK-Snarks if a quantum attack were plausible?
can secrets be deciphered from the proofs generated with ZK-Snarks if a quantum attack were plausible?
I understand the concern that ZK-snarks and some of their cryptography may be broken by quantum ...
- 3
1
vote
1
answer
105
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 ...
- 2,317
1
vote
0
answers
105
views
Encryption scheme with variable and provable key-length
I'm currently studying the possibility of a novel ransomware technique, where an adversary instead of forcing the victim to pay a ransom, forces them to brute force a key of given length and thus ...
- 253
1
vote
1
answer
110
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:...
- 477
1
vote
0
answers
46
views
How do we represent a Gate involving a constant to the left or right of the operator in PLONK?
Let's say I have the following equation to be arithmetised in PLONK
$x^3 + x + 5 = 35$ and the witness is $x = 3$
$3 * 3 = 9$
$9 * 3 = 27$
$27 + 3 = 30$
$30 + 5 = 35$
Now the 4th gate can be expressed ...
- 2,262
1
vote
0
answers
42
views
Disjunctive ZK Proof of knowledge of discrete log
I want to construct a non-interactive ZK proof that in a set of pairs of group (where the DDH-assumption holds true) elements:
$(g_1, Y_1), (g_2, Y_2), ..., (g_n, Y_n)$
, the prover knows at least one ...
- 21
1
vote
1
answer
112
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 ...
- 83
2
votes
1
answer
194
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$ ...
- 2,262
0
votes
1
answer
75
views
Why does the permutation polynomial have the First Lagrange base added to it in PLONK?
From the PLONK paper.
On page 19 & ahead, the permutation check is described.
In particular, on page 20, the protocol is described.
Step 5 of the check is described as
Verifier checks if for all $...
- 2,262
1
vote
0
answers
396
views
ZK-STARK soundness
I've been reading about ZK-STARK. There's an example that appears in several blogs. The most detailed explanation of that specific example which I have found so far is in this blog.
The description of ...
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 ...
- 156
0
votes
1
answer
379
views
R1CS and zkSNARK
so recently I've been exploring zk-SNARKs algorithm, and I have a maybe stupid question. For example, let's take $x^2+x+1$ and make an algebraic circuit from it:
$y=x*x$
$sum=x+1$
$out=sum+y$
(First ...
- 1
0
votes
2
answers
156
views
PLONK: Reducing the number of Field Elements Trick
From the PLONK paper.
Page 18
We describe an optimization by Mary Maller to reduce the number of $F$-elements in the proof from $M$. We begin with an illustrating example. Suppose $V$ wishes to check ...
- 2,262
0
votes
1
answer
253
views
PCD vs Recursive SNARK vs Non-uniform IVC
I was wondering if anyone could clarify the differences between PCD vs Recursive SNARKs(like pickles) vs Non-uniform IVC(like hypernova)
They all seem very similar to me
0
votes
1
answer
48
views
Is there a SNARK system that will give the same proof bytes for different witnesses?
Suppose the circuit is a hash function with the input being the pre-image (private) and the output being the digest (public). If one knows of a collision can they create 2 different proofs that are ...
- 5
0
votes
0
answers
63
views
Is it posible to generate SNARK of MPC share validity?
Assume we have a central issuing authority that sends each participant a share that reconstructs in key $P_k$. I.e. Shamir Secret Share with $2$ out of $N$ format where $N>3$.
This central ...
- 1
0
votes
1
answer
132
views
The Multiplication of z(x) and z(Xw) in the Quotient Polynomial from the PLONK
From the PLONK paper.
Page 29, Round 3
Why multiply z(x) and z(Xw) in the quotient polynomial? (why does internal wiring have to multiply input permutation)
Why the second term have to "shift by ...
- 156
1
vote
0
answers
88
views
How many pairings are needed to verify beta term in GGPR13 zk-snark? Pinocchio paper says 3 but I count 4
The Pinocchio paper contains a description of the GGPR protocol (Protocol 1), and states that verification requires "8 pairings for the $\alpha$ terms, and 3 for the $\beta$ term". However I ...
- 121
1
vote
1
answer
152
views
Which Rust library is recommended if I would like to implement PLONK? [closed]
I think it should have APIs for polynomials, FFT and bilinear mapping if KZG commitment scheme is used.
- 61
0
votes
1
answer
174
views
Verification in Bulletproof commitment scheme
I am reviewing the ZKP course, represented by the university of Berkley (https://zk-learning.org/). In pages 44 of lecture 6 that is attached below (https://zk-learning.org/assets/lecture6.pdf), the ...
- 181
1
vote
1
answer
54
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 ...
- 325