Litecoin 的 Scrypt Mining 流程

萊特幣(Litecoin)基於Bitcoin的協議,但採用了Scrypt演算法的貨幣。
頭像
kevin
系統管理員
文章: 796
註冊時間: 2013年 12月 16日, 22:11

Litecoin 的 Scrypt Mining 流程

文章kevin » 2014年 1月 1日, 02:57

我一直很好奇挖礦到底在幹什麼。
不過一般只會提到Satoshi Nakamoto 的 Paper 但卻不太拆解它實作的流程。
所以趁著跨年前這段時間,研究了一下下...

Litecoin 是一個混和SHA256 跟 Scrypt 的 CryptoCurrency。
而Litecoin採用的Scrypt又帶有下列限定的 initial 參數。

代碼: 選擇全部

N = 1024;
r = 1;
p = 1;
buflen=32;

Scrypt 的輸入值一般為 Scrypt hash(password, salt, N=16384, r=8, p=1, buflen=64)
salt (密碼學中加鹽的部份, 用來增加雜湊處理的可靠性) 而在挖礦時password 跟 salt 同值。
N值為二的次方的整數,有一些CryptoCurrency 特別將N設為可變量, 希望藉此排除其他ASIC or FPGA設備礦機的可能性.
r 跟 p 值必須要滿足下式 r * p < 2^30 而 buflen則是 buflen <= (2^32 - 1) * 32。

讓我們取 Litecoin 第 100000 個block來當例子。
http://explorer.litecoin.net/block/e110 ... bf3946ce60

假設原先miner取得的getwork的時候,json長的像這樣。

代碼: 選擇全部

~/litecoind getwork
{
    "midstate" : "e11049dfa5858be3809f285685e12a5d6f84b936b0f8e8272b5363bf3946ce60",
    "data" : "00000001e29b694e070915c380466c4b101e64f3dffd4bfca3b6cc830efa1b85348917aea959ab3b821f375917c7458befed853b3e084324f97896a537ef99218d2d67bd4f6126711d00d54400000000000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000",
    "hash1" : "00000000000000000000000000000000000000000000000000000000000000000000008000000000000000000000000000000000000000000000000000010000",
    "target" : "000000000000000000000000000000000000000000000000000044d500000000"
}


其中midstate是Hash的Initial Value,在getwork挖礦時並不會直接拿來用。但我也不認為將來也會從getwork中移除。
而在 URL 中看到的 Litecoin 100000的 Block Hash : e11049dfa5858be3809f285685e12a5d6f84b936b0f8e8272b5363bf3946ce60
其實是後來才從"data"中生出來的。這邊舉例的這個是假值。

hash1是檢查用,並不會拿來運算。target則是解礦時Hash的門檻。

data 才是核心,而裡面則包含很多項目。

版本: Version - 00000001

前一個Block的Hash: Previous hash - e29b694e070915c380466c4b101e64f3dffd4bfca3b6cc830efa1b85348917ae
一般你在挖礦時會多次的進行getwork,但直到出現下一個Block之前,這個值都不會變。你在getwork的時候其實只有這個值跟DIFF是固定的。

Merkle root - a959ab3b821f375917c7458befed853b3e084324f97896a537ef99218d2d67bd

Merkle root其實是 Merkle Tree 的一個節點,而 Merkle Tree 又被稱為 Hash Tree,是一種資料結構當中常提到的搜尋樹的一種。
它的存在也被作為憑證使用,由你上一個節點證明你現在的這個交易是由此這個Block開始產生的。
具有鍊結關係。同時check交易的可性度時,只需要回溯到上一筆交易是可信的便可以信任這一次也是可信的。
而不用從頭確認。更好的是,由於Block跟Block之間也混和了Merkle root進來運算,所以Block的關聯性也完整的加進了Merkle Tree。

時間戳記 Timestamp - 4f612671

2012-03-14 23:14:57 的unix time = 1331766897, 將其轉成16進位 hex(1331766897) = 0x4f612671

Bits (target in compact form) - 1d00d544 (4 bytes)
難度 1.200 (Bits: 1d00d544)
其實呢... 將難度轉為 little-endian 小尾 44d5001d 後 套用算式: hex( 0x44d500 * 2**(8*(0x1d - 3)) ) 就是Target囉。

Nonce - 00000000

Nonce為正整數的UINT32變量。運算的過程中會跑一整個Nonce size的迴圈,藉由Nonce一直加上去調整你手上這個work,使它符合Target。
當然也有可能調整完還是不符合,這時就會再去取下一個。

#80019245

現在我們來試算一個可解的Block,將Nonce 訂為 2147586629(0x80019245),將我們剛剛舉的所有數值轉為 little-endian 。

代碼: 選擇全部

