摩爾定律放緩 靠啥提升AI晶片運算力?
作者 : 黃燁鋒,EE Times China
2021-07-26
對於電子科技革命的即將終結的說法,一般認為即是指摩爾定律的終結——摩爾定律一旦無法延續,也就意味著資訊技術的整棟大樓建造都將出現停滯,那麼第三次科技革命也就正式結束了。這種聲音似乎是從十多年前就有的,但這波革命始終也沒有結束。AI技術本質上仍然是第三次科技革命的延續……
人工智慧(AI)的技術發展,被很多人形容為第四次科技革命。前三次科技革命,分別是蒸汽、電氣、資訊技術(電子科技)革命。彷彿這“第四次”有很多種說辭,比如有人說第四次科技革命是生物技術革命,還有人說是量子技術革命。但既然AI也是第四次科技革命之一的候選技術,而且作為資訊技術的組成部分,卻又獨立於資訊技術,即表示它有獨到之處。
電子科技革命的即將終結,一般認為即是指摩爾定律的終結——摩爾定律一旦無法延續,也就意味著資訊技術的整棟大樓建造都將出現停滯,那麼第三次科技革命也就正式結束了。這種聲音似乎是從十多年前就有,但這波革命始終也沒有結束。
AI技術本質上仍然是第三次科技革命的延續,它的發展也依託於幾十年來半導體科技的進步。這些年出現了不少專門的AI晶片——而且市場參與者相眾多。當某一個類別的技術發展到出現一種專門的處理器為之服務的程度,那麼這個領域自然就不可小覷,就像當年GPU出現專門為圖形運算服務一樣。
所以AI晶片被形容為CPU、GPU之後的第三大類電腦處理器。AI專用處理器的出現,很大程度上也是因為摩爾定律的發展進入緩慢期:電晶體的尺寸縮減速度,已經無法滿足需求,所以就必須有某種專用架構(DSA)出現,以快速提升晶片效率,也才有了專門的AI晶片。
另一方面,摩爾定律的延緩也成為AI晶片發展的桎梏。在摩爾定律和登納德縮放比例定律(Dennard Scaling)發展的前期,電晶體製程進步為晶片帶來了相當大的助益,那是「happy scaling down」的時代——CPU、GPU都是這個時代受益,不過Dennard Scaling早在45nm時期就失效了。
AI晶片作為第三大類處理器,在這波發展中沒有趕上happy scaling down的好時機。與此同時,AI應用對運算力的需求越來越貪婪。今年WAIC晶片論壇圓桌討論環節,燧原科技創始人暨CEO趙立東說:「現在訓練的GPT-3模型有1750億參數,接近人腦神經元數量,我以為這是最大的模型了,要千張Nvidia的GPU卡才能做。談到AI運算力需求、模型大小的問題,說最大模型超過萬億參數,又是10倍。」
英特爾(Intel)研究院副總裁、中國研究院院長宋繼強說:「前兩年用GPU訓練一個大規模的深度學習模型,其碳排放量相當於5台美式車整個生命週期產生的碳排量。」這也說明了AI運算力需求的貪婪,以及提供運算力的AI晶片不夠高效。
不過作為產業的底層驅動力,半導體製造技術仍源源不斷地為AI發展提供推力。本文將討論WAIC晶片論壇上聽到,針對這個問題的一些前瞻性解決方案——有些已經實現,有些則可能有待時代驗證。
XPU、摩爾定律和異質整合
「電腦產業中的貝爾定律,是說能效每提高1,000倍,就會衍生出一種新的運算形態。」中科院院士劉明在論壇上說,「若每瓦功耗只能支撐1KOPS的運算,當時的這種運算形態是超算;到了智慧型手機時代,能效就提高到每瓦1TOPS;未來的智慧終端我們要達到每瓦1POPS。 這對IC提出了非常高的要求,如果依然沿著CMOS這條路去走,當然可以,但會比較艱辛。」
針對性能和效率提升,除了尺寸微縮,半導體產業比較常見的思路是電晶體結構、晶片結構、材料等方面的最佳化,以及處理架構的革新。
(1)AI晶片本身其實就是對處理器架構的革新,從運算架構的層面來看,針對不同的應用方向造不同架構的處理器是常規,更專用的處理器能促成效率和性能的成倍增長,而不需要依賴於電晶體尺寸的微縮。比如GPU、神經網路處理器(NPU,即AI處理器),乃至更專用的ASIC出現,都是這類思路。
CPU、GPU、NPU、FPGA等不同類型的晶片各司其職,Intel這兩年一直在推行所謂的「XPU」策略就是用不同類型的處理器去做不同的事情,「整合起來各取所需,用組合拳會好過用一種武器去解決所有問題。」宋繼強說。Intel的晶片產品就涵蓋了幾個大類,Core CPU、Xe GPU,以及透過收購獲得的AI晶片Habana等。
另外針對不同類型的晶片,可能還有更具體的最佳化方案。如當代CPU普遍加入AVX512指令,本質上是特別針對深度學習做加強。「專用」的不一定是處理器,也可以是處理器內的某些特定單元,甚至固定功能單元,就好像GPU中加入專用的光線追蹤單元一樣,這是當代處理器普遍都在做的一件事。
(2)從電晶體、晶片結構層面來看,電晶體的尺寸現在仍然在縮減過程中,只不過縮減幅度相比過去變小了——而且為緩解電晶體性能的下降,需要有各種不同的技術來輔助尺寸變小。比如說在22nm節點之後,電晶體變為FinFET結構,在3nm之後,電晶體即將演變為Gate All Around FET結構。最終會演化為互補FET (CFET),其本質都是電晶體本身充分利用Z軸,來實現微縮性能的提升。
劉明認為,「除了基礎元件的變革,IC現在的發展還是比較多元化,包括新材料的引進、元件結構革新,也包括微影技術。長期賴以微縮的基本手段,現在也在發生巨大的變化,特別是未來3D的異質整合。這些多元技術的協同發展,都為晶片整體性能提升帶來了很好的增益。」
他並指出,「從電晶體級、到晶圓級,再到晶片堆疊、引線接合(lead bonding),精準度從毫米向奈米演進,互連密度大大提升。」從晶圓/裸晶的層面來看,則是眾所周知的朝more than moore’s law這樣的路線發展,比如把兩片裸晶疊起來。現在很熱門的chiplet技術就是比較典型的並不依賴於傳統電晶體尺寸微縮,來彈性擴展性能的方案。
台積電和Intel這兩年都在大推將不同類型的裸晶,異質整合的技術。2.5D封裝方案典型如台積電的CoWoS,Intel的EMIB,而在3D堆疊上,Intel的Core LakeField晶片就是用3D Foveros方案,將不同的裸晶疊在一起,甚至可以實現兩片運算裸晶的堆疊、互連。
之前的文章也提到過AMD剛發佈的3D V-Cache,將CPU的L3 cache裸晶疊在運算裸晶上方,將處理器的L3 cache大小增大至192MB,對儲存敏感延遲應用的性能提升。相比Intel,台積電這項技術的獨特之處在於裸晶間是以混合接合(hybrid bonding)的方式互連,而不是micro-bump,做到更小的打線間距,以及晶片之間數十倍通訊性能和效率提升。
這些方案也不直接依賴傳統的電晶體微縮方案。這裡實際上還有一個方面,即新材料的導入專家們沒有在論壇上多說,本文也略過不談。
1,000倍的性能提升
劉明談到,當電晶體微縮的空間沒有那麼大的時候,產業界傾向於採用新的策略來評價技術——「PPACt」——即Powe r(功耗)、Performance (性能)、Cost/Area-Time (成本/面積-時間)。t指的具體是time-to-market,理論上應該也屬於成本的一部分。
電晶體微縮方案失效以後,「多元化的技術變革,依然會讓IC性能得到進一步的提升。」劉明說,「根據預測,這些技術即使不再做尺寸微縮,也會讓IC的晶片性能做到500~1,000倍的提升,到2035年實現Zetta Flops的系統性能水準。且超算的發展還可以一如既往地前進;單裸晶儲存容量變得越來越大,IC依然會為產業發展提供基礎。」
500~1,000倍的預測來自DARPA,感覺有些過於樂觀。因為其中的不少技術存在比較大的邊際遞減效應,而且有更實際的工程問題待解決,比如運算裸晶疊層的散熱問題——即便業界對於這類工程問題的探討也始終在持續。
不過1,000倍的性能提升,的確說明摩爾定律的終結並不能代表第三次科技革命的終結,而且還有相當大的發展空間。尤其本文談的主要是AI晶片,而不是更具通用性的CPU。
矽光、記憶體內運算和神經型態運算
在非傳統發展路線上(以上內容都屬於半導體製造的常規思路),WAIC晶片論壇上宋繼強和劉明都提到了一些頗具代表性的技術方向(雖然這可能與他們自己的業務方向或研究方向有很大的關係)。這些技術可能尚未大規模推廣,或者仍在商業化的極早期。
(1)近記憶體運算和記憶體內運算:處理器性能和效率如今面臨的瓶頸,很大程度並不在單純的運算階段,而在資料傳輸和儲存方面——這也是共識。所以提升資料的傳輸和存取效率,可能是提升整體系統性能時,一個非常靠譜的思路。
這兩年市場上的處理器產品用「近記憶體運算」(near-memory computing)思路的,應該不在少數。所謂的近記憶體運算,就是讓儲存(如cache、memory)單元更靠近運算單元。CPU的多層cache結構(L1、L2、L3),以及電腦處理器cache、記憶體、硬碟這種多層儲存結構是常規。而「近記憶體運算」主要在於究竟有多「近」,cache記憶體有利於隱藏當代電腦架構中延遲和頻寬的局限性。
這兩年在近記憶體運算方面比較有代表性的,一是AMD——比如前文提到3D V-cache增大處理器的cache容量,還有其GPU不僅在裸晶內導入了Infinity Cache這種類似L3 cache的結構,也更早應用了HBM2記憶體方案。這些實踐都表明,儲存方面的革新的確能帶來性能的提升。
另外一個例子則是Graphcore的IPU處理器:IPU的特點之一是在裸晶內堆了相當多的cache資源,cache容量遠大於一般的GPU和AI晶片——也就避免了頻繁的訪問外部儲存資源的操作,極大提升頻寬、降低延遲和功耗。
近記憶體運算的本質仍然是馮紐曼架構(Von Neumann architecture)的延續。「在做處理的過程中,多層級的儲存結構,資料的搬運不僅僅在處理和儲存之間,還在不同的儲存層級之間。這樣頻繁的資料搬運帶來了頻寬延遲、功耗的問題。也就有了我們經常說的運算體系內的儲存牆的問題。」劉明說。
構建非馮(non-von Neumann)架構,把傳統的、以運算為中心的馮氏架構,變換一種新的運算範式。把部分運算力下推到儲存。這便是記憶體內運算(in-memory computing)的概念。
記憶體內運算的就現在看來還是比較新,也有稱其為「存算一體」。通常理解為在記憶體中嵌入演算法,儲存單元本身就有運算能力,理論上消除資料存取的延遲和功耗。記憶體內運算這個概念似乎這在資料爆炸時代格外醒目,畢竟可極大減少海量資料的移動操作。
其實記憶體內運算的概念都還沒有非常明確的定義。現階段它可能的內涵至少涉及到在儲記憶體內部,部分執行資料處理工作;主要應用於神經網路(因為非常契合神經網路的工作方式),以及這類晶片具體的工作方法上,可能更傾向於神經型態運算(neuromorphic computing)。
對於AI晶片而言,記憶體內運算的確是很好的思路。一般的GPU和AI晶片執行AI負載時,有比較頻繁的資料存取操作,這對性能和功耗都有影響。不過記憶體內運算的具體實施方案,在市場上也是五花八門,早期比較具有代表性的Mythic導入了一種矩陣乘的儲存架構,用40nm嵌入式NOR,在儲記憶體內部執行運算,不過替換掉了數位週邊電路,改用類比的方式。在陣列內部進行模擬運算。這家公司之前得到過美國國防部的資金支援。
劉明列舉了近記憶體運算和記憶體內運算兩種方案的例子。其中,近記憶體運算的這個方案應該和AMD的3D V-cache比較類似,把儲存裸晶和運算裸晶疊起來。
劉明指出,「這是我們最近的一個工作,採用hybrid bonding的技術,與矽通孔(TSV)做比較,hybrid bonding功耗是0.8pJ/bit,而TSV是4pJ/bit。延遲方面,hybrid bonding只有0.5ns,而TSV方案是3ns。」台積電在3D堆疊方面的領先優勢其實也體現在hybrid bonding混合鍵合上,前文也提到了它具備更高的互連密度和效率。
另外這套方案還將DRAM刷新頻率提高了一倍,從64ms提高至128ms,以降低功耗。「應對刷新率變慢出現拖尾bit,我們引入RRAM TCAM索引這些tail bits」劉明說。
記憶體內運算方面,「傳統運算是用布林邏輯,一個4位元的乘法需要用到幾百個電晶體,這個過程中需要進行資料來回的移動。記憶體內運算是利用單一元件的歐姆定律來完成一次乘法,然後利用基爾霍夫定律完成列的累加。」劉明表示,「這對於今天深度學習的矩陣乘非常有利。它是原位的運算和儲存,沒有資料搬運。」這是記憶體內運算的常規思路。
「無論是基於SRAM,還是基於新型記憶體,相比近記憶體運算都有明顯優勢,」劉明認為。下圖是記憶體內運算和近記憶體運算,精準度、能效等方面的對比,記憶體內運算架構對於低精準度運算有價值。
下圖則總結了業內主要的一些記憶體內運算研究,在精確度和能效方面的對應關係。劉明表示,「需要高精確度、高運算力的情況下,近記憶體運算目前還是有優勢。不過記憶體內運算是更新的技術,這幾年的進步也非常快。」
去年阿里達摩院發佈2020年十大科技趨勢中,有一個就是存算一體突破AI算力瓶頸。不過記憶體內運算面臨的商用挑戰也一點都不小。記憶體內運算的通常思路都是類比電路的運算方式,這對記憶體、運算單元設計都需要做工程上的考量。與此同時這樣的晶片究竟由誰來造也是個問題:是記憶體廠商,還是數文書處理器廠商?(三星推過記憶體內運算晶片,三星、Intel垂直整合型企業似乎很適合做記憶體內運算…)
(2)神經型態運算:神經型態運算和記憶體內運算一樣,也是新興技術的熱門話題,這項技術有時也叫作compute in memory,可以認為它是記憶體內運算的某種發展方向。神經型態和一般神經網路AI晶片的差異是,這種結構更偏「類人腦」。
進行神經型態研究的企業現在也逐漸變得多起來,劉明也提到了AI晶片「最終的理想是在結構層次模仿腦,元件層次逼近腦,功能層次超越人腦」的「類腦運算」。Intel是比較早關注神經型態運算研究的企業之一。
傳說中的Intel Loihi就是比較典型存算一體的架構,「這片裸晶裡面包含128個小核心,每個核心用於模擬1,024個神經元的運算結構。」宋繼強說,「這樣一塊晶片大概可以類比13萬個神經元。我們做到的是把768個晶片再連起來,構成接近1億神經元的系統,讓學術界的夥伴去試用。」
「它和深度學習加速器相比,沒有任何浮點運算——就像人腦裡面沒有乘加器。所以其學習和訓練方法是採用一種名為spike neutral network的路線,功耗很低,也可以訓練出做視覺辨識、語言辨識和其他種類的模型。」宋繼強認為,不採用同步時脈,「刺激的時候就是一個非同步電動勢,只有工作部分耗電,功耗是現在深度學習加速晶片的千分之一。」
「而且未來我們可以對不同區域做劃分,比如這兒是視覺區、那兒是語言區、那兒是觸覺區,同時進行多模態訓練,互相之間產生關聯。這是現在的深度學習模型無法比擬的。」宋繼強說。這種神經型態運算晶片,似乎也是Intel在XPU方向上探索不同架構運算的方向之一。
(2)微型化矽光:這個技術方向可能在層級上更偏高了一些,不再晶片架構層級,不過仍然值得一提。去年Intel在Labs Day上特別談到了自己在矽光(Silicon Photonics)的一些技術進展。其實矽光技術在連接資料中心的交換機方面,已有應用了,發出資料時,連接埠處會有個收發器把電訊號轉為光訊號,透過光纖來傳輸資料,另一端光訊號再轉為電訊號。不過傳統的光收發器成本都比較高,內部元件數量大,尺寸也就比較大。
Intel在整合化的矽光(IIIV族monolithic的光學整合化方案)方面應該是商業化走在比較前列的,就是把光和電子相關的組成部分高度整合到晶片上,用IC製造技術。未來的光通訊不只是資料中心機架到機架之間,也可以下沉到板級——就跟現在傳統的電I/O一樣。電互連的主要問題是功耗太大,也就是所謂的I/O功耗牆,這是這類微型化矽光元件存在的重要價值。
這其中存在的技術挑戰還是比較多,如做資料的光訊號調變的調變器調變器,據說Intel的技術使其實現了1,000倍的縮小;還有在接收端需要有個探測器(detector)轉換光訊號,用所謂的全矽微環(micro-ring)結構,實現矽對光的檢測能力;波分複用技術實現頻寬倍增,以及把矽光和CMOS晶片做整合等。
Intel認為,把矽光模組與運算資源整合,就能打破必須帶更多I/O接腳做更大尺寸處理器的這種趨勢。矽光能夠實現的是更低的功耗、更大的頻寬、更小的接腳數量和尺寸。在跨處理器、跨伺服器節點之間的資料互動上,這類技術還是頗具前景,Intel此前說目標是實現每根光纖1Tbps的速率,並且能效在1pJ/bit,最遠距離1km,這在非本地傳輸上是很理想的數字。
還有軟體…
除了AI晶片本身,從整個生態的角度,包括AI感知到運算的整個鏈條上的其他組成部分,都有促成性能和效率提升的餘地。比如這兩年Nvidia從軟體層面,針對AI運算的中間層、庫做了大量最佳化。相同的底層硬體,透過軟體最佳化就能實現幾倍的性能提升。
宋繼強說,「我們發現軟體最佳化與否,在同一個硬體上可以達到百倍的性能差距。」這其中的餘量還是比較大。
在AI開發生態上,雖然Nvidia是最具發言權的;但從戰略角度來看,像Intel這種研發CPU、GPU、FPGA、ASIC,甚至還有神經型態運算處理器的企業而言,不同處理器統一開發生態可能更具前瞻性。Intel有個稱oneAPI的軟體平台,用一套API實現不同硬體性能埠的對接。這類策略對廠商的軟體框架構建能力是非常大的考驗——也極大程度關乎底層晶片的執行效率。
在摩爾定律放緩、電晶體尺寸微縮變慢甚至不縮小的前提下,處理器架構革新、異質整合與2.5D/3D封裝技術依然可以達成1,000倍的性能提升;而一些新的技術方向,包括近記憶體運算、記憶體內運算和微型矽光,能夠在資料訪存、傳輸方面產生新的價值;神經型態運算這種類腦運算方式,是實現AI運算的目標;軟體層面的最佳化,也能夠帶動AI性能的成倍增長。所以即便摩爾定律嚴重放緩,AI晶片的性能、效率提升在上面提到的這麼多方案加持下,終將在未來很長一段時間內持續飛越。這第三(四)次科技革命恐怕還很難停歇。
資料來源:https://www.eettaiwan.com/20210726nt61-ai-computing/?fbclid=IwAR3BaorLm9rL2s1ff6cNkL6Z7dK8Q96XulQPzuMQ_Yky9H_EmLsBpjBOsWg
乘法快速算法 在 Taipei Ethereum Meetup Facebook 的精選貼文
📜 [專欄新文章] [ZKP 讀書會] Trust Token Browser API
✍️ Yuren Ju
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
Trust Token API 是一個正在標準化的瀏覽器 API,主要的目的是在保護隱私的前提下提供跨站授權 (Cross-domain authorization) 的功能,以前如果需要跨站追蹤或授權通常都使用有隱私疑慮的 Cookies 機制,而 Trust Token 則是希望在保護隱私的前提下完成相同的功能。
會在 ZKP (Zero-knowledge proof) 讀書會研究 Trust Token 主要是這個 API 採用了零知識證明來保護隱私,這也是這次讀書會中少見跟區塊鏈無關的零知識證明應用。
問題
大家應該都有點了一個產品的網頁後,很快的就在 Facebook 或是 Google 上面看到相關的廣告。但是產品網頁並不是在 Facebook 上面,他怎麼會知道我看了這個產品的頁面?
通常這都是透過 Cookie 來做跨網站追蹤來記錄你在網路上的瀏覽行為。以 Facebook 為例。
當使用者登入 Facebook 之後,Facebook 會透過 Cookie 放一段識別碼在瀏覽器裡面,當使用者造訪了有安裝 Facebook SDK 來提供「讚」功能的網頁時,瀏覽器在載入 SDK 時會再度夾帶這個識別碼,此時 Facebook 就會知道你造訪了特定的網頁並且記錄下來了。如此一來再搭配其他不同管道的追蹤方式,Facebook 就可以建構出特定使用者在網路上瀏覽的軌跡,從你的瀏覽紀錄推敲喜好,餵給你 Facebook 最想給你看的廣告了。
不過跨站追蹤也不是只能用在廣告這樣的應用上,像是 CDN (Content Delivery Network) 也是一個應用場景。CDN 服務 Cloudflare 提供服務的同時會利用 Captcha 先來確定進入網站的是不是真人或是機器人。而他希望使用者如果是真人時下次造訪同時也是採用 Cloudflare 服務的網站不要再跳出 Captcha 驗證訊息。
雖然 Cloudflare 也需要跨站驗證的功能來完成他們的服務,但是相較於 Google 或 Facebook 來說他們是比較沒那麼想知道使用者的隱私。有沒有什麼辦法可以保護使用者隱私的狀況下還能完成跨站驗證呢?
這就是今天要講的新 API: Trust Token。
Trust Token API - The Chromium Projects
Trust Token / Privacy Pass 簡介
Trust Token 其實是由 Privacy Pass 延伸而來。Privacy Pass 就是由 Cloudflare 所開發的實驗性瀏覽器延伸套件實作一個驗證機制,可以在不透漏過多使用者隱私的前提下實作跨站驗證。而 Trust Token 則是標準化的 Privacy Pass,所以兩個運作機制類似,但是實作方式稍有不同。
先看一下 Privacy Pass 是如何使用。因為這是實驗性的瀏覽器延伸套件所以看起來有點陽春,不過大致上還是可以了解整個概念。
以 hCaptcha 跟 Cloudflare 的應用為例,使用者第一次進到由 Cloudflare 提供服務的網站時,網站會跳出一些人類才可以解答的問題比如說「挑出以下是汽車的圖片」。
當使用者答對問題後,Cloudflare 會回傳若干組 blind token,這些 blind token 還會需要經過 unblind 後才會變成真正可以使用的 token,這個過程為 issue token。如上圖所示假設使用者這次驗證拿到了 30 個 token,在每次造訪由 Cloudflare 服務的網站時就會用掉一個 token,這個步驟稱為 redeem token。
但這個機制最重要的地方在於 Cloudflare 並無法把 issue token 跟 redeem token 這兩個階段的使用者連結在一起,也就是說如果 Alice, Bob 跟 Chris 都曾經通過 Captcha 測試並且獲得了 Token,但是在後續瀏覽不同網站時把 token 兌換掉時,Clouldflare 並無法區分哪個 token 是來自 Bob,哪個 token 是來自 Alice,但是只要持有這種 token 就代表持有者已經通過了 Captcha 的挑戰證明為真人。
但這樣的機制要怎麼完成呢?以下我們會透過多個步驟的例子來解釋如何達成這個目的。不過在那之前我們要先講一下 Privacy Pass 所用到的零知識證明。
零知識證明 (Zero-knowledge proof)
零知識證明是一種方法在不揭露某個祕密的狀態下,證明他自己知道那個秘密。
Rahil Arora 在 stackexchange 上寫的比喻我覺得是相對好理解的,下面簡單的翻譯一下:
假設 Alice 有超能力可以幾秒內算出樹木上面有幾片樹葉,如何在不告訴 Bob 超能力是怎麼運作並且也不告訴 Bob 有多少片葉子的狀況下證明 Alice 有超能力?我們可以設計一個流程來證明這件事情。
Alice 先把眼睛閉起來,請 Bob 選擇拿掉樹上的一片葉子或不拿掉。當 Alice 睜開眼睛的時候,告訴 Bob 他有沒有拿掉葉子。如果一次正確的話確實有可能是 Alice 幸運猜到,但是如果這個過程連續很多次時 Alice 真的擁有數葉子的超能力的機率就愈來愈高。
而零知識證明的原理大致上就是這樣,你可以用一個流程來證明你知道某個秘密,即使你不真的揭露這個秘密到底是什麼,以上面的例子來說,這個秘密就是超能力運作的方式。
以上就是零知識證明的概念,不過要完成零知識證明有很多各式各樣的方式,今天我們要介紹的是 Trust Token 所使用的零知識證明:DLEQ。
DLEQ (Discrete Logarithm Equivalence Proof)
說明一下以下如果小寫的變數如 c, s 都是純量 (Scalar),如果是大寫如 G, H則是橢圓曲線上面的點 (Point),如果是 vG 則一樣是點,計算方式則是 G 連續相加 v 次,這跟一般的乘法不同,有興趣可以程式前沿的《橢圓曲線加密演算法》一文解釋得比較詳細。
DLEQ 有一個前提,在系統中的所有人都知道公開的 G 跟 H 兩個點,此時以下等式會成立:
假設 Peggy 擁有一個秘密 s 要向 Victor 證明他知道 s 為何,並且在這個過程中不揭露 s 真正的數值,此時 Victor 可以產生一個隨機數 c 傳送給 Peggy,而 Peggy 則會再產生一個隨機數 v 並且產生 r,並且附上 vG, vH, sG, sH:
r = v - cs
所以 Victor 會得到 r, sG, sH, vG, vH 再加上他已經知道的 G, H。這個時候如果 Victor 計算出以下兩個等式就代表 Peggy 知道 s 的真正數值:
vG = rG + c(sG)vH = rH + c(sH)
我們舉第二個等式作為例子化簡:
vH = rH + c(sH) // 把 r 展開成 v - csvH = (v - cs)H + c(sH) // (v - cs)H 展開成 vH - csHvH = vH - c(sH) + c(sH) // 正負 c(sH) 消掉vH = vH
這樣只有 Peggy 知道 s 的狀況下才能給出 r,所以這樣就可以證明 Peggy 確實知道 s。
從簡易到實際的情境
Privacy Pass 網站上透過了循序漸進的七種情境從最簡單的假設到最後面實際使用的情境來講解整個機制是怎麼運作的。本文也用相同的方式來解釋各種情境,不過前面的例子就會相對比較天真一點,就請大家一步步的往下看。
基本上整個過程是透過一種叫做 Blind Signature 的方式搭配上零知識證明完成的,以下參與的角色分為 Client 與 Server,並且都會有兩個階段 issue 與 redeem token。
Scenario 1
如果我們要設計一個這樣可以兌換 token 來確認身分的系統,其中有一個方法是透過橢圓曲線 (elliptic curve) 完成。Client 挑選一個在橢圓曲線上的點 T 並且傳送給 Server,Server 收到後透過一個只有 Server 知道的純量 (scalar) s 對 T 運算後得到 sT 並且回傳給 Client,這個產生 sT 的過程稱為 Sign Point,不過實際上運作的原理就是橢圓曲線上的連續加法運算。
SignPoint(T, s) => sT
等到 Client 需要兌換時只要把 T 跟 sT 給 Server,Server 可以收到 T 的時候再 Sign Point 一次看看是不是 sT 就知道是否曾經 issue 過這個 token。
Issue
以下的範例,左邊都是 Client, 右邊都是 Server。 -> 代表 Client 發送給 Server,反之亦然。
// Client 發送 T 給 Server, 然後得到 sT
T -> <- sT
Redeem
// Client 要 redeem token 時,傳出 T 與 sT
T, sT ->
問題:Linkability
因為 Server 在 issue 的時候已經知道了 T,所以基本上 Server 可以透過這項資訊可以把 issue 階段跟 redeem 階段的人連結起來進而知道 Client 的行為。
Scenario 2
要解決上面的問題,其中一個方法是透過 Blind Signature 達成。Client 不送出 T,而是先透過 BlindPoint 的方式產生 bT 跟 b,接下來再送給 Server bT。Server 收到 bT 之後,同樣的透過 Sign Point 的方式產生結果,不一樣的地方是情境 1 是用 T,而這邊則用 bT 來作 Sign Point,所以得出來的結果是 s(bT)。
Client:BlindPoint(T) => (bT, b)
Server:SignPoint(bT, s) => sbT
而 Blind Signature 跟 Sign Point 具備了交換律的特性,所以得到 s(bT) 後可以透過原本 Client 已知的 b 進行 Unblind:
UnblindPoint(sbT, b) => sT
這樣一來在 Redeem 的時候就可以送出 T, sT 給 Server 了,而且透過 SignPoint(T, s) 得出結果 sT’ 如果符合 Client 傳來的 sT 就代表確實 Server 曾經簽過這個被 blind 的點,同時因為 T 從來都沒有送到 Server 過,所以 Server 也無法將 issue 與 redeem 階段的 Client 連結在一起。
Issue
bT -> <- s(bT)
Redeem
T, sT ->
問題:Malleability
以上的流程其實也有另外一個大問題,因為有交換律的關係,當 Client 透過一個任意值 a 放入 BlindPoint 時產生的 a(sT) 就會等於 s(aT):
BlindPoint(sT) => a(sT), a// a(sT) === s(aT)
此時如果將 aT 跟 s(aT) 送給 Server Redeem,此時因為
SignPoint(aT, s) => s(aT)
所以就可以兌換了,這樣造成 Client 可以無限地用任意數值兌換 token。
Scenario 3
這次我們讓 Client 先選擇一個純數 t,並且透過一種單向的 hash 方式來產生一個在橢圓曲線上的點 T,並且在 redeem 階段時原本是送出 T, sT 改成送出 t, sT。
因為 redeem 要送出的是 t,上個情境時透過任意數 a 來產生 s(aT) 的方法就沒辦法用了,因為 t 跟 sT 兩個參數之間並不是單純的再透過一次 BlindPoint() 就可以得到,所以就沒辦法無限兌換了。
Issue
T = Hash(t) bT -> <- sbT
Redeem
t, sT ->
問題:Redemption hijacking
在這個例子裏面,Client 其實是沒有必要傳送 sT 的,因為 Server 僅需要 t 就可以計算出 sT,額外傳送 sT 可能會導致潛在的 Redemption hijacking 問題,如果在不安全的通道上傳輸 t, sT 就有可能這個 redemption 被劫持作為其他的用途。
不過在網站上沒講出實際上要怎麼利用這個問題,但是少傳一個可以計算出來的資料總是好的。Client 只要證明他知道 sT 就好,而這可以透過 HMAC (Hash-based Message Authentication Code) 達成。
Scenario 4
步驟跟前面都一樣,唯一不一樣的地方是 redeem 的時候原本是傳 t, sT,現在則改傳 t, M, HMAC(sT, M),如果再介紹 HMAC 篇幅會太大,這邊就不解釋了,但可以是作是一個標準的 salt 方式讓 Hash 出來的結果不容易受到暴力破解。
這樣的特性在這個情境用很適合,因為 Server 透過 t 就可以計算出 sT,透過公開傳遞的 M 可以輕易地驗證 client 端是否持有 sT。
Issue
T = Hash(t) bT -> <- sbT
Redeem
t, M, HMAC(sT, M) ->
問題:Tagging
這邊的問題在於 Server 可以在 issue 階段的時候用不一樣的 s1, s2, s3 等來發出不一樣的 sT’,這樣 Server 在 Redeem 階段就可以得知 client 是哪一個 s。所以 Server 需要證明自己每次都用同樣的 s 同時又不透漏 s 這個純亮。
要解決這個問題就需要用到前面我們講解的零知識證明 DLEQ 了。
Scenario 5
前面的 DLEQ 講解有提到,如果有 Peggy 有一個 s 秘密純量,我們可以透過 DLEQ 來證明 Peggy 知道 s,但是又不透漏 s 真正的數值,而在 Privacy Pass 的機制裡面,Server 需要證明自己每次都用 s,但是卻又不用揭露真正的數值。
在 Issue 階段 Client 做的事情還是一樣傳 bT 給 Server 端,但 Server 端的回應就不一樣了,這次 Server 會回傳 sbT 與一個 DLEQ 證明,證明自己正在用同一個 s。
首先根據 DLEQ 的假設,Server 會需要先公開一組 G, H 給所有的 Client。而在 Privacy Pass 的實作中則是公開了 G 給所有 Client,而 H 則改用 bT 代替。
回傳的時候 Server 要證明自己仍然使用同一個 s 發出 token,所以附上了一個 DLEQ 的證明 r = v - cs,Client 只要算出以下算式相等就可證明 Server 仍然用同一個 s (記住了 H 已經改用 bT 代替,此時 client 也有 sbT 也就是 sH):
vH = rH + c(sH) // H 換成 bTvbT = rbT + c(sbT) // 把 r 展開成 v - csvbT = (v - cs)bT + c(sbT) // (v - cs)bT 展開成 vbT - csbTvbT = vbT - c(sbT) + c(sbT) // 正負 c(sbT) 消掉vbT = vbT
這樣就可以證明 Server 依然用同一個 s。
Issue
T = Hash(t) bT -> <- sbT, DLEQ(bT:sbT == G:sG)
Redeem
t, M, HMAC(sT, M) ->
問題:only one redemption per issuance
到這邊基本上 Privacy Pass 的原理已經解釋得差不多了,不過這邊有個問題是一次只發一個 token 太少,應該要一次可以發多個 token。這邊我要跳過源文中提到的 Scenario 6 解釋最後的結果。
Scenario 7
由於一次僅產生一個 redeem token 太沒效率了,如果同時發很多次,每次都產生一個 proof 也不是非常有效率,而 DLEQ 有一個延伸的用法 “batch” 可以一次產生多個 token, 並且只有使用一個 Proof 就可以驗證所有 token 是否合法,這樣就可以大大的降低頻寬需求。
不過這邊我們就不贅述 Batch DLEQ 的原理了,文末我會提及一些比較有用的連結跟確切的源碼片段讓有興趣的人可以更快速的追蹤到源碼片段。
Issue
T1 = Hash(t1) T2 = Hash(t2)T3 = Hash(t3)b1T1 ->b2T2 ->b3T3 -> c1,c2,c3 = H(G,sG,b1T1,b2T2,b3T3,s(b1T1),s(b2T2),s(b3T3)) <- sb1T1 <- sb2T2 <- sb3T3 <- DLEQ(c1b1T1+c2b2T2+c3b3T3:s(c1b1T1+c2b2T2+c3b3T3) == G: sG)
Redeem
t1, M, HMAC(sT1, M) ->
結論
Privacy Token / Trust Token API 透過零知識證明的方式來建立了一個不需要透漏太多隱私也可以達成跟 cookie 相同效果的驗證方式,期待可以改變目前許多廣告巨頭透過 cookie 過分的追蹤使用者隱私的作法。
不過我在 Trust Token API Explainer 裡面看到這個協議裡面的延伸作法還可以夾帶 Metadata 進去,而協議制定的過程中其實廣告龍頭 Google 也參與其中,希望這份協議還是可以保持中立,盡可能地讓最後版本可以有效的在保護隱私的情況下完成 Cross-domain authorization 的功能。
參考資料
IETF Privacy Pass docs
Privacy Pass: The Protocol
Privacy Pass: Architectural Framework
Privacy Pass: HTTP API
Cloudflare
Supporting the latest version of the Privacy Pass Protocol (cloudflare.com)
Chinese: Cloudflare支持最新的Privacy Pass扩展_推动协议标准化
Other
Privacy Pass official website
Getting started with Trust Tokens (web.dev)
WICG Trust Token API Explainer
Non-interactive zero-knowledge (NIZK) proofs for the equality (EQ) of discrete logarithms (DL) (asecuritysite.com) 這個網站非常實用,列了很多零知識證明的源碼參考,但可惜的是 DLEQ 這個演算法講解有錯,讓我在理解演算法的時候撞牆很久。所以使用的時候請多加小心,源碼應該是可以參考的,解釋的話需要斟酌一下。
關鍵源碼
這邊我貼幾段覺得很有用的源碼。
privacy pass 提供的伺服器端產生 Proof 的源碼
privacy pass 提供的瀏覽器端產生 BlindPoint 的源碼
github dedis/kyber 產生 Proof 的源碼
[ZKP 讀書會] Trust Token Browser API was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
乘法快速算法 在 AppWorks Facebook 的最讚貼文
[AppWorks 創業者真心話] Johnny 蔡豐任, VoiceTube 共同創辦人
「Johhny 是 AppWorks 加速器 #7 屆的校友,共同創辦線上英語學習平台 VoiceTube 看影片學英語,目前擁有超過 400 萬用戶,跨足台灣、日本,並於去年底完成 A 輪募資。認識 Johhny 多年,我知道他是很可靠的創業者,總是熱心、真誠地和初創業者分享他的觀察與發現。於是我決定,這次的創業者真心話系列一定要邀請他,和大家分享平常較少對外聊的創業點滴與個人經歷。」by 本月編輯 Alyssa
.
.
『1. 曾經挑戰不同的創業題目,有失敗、有成功。現在回顧自己的經歷,你想給初創業者者什麼建議?』
#專心聆聽用戶需要什麼。
初創業者常會從「自己會什麼」出發,但自己過往的經驗與技能常常框住了想像力,我也不例外。我在創業前是在金融業服務,一開始創業也是從金融服務開始,但是我提供的服務並不是用戶迫切需要的,最後以失敗收場。
在一次機緣下,我遇到一群積極找我練習英文會話的人,也開始想怎麼樣可以幫助他們提升英文能力,意外開啟了我做英語教學的事業。我們把 YouTube 影片變成學習教材的方案,擄獲了一群死忠的用戶,用戶甚至成為我們的朋友,也自願幫我們做了很多工作、給我們很多回饋,讓我們優化產品,許多當時開發的功能,到今天都還是我們的核心服務。
這也印證了 Paul Graham 所說,「寧可做讓一小群用戶愛上的服務,也不要做一大群用戶都覺得一般的服務。」因為產品的競爭力會反應在用戶滿意度上,而用戶滿意度是很難優化到極致的,相較之下,爭取用戶則是相對容易的事。所以在創業初期一定要專注在用戶上,打造讓用戶愛上的產品。
.
.
『2 .在創業過程中,讓你最痛、也印象最深的一門教訓是什麼?』
#在用人上妥協,是我最深的教訓。
在公司成長快速的階段,事情越來越多,因為急著擴張解決事情,就用了最偷懶的方法 — 加人。因為許多是雜事或是日常營運,選人就也沒有太要求,能完成工作就好。但是後來才發現,團隊合作是乘法不是加法,因為太多事情是協作的且環環相扣,在一個環節上表現只有 60 分勉強及格,其實就會讓整個團隊的績效大打折扣。
另外,不對的態度也會影響到整個團隊。當有一個人只做 60 分又很悠哉的上班,卻沒有不好的後果,在旁邊拼盡全力的人就會萌生「自己為何而戰?」的想法,讓公司難以產生敬業的態度與文化。
後來我才理解,為何許多外商公司的員額抓這麼緊,而且寧可用更高的薪資請人,因為多增加一個人,其實是多增加一次的溝通成本,團隊越大溝通成本越高,效益其實是不會直線上升的。一樣的薪資總額,寧可是人力較精簡的菁英部隊、大家多負責一些事情;也不要請太多人、每人只負責少數的事。
在台灣因為薪資成本較國外低,所以台灣的企業主更容易犯這個錯誤,習慣增加勞力解決事情,不但讓組織臃腫沒有效率,也不會強迫自己把事情更自動化系統化,建立起可以規模化的企業組織架構。
.
.
『3. 有哪些難忘的特殊經歷,而塑造了現在的你?』
我一直很嚮往在國際化的環境工作,大學的時候去國外實習讓我更加確定方向,也打定主意要進外商公司工作,但是畢業後我在求職路上卻一路碰壁,超過半年找不到工作。
後來有一次透過別人介紹到了一家知名外商面試,面試我的長輩後來委婉的跟我說,我表現不錯,可是跟我一起爭取這個位子的人都是台大政大的同學,而我只有私立大學學歷,他若不選台大生選我,需要很強力能說服其他人的理由。我這才深刻體會職場的競爭以及自己的不足,也毅然決然決定出國進修,認真準備留學考試,很幸運進了哥倫比亞大學的研究所。
在哥大,我的同學有麥肯錫的分析師,有在華爾街工作的研究員,而我能跟他們一起討論個案,成績也不輸他們,也用課餘時間在紐約的瑞士銀行實習,這讓我有了信心,#我是有能力與各國的菁英競爭的。這也是為什麼我現在創業,也持續努力要把產品做到海外,我相信只要我們努力,我們一定能在國際舞台上擁有一席之地。
.
.
[本文作者]
Johhny 蔡豐任,英文學習平台 VoiceTube 的共同創辦人暨營運長,負責全球的產品運營,將科技與娛樂的元素結合,開發出創新的影音學習服務。
Johhny 是美國哥倫比亞大學作業研究碩士,畢業後曾於金融業擔任證券分析師及交易員。在觀察到行動網路興起的趨勢後,投入創業,並在教育科技領域找到自己的興趣與自己貢獻所長的機會。
VoiceTube 的使命是「讓所有人都能快樂的學習語言,進而與世界連結。運用獨家打造的演算法分析超過 10 萬部的影音內容,將真實的生活影音內容轉變為教材,每位用戶都能用最適合自己的內容學習,將外語融入生活與興趣中,有效提升語言能力。
https://www.voicetube.com/
#AppWorks #Startup #Founder #VoiceTube #創業者真心話