原文标题

Cheat-Proof Playout for Centralized and Distributed Online Games

作者

Nathaniel E. Baughman
Brian Neil Levine
Department of Computer Science
University of Massachusetts
Amherst, MA

年份

2001年

摘要

  我们探索了在客户端-服务器和分布式、无服务器架构的实时多人游戏中作弊的可能漏洞。 我们提供了网络游戏作弊的第一个形式，并提出了一套初步的强大解决方案。 我们提出了一种协议，它具有可证明的反作弊保证，但会遭受性能损失。 然后，我们开发了该协议的扩展版本，称为异步同步，它避免了惩罚，是无服务器的，提供可证明的反作弊保证，在丢包时具有鲁棒性，并提供显著提高的通信性能。 该技术适用于常见的游戏特征以及大规模多人游戏的聚类和基于单元的技术。 我们的性能声明得到了使用基于真实游戏轨迹的模拟分析的支持。

1 介绍

  我们探索了在客户端-服务器和分布式、无服务器架构作弊与玩游戏一样古老。 对于网络游戏来说，作弊与影响游戏质量的三大因素密切相关：实时交互的及时播放； 通信和游戏架构对大量用户的可扩展性； 以及防止或检测作弊玩家。
  在线、实时、策略游戏 [1]、第一人称射击游戏 [2]、[3] 和大型多人虚拟世界 [4]、[5] 都依赖于类似的模拟技术。 理想情况下，网络上的所有玩家都能够同步游戏事件和动作，这样玩家的控制和交互在所有玩家的观点上都是一致的。 然而，游戏经常以精确控制换取通信性能增益，以保持游戏播放的实时质量。
  当今最流行的是集中式客户端-服务器游戏架构，它提供单点游戏协调，但随着在线世界中玩家规模和数量的增加，会产生处理和信号传输的瓶颈。 转向分布式、无服务器架构可提高可扩展性和性能，但会使玩家交互复杂化，并增加在集中式方法中已经存在的作弊可能性。
  当前互联网上的游戏作弊比比皆是，但几乎没有或没有真正的安全措施可以防止网络游戏中的作弊。秘籍很容易下载和使用。在本文中，我们将防作弊交互和交互公平播放作为游戏交流的必要条件。我们表明，用于保持在线游戏实时质量的常见同步技术不利于游戏玩法，甚至会产生破坏游戏协调性的无法解决的情况。我们揭示了在常见同步技术下作弊的可能性，并表明作弊玩家与非作弊玩家无法区分。然后，我们提出了一种具有反作弊保证的多人游戏通信协议。该协议足以提供精确的玩家交互协调，但它不能扩展到大型虚拟世界。然后，我们使用在线游戏同步的新技术扩展协议，以保持协调性和安全性，同时提高可扩展性和性能。我们的协议也是第一个确保在分布式、无服务器架构下公平播放事件的协议，即没有可信第三方的架构。第二部分介绍了游戏架构的背景信息。第三部分考虑了游戏同步期间作弊的可能性。第四部分介绍了防止作弊的新协议。第五节对协议的性能进行了分析。第六节介绍了我们的技术如何与聚类和基于单元的技术相结合，以扩展到大规模多人游戏场景。第七节结束。

2 假设和术语

  在本文中，我们授予作弊者读取、插入、修改和阻止与游戏协议相关的消息的能力。我们开发了一些技术来防范对此类易受攻击的应用程序级信号的攻击。防止对现有传输层和网络层协议的攻击（例如拒绝服务攻击）超出了本文的范围。
  我们假设应用软件是用户可读的，并且将按照最初的预期执行其功能。此外，玩家可以获得客户端可用的任何信息，例如游戏状态或加密密钥。这一假设排除了任何通过默默无闻来使用安全性的尝试，这是当今游戏中的主要模型 [6]。有一个被入侵的客户端是可能的，但需要访问和理解原始源代码或更改应用程序编译版本的能力。防止由于客户端修改而导致的所有作弊超出了本初步研究的范围，留待未来工作。然而，本文中提出的用于防作弊播放的特定技术可以容忍对客户端的修改。

