"擁有"一枚比特幣究竟意味著什么？

很多人都聽(tīng)說(shuō)過(guò)比特幣, 它是一種數(shù)字貨幣，并不需要特定政府發(fā)行, 也不依賴(lài)銀行來(lái)管理賬戶及驗(yàn)證交易, 甚至都沒(méi)有人真正知曉其發(fā)明者，很多人都不知道上面那個(gè)問(wèn)題的答案, 或者說(shuō)至少不全了解. 要想搞明白，同時(shí)也為了讓比特幣背后的技術(shù)細(xì)節(jié)顯得直觀, 我們將從你會(huì)如何發(fā)明自的比特幣的過(guò)程中一步一步地闡明.

首先我們從你用于記錄你與好友們交易的公共賬本開(kāi)始, 然而你與好友及世界上的其他人的互信開(kāi)始逐漸降低. 但聰明的你引入了密碼學(xué)中的某些概念來(lái)解決信任危機(jī), 你就創(chuàng)造了一種新事物，叫做"加密貨幣".

比特幣只是第一個(gè)被廣泛應(yīng)用的加密貨幣的例子, 而如今有了更多其他的加密貨幣并與傳統(tǒng)貨幣可以發(fā)生交易. 現(xiàn)在從你想要發(fā)明你自己的加密貨幣入手, 能幫助我們理解如今幾大主流加密貨幣的理論基礎(chǔ), 了解其背后在不同方面存在著不同的設(shè)計(jì)空間.

事實(shí)上我選這個(gè)選題是因?yàn)樵谶^(guò)去一年中針對(duì)加密貨幣有大量的關(guān)注、資本投入甚至老實(shí)講還有媒體過(guò)分渲染. 我并不會(huì)對(duì)當(dāng)前及未來(lái)的匯率發(fā)表評(píng)論及預(yù)測(cè), 但我想任何想要購(gòu)買(mǎi)加密貨幣的人都應(yīng)搞明白加密貨幣究竟是怎么一回事.

我不會(huì)含糊地將其與挖礦作類(lèi)比, 我會(huì)直接描述當(dāng)我們發(fā)送、接受、創(chuàng)造加密貨幣時(shí)候, 計(jì)算機(jī)內(nèi)部所發(fā)生的事情和原理.

我還要強(qiáng)調(diào)一點(diǎn)：雖然我們將花一些時(shí)間稍深入地了解背后的原理, 但是如果僅僅日常使用的話，我們并不需要了解其詳細(xì)技術(shù)原理, 就像你不需要了解你刷信用卡背后所發(fā)生的一切一樣. 與電子支付一樣，加密貨幣也有很多方便易用的App可以直接用于發(fā)送和接受貨幣, 而不需要知道是怎么實(shí)現(xiàn)的.

區(qū)別在于加密貨幣的背后并不是某家銀行來(lái)驗(yàn)證交易, 而是一套基于密碼學(xué)中某些數(shù)學(xué)方法的, 來(lái)在去中心化的、互不信任的交易下驗(yàn)證交易的可靠.

在開(kāi)始講之前，你暫時(shí)把加密貨幣放在一邊, 我們先從更基本的概念入手：賬本和電子簽名。

如果你和你的朋友們有很頻繁的金錢(qián)來(lái)往, 比如AA支付晚餐的賬單等等, 總是用現(xiàn)金總是不方便的. 所以可能會(huì)用到一個(gè)公共賬本: 它記錄了未來(lái)將要償還的所有數(shù)目, 如Alice支付Bob 20元，Bob支付Charlie 40元等等.

這個(gè)賬本必須是公開(kāi)的，每個(gè)人都能查閱, 就像一個(gè)網(wǎng)站一樣，每個(gè)人都能查閱并添加新的交易記錄. 而到了每個(gè)月底大家對(duì)交易記錄都無(wú)異議就會(huì)一起把賬算清. 如果你入不敷出，就要再掏錢(qián)出來(lái). 如果仍有結(jié)余，就可以從中拿回自己多付的錢(qián).

所以這個(gè)簡(jiǎn)單體系的設(shè)計(jì)大概會(huì)是如下所述: 每個(gè)人都能向賬本添加新的交易信息，到月底再用真金白銀統(tǒng)一結(jié)算.

但這樣的公共賬本存在一個(gè)問(wèn)題，正因?yàn)槊總€(gè)人都能添加交易記錄, 應(yīng)該怎樣避免Bob在沒(méi)有經(jīng)過(guò)Alice同意的情況下偷偷記下：Alice給Bob 100元. (這樣月底結(jié)算時(shí)候, Alice就要為這筆捏造出來(lái)的交易付錢(qián)出來(lái)了).

我們又憑什么相信賬本中的記錄都準(zhǔn)確無(wú)誤呢, 這里就需要密碼學(xué)中的電子簽名技術(shù). 就像手寫(xiě)簽名一樣，Alice需能在每筆交易信息邊上留下記錄, 以證明她了解并且認(rèn)可這筆交易發(fā)生, 而且這個(gè)簽名不能被他人獲取并偽造.

電子簽名確保交易的真實(shí)性

乍一思索電子簽名似乎不太可能實(shí)現(xiàn), 無(wú)論電子簽名是如何存儲(chǔ)的，計(jì)算機(jī)都可以讀取并復(fù)制. 那究竟該如何防止偽造呢? 要實(shí)現(xiàn)電子簽名，每個(gè)人都需要生成一對(duì)秘鑰: 公共密鑰及私人密鑰.

每一個(gè)密鑰其實(shí)都是一串 0 或 1 比特串. 私人密鑰有時(shí)也被叫做"秘密"鑰匙, 以便能夠縮寫(xiě)成 sk, 公共密鑰則縮寫(xiě)成 pk.

正如其名，私人密鑰是由你自己保存的, 現(xiàn)實(shí)生活中，你本人所簽署的所有文件中的簽名都是一樣的. 電子簽名則更進(jìn)一步，它會(huì)隨著簽署的內(nèi)容變化而改變. 它看上去就是一串10代碼，通常長(zhǎng)度是256位. 而任何要加密內(nèi)容的一個(gè)字符的變動(dòng)都會(huì)讓這串產(chǎn)生的新的簽名變得完全不同.

正式一點(diǎn)地講，產(chǎn)生這樣的簽名需要一個(gè)函數(shù) Sign, 它同時(shí)要求所簽署的內(nèi)容以及你的私人密鑰,也就是Sign(簽署的內(nèi)容, 秘鑰) → 生成新的簽名.

