[区块链]Knowledge Point List

A. Some References

1. Jonathan Katz and Yehuda Lindell，Introduction to Modern Cryptography
2. Dan Boneh，A Graduate Course in Applied Cryptography
3. Oded Goldreich，Foundations of Cryptography I、II

B. Four Stages of Cryptography Applications

1. symmetric-key cryptography：secret communication through shared key
2. public-key cryptography：secret communication without shared key、电子签名
3. blockchain technology and Decentralization Vision
   virtual TTP in half，trust without privacy；实现了可信方的部分功能，但没有实现隐私性
4. Private-Preserving Computation (Advanced Cryptography：ZKP、FHE、MPC)
   virtual TTP complete，trust in full privacy；

C. Further Elaboration of the Above Points

1. DES as the industrial standard of symmetric cryptography in 1970s，later upgraded to AES，key length 128, 192, 256
2. Hash functions，Merkle trees
3. Diffie and Hellman, New Directions in Cryptography, 1976
4. Diffie-Hellman key exchange protocol，hardness of discrete logarithm in finite fields
5. Public-key cryptography, public-key and private-key，digital signature (identity authentication, data integrity, non-repudiation)
6. CA，PKI，SSL/TLS，https
7. Rivest, Shamir, Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, 1978
8. RSA algorithm，hardness of factoring
9. Combining public key cryptography with symmetric cryptography (for its efficiency)
10. Many technologies in private-preserving computation：ZKP，FHE，MPC，trusted execution environment (TEE)，federated learning (FL)，differential privacy (DP)，private AI

D. Blockchain Basics

1. Satoshi Nakamoto，Bitcoin：A peer-to-peer electronic cash system，2008
2. Blockchain，bitcoin white paper，the main purpose：to replace TTP
3. Transaction，solution of double spending problem by the construction of time stamp
4. PoW：consensus by proof of work，the rule of the longest chain，security of the system
5. Mining as an incentive mechanism (including transaction fee)
6. Lack of privacy and Satoshi Nakamoto’s attempt to deal with it，which is inadequate
7. Three vital weaknesses of the original blockchain design：limited computational capacity，limited storage capacity，nearly no privacy，insufficient for real business applications（每个区块只记录7笔交易）
8. Zero Knowledge Proof as the key technology to solve the above problems

E. Math Preparation: Discrete Logarithm and Pairing

1. finite field F q = Z / p Z = { 1 , 2 , … , q ? 1 } F_q=Z/pZ=\{1,2,\ldots,q-1\} Fq?=Z/pZ={1,2,…,q?1}，its multiplication group F q ? = { 1 , 2 , … , q ? 1 } F_q^\ast=\{1,2,\ldots,q-1\} Fq??={1,2,…,q?1}，subgroup $G?F_q^{?}$ of prime order $p$， G = { e , g , g 2 , … , g p ? 1 } G=\{e,g,g^2,\ldots,g^{p-1}\} G={e,g,g2,…,gp?1}，hardness of discrete logarithm in $G$
   mZ是个啥？
   Z/pZ是啥?
2. Example：let $q=11$， F 11 = { 0 , 1 , 2 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } F_{11}=\{0,1,2,4,5,6,7,8,9,10\} F11?={0,1,2,4,5,6,7,8,9,10}， F 11 ? = { 1 , 2 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } F_{11}^\ast=\{1,2,4,5,6,7,8,9,10\} F11??={1,2,4,5,6,7,8,9,10}；Let $g=4$，then $g^2=16=5$，$g^3=20=9$，$g^4=36=3$，$g^5=12=1$；This means we have G = { e , g , g 2 , g 3 , g 4 } = { 1 , 4 , 5 , 9 , 3 } G=\left\{e,g,g^2,g^3,g^4\right\}=\{1,4,5,9,3\} G={e,g,g2,g3,g4}={1,4,5,9,3}，a group of order $p=5$
3. Elliptic curve $E$ over finite field $F_q$ which forms a group，subgroup $G?E$ of prime order $p$， G = { e , g , g 2 , … , g p ? 1 } G=\{e,g,g^2,\ldots,g^{p-1}\} G={e,g,g2,…,gp?1}，hardness of discrete logarithm in $G$
4. Exponential map $Exp:F_p\to G$ defined by $Exp\left(x\right)=g^x$，and discrete logarithm means the inversion of the exponential map，Hardness of discrete logarithm is not true in all groups；It is special to find such groups as in the above two cases
5. Pederson commitment，the trade-off between hiding and binding，additive homomorphic property
6. Zero knowledge proof through homomorphic property
7. In addition to the additive homomorphic property of the exponential map，a more special algebraic structure called pairing (also called bilinear structure) serves to facilitate some multiplicative homomorphic property
8. Three groups： G 1 = { e , g 1 , g 1 2 , … , g 1 p ? 1 } G_1=\{e,g_1,g_1^2,\ldots,g_1^{p-1}\} G1?={e,g1?,g12?,…,g1p?1?}， G 2 = { e , g 2 , g 2 2 , … , g 2 p ? 1 } G_2=\{e,g_2,g_2^2,\ldots,g_2^{p-1}\} G2?={e,g2?,g22?,…,g2p?1?}， G T = { e , g T , g T 2 , … , g T p ? 1 } G_T=\{e,g_T,g_T^2,\ldots,g_T^{p-1}\} GT?={e,gT?,gT2?,…,gTp?1?}，all of prime order $p$，with a map $e:G_1\times G_2\to G_T$ which satisfies the bilinear condition $e\left(x^a,y^b\right)={e(x,y)}^{ab}$，We can assume $e\left(g_1,g_2\right)=g_T$，this means $e\left(g_1^a,g_2^b\right)=g_T^{ab}$
9. ZKP for any quadratic relation：$\Sigma c_{ij}{x}_i{x}_j+\Sigma c_k{x}_k+c=0$，by exponentiation with $g_T$