fig.png

  我们将随时描述游戏所需的一组信息称为游戏状态，它由实体状态组成。一个实体可能由多个游戏对象（例如军队）组成，并由玩家控制。我们可以将玩家称为玩游戏的人以及该人在游戏中控制的对象。游戏状态的划分如图 1 所示。自动化玩家是可能的。玩家做出决定，即他们决定改变自己状态的事件。当交互发生时，必须通过计算结果状态来解决多个玩家的决定。
  我们考虑模拟器，其中游戏中时间的进展（称为帧）与挂钟时间不同，模拟器计算每一帧的游戏状态。玩家在每一帧中恰好轮流一次。此类模拟器提供精确的游戏控制，但如果模拟器不能足够快地计算每个连续的游戏时间单位，则对玩家来说可能会显得很慢。就挂钟时间而言，如果玩家必须等待来自网络上的玩家的更新，则玩家也可能感觉到较慢的游戏进行。
  多人游戏通过集中式客户端-服务器或分散式分布式架构进行协调。架构因维护游戏状态的位置而异，其中涉及影响更改和协调交互。在客户端-服务器架构下，所有实体状态都由服务器维护，服务器根据来自客户端的输入计算游戏状态并将当前游戏状态通知客户端。在集中控制的客户端-服务器架构中，如图 2 所示，客户端向服务器发送请求以更改客户端的实体状态。在分散控制的客户端 - 服务器架构中，如图 3 所示，客户端将影响客户端实体状态的更新决策通知服务器，服务器解决游戏对象之间的交互并协调全局游戏状态。在分布式架构下，客户端被称为主机，每个主机维护自己的实体状态，通知其他主机决策，并在不使用任何集中授权的情况下解决任何交互。分布式架构（如图 4 所示）是无服务器的，也适用于点对点游戏。
  客户端-服务器架构在服务器上提供单点游戏协调。在分散控制的客户端-服务器架构中，服务器维护一个实体模型，该模型表示由客户端更新的最后一个已知实体状态。面对丢失的更新，服务器使用实体模型来解决任何交互，这可能导致服务器和受影响客户端之间的游戏状态视图冲突。但是，由于服务器有权维护游戏状态，因此客户端必须接受这些差异并符合服务器对游戏世界的看法。除了其他好处之外，这些简化使得客户端-服务器架构流行起来。实体模型也被分布式主机用于远程实体。然而，面对缺失的实体状态，无法在不破坏整体游戏状态的情况下做出交互决策。我们将在下一节进一步探讨这一点。
  每种架构都呈现出各种潜在的作弊结果。当玩家导致违反游戏规则或获得不公平优势的游戏状态更新时，就会发生作弊。例如，玩家可以通过使用一些根据游戏规则不允许玩家知道的游戏状态来作弊。

A 相关工作

  航位推算是一种技术，它通过允许主机根据最后已知的向量在缺少更新时猜测另一个玩家的状态来补偿网络中可变的通信延迟和丢失。航位推算是分布式交互模拟 (DIS) 和高级架构 (HLA) 标准 [7]、[8] 的一部分，研究人员和开发人员常用 [9]、[10]、[11]， [12]、[13]、[14]、[15]。在最简单的形式中，玩家的预测位置等于之前的位置加上速度乘以经过的时间。 Singhal 和 Cheriton 改进了这个基本公式 [13]。 Diot、Gautier 和 Kurose 在一个名为 MiMaze [11]、[12] 的简单分布式游戏中评估了桶同步与航位推算的性能。桶同步在每个主机上提供一系列桶，游戏中每个离散时间单位一个桶。每个存储桶收集从每个远程播放器发送的状态更新。当需要处理一个存储桶时（即游戏时间已达到该存储桶指定的时间单位），任何丢失的更新都将被计算在内。也就是说，缺席玩家的实体模型是使用前一个桶中玩家的状态来猜测的。
  以前的工作将航位推算作为及时玩游戏的必要技术，但在很大程度上将由此产生的实体交互解决问题作为未来的增强。在本文中，我们表明采用航位推算方案和解决实体交互是相互排斥的。在之前的工作中也没有解决同步方案下作弊的可能性。我们表明在航位推算系统中作弊是可能的。我们在本文的后面部分提供了作弊问题的解决方案。下一节表明，任何形式的航位推算都会导致无法解决的玩家交互，尤其是在分布式架构中。
我们的工作还涉及大型多人游戏和应用程序的兴趣管理技术 [16]、[17]、[18]、[19]、[20]、[21]。通常，兴趣分组是基于 (x,y) 网格坐标完成的，这是虚拟环境应用领域的自然兴趣聚类。第六节讨论了我们的工作如何利用这些技术。
  最后，我们的工作与并行模拟技术有关 [22]、[23]、[8]。并行模拟使用保守或乐观事件处理进行操作。在保守处理中，没有实体可能与其他实体不同步，因此不可能有事件的前瞻和处理。乐观技术允许实体异步执行事件，但在执行期间必须容忍不正确的状态或计算。通常，一旦意识到存在这种不正确的状态，计算就会撤消或回滚到最后一个正确的点。此方法要求保存状态。这种技术对实时多人游戏没有用，因为强迫人类参与者重新开始游戏中的先前点是不切实际的。在本文中，我们允许进行乐观处理而无需回滚。

3 公平的比赛

  如果每个玩家所感知的状态与游戏规则定义的每个其他玩家（包括服务器）的期望一致，我们将在线游戏定义为公平的。 以多种方式使用航位推算可能会使游戏事件的公平解决变得复杂。