私人密鑰確保了只有你本人能產(chǎn)生這個(gè)電子簽名, 這個(gè)產(chǎn)生的簽名還取決于所要簽署的內(nèi)容, 就意味著其他人不能簡(jiǎn)單地復(fù)制這個(gè)簽名, 并在其他捏造的內(nèi)容上偽造另一個(gè)簽名(因?yàn)槟笤斓膬?nèi)容肯定與原內(nèi)容不同).

與此同時(shí)還有一個(gè)函數(shù) Verify 驗(yàn)證用于驗(yàn)證簽名是否真實(shí), 而這個(gè)函數(shù)還需要三樣?xùn)|西:簽署的內(nèi)容, 生成的簽名, 公共密鑰. 它的作用是告訴我們這個(gè)簽名是否是由輸入公鑰對(duì)應(yīng)私鑰來(lái)生成的.

這里并不會(huì)具體討論這些函數(shù)具體如何實(shí)現(xiàn)([遇見(jiàn)數(shù)學(xué)]會(huì)在未來(lái)《圖解密碼學(xué)》中介紹), 但它保證了如果你不知道對(duì)方私鑰的情況下，幾乎不可能找到一個(gè)正確的簽名. 準(zhǔn)確地講，只有通過(guò)窮舉并反復(fù)驗(yàn)證才有可能找到正確的簽名, 然后用公開(kāi)的公鑰 pk 來(lái)通過(guò)驗(yàn)證.

現(xiàn)在想想256位比特到底有多少可能的簽名, 總共有2256次方個(gè)可能的簽名, 這是一個(gè)天文數(shù)字, 稱(chēng)其為天文數(shù)字實(shí)際上又遠(yuǎn)遠(yuǎn)高估了天文學(xué)的范疇, 我還做了另一個(gè)補(bǔ)充視頻來(lái)演示這個(gè)數(shù)字究竟有多大，文后會(huì)詳細(xì)介紹。

現(xiàn)在如果一旦你驗(yàn)證了一個(gè)簽名是真的, 你就能相當(dāng)有把握地認(rèn)為, 這個(gè)簽名只能由他本人持有的私鑰加密產(chǎn)生.

編號(hào)確保交易唯一性

現(xiàn)在確保了每個(gè)人都會(huì)在交易信息后面簽名, 不過(guò)仍然會(huì)存在另一個(gè)問(wèn)題, 比如Alice簽署了一條Alice支付Bob 100元的交易記錄, 即便Bob不能在Alice的新交易記錄上偽造簽名, 他還可以把這條記錄隨心所欲地復(fù)制好幾遍, 因?yàn)檫@些記錄以及它對(duì)應(yīng)的簽名都是正確的.

要解決這個(gè)問(wèn)題，你在簽署每一筆新的交易信息時(shí), 交易信息還必須包含一個(gè)唯一的編號(hào)與之對(duì)應(yīng). 那樣如果Alice多次支付Bob 100元的話, 賬本上的每條記錄都會(huì)要求一個(gè)新的簽名.

有了電子簽名就解決絕大部分了原本體系中的信任危機(jī), 但要真正實(shí)現(xiàn)，仍然需要依賴(lài)一個(gè)類(lèi)似的信用機(jī)構(gòu), 也就是說(shuō)你信任每個(gè)人到了月底都會(huì)出現(xiàn)并用現(xiàn)金結(jié)算, 因?yàn)槿f(wàn)一Charlie欠了很多錢(qián)但就是不出來(lái)還錢(qián)該怎么辦, 這就是月底人們?cè)俅斡矛F(xiàn)金結(jié)算的唯一原因 - 擔(dān)心某些人(比如 Charlie) 欠了很多錢(qián).

聰明的你想到了一個(gè)方法就不需要真正再用現(xiàn)金結(jié)算, 只要能夠避免其中有些人的支出金額小于剩余可支付金額. 比如所有人剛開(kāi)始就需要往賬上支付100元，賬本上最先記錄幾條：Alice獲得100元，Bob獲得100元，Charlie等等.

現(xiàn)在只需要拒絕在賬本上記錄某些人入不敷出的交易就可以了, 舉個(gè)例子，如果前兩條交易記錄是: Charlie支付Alice 50元，Charlie支付Bob 50元. 再來(lái)如果Charlie還要支付你20元的時(shí)候，那這項(xiàng)交易將是無(wú)效的，這就跟他沒(méi)有簽名一樣是無(wú)效的.

不過(guò)這就意味著驗(yàn)證當(dāng)前的一條交易, 就需要了解截至當(dāng)前所有的歷史交易信息. 這在加密貨幣中同樣如此，并且仍有待優(yōu)化的余地.

但有趣的是，這個(gè)設(shè)計(jì)真正去掉了賬本和真實(shí)美元之間的聯(lián)系, 理論上如果世界上所有人都是用這個(gè)賬本, 你整個(gè)一生都可以在這個(gè)賬本上支付并獲得收入中度過(guò), 根本沒(méi)有必要獲得真實(shí)的貨幣.

為了強(qiáng)調(diào)這一點(diǎn)，我們把賬本上的貨幣單位稱(chēng)之為"賬本元"，并簡(jiǎn)稱(chēng)為L(zhǎng)D. 當(dāng)然, 你也可以隨時(shí)將LD自由地兌換成真的美元.

舉個(gè)例子，Alice在現(xiàn)實(shí)中給了Bob 100元, 同時(shí)Bob在公共賬本上記上Bob支付Alice 100元. 但這樣的兌換并不在這套系統(tǒng)的設(shè)計(jì)初衷之內(nèi), 所以不會(huì)受協(xié)議的保護(hù). 這樣的兌換與美元和歐元或市場(chǎng)上其他的貨幣兌換類(lèi)似, 那是另外一個(gè)事情了.

比特幣的核心

這是理解比特幣和其他加密貨幣的最重要的信息了, 它實(shí)際上就是一個(gè)賬本, 所有的歷史交易就視為貨幣的實(shí)體.

當(dāng)然就比特幣而言, 人們只有用現(xiàn)金購(gòu)買(mǎi)和使用比特幣才會(huì)在賬本上記錄. 但新的比特幣如何產(chǎn)生我一會(huì)兒再細(xì)說(shuō).

但此之前，我們的LD體系和實(shí)際的加密貨幣還有一處不同, 我剛提到這個(gè)公共賬本存在于某個(gè)公共地點(diǎn). 比如一個(gè)網(wǎng)站，所有人都能登陸并添加記錄, 那樣的話我們就必須信任這一中心機(jī)構(gòu). 那究竟誰(shuí)來(lái)管理這個(gè)網(wǎng)站，誰(shuí)來(lái)控制添加記錄的規(guī)則呢?

