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的魔法。

我们在两个角色之间做一个自动对战的模拟器。这些角色有四种状态:

-健康。等于他们能承受的伤害总量。

接下来,让我们选出谁将会有这场史诗般的战斗:

Opside已在测试网上线ZK-Rollup LaunchBase:8月14日消息,去中心化ZK-RaaS平台Opside已在测试网上线ZK-Rollup LaunchBase,支持开发者构建专用应用程序Rollup,包括Layer1、zkEVM、Gas、Data Availability与Sequencer各个组件。LaunchBase现允许开发者从Opside、Goerli、Mumbai与BNB测试网等EVM兼容的Layer1中选择以构建其应用程序的特定rollup,支持Polygon zkEVM、zkSync、Scroll与Starknet四个zkEVM。[2023/8/14 16:24:39]

我们将有一个食人魔,它有很长的血条,每次攻击造成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的许多要求之一是,所有的输入都必须是非负数。这是我们开发人员的不幸,但是我们英雄的幸事,食人魔的健康值会变负,这就是一个负数:(

为了绕过这个限制,我们将在所有的健康值上加上1000,如果一个角色的健康值低于1000,就认为他已经死亡。为了使这个方法适用于不同的角色伤害值,我们还需要确保一个角色的伤害永远不会超过1000,因为那样的话某人的健康状况可能会再次变成负数。以下是代码:

非营利组织人权基金会和Starkware宣布推出一个为期4个月的ZK-Rollup赞助研究项目:3月25日消息,非营利组织人权基金会(HRF)和Starkware宣布推出一个为期4个月的ZK-Rollup赞助研究项目,研究员将获得1BTC以支持他们的研究和写作输出,赞助部分来自Starkware,另一部分来自CMSHoldings最近对HRF的捐赠。研究将包含6个方面的问题。[2022/3/25 14:16:57]

{"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中看到的非常相似:

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中是不可能的,我们需要通过递归来实现同样的逻辑。因此,让我们定义一个递归函数,它将验证一个单一回合的战斗,然后再递归验证所有其他回合的战斗:

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]

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

ZKSwap将在2到3周内发布100% ZK-Rollup版本:据官方消息,ZKSwap将在2到3周内发布100% ZK-Rollup版本。[2021/2/28 18:00:41]

与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程序的输出进行对比。下面是代码:

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

波卡二层扩容协议Plasm开始研究ZK-Rollups 并计划于Q4公布相关信息:10月13日,波卡二层扩容协议Plasm发推公布项目周报。周报显示,Plasm Network计划将实现Rollup解决方案,并已开始着手研究ZK-Rollups。官方表示,这方面的信息应该将在2020年第四季度公布。此外,周报还提到,Plasm已集成以太坊虚拟机EVM并升级至Substrate 2.0。[2020/10/13]

除了检查这些战士的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

郑重声明: 本文版权归原作者所有, 转载文章仅为传播更多信息之目的, 如作者信息标记有误, 请第一时间联系我们修改或删除, 多谢。

金智博客

[0:0ms0-4:723ms