忽略额外零值：方差最优的矿池

### 忽略额外零值：方差最优的矿池 #### 1. 非无记忆的自然奖励共享方案示例 存在一种非无记忆的自然奖励共享方案（RSS），即比例 RSS。在区块授权时，它会根据每个矿工自最近一次成功区块授权以来发送的签名消息数量，按比例将相应奖励分配给矿工。这里，矿工因一条签名消息获得的奖励取决于过去，具体取决于矿池自最近一次成功区块授权以来收到的签名消息数量。 #### 2. 消息独立性与对称化 - **消息独立性**：若 RSS ϕ 满足 ϕ((s1, m1), ..., (st, mt)) 与 m1, m2, ..., mt 无关，即 RSS 不考虑消息 m1, ..., mt 的内容，则称该 RSS 是消息独立的。消息独立性对应于引言中的“单类份额”概念，RSS 仅考虑消息的可接受性（即属于集合 A），而不考虑消息的具体内容。PPS、PPLNS 和比例 RSS 都是消息独立的。若根据可接受消息中的前导零数量等条件来确定奖励，则会得到非消息独立的 RSS。 - **对称化**：对于一个（不一定是消息独立的）RSS ϕ，其对称化 ϕsym 定义为： - ϕsym((s1, m1), ..., (st, mt)) = Eu1,...,ut∼A[ϕ(si, mi)]，其中 ui 是来自集合 A 的独立同分布的均匀随机消息。 - 对于无记忆的 RSS ϕ，有 ϕsym(s, m) = Eu∼A[ϕ(s, m)]。 - 命题 1：对于每个 RSS ϕ，其对称化 ϕsym 是消息独立的。 #### 3. 作为哈希率估计器的奖励共享方案 为了比较不同 RSS 的统计特性（如最小化方差），可将 RSS 视为哈希率分布的统计估计器。估计器是一个将每个序列 (s1, m1), ..., (st, mt) 与矿工 [k] 上的概率分布相关联的函数。 - 给定 RSS ϕ，相应的估计器 fϕ 将每个签名消息序列 (s1, m1), ..., (st, mt) 与 k 维向量 p 相关联，其中第 j 个分量 pj 是分配给矿工 j 的奖励比例： - pj = 1 / Z · ∑i∈[t] : si=j ϕ((s1, m1), ..., (si, mi))，其中 Z = ∑t i=1 ϕ((s1, m1), ..., (si, mi)) 是归一化因子。对于无记忆规则 ϕ，可在上述公式中用 ϕ(si, mi) 代替 ϕ((s1, m1), ..., (si, mi))。若 RSS ϕ 是随机化的，则相应的估计器 fϕ 也是随机化的（即使对于固定样本）。 - 签名消息序列 (s1, m1), ..., (st, mt) 在哈希率分布 h 下的似然性，是 t 个独立同分布的从由 h 诱导的消息分布 M(h) 中抽取的样本为 (s1, m1), ..., (st, mt) 的概率。最大似然估计器（MLE）将每个序列 (s1, m1), ..., (st, mt) 映射到使该序列似然性最大的哈希率分布。虽然没有先验要求 MLE 由 RSS 诱导，但后面会证明 PPS RSS 会诱导一个 MLE。 - **无偏性**：为了得到有意义的最小化方差结果，需要某种无偏性假设。若对于每个正整数 t 和哈希率分布 h，有 E[f((s1, m1), ..., (st, mt))] = h，则称估计器 f 是无偏的，其中期望是对 t 个独立同分布的来自 M(h) 的样本以及估计器内部的任何随机化取的。例如，PPS、PPLNS 和比例 RSS 都诱导无偏估计器。 - 命题 2：对于每个无偏 RSS ϕ，其对称化 ϕsym 也是无偏的。 - 若估计器在第 s 个坐标上满足上述无偏性等式，则称该估计器对矿工 s 是无偏的。一个估计器是无偏的当且仅当它对每个矿工都是无偏的。 - **t - 样本方差**：对于给定的估计器 f、正整数 t 和哈希率分布 h，可定义其矿工 s 的 t - 样本方差为 E[(f((s1, m1), ..., (st, mt)))s - hs)2]，其中期望同样是对 t 个独立同分布的来自 M(h) 的样本以及估计器内部的任何随机化取的。估计器 f 对于哈希率分布 h 的 t - 样本方差是所有这些方差（针对不同矿工 s）组成的向量。 #### 4. t 为随机变量的情况 t - 样本方差指的是固定数量 t 的样本，对应于固定数量的矿工份额。若固定一段时间，则 t 本身是一个随机变量（在该时间窗口内找到的份额数量，服从泊松分布）。所有的 t - 样本方差最优性结果（如定理 4 和定理 5）对所有正整数 t 同时成立。根据总方差定律，这些方差最优性结果可推广到 t 是随机变量的情况（如固定时间窗口的情况）。 #### 5. 热身：最大化似然性 从统计预测的角度来看，PPS 对应的估计器实际上是哈希率分布 h 的最大似然估计器（给定 t 个独立同分布的来自消息分布 M(h) 的样本）。 - **定理 1（PPS 是最大似然估计器）**：PPS 奖励共享方案诱导的估计器 fPPS 是一个最大似然估计器。 - 为证明该定理，先给出如下结果：设 X1, ..., Xn 是具有离散支撑 [k] 的独立同分布随机变量。对于 s ∈ [k]，令 ns = |{Xi = s}|。若 p = (p1, ..., pk) 满足 p = argmaxq∈Q ∏n s=1 qns s，其中 Q = {q ∈ Rk : ∑k s=0 qs = 1, ∀s qs ≥ 0} 表示单纯形，则称 p 是最大似然估计。 - **定理 2**：最大似然估计由经验分布给出，即对于所有 s ∈ [k]，ps = ns / n。 - **定理 1 的证明**： - 首先，si 的值是独立同分布的。对于每个 i，si 由哈希分布选择，且由于泊松过程是无记忆的，对于任何 i ≠ j，si 与 sj 相互独立。 - 其次，PPS 诱导的估计器是经验分布。当关注 PPS（每份固定奖励为 c）时，公式（1）可简化为 ps = 1 / (c · t) · ∑i∈[t] : si=s c = |{i : si = s}| / t。 - 由定理 2 可得定理 1。 虽然定理 1 为从众多 RSS 中挑选出 PPS 提供了一种新颖的方式，但矿池的主要目的是最小化方差，而非单纯的预测。因此，接下来将探讨关于方差最优性的主要结果，其中 PPS RSS 将继续发挥核心作用。 下面用 mermaid 绘制一个简单的流程图来展示上述部分内容的逻辑关系： ```mermaid graph LR A[非无记忆的 ```