>>> import hashlib
>>> header_hex = ("01000000" +
...   "ae178934851bfa0e83ccb6a3fc4bfddff3641e104b6c4680c31509074e699be2" +
...   "bd672d8d2199ef37a59678f92443083e3b85edef8b45c71759371f823bab59a9" +
...   "7126614f" +
...   "44d5001d" +
...   "45920180")
>>> header_bin = header_hex.decode('hex')
>>> hash = hashlib.sha256(hashlib.sha256(header_bin).digest()).digest()
>>> hash.encode('hex_codec')
'60ce4639bf63532b27e8f8b036b9846f5d2ae18556289f80e38b85a5df4910e1'
>>> hash[::-1].encode('hex_codec')
'e11049dfa5858be3809f285685e12a5d6f84b936b0f8e8272b5363bf3946ce60'

這個小尾的hex_codec:e11049dfa5858be3809f285685e12a5d6f84b936b0f8e8272b5363bf3946ce60
若通過門檻,它就是Header (or midstate)啦。

scrypt函數的話有兩種.
第一個是ltc_scrypt litecoin的作者coblee弄好的版本。

代碼: 選擇全部

>>> import ltc_scrypt
>>> pow_hash = ltc_scrypt.getPoWHash(header_bin)
>>> pow_hash[::-1].encode('hex_codec')
'000000003b4ba52ab765631e20a04b88cd27f0b66d3509fb2da7781fae6d7901'

另外是一般的python scrypt module.

代碼: 選擇全部

>>> import scrypt
>>> pow_hash = scrypt.hash(header_bin, header_bin, 1024, 1, 1, 32)
>>> pow_hash[::-1].encode('hex_codec')
'000000003b4ba52ab765631e20a04b88cd27f0b66d3509fb2da7781fae6d7901'


因為 000000003b4ba52ab765631e20a04b88cd27f0b66d3509fb2da7781fae6d7901
低於 Target : 0x000000005d440000000000000000000000000000000000000000000000000000 於是此組值可解。

可喜可賀。

fishlover2009
文章: 362
註冊時間: 2013年 12月 20日, 05:26

Re: Litecoin 的 Scrypt Mining 流程

文章fishlover2009 » 2014年 1月 1日, 08:15

我一直在想說
因為一般都說挖礦是在找一個比某數還小的值...
所以如果只是這樣
用人腦來算會不會比較快??

還是說挖礦其實比較像
有一個數
經過了一大串加密運算
變成另一個數
然後給定一個範圍
要你猜出原本那個數是什麼?(猜數字遊戲?)
所以礦機就只能一直代入值
算到結果=加密後那個數
就等於挖到礦??

所以如果剛好礦機帶入幾個數
就得到答案了
就能運氣好挖走礦
也有可能礦機代到了最後一個可能的數才是答案
那就需要很多時間??

頭像
jclin
文章: 187
註冊時間: 2013年 12月 18日, 11:02

Re: Litecoin 的 Scrypt Mining 流程

文章jclin » 2014年 1月 1日, 09:13

基本上要是人腦可以算出來,也可透過公式化讓電腦算出來。
挖礦是找到一個數字,讓 SHA-256 或 scrypt 把資料跟你的數字運算後,得到比目標還要小的數字。
但是這跟 SHA-256 一樣是單方向函數,無法逆向。雖然有研就是專門找 collision,但是這並不是 cryptcurrency 所要。
所以只能用暴力法去窮舉。
DOGE: DDJEfQ9N6jtMcFFqeyRfM58yLbpFsny9oP

為什麼要貼錢包地址? 因為好心人士會打賞發錢

頭像
jclin
文章: 187
註冊時間: 2013年 12月 18日, 11:02

Re: Litecoin 的 Scrypt Mining 流程

文章jclin » 2014年 1月 1日, 22:02

補充一下為何 scrypt 會增加 ASIC/FPGA 礦機的難度。
SHA-256 其實很簡單的就只是一堆整數運算,加法、移位、旋轉、xor,甚至還可以切成 pipeline 來增加 throughput
而 scrypt 跟 SHA-256 最不一樣的就是他多了 PBKDF (Password-Based Key Derivation Function) 來作 ROM mix
Litecoin 用的 PBKDF 是 salsa, N=1024 表示有 1024 組記憶資料
因此需要 32 組 32-bit integer * 1024 = 1024 * 32 * 4 bytes = 128KB
每算一次 scrypt 需要至少 128KB 的記憶體空間,而這部份是無法省略或是 pipeline
因為後面再次作 1024 次計算,會用到這 1024 組的記憶資料
Initial 階段:
V1 = input X
V2 = X = salsa(X)
V3 = X = salsa(X)
...
V1024 = X = salsa(X)

ROM Mix 階段:
For i=1...1024
j = X[n] % 1024
X = salsa(X ^ Vj)
結果 output = X

另外現在 GPU 挖礦的速度其實受限於記憶體速度 & bandwidth,所以 hashrate 只有純理論上一半,因為 lookup gap = 2
表示 1024 組的記憶空間,程式只記了 V1,V3,V5... 等間隔的值,而另外的值是需要時再由前一組的值去計算而來。
因為 GPU 在 access global memory 時候會大大降低效能導致,所以不要去記每一筆 1024 組的數值反而會比較快。
可是就 GPU computation unit 來說,等於需要時 runtime 還要再多去計算一次,造成運算上的浪費。
舉例來說
V1 = X
V2 = salsa(V1)
V3 = salsa(V2)
因為只有記了 V1, V3,雖然不存 V2 還是要算才能得到 V3,這邊無法省略不去計算。
可是 V2 並沒有存入記憶體,所以 ROM mix 需要 V2 時,只好從 V1 再來計算 V2
但好處是,本來需要 128KB 的記憶體量,瞬間變成 64KB 而已。如果 lookup gap = 3,就只要 32KB
但是想當然省這些記憶體就需要額外的計算時間,這就要看 memory access time/bandwidth 跟 ASIC 本身運算速度上 trade-off

