区块链数据分类的高效化

By Enrique Piqueras 28/Aug/2018

如果方法不得当，在诸如游戏之类的抽签中计算动态投注额会消耗很高的算力。下面，让我们看一个比较合适的方案......

在去中心化的应用程序中，最普遍的抽签方式就是：使用与用户所持有的令牌数量成比例的一个随机数。 如果只允许增加用户持有量，这就非常简单。 但是，如果你想在所有抽签轮次中自由更改用户持有量时，抽签的随机计算就会变得非常复杂......

基本的方式

构建这样的系统最简单方法是创建一个虚拟列表，其中包含每个参与抽签地址的区段。 使用一个存储变量来跟踪列表大小，并且每当有人改变持有量时：

    tokenHolder.segmentStart = segmentSize;
    segmentSize += _stake;
    tokenHolder.segmentEnd = segmentSize;

这种方法存在两大问题（尽管根据使用情况，可能不会很严重）。首先，如果持有人希望更改或删除他们的投入额，那么拼接这个列表的计算成本会很高。其次，获得被抽中者需要迭代每位持有者，如下所示：

    // O(n) where n is the number of token holders with stake
    for (uint i = 0; i < tokenHolders.length; i++)   		
        if (currentDrawnNumber < tokenHolders[i].segmentEnd)       		
            return tokenHolders[i].address

   在任何规模可观的系统中，每次抽奖都会需要很多算力。 这种算法还制造了O（d * a）个影子漏洞，其中d是抽签次数，a是令牌持有者的数量，因为攻击者可以用最低额创建大量账户。 这意味着唯一合理的方法是让令牌持有者检查自己是否被抽出。 这严重限制了智能合约实施自动化的逻辑，无法实现自动抽取和通知被抽取者。

树状数组解决方案

在寻求更好的方法过程中，我们的首席技术官Clément Lesaege从一种复杂的数据结构形式里找到了答案：K-Ary树状数组。 K-Ary树状数组的每个非数据点都有K个子节点并且保存所有节点的值的总和。 这意味着我们关心的实际值都是数据点，经证明以这种方式组织数据对性能有非常大的提高。 比如一个二进制的树状数组（K = 2），其中Alice有10个令牌投注，Bob有15个令牌投注，Carl有20个令牌投注，Dave有5个令牌投注，看起来像：

             二进制树状数组示例

在以上示例中，假设我们抽取到数字13，寻取方式如下：

首先13落在[0-24,25-49]的哪个区？ 0-24，所以往下进入左侧区域。

之后判断13 落入[0-9,10-24]的哪个区域？由此抽取到鲍勃。

现在，假设我们抽取到2。同理，从根开始，但是这次27落到25-49，所以我们进入右侧区域。

同样对[0-20,21-24]重复相同的过程，但是使用2而不是27，因为您通过跳过第一级中的左节点“花费”了25，于是抽取到了卡尔。

所以这个数据结构让我们的抽取复杂度变为O（K * log（n）/ log（K）），其中K是每个节点的子节点数。 log（n）/ log（K）是遍历K次数据节点数的数值，换句话说，就是数据结构的层级数。 将它乘以K是因为在最坏的情况下，你必须查看你遍历的每个节点的每个子节点，以确定是否遍历下一个节点。

设置，删除和追加的复杂度都是O（log（n）/ log（K）），因为是从给定的数据节点开始，逐级向上操作。 注意保留一定量的空闲数据节点，是保证在删除操作中保持数据结构完整的捷径。 这些操作非常容易实现：

• 设置：设置新值并更新根值。
• 删除：将值设置为0，将数据节点推送到一个空闲节点，然后更新根节点。 请注意，这个操作实际上并没有从数据结构中删除节点，因此n永远不会减少。
• 追加：从前面提到的空闲堆栈中弹出一个节点，否则追加一个新节点，并赋值。
  

执行过程中的算力节省

因为结构中的数据并未被删除（它们只被设置为0并被推送到堆栈），所以在执行过程中可以节省一大部分的算力。 我们只需要一个空闲节点堆栈列表和一个数据结构中实际值的列表。 如上例所示，列表会是：[50,25,25,10,15,20,5]。 使用以下等式可以轻松实现节点遍历：

• 节点 i 的第C个子节点：K * i + c。 原理：首先必须跳过每个 i 之前的节点的和它们的子节点， 所以是K * i ；然后加上c来得到你想要的子节点。
• 节点 i 的根节点：（i-1）/ K 。原理：跳过多少个有K个子节点的节点才能到达i。
• 检查节点 i 是否是第一个/最左边的节点：（i-1）％K === 0。基本原理类似于找到根节点的，当余数为0时就是第一个/最左边的节点。
  

Kleros的实例

Kleros智能合约库的数据结构文件夹中，包括了k-ary树状数组的开源实现（每个节点的子节点数目可以自定）：https://github.com/kleros/kleros/tree/master/contracts/data-structures里面包括了一个继承该功能的分类树状数组智能合约，可用于所有需要分类的智能合约。

加入Kleros！

加入Telegram上的社区聊天
访问我们的网站
在推特上关注我们
加入我们的Slack进行开发人员对话
贡献于Github