2017年3月29日 星期三

IBM Hyperledger Fabric 文件出來了

本月份(2017年3月),IBM的Hyperledger Fabric文件出來了。這是另外一種Blockchain,稱為Permissioned Blockchain。與Bitcoin的Permissionless Blockchain不同之處在於,Bitcoin的Blockchain是大家都看的到,而Hyperledger Fabric,只有某些人,能看到部份Blockchain。這其實比較貼近大部份的實務應用。

在YouTube,有一個例子,說明Permissioned Blockchain的使用案例。
Building a blockchain for business with the Hyperledger Project

看完視頻之後,再去看Hyperledger Fabric的文件,會更有感覺。
 Hyperledger Fabric documentation

-Count

2017年3月27日 星期一

如何對Bitcoin進行Consensus Attack攻擊?

本篇從安全的角度,探討Bitcoin的原理。研究一套系統,若沒有深入思考安全的問題,就談不上真正的了解。如果能對Consensus Attack解釋清楚,那麼對Bitcoin的架構,也差不多了解一半了。

下面的例子,取自於「Mastering Bitcoin」這本書。本來,書中只有文字說明,難懂,何況是英文。我花了一些時間研讀,搞懂之後,用自己的方式,用中文,並且圖文並茂,希望能說明清楚。



Mallory向Carol買一幅畫「The Great Fire」,並且雙方同意用Bitcoin交易。不過Mallory是一個不懷好意的買家,他想用Consensus Attack方式,騙取這幅畫。他要如何做到?

首先,由Mallory的錢包產生兩筆Transaction:tx1和tx2。tx1是用$25,000金額購買這幅畫,錢是給Carol。而tx2是惡意產生出來的Double Spending Transaction,$25,000錢是給Mallory自己。

我們知道,正常情況下,Bitcoin是不允許Double Spending Transaction存在的。因此Consensus Attack就是利用這一點來進行騙取。

Mallory將產生的tx1傳送給Carol,Carol檢查tx1,並且等10分鐘,讓tx1進入blockchain的最新Block,也就是這時tx1的confirmation次數為1。Carol認為這樣交易沒問題,拿到錢,就把這幅畫賣給Mallory。

其實,Mallory將tx1傳給Carol同時,愉愉將惡意的tx2傳給Paul。Paul是惡意的挖礦集團,手下控制Bitcoin世界51%以上的礦工。他們努力挖礦,10分鐘後,也產生新的包含tx2的Block。這個時候,Bitcoin世界就產生Blockchain分叉。

Paul為了搶得自己的那一條Blockchain,他叫手下的礦工,繼續挖礦。他大概有1半以上的機率,先挖到礦,因為他控制了Bitcoin世界51%以上的礦工。再過10分鐘後,如果是他挖到了,那麼他自己的那條Blockchain就變長了,於是他的Blockchain就將會變成主幹。

再經過10分鐘,會有新的Block進來。不管是Paul集團挖到的,還是別人挖到的。這個新的Block會加入Paul的Blockchain。為什麼?因為Paul的Blockchain最長。而較短的那一條Blockchain就會被丟棄,同時裡面的tx1也將會被丟棄。

大家會想,tx1從Block脫離後,為何不能回到Transaction Pool,等待加入下一個Block?我們知道Bitcoin不允許Double Spending Transaction出現。這個時候,tx2己經在blockchain而tx1被踢出去了,tx1反而成為Double Spending Transaction,所以它不會回到transaction pool,而是直接被終結掉。

最後的情況就是,tx1被終結了,只留tx2。於是Carol沒有拿到錢,可是畫已經被Mallory拿走了。

Carol如何預防這種情況?一般來說,大筆金額的交易,要被6個block壓住,才算妥當。所以Carol最好等1個小時,確認tx1被confirm 6次,才能把畫給Mallory。

中本聰論文,最後一段,有算出Consensus Attack的成功機率。個人認為,這是論文的精華之處,以後再為大家解釋一下。

-Count

2017年3月21日 星期二

Learning Rate在Neural Network的作用

今天,我為了下面這條公式,思索了一整天,然後回想起,學生時代,微積分以及線性代數的種種有趣的事情。這或許是在這把年紀,學習Neural Network的有趣之處吧!



此公式出自於「Make Your Own Neural Network」這本書。想不透Learning Rate在其中的作用?也搞不懂,新的weight,為何要靠這條公式調整?現在,我懂了。

感謝Apple Pencil,幫我畫出下面幾張圖,弄清了思路。此公式的目的是,不斷調整w的值,直到找到最小的E值為止。用下圖來表達,就很清楚了。



為何此公式可以找到最小的E值?我畫出下面這張表格。



它是靠斜率。斜率越大,w的調整幅度就越大,反之就愈小,非常直觀。大家應該有爬過山,下山時,是不是遇到陡坡,跨的步伐就變大,到了平地,步伐就變小。這就是表格第2行想要表達的意思。

可以試一下矇眼下山。一開始遇到的坡,斜率是3,感覺步伐變大,為3。接下來遇到斜率是1的坡,步伐就變成1。最後是斜率1/3的坡,步伐變小,為1/3。雙腳應該感覺應該接近平地了吧。

那麼,為何該公式要有Learning Rate呢?其作用在於,讓我們在下山的時候,不要走太快,除了會傷膝蓋,也會錯過一些風景。這就是表格第3行所要表達的意思。大家自己去看,我就不多做解釋了。

我要稱讚「Make Your Own Neural Network」這本書,淺顯易懂。但不能因為這樣,就隨便翻,以為自己讀完了,反而會忽略了一些值得花時間研究的東西,這是不是Learning Rate給我們的啟發呢?

-Count

2017年3月20日 星期一

如何產生Neural Network的Output?

這裡用3 Layer Neural Network為例,每一層都有3個節點,第3層節點的Output的值,可以用下面的公式算出來:


這張圖,出自於「Make Your Own Neural Network」這本書,作者可能想用這道公式,嚇唬大家,至少我被唬到了。我怪這些搞數學的,喜歡把公式寫的又臭又長,拿來唬人有用。但是對於想實作Neural Network的程序員來說,就頭大了。因為要把這種數學公式,翻譯成程式,腦袋要轉好幾個彎。

我常常抱怨,程序員的命不好,除了要翻譯各式各樣的Computer Language,還要看懂數學家寫的數學公式。相對而言,數學家就比較好命了,只要面對數學公式就可以,這一段只是我個人的看法。

國中時,我聽某位數學老師說過,公式,只是為了計算方便。

職場上的我說:Coding Standard,是為了寫程式方便。

最近的我說:遵循Coding Standard的數學公式,是為了方便程式員理解。

今天,我給大家一句話:「數學家,發明公式;程序員,撰寫程式」

這兩種人,各司其職,各有自己的飯碗要顧。

有些數學公式,會以程式的形式出現。喜歡賣弄程式技巧的人,就像這道數學公式一樣,只用一行把程式寫出來。數學公式這樣寫,可能是為了數學家獨特的審美觀,我不是數學家,不便評論。可是,若程序員,複雜的程式一行搞定,那是給接手的人麻煩。

抱怨完了,開始介紹如何實作初步的Neural Network。

一般程序員,大不了就按照這個數學公式,採用裡面的符號,直接寫出程式,這樣很快就交差了事。可是比較有理想的程序員,會想到以後的擴充性,如:3層變成4層。如果程式直接採用裡面的符號,想必將來變成4層,程式就會變得一團糟。避免這種情況發生,就要將Coding Standard的觀念,套用在數學公式上,亦即,拆解並改寫數學公式,使用漂亮可擴充的符號。這件事情,必須由程序員作的,不能期望數學家。程序員在解釋數學公式的同時,也要保留數學公式的原貌,算是對數學家的一種尊重。

還是回歸正題吧。

下圖是3x3 Neural Network,將符號重新命名,以方便將來的實作。有3層,分別是L1, L2, L3。不採用Input Layer, Hidden Layer, Output Layer,而採用編號的方式,是為了方便理解,及將來程式擴充方便。I代表Input的值,O代表Output的值。i, j, k, 就是我們寫程式時,會用到的迴圈變數。用i代表L1的某個節點、j代表L2的某個節點,k代表L3的某個節點。那麼,將來有4層時,要用什麼符號代表L4的節點呢?這個問題先打住。寫程式,先從簡單的開始,等到有一個樣子出現時,再重新定義符號(Refactoring),以方便擴充性。


基本符號定義好了之後,就開始Neural Network是如何運作。我們知道,L1不做任何運算,L2和L3會對權值加總後,做sigmoid運算。



至此,我們用習慣的符號,將Neural Network的程式,寫出來了。接下來,考慮擴充性。寫成Matrix是不錯的方法。對Neural Network有基本觀念的人,知道這些運算,可以用Matrix表示:



這個時候,想買弄數學技巧的程序員,可以寫成下面的式子,這和一開始的數學公式很像,但它是以Matrix形式表達。雖然我覺得,這似乎不是標準的數學公式,但大家應該能看的懂吧。



最後,開始做符號的Refactoring。我們把X, SX, Y這些難以通用的符號換掉,採用I, O, W並且給它們的下標一個編號,代表第幾層。



這樣一來,數學公式,經過這翻更改之後,就算交給資淺的程序員,程式應該很快就可以寫出來吧?而且,也適用於TensorFlow,這個以後再說明。

-Count

2017年3月18日 星期六

Neural Network如何選用Sigmoid Function?

為了搭上AI的熱潮,開始寫一些相關文章,因為除了本人對它感興趣之外,也是最近非碰不可,不然就落伍了。Neural Network為何不用Step Function?大家可以自己找書來看。有一本書,「Make Your Own Neural Network」,有不錯的解釋。

本篇要探討的是,如何挑選一個可以取代Step Function的Sigmoid Function?這個問題,似乎是有點吹毛求疵,因為專家說,使用Sigmoid Function就沒錯了,聽專家的話,就對了。但我就是好奇,發明Neural Network的人是如何知道要用Sigmoid Function?應該不是憑空想出來的。

南宋哲學家,朱熹,提倡「格物致知」。我的解釋是,光聽專家的意見,或看書是不夠的,要用批判的心態去質疑。因為透過書或專家的解釋,那是二手的,有時候自己會以為書上寫的很清楚,會容易誤以為自己真的了解,嚴重者是獲得錯誤的知識,而產生錯誤的認知,可能會影響一輩子。所以,沒有去做一些「格物致知」功夫,書讀再多也是枉然。

講了這麼多,無非是想大家知道,本人不是沒事找渣,是為了「格物致知」。古代人「格」事物,能用的工具有限。現代人,可以用的工具就很多了。

剛開始去理解Sigmoid Function時,發現有兩個部份要「格」,公式和曲線圖。更進一步「格」,發現,公式不是目的,曲線圖才是目的。發明Neural Network的人,認為Step Function太陡了,需要一個平滑的曲線。如果我是發明Neural Network的人,憑自己的才智,無法馬上想到公式,而是先畫出一個心目中希望出現的曲線出來,然後再從這個曲線,找出能夠套用它的公式。可能不只一個公式,但盡量找到一個簡單的公式給大家或電腦用。

當然,我看過這個公式長什麼樣子,已經先知道答案了,所以從曲線「格」出公式,有作幣的嫌疑。但從「格」的過程,可以幫助我了解公式的原理,而不光是死記公式。

首先,把想要的曲線畫出來。希望的曲線是,保留Step Function的大部份特性,亦即x<<0時y=0、x=0時y=1/2、x>>0時y=1,但是要平滑。


然後就用下面的表格,把公式「格」出來。


先把 y = 0, 1/2, 1 放到表格的第一列,從這一列開始「格」公式。經過步驟1和2之後,產生表格的第3列,公式就快浮出水面了。於是這個問題,就簡化為,找格∞, 1, 0的公式,這就是經由步驟3後,產生表格的第4列。