考慮到如果讓所有人都能獲取這份賬本也就不需要信任中心機(jī)構(gòu)了. 當(dāng)你需要發(fā)生交易，如Alice支付Bob 100元, 你需要將這個(gè)信息廣播給網(wǎng)絡(luò)中所有的其他人, 他人收到了這個(gè)信息都在自己那份賬本上記下這條交易.

這樣想法雖然簡(jiǎn)單，但真的這樣設(shè)計(jì)就會(huì)相當(dāng)糟糕, 因?yàn)槿绾未_保所有人手里都是正確的那份賬本呢

當(dāng)Bob收到了如Alice支付Bob 10 LD 的交易，他如何確保并相信其他所有人也同樣收到了這一信息, 以便未來(lái)能讓他在可以用這 10 LD支付給Charlie做交易呢?

試著想想是你自己收聽(tīng)著來(lái)自外界的交易信息廣播, 該如何確保其他人和你一樣以相同的順序接受交易信息, 這才是關(guān)鍵所在，也是一個(gè)有趣的難題.

你能想出一個(gè)協(xié)議來(lái)決定接受或拒絕收到的交易信息, 而且你確信其他所有人在這個(gè)方法下能以同樣的順序接受交易信息, 最終可以形成一模一樣的賬單, 這也是比特幣原始論文中詳述的部分.

簡(jiǎn)單地講，比特幣給出解決辦法是: 選擇信任消耗最多計(jì)算資源(計(jì)算量最大)的那份賬本. 我會(huì)花一些時(shí)間詳細(xì)講是什么意思, 它涉及到"加密散列函數(shù)"這個(gè)概念.

基本的思路如下：如果你將計(jì)算資源的消耗作為你信任的基礎(chǔ)，那么偽造交易記錄和賬本不一致的情形所要耗費(fèi)的計(jì)算力成本要高到不可行。

這個(gè)想法實(shí)在是太酷了！如果你懂了，你就會(huì)理解比特幣和其他加密貨幣的核心.

那么首先，什么是散列(哈希)函數(shù)？這些函數(shù)的輸入可以是任何信息或文件, 它們會(huì)輸出一個(gè)固定長(zhǎng)度的比特字符串，如256位, 這個(gè)輸出值叫做這個(gè)信息的散列值，或者稱(chēng)其為"摘要", 它故意設(shè)計(jì)成會(huì)輸出看似相當(dāng)隨機(jī)的內(nèi)容, 但并不是隨機(jī)的，只要是給定相同的信息總是輸出相同的內(nèi)容.

但如果你將輸入稍作修改，也許僅僅只是修改了其中一個(gè)字符，最終的散列值會(huì)變得面目全非. 事實(shí)上，我這里做演示的散列函數(shù)叫做"SHA256" .

輸入的輕微修改，輸出就會(huì)完全不同，毫無(wú)規(guī)律可言, 明白了吧，這不是普通的散列函數(shù)，這是加密散列函數(shù), 這就意味著逆向計(jì)算是不可能的.

如果告訴你一串 256 位的1,0的字符串然后問(wèn)你, 找到SHA256 函數(shù)輸入的內(nèi)容, 使得兩者經(jīng)過(guò) SHA256 后具有同樣的結(jié)果. 你只有一個(gè)一個(gè)暴力去試錯(cuò)的方法.

不過(guò)你想感受一下2^256次方個(gè)嘗試究竟需要計(jì)算多久, 可以看看這個(gè)補(bǔ)充視頻(《256位加密有多安全?》過(guò)幾天[遇見(jiàn)數(shù)學(xué)]會(huì)整理出來(lái)).

你會(huì)想如果知道了這個(gè)函數(shù)的運(yùn)作細(xì)節(jié), 是不是就可以不用瞎猜, 而是可以倒推回來(lái)猜出這個(gè)輸入呢. 但目前沒(méi)有人可以做到.

有趣的是，目前還沒(méi)有嚴(yán)格的證明逆向計(jì)算是困難的, 但目前大量的安全行業(yè)和加密需求都取決于加密散列函數(shù)以及它的這個(gè)性質(zhì).

如果你細(xì)看瀏覽器和 youtube 建立的加密連接背后的加密算法, 或?yàn)g覽器連接銀行網(wǎng)站時(shí), 你很可能會(huì)看到SHA256算法.

但現(xiàn)在，我們的關(guān)注點(diǎn)會(huì)是這樣的散裂函數(shù)如何證明賬單上一系列的交易是和一個(gè)很大計(jì)算量有關(guān)系呢?

想想如果有人給你一份交易記錄，并說(shuō)"嘿！我發(fā)現(xiàn)了一個(gè)特殊的數(shù)字(下圖中賬本中綠色數(shù)字 1073765433)，你把這個(gè)數(shù)字放在這份交易記錄后面, 然后在給整個(gè)交易記錄信息進(jìn)行SHA256函數(shù)計(jì)算后, 前面30個(gè)數(shù)字都會(huì)是0！"

你想想找到這樣的一個(gè)數(shù)字有多難？對(duì)于一個(gè)隨機(jī)的信息，其散列值前30位都是0的概率是2的30次方分之一, 也就是差不多是十億分之一, 而且因?yàn)镾HA256是一個(gè)加密散列函數(shù), 找到這個(gè)特殊數(shù)字的唯一方法只能是暴力窮舉驗(yàn)證, 所以你基本上已經(jīng)嘗試了十億次, 才找到了這個(gè)特別數(shù)字.

而你一旦知道了這個(gè)數(shù)字，很快計(jì)算一下這個(gè)交易列表和數(shù)字在一起作為輸入, 經(jīng)過(guò)散列計(jì)算后發(fā)現(xiàn)開(kāi)頭確實(shí)是30個(gè)0就行列.

換言之，你能很快地驗(yàn)證他們確實(shí)經(jīng)過(guò)了大量的計(jì)算, 而你不需要親自消耗這么大計(jì)算量。這叫做"工作量證明".

重要的是，這個(gè)工作量證明本身就對(duì)應(yīng)列這份交易記錄. 如果你更改了其中一條交易信息，即便是修改列一個(gè)數(shù)字, 也會(huì)完全改變最終的散列值. 所以就又需要經(jīng)過(guò)十億次嘗試才能找到新的工作量證明 - 即找到那個(gè)特別數(shù)字, 接在你修改后的交易列表后面, 使得對(duì)應(yīng)的散列值開(kāi)頭是 30 個(gè)0.

現(xiàn)在回過(guò)頭來(lái)考慮我們的分布式賬本的情形：每個(gè)人都在廣播交易信息，我們想找到一個(gè)方法能讓所有人都認(rèn)可一份正確的賬單. 我前面說(shuō)過(guò)比特幣原始論文的核心點(diǎn)就是, 每個(gè)人都信任需要消耗最大計(jì)算量的那份賬單.

