区块链分叉中补丁传播时间的估计

### 区块链分叉中补丁传播时间的估计 在区块链的世界里，比特币作为先驱，其代码被大量复刻和修改，形成了众多的山寨币（altcoins）。这些山寨币通常会通过变基（rebase）操作来移植比特币核心的软件补丁，但变基操作会改变提交历史的时间戳，给补丁传播时间的分析带来挑战。本文将介绍一种名为GitWatch的工具，它可以有效解决这一问题，并通过实际案例分析不同山寨币的补丁传播情况。 #### 1. Git操作基础 在深入了解补丁传播时间的分析之前，我们需要先了解一些基本的Git操作： - **提交（Commit）**：一个提交被定义为元数据（M）和数据（D）的对，即C = (M, D)。元数据包含提交哈希（h，即提交ID）、父提交（p）、作者（a）、提交者（c）以及作者时间戳（ta）和提交者时间戳（tc）。提交ID是对数据和其他元数据的加密哈希，即h = H(p, a, c, ta, tc, D)。Git允许为提交操作关联标签，标签包含目标提交的引用、时间戳和可读标签。 - **推送（Push）**：用户u创建的一批提交形成一个序列 (C1, ..., Cm)，作者和提交者最初与推送提交的用户一致，作者和提交者时间戳也相同。 - **分叉（Fork）**：现有仓库R的分叉仓库Rχ与R共享共同历史，R称为主分支。R和Rχ的最新共同提交称为基础提交。假设CH和CHχ分别是R和Rχ的提交历史，则CH = (C0, ..., Cm, ..., Cm+s)，CHχ = (C0, ..., Cm, Cχ1, ..., Cχr)，其中Cm是基础提交，所有Cχi都与主分支不同。 - **变基（Rebase）**：变基操作允许将主分支R的更改集成到分叉Rχ中，通过从R的新基础提交重新应用所有推送到Rχ的提交。变基会修改分叉的提交历史，更新提交的父提交和提交者时间戳（作者时间戳不变）。具体来说，变基后提交的父提交会被更新，并且提交者时间戳会被设置为当前时间。 变基操作虽然可以帮助山寨币获取比特币的最新更新，但它会导致时间戳不可靠。每次变基都会重置提交历史中的提交者时间戳，覆盖之前的时间戳信息。不过，在GitHub中，变基前后的提交最初都可以通过各自的提交ID访问，这为我们提供了一种检索变基时间戳的策略。 #### 2. 提取变基时间 为了提取有意义的补丁传播时间信息，我们依赖于GitHub的事件API和GH存档（GH archive）。GH存档是一个开放服务，提供自2011年以来所有GitHub事件的历史记录。我们的工具GitWatch利用这些资源来测量补丁传播时间。 GitWatch的工作流程如下： 1. **重建提交树**：GitWatch首先重建GitHub项目χ中曾经存在的所有提交的树，构建一个图Gχ = (V, E)，其中V包含所有提交（包括悬空提交），E表示父子关系。为了实现这一点，它会爬取GH存档中与χ相关的所有事件，并从GitHub的API中检索所有提交。 2. **定位目标补丁**：使用Gχ，GitWatch定位应用目标补丁到χ的提交（如果存在），并使用三种不同的启发式方法来估计相应的时间戳： - **补丁提交查找器（PCF）**：给定一个比特币的补丁提交Ci，PCF遍历Gχ以收集所有在其历史中包含Ci的非比特币提交Cj。然后，它在这些提交中找到最早的提交C∗，其提交者时间戳最早。补丁传播时间估计为ΔPCF ← C∗.tc - Ci.ta。 - **补丁事件查找器（PEF）**：除了Gχ，PEF还依赖于检查GitHub事件。事件与一个或多个提交相关联，一个推送事件e包含作者推送的提交列表。PEF查找最早的非比特币提交C∗，该提交在其历史中包含补丁Ci，并根据事件时间戳而不是提交时间戳来测量时间流逝。补丁传播时间估计为ΔPEF ← φ(C∗).t - Ci.ta，其中φ(C∗)是与C∗关联的事件。 - **补丁标签查找器（PTF）**：PTF依赖于为相关标签记录的时间戳。它估计补丁传播时间为比特币补丁Ci创建与第一个与χ中包含Ci的提交相关联的非比特币标签创建