印象中,很像之前學過的y = e^x,不過它的值倒過來,是0, 1, ∞。這就是經由步驟4,產生的第5列。而符合第5列的公式,就是e^x,這就是步驟5的結果。為何選e?不選其它的數字?這可能是e有些有趣的特性,導致大部份的數學家喜歡使用它來建立公式。

接下來,我們就往表格的上方走。經由步驟6,產生e^(-x),因為它是左右對稱的。最後是步驟7,將e^(-x)放進右下角那塊存放∞, 1, 0值的區域。於是,Sigmoid Function就被「格」出來了。

在「Make Your Own Neural Network」這本書提到,Step Function有Threshold,可是Sigmoid Function似乎沒有考慮到Threshold?這是我的疑點,下次再去「格」它。

本篇,是我去「格」Sigmoid Function的心路歷程。當然,講給大家聽,就變成「二手」的。其中一個目的,是希望讓大家知道,如何「格物致之」。當然,大家還是要去質疑,其中的對錯。

-Count

Transaction的後半生

前篇講到Transaction的前半生,從Create、Broadcast、到Propagate。真正精彩的是牠的後半生,以及牠的「生後」所發生的事情。

Transaction一旦進入Transaction Pool,就進入了牠的後半生,等待和Block結合。而Block會和Blockchain結合。在Transaction在Blockchain的日子裡,剛始的的狀態是不穩定的,有可能Block會離開Blockchain,Block一離開,就崩解,裡面的Transaction都解放出來。Block被埋在Blockchain愈深,Block就愈穩定,Transaction就愈難離開。這時候的Transaction可視為「壽終正寢」並且「蓋棺論定」了。

細節,我為大家一一道來。




Transaction,tx1,牠的前半生,像病毒一樣散播給全世界的Node。Node會去Verify tx1,若Node具有挖礦能力,稱為Miner,Verify通過,會把牠安置在Transaction Pool。這時tx1的狀態是Verified,開始進入牠的後半生。

Miner收集到足夠多的Transaction後,就開始建立一個Candidate Block,標記為Block 2,Miner按照優先順序,從Pool挑選到tx1,放到Block 2裡,開始對它挖礦。

我們把Block視為一道難解的問題,挖礦目的是去找到問題的答案。為了維持,全世界每10分鐘產生一個新的Block的節奏,該題目的難度是會被調整的。什麼是難解問題?如何挖礦?將在另一篇文章裡說明。

若Miner找到Block 2的解答,表示挖到礦,Miner將此Block 2放到Blockchain最上層的Block 1上面。這時候,tx1的狀態變成Confirmed。

這時候,在Blockchain裡面的tx1,還不算是穩定的。因為Miner還沒有將Block 2廣播出去,而且,其它的Miner也可能挖到礦。這種情況下,就會出現Blockchain的分叉。解決分叉的辦法,就是等新的Block出現,看它出現在那一個分叉,保留最長分叉的那一支Blockchain,短的那一支的Block就捨棄。所以,若Miner辛苦挖的Block 2不幸落入短的分叉,Block 2就會解體,裡面的Transaction,若還沒有被放在最新Blockchain裡,就會回到Transaction Pool。這時候的狀態,從Confirmed,變回Verified。

Blockchain的分叉,有時間,我再另擇文說明。

我們稱,Transaction有One Confirmation的意思是,牠現在在Blockchain裡面,並且埋在牠所屬的Block位於Blockchain的最上層。Two Confirmation的意思就是,被兩個Block埋,所屬的Block上面還有一個Block。

所以Confirmation的次數愈多,表示Transaction被Block埋的深度愈深,埋的愈深,出土或復活的機會就愈少,可以視為該Transaction「壽終正寢」了。

通常,大筆金額交易,要等6個Confirmation完成,亦即被6個Block埋,這就是我說的「蓋棺論定」的意思。也就是該Transaction的功過,己經被牢牢寫在Blockchain裡了。

-Count

2017年3月17日 星期五

Transaction的前半生

要了解Blockchain,得先了解Transaction不可。因為Blockchain是死的,Transaction是活的,Blockchain是Transaction的墳墓,所以先了解Transaction,再了解Block,最後是Blockchain,按照這個順序,思路會比較清楚。

Transaction,字面上的意思就是交易,有牠存活的時間,我將牠分為「前半生」和「後半生」。從Transaction的誕生,到與Block結合之前,是牠的「前半生」。與Block結合時,就開始走向牠的「後半生」。牠有捨棄Block的機會。但若被另外一個Block壓住,離開的機會就變少了。被愈多Block壓住,就愈難離開。我們可以將牠視為被埋葬了,亦即「壽終正寢」並且「蓋棺論定」。

如下圖,Transaction的前半生,分三個階段:

  1. Create
  2. Broadcast
  3. Propagate


Step 1 - Create

Transaction如何誕生?例如,Alice向Bob買一杯咖啡,想用Bitcoin交易,於是Alice開啟手機上Bitcoin Wallet App,去掃Bob POS上顯示該咖啡的QR Code,Wallet App就會生出一個Transaction。

Step 2 - Broadcast

接下來要告知全世界的Node,誕生了一個Transaction。首先,廣播(Broadcast)出去。通常Bob的POS會先收到Alice的Transaction,然後去驗證牠,驗證沒問題,Bob才會放心把咖啡遞給Alice。Transaction可以透過任何形式通道廣播,如:Wi-Fi、Bluetooth、NFC等,並且可以是Non Secure Channel,亦即通道不需要加密,這和一般信用卡交易不同。

Step 3 - Propagate

收到Transaction的Node,驗證沒問題,就開始繁殖(Propagate)牠,並且傳給其它3到4個Node。這裡為何強調「繁殖」,意思是,Node自己也要保留一份Transaction,挖礦用的。很快地,就像散播病毒一樣,全世界的Node都會收到Transaction。

