比特幣:被放棄的那條 block chain 上面的交易該怎麼辦

一篇俄羅斯人分析比特幣寫的論文

https://dl.dropboxusercontent.com/u/3658181/PiotrPiasecki-BitcoinMasterThesis.pdf

個人最想了解的問題:出現分歧之後「被放棄的那條 block chain 上面的交易該怎麼辦」

這個問題還沒有解法

目前的答案應該是「被放棄的 block chain上面的交易被視為無效」

所以目前比特幣交易至少要等十分鐘之後才算完成(https://bitcoin.org/zh_TW/faq#why-do-i-have-to-wait-10-minutes)

也就是十分鐘之後交易才開始有被至少一個 Node 驗證

並且建議等待60分鐘,也就是產生了 6 個 block 之後才算保證安全

根據本論文紀錄 ,2012 年已知最長的被取消的區塊鍊長度為 4

 

有另一個資訊也非常有趣

論文第38頁

Reaching the current transaction volume of Visa (2000 transactions per second) would require a creation and propagation of 1.14GB Block each 10 minutes

也就是說如果要達到目前VISA的交易次數,每秒兩千次,每十分鐘生成的 block 會佔用1.14GB的空間,就網路傳輸來看,可以說跟本不可能達到比特幣設計初衷的將這個 block 散佈到所有 Node

The current implementation of the Bitcoin Protocol does not support such scalability. As a standard Transaction on average is at least 0.23kB in size and the maximum Block size is 1MB, the entire Block would be filled at most with 4348 Transactions. As each Block should be generated every 10 minutes, the Protocol can handle about 8 Transactions per second. The current peak usage of Bitcoin was about 14,000 Transactions in a day [124], averaging to about 0.16 Transactions per second

目前每一筆交易大約佔用 0.23KB 的空間,一個 block 大小為 1MB,平均一個 block 可以存放 4348 筆交易

並且每十分鐘才能產生一個 block ,也就是平均每秒可以處理至多 8 筆交易

目前平均一天有約 14,000 幣比特幣交易,平均每秒 0.16 筆

第44頁

Up to this date the longest Block Chain fork was 4 Blocks long

本篇論文撰寫的時候,最長的分歧也才4 個 block

也就是過去 40 分鐘內的交易失效了,我認為這時間並不短,而且交易失效非常嚴重

 

我是從http://bitcoin.stackexchange.com/a/4976/33824 這個連結發現這篇俄羅斯論文的

總結來說,目前針對 bitcoin 的缺陷能夠解決的辦法就是「等待」

「等待」一個 block 被算出來,或者更安全些,「等待」六個 block 被算出來

這個等待的時間遠遠長於一般日常的小額交易,例如你去超市買個咖啡交易只要三秒鐘,但等待要十分鐘

這個等待的時間遠遠短於跨國匯款的大額交易,例如你從台灣匯款到美國至少需要一天經過本地銀行+中轉行+收款行入帳,但是等待只要六十分鐘就算安全

又想到另一個問題,當初Satoshi Nakamoto 是怎麼想到 sha hash 開頭可能都是 0 ?能想到這點真是太天才了,一般常識認知 Hash 之後就是個亂數,沒想到竟然有機會找到開頭都是 0 ,這真的太神奇了!

 

2016/04/24更新

讀完了mastering-bitcoin中文版

整本沒有提出 fork chain 之後被放棄的鍊上面的交易該怎麼辦

http://zhibimo.com/read/wang-miao/mastering-bitcoin/mastering-bitcoin.pdf

El Gamal 加密演算法範例

以下範例操演一次 El-Gamal 加密演算法的過程,我們假設 AA 要傳送明文訊息 M = 46 給 BB。

公開選定的數(任意) g = 4 , 大質數 p = 113

每次傳送隨機選一個數字(任意) r = 3

首先 BB 要利用 g 值和另一個自選的值 X = 10

運算 gXmod p 得公鑰 Y = 49

AA 獲取 BB 的公鑰 Y 然後進行以下運算

  1. 43mod113≡C1 , C1 運算結果為64
  2. 46*493mod113≡C2 , C2 運算結果為 58
  3. C = (C1 , C2),密文 C 送給 BB

BB 接收到密文 C 之後進行以下運算以解密

  • 64113-1-10*46 mod 113≡46

餘數 46 即為明文。


下面解釋數學原理,這數學原理真是太強大了,真牛逼阿!

公開的數:g
大質數:p
接收端自選秘鑰(KEY):X
接收端公鑰:gX mod p
每次加密隨機產生的數:r
明文:M
密文:C = (C1 , C2)

發送端運算密文的方法:

  1. C1 = gr mod p
  2. C2 = M*(Y)r mod p
  3. 密文 C 由C1C2組成,收送端協議好分隔的方法即可

接收端解出明文的原理:

  1. (C1X)-1 * C2 mod p
  2. g-rX * M*(Yr) mod p
  3. g-rX * M*grX mod p
  4. M mod p
  5. 1 2 3 式都只是變數的代換,仔細看一下這些變數之間的關係一定可以了解的。
    第 4 式因為 M 比 p 小,所以求得餘數結果就是 M 了!

理論上這些式子成立,而且接收端可以收到第 1 式裡面的所有變數,所以只要接收端能夠運算出第一個式子的值,那明文就出來了!

不過,問題來了,試問(C1X)-1這個值是多少?即使硬算出來,應該也會發現他是一個分數,而導致無法繼續運算下去(我在這邊也卡很久,想了六天吧!)

為了解決這個問題,我們必須使用質數的另外一項特性,
如果 P 為質數,則任意數 C 滿足以下式子:

  • CP-1 mod P≡1
  • 136mod 7 ≡1
    236mod 7 ≡1

因此,第 1 式 (C1X)-1 mod p 的部份可以寫成下面這樣

  • C1p-1-X mod p

也就是說呢,整個解密的式子會變形為

  • C1p-1-X * C2 mod p

如此一來即可輕易地計算第 1 式的值了,也就獲得了明文 M 的值了。

而其安全性建立在所謂的『有限域上離散對數的難題』,白話一點的說,接收端公鑰:Y = gX mod p是看起來跟 KEY 最相關的東西,而且 Y 和 g 和 p 都是公開的數值,理論上一條等式裡面四個變數,三個已知,應該是可以算出第四個未知數,也就是 X(KEY) ,但實際上這個要算很久很久,時間長度久遠到算的上安全吧!

又如果第三者拿到了一段明文和一段密文的話可能運算出 KEY 嗎?也就是所謂的『Know-plaintext attack』,應該不行,因為拿到明文和密碼似乎對於計算 KEY 一點幫助也沒有= =a

想要暴力破解第 1 式的第三者…在目前的電腦運算力可能花一輩子也算不到正確的密文。

那麼,每次運算密文隨機選擇的 r 是做什麼用的呢?(我也還不知道阿~阿~阿~)

RSA演算法範例

先講一下 RSA 演算法裡面一些你需要知道的東西!

N = pq p、q分別都是隨意挑的質數,N是p、q的乘積。
φ(N) = (p-1)(q-1) φ(N)的意思是小於 N 的質數,(p-1)(q-1) 是φ(N)的公式算法。
gcd( e , φ(N) ) = 1 找出一個和 φ(N) 這個數互質的 e 。
d*e ≡ 1 (mod φ(N)) 找到 d ,條件如下,使得 d*e 之乘積除以 φ(N) 的餘數等於 1 !也就是說, ( d*e -1 ) 是 φ(N) 的整數倍!
Me≡C (mod N) M 代表原文,Me除以 N 取餘數,餘數即為密文!
Cd≡M (mod N) C 代表密文,Cd除以 N 取餘數,餘數即為密文!

數學原理不談。

知道以上這些東西之後,就可以真正來看一個 RSA 加密的傳送訊息範例!

Example:A 要傳送訊息 “islab" 給 B 。

首先 B 要運算出e, N:

  1. B 選擇 p = 47, q = 71,則 N = 3337 (47*71)。
  2. φ(N) = 3220 (46*70)。
  3. 找一個和 3220 互質的數字,假設我們找 79,e = 79。
  4. 利用公式 d*e ≡ 1 (mod φ(N)) ,推得 ( d*e -1 ) = Z*φ(N),Z是正整數、e是79、φ(N)是3220。找到Z為25時,d是正整數1019
  5. 把e=79、N=3337的訊息送過去給A

A 利用傳送過來的 e 和 N 運算出密文:

  1. 將原文 “islab" 轉為十進位的ASCII碼 “105115108097098″(我們假設通訊內容的字母編碼為三位數)。
  2. 將轉碼後的原文分割為三個數一組"105 115 108 097 098″,要割成幾個一組都可以。
  3. 進行加密的運算Me≡C (mod N)
  4. 10579(mod 3337) -> 193
    11579(mod 3337) -> 732
    10879(mod 3337) -> 1795
    09779(mod 3337) -> 957
    09879(mod 3337) -> 617

  5. 將密文"01930732179509570617″送給B,因為餘數最多可能到四位數,不足地方補零,才不會造成錯誤。

B利用 d 和 N 進行解密:

  1. 進行解密的運算Cd≡M (mod N)
  2. 1931019(mod 3337) -> 105
    7321019(mod 3337) -> 115
    17951019(mod 3337) -> 108
    9571019(mod 3337) -> 97
    6171019(mod 3337) -> 98

從頭到尾 d 都只有在 B 這邊出現,除非 d 值流出,否則別人即使得到網路上傳送的密文,也很難運算出原文!

PS:當指數高達千位時,我是利用python運算的,ex 5**5,5的5次方,python會自動轉為大數進行運算,超酷的!

Rotor Machine 旋轉機

在密碼學中,旋轉機是一種用來加密與解密秘密訊息的機械裝置,旋轉機在密碼歷史中雖然只有獨占鰲頭一小段時間,但也絕對是密碼史上相當輝煌的一段。旋轉機在 1930 年至 1950 年中間受到非常廣泛的使用,最有名的例子就是 Enigma machine

旋轉機的主要構造是轉片(rotors)、也稱為轉輪(wheels)、滾筒(drums),是由兩邊有一排排電磁接頭的轉片(rotor)組合而成的。在接點與接點中間的連線實做了各個字母的對應,並且用不規則的方式來排列。

180px-Enigma_rotor_set
德軍在第二次世界大戰使用的旋轉機,由三個轉片組成

就機械本身來說,能提供的安全保護並不高,但是透過旋轉機的進階使用,也就是加密每一個字母,透過此法便可以產生出複雜的多字母密碼( Polyalphabetic_substitution )

在古典密碼學中,最早的一種加密方法是替代密碼(substitution cipher),替代密碼用一種有系統的私密配對策略進行字母的替代。單一字符替代密碼只會使用一個字母作為替代,而這很容易被破解,使用 Frequency analysis 分析就可以了,稍微安全一點的方法是使用多個字母作為替代( polyalphabetic ciphers )。另外,因為這樣的加密方式是人工進行操作,所以能夠使用的字符數量很少,太多字符的話將會難以操作。

但是,只用少量的字符會導致加密很容易受到攻擊,而 Rotor Machine 的發明剛好精進了字符加密的方法,也讓大量字符加密的操作變得容易。

最早的密碼分析技術是 Frequency analysis ,每一種語言不同的字符組合可以用來找出單一字符替代密碼的字符資訊,舉例來說,在英文裡面,E、T、A、O、I、N這幾個字符很常使用(這同時也是鍵盤按鍵 排序混雜 的原因),所以這幾個字符相對應的替代密碼出現的頻率也會比較高,除此之外 bigram 例如像 NG ST ,很容易出現這樣的字符組組(編按:例如 th he in 等等),而Q就幾乎不會接在就幾乎不會接在U後面。因為字符替代密碼總是用一個密碼字符去代替名文字符,所以這些簡單的頻率分析才會得以使用。若非如此,解密將會變得困難許多!密碼學家多年來嘗試用幾組不同的替代密碼來隱藏會洩漏資訊的『頻率』這個資訊,但即使如此依然無法避免那些經常出現的連續字符組,字符替代方法在16世紀正式告終。

十五世紀中期,Alberti發明了一種新技術,也就是目前所熟知的多字母替代密碼 polyalphabetic ciphers ,這個技術確定了使用多字符替代的價值!

FROM Rotor_machine`wiki

感覺有點無聊,暫時不翻了= =a