Skip to main content

Questions tagged [starks]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
132 views

Unable to understand Eli Ben Sasson's STARK arithmetization & proof example

This is from this video - https://www.youtube.com/watch?v=9VuZvdxFZQo Bob has a list of length $10^6$. Bob wants to convince Alice that every number in the list is between 1 & 10. Alice needs to ...
1 vote
1 answer
82 views

How does the verification step operations using FRI polynomial commitments in zk-STARKs?

I have been going through the lectures in ZKP MOOC here youtube series. I am trying to understand the zk-STARKs discussed in video ZKP MOOC Lecture 8: FRI-based Polynomial Commitments and Fiat-Shamir. ...
2 votes
1 answer
148 views

Use zk-STARK for post-quantum signature scheme?

Could you not use zk-STARK for a post-quantum signature scheme? Your private key is a random symmetric encryption key, your public key is the hash of the encryption key. To sign you run an algorithm ...
1 vote
0 answers
325 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 ...
1 vote
0 answers
59 views

How can we explain STARK with less math?

I am trying to understand STARK with not much math. I understand SNARK like this: Computation → Arithmetic Circuit → R1CS → QAP → zk-SNARK From the helpful article: https://z.cash/technology/zksnarks/ ...
3 votes
1 answer
142 views

STARKs for arbitrary computation

I have been reading Vitalik's series on STARKs recently (Part 1, 2 and 3). It is a nice and very understandable read for a layman like me. Brutal summary of my current understanding Vitalik outlines ...
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 ...
1 vote
1 answer
911 views

Why are zk-STARK quantum secure?

I have a rough idea of how STARK work, but I want to know which part makes them quantum secure. Is it because when the prover generates the proof they use the random number from the Merkle root, which ...
2 votes
1 answer
1k views

Is the STARK Curve a SafeCurve?

SafeCurves defines criterias for choosing safe curves in elliptic-curve cryptography. STARK Curve defines a Stark-friendly elliptic curve that can be used with ECDSA. I was wondering: Is the STARK ...
1 vote
1 answer
385 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 ...
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. ...
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 ...
1 vote
1 answer
269 views

Linear combination IOP for SNARK registers

The STARK paper says Our ZK-STARK uses a separate Reed-Solomon codeword for each register, leading to w many codewords, each of lower degree ...
4 votes
1 answer
581 views

Transparent Setup of SNARKs

The STARKs paper states Third, and most important, ZK-PCPs are transparent (or “public randomness” ), which means that the randomness used by the verifier is public; in particular, setting up a ...
2 votes
0 answers
58 views

Assumptions underlying the soundness of STARKs

STARKs have recently received quite a lot of attention due to their small proof size and supposedly simple assumptions. The paper introduction itself seems to mainly state that their construction is ...