Transaction的前半生,就說到這裡了。下一篇文章,會講牠的後半生、牠如何和Block結合、如何「壽終正寢」、以及怎樣才算是「蓋棺論定」。精彩的在後頭,Transaction的後半生

-Count

2017年3月15日 星期三

Full Node和SPV Node如何驗證Transaction?

對於Full Node和SPV Node如何驗證Transaction?在閱讀完以下論文、書籍、網上資料後,我把這個問題整理出來,希望能解釋清楚,讓大家了解:

首先,我們要知道,Transaction的驗證,實際上有兩件事情要做。前篇文章有提:
  1. Transaction存在性檢查 
  2. Transaction無重花(重覆花費)檢查 
Full Node和SPV Node對這兩項檢查的策略不同,Full Node是走Height,SPV Node是走Depth。想必大家剛開始研究Bitcoin時,也常常搞不清楚什麼是Height,什麼是Depth?希望本文,對照下圖,能為大家撥雲見日:


Verify Transaction
  • Full Node - Block Height Verification
  • SPV Node - Block Depth Verification

Full Node - BHV (Block Height Verification)

Full Node就是有完整Blockchain的Node,所以檢查Transaction是否存在Block,就拿它與整個Blockchain搜尋一下就好了。

Transaction存在性檢查通過,並不保證該Transaction的Input不是重花,所以要進行這項檢查。方法有兩種:

方法一:如圖,我們要檢查的Transaction叫tx2,它己經被驗證是在Block 300000裡。於是Full Node就往之前的Block去找Transaction串列,如找到tx1的output是tx2的input,就表示tx2的確被花費了。為了確保tx2沒有被重花,還得往更前面的Block去找,直到Genesis Block為止。

方法二:從Blockchain建立UTXO Pool,也就是將所有未花費的transaction收集起來。其實一旦建立了UTXO Pool,也就驗證了所有Transaction沒有被重花。

SPV Node - BDV (Block Depth Verification)

這種方法,在中本聰論文提到。SPV Node只有Block Header,為了檢查Transaction是否存在某個Block,就去問Full Node,它會回傳Merkle Path給SPV Node,SPV Node用它來驗證該Transaction是否存在Block,此驗證方稱之為Merkle Path Proof。

一樣,Transaction存在性檢查通過,並不保證該Transaction的Input不被重花。SPV Node採用不同的方式,它是去看之後的Block有幾個。愈多,表示該Transaction所屬的Block被「埋」的愈深,用Depth表示Transaction被埋的深度。埋的愈深,表示該Transaction被Confirm的次數就愈多。一般來說,Transaction被6個Block埋,就夠了。這表示該Transaction在Blockchain裡面,是被大家核準通過的,而且沒有重花。

當然,BDV的嚴謹性,比不上BHV。因為SPV Node沒有全部的Transaction,無法做到BHV,BDV是退而求其次的方法。

-Count

Bitcoin Block 如何儲存 Merkle Tree?

中本聰在Bitcoin P2P Network的論文提到,Merkle Tree在SPV Client應用。我們知道,SPV Client不儲存所有的Transaction。當它要確認某個Transaction是否在Block裡,就去問Peer,Peer回傳Merkle Path,給SPV Client驗證就行了。

本篇提出一些問題給大家深入思考:
  1. Merkle Tree存在何處?
  2. 除了Merkle Tree,還有什麼別的方法,可以用在SPV Client上?

問題一:Maerkle Tree存在何處?

我們知道,Merkle Tree是一種Binary Hash Tree。它的用途和原理這裡就不多說了,不熟的,請大家自己上網找。為了本文講解方便,列出相關名詞。

Merkle Tree裡的Node分為兩類,Leaf Node與Non-Leaf Node,Non-Leaf Node裡面,還有一個惟一的Node叫Root Node,用來代表整個Merkle Tree。

Merkle Tree
  • Leaf Node
  • Non-Leaf Node
    • Root Node

簡單來說,每一個Transaction的Hash值存在Leaf Node,兩兩Leaf Node的Hash值存放在上一層的Node,直到Root Node,其值,就是用來代表Block所包含的所有Transaction。

那麼,Merkle Tree存在那裡?我一直以為是在Block,後來發現,其實Block只存Root Node,連Leaf Node都不存。除了Root Node之外,其它Node都是依照需要,當場計算出來的。我把Block和Transaction的關係,畫成下面這張圖:



從圖中,我們可以很清楚的知道,Block和Transaction都不存Merkle Tree,連Leaf Node都無,只有存在Block Header的Merkle Root,是用來驗證它所包含的Transactions完整性的最後一關。

Full Peer會儲存完整的Block:Block Size + Block Header + Transaction Counter + Transactions

SPV (Simplified Payment Verification) Client只存精簡的Block:Block Size + Block Header

Full Peer會儲存完整的Transaction,但也沒有Merkle Tree,甚至連Transaction Hash也沒有。

Transaction Input的Transaction Hash指的是關連到上一筆的Transaction,而非這一筆。

由此可知道,整個Blockchain、Block、與Transaction的資料結構,在設計上,是以儲存空間最小為考量,而非查詢方便為考量。這是因為Blockchain是大家共用的帳本,愈小,愈利於傳輸。

不管是Full Peer還是SPV Client,Transaction有兩項要檢查:
  1. Transaction存在性檢查 - 檢查Transaction是否真的存在Block裡
  2. Transaction沒有被重覆花費 - 檢查Transaction的Input不是重覆花費

Full Peer和SPV Client對這兩項的檢查方式會有所不同,我將會寫另一篇文章探討。本文拿,SPV Client對Transaction做存在性檢查,做為一個例子,解釋Merkle Tree在這檢查的過程中,起了什麼樣的做用。

