Q-Learning 初探

簡介
強化學習 (Reinforcement Learning) 是一種透過嘗試做不同決策，然後根據所獲取的奬勵 (Rewards) 或懲罰 (Punishment)，找出最佳解 (Optimized Solution) 的算法。由於它採用分數奬勵的形式訓練，所以它特別適合玩迷宮、小遊戲、甚至訓練機器人走路這類「未必有絕對答案，只需完成目的」的應用。

強化學習與監督學習 (Supervised Learning) 有所不同的是：監督學習需要集齊不同迷宮的最佳解，然後讓系統在訓練模式中找出 hidden pattern。相反，強化學習並不需要有最佳解的數據庫：系統只需透過選擇性地嘗試，然後採取最低風險（最高回報）的做法，最後就能找出接近最佳解。

以下會利用 Q-Learning 作為例子，講解算式，最後會用一個程式例子演示。

使用「類 Markov Matrix」表示奬勵積分
以下內容，節錄自 A Painless Q-Learning Tutorial [1]。

假設有五間房，我需要設計一個使用 Q-Learning 離開房間的程式的話，我可以假設每一間房為一個 state （state 0 - 4 共五個 state），而「房間外」則為「State 5」 ，所以一共有六個 state：

然後，為了鼓勵人離開房間，每當離開所有房間（也就是去到 State 5），我都會奬勵它 100 分，其餘行動則獲得 0 分：

最後，我們可以用矩陣去表達這個 Markov Decision Chain，當中不存在的事件，我們之後會忽略掉不計。為了整齊，這裏暫時會用 -1 代表：

例子：
如果我在 State 1，想跳去 State 5，將會得到 100 分奬勵。
如果我在 State 2，想跳去 State 3，將會獲得 0 分奬勵。
如果我在 State 4，想跳去 State 1，我們會忽略這個情況，因為並不合法。

簡化版 Q-Learning 算式
定好了 Reward Table，就可以開始 Q-Table 演算。Q-Table 是一個儲存經驗值的矩陣，經過一輪運算，這個 Table 中的數值，將會幫助系統找出最佳解。

以下例子，會用簡化版 (learning rate = 1) 去講解：
（正常版的數式在 Wikipedia 中有提及，但由於比較複雜，所以不在此詳述）

 

運算步驟：

• 首先選一個起點（例子：State 2）和一個終點（離開房間 = State 5）
• 重覆以下步驟，直至到達終點為止：
• 用 Q-Table Equation 更新 Q-Table:
• 任意取下一點 S，獲取奬勵 R，
• 基於 S 點，找出 Q-Table 中最大數值的點（若同樣則任意選一點）
• 將 S 變成現時點，繼續重覆上一步
  

例子（假設 gamma 為 0.8）：

初始值 Q-Table 全為零。

選取起點 State 1，然後從 S=(3,5) 中任意選一點， S=5，
基於 S=5，可以去 (1,4,5) 三點，但 Q-Table 中去三點 (Q(5,1), Q(5,4), Q(5,5)) 均為零，
所以任意選 5，並更新 Q Table 值：Q(1,5) = R(1,5) + 0.8*0 = 100
最後，將 S=5 變成現時點，但由於現時點＝終點，所以計算結束。

選取起點 State 3，然後從 S=(1,2,4) 中任意選一點，S=1，
基於 S=1，可以去 (3,5) 兩點，而 Q-Table 中 Q(1,3)=0, Q(1,5)=100，因選最大，所以選 5。
然後更新 Q Table 值：Q(3,1) = R(3,1) + 0.8*100 = 0+80 = 80
最後，將 S=5 變成現時點，但由於現時點＝終點，所以計算結束。

選取起點 State 0，然後從 S=(4) 中任意選一點，S=4，
基於 S=4，可以去 (3,5) 兩點，而 Q-Table 中 Q(4,3) 和 Q(4,5) 均為零，
所以任意選 3，並更新 Q Table 值： Q(0,4) = R(0,4) + 0.8*0 = 0，
最後，將 S=4 變成現時點，繼續運算：

