有一種有效的學(xué)習(xí)方法叫費(fèi)曼學(xué)習(xí)法。它的做法是把你學(xué)到的東西系統(tǒng)性的講述出來(lái)，如果別人通過(guò)你的描述也能理解其中內(nèi)容，這說(shuō)明你對(duì)所學(xué)知識(shí)有了一定程度的掌握。目前我正在系統(tǒng)性的研究區(qū)塊鏈技術(shù)，因此想借助費(fèi)曼學(xué)習(xí)法，把我掌握的信息系統(tǒng)性的輸出，一來(lái)能幫助自己更好的理解消化知識(shí)，另一方面也希望能幫助對(duì)這方面有興趣的同學(xué)。當(dāng)然區(qū)塊鏈的技術(shù)信息汗牛充棟，相比與其他資料，我覺(jué)得我的優(yōu)勢(shì)在于能體會(huì)初學(xué)者的難處，因?yàn)槲易约壕褪浅鯇W(xué)者。

在我看來(lái)區(qū)塊鏈技術(shù)的兩大基礎(chǔ)在于加解密和分布式。因此系統(tǒng)性的掌握區(qū)塊鏈就需要系統(tǒng)性的掌握這兩塊。首先我們從加解密這塊入手，其中這塊中最基礎(chǔ)的就是橢圓曲線。

從上面圖形可以看到，橢圓曲線其實(shí)就是一個(gè)最高指數(shù)為3的多項(xiàng)式，這里需要注意的是多項(xiàng)式的計(jì)算要基于除法求余的基礎(chǔ)，也就是它的計(jì)算方式如下：

y ^ 2 mod p = x^3 + a*x + b mod p

對(duì)于區(qū)塊鏈而言他需要專(zhuān)門(mén)指定公式中a, b ， p 這個(gè)幾個(gè)參數(shù)。因此它也有一個(gè)專(zhuān)有名字叫secp256k1，我們看看幾個(gè)參數(shù)的具體數(shù)值：

p = 2 ^ 256 - 2 ^32 - 2 ^ 9 - 2 ^ 8 - 2 ^ 7 - 2 ^ 6 - 2 ^ 4 - 1
a = 0
b = 7

在運(yùn)用中，x只取整數(shù)，我們使用代碼看看橢圓曲線的例子;

def is_on_blockchain_curve(point):
    '''
    p = 2 ^ 256 - 2 ^32 - 2 ^ 9 - 2 ^ 8 - 2 ^ 7 - 2 ^ 6 - 2 ^ 4 - 1
    a = 0
    b = 7
    該函數(shù)判斷給定的點(diǎn)是否在橢圓曲線上, 其中point包含兩個(gè)數(shù)值(x,y)
    '''
    p = 2 ** 256 - 2 ** 32 - 2 ** 9 - 2 ** 8 - 2 ** 7 - 2 ** 6 - 2 ** 4 - 1
    return (point[1] ** 2) % p == (point[0] ** 3 + 7) % p

p = (55066263022277343669578718895168534326250603453777594175500187360389116729240,
     32670510020758816978083085130507043184471273380659243275938904335757337482424)

print(f"is point p on curve: {is_on_blockchain_curve(p)}")

上面代碼構(gòu)造了橢圓曲線，然后給定一個(gè)點(diǎn)p,并判斷這個(gè)點(diǎn)是否在曲線上，代碼運(yùn)行后返回結(jié)果為:

is point p on curve: True

也就是給定的P點(diǎn)確實(shí)在曲線上，從這里可以看出，橢圓曲線在運(yùn)用時(shí)，我們需要處理數(shù)值相當(dāng)大的點(diǎn)。

在數(shù)學(xué)上橢圓曲線定義了一種運(yùn)算叫"加法“，千萬(wàn)不要將其與我們普通的四則運(yùn)算等同起來(lái)，我們看看橢圓曲線的"加法"是如何運(yùn)作的。在橢圓曲線上取兩點(diǎn)，如果這兩點(diǎn)不是同一點(diǎn)，那么這兩點(diǎn)相加的運(yùn)算如下圖所示:

