zk-STARK: 在以太坊上验证复杂的自动对战计算

原文作者:?Killari

原文标题:?STARKs:VerifyingcomplexautobattlercalculationonEthereum—Scalingdecentralizedgames

在以太坊上执行复杂的函数一直是一个大忌，永远不应该这么做。区块链计算是非常昂贵的，因为需要所有节点执行相同的计算来验证其正确性。

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

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

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

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

我们将有一个食人魔，它有很长的血条，每次攻击造成48点伤害，但每次攻击之间需要等80下。食人魔每回合还能恢复三点健康值。

Scroll在Goerli测试网推出以太坊L2网络zk-EVM的测试网版本:金色财经报道，Scroll在Goerli测试网上发布了其以太坊L2网络的测试网版本，这是将zk-EVM从pre-alpha转移到alpha的测试阶段。到目前为止，Scroll可以在基于该项目的以太坊克隆的测试网上进行试用。测试网的代码将是开源的，这意味着该网络可以开始建立弹性。此外，Goerli测试网和Scroll之间已经建立了一个桥梁来转移资产。

据悉，Zk-EVM是建立在以太坊上的第2层网络，它使用零知识证明来实现可扩展性。[2023/2/28 12:32:53]

我们的挑战者英雄的生命值要低得多，只有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?=?1000assert?player1.damage?<?ZERO_HP_POINTassert?player2.damage?<?ZERO_HP_POINTdata?=?{????'player1':?{?????'stats':?????},????'player2':?{?????'stats':?????},??'log':?simulateFight(player1,?player2。data?=?]with?open('combat-input.json',?'w')?as?outfile:json.dump(data,?outfile)

我们可以从结果中读出，这场战斗持续了272个回合，战斗结束是因为食人魔被打败了。我们的英雄以巨多的96点血取得了胜利！这就是我们的英雄。

接下来让我们把所有关于战斗的必要的重要信息存储在一个文件中，这样我们就可以在以后用STARK证明来证明这场战斗。我们所需要的是程序输入和程序输出。我们的验证器根本不需要程序本身！

我们将用Cairo编写验证器。Cairo是一种用于编写可验证程序的编程语言。Cairo的许多要求之一是，所有的输入都必须是非负数。这是我们开发人员的不幸，但是我们英雄的幸事，食人魔的健康值会变负，这就是一个负数:(

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

首个基于ZK-Rollups的NFT协议ZKBox上线:9月24日消息，由 L2 Labs支持的基于 ZK-Rollups 的第 2 层 NFT 协议ZKBox今天推出其白皮书 和官网，致力于提供实时的 NFT 铸币、交易, 存取款服务免费。[2021/9/24 17:03:13]

{????"player1":?{?????"stats":?????},????"player2":?{?????"stats":?????},????"log":?{?????"endHealths":?,?????"nCombatRounds":?272????}}ZERO_HP_POINT?=?1000assert?player1.damage?<?ZERO_HP_POINTassert?player2.damage?<?ZERO_HP_POINTdata?=?{????'player1':?{?????'stats':?????},????'player2':?{?????'stats':?????},??'log':?simulateFight(player1,?player2。data?=?]with?open('combat-input.json',?'w')?as?outfile:json.dump(data,?outfile)

这段代码为我们产生了最终的模拟输出，它将被储存在combat-input.json文件中。

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

编写Cairo验证器

接下来，我们需要编写一个验证器程序，以便能够对我们的Python程序的执行进行STARK证明。这个程序需要能够验证，在给定初始玩家属性的情况下，当模拟代码运行时，模拟器会产生显示在log区域的确切输出。为了实现这一点，我们将改用Cairo语言编程。

我们将在Cairo中定义角色结构，其方式与我们在python中看到的非常相似：

struct?Character:????member?health:?felt????member?damage:?felt????member?attackRecoverTime:?felt????member?healthPerTurn:?feltend

与Python相比，这里的一个很大的区别是，我们需要将所有的变量指定为某种陌生的数据类型felt。felt数据类型是一个252位的变量类型，定义在(-P/2,P/2)之间，其中P是一个252位的大素数。

虽然看起来很奇怪，但对于我们的目的来说，felt的行为就像一个整数。这种数据类型的意义在于，与我们实际处理整数或浮点变量类型相比，Cairo编译器更容易从我们的代码中做出STARK证明。你可以从Cairo的文档中阅读更多关于felt变量类型的信息。

现在，让我们开始编写Cairo程序，以确保战斗已经按计划进行，而且程序的执行者不能对其他玩家撒谎。除了输入变量的felt类型和非负性之外，Cairo还有一些其他的限制。我们在Python代码中使用了一个while循环，但是动态长度循环在Cairo中是不可能的，我们需要通过递归来实现同样的逻辑。因此，让我们定义一个递归函数，它将验证一个单一回合的战斗，然后再递归验证所有其他回合的战斗：

币赢Defi专区Miniswap成为首个基于可编程 ZK-Rollups 技术的 layer-2 去中心化平台:据官方消息，币赢Defi专区Miniswap首家开发针对DeFi的“Derivative”智能合约语言并将其将引入支持ZK-rollup的 Layer2网络。据悉，此项Layer2技术可除了实现0 Gas费，解决DEX交易拥堵，降低DEX交易成本，提高DEX交易效率之外，其“Derivative”智能合约语言还能够方便开发者进行二次开发，增强其生态可拓展性。

币赢MINI当前报价0.0789U，24小时涨幅15.56%[2021/1/6 16:33:24]

func?simulateCombat{?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_localslocal?nextHealths:?(felt,?felt)local?nextLastAttacks:?(felt,?felt)local?ZERO_HP_POINT?=?1000if?lastAttacks?==?player2.attackRecoverTime:?tempvar?afterDamage?=?currentHealths?-?player2.damage?nextHealths?=?afterDamage??player1.healthPerTurn?nextLastAttacks?=?0else:?nextHealths?=?currentHealths??player1.healthPerTurn?nextLastAttacks?=?lastAttacks??1endif?lastAttacks?==?player1.attackRecoverTime:?tempvar?afterDamage?=?currentHealths?-?player1.damage?nextHealths?=?afterDamage??player2.healthPerTurn?nextLastAttacks?=?0else:?nextHealths?=?currentHealths??player2.healthPerTurn?nextLastAttacks?=?lastAttacks??1end

动态 | TRON将实现“四大发展” 包括将于2019年第二季度推出的zk-SNARKs:米莎·莱德曼（Misha Lederman）透露TRON的主要发展将在2019年第二季度实现，包括：

-比特流速度；

-对机构友好的多重签名和账户管理；

-USDT-TRON稳定币在TRX区块链上推出；

-保护交易流程的隐私[2019/3/22]

与Python相比，Cairo代码的编写方式有些不同。这是因为在Cairo中我们只能利用常数变量。一旦我们为一个变量设置了一个值，我们就不能再改变它的内容。因此，当我们为健康恢复而增加玩家的生命值时，我们在计算伤害的同时也计算了它。

接下来我们将检查我们是否已经模拟了所要求的回合数，如果是，我们就结束模拟。如果模拟还没有结束，我们需要检查两个玩家是否还活着。如果我们没有这个检查，恶意的模拟器运行者可以一直模拟战斗，直到两个玩家都死了，这会让一个已经死了的玩家继续战斗！我们不能允许这样的疯狂行为，我们不能允许不死的战士出现在我们的竞技场上！

if?currentRound?==?nCombatRounds:?return(nextHealths,?nextLastAttacks)else:?#?if?the?combat?has?not?ended,?nobody?can?be?dead?assert_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程序的输出进行对比。下面是代码：

func?main{?output_ptr:?felt*,?range_check_ptr?}()?->?():?alloc_locals?local?range_check_ptr?=?range_check_ptr?local?pl1:?Character*?local?pl2:?Character*?local?endHealths:?felt*?local?nCombatRounds:?felt?%{?????log?=?program_input?????dat_endHealths?=?log?????dat_nCombatRounds?=?log??????????ids.pl1?=?pl1?=?segments.add()?????for?i,?val?in?enumerate(program_input):?????????memory?=?val??????????????ids.pl2?=?pl2?=?segments.add()?????for?i,?val?in?enumerate(program_input):?????????memory?=?val?????ids.endHealths?=?endHealths?=?segments.add()?????for?i,?val?in?enumerate(dat_endHealths):?????????memory?=?val?????ids.nCombatRounds?=?dat_nCombatRounds?????assert?len(program_input)?==?4?????assert?len(program_input)?==?4?????assert?len(dat_endHealths)?==?2?%}?????local?player1:?Character?=?pl1?local?player2:?Character?=?pl2?????local?currentHealths:?(felt,?felt)?=?(player1.health,?player2.health)?local?lastAttacks:?(felt,?felt)?=?(0,?0)?????let?(simulatedEndHealths,?lastSimulatedAttacks)?=?simulateCombat(?????player1?=?player1,?????player2?=?player2,?????currentHealths?=?currentHealths,?????lastAttacks?=?lastAttacks,?????currentRound?=?0,?????nCombatRounds?=?nCombatRounds?)?????#?Check?that?the?healths?will?match?what?was?claimed?assert?simulatedEndHealths?=?endHealths?assert?simulatedEndHealths?=?endHealths?#?Return?the?program?input?and?output?serialize_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

以色列理工学院所研究的区块链隐私解决方案 ZK-Starks正在变成现实:5月26日，据Coindesk报道，以色列理工学院发明的区块链隐私解决方案ZK-Starks受到许多开发者称赞。所谓的zk-starks提供了一种有希望将大量信息压缩成小样本的方式，命名为starks，并可以使用零知识证明来保护该信息的隐私。Starks对于量子计算也是高效，透明和安全的，Starks团队称之为“令牌技术模型”.创始人Eli Ben-Sasson和Alessandro Chiesa正在走企业路线，希望将他们的新技术提供给实际区块链以换取其原生资产。许多社区的倡导者对这项技术发表了积极的评论，其中包括以太坊创始人Vitalik，他曾暗示这种系统可以部署在“以太坊3.0”之上。Ben-Sasson称：“我们的技术是独一无二的，因为它是目前唯一一个允许真正指数级加速验证的计算系统，无需设置假设，也无需事先分配任何密钥。”[2018/5/27]

除了检查这些战士的nCombatRounds模拟结果是否为给定的健康值外，我们还应该检查在战斗结束时是否有一个或两个角色已经死亡。如果想让战斗持续下去，直到有人死亡。我们没有在这个简单的例子中实现这一点，可以由读者来实现。在目前的代码中，只能模拟运行几轮，并在给定回合后，在任何一个玩家死之前停止战斗。然而，执行者不能对模拟回合的进行情况撒谎，因为这是我们要检查的。

运行！

我们可以运行Python模拟器，用以下命令编译我们的Cairo验证器：

>?python?combat.py>?cairo-compile?combat.cairo?--?output?combat-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:?Error?at?pc=0:201:An?ASSERT_EQ?instruction?failed:?1096?!=?1097assert?simulatedEndHealths?=?endHealths^*******************************************^

.pie文件包含了SHARP为我们进行证明生成所需的所有信息。SHARP是由StarkWare运营的一项服务，它可以生成证明，证明Cairo程序执行的有效性。然后，它将这些证明发送到以太坊测试网，由以太坊智能合约进行验证。

目前，SHARP不能在本地运行，从Cairo程序中生成证明的唯一方法是利用StarkWare的服务器来做证明验证。希望这种情况在未来会有所改变，任何人都可以生成关于任何东西的证明。StarkWare公司计划在稍后阶段发布SHARP的源代码。目前现状来说，去中心化的游戏无法使用Cairo来构建。

让我们向SHARP提交我们的工作吧：

>?cairo-sharp?submit?--?cairo_pie?combat.pieSubmitting?to?SHARP...Job?sent.Job?key:?f48c551e-c0c6-4cf5-8a52-a0aa1c43728cFact:?0x17ee903dfb54b55e53cc03d5a47602e83ed0ff9e219fe4567b8d59fa2666f682

过了很久，我们应该能看到我们的事实被验证了，而且是有效的：

>?cairo-sharp?is_verified?0x17ee903dfb54b55e53cc03d5a47602e83ed0ff9e219fe4567b8d59fa2666f682?--?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?-program?combat-compiled.json0x248070cb7b7f20b0b9445a382fdb4faa6b69c1f3653355077ae05b82c636ddf

这是我们之前所有工作的高潮，现代密码学的奇迹，一个简单的Solidity函数可以验证一个事实并检查程序输出programOutput是否有效。所有这些都不需要计算本身。

function?verifyCombatOutput(uint256?memory?programOutput)?public?bytes32?cairoProgramHash_?=?0x248070cb7b7f20b0b9445a382fdb4faa6b69c1f3653355077ae05b82c636ddf?//?Ensure?that?a?corresponding?proof?was?verified.?bytes32?outputHash?=?keccak256(abi.encodePacked(programOutput));?bytes32?fact?=?keccak256(abi.encodePacked(cairoProgramHash_,?outputHash));?require(cairoVerifier_.isValid(fact),?"MISSING_CAIRO_PROOF");?//?Ensure?the?output?consistency?with?current?system?state.?require(programOutput.length?==?10,?"INVALID_PROGRAM_OUTPUT");?require(player1.health?==?programOutput,?"INVALID_PROGRAM_OUTPUT?0");?require(player1.damage?==?programOutput,?"INVALID_PROGRAM_OUTPUT?1");?require(player1.attackRecoverTime?==?programOutput,?"INVALID_PROGRAM_OUTPUT?2");?require(player1.healthPerTurn?==?programOutput,?"INVALID_PROGRAM_OUTPUT?3");?????require(player2.health?==?programOutput,?"INVALID_PROGRAM_OUTPUT?4");?require(player2.damage?==?programOutput,?"INVALID_PROGRAM_OUTPUT?5");?require(player2.attackRecoverTime?==?programOutput,?"INVALID_PROGRAM_OUTPUT?6");?require(player2.healthPerTurn?==?programOutput,?"INVALID_PROGRAM_OUTPUT?7");?????//?Now?we?know?that?programOutput?and?programOutput?represent?the?resulting?health?values,?//?given?the?initial?combat?state?variables?programOutput!.?????//?Pure?Magic.}

这里cairoVerifier._isValid(fact)是一个Goerli的合约。

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

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

标签：LAYERPLAPLAYSTALAYER价格PLAT币PlayZapStabilize

欧易交易所app官网下载热门资讯