Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

区块链数据分类的高效化

家养宠物繁殖
102 0 0
如果方法不得当,在诸如游戏之类的抽签中计算动态投注额会消耗很高的算力。下面,让我们看一个比较合适的方案......$ ?3 m# D. c. w8 j+ ~5 z2 g
3 D+ B$ T- W. G" G" f. e9 j
    在去中心化的应用程序中,最普遍的抽签方式就是:使用与用户所持有的令牌数量成比例的一个随机数。如果只允许增加用户持有量,这就非常简单。但是,如果你想在所有抽签轮次中自由更改用户持有量时,抽签的随机计算就会变得非常复杂......
6 ]0 A4 j- ?, g$ @" Z* W- n
3 _: O! H( U2 a' G) N6 u6 x! e- B# r    基本的方式
) X* u( g& m0 K' {
- c7 E. x0 v( M, A8 b, g    构建这样的系统最简单方法是创建一个虚拟列表,其中包含每个参与抽签地址的区段。使用一个存储变量来跟踪列表大小,并且每当有人改变持有量时:! |  K7 {5 ^6 W* b
7 z: o5 v, G6 A; ^! n! r
    tokenHolder.segmentStart=segmentSize;
# y! c' X. A! v6 v3 J5 U/ g+ i- y) m4 Q" i3 `# r
    segmentSize+=_stake;" x5 S' F6 q" |: F2 G* |
- b- W6 ]% q0 m& |
    tokenHolder.segmentEnd=segmentSize;! H' N5 F9 ~6 u% P$ Z

+ V9 t0 g1 F9 a% X8 u    这种方法存在两大问题(尽管根据使用情况,可能不会很严重)。1 n; s7 q$ Y& X% s" X$ Y

" W' ]2 R3 @8 n    首先,如果持有人希望更改或删除他们的投入额,那么拼接这个列表的计算成本会很高。
* |6 T/ z+ I! k: v  k" h
1 `6 P9 d- I* O6 s6 W    其次,获得被抽中者需要迭代每位持有者,如下所示:
# i5 H* D9 H* b+ y  V' }4 q1 \4 x1 N9 }9 K, M0 K: K
    //O(n)wherenisthenumberoftokenholderswithstake  d3 Y' P$ Z& B& s; C5 g# `
$ ^. F4 E. J, I" e: c# Q
    for(uinti=0;i- X! L# M$ _+ U$ a

" O6 w5 ?1 Q) C' t- L+ [    if(currentDrawnNumber.segmentEnd)5 E8 `- r/ C# h* j& O+ I' j0 U" g

& n/ ?* S9 ]* z) k* q6 C    returntokenHolders.address9 s! [  a8 W2 j4 n

( e! k2 w  ^' P2 f4 M( q6 u    在任何规模可观的系统中,每次抽奖都会需要很多算力。这种算法还制造了O(d*a)个影子漏洞,其中d是抽签次数,a是令牌持有者的数量,因为攻击者可以用最低额创建大量账户。这意味着唯一合理的方法是让令牌持有者检查自己是否被抽出。这严重限制了智能合约实施自动化的逻辑,无法实现自动抽取和通知被抽取者。
1 s9 v( T8 P8 M" A1 e5 u. Z  T0 v) L, }6 y" U
    树状数组解决方案
* N! B/ g# G# C( Y9 g& B' C5 @
* P- l; {3 p- V8 b% ~% N    在寻求更好的方法过程中,我们的首席技术官ClémentLesaege从一种复杂的数据结构形式里找到了答案:K-Ary树状数组。K-Ary树状数组的每个非数据点都有K个子节点并且保存所有节点的值的总和。这意味着我们关心的实际值都是数据点,经证明以这种方式组织数据对性能有非常大的提高。比如一个二进制的树状数组(K=2),其中Alice有10个令牌投注,Bob有15个令牌投注,Carl有20个令牌投注,Dave有5个令牌投注,看起来像:% J8 i& l! T) ~4 g* r7 @% g
" h1 L% _' F& t# H9 n1 O6 F
    二进制树状数组示例
: t  q- @- i' B, u6 b: g/ G9 d5 F7 C1 V
    在以上示例中,假设我们抽取到数字13,寻取方式如下:首先13落在[0-24,25-49]的哪个区?0-24,所以往下进入左侧区域。之后判断13落入[0-9,10-24]的哪个区域?由此抽取到鲍勃。( K. M& ^. q! s) C3 q) y
, |1 t. y, k# x- [, ~) z% ^) ?- S
    现在,假设我们抽取到2。同理,从根开始,但是这次27落到25-49,所以我们进入右侧区域。同样对[0-20,21-24]重复相同的过程,但是使用2而不是27,因为您通过跳过第一级中的左节点“花费”了25,于是抽取到了卡尔。
  P) }$ u' }9 Z) U8 S4 K
0 b' ]$ R5 w0 q: H9 }    所以这个数据结构让我们的抽取复杂度变为O(K*log(n)/log(K)),其中K是每个节点的子节点数。log(n)/log(K)是遍历K次数据节点数的数值,换句话说,就是数据结构的层级数。将它乘以K是因为在最坏的情况下,你必须查看你遍历的每个节点的每个子节点,以确定是否遍历下一个节点。
4 g* X. b, |' D* A2 s8 i( v! I) a) [! d
    设置,删除和追加的复杂度都是O(log(n)/log(K)),因为是从给定的数据节点开始,逐级向上操作。注意保留一定量的空闲数据节点,是保证在删除操作中保持数据结构完整的捷径。这些操作非常容易实现:$ k- h  P/ ^4 s* l+ v

; F: N$ V, Y+ {, \$ \    设置:设置新值并更新根值。
7 p5 O5 T" l: ~" `+ a" e) _! V6 m  {* Z$ E
    删除:将值设置为0,将数据节点推送到一个空闲节点,然后更新根节点。请注意,这个操作实际上并没有从数据结构中删除节点,因此n永远不会减少。. O6 w9 Z, c5 H

$ L& O) Y. z5 [9 k6 ]3 q- I. p    追加:从前面提到的空闲堆栈中弹出一个节点,否则追加一个新节点,并赋值。% K, F: V9 x& M+ q6 K

: M- D) h& [- v( d( e- u    执行过程中的算力节省6 G  K: N$ x2 S( u; W  I

' @% N7 J! K% c% u3 Z0 O    因为结构中的数据并未被删除(它们只被设置为0并被推送到堆栈),所以在执行过程中可以节省一大部分的算力。我们只需要一个空闲节点堆栈列表和一个数据结构中实际值的列表。如上例所示,列表会是:[50,25,25,10,15,20,5]。使用以下等式可以轻松实现节点遍历:) i, k- Z" x' U7 _, G1 `+ S

7 Z3 |. S# g( K, Q7 c3 |/ x" k    节点i的第C个子节点:K*i+c。原理:首先必须跳过每个i之前的节点的和它们的子节点,所以是K*i;然后加上c来得到你想要的子节点。
' x0 V2 _5 Q: D3 Y  p
  T6 u. k3 @+ Z9 x1 C    节点i的根节点:(i-1)/K。原理:跳过多少个拥有K个子节点的节点才能到达i。
0 E( N" P' G9 m- e4 n3 n; _7 S5 q, x. t
    检查节点i是否是第一个/最左边的节点:(i-1)%K===0。基本原理类似于找到根节点的,当余数为0时就是第一个/最左边的节点。" Z2 C  ^9 a- p# {/ e
" g5 s6 X0 O* G, |
    Kleros的实例
$ T! j& H' @3 \4 r/ M. O, e) J4 e7 w8 [9 k- E! T3 l
    Kleros智能合约库的数据结构文件夹中,包括了k-ary树状数组的开源实现(每个节点的子节点数目可以自定):https://github.com/kleros/kleros ... cts/data-structures
; Y1 P/ p+ A+ }% J2 G( [
1 S8 L  Y7 j7 ^* w  F- r# ]    里面包括了一个继承该功能的分类树状数组智能合约,可用于所有需要分类的智能合约。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

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

    0

  • 关注

    0

  • 主题

    1