F. Zero knowledge Proof General

1. Goldwasser，Micali and Rackoff，The Knowledge Complexity of Interactive Proof-Systems，1985
2. Goldreich，Micali and Wigderson，Proofs That Yield Nothing But Their Validity or All Languages in NP Have Zero Knowledge Proof Systems，1986
3. Vanishree Rao，Zero-knowledge Proofs-An Intuitive Explanation，2019
4. ZKP for 3-coloring of graph by physical procedure (board and coins)
5. The essential elements of the above physical procedure：hiding and binding，which corresponds to the cryptographic primitive：commitment scheme
6. NP-problem，general formulation of ZKP，proof without giving full evidence (witness)
7. ZKP for discrete logarithm，$g^w=y$，$P$ has solution $w$ and randomly splits it into two parts as $w=w_0+w_1$，which gives $g^{w_0}=y_0$ and $g^{w_1}=y_1$ satisfying $y_0{y}_1=y$；$P$ sends $y_0$ and $y_1$ to $V$ for verification，and $V$ can randomly choose a bit $b=0$ or $1$，and ask for $w_b$ for verification；The above can be repeated many times till $V$ is convinced
8. To convert the above proving process into non-interactive proof，choose some hash function $H$ and try to use $b=H({g,y}_0{,y}_1)$ to simulate $V’s$ challenge；The idea is to let $P$ alone do all the computation，$P’s$ can try to cheat by trying different fake split $w=w_0+w_1$ where one of the $w_b$ is good ($g^{w_b}=y_b$)，but the other is fake，and try to find a desired $b$ which allows it to pass the test
9. To overcome this problem，in the original protocol，replace the bit $b$ (which represents two possible outcome that can be exhausted by a few random trails) by a value $c$ that has too many possible values to be exhausted；Instead choosing $b$ and ask for $w_b$，$V$ chooses $c$ and asks for $w_c=\left(1?c\right)w_0+c{w}_1$，which needs to satisfy $g^{w_c}=g^{\left(1?c\right)w_0+c{w}_1}=y_0^{1?c}?y_1^c$
10. In fact，with this change，there is no need to do many rounds of challenges and responses as in the cases of using $b$，one round is enough；Suppose $c$ has $N$ possible different values，$P’s$ faces the challenge of providing all correct $w_c=\left(1?c\right)w_0+c{w}_1$ values for these $N$ possible $c$ values，depending on $V’s$ random choices；But for this，$P$ only needs to know $w_c$ for two different $c$ values，which implies the knowledge of both $w_0$ and $w_1$；To prove this is easy；Because if this were not true，it would mean that $P$ only knows $w_c$ for one value of $c$；This means with random choice of $c$，the probability of failure is $(N?1)/N$；If $N$ is big enough，one round will do the job
11. With the above change from $b$ to $c$，will can use $c=H(g,y_0,y_1)$ to do the non-interactive version；$P$ can compute the transcript $\pi =(g,y_0,y_1,w_c)$ and send to $V$；$V$ will verify：1) $y_0{y}_1=y$，2) $g^{w_c}=y_0^{1?c}{y}_1^c$，where $c=H(g,y_0,y_1)$
12. General formulation of interactive proof process：
    $P$ sends $m_0$ to $V$
    $V$ sends $c_1$ to $P$ ($c_1$ is a random challenge)
    $P$ sends $m_1$ to $V$ ($m_1$ is a response to the above challenge，and needs to pass $V’s$ verification)
    $\dots \dots$
    $V$ sends $c_k$ to $P$
    $P$ sends $m_k$ to $V$
    In the above process，$c_l$ is sent after $m_0,m_1\dots ,m_{l?1}$ has already been sent and cannot be changed