P, Q是曲線上兩點(diǎn)，P + Q的結(jié)果就是，先將P,Q兩點(diǎn)連線，這條線會(huì)跟曲線交在第三點(diǎn)也就是上方的R點(diǎn)，然后找這點(diǎn)相對(duì)x軸的對(duì)稱(chēng)點(diǎn)，那點(diǎn)的左邊就是P+Q的結(jié)果。如果P,Q指的是同一點(diǎn)，那么就在這點(diǎn)上做曲線的切線，這條切線會(huì)跟曲線交于第二點(diǎn)，把交點(diǎn)根據(jù)x軸進(jìn)行對(duì)稱(chēng)操作，所得的點(diǎn)就是加法的結(jié)果，如下圖所示：

對(duì)于橢圓曲線上針對(duì)某個(gè)點(diǎn)做乘法，實(shí)際上就是將加法重復(fù)相應(yīng)的次數(shù)。橢圓曲線在區(qū)塊鏈上的一大應(yīng)用就是創(chuàng)建個(gè)人錢(qián)包的地址，這個(gè)地址類(lèi)似于TCP/IP協(xié)議上的IP地址，通過(guò)這個(gè)地址，別人就可以跟你交換數(shù)據(jù)，例如將比特幣轉(zhuǎn)移給你。要想創(chuàng)建個(gè)人錢(qián)包地址，我們需要先從橢圓曲線創(chuàng)建一個(gè)叫"公鑰”的數(shù)據(jù)，首先我們?cè)谇€上取專(zhuān)門(mén)的一點(diǎn)用G表示，然后創(chuàng)建一個(gè)足夠大的隨機(jī)數(shù)k,然后計(jì)算這兩個(gè)數(shù)相乘的結(jié)果 K = k * G , 注意這里G是橢圓曲線上的一個(gè)點(diǎn)，k是一個(gè)很大的整數(shù)，乘法操作就是把上面描述的加法重復(fù)k次，在這里k就是區(qū)塊鏈用戶的私鑰，K就是公鑰，在數(shù)學(xué)上可以證明，通過(guò)K是不能計(jì)算出k的，因此我們可以將K發(fā)布到網(wǎng)絡(luò)上作為個(gè)人的地址。

我們看4 * G的計(jì)算過(guò)程:

首先我們計(jì)算2*G,那就是在G點(diǎn)做切線，它跟曲線的另一個(gè)交點(diǎn)記作-2G，然后根據(jù)x軸做對(duì)稱(chēng)得到點(diǎn)2G,然后對(duì)點(diǎn)2G做切線，它與曲線相交于點(diǎn)-4G,然后再根據(jù)x軸做對(duì)稱(chēng)得到最終結(jié)果4G，在上圖中G點(diǎn)是一個(gè)事先指定好在橢圓曲線上的一個(gè)點(diǎn)，它的坐標(biāo)為(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)，可以看到這是一個(gè)相當(dāng)巨大的天文數(shù)字，下面我們從數(shù)學(xué)原理并結(jié)合代碼的方式來(lái)深入認(rèn)識(shí)一下橢圓曲線的原理。

幾乎所有加解密的原理都基于抽象代數(shù)。特別是在抽象代數(shù)中的有限域這個(gè)概念。所謂有限域它是一個(gè)包含有限個(gè)元素的集合，同時(shí)它支持兩種運(yùn)算，分別用“+”和“*”，來(lái)表示，這兩種運(yùn)算具有如下性質(zhì)：
1，如果a, b 是集合中兩個(gè)元素，那么a + b 和 a * b 所的的結(jié)果也屬于該集合，這個(gè)性質(zhì)叫閉合性。
2，集合中存在一個(gè)特殊元素用符號(hào)0表示，它滿足0 + a = a
3，集合中存在一個(gè)特殊元素，用1表示，它滿足 1 * a = a
4, 對(duì)集合中任何一個(gè)元素a, 集合還存在另一個(gè)對(duì)應(yīng)元素記作-a, 它滿足a + (-a) = 0
5, 對(duì)集合中任何一個(gè)元素a, 集合還存在另一個(gè)對(duì)應(yīng)元素記作a^(-1)，它滿足 a * a^(-1) = 1

