Introduction to Blockchain

Lecture 2: Cryptographic Hash Function (Example: SHA256)

$\sum$指所有可能出现的字符. $\sum^* = \sum^0 \cup \sum^1 \cup …$。上面的数字指的是字符序列长度

$f: \sum^* \rightarrow \sum^n$ map from infinite to finite

Hash function characteristic:

• Collision-resistance: It is hard to find $x, y \in \sum^*$, s.t., $x \neq y$ and $f(x) = f(y)$

• Hiding: Given a hash value $h$, it is hard to find same $x$ s.t. $f(x) = h$

• Puzzle friendliness

---

Problem: Finding Files

I have huge files $F_1, F_2, …, F_n$. Given a new file, find if it exists in my files ($\exist F_i, F_i = F_{new}$)

Solution: Save $Hash(F_i)$ the same time when saving $F_i$

---

Problem: Ledger with hash pointers

node $o_1$ save the pointer to $Hash(o_2)$, then I can find $o_2$ by table. But it need to guarantee the immutability or if $o_2$ changes, we can no longer access it.

Create a link list of all the transactions.

$Tx_1$. When another transaction occurs, $Tx_1 \leftarrow Tx_2$. Bank creates $Tx_2$, and points to $Tx_1$. Then bank sends me an email of the information $Tx_2$ and hash of $Tx_2$. The pointer is $Hash (Tx_1)$. 这可以用来证明你进行了$Tx_2$，因为可以根据指针追溯到最本源的交易。

当银行想要更改$Tx_1$，那么$Hash (Tx_1)$需要改变，接着因为$Tx_2$ saves $Hash (Tx_1)$, $Hash (Tx_2)$ has to change, therefore $Tx_3$ has to change…

---

Commitment Scheme

Players $p_1, p_2, …, p_n$ have bids $b_1, b_2, …, b_n$ respectively

rule: No other ppl can see my bid and I can no longer change my bid.

Assume the cheater is powerful enough, he can know any bid of players.

We need to design a protocol to prevent cheating:

• Make sure the highest $b_i$ is found (需要知道谁胜出)
• No player can change their bid after seeing other players’ bids.
• Auditability: make sure every player can check through the protocol

Solution:

Hash function: $h$

Step 1: Every player computes his hash $h_i = h (b_i)$

Step 2 (commit): $p_i$ publishes $h_i$

Step 3 (reveal): After everyone commits, $p_i$ publishes $b_i$

保证所有人都commit且reveal，否则出局

Dealer可以根据reveal的$b_i$ compute $h_i$，防止有人两个publish的不是一个东西

Problem:

• When doing hashing, the domain should be larger (不然domain太小容易被猜出来)

Improvement:

Step 1: Every player $p_i$ chooses a random nonce $n_i$. $h_i = h (b_i | n_i)$

Step 2 (commit): $p_i$ publishes $h_i$

Step 3 (reveal): After everyone commits, $p_i$ publishes $b_i$ and $n_i$

但是dealer不是必须的，可以做成decentralized的。

---

Lecture 3: Merkle Trees

---

Problem

I am running a bank. The bank has two branches, HK and SH.

Let’s say there’s no internet but has computers and hash function.

Have a bunch of transactions (deposit) at HK branch, then they want ot get their money back in SH branch with their deposit proof

I can just send a short message from HK to SH to prove the deposit proof is true and 钱没被取出来过

And any leak of the short message should not have someone know the information about the deposits.

Assume the original channel is unsafe and expensive. 并且可能存在A存钱，但是B会copy A的存折去取钱的情况

Solution

First step, be clear about the properties.

Properties:

• Every deposit can be taken back
• No one can reclaim the same deposit twice
• Message $m$ going from HK to SH is really short
• $m$ does not leak any data
• Every depositor $i$ receives a proof $p_i$
• It is possible to verify every $p_i$ using $m$
• Additional property: short proof
• Additional property: privacy for depositor (一个depositor不会看到其他depositor的内容)

Suppose we have a ledger(账本)

When Alice deposits, she gives me a random number $n_1$. So Bob and Carol $n_2, n_3$ respectively. 此时我们将每个transaction的内容(name, amount of money…) hash起来而不是明确地表示出来，即$Tx_1$存储的是hash (Alice || \$100 || $n_1$)，那么此时就无法读取别人的内容了。

那么此时HK只需要向SH传输hash ($Tx_3$)，然后Carol带着$Tx_3$去SH取钱，SH计算$Tx_3$的hash值，并与$m$进行比对，同时Carol再提供自己的name以及amount of money，SH再将这些信息进行hash，并与$Tx_3$内的hash (Carol || \$150 || $n_3$)进行比对，则可以确定这笔钱确实是Carol的。

那么对于Alice，她则需要提供$Tx_3, Tx_2, Tx_1$，SH先分别验证$Tx_3, Tx_2$的真实性，最后通过Alice提供的name与amount of money数据来匹配$Tx_1$。

可以发现，上述过程每个人都不知道其他人的transaction的具体内容，都是hash。

However, 当transaction很多的时候，Alice要存的内容就非常多了，要存所有人的数据，那怎么解决这个问题呢？需要用Merkle Trees。


Merkle Trees正如图中所示，实际上就是一个二叉搜索树，将transaction的hash存作叶子结点的value，然后两个子节点的父节点的value是两个字节的value的hash，即比如子节点$l_1, l_2$，其father node的value即为$hash (l_1 || l_2)$。此时需要传输的message $m$即为根节点的value。

那么现在的问题就是，我们并没有传输整棵树，要怎么traverse这个Merkle Tree来判断$l_1$是否存在于树中呢？所以实际上，Alice需要给定$b_1, b_2, l_1, l_2, D_1$，SH将$b_1, b_2$进行hash，来判断他们是不是$m$的子节点；同样的，她需要提供$l_1, l_2$来判断他们是不是$b_1$的子节点。这样才能最终判断$D_1$在不在树中。

那么此时对于一个depositor，他需要存储的最多信息的长度就是$2\log n$

Lecture 4: Symmetric Encryption

Scenario: two people Alice & Bob. They want to communicate, but only with unsafe channel. Someone else may can read the messages. Suppose the ‘someone else’ is Eve.

Send a message $m$. The encrypted message $e$.

那么实际上Eve能看到的就是encrypted message $e$

在课程中红色标记的表示private，蓝色的是public

Definition:

A key $k \in \sum^*$ which is only known to Alice & Bob.

Alice knows a function $Enc_k: \sum^* \rightarrow \sum^*$ (编码器encrypte function)

Bobo knows a function $Dec_k: \sum^* \rightarrow \sum^*$ (解码器decrypte function)

$\forall m \in \sum^*, Dec_k (Enc_k (m)) = m$ (即解码编码后的message会得到原信息)

这叫做symmetric encryption

在当前时代下，我们认为这个编码器和解码器的function都是已知的，唯一未知的是key $k$

One-time Pad:

因为message实际上是二进制的，我们用$\oplus$表示xor，使得 $e = Enc_k (m) = m \oplus k$，$Dec_k (e) = e\oplus k$

$Dec_k (Enc_k (m)) = Dec_k (m \oplus k) = m$

Property:

Eve cannot figure out any message in $m$ from $e$, even one bit of $m$.

Security Analysis:

How to show Eve cannot find anything about $m$?

Eve sees $e$, $|e| = n$

For evey possible message of length $n$, there exists key $k_m \in \sum^n$, $Enc_k (m) = e$，此时 $k_m = m \oplus e$。这个性质是要保证他不是一对一映射，也就是说我拿到一个$e$，但是他有很多个可能的$m$和$k_m$的组合，以至于我几乎没法通过枚举猜出来。

但是，do not reuse the keys。因为比如我发两个message，$e_1 = m_1 \oplus k, e_2 = m_2 \oplus k$，那么Eve通过计算$e_1 \oplus e_2 = m_1 \oplus m_2$，那么Eve虽然不知道具体信息，但是可以gain some information about the messages，之后便可以通过枚举等方法尝试，所以是不那么safe的。

---

Key Exchange

首先Scenario和上面差不多。还是Alice，Bob传输message，Eve来intercept。

Alice has a secret $a$, Bob has a secret $b$. 他们想相互传输（exchange）secret。

他们目前想通过加密函数来互相传输以至于不被窃听。

• Alice computes $f(a)$ and sends it to Bob
• Bob computes $f(b)$ and sends it to Alice
• 此时Alice knows $a, f(b)$，Bob knows $b, f(a)$，Eve knows $f(a), f(b)$
• 那么此时，我们需要解决的就是，define $k$ to be a value that it is easy to compute $b$ by $a ~ \& ~ f(b)$, or compute $a$ by $b ~ \& ~ f(a)$, but impossible to compute $a$ or $b$ by $f(a) ~ \& ~ f(b)$
• 所以实际上Alice和Bob还额外知道一个$k$

这个算法叫做Diffie-Hellman Merkle Exchange

DH Exchange:

• Alice or Bob chooses a large prime number $p$ (这个$p$是public的) and sends it over。这个$p$在二进制下要尽可能长，要比你可能发送的最长信息的长度还要长。

• 同时他们再choose一个number $g \in \{0, …, p - 1\}$ s.t. $\{g^0, g^1, g^2, …, g^{p - 2}\} = \{1, 2, …, p - 1\}$。也将这个$g$相互发送。

  这个 $g$ 叫做primitive root

• Alice choose a secret $a \in \{0, 1, …, p - 2\}$

  Bob chooses another secret $b \in \{0, 1, …, p - 2\}$

• Alice computes $g^a \mod p$ and sends it to Bob

  Bob computes $g^b \mod p$ and sends it to Alice

• Alice computes $k = (g^b)^a = g^{ab} \mod p$

  Bob computes $k = (g^a)^b = g^{ab} \mod p$

Alice and Bob compute the shared secret they can use it as an encryption key, known only to them, for sending messages across the same open communications channel.

Now eve knows $p, g, g^a, g^b$ but needs to compute $k = g^{ab} \mod p$

Lecture 5: Basic Number Theory and ElGamal Encryption

Fermat’s little theorem

$a^{p - 1} \equiv 1 \pmod p, a \in [1, p - 1]$

Computing Primitive Roots

$p$ is a large prime number

find $g$ s.t. $\{g^0, g^1, …, g^{p - 2}\} = \{1, 2, …, p - 1\}$

How to check if $g$ a primitive root?

compute $g^0, g^1, …$ until a cycle is found. 但是显然，当 $p$ 很大的时候，是不可行的。

$o(g)$ = length of the cycle of powers of $g$ = smallest positive $i$ s.t. $g^i = 1 \pmod p$

我们需要证明的是，$o(g) = p -1$，而不是$o(g) < p - 1$。Apparently, 不管在什么情况下， $o(g) | p - 1$

facterize: $p - 1 = q_1^{\alpha_1}q_2^{\alpha_2}…q_r^{\alpha_r}$

那么实际上 $g$ 若不是primitive root的情况只有 $o(g) | \frac{p - 1}{q_1} \text{or} o(g) | \frac{p - 1}{q_2} \text{or} … $，因为这说明$o(g)$肯定小于$p - 1$。此时只需检查是否$g^{\frac{p - 1}{q_1}} \equiv 1 \pmod {p - 1} \text{or} g^{\frac{p - 1}{q_2}} \equiv 1 \pmod {p - 1} \text{or} …$即可，若其中一个同余1，则说明cycle提前结束了。

Fast Modular Exponentiation

接下来我们需要考虑如何compute $a^b \text{mod} c$

快速幂

现在则要回归最初始的问题——怎么找primitive root $g$？

Method: Choose a random value $g$, then check if it is a primitive root.

为什么这个随机算法可行呢？因为原根有很多个。I know there is at least one primitive root $g$，假设我们现在随机选了个数，他是$g^i$， 并且 if $i \perp p - 1$ then 我通过枚举 $i$ 来循环 $g^i$，最终会把所有数都循环一遍。

（找原根这部分目前没太懂，需补）

Modular Multiplicative Inverse

Fermat: $a \neq 0 \pmod p \Rightarrow a^{p - 1} \equiv 1 \pmod p$

which means $a \cdot a^{p - 2} \equiv 1 \pmod p$，这说明 $a^{p - 2}$ 是 $a$ 的乘法逆元 $\pmod p$

How to compute $a^{- 1} \text{mod} ~ n$ ?

If gcd (a, n) $\neq$ 1, then $a$ has no inverse.

重回正题

现在我们假设Alice或者Bob其中一人是offline的，即不需要一直online等待别人sending message

为什么会有这个问题呢？因为Alice有$p, g$数据，而Bob的$p, g$数据是Alice发给他的，所以当Alice offline时，Bob就没法decode发来的message了

Process:

• Alice generates $p, g, a, g^a$ and broadcast $(p, g, g^a)$。因为此时Alice不知道谁会要与她交流，所以是broadcast。之后，Alice turns her computer off (offline)
• 现在Bob want to send a message to Alice。Bob generates a random secret $b$ and computes $g^{ab} = (g^a)^b$。
• Bob sends $(g^b, e = m + g^{ab})$ to Alice …之后跟上面的操作一样就好了，因为Alice已经能算出 $k$ 了
• When Alice is back online, Alice computes $g^{ab} = (g^b)^a$
• Alice computes $m = e - g^{ab}$

注意，上述过程都是基于$\text{mod} ~ p$的情况

Lecture 6: The RSA Cryptosystem

Requirements:

I need to have two functions: an encryption function $Enc_k: \sum^* \rightarrow \sum^$ & a decryption function $Dec_k: \sum^ \rightarrow \sum^*$

And I also need a key pair $(e, d)$。这里$e$是public，$d$是private。

同时也需要满足，$\forall m, Dec_d (Enc_e (m)) = m$

Security Requirements:

If the adversary knows $e$ & $Enc_e(m)$ & $Enc$ algorithm & $Dec$ algorithm, they cannot find any information about $m$(private).

---

Rivest-Shamir-Adleman (RSA)

前提：I have a number $n$ and all calculations are $\text{mod} ~ n$. And $e, d \in [0, n)$

$Enc_e (m) = m^e \mod n$

$Dec_d (m’) = m’^d \mod n$。这里$m’$代指加密后message

$Des_d (Enc_e (m)) = Dec_d (m^e) = m^{ed}$