A 无法解决的交互

  如前所述，玩家通过导致违反游戏规则或获得不公平优势的游戏状态更新来作弊。 实时交互的正确播放意味着每个玩家对游戏状态的感知都是相同的。 公平游戏是指玩家可以看到游戏规则所预期的事件发生并采取行动。 本文的目标是实现防作弊、正确和公平的游戏玩法。 在信号成本方面，解决方案必须可扩展到许多玩家，并保持播放，以便玩家可以最低限度地感知游戏时间提前的延迟。
  航位推算可用于客户端-服务器或分布式环境[11]、[12]，操作相同。 在中心化的情况下，交互由服务器统一解决，但不公平。 也就是说，服务器是用于解决交互的游戏状态的唯一权威，因此所有客户端都使用相同的结果世界视图进行更新。 但是，如果服务器使用航位推测状态来解决交互，则该决定可能与航位推测玩家的期望不同。 因此，航位推算的玩家可能会认为服务器的决定是不公平的，因为服务器没有使用玩家的真实行为。 由此产生的播放差异可能会导致游戏中的跳跃或其他伪影。 由于互联网的不可靠性和延迟可变性，游戏玩家无法容忍这种客户端-服务器的不公平。
  不公平决策的烦恼在分布式架构中变得具有破坏性，因为基于航位推算状态的交互可能会破坏每个主机看到的全局游戏状态。根据其他玩家的说法，由于主机之间的航位推测状态可能不一致，因此使用航位推测状态来解决交互会导致不公平的决定。在分布式上下文中，公平包括正确性。在分布式架构中解决基于航位推算状态的交互的结果是整个游戏状态可能不正确。例如，假设玩家 B 和 C 认为玩家 A 不采取任何行动，而实际上 A 摧毁了 B（现实被定义为公平正确地解决交互时的游戏状态）。如果玩家 B 在 A 的行动解决之前摧毁了玩家 C，那么游戏玩法就被破坏了。游戏时间可以恢复到交互之前的状态，但这显然不是一个公平或实用的解决方案，尽管它正是高层架构的乐观时间管理服务所采用的方法[8]。当使用航位推算并且交互由服务器不公平地确定或由分布式主机可能不正确地确定时，会导致无法解决的交互问题。

B 在航位推算下作弊

  在多人游戏中，作弊的可能性被广泛忽视。 许多游戏都是围绕客户端-服务器架构设计的，它提供了一些隐含的安全性以及对游戏状态的集中控制。 分布式游戏更容易作弊，但在客户端-服务器游戏中作弊也是可能的。
  存储桶同步下的一个安全漏洞是我们所说的抑制正确作弊，它允许主机通过故意丢弃更新消息来获得优势。假设在某种航位推算策略下，在认为玩家失去连接并从游戏中移除之前，允许进行n个桶的航位推算（分布式游戏中协调玩家的移除超出了本文的范围） .有了这样的策略，作弊的玩家可以在玩游戏时故意丢弃 n-1 个更新包。然后，玩家使用当前游戏状态的知识为第 n 个桶构建更新数据包，这提供了一些优势。一个简单的例子，让行动迟缓的玩家 S 追逐更敏捷的玩家 A。S 开始追逐，然后丢弃 n-1 次更新；同时，A 死亡推算 S 的缺失状态，但无法确认 S 的真实位置。对于第 n 个桶，S 发送一个伪造的更新，将 S 置于 A 之后。只要 S 每隔第 n 个桶发送似是而非的更新，就不能确认 S 是否在作弊； S 只是声称处于拥塞、有损链路上。这种作弊既适用于客户端-服务器游戏，也适用于分布式游戏。我们可以得出结论，当使用航位推算时，公平竞争与作弊是没有区别的。在本文的以下部分中，我们为作弊预防和检测提供了强有力的保证。

4 防作弊游戏互动

  大多数实时战略游戏需要在游戏中的每个离散时间单位或回合中进行交互解析。 类似于用于可靠传输的协议 [24] 的停止等待类型协议可以满足客户端-服务器或分布式架构的这一要求：在游戏时间推进之前，每个玩家做出的状态更改决策必须可用。 换句话说，对于 t 帧的游戏，所有玩家都停下来等待所有其他玩家决定并宣布他们在第 t+1 帧的轮次，并在继续到第 t+2 帧之前收到所有其他玩家的公告。 因为不允许航位推算，所以消除了抑制正确的作弊。 此外，由于所有状态决策在每一轮都是已知的，所有交互都可以由每个主机解决。
  这样的方案期望每个玩家将根据当前回合状态做出下一回合决定，然后将该决定发送给其他玩家。然而，这代表了另一个作弊的机会：作弊的玩家可以简单地等待，直到所有其他玩家都发送了他们的决定，我们称之为先行作弊。例如，B 可能对 A 进行致命射击，而在正常的人类反应时间内无法防御。然而，使用前瞻作弊，玩家 A 可能有一个作弊代理，及时发送决定提高盾牌。当采用停止等待型协议时，看起来较慢的玩家实际上可能正在实施先行作弊，这可能会很严重，具体取决于此类游戏功能。在本节中，首先我们提出一个协议，其中不可能进行前瞻作弊和抑制正确作弊。该协议具有性能缺陷，因为所有玩家的速率都被限制为最慢的玩家的速率。在本节的第二部分，我们提供了增强功能以允许公平游戏，同时允许玩家在游戏时间前进之前不等待所有玩家。

