Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

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
0 votes
0 answers
60 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" ...
Steve Nguyen's user avatar
0 votes
1 answer
29 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 = ...
user93353's user avatar
  • 2,235
1 vote
1 answer
97 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,235
1 vote
0 answers
65 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 ...
Justin Martin's user avatar
0 votes
1 answer
54 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? ...
MShakeG's user avatar
  • 101
2 votes
1 answer
151 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,235
0 votes
1 answer
59 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, ...
user93353's user avatar
  • 2,235
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 ...
dreamer's user avatar
0 votes
1 answer
88 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 ...
dreamer's user avatar
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
94 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 ...
limeeattack's user avatar
1 vote
1 answer
91 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
0 answers
45 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 ...
user93353's user avatar
  • 2,235
1 vote
0 answers
37 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 ...
drydrydesert's user avatar
1 vote
1 answer
77 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
2 votes
1 answer
175 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,235
0 votes
0 answers
42 views

What is the running time of precomputation for the PLONK zk-SNARK?

I have been looking for benchmarks on the precomputation phase of PLONK (https://eprint.iacr.org/2019/953.pdf), but found none. Is there a resource where one can get a feel for this? Either in terms ...
joakimb's user avatar
  • 243
0 votes
1 answer
62 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 $...
user93353's user avatar
  • 2,235
1 vote
0 answers
299 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 ...
artificial_inspector's user avatar
2 votes
0 answers
94 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
0 votes
1 answer
298 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 ...
alygg's user avatar
  • 1
0 votes
2 answers
148 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 ...
user93353's user avatar
  • 2,235
0 votes
1 answer
171 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
questionman123's user avatar
0 votes
1 answer
46 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 ...
Stent's user avatar
  • 5
0 votes
0 answers
56 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 ...
Peersky's user avatar
0 votes
1 answer
124 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 ...
Paul Yu's user avatar
  • 156
1 vote
0 answers
87 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 ...
Ethan's user avatar
  • 121
0 votes
0 answers
50 views

The PLONK Gate constraint equation seems to designed more for accomodating adding a constant in a Gate but not multiplying with a constant

From the PLONK paper. Page 23, 6 Constraint System The constraint system $C = (V, Q)$ is defined as follows. $V$ is of the form $V = (a, b, c)$, where $a$, $b$, $c \in [m]^n$. We think of $a$, $b$, $...
user93353's user avatar
  • 2,235
1 vote
1 answer
128 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.
Walker's user avatar
  • 61
0 votes
1 answer
148 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 ...
tesoke's user avatar
  • 181
1 vote
1 answer
44 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
3 votes
1 answer
183 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,235
3 votes
1 answer
69 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,235
2 votes
1 answer
111 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,235
1 vote
1 answer
157 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,235
1 vote
1 answer
162 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
2 answers
149 views

Where can I find 2 of the steps/proofs described in Dan Boneh's video on PLONK in the PLONK Paper? The 2 don't seem to match

This is Dan Boneh's video on PLONK - https://www.youtube.com/watch?v=vxyoPM2m7Yg I went through the video multiple times & also tried to go through the original PLONK paper - https://eprint.iacr....
user93353's user avatar
  • 2,235
1 vote
0 answers
30 views

Why do we need the random number in Pinochioo protocol compared with GGPR

I find it hard to fully grasp the whole Pinocchio protocol . I understand that the $\alpha$ s are for restricting the prover to compute only the corresponding set-up values. But it's not clear for me ...
Wang Linger's user avatar
2 votes
1 answer
52 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
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,235
1 vote
1 answer
60 views

Prod Check Gadget in PLONK - any polynomial which satisfies the prod check seems to be the trivial polynomial

In Dan Boneh's PLONK Video - https://www.youtube.com/watch?v=vxyoPM2m7Yg he refers to the Prod Check Gadget $\omega \in F_p$ is a primitive $k$-th root of unity ($\omega^{k-1} = 1$) $H = \{1, \omega, \...
user93353's user avatar
  • 2,235
1 vote
1 answer
101 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,235
2 votes
1 answer
105 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,235
0 votes
1 answer
82 views

Looking for the proof of the prod check gadget referred to by Boneh in his PLONK video

I am going through Dan Boneh's video tutorial on PLONK Polynomial IOPs - https://www.youtube.com/watch?v=vxyoPM2m7Yg He describes 3 type of proof gadgets he will use He gives a proof of the Zero Test ...
user93353's user avatar
  • 2,235
2 votes
1 answer
402 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
4 votes
1 answer
105 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
1 vote
0 answers
59 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/...
baro77's user avatar
  • 730
3 votes
0 answers
62 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
0 votes
1 answer
167 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 ...
INDUKURI MANI VARMA 21911012's user avatar
6 votes
1 answer
700 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,235