所以我们现在需要考虑的是，how do I generate key $e, d$，s.t.，$m \equiv m^{ed} \pmod n$

Key Generation:

What happens if $n$ is prime?

$\forall m, m^{ed} \equiv m \pmod n \Leftrightarrow \forall m, m^{ed - 1} \equiv 1 \pmod n$

要满足上面的式子，只需要使得 $n - 1 | ed - 1$ 即可 (by Fermat’s Little Theorem)

$ed - 1 \equiv 0 \pmod {n - 1} \Leftrightarrow ed \equiv 1 \pmod{n - 1} \Leftrightarrow d \equiv e^{- 1} \pmod{n - 1}$

What does Eve see?

$e, n, m^e$.

Eve can compute $d = e^{- 1} \mod{n - 1}$. Then Eve can decrypte the message like us: $m = Dec_d (m^e)$

那么会造成这种结果的原因实际上就是计算key $d$的成本太低了，只需要知道$n - 1$就行，所以我们需要修改这个。也就是说，单纯让$n$是个prime number太简单了。

Key Generation (Attempt 2)

Alice chosses two large primes $p, q$ and set $n = pq$. 这里$n$是public，但是$p, q$是private。

I need to generate $d, e$, s.t., $\forall m, m^{ed} \equiv m \pmod n$

这里我们需要用到Chinese Remainder Theorem