A Lockstep协议

  为了对抗前瞻作弊，我们提出了一种带有决策承诺步骤的停止等待类型协议。 我们将此安全版本称为锁步协议，它足以实现如下所述的锁步同步。
  假设回合 t 已完成。每个玩家决定但不宣布它的回合 t+1 。相反，每个玩家将其决策的加密安全单向散列作为承诺，包括随机填充，以避免可识别的散列决策和冲突[25]。一旦所有玩家都宣布了他们的承诺，玩家就会以明文形式透露他们的决定。主机可以通过将明文的哈希值与之前发送的提交值进行比较来轻松验证显示的决策。因为每个主机只有当前的转弯信息来做出它的下一个转弯决定，所以防止了前瞻作弊。等待不再有益。作为优化，如果所有其他主机已经提交了他们的决定，则不需要最后一个主机提交其决定；最后一位玩家可以立即透露其决定。
  锁步协议中所有参与者的两阶段承诺和所需的等待时间引入了性能损失。尽管通过防止前瞻作弊保留了正确的播放，但游戏和所有玩家将以最慢玩家的速度运行。其他玩家的数据包的接收很可能会因当前的网络状况而延迟。下一节介绍了一种同步机制和协议，它保留了锁步协议的理想属性，并允许游戏尽可能以独立于所有玩家的速度运行。

A.1 正确性证明

  锁步协议的安全性和活性证明表明，它通过不产生错误条件并始终在进步来满足其要求 [24]。 我们做了一些假设：所有参与者之间都存在可靠的渠道； 所有玩家都知道所有其他玩家； 玩家能够验证来自其他玩家的消息； 并且所有参与者在做出决定和披露承诺之前只等待有限的时间。
  定理：锁步协议是安全的：在游戏规则允许之前，任何主机都不会收到另一个主机的状态； 如果 A 在 A 提交 t 处的事件之前知道 B 在帧 t 的状态，则会发生错误，其中 A 和 B 是任意两个玩家。 锁步协议是实时的：每个玩家解决的帧随着挂钟时间单调推进。
  证明：锁步属性的安全性直接来自协议规范。 让 AN 等于任意玩家 A 正在解决的当前帧。最初，AN = 0。根据协议描述，一旦收到所有其他玩家的承诺，A 就会宣布它为 AN 做出的决定的散列版本 对于同一帧。 A 不会在时间 AN + 1 内宣布其承诺的决定，直到来自其他所有参与者的时间 AN 的决定被揭示、接收并根据承诺进行验证。 任何玩家，包括 A，都不能因为哈希承诺而改变宣布的事件。 因为 A 可能不会前进，所以其他参与者不可能在当前正在解决的帧之前了解 A 对稍后帧的决定。
  对于活跃度，让 t1 是任意玩家 A 开始解析游戏帧 AN 的挂钟时间。 设 t2 是所有玩家学习帧 AN 中所有其他玩家的已揭示决策的挂钟时间； 让 t2 = ∞" 如果这永远不会发生。让 t3 是玩家 A 前进到时间帧 AN + 1 的挂钟时间；如果这永远不会发生，让 t3 = ∞。我们将证明 t1 < t2 < t3 并且 t3 是 有限。
  假设玩家 A 不是最后一个提交的玩家。 令 AN(t) 等于玩家 A 在挂钟时间 t 处的变量 AN 的值。 设 AN(t1) = i。 根据协议的定义，我们知道 AN(t2) = i。 因为所有参与者在做出决定之前只等待有限的时间，并且因为所有的通信都是通过可靠的渠道进行的，所以我们知道最后一个参与者的承诺将在有限的时间内收到，因此，t2 是有限的。 因为协议是安全的，我们知道 AN 的值只在 t3 时刻增加到 t+1。 从算法的陈述中可以清楚地看出，AN(t) 是一个不随时间递减的值。 因为 AN(t) 是非递减的，所以 t2 < t3。 因为所有参与者都在有限的时间内通过可靠的渠道披露承诺，所以 t3 也是有限的。
如果玩家是最后一个提交的玩家，则可以构建类似的证明。 在这种情况下，是 A 的通信确保 t2 和 t3 是有限的。

B. 异步同步(AS)

  在本节中，我们提出了一种新的同步技术，它可以保证公平播放，称为异步同步 (AS)，它通过分散游戏时钟来放宽锁步同步的要求。每个主机与其他主机异步地在时间上前进，但在需要交互时进入锁步式模式。保证正确的播放和公平。锁步机制的异步操作提供了性能优势，因为有时即使没有与所有其他玩家接触，玩家也可以提前游戏时间。这种宽松的联系要求可以克服间歇性缓慢的网络信令、数据包丢失或缓慢的主机处理。我们不希望使用 AS 来让网络和主机资源完全不同的玩家一起玩。相反，对于这个初始设计，AS 是一种技术，可以隔离大部分时间以相同速率玩游戏的玩家之间暂时连接不良的影响，并减少解决交互所需的时间。