檢查Transaction是否真的在某個Block裡?我猜想的步驟如下:
  1. SPV Client將這個問題包裝成 Q = (Transaction, Block Header) 
  2. SPV Client將問題Q傳給Full Peer
  3. Full Peer拆解Q,若發現Transaction屬於Block,則建立Merkle Path
  4. Full Peer將Merkle Path傳給SPV Client
  5. 若SPV Client拿到Merkle Path,就表示Full Peer回答了Transaction是在Block裡。
  6. SPV Client也會對Merkle Path驗證Transaction是否真的存在Block,做二次驗證。
這裡有一個問題:為何不讓Full Peer直接給答案就好了?還要丟一個Merkle Path給SPV Client,讓它做二次驗證?

這是因為,SPV Client無法確認Full Peer是否可信的?Bitcoin世界裡,Blockchain是惟一可信的,當然裡面的Block、Merkle Root、Transaction都是可信的。若待驗證的Transaction透過Merkle Path,可以接到可信的Merkle Root,那麼就可以驗證Transaction的存在性。

這種驗證Transaction存在性的方法,叫做Merkle Path Proof。再次強調,此法無法驗證Transaction的合法性,因為無法證明Transaction的Input不是重覆花費。

若Full Peer是惡意的,分析一下欺騙SPV Client的可能性如下:

Transaction不屬於Block1:
Full Peer可以騙SPV Client說:Transaction在Block1裡嗎?不行,因為很難做出一個假的Merkle Path,因為Merkle Root是一個不斷SHA256的值,要造假很困難。(題外話,若是SHA1就很容易造假了,因為Google最近發表,在可接受的時間內,產生相同的SHA1出來)

Transaction屬於Block1:
Full Peer可以騙SPV Client說:Transaction不在Block1嗎?可以。

以後再探討Bitcoin Network的安全問題。

問題二:除了Merkle Tree,還有什麼別的方法,可以用在SPV Client上?

為了建立Merkle Path,Full Peer要先從計算所有Leaf Node開始,再往上算出Non-Leaf Node,直到Root Node。為何不用較簡單的List資料結構?Hash所有Leaf Node,放到第1個Node?

List
  • Root Node
  • Leaf Node

用List,的確可以減輕Server的運算量,因為不用計算Node。但從Full Peer傳給SPV Client的資料量會變很多。原來傳給SPV Client的只要Merkle Path,只要Log(2, N),現在要N。想像1個Block有1024筆Transaction,其資料量就是 1024 x 36 (SHA256 size) = 36K bytes。如果傳的是Merkle Path,其資料量是 Log (2, 1024) x 36 = 360 bytes。

由此可見,Merkle Tree雖然會增加Full Peer計算Node的負擔,但不會很多。計算Leaf Node運算量會比較大,因為它是Hash兩個32 bytes的Leaf Node。而傳輸的資料會少很多。

再來看本文最初提的兩個問題:
  1. Merkle Tree存在何處?
  2. 除了Merkle Tree,還有什麼別的方法,可以用在SPV Client上。

結論:
  • Blockchain不存放Merkle Tree。
  • 但在實作上,Full Peer可以建立一個方便查詢或建立Merkle Tree的Index。建Index的方法就有很多了。
  • SPV Client採用Merkle Tree,這是運算量和資料傳輸量之間的折衷方案。

-Count

2017年3月11日 星期六

SPV Node如何用Bloom Filter詢問自己有多少錢?

Wallet (SPV Node)如何知道自己有多少錢?在上一篇文章,如何知道Bitcoin Wallet有多少錢,列出三種方法。

方法一:下載完整帳本(Blockchain)後自己從裡面去找
方法二:向Peer公開Wallet的所有訊息,Peer就回傳屬於該Wallet的UTXO
方法三:向Peer公開Wallet的部份訊息,Peer回傳可能屬於該Wallet的UTXO

三種方法,各有優缺點。本篇介紹第三種,參考自,BIP37 - Connection Bloom Filtering。想深入了解Bloom Filter在Bitcoin Protocol的運作原理,建議多花一些時間閱讀。看得懂的,本篇文章就不用再看下去了。若看不太懂,希望本文對大家會有一些幫助,當然,最重要的一點是,鼓勵大家對照原來的BIP37,質疑本文的正確性,這樣做,有助於提升大家的思考能力。

用下圖說明,Wallet如何用Bloom Filter,去向Peer問,自己擁有多少錢。這裡,我們的前提條件是,Wallet被重啟後,只剩下Private Key,其它什麼都沒有。不用擔心,透過下面步驟,可以把錢找回來。


Wallet向Peer詢問,自己應該有多少錢,步驟如下:

  1. Wallet從Private Key推衍Public Key,再來是一組Address (a1, a2, a3)。最後建立Bloom Filter。可以想像它是一個過瀘器,用來過瀘大部份不屬於Wallet的Transaction。
  2. Wallet對Peer發送filterload message,將Bloom Filter傳給Peer。
  3. Wallet發送getblocks message,要求Peer傳回Block。若Wallet沒有發filterload,那麼Peer會準備一股腦的Block。但因為現在Peer有了Bloom Filter,所以它會過瀘大部份不相干的Transaction。
  4. 這時Peer開始從Blockchain中,用Bloom Filter找出可能屬於Wallet的Transaction,及其所屬的Block。假設第一個找到的是Block1,底下掛了一個tx1,其output指向a1,表示該transaction屬於Wallet。
  5. 為了要確保tx1的output沒有被花費到,Peer必須檢查是否有其它的transaction的input花費了a1。假設Peer發現了Block1底下掛了一個tx2,其input指向a1,就表示tx2花費了tx1的output。
  6. 若在Step 5發現Transaction有被花費,則Peer會依據Transaction的格式,及當初從filterload設定的Flag,決定要不要更新Bloom Filter。這樣會造成Bloom Filter的孔會愈來愈大,導致判定Transaction屬於Wallet的準確率也會變大。其中的細節,留待下一篇文章說明吧!
  7. 當Peer找到所有可能的Transaction後,就會發一個inv message,給Wallet。inv裡面會有:待選Transaction所屬Block的頭、Merkle Path、以及Transaction本身。
  8. 最後,Wallet收到inv message帶來的東西後。就依照中本聰論文理所提的兩種檢查方式:Merkle Path Proof和Proof of Work(這一點我以後再解釋),檢查那些Transaction是屬於Wallet,並且是尚未被花費的Transaction,然後建立UTXO Pool,暫時存放尚未被花費的屬於該Wallet的Transaction。將這些Transaction的Output加總,就是該Wallet的餘額(Balance)了。