另外網路上找到的參考資料。
https://docs.google.com/viewer?url=http ... oncept.pdf
DOGE: DDJEfQ9N6jtMcFFqeyRfM58yLbpFsny9oP

為什麼要貼錢包地址? 因為好心人士會打賞發錢

圈圈你個大圈
文章: 62
註冊時間: 2013年 12月 18日, 00:05

Re: Litecoin 的 Scrypt Mining 流程

文章圈圈你個大圈 » 2014年 1月 2日, 11:09

看起來和BTC完全不同的運算方式...
之前研究BTC時是完全看不太懂它底層怎樣運算
後來看我教授寫的文章後才稍微了解到...
順便推廣一下這雜誌XD>>>>
http://programmermagazine.github.io/201401/htm/home.html

LTC又是另一種算法@@..
一種幣一個算法,那大概會延伸很多無限種...

頭像
jclin
文章: 187
註冊時間: 2013年 12月 18日, 11:02

Re: Litecoin 的 Scrypt Mining 流程

文章jclin » 2014年 1月 2日, 11:44

圈圈你個大圈 寫:看起來和BTC完全不同的運算方式...
之前研究BTC時是完全看不太懂它底層怎樣運算
後來看我教授寫的文章後才稍微了解到...
順便推廣一下這雜誌XD>>>>
http://programmermagazine.github.io/201401/htm/home.html

LTC又是另一種算法@@..
一種幣一個算法,那大概會延伸很多無限種...


原來 kevin 大是陳教授學生

基本上 cryptocurrency 底層的原理和做法都是一樣,只是廣義上 hash function 方式不一樣。
有另外一種幣別叫做 primecoin,把質數拿來當作解答。這對科學計算也很有貢獻,現在有些大質數是 prime coin P2P network 找到的
BTC hash function = SHA-256
LTC hash function = scrypt = SHA-256 + salsa PBKDF
XPM hash function = prime searching
DOGE: DDJEfQ9N6jtMcFFqeyRfM58yLbpFsny9oP

為什麼要貼錢包地址? 因為好心人士會打賞發錢

圈圈你個大圈
文章: 62
註冊時間: 2013年 12月 18日, 00:05

Re: Litecoin 的 Scrypt Mining 流程

文章圈圈你個大圈 » 2014年 1月 2日, 12:03

jclin 寫:
圈圈你個大圈 寫:看起來和BTC完全不同的運算方式...
之前研究BTC時是完全看不太懂它底層怎樣運算
後來看我教授寫的文章後才稍微了解到...
順便推廣一下這雜誌XD>>>>
http://programmermagazine.github.io/201401/htm/home.html

LTC又是另一種算法@@..
一種幣一個算法,那大概會延伸很多無限種...


原來 kevin 大是陳教授學生

基本上 cryptocurrency 底層的原理和做法都是一樣,只是廣義上 hash function 方式不一樣。
有另外一種幣別叫做 primecoin,把質數拿來當作解答。這對科學計算也很有貢獻,現在有些大質數是 prime coin P2P network 找到的
BTC hash function = SHA-256
LTC hash function = scrypt = SHA-256 + salsa PBKDF
XPM hash function = prime searching



prime我之前只知道是拿來跑CPU的壓力測試....
雖然那套tool我現在還是搞不清楚怎用(prime95)
最近不久才發現原來這也有創造幣的價值...
看起來比較偏向科學運用

頭像
kevin
系統管理員
文章: 796
註冊時間: 2013年 12月 16日, 22:11

Re: Litecoin 的 Scrypt Mining 流程

文章kevin » 2014年 1月 2日, 15:21

jclin 寫:原來 kevin 大是陳教授學生


等等... 這裡的陳教授應該是 圈圈你個大圈 的教授,陳鍾誠教授吧... :lol:

怎麼出現我的名子了... XDDDDD

頭像
jclin
文章: 187
註冊時間: 2013年 12月 18日, 11:02

Re: Litecoin 的 Scrypt Mining 流程

文章jclin » 2014年 1月 2日, 15:27

kevin 寫:
jclin 寫:原來 kevin 大是陳教授學生


等等... 這裡的陳教授應該是 圈圈你個大圈 的教授,陳鍾誠教授吧... :lol:

怎麼出現我的名子了... XDDDDD


阿阿,看錯作者了,眼花了 haha
DOGE: DDJEfQ9N6jtMcFFqeyRfM58yLbpFsny9oP

為什麼要貼錢包地址? 因為好心人士會打賞發錢


回到「Litecoin」

誰在線上

正在瀏覽這個版面的使用者:沒有註冊會員 和 1 位訪客