B.1 影响范围(SOI--Spheres of Influence)

  使用AS，每个玩家的主机在游戏过程中跟踪每个玩家在游戏时间和空间上的进步。下一轮可能受到玩家影响的游戏区域——因此可能需要其他玩家决定来解决——被称为玩家的球体影响范围 (SOI--sphere of influence)。我们将影响力定义为影响玩家决策的任何游戏内信息，从而影响玩家决策的结果；其中游戏内指的是游戏世界的一部分，而不是玩家可能拥有的外部知识，例如某个对手通常遵循某种策略。因此，影响范围是游戏中的区域，包含对玩家即将做出的决定产生潜在影响的所有来源。因此，玩家当前 SOI 之外的任何事情对于玩家的游戏决策和由此产生的事件都是无关紧要的。例如，如果玩家不在森林的可听到范围内，那么玩家不在乎倒下的树是否发出任何声音，也不在乎它是否倒下。
  在 AS 中，每个参与者都考虑两种 SOI 的交集。首先，玩家自己的 SOI，它表示一个几何区域，其中做出的决定会影响玩家下一轮的决定，并且必须与玩家的决定一起解决。其次，远程玩家的 SOI，表示下一轮可能受到其他玩家影响的区域。因此，如果两个玩家的 SOI 在某个回合内不相交，那么他们决定的事件在解决该回合的游戏状态时不会相互影响。
  在基于 AS 的游戏中，每个主机可能会在不同的时间范围内做出决定，并独立于其他主机而推进其时间范围； 详情在后面描述。 因此，SOI 由两部分组成。 基础 SOI 是在任何一圈可能影响或被影响的最大面积。 delta SOI 是可能发生在后续转弯中的影响区域的变化。 Base 和 delta 表示为半径，如图 5 所示，并将 delta 添加到 base 以计算后续匝数。

图5.png

B.2 异步同步协议

  我们对 AS 协议的描述是从分布式、无服务器架构中的一台主机的角度来看的。 该协议可以很容易地适应集中式架构。 该协议的正式描述在图 6 和图 7 中给出，因为它将发生在玩家 l 处的任意回合 t。 如果玩家到达了第 t 回合，那么我们假设它已经显示了第 t-1 回合的状态。

图6_图7.png

  为简单起见，我们假设按顺序、完全可靠地传送数据包。 在本节后面，我们将协议扩展到乱序、不可靠的消息传递。 未显示的是在游戏开始之前发生的初始化阶段：每个玩家学习远程其他玩家的完整集合 R，并启动每个远程玩家 r 为 R 子集，与其他每个玩家同步，直到初始位置 其他玩家通过网络接收。
  对于任意回合 t，玩家首先确定该回合的决定（步骤 1），然后向所有玩家宣布该决定的承诺（步骤 2）。 第三，接受远程播放器最后显示帧后一帧的承诺（步骤 3）。 在透露其承诺之前，本地玩家必须确定它正在等待哪些远程玩家（步骤 4）。 仅当与从远程播放器的最后显示帧扩展的 SOI 没有交集，或者如果来自远程播放器的承诺已被本地播放器接受时，远程播放器才不处于等待状态。
  每个其他远程玩家的 SOI 使用最后一个已知位置的基本半径加上本地玩家领先于远程玩家最后一个已知时间帧的每个时间帧的增量半径来计算。 如果本地主机在未来相对于另一个玩家，那么另一个玩家影响本地玩家下一个决定的潜力会扩大到本地玩家的下一个时间范围（图 8a）。 如果本地主机不是远程主机的未来，则不执行扩张。 图 8b 示出了在本地玩家移动到下一个时间帧而没有从远程玩家接收到显示状态时 SOI 的交叉点，如图 8b 所示。

图8.png

图9.png

