亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于Monad的可認(rèn)證數(shù)據(jù)結(jié)構(gòu)

        2022-06-24 10:01:40賀新征祝躍飛
        關(guān)鍵詞:編譯器范疇語義

        賀新征 光 焱 祝躍飛

        1(中國人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué) 河南 鄭州 450001) 2(河南大學(xué)計(jì)算機(jī)與信息工程學(xué)院 河南 開封 475000)

        0 引 言

        可認(rèn)證數(shù)據(jù)結(jié)構(gòu)(Authenticated Data Structure)是基于Merkle[1]樹的二叉樹數(shù)據(jù)結(jié)構(gòu)。用戶從樹上獲得某個(gè)數(shù)據(jù)的同時(shí),還得到從根到數(shù)據(jù)的路徑信息,后者稱為證明流。依靠證明流能校驗(yàn)所獲得數(shù)據(jù)的真實(shí)性。例如,比特幣的超級(jí)賬本底層采用了Merkle樹結(jié)構(gòu),經(jīng)過實(shí)踐測試能有效防止中間人攻擊。Merkle樹啟發(fā)研究人員,按照鏈表、字典等方式組織的數(shù)據(jù)也可重新設(shè)計(jì)為基于Merkle樹的可認(rèn)證數(shù)據(jù)結(jié)構(gòu),但對(duì)每類非二叉樹結(jié)構(gòu)都需重新設(shè)計(jì)。

        Miller等[2]從Merkle樹中抽取出生成證明流和驗(yàn)證證明流的操作性語義,將兩者寫入編譯器,然后作為一種新的程序設(shè)計(jì)語言特性提供給編程人員,從而能讓非二叉樹數(shù)據(jù)結(jié)構(gòu)使用可認(rèn)證數(shù)據(jù)結(jié)構(gòu)進(jìn)行數(shù)據(jù)驗(yàn)證。這種實(shí)驗(yàn)性的方法是在OCaml編譯器上實(shí)現(xiàn)的。但不足之處是,研究人員在具體實(shí)施時(shí)需要掌握Hack OCaml和特定于OCaml編譯器的Camlp4語法樹轉(zhuǎn)換技術(shù),因此難以移植到其他編譯器中實(shí)現(xiàn)。

        本文采用一種更為抽象和凝練的基于范疇論的Monad技術(shù),通過將編譯器中一小部分操作性語義轉(zhuǎn)化為等價(jià)的指示性語義,可從編譯器中抽取出需要的語義將其轉(zhuǎn)化為目標(biāo)編譯器語言編碼的庫文件供程序員調(diào)用。因?yàn)镸onad適用于所有基于Hindley-Milner[3]類型推導(dǎo)系統(tǒng)函數(shù)式的編程語言,所以這種方法能推廣到所有這類編程語言編譯器。

        1 背 景

        1.1 研究背景

        文獻(xiàn)[2]首次提出將Merkle樹證明語義寫入到編譯器的方法。文獻(xiàn)[4]全面分析和總結(jié)了ADS算法。文獻(xiàn)[5-6]從數(shù)字金融領(lǐng)域的實(shí)踐角度,介紹了使用ADS的Merkle樹創(chuàng)建區(qū)塊鏈的技術(shù)細(xì)節(jié)。在類型理論和范疇理論的交叉領(lǐng)域,已經(jīng)有很多學(xué)者對(duì)Monad理論和應(yīng)用進(jìn)行了深入的研究和討論。文獻(xiàn)[7]第一次從理論上通過范疇論的Monad將操作性語義等價(jià)翻譯為指示性語義。文獻(xiàn)[8-10]將Moggi的Monad理論逐步應(yīng)用到了ML系列的函數(shù)式編程語言,范疇論因此正式成為OCaml和Haskell語言的重要理論基礎(chǔ)。文獻(xiàn)[11-12]對(duì)迄今為止的Monad概念的各種形式化和比喻性的解釋進(jìn)行了總結(jié)。文獻(xiàn)[13-14]對(duì)以操作性語義為主的類型理論進(jìn)行綜合講解,多數(shù)程序設(shè)計(jì)語言都是基于其中理論語言系統(tǒng)F或Fw進(jìn)行二次開發(fā)。文獻(xiàn)[15-17]分別從程序員角度、計(jì)算理論角度和范疇論專家角度對(duì)與Monad緊密相關(guān)的函子、自然轉(zhuǎn)換和伴隨函子進(jìn)行了全面介紹。

        1.2 Merkle樹

        Merkle是一個(gè)帶有Hash指針的二叉樹,如圖1所示。葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù),非葉子節(jié)點(diǎn)存儲(chǔ)Hash指針。先計(jì)算兩個(gè)葉子節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)的哈希值,然后將結(jié)果存儲(chǔ)到父節(jié)點(diǎn)。如此反復(fù)計(jì)算,直到計(jì)算根節(jié)點(diǎn)左右孩子的哈希值,并將結(jié)果存儲(chǔ)到根節(jié)點(diǎn)中。Merkle樹最主要的優(yōu)點(diǎn)是能提供節(jié)點(diǎn)與Merkle樹關(guān)系的證明。例如,如果客戶向服務(wù)器提出數(shù)據(jù)d2的請(qǐng)求后,服務(wù)器向客戶端返回〈data,proof〉。

        proof=hash(h1,h2)+hash(h3,h4)+hash(d2)

        path=〈L;R〉

        如果客戶希望知道數(shù)據(jù)d2是否確實(shí)是Merkle樹的成員,可以從葉節(jié)點(diǎn)沿路徑〈L;R〉計(jì)算每個(gè)中間節(jié)點(diǎn)的哈希值,向上一直到根節(jié)點(diǎn),依次與證明流proof提供的哈希值進(jìn)行比對(duì)。

        圖1 Merkle樹沿著路徑〈L;R〉生成數(shù)據(jù)d2的證明流proof

        2 Monad理論框架和解釋

        來自范疇論的Monad是函數(shù)式編程語言中最抽象的概念之一。理論上的Monad概念是位于范疇論2-Category維度上,在編程語言的具體實(shí)踐中隱藏在functor中。已發(fā)表的研究Monad的文獻(xiàn)可分為面向純理論研究人員、面向編程應(yīng)用人員和面向理論應(yīng)用結(jié)合人員三類。本節(jié)選擇從理論與應(yīng)用相結(jié)合的角度來引入Monad的解釋。

        2.1 計(jì)算的一般化

        通常程序被認(rèn)為是函數(shù)。但計(jì)算機(jī)科學(xué)中的程序,與數(shù)學(xué)中的函數(shù)有很大區(qū)別。給定相同輸入,每次運(yùn)行程序可能會(huì)得到不同結(jié)果。例如,數(shù)學(xué)上的函數(shù)f(x)=x+1作為計(jì)算機(jī)中的程序運(yùn)行時(shí),可能會(huì)有以下幾類結(jié)果。

        (1) 如果輸入x=1,結(jié)果為2;如果程序在運(yùn)行時(shí),突然斷電則結(jié)果未知,記為⊥。結(jié)果集合B=f(A)+⊥。其中,+號(hào)表示OR的關(guān)系。

        (2) 如果輸入x=1,結(jié)果為2;如果得到計(jì)算結(jié)果,將結(jié)果打印到屏幕上。結(jié)果集合C=(f(A),S)=f(A)×S。其中,×表示AND關(guān)系,S表示輸出到屏幕。

        以上兩個(gè)例子說明,數(shù)學(xué)上的函數(shù)變?yōu)橛?jì)算機(jī)上的程序后,即便每次輸入固定數(shù)值,也可能會(huì)得到不同的輸出結(jié)果集合。為表示區(qū)別,將數(shù)學(xué)上函數(shù)稱為純函數(shù),將程序表示的函數(shù)稱為非純函數(shù),這兩類函數(shù)都有“計(jì)算”的概念。很容易看出絕大多數(shù)程序都是非純函數(shù)的計(jì)算。若能將計(jì)算概念一般化,即用一種數(shù)學(xué)公式統(tǒng)一數(shù)學(xué)上的純函數(shù)和程序的非純函數(shù)的表示,則能將數(shù)學(xué)和程序通過一般性計(jì)算連接起來。計(jì)算一般化的典型代表是范疇理論中的Monad。

        2.2 范疇和對(duì)象

        因?yàn)樽⒁獾綌?shù)學(xué)對(duì)象在映射時(shí)具有保留結(jié)構(gòu)的特點(diǎn),因此范疇論期望能抽象出數(shù)學(xué)結(jié)構(gòu)映射關(guān)系。例如,將范疇論應(yīng)用到編程語言的類型理論研究時(shí),可將數(shù)據(jù)類型類比為對(duì)象,類型之間的映射類比為態(tài)射。函數(shù)f1:int→int,f2:char→char和f3:float→float都有相似的結(jié)構(gòu)。果讓所有簡單數(shù)據(jù)類型從類型變量*={α,β,γ,…}中取值,那么上述三個(gè)函數(shù)具有統(tǒng)一的形式,即f:*→*。

        2.3 函 子

        定義2函子(Functor)

        并且滿足以下條件:

        (2)F1(id(A))=id(F0(A))。

        (3)F1(f°g)=F1(f)°F1(g)。

        2.4 自然轉(zhuǎn)換

        定義3自然轉(zhuǎn)換(Natural Transformation)

        自然轉(zhuǎn)換φ:F→G符合范疇論統(tǒng)一形式?→?,此時(shí)?表示的數(shù)學(xué)對(duì)象是函子。自然轉(zhuǎn)換表示“(映射后的)結(jié)構(gòu)1→(映射后的)結(jié)構(gòu)2”的兩個(gè)映射后結(jié)構(gòu)之間的轉(zhuǎn)換。如果將函子代入到自然轉(zhuǎn)換中,會(huì)得到一個(gè)抽象關(guān)系“(原始結(jié)構(gòu)→映射后的結(jié)構(gòu)1)→(原始結(jié)構(gòu)→映射后的結(jié)構(gòu)2)”。

        2.5 態(tài)射、函子和自然轉(zhuǎn)換的比喻

        2.6 純函數(shù)組合需滿足的屬性

        程序可由多個(gè)函數(shù)組成。程序的可組合性表示整個(gè)程序的行為由所構(gòu)成的每個(gè)函數(shù)決定。假設(shè),P=h°g°f構(gòu)成一個(gè)程序,令P1=h°g,P2=g°f,那么P1°f=h°P2=P。表示的含義是程序P可像搭積木一樣構(gòu)成,先挑選功能f,再與功能P1組合的結(jié)果,與先挑選功能P2再與功能h組合的結(jié)果是一樣的。因此,可組合的含義是功能可替換。在數(shù)學(xué)上純函數(shù)滿足可組合屬性的集合M,就是含幺半群(monoid)代數(shù)結(jié)構(gòu)(M,?,)。其中?表示某種組合操作,表示單位元。

        值得注意的是,含幺半群是非對(duì)稱代數(shù)結(jié)構(gòu),即沒有屬性g°f≠f°g。這種特性恰好滿足編程時(shí)函數(shù)調(diào)用順序的要求,即一個(gè)函數(shù)序列不同調(diào)用順序生成不同結(jié)果。如果將數(shù)據(jù)當(dāng)做對(duì)象,函數(shù)當(dāng)做態(tài)射,程序非常像一種含幺半群代數(shù)結(jié)構(gòu)。

        2.7 非純函數(shù)的組合性問題

        任意程序都能當(dāng)作函數(shù),從兩個(gè)已有函數(shù)可以組合出新函數(shù)。函數(shù)組合的要求是前一個(gè)函數(shù)的值域等于后一個(gè)函數(shù)的定義域。實(shí)際情況是,并非每個(gè)函數(shù)的輸入都能恰好映射到函數(shù)的輸出中,會(huì)產(chǎn)生一些附加行為或數(shù)據(jù)。例如,將數(shù)據(jù)寫入文件,數(shù)據(jù)輸出到屏幕。這類附加行為稱之為計(jì)算效果(computation effective),此類函數(shù)稱為非純函數(shù)。類比純函數(shù),非純函數(shù)能夠組合必須滿足兩個(gè)條件,一是要具備模擬純函數(shù)的單位函數(shù)(identity function),二是要具備自定義的兩個(gè)函數(shù)的組合規(guī)則。

        Moggi觀察到所有非純函數(shù)都有一樣的稱為Monad的計(jì)算結(jié)構(gòu)。如果輸入數(shù)據(jù)為A,將所有在此結(jié)構(gòu)上函數(shù)操作的集合統(tǒng)稱為T。那么輸出結(jié)果要么就是TA,恰好是所有對(duì)應(yīng)于輸入為A的、純函數(shù)集合為T的輸出結(jié)果的集合。要么輸出結(jié)果是TB,表示輸出結(jié)果對(duì)應(yīng)于所有輸入為B的、所有純函數(shù)集合為T的輸出結(jié)果的集合(如圖2所示)。如果比較TA與TB輸出結(jié)果的大小,TB比TA多出來的數(shù)據(jù)結(jié)果是TB具備的而TA所沒有的行為結(jié)果,就是所謂的計(jì)算效果。如果f:A→TB與g:B→TC進(jìn)行組合,只需要將g的定義域B擴(kuò)大為TB,同時(shí)將g的陪域擴(kuò)大為TTB即可。因此,常有術(shù)語稱Monad進(jìn)行了兩次擴(kuò)展。準(zhǔn)確的Monad數(shù)學(xué)定義見下節(jié)。

        圖2 如果TB≠B則無法組合函數(shù)

        2.8 Monad的數(shù)學(xué)定義與解釋

        Monad有兩種范疇論的解釋性定義。需要指出,由于Monad是位于2-Category維度,所以試圖繪制或想象出某個(gè)Monad內(nèi)部結(jié)構(gòu)是非常困難的事情。如果將Monad想象為一個(gè)球體,準(zhǔn)確描述球體內(nèi)部到底具體包含哪些態(tài)射和對(duì)象是非常困難的。但通過建立一套準(zhǔn)則只測試球體外部所表現(xiàn)出行為,同樣能間接確定球體內(nèi)部所有成員的共同屬性。

        2.8.1兩種Monad定義形式

        圖3 Eilenberg-Moore解釋的Monad含義

        如果輸入數(shù)據(jù)為A,則ηA:A→TA,μA:T2A→TA。對(duì)應(yīng)到函數(shù)式編程語言中的monad,η就應(yīng)為return(ret)操作,而μ對(duì)應(yīng)為join操作。第一種解釋便于理解Monad,但不便于具體編碼實(shí)現(xiàn),主要是因?yàn)閖oin操作異于編程人員對(duì)函數(shù)組合的一般性理解。

        非純函數(shù)f:A→TB和g:B→TC內(nèi)部是什么具體數(shù)學(xué)形式并不重要,重要的是前一個(gè)函數(shù)的值域與后一個(gè)函數(shù)的定義域相同。T是范疇論中的函子,表示計(jì)算,它可看作是把一種結(jié)構(gòu)映射到另外一種結(jié)構(gòu)的函數(shù)。Eilenberg-Moore的解決思路是:

        (1) 先同時(shí)擴(kuò)大g的定義域與值域,即T(g):T(B)→T(TC)。如果將T(g)簡記為Tg,T(TC)記為T2C,則有Tg:TB→T2C。目的是保證前一個(gè)函數(shù)的值域與后一個(gè)函數(shù)的定義域相同。

        (2) 由于擴(kuò)充g后值域變?yōu)榱薚2C,因此需要通過自然轉(zhuǎn)換μ讓T2C變?yōu)門C,即μC:T2→TC。

        圖4 Kleisli條件滿足的兩個(gè)等式ηA=idTA和f*° ηA=f

        (4) 如果存在f*:TA→TB,必定存在f:A→TB。是Keisli的擴(kuò)展推論,常稱為lift(f)操作,記為f*。f*就是函數(shù)式編程語言中Monad的bind(>>=)操作。

        假設(shè)有函數(shù)f:A→TB和g:B→TC,Kleisli的定義下g*°f*=(g*°f)*。其中f*:A→B表示純函數(shù),f:A→TB表示非純函數(shù),f*:TA→TB表示lift就是函數(shù)式編程語言中的bind函數(shù)(如圖5所示)。如果要計(jì)算g°f就先要將f提升為f*,g提升為g*,因此實(shí)際計(jì)算的是g*°f*。

        圖5 Klesili函數(shù)組合的解釋

        2.8.2Monad計(jì)算的解釋

        非純函數(shù)的值域難以確切表示,因?yàn)椴煌?jì)算方式會(huì)產(chǎn)生不同值域集合。一種較為容易理解的觀點(diǎn)是,計(jì)算就是value-set形式,即輸入一組數(shù)據(jù)集合生成結(jié)果集合。這種觀點(diǎn)下,計(jì)算的結(jié)果是集合。但如果將計(jì)算理解為value-function的形式,即輸入一組數(shù)據(jù)生成一種適合某種類型集合的計(jì)算,則計(jì)算的結(jié)果是另外某個(gè)計(jì)算。

        例如,函數(shù)f(x,y)=x+y。當(dāng)輸入x=1時(shí),結(jié)果是另外一個(gè)函數(shù),即g(y)=f(1,y)=1+y,這是一種value-function的形式。由函數(shù)g(y)能產(chǎn)生結(jié)果集合,而一旦確定y的具體數(shù)值,結(jié)果必定在此集合中。因此,函數(shù)產(chǎn)生了結(jié)果集合,結(jié)果集合就能用函數(shù)表示。從這個(gè)角度來看,函數(shù)就是數(shù)據(jù)。

        如圖5所示,由于函數(shù)就是數(shù)據(jù),因此生成的數(shù)據(jù)集合記為TB。如果B=A,生成的數(shù)據(jù)就是TA,表示A→TA。抽象出代數(shù)結(jié)構(gòu)變?yōu)?1→T)(A),其中(1→T)就是抽象代數(shù)結(jié)構(gòu),A表示輸入的數(shù)據(jù)集合。丟掉具體的A,保留下的(1→T)就是?→?形式。因?yàn)門是函子,所以1→T必定是自然轉(zhuǎn)換,命名為η:1→T??煽闯靓俏ㄒ蛔龅氖虑槭菍原樣輸出為TA。此時(shí)η類似于編程中經(jīng)常需要的空操作,例如已經(jīng)計(jì)算出函數(shù)結(jié)果,再計(jì)算一次仍舊是原結(jié)果。

        對(duì)于生成數(shù)據(jù)操作T如果能組合,就應(yīng)該滿足類似于含幺半群的代數(shù)結(jié)構(gòu)。前面已經(jīng)找到單位操作η:1→T,類似必須還要有組合操作滿足μ:T×T→T,簡記為μ:T2→T。由于T是函子,所以μ必定是自然轉(zhuǎn)換??疾炱渲械慕M合,μB:T2B→TB。結(jié)合上面分析就有,μB°Tf°ηA:A→TB,而因?yàn)閒:A→TB,因此μB°Tf°ηA=f。

        上述代數(shù)結(jié)構(gòu)就是Monad,記為(T,η,μ)。與含幺半群(M,?,1)對(duì)比,兩者都具有?→?的結(jié)構(gòu)。對(duì)于含幺半群來說,?對(duì)象是集合,→是函數(shù)。對(duì)于Monad來說,?對(duì)象是函數(shù)表示的集合(即將計(jì)算當(dāng)作對(duì)象),而→則是從一種計(jì)算結(jié)構(gòu)到另外一種計(jì)算結(jié)構(gòu)的映射,即自然轉(zhuǎn)換。Monoid的底層結(jié)構(gòu)是集合,它可將純函數(shù)組合;Monad通過一般化計(jì)算,將函數(shù)當(dāng)做數(shù)據(jù)對(duì)待,可將非純函數(shù)組合。因此,常稱Monad是在自函子上的含幺半群代數(shù)結(jié)構(gòu),實(shí)現(xiàn)了一般性計(jì)算的函數(shù)組合操作。

        2.9 操作性語義到指示語義的轉(zhuǎn)換

        文獻(xiàn)[9-10,12,18]從純編程角度解釋Monad,而不涉及任何范疇論和類型理論討論。然而,為了將操作性語義轉(zhuǎn)換為指示性語義,仍然需要借助一些類型理論和范疇論知識(shí)。在基于λ演算的類型理論看來,數(shù)學(xué)中的純函數(shù)f(x)和g(x),用λ演算可表示為f(x)=λx.e1和g(x)=λx.e2,e1和e2表示任意表達(dá)式。數(shù)學(xué)中的純函數(shù)組合h(x)=(g°f)(x),根據(jù)λ演算的β法則可表示為h(x)=(λx.e1)[e2/x],[e2/x]表示用e2替換表達(dá)式e1中出現(xiàn)的所有非自由變量x。在正式的ML系列編程語言編譯器的實(shí)現(xiàn)中,λ表達(dá)式的語法為f(x)=funx→e1,β法則一般用可讀性較好的正式語法letx=e2ine1表示。因此,數(shù)學(xué)中的純函數(shù)組合h(x)就可以編碼為λ表達(dá)式,即h(x)=(funx→e1)e2,等價(jià)于用let…in…編碼為了h(x)=lety=e2ine1。

        但非純函數(shù)f:A→TB和g:B→TC無法直接組合為h:A→TC,因?yàn)閒的陪域?yàn)門B,而g的定義域?yàn)锽,TB≠B。所以,意味著非純函數(shù)無法直接編碼為λ表達(dá)式或let語句,因?yàn)閮蓚€(gè)非純函數(shù)無法直接組合。解決問題的關(guān)鍵在于要先將類型理論中的類型映射到范疇論的對(duì)象上,將類型理論中的函數(shù)映射到范疇理論中的態(tài)射上,再通過范疇中的Kleisli范疇進(jìn)行非純函數(shù)的組合。

        (1) 將類型理論中的基本類型用范疇理論的對(duì)象解釋。例如,[[τ]]=τ。

        由于主要關(guān)心非純函數(shù)的組合問題,因此簡化為只考慮類型理論中的非純函數(shù)如何用Kleisli范疇表示。如圖所示,左邊是先前的Kleisli范疇,右圖是將操作性語義對(duì)應(yīng)到指示性語義。其中類型α對(duì)應(yīng)到范疇論的對(duì)象A,類型αt對(duì)應(yīng)到范疇論的對(duì)象TA。類型理論中的表達(dá)式e1和e2對(duì)應(yīng)到范疇論中的態(tài)射。在Klesili中非純函數(shù)f轉(zhuǎn)換為純函數(shù)f*的操作就是bind(也稱為lift,或>>=),即f*=bindηAf。與之對(duì)應(yīng),將操作性語義轉(zhuǎn)換后的指示性語義后,就把原來將帶有效果的函數(shù)λx.e1轉(zhuǎn)化為不帶效果可以組合的函數(shù),用let語句表示就是[[letx=e1ine2]]=bind[[x]][[λx.e1]],如圖6所示。

        圖6 用Klesili轉(zhuǎn)化為指示性語義

        3 核心代碼分析

        核心代碼是把Miller等定義的auth和unauth語義進(jìn)行Monad轉(zhuǎn)換。以下分析過程中,其為了方便討論,并未將x:TB寫為準(zhǔn)確的OCaml的語法類型x:βt,默認(rèn)認(rèn)為在范疇論CCC的理論框架下,TB等價(jià)于類型理論的βt。范疇論中表示對(duì)象的{A,B,C,…}符號(hào)等價(jià)于類型論類型變量{α,β,γ,…}的符號(hào),兩者在以下討論中可以相互替代。

        3.1 Auth分析

        Auth是將經(jīng)過認(rèn)證數(shù)據(jù)的證明流proof寫入到磁盤上,因此auth程序的行為與write行為相似,屬于write monad。假設(shè)proof為加密后的字符串。為了方便討論,將其簡化為Σ*={a,b,c,…}形式,表示為所有字符組成的有限字符串序列。令表示空加密字符串,那么hash(a,b)就可以想象為兩個(gè)字符串之間的某種組合操作(例如,字符串按位異或操作)。將此操作定義為?,那么v=s?t就表示v是s和t的一種組合結(jié)果。

        proof≌Σ*={a,b,c,…}

        noproof≌=[]

        auth程序的行為可描述為輸入類型A的數(shù)據(jù),輸出結(jié)果為類型B的數(shù)據(jù),同時(shí)生成代表證明流proof的字符串Σ*,并將其寫入到磁盤上。Σ*是函數(shù)產(chǎn)生的效果。函數(shù)f可以表示為(假設(shè),TB=B×Σ*,TC=C×Σ*):

        f:A→TB=f:A→B×Σ*

        此時(shí)f(a)=(b,s)的含義是:如果輸入數(shù)據(jù)為a,那么f(a)表示在返回?cái)?shù)據(jù)b的同時(shí),將生成寫入磁盤的證明流s。為了能讓非純函數(shù)f(x)和g(x)可以組合,則必須滿足下面兩個(gè)條件才能構(gòu)成Monad。

        當(dāng)輸入為a時(shí),由單位函數(shù)定義可知,單位函數(shù)輸入和輸出結(jié)果應(yīng)保持一致,而且不會(huì)產(chǎn)生證明流,因此id(a)=(a,)。由圖3和圖6可知,id就是Monad中的ret。因此,ret(a)=(a,[])。與之對(duì)應(yīng)的OCaml代碼為let returna=(a,[])。

        當(dāng)輸入為a時(shí),令f(a)=(b,s)且g(b)=(b,t)。表示f產(chǎn)生結(jié)果b并生成證明流s。當(dāng)兩個(gè)函數(shù)組合時(shí),g需要輸入數(shù)據(jù)b,并產(chǎn)生證明流t,即(g°f)=(c,s?t)。

        (g°f)(a)

        1.≈ (λx.g)(f(a))

        2.≈ letx?f(a) ing(x)

        3.= letx:TB?f(a:A):TB

        ing(x:B):TC

        4.= letx:TB? (b,s):TB

        ing(x:B):TC

        5.= let (m,n):B×Σ*? (b,s):B×Σ*

        ing(x:B):TC

        6.= let (m:B?b:B,n:Σ*?s:Σ*):TB

        ing(x:B):TC

        7.=g(x:B?b:B):TC

        8.= (c,s?t)

        為了檢查數(shù)據(jù)類型是否保持一致,第3行開始添加數(shù)據(jù)對(duì)應(yīng)的類型。例如,x:TB表示變量x的數(shù)據(jù)類型是TB。從第6行到第7行后,數(shù)據(jù)s是否與數(shù)據(jù)t進(jìn)行?操作由g(x)的內(nèi)部實(shí)現(xiàn)確定,因此s應(yīng)出現(xiàn)在g(x)的具體代碼實(shí)現(xiàn)中。就具體示例來說,由于證明流是需要進(jìn)行Hash連接的,因此s?t確實(shí)進(jìn)行了字符串連接操作。

        與上述過程對(duì)應(yīng)的OCaml代碼實(shí)現(xiàn)如下。

        let (>>=) (prf,a) f= (*>>=表示Monad綁定*)

        let (prf′,b)=f a in (*lety=e2ine1*) (prf @ prf′,b) (*TB*)

        3.2 Unauth分析

        Unauth從磁盤上讀取經(jīng)過加密的數(shù)據(jù)流,根據(jù)Merkle樹從葉節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑逐個(gè)節(jié)點(diǎn)解密,如果解密后的證明流滿足Hash值要求,則接收,否則報(bào)錯(cuò)。unauth程序的行為類似于parser monad。與3.1節(jié)類似,為了方便討論引入Σ*表示證明流。unauth程序的行為可描述為輸入(A,Σ*)數(shù)據(jù)是product類型,結(jié)果滿足Hash運(yùn)算要求時(shí)輸出為(B,Σ*),否則程序輸出異常E。這表明輸出數(shù)據(jù)類型是sum類型數(shù)據(jù)(B,Σ*)+E。

        f:A→TB=f:A×Σ*→(B,Σ*)+E

        注意到等式左邊只有一個(gè)輸入?yún)?shù)A,而等式右邊輸入?yún)?shù)是A×Σ*,也就是左右兩邊的輸入?yún)?shù)不一樣。根據(jù)Curring定理可知(Homset表示態(tài)射集合):

        Homset(A×B,C)≌Homset(A,CB)

        令A(yù)×B=A×Σ*,C=(B,Σ*)+E,代入Curring展開公式則有:

        Homset(A×Σ*,(B,Σ*)+E)≌Homset(A,((B,Σ*)+E)Σ*)

        CB={Z|Z:B→C}表示所有從B到C的函數(shù)組成的態(tài)射Z。因此:

        f:A→TB=f:A→(Σ*→(B,Σ*)+E)

        即TB=Σ*→(B,Σ*)+E。將B代換為A結(jié)果不變,形式如下:

        f(A)=TA=Σ*→(A,Σ*)+E

        以下為了便于討論,仍舊使用f(a,s)的形式,而不采用Curring展開式。f(a,s1)=(b,s2)+failed含義是當(dāng)輸入數(shù)據(jù)類型a和對(duì)應(yīng)的證明流s1后,如果成功解析數(shù)據(jù)則得到數(shù)據(jù)b及其證明流s2,即(b,s2);否則,引起異常,輸出failed。為了能讓非純函數(shù)f(x)和g(x)可以組合,則必須滿足下面兩個(gè)條件才能構(gòu)成Monad。

        當(dāng)輸入為a時(shí),由單位函數(shù)定義可知,id(a,s1)=(a,s1)。因此,ret(a,s1)=(a,s1)。與之對(duì)應(yīng)的OCaml代碼let returna=funproof→′Ok(a,proof)。注意,代碼中使用了Uncurring形式,proof就是證明流。如果是兩個(gè)函數(shù)的組合,當(dāng)輸入為(a,s1)時(shí),令f(a,s1)=(b,s2)+E且f(b,s2)=(c,s3)+E,那么(g°f)(a,s1)=(c,s3)+E。

        形式為f(A)=A+B函數(shù)是sum類型,可用如下形式表示,語義等價(jià)于match…with…語句。函數(shù)組合可以如下進(jìn)行化簡。

        (g°f)(a,s1)

        1.≈ (λx.g)(f(a,s1))

        2.≈ letx?f(a,s1) ing(x,s2)

        3.= let matchf(a,s1) with

        | (b,s2)→g(x,s2)

        |E→failed

        最后一行通過match進(jìn)行分支跳轉(zhuǎn),跳轉(zhuǎn)后的代碼分析與3.1節(jié)相似,此處省略。與上述過程對(duì)應(yīng)的OCaml代碼實(shí)現(xiàn)如下。

        let (>>=) c f=

        fun prfs→

        match c prfs with

        |、ProofFailure→、ProofFailure

        |、Ok(prfs′,a)→f a prfs′

        3.3 實(shí)現(xiàn)Merkle樹和關(guān)鍵接口

        為了能將提取出的可認(rèn)證數(shù)據(jù)結(jié)構(gòu)的語義信息進(jìn)行編碼,首先要明確Functor和Monad在程序語言中的表現(xiàn)形式。在OCaml中Functor通過Modular實(shí)現(xiàn)。OCaml中Functor和Monad機(jī)制與Haskell有所區(qū)別,主要是因?yàn)镺Caml中沒有Higher-Kind數(shù)據(jù)類型,而Haskell有表現(xiàn)Higher-Kind數(shù)據(jù)類型的Type-Class。用Haskell實(shí)現(xiàn)代碼時(shí),要專門尋找在Haskell中對(duì)應(yīng)于Type-Class概念而設(shè)計(jì)的Functor和Monad機(jī)制。通過Modular機(jī)制將可認(rèn)證數(shù)據(jù)結(jié)構(gòu)抽象為簽名:

        module type AUTHENTIKIT=sig

        在創(chuàng)建表示新添加的可認(rèn)證數(shù)據(jù)類型時(shí),需通過類型構(gòu)造器創(chuàng)建auth類型,并將該類型提交給OCaml編譯器。按照編程方法的約定,此時(shí)只需要表現(xiàn)數(shù)據(jù)結(jié)構(gòu)的形式,而不需要有具體代碼實(shí)現(xiàn),也就是在AUTHENTIKIT中寫出所有要用到數(shù)據(jù)的抽象語法。

        可認(rèn)證計(jì)算需要生成證明流以供數(shù)據(jù)驗(yàn)證方使用。 在代碼實(shí)踐時(shí),原來的可認(rèn)證計(jì)算過程是運(yùn)用 Hack 技術(shù)通過 Campl4 直接寫入到 OCaml 編譯器 。 但通過Monad 可以將寫入到編譯器中的可認(rèn)證語義提取出來,如代碼段1所示。 第1行代碼定義了抽象可認(rèn)證計(jì)算類型,以參數(shù)多態(tài)形式表現(xiàn)。第2行定義了返回函數(shù),本質(zhì)就是η。第3行定義了 bind 操作, 本質(zhì)是定義了函數(shù)組合方式。

        代碼段1(可認(rèn)證計(jì)算的Monad接口):

        1. type ′a auth

        2. type ′a authenticated_computation

        3. val return: ′a->′a authenticated_computation

        4. val(>>=): ′a authenticated_computation->

        (′a->′b authenticated_computation)->

        ′b authenticated_computation

        在代碼中產(chǎn)生附加效果的數(shù)據(jù)類型用TA=′aτ表示,附加效果中含有需要的證明流和待驗(yàn)證數(shù)據(jù),而其中τ=authenticated_computation。數(shù)據(jù)綁定過程就是Monad理論中的μ合并數(shù)據(jù)過程,其中bind就是符號(hào)>>=,用公式表示是:

        bind:A→TB=(A→TA)→(B→TB)→(A→TB)

        如果令A(yù)=()單位輸入,則上述公式變?yōu)?

        bind:A→TB=(()→TA)→(B→TB)→(()→TB)

        由于根據(jù)范疇論,可以省略,所以公式變化為:

        bind:A→TB=TA→(B→TB)→TB

        這就是代碼中第4行綁定數(shù)據(jù)的形式。由于最后計(jì)算結(jié)果是A→TA,因此需要η說明id函數(shù)的計(jì)算過程,這就是代碼中return方法所起到的作用。實(shí)際計(jì)算是從A開始,通過lift操作得到TA,然后解析出TA中的A,再通過A→TB函數(shù)計(jì)算出帶有效果的數(shù)值,最后將計(jì)算結(jié)果放到TB中。整個(gè)計(jì)算過程是兩次擴(kuò)展,首先將A的陪域擴(kuò)展為TA,然后將B的定義域擴(kuò)展為TB,最后將兩個(gè)函數(shù)連接起來求出TB。

        另外還需證明需要驗(yàn)證的數(shù)據(jù)流是“可認(rèn)證的”。本質(zhì)上相當(dāng)于需要確保寫入到磁盤上的證明流是連續(xù)的,如果在寫入證明流時(shí),寫入過程被其他線程打斷,那么所寫入的證明流可能由于不連續(xù)而出錯(cuò)。在原論文中默認(rèn)寫入到磁盤的證明流是連續(xù)不會(huì)被打斷的,以這種方式改寫編譯器內(nèi)核后,可能會(huì)導(dǎo)致出現(xiàn)無法跟蹤的錯(cuò)誤情況。因此當(dāng)假設(shè)寫入證明流過程可能會(huì)被打斷的時(shí)候,就需要采用更為正式的方式來驗(yàn)證證明流的完整性。只有當(dāng)驗(yàn)證證明流是完整之后,才能繼續(xù)后面的工作。所以需要加入代碼2所示的接口Authenticatable。

        代碼段2(防止證明流被打斷代碼接口):

        module Authenticatable: sig(*防止證明流被打斷*)

        type′a evidence

        val auth: ′a auth evidence

        val pair: ′a evidence->′b evidence

        ->(′a*′b) evidence

        val sum: ′a evidence->′b evidence

        ->[′left of ′a|′right of ′b] evidence

        val string: string evidence

        val int: int evidence

        end

        可明顯看出,這是創(chuàng)建樹中節(jié)點(diǎn)的過程。通過pair就能合并兩個(gè)葉子節(jié)點(diǎn)的哈希值,通過sum可將左或右葉子節(jié)點(diǎn)的數(shù)值合并到當(dāng)前節(jié)點(diǎn)中。

        由于在接口中添加了一層新的驗(yàn)證數(shù)據(jù)流完整性的接口,因此所有需要驗(yàn)證的數(shù)據(jù)都必須先經(jīng)過此接口才能繼續(xù)驗(yàn)證。也就是,創(chuàng)建證明路徑和解析Merkle樹的完整過程都可觀察。對(duì)驗(yàn)證過程來說,要確保所有待驗(yàn)證或待寫入數(shù)據(jù)都是完整不被打斷的讀取或?qū)懭氲倪^程。

        unauth函數(shù)返回Monad計(jì)算中驗(yàn)證的數(shù)據(jù)后,如果有證明路徑信息,加上現(xiàn)在獲取的驗(yàn)證信息,表示接下來就對(duì)可認(rèn)證數(shù)據(jù)結(jié)構(gòu)開展驗(yàn)證工作。代碼段3所示代碼最終定義了auth和unauth函數(shù)。從代碼行可以看出,兩者輸入時(shí)都要求有Authenticatable類型數(shù)據(jù),即要求數(shù)據(jù)是連續(xù)的完整的數(shù)據(jù)。

        代碼段3(auth和unauth定義代碼接口):

        valauth: ′a Authenticatable.evidence->′a->′a auth

        val unauth: ′a Authenticatable.evidence->′a auth->

        ′a authenticated_computation

        在AUTHENTIKIT中需要添加基本Merkle樹結(jié)構(gòu)。樹的實(shí)現(xiàn)有很多種方法,但每種實(shí)現(xiàn)方法都與具體要傳輸?shù)男畔⒔Y(jié)構(gòu)密切相關(guān)。因?yàn)槭窃诰W(wǎng)絡(luò)中傳輸結(jié)構(gòu)化信息,所以最方便的方式是使用JSON數(shù)據(jù)格式。OCaml自身提供了多種JSON數(shù)據(jù)格式轉(zhuǎn)換庫以供調(diào)用,可以很方便用數(shù)組形式實(shí)現(xiàn)樹形結(jié)構(gòu)?;綧erkle樹需要提供計(jì)算葉子節(jié)點(diǎn)哈希值功能,由makeleaf函數(shù)實(shí)現(xiàn)。通過哈希方式合并非葉子節(jié)點(diǎn)并計(jì)算出合并后哈希值功能的函數(shù)由make_branch函數(shù)實(shí)現(xiàn)。在構(gòu)造Merkle樹時(shí),只需要上述兩個(gè)函數(shù)即可。為了測試目的,提供了兩個(gè)測試函數(shù),分別是用于retrieve和update函數(shù)用于檢索和更新Merkle上的節(jié)點(diǎn)。

        由于Prover和Verifier都要通過同一個(gè)Merkle結(jié)構(gòu)來訪問可認(rèn)證數(shù)據(jù)流,因此Merkle樹應(yīng)該是一個(gè)函子:

        moduleMerkle: MERKLE=

        functor (A: AUTHENTIKIT)->struct; open A; …

        也就是說,當(dāng)需要使用Merkle樹的是Prover時(shí)使用Prover提供的功能訪問Merkle樹,當(dāng)需要使用Merkle樹的是Verifier時(shí)就用Verifier提供的功能訪問Merkle樹。需要注意的是,此處OCaml的Functor與Haskell中Functor在范疇論上是同一概念,但在具體編程實(shí)踐上是兩個(gè)不同的概念。前者屬于類型理論中的*→*數(shù)據(jù)類型,后者屬于類型理論中的Higher-kind數(shù)據(jù)類型,即屬于?→?類型。

        Merkle樹接口的定義與實(shí)現(xiàn)部分與Monad無關(guān),是完全抽象出來的一個(gè)數(shù)據(jù)層。完全可以將Merkle樹的實(shí)現(xiàn)當(dāng)作一個(gè)普通的數(shù)據(jù)結(jié)構(gòu)。只有當(dāng)Prover和Verifier這兩個(gè)模塊作為參數(shù)傳遞給Merkle樹的時(shí)候,Monad接口才會(huì)與之發(fā)生松耦合的聯(lián)系。在Merkle樹看來,auth和unauth就像兩個(gè)新的語法特性一樣。

        與原論文所不同的是,新實(shí)現(xiàn)的auth和unauth是作為庫文件功能提供給Merkle樹使用,在增添新的語法功能時(shí),并沒有修改OCaml編譯器的抽象語法樹。因此,可認(rèn)證功能將直接使用OCaml的類型檢查算法和錯(cuò)誤報(bào)告機(jī)制,在編譯源代碼時(shí),如果錯(cuò)誤使用了auth或unauth的調(diào)用方式,OCaml就會(huì)給出提示信息。

        4 新方法的改進(jìn)之處

        4.1 原方法的局限性

        原方法的局限性是比較復(fù)雜且不夠通用。原方法是先用Camlp4分析OCaml編譯器的語法樹,然后再通過Hack OCaml的技術(shù)在編譯器內(nèi)部語法樹上添加自定義關(guān)鍵字的語法屬性。

        由于需直接修改編譯器內(nèi)部復(fù)雜的抽象語法樹,導(dǎo)致基于修改語法樹實(shí)現(xiàn)的方法也非常復(fù)雜。不夠通用是因?yàn)楦鞣N編譯器內(nèi)部語法樹都有所差異,且并不是所有編譯器都公開內(nèi)部編譯器語法樹,所以這種方法并不適用于所有編譯器。

        原方法在實(shí)現(xiàn)時(shí),必須要首先了解OCaml編譯器內(nèi)部語法樹的屬性和規(guī)則,找到語法描述結(jié)構(gòu),然后才能裁剪抽象語法樹,添加關(guān)鍵字的屬性。抽象語法樹結(jié)構(gòu)整體十分復(fù)雜,只有通過OCaml的提供的接口才能添加新的語法屬性。

        如果希望添加新的語法關(guān)鍵字,在具體實(shí)現(xiàn)時(shí)同樣需要先分析抽象語法樹。每種編譯器的抽象語法樹都略有不同,分析對(duì)象就會(huì)有差異性。有些編譯器并未公開內(nèi)部語法樹結(jié)構(gòu),因此無法通過Hack內(nèi)部語法樹結(jié)構(gòu)的方法添加新的語法功能。

        4.2 新方法的特點(diǎn)

        通過Monad將編譯器中一小部分操作性語義轉(zhuǎn)化為等價(jià)的指示性語義。在實(shí)現(xiàn)時(shí),Monad并未向編譯器語法樹引入新語法屬性,基于OCaml自身的語法實(shí)現(xiàn)了添加新語言特性的目標(biāo)。這種只使用源語言的語法就能產(chǎn)生新語言特性Monad方法普遍適用于函數(shù)式編程語言。不需要語言特性設(shè)計(jì)者深入了解修改編譯器語法樹,也不需要修改源語言的語法。

        使用Monad方法創(chuàng)建認(rèn)證數(shù)據(jù)結(jié)構(gòu)的方法具有通用性。只要程序語言編譯器具有最一般性的類型推導(dǎo)系統(tǒng),就能通過該方法將抽取出的證明流的語義寫入到庫文件中,形成新的語言特性。例如,Haskell是另外一種函數(shù)式程序語言編譯器,同樣也能通過Monad方法,在僅使用Haskell自身語言語法,便可實(shí)現(xiàn)在程序語言中引入可認(rèn)證數(shù)據(jù)結(jié)構(gòu)語言特性。

        5 結(jié) 語

        本文通過完整展示將可認(rèn)證數(shù)據(jù)結(jié)構(gòu)的操作性語義轉(zhuǎn)化為指示性語義的過程,闡述了Monad的理論概念如何對(duì)應(yīng)到的具體實(shí)踐的編程概念。由于Monad概念過于抽象,所以本文重點(diǎn)描述了auth和unauth代碼的分析過程,以具體實(shí)例展示如何將非純函數(shù)組合在一起。采用Monad方法可直接借助源編譯器語言實(shí)現(xiàn)新的語言功能,因此可避免修改編譯器的語法樹,同時(shí)便于在不同程序編譯器之間移植新的語言功能。

        猜你喜歡
        編譯器范疇語義
        批評(píng)話語分析的論辯范疇研究
        正合范疇中的復(fù)形、余撓對(duì)及粘合
        語言與語義
        基于相異編譯器的安全計(jì)算機(jī)平臺(tái)交叉編譯環(huán)境設(shè)計(jì)
        Clean-正合和Clean-導(dǎo)出范疇
        “上”與“下”語義的不對(duì)稱性及其認(rèn)知闡釋
        認(rèn)知范疇模糊與語義模糊
        通用NC代碼編譯器的設(shè)計(jì)與實(shí)現(xiàn)
        語義分析與漢俄副名組合
        編譯器無關(guān)性編碼在微控制器中的優(yōu)勢
        色欲av蜜桃一区二区三| 国产少妇露脸精品自拍网站| 日本超级老熟女影音播放| 日韩av激情在线观看| 亚洲av无码av吞精久久| 无码一区二区三区在| 大香蕉青青草视频在线| 国产黄大片在线观看画质优化| 欧美性性性性性色大片免费的| 久久综合给合久久狠狠狠9| 一本色道加勒比精品一区二区| 性欧美长视频免费观看不卡| 日产精品久久久久久久性色| 亚洲无AV码一区二区三区| 不卡av一区二区在线| 观看在线人视频| 丰满人妻妇伦又伦精品国产| 久久精品国产亚洲AⅤ无码剧情| 国产精品视频白浆免费视频| 娇妻在交换中哭喊着高潮| 亚洲色欲在线播放一区| 日本一区二区三区的免费视频观看 | 亚洲av无码电影网| 完整在线视频免费黄片| 亚洲国产综合人成综合网站| 国产又粗又黄又爽的大片| 日本免费不卡一区| 久久夜色精品国产亚洲av老牛| 欧美成人精品第一区| 日韩精品无码av中文无码版| 丁香九月综合激情| 中文字幕亚洲综合久久综合| 啦啦啦www播放日本观看| 91性视频| 美女被内射中出在线观看| 亚洲精品色婷婷在线影院| 99re这里只有热视频| 丰满人妻被猛烈进入中文字幕护士| 日韩人妻不卡一区二区三区| 人妻影音先锋啪啪av资源| 亚洲中文字幕不卡无码|