要實(shí)現(xiàn)這個(gè)想法首先需要將賬單整理成"區(qū)塊". 這些區(qū)塊包含了一系列交易信息以及其工作量證明, 也即有一個(gè)特別數(shù)字滿足其散列值以一系列0開(kāi)頭.

我們暫時(shí)先定60個(gè)0開(kāi)頭吧，一會(huì)兒我們會(huì)回頭來(lái)看如何系統(tǒng)地確定這些0的個(gè)數(shù).

類(lèi)比于交易信息要經(jīng)過(guò)發(fā)送方簽名才被認(rèn)定為有效, 同樣的, 一個(gè)區(qū)塊只有當(dāng)它有工作量證明時(shí)才被認(rèn)定為有效.

而且為了確保這些區(qū)塊有一個(gè)標(biāo)準(zhǔn)的順序, 我們規(guī)定前一區(qū)塊的散列值必須加入到當(dāng)前區(qū)塊的頭部信息中.

這樣的話，如果你回頭想改變其中某個(gè)區(qū)塊的內(nèi)容, 或交換兩個(gè)區(qū)塊的順序, 你就會(huì)改變它后一個(gè)區(qū)塊的內(nèi)容, 也就改變了那個(gè)區(qū)塊的散列值, 然后又影響到再下一個(gè)區(qū)塊......

這就需要重新計(jì)算所有這些區(qū)塊的散列值，重新尋找每個(gè)特別數(shù)字使得區(qū)塊的散列值以60個(gè)0開(kāi)頭. 因?yàn)樗械膮^(qū)塊以這種方式相互鏈接, 所以我們一般不把它叫做賬本，而是為"區(qū)塊鏈"(blockchain).

在這個(gè)新的體系之下，我們現(xiàn)在允許世界上的每個(gè)人都參與建造區(qū)塊, 意思是說(shuō)他們都可以收聽(tīng)網(wǎng)絡(luò)中的交易信息，整理這些信息生成區(qū)塊，然后花大量的計(jì)算工作, 找到那個(gè)特別數(shù)字使得區(qū)塊的散列值以60個(gè)0開(kāi)頭.

一旦找到了這個(gè)數(shù)字，他們就將這個(gè)區(qū)塊廣播出去. 為了獎(jiǎng)勵(lì)這個(gè)區(qū)塊建立者所消耗巨大的計(jì)算量付出，當(dāng)她建立了一個(gè)區(qū)塊，我們規(guī)定她可以把一筆特別的交易信息放在賬單開(kāi)頭，即：讓她憑空獲得10 LD。這叫做"區(qū)塊獎(jiǎng)勵(lì)"，這并不屬于任何交易, 它并不來(lái)自于其他人，所以也并不需要簽名。

這也意味著, 每一個(gè)新建的區(qū)塊都會(huì)增添新的虛擬貨幣, 建立區(qū)塊通常叫做"挖礦"，因?yàn)樗鼤?huì)需要消耗大量的計(jì)算工作量, 挖礦會(huì)為整個(gè)經(jīng)濟(jì)中引入新的貨幣量.

所以當(dāng)你聽(tīng)到或看到礦工時(shí), 你現(xiàn)在明白他們所做的其實(shí)就是:收聽(tīng)交易信息，建立區(qū)塊，廣播區(qū)塊，并獲得新貨幣的獎(jiǎng)勵(lì)，如此而已．

而在礦工眼中，每個(gè)區(qū)塊就像是一個(gè)小型的彩票，每個(gè)人都想盡可能快得猜對(duì)那個(gè)特殊的數(shù)字，直到其中有一個(gè)幸運(yùn)兒找到了那個(gè)特別數(shù)字，能讓區(qū)塊的散列值以很多0開(kāi)頭，然后他們就得到獎(jiǎng)勵(lì).

而對(duì)于其他只是想利用這個(gè)系統(tǒng)做交易的人而言，并不需要收聽(tīng)交易記錄，他們只需要收聽(tīng)被礦工廣播的區(qū)塊即可，然后更新自己保持的區(qū)塊鏈就可以了.

現(xiàn)在我們協(xié)議的關(guān)鍵點(diǎn)來(lái)了, 如果我們收到了兩份完全不同的區(qū)塊鏈，其中交易信息相沖突的時(shí)候, 你只保留最長(zhǎng)的那一個(gè)，也就是包含最大的工作量的那一份(比如區(qū)塊鏈長(zhǎng)度為 4和5 , 就選擇長(zhǎng)度為 5 的那份)。

如果暫時(shí)難分上下，等待下一個(gè)區(qū)塊的廣播，總有一個(gè)會(huì)形成更長(zhǎng)的區(qū)塊鏈, 所以即便沒(méi)有中心權(quán)威機(jī)構(gòu)，所有人也都各自記錄自己的那份區(qū)塊鏈, 但如果每個(gè)人都信任最多工作量的那個(gè)區(qū)塊鏈，我們就達(dá)到了一個(gè)去中心化的共識(shí).

為了理解這個(gè)系統(tǒng)為什么可信，以及怎樣才應(yīng)該相信每一筆交易是否真實(shí). 我們其實(shí)可以去理解, 要怎么做才能在這個(gè)系統(tǒng)下進(jìn)行欺騙.

也許Alice想要用一個(gè)偽造的區(qū)塊欺騙Bob, 也就是她給Bob一個(gè)區(qū)塊里包含里她支付Bob 100賬元的信息, 但她沒(méi)有把這個(gè)區(qū)塊廣播給網(wǎng)絡(luò)中的其他人. 那樣的話，其他人都還以為她仍然持有那100賬元. 為了做到這一點(diǎn), 她要比其他所有礦工先找到工作量證明才能欺騙所有人, 因?yàn)樗械牡V工他們也都在獨(dú)立建造區(qū)塊.

而這確實(shí)是有可能發(fā)生的！有可能Alice剛好比其他所有人都先找到了這個(gè)表示計(jì)算量的特殊數(shù)字, 但Bob也還會(huì)收到來(lái)自其他礦工的區(qū)塊廣播. 所以為了讓他相信她那份偽造的區(qū)塊，Alice后面都要持續(xù)重新計(jì)算, 她那份偽造給Bob的區(qū)塊后面的所有區(qū)塊, 這些區(qū)塊和Bob收到了來(lái)自其他礦工的區(qū)塊都不同.

但系統(tǒng)協(xié)議規(guī)定Bob總是信任他所指的最長(zhǎng)的那一個(gè)區(qū)塊鏈, Alice在前幾個(gè)區(qū)塊還有可能保持領(lǐng)先 - 剛好碰巧她比其他所有礦工都先找到那個(gè)區(qū)塊.

