ty to ember for the casual talk / discussion!!!
/ zero knowledge proofs
prove you know something w/o having to reveal what that something is
applications:
private transactions, anonymous voting
proof systems
prover and a verifier
prover gives verifier a proof
define R(): a relation fun
takes a public set of parameters, called x, and a solution/witness called w
solution is private
the parameters are public (x)
proof system needs to satisfy properties:
1 - complete
i.e. if w is valid solution, R = 1
verifier needs to accept the proof
(completeness: if r is valid, verifier accepts the proof)
2 - soundness
if w is not a valid solution, verifier should reject with high probability
?: why high probability
in cryptography — information theoretic security
mathematically impossible to find the value
but what makes cryptography practical / performant / usable for us — we state security in terms of probabilities
it’s secure if it’s very hard for attacker to distinguish or retrieve something
3 - knowledge soundness property
if verifier accepts the proof, that must mean the prover must know what the solution (w) actually is
4 - optional: zero knowledge
the proof reveals nothing about w (the solution)
analogy:
R is the rules of sudoku
x is a particular puzzle instance
w is a solution for that sudoku puzzle
so: R(x,w) = 1
proving knowledge of an assignment
arithmetic circuit
turning an equation into a graph
how to represent instance / problem the witness/solution is solving?
examples of how to represent problems in this format: (arithmetic circuits)
e.g. range proof - can represent as polynomials
e.g. verifiable shuffle - prove permutations
range proof in transactions
want to prove that the exchange equals out (not creating/destroying money)
need to prove that the amount is >=0
use polynomials
zero-knowledge interactive proofs
schnorr: basis of schnorr signatures
sigma protocol — a set of proof of knowledge that greeks invented
i have a secret key
want to reveal that i have a secret key w/o revealing the key
show it to another person by providing a signature with the key
steps: ***
alpha is secret key, prover want to prover they know alpha
Y = alpha * G
Y is public key
alpha is the secret key
1 - R is commitment. R = r * G
r is random scalar in this group
G is a generator of the group
when you multiply r*G you get a public key, basically. a public commitment to that secret value
2 - verifier generates a random scalar, c
3 - prover computs s = r + c * a
4 - verifier checks:
s * G = R + c * Y
if equal, then verified
“discrete logs are hard”
schnorr proof of knowledge
using fiat-shamir
instead of sending c (verifier sending a random number in the interaction)
uses hashes
c = hash of the transcript of the protocol
steps:
same but:
we replace verifier sending c
c <- H(Y, R)
by sending the hash instead of generating a c,
c is “basically random”
hash — you know that the person on the other side can’t choose an incorrect value
fiat shamir transform — same property
result: prover can just send everything in one message
sigma protocol: s looks like the “back and forth” lol
you just send over s because you know all the other values
you both agree on H already so you can send all the values over in one interaction
fiat-shamir transform
original proof should be a public-coin proof
the random numbers being sent are public
allows for interactive -> non interactive
succinct NARGs -> zkSNARKS
succinct
an argument is only sound against computationally bound provers
how to make succinct?
PCP theorem + merkle trees
idea: turn everything into polynomials
zkSNARKS
hard part is succinctness
1 - turn problem into polynomials
2 - how do we prove that two polynomials are equal?
two polynomials that are different, are different in most places
two different polynomials of degree 1 intersect in at most 1 point
two diff polynomials of degree 2 intersect in at most 2 points
two different polynomials of degree n can intersect in at most n points
how to turn a problem into a set of polynomials you can input into zksnark?
kind of a grind lol
rank 1 constraint system (R1CS) representation of circuits
an equation of matrices in this form
Quadratic Arithmetic Program (QAP) - represent arithmetic equations
trusted setup: for ZKPs, some have trusted set up and some don’t
a result of doing a trusted setup, it can speed up the subsequent verifications
the fastest ZKPs today still require trusted setup
zkSTARKS: don’t require trusted setup
zcash: ceremony
downside of trusted setup: requires trusting someone to do the setup
zcash: there’s “toxic waste” — but failed to throw away something “toxic” that allowed ppl to double-spend counterfeit money
https://electriccoin.co/blog/zcash-counterfeiting-vulnerability-successfully-remediated/
need to generate parameter w certain properties
an intermediate of that process — that data can allow you to break the privacy guarantees of the system
should be thrown away — but if you have the intermediates, that lets you break the system
trusted setup:
1 - five ppl do diff parts on diff computer
2 - organized a mailing list and allowed anyone join the trusted setup, w the idea that if anyone is honest and throws away their thing, then you can’t break the system
limited set of ppl: each sets up a part of public and private key pair. everyone destroys the private keys at the end
but they kept some transcript value in the output/typo in the original paper. a lot of implementations just followed the paper
CRS: common reference string. output of the trusted setup, used in the subsequent proofs
?: how often do u have to do this trusted setup?
depends on the proof system
some proof systems require trusted setup, per transaction
others are trusted setup but transparent (zkSTARKs) and updatable
ppl can keep adding themselves to the trusted setup?
examples
constructions of zk proof systems:
e.g. zksnarks, bulletproofs, zkstarks, PLONK, halo, grof
considerations: proof size, prover work, verifier work, post-quantum, trusted setup
?: how big of a concern / soon is quantum computing?
discrete log problem — a lot of crytpography depends on this being hard
schnorrs algorithm — a quantum computer would make it easy to solve the discrete log problem
so if we have quantum computers fast enough, all these systems would be broken
how many qubits … how powerful does a qcomp need to be for cryptographic consideration?
100? 1000? qubits?
e.g. bulletproofs — rely on discrete log problem
very fat
but not post-quantum resistant
e.g. sha3
algorithms are not post quantum safe
some standards / working groups consider it when choosing a standard paik? algorithm
depends on the problem … the nature/scale … security assumptions, if the trade off is worth the extra complexity for post quantum resistance
e.g. penumbra
stark-ish
PLONK uses “Kate commitments”