這里我們需要注意，千萬(wàn)不要把操作+和* 跟四則運(yùn)算中的加法和乘法等同起來(lái)，由于整數(shù)或?qū)崝?shù)中對(duì)應(yīng)的加法和乘法都滿足上面性質(zhì)，因此我們?cè)谒季S上會(huì)不自覺(jué)把上面定義的兩種操作等同起來(lái)，因此一定要注意不要等同，不然它會(huì)對(duì)我們的理解造成很大的障礙。

有幾個(gè)要點(diǎn)需要注意，首先集合里面元素的個(gè)數(shù)必須是有限的，假設(shè)集合中包含元素的個(gè)數(shù)為p,那么我們把p稱(chēng)作該集合的order。對(duì)于第一點(diǎn)要求，我們必須確保+和*兩種操作是閉合的，假設(shè)集合元素為{1,2,3}，這兩種操作對(duì)應(yīng)四則運(yùn)算的加法和乘法，那么這兩種操作就不能實(shí)現(xiàn)閉合，因?yàn)?+3等于4，而4不在集合中。但是對(duì)于集合{1, 0, -1},那么四則元素的加法和乘法對(duì)于這個(gè)集合的元素就是閉合的。所以我們不要把普通的加法和乘法跟上面的定義等同起來(lái)。同時(shí)需要注意的是，對(duì)有限域而言，它元素的個(gè)數(shù)需要是素?cái)?shù)。為了更好的理解有限域，我們看看如何使用python來(lái)實(shí)現(xiàn)。

class LimitFieldElement: #實(shí)現(xiàn)有限域的元素
    def __init__(self, num, order):
        """
        order 表示集合元素的個(gè)數(shù)，它必須是一個(gè)素?cái)?shù)，不然有限域的性質(zhì)不能滿足
        num 對(duì)應(yīng)元素的數(shù)值
        """

        if order <= num < 0:
            err = f"元素 {num} 數(shù)值必須在0到 {order - 1} 之間"
            raise ValueError(err)
        self.order = order
        self.num = num

    def __repr__(self):
        return f"LimitFieldElement_{self.order}({self.num})"

    def __eq__(self, other):
        if other is None:
            return False
        return self.num == other.num and self.order == other.order
        
    def __ne__(self, other):
        if other is None:
            return True

        return self.num != other.num or self.order != other.order
       

上面代碼首先定義有限域元素，同時(shí)規(guī)定元素對(duì)應(yīng)的值必須在0到集合元素個(gè)數(shù)之間，同時(shí)要注意，集合元素的個(gè)數(shù)需要是素?cái)?shù)，不然它對(duì)應(yīng)的性質(zhì)就會(huì)有問(wèn)題。注意到前面描述有限域中元素有兩種運(yùn)算，分別是"+“, 和”*"，這兩種運(yùn)算的特性是具有閉合性，也就是說(shuō)兩個(gè)元素執(zhí)行這兩種運(yùn)算后，所得結(jié)果依然屬于該集合，前面我們也看到，我們熟悉的四則元素加法和乘法不一定能滿足閉合性，但是我們稍微對(duì)這兩種運(yùn)算做一個(gè)簡(jiǎn)單的“加工”，就能滿足，這個(gè)“加工”就是基于求余的加法和乘法，具體來(lái)說(shuō)就是對(duì)兩個(gè)元素進(jìn)行四則運(yùn)算的加法和減法后，再把所得結(jié)果根據(jù)集合元素的個(gè)數(shù)進(jìn)行求余。

