ref: https://vivek-singh.medium.com/system-design-cheat-sheet-318ba2e34723

本篇文章是一個筆記文，紀錄關於 System Design 路上常遇到的架構與元件，譬如
1. LoadBalancer
2. Caches
3. Queues
4. Configuration Service
5. API Gateway
6. Service Mesh
7. CDN
8. Cassandra
9. Snowflake
10. Numbers

每個概念都還會附上一些相關影片與文章，也因為是個筆記內容，因此每個元件的介紹都不會非常詳細，都是小小段落介紹每個元件的最基本概念。
譬如 LoadBalancer 的筆記有
1. L4/L7 兩種的差異
2. AWS 上 ELB/ALB/NLB 的三種差異
3. LB 的演算法， Round Robin,Weighted RR, Least Connection/Response Time/Resource based 等

Caches
1. 實作有 Memcached, Redis 等相關專案
2. 什麼時候會使用 Memcached:
a. 需求簡單，譬如單純 Key/Value 字串，可以輕易地透過調整 cores/threads 來調整效能。
b. Volatile，沒有儲存機制
c. 只有 LRU 的 Cache 演算法
d. Key 最多 250B, Value 最多 1MB
3. 什麼時候使用 Redis
a. 需要儲存 object，而非單純 string
b. 支援多種演算法
c. 支援 data store，可以達到 non-volatile 效果
d. 可以支援 Set/Hash/List/Sorted Set 不同型態

這類型的文章對於踏入 System Design 能夠提供一個簡易的入門介紹，先有哪些類別需要學習，再針對每個類別獨立學習也是一個不錯的學習路徑。

🌳線上課程介紹：目標導向的行動計劃遊戲開發的高階人工智慧( AI )

使用人工智慧( AI )創造複雜的遊戲角色行為模擬、即時戰略遊戲等

目標導向的行動計劃（GOAP，Goal-Oriented Action Planning ）是一種 AI 架構，可為遊戲角色提供選擇目標的能力，並根據環境狀況和可用資源制定計劃以實現這些目標。它可以用於從第一人稱射擊遊戲( first-person shooters )到即時戰略的各種遊戲類型，以開發不需要大型有限狀態機( finite state machines )下能夠做出明智決策的智能角色。該程式碼基底( codebase )看似簡單，但又邏輯合理，可重用且功能強大。該程式庫使用 C＃編寫並在 Unity V.2019 中實現，但是可以輕鬆移植到其他應用程式。

在本課程中，Penny 憑藉其享譽國際的教學風格和 25 年來與遊戲、圖形學相關的知識，還有其撰寫過兩本屢獲殊榮的 AI 遊戲書籍，揭秘了 GOAP 的先進 AI 技術，該技術用於在遊戲中創建真實可信的遊戲角色。在整個課程中，你將跟隨著進度動手實踐，老師將帶你完成建構自己的 GOAP API 的每一步。你將從頭開始建構整個 GOAP 程式庫，同時平行建構醫院模擬方案，以在運行時測試 API。

學習如何做程式設計並運用 :

✅ 可廣泛用於各種程式專案的 GOAP 程式庫和 API
✅ 定義遊戲環境狀態的目標、行動、狀態和相信，這些個別角色想做以及他們對自己的世界的認知
✅ 提供高級路徑的導航網格( Meshes )和代理( Agents )
✅ 角色的計畫與導航能力
✅ 導航網路 ( NavMeshes ) 的動態建立允許環境裡的資源重新定位
✅ 每個角色的倉儲( inventories )以用來完成任務達成角色的目標
✅ Unity UI 系統上移動可拉動的資源到一個遊戲環境中

🔥 對這個課程有興趣請參考底下留言區，目前特價中

📜 [專欄新文章] Merkle Tree in JavaScript

✍️ Johnson

📥 歡迎投稿： https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium

這篇文章會說明 Merkle Tree 的運作原理，以及解釋 Merkle Proofs 的用意，並以 JavaScript / TypeScript 簡單實作出來。

本文為 Tornado Cash 研究系列的 Part 1，本系列以 tornado-core 為教材，學習開發 ZKP 的應用，另兩篇為：

Part 2：ZKP 與智能合約的開發入門

Part 3：Tornado Cash 實例解析

Special thanks to C.C. Liang for review and enlightenment.

本文中實作的 Merkle Tree 是以 TypeScript 重寫的版本，原始版本為 tornado-core 以 JavaScript 實作而成，基本上大同小異。

Merkle Tree 的原理

在理解 Merkle Tree 之前，最基本的先備知識是 hash function，利用 hash 我們可以對資料進行雜湊，而雜湊後的值是不可逆的，假設我們要對 x 值做雜湊，就以 H(x) 來表示，更多內容可參考：

一次搞懂密碼學中的三兄弟 — Encode、Encrypt 跟 Hash

SHA256 Online

而所謂的 Merkle Tree 就是利用特定的 hash function，將一大批資料兩兩進行雜湊，最後產生一個最頂層的雜湊值 root。

當有一筆資料假設是const leaves = [A, B, C, D]，我們就用function Hash(left, right)，開始製作這顆樹，產生H(H(A) + H(B))與H(H(C) + H(D))，再將這兩個值再做一次 Hash 變成 H(H(H(A) + H(B)) + H(H(C) + H(D)))，就會得到這批資料的唯一值，也就是 root。

本文中使用的命名如下：

root：Merkle Tree 最頂端的值，特色是只要底下的資料一有變動，root 值就會改變。

leaf：指單一個資料，如 H(A)。

levels：指樹的高度 (height)，以上述 4 個資料的假設，製作出來的 levels 是 2，levels 通常會作為遞迴的次數。

leaves：指 Merkle Tree 上的所有資料，如上述例子中的 H(A), H(B), H(C), H(D)。leaves 的數量會決定樹的 levels，公式是 leaves.length == 2**levels，這段建議先想清楚！

node：指的是非 leaves 也非 root 的節點，或稱作 branch，如上述例子中的H(H(A) + H(B)) 和 H(H(C) + H(D))。

index：指某個 leaf 所在的位置，leaf = leaves[index]，index 如果是偶數，leaf 一定在左邊，如果是奇數 leaf 一定在右邊。

Merkle Proofs

Merkle Proofs 的重點就是要證明資料有沒有在樹上。

如何證明？就是提供要證明的 leaf 以及其相對應的路徑 (path) ，經過計算後一旦能夠產生所需要的 root，就能證明這個 leaf 在這顆樹上。

因此這類要判斷資料有無在樹上的證明，類似的說法有：proving inclusion, proving existence, or proving membership。

這個 proof 的特點在於，我們只提供 leaf 和 path 就可以算出 root，而不需要提供所有的資料 (leaves) 去重新計算整顆 Merkle Tree。這讓我們在驗證資料有沒有在樹上時，不需要花費大量的計算時間，更棒的是，這讓我們只需要儲存 root 就好，而不需要儲存所有的資料。

在區塊鏈上，儲存資料的成本通常很高，也因此 Merkle Tree 的設計往往成為擴容上的重點。

我們知道 n 層的 Merkle Tree 可以存放 2**n 個葉子，以 Tornado Cash 的設計來說，他們設定 Merkle Tree 有 20 層，也就是一顆樹上會有 2**20 = 1048576 個葉子，而我們用一個 root 就代表了這 1048576 筆資料。

接續上段的例子，這顆 20 層的 Merkle Tree 所產生的 Proof ，其路徑 (path) 要從最底下的葉子 hash 幾次才能到達頂端的 root 呢？答案就是跟一棵樹的 levels 一樣，我們要驗證 Proof 所要遞迴的次數就會是 20 次。

在實作之前，我們先來看 MerkleTree 在 client 端是怎麼調用的，這有助於我們理解 Merkle Proofs 在做什麼。

基本上一個 proof 的場景會有兩個人：prover 與 verifier。

在給定一筆 leaves 的樹，必定產生一特定 root。prover 標示他的 leaf 在樹上的 index 等於 2，也就是 leaves[2] == 30，以此來產生一個 proof，這個 proof 的內容大致上會是這個樣子：

對 verifier 來說，他要驗證這個 proof，就是用裡面的 leaf 去一個一個與 pathElements 的值做 hash，上述就是 H('30', 40) 後得出 node，再 hash 一次 H('19786...', node) 於是就能得出這棵樹的 root。

重點來了，這麼做有什麼意義？它的巧思在於對 verifier 來說，他只需要儲存一個 root，由 prover 提交證明給他，經過計算後產生的 root 如果跟 verifier 儲存的 root 一樣，那就證明了 prover 所提供的資料確實存在於這個樹上。

而 verifier 若不透過 proof ，要驗證某個 leaf 是否存在於樹上，也可以把 leaves = [10, 20 ,leaf ,40]整筆資料拿去做 MerkleTree 的演算法跑一趟也能產生特定的 root。

但由 prover 先行計算後所提交的 proof，讓 verifier 不必儲存整批資料，也省去了大量的計算時間，即可做出某資料有無在 Merkle Tree 上的判斷。

Sparse Merkle Tree

上述能夠證明資料有無在樹上的 Merkle Proofs 是屬於標準的 Merkle Tree 的功能。但接下來我們要實作的是稍微不一樣的樹，叫做 Sparse Merkle Tree。

Sparse Merkle Tree 的特色在於除了 proving inclusion 之外，還可以 proving non-inclusion。也就是能夠證明某筆資料不在某個 index，例如 H(A) 不在 index 2 ，這是一般 Merkle Tree 沒辦法做到的。

而要做到 non-membership 的功能其實也不難，就是我們要在沒有資料的葉子裡補上 zero value，或是說 null 值。更多內容請參考：What’s a Sparse Merkle Tree。

實作細節

本節將完整的程式碼分成三個片段來解釋。

首先，這裡使用的 Hash Function 是 MiMC，主要是為了之後在 ZKP 專案上的效率考量，你可以替換成其他較常見的 hash function 例如 node.js 內建 crypto 的 sha256：

crypto.createHash("sha256").update(data.toString()).digest("hex");

這裡定義簡單的 Merkle Tree 介面有 root, proof, and insert。

首先我們必須先給定這顆樹的 levels，也就是樹的高度先決定好，樹所能容納的資料量也因此固定為 2**levels 筆資料，至於要不要有 defaultLeaves 則看創建 Merkle Tree 的 client 自行決定，如果有 defaultLeaves 的話，constructor 就會跑下方一大段計算，對 default 資料開始作 hash 去建立 Merkle Tree。

如果沒有 defaultLeaves，我們的樹也不會是空白的，因為這是顆 Sparse Merkle Tree，這裡使用 zeroValue 作為沒有填上資料的值，zeros 陣列會儲存不同 level 所應該使用的 zero value。假設我們已經填上第 0 筆與第 1 筆資料，要填上第 2 筆資料時，第 2 筆資料就要跟 zeros[0] 做 hash，第 2 筆放左邊， zero value 放右邊。

我們將所有的點不論是 leaf, node, root 都用標籤 (index) 標示，並以 key-value 的形式儲存在 storage 裡面。例如第 0 筆資料會是 0–0，第 1 筆會是 0–1，這兩個 hash 後的節點 (node) 會是 1–0。假設 levels 是 2，1–0 節點就要跟 1–1 節點做 hash，即可產出 root (2–0)。

後半部份的重點在於 proof，先把 proof 和 traverse 看懂，基本上就算是打通任督二脈了，之後有興趣再看 insert 和 update。

sibling 是指要和 current 一起 hashLeftRight 的值…也就是相鄰在兩旁的 leaf (or node)。

到這裡程式碼的部分就結束了。

最後，讓我們回到一開始 client 調用 merkleTree 的例子：

以及 proof 的內容：

前面略過了 proof 裡頭的 pathIndices，pathIndices 告訴你的是當前的 leaf (or node) 是要放在左邊，還是放在右邊，大概是這個樣子：

if (indices == 0) hash(A, B);if (indices == 1) hash(B, A);

有興趣的讀者可以實作 verify function 看看就會知道了！

原始碼

TypeScript from gist

JavaScript from tornado-core

參考

Merkle Proofs Explained

What’s a Sparse Merkle Tree?

延伸：Verkle Tree

Merkle Tree in JavaScript was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.

👏 歡迎轉載分享鼓掌

從EXCEL VBA到Python開發第1次上課(問卷結果&課程綱要與下載懶人包&ECLIPSE連結PYTHON與建立專案&修改語系與轉型與環境設定&年齡邏輯判斷)

01_課前問卷與下載懶人包
02_課程說明與開啟ECLIPSE
03_在ECLIPSE中設定PYTHON路徑
04_建立專案與模組並撰寫程式
05_編輯器字型放大縮小與算術運算子
06_修改編碼為UTF8與轉型為字串
07_下載PYTHON與ECLISPE手動建立環境與變數型態
08_型別轉換與串列與脫逸字元
09_流程控制撰寫年齡判斷程式

完整教學
http://goo.gl/aQTMFS

吳老師教學論壇
http://www.tqc.idv.tw/

教學論壇(之後課程會放論壇上課學員請自行加入)：
https://groups.google.com/forum/#!forum/scu_python109

懶人包：
EXCEL函數與VBA http://terry28853669.pixnet.net/blog/category/list/1384521
EXCEL VBA自動化教學 http://terry28853669.pixnet.net/blog/category/list/1384524

課程簡介：入門
建置Python開發環境
基本語法與結構控制
迴圈、資料結構及函式
VBA重要函數到Python
檔案處理
資料庫處理
課程簡介：進階
網頁資料擷取與分析、Python網頁測試自動化、YouTube影片下載器
處理 Excel 試算表、處理 PDF 與 Word 文件、處理 CSV 檔和 JSON 資料
實戰：PM2.5即時監測顯示器、Email 和文字簡訊、處理影像圖片、以 GUI 自動化來控制鍵盤和滑鼠

上課用書：
參考書目
Python初學特訓班(附250分鐘影音教學/範例程式)
作者： 鄧文淵/總監製, 文淵閣工作室/編著?
出版社：碁峰? 出版日期：2016/11/29

Python程式設計入門
作者：葉難
ISBN：9789864340057
出版社：博碩文化
出版日期：2015/04/02

吳老師 109/2/11

EXCEL,VBA,Python,自強工業基金會,EXCEL,VBA,函數,程式設計,線上教學,PYTHON安裝環境

文大Python程式入門或證照第1次課程介紹與安裝環境&下載ECLIPSE&設定工作區&安裝PYTHON外掛&編輯環境自行放大與修改編碼方式與轉型&輸出資料型別與型別轉換練習&變數的型別與轉換&證照考題

上課內容：
01_課程介紹與安裝環境
02_下載ECLIPSE說明
03_解壓縮ECLIPSE與設定工作區
04_安裝PYTHON外掛
05_設定PYTHON實體路徑與建立專案
06_編輯環境自行放大與修改編碼方式與轉型
07_輸出資料型別與型別轉換練習
08_變數的型別與轉換
09_證照考題題型說明

完整影音
http://goo.gl/aQTMFS

教學論壇(之後課程會放論壇上課學員請自行加入)：
https://groups.google.com/forum/#!forum/pccu_python_2018_2

懶人包：
EXCEL函數與VBA http://terry28853669.pixnet.net/blog/category/list/1384521
EXCEL VBA自動化教學 http://terry28853669.pixnet.net/blog/category/list/1384524

TQC+Python證照目錄：
Python 第1類：基本程式設計
技能內容：變數與常數、指定敘述、標準輸入輸出、運算式、算術運算子、數學函式的應用、格式化的輸出Python 第2類：選擇敘述
技能內容：if、if...else、if…elif
Python 第3類：迴圈敘述
技能內容：while、for…in
Python 第4類：進階控制流程
技能內容：常用的控制結構、條件判斷、迴圈
Python 第5類：函式(Function)
技能內容：函式使用、傳遞參數、回傳資料、內建函式、區域變數與全域變數
Python 第6類：串列(List)的運作(一維、二維以及多維)
技能內容：串列的建立、串列的函式、串列參數傳遞、串列應用
Python 第7類：數組（Tuple）、集合（Set）以及詞典（Dictionary）
技能內容：數組、集合、詞典的建立、運作及應用
Python 第8類：字串(String)的運作
技能內容：字串的建立、字串的庫存函式、字串的應用
Python 第9類：檔案與異常處理
技能內容：文字I/O、檔案的建立、寫入資料與讀取資料、二進位I/O、編碼（Encoding）、異常處理

課程簡介：入門
建置Python開發環境
基本語法與結構控制
迴圈、資料結構及函式
VBA重要函數到Python
檔案處理
資料庫處理
課程簡介：進階
網頁資料擷取與分析、Python網頁測試自動化、YouTube影片下載器
處理 Excel 試算表、處理 PDF 與 Word 文件、處理 CSV 檔和 JSON 資料
實戰：PM2.5即時監測顯示器、Email 和文字簡訊、處理影像圖片、以 GUI 自動化來控制鍵盤和滑鼠

上課用書：
參考書目
Python初學特訓班(附250分鐘影音教學/範例程式)
作者： 鄧文淵/總監製, 文淵閣工作室/編著
出版社：碁峰? 出版日期：2016/11/29

吳老師 107/12/3

EXCEL,VBA,Python,文化推廣部,EXCEL,VBA,函數,程式設計,線上教學,PYTHON安裝環境