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?
• schwartz-zippel lemma
  • 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

• PLONK
  • stark-ish
    • PLONK uses “Kate commitments”