图10.png

  作为说明性示例，请考虑图 9 和 10 中描绘的情况，从模拟结果得出。图 9 显示了一对玩家在游戏的 xy 平面中相互交叉。 z 轴代表每个玩家对应的 xy 坐标的帧。两个玩家的路径都从第 0 帧开始，到第 111 帧结束。 考虑另一组玩家 C 和 D，它们在游戏中采用相同的路径，但必须同步进行。玩家 C 和 D 具有与玩家 A 和 B 相同的帧对 xy 坐标图。图 10 显示了 xy 平面中的相同路径，但 z 轴表示每个坐标的玩家的挂钟时间。玩家 C 和 D 由在挂钟时间（z 平面中较高）中缓慢前进的两条线表示。
  相比之下，玩家 A 和 B 则按照 AS 算法前进：他们可能会尽可能快地前进，只有在他们的 SOI 相交时才同步前进。图 10 显示玩家 A 和 B 仅在两人在 xy 平面上相互接近时斜率急剧增加。玩家 A 和 B 无需等待其他玩家的消息继续游戏，因此不受网络延迟的影响。相比之下，玩家 C 和 D 必须不断地等待对方，因此网络延迟会影响游戏的每一刻。
  使用 AS，类似于锁步协议，防止前瞻作弊：通过提交下一轮决策的散列，直到所有主机都在同一时间框架内提交或揭示了过去的决定以消除作弊的可能性（即潜在的用于交互）。 AS 也以与锁步协议相同的方式消除了抑制正确的作弊。宿主无法及时推进，直到一回合内的所有潜在影响都已解决。前瞻欺骗似乎比锁步同步更严重：主机可能故意落后于其他主机以预览未来的信息。但是，主机无法及时前进到检测到潜在影响的时间点，因此作弊是没有用的，因为没有玩家会受到作弊的影响。 （注意简单的位置跳跃很容易被检测到，因为它位于来自已知位置的扩张 SOI 之外）。根据 SOI 的定义，推进主机发布的未来信息对任何其他玩家的游戏决策都无关紧要。
  请注意，AS 信令可能会向玩家提供有关其他玩家的预先位置信息，这将不允许对游戏进行作弊，但可能会改变玩家的策略。 但是，我们在第六节中提出了针对集中式和分布式架构的这种情况的解决方案。
  AS 协议还保留了锁步同步保证正确和公平的播放，因为所有交互都通过游戏中每一轮的完美信息来解决。 性能提升是在不可能进行交互时独立于远程主机及时推进的能力。 我们在第五节中通过模拟展示了这种性能提升。
  使用 AS 协议的分布式游戏中的主机可以尽可能快地执行，直到检测到潜在的影响重叠。 为了保持设定的游戏帧率，设计者可以强加最大游戏速度。 （第 5 部分中的模拟结果使用了类似类型的上限速率。）充其量，一旦检测到 SOI 交叉点，主机将只需要等待另一个玩家的一次更新，这将限制其潜在的 SOI 并允许 本地主机继续。 在最坏的情况下，潜在的交互玩家必须及时赶上速度更快的主机才能解决实际交互。 例如，当落后玩家以最大增量速率直接向另一个玩家的未来位置移动时，就会发生这种最坏的情况。 否则，过去玩家的扩张 SOI 将不会与未来玩家的 SOI 相交，未来玩家可能会继续。

B.3 有丢包的 AS

  虽然我们的 AS 证明假设所有参与者之间存在可靠的通道，但可以放宽这个假设。 简单地说，当丢失的数据包代表 SOI 交叉点之外的状态时，玩家可以跳过丢失的数据包并接受来自其他玩家的新的、无序的数据包。 不能丢弃或跳过表示 SOI 交集的丢失数据包。 我们在此不提供新的证明，但是，可以通过检查丢失数据包导致的扩张 SOI 是否导致交叉来轻松构建； 如果没有，数据包可能会被跳过。 很明显，协议有足够的信息来确定如果最终收到丢失的信息是否可能导致 SOI 交叉。
  我们可以得出结论，AS 比锁步具有性能优势。 而不是每回合都联系每个玩家，使用 AS，玩家只需要联系具有 SOI 交叉点的玩家。 换句话说，20 个 SOI 半径外的玩家只需要在 20 回合后听到，就可以确定没有 SOI 交叉点。 下一节将更详细地探讨其他性能优势。

C. 秘密财产

  许多游戏都包含秘密信息的概念，这是一种有价值的游戏状态，可能只有一部分玩家知道。一种类型是秘密财产，即玩家选择不立即向其他玩家透露的物品，条件是在物品被揭露之前不对物品采取任何行动。
  分布式游戏中的玩家可能希望隐藏一个对象，例如武器或钥匙，以备后用。然而，对手可能希望证明该对象实际上是在游戏规则内更早获得的。例如，在夺旗游戏中，玩家可以夺取对手的旗帜带回本垒以赢得比赛。玩家可以隐藏哪个游戏士兵有旗帜，导致对手在不清楚哪个有旗帜时必须中和所有跑向本垒的玩家士兵。为了解决这个难题，我们将承诺定义为秘密财产的占位符，条件是远程玩家声称与隐藏财产不存在潜在的交互。 Promise 可以通过散列或加密的承诺发送给对手并稍后显示的形式轻松实现。对手必须签署承诺，以防止否认未承诺该秘密。有希望的玩家可以选择不继续游戏，直到对手签署承诺。
  为了让本地玩家 L 相信隐秘的远程玩家 S 是诚实的，我们提出了一个作弊检测方案，它不能防止作弊，但允许它被发现。除了承诺之外，S 还必须承诺其当前（秘密）状态，例如，使用锁步协议中的单向哈希函数。 L 记录提交状态。状态在指定时间显示和验证，要么在游戏完成后，要么基于某个过期时间，在此之后旧的秘密信息被视为解密，或者不再重要而不再保密。我们将记录器服务定义为一种驻留在每个主机中并记录承诺信息以供稍后验证的机制。为了提供更实时的作弊检测解决方案，我们将观察者服务定义为一个可信的、集中的实体，它通过安全渠道接收秘密信息并在游戏过程中对其进行验证。如果检测到作弊，协议可以提醒玩家并提示采取一些行动；例如，从当前游戏中移除并从锦标赛中移除。
  如果 L 永远不知道 S 的位置，则不会为 L 提供异步操作，因为 L 只能以 S 的承诺的速率及时推进，假设 S 只能在每个时间范围内发出一个承诺。如果 L 希望比 S 在时间上前进得更快，那么 L 必须确定 S 的扩张的潜在 SOI 不与其自身相交，否则潜在的相互作用可能无法解决。为了保持异步时间提前的好处，我们提供了一个集中的解决方案。承诺服务是一个可信的、集中的实体，它以与观察者服务相同的方式接收秘密和非秘密信息。承诺服务将 S 的 SOI 扩展到 L 的时间范围，如果不存在交互，则向 L 发出承诺。假设 promise 服务主机的执行速度至少与 L 的主机一样快，即使在 S 没有及时推进的情况下，也可以向 L 发出 promise。没有向 L 透露任何秘密信息，并且由于承诺服务在制定 AS 协议时保证了交互解决。 Promise 服务还解决了没有玩家可能知道另一个玩家的实体状态的情况。 SOI 由承诺服务扩展并代表每个参与者发出承诺。引入这样的集中式解决方案抵消了为大型分布式模拟环境部署 AS 的潜力，分布式解决方案留待未来工作。

