機器學習識別特徵阻絕代測 上鏈回送監理資料庫防竄改
人臉辨識加酒精鎖阻酒駕 串區塊鏈上傳比對告警
2021-05-24社團法人台灣E化資安分析管理協會元智大學多媒體安全與影像處理實驗室
本文將介紹酒精防偽人臉影像辨識系統,結合了人臉辨識、酒精鎖以及區塊鏈應用,以解決酒駕問題,並透過監控系統避免代測狀況發生。且利用區塊鏈不可修改的特性,將車輛與人臉資料串上區塊鏈,以確保駕駛人的不可否認性。
長長期以來「酒駕」都是一個很嚴肅且必須被重視的議題,儘管在2019年立法院修法酒駕及拒絕酒測的罰則,但是抱持僥倖心態的人還是數不勝數,導致因酒駕釀成車禍的悲劇還是一再重演,讓不少的家庭因此破滅。
據統計,從2015年到2018年的酒駕取締件數都逾10萬件,而因為酒駕車禍的死亡人數逾百人。在2019年酒駕新制上路以後,2020年警方酒駕取締件數有明顯下降至約6萬件,雖然成功達到嚇阻效果,但是死亡人數仍與去年前年持平,可見離完全遏止酒駕還有很長的路需要努力。
立法院於2018年三讀通過了「道路交通管理處罰條例部分條文修正案」,酒駕者必須重新考照,並且只能駕駛具有酒精鎖(Alcohol Interlock)的車輛,所謂酒精鎖,屬於車輛點火自動鎖定裝置,在汽車發動前必須進行酒測,通過才能將汽車發動,而且在每45分鐘至60分鐘後酒精鎖系統就會要求駕駛人在一定時間內進行重新酒測,以便防範在行車過程中有飲酒的情況發生,若駕駛人未遵守其要求,車子就會強制熄火並鎖死,必須回酒精鎖服務中心才能將鎖解開。
由於法案的方式無法完全遏止酒駕,因此許多創新科技或是企業致力於研究相關科技來解決酒駕的問題。
其中本田(Honda)汽車與日立(Hitachi)公司研發出手持型酒精含量檢測裝置,讓駕駛人必須在駕駛之前都先進行酒測,若酒精濃度超標就會將汽車載具上鎖,藉此避免酒駕意外或事故發生,且該技術結合了智慧鑰匙功能,若偵測到酒測值超標,車輛中的顯示面板將會發出警告訊號告知駕駛人,避免酒駕上路之問題。
另一方面則是解決酒精殘值之問題,因為有許多駕駛人都會認為,休息一下後,身體也無感到不適,即駕車出門,等到駕駛人被警方臨檢時才知道酒測未通過,因此收到罰單,甚至是吊銷駕照處罰等。
根據醫學研究指出,酒精是在人體體內由肝臟代謝,實際代謝時間必須看體質以及飲酒量而定。台灣酒駕防制社會關懷協會建議,喝酒後至少要10至20小時後再駕車比較安全。多數人無具備酒精代謝時間的觀念,導致駕駛人貿然上路,待意外發生或罰單臨頭時,已經為時已晚。
背景知識說明
本文介紹的方法為酒精鎖結合攝影鏡頭進行人臉辨識,並將人臉特徵資料與車輛資料串上區塊鏈,並利用區塊鏈不可篡改的特性,來避免駕駛人在解鎖酒精鎖時發生他人代測的問題。
由於人臉辨識技術具備防偽性、身分驗證的特性,因此將酒精鎖的技術結合人臉辨識,便可確認為駕駛本人。
何謂人臉辨識
人臉辨識技術屬於生物辨識的一種,基於人工智慧、機器學習、深度學習等技術,將大量人臉的資料輸入至電腦中做為模型訓練的素材,讓電腦透過演算法學習人類的面部特徵,藉以歸納其關聯性最後輸出人臉的特徵模型。
目前人臉辨識技術已經遍佈在日常生活之中,其應用面廣泛,最為常見的應用即為智慧型手機的解鎖、行動支付如LINE Pay、Apple Pay等,其他應用還包括行動網路銀行、網路郵局、社區大樓門禁管理系統、企業監控系統、機場出入關、智能ATM、中國天眼系統等。一般來說,人臉辨識皆具備以下幾個特性:
‧ 普遍性:屬於任何人皆擁有的特徵。
‧ 唯一性:除本人以外,其他人不具相同的特徵。
‧ 永續性:特徵不易隨著短時間有大幅的改變。
‧ 方便性:人臉辨識容易實施,設備容易取得,如相機鏡頭。
‧ 非接觸性:不須直接接觸儀器,也可以進行辨識,這部分考量到衛生問題以及辨識速度。
人臉辨識透過人臉特徵的分析比對進行身分的驗證,別於其他生物辨識如虹膜辨識、指紋辨識,無須近距離接觸,也可以精準地辨識身分,且具有同時辨識多人的能力。因應新冠肺炎疫情肆虐全球,人臉辨識技術也被用來管理人來人往的人流。人臉辨識的儀器可以搭配紅外線攝影機來測量人體體溫,在門禁進出管制系統中,利於提高管理效率,有效掌握到進出人員的身分,以及幫助衛生福利部在做疫調時更容易掌握到確診病患行經的足跡。
人臉辨識的步驟
人臉辨識的過程與步驟,包括人臉偵測、人臉校正、人臉特徵值的摘取,進行機器學習與深度學習、輸出人臉模型,從影像中先尋找目標人臉,偵測到目標後會將人臉進行預處理、灰階化、校正,並摘取特徵值,接著人臉資料交給電腦進行機器學習與深度學習運算,最後輸出已訓練好的模型。相關辨識的步驟,如圖1所示。
人臉偵測
基於Haar臉部檢測器的基本思想,對於一個一般的正臉而言,眼睛周圍的亮度較前額與臉頰暗、嘴巴比臉頰暗等其他明顯特徵。基於這樣的模式進行數千、數萬次的訓練,所訓練出的人臉模型,其訓練時間可能為幾個小時甚至幾天到幾周不等。利用已經訓練好的Haar人臉特徵模型,可以有效地在影像中偵測到人臉。
Python中的Dilb函式庫提供了訓練好的人臉模型,可以偵測出人臉的68個特徵點,包括臉的輪廓、眉毛、眼睛、鼻子、嘴巴。基於這些特徵點的資料就能夠進行人臉偵測,如圖2~4所示。圖中左上角的部分是偵測到的分數,若分數越高,代表該張影像就越可能是人臉,右側括弧中的編號代表子偵測器的編號,代表人臉的方向,其中0為正面、1為左側、2為右側。
人臉的預處理
偵測到人臉後,要針對圖片進行預處理。通常訓練的影像與攝影鏡頭拍出來的照片會有很大的不同,尤其會受到燈光、角度、表情等影響,為了改善這類問題,必須對圖片進行預處理以減少這類的問題,其中訓練的資料集也很重要:
‧ 幾何變換與裁剪:將影像中的人臉對齊與校正,將影像中不重要的部分進行裁切,並旋轉人臉,並使眼睛保持水平。
‧ 針對人臉的兩側用直方圖均衡化:可以增強影像中的對比度,可以改善過曝的影像或是曝光不足的問題,更有效地顯示與取得人臉目標的特徵點。
‧ 影像平滑化:影像在傳遞的過程中若受到通道、劣質取樣系統或是受到其他干擾導致影像變得粗糙,藉由使用圖形平滑處理,可以減少影像中的鋸齒效應和雜訊。
人臉特徵摘取
關於人臉特徵摘取,相關的技術說明如下:
‧ 歐式距離:人臉辨識是一個監督式學習,利用建立好的人臉模型,將測試資料和訓練資料進行匹配,最直觀的方式就是利用歐式距離來計算所有測試資料與訓練資料之間的距離,選擇差距最小者的影像作為辨識結果。由於人臉資料過於複雜,且需要大量的訓練集資料與測試集資料,會導致計算量過大,使辨識的速度過於緩慢,因此需要透過主成分分析法(Principal Components Analysis,PCA)來解決此問題。
‧ 主成分分析法:主成分分析法為統計學中的方法,目的是將大量且複雜的人臉資料進行降維,只保留影像中的主成分,即為影像中的關鍵像素,以在維持精確度的前提下加快辨識的速度。先將原本的二維影像資料每列資料減掉平均值,並計算協方差矩陣且取得特徵值與特徵向量,接著將訓練集與測試集的資料進行降維,讓新的像素矩陣中只保留主成分,最後則將降維後的測試資料與訓練資料做匹配,選擇距離最近者為辨識的結果。由於影像資料經過了降維的步驟,因此人臉辨識的速度將會大幅度地提升。
‧ 卷積神經網路:卷積神經網路(Convolutional Neural Network,CNN)是一種神經網路的架構,在影像辨識、人臉辨識至自駕車領域中都被廣泛運用,是深度學習(Deep Learning)中重要的一部分。主要的目的是透過濾波器對影像進行卷積、池化運算,藉此來提取圖片的特徵,並進行分類、辨識、訓練模型等作業。在人臉辨識的應用中,首先會輸入人臉的影像,再透過CNN從影像提取像素特徵並轉換成特定形式輸出,並用輸出的資料集進行訓練、辨識等等。
何謂酒精鎖
酒精鎖(圖5)是一種裝置在車輛載體中的配備,讓駕駛人必須在汽車發動前進行酒測,通過後才能將車輛發動。且每隔45分鐘至60分鐘會發出要求,讓駕駛人在時間內再次進行檢測。
根據歐盟經驗,提高罰款金額以及吊銷駕照只有在短期實施有效,只有勸阻的效果,若在執法上不夠嚴謹,被吊照者會轉變成無照駕駛,因此防止酒駕最有效的方法就是強制讓駕駛人無法上路,這就是「酒精鎖」的設計精神。
在本國2020年3月1日起酒駕新制通過後,針對酒駕犯有了更明確且更嚴厲的規定,在酒駕被吊銷駕照者重考後,一年內車輛要裝酒精鎖,未通過酒測者無法啟動,且必須上15小時的教育訓練才能重考,若酒駕累犯三次,要接受酒癮評估治療滿一年、十二次才能重考。
許多民眾對於「酒精鎖」議論紛紛,懷疑是否會發生找其他人代吹酒精鎖的疑慮,為防範此問題,酒精鎖在啟動後的五分鐘內重新進行吹氣,且汽車在行駛期間的每45至60分鐘內,便會隨機要求駕駛重新進行酒測,如果沒有通過測量或是沒有測量,整合在汽車智慧顯示面板的酒精鎖便會發出警告,並勸告駕駛停止駕車。
對於酒精鎖的實施,目前無法完全普及到每一台車子,而且對於沒有飲酒習慣的民眾而言,根本是多此一舉,反而增加不少麻煩給駕駛。若還有每45~60分鐘的隨機檢測,會導致多輛汽車必須臨時停靠路邊進行檢測,可能加劇汽車違規停車的發生頻率。
認識區塊鏈
區塊鏈技術是一種不依賴於第三方,透過分散式節點(Peer to Peer,P2P)來進行網路數據的存儲、交易與驗證的技術方法。本質上就是一個去中心化的資料庫,任何人在任何時間都可以依照相同的技術標準將訊息打包成區塊並串上區塊鏈,而這些被串上區塊鏈的區塊無法再被更改。區塊鏈技術主要依靠了密碼學與HASH來保護訊息安全,也是賦予區塊鏈技術具有高安全性、不可篡改性以及去中心化的關鍵。區塊鏈相關概念,如圖6所示。
區塊鏈的原理與特性
可以將區塊鏈想像成是一個大型公開帳本,網路上的每個節點都擁有完整的帳本備份,當產生一筆交易時,會將這筆交易廣播到各個節點,而每個節點會將未驗證的交易HASH值收集至區塊內。接著,每個節點進行工作量證明,選取計算最快的節點進行這些交易的驗證,完成後會把區塊廣播給到其他節點,其他節點會再度確認區塊中包含的交易是否有效,驗證過後才會接受區塊並串上區塊鏈,此時就無法再將資料進行篡改。
關於區塊鏈的特性,可分成以下四部分做說明:
1. 去中心化:區塊鏈其中一個最重要的核心宗旨,就是「去中心化」,區塊鏈採用分散式的點對點傳輸,該概念架構中,節點與節點之中沒有所謂的中心,所有的操作都部署在分散式的節點中,而無須部署在中心化機構的伺服器,一筆交易或資料的傳輸不再需要第三方的介入,因此又可以說每個節點就是所謂的「中心」。這樣的結構也加強了區塊鏈的穩定性,不會因為其中的部分節點故障而癱瘓整個區塊鏈的結構。
2. 不可篡改性:透過密碼學與雜湊函數的運用來將資料打包成區塊並上鏈,所有區塊都有屬於它的時間戳記,並依照時間順序排序,而所有節點的帳本資料中又記錄了完整的歷史內容,讓區塊鏈無法進行更改或是更改成本很高,因此使區塊鏈具備「不可篡改性」,並且同時確保了資料的完整性、安全性以及真實性。
3. 可追溯性:區塊鏈是一種鏈式的資料結構,鏈上的訊息區塊依照時間的順序環環相扣,這便使得區塊鏈具有可追溯的特性。可追本溯源的特性適用在廣泛的領域中,如供應鏈、版權保護、醫療、學歷認證等。區塊鏈就如同記帳帳本一般,每筆交易記錄著時間和訊息內容,若要進行資料的更改,則會視為一筆新的交易,且舊的紀錄仍會存在無法更動,因此仍可依照過去的交易事件進行追溯。
4. 匿名性:在去中心化的結構下,節點與節點之間不分主從關係,且每個節點中都擁有一本完整的帳本,因此區塊鏈系統是公開透明的。此時,個人資料與訊息內容的隱私就非常重要,區塊鏈技術運用了HASH運算、非對稱式加密與數位簽章等其他密碼學技術,讓節點資料在完全開放的情況下,也能保護隱私以及用戶的匿名性。
區塊鏈與酒精鎖
由於區塊鏈的技術具備去中心化、記錄時間以及不可篡改的特性,且更加強酒精鎖的檢測需要身分驗證的保證性。當進行酒精鎖檢測解鎖時,系統記錄駕駛人吹氣時間以及車輛的相關資訊,還有人臉特徵資料打包成區塊並串上區塊鏈。因此,在同一時間當監控系統偵測到當前駕駛人與吹氣人不同時,此時區塊鏈中所記錄的資料便能成為一個強而有力的依據,同時也能讓其他的違規或違法事件可以更容易進行追溯。
酒駕防偽人臉辨識系統介紹
為了解決酒精鎖發生駕駛人代測的問題,酒精鎖產品應導入具有身分驗證性的人臉辨識技術。酒駕防偽人臉辨識系統即為駕駛人在進行酒精鎖解鎖時,要同時進行人臉辨識,來確保駕駛人與吹氣人為同一人。
在駕駛座前方的位置會安裝攝影鏡頭,作為駕駛的監控裝置。進行酒測吹氣的人臉資料將會輸入到該系統中的資料庫儲存,並將人臉資料以及酒測的時間戳記打包成區塊串上區塊鏈,當汽車已經駛動時,攝影鏡頭將會將當前駕駛人畫面傳回系統進行人臉比對驗證。如果驗證成功,會將通過的紀錄與時間戳一同上傳至區塊鏈,若是系統偵測到駕駛人與吹氣人為不同對象,系統將發出警示要求駕駛停車並重新進行檢測,並同時將此次異常的情況進行記錄上傳到區塊鏈中。
如果駕駛持續不遵循系統指示仍持續行駛,該系統會將區塊鏈的紀錄傳送回給開罰的相關單位,並同時發出警報以告知附近用路人該車輛處於異常情況,應先行迴避。且該車輛於熄火後,酒精鎖會將車輛上鎖,必須聯絡酒精鎖廠商或酒精鎖服務中心才能解鎖。相關的系統概念流程圖,如圖7所示。
區塊鏈打包上鏈模擬
在進行酒測解鎖完畢以及進行人臉資料儲存後,會透過CNN將影像轉換輸出成128維的特徵向量作為人臉資料的測量值,接著將128個人臉特徵向量資料取出,並隨著車輛資訊一起打包到同一個區塊,然後串上區塊鏈。取出的人臉特徵資料,如圖8所示。
要打包成區塊和上鏈的內容,包括了人臉特徵資料、車牌號碼、酒測解鎖時間點等相關輔助資料,接著透過雜湊函數將相關的資料打包成區塊。以車牌號碼ABC-1234為例,圖9顯示將車輛資料和人臉資料進行區塊鏈的打包,並進行HASH運算。
將人臉資料和車輛相關資料作為一次的交易內容,並打包區塊,經過HASH後的結果如圖10所示,其中prev_hash屬性代表鏈結串列指向前一筆資料,由於這是實作模擬情境,並無上一筆資料,其中messages屬性代表內容數,一筆代表車牌資料,另一筆則為人臉資料。time屬性則代表區塊上鏈的時間點,代表車輛解鎖的時間點。
情境演練說明
話說小禛是一間企業的上班族,平時以開車為上下班的交通工具,他的汽車配置了酒駕防偽影像辨識系統,以下模擬小禛下班後準備開車的情境。
已經下班的小禛今天打算從公司開車回家,當小禛上車準備發動車子時,他必須先拿起安裝在車上的酒測器進行吹氣,並將臉對準攝影鏡頭讓系統取得小禛的人臉影像。小禛在汽車發動前的人臉影像,如圖11所示。
待攝影鏡頭偵測到小禛的人臉後,接著系統便會擷取臉上五官的68個特徵點,如圖12所示。然後,相關數據再透過CNN轉換輸出成128維的特徵向量作為人臉資料的測量值,如圖13所示。
酒精鎖通過解鎖後,車輛隨之發動,解鎖成功的時間點將會記錄成時間戳記,隨著影像與相關資料串上區塊鏈。在行駛途中,設置在駕駛座前方的鏡頭將擷取目前駕駛的人臉,以取得駕駛人的128維人臉特徵向量測量值,並且與汽車發動前所存入的人臉資料進行比對,藉以判斷目前的駕駛人與剛才的吹氣人臉是否為同一位駕駛。當驗證通過後,也會再將通過的紀錄與時間戳上傳至區塊鏈中,如此一來,區塊鏈的訊息內容便完整記載了這一次駕車的紀錄,檢測通過的示意圖如圖14所示。
系統通過辨識後,便確認了駕駛人的身分與吹氣人一致。且透過時戳的紀錄和區塊鏈的輔助,也確保了駕駛的不可否認性。若有其他違規事件發生時,區塊鏈的紀錄便成為一個強而有力的依據來進行追溯。
如此一來,便可以預防小禛喝酒卻找其他人代吹酒測器的情況發生。在駕駛的途中,如果有需要更換駕駛人,必須待車輛靜止時,從車載系統發出更換駕駛要求,再重新進行酒測以及重複上述流程,才可以更換駕駛人。如果沒有按照該流程更換駕駛,系統將視為異常情況。
結語
酒駕一直是全球性的問題,將有高機率導致重大交通事故,造成人員傷亡、家庭破碎,進而醞釀後續更多的社會問題,皆是酒駕所引發的不良效益。為了解決酒駕的問題,各個國家都有不同的酒駕標準或是法律規範,但是大部分國家的規範和制度都只有嚇阻作用卻無法完全遏止。在不同的國家防止酒駕的方式不盡相同,有的國家如新加坡,透過監禁及鞭刑來遏止酒駕犯,又或者是薩爾瓦多,當發現酒駕直接判定死刑,這樣的制度雖嚇阻力極強,但是若讓其他國家也跟進,會造成違憲或是違反人權等問題。因此,各國都在酒駕的問題方面紛紛投入研究,想要達到零酒駕的社會。
為達成此理想,本文介紹了基於區塊鏈的酒駕防偽辨識系統,利用酒精鎖搭配人臉辨識技術以及區塊鏈技術,使有飲酒的駕駛人無法發動汽車。且該系統搭載在行車電腦中,結合攝影鏡頭的監控對駕駛進行酒測防制管理,將人臉資料、酒精鎖、解鎖時間點與相關資訊打包成區塊並上鏈。基於區塊鏈技術內容的不易篡改,可加強駕駛人的不可否認性,當汽車發生異常情況時,便能利用有效且可靠的依據進行追溯。人工智慧和物聯網時代已經來臨,透過酒駕防偽辨識系統來改善酒駕問題,在未來能夠普及並結合法規,智慧汽車以及智慧科技的應用將會帶給人們更安全、更便利的社會。
附圖:圖1 人臉辨識的步驟。
圖2 人臉特徵點偵測(正臉)。
圖3 人臉特徵點偵測(左側臉)。
圖4 人臉特徵點偵測(右側臉)。
圖5 酒精鎖。 (圖片來源:https://commons.wikimedia.org/wiki/File:Guardian_Interlock_AMS2000_1.jpg with Author: Rsheram)
圖6 區塊鏈分散式節點的概念圖。
圖7 系統概念流程圖。
圖8 取出人臉128維特徵向量。
圖9 儲存車輛相關資料及人臉資料到區塊。
圖10 HASH後及打包成區塊的結果。
圖11 汽車發動前小禛的人臉影像。
圖12 小禛的人臉影像特徵點。
圖13 小禛的人臉特徵向量資料。
圖14 系統通過酒測檢測者與駕駛人為同一人。
資料來源:https://www.netadmin.com.tw/netadmin/zh-tw/technology/CC690F49163E4AAF9FD0E88A157C7B9D
雜湊函數特性 在 Taipei Ethereum Meetup Facebook 的精選貼文
📜 [專欄新文章] ELI5! 區塊鏈到底在幹嘛?
✍️ Juin Chiu
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
用生活化的例子輕鬆學會區塊鏈技術的重要概念
前言
我們熟知的世界正在慢慢地被區塊鏈技術瓦解與重建。不論背景,有愈來愈多人想對區塊鏈技術一探究竟,或許更進一步成為從業者、貢獻者或佈道者。
不幸的是,初學者若想學習區塊鏈技術,第一個問題可能會是高學習門檻,這是因為目前在各種主流平台上所流傳的區塊鏈知識或資源,都不免會大量使用艱澀的術語,長久以來便塑造出區塊鏈高大上的距離感,好似區塊鏈是只專屬於一小群駭客或者專業人士才能理解的技術。然而這是不準確的,事實上,區塊鏈技術中許多概念都能用一般常識理解,頂多只需要國小數學。
本文中,筆者將化繁為簡,試著把區塊鏈技術中的每個元素都使用生活化的例子比擬,讓區塊鏈愛好者與初學者不需用到密碼學/經濟學/資訊科學,也能領會區塊鏈技術的精髓之處。
本文將提及的概念如下:
什麼是帳本?
什麼是交易?
為什麼需要區塊?
有哪些共識機制?
區塊鏈安全嗎?
智能合約如何運作?
以下正文開始:
區塊鏈:一個公平的記錄系統
簡單來說,區塊鏈技術旨在打造一個去中心化的(Decentralized)狀態紀錄系統,更準確一點:區塊鏈技術旨在打造是一個追求真正「公平」的系統。
區塊鏈實現公平的關鍵在於:它完全仰賴自然法則運作,只透過一系列精細的規則就能保證系統的正確,這打破了人類社會一直以來的仰賴的中心化系統,使促成不平等的最大因素不復存在。
區塊鏈技術可以打造出具世界規模的去中心化運算平台,由數千甚至數萬個參與者共同維護狀態並提供計算資源。如果這個運算平台是應用在貨幣與資產的場景中,那麼這個平台可被稱為分散式帳本。
在接下來的段落,筆者將用一個例子展示一個極度精簡、只用紙跟筆的就可以運作的分散式帳本。在這個例子中,一群學生可以使用區塊鏈技術發行屬於他們自己的虛擬幣:「考卷幣」(Exam Paper Coin, EPC)。
考卷幣:使用區塊鏈技術發行的虛擬幣
考卷幣(EPC)是一種使用區塊鏈技術發行的虛擬幣,並存在於分散式帳本中。它的用途是為考卷加分,這將會吸引想考高分或者擔心被當的人學生持有。為什麼 EPC 只能被稱作虛擬幣,而不被稱作密碼貨幣?這是因為 EPC 的發行不會使用任何有關密碼學的技術,因此 EPC 嚴格來說不是密碼貨幣。
在分散式帳本被創建之初,沒有任何人擁有 EPC ,那麼 EPC 是怎麼「鑄造」與分配的?至少可以肯定的是,EPC 不能憑空產生,否則所有參與者就能不斷製造 EPC,使分散式帳本崩潰。事實上,EPC 的價值奠基於參與者的「付出」。
分散式帳本中最重要的角色非記帳者莫屬。每當記帳者成功完成工作,它便可以獲得固定數量的 EPC 作為報酬。於是,分散式帳本中的 EPC 便如此逐步地被鑄造出來。將 EPC 賦予具有貢獻的記帳者除了能夠公平分配 EPC,同時也是一種激勵機制(Incentivizing Mechanism),提供參與者維護帳本的動機。
那麼每個人所具有的 EPC 是怎麼記錄在帳本中的?
帳本: EPC 都要記錄下來
帳本即為依時間順序與特定格式記錄價值的系統。在分散式帳本中,每一批紀錄都會由某一個特定的「記帳者」維護,而記帳者會以特定的規則從所有的參與者中選出,因此分散式帳本是具有多個「記帳者」的系統。
為了確保能公平選出 EPC 的所有記帳者,分散式帳本不會使用任何記帳者的個人資訊,例如姓名、電話,做為帳本上的識別。記帳者可以自由地使用假名(Pseudonym)作為帳本上唯一的識別(Identifier),或者稱為地址(Address)。所以王小庭同學可以使用 Alice 這個假名,而且如果王小庭同學喜歡的話,他也可以同時使用 Bob 這個假名。
EPC 使用如下的格式記錄每個地址幣的數量:
Alice 100 EPCBob 0 EPCCharlie 0 EPCDavid 0 EPCEva 0 EPC
多數區塊鏈稱其識別為地址(Address),其為非對稱密碼學中公鑰(Public Key)的雜湊值(Hash)。地址具有統一的格式,例如以太坊的地址為長度 160 位元的 16 進位數字。
交易:把我的 EPC 轉移給別人
EPC 是可以轉移的,現在 Alice 可以將它持有的 100 EPC 中的 60 EPC 轉移給 Bob,以幫助 Bob 在下一次考試中免於被當。這樣的轉幣紀錄稱為交易(Transaction, Tx),可以如下表示:
Tx1
60 EPC, from [Alice] to [Bob]
而這筆交易會由 Alice 以上述格式記在紙條上,以 Tx1 表示。
簽章:讓參與者的所有動作都不可抵賴
EPC 的每個參與者的每個行為,例如交易,都必須附帶簽章(Signature),證明「這個動作確實是由我本人發起的」,簽署者不可抵賴,任何沒有附帶簽名的動作都是不被承認的。一個附帶簽名的交易紙條會像這樣:
Tx1
60 EPC, from [Alice] to [Bob], ALICE
簽章分為簽署(Sign)及驗證(Verify)兩個動作。驗證即是確認簽章是否確實是由行為發起者所簽署。在這個例子中,僅用一個簡單的驗證:若簽章與識別相符,則驗證成功。例如 Tx1 中,簽名 ALICE 確實與交易發起者 Alice 相符,因此驗證成功。
簽章就是區塊鏈的數位簽章(Digital Signature),其使用私鑰(Private Key)簽署,公鑰(Public Key)驗證,非常難以偽造。
訊息的散佈:怎麼讓所有參與者都收到訊息?
由於 Tx1 是由 Alice 發起的,因此 Alice 將於它自己的帳本記下這筆交易,接著 Alice 必須把這筆交易的內容也轉達所有的參與者,讓所有參與者皆具有所有的交易內容。
EPC 的參與者們不以口語,而是以傳紙條的方式互相交換訊息。紙條要如何有效率地傳播訊息給所有在教室中的參與者呢?可以使用「一傳十、十傳百」的策略。也就是:一次傳 10 張紙條給自己周圍的參與者,參與者收到後再抄寫 10 次後傳給周圍尚未收到該紀錄的其他參與者,逐步將訊息擴散致所有參與者。
這樣的傳播策略正如同流言被散佈的方式,因此也被稱為流言散佈協定(Gossip Protocol)。紙條傳播的網路就是對等網路(Peer-to-peer Network),紙條就是對等網路的封包(Packet)。關於對等網路的介紹,可以參考筆者日前的撰文:
隱私、區塊鏈與洋蔥路由
區塊:記錄一段時間內的交易順序
經過一段時間之後,每個 EPC 參與者手上都會有許多來自別的參與者的紙條,每張紙條都記載著不同的交易。在理想狀況下,如果所有參與者收到紙條的順序都相同,且每個參與者都收到了所有紙條,則所有參與者的帳本上的狀態,也就是餘額,都會相同。然而,若採用上述的訊息散佈策略,會發生兩種情況:每個參與者收到紙條的順序會不同,或者某些紙條可能會被遺漏。這些情況都會讓每個參與者的帳本產生差異,使帳本不可靠。而一個不可靠的帳本,不能作為貨幣發行的工具。
有沒有辦法能使所有 EPC 參與者用相同的交易順序記帳呢?這便是區塊鏈技術的奧秘之處。
為此,我們需要使用一個精心設計的結構:區塊(Block)。每個參與者皆會將一段時間內收到的交易紙條的編號,依照自己的順序寫在另一張紙條上,這張紙條就是區塊紙條,簡稱區塊,產出區塊的參與者則稱為區塊生產者。收到區塊紙條的其他參與者便會知道區塊生產者在這段時間內的交易順序。
為了要讓所有帳本都具有一致的狀態,EPC 的所有參與者必須要選出其中一個區塊作為所有參與者的共識(Consensus)。所有參與者都必須要遵照共識區塊的交易順序來更新自己的帳本,而這個區塊生產者就是記帳者。由於記帳者可以獲得報酬,因此在利益的驅使下,所有參與者都會努力生產區塊以爭取記帳權。
值得注意的是,每個區塊當中都會記錄前一個已達成共識的區塊的編號。例如接下來的範例,Bk15 的前一個已達成共識的區塊為 Bk3:
Bk15
Last Block: Bk3
Height: 15
Transactions:- Tx1- Tx5- Tx4- Tx10- Tx7- Tx13
Nonce: 1
Signature: CHARLIE
由於每個新的共識區塊都會指向前一個共識區塊,如此便會形成一條長鏈般的結構,已形成共識的區塊接成一條鏈,這就是區塊鏈(Blockchain)名稱的由來。
而當 EPC 參與者在收取共識的區塊後,將按照共識依序為每個交易內容進行帳本餘額的轉換。如此,所有的帳本都將具有一致的狀態。
依據特定輸入及轉換函數(Transition Function)執行狀態更新的系統,稱為狀態機複製(State Machine Replication)
摘要:濃縮紙條上的訊息
在介紹達成共識的方法前,筆者要先來介紹一個樸實無華但重要的概念:摘要(Digest),其顧名思義就是一段內容經過消化的產物。假設有一種摘要產生器,這個機器可以放入一張紙條,然後透過 3 個步驟計算出紙條的摘要。
摘要產生器將記載訊息的紙條切成一條一條固定寬度的細長條狀紙帶,如下圖:
2. 將這些紙帶依照順序接成一個長條紙帶。紙帶上有字跡的黑色部分與沒字跡的白色部分會出現不規則相間,測量每個黑色區塊之間相鄰的距離,如下圖:
3. 每段距離的數字相乘後的數字就是這個紙條的摘要(Digest)。
每個 EPC 參與者都會有一台摘要產生器,而它需要上緊發條才能開始工作,且每計算完一張紙條便須重新上一次發條。
摘要的計算雖然簡單,卻具有一些很有用的特性:
首先,摘要會隨著紙條內容的變動而更動。只要更動了任何一點紙條內容,例如區塊的交易順序,或者流水號(Nonce),都會使摘要改變。因此一個附上摘要的紙條,可以讓收到紙條的人在收到後再自行計算一次摘要並比對兩者,以驗證紙條的內容是否被修改過。因此,摘要是可驗證的(Verifiable)。
若想在不更動摘要的情況下同時變動紙條內容,只能不斷嘗試用不同內容產生摘要,直到發生碰撞(Collision) — 意即兩個不同內容的紙條出現相同摘要。
其次,摘要也是單向的:一個紙條很容易產出摘要,但摘要很難還原出原本的紙條內容。這也代表摘要是隨機且難以預測的,因此摘要可以作為一種亂數(Random Number)來源。
正式的區塊鏈使用更難預測且更不易碰撞的的密碼雜湊函數(Cryptograpgic Hash Function)產生訊息摘要。
理解關於區塊鏈技術的基本要件後,接下來就來看看區塊鏈技術的精妙之處:共識機制。
共識機制:如何達成共識?
在區塊鏈技術中,大致上有兩種方式可以產生共識:抽彩(Lottery)或表決(Vote),它們各自有不同特性,每一種分散式帳本都會使用其中之一作為共識機制。
抽彩
在抽彩機制中,唯有摘要小於門檻值的「合法」區塊才會被所有參與者收受。然而,區塊生產者無法預測摘要,且可驗證的摘要使區塊生產者難以作弊。因此若想生產數字小於門檻值的摘要,區塊生產者必須不斷改動區塊內容,例如流水號或者交易順序,直到找到摘要小於門檻值的區塊,就像抽彩一樣。只有合法的區塊才會被區塊生產者散佈給其他 EPC 參與者。
在這樣的規則下,可能會同時出現多個合法區塊。還記得區塊鏈中「鏈」的部分嗎?當收受多個低於門檻的區塊時,該選哪個區塊作為上一個區塊呢?這裡我們可以用一些簡單的規則來做抉擇:選擇合法區塊中高度(Height)最高的區塊,若高度一樣則選擇摘要數字較低的區塊。
區塊紙條的摘要就是正式區塊鏈中的區塊雜湊值。在正式的區塊鏈中,門檻值愈低,困難度(Difficulty)也愈高。區塊的選擇規則也稱為分岔選擇規則(Fork Choice Rule),使用可驗證的亂數作為共識的做法又稱為中本共識(Nakamoto Consensus)。
表決
有別於複雜的抽彩,表決機制相當直觀:所有參與者針對某個預先選出的領袖(Leader)的提案(Proposal),也就是區塊,進行投票。領袖是怎麼選出的?一個直覺的做法是按照假名的順序,按照 Alice / Bob / Charlie 的順序,所有參與者輪流擔任領袖。
所有參與者在收到提案後,可以選擇同意或反對這個區塊的內容,若同意的話,則將自己對提案的同意票記在紙條上,並將這個投票紙條散佈給所有其他參與者。若多數的參與者同意了提案,則所有參與者皆須認定該提案為共識。
然而,表決機制雖然直觀,卻不如抽彩具有可驗證性,參與者若想作弊則相對容易:例如,參與者可以重複投票,或者串通其他參與者一起不投票,以破壞帳本;另一方面,表決比抽彩來得有效率,因其不需要所有參與者都費功去製造可能將不被收受的區塊。
拜占庭錯誤(Byzantine Fault)特指這些不在預期內的行為,表決機制事實上也就是拜占庭容錯(Byzantine-fault-tolerant, BFT)演算法。PBFT 家族的協定是目前拜占庭容錯演算法的主流,然而其至多只能容忍不超過參與者總數一半的拜占庭錯誤。若想了解更多 PBFT 的細節,可以參考筆者日前的撰文:
若想搞懂區塊鏈就不能忽視的經典:PBFT
女巫:如何避免帳本被單一個體掌控?
上文提到:為了保證公平的記帳權,帳本上的識別都是假名,如上文提及,Alice 跟 Bob 實際上都是由同一個參與者王小庭所控制,其他參與者不僅難以得知,而且王小庭喜歡的話,他愛用幾個假名就用幾個假名 — 掌控多個假名的王小庭就成為了「女巫」(Sybil)。
不論是採取何種共識機制,女巫的存在都會破壞分散式帳本的安全性:
在抽彩機制中,如果多數的參與者皆由女巫控制,則女巫有很大的機會可以無視規則,不需抽彩便竄改帳本。
在表決機制中,如果由女巫控制的參與者可以集體進行不在預期內的行為,例如重複投票或者不投票。
因此,抵抗女巫對於分散式帳本的安全至關重要。對此,一個直覺的思路是:讓每個假名的行為都必須付出有限的資源,例如錢跟力。因此有兩種方式可以抵抗女巫:要嘛出錢,要嘛出力。
出力:在抽彩機制中,每個合法區塊的生產都必須附有低於門檻的摘要,而摘要的計算需要參與者出力不斷地重上發條。
出錢:在表決機制中,抵押一定數量 EPC 的參與者才能獲選為領袖被生產提案,且若違反規則,參與者的押金將會被沒收。
出力即是工作證明(Proof of Work, PoW);出錢即是權益證明(Proof of Stake, PoS),抵抗女巫的機制稱為抗女巫機制(Sybil-control Mechanism)。
合約:進行條件式的交易
回顧一下本文開頭所提:區塊鏈技術可以用來打造去中心化的運算平台,它可以用以記錄任何資訊,不止餘額,例如一段合約(Contract)。合約就是指一段會依據不同條件而達成不同執行結果的語句。例如:
CheckAndPay
給定 A、B 兩個假名,若 A 的餘額大於/等於 30 EPC,則 A 支付 20 EPC 給 B ,否則 A 不支付任何 EPC。
這個合約就可以被記錄在帳本中:
Alice 100 EPCBob 0 EPCCharlie 0 EPCDavid 0 EPCEva 0 EPCCheckAndPay "給定 A、B 兩個假名,若 A 的餘額大於/等於 30 EPC,則 A 支付 20 EPC 給 B ,否則 A 不支付任何 EPC。"
之後 Alice 就可以發起像這樣的交易:
Tx 99
CheckAndPay, {[Alice], [Bob]}, ALICE
如此,若 Alice 的 EPC 餘額不足 30 EPC 則不會支付 Bob。
觸發合約的 Tx 99 ,它的執行過程比較煩瑣:執行 Tx 99 的參與者首先會從帳本中尋找 CheckAndPay 的合約內容,並從 Tx 99 中取出合約需要的輸入:A 與 B,接著參與者再解讀合約的語句,依照條件進行帳本的狀態轉換。其中,為了使參與者能解讀合約,合約需用所有參與者皆能看懂的語言書寫。
合約又稱智能合約(Smart Contract)。正式的區塊鏈使用虛擬機(Virtual Machine)來解讀與執行合約。事實上,智能合約能做的事情非常多,這使具有智能合約功能的分散式帳本得以成為去中心化的運算平台,例如以太坊(Ethereum)。
總結: 分散式帳本究竟是一個怎樣的系統?
如果以上環節皆運作順利,那麼便能成功只用紙筆便發行了專由學生使用的貨幣。最後再次強調一次:這是一個為了便於使初學者掌握核心觀念而極度簡化的例子。正式運行的區塊鏈,例如以太坊,其實際運作遠遠複雜得多。
還有一些比較進階的概念,雖然礙於篇幅未在此文章提及,但部分主題筆者曾撰文介紹:
可擴展性(Scalability):第二層方案(Layer 2)與分片(Sharding)
隱私(Privacy)與匿名(Anonymity)
共識機制的安全性(Safety)與活躍性(Liveness)
最後,如果日後朋友/家人問起「什麼是區塊鏈」時,我想你會知道如何解釋了:)
ELI5! 區塊鏈到底在幹嘛? was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
雜湊函數特性 在 Taipei Ethereum Meetup Facebook 的精選貼文
📜 [專欄新文章] 瞭解神秘的 ZK-STARKs
✍️ Kimi Wu
📥 歡迎投稿: https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
上一篇關於 zkSNARK扯到太多數學式,導致很難入手,這次介紹 STARK 會盡量減少數學式,以原理的方式跟大家介紹。
STARK 被視為新一代的 SNARK,除了速度較快之外,最重要的是有以下好處1. 不需要可信任的設置(trusted setup),以及
2. 抗量子攻擊
但 STARK 也沒這麼完美,STARK 的證明量(proof size)約 40–50KB,太佔空間,相較於 SNARK 只有288 bytes,明顯大上幾個級距。此外,這篇論文發佈約兩年的時間,就密碼學的領域來說,還需要時間的驗證。
STARK 的 S 除了簡潔(Succinct)也代表了擴展性(Scalable),而T代表了透明性(Transparency),擴展性很好理解,透明性指的是利用了公開透明的算法,可以不需要有可信任的設置來存放秘密參數。
SNARK 跟 STARK 都是基於多項式驗證的零知識技術。差別在於,如何隱藏資訊、如何簡潔地驗證跟如何達到非互動性。
快轉一下 SNARK 是如何運作的。
Alice 有多項式 P(x)、Bob有秘密 s,Alice 不知道 s、Bob 不知道 P(x)的狀況下,Bob 可以驗證P(s)。藉由同態隱藏(Homomorphic Hindings)隱藏Bob的 s → H(s),藉由 QAP/Pinocchio 達到了簡潔地驗證,然後把 H(s) 放到CRS(Common Reference String),解決了非互動性。細節可以參考之前的文章 。
問題轉換
零知識的第一步,需要先把「問題」轉成可以運算的多項式去做運算。這一小節,只會說明怎麼把問題轉成多項式,至於如何轉換的細節,不會多琢磨。
問題 → 限制條件 → 多項式
在 SNRAK 跟 STARK 都是藉由高維度的多項式來作驗證。也就是若多項式為: x³ + 3x² + 3 = 0,多項式解容易被破解猜出,若多項式為 x^2000000 + x^1999999 + … 則難度會高非常多。
第一步,先把想驗證的問題,轉換成多項式。
這邊以Collatz Conjecture為例子,什麼是Collatz Conjecture呢?(每次都用Fibonacci做為例子有點無聊 XD)
1. 若數字為偶數,則除以2
2. 若數字為奇數,則乘以3再加1 (3n+1)
任何正整數,經由上述兩個規則,最終結果會為 1 。(目前尚未被證明這個猜想一定成立,但也還未找出不成立的數字)
52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.
把每個運算過程的結果紀錄起來,這個叫做執行軌跡(Execution Trace),如上述52 -> 26 -> … -> 1。接著我們把執行軌跡轉換成多項式(由執行軌跡轉成多項式不是這裡的重點,這裡不會贅述,細節可以參考 StarkWare的文章 )如下
https://medium.com/starkware/arithmetization-i-15c046390862
合成多項式
接著就把這四個限制條件的多項式合成為一個,這個最終的多項式就叫做合成多項式(composition polynomial),而這個合成多項式就是後面要拿來驗證的多項式。
就像一開始提的,SNARK跟STARK都是使用高維度多項式,接著,來介紹STARK是藉由哪些方式,達到零知識的交換、透明性(Transparency)跟可擴展性(Scalability)。
修改多項式維度
這一步是為了後面驗證做準備的。在驗證過程使用了一個技巧,將多項式以2的次方一直遞減為常數項(D, D/2, D/4 … 1),大幅減低了驗證的複雜度。因此,需要先將多項式修改為2^n維度
假設上述的每個限制多項式(不是合成多項式喔)為Cj(x),維度為 Dj,D >= Dj 且 D 等於2^n,為了達到 D 維度,乘上一個維度(D -Dj)的多項式,
所以最終的合成多項式,如下
其中的αj、βj是由驗證者(verifier)所提供,所以最終的多項式是由證明方(prover)跟驗證方所共同組成。
*這小節的重點是將多項式修改成D維度,覺得多項式太煩可忽略
FRI
FRI 的全名是”Fast RS IOPP”(RS = “Reed-Solomon”, IOPP = “Interactive Oracle Proofs of Proximity”)。藉由FRI可以達到簡潔地驗證多項式。在介紹FRI 之前,先來討論要怎麼證明你知道多項式 f(x) 為何?
RS 糾刪碼:
糾刪碼的概念是把原本的資料作延伸,使得部分資料即可以做驗證與可容錯。其方式是將資料組成多項式,藉由驗證多項式來驗證資料是否正確。舉例來說,有d個點可以組成 d-1 維的多項式 y = f(x),藉由驗證 f(z1) ?= y,來確定 z1是否是正確資料。
回到上面的問題,怎麼證明知道多項式?最直接的方式就是直接帶入點求解。藉由糾刪碼的方式,假設有d+1個點,根據Lagrange插值法,可以得到一個 d 維的多項式 h(x),如果如果兩個多項式在(某個範圍內)任意 d 點上都相同( f(z) = h(z), z = z1, z2…zd),即可證明我知道 f(x)。但是我們面對的是高維度的多項式,d 是1、2百萬,這樣的測試太沒效率,且不可行。FRI 解決了這個問題,驗證次數由百萬次變成數十次。
降低複雜度
假設最終的合成多項式為 f(x),藉由將原本的1元多項式改成2元多項式,以減少多項式的維度。假設 f(x) = 1744 * x^{185423},加入第二變數 y,使 y = x^{1000},所以多項式可改寫為 g(x, y) = 1744*x^{423}*y^{185}。藉由這樣的方式,從本來10萬的維度變成1千,藉由這種技巧大幅降低多項式的維度。在 FRI 目前的實做,是將維度對半降低 y = x²(f(x) = g(x, x²))。
此外,還有另一個技巧,將一個多項式拆成兩個較小的多項式,把偶數次方跟奇數次方拆開,如下:
f(x)= g(x²) + xh(x²)
假如:
f(x) = a0 + a1x + a2x² + a3x³ + a4x⁴ + a5x⁵
g(x²) = a0 + a2x² + a4x⁴, (g(x) = a0 + a2x + a4x²)
h(x²) = a1x + a3x² + a5x⁴, (h(x) = a1 + a3x + a5x² )
藉由這兩個方法,可以將高維度的多項式拆解,重複地將維度對半再對半,以此類推到常數項。而 FRI 協議在流程上包含兩階段 — 「提交」跟「查詢」。
提交階段:提交階段就如同上述過程,將多項式拆解後,由驗證者提供一亂數,組成新的多項式,再繼續對多項式拆解,一直重複。
f(x) = f0(x) = g0(x²) + x*h0(x²)
==> f1(x) = g0(x) + α0*h0(x), ← α0(驗證者提供)
==> f2(x) = g1(x) + α1*h1(x), ← α1(驗證者提供)
==> . . .
查詢階段:這個階段要驗證證明者所提交的多項式 f0(x), f1(x), f2(x), … 是否正確,這邊運用一個技巧,帶入任意數 z 及 -z(這代表在選域的時候,需滿足 L²= {x²:x ∊ L},這邊不多提)。所以可以得
f0(z) = g0(z²) + z*h0(z²)
f0(-z) = g0(z²) -z*h0(z²)
藉由兩者相加、相減,及可得g0(z²)、h0(z²),則可以計算出f1(z²),再推導出f1(x),以此類推驗證證明者傳來的多項式。
Interactive Oracle Proofs (IOPs)
藉由FRI(RS糾刪碼、IOPs),將驗證次數由數百萬降至20–30次(log2(d)),達到了簡潔地驗證。不過,我們解決了複雜度,但還有互動性!
* 與SNARK比較 :SNARK在驗證方面利用了QAP跟Pinocchio協定。
非互動性
藉由 Micali 建構(Micali construction)這個概念來解釋如何達到非互動的驗證。Micali 建構包括兩部分,PCPs(Probabilistically checkable proof)跟雜湊函數。PCPs 這是一個隨機抽樣檢查的證明系統。簡單來說,證明者產出一個大資料量的證明(long proof),經由隨機抽樣來驗證這個大資料量的證明。過程大約是這樣,證明者產出證明𝚿,而驗證者隨機確認 n 個點是否正確。
在STARK,我們希望達到:1.小的證明量,2.非互動。隨機抽樣可以讓達到小的證明量,那互動性呢? 想法很簡單,就是預先抽樣,把原本 PCPs 要做的事先做完,然後產出只有原本證明 𝚿 抽樣出的幾個區塊當作證明。但想也知道,一定不會是由證明者抽樣,因為這樣就可以作假。這裡是使用 Fiat-Shamir Heuristic 來作預先取樣。
首先,先把證明 𝚿組成 merkle tree,接著把 merkle root 做雜湊可得到一亂數 𝛒,而 𝛒 就是取樣的索引值。將利用𝛒取出來的區塊證明、區塊證明的 merkle tree 路徑跟 merkle root, 組一起,即為STARK 證明 𝛑。
到目前,只使用雜湊函數這個密碼學的輕量演算法。而雜湊函數的選擇是這個證明系統唯一的全域參數(大家都需要知道的),不像是 SNARK 有 KCA 使用的(α, β, 𝛾)等全域的秘密參數,再藉由 HH(同態隱藏)隱藏這些資訊來產生 CRS。因為證明的驗證是靠公開的雜湊函數,並不需要預先產生的秘密,因此 STARK 可以達到透明性,也不用可信任的設置。
接著,將FRI中需要互動的部分(驗證者提供 α 變數),使用上述的 PCP + Fiat-Shamir Heuristic, 即可達到非互動性。
* 與SNARK比較: SANRK 的非互動性是將所需的全域參數放到CRS中,因為全域參數是公開的,所以CRS裡的值使用了 HH 做隱藏。
MIMC
大部分證明系統,會使用算數電路來實作,此時,電路的複雜程度就關係到證明產生的速度。 STARK 的雜湊函數選用了電路複雜度較簡單的 MIMC,計算過程如下:
https://vitalik.ca/general/2018/07/21/starks_part_3.html
這樣的計算有另一個特性,就是無法平行運算,但卻又很好驗證,因此也很適合 VDF 的運算。Vitalik有一個使用 MIMIC 作為 VDF 的提案。
ps. 反向運算比正向慢百倍,所以會是反向計算,正向驗證
從上面的解釋,可以理解為什麼 STARK 不需要可信任設置,至於為什麼能抗量子?因為 SNARK 中使用了 HH 來隱藏秘密,而 HH 是依靠橢圓曲線的特性,但橢圓曲線沒有抗量子的特性(也就是可以從公鑰回推私鑰)。而STARK在整個過程中只使用了雜湊函數,而目前還沒有有效的演算法能破解雜湊函數,因此可以抵抗抗量子攻擊。
有錯誤或是不同看法,歡迎指教
參考:
StarkDEX Deep Dive: the STARK Core Engine
STARK 系列文:
STARK Math: The Journey Begins
Arithmetization I
Arithmetization II
Low Degree Testing
A Framework for Efficient STARKs
Vitalik 系列文:
STARKs, Part I: Proofs with Polynomials
STARKs, Part II: Thank Goodness It’s FRI-day
STARKs, Part 3: Into the Weeds
ZK-STARKs — Create Verifiable Trust, even against Quantum Computers
https://ethereum.stackexchange.com/questions/59145/zk-snarks-vs-zk-starks-vs-bulletproofs-updated
Originally published at http://kimiwublog.blogspot.com on November 12, 2019.
瞭解神秘的 ZK-STARKs was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
雜湊函數特性 在 資訊與網路安全概論:雜湊函數簡介 - YouTube 的推薦與評價
收視網站:http://www.tsnien.idv.tw/Security_WebBook/security.htm. ... <看更多>
雜湊函數特性 在 筆記- 加解密與數位簽章 - 魔法師的手杖 的推薦與評價
特性. 分成公鑰(public key)與私鑰(private key)。 ... 在做加密前,會先將原本的明文使用雜湊函數(hash function)轉成訊息摘要之後,然後再做加密。 ... <看更多>