選取起點 State 4，然後從 S=(3,5) 中任意選一點，S=3，
基於 S=3，可以去 (1,2,4) 三點，而 Q-Table (Q(3,1), Q(3,2), Q(3,4)) 中，
因 Q(3,1)=80 為最大，所以選 1，並更新 Q-Table 值：Q(4,3) = R(4,3) + 0.8*80 = 64，
最後，將 S=1 變成現時點，繼續運算：

選取起點 State 1，然後從 S=(3,5) 中任意選一點， S=5，
基於 S=5，可以去 (1,4,5) 三點，而 Q-Table (Q(5,1), Q(5,4), Q(5,5)) 中，三點均為零，
所以任意選 5，並更新 Q Table 值：Q(1,5) = R(1,5) + 0.8*0 = 100
最後，將 S=5 變成現時點，但由於現時點＝終點，所以計算結束。

經過以上幾輪計算，得出以下 Q-Table 值：
Q(1,5) = 100 / Q(3,1) = 80 / Q(0,4) = 0 / Q(4,3) = 64

若果經過更多輪計算，不同數值將會繼續更新，
但最後，均會大約在以下結果中，開始收歛 (convergence)：

所以，將它換成 Markov Chain 表示的話，將會變成：

如是者，就可以判斷出以下結果：

• 由 2 出發，去 3 可獲得最高奬勵，
• 到 3 之後，任意選 1 或 4 均可得相同奬勵，
• 假設選 1 之後，去 5 可獲得最高奬勵。
• 故此，由 2 出發，到 5 的次序為 [2,3,1,5]
  

程式演示

https://gist.github.com/cmcvista/d5067fe96f66a72824127f1ea44d2820

（由於比較繁複，日後有需要，會再加以解釋。）

---

參考：

[1] - A Painless Q-Learning Tutorial - http://mnemstudio.org/path-finding-q-learning-tutorial.htm

[2] - https://www.learndatasci.com/tutorials/reinforcement-q-learning-scratch-python-openai-gym/

[3] - https://gist.github.com/kastnerkyle/d127197dcfdd8fb888c2

Chameleon Signature 變色龍簽名入門

傳統電子簽名 (Conventional Digital Signature Algorithms)
傳統的電子簽名方法，例如 DSA / ECDSA 等，
主要可分為公鑰 (Public Key) 、私鑰 (Private Key) 以及簽署 (Signature / Digest) 三個部分。

例如，Alice 可以運用自己的私鑰，透過 DSA，得出一份加上了簽署的文件。
然後，Bob 就可以利用 Alice 的公鑰，透過驗證該簽署，去確認文件是由 Alice 所發出的。

過程中，當 Alice 簽署了這份文件，就代表她認同，電子簽署具有以下所有特性：

• 不可偽造性 (Unforgeability): 因為只有 Alice 擁有私鑰，任何人都不可能輕易偽造一份合法的電子簽名，冒認 Alice 已經認可另一份文件。
• 不可爭議性 (Non-Repudiation): 因為簽名難以偽造，一旦 Alice 簽署過這一份文件，她就不可能否認自己已經簽過。情況就有如銀行過數一樣，一旦成功操作，就不可逆轉。
• 可傳播性 (Transferability): 同一個簽名，不但只 Bob 會相信。只要任何一個人擁有 Alice 的公鑰，只要私鑰沒有外泄，他們都一樣會相信 Alice 已經認可這份文件。

然後，有人就提出了一個問題：有沒有一種電子簽名，可以只保留部分特點？
於是，變色龍簽署 (Chameleon Signature) 應運而生。

---

變色龍電子簽名 (Chameleon Signature Algorithms)
在 1997 年左右，Krawczyk 與 Rabin 發表了一種算法 [1]，
透過在 Hash Function 中加多一個後門 (trapdoor)，達至「簽名不變，內容可篡改」的特性。

聽起上來，「可以篡改內容」的電子簽名，就像「沒有用」的簽名，
但實際上，情況卻正好相反，因為：