5 性能分析

  我们通过仿真分析了 AS 协议与锁步协议相比的性能。 我们没有与航位推算技术进行比较，因为很明显航位推算会表现得更好，但会为集中式架构和分布式架构中的不可解决事件引入不公平的操作。
  我们不知道有任何工作可以提供典型游戏玩法的分析模型。 因此，我们从具有代表性的游戏 XPilot [26] 中获取痕迹，这是一款联网的多人游戏，玩家可以在二维空间中控制船只。 因此，我们不能声称本节中提供的结果是通用的。 但是，我们希望它们具有代表性。
  我们构建了一个自定义模拟器，它根据来自真实 XPilot 会话的跟踪来控制游戏中的每个玩家。 我们将 XPilot 配置为在 300 x 300 大小的地图上运行大约 4000 帧的游戏，并在不同数量的自动播放器上运行，并修改游戏以将 xy 坐标信息记录到文件中。 直到所有玩家都加入游戏后才开始记录。 我们的模拟器将日志作为每个玩家的输入，日志中的每个 xy 坐标都被认为是每个玩家做出的回合决定。
  每个模拟器时间单位代表挂钟时间的 10 毫秒。 在模拟器中的每个时间单位，玩家都可以从日志中读取下一个回合并将该回合发送给其他玩家。 但是，根据反作弊约束，锁步或 AS 协议会适当地阻止决策的发送。
  我们假设玩家之间采用星型拓扑。 每个玩家的网络连接到星形拓扑的中心点都有延迟，该延迟是从指数分布中得出的，每个回合都从平均为 5 个模拟器时间单位的指数分布中得出。 一个简单的指数分布适用于这个初步调查； 我们未来的工作将包括模拟更多不同的分布和网络拓扑。 星形拓扑有两种解释。 第一个是数据包从每个玩家组播到其他玩家。 第二个是数据包被单播到位于星星中心的非播放服务器，然后立即并同时将数据包单播给其他玩家。
  玩家轮流的次数不能超过模拟的每 4 个单位，因此我们与先前模拟工作[11]、[12] 所假设的人类反应时间限制保持一致； 我们将其称为下限。 此外，玩家有一个上限：每经过 10 个单位的模拟器时间，他们不能轮流前进超过一次。 这是为了模拟以每秒 10 帧的速度运行的游戏，这与典型的 XPilot 游戏一致。
  例如，考虑一个在模拟器时间 30 的玩家，他刚刚读取游戏第 3 帧的决定并将其发送给所有其他玩家。 它必须等待 4 个步骤才能读取下一个回合（下限），并且在达到模拟器时间 40（上限）之前可能不会发送数据包。 但是，请考虑是否由于锁步约束，玩家被迫等到模拟器时间 51 才能发送第 4 帧的数据包。 由于从跟踪中读取第 4 帧以来已经过去了四个时间单位，并且由于时间 50 已经过去， 它可以立即从跟踪日志中读取第 5 帧，并且可以尝试立即发送数据包（受锁步约束）。
  我们记录了 10、18、30 和 37 名玩家的踪迹。 我们未来的工作将包括对更多玩家的研究； XPilot 不适合与数百名或更多玩家一起玩的游戏。 将我们的模拟视为基于单元格或集群游戏中的一个单元格的模拟也是合适的； 这将在第六节进一步讨论。 对于每条迹线，我们的模拟器使用了四种不同的 SOI 尺寸。 可用的最小 SOI 被设置为任何玩家在单个回合中可以移动的最大距离。 我们希望这是实际使用的大小。 模拟的最大 SOI 具有无限大小，与锁步协议完全对应。 为了比较，我们还模拟了两倍最小 SOI 尺寸（在图中表示为 soi-2x）和四倍最小 SOI 尺寸（表示为 soi-4x）。

图11-1.png

图11-2.png

图11-3.png