13. Fiat-Shamir heuristic：$P$ computes $c_1=H(m_0),c_2=H(m_0,m_1),\dots ,c_k=H(m_0,m_1,\dots ,m_{k?1})$ all by itself，and let $\pi =(m_0,m_1,\dots ,m_k)$ and send to $V$ for verification
14. the key point is the formula $c_l=H(m_0,m_1,\dots ,m_{l?1})$，which implies once $c_l$ is decided，$m_0,m_1,\dots ,m_{l?1}$ cannot be manipulated

G. Math Preparation: Polynomial Algebra Over Finite Field $F_p$

1. Lagrange interpolation of polynomial over $F_p$
2. Schwartz-Zippel lemma and its magical use in cryptography：testing the validity of polynomial equation by a random evaluation point
3. Elementary lemma which converts polynomial equations on a subset $S?F_p$ into polynomial satisfiability conditions on $F_p$

H. zk-SNARK

1. Parno，Howell，Gentry，and Raykov，Pinocchio：Nearly Practical Verifiable Computation (2013)
2. Ariel Gabizon，Williamson and Ciobotaru，Plonk：Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge (2019)
3. Two different lines of research in cryptography：1) general theory，which aims to prove general theorems in terms of the asymptotic complexity of algorithms； 2) the construction of practical algorithm，which must achieve practical usability under current hardware and other engineering conditions
4. Four aspects of understanding ZKP：1) ZKP for specific problems such as 3-colouring of graph and discrete logarithm；2) general theory of ZKP，which is quite complex and rich；3) practical schemes such as zk-SNARK；4) practical application cases such as ZCash
5. zk-SNARK presents present day’s mainstream of practical zero knowledge proof schemes
6. Performance：proof time，proof size，verification times，setup cost，circuit dependence
7. Security：universal / updatable setup，quantum resistance
8. The concept of commitment：binding and hiding，commitment construction by DL (离散对数)，Pederson commitment
9. Converting any NP-problem (within a fixed size) into Boolean circuit and arithmetic circuit
10. Arithmetization：converting circuit satisfiability problem into polynomial satisfiability conditions

I. ZKP’s Applications

1. Verifiable random function (VRF)：given a public input and the private key $sk$ of $P$，compute value $v=F(x,sk)$, and a proof $\pi =\pi (x,sk)$；The correctness of $v$ can be verified by anyone using public key $pk$ of $P$，namely that $V(x,v,\pi ,pk)=0/1$；VRF gives unpredictability，verifiability and privacy (no extra information about the private key $sk$ can be gain)
2. VRF can be used to construct decentralized lottery，which is essential in PoS consensus in blockchain
3. Zcash：the first fully anonymous crypto currency，and also the first large scale deployment of ZKP in real world application scenario
4. Application cases in blockchain technology：1) Ethereum scalability through zk-rollup；2) FileCoin and storage proof；3) Dusk and the trading of real world assets (securities)；4) Mina and recursive proof；5) Dfinity and internet computer

J. Brief Introduction to MPC

1. Shamir，Rivest and Adleman，Mental Poker，1979
2. Andrew C. Yao，Protocols for Secure Computations，1982
3. Andrew Chi-Chih Yao，How to Generate and Exchange Secrets，1986
4. Algorithms for solving the millionaire’s problem，and mental poker problem，their significance：the origin of decentralization which precede blockchain by 30 years
5. Yao’s Garbled protocol for 2-party，many practical optimizations
6. Secret sharing and n-party protocol，general theoretical results of MPC，Beaver triples and other optimizations.

ON DATA BANKS AND PRIVACY HOMOMORPHISMS

1. Rivest，Adleman and Dertouzos，On data banks and privacy homomorphism，1978
2. David，Wu，Fully Homomorphic Encryption：Cryptography’s Holy Grail
3. Craig Gentry，A Fully Homomorphic Encryption Scheme，2009
4. FHE and the out-sourcing of computation
5. Arbitrary computation → Boolean circuit → arithmetic circuit over $F_2$ → multivariate polynomial over $F_2$
6. Somewhat homomorphic encryption scheme：$E\left(b\right)=qp+2r+b$ with large odd number $p$，random $q$ and small $r$；Then $r$ is the noise which increases by the operation of addition and multiplication；The computation can be carried on as long as the noise level of the computation result is within the limit of $2r<p/2$
7. Gentry’s ingenious idea of bootstrapping；Starting with a somewhat homomorphic encryption scheme, and assume a cyphertext $b^{?}$'s noise level is approaching the limit；Observe that $b=D(sk,b^{?})$，if the SWHE can evaluate the circuit (or the polynomial) corresponding to $D$ (with one more additional operation), one can obtain a lower noise encryption of $b$
8. Microsoft’s SEAL open-source library；Great performance improvements from the initial ${10}^{13}$ times of ordinary computation to ${10}^3$，after over 10 years of optimization efforts