• 假設 Alice 擁有 K 的公鑰、私鑰和後門，而 Bob 則只有 K 的公私鑰。當一份文件中包含了 K 簽名，這份文件就有可能是由 Alice 或 Bob 所簽署。所以，如果該文件是由 Bob 利用 K 簽發的話，除了 Alice 以外，沒有其他會相信 Bob：因為其他人會質疑 Bob 發出的文件，即使簽名不變、驗證也成功，但因為 Alice 有後門，所以她有可能偷偷改過內容。換句話說，文件中的簽名的可傳播性 (transferability)，就降低到只有 Alice 與 Bob 之間：只有他們兩個，才知道真相如何。
• 同一個例子，如果 Alice 真的偷偷改過文件內容，到「審判」的一天，Bob 就可以拿出原文件，證明自己清白：因為 Bob 沒有後門，要在短時間內，要找出可以產生同一個簽名的文件，幾乎不可能發生。所以，Bob 就可以用自己原文件，向「審判官」證明是 Alice 動了手腳，與己無尤。可見，這種簽名，仍然有一定程度的不可爭議性 (non-repudiatory)。
• 其實整個系統，論安全性而言，基本上與傳統的 DSA 無異：如果黑客沒有私鑰或者後門，簽名同樣難以偽造 (unforgeable)，所以仍然算得上安全。

---

變色龍簽名系統架構
由於涉及數論 (Number Theory) 及 Discrete Log Arithmetic，為避免鑽得太過深入，
以下只提及一些重要元件，數學推算內容則輕輕帶過。

變色龍散列 / 哈希函數 (Chameleon Hash)

• 假設訊息為 m，修改過的訊息為 m'，目標為：ChameleonHash(m) = ChameleonHash(m')
• 只要達到以上目標，產生的簽名 σ = (CH(m), SK) 就自然不變。

初始化

• 隨機產生後門 x ∈ Zp，並計算出變色龍函數公鑰 K = (g, y) = (g, g^x mod p)
• 排除後門的話，它有點像 HMAC 的概念。

ChameleonHash 計算過程（使用公鑰 K 產生）

• 隨機產生臨時變數 r
• 計算出 CH = (g^my^r mod p) = (g^mg^xr mod p) = (g^m+xr mod p)
• 最後得出 (m, r, CH)

ChameleonHash 驗證過程（使用公鑰 K）

• 由於 r 已經提供，計算方法同上，得出 CH2，對比 CH 即可得出結果。

ChameleonHash 的後門 x 使用過程

• 目標：假設已有 CH 及 m'，利用 x 幫助找出 r' 的值。
• 公式：移項後可得出 r' = [ ( m + xr - m' ) / x ] mod q
• 結果得出 (m', r', CH)，當中即使 m 已經改變，但 r 同時更新，故 CH 可以不變。
• 如果黑客沒有 x，找出新的 r 將會變成 DLP 問題 (Discrete Log Problem)。

將 ChameleonHash 與簽名系統結合

• 初始化：
• 產生 Alice 的 DSA 公私鑰 PK_A 及 SK_A（或稱為私鑰 S）
• 產生 ID，CH 的公鑰 K（或稱為公鑰 R）及後門 x
• 簽名：
• 簽署者擁有 K, PK_A, SK_A
• 使用 K 將訊息 m 進行 Chameleon Hash，得出結果 Digest = (m, r, CH)
• 將結果加上 ID，並以 Alice 的私鑰進行 DSA 簽署，得出 σ = Sign_SKA(CH || ID)
• 最後，整個訊息為 (m, r, σ)
• 驗證：
• 任何人均擁有 K, PK_A
• 收到 (m, r, σ) 後，使用 K 及 r 將訊息 m 進行 Chameleon Hash，得出結果 CH
• 將結果加上 ID，再以 DSA 驗證，得出 Result = Verify_PKA((CH || ID), σ)
• 修改內容：
• 修改者需擁有 K 及 x
• 擁有 x 的人可以選擇修改內容（由 m 變成 m'），並得出新的 r 值（r'）
• 由於 Chameleon Hash 值一致，所以不用重新進行 DSA 簽名
• 結果得出 (m', r', σ)

如是者，系統將有公鑰 (Public Key) 、私鑰 (Private Key) 、變色龍公鑰 (K)、變色龍後門 (Trapdoor x)，以及簽署 (Signature / Digest) 五個部分。

---

變色龍簽名（或散列）的應用

現實生活中，這種簽名的應用仍未普及，以下為一些可行例子：