本文遺留幾個問題,近期之內會說明:
  • Peer在什麼情況下,會去更新Bloom Filter?
  • 如何從,中本總Bitcoin P2P Network論文,解釋SPV檢查Transaction的方法?
至於Merkle Tree和Bloom Filter的原理,建議大家自己上網找資料,沒必要我就不多解釋了。

-Count

如何知道Bitcoin Wallet有多少錢?

Bitcoin Network,大致上有兩種Node:
  • Full Node,存放所有Block和Transaction
  • SPV Node,存放所有Block Header

如果只有Full Node,那我們就不用去想設計Merkle Tree,以及後來的Bloom Filter,那麼這個世界就簡單多了。但為了要讓Bitcoin Wallet(錢包)可以通行所有裝置,特別是手機,SPV Node就很重要了,不然就需要100G以上空間存放整個Blockchain,這是不可行的。

自從中本聰的Bitcoin P2P Network論文,2008年橫空出世之來,他就預測到,將來必定是SPV Node盛行,所以他很早就提出了SPV (Simplified Payment Verification)的概念。

而後來2012年提出的BIP37 - Connection Bloom Filtering,是基於SPV的概念,用Bloom Filter,提出一個更加可行的方案出來。

本篇先為這個問題:「Bitcion Wallet如何知道有多少UTXO?」,提供簡單的回答。

我們知道,Wallet只存所有的Block Header,而沒有全部的Transaction,最多只存屬於自己的Transaction。一開始,連Block Header都沒有的情況下,如何知道Wallet有些UTXO(Unspent Transaction Output)呢?它要去問具有完整帳本(Blockchain)的Peer。問的方式有兩種:

方法一:下載完整帳本(Blockchain)後自己從裡面去找
方法二:向Peer公開Wallet的所有訊息,Peer就回傳屬於該Wallet的UTXO
方法三:向Peer公開Wallet的部份訊息,Peer回傳可能屬於該Wallet的UTXO

這個問題,講白一點,就是:「我想知道錢包有多少錢?」

要知道真實的錢包有多少錢,直接打開來數一下就行了。Bitcoin Wallet,是電子錢包,運行的時候,會顯示目前的餘額,斷電的時候,不需要保存餘額,因為下次重啟的時候,只要去問就好了。根據什麼來問?Wallet惟一需要存放的,是一組Private Keys,被安全存放在晶片裡,可能是Secure Element或Trust Zone。這一組Key是別人獲取不到的,甚至Wallet App自己也獲取不到。Wallet的安全晶片,可以從Private Key去推算出Public Key。這個Public Key可以視為Address。有時候Address是從Public Key被Hash兩次算得來的。

我們把Address視為銀行的帳號。所以別人要給我Bitcoin,我就要將Address給別人,請他將錢匯到這個帳號,就行了。

回到原來的問題「我想知道錢包有多少錢?」

方法一:下載完整帳本(Blockchain),然後自己從裡面去找

這種方法,最簡單,但耗費的網路頻寬最多,至要要傳輸100G以上的資料量。因為Wallet沒有向Peer表明,那些Address屬於Wallet,所以Peer當然不知道那些Address屬於Wallet。我們無法從Blockchain存放的Address,往回推導出是從那一個Wallet產生出來的。所以Peer只好將Blockchain一股腦傳給Wallet,讓Wallet自己去找。

優點:結果精確,保留隱私
缺點:浪費頻寬

方法二:向Peer公開Wallet的所有訊息,Peer就回傳屬於該Wallet的UTXO

Wallet向Peer公開所有的Address,可是這樣一來,就洩露隱私。Peer拿到Address,就回報屬於該Wallet的UTXO,及所屬的Block。根據中本聰的論文,此Block不會自帶所有的Transaction,而是Merkle Path。

優點:結果精確,簡省頻寬
缺點:洩露隱私

方法三:向Peer公開Wallet的部份訊息,Peer回傳可能屬於該Wallet的UTXO

Wallet向Peer公開部份訊息,以Bloom Filter呈現。Peer拿到Bloom Filter,就回報「可能」屬於該Wallet的UTXO,及所屬的Block Header,及Merkle Path。因為Bloom Filter沒有直接呈現Address,所以保留了一點隱私。

但是Bloom Filter,的特性是:
  • 沒有從Bloom Filter過瀘出來的Transaction,「一定」不是屬於Wallet的
  • 從Bloom Filter過瀘出來的Transaction,「應該」是屬於Wallet的
  • 而且隨者Wallet的Transaction數量愈大,「應該」的準確性就愈低。

優點:保留一定程度的隱私,簡省頻寬
缺點:結果不精確 (但可接受)

下一篇,對「方法三」,會有圖文並茂的說明。

-Count

2017年3月10日 星期五

從Gartner技術成熟度曲線,預測Blockchain及其它關鍵技術未來的發展

最近看一本書「區塊鏈 重塑經濟與世界」,裡面提到,Gartner技術成熟度曲線。有些技術,經過高價狂跌後,若還能爬起來,那就表示該技術將要邁向成熟階段。

下圖是2015技術成熟度曲線,發現並沒有Blockchain,但有與其相關的Cryptocurrencies,與Cryptocurrency Exchange,處於下滑階段。


再看下圖,2016技術成熟度曲線。Cryptocurrencies,與Cryptocurrency Exchange不見了,但Blockchain出現了,而且是在爆衝階段。


其它有趣的技術,比如IoT,在2015年,位在最高點,但在2016年,就不見了。到是IoT Platform還在維持,並在2016年上升了一點。這說明了IoT要搞好,Platform是關鍵。