但除非她擁有接近所有礦工的計(jì)算資源的50%, 否則, 從概率上看, 基本能肯定的是其他所有礦工計(jì)算的區(qū)塊會(huì)比Alice偽造給Bob的區(qū)塊形成的區(qū)塊鏈更長(zhǎng)更快.

所以經(jīng)過(guò)足夠長(zhǎng)的時(shí)間，Bob會(huì)拒絕他收到的來(lái)自Alice的區(qū)塊鏈, 而選擇其他所有人都在使用的最長(zhǎng)的區(qū)塊鏈.

注意了, 這意味著你不一定要信任你剛剛接受到的新區(qū)塊, 而應(yīng)該等后面有新的幾個(gè)區(qū)塊添加后, 如果你還沒(méi)收聽(tīng)到更長(zhǎng)的區(qū)塊鏈，你就能信任這個(gè)區(qū)塊的確屬于其他所有人都在用的那條鏈上.

到此，我們講解了所有主要內(nèi)容, 這個(gè)基于工作量證明的分布式賬本系統(tǒng), 基本上就是比特幣還有其他加密貨幣的工作原理. 再講講更多的細(xì)節(jié), 剛我講到工作量證明, 就是尋找那一個(gè)特別數(shù)字, 滿足其區(qū)塊的散列值以60個(gè)0開(kāi)頭. 而現(xiàn)實(shí)的比特幣協(xié)議中會(huì)定理改變 0 的個(gè)數(shù), 好保證平均每10分鐘可以產(chǎn)生一個(gè)新的區(qū)塊.

當(dāng)有越來(lái)越多的礦工加入到"挖礦"的行列中后, 這個(gè)計(jì)算的挑戰(zhàn)性也越來(lái)越高. 好讓這個(gè)小彩票, 大約每 10 分鐘才能有一個(gè)人中獎(jiǎng). 很多新的加密貨幣有更短的區(qū)塊時(shí)間間隔.

比特幣體系中所有的比特幣都來(lái)自于生成新區(qū)塊的獎(jiǎng)勵(lì), 在一開(kāi)始，是每區(qū)塊50個(gè)比特幣. 還有一個(gè)叫做"Block Explorer"的網(wǎng)站你可以去看看, 上面能輕松地看到比特幣區(qū)塊鏈中的信息, 如果你看區(qū)塊鏈最初識(shí)的那幾個(gè)區(qū)塊, 它們除了獎(jiǎng)勵(lì)給礦工的50個(gè)比特幣之外并沒(méi)有其他交易.

但每過(guò)210000個(gè)區(qū)塊，差不多每4年，區(qū)塊獎(jiǎng)勵(lì)就會(huì)減半. 現(xiàn)在，每個(gè)區(qū)塊的獎(jiǎng)勵(lì)是12.5個(gè)比特幣, 也因?yàn)檫@個(gè)獎(jiǎng)勵(lì)隨著時(shí)間等比減少, 也就意味著最終可獲取的比特幣不會(huì)超過(guò)21000000. 但這并不是說(shuō)礦工最終賺不到錢(qián), 除了區(qū)塊獎(jiǎng)勵(lì)外，礦工還可以獲得交易費(fèi), 每當(dāng)你支付時(shí)，你可選擇一小筆交易費(fèi)一起支付, 這筆交易費(fèi)最終會(huì)給包含這筆記錄的區(qū)塊建立者, 你這么做能夠激勵(lì)礦工們繼續(xù)工作, 將包含你這筆交易信息的區(qū)塊廣播給網(wǎng)絡(luò)中的其他人.

在比特幣中，每個(gè)區(qū)塊包含約2400筆交易記錄, 很多批判家認(rèn)為這個(gè)限制過(guò)于嚴(yán)格, 與VISA比較，VISA每秒平均處理約1700筆交易, 而有能力每秒能夠處理多達(dá)24000筆交易. 相比而言比特幣較慢的交易速度使得它的交易費(fèi)用更高, 正是交易費(fèi)用決定了礦工哪些交易加入到新的區(qū)塊中.

除了以上這些加密貨幣的基礎(chǔ)知識(shí), 還有其他許多不同的加密貨幣的系統(tǒng)設(shè)計(jì)尚未涉及, 但我希望這個(gè)視頻能稱(chēng)為堅(jiān)實(shí)的求知欲基石, 感興趣的話, 可以擴(kuò)展閱讀, 繼續(xù)學(xué)習(xí). 正如我開(kāi)頭所說(shuō)，我做此視頻的初衷是因?yàn)樵S多的資金涌入加密貨幣中, 是好是壞我并不過(guò)多評(píng)價(jià), 但我認(rèn)為想要進(jìn)入這一領(lǐng)域的人, 至少了解這門(mén)技術(shù)的基礎(chǔ), 應(yīng)該是很有益的.

256加密有多安全

為了攻破一個(gè)安全系統(tǒng), 你必須得猜對(duì)一個(gè)256位的比特串. 第一次是在電子簽名的部分提的, 第二次是在密碼散列函數(shù)的部分提到的.

比如說(shuō)，假如你想找到一條信息讓它的SHA256 散列值(哈希值)等于某個(gè) 256位比特串的話, 沒(méi)有其他辦法，只能暴力猜測(cè), 并檢驗(yàn)結(jié)果. 這需要嘗試

22562256次.

這個(gè)數(shù)字比我們通常遇到的數(shù)都要大得多, 因此很難去體會(huì)它的規(guī)模. 不過(guò)我們不妨試一試,22562256也就是232232, 和它自己相乘 8 次

這樣分解的好處在于我們知道232232大約是 40億這樣一個(gè)數(shù)量.

我們起碼可以想象"小一點(diǎn)"這個(gè)數(shù)字吧, 嗯，再來(lái)就是去體會(huì) 40 億連續(xù)相乘 8 次是怎樣的概念？很多人知道，我們的電腦里的 GPU 可以飛速的進(jìn)行大量的并行計(jì)算. 因此要請(qǐng)你專(zhuān)門(mén)讓 GPU 反復(fù)計(jì)算密碼散列函數(shù). 一個(gè)性能很好的 GPU 每秒也許能算出接近 10 億個(gè)散列值.

假如你拿上一堆這樣的 GPU , 而讓你這臺(tái)超級(jí)電腦每秒能算 40 億個(gè)散列值, 那么就開(kāi)始的 40 億代表了你這臺(tái)超級(jí)電腦每秒算出的散列值的數(shù)目.

