如果方法不得当，在诸如游戏之类的抽签中计算动态投注额会消耗很高的算力。下面，让我们看一个比较合适的方案......8 L5 t, E3 H, U( @& \: v

: f. H' I! {9 B# |! {  S3 k) x7 Q- v    在去中心化的应用程序中，最普遍的抽签方式就是：使用与用户所持有的令牌数量成比例的一个随机数。如果只允许增加用户持有量，这就非常简单。但是，如果你想在所有抽签轮次中自由更改用户持有量时，抽签的随机计算就会变得非常复杂......
  P0 i6 _' d5 D- }' A. w! q
! m7 ^. I; ^1 C0 f, h9 {2 U- z    基本的方式, Z& z: q( b& H4 y& y

6 I  Q6 p" ]* k  A' ~9 G    构建这样的系统最简单方法是创建一个虚拟列表，其中包含每个参与抽签地址的区段。使用一个存储变量来跟踪列表大小，并且每当有人改变持有量时：9 G9 @0 |0 q: ?

7 v% R7 W& Z  g% I; y1 i    tokenHolder.segmentStart=segmentSize;
& w) H; B; ]4 c% n
" z0 ]8 g( z( ^1 k    segmentSize+=_stake;
/ z5 g4 O9 O' n6 Q$ ^  t: i8 b, f4 Y
    tokenHolder.segmentEnd=segmentSize;
( Q5 g+ Z$ Z7 O$ h! t- W' F
6 E% H# t6 v; S4 ?; o) ~" @# `    这种方法存在两大问题（尽管根据使用情况，可能不会很严重）。2 ?' w! a# v; o# ~

7 u) h* I! K9 V    首先，如果持有人希望更改或删除他们的投入额，那么拼接这个列表的计算成本会很高。4 D# y  t# f2 R# j; F

9 d  g' o+ b$ H  e5 U! ^) y    其次，获得被抽中者需要迭代每位持有者，如下所示：- z2 p& M. N7 D/ l  N6 f* x
$ J3 G( _" ?8 K) b' @
    //O(n)wherenisthenumberoftokenholderswithstake
+ p6 ^1 C( z" B$ y9 H1 H, h2 c4 l: J8 T! C8 I+ S+ B
    for(uinti=0;i
+ K7 b; }2 s# i! ~# d9 M! v
% @9 `! \- X( A. J( g6 ^    if(currentDrawnNumber.segmentEnd)! k: K5 x- ]* V/ h+ b; I

/ [" e. v9 }# N+ D* j  N    returntokenHolders.address- u3 u, g( x3 U3 o& F. @
' s6 _7 I+ o3 {8 H3 ?4 i
    在任何规模可观的系统中，每次抽奖都会需要很多算力。这种算法还制造了O（d*a）个影子漏洞，其中d是抽签次数，a是令牌持有者的数量，因为攻击者可以用最低额创建大量账户。这意味着唯一合理的方法是让令牌持有者检查自己是否被抽出。这严重限制了智能合约实施自动化的逻辑，无法实现自动抽取和通知被抽取者。
2 {$ n- b. J' F) s
  `8 ~6 V: O4 `' H8 y  ]" k  r5 c    树状数组解决方案3 g% {/ o: x" W9 {5 b% m( Q! |

' Z  a4 a9 i, z0 J) C    在寻求更好的方法过程中，我们的首席技术官ClémentLesaege从一种复杂的数据结构形式里找到了答案：K-Ary树状数组。K-Ary树状数组的每个非数据点都有K个子节点并且保存所有节点的值的总和。这意味着我们关心的实际值都是数据点，经证明以这种方式组织数据对性能有非常大的提高。比如一个二进制的树状数组（K=2），其中Alice有10个令牌投注，Bob有15个令牌投注，Carl有20个令牌投注，Dave有5个令牌投注，看起来像：
) K2 }, F- V* ?$ \  y$ i* M4 d8 X. B0 Y/ \( N
    二进制树状数组示例
0 c/ O) A9 x+ e0 J1 B
0 \: }* I* Z" I; t$ v% G    在以上示例中，假设我们抽取到数字13，寻取方式如下：首先13落在[0-24,25-49]的哪个区？0-24，所以往下进入左侧区域。之后判断13落入[0-9,10-24]的哪个区域？由此抽取到鲍勃。: D* A+ x/ H1 L: W
% G" }) S! B( N! B
    现在，假设我们抽取到2。同理，从根开始，但是这次27落到25-49，所以我们进入右侧区域。同样对[0-20,21-24]重复相同的过程，但是使用2而不是27，因为您通过跳过第一级中的左节点“花费”了25，于是抽取到了卡尔。4 K' c7 t8 v! _* z7 P/ q7 e+ P) ?

# F" Q1 \2 r% w# ~2 p    所以这个数据结构让我们的抽取复杂度变为O（K*log（n）/log（K）），其中K是每个节点的子节点数。log（n）/log（K）是遍历K次数据节点数的数值，换句话说，就是数据结构的层级数。将它乘以K是因为在最坏的情况下，你必须查看你遍历的每个节点的每个子节点，以确定是否遍历下一个节点。' E2 ^/ ?  L; x0 t
. V. r( a. @* p3 Y% ?+ Y
    设置，删除和追加的复杂度都是O（log（n）/log（K）），因为是从给定的数据节点开始，逐级向上操作。注意保留一定量的空闲数据节点，是保证在删除操作中保持数据结构完整的捷径。这些操作非常容易实现：
9 B# L7 f* t! C! a
/ c2 k5 b4 f! k! S    设置：设置新值并更新根值。
( b8 N( k+ X9 e$ h6 ~
0 U) }' T3 X9 e  \3 y) {    删除：将值设置为0，将数据节点推送到一个空闲节点，然后更新根节点。请注意，这个操作实际上并没有从数据结构中删除节点，因此n永远不会减少。7 W5 O1 E/ F( M" K
7 m; e% a3 z$ e
    追加：从前面提到的空闲堆栈中弹出一个节点，否则追加一个新节点，并赋值。
9 J" C* a1 i/ l- T5 h
5 O- w& c* T4 r; M5 ~1 t3 S$ T    执行过程中的算力节省
, {7 Y. d7 {% e$ A0 n- Q
0 T$ a  L  V( v6 R* ^% I    因为结构中的数据并未被删除（它们只被设置为0并被推送到堆栈），所以在执行过程中可以节省一大部分的算力。我们只需要一个空闲节点堆栈列表和一个数据结构中实际值的列表。如上例所示，列表会是：[50,25,25,10,15,20,5]。使用以下等式可以轻松实现节点遍历：" u, z( u& u$ `3 r; y- ?
3 _9 a+ n  j* A
    节点i的第C个子节点：K*i+c。原理：首先必须跳过每个i之前的节点的和它们的子节点，所以是K*i；然后加上c来得到你想要的子节点。
% _: i1 V! z. G  S- h7 s* i/ O* ?' A
    节点i的根节点：（i-1）/K。原理：跳过多少个拥有K个子节点的节点才能到达i。, H+ g' ?: f, }* x

4 \0 p" J% f1 a" m7 n- i    检查节点i是否是第一个/最左边的节点：（i-1）％K===0。基本原理类似于找到根节点的，当余数为0时就是第一个/最左边的节点。1 C( G: a; z0 V4 @$ k
# N! T1 }( P* Z" H" b
    Kleros的实例% A$ n8 s% Y# S5 _$ d* w! o
0 c3 Y1 w+ I  ^: r1 _" u
    Kleros智能合约库的数据结构文件夹中，包括了k-ary树状数组的开源实现（每个节点的子节点数目可以自定）：https://github.com/kleros/kleros ... cts/data-structures/ h) G! _( ~! o) g( _' i, ]
; h& {) l. l( e( r) q& z
    里面包括了一个继承该功能的分类树状数组智能合约，可用于所有需要分类的智能合约。