Questions tagged [starks]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
85 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 ...
LightTunnelEnd's user avatar
1 vote
0 answers
197 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
1 vote
1 answer
112 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 ...
user93353's user avatar
  • 2,179
1 vote
0 answers
52 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/ ...
manu muraleedharan's user avatar
3 votes
1 answer
136 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 ...
Matteo Monti's user avatar
  • 1,395
2 votes
1 answer
346 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 ...
jmcph4's user avatar
  • 121
1 vote
1 answer
716 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 ...
Fieldza555's user avatar
2 votes
1 answer
869 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 ...
oberstet's user avatar
  • 447
1 vote
1 answer
322 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 ...
Andrea Farneti's user avatar
2 votes
0 answers
146 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. ...
Bean Guy's user avatar
  • 722
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 ...
Paul Miller's user avatar
1 vote
1 answer
251 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 ...
Daniel Lubarov's user avatar
4 votes
1 answer
505 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 ...
Cryptonaut's user avatar
  • 1,066
2 votes
0 answers
57 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 ...
Cryptonaut's user avatar
  • 1,066