利用法定人数加速查询

### 利用法定人数加速查询 #### 1. 算法背景与问题提出 在分布式系统中，输入计数和法定人数形成是重要的问题。传统的输入计数方法存在负载不均衡的问题，每个深度为 i 的节点在最坏情况下会发送和接收 $n/2^i$ 条消息。为了解决这个问题，采用了随机化方法，确保数据结构的每个叶子节点以高概率至少接收 7 log n 条消息。同时，在法定人数形成方面，之前有 King 等人在同步模型下提出了有效的算法，而新的 Create - Quorum 算法在此基础上解决了异步模型下的法定人数形成问题。 #### 2. 算法整体框架 算法主要基于一个电路图 G，它由计算函数 f 的电路 C 构建而来。电路图 G 是一个包含 m + n 个节点的有向无环图，其中 n 个是输入节点，每个对应一个参与者；m 个是门节点，每个对应一个门。对于图 G 中的节点，定义了以下变量： - $Q_v$：与节点 v 关联的法定人数。 - $y_v$：对应于节点 v 的门的输出。 - $r_v$：随机掩码。 - $\hat{y}_v$：与节点 v 关联的掩码输出，即 $\hat{y}_v = y_v + r_v$。 主算法 Algorithm 1 由四个部分组成： 1. 所有参与者运行 Create - Quorum 算法，以达成对 n 个良好法定人数的共识。 2. 所有参与者运行 Input - Commitment 算法，法定人数形成计数树，每个参与者将其输入值提交到计数树叶子节点的法定人数中，法定人数中的参与者决定这些值是否参与计算。 3. 所有参与者运行 Circuit - Eval 算法，对电路进行评估。 4. 通过以完全二叉树形式排列的法定人数将电路评估的输出发送回所有参与者。 ```plaintext Algorithm 1. Main Algorithm 1. All players run Create - Quorum, 2. All players run Input - Commitment, 3. All players run Circuit - Eval, 4. Propagate the output by quorums arranged in a complete binary tree. ``` #### 3. Input - Commitment 算法 该算法基于 τ - Counter 算法，用于输入承诺。τ - Counter 是一个蒙特卡罗算法，用于对阈值 τ（τ ≥ n/2）进行计数。 ##### 3.1 τ - Counter 算法流程 τ - Counter 算法分为上阶段和下阶段： - **上阶段**： - **数据结构构建**：根节点（玩家 1）有 D = ⌈log(τ / 14 log n)⌉ 个孩子，每个孩子是一个完全二叉子树（收集子树）的根，不同的收集子树深度不同。玩家按顺序分配到节点上。 - **输入计数**：当玩家输入为 1 时，向第一个收集子树中的一个随机收集节点发送 ⟨Flag⟩ 消息。收集节点收到 7 log n 条 ⟨Flag⟩ 消息后，向其父节点发送 ⟨Count⟩ 消息。后续收到的 ⟨Flag⟩ 消息，最多 14 log n 条，会转发到下一个收集子树的随机收集节点。添加节点在收到所有子节点的 ⟨Count⟩ 消息后，向其父节点发送 ⟨Count⟩ 消息。根节点根据收到的 ⟨Count⟩ 和 ⟨Flag⟩ 消息更新计数，当计数达到 τ 时进入下阶段。 - **下阶段**：根节点向玩家 2 和 3 发送 ⟨Done⟩ 消息，玩家 j（j > 1）收到 ⟨Done⟩ 消息后，将其转发给玩家 2j 和 2j + 1（如果存在）。 ```plaintext Algorithm 2. τ - Counter n is the number of players, τ is the threshold. D = ⌈log(τ / 14 log n)⌉ 1. Setup (no messages sent here): (a) Build the data structure: – Player 1 is the root. – For 1 ≤ j ≤ D, player j + 1 is a child of the root and the root of the jth collection subtree, which has depth D + 1 - j. – The remainder of the nodes in the collection subtrees are assigned to players left to right and top to bottom, starting with player D + 2. (b) Let sum = 0 for the root. 2. Up stage (a) Individual Players: upon input change to 1 choose a uniformly random collection node v from collection subtree 1 and send a ⟨Flag⟩ to v. (b) Collection nodes in collection subtree j: – Upon receiving 7 log n ⟨Flag⟩s from collection subtree j - 1, if j > 1, or from individual players if j = 1, send parent a ⟨Count⟩ message. – Upon subsequently receiving a ⟨Flag⟩, send it to a uniformly random collection node in collection subtree j + 1, if j < D. If j = D then send these directly to the root. Do this for up to 14 log n flags. Then ignore all subsequent ⟨Flag⟩ messages. (c) Adding nodes: Upon receiving ⟨Count⟩ messages from both children, send parent a ⟨Count⟩ message. (d) Root: While sum < ```