Merkle Tree 和 Bitcoin 的關係

Merkle Tree 入門

要確保整串非常長的資料（例如區塊鏈）的完整性，理論上，我們可以有幾種方法：

• 直接將整條資料 Hash 成一個 hash value
  
• 將資料斬成一個一個區塊 (block)，然後下一個 block 記低上一個 block 的 hash value
• 將資料斬成一個一個區塊 (block)，然後算出每個 block 的 hash value，最後以 binary tree 形色不斷向上計算，直至得到最後一個 hashed value，又稱為 Merkle Root

Merkle Tree 指就是第三種方法。當 block 數量為雙數時，Merkle Root 可以這樣得出 [1]：

簡單而言，就是計算 L1 - L4 的 Hash，得出 H(L1) - H(L4)，

然後計算 H0 = H(H(L1) || H(L2)) 和 H0 = H(H(L3) || H(L4))，

最後計算 Merkle Root = H(H0 || H1)。

當 Block 數為單數時，以上圖為例，假設只有 L1-L3，我們就可以：

假設有一個 block L4 = L3，

然後故技重施，最後得出 Merkle Root。

當 Block 數為單數，並導致上一層也是單數，我們也同樣故技重施，直至單數消失。

這種架構，對於本身資料結構已經是 linked list 的區塊鏈 (Blockchain) 來講特別方便。

因為不需要花額外的工作處理資料切割，就能直接用這個方法，確保資料完整性。

而且當區塊鏈不斷變長，我們也不需要重新計算舊的區塊，變相可以刪掉舊區塊節省空間。

（例如當加入 L5， 我們並不需重新計過 H(L1) ~ H(L4)，也可以找到 Merkle Root）

Merkle Tree 在 Bitcoin 的應用

作為第一個引人注目的 Blockchain 應用，Bitcoin 中同樣引入了 Merkle Tree，

而它的出發點同樣是想保護整條 Block 的完整性。

我們可先看一下 Bitcoin 的 header 架構 [2]：

Bytes	Name	Data Type	Description
4	version	int32_t	The block version number
32	previous block header hash	char[32]	A SHA256(SHA256()) hash in internal byte order of the previous block’s header. This ensures no previous block can be changed without also changing this block’s header.
32	merkle root hash	char[32]	A SHA256(SHA256()) hash in internal byte order. The merkle root is derived from the hashes of all transactions included in this block, ensuring that none of those transactions can be modified without modifying the header.
4	time	uint32_t	The block time is a Unix epoch time when the miner started hashing the header (according to the miner).
4	nBits	uint32_t	An encoded version of the target threshold
4	nonce	uint32_t	An arbitrary number miners change to modify the header hash in order to produce a hash less than or equal to the target threshold.

當中可見，Previous Block Header Hash 是用來確保上一個 block 的合法性。理論上，我們如果要確定任何一個 block 是否合法，最簡單的方法，就是用這個欄目，一直追溯直至第一個 block（又稱作 Coinbase）即可。但這種做法，將會耗費大量時間，所以理論上可行，實際上卻十分困難。

Bitcoin 的發明者 Satoshi Nakamoto 似乎一早就發現這個情況，所以他增加了 Merkle Root Hash 這個項目。自此，如果你要確認某一個 block，你只需要重新找出該 block 的 H(block)，然後向上推演，計出 Merkle Root，再比對 chain head 中的 Merkle Root Hash 是否相等即可。根據 [3] 所指，要推算任何一個 block，理論上只需要 2*log2(N) 次計算，變相快速有效得多。

Merkle Tree 其他應用

Merkle Tree 提供一種便捷的驗證方法，所以一直有不少地方均用到。

例如 Tor，Git，SEMUD [4] 等等。

---

參考：

[1] - https://en.wikipedia.org/wiki/Merkle_tree#/media/File:Hash_Tree.svg

[2] - https://bitcoin.org/en/developer-reference#block-headers

[3] - Mastering Bitcoin by Andreas M. Antonopoulos - https://www.oreilly.com/library/view/mastering-bitcoin/9781491902639/ch07.html

[4] - http://ieeexplore.ieee.org/document/8264846/

Schnorr Signature 簡介

Schnorr Signature 的動機

提到電子簽名，最常見的包括以 RSA 為基礎的 RSA，或者以橢圓曲線為基礎的 ECDSA。

這些算法雖然普遍，但普遍來講因為算法複雜，耗時也比較高。

Schnorr Signature 就是基於這個背景下產生的：由於它算法簡單易明，速度也比較快。

Schnorr Signature 的算法簡介

1. 初始化：

• 首先產生一個 Schnorr Group Parameters，得出 generator (g) 和 prime order (q)。
• 選取一個 cryptographic hash function H。
  

2. 產生 Key：

• 隨機產生一個 x，這個 x 必需與 q 是 relatively prime，這個將成為 Private Key。
  
• 運用 y = g^x 產生 y，這個成為 Public Key。

3. 簽名：

• 隨機產生一個 k，這個 k 必需與 q 是 relatively prime
• 計算 r = g^k
• 計算 e = H( r || M ) 或可寫作 H ( g^k || M )，當中 M 是訊息，|| 指組連 (concatenate)
• 計算 s = k - xe，或可寫作 s = k - x*H( g^k || M )
• 公布 (s, e) 出去，也可以寫成 ( k-xe, e )，這個就是 Schnorr Signature 簽名 (digest)。 
  

PS：如果 prime order 是小於 2^160 (160 bit) 的話，基本上 s 和 e 各佔不多於 40 bytes (320 bits)。

PS2：過程當中，簽署方必須小心，k 的數值必須每次不同，否則如果有兩條不同 M，其他人就可以透過得出的 s 和 s'，透過相減約走 k，繼而找出 x：

• s - s' = (k-xe) - (k'-xe') = (k-k') - x(e-e') = 0 - x(e-e')
• 因為 e' 和 e' 均是由相同的 g^k 疊加已知的 M 或 M' 再 hash 而成，
  所以只要不斷撞，很大機會能找回 concat 的 g^k 值到底是什麼，最後找回 x。
  

4. 驗證簽名：

• 手持 Public Key y = g^x
• 計算 r_verify = g^s * y^e = g^(k - xe) * g^(xe) = g^( k - xe + xe ) = g^k
• 計算 e_verify = H ( r_verify || M ) = H ( g^k || M )
• 如果 e_verify 與 e 相等，簽名則為有效。

Schnorr Signature 的缺點

由於它計算快捷，普遍來講，相對其他複雜的算法，它更易撞到，也就是更容易破解。

所以，一般而言，密碼學家認為它需要比其他算法長 4 倍，才能達到相近的強度。例如 NIST 256-bit 來講，Schnorr Signature 最少需要 1024 bit 簽名長度，才能達到 ECDSA 的 ECDSAwithSHA256 (256 bit) 簽名相等的安全性。

（也有其他新的論文提到了 Short Schnorr Signature，它的長度能減少至 3t 右右。）

基於橢圓曲線 (Elliptic Curve) 的 Schnorr Signature

有一種算法 EdDSA，正正使用相類似的原理運作。

它採用特殊的曲線，達至相類似的效果。而且廢除了隨機產生的 k，減低密碼外流的風險。

---

參考：

[1] - https://en.wikipedia.org/wiki/Schnorr_signature

Multi Factor Multi Level ANOVA 概念入門

簡介
普遍來講，一個實驗會涉及非常多不同的變數。例如：想提升溶液的溶解度，我們可以選擇不同溶液、不同温度、不同攪拌速度、不同容器等等。又例如：想提升機器學習的效能，我們可以選擇不同神經網絡、不同深度、不同參數等。當中，我們希望找出最關鍵的變數，以達至用最低的成本，提供最高的效果。這個就是 2-way / 3-Way / N-Way ANOVA 的目標。

與 One-Way ANOVA (Single Factor ANOVA) 相似之處，N-Way ANOVA 的出發點，同樣是找出 μ1, μ2 ... μN 是否一致。不過，因為 ANOVA 能找出每個因子的重要性 (significance of each factors)，所以它常被用作找出關鍵因子 (key factors) 的方法。

條件
所有假設條件與 One-Way ANOVA 一樣，除了可以有多個不同因子。

界定準則
與 One-Way ANOVA 一樣，它一樣能找出「這個因子 跟 實驗誤差 之間，到底有多大差距」。而且，由於 N-Way ANOVA 涉及多種變數，它也會找出「兩個（或以上）因子結合」的結果，繼而可以發現出不同因子之間千絲萬縷的關係。

用溶液溶解度的例子來講，我們不但可以找出「温度上升」、「攪拌速度上升」、「使用 B 溶液」可以提高溶解度，更能找到「温度上升＋攪拌速度上升」、「使用 C 溶液＋低温」、「使用 A 溶液＋温度上升＋攪拌速度上升」等的不同組合帶來的互動效果 (interaction effect)。對於找出奇怪的組合，十分有幫助。（例如用雞蛋汁做溶液的話，低温效果更好，所以高温並不一定能提升溶解度）

公式
以下只列出 Two-Way ANOVA 的公式，因為 N-Way ANOVA 涉及的公式太多，而且只是 Two-Way ANOVA 的延伸，更何況可交給電腦處理，所以就在此處省略掉。

假設數據的確會因為因子改變而改變，我們就可以用以下公式 (effect model) 表達其關係，當中 y 是指單一實驗結果，μ 是指總平均 (global mean)，τ 是指因子 A 變化產生的影響，β 是指因子 B 變化產生的影響，ε 則指各數據與總平均之間的誤差：

由此可見，若果因子 A 變化的確會影響實驗結果的話，τ 的數值一定需要十分明顯，甚至必須比 ε 大得多，β 及 (τβ) 亦同理。從以上觀察，我們可以推算下面的公式：

以溶液實驗作為例子，假設 A 因子為溶液温度 (3 levels, 25°C / 50°C / 70°C)，B 因子為攪拌速度 (2 levels, 10 rpm / 20 rpm)，每個實驗重覆 4 次 (n = 4 replicates)。

• SSA (Sum of Square of Factor A) 指：
  溶液在 25 度的平均，減去總平均，再次方，加上
  溶液在 50 度的平均，減去總平均，再次方，加上
  溶液在 70 度的平均，減去總平均，再次方，
  然後除以 4 得到「溶液在三種不同温度的平均方差」，
  再除 b (2) 得到「溶液在三種不同温度，面對兩種攪拌速度的平均方差」。
• SSB (Sum of Square of Factor B) 指：
  溶液在 10 rpm  速度的平均，減去總平均，再次方，加上
  溶液在 20 rpm  速度的平均，減去總平均，再次方，
  然後除以 4 得到「溶液在兩種不同攪拌速度的平均方差」，
  再除 a (2) 得到「溶液在兩種不同温度，面對三種温度的平均方差」。
• SSAB (Sum of Square of Factor AB) 指：
  10 rpm  + 25°C 的平均，減去 25°C 的總平均，再減去 10 rpm 的總平均，再加總平均，再次方，如此類推，目標得出「溶液在固定温度與攪拌速度下的平均方差」。

系統化的公式表列示如下：

界定準則與判定
跟 One-Way 檢測一樣，我們同樣使用 Significance Level (α) 及 F-distribution 來判斷。

補充資料：使用 F-distribution 的原因，主要是因為兩個 Chi-Square Distribution 相除的結果，而 SS 因為是二次方，所以是 t-Distribution 的二次方，也就是 Chi-Square Distribution。而使用 t-Distribution 的原因，是因為數據中的 variance 是估計而得。這段不明白也不重要，只需知道如何使用公式表或電腦運算即可。


使用電腦運算 
使用圖形化的 SPSS 可參考：https://statistics.laerd.com/spss-tutorials/two-way-anova-using-spss-statistics.php
使用 MATLAB 可參考：https://www.mathworks.com/help/stats/anova2.html

小結
N-Way ANOVA 對於 Factor Screening 特別有用，因為可以從多個因子中選擇較重要的因子，並將不必要的因子除掉，令日後的實驗步驟得以簡化。同時，選取重要因子，可以幫助我們以更少的成本，提升系統整體效能。當然，有時候，即使該因子的統計重要性 (statistical significance) 再高，我們也要考慮現實的重要性 (practical significance)。換句話說，有時候知道結果，也未必可以減低成本（例如提升温度代表需要更多電力）。這個時候，我們就需要更深入的 cost optimization 和 opportunity cost calculation，才能做出正確決定。