• 公開記帳系統 (Open Ledger) [2]：
  假設 Alice 想給 Bob 10% 的家財，Alice 可以立下單據，並用 Bob 的給予的變色龍公鑰 K 及自己的電子簽名私鑰 SK 進行變色龍簽名，然後將簽名公開。這樣，每一個外人都可以見證這一個簽名，但卻不會完全相信 Alice 與 Bob 之間的約定（因為 Bob 有後門可以修改內容）。這種方法，可以以保障 Alice 和 Bob 之間的約定，有多人見證，但同時也不會因外人妒忌，而影響自己的人身安全。假若有一天，Bob 真的偷偷改掉內容，Alice 只需向大家公開原單據，就可以證明自己清白。
• 可修改式區塊鏈 (Redactable Blockchain)：
  在一些私人區塊鏈中，給予某方（例如管理層）最大權力，保留可改性，可以防止因為錯誤決定，或者資料問題，而導致整個系統不可用的情況。例如當 GPDR 私隱條例實施後，管理層就可以決定先暫停一下區塊鏈網絡，然後將所有敏感資料，從區塊鏈中擦去，最後重新啟動系統。系統根據 Longest Chain Rule，就會在日後自動抹去舊的區塊鏈，如是者，管理員就不必重新建立整個系統。
• RUSH 5G Handover 系統：
  這篇由 Y. Zhang 發布的論文 [3]，也提到 Chameleon Hash 的應用。
  內容主要是用作 mutual authentication。

---

參考：

[1]: Krawczyk, Hugo, and Tal Rabin. "Chameleon hashing and signatures." Internet-https://pdfs.semanticscholar.org/1c29/4428c76ba7d1d0bb5e1d1bc931138c092453.pdf (1997).

[2]: 哈希（Chameleon Hash）、零知识证明（Zero—Knowledge Proof）和广播加密相关知识, MUZIBing's BLOG, https://muzibing.github.io/2019/10/12/2019.10.12%EF%BC%8885%EF%BC%89/#%E4%B8%80%E3%80%81%E5%8F%98%E8%89%B2%E9%BE%99%E5%93%88%E5%B8%8C%EF%BC%88Chameleon-Hash%EF%BC%89

[3]: Y. Zhang, R. Deng, E. Bertino, and D. Zheng, “Robust and Universal Seamless Handover Authentication in 5G HetNets,” IEEE Trans. Dependable Secur. Comput., vol. 47907, no. c, pp. 1–1, 2019, doi: 10.1109/tdsc.2019.2927664.

Practical Byzantine Fault Tolerance (pBFT) 實用拜占庭容錯入門

入門：拜占庭將軍問題 (Byzantine Genreals Problem)
拜占庭帝國 (Byzantine Empire) 是一個幅員很廣的古代國家，
所以，軍隊之間要一起行動，必須先遠程溝通，協商，
獲得可靠的共識，最後一致進攻，才能成事。

不過，由於不同軍隊之間距離偏遠，古代每個將軍只能用密函互傳訊息。
同時，由於敵方也知道我方軍隊的兵力相當，
所以，它們也派了一些間諜將軍，希望可以傳一些錯誤的訊息，打亂我方的陣腳。

投票
假設我方有 7 個每個將軍，每人都可以傳一封密函給其他將軍一次。
這 7 個（故意選單數，避免票數打和）將軍當中，有 1 個是間諜，6 個是誠實的。
每個人需要投票表示「進攻」和「防守」，多數服從少數。

如果誠實的將軍中，有 3 位投贊成，3 位投反對，
間諜就可以向那 3 位投進攻的將軍表示投進攻，同時向那 3 位投防守的人表示投防守。

這樣，3 個贊成進攻的將軍，就會以為自己是大多數，所以進攻。
同時，3 個贊成防守的將軍，也會因為以為自己是大多數，所以防守。
最後，由於大家沒有可靠的共識 (reliable consensus)，就會有人出兵，有人留城，
整個戰爭將會慘敗。

共識
假設進攻由一個將軍決定，當將軍們都收到其他將軍的肯定，就可以進攻。
現在，假設整個帝國有 6 個將軍，但每一個將軍都只收到 3 封回音。

