Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

区块链数据分类的高效化

家养宠物繁殖
171 0 0
如果方法不得当,在诸如游戏之类的抽签中计算动态投注额会消耗很高的算力。下面,让我们看一个比较合适的方案......0 M# H0 F6 z9 C* ]3 a

( ?# k3 I, H% p1 C3 @& Y1 p) p    在去中心化的应用程序中,最普遍的抽签方式就是:使用与用户所持有的令牌数量成比例的一个随机数。如果只允许增加用户持有量,这就非常简单。但是,如果你想在所有抽签轮次中自由更改用户持有量时,抽签的随机计算就会变得非常复杂......$ G* [! v( R1 A9 \6 k% D

  K# l% j2 a3 q5 {4 R% K: m    基本的方式
; g. Z5 S( E( H
/ t6 h5 ?' X7 J# x. {    构建这样的系统最简单方法是创建一个虚拟列表,其中包含每个参与抽签地址的区段。使用一个存储变量来跟踪列表大小,并且每当有人改变持有量时:: a) @5 e$ i) S7 q8 F% [
& A) H3 `/ D7 o
    tokenHolder.segmentStart=segmentSize;. z3 ?$ V* G* u6 ]
7 F7 g% H; t* o$ O) |4 }" c+ O
    segmentSize+=_stake;
, V" r6 D4 G. ?
8 G( J! D0 j# W3 |0 y3 p" b, p7 T    tokenHolder.segmentEnd=segmentSize;( b; K( o6 z1 Z7 ^
% m. X6 e- X5 _5 O. ^
    这种方法存在两大问题(尽管根据使用情况,可能不会很严重)。( H7 ^; E; D* c+ {# U3 `
' d/ N& n8 L; Y& w5 J! a/ \. B
    首先,如果持有人希望更改或删除他们的投入额,那么拼接这个列表的计算成本会很高。
8 D, _/ D$ ?  B! w: Y% {/ K! t
( c2 R8 }$ ?) M0 N8 l* E: z* k    其次,获得被抽中者需要迭代每位持有者,如下所示:  f$ J; l' \  F; D/ s

) r3 U2 T4 y( c+ Y0 Z5 l    //O(n)wherenisthenumberoftokenholderswithstake% w, Z* a5 p7 t" ^
3 z4 p' A, P+ E1 L
    for(uinti=0;i+ m& L) b1 d& e" e2 c7 y8 z
  n. ?  [# `' Y. h8 @
    if(currentDrawnNumber.segmentEnd)
3 j& o* w3 v4 ^0 ]6 D
: S0 S- x0 u4 @0 e& X, p8 B    returntokenHolders.address
/ N9 X* a2 S# K2 q
( H$ ?! h' w( F6 X$ v+ M# O    在任何规模可观的系统中,每次抽奖都会需要很多算力。这种算法还制造了O(d*a)个影子漏洞,其中d是抽签次数,a是令牌持有者的数量,因为攻击者可以用最低额创建大量账户。这意味着唯一合理的方法是让令牌持有者检查自己是否被抽出。这严重限制了智能合约实施自动化的逻辑,无法实现自动抽取和通知被抽取者。6 N/ V; R6 l" `  u

* \2 {5 D% q5 y' J    树状数组解决方案1 g" ~) J" O% y& u' |

0 I. }# W. r' r" Q0 J  C. b    在寻求更好的方法过程中,我们的首席技术官ClémentLesaege从一种复杂的数据结构形式里找到了答案:K-Ary树状数组。K-Ary树状数组的每个非数据点都有K个子节点并且保存所有节点的值的总和。这意味着我们关心的实际值都是数据点,经证明以这种方式组织数据对性能有非常大的提高。比如一个二进制的树状数组(K=2),其中Alice有10个令牌投注,Bob有15个令牌投注,Carl有20个令牌投注,Dave有5个令牌投注,看起来像:
1 Y& F5 A& P$ @: P: O; L
* Y5 k9 _9 H6 C6 @! J& W1 m, C    二进制树状数组示例
. O  Z" d+ h$ E& e# X8 b2 f: B
" Z2 F3 ?. m( z: g3 f/ d    在以上示例中,假设我们抽取到数字13,寻取方式如下:首先13落在[0-24,25-49]的哪个区?0-24,所以往下进入左侧区域。之后判断13落入[0-9,10-24]的哪个区域?由此抽取到鲍勃。; F8 n# R5 y; U/ \3 T  B+ K
" l  d8 |* _: |. m* \' z  ~7 r
    现在,假设我们抽取到2。同理,从根开始,但是这次27落到25-49,所以我们进入右侧区域。同样对[0-20,21-24]重复相同的过程,但是使用2而不是27,因为您通过跳过第一级中的左节点“花费”了25,于是抽取到了卡尔。
8 \% w) o4 W1 n( c. q, s9 M4 N, k' |4 k' [9 R; s9 e* O& D
    所以这个数据结构让我们的抽取复杂度变为O(K*log(n)/log(K)),其中K是每个节点的子节点数。log(n)/log(K)是遍历K次数据节点数的数值,换句话说,就是数据结构的层级数。将它乘以K是因为在最坏的情况下,你必须查看你遍历的每个节点的每个子节点,以确定是否遍历下一个节点。
- w0 b+ i( M7 V% m9 V1 e* W; L; ^- o+ y
    设置,删除和追加的复杂度都是O(log(n)/log(K)),因为是从给定的数据节点开始,逐级向上操作。注意保留一定量的空闲数据节点,是保证在删除操作中保持数据结构完整的捷径。这些操作非常容易实现:; T! l7 l/ v) U( w5 M

* E" z0 E( Y1 ~    设置:设置新值并更新根值。. q; X0 `3 l. r  {# }  |
! c$ R# G3 T+ o/ n/ g$ |4 J
    删除:将值设置为0,将数据节点推送到一个空闲节点,然后更新根节点。请注意,这个操作实际上并没有从数据结构中删除节点,因此n永远不会减少。! q1 S( y3 ^0 W6 l9 V  e4 b
' L7 k9 p& q) C- _5 N& D
    追加:从前面提到的空闲堆栈中弹出一个节点,否则追加一个新节点,并赋值。
- @# _8 a$ a( M  P/ S  `% |, j1 P; {. I8 a( T$ R% ]
    执行过程中的算力节省
  B4 t. v& M7 ~" y8 o1 X* K+ }' U9 W! Y
    因为结构中的数据并未被删除(它们只被设置为0并被推送到堆栈),所以在执行过程中可以节省一大部分的算力。我们只需要一个空闲节点堆栈列表和一个数据结构中实际值的列表。如上例所示,列表会是:[50,25,25,10,15,20,5]。使用以下等式可以轻松实现节点遍历:
( }  p  n; m; o+ `/ {0 N/ t
; ?2 V1 s$ [% T: B    节点i的第C个子节点:K*i+c。原理:首先必须跳过每个i之前的节点的和它们的子节点,所以是K*i;然后加上c来得到你想要的子节点。0 M+ k/ a. X- O( x8 R. j& v

" K  N% l! t' Y" c( m( ~    节点i的根节点:(i-1)/K。原理:跳过多少个拥有K个子节点的节点才能到达i。
# V" a6 _$ V& U+ E; o0 ^* I9 J# y$ ]5 N0 V: h. Y
    检查节点i是否是第一个/最左边的节点:(i-1)%K===0。基本原理类似于找到根节点的,当余数为0时就是第一个/最左边的节点。& b- \5 l/ d2 S1 ~$ }, m) T: l* @

5 z# a5 `; W" ^" M. N    Kleros的实例# t, l6 s3 f' V! K. x$ H9 Y% S$ A

2 h% D% {  A) ]8 h: L    Kleros智能合约库的数据结构文件夹中,包括了k-ary树状数组的开源实现(每个节点的子节点数目可以自定):https://github.com/kleros/kleros ... cts/data-structures
! @- a" Q& I7 @/ l( z/ c" R4 `/ t7 w9 i
    里面包括了一个继承该功能的分类树状数组智能合约,可用于所有需要分类的智能合约。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

家养宠物繁殖 小学生
  • 粉丝

    0

  • 关注

    0

  • 主题

    1