舉個(gè)具體例子，對(duì)應(yīng)集合{0, 1, 2, 3, 4} ，3“+”5的過(guò)程為先計(jì)算3加上5的結(jié)果，也就是8，然后對(duì)對(duì)集合元素個(gè)數(shù)做求余，由于集合元素有5個(gè)，因此3 = 8 % 5 , 于是3 “+” 5的結(jié)果就是3.雖然在集合中所有元素都是正數(shù)，但是我們可以在運(yùn)算”+“的基礎(chǔ)上定義負(fù)數(shù)，如果集合中兩個(gè)元素a,b，執(zhí)行操作a “+” b 后結(jié)果為0， 那么我們就規(guī)定 b 可以記作-a。

這里有點(diǎn)違法我們的直覺(jué)，因?yàn)楦鶕?jù)上面的定義對(duì)于元素2, 那么-2 其實(shí)就是元素3， 因?yàn)? “+” 3 = 0，初次接觸到有限域運(yùn)算的同學(xué)可能會(huì)比較迷糊。下面我們把操作“+”實(shí)現(xiàn)在有限域的元素上，對(duì)應(yīng)代碼如下：

    def __add__(self, other):
        """
        有限域元素的"+"操作，它是在普通加法操作的基礎(chǔ)上，將結(jié)果對(duì)集合中元素個(gè)數(shù)求余
        """
        if self.order != other.order:
            raise TypeError("不能對(duì)兩個(gè)不同有限域集合的元素執(zhí)行+操作")
        #先做普通加法，然后在結(jié)果基礎(chǔ)上相對(duì)于集合元素的個(gè)數(shù)做求余運(yùn)算
        num = (self.num + other.num) % self.order
        """
        這里使用__class__而不是LimitFieldElemet是為了后面實(shí)現(xiàn)類(lèi)的繼承考慮，
        后面我們實(shí)現(xiàn)的對(duì)象需要繼承與這個(gè)類(lèi)
        """
        return self.__class__(num, self.order)

實(shí)現(xiàn)上面的方法后，下面的代碼結(jié)果為T(mén)rue:

a = LimitFieldElement(7, 13)
b = LimitFieldElement(12, 13)
c = LimitFieldElement(6, 13)
print(a + b == c)

完成了"+“操作下面我們看看”*“操作，跟”+“操作一樣，”*“操作就是先將兩個(gè)元素進(jìn)行普通乘法操作，然后將結(jié)果針對(duì)集合的元素個(gè)數(shù)執(zhí)行求余操作，例如對(duì)于集合{0, 1, 2, 3, 4}, 對(duì)于3 “*” 4, 我們先計(jì)算3*4 = 12，然后對(duì)集合元素個(gè)數(shù)求余，也就是12 % 5 = 2, 于是 3 “*” 4 = 2，在”*“操作的基礎(chǔ)上我們可以定義倒數(shù)這個(gè)概念，對(duì)于元素a,b，如果a “*” b = 1，那么我們就規(guī)定b 可以記作1/a, 或者a 可以記作1/b。在”*"操作的基礎(chǔ)上，我們還可以定義指數(shù)操作，對(duì)于集合中的元素a, a ^ 3對(duì)應(yīng)的是a “*” a “*” a,我們看看對(duì)應(yīng)操作的代碼實(shí)現(xiàn)，相關(guān)代碼如下:

 def __mul__(self, other):
        """
        有限域元素進(jìn)行"*"操作時(shí)，先執(zhí)行普通的乘法操作，然后將結(jié)果針對(duì)集合元素的個(gè)數(shù)進(jìn)行求余
        """
        if self.order != other.order:
            raise TypeError("能對(duì)兩個(gè)不同有限域集合的元素執(zhí)行*操作")
        
        num = (self.num * other.num) % self.order
        return self.__class__(num, self.order)
    
    def __pow__(self, power, modulo=None):
        """
        指數(shù)操作是先執(zhí)行普通四則運(yùn)算下的指數(shù)操作，再將所得結(jié)果針對(duì)集合元素個(gè)數(shù)求余
        """
        num = (self.num ** power) % self.order
        return self.__class__(num, self.order)