想象一下 40 億臺(tái)這樣滿載 GPU 的超級(jí)電腦, 跟 Google 對(duì)比下, 雖然谷歌沒(méi)有對(duì)外公布他們的服務(wù)器數(shù)量, 但是有估計(jì)說(shuō)大概有幾百萬(wàn)臺(tái). 現(xiàn)實(shí)中他們大部分服務(wù)器的算力都不如我們滿載 GPU 的電腦強(qiáng), 我們假設(shè)谷歌把上百萬(wàn)個(gè)服務(wù)器全換成這樣的超級(jí)電腦. 那么 40 億臺(tái)超級(jí)電腦大概是 1000 個(gè)這種打了雞血后的谷歌. 我們就把這個(gè)算力叫做 "千谷歌"吧.

我們?cè)偻铱? 全世界的人口大概有73億, 接下來(lái)我們假設(shè)一多半的人(40億臺(tái))都擁有自己的千谷歌,

然后想象, 40 億個(gè)這樣的地球, 作為對(duì)比，銀河系大約有 1000 到 4000 億顆恒星, 雖然我們并不確定，但估算大致就在這個(gè)范圍. 所以這相當(dāng)于銀河系的 1% 恒星, 并且每個(gè)地球上一半的人口都擁有自己的千谷歌.

接著想象, 40 億個(gè)這樣的銀河系, 我們把它叫做"億萬(wàn)星系超級(jí)計(jì)算機(jī)", 每秒能猜21602160次.

40 億秒, 大概是 126.8 年, 它的 40 億倍, 就是 5070 億年, 差不多是宇宙年齡的37倍. 所以就算你有( GPU 滿滿的超級(jí)計(jì)算機(jī)) * (地球上超過(guò)一般人都擁有千谷歌) * (行星云集) * (億萬(wàn)星系計(jì)算機(jī)) * (猜上 37 倍宇宙年齡的時(shí)間), 也只有 40 億分之一的可能性猜測(cè)到正確的數(shù)字.

密碼學(xué)原理

知道什么是公鑰密碼學(xué)的人可能已經(jīng)聽(tīng)說(shuō)過(guò)ECC、ECDH或是ECDSA。第一個(gè)術(shù)語(yǔ)是橢圓曲線密碼學(xué)（Elliptic Curve Cryptography） 的縮寫(xiě)，后兩個(gè)是基于它的算法名稱(chēng)。

如今，我們可以在TLS、PGP和SSH中見(jiàn)到橢圓曲線加密系統(tǒng)，這是現(xiàn)代網(wǎng)絡(luò)和IT世界所依賴(lài)的三種主要技術(shù)。比特幣和其他加密貨幣就是利用這種加密算法進(jìn)行加密的。

在ECC流行起來(lái)之前，幾乎所有的公鑰算法都是基于RSA、DSA和DH ———— 基于模運(yùn)算的可選加密系統(tǒng)。RSA及其友類(lèi)算法在當(dāng)前仍非常重要，經(jīng)常與ECC一并使用。不過(guò)，RSA及其友類(lèi)算法背后的原理很容易解釋?zhuān)蚨粡V泛理解，一些簡(jiǎn)單的實(shí)現(xiàn)也可以很容易編寫(xiě)出來(lái)；但ECC的實(shí)現(xiàn)基礎(chǔ)對(duì)于大多數(shù)人來(lái)說(shuō)仍很神秘。

通過(guò)一系列的博文，我打算用一個(gè)通俗的方式介紹橢圓曲線密碼學(xué)。我的目標(biāo)不是提供ECC完整和詳細(xì)的指導(dǎo)（網(wǎng)上有這方面的充足信息），而是簡(jiǎn)單概述“ECC是什么、為什么它被認(rèn)為是安全的”，避免把時(shí)間浪費(fèi)在長(zhǎng)篇的數(shù)學(xué)證明和惱人的實(shí)現(xiàn)細(xì)節(jié)上。我還將提供一些輔助示例以及可視化圖形工具和腳本給大家使用。

具體來(lái)說(shuō)，我將觸及以下主題：

1. 基于實(shí)數(shù)域的橢圓曲線和群公理（本文中涉及）

2. 基于有限域的橢圓曲線和離散對(duì)數(shù)問(wèn)題

3. 密鑰對(duì)的生成以及兩個(gè)ECC算法：ECDH和ECDSA

4. 破壞ECC安全性的算法，并與RSA作對(duì)比

為了能夠理解本文所述的內(nèi)容，你需要了解集（set)理論、幾何、模運(yùn)算等基本概念，并大致知道對(duì)稱(chēng)式和非對(duì)稱(chēng)式加密。此外，你需要清楚的知道什么是“易解”問(wèn)題，什么是“難解”問(wèn)題，以及它們?cè)诿艽a學(xué)中的角色。

準(zhǔn)備好了嗎？開(kāi)始！

橢圓曲線

首先，什么是橢圓曲線？ MathWorld 線上數(shù)學(xué)百科全書(shū)給出了一個(gè)極好并完整的定義。不過(guò)，針對(duì)我們的學(xué)習(xí)目的，橢圓曲線將簡(jiǎn)化為用下面這個(gè)等式所描述的點(diǎn)的集合：

其中， 4a3 + 27b2 ≠ 0 (這是為了排除奇曲線)。上面的等式稱(chēng)為橢圓曲線的魏爾斯特拉斯范式（ Weierstrass normal form）

不同的橢圓曲線的不同形狀 (b = 1, a 取值由 2 變化至 -3).

奇點(diǎn)類(lèi)型: 左側(cè), 帶一個(gè)尖角的曲線 (y2 = x3)。右側(cè), 帶一個(gè)自交叉的曲線 (y2 = x3 – 3x + 2). 這兩種都不是有效的橢圓曲線。

根據(jù)a和b的值，橢圓曲線在平面上可以呈現(xiàn)不同形狀。可以很容易看出并驗(yàn)證： 橢圓曲線是關(guān)于x-軸對(duì)稱(chēng)的。為了實(shí)現(xiàn)我們的目標(biāo)，我們還需要把一個(gè)無(wú)窮遠(yuǎn)點(diǎn)（亦稱(chēng)之為理想點(diǎn)) 視為橢圓曲線的一部分。從現(xiàn)在開(kāi)始，我們將用符號(hào)0（零）來(lái)代表無(wú)窮遠(yuǎn)點(diǎn)。

如果我們想顯式地將無(wú)窮遠(yuǎn)點(diǎn)納入考慮，我們可以按如下的方式細(xì)化橢圓曲線的定義：

群

數(shù)學(xué)中的“群”是一個(gè)由我們定義了一種二元運(yùn)算的集合，二元運(yùn)算我們稱(chēng)之為“加法”，并用符號(hào)“+”來(lái)表示。為了讓一個(gè)集合G成為群，必須定義加法運(yùn)算并使之具有以下四個(gè)特性：