另外還有AI相關技術。發現Machine Learning,2015正從頂峰下滑,2016又愉愉回到頂峰。這說明Machine Learning非常火。Virtual Personal Assistants,2015年出現,2016年還活者,並且往上爬。

還有,2015年和2016年,Quantum Computing還活者,我認為,這玩意兒,遲早會顛覆整個網路安全架構。

最後,將這些技術依成熟度排在一起:
Quantum Computing ==> IoT Platform ==> Blockchain ==> Machine Learning

未來發展可能會:
  • Machine Learning會想採用Blockchain最為資料核心引擎,所以Blockchain可能會先搭上Machine Learning的順風車。
  • IoT Platform,先天上,就適合分散式的架構。所以當Blockchain技術成熟時,IoT Platform應該會想採用Blockchain技術。
  • 後面就會跟來Quantum Computing,會將之前風行的技術重新洗牌。

-Count

2017年3月9日 星期四

為何傳統藍牙配對容易遭受攻擊?

傳統藍牙配對(Bluetooth Legacy Paring),最為人垢病之處,是容易遭受駭客攻擊。

其實原理很簡單,大家只要有時間,翻一下Bluetooth Spec,了解一些各種Key的產生方式,就知道如何進行攻擊。當然,這方面的文章,網路上很多,大家可以去看看。在這裡,用我自己的方式,解釋給大家。如果看完後,晃然大悟,那就是對大家有貢獻。若看完了還是不懂,可能是本人表達的不清楚,只好自己想辦法吧。

藍芽配對的流程,從輸入PIN產生Kinit,再產生Kab,即完成配對。配對完的兩個設備,都存放相同的Kab。用下面兩張圖(來自於Multilevel Security Algorithm for Bluetooth Technology)說明。






兩個設備靠近時,要建立安全通訊之前,要先確認對方設備是否曾經被配對過,也就是確認對方是否可信的(Trusted)。如下圖,Device A想要驗證Device B是否可信:


  1. Device A發一個亂數AU_RANDa給Device B。
  2. Device B拿到AU_RANDa,和BD_ADDRa和Kab,計算,得到AU_RANDa。
  3. Device B回傳SRESa'給Device A
  4. Device A自已也會根據AU_RANDa用和Device B同樣的方式(E1),算出SRESa。
  5. Device A比較這兩個值,SRESa與SRESa',若一樣,表示Device B是可信的。
以上是兩個設備的驗證過程。駭客可以利用這一點,暴力破解,去猜PIN。若SRESa與RRESa'值一樣,表示PIN被猜到了。

我將上面3張圖,簡化成下面這張圖,就可以很清楚知道駭客會怎麼做了。


使用者,在做傳統藍牙配對的時候,駭客會用藍牙分析儀去監聽藍牙封包。分析儀是得不到PIN,因為那是使用者自己輸入的。但分析儀可以得到
  • IN_RAND
  • Kinit xor LK_RANDa
  • Kinit xor LK_RANDb
  • 雙方的藍牙位址:BD_ADDRa、BD_ADDRb
分析儀這些這值記錄下來,就可以對6位數字的PIN進行暴力破解了。通常,功能強大的藍牙分析儀,再抓封包的時候,會順便破解一下PIN。這種分析儀,我以Attacker稱之,如下圖:



攻擊步驟:

  1. Attacker監聽兩個設備配對的過程,截取以下值及藍牙地址,記錄在Table裡
    • IN_RAND
    • LK_RANDa xor Kinit
    • LK_RANDb xor Kinit
  2. Attacker不知道Device的PIN,但知道配對時傳遞的一些數據,而且存在Table裡,於是開始爆力破解PIN。
  3. Attacker 發AU_RANDa給Device
  4. Device傳SRESA’給Attacker
  5. Attacker不斷地試PIN,就會一直產生SRESa。直到找到PIN,使得SERSa=SERSa’。因為PIN只有6位數,所以很快可以找到。
  6. 一旦Attacker知道PIN,就可以算出Kinit ==> Kab ==> Kc ==> Kc’。
  7. 之後兩個設備之間通訊是拿Kc’加密。因所以Attacker會順便破解藍牙通訊傳遞的密文。
為何Bluetooth Simple Paring無法採用這種方式?因為配對過程用的是ECC,雙方各有Public Key與Private Key,而且Key的大小是256 bit,很難爆力破解。這涉及到密碼學,以後有空再為大家介紹。

-Count

2017年3月7日 星期二

SPV Node如何建立UTXO Pool?

SPV Node如何建立UTXO Pool?

這個問題,又衍生另一個問題。

SPV Node需要建立包含所有UTXO的UTXO Pool嗎?

我們可以從Wallet(電子錢包)的角度去想這些問題。

Bitcoin的UTXO (Unspent Transaction Output),就是尚未花費的輸出,相當於現實世界還沒有花出去的鈔票。

Software Wallet是SPV Node的一種,它會有一個Database儲存屬於該Wallet的UTXO Pool。

Wallet為何不存放別人的UTXO呢?

因為這樣做沒有多大用處。我們知道Wallet,相當於現實世界的錢包,Wallet所記錄的UTXO,其值的加總,就相當於現實世界的錢包裡放了多少錢。

現實世界裡,你的錢包會記錄別人的錢包有多少錢嗎?

不會的。所以Bitcoin Wallet只記錄所屬的UTXO就好了。

使用新的Wallet,它的UTXO Pool為空的,因為還沒有用它來進行Transaction。只要有Transaction發生,並且該Transaction收集到Block,成為Blockchain,該Transaction的Output就是UTXO了。這時Wallet的UTXO Pool就會記錄一筆UTXO了。

UTXO Pool就是Persistent Database,如果被破壞了,UTXO不見了,是否表示錢就不見了?

我們使用Bitcoin不用擔心Database消失這件事。因為Wallet的UTXO來自於Blockchain,而每一個Node都有相同的Blockchain。所以UTXO不見了,只要去連網,重新下載UTXO就好了。我們要擔心的是Private Key消失或洩露。