完成上面兩個(gè)函數(shù)后，如下代碼在執(zhí)行時(shí)返回結(jié)果都是True:

a = LimitFieldElement(3, 13)
b = LimitFieldElement(12, 13)
c = LimitFieldElement(10, 13)
print(a * b == c)

a = LimitFieldElement(3, 13)
b = LimitFieldElement(1, 13)
print(a ** 3 == b)

相對(duì)于“+”的逆運(yùn)算我們定義為“-”，它的運(yùn)算比較簡(jiǎn)單，對(duì)于兩個(gè)集合中的元素a,b，計(jì)算a"-“b，我們先用四則運(yùn)算中的減法獲得其結(jié)果，然后再將結(jié)果對(duì)應(yīng)到集合中的元素，例如集合{0, 1, 2 ,3 ,4}，a = 1, b = 3, 那么a “-” b就先對(duì)其進(jìn)行正常的減法運(yùn)算，然后將結(jié)果針對(duì)元素個(gè)數(shù)求余，因此 1 “-” 3 就先計(jì)算 1 - 3 = -2， 然后再對(duì)元素個(gè)數(shù)也就是5求余，-2 % 5 = 3，也就是1 “-” 3 = 3，如此看起來(lái)是有點(diǎn)反直覺(jué)。下面我們看看”*"操作下，所定義除法操作的實(shí)現(xiàn)，這里我們就需要一點(diǎn)數(shù)學(xué)推導(dǎo)了，以下將是一個(gè)理解難點(diǎn)。

對(duì)于操作“/"而言，我們不能像前面那樣，先做普通的除法然后再將結(jié)果針對(duì)集合元素個(gè)數(shù)求余。這里我們需要使用一個(gè)名為費(fèi)馬小定理，它的內(nèi)容如下：

對(duì)任一素?cái)?shù)p，以及任意正整數(shù)n，n % p != 0，那么有：n^(p-1) % p = 1
(這里的運(yùn)算對(duì)應(yīng)普通的四則運(yùn)算)

這個(gè)定理有很多證明方法，一種簡(jiǎn)單的做法是，如果p是素?cái)?shù)，然后給定任意一個(gè)整數(shù)n > 0, 我們有{1, …, p - 1} 等同于({n% p, 2n%p, … (p-1)n%p}，需要注意的是，這里的等同是指兩個(gè)集合包含相同的元素，而不是指兩個(gè)集合的元素一一對(duì)應(yīng)。我們簡(jiǎn)單研究一下這個(gè)結(jié)論，由于在第二個(gè)集合中，每個(gè)元素都對(duì)應(yīng)形式( k * n) % p, 1 <= k <= p-1,由于對(duì)p求余，因此第二個(gè)集合最多包含p - 1個(gè)元素，而且元素值不超過(guò)p，如果第二個(gè)集合中沒(méi)有重復(fù)元素，那么集合就包含p-1元素，由此兩個(gè)集合就包含相同元素，于是兩個(gè)集合等價(jià)。

假設(shè)第二個(gè)集合包含重復(fù)元素，那意味著存在1 <= t, k <= p-1, t !=k, 但是有 (t*n) % p = (k * n) % p，不失一般性，假設(shè)t > k， 那么有 [(t * n) - (k * n)] % p = 0，合并一下就有[(t - k) * n] % p = 0，由于我們?cè)诙ɡ碚f(shuō)明中已經(jīng)有 n % p != 0,因此這個(gè)等式要成立就必須有(t-k) % p = 0, 但是我們已經(jīng)知道 1 <= t < k < p - 1, 因此t - k < p, 由此(t - k) % p不能等于0，有就是說(shuō)第二個(gè)集合中沒(méi)有重復(fù)元素，于是兩個(gè)集合包含相同元素。

