三分鐘帶你了解比特幣的數(shù)學(xué)原理!
2017年已然逝去,過(guò)去的一年人類對(duì)于科技再度狂熱,但是狂熱所引發(fā)的思潮卻指向了截然不同的方向。
一個(gè)爆炸性的突破是引力波被實(shí)驗(yàn)證實(shí),從而驗(yàn)證了愛(ài)因斯坦廣義相對(duì)論的預(yù)言。數(shù)十年前,韋伯的引力波實(shí)驗(yàn)就已經(jīng)家喻戶曉,但是其宣布的幾次探測(cè)到的引力波沒(méi)有得到世間公認(rèn)。韋伯的歷史角色一直在科學(xué)殉道者和江湖郎中之間徘徊。這次引力波探測(cè)成功,無(wú)疑將韋伯定義為歷史先驅(qū),使得他多舛的命運(yùn)被賦予上悲劇英雄的色彩;同時(shí),這也宣示著人類理性思維的巨大成功。愛(ài)因斯坦廣義相對(duì)論的建立遵循了經(jīng)典理論研究途徑,從公理體系的建立,到嚴(yán)格數(shù)學(xué)推理,直至精確物理預(yù)言,最后由實(shí)驗(yàn)檢驗(yàn);數(shù)學(xué)推理中抽象的黎曼幾何超越了人類直覺(jué),真正指導(dǎo)愛(ài)因斯坦建立恢弘體系的是對(duì)理論體系內(nèi)在和諧性的審美。
另一個(gè)顛覆性的進(jìn)展是人工智能,特別是機(jī)器學(xué)習(xí)的熱潮。這幾年來(lái),機(jī)器學(xué)習(xí)的知識(shí)技巧鋪天蓋地而來(lái),學(xué)生每天都被各種學(xué)術(shù)廣告所沖擊,眼花繚亂、難以適從,終日處于被時(shí)代拋棄的焦慮之中。經(jīng)過(guò)數(shù)年的學(xué)術(shù)訓(xùn)練后,依然無(wú)法對(duì)于問(wèn)題進(jìn)行數(shù)學(xué)建模、理論分析,取而代之的是“端到端”的訓(xùn)練技巧。這種基于經(jīng)驗(yàn)統(tǒng)計(jì)的“煉金術(shù)”是否最終會(huì)被嚴(yán)格理論所闡發(fā)和提煉,目前仁者見(jiàn)仁,智者見(jiàn)智。靜待泡沫散去,時(shí)光自會(huì)蒸餾出醇酒。
第三個(gè)狂潮卻饒有興味,比特幣和區(qū)塊鏈。年末比特幣市場(chǎng)日趨狂熱,日益脫離數(shù)字貨幣的初心,淪為豪賭的工具。雖然人類對(duì)于金錢(qián)的追求日益非理性,但是中本聰設(shè)計(jì)的比特幣網(wǎng)絡(luò)協(xié)議卻是基于人類理性的假設(shè)。人類歷史上,金融交易系統(tǒng)都是建立在信任基礎(chǔ)之上的,一直存在可信賴的中心機(jī)構(gòu)來(lái)認(rèn)證個(gè)人擁有的財(cái)富值,來(lái)認(rèn)證每筆交易的正確性。而比特幣卻顛覆了這兩點(diǎn):比特幣系統(tǒng)不需要信任機(jī)構(gòu)作為中心;比特幣系統(tǒng)具有不可追蹤性,無(wú)法從賬戶地址推斷所有者。這種數(shù)字貨幣系統(tǒng)是基于如下的兩個(gè)理性假設(shè):首先,比特幣網(wǎng)絡(luò)上“好人”永遠(yuǎn)多于“壞人”;其次,基于橢圓曲線的加密算法是安全的,無(wú)法被輕易破解。
橢圓曲線理論的興起得益于費(fèi)馬大定理(Fermat‘s Last Theorem)的證明。費(fèi)馬猜測(cè)方程當(dāng)n大于2時(shí),不存在整數(shù)解。這一猜測(cè)猶如萬(wàn)丈絕壁,橫亙?cè)跀?shù)論發(fā)展的歷史道路上長(zhǎng)達(dá)三百余年。最關(guān)鍵的突破來(lái)自于橢圓曲線。谷山豐提出的谷山-志村猜測(cè)建立了橢圓曲線和模形式(某種周期性全純函數(shù))之間的重要聯(lián)系。谷山豐雖然洞察到了天機(jī),但是無(wú)法證明,三十出頭蹈海而逝,其新婚的妻子也殉情自殺。后來(lái),安德魯。懷爾斯(Andrew Wiles)證明了谷山-志村猜測(cè)的一部分,從而證明了費(fèi)馬大定理。費(fèi)馬定理的證明自然是人類思想史上的豐碑,谷山為數(shù)學(xué)殉道,終成千古絕唱;懷爾斯數(shù)十年如一日癡心追夢(mèng),令人景仰。但是,在那時(shí),無(wú)人會(huì)預(yù)料費(fèi)馬定理證明所孕育的橢圓曲線理論會(huì)有一日成為比特幣網(wǎng)絡(luò)的基礎(chǔ)。
數(shù)學(xué)上愈是艱深的理論,轉(zhuǎn)換成算法愈是難以破解,因此也是愈發(fā)安全。在有限域上,橢圓曲線所定義的代數(shù)簇(解的點(diǎn)集)是一個(gè)有限的離散點(diǎn)集。每條橢圓曲線和直線有三個(gè)交點(diǎn),我們將其理解為三個(gè)點(diǎn)之和為0,如此在代數(shù)簇上定義了一個(gè)群結(jié)構(gòu)。在這個(gè)群中,我們可以構(gòu)造一些容易檢驗(yàn)但是難以求解的問(wèn)題,所謂單向函數(shù),例如離散對(duì)數(shù)。這些單向函數(shù)用于數(shù)字簽名,使得用戶容易驗(yàn)證,但是無(wú)法偽造,由此構(gòu)成了比特幣協(xié)議的基礎(chǔ)。數(shù)學(xué)上,對(duì)于橢圓曲線群結(jié)構(gòu)的理解,對(duì)于比特幣系統(tǒng)至關(guān)重要。
橢圓曲線的加法群橢圓曲線具有形式 ,多項(xiàng)式方程有相異根的充要條件是非零。我們考察代數(shù)簇這里是無(wú)窮遠(yuǎn)點(diǎn)。
圖1. 橢圓曲線上的加法
如圖1所示,我們考慮定義在實(shí)數(shù)域上的一條橢圓曲線,它和過(guò)點(diǎn)P,Q的直線交于第三個(gè)點(diǎn)R,過(guò)R做鉛直線,鉛直線和橢圓曲線交于第四個(gè)點(diǎn)。第四個(gè)點(diǎn)和R互反,記為。那么,我們定義加法 。經(jīng)過(guò)簡(jiǎn)單代數(shù)運(yùn)算,我們得到如此定義的加法使得橢圓曲線上所有的點(diǎn)構(gòu)成一個(gè)加法群,無(wú)窮遠(yuǎn)點(diǎn)為單位元。圖2. 橢圓曲線上的乘法。
圖2顯示了橢圓曲線上的乘法。如果我們過(guò)點(diǎn)G做切線,切線交橢圓曲線于-2G,經(jīng)過(guò)反射得到2G。如此,我們可以定義4G,8G等等。
以上的幾何運(yùn)算可以直接轉(zhuǎn)換成代數(shù)運(yùn)算。令,過(guò)兩點(diǎn)的直線為,這里那么。由此,我們看到如果橢圓曲線的系數(shù)A和B在某個(gè)域K中,的坐標(biāo)也在域K中,那么和的坐標(biāo)也在域K中。由此,龐加萊(Poincare)證明了實(shí)數(shù)域上橢圓曲線E(R)上所有坐標(biāo)在K中的點(diǎn)E(K)(并上無(wú)窮遠(yuǎn)點(diǎn))構(gòu)成子群。
復(fù)數(shù)域上的橢圓曲線-黎曼面
如果橢圓曲線的域?yàn)閺?fù)數(shù)域,那么橢圓曲線的代數(shù)簇構(gòu)成一張黎曼面,虧格為一的拓?fù)漭喬?。首先我們定義一個(gè)格點(diǎn),那么輪胎是商空間。
圖4. 復(fù)數(shù)域上的橢圓曲線。
我們定義威爾斯特拉斯p-函數(shù),(Weierstrass p-funcTIon),那么我們令則。這里威爾斯特拉斯p-函數(shù)是雙周期函數(shù),滿足周期性條件。
這時(shí),橢圓曲線群的結(jié)構(gòu)為,即為拓?fù)漭喬ァN覀児潭ㄒ粋€(gè)大于1的正整數(shù)N,定義子群,即橢圓曲線上所有秩可以整除N的點(diǎn)構(gòu)成的子群。那么這個(gè)子群是兩個(gè)循環(huán)子群的乘積。
有理數(shù)域上的橢圓曲線如果橢圓曲線的域?yàn)橛欣頂?shù)域,具有無(wú)窮多個(gè)點(diǎn)。Mordell于1922年證明了是有限生成的群,存在有限點(diǎn)集,任意一個(gè)點(diǎn)可以被表示為,
更進(jìn)一步,,這里是橢圓曲線的有限階撓子群,r被稱為是橢圓曲線的秩(rank)。1977年,Mazur證明了橢圓曲線的撓子群只有15種情況,和。但是橢圓曲線的秩卻依然神秘,人們猜測(cè)對(duì)于任意大的r,都存在有理數(shù)域上的一條橢圓曲線,其秩等于r。
有限域上的橢圓曲線
令p是一個(gè)正整數(shù),是模p的整數(shù)域。一條橢圓曲線,滿足,其代數(shù)簇是離散點(diǎn)集,如圖5所示,同一條橢圓曲線在不同的有限域上,其代數(shù)簇包含不同數(shù)目的離散點(diǎn)。
圖5. 同一條橢圓曲線,在不同的有限域上具有不同數(shù)目的離散點(diǎn)
Hasse在1922年證明了有限域上橢圓曲線代數(shù)簇點(diǎn)的個(gè)數(shù)和(p+1)的差不大于p的平方根的兩倍 :。特別的,如果p為2的指數(shù),即所謂的Koblitz曲線,那么。
令橢圓線E是定義在一個(gè)有限域上,,,令S和T是橢圓曲線上的兩個(gè)點(diǎn),找到整數(shù)m使得,這一問(wèn)題被稱為是離散對(duì)數(shù)問(wèn)題。目前求解離散對(duì)數(shù)最為有效的是Pollar方法,其算法復(fù)雜度為,為k的指數(shù)級(jí)復(fù)雜度。比特幣協(xié)議中數(shù)字簽名的安全性就是離散對(duì)數(shù)問(wèn)題的指數(shù)級(jí)復(fù)雜度。
一般而言,如果橢圓曲線群具有更加豐富的結(jié)構(gòu),那么離散對(duì)數(shù)問(wèn)題的難度會(huì)被降低。數(shù)學(xué)上的常用手法是將有限域變換成另外一個(gè)域,尤其是有理數(shù)域,從而建立兩個(gè)橢圓曲線群之間的同態(tài),并且在特定情況下,同態(tài)可以被增強(qiáng)為同構(gòu)。具體而言,固定一個(gè)有理數(shù)域上橢圓曲線E(Q),將其系數(shù)模p,我們把它映射到有限域上的橢圓曲線E(Fp),每個(gè)E(Q)上的點(diǎn)P(x,y)被映射到E(Fp)上的點(diǎn),假設(shè)x=a/b,那么。這一映射被稱為是 ReducTIon Modulo p Map。如果E(Fp)非退化,那么這一映射給出群E(Q)和E(Fp)之間的同態(tài)。至關(guān)重要的是,如果我們選定一個(gè)正整數(shù)N,和p彼此互素,那么ReducTIon Modulo p Map是 之間的同構(gòu)。這個(gè)定理的重要性,無(wú)論怎么強(qiáng)調(diào)都不會(huì)為過(guò)。
這種變換代數(shù)曲線基本數(shù)域的方法非常優(yōu)雅,本質(zhì)上如果用有限域,我們得到的是數(shù)論問(wèn)題,如果我們用復(fù)數(shù)域,我們得到的是黎曼面的復(fù)幾何問(wèn)題。例如,著名的橢圓曲線L序列問(wèn)題,就是數(shù)論和代數(shù)幾何的交叉點(diǎn)。令E是一個(gè)固定的橢圓曲線,其系數(shù)A,B為整數(shù)。對(duì)任意一個(gè)素?cái)?shù)p,我們將E映射到模p域上,得到橢圓曲線E(Fp),我們定義E(Fp)的跡為, 著名的L-序列(L-series) 將所有的跡編碼至一個(gè)函數(shù)。
Wile證明L(E,s)可以解析延拓到整個(gè)復(fù)平面上。s=1是L(E,s)的零點(diǎn),著名的Brich-Swinnerton-Dyer猜測(cè)是說(shuō)這一零點(diǎn)的指標(biāo),等于有理域上曲線E(Q)的生成元的個(gè)數(shù)。最近,華裔數(shù)學(xué)新星惲之瑋和張偉贏得了2018數(shù)學(xué)“新視野獎(jiǎng)”,這一大獎(jiǎng)由谷歌創(chuàng)始人、FaceBook創(chuàng)始人、俄羅斯富翁米爾納夫婦和馬化騰等共同捐贈(zèng)。
小結(jié)橢圓曲線連接著代數(shù)幾何和數(shù)論,蘊(yùn)含著自然的天機(jī),其博大精深令無(wú)數(shù)的數(shù)學(xué)家心醉神迷,一往情深。從谷山豐的慷慨悲歌、到威爾斯的英雄史詩(shī),再到中本聰?shù)拿钍稚袼悖?從數(shù)學(xué)圣壇上的抽象理論到金融市場(chǎng)的數(shù)字貨幣,從數(shù)學(xué)家為自然真理的決絕殉道,到蕓蕓眾生貪婪癲狂的拜金主義,這一切方向都是狂悖混亂,截然相反,卻又順理成章,天衣無(wú)縫。歷史的發(fā)展總是超出想象,顛覆一切,卻又天道循環(huán),生生不息。我們深信, 人性中對(duì)真理的追求和對(duì)金錢(qián)的追求,亙古不變:會(huì)有更多的青年才俊,為追尋自然真理而苦心孤詣,嘔心瀝血;也會(huì)有更多的金融高手,閃轉(zhuǎn)騰挪,翻手云雨。依隨橢圓曲線理論的進(jìn)一步突破,更多的金融創(chuàng)新會(huì)再度橫空出世。