This, by no means, is a thorough post covering all the topics. This is just my notes that I like to make while learning any new topic. I have tried attaching any good resource I found along the way.

## ECC

- ECDSA: Elliptic Curve Signatures - Practical Cryptography for Developers
- Elliptic Curve Cryptography: a gentle introduction

nonce: $r$

temp key: $R=r∗G$

Signature in ECDSA: $s=k_{−1}∗(h+r∗x)(modn)$

## EdDSA Algorithm

Used to sign arbitrary messages with private keys

- Public key, $PK:xG$
- Create temp key $R$ from random nonce, $r$: $R=rG$
- $e=Hash(R∣∣m)$
- $s=r+ex$

Public key is known, then send $m,R,s$ to other party

## EdDSA Verification

Known: PK, m, r, s

$s.G=r.G+ex.G=R+e.PK$

Other party calculates $e,s.G$ If $LHS=RHS$, then signature is correct

## ECDH (Elliptic Curve Diffie-Hellman)

Ways for two parties to exchange information without revealing their private keys

Let there be two parties Alex and Alice,

- Alex has $pk$: $x$, Alice has $pk$: $y$
- Generate public keys: $P_{alex}=xG$, $P_{alice}=yG$
- Send each other public keys
- Calculate new public key $P_{s}=P_{alex}∗y$ OR $P_{alice}∗x$

## Threshold Signature Schemes

Contrary to multi-sigs, these signature employ MPCs to create signatures using interactive multiple parties, thus not giving ownership of the asset to only one party while not blowing up computation needs.

## Shamir Secret Sharing

Secret $S$ is divided into $n$ *pieces* or *shares* $s_{1}+s_{2}+⋯+s_{n}$ such than any combination of any $k$ pieces is enough to recover the secret, but any $k−1$ pieces cannot recover $S$.

This is based upon polynomials such that any $k−degree$ polynomial can be uniquely identified using $k+1$ distinct points.

### Splitting $S$

- Generating polynomial $f(x)$ of degree $k−1$ over a finite field $F_{p}$
- generating distinct shares: $s_{i}=x_{i},f(x_{i})$

Polynomial is of the form:

$f(x)=S+r_{1}x+⋯+r_{k−1}x_{k−1}$

These $r_{i}$ coefficients are randomly sampled and the points are generated which are the shares.

### Recovering $S$

$S$ is recovered using Lagrange polynomial.

Putting $x=0$, gives us $f(0)=S$

### Pitfalls

**Zero-share**: Common pitfalls occur during share generation as any shareholder who gets $x_{i}=0$ has its share as $0,S$, thus revealing the secret.**Non-unique shares:**when generating secret back, the protocol needs to evaluate $x_{m}−x_{j}x_{m} $ , and if $x_{m}=x_{j}(modq)$, then $x_{m}−x_{j}$ doesn’t exist and protocol fails.

## Fiat-Shamir Heuristic

- Feige-Fiat-Shamir and Zero Knowledge Proof
- Non-Interactive Zero Knowledge Proof - GeeksforGeeks
- Ring Signatures (Part 1): Schnorr Identity Protocol
- Fiat-Shamir transformation

Method to convert interactive ZKP system into non-interactive system such that public verifiability is feasible and both prover and verifier doesn’t need to be online at all times.

Let *prover* prove to *verifier* that it possess $s1⋯sk$secrets co-prime to $N$, without revealing any of the number to verifier. Takes advantage of difficulty of calculating modular square roots as verifier can’t derive $s1$ from $v1$

## BLS Signatures

Comes under elliptic curve pairing based schemes which makes aggregation easier than other signature schemes like ECDSA, schnorr.

Two main things used in BLS signatures are:

### Hash to Curve

For BLS signature to work, message hashing has to be on the curve i.e. $H(m)$ has to be a point on the curve.

To do this, the method is to concatenate message incrementally with counter to try to find a point.

## Pairings

Signature/Proof of possession: $S_{X}=x.H_{G_{1}}(X)$

$e(S_{X},G_{2})=e(H’_{G_{1}}(X),X)$

## Commitment Schemes

Prover commits to a message and later opens it to reveal the content of the message without revealing it beforehand.

## Zero Knowledge Proof System

- Completeness/Liveness: If
*prover*is correct, it will eventually convince*verifier* - Soundness/Safety:
*prover*can only convince*verifier*if it’s correct - Zero Knowledge

### Proving Schnorr Signatures Are Zero-knowledge

Proving **completeness** is the easiest part in protocol, i.e. if the prover performs protocol honestly, verifier is able to verify it by just substituting g in schnorr signatures.

**Soundness** is done through another algorithm called * extractor* which is able to extract secret of the prover by tricking it. Note: it doesn’t actually reveal the secret but only proving that extractor can extract the secret by duping prover. Done through

*replay attack*on schnorr protocol.

**Zero-Knowledgness** is proven through a *simulator* which has no knowledge of the the secret and yet it is able to convince every verifier into believing that the statement is true. This has an **assumption** that *verifier* is **honest.** Done through rewinding a verifier so that prover knows challenge $c$

and forging false signature on the basis of it.

## References

- CS-355: Topics in Cryptography; Lecture 5: Proofs of Knowledge, Schnorr’s Protocol, NIZK
- GitHub - jlogelin/fiat-shamir: Zero Knowledge Proofs with Fiat-Shamir Heuristic in Solidity
- Lecture 1: Honest Verifier ZK and Fiat-Shamir: https://www.cs.jhu.edu/~susan/600.641/scribes/lecture11.pdf
- 0xPARC ZK Learning Group
- eth-research ZK learning starter pack
- Road to ZK