比特币矿池运营背后的数学问题

Reading time ~1 minute

最新一朋友在做比特币矿池方向的创业,受邀请帮忙研究下运营矿池的破产概率问题,以尽可能地规避风险。下面会将相应的一些概念与问题一一道来。

1.泊松分布与挖矿问题

泊松分布

  • 泊松分布适合于描述单位时间内随机事件发生的次数。
  • 泊松分布的参数λ是单位时间(或单位面积)内随机事件的平均发生率。
  • 泊松分布的期望和方差均为λt.

1.1 问题

比特币挖矿的数目服从泊松分布。

这是为什么?且细细看来。

  • 1.btc挖矿机的一次计算是否产生一个合法区块可以认为是一个随机事件,任何所有的计算hash彼此相互独立。

  • 2.每次hash计算有对应的计算难度,标为D,决定着发现一个合法块的难度。

  • 3.每次hash计算(32位hash计算,共有1/2^32个hash值)都会有的概率产生一个合法区块。

  • 4.矿工的算力(hashrate:每秒计算hash的次数):h

ok,这个问题可以化简为:

t时间内,该算力的矿工可以挖到多少btc区块?它服从什么分布?

1.2 解释

ok,很明显,速率问题,泊松分布.

速率λ(即:每秒能挖到多少个区块)为:

  • 单人在t时间内挖到的区块数目期望:
  • 单人在t时间内挖到的区块数目方差:

另外,还有一个条件:即一个合法区块对应着B个btc。换算成btc的话,这一个常数项的线性变换,即是一个POI(BX)的问题.

根据期望和方差的性质:

  • C为常数,X为随机变量
  • 期望性质:
  • 方差性质:

从而,我们得到:

单人在t时间内对应回报的期望为:

单人在t时间内对应回报的方差为:

单人在t时间内对应回报的标准差为:

单人在t时间内对应回报的标准差/期望(标准差是期望的多少倍)为:

1.3 进一步

矿池挖矿模式与单人solo挖矿模式略有不同:

  • 1.它集合了矿池内所有矿工的算力:其hashrate为:H

矿池将在周期t内获得的区块数同样服从泊松分布(为做区分,此处为随机变量Y)。修改一下算力,得到相应的期望/方差:

矿池将在周期t内获得的区块数期望:

矿池将在周期t内获得的区块数方差:

将区块数换算成btc,对应的期望/方差:

矿池在周期t内获得的btc期望:

矿池在周期t内获得的btc方差:

那么在矿池中,单个矿工的收益又是肿么样的一个期望/方差呢?

这里又有另外一项变换:单个矿工的hashrate为:h=qH(其中:q是该矿工对该矿池中总算力的贡献,0<q<1)

根据期望/方差性质,再做一次换算:

在矿池中,个人在周期t内获得的btc期望: ,该值与solo模式一样

在矿池中,个人在周期t内获得的btc方差:,是solo模式的q倍。(0<q<1,因而方差变小,风险也变小了)

2.矿池如何实现收支平衡?

2.1 一般的矿池

矿池通常由一个矿池运营者(pool operator)来维护,它会在相应的服务上花费一定的费用。这通常是区块回报的一个固定百分比:f。因此,对于每个发现的区块,operator都将收到一笔fB的费用,余下的(1-f)B将分配给矿工。

再做一次变换,利用期望/方差的性质:

矿池中,单个矿工获得的的实际btc收入的期望为:,与solo模式略有下降(但其实个人挖一样需要支付电费等问题存在)

矿池中,单个矿工获得的的实际btc收入的方差为:,是solo模式的(1-f)^2q倍. 方差更小。

2.2 变态的矿池

PPS矿池就是这样。

只要挖,不管有没挖到,在周期t时间里,矿工都会有收入。

在矿池中,单个矿工的收入的方差为0。operator承担所有的方差,风险更大,因而需要对operator再做一定的补偿。如果operator不正确平衡矿池的费用以及他的财产准备金,矿池有很大可能会破产。

这里有两个问题:

  • 补偿方式有变化?
  • 在有限资源的情况下,准备金至少需要多少,才能让破产机率更低?

先回到原先讲的:

  • 1.矿池中每次hash计算成为一个share的概率:
  • 2.每个share成为合法区块都有一个概率:
  • 3.矿工在每次提交一个share时将平均接收到的回报:pB
  • 4.对于operator则收到的费用:

2.2.1 推导阶段一

如何分配它?

这里,每次提交share可以当成一个step。在这个周期t内,计算出来的share本身有两个状态:合法(可得到btc)、非法(无效计算,得不到btc)。合法的概率为p,非法的概率为:1-p。

如果合法,则获得B个btc。然后拿出(1-f)pB进行分配给矿工,剩余的归operator自己。如果非法,那就没有收入了,但仍要拿出(1-f)pB进行分配给矿工。这是一个典型的连续时间随机过程,可以用马尔可夫链来表示。一个周期间,operator所得到的收入(包括损失):

它的期望为:

同理使用方差计算公式可得,真实的方差为: ,而btc矿池paper将它近似认为:,这里有些疑问(只有当p的概率较大时,才有可能近似)。

根据中心极限定理可知(这一步有待进一步求证),长期行为服从的正态分布。而这面的这个随机过程正好服从该分布(期望/方差一致),因而可以近似等价为:

我们再对这个初始条件按因子做一下缩放:

这样缩放的好处,对后面推导有利。每次输赢为常量(f恒定, p恒定)。

2.2.2 推导阶段二

剩下的问题,其实就等价于随机过程中马尔可夫链的经典问题:《赌徒输光问题》。

表示,从状态n开始要达到0的概率(表示矿池破产)。我们在第一步得到的条件,表示:

这个随机过程可以表示为:

可以用常系数齐次线性方程求解该多项式特征方程:

该方程的解为:

整个特征方程,它的通解形式为:

代入初始值(边界条件):

即:A=0, B=1,得到

如果operator以一个R的话准备金启动,矿池的破产概率为:

相反地,为了维持一个破产概率最大为,矿池应至少保有准备金:

参考:

1.Analysis of Bitcoin Pooled Mining Reward Systems. Meni Rosenfeld

youtube基于深度学习的推荐

youtube的基于深度学习的推荐系统,主要分成两大部分:# 一、候选生成将推荐当成是一个多分类问题,预测问题为:视频库V,有上百万的视频,某用户U,在上下文C上,在时间t时的观看行为\$w_t\$,刚好是某个视频i.$$P(w_t =i|U,C)=\frac{e^{v_{...… Continue reading

fastText介绍

Published on August 20, 2016

paragraph2vec介绍

Published on March 05, 2016