如果原因是因為，有 2 個將軍的飛馬傳信失敗，同時又有 2 個成功的傳信是來自間諜。
這樣，憑著收回來的 3 個訊息（2 個來自間諜，1 個來自將軍。有 2 封掉失，1 封自己），
將軍也無法肯定是否應該進攻。

科學家稱這兩種攻擊方法為「拜占庭攻擊 (Byzantine Attack)」，
而這兩種錯誤的情況，則稱之為「拜占庭錯誤 (Byzantine Fault)」。

解決方法：CFT 與 BFT
現今世界中，共識算法 (Consensus Algorithm) 正正就是解決以上問題的重要工具。
共識算法主要可分為兩種： Crash Fault Tolerance (CFT) 和 Byzantine Fault Tolerance (BFT)。

CFT 主要指將軍沒有回應，或者訊息間傳遞失敗；
而 BFT 則更進一步，既針對訊息傳遞問題，也考慮到會有間諜在其中作惡。

Practical Byzantine Fault Tolerance (pBFT) 實用拜占庭容錯
在 1999 年，Miguel Castro 及 Barbara Liskov 提出了一個針對 BFT 的解決方案，稱為 pBFT。

假設有 f 個間諜的話，pBFT 需要有 3f+1 個節點 (replica)，才能要防止間諜影響共識。
換句話說，在 7 個節點的系統，如果運行 pBFT，只容許有 2 個間諜存在 (3*2+1=7)。

當中 3f+1 的證法比較複雜，詳細可參考 [2] 中的證法。有另一個證法：
假設系統中有 R 個節點，當中有 k 個忠誠節點，有 f 個非法節點。
如果目前 k 個忠誠節點中，有  f 個下了線，然後 f 個非法節點又同時發出假消息，
要阻止假消息「成真」，剩餘的 k-f 必須要比 f 大，
所以得出 k-f > f，也就是 k > 2f，
因為 R = k+f，所以也得出 R-f > 2f，也就是 R > 3f。

整個系統有五大階段：

1. Request: 
用戶 (Request Client) 發送一個 request 去主節點去寫入訊息 m。

2. Pre-Prepare: 
主節點會以 multicast 形式，發送 Pre-Prepare 指令去其他各節點。

3. Prepare: 
當每一個節點收到來自其他節點的 Pre-Prepare，並且驗證過內容為相同及正確後，
就會以 multicast 發送 Prepare 去其他節點。

4. Commit:
當各節點收到 2f+1（包括它自己）的 Prepare 訊息後，就會進入 Prepared 狀態。
然後，各節點就會發送 Commit 去其他節點。

5. Reply:
當各節點收到 2f+1（包括它自己）的 Commit 訊息後，就會進入 Committed 狀態。
然後，各節點就會傳送 Reply 給 Request Client。
當 Client 收到最少 f+1 （還是 2f+1？）個 Reply，就可以確認整個系統已經寫入共識 m。

6. Checkpoint:
系統會偶爾用 checkpoint 作為舊記錄的封存，
以防止他日重開系統，需要由頭開始計起（及驗證）共識值。

pBFT 的潛在問題
pBFT 有以下兩個主要特點：

• pBFT 假設 malicious node 只是行為怪異，但並不考慮資料外泄問題。
  換言之，pBFT 只能在相信每一個 replica 中的資料並不私隱的情況下，才能運作。

• pBFT 需要大量的 multicast 訊息傳播。
  當系統變得越大，訊息量將會指數性增加，令系統負擔變大。

---

參考：

[1]: Castro, Miguel, and Barbara Liskov. "Practical Byzantine fault tolerance." OSDI. Vol. 99. No. 1999. 1999. (http://pmg.csail.mit.edu/papers/osdi99.pdf)

[2]: Bracha, Gabriel, and Sam Toueg. "Asynchronous consensus and broadcast protocols." Journal of the ACM (JACM) 32.4 (1985): 824-840.(https://zoo.cs.yale.edu/classes/cs426/2012/bib/bracha85asynchronous.pdf)

[3]: https://medium.com/coinmonks/pbft-understanding-the-algorithm-b7a7869650ae

[4]: https://zhuanlan.zhihu.com/p/56780298