zk-STARK: 在以太坊上驗證復雜的自動對戰計算-ODAILY

在以太坊上執行復雜的函數一直是一個大忌，永遠不應該這么做。區塊鏈計算是非常昂貴的，因為需要所有節點執行相同的計算來驗證其正確性。

StarkWare是以太坊擴展服務之一，它試圖使用STARK證明來擴展以太坊。在這篇文章中，我不會太深入于STARK是如何工作的，但我將對它在實踐中的應用做一個實際的概述。

有時在STARK前面加上“zk-”前綴，表示“零知識證明”，這使得STARK能夠在不透露我們試圖證明的事物的所有信息的情況下證明一些東西。StarkWare公司正致力于在以后的管道中加入ZK，但現在他們只關注可擴展性，而要實現這一點并不需要零知識。

Vitalik的博客文章對于zk-SNARK如何呈現在用戶面前所繪制的插圖。

Vitalik在他的文章中對STARK做了一個簡短的概述。STARK第一部分：用多項式進行證明，簡要解釋了這些加密基元的工作原理。還有SNARK，可以實現與STARK類似的東西，但有點不同。如果對理解zk-SNARK更感興趣，強烈推薦這篇解釋論文：zk-SNARK的原理和實現，MaksymPetkus的權威解釋。Petkus解釋了zk-SNARK的原理，從非常基本的數學，然后逐步深入更復雜的數學，站在前人的肩膀上眺望。非常棒的閱讀體驗。

Petkus對zk-SNARK總結如下：

零知識簡明非交互式知識論證是真正巧妙的方法，可以證明某件事情是真實的，而不透露任何其他信息。

STARK和自動對戰游戲

自動對戰游戲是一種游戲類型，玩家在其中做出角色成長的選擇，但在戰斗當中不能做出任何選擇，而是自動進行。如果有這樣的游戲在以太坊L1上運行，會很好玩，但目前這樣的游戲做不起來。

那么，STARK能給自動對戰游戲帶來什么好處呢？自動對戰游戲的模擬可能是非常復雜的，所以很難跑起來。如果有一種技術可以使它只運行一次，而其他玩家可以只相信這種計算，同時確信沒有人在說謊，這將使我們能夠擁有一個去中心化的自動對戰。

以下是行動計劃：

1)用Python編寫自動對戰邏輯。

2)用StarkNet的Cairo語言建立一個驗證器。

3)執行自動戰斗的代碼，用我們建立的Cairo驗證器創建一個關于程序執行的STARK證明。

4)觀察我們如何在以太坊的Solidity環境利用自動戰斗器的戰斗結果。

用Python編寫自動戰斗系統

為了開始我們的旅程，我們簡單地對自動對戰的邏輯進行編程，就像我們平時做的那樣，這里不需要STARK的魔法。

我們在兩個角色之間做一個自動對戰的模擬器。這些角色有四種狀態：

-健康。等于他們能承受的傷害總量。

接下來，讓我們選出誰將會有這場史詩般的戰斗：

Charles Hoskinson：Cardano對ZK-rollups有一個“美麗計劃”:4月15日消息，Input Output首席執行官Charles Hoskinson在最近AMA活動中被問到為什么Cardano區塊鏈沒有涉及ZK-rollups，他回應稱Cardano對ZK-rollups有一個“美麗計劃”，應該會與Midnight有很大關系，更多細節將在后續公布。Midnight是隱私為中心的Cardano側鏈，專注于保護敏感的商業和個人數據、開發者和個人數據，分析認為雖然Charles Hoskinson沒有詳細說明Cardano區塊鏈將如何使用ZK-rollups，但提及Midnight可能與安全驗證鏈上數據有關。（cryptoslate）[2023/4/16 14:06:00]

我們將有一個食人魔，它有很長的血條，每次攻擊造成48點傷害，但每次攻擊之間需要等80下。食人魔每回合還能恢復三點健康值。

