Blockchain One Pager

important ppts

AMAs

Explore

Starkware

$icon picker$
Starkware Polynomials【Math major recommended】

The Magic behind STARK - Polynomials!

Let explore with Eli Ben-Sasson

Intro

Old account State A ———new account State B, 10k valid transactions

Everything includes polynomials in Stark, but why??

Prove any statement

Prove any statement

Prover

Verifier

OK to move A to B with 10k transactions

d1......dk

P1, P2.... deg(Pi)<=di

Randomly sampled x in [0,a-1], while here a is large like a<2^256

P1(x).....Pk(x)

decide yes or no

There are no rows in this table

⁠

Thm: Protocal has a one-side error (honest prover always suceeds)

Pr(error)< (10*deg)/a, normally a = 2^256

And #queries <<<< deg

This is transparent, no trust set up required (Better than SNARK)

With the T standing for "transparent"

ZK-STARKs resolve one of the primary weaknesses of ZK-SNARKs, its reliance on a "trusted setup"

Features of Polynomials

Are excellent error correcting nodes(keep info that is redundent)

redundent values = 0’s in a polynomial

poly of deg x cannot have more than x 0’s

Thm: For any messages m!=m’ of size d, their encoding must differ at |Evaluation domain| -d

⁠

Here, for polynomials f(x) with deg b, max # of distinct solution to f(x)=0 is b

While in the evaluation domain, if the (b-1)th point, f(x(b-1))!=0

then the value after (b-1)th point might influence the rest of function to wrong direction

A tiny change in a small data, like 9999th of 10000 has problem, spread out to a huge area, to be easily found【Succinctness】

Have efficient batch zero testing(Facilitates taking single sample many facts)

Make the Pr(cheater picking one #) small

⁠

Have mutiplication property【encode constrains about any computation】

⁠

If P(777) = 7, not 0 or 1

Then you cannot write C(P777(X)) = P~(X)*V(X) due to thm

Pr(error)< (10*deg)/a, normally a = 2^256, here deg<10^7

Achievements

Avoiding the need for elliptic curves, pairings and the knowledge-of-exponent assumption and instead relying purely on hashes and information theory;

This also means that they are secure even against attackers with quantum computers【No tech attack】

The size of a proof goes up from 288 bytes to a few hundred kilobytes

General ZKP

⁠

Proof you know f(x)=y, without revealing x

Public funtion f, public output y

Private input x

Example

You have a blockchain like Ethereum, and you download the most recent block.

You want a proof that this block is valid

You ask an existing full node to provide such a proof

x is the entire blockchain (yes, all ?? gigabytes of it)

f is a function that processes it block by block, verifies the validity and outputs the hash of the last block

y is the hash of the block you just downloaded

Suppose

Prove P(x) is an integer & 0≤P(x)≤9 for all x from 1 to 1,000,000

It needs 1,000,000 steps to check every points

If 999,999 fuiflills, but not the last one

Suppose C(a)=0 if 0≤a≤9 and is nonzero otherwise

so here, a = P(x), prove that you know P such that C(P(x))=0 for all x from 1 to 1,000,000.

Let Z(x)=(x−1)⋅(x−2)⋅…(x−1000000).

It's a known mathematical fact that any polynomial which equals zero at all x from 1 to 1,000,000 is a multiple of Z(x).

Hence, the problem can now be transformed again: prove that you know P and D such that C(P(x))=Z(x)⋅D(x) for all x.

So how does one prove this claim?

We can imagine the proof process as a three-step communication between a prover and a verifier:

the prover sends some information

then the verifier sends some requests

then the prover sends some more information

First, the prover commits to (ie. makes a Merkle tree and sends the verifier the root hash of) the evaluations of P(x) and D(x) for all x from 1 to 1 billion (yes, billion). This includes the 1 million points where 0≤P(x)≤9 as well as the 999 million points where that (probably) is not the case.

⁠

Z(x) = "public verification key", the verifier already knows

Aelects a random 16 x values between 1 and 1 billion, and asks the prover to provide the Merkle branches for and there.

The prover provides these values, and the verifier checks that

(i) the branches match the Merkle root that was provided earlier

(ii)C(P(x)) actually equals Z(x)*D(x) in all 16 cases

We know that this proof perfect completeness - if you actually know a suitable P(x), then if you calculate D(x) and construct the proof correctly it will always pass all 16 checks.

⁠