1. 封閉性：如果a和b是集合G中的元素，那么（a + b)也是集合G中的元素。

2. 結(jié)合律：(a + b) + c = a + (b + c);

3. 存在單位元0，使得a + 0 = 0 + a =a;

4. 每個(gè)元素都有逆元，即：對(duì)于任意a，存在b，使得a + b = 0.

如果我們?cè)黾拥?個(gè)條件：

5. 交換律： a + b = b + a

那么，稱(chēng)這個(gè)群為阿貝爾（abelian)群。

配上通常概念的加法時(shí)，整數(shù)的集合Z就是一個(gè)群（同時(shí)還是個(gè)阿貝爾群）。而自然數(shù)的集合（N）就不是群，因?yàn)樗粷M足第4個(gè)特性。

“群”很有用，因?yàn)橐坏┪覀冏C明它具備上述4個(gè)特性，那么我們就可以自由地獲取到一些其他特性。比如：?jiǎn)挝辉俏ㄒ坏模淮送猓嬖彩俏ㄒ坏模矗簩?duì)于每一個(gè)a，存在唯一的一個(gè)b，使得a + b = 0 （我們可以將b寫(xiě)成-a）。后面我們會(huì)發(fā)現(xiàn)，群的這些特性以及其他存在的事實(shí)，或者直接或者間接，對(duì)于我們來(lái)說(shuō)非常重要。

橢圓曲線的群公理

我們可以定義一個(gè)基于橢圓曲線的群。如下：

? 群中的元素是一條橢圓曲線上的點(diǎn);

? 單位元為無(wú)窮遠(yuǎn)點(diǎn)O;

? 點(diǎn)P的逆元是其關(guān)于x-軸的對(duì)稱(chēng)點(diǎn);

? 加法，滿足以下規(guī)則: 對(duì)于3個(gè)處在同一直線上的非零點(diǎn) P, Q 和 R, 它們的和 P + Q + R = 0.

同一直線上的三個(gè)點(diǎn)之和等于0.

注意一下最后一個(gè)規(guī)則，我們需要的只是三個(gè)點(diǎn)同線，與點(diǎn)的次序無(wú)關(guān)。這意味著，如果P、Q和R同線，那么P + (Q + R) = Q + (P + R) = R + (P + Q) = ? ? ? = 0. 這樣，我們直觀地證明了我們的“+”運(yùn)算既滿足結(jié)合律也滿足交換律：我們創(chuàng)建了一個(gè)阿貝爾群。

到目前還很不錯(cuò)。但我們?nèi)绾螌?shí)際計(jì)算任意兩點(diǎn)之和呢？

幾何加法

得益于我們使用的是一個(gè)阿貝爾群，我們可以把 P + Q + R = 0 寫(xiě)成P + Q = –R。方程的這一形式，讓我們可以推導(dǎo)出計(jì)算兩點(diǎn)P和Q之和的幾何方法：畫(huà)一條過(guò)P和Q點(diǎn)的直線，這條直線與曲線相交得到第3個(gè)點(diǎn)R（這一事實(shí)意味著P、Q、R必然共線）。如果我們獲取了該點(diǎn)的逆元-R，那么我們就得到了P + Q的結(jié)果。

過(guò)P和Q畫(huà)一條直線。該直線與曲線相交與第3點(diǎn)R。與之對(duì)稱(chēng)的點(diǎn)-R即為P+Q 的結(jié)果

這種幾何方法可以成立，但還需一些改進(jìn)。特別是，我們需要回答以下幾個(gè)問(wèn)題：

? 當(dāng)P = 0或Q = 0時(shí)怎么辦? 顯然，我們無(wú)法畫(huà)任何直線（0點(diǎn)不在xy-平面上）。不過(guò)，由于我們定義了0點(diǎn)為單位元，所以，對(duì)于任意P和任意Q，都有：P + 0 = P ， 0 + Q = Q

? 當(dāng)P= –Q時(shí)怎么辦? 這種情況下，通過(guò)兩點(diǎn)的直線是一條垂線，與曲線不會(huì)有第三個(gè)交點(diǎn)。不過(guò)，由于P是Q的逆元，那么由逆元的定義可知P + Q = P + (-P) = 0 .

? 當(dāng)P= Q時(shí)怎么辦? 這種情況下，經(jīng)過(guò)該點(diǎn)的直線有無(wú)數(shù)條。事情開(kāi)始有點(diǎn)復(fù)雜了。不過(guò)，先想像一個(gè)點(diǎn) Q’ ≠ P。如果我們令Q’ 向P逼近，越來(lái)越靠近P會(huì)怎么樣？

隨著兩個(gè)點(diǎn)越來(lái)越接近，過(guò)這兩點(diǎn)的直線最終變成了曲線的切線

隨著Q’ 趨向P, 過(guò)P和Q’ 的直線最終成為曲線的切線。看到這一點(diǎn)，我們可以定義 P + P = –R, 其中R是過(guò)P點(diǎn)的切線與曲線的交點(diǎn)。

? 當(dāng)P ≠ Q，但找不到第三個(gè)點(diǎn)R時(shí)怎么辦? 這種情況和上面那個(gè)非常類(lèi)似。實(shí)際上，這是因?yàn)檫^(guò)P和Q的直線與曲線相切。

如果直線與曲線只有兩個(gè)交點(diǎn)，那么該直線為曲線的切線。可以很容易地看出，兩點(diǎn)相加的結(jié)果是其中一點(diǎn)的對(duì)稱(chēng)點(diǎn)

? 假設(shè)P是切點(diǎn)，在上一情況中，我們已經(jīng)得出P + P = –Q. 等式現(xiàn)在變?yōu)?P + Q = –P。 如果Q 是切點(diǎn)，正確的等式應(yīng)為 P + Q = –Q.

現(xiàn)在，用幾何方法可以完全覆蓋所有情況了。用一支鉛筆和一把尺，我們可以做任意橢圓曲線上所有點(diǎn)的加法運(yùn)算。如果你想試試，請(qǐng)到 HTML5/JavaScript visual tool 看一下，這是我建的一個(gè)工具，用來(lái)計(jì)算橢圓曲線的加法!

代數(shù)加法

如果我們想把點(diǎn)的加法運(yùn)算計(jì)算機(jī)來(lái)完成，那么需要將幾何方法轉(zhuǎn)化為代數(shù)方法。將上面描述的規(guī)則轉(zhuǎn)換為一組公式看似簡(jiǎn)單，實(shí)際上是非常繁瑣的，因?yàn)樾枰蠼馊畏匠獭Ｒ虼耍@里我只通報(bào)結(jié)果。