根据CRT，可以得到
$$
m^{ed} \equiv m x\pmod n \Rightarrow
\left\{
\begin{aligned}
m^{ed} \equiv m \pmod p \
m^{ed} \equiv m \pmod q
\end{aligned}
\right.
\Leftrightarrow
\left\{
\begin{aligned}
m^{ed - 1} \equiv 1 \pmod p \
m^{ed - 1} \equiv 1 \pmod q
\end{aligned}
\right.
$$
We make sure that $ed - 1$ is a multiple of both $p - 1$ and $q - 1$.

所以我们可以直接计算$l = lcm (p - 1, q - 1)$. 之后Alice chooses $e, d$, s.t., $l | ed - 1$

推导一下，得到$ed - 1 \equiv 0 \pmod l \Leftrightarrow e = d^{- 1} \mod l$

What does Eve see?

$e, n, m^e$

此时我们的$d = e^{- 1} \mod l$。会发现此时Eve不知道$p, q$，所以她没法知道$l$。但是实际上，Eve可以factorize $n$，毕竟$n$就是两个prime的结合，但假若$p, q$足够大，所以此处我们暂且认定Eve cannot find $p, q, l = lcm (p - 1, q - 1), d, m$

---

RSA Assumption

Given $e, n, m^e$, one cannot find $m$.

We do not have a proof to it, but it actually works.

Lecture 7: Digital Signatures

In one-time pad, we use our key $k$ only once, or it would be figured out if being multiplely used.

However, in RSA with key pair $(e, d)$, we always keep them the same.

Homomorphic property of RSA

$Enc_e (m_1) \cdot Enc_e (m_2) = Enc_e (m_1 \cdot m_2)$

Digital Signatures

Definition:

Alice wants to send messages to Bob in the Internet.

Meanwhile, Charlie can change the message Alice sends in the middle.

所以问题就是，how can Bob be sure the message is originally from Alice?

这时Alice除了send message $m$，还要send a signature $sgn(m)$，并且要满足，everyone including Bob is able to verify this signature.

A signature function $sgn_d: \sum^* \rightarrow \sum^$ with a *secret key** $d$.

A verification function $ver_e: \sum^* \times \sum^* \rightarrow \{0, 1\}$ with a public key $e$. 这里的0，1指的是确认是假的或真的。同时还要有个 $\overline{ver_e}: \sum^* \rightarrow \sum^*$，这个函数是返回originial message来check if it is the same msg用的。

Validity Property:

$\forall m, ver_e (m, sgn_d(m)) = 1$

$\forall m, \overline{ver_e} (sgn_d (m)) = m$

Security Property:

Only Alice can sign.

If Charlie knows $m, e, sgn, \overline{ver}$, he should not be able to compute $sgn_d (m)$.

RSA Signatures

• Alice creates RSA keys $n = pq, e, d$, s.t., $\forall m, m^{ed} = m \pmod n$
• We assume everyone knows $n, e$
• Alice computes $s = sgn_d (m) = dec_d (m) = m^d$ and sends it to Bob
• Bob verifies Alice’s signature by computing $\overline{ver_e}(s) = enc_e(s) = s^e = m^{ed}$

If $s$ is really Alice’s signature on $m$, then $s = m^d$ so $m^{de} \equiv m \pmod n$

What does Charlie knows?

$m, m^d, n, e$

But he cannot forge a signature. Because to forge a signature on $m’$, Charlie must compute $m’^d$, which is the same as decryption (因为Charlie需要解码得到$d$来重新根据自己欲修改的信息$m’$得到$sgn_d(m’)$再发给Bob) which the RSA assumpltion rules out.

Homomorphic Property

Alice signs $m_1, m_2$ and sends $sgn_d (m_1) = m_1^d, sgn_d (m_2) = m_2^d$ to Bob.

Charlie knows $m_1^d$ and $m_2^d$, so he comptues $(m_1m_2)^d$.

$\forall m_1, m_2, sgn_d(m_1) \cdot sgn_d(m_2) = sgn_d (m_1 \cdot m_2)$

Simple and important: Never sign a message $m$. Always sign $hash (m)$.

这么说是因为Charlie肯定能得到$sgn_d (m_1 \cdot m_2)$，我们需要保证他得到的东西必须是个garbage message，故要sign $hash (m)$而不是$m$。

Lecture 8: Transactions and Double-spending

现在将上面讲的两个做一个整合。还是假设Alice send to Bob，中间有Eve和Charlie分别劫持message和digital signature


Alice wants to send $m$ o Bob:

• Alice computes the signature $s = sgn_{d_2} (hash (m))$
• Alice encrypts $(s, m)$ to obtain $x = Enc_{e_3} (s, m)$ and sends $x$ to Bob
• Bob decrypts $x$ to get $Dec_{d_3}(x) = (s, m)$
• Bob verifies Alice’s signature by checking if $\overline{ver_{e2} (s)}$ equals to $hash (m)$

Creating a Cryptocurrency (Public Keys as Identities)

Creating an account = generating keys $(e, d)$

$e$ = my public identity

$d$ = used for signatures

Make Transactions

Required information:

• Sender’s identity = pubic key
• Recipient’s identity
• Amount
• Proof of ownership (hash pointer to the transaction that paid sender) 来证明sender有足够的钱来做transaction
• Proof of consent (signature from the sender) 证明sender确认转账


How to verify a transaction?

Assumption: Everyone knows what the previous transactions were.

• Verify the signature to make sure Tx is approved by the sender
• Check identities of all inputs of Tx
• The amount of money counted by the inputs should be greater than the amount counted by the outputs.
• Every output can be spent at most once

Double Spending

Lecture 9: A Centralized Ledger

double spending affects consensus，因为我们不知道对方到底可不可信。

那么结局这个consensus问题的最简单的方法当然就是有一个centralized的entity，那么大家信任这个entity就好了。

There is a central bank B which keeps track of the history of all the transactions and also publishes it.

为了接下来实现decentralized，Let’s first try somehow limit the power of centralizd bank.

Group our tansactions into bunch of blocks, i.e., block: a sequence(有order) of Txs of size at most $b$ (one million bites).

每个后面的block有个hash pointer to the previous block.

When the bank has enough Txs, it creates a new block, it has a lot of Txs in it, and a pointer to the previous block. 那么我们会存在以下问题，以及解决方法。

• How to know if some block $B_i$ was created by the central bank? (ANS: The bank signs every block, i.e., everyone should know the bank’s public key s.t. everyone can check if the blocks were created)
• How to make sure the bank does not change the history? (ANS: If the bank want to change sth in the block 1, then everything will change until the very last one. 所以这是bank不能change的保证。)
• What is the history of Txs? What Txs has taken place? (ANS: Any Tx in the chain is considered to be already processed / done / finalized)

Viewpoint of a user:

• Form a Tx (参考Lec8)
• Publish Tx (Send Tx to all of my neighbours)
• Wait until the Tx gets into the blockchain (wait and listen for new blocks)

The Tx is finalized when I see a valid block containing the Tx.

Viewpoint of a node:

• Keep track of the blockchain

• Listen for Txs and blocks

  • Case 1: If I hear a new Tx (not process the same Tx twice)
    • Check the validity of the Tx (This check applies to everyone except the bank)
      • Pass signature verification (Anyone who’s sending some money in this Tx should have signed this Tx)
      • The sum of inputs in the Tx should $\ge$ output
      • No double spending (There is no coin/input that is spent in this Tx and also in another Tx that is on the blockchain)
    • If Tx is valid, send it to all neighbours
  • Case 2: If I hear a block $B_i$
    • Check the validity of $B_i$
      • Verify bank signature (if it is signed by the bank)
      • Validate every Tx in $B_i$ w.r.t $B_0, …, B_{i - 1}$ and previous Txs in $B_i$ (比如看看跟之前block里的有没有double spending)
      • $B_i$ points to $B_{i - 1}$
    • If $B_i$ is valid
      • Add it to my blockchain
      • Send it to neighbours

Viewpoint of the bank

• Maintain a copy of the blockchain $B_0, …, B_{i - 1}$

• Maintain a new block $B_i$

• Listen for Txs

  When I hear a Tx

  • Verify the Tx w.r.t. $B_0, …, B_{i - 1}, B_i$

    If Tx is valid then $B_i \leftarrow B_i \cup \{\text{Tx}\}$ (add Tx to $B_i$)

    When $B_i$ is large enough (has enough Tx in it)

  • Make $B_i$ point to $B_{i - 1}$

  • Sign $B_i$

  • Publish $B_i$ with signature

Property

• I don’t need to disclose my identity. I only need to create an account (a public and private key pair). Then just make Tx using this account.
• 不需要直接与bank communicate，因为你可以随便给人发Tx的信息然后他们继续向neighbour发送最终都会reach the bank.
• Bank cannot create Tx invalid或者挪用你的coin，因为如果bank想spend coin，必须要有valid signature喝valid Tx，但是这些只有你本人有权利发布

那么有个最原始的问题，最开始的coin是哪里来的？

所以我们需要给bank ability to create money. 这也是为什么上面viewpoint of node case 1 Check the validity of the Tx后面有括号补充的原因

Lecture 10: Bitcoin and Proof of Work

The central bank’s power in centralized ledger:

• Extend the blockchain
• Print money

---

Decentralization

Every node has the same permissions.

How to extend the chain, while preserving consensus for honest nodes?

Extend the chain: Mining

Person who extends the chain: Miner

这边我们不考虑fairness，只考虑consensus，即是不是chain上所有人都认可新加的block。

Method: Ask everyone to solve a really hard mathematical puzzle, the first one who solves is able to add it. 这叫做 Proof of work

Property

• Hard to solve
• Easy to verify
• Impossible to steal (比如我再通知我neighbor的时候不会让他们知道solution以至于steal我的sol来说新block是他们的)

那么如何得到第三个property呢？

Hash-based Proof of Work (PoW)

Structure of a block (what does it contain)

• Number (ID)
• Pointer to the previous block ($prevB$)
• Transactions (以Merkle Tree形式储存)
• Nonce (A number that is chosen by the miner)

For B to be valid $h(B)$ should be small, e.g., $h(B) = 0000…0…$ 最少60个0.

所以实际上，这个puzzle就是你怎么找到一个nonce，使得$h(B)$很小，而当你找出来后publish你的block，别人是能通过你的nonce验证的。而实际上，你的$hash (B)$ hash的是你的block，即你的number, prevB, Txs, etc..，所以别人在里面这些参数不同的情况下，是没法steal你的nonce来encode他们的block使得hash value很小的。这也就满足了第三条性质。

How the whole protocol works

• Every node is equal (decentralization)
  • Everyone can be a transactor: Create new transactions (exactly as in centralized ledger (CL))
  • Everyone is a node on the network
  • Everyone can be a miner: Create new blocks (does anything the central bank does, and at the same time do PoW)

Viewpoint of nodes

A node keeps track of

• Blockchain
• Mempool (the set of all valid Txs I have seen now, but have not been published to the blockchain (not finalized))

If the node hears a new Tx

• Verify its validity

  • Verify signatrues
  • Verify if $\sum inpts \ge \sum outputs$
  • Verify no double-spending w.r.t. the blockchain & mempool

• If Tx is valid

  • Send Tx to all neighbours

  • Add Tx to mempool

If the node hears a new block $B$

• Verify the validity of $B$
  • $h(B)$ is smaller than $d$
  • All Txs in $B$ are valid
    • Signatures
    • $\sum inputs \ge \sum output$
    • No double-spending w.r.t. blockchain $\cup$ $B$ (no mempool，因为mempool的是没有finalized的，所以我们可以允许这个miner在这种情况下double-spending，即在blockchain上发布一个新的block)
• If the block is valid
  • Add it to blockchain (my own copy of blockchain)
  • Update my mempool
  • Send $B$ to all neighbours

What happens if two valid blocks are found at approximately the same time?

这个situation也被称作fork

Consensus rule of bitcoin:

• Miners get to choose which chain to extend
• 取最长的链作为正确的链

所以实际上一个node会keep track of all valid forks

Lecture 11: Mining Rewards and Forks

How to cerate new units of currency

Why should anyone be a miner

Block rewards: Any valid block can include a transasction that has no input and a single output paying the miner

比如block reward = 25 BTC

In bitcoin, the block reward gets halved after every 210000 blocks (~ 4 years). 这可以control the amount of bitcoin currency以防止他不是无限膨胀的。

Why should a miner mines a non-empty block

作为一个miner，我可以只mine empty block to obtain block rewards

Transaction fees (可以理解为手续费)

• In every valid Tx, $\sum inputs \ge \sum outputs$
• The difference $\sum inputs - \sum outputs$ is paid to the miner who adds this Tx to the blockchain as a transaction fee

If you want to add your Tx sooner to the blockchain, pay more Tx fees

In Bitcoin, each block is at most $10^6$ bytes 来防止在run protocol时出现delay。

所以有了size的限制以及transaction fee的竞争，我在通过mining获得了block rewards后能够大概率保证让它上链的最佳办法就是pay more transaction fees

Question: What if the block created by a miner is not in the longest chain, will the miner still gets rewards?

Answer: No. Any Tx outside the consensus chain is ignored.

Double-spending attack

Scenario: Suppose a bitcoin-based vending machine (bitcoin-based自动售货机)

• Merchant provides their identity (public key)
• Customer creates a Tx paying the merchant
• Customer gives Tx to the merchant
• Merchant verifies the validity of the Tx
  • If valid
    • Publish Tx
    • Provide item

但里面有些问题：

First attack: Immediate double-spending

Suppose a Tx on blockchain, which pays 1 BTC to Alice. Now Alice creates a new Tx $Tx_1$, and takes the 1 BTC as the input of $Tx_1$, and set output as 0.99 BTC (不可能是1，因为有Tx fee) to the vending machine. Suppose now she creates another $Tx_2$ immediately and uses the same input, and pay 0.95 BTC to Alice (herself). 比如这两个Tx是在不同地方发生的，比如HK和US，那么可能HK的人先看见$Tx_1$，但是US的人先看见$Tx_2$，那么这笔double-spending可能就会成功

If the miner includes $Tx_2$ in a block, then the attck will be successful.

另一种更聪明的方法是Alice can bribe the miner to increase her chances，即让$Tx_2$的Tx fee更高，而这笔钱是付给其他miner的。

Solution

Wait for $Tx_1$ to be mined (added to the blockchain)

Second attack: Double-spending in a fork

这时用上面的方法就行不通了，因为如果我要等$Tx_1$被finalized，就需要等下一个block be mined to contruct a longer chain。然而这个时间可能会是10min甚至更久，而vending machine要的就是实时付款实时交货，所以不可行。

What the merchant sees

• $Tx_1$ that is paying merchant
• Wait for almost 10 min until a block in the blockchain that contains $Tx_1$

那么问题来了，some blocks can be reverted (it used to be in the consensus chain, but now no longer in) and $Tx_1$ might be removed from the consensus chain

Solution

Wait for confirmation (一般来讲是6 confirmations)

这里的confirmation指的是比如$B_n$是要pay给我的那个Tx，它的后继有一个新的block added，那么这个新的block就相当于一个confirmation，因为它认可了$B_n$作为the last block的地位；如果后面又接了一个block，那么就是second confirmation…

但这样就需要等待~ 1h了。所以vending machine并不适合bitcoin。

Adjusting difficulty

In Bitcoin, a new block is mined ~ 10 minutes

PoW: Find a valid block $B$ s.t. $h(B) \le d$

Suppose a hash function $h: \sum^* \rightarrow \sum^{256}$

Let’s assume $h$ behaves like a uniformly randomed function

What is a miner’s success probability if they try $k$ blocks?

Every time I have a prob of $\frac{d}{2^{256}} \ge \frac{kd}{2^{256}}$ to succeed

那么try $k$次成功的概率就是$1 - (1 - \frac{d}{2^{256}})^k$

Now, here’s the thing. I can dynamically change the number $d$ 来让我的problem变得harder

All Bitcoin blocks have a timestamp。太久远或者未来的timestamp就不用管了

然后我根据这些timestamps选出最近的1000个，find the avg mining time $\mu$

• If $\mu > 10$, increase $d$, decrease difficulty
• If $\mu < 10$, decrease $d$, increase difficulty

从而保证期望新增一个block的时间是10min

Lecture 12: Centralization and Scripts

Bitcoin’s honesty assumption

Majority of the computational power is honest

What if the assumption does not hold?

Imagine a malicious miner with more than half of the hash power

Suppose block B1 <- B2 <- B3

假如我是个honest miner，那么我会extend B3。反之，若是malicious，我会extend B2，并让这个dishonest chain不断延长，使得B3不复存在

那么现在因为我有more than half of the hash power，所以我有能力做到作假

这种attack方式叫做51% attack

own more than 50% computational power的另一种作弊的方法: Double-spending，本质上和上面的是差不多的，

---

Scripts

Tx:

Input:

• Value & parameters(Scripts) to spend the coins (与下面的conditions to use coins对应)

Output:

• Value & Conditions(Scripts) to use these coins (比如condition可以是require signs from A & B，就是加一些使用条件)

Micropayments (Scripts的用处)

Scenario:

Alice is a customer & Bob is a mobile network

Alice makes a phone call and pays 0.1 HKD per min

Neither side trusts the other

Alice does not trust Bob, she wants service first

Bob does not trust Alice, he wants payment first

且我们不想pay every minute，即不想有很多的transaction

• Alice puts down a deposit of 100 HKD，现在她不想直接付钱

  She creates a Tx1, putting 100 HKD as input, and an output of 100 HKD (conditions: needs signatures from both Alice & Bob)

  The Alice publishes the block to the blockchain. And wait until it is completely on the blockchain.

• Alice starts her phone call。但是要能打Alice必须先pay 1 HKD

  那么现在Alice将Tx1的output连到一个新的block，并给Tx1签名，这个block的output有两个: 1 HKD to Bob & 99 HKD to Alice。

  到了second minute，Alice再create一个new Tx，taking the same deposit as input, but paying 2 HKD to Bob & 98 HKD to Alice。

  以此类推

  上面的Tx目前都是invalid的，但是只要Bob给Tx1签名，再选择一个出来的block publish，就可以收到钱了。当然，假如Alice打了k分钟电话，那么Bob选的肯定是第k个block。因为如果Bob cheat publish多个，那就是double-spending。

• Bob signs the last Tx and publishes it to the blockchain

但是上述protocol有一个问题，就是在Alice publish Tx1后，她的这100 HKD实际上是被locked的，也就是说，只要Bob不签名，她这100 HKD就相当于存进去取不出来了。所以此时Bob就有机会去extort Alice，threaten她说如果你不给我50 HKD，then I’ll not sign any of these transactions，让她的钱被永久冻结。

解决方法是在最开始的condition那儿加上一句(or signature from Alice and block number > $c$)，即多少天后

Lecture 13: Two-way Payment Channels

One-way Payment Channel

• Alice publishes $Tx_1$

  

  右上角是timeline，$Tx_0$ 是Alice发起transaction的时间，被括弧框住的时间区间是Alice能pay Bob的时间，最后的 $t$ 就是Bob经过这么长的时间不sign不accept，Alice把自己的钱收回来的时间。

  那么Bob的ddl和 $t$ 之前的时间段又代表着什么呢？它代表着Bob publishes the last transaction but still waiting for the confirmation。

• Alice creates a series of $Tx_1$ which takes the output of $Tx_0$ as input, and output 1 unit to Bob & 99 unit back to Alice

  Alice creates and signs $Tx_1$ and sends it to Bob. 其他unit to Bob以此类推

• Bob signs $Tx_k$ and publishes it on the network (and finalized on the blockchain)

Properties

• Money flows in one direction (Alice $\rightarrow$ Bob)

  Alice can only increase the total payment to Bob (因为Bob总会选择自己获益最大的那个block)

• Bob can close the channel

• The channel expires at time $t$

• The channel has a fixed capacity

Only two Txs are added to the blockchain $\Rightarrow$ only two Tx fees paid for $k$ payments

Payments are instant，原因是对于Alice，我构造出了$Tx_0$之后只需要直接sign，然后再构造出$Tx_1, Tx_2, …$，之后就不用管了，是instant就可以结束了；对于Bob，我也是直接sign一个新构造的block就可以了。

Two-way Payment Channel

Scenerio: Alice & Bob are friends，他们直接经常需要进行transaction，并且不想每次都pay transaction fee。

Simple Solution

• Create two one-way channels (Alice $\rightarrow$ Bob & Bob $\rightarrow$ Alice)

但是这样有几个问题：

• Alice can only increase the total payment to Bob

• A created channel has a capacity

  比如说，Alice creates a block跟上面的 $Tx_0$ 一样，那么他的capacity就是100 (100 + 1，其中1是transaction fee)，因为这钱花完了就没了，除非你重新给$Tx_k$接入一个新的input，那么这又需要重新构造新的block。

Second Attempt: Let money flow in both directions

如果Bob cheat就触发后面的$\text{Alice} \cap c$，降钱还给Alice，没有的话就正常给Bob after time $t$。

那么proof $c$怎么生成呢？

Here the cheat means Bob has published $Tx_i$ but $\exist Tx_j, j > i$ that pays less to Bob，即他publish的不是最后的block，因为最后的block总是代表着Alice要给Bob钱数的最终想法。

Change in protocol: Bob has to sign the index of every transaction, and sends the signatures to Alice。其中index指的是上图每个block中间的小方框中的 $1, 2, 3, …$

那么此时，$c = $ Bob’s signature on an index $>$ current transaction’s index

One-way Channel with Refunds

• Alice puts down a deposit

  

• When Alice wants to pay Bob

  

• When Bob wants to refund

  

Two-way Channel

Alice creates a one-way channel with refunds $c_1$ to Bob ($\text{Alice} \rightarrow \text{Bob}$)

Bob creates a one-way channel with refunds $c_2$ to Alice ($\text{Bob} \rightarrow \text{Alice}$)

可以发现上面的操作只需要一个操作create a block，跟之前的比起来好很多

Lecture 15: Escrows and Ethereum-like Smart Contracts

Scenario: Alice wants to buy a physical good from Bob and pay BTC, and they do not trust each other

Awful solution: Use a third-party Carol

Problem: Bribery

A rational Carol signs and publishes $Tx_m$ (You are rational iff you only care about maximizing your own payoff)

存在这个问题的话，我们也无法信任Carol。

Next step: Remove Carol from the protocol

因为Bob可以wait for Alice to put down the deposit and don’t send the item，之后跟Alice说我可以不sign，那么你就会lose 100 ETH，以此来进行extortion。

所以我们需要两边都put down deposits

Solution: Change the deposit $Tx$

这个方法叫做bithalo

Problem with Bitcoin Scripts

• Scripts are attached to outputs
• Limited language
  • complete and unambiguous semantics
  • All scripts must terminate in $O (1)$
  • Bitcoin miners have script whitelists

Ethereum-like Smart Contract

The consensus in bitcoin is on a sequence of transactions

Let Txs do moreL

• Deploy a program (i.e., smart contract)

  The code now reaches consensus, and now everyone knows what exactly my code was

  data: program’s code

• Invoke functions of a previously-deployed smart contract

  data:

  • pointer to the contract
  • function name $f$
  • parameters of $f$

Every contract can receive and manage money

Lecture 14: Basics of Solidity and Ethereum Smart Contracts

Gas & Fees

这个东西的出现是因为可能会出现以下的情况，

一个malicious actor写了一个never terminate的function，并且publish到了blockchain，且让一个block去invoke它，让它形成consensus，那么此时chain上的所有人都得一个个function调用，总是会调用到这个导致never terminate，从而cause a denial of service attack

Gas refers to the unit that measures the amount of computational effort required to execute specific operations on the Ethereum network.

它实际上就是一个约束，你的function运行时间越长，你的transaction fee要交的越多

Lecture 19: Secret Sharing

Commitment Schemes

A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value (or chosen statement) while keeping it hidden to others, with the ability to reveal the committed value later.

下面来讲解几个commitment schemes的用的area

Random Number Genenration

• Phase 1: Player $i$ first commits to the hash of $r_i$. i.e., $h (r_i)$, and wait for other players to commit
• Phase 2: Player $i$ reveals $r_i$
• Output random number $r = \oplus_{i = 1}^n r_i$

Problem:

• It is in an honest player’s best interest not to reveal their value $r_i$ in phase 1

• What if a malicious player does not reveal in phase 2?

  改进版:

• Phase 1: Player $i$ first commits to the hash of $r_i$. i.e., $h (r_i)$ and pay a deposit $d_i$, and wait for other players to commit

• Phase 2: Player $i$ reveals $r_i$, if he does not reveal then he will lose the deposit

• Output random number $r = \oplus_{i = 1}^n r_i$

而且我们要保证的是malicious player lose的比可能win的多，否则他会选择这局放弃deposit然后restart，在下一局赚回来，或是继续重复restart，直到赚回钱, i.e., $d > \sum tickets$

我们可以发现，这一切extortion的源头都是因为总是回存在一个人在别人后面publish，即不是simultaneous的。所以commitment schemes实际上就是在simulate simultaneous information publishment

但是实际上，commitment scheme是有弱点的，在对方，Bob intentionally leak他自己的choice的时候，commitment scheme就失去了意义，他仍然可以extort Alice。这个跟Escrow的例子是一样的

在这个例子中，Alice deposit 2 ETH，Bob deposit 1 ETH，Bob claim他已经把货发给了Alice，即 $r_i = fulfilled$，但实际上没有。他就此extort Alice。如果Alice接受extortion，她会get 1 ETH back，Bob得到2 ETH。反之，Alice gets nothing back，Bob也gets nothing back。作为一个rational player，Alice会accept extortion。

---

Random Number Generation

Main flaw(缺陷): A player can choose not to reveal

Solution: Design a protocol in which $r_i$ is revealed even if player $i$ doesn’t want to

Secret Sharing

Alice has a secret $s \in [0, p)$, $p$ 是模数

注意这里需要学习拉格朗日插值

我们可以发现拉格朗日插值和我们要的结果很像，就是我们能够根据 $t$ 个information构建一个polynomial，但是 $t - 1$ 个就不行

所以一个很直接的想法就是，Alice可以把她的secret encode成coefficients of the polynomial

• Alice creates a polynomial $g$ of degree $t -1$

  $g(x) = a_0 + a_1x + … + a_{t - 1}x^{t - 1}$

  $a_0 = g (0) = s$, $a_1, a_2, …$ chosen randomly

• Alice computes $s_i = g (i)$ and gives it to $f_i$

现在回到原来的问题，怎么样才能让别人能够compute $r_i$呢

一个方法便是，在你choose你的 $r_i$ 的时候你也必须要告诉别人你的share of $r_i$，这样若你refuse to reveal，别人也能够compute your $r_i$

所以，overall的方法便是，(首先假设everyone knows a prime number $p$)

• Players sign up with smart contract and pay deposit $d$

  Assume $n$ people sign up

• Each player $i$ chooses $r_i$

  Player $i$ forms $g_i$ of degree $t - 1$ and gives shares to everyone $j \neq i$

• Player $i$ commits to $h (r_i, n_i)$ on the smart contract

• Player $i$ reveals $r_i, n_i$

• If a player $i$ fails to reveal, then other players come together and compute $r_i$

• $r = \sum r_i \mod p$

Constraints:

• At least $t$ honest players，不然没法计算出准确的 $r_i$
• At most $t - 1$ dishonest players，若dishonest的players有大于等于 $t$ 个，那么他们就足以伪造一个 $r_i$

注意，在这种情况下，如果你想cheat，那么你不得不在phase 1进行cheat，但是此时you know nothing about $r$，所以cheating is pointless

Lecture 20: Random Number Generation via Verifiable Delay Functions

Goal: Gneerate a random number $r = \{0, 1, …, n - 1\}$

Desired properties:

• Uniform Distribution: 只要我的任意一个player is honest并且给我generate了一个random number from uniform distribution，那么我最后计算得到的 $r$ 一定是from uniform distribution的
• Tamper-resistance
  • Commitment Scheme: Need deposits > $\sum tickets$
  • Secret sharing: Need > half of the players are honest

Ideal Protocol

• Phase 1: Every player $i$ chooses $r_i$ and computes $c_i = commit (r_i)$ and records it in smart contract + paying deposit $d$
• Phase 2: Every player $i$ reveals $r_i$ to the smart contract & SC verifies that $c_i = commit (r_i)$
• Phase 3: For every player $i$ who has not revealed $r_i$ other players can compute $r_i$

Properties of Commmit (hash function)

• Collision-free: It is impossible to find $x \neq y$ s.t. $commit (x) = commit (y)$

• Time-consuming to invert: Given a commitment $c_i = commit (r_i)$, it takes at least $T$ units of time no matter how many cores/threads you have to compute $r_i$

  假设我们phase 1 + phase 2总共加起来需要 $\frac{T}2$ 的时间，那么commit就可被视作无法被解密

• Easy to compute

但是你会发现有一个问题，就是实际上hash function不可能是one-to-one的，这就和time-consuming to invert冲突了，因为malicious player就可以在游戏开始前花费时间 $T$ 预先算好两个 $x, y$, s.t., $commit (x) = commit (y)$。那么在提交相同commit的情况下，第二次publish的结果却不同了

所以我们需要一个close to上述所有条件的function

---

VDF: Verifiable Delay Function

• Evaluation function: $Eval (x) = (y, \pi)$，其中 $f(x) = y$，而 $\pi$ 指的是 the proof that shows $y$ is really $x$ 根据函数 $f$ 得到的hash结果

  Takes at least $T$ time

• Verification: $Verify (x, y, \pi) \rightarrow \{true, false\}$

  Fast

Uniqueness: $\forall x !\exist y \exist \pi, verify (x, y, \pi) = true$，这里 $!\exist$ 指的是exist exactly one

$\epsilon$-sequentiality: Given $x$ and spending $T (1 - \epsilon)$ time, you cannot find anything about $y$

---

VDF-Based RNG

• Phase 1: Every player $i$ submites $r_i$ to SC
• Phase 2: $h = \sum r_i \mod n$
• Phase 3: $r = VDF_T (h)$

Phase 1 + Phase 2 = $\frac{T}{10}$ of time

• Phase 4: Someone submits $r$ and $\pi$ to the SC, then SC does $verify (h, r, \pi)$

Lecture 21: Mixing and Blind Signatures

Bitcoin identities are public keys & not connected to real-world identity

But can someone find my real-world identity if I use bitcoin?

We need to answer some questions

• Where do I get my bitcoins?
  • Mine —— Safe but not practical
  • Buy —— Leaks your real-world identity (you need to identify yourself through legal procedures to buy bitcoins)
• Where do I spend my bitcoins?
  • When you pay you disclose
    • Your public key
    • Your real-world identity (for example government asks you to do)
• Why care?
  • Even if one public key is leaked, all future Txs are deanonymized
  • Even if one public key is leaked, all past Txs are deanonymized

---

How to Keep the IDs Private?

Break the link between your public key & real-world ID

First Idea: Money Landering

Be chaotic:

• Create a lot of accounts
• Randomly move money around

Gives you privacy w.r.t. small actors

Second Idea: Use a Mixer

Everyone can transfer money to the mixer. Pay in with the same amount, and the mixer pay to new accounts

这样别人就无法找到input account和output account的联系了

Problems:

• This is centralized solution, we cannot trust the mixer who knoews both of my accounts
• The mixer might steal my money and there is nothing I can do about it

Solution:

I need these properties:

• trustlessness: wanna make sure the mixer cannot keep my money
  • Sol: 把mixer的角色从一个account换成smart contract
• privacy from the mixer: make sure even the mixer itself cannot link between my old & new account

---

Blind Signatures

Scenario (in real world):

• Alice is a customer of the bank
• Only the bank knows her balance
• Bob is a customer, too
• Alice wants to pay Bob

但是Alice现在不想让知道bank我现在要pay的是Bob，即we want privacy w.r.t. the bank

所以bank需要知道的只有:

• Money leaves Alice’s account
• Money enters Bob’s account

在这种情况下没有serial number的banknotes就可以起到这个作用。Alice withdraw一个banknotes，然后给Bob，Bob再将其拿给bank兑换，那么bank knows nothing about the process

放到digital world也是同理，我们想要实现上面这样的功能

Idea: Issue Banknotes

$b = \text{“I am a banknote # … worth 100 HKD”}$

之后Alice将 $(b, sgn_{bank} (b))$ sends to Bob，Bob可以验证bank的signature来判断他是不是官方的

How to avoid double-spending

Bob can avoid double-spending by depositing immediately。如果bank告诉他这个banknotes已经被用了，那么他就不接受Alice的这个banknote

但是你会发现这其中有很多问题，比如bank必须要track serial number来判断这个banknote是否已经被用掉了，这就与anonymous不符

而且bank可以be malicious，他可以issue different banknotes with same serial numbers，但Alice无法知道这件事

Solution: Blind Signing

Blind signing指的是the person who is signing doesn’t know what on earth he is signing

此处就相当于bank在不知道 $b$ 的情况下sign $b$

---

RSA Blind Signatures

The bank has announced $e, N$ but not the secret key $d$ for RSA

• Alice creates a banknotes $b$
• Alice hashes $b$ and obtains $h$

Goal: Alice wants to obtain the signature $h^d$ but doesn’t want the bank to have any information on $h$

• Alice computes $h’ = h \cdot r^e \mod N$ where $r$ is a random number

• Alice sends $h’$ to the bank

• The bank signs $h’$ and sends the signature $(h’)^d$ bank to Alice

• Alice has $(h’)^d = h^d \cdot r^{de} \equiv h^d \cdot r \pmod N$ according to RSA property: $r^{ed} \mod N = r \mod N$

  Alice computes $h^d = (h’)^d \cdot r^{- 1} \mod N$

• Alice sends $(b, h^d)$ to Bob

• Bob immediately sends $(b, h^d)$ to the bank

• The bank verifies its own signature

  • Increases Bob’s balance by 100 HKD
  • Adds the serial number of $b$ to the list of spent banknotes

---

重新回到mixer，但是我们发现，因为SC里面的所有东西都是public的，所以我们没法将 $d$ 这样的private key存到里面，所以我们还需要一个extra actor —— bank (a real-world person)来做blind signature

• The bank creates $N, e, d$ and sends $N, e$ to the mixer

• Alice pays the mixer 1 ETH & sends $h’ = h \cdot r^e$

• The bank signs & sends $(h’)^d$ to the mixer

  在这一步若bank sends一个假的 $(h’)^d$ 可以被mixer verify出来，因为他拥有 $N, e$

• Bob sends $(b, h^d)$ to the mixer

• The mixer transfers 1 ETH to Bob

Attack:

The bank can issue extra banknotes. 即他可以issue some fake banknotes自己sign然后去当作Bob取钱

Solution:

Mixer可以在收到Bob的取钱banknote的时候不立即给他钱，而是等到一个ddl再给，如果比如现在我mixer总共存进去1000笔，而取出1001笔，那么就说明bank is cheating，就可以把bank给ban了，然后refund to Alice

Goldwasser-Micali Cryptosystem

Probabilistic Encryption & Signature

之前我们见到的encryption或是signature全部都是deterministic的，比如RSA的encryption就是unique的。

Goldwasser-Micali Cryptosystem

Quadratic Residual (二次剩余)

$x \in \{0, \cdots, n - 1\}$ is a QR modulo $n$ if $\exists y, y^2 \equiv x \pmod n$

Quadratic Residuosity Problem

Given $n$ and $x$, is $x$ a QR mod $n$?

If $n$ is a prime $n = p$，根据fermat’s little theorem，$x = y^2 \Rightarrow x^{\frac{p - 1}2} \equiv 1 \pmod p$

If $n = pq$ and we know $p, q$，那么问题就变成了 $x$ 是否是 $p, q$ 的二次剩余

GM crypto实际上就是based on QR，假如只有发件人Alice知道 $p, q$，那么别人都没法answer QR question，那么我要做的实际上就是达到一个目的: 如果你要decrypt，就必须要answer QR question

Key Generation

• Alice picks two large primes $p, q$ and sets $n = pq$

• Alice finds $x \in \{0, 1, \cdots, n - 1\}$ s.t.

  • $x$ is not a QR mod $p$
  • $x$ is not a QR mod $q$

• Alice publishes $(x, n)$ as her public key and uses $(p, q)$ as her secret key

• 假设Bob有个message $m$ 想发给Alice，然后他将其encode为很多bit $m = m_1m_2…m_k$，之后他会encrypt each bit seperately，encrypt的方法如下

  对于一个bit $m_i$，如若 $m_i = 0$，那么Bob将会send Alice一个是 $p, q$ QR的数，反之则是send一个不是QR的数

  For every $i$, Bob picks $y_i \in \{0, 1, …, n - 1\}$ s.t. $\gcd (y_i, n) = 1$, $c_i = y_i^2 \cdot x^{m_i}$

  这样的话，因为 $x$ 不是QR，如果 $m_i = 0$ 那么 $c_i$ 就是QR，反之就不是

Decryption

• For every $i$, Alice checks whether $c_i$ is a QR mod $n$

  If “yes”, then $m_i = 0$, else $m_i = 1$

可以发现，same message可以有很多个encryption

Homomorphic Encryption

Homomorphic Property of GM

$Enc (b_1) \cdot Enc (b_2) = Enc (b_1 \oplus b_2)$

两个二次剩余的积还是一个二次剩余

Homomorphic Property of RSA

$Enc (m_1) \cdot Enc (m_2) = m_1^e \cdot m_2^e = (m_1m_2)^e = Enc (m_1 \cdot m_2)$

ElGamal Cryptosystem

• Alice chooses a prime number $p$ and a secret $a$, a primitive root $g$

  Public key of Alice is $(p, g^a)$

• Bob has a message $m$, and chooses a secret $b$, then computes $g^{ab}$

  Send $(g^b, m + g^{ab})$ to Alice

• Then Alice can obtain $m$

Zero-knowledge proof

Alice wants to prove she knows $a$ s.t. $g^a \equiv x \pmod p$

这时这就可以通过encryption和decryption来实现了，只要Alice decrypt了Bob的message，那么Bob就知道Alice knows $a$

Zero-Knowledge Proofs

NP

假设存在两个polynomial $p_1, p_2$, a problem $L$ is in NP if there exists an algorithm $V$ s.t.

• $\forall x \in L, \exists y \in \sum^{p_1 (x)}, V (x, y) = 1$

  即对任意满足problem $L$的condition的 $x$，一定存在某个proof $y$，这个proof的length是 $p_1 (x)$，algorithm $V$可以告诉我们 $y$ 是correct的

• $\forall x \not\in L, \forall y \in \sum^{p_1 (x)}, V (x, y) = 0$

• $T (V, x, y) \le p_2 (x + y)$

  Runtime of the verifier的最大值是 $p_2 (x + y)$

总之就是可以在polynomial的时间内check

Claim: I know the prime factorization of $N = pq$ ($pq$ 是private的，只有我知道)。我要怎么prove我know？

最简单的办法:

Proof: Disclose $p$ and $q$

Verification: Compute $pq$ and checks if $pq = N$

Problem. The prover (Peggy) wants to prove $\phi$ to the verifier (Victor) but she does not want to leak any extra information

Example 1.

Imagine Victor is color-blind and we have two identical balls 但是分别是green和red

Solution: At each step, Victor randomly shows one ball and Peggy has to say if he swapped

Zero-Knowledge Proof

It must have these properties:

• If both Peggy & Victor are honest and Peggy’s claim holds, then Victor would be convinced with high probability
• If Peggy is lying, she cannot convince Victor
• Victor gains no extra knowledge apart from the fact that Peggy’s claim holds (Zero-knowledge property)

Prove zero-knowledge property

Observation: Imagine that Victor records all the interations and later plays the recording for Sarah. There should be no way to convince Sarah that the recording was not staged.

Example

其中，$y’$ 是Victor自己随便选的一个secret。这个证明的本质就是让Peggy证明自己能算出 $g^{yy’}$，这个是个shared secret，因为Victor也能通过 $x^{y’}$ 算出，所以他就能验证Peggy的claim是否为true

Example

There is a graph $G$ and Peggy claims that she knows a Hamiltonian cycle (哈密顿回路) in $G$

• Peggy chooses a permutation and compute $H \approx G$

• Peggy commits to every edge of $H$

  $e_i = (u, v)$ in H, and compute $h_i = hash (u | v | nonce)$ and publish it

• Victor can ask for

  • ( i ) Prove isomorphism
  • ( ii )A Hamiltonian cycle in $H$

• If Victor asked for ( i ), Peggy reveals every edge in $H$ and the permutation

  IVictor asked for ( ii ), Peggy only reveals the edges that are in Hamiltonian cycle

Example

Example

Example

Example

Lecture 25: Be Vindictive

transfer, send, call

首先transfer和send都有gas limit，可能没有足够的gas去send成功

假设我们通过调用function $f$，$f$ 中使用了这些transfer money的函数

• transfer: 如果receiver在receive或者fallback上动手脚，比如throw an exception，那么整个 $f$ 会立刻停止运行，使其revert
• send: 但是send并不会revert整个过程
• call: call 不会遇到上述问题，但是receiver可能会intentionally waste gas，比如在fallback里面加入循环

所以其实最好的方法是，不要我们send他钱，而是让他自己withdraw