即然Wallet的UTXO來自於網路上的Blockchain,為何還要自己保存一份在UTXO Pool?

那是為了Offline Payment方便。可以在離線狀況,知道自己有多少錢。甚至可以做到離線支付。

如何預防 Malicious Wallet (惡意錢包)?

Bitcoin Wallet有很多型式,程式是其中一種。我們可以自己寫一個Wallet程式,然後建立一個Transaction,去挖別人的UTXO,變成自己的嗎?

如果有別人的Private Key,這麼做是可行的,因為我們可以拿別人的Private Key對Transaction的Input簽名。這樣一來,當Transaction上傳到某個Node,會被驗證通過,進而放到Blockchain,這樣錢就要不回來了。

所以Wallet的Private Key非常重要,絕不能洩露出去,也絕不能不遺失。因為若Private Key遺失,我們就沒辦將UTXO花掉。所以:
  • 「Private Key遺失」,就是錢不見的意思。
  • 「Private Key洩露」,就是錢隨時會被愉走的意思。

所以有另一種Wallet叫Paper Wallet,就是將Private Key印出來,長的像鈔票似的,上面有Private Key,還有它的二維碼。說它長的像鈔票,其實就是鈔票。和一般鈔票不同,這張鈔票是不能給別人看到的,自己留者備份,防止Private Key遺失。

下圖是「Mastering Bitcoin」這本書裡,談到的Paper Wallet


Paper Wallet安全嗎?

這裡有一個吊詭的地方。我們做Security System的都知道,存放Private Key最安全的地方是Secure Element,程式是無法讀取裡面的Private Key。
  • 程式要能讀取Private Key,才能列印。
  • 若Private Key能被程式讀取,表示它的儲存方式是不安全的。
這裡面還有很多細節,需要去探討。用密碼去保護Private Key,可能是其中一個方法。目前我還沒有明確的答案。

-Count

誰決定比特幣的交易稅(Transaction Fee)?

比特幣的每筆Transaction,有時會出現Fee。是誰指定的?指定後對於Transaction會有何影響?

翻了一下「Mastering Bitcoin」這本書,總結如下:

  • Minimum Transaction Fee由市場決定 (市場如何決定?待下一篇說明之)
    • Current Minimum Transaction Fee = 0.0001 bitcoin per kilobyte
  • 建立Transaction的人,可以指定Fee,也可以不指定
    • 若指定,至少要給Minimum Transaction Fee
    • 可以多給Fee,這樣Miner若挖到包含該Transaction的Block,就賺到了
  • 有些Miner喜歡挖有Fee的礦,有些不喜歡
  • Age和Fee會影響Node要先處理那些Transaction

下圖,Block包含了二大塊:Block Header、Transaction Space。

Transaction Space又分二區,第1區存放High-Priority Transactions,第2區存放有Fee的Transactions。




每個Miner在挖礦之前,會建立一個Candidate Block(如上圖),並且從Transaction Pool裡挑選幾個Transaction塞進來。

首先會挑選High-Priority Transactions到第一區。如何判定Transaction是High-Priority?

先計算Transaction的Priority:

Priority = Sum (Value of Input * Input Age) / Transaction Size

若Priority > 57,600,000為High Priority,書中舉的例子如下:

有一個Transaction,Size為250 bytes,Input總計為1 Bitcoin = 100m satoshis,待了1天,經過144個Block,都沒有被處理到,它的Priority目前為57,600,000。所以只要再經過1個block,就有可能被下一個block處理到了。

High Priority > 100,000,000 satoshis * 144 blocks / 250 bytes = 57,600,000

接下來,根據Fee挑選Transactions會被塞到第2區。沒有Fee的Transaction,絕不會到第2區。沒有Fee的Transaction,要等到Age增加,成為High-Priority Transaction,才有機會被塞到之後的Block的第1區。

-Count

2017年3月4日 星期六

Bitcoin有那些Pool?

在讀完"Mastering Bitcoin"這本書之後,我發現Bitcoin Network裡有許多不同種類的Pool:
  • UTXO Pool
  • Pool of Address
    • Vanity Pool
  • Transaction Pool
    • Orphan Transaction Pool
  • Orphan Block Pool
  • Mining Pool
    • Managed Pool
如果我們無法很清楚地了解這些Pool的含義及差異,表示我們對於Bitcoin Network的認知還不夠。因此,這裡試圖為大家介紹這些Pool。但不能保證大家可以因此而了解整個Bitcoin Network的運作。大家還是要下功夫去學習,求學問,很少能一步登天。大家要不斷地:思考、思考、再思考……。

首先,我們來了解UTXO Pool

UTXO全名是Unspent Transaction Outputs,意思就是尚未花費的Bitcoin。將所有UTXO的值加起來,就是整個Bitcoin的市值。Bitcoin Client會有一個Persistent Storage記錄UTXO Pool。

Transaction Pool v.s. Orphan Transaction Pool

每次新產生的Transaction,被Node驗證後,會先存放在Transaction Pool。Transaction的每一個Input,都要指向一個Parent Transaction。但如果有兩個Transaction,tx1與tx2同時產生, tx1是tx2的父親,如下圖左所示。



(1) 若tx2先進入某一個Node,驗證後,發現tx2的父親還沒進來,那麼,該Node會將它視為孤兒(Orphan),於是就將它放到Orphan Transaction Pool。 (2) 直到tx1進來後,(3) Node找到了tx2的父親,就將tx2從Orphan Transaction Pool移到Transaction Pool。

(最後一段,有誤,己更正。感謝大學同學,益修指正)

總結:


存放在UTXO Pool的Transaction都是被驗證過的(Confirmed),並且是以Persistent Storage形式永久存放的。

存放在Transaction Pool或Orphan Pool是尚未被驗證過的(Unconfirmed),是暫時存在Memory裡。

至於其它Pool,留待下篇講解。

-Count