首先，先拋開(kāi)最?lèi)廊说臉O端情況。我們已經(jīng)知道P + (-P) = 0, 還知道P + 0 = 0 + P = P。所以，在我們的公式中 ，我們將避免這兩種情況，只考慮兩個(gè)非零、非對(duì)稱(chēng)點(diǎn) P = (xP, yP) 和Q = (xQ, yQ).

如果 P 和 Q 不相同， (xP ≠ xQ), 過(guò)這兩點(diǎn)的直線斜率為:

該直線與橢圓曲線交于第三點(diǎn) R = (xR, yR):

或是, 等價(jià)形式:

因此，(xP, yP) + (xQ, yQ) = (xR, –yR) (注意正負(fù)號(hào)，記住P + Q = –R).

如果我們想檢查這一結(jié)果是否正確，我們將不得不檢查R是否在曲線上，同時(shí)P、Q、Q是共線。檢查點(diǎn)是否共線輕而易舉，但檢查R是否在曲線上就不容易了，因?yàn)樾枰蠼馊畏匠蹋@可不是什么好玩的事兒。

不過(guò)，我們可以用一個(gè)例子來(lái)試一下：根據(jù) 可視化工具的計(jì)算， 當(dāng) P = (1, 2) 、Q = (3, 4) ，橢圓曲線 y2 = x3 – 7x + 10, 兩點(diǎn)之和 P + Q = –R = (-3, 2). 讓我們看一下與我們的公式是否一致:

好的，正確!

注意上面的公式即使在其中一個(gè)點(diǎn)P或Q是切點(diǎn)的情況下也成立。讓我們?cè)囈幌翽 = (-1, 4) 、 Q = (1, 2).

我們計(jì)算出 P + Q = (1, -2), 與使用 可視化工具計(jì)算出的結(jié)果相同。

P = Q 的情況需要做點(diǎn)不同的處理：方程中 xR 和 yR 相同, 由于 xP = xQ, 我們必須使用不同的公式來(lái)計(jì)算斜率：

注意，我們可以料到，m的表達(dá)式實(shí)際是下面這個(gè)函數(shù)的一階導(dǎo)數(shù):

為了證明結(jié)果的有效性，只要檢查R是否在曲線上，以及P和R在曲線上只有兩個(gè)交點(diǎn)就足夠了。但同樣，我們不去證明這一事實(shí)，而是試算一個(gè)例子: P = Q = (1, 2).

公式計(jì)算出 P + P = –R = (-1, -4).正確!

盡管推導(dǎo)過(guò)程真的是極其繁瑣，不過(guò)最后的公式還是很簡(jiǎn)潔。這要感謝魏爾斯特拉斯范式：要是沒(méi)有這一范式，最后的公式會(huì)真的又長(zhǎng)又復(fù)雜。

標(biāo)量乘法

在加法之外，我們還可以定義另一種運(yùn)算：標(biāo)量乘法，即：

nP，其中n為自然數(shù)。我為標(biāo)量乘法也寫(xiě)了個(gè) 可視化工具 ，如果你想試算時(shí)可以使用。

用這種形式表示時(shí)，計(jì)算nP似乎需要n次加法運(yùn)算。如果n有k個(gè)二進(jìn)制位，那么算法的時(shí)間復(fù)雜度將為O（2^k)，這真不是很好。不過(guò)存在一些更快的算法。

其中一種是“加倍（double)與相加（add)”算法。

計(jì)算的原理可以用一個(gè)例子來(lái)更好地解釋。取n = 151。它的二進(jìn)制表示形式為100101112 。這一二進(jìn)制表示形式可以轉(zhuǎn)換為一系列2的冪之和。

(取n的 每個(gè)二進(jìn)制位上的數(shù)字，并用它乘以一個(gè)2的冪.)

用這種方法，我們可以將n這樣寫(xiě):

“加倍（double)與相加（add)”算法需要這樣做:

? 取 P.

? 加倍，得到2P.

? 2P與P相加(為了得到 21P + 20P).

? 加倍 2P，得到22P.

? 與前一結(jié)果相加 (得到 22P + 21P + 20P).

? 加倍 22P，得到23P.

? 對(duì)23P不做任何操作.

? 加倍23P，得到24P.

? 與前一結(jié)果相加 (得到 24P + 22P + 21P + 20P).

? …

最后，我們可以計(jì)算151 ? P ，只需7次“加倍”運(yùn)算和4次“相加”運(yùn)算。

如果還不夠清楚，這里有一個(gè)實(shí)現(xiàn)該算法的python代碼段：

如果“加倍”和“相加”操作復(fù)雜度均為O(1),那么 該算法的時(shí)間復(fù)雜度為O(log n) (或是O(k)，如果我們考慮的是二進(jìn)制位的長(zhǎng)度），這相當(dāng)不錯(cuò)。比最初O(n)的算法肯定要好得多。

對(duì)數(shù)

給定n和P, 我們現(xiàn)在至少有一個(gè)多項(xiàng)式時(shí)間算法來(lái)計(jì)算Q = nP。不過(guò)，逆運(yùn)算需要計(jì)算多少輪呢？如果已知Q和P，我們想求解n會(huì)怎么樣？這一問(wèn)題被稱(chēng)為對(duì)數(shù)問(wèn)題。我們稱(chēng)之為“對(duì)數(shù)”而不是“除法”是為了與其他加密系統(tǒng)（在術(shù)語(yǔ)上）保持統(tǒng)一（那些系統(tǒng)中，不稱(chēng)“乘法”，而稱(chēng)“冪”）。

我不知道任何關(guān)于對(duì)數(shù)問(wèn)題的“易解”算法，不過(guò)，通過(guò)擺弄乘法 ，很容易發(fā)現(xiàn)一些模式。例如，對(duì)于曲線 y2 = x3 – 3x + 1和點(diǎn) P = (0, 1). 我們可以立即驗(yàn)證出, 如果n為奇數(shù)，nP在曲線的左半面，如果n為偶數(shù)，nP在曲線的右半面。如果我們嘗試更多次，我們或許可以找出更多的模式，最終可以讓我們寫(xiě)出一個(gè)算法來(lái)高效計(jì)算那條曲線的對(duì)數(shù)問(wèn)題。

不過(guò)，對(duì)數(shù)問(wèn)題有一個(gè)變體：離散對(duì)數(shù)問(wèn)題。在下一篇博文中，我們將看到，當(dāng)我們對(duì)橢圓曲線的域進(jìn)行縮減后，標(biāo)量乘法仍舊”易解“，而離散對(duì)數(shù)問(wèn)題成為了”難解”問(wèn)題。這種雙重性是橢圓曲線密碼學(xué)的關(guān)鍵基石。