于是我們就有 [1 * 2 * … * (p-1)] % p = [ (n%p) * (2n) % p * … * (p-1)*n]，簡(jiǎn)化一下兩邊就有(p-1)! % n = (p-1)!*(n^(p-1)) % n, 兩邊消掉(p-1)!%n就有 1 = n ^ (p-1) % n。

由于要計(jì)算 a “” b， 我們只要找到另一個(gè)元素c, 如果它滿足 c “*” b = 1, 那么 a “” b 就轉(zhuǎn)換為a “*” c，這時(shí)候費(fèi)馬小定理就能發(fā)揮作用，因?yàn)橛衎^(p-1) % p = 1, 由此我們得出c = [b ^ (p-2)] % p，由于我們已經(jīng)知道如何做指數(shù)運(yùn)算，因此就可以計(jì)算出c的值，由此就能計(jì)算 a “” b。

下面我們看看運(yùn)算""的實(shí)現(xiàn)。在前面實(shí)現(xiàn)的函數(shù)__pow__中，我們其實(shí)可以使用python自帶的pow函數(shù)來(lái)實(shí)現(xiàn)，這個(gè)函數(shù)不但能實(shí)現(xiàn)指數(shù)運(yùn)算，而且還能實(shí)現(xiàn)基于求余的指數(shù)運(yùn)算，它第三個(gè)參數(shù)就可以指定要求余的數(shù)值p，但是有個(gè)問(wèn)題在于它不能接受負(fù)數(shù)，如果第二個(gè)參數(shù)是負(fù)數(shù)他就會(huì)拋出異常。因此我們不能執(zhí)行pow(3, -5, 17)，但是由于有費(fèi)馬小定理，a ^ (p-1) % p = 1, 于是 a ^ (-5) % p = a ^ (-5) %p * a^(p-1) % p = a ^ (p-6) % p,于是我們就有pow(3, -5 , 17) = pow(3, 17-6 , 17),因此我們可以將我們前面對(duì)__pow__的實(shí)現(xiàn)優(yōu)化如下：

    def __pow__(self, power, modulo=None):
        """
        指數(shù)操作是先執(zhí)行普通四則運(yùn)算下的指數(shù)操作，再將所得結(jié)果針對(duì)集合元素個(gè)數(shù)求余
        """
        while power < 0:
            power += self.order
        num = pow(self.num, power, self.order)
        return self.__class__(num, self.order)

最后我們基于上面的代碼來(lái)實(shí)現(xiàn)"/"操作：

    def __truediv__(self, other):
        if self.order != other.order:
            raise TypeError("不能對(duì)兩個(gè)不同有限域集合的元素執(zhí)行*操作")
        #通過(guò)費(fèi)馬小定理找到除數(shù)的對(duì)應(yīng)元素
        negative = other ** (self.order - 2)
        num = (self.num * negative.num) % self.order
        return self.__class__(num, self.order)

有了"/"運(yùn)算后，下面的代碼運(yùn)行后輸出結(jié)果為T(mén)rue:

a = LimitFieldElement(3, 13)
#由于(7 * 2) % 13 = 1，因此元素3 "/" 7 等價(jià)余 3 "*" 2, 因此 3 "/" 7 = 3 "*" 2 = 6
b = LimitFieldElement(7, 13)
c = LimitFieldElement(6, 13)

以上的內(nèi)容就是區(qū)塊鏈技術(shù)中對(duì)應(yīng)的有限域原理以及實(shí)現(xiàn)，完整代碼的下載地址：https://github.com/wycl16514/blockchain_finit_field.git，下一節(jié)我們看看橢圓曲線是如何在有限域的基礎(chǔ)上實(shí)現(xiàn)數(shù)據(jù)加密的，更多內(nèi)容請(qǐng)?jiān)赽站搜索"Coding迪斯尼"。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-491207.html

到了這里，關(guān)于區(qū)塊鏈的系統(tǒng)探索之路：橢圓曲線之有限域的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！