Skip to content

On ZKPs, STARKS, SNARKS

General information on the topic of ZKPs, not necessarily structured but should be ongoing article as I continue to learn about this technology. These are just notes specifically from meetup on ZKPs.

Honest computation through Zero Knowledge Proofs is a set of steps. It is this complex math and application of the cryptographic primitives that are ultimately provide proofs. Forms of Zero-Knowledge proofs provide post-quantum secure, scalablity and privacy improvements to blockchain based, game theory driven software applications that can provide an honest deduction of the steps taken to reach a provable outcome.

There are three sets of zero knowledge proofs and their application are becoming more implemented for scaling and batching transactions sets:

  • SNARKS
  • STARKS
  • BULLETPROOFS

SNARKS

f(x) = y

Suppose that you have a (public) function f, a (private) input x and a (public) output y. You want to prove that you know an x such that f(x) = y, without revealing what x is. Furthermore, for the proof to be succinct, you want it to be verifiable much more quickly than computing f itself.

Snarkjs – Snark JavaScript

Circom – DML Language for creating circuits

Bellman – Rust Implementation

ZoKrates

ZKP Steps

  1. Trusted Setup
  2. Challenge
  3. Proof
  4. Verify

STARKS – STARKs (“Scalable Transparent ARgument of Knowledge” are a technique for creating a proof that f(x)=y where f may potentially take a very long time to calculate, but where the proof can be verified very quickly. With the T standing for “transparent”, ZK-STARKs resolve one of the primary weaknesses of ZK-SNARKs, its reliance on a “trusted setup”.

F(X, Y) = Z

F Any Function

X Public Input

Y Private Input

Y Public Outputs

BULLETPROOFS

BulletProofs(Range Proofs)

any number can be represented as inner product of two vectors

need at least 3 bits to represent 5 n has to be at least 3

That assignment of a is correct.

I am going to create a simple Zero Knowledge Proof Generator that can be spun up as a docker container and run as a serverless container.

honest multiparty computation across stakeholders

merkle path to the cover transactions entire blockchain

SNARK 288 bytes STARKS

ZKPs uses SNARKs

compress the blockchain using

Bulletproofs are used for proofs in monero

batching transactions using ZeroKnowledgeProofs

SNARKs

STARKs

Bulletpoorf

Bellman Rust Implementation

Circom (Iden3s)

Modular Math

diffie hellman

p=23(modulus)g=5(base)

RSA Choose 2 primes p-3 q -5

n=p*q=15

g is a number generator

wants to prove that she knows x, such that u y = g of x

and sends t that t = g of v

bob pics random c send to

ECDHE for https://

Abelian Group Properties for a set G

ECC – Multiplication

Logarithm Problem

ECC – Finate Fields & Discrete Logs

P+P = ? in a finite field

ECDSA signature

multiple private key by generator point and get the point

Pedersen Commitment basis for Grin

you could user Q = vG to “hash” or hide amounts per tx

Com(v) = vG+bH

Com(v1) = v1G+b1H

Com(v2)=v2G+b2H

STARKS

SNARKS – QAP

The are many variants of SNARKs

QAP variant(quadratic arithmetic program):

Computation -> Arithmetic Circuit -> R1CS

x + y + 4 = 10

without telling x or y

x*y

x*y=4

left input, right input and output.

Lagrade

L*R

L(x)*R(x) = O(x) for x in {1,2}

The prover would send evaluations of x for L,R,), and H polynomials

But how would we ensure that

1) This “x” is hidden

2) Prover actually uses its polynomials

doing operations on the encrypted number

challenger to send a challenge encrypted

use a polynomial to answer back.

Who knows what s was in plaintext

setup for this challenge that is encrypted and hardcoded in the entire system

How can we evaluate a value that is encrypted

Adding zero-knowledge:

blinding factors

Setup

Prover has L, R O and H polynomials

Prover sends E(L(s)), E(R(s)), E(O(s)),E(H(s))

Anyone in the network can verify it

Pairing of Elliptic Curves for the Verified

This went over the Pinnochio

SNARKs –

  • Research in pairings
  • Research in optionality of elliptic curves
  • Lattice-based SNARKs
  • Tokenized World Scenario
  • How do we scale this.

Scaling Blockchains

Layer 1

  • Polkadot
  • DFinity
  • Cosmos
  • Sharding
  • Pruning
  • PoS
  • Casper
  • State Rent
  • WASM WASM as core for scaling.
  • ZKPs

Layer 2

  • DApps
  • Plasma Cash
  • Ignis
  • RollUp

Layer 2 Scaling

  • Data on Chain
  • compression
  • Data Off cain
  • merkletrees
  • accumulators
  • vector commitments
  • ZKPs
  • Honest Proofs
  • signature aggregation
  • Fraud Proofs

Off-chain ZKPs

Honest ZKPs

STARK Batching

F(X, Y) = Z

F Any Function

X Public Input

 

More information:

starkware

snarkjs

circom DSL

zokrates

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: