📜 [專欄新文章] ZKP 與智能合約的開發入門
✍️ Johnson
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
這篇文章將以程式碼範例,說明 Zero Knowledge Proofs 與智能合約的結合,能夠為以太坊的生態系帶來什麼創新的應用。
本文為 Tornado Cash 研究系列的 Part 2,本系列以 tornado-core 為教材,學習開發 ZKP 的應用,另兩篇為:
Part 1:Merkle Tree in JavaScript
Part 3:Tornado Cash 實例解析
Special thanks to C.C. Liang for review and enlightenment.
近十年來最強大的密碼學科技可能就是零知識證明,或稱 zk-SNARKs (zero knowledge succinct arguments of knowledge)。
zk-SNARKs 可以將某個能得出特定結果 (output) 的計算過程 (computation),產出一個證明,而儘管計算過程可能非常耗時,這個證明卻可以快速的被驗證。
此外,零知識證明的額外特色是:你可以在不告訴對方輸入值 (input) 的情況下,證明你確實經過了某個計算過程並得到了結果。
上述來自 Vitalik’s An approximate introduction to how zk-SNARKs are possible 文章的首段,該文說是給具有 “medium level” 數學程度的人解釋 zk-SNARKs 的運作原理。(可惜我還是看不懂 QQ)
本文則是從零知識證明 (ZKP) 應用開發的角度,結合電路 (circuit) 與智能合約的程式碼來說明 ZKP 可以為既有的以太坊智能合約帶來什麼創新的突破。
基本上可以謹記兩點 ZKP 帶來的效果:
1. 擴容:鏈下計算的功能。
2. 隱私:隱藏秘密的功能。
WithoutZK.sol
首先,讓我們先來看一段沒有任何 ZKP 的智能合約:
這份合約的主軸在 process(),我們向它輸入一個秘密值 secret,經過一段計算過程後會與 answer 比對,如果驗證成功就會改寫變數 greeting 為 “answer to the ultimate question of life, the universe, and everything”。
Computation
而計算過程是一個簡單的函式:f(x) = x**2 + 6。
我們可以輕易推出秘密就是 42。
這個計算過程有很多可能的輸入值 (input) 與輸出值 (output):
f(2) = 10
f(3) = 15
f(4) = 22
…
但是能通過驗證的只有當輸出值和我們存放在合約的資料 answer 一樣時,才會驗證成功,並執行 process 的動作。
可以看到有一個 calculate 函式,說明這份合約在鏈上進行的計算,以及 process 需要輸入參數 _secret,而我們知道合約上所有交易都是公開的,所以這個 _secret 可以輕易在 etherscan 上被看到。
從這個簡單的合約中我們看到 ZKP 可以解決的兩個痛點:鏈下計算與隱藏秘密。
Circuits
接下來我們就改寫這份合約,加入 ZKP 的電路語言 circom,使用者就能用他的 secret 在鏈下進行計算後產生一個 proof,這 proof 就不會揭露有關 secret 的資訊,同時證明了當 secret 丟入 f(x) = x**2 + 6 的計算過程後會得出 1770 的結果 (output),把這個 proof 丟入 process 的參數中,經過 Verifier 的驗證即可執行 process 的內容。
有關電路 circuits 的環境配置,可以參考 ZKP Hello World,這裡我們就先跳過去,直接來看 circom 的程式碼:
template Square() { signal input in; signal output out; out <== in * in;}template Add() { signal input in; signal output out; out <== in + 6;}template Calculator() { signal private input secret; signal output out; component square = Square(); component add = Add(); square.in <== secret; add.in <== square.out; out <== add.out;}component main = Calculator();
這段就是 f(x) = x**2 + 6 在 circom 上的寫法,可能需要時間去感受一下。
ZK.sol
circom 寫好後,可以產生一個 Verifier.sol 的合約,這個合約會有一個函式 verifyProof,於是我們把上方的合約改寫成使用 ZKP 的樣子:
我們可以發現 ZK 合約少了 calculate 函式,顯然 f(x) = x**2 + 6 已經被我們寫到電路上了。
snarkjs
產生證明的程式碼以 javascript 寫成如下:
let { proof, publicSignals } = await groth16.fullProve(input, wasmPath, zkeyPath);
於是提交 proof 給合約,完成驗證,達到所謂鏈下計算的功能。
最後讓我們完整看一段 javascript 的單元測試,使用 snarkjs 來產生證明,對合約的 process 進行測試:
對合約來說, secret = 42 是完全不知情的,因此隱藏了秘密。
publicSignals
之前不太清楚 publicSignals 的用意,因此在這裡特別說明一下。
基本上在產生證明的同時,也會隨帶產生這個 circom 所有的 public 值,也就是 publicSignals,如下:
let { proof, publicSignals } = await groth16.fullProve(input, wasmPath, zkeyPath);
在我們的例子中 publicSignals 只有一個,就是 1770。
而 verifyProof 要輸入的參數除了 proof 之外,也要填入 public 值,簡單來說會是:
const isValid = verifyProof(proof, publicSignals);
問題來了,我們在設計應用邏輯時,當使用者要提交參數進行驗證的時候,publicSignals 會是由「使用者」填入嗎?或者是說,儘管是使用者填入,那它需不需要先經過檢查,才可以填入 verifyProof?
關鍵在於我們的合約上存有一筆資料:answer = 1770
回頭看合約上的 process 在進行 verifyProof 之前,必須要檢查 isAnswer(publicSignals[0]):
想想要是沒有檢查 isAnswer,這份合約會發生什麼事情?
我們的應用邏輯就會變得毫無意義,因為少了要驗證的答案,就只是完成計算 f(42) = 1770,那麼不論是 f(1) = 7 或 f(2) = 10,使用者都可以自己產生證明與結果,自己把 proof 和 publicSignals 填入 verifyProof 的參數中,都會通過驗證。
至此可以看出,ZKP 只有把「計算過程」抽離到鏈下的電路,計算後的結果仍需要與鏈上既有的資料進行比對與確認後,才能算是有效的應用 ZKP。
應用邏輯的開發
本文主要談到的是 zk-SNARKs 上層應用邏輯的開發,關於 ZKP 的底層邏輯如上述使用的 groth16 或其他如 plonk 是本文打算忽略掉的部分。
從上述的例子可以看到,即使我們努力用 circom 實作藏住 secret,但由於計算過程太過簡單,只有 f(x) = x**2+6,輕易就能從 answer 反推出我們的 secret 是 42,因此在應用邏輯的開發上,也必須注意 circom 的設計可能出了問題,導致私密訊息容易外洩,那儘管使用再強的 ZKP 底層邏輯,在應用邏輯上有漏洞,也沒辦法達到隱藏秘密的效果。
此外,在看 circom 的程式碼時,可以關注最後一個 template 的 private 與 public 值分別是什麼。以本文的 Calculator 為例,private 值有 secret,public 值有 out。
另外補充:
如果有個 signal input 但它不是 private input,就會被歸類為 public。
一個 circuit 至少會有一個 public,因為計算過程一定會有一個結果。
最後,在開發的過程中我會用 javascript 先實作計算過程,也可以順便產出 input.json,然後再用 circom 語言把計算過程實現,產生 proof 和 public 後,再去對照所有 public 值和 private 值,確認是不是符合電路計算後所要的結果,也就是比較 javascript 算出來的和 circom 算出來的一不一樣,如果不一樣就能確定程式碼是有 bug 的。
參考範例:https://github.com/chnejohnson/circom-playground
總結
本文的程式碼展現 ZKP 可以做到鏈下計算與隱藏秘密的功能,在真實專案中,可想而知電路的計算過程不會這麼單純。
會出現在真實專案中的計算像是 hash function,複雜一點會加入 Merkle Tree,或是電子簽章 EdDSA,於是就能產生更完整的應用如 Layer 2 擴容方案之一的 ZK Rollup,或是做到匿名交易的 Tornado Cash。
本文原始碼:https://github.com/chnejohnson/mini-zkp
下篇文章就來分享 Tornado Cash 是如何利用 ZKP 達成匿名交易的!
參考資料
概念介紹
Cryptography Playground
zk-SNARKs-Explainer
神奇的零知識證明!既能保守秘密,又讓別人信你!
認識零知識證明 — COSCUP 2019 | Youtube
應用零知識證明 — COSCUP 2020 | Youtube
ZK Rollup
動手實做零知識 — circom — Kimi
ZK-Rollup 开发经验分享 Part I — Fluidex
ZkRollup Tutorial
ZK Rollup & Optimistic Rollup — Kimi Wu | Medium
Circom
circom/TUTORIAL.md at master · iden3/circom · GitHub
ZKP Hello World
其他
深入瞭解 zk-SNARKs
瞭解神秘的 ZK-STARKs
zk-SNARKs和zk-STARKs解釋 | Binance Academy
[ZKP 讀書會] MACI
Semaphore
Zero-knowledge Virtual Machines, the Polaris License, and Vendor Lock-in | by Koh Wei Jie
Introduction & Evolution of ZK Ecosystem — YouTube
The Limitations of Privacy — Barry Whitehat — YouTube
Introduction to Zero Knowledge Proofs — Elena Nadolinski
ZKP 與智能合約的開發入門 was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
同時也有10000部Youtube影片,追蹤數超過2,910的網紅コバにゃんチャンネル,也在其Youtube影片中提到,...
「hash function範例」的推薦目錄:
- 關於hash function範例 在 Taipei Ethereum Meetup Facebook 的最佳解答
- 關於hash function範例 在 Taipei Ethereum Meetup Facebook 的最讚貼文
- 關於hash function範例 在 Taipei Ethereum Meetup Facebook 的精選貼文
- 關於hash function範例 在 コバにゃんチャンネル Youtube 的最佳解答
- 關於hash function範例 在 大象中醫 Youtube 的最讚貼文
- 關於hash function範例 在 大象中醫 Youtube 的最讚貼文
- 關於hash function範例 在 [心得] Bit index和de Bruijn sequence - 看板C_and_CPP 的評價
- 關於hash function範例 在 Hash Table:Intro(簡介) 的評價
- 關於hash function範例 在 【圖解演算法教學】【Hash】「實作」還在用古老的二元搜尋 ... 的評價
- 關於hash function範例 在 【C++ 資料結構與演算法】雜湊表(hash table) - YouTube 的評價
- 關於hash function範例 在 Introduction-to-cryptography/1. 有關雜湊.md at master - GitHub 的評價
- 關於hash function範例 在 hash演算法2023-在Facebook/IG/Youtube上的焦點新聞和熱門 ... 的評價
- 關於hash function範例 在 hash演算法2023-在Facebook/IG/Youtube上的焦點新聞和熱門 ... 的評價
hash function範例 在 Taipei Ethereum Meetup Facebook 的最讚貼文
📜 [專欄新文章] ELI5! 區塊鏈到底在幹嘛?
✍️ Juin Chiu
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
用生活化的例子輕鬆學會區塊鏈技術的重要概念
前言
我們熟知的世界正在慢慢地被區塊鏈技術瓦解與重建。不論背景,有愈來愈多人想對區塊鏈技術一探究竟,或許更進一步成為從業者、貢獻者或佈道者。
不幸的是,初學者若想學習區塊鏈技術,第一個問題可能會是高學習門檻,這是因為目前在各種主流平台上所流傳的區塊鏈知識或資源,都不免會大量使用艱澀的術語,長久以來便塑造出區塊鏈高大上的距離感,好似區塊鏈是只專屬於一小群駭客或者專業人士才能理解的技術。然而這是不準確的,事實上,區塊鏈技術中許多概念都能用一般常識理解,頂多只需要國小數學。
本文中,筆者將化繁為簡,試著把區塊鏈技術中的每個元素都使用生活化的例子比擬,讓區塊鏈愛好者與初學者不需用到密碼學/經濟學/資訊科學,也能領會區塊鏈技術的精髓之處。
本文將提及的概念如下:
什麼是帳本?
什麼是交易?
為什麼需要區塊?
有哪些共識機制?
區塊鏈安全嗎?
智能合約如何運作?
以下正文開始:
區塊鏈:一個公平的記錄系統
簡單來說,區塊鏈技術旨在打造一個去中心化的(Decentralized)狀態紀錄系統,更準確一點:區塊鏈技術旨在打造是一個追求真正「公平」的系統。
區塊鏈實現公平的關鍵在於:它完全仰賴自然法則運作,只透過一系列精細的規則就能保證系統的正確,這打破了人類社會一直以來的仰賴的中心化系統,使促成不平等的最大因素不復存在。
區塊鏈技術可以打造出具世界規模的去中心化運算平台,由數千甚至數萬個參與者共同維護狀態並提供計算資源。如果這個運算平台是應用在貨幣與資產的場景中,那麼這個平台可被稱為分散式帳本。
在接下來的段落,筆者將用一個例子展示一個極度精簡、只用紙跟筆的就可以運作的分散式帳本。在這個例子中,一群學生可以使用區塊鏈技術發行屬於他們自己的虛擬幣:「考卷幣」(Exam Paper Coin, EPC)。
考卷幣:使用區塊鏈技術發行的虛擬幣
考卷幣(EPC)是一種使用區塊鏈技術發行的虛擬幣,並存在於分散式帳本中。它的用途是為考卷加分,這將會吸引想考高分或者擔心被當的人學生持有。為什麼 EPC 只能被稱作虛擬幣,而不被稱作密碼貨幣?這是因為 EPC 的發行不會使用任何有關密碼學的技術,因此 EPC 嚴格來說不是密碼貨幣。
在分散式帳本被創建之初,沒有任何人擁有 EPC ,那麼 EPC 是怎麼「鑄造」與分配的?至少可以肯定的是,EPC 不能憑空產生,否則所有參與者就能不斷製造 EPC,使分散式帳本崩潰。事實上,EPC 的價值奠基於參與者的「付出」。
分散式帳本中最重要的角色非記帳者莫屬。每當記帳者成功完成工作,它便可以獲得固定數量的 EPC 作為報酬。於是,分散式帳本中的 EPC 便如此逐步地被鑄造出來。將 EPC 賦予具有貢獻的記帳者除了能夠公平分配 EPC,同時也是一種激勵機制(Incentivizing Mechanism),提供參與者維護帳本的動機。
那麼每個人所具有的 EPC 是怎麼記錄在帳本中的?
帳本: EPC 都要記錄下來
帳本即為依時間順序與特定格式記錄價值的系統。在分散式帳本中,每一批紀錄都會由某一個特定的「記帳者」維護,而記帳者會以特定的規則從所有的參與者中選出,因此分散式帳本是具有多個「記帳者」的系統。
為了確保能公平選出 EPC 的所有記帳者,分散式帳本不會使用任何記帳者的個人資訊,例如姓名、電話,做為帳本上的識別。記帳者可以自由地使用假名(Pseudonym)作為帳本上唯一的識別(Identifier),或者稱為地址(Address)。所以王小庭同學可以使用 Alice 這個假名,而且如果王小庭同學喜歡的話,他也可以同時使用 Bob 這個假名。
EPC 使用如下的格式記錄每個地址幣的數量:
Alice 100 EPCBob 0 EPCCharlie 0 EPCDavid 0 EPCEva 0 EPC
多數區塊鏈稱其識別為地址(Address),其為非對稱密碼學中公鑰(Public Key)的雜湊值(Hash)。地址具有統一的格式,例如以太坊的地址為長度 160 位元的 16 進位數字。
交易:把我的 EPC 轉移給別人
EPC 是可以轉移的,現在 Alice 可以將它持有的 100 EPC 中的 60 EPC 轉移給 Bob,以幫助 Bob 在下一次考試中免於被當。這樣的轉幣紀錄稱為交易(Transaction, Tx),可以如下表示:
Tx1
60 EPC, from [Alice] to [Bob]
而這筆交易會由 Alice 以上述格式記在紙條上,以 Tx1 表示。
簽章:讓參與者的所有動作都不可抵賴
EPC 的每個參與者的每個行為,例如交易,都必須附帶簽章(Signature),證明「這個動作確實是由我本人發起的」,簽署者不可抵賴,任何沒有附帶簽名的動作都是不被承認的。一個附帶簽名的交易紙條會像這樣:
Tx1
60 EPC, from [Alice] to [Bob], ALICE
簽章分為簽署(Sign)及驗證(Verify)兩個動作。驗證即是確認簽章是否確實是由行為發起者所簽署。在這個例子中,僅用一個簡單的驗證:若簽章與識別相符,則驗證成功。例如 Tx1 中,簽名 ALICE 確實與交易發起者 Alice 相符,因此驗證成功。
簽章就是區塊鏈的數位簽章(Digital Signature),其使用私鑰(Private Key)簽署,公鑰(Public Key)驗證,非常難以偽造。
訊息的散佈:怎麼讓所有參與者都收到訊息?
由於 Tx1 是由 Alice 發起的,因此 Alice 將於它自己的帳本記下這筆交易,接著 Alice 必須把這筆交易的內容也轉達所有的參與者,讓所有參與者皆具有所有的交易內容。
EPC 的參與者們不以口語,而是以傳紙條的方式互相交換訊息。紙條要如何有效率地傳播訊息給所有在教室中的參與者呢?可以使用「一傳十、十傳百」的策略。也就是:一次傳 10 張紙條給自己周圍的參與者,參與者收到後再抄寫 10 次後傳給周圍尚未收到該紀錄的其他參與者,逐步將訊息擴散致所有參與者。
這樣的傳播策略正如同流言被散佈的方式,因此也被稱為流言散佈協定(Gossip Protocol)。紙條傳播的網路就是對等網路(Peer-to-peer Network),紙條就是對等網路的封包(Packet)。關於對等網路的介紹,可以參考筆者日前的撰文:
隱私、區塊鏈與洋蔥路由
區塊:記錄一段時間內的交易順序
經過一段時間之後,每個 EPC 參與者手上都會有許多來自別的參與者的紙條,每張紙條都記載著不同的交易。在理想狀況下,如果所有參與者收到紙條的順序都相同,且每個參與者都收到了所有紙條,則所有參與者的帳本上的狀態,也就是餘額,都會相同。然而,若採用上述的訊息散佈策略,會發生兩種情況:每個參與者收到紙條的順序會不同,或者某些紙條可能會被遺漏。這些情況都會讓每個參與者的帳本產生差異,使帳本不可靠。而一個不可靠的帳本,不能作為貨幣發行的工具。
有沒有辦法能使所有 EPC 參與者用相同的交易順序記帳呢?這便是區塊鏈技術的奧秘之處。
為此,我們需要使用一個精心設計的結構:區塊(Block)。每個參與者皆會將一段時間內收到的交易紙條的編號,依照自己的順序寫在另一張紙條上,這張紙條就是區塊紙條,簡稱區塊,產出區塊的參與者則稱為區塊生產者。收到區塊紙條的其他參與者便會知道區塊生產者在這段時間內的交易順序。
為了要讓所有帳本都具有一致的狀態,EPC 的所有參與者必須要選出其中一個區塊作為所有參與者的共識(Consensus)。所有參與者都必須要遵照共識區塊的交易順序來更新自己的帳本,而這個區塊生產者就是記帳者。由於記帳者可以獲得報酬,因此在利益的驅使下,所有參與者都會努力生產區塊以爭取記帳權。
值得注意的是,每個區塊當中都會記錄前一個已達成共識的區塊的編號。例如接下來的範例,Bk15 的前一個已達成共識的區塊為 Bk3:
Bk15
Last Block: Bk3
Height: 15
Transactions:- Tx1- Tx5- Tx4- Tx10- Tx7- Tx13
Nonce: 1
Signature: CHARLIE
由於每個新的共識區塊都會指向前一個共識區塊,如此便會形成一條長鏈般的結構,已形成共識的區塊接成一條鏈,這就是區塊鏈(Blockchain)名稱的由來。
而當 EPC 參與者在收取共識的區塊後,將按照共識依序為每個交易內容進行帳本餘額的轉換。如此,所有的帳本都將具有一致的狀態。
依據特定輸入及轉換函數(Transition Function)執行狀態更新的系統,稱為狀態機複製(State Machine Replication)
摘要:濃縮紙條上的訊息
在介紹達成共識的方法前,筆者要先來介紹一個樸實無華但重要的概念:摘要(Digest),其顧名思義就是一段內容經過消化的產物。假設有一種摘要產生器,這個機器可以放入一張紙條,然後透過 3 個步驟計算出紙條的摘要。
摘要產生器將記載訊息的紙條切成一條一條固定寬度的細長條狀紙帶,如下圖:
2. 將這些紙帶依照順序接成一個長條紙帶。紙帶上有字跡的黑色部分與沒字跡的白色部分會出現不規則相間,測量每個黑色區塊之間相鄰的距離,如下圖:
3. 每段距離的數字相乘後的數字就是這個紙條的摘要(Digest)。
每個 EPC 參與者都會有一台摘要產生器,而它需要上緊發條才能開始工作,且每計算完一張紙條便須重新上一次發條。
摘要的計算雖然簡單,卻具有一些很有用的特性:
首先,摘要會隨著紙條內容的變動而更動。只要更動了任何一點紙條內容,例如區塊的交易順序,或者流水號(Nonce),都會使摘要改變。因此一個附上摘要的紙條,可以讓收到紙條的人在收到後再自行計算一次摘要並比對兩者,以驗證紙條的內容是否被修改過。因此,摘要是可驗證的(Verifiable)。
若想在不更動摘要的情況下同時變動紙條內容,只能不斷嘗試用不同內容產生摘要,直到發生碰撞(Collision) — 意即兩個不同內容的紙條出現相同摘要。
其次,摘要也是單向的:一個紙條很容易產出摘要,但摘要很難還原出原本的紙條內容。這也代表摘要是隨機且難以預測的,因此摘要可以作為一種亂數(Random Number)來源。
正式的區塊鏈使用更難預測且更不易碰撞的的密碼雜湊函數(Cryptograpgic Hash Function)產生訊息摘要。
理解關於區塊鏈技術的基本要件後,接下來就來看看區塊鏈技術的精妙之處:共識機制。
共識機制:如何達成共識?
在區塊鏈技術中,大致上有兩種方式可以產生共識:抽彩(Lottery)或表決(Vote),它們各自有不同特性,每一種分散式帳本都會使用其中之一作為共識機制。
抽彩
在抽彩機制中,唯有摘要小於門檻值的「合法」區塊才會被所有參與者收受。然而,區塊生產者無法預測摘要,且可驗證的摘要使區塊生產者難以作弊。因此若想生產數字小於門檻值的摘要,區塊生產者必須不斷改動區塊內容,例如流水號或者交易順序,直到找到摘要小於門檻值的區塊,就像抽彩一樣。只有合法的區塊才會被區塊生產者散佈給其他 EPC 參與者。
在這樣的規則下,可能會同時出現多個合法區塊。還記得區塊鏈中「鏈」的部分嗎?當收受多個低於門檻的區塊時,該選哪個區塊作為上一個區塊呢?這裡我們可以用一些簡單的規則來做抉擇:選擇合法區塊中高度(Height)最高的區塊,若高度一樣則選擇摘要數字較低的區塊。
區塊紙條的摘要就是正式區塊鏈中的區塊雜湊值。在正式的區塊鏈中,門檻值愈低,困難度(Difficulty)也愈高。區塊的選擇規則也稱為分岔選擇規則(Fork Choice Rule),使用可驗證的亂數作為共識的做法又稱為中本共識(Nakamoto Consensus)。
表決
有別於複雜的抽彩,表決機制相當直觀:所有參與者針對某個預先選出的領袖(Leader)的提案(Proposal),也就是區塊,進行投票。領袖是怎麼選出的?一個直覺的做法是按照假名的順序,按照 Alice / Bob / Charlie 的順序,所有參與者輪流擔任領袖。
所有參與者在收到提案後,可以選擇同意或反對這個區塊的內容,若同意的話,則將自己對提案的同意票記在紙條上,並將這個投票紙條散佈給所有其他參與者。若多數的參與者同意了提案,則所有參與者皆須認定該提案為共識。
然而,表決機制雖然直觀,卻不如抽彩具有可驗證性,參與者若想作弊則相對容易:例如,參與者可以重複投票,或者串通其他參與者一起不投票,以破壞帳本;另一方面,表決比抽彩來得有效率,因其不需要所有參與者都費功去製造可能將不被收受的區塊。
拜占庭錯誤(Byzantine Fault)特指這些不在預期內的行為,表決機制事實上也就是拜占庭容錯(Byzantine-fault-tolerant, BFT)演算法。PBFT 家族的協定是目前拜占庭容錯演算法的主流,然而其至多只能容忍不超過參與者總數一半的拜占庭錯誤。若想了解更多 PBFT 的細節,可以參考筆者日前的撰文:
若想搞懂區塊鏈就不能忽視的經典:PBFT
女巫:如何避免帳本被單一個體掌控?
上文提到:為了保證公平的記帳權,帳本上的識別都是假名,如上文提及,Alice 跟 Bob 實際上都是由同一個參與者王小庭所控制,其他參與者不僅難以得知,而且王小庭喜歡的話,他愛用幾個假名就用幾個假名 — 掌控多個假名的王小庭就成為了「女巫」(Sybil)。
不論是採取何種共識機制,女巫的存在都會破壞分散式帳本的安全性:
在抽彩機制中,如果多數的參與者皆由女巫控制,則女巫有很大的機會可以無視規則,不需抽彩便竄改帳本。
在表決機制中,如果由女巫控制的參與者可以集體進行不在預期內的行為,例如重複投票或者不投票。
因此,抵抗女巫對於分散式帳本的安全至關重要。對此,一個直覺的思路是:讓每個假名的行為都必須付出有限的資源,例如錢跟力。因此有兩種方式可以抵抗女巫:要嘛出錢,要嘛出力。
出力:在抽彩機制中,每個合法區塊的生產都必須附有低於門檻的摘要,而摘要的計算需要參與者出力不斷地重上發條。
出錢:在表決機制中,抵押一定數量 EPC 的參與者才能獲選為領袖被生產提案,且若違反規則,參與者的押金將會被沒收。
出力即是工作證明(Proof of Work, PoW);出錢即是權益證明(Proof of Stake, PoS),抵抗女巫的機制稱為抗女巫機制(Sybil-control Mechanism)。
合約:進行條件式的交易
回顧一下本文開頭所提:區塊鏈技術可以用來打造去中心化的運算平台,它可以用以記錄任何資訊,不止餘額,例如一段合約(Contract)。合約就是指一段會依據不同條件而達成不同執行結果的語句。例如:
CheckAndPay
給定 A、B 兩個假名,若 A 的餘額大於/等於 30 EPC,則 A 支付 20 EPC 給 B ,否則 A 不支付任何 EPC。
這個合約就可以被記錄在帳本中:
Alice 100 EPCBob 0 EPCCharlie 0 EPCDavid 0 EPCEva 0 EPCCheckAndPay "給定 A、B 兩個假名,若 A 的餘額大於/等於 30 EPC,則 A 支付 20 EPC 給 B ,否則 A 不支付任何 EPC。"
之後 Alice 就可以發起像這樣的交易:
Tx 99
CheckAndPay, {[Alice], [Bob]}, ALICE
如此,若 Alice 的 EPC 餘額不足 30 EPC 則不會支付 Bob。
觸發合約的 Tx 99 ,它的執行過程比較煩瑣:執行 Tx 99 的參與者首先會從帳本中尋找 CheckAndPay 的合約內容,並從 Tx 99 中取出合約需要的輸入:A 與 B,接著參與者再解讀合約的語句,依照條件進行帳本的狀態轉換。其中,為了使參與者能解讀合約,合約需用所有參與者皆能看懂的語言書寫。
合約又稱智能合約(Smart Contract)。正式的區塊鏈使用虛擬機(Virtual Machine)來解讀與執行合約。事實上,智能合約能做的事情非常多,這使具有智能合約功能的分散式帳本得以成為去中心化的運算平台,例如以太坊(Ethereum)。
總結: 分散式帳本究竟是一個怎樣的系統?
如果以上環節皆運作順利,那麼便能成功只用紙筆便發行了專由學生使用的貨幣。最後再次強調一次:這是一個為了便於使初學者掌握核心觀念而極度簡化的例子。正式運行的區塊鏈,例如以太坊,其實際運作遠遠複雜得多。
還有一些比較進階的概念,雖然礙於篇幅未在此文章提及,但部分主題筆者曾撰文介紹:
可擴展性(Scalability):第二層方案(Layer 2)與分片(Sharding)
隱私(Privacy)與匿名(Anonymity)
共識機制的安全性(Safety)與活躍性(Liveness)
最後,如果日後朋友/家人問起「什麼是區塊鏈」時,我想你會知道如何解釋了:)
ELI5! 區塊鏈到底在幹嘛? was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
hash function範例 在 Taipei Ethereum Meetup Facebook 的精選貼文
📜 [專欄新文章] Solidity Weekly #9
✍️ mingderwang
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
什麼時候用 storage,什麼時候該用 memory?
其實這副標題,有可能又會誤導大家如何寫 solidity。簡單講它們是完全不一樣的東西。所以應該會用在不同的地方,做不同的事才對。
先簡單說明它們的原理:
storage 就是 smart contract 正常存放狀態 (state) 的地方,而這些地方就是用來呈現在區塊鏈裡狀態值的變更。所以一般來說,全域變數就會用 storage 來儲存。
它以 32 bytes 為單位類似 hash 的方式做 key/value 的查詢。所以即時key 1 跟 key 1000,所用的空間跟 key 1 跟 key 2 一樣。(所花的 gas 也應該相同)
另外,通常方程式帶入的變數或回傳值,會以 memory 方式表示,或有些 compiler 會用 stack 來儲存 (不花 gas)。若帶入變數內容來自於一個全域變數,它會複製一份 storage 裡的資料到 memory 做修改。但如果你在方程式帶入的變數前用 storage 保留字來描述,它就變成 passed by reference,把 storage 的位置直接傳給該方程式,因此所有的變動,都會直接改到 storage 裡的值。
而一般在方程式裡的本域變數 (local variables),也預設用 storage 來處理,除非你故意用 memory 保留字來定義它。但用 memory 來處理陣列會有點困難。不像 storage 的陣列,可以用 push。(如下錯誤範例)
function createRoom() public{ address[] memory adr; adr.push(msg.sender); // compiler error ...}
但為了節省 gas 的消耗,在方程式裡本域變數改用 memory 也是很常見的事。
links 分享;
Ethereum Solidity: Memory vs Storage & How to initialize an array inside a struct — (Georgios Konstantopoulos)
Solidity Introduction — (A very good Solidity tutorial from BitDegree)
New Features of Solidity 0.5.0 — (@Christian Reitwiessner)
Solidity Weekly #9 was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
hash function範例 在 Hash Table:Intro(簡介) 的推薦與評價
若以Division Method實作Hash Function,定義h(Key)=Keymodm,Table大小為m=6,目前要處理的資料之Key有67,26,50,33,16,71,那麼各個Key將被對應到的index如下,同時參考圖 ... ... <看更多>
hash function範例 在 【圖解演算法教學】【Hash】「實作」還在用古老的二元搜尋 ... 的推薦與評價
![影片讀取中](/images/youtube.png)
【圖解演算法教學】【Hash】「實作」還在用古老的二元搜尋法?是時候跟上「Hash Search」 的車尾燈了! ... Hash Tables and Hash Functions. ... <看更多>
hash function範例 在 [心得] Bit index和de Bruijn sequence - 看板C_and_CPP 的推薦與評價
以前上課的時候老師有提過這個問題,這些是當時的筆記,我覺得最後
的解法蠻有趣的,跟大家分享。
假定有一個非零正數x以二進位表示,要找出最後一個1的位置,範例:
0100101000100000 <- 第 6 個位置為1,所以輸出 5
(計算0-base的位置,也可以想像成是算最後有幾個0)
在這邊先假設n為機器上表示一個整數所使用的位元數,以n=32來示範。
首先可以把題目簡化,假定x中只有一個bit為1,如果x中有兩個以
上的bit為1,可以利用 x &= (~x+1)來把最後一個1分離。
(x &= -x也可以,如果是二的補數表示法)
當分離出來之後,就有很多種計算法了,這邊就不考慮用組合語言的解法。
第一種是迴圈法
for ( index = -1; x > 0; x >>= 1, ++index ) ;
不過這種方法會需要n次的計算。
第二種是二分搜尋法,這需要lg n次的比較。
第三種方法是用bitwise parallel的技巧,其實跟二分搜尋法是一樣的道理
index = 0;
index += (!!(x & 0xAAAAAAAA)) * 1;
index += (!!(x & 0xCCCCCCCC)) * 2;
index += (!!(x & 0xF0F0F0F0)) * 4;
index += (!!(x & 0xFF00FF00)) * 8;
index += (!!(x & 0xFFFF0000)) * 16;
雖然需要lg n次的計算,但是不像二分搜尋法要做比較運算。
第四種方法是查表,不過x的範圍很大,所以只能分段查表。
第五種方法是利用perfect hash的技巧。
因為x只有32種可能,可以設計一個perfect hash function直接查
出index。
而這個hash function一般會用 x % 37,同時需要開一個大小為37
的table(所以有一些空間會浪費了)。
這方法很好設計,就是找比n稍微大一點的數字來試試看即可。
第六種是利用de Bruijn sequence。
其實這方法跟第五種方法很像,也是設計一個perfect hash function。
只是這方法免除了取餘數的運算,同時也只需要大小為32的table。
hash function是 (x * 0x077CB531) >> 27 其中的0x077CB531就是
de Bruijn sequence。
這方法對於n是二的次方數的機器都可以使用,至於n不是二的次方數
的機器應該不多。
這方法的原理從兩個方面來看,第一個是x本身一定是二的次方數,
所以任何一個數字乘以x,就相當於左移的運算。
而de Bruijn sequence的特殊之處,就是在於此序列中的任意連續
五位元都是相異的。五個位元總共有三十二種可能性,而至少要有
三十二個位元才有可能包含所有三十二種可能性(序列要想成頭尾
相接的)
舉例:00010111就包含了 000, 001, 010, 101, 011, 111, 110, 100
這八種三位元的所有組合。
所以當de Bruijn sequence乘以 x 又右移27個位元的時候,就相
當於是把sequence中的一組五位元子序列取出,這保證不同的x一
定會有不同的子序列,所以是一個很好的hash函數。
(32位元的de Bruijn sequence有很多個,但是這方法要用的時候
必須挑00000開頭的)
關於第六種方法的詳細研究可以參考下面這網址,裡面還有說當一
個數字有兩個bit為1的時候,怎樣可以快速找出來
https://supertech.csail.mit.edu/papers/debruijn.pdf
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.51
... <看更多>