我們的挑戰者英雄的生命值要低得多，只有240血，完全沒有生命值恢復，每次攻擊的傷害較小，但我們的英雄只需等待2個回合就可以攻擊。因此，至少我們的英雄在某種程度上比食人魔要好！這就是我們的英雄。這是一場真正的大衛和歌利亞之間的戰斗。

我們可以在代碼中定義我們的角色，如下所示

player1=Character(1000,48,80,3)#Ogreplayer2=Character(240,20,2,0)#Hero

然后我們可以通過調用戰斗函數來模擬戰斗。

simulateFight(player1,player2

我們將得到戰斗的結果：

{"player1":{"stats":},"player2":{"stats":},"log":{"endHealths":,"nCombatRounds":272}}ZERO_HP_POINT=1000assertplayer1.damage<ZERO_HP_POINTassertplayer2.damage<ZERO_HP_POINTdata={'player1':{'stats':},'player2':{'stats':},'log':simulateFight(player1,player2。data=]withopen('combat-input.json','w')asoutfile:json.dump(data,outfile)

我們可以從結果中讀出，這場戰斗持續了272個回合，戰斗結束是因為食人魔被打敗了。我們的英雄以巨多的96點血取得了勝利！這就是我們的英雄。

接下來讓我們把所有關于戰斗的必要的重要信息存儲在一個文件中，這樣我們就可以在以后用STARK證明來證明這場戰斗。我們所需要的是程序輸入和程序輸出。我們的驗證器根本不需要程序本身！

我們將用Cairo編寫驗證器。Cairo是一種用于編寫可驗證程序的編程語言。Cairo的許多要求之一是，所有的輸入都必須是非負數。這是我們開發人員的不幸，但是我們英雄的幸事，食人魔的健康值會變負，這就是一個負數:(

V神：ZK-EVM是以太坊Layer 1安全和驗證過程的重要組成部分:金色財經報道，以太坊聯合創始人“V神”Vitalik Buterin在其官方博客上發布文章《以太坊的多客戶端理念將如何與ZK-EVM交互？》（How will Ethereum's multi-client philosophy interact with ZK-EVMs?），其中指出ZK-EVM將在未來發展成為以太坊Layer 1安全和驗證過程的重要組成部分，但關鍵在于如何為零知識證明以太坊區塊的正確性創建一個“多客戶端”生態系統。V神建議采取開放的多個ZK-EVM，因為不同的客戶端有不同的ZK-EVM實現，每個客戶端可以在接受一個區塊為有效之前等待與自己兼容的證明。此外，Vitalik Buterin還對人工智能最近的快速發展大加贊揚，他覺得人工智能的進步可以“加速”證明ZK-EVM實現的發展。“從長遠來看，當然任何事情都有可能發生。也許AI會加強形式驗證，使其可以輕松證明ZK-EVM實現等效并識別導致彼此之間差異的所有錯誤。”[2023/4/2 13:40:23]

為了繞過這個限制，我們將在所有的健康值上加上1000，如果一個角色的健康值低于1000，就認為他已經死亡。為了使這個方法適用于不同的角色傷害值，我們還需要確保一個角色的傷害永遠不會超過1000，因為那樣的話某人的健康狀況可能會再次變成負數。以下是代碼：

{"player1":{"stats":},"player2":{"stats":},"log":{"endHealths":,"nCombatRounds":272}}ZERO_HP_POINT=1000assertplayer1.damage<ZERO_HP_POINTassertplayer2.damage<ZERO_HP_POINTdata={'player1':{'stats':},'player2':{'stats':},'log':simulateFight(player1,player2。data=]withopen('combat-input.json','w')asoutfile:json.dump(data,outfile)

這段代碼為我們產生了最終的模擬輸出，它將被儲存在combat-input.json文件中。

{"player1":{"stats":},"player2":{"stats":},"log":{"endHealths":,"nCombatRounds":272}}

編寫Cairo驗證器

接下來，我們需要編寫一個驗證器程序，以便能夠對我們的Python程序的執行進行STARK證明。這個程序需要能夠驗證，在給定初始玩家屬性的情況下，當模擬代碼運行時，模擬器會產生顯示在log區域的確切輸出。為了實現這一點，我們將改用Cairo語言編程。

我們將在Cairo中定義角色結構，其方式與我們在python中看到的非常相似：

V神：ZK-Rollups或成為以太坊主要Layer 2解決方案:8月8日消息，以太坊聯合創始人Vitalik Buterin在ETHSeoul演講時預測，ZK-Rollups將在以太坊Layer2擴容之戰中擊敗Optimistic Rollups，比如用戶不需要7天的等待期。Vitalik Buterin指出，ZK-Rollups在將資金移入和移出主網時速度更快，這可能會導致更廣泛地采用。從現在起的10多年甚至更久，我預計Rollups基本上都將會是ZK。ZK-Rollups的EVM兼容性正在開發當中，Vitalik Buterin補充道，我們實際上已經能看到zk-EVM幾乎準備好實現與以太坊交易一起進行擴容，這太棒了。（the block）[2022/8/9 12:10:54]

structCharacter:memberhealth:feltmemberdamage:feltmemberattackRecoverTime:feltmemberhealthPerTurn:feltend

與Python相比，這里的一個很大的區別是，我們需要將所有的變量指定為某種陌生的數據類型felt。felt數據類型是一個252位的變量類型，定義在(-P/2,P/2)之間，其中P是一個252位的大素數。

雖然看起來很奇怪，但對于我們的目的來說，felt的行為就像一個整數。這種數據類型的意義在于，與我們實際處理整數或浮點變量類型相比，Cairo編譯器更容易從我們的代碼中做出STARK證明。你可以從Cairo的文檔中閱讀更多關于felt變量類型的信息。

現在，讓我們開始編寫Cairo程序，以確保戰斗已經按計劃進行，而且程序的執行者不能對其他玩家撒謊。除了輸入變量的felt類型和非負性之外，Cairo還有一些其他的限制。我們在Python代碼中使用了一個while循環，但是動態長度循環在Cairo中是不可能的，我們需要通過遞歸來實現同樣的邏輯。因此，讓我們定義一個遞歸函數，它將驗證一個單一回合的戰斗，然后再遞歸驗證所有其他回合的戰斗：

funcsimulateCombat{range_check_ptr}(player1:Character,player2:Character,currentHealths:(felt,felt),lastAttacks:(felt,felt),currentRound:felt,nCombatRounds:felt)->(simNextHealths:(felt,felt),simNextLastAttacks:(felt,felt))

該函數接收我們的兩個角色，他們當前的健康狀況和最后一次攻擊的計時器，當前的戰斗回合和要模擬的戰斗回合數。然后，我們將在驗證回合后返回更新的健康和最后一次攻擊的計時器，以便能夠通過遞歸驗證下一個回合。

你可能已經注意到了我們函數開頭的range_check_ptr。range_check_ptr是一個指針，我們需要用它來進行范圍檢查。這些運算在Cairo中也很困難，但幸運的是，我們仍然能夠通過使用Cairo的range_check_ptr內置函數來完成這些運算。

接下來，讓我們開始定義函數的內部內容。我們基本上實現了與我們在Python中的戰斗回合完全相同的邏輯：

alloc_localslocalnextHealths:(felt,felt)localnextLastAttacks:(felt,felt)localZERO_HP_POINT=1000iflastAttacks==player2.attackRecoverTime:tempvarafterDamage=currentHealths-player2.damagenextHealths=afterDamage+player1.healthPerTurnnextLastAttacks=0else:nextHealths=currentHealths+player1.healthPerTurnnextLastAttacks=lastAttacks+1endiflastAttacks==player1.attackRecoverTime:tempvarafterDamage=currentHealths-player1.damagenextHealths=afterDamage+player2.healthPerTurnnextLastAttacks=0else:nextHealths=currentHealths+player2.healthPerTurnnextLastAttacks=lastAttacks+1end

Cardano推出首個ZK-Rollups擴容解決方案Orbis:2月25日消息，Cardano（ADA）推出首個 ZK-Rollup Layer 2 解決方案 Orbis，旨在通過提升可擴展性和交易吞吐量支持 DeFi 應用程序和區塊鏈生態系統，交易會在 Orbis Layer 2 鏈下執行并形成一個零知識證明，然后提交給 Cardano Layer 1。

Orbis 有兩個主要組件：證明者（Prover）和驗證者（Verifier），前者目的是構建 zkSNARK 證明來驗證交易的發生，后者是一個鏈上智能合約，接受鏈上資產輸入，將它們鎖定在合約中，以便它們可以在 Rollup 中使用并確保不會出現雙花風險。據了解，Orbis 團隊已經在 Project Catalyst 的 Ideascale 平臺上發布了資金申請，希望申請 100 萬美元資金來支持開發和上線工作。[2022/2/25 10:16:05]

與Python相比，Cairo代碼的編寫方式有些不同。這是因為在Cairo中我們只能利用常數變量。一旦我們為一個變量設置了一個值，我們就不能再改變它的內容。因此，當我們為健康恢復而增加玩家的生命值時，我們在計算傷害的同時也計算了它。

接下來我們將檢查我們是否已經模擬了所要求的回合數，如果是，我們就結束模擬。如果模擬還沒有結束，我們需要檢查兩個玩家是否還活著。如果我們沒有這個檢查，惡意的模擬器運行者可以一直模擬戰斗，直到兩個玩家都死了，這會讓一個已經死了的玩家繼續戰斗！我們不能允許這樣的瘋狂行為，我們不能允許不死的戰士出現在我們的競技場上！

ifcurrentRound==nCombatRounds:return(nextHealths,nextLastAttacks)else:#ifthecombathasnotended,nobodycanbedeadassert_nn(nextHealths-ZERO_HP_POINT)assert_nn(nextHealths-ZERO_HP_POINT)end

這里我們使用的是assert_nn函數，它正在檢查函數內部的值是否為非負值：nextHealths>ZERO_HP_POINT。如果assert為假，則執行失敗，我們知道運行模擬器的人對我們撒謊了。

最后，讓我們調用我們的函數來獲得下一輪的模擬，然后我們將返回最終的模擬結果。

let(simulatedEndHealths,simulatedLastAttacks)=simulateCombat(player1=player1,player2=player2,currentHealths=nextHealths,lastAttacks=nextLastAttacks,currentRound=currentRound+1,nCombatRounds=nCombatRounds)return(simNextHealths=simulatedEndHealths,simNextLastAttacks=simulatedLastAttacks)

一旦我們有了模擬邏輯的代碼，我們就需要為我們的Cairo程序編寫主函數。該程序需要讀取Python程序的輸出，然后調用我們剛剛創建的simulateCombat函數。該函數將返回最終的健康值，然后我們需要將其與Python程序的輸出進行對比。下面是代碼：

聲音 | V神：建議使用zk-SNARK來擴展以太坊:據blockmanity消息，V神關于以太坊研究的最新文章，概述了一個關于鏈縮放的解決方案，沒有任何附加層，而是使用zk- spuks（隱私令牌ZCash背后的加密算法），該方案可能將以太坊擴展至500tx/秒。[2018/9/23]

funcmain{output_ptr:felt*,range_check_ptr}()->():alloc_localslocalrange_check_ptr=range_check_ptrlocalpl1:Character*localpl2:Character*localendHealths:felt*localnCombatRounds:felt%{log=program_inputdat_endHealths=logdat_nCombatRounds=logids.pl1=pl1=segments.add()fori,valinenumerate(program_input):memory=valids.pl2=pl2=segments.add()fori,valinenumerate(program_input):memory=valids.endHealths=endHealths=segments.add()fori,valinenumerate(dat_endHealths):memory=valids.nCombatRounds=dat_nCombatRoundsassertlen(program_input)==4assertlen(program_input)==4assertlen(dat_endHealths)==2%}localplayer1:Character=pl1localplayer2:Character=pl2localcurrentHealths:(felt,felt)=(player1.health,player2.health)locallastAttacks:(felt,felt)=(0,0)let(simulatedEndHealths,lastSimulatedAttacks)=simulateCombat(player1=player1,player2=player2,currentHealths=currentHealths,lastAttacks=lastAttacks,currentRound=0,nCombatRounds=nCombatRounds)#CheckthatthehealthswillmatchwhatwasclaimedassertsimulatedEndHealths=endHealthsassertsimulatedEndHealths=endHealths#Returntheprograminputandoutputserialize_word(player1.health)serialize_word(player1.damage)serialize_word(player1.attackRecoverTime)serialize_word(player1.healthPerTurn)serialize_word(player2.health)serialize_word(player2.damage)serialize_word(player2.attackRecoverTime)serialize_word(player2.healthPerTurn)serialize_word(simulatedEndHealths)serialize_word(simulatedEndHealths)return()end

除了檢查這些戰士的nCombatRounds模擬結果是否為給定的健康值外，我們還應該檢查在戰斗結束時是否有一個或兩個角色已經死亡。如果想讓戰斗持續下去，直到有人死亡。我們沒有在這個簡單的例子中實現這一點，可以由讀者來實現。在目前的代碼中，只能模擬運行幾輪，并在給定回合后，在任何一個玩家死之前停止戰斗。然而，執行者不能對模擬回合的進行情況撒謊，因為這是我們要檢查的。

為什么我們需要兩個程序？

我們本來可以把Python和Cairo程序寫在一起，作為一個單一的Cairo程序，以大大減少代碼量。然而，在實踐中，我們需要在Python程序中添加更多的功能，這樣我們就可以為我們的終端用戶制作戰斗的動畫。例如，我們希望記錄每個玩家每輪的健康狀況，以及每輪發生的情況。這些邏輯在驗證器部分是完全不需要的。我也喜歡想象有兩個程序：一個戰斗邏輯計算器和一個戰斗結果驗證器。這類似于我們經常有的程序和測試用例的邏輯分割。

運行！

我們可以運行Python模擬器，用以下命令編譯我們的Cairo驗證器：

>pythoncombat.py>cairo-compilecombat.cairo--outputcombat-compiled.json

然后我們可以用我們用combat.py生成的輸入文件來運行Cairo程序，生成combat.pie文件：

>cairo-run--program=combat-compiled.json--program_input=combat-input.json--layout=small--cairo_pie_output=combat.pie

我們還可以用以下命令驗證pie文件是否正確：

>cairo-run--layout=small--run_from_cairo_pie=combat.pie

你可以嘗試修改battle-input.json文件的結果健康值，要注意的是，如果不得到Cairo的驗證錯誤，你就不能修改它們。對于每個起始輸入，戰斗只有一種解決方式。例如，如果我們試圖作弊，在戰斗結束時給我們的英雄多加一個健康值，驗證器會注意到我們在試圖作弊。

combat.cairo:120:5:Erroratpc=0:201:AnASSERT_EQinstructionfailed:1096!=1097assertsimulatedEndHealths=endHealths^*******************************************^

.pie文件包含了SHARP為我們進行證明生成所需的所有信息。SHARP是由StarkWare運營的一項服務，它可以生成證明，證明Cairo程序執行的有效性。然后，它將這些證明發送到以太坊測試網，由以太坊智能合約進行驗證。

目前，SHARP不能在本地運行，從Cairo程序中生成證明的唯一方法是利用StarkWare的服務器來做證明驗證。希望這種情況在未來會有所改變，任何人都可以生成關于任何東西的證明。StarkWare公司計劃在稍后階段發布SHARP的源代碼。目前現狀來說，去中心化的游戲無法使用Cairo來構建。

讓我們向SHARP提交我們的工作吧：

>cairo-sharpsubmit--cairo_piecombat.pieSubmittingtoSHARP...Jobsent.Jobkey:f48c551e-c0c6-4cf5-8a52-a0aa1c43728cFact:0x17ee903dfb54b55e53cc03d5a47602e83ed0ff9e219fe4567b8d59fa2666f682

過了很久，我們應該能看到我們的事實被驗證了，而且是有效的：

>cairo-sharpis_verified0x17ee903dfb54b55e53cc03d5a47602e83ed0ff9e219fe4567b8d59fa2666f682--node_url=https://goerli-light.eth.linkpool.io/True

我們也可以從Cairo的游樂場找到這個結果。

https://www.cairo-lang.org/playground/sharp.html?job_key=f48c551e-c0c6-4cf5-8a52-a0aa1c43728c

在以太坊智能合約上利用證明

現在我們知道，對于給定的輸入值，給定事實哈希值，程序應該輸出最終的健康值，我們能夠在鏈上驗證計算，而無需在鏈上再次執行計算。

實際上，我們還缺少一個信息，那就是程序的哈希值。

>cairo-hash-program-programcombat-compiled.json0x248070cb7b7f20b0b9445a382fdb4faa6b69c1f3653355077ae05b82c636ddf

這是我們之前所有工作的高潮，現代密碼學的奇跡，一個簡單的Solidity函數可以驗證一個事實并檢查程序輸出programOutput是否有效。所有這些都不需要計算本身。

functionverifyCombatOutput(uint256memoryprogramOutput)publicbytes32cairoProgramHash_=0x248070cb7b7f20b0b9445a382fdb4faa6b69c1f3653355077ae05b82c636ddf//Ensurethatacorrespondingproofwasverified.bytes32outputHash=keccak256(abi.encodePacked(programOutput));bytes32fact=keccak256(abi.encodePacked(cairoProgramHash_,outputHash));require(cairoVerifier_.isValid(fact),"MISSING_CAIRO_PROOF");//Ensuretheoutputconsistencywithcurrentsystemstate.require(programOutput.length==10,"INVALID_PROGRAM_OUTPUT");require(player1.health==programOutput,"INVALID_PROGRAM_OUTPUT0");require(player1.damage==programOutput,"INVALID_PROGRAM_OUTPUT1");require(player1.attackRecoverTime==programOutput,"INVALID_PROGRAM_OUTPUT2");require(player1.healthPerTurn==programOutput,"INVALID_PROGRAM_OUTPUT3");require(player2.health==programOutput,"INVALID_PROGRAM_OUTPUT4");require(player2.damage==programOutput,"INVALID_PROGRAM_OUTPUT5");require(player2.attackRecoverTime==programOutput,"INVALID_PROGRAM_OUTPUT6");require(player2.healthPerTurn==programOutput,"INVALID_PROGRAM_OUTPUT7");//NowweknowthatprogramOutputandprogramOutputrepresenttheresultinghealthvalues,//giventheinitialcombatstatevariablesprogramOutput!.//PureMagic.}

這里cairoVerifier._isValid(fact)是一個Goerli的合約。

https://goerli.etherscan.io/address/0xAB43bA48c9edF4C2C4bB01237348D1D7B28ef168

可以在這里找到文章中文件的源代碼：https://github.com/KillariDev/STARK-Combat

Tags：LAYERQUOPLAYPLAUnilayerXQuota4PLAY幣Plant Exodus

波場