图11-4.png

  图 11 显示了 10、18、30 和 37 名玩家的轨迹结果。每张图都显示了一个直方图，表示由于锁步反作弊约束，普通玩家在帧之间停滞的时间分布；即，从上一回合开始测量，平均玩家在每回合做出决定之前所延迟的毫秒数可以通过网络传输。由于上限和下限导致的停顿时间不包括在这些结果中，因为它们不参与 AS 计算。
  仿真结果清楚地展示了AS协议的性能优势。使用锁步协议，玩家总是等待最慢的玩家发送他们的决定。使用 AS 协议，即使对于更多的玩家，也可以毫不拖延地进行至少 50% 的回合以进行玩家协调，同时仍能保证防作弊的游戏玩法。即使玩家必须被拖延，AS 协议也能让玩家拖延更短的时间。仿真表明，虽然 AS 性能下降缓慢，但锁步协议也是如此，并且 AS 始终保持着很大的优势。我们希望这些结果适用于大型环境中的大量玩家，我们未来的工作将是测试这一理论。此外，在下一节中，我们将介绍一种支持分布式基于单元的游戏玩法的技术，这样玩家只需联系自己单元中的其他玩家，同时仍然遵循反作弊约束。

6 支持基于单元的架构

  为了将大型多人游戏扩展到数千或更多参与者，每个客户端的通信和处理量必须对所有相关实体保持低水平。 对于基于服务器的架构和无服务器架构来说都是如此。 一种常用的方法不是采用基于客户端或服务器的过滤，而是根据几何位置将参与者聚集到单独的多播地址或单独的服务器中。 因此，虚拟比赛场地可以分成多个单元以增加可扩展性 [16]、[17]、[18]、[19]、[20]、[21]。 单元格对玩家的游戏视图是透明的。
  AS 技术与基于单元的技术很好地结合在一起。 单元尺寸应该比 SOI 尺寸大很多。 玩家只能为同一单元格内的玩家执行 AS。
  不幸的是，作弊玩家可能会使用在正确操作 AS（或航位推算或锁步）所需的信号中可用的单元格位置信息，以便获悉即将发生的伏击。 虽然了解远程伏击或隐藏控球的位置可能不会影响第三节中讨论的游戏分辨率，但它可能会影响玩家策略。
  在客户端-服务器架构中，秘密信息不存在问题，因为可以信任服务器来解决交互和推进玩家，而无需向玩家透露秘密信息。
  对于分布式架构，秘密信息为 AS、航位推算和锁步方法带来了困难的困境。 玩家必须交换位置信息才能执行协议，但信号代表了通过向玩家提供位置的预先知识来作弊的机会，可能会改变他们的策略。
  在本节中，我们将在 AS 协议的上下文中提出该问题的解决方案。 以下技术可以让玩家发现他们是否占据了同一个模拟单元，而无需互相透露他们当前的位置。

A. 隐藏位置

图12.png

  假设游戏场地被划分为 n 个单元，如图 12 所示。让游戏的每个单元分配一个从 1 到 n 的数字。 假设玩家 A 在单元格 1 <= x <= n 中，玩家 B 在单元格 1 <= y <= n 中。
  每当玩家决定进入一个新单元格时，它都会参与此协议。 不幸的是，它必须与所有玩家进行交换以确定谁在同一单元格中。 可选地，一旦在同一单元格中找到任何玩家，单元格内的玩家可以将所有其他单元格成员通知新参与者。 但是，我们不在这里讨论这种优化的细节。
  假设下面使用的密码系统是可交换的（例如，RSA [27] 或 Pohlig-Hellman [28]），因此对于任何消息 M，我们有 Ek(E'k(M)) = E'k(Ek(M)) ，其中 Ek 表示使用密钥 K 对消息进行加密。该方案还需要所有参与者之间进行密钥交换，我们在此未指定，但已经存在几种可以使用的方法（Schneier 列出了几种 [25]）。

step.png

  B 可以通过要求 A 加密几个选项来尝试作弊。 但是，我们要求每个玩家稍后在第 4 步和第 6 步中透露他们的承诺。在最坏的情况下，这可能会在游戏结束时完成。

7 结论

  我们第一次将防作弊播放作为网络游戏通信架构设计的必要条件。我们已经证明，以前的网络游戏通信方法可以被欺骗玩家利用。我们提出了第一个为集中式和分布式网络游戏提供防作弊和公平播放的协议。为了提高该协议的性能，我们提出了异步同步协议，该协议允许事件的乐观执行，而不会因丢包或作弊而导致状态冲突的可能性。异步同步不需要回滚技术或中央服务器。我们的性能分析表明，它比锁步协议显着提高了性能。异步同步提供了面对丢包时的隐性鲁棒性，并允许与基于单元的技术结合使用减少的信令要求，同时始终保持作弊预防和检测，允许大规模多人游戏环境。

致谢

  我们感谢马萨诸塞大学的 Andy Fagg、普渡大学的 Amherst 和 Mikhail Atallah 的有益见解。 本文档中包含的技术已在全球范围内受到专利保护。 这项工作将出现在 IEEE Infocom 2001，2001 年 4 月，并受版权保护。 允许将本作品的全部或部分制作数字或硬拷贝以供课堂使用，但不收取任何费用，前提是拷贝不是为了盈利或商业利益而制作或分发的，并且所有拷贝都带有此完整的通知和完整的引文。

参考

引用_1.png

引用_2.png

引用_3.png