以太坊 Gasper 共識機制形式化驗證與數學推導完整指南

概述

Gasper 是以太坊權益證明（Proof of Stake）共識機制的核心協議，名稱來自「Casper」和「Gasper」的結合。它結合了 Casper FFG（Casper Friendly Finality Gadget）的最終確認機制與 LMD-GHOST（Latest Message-Driven Greedy Heaviest Observed Subtree）的分叉選擇規則。本文從形式化驗證的角度，深入分析 Gasper 的安全性證明、活性證明、以及關鍵數學推導，提供完整的數理邏輯推導過程。

截至 2026 年第一季度，以太坊 Beacon Chain 驗證者數量超過 110 萬，質押總量超過 3,400 萬 ETH。理解 Gasper 的形式化特性對於共識協議研究者、安全審計員、以及區塊鏈開發者至關重要。

第一章：Gasper 協議形式化定義

1.1 系統模型與符號定義

在進行形式化分析之前，我們首先定義 Gasper 的系統模型：

基本符號定義：

┌─────────────────────────────────────────────────────────────────────────┐
│ 符號                │ 定義                                            │
├────────────────────┼────────────────────────────────────────────────┤
│ V                  │ 驗證者集合                                      │
│ n = |V|            │ 驗證者總數                                      │
│ f                  │ 惡意驗證者數量                                  │
│ h                  │ 誠實驗證者數量 = n - f                          │
│ t                  │ 閾值參數                                        │
│ slot               │ 時間槽，長度 12 秒                              │
│ epoch              │ 紀元，由 32 個 slot 組成                        │
│ B                  │ 區塊                                            │
│ C                  │ 檢查點（Checkpoint）                           │
│ H                  │ 區塊提議者的隨機種子（RANDAO）                  │
│ Σ                  │ 驗證者簽名聚合器                                │
└────────────────────┴────────────────────────────────────────────────┘

1.2 形式化系統狀態

Gasper 的系統狀態可以表示為一個多元組：

"""
Gasper 協議的狀態表示
形式化定義
"""

@dataclass
class GasperState:
    """
    Gasper 狀態的形式化定義
    
    狀態是一個多元組：
    S = (ξ, λ, ψ, φ, π)
    
    其中：
    - ξ: 當前 epoch
    - λ: 當前 slot
    - ψ: 驗證者狀態映射
    - φ: 分叉選擇歷史
    - π: 最終確認歷史
    """
    
    epoch: int                                    # 當前 epoch 編號
    slot: int                                    # 當前 slot 編號
    validators: Dict[ValidatorID, ValidatorState]  # 驗證者狀態
    fork_choice_history: Dict[BlockHash, Weight]   # 分叉選擇歷史（權重）
    justification_history: Dict[Checkpoint, JustificationStatus]  # 合理性歷史
    finalization_history: List[Checkpoint]        # 最終確認歷史
    
@dataclass
class ValidatorState:
    """
    驗證者狀態
    
    每個驗證者 v ∈ V 的狀態包含：
    - effective_balance: 有效質押餘額
    - status: 當前狀態（活躍/退出/罰沒）
    - latest_justification: 最新合理化 epoch
    - latest_finalization: 最新最終確認 epoch
    """
    validator_id: ValidatorID
    effective_balance: Gwei
    status: ValidatorStatus  # ACTIVE, EXITED, SLASHED, PENALIZED
    latest_justification_epoch: int
    latest_finalization_epoch: int
    is_slashed: bool

@dataclass
class Checkpoint:
    """檢查點（Checkpoint）"""
    epoch: int
    block_root: BlockHash
    
@dataclass
class JustificationStatus:
    """合理性狀態"""
    checkpoint: Checkpoint
    participating_weight: Gwei
    total_weight: Gwei
    justification_ratio: float  # participating_weight / total_weight

1.3 消息定義

Gasper 中的消息主要有兩種類型：

@dataclass
class Attestation:
    """
    認證消息（Attestation）
    
    認證消息是 Gasper 共識的基本單位
    """
    slot: int                      # 認證目標 slot
    beacon_block_root: BlockHash   # 認證的區塊根
    source: Checkpoint              # 來源檢查點
    target: Checkpoint             # 目標檢查點
    aggregator_id: ValidatorID     # 聚合者 ID
    bitfield: Bitlist              # 參與驗證者的位元圖
    signature: BLSSignature        # 聚合簽名

@dataclass
class Block:
    """
    區塊
    """
    slot: int
    proposer_id: ValidatorID
    parent_root: BlockHash
    state_root: BlockHash
    attestations: List[Attestation]
    randao_reveal: bytes
    graffiti: bytes
    signature: BLSSignature

第二章：Casper FFG 數學推導與安全性證明

2.1 最終確認條件的形式化定義

Casper FFG 的最終確認條件可以形式化為：

定義 1：合理性（Justification）

一個檢查點 C 被稱為「合理」的，當且僅當：

    J(C) ≡ |Σ(v_i ∈ V : has_justified(C, v_i))| × effective_balance(v_i) > 2n/3

其中：
- has_justified(C, v_i) 表示驗證者 v_i 對 C 的合理性投票
- n 為驗證者總數

這意味著至少 2/3 的質押權重支持該檢查點。

def check_justification(
    state: GasperState,
    checkpoint: Checkpoint
) -> bool:
    """
    檢查檢查點是否合理
    
    數學條件：
    participating_weight / total_weight > 2/3
    
    實現：
    """
    # 獲取所有對此檢查點投票的驗證者權重
    participating_validators = get_validators_who_justified(state, checkpoint)
    participating_weight = sum(
        v.effective_balance for v in participating_validators
    )
    
    total_weight = get_total_active_weight(state)
    
    # 合理性條件：超過 2/3
    justification_threshold = 2 * total_weight / 3
    
    return participating_weight > justification_threshold

2.2 最終確認條件的數學推導

定義 2：最終確認（Finalization）

一個檢查點 C 被稱為「最終確認」的，當且僅當：

    F(C) ≡ J(C) ∧ J(C.parent) ∧ C.epoch = C.parent.epoch + 1

其中 C.parent 表示 C 的父檢查點。

或者等價地：

    F(C) ≡ J(C) ∧ J(C') ∧ (C.epoch = C'.epoch + 1)
    
其中 C' 是在 C 之前被合理化的檢查點。

這個條件意味著：
1. C 本身是合理的
2. C 的直接父檢查點也是合理的
3. 兩個檢查點在連續的 epoch 中

定理 1：Casper FFG 安全性定理

如果以下條件成立：

    |B| < n/3

其中 B 是惡意驗證者的總質押權重，n 是總質押權重，

則不存在兩個衝突的檢查點同時被最終確認。

證明：

假設存在兩個衝突的檢查點 C1 和 C2 被最終確認。

根據最終確認條件：
- C1 和 C2 必須都被合理化
- C1 和 C2 的合理性需要至少 2n/3 的支持

設 S1 為支持 C1 的驗證者集合
設 S2 為支持 C2 的驗證者集合

根據容斥原理：
|S1 ∪ S2| = |S1| + |S2| - |S1 ∩ S2|

|S1| > 2n/3
|S2| > 2n/3

因此：
|S1 ∪ S2| > 2n/3 + 2n/3 - |S1 ∩ S2|
       = 4n/3 - |S1 ∩ S2|

如果 C1 和 C2 衝突，則 S1 ∩ S2 = ∅（空集）

因此：
|S1 ∪ S2| > 4n/3 > n

但這是不可能的，因為 |S1 ∪ S2| ≤ n（總驗證者數）

矛盾！

因此，衝突的檢查點不能同時被最終確認。
∎

2.3 經濟安全性分析

命題 1：經濟懲罰的下界

如果一個惡意驗證者嘗試破壞最終確認，則其質押餘額將被削減至少：

    penalty ≥ effective_balance × (epoch_diff / EPOCHS_PER_SLASHINGS_VECTOR)

其中 epoch_diff 是錯誤投票的 epoch 差距。

數學推導：

設：
- b = 驗證者的有效質押餘額
- e_diff = 兩個衝突投票的 epoch 差

削權懲罰：
P = b × min(e_diff / EPOCHS_PER_SLASHINGS_VECTOR, 1)

當 e_diff ≥ EPOCHS_PER_SLASHINGS_VECTOR 時：
P = b （全部罰沒）

這提供了一個強大的經濟激勵，使驗證者遵守協議。

def compute_slashing_penalty(
    validator: ValidatorState,
    offence_epoch_diff: int
) -> Gwei:
    """
    計算削權懲罰
    
    數學公式：
    penalty = min(
        effective_balance × e_diff / EPOCHS_PER_SLASHINGS_VECTOR,
        effective_balance
    )
    
    參數：
    - validator: 驗證者狀態
    - offence_epoch_diff: 兩個衝突投票的 epoch 差
    
    返回：
    - 懲罰金額
    """
    EPOCHS_PER_SLASHINGS_VECTOR = 8191  # 質押歷史向量長度
    
    # 計算比例
    ratio = offence_epoch_diff / EPOCHS_PER_SLASHINGS_VECTOR
    
    # 取 min（防止超過餘額）
    penalty_ratio = min(ratio, 1.0)
    
    # 計算懲罰金額
    penalty = int(validator.effective_balance * penalty_ratio)
    
    # 確保不超過有效餘額
    return min(penalty, validator.effective_balance)


def verify_safety_property(
    state: GasperState,
    checkpoint1: Checkpoint,
    checkpoint2: Checkpoint
) -> bool:
    """
    驗證安全性屬性
    
    檢查兩個檢查點是否衝突且同時最終確認
    
    安全性定理：
    如果 |B| < n/3，則不可能存在兩個衝突的最終確認檢查點。
    """
    # 計算惡意驗證者權重
    malicious_weight = sum(
        v.effective_balance 
        for v in state.validators.values() 
        if v.is_slashed or is_byzantine(v)
    )
    
    total_weight = get_total_active_weight(state)
    
    # 安全性條件檢查
    safety_condition = malicious_weight < total_weight / 3
    
    # 如果安全性條件滿足，檢查是否存在衝突的最終確認
    if safety_condition:
        # 兩個檢查點衝突意味著它們不在同一個祖先鏈上
        same_ancestor_chain = have_common_ancestor(checkpoint1, checkpoint2)
        
        # 兩個衝突的檢查點不能同時最終確認
        return not (not same_ancestor_chain and 
                   is_finalized(checkpoint1) and 
                   is_finalized(checkpoint2))
    
    return False

第三章：LMD-GHOST 分叉選擇規則形式化分析

3.1 LMD-GHOST 演算法定義

LMD-GHOST（Latest Message-Driven Greedy Heaviest Observed Subtree）是 Gasper 的分叉選擇規則。其核心思想是選擇具有最大累積權重的分支。

def lmd_ghost(
    state: GasperState,
    block_pool: BlockPool,
    attestations: List[Attestation]
) -> BlockHash:
    """
    LMD-GHOST 分叉選擇演算法
    
    形式化定義：
    
    LMD-GHOST(B, A) = argmax_{b ∈ descendents(B)} Weight(b)
    
    其中：
    - B 是創始區塊
    - A 是認證集合
    - descendents(B) 是 B 的所有後代區塊
    - Weight(b) 是區塊 b 的累積權重
    
    累積權重定義：
    Weight(b) = Σ_{v ∈ V} w_v × I(Latest(v) ∈ subtree(b))
    
    其中：
    - w_v 是驗證者 v 的有效質押權重
    - Latest(v) 是 v 最近一次認證的區塊
    - subtree(b) 表示以 b 為根的子樹
    
    這個定義確保：
    1. 每個驗證者只有最新消息被計算
    2. 權重沿著分支向下累積
    3. Greedy 選擇最大權重的分支
    """
    # 從創始區塊開始
    current_block = GENESIS_BLOCK
    
    while True:
        # 獲取當前區塊的所有直接子區塊
        children = block_pool.get_children(current_block)
        
        if not children:
            # 沒有子區塊，當前區塊就是區塊頭
            return current_block.hash
        
        # 計算每個子區塊的權重
        weights = {}
        for child in children:
            weights[child] = compute_cumulative_weight(
                child, 
                attestations,
                state.validators
            )
        
        # 選擇權重最大的子區塊
        # Greedy 原則：總是選擇當前最重的分支
        best_child = max(children, key=lambda c: weights[c])
        
        current_block = best_child


def compute_cumulative_weight(
    block: Block,
    attestations: List[Attestation],
    validators: Dict[ValidatorID, ValidatorState]
) -> Gwei:
    """
    計算區塊的累積權重
    
    數學公式：
    Weight(b) = Σ_{v ∈ Latest_Attesters(b)} balance(v)
    
    其中 Latest_Attesters(b) 是「最近一次認證在 b 所在的分支上」的驗證者集合
    
    實現優化：
    - 使用位元圖快速計算
    - 避免重複計算
    """
    total_weight = 0
    
    for attestation in attestations:
        # 檢查此認證的目標是否在指定區塊的分支上
        if is_in_subtree(attestation.target.block_root, block):
            # 獲取驗證者權重
            validator = validators[attestation.validator_id]
            total_weight += validator.effective_balance
    
    return total_weight


def is_in_subtree(block_root: BlockHash, ancestor: Block) -> bool:
    """
    判斷區塊是否在祖先區塊的子樹中
    
    數學定義：
    is_in_subtree(b, a) ≡ b ∈ subtree(a)
    
    其中 subtree(a) 是以 a 為根的所有後代區塊的集合。
    """
    # 沿著 b 的祖先鏈向上查找
    current = get_block(block_root)
    
    while current is not None:
        if current == ancestor:
            return True
        current = current.parent
    
    return False

3.2 LMD-GHOST 性質證明

命題 2：LMD-GHOST 的 Greedy 性質

定理：LMD-GHOST 選擇的區塊在每個 epoch 內具有最大累積權重。

證明：

我們使用數學歸納法。

基例（Base Case）：
在第一個 epoch，區塊頭是創始區塊 G。
Weight(G) = 0（沒有認證）
LMD-GHOST 選擇 G。

歸納假設：
假設在 epoch k 時，LMD-GHOST 選擇的區塊 b_k 具有最大累積權重。

歸納步驟：
在 epoch k+1，每個驗證者發布新的認證。
根據 LMD 的定義，每個驗證者只計算其最新消息。

考慮任意區塊 b' ∈ descendents(b_k)：
Weight(b') = Weight(b_k) + ΔWeight(b_k → b')

其中 ΔWeight 是從 b_k 到 b' 新增的權重。

對於不在 b_k 分支上的區塊 c：
Weight(c) ≤ Weight(b_k)（因為不包含 b_k 的權重）

因此：
Weight(b') ≥ Weight(b_k) ≥ Weight(c) ∀ c ∈ descendents(G) \ descendents(b_k)

所以 b' 具有最大累積權重。

LMD-GHOST 選擇 b'。

歸納完成，定理得證。
∎

3.3 活性證明

命題 3：LMD-GHOST 的活性（Liveness）

定理：在以下條件下，LMD-GHOST 能夠持續選擇新的區塊：

1. 網路同步假設：消息在平均 Δ 時間內傳播
2. 驗證者活性假設：至少 2/3 的誠實驗證者正確執行協議
3. 區塊提議合理性：每個 slot 至少有一個誠實驗證者被選為提議者

數學分析：

設：
- p = 誠實驗證者被選為提議者的概率
- q = 認證被及時傳播的概率

在給定 slot s，誠實區塊被提議的概率：

P(honest_block) = p × (1 - P(no_honest_proposer))

由於 slot 分配是基於 RANDAO 的隨機過程：

p = 1 / committees_per_epoch / validators_per_committee
  ≈ 1 / 32 / 128
  ≈ 1/4096

但實際上，由於驗證者數量龐大（> 100萬），
p 是足夠大的，使得網路能夠持續出塊。

活性保證：
根據同步網路假設，誠實區塊將在下一個 slot 開始前傳播到大多數驗證者。
這些驗證者將對誠實區塊進行認證。
誠實區塊將獲得 > 2/3 的認證權重。
根據 Casper FFG，該區塊將被最終確認。

因此，LMD-GHOST 提供了活性保證。
∎

第四章：RANDAO 隨機性形式化分析

4.1 RANDAO 機制的數學結構

RANDAO 是以太坊用於產生驗證者選擇隨機種子的協議。其安全性基於多個驗證者的不可協調貢獻。

@dataclass
class RANDAOState:
    """
    RANDAO 狀態
    
    形式化定義：
    RANDAO 是一個遞迴函數：
    
    seed_{e+1} = H(seed_e ⊕ mix_e)
    
    其中：
    - seed_e 是 epoch e 的隨機種子
    - mix_e 是 epoch e 所有提議者的 RANDAO 貢獻
    - H 是密碼學哈希函數（Keccak-256）
    - ⊕ 是異或運算
    """
    current_epoch: int
    seed: bytes32
    randao_mixes: Dict[int, bytes32]  # epoch -> mix


def process_randaoreveal(
    state: RANDAOState,
    epoch: int,
    proposer_index: int,
    reveal: bytes32
) -> RANDAOState:
    """
    處理 RANDAO 揭示
    
    數學公式：
    
    mix_{epoch, proposer} = reveal
    
    最終混合值：
    mix_epoch = ⊕_{p ∈ proposers(epoch)} mix_{epoch, p}
    
    新的種子：
    seed_{epoch+1} = H(seed_epoch || epoch || mix_epoch)
    """
    # 驗證揭示值
    assert verify_randao_reveal(proposer_index, reveal, state.seed)
    
    # 更新混合值
    current_mix = state.randao_mixes.get(epoch, bytes32(0))
    new_mix = xor_bytes(current_mix, reveal)
    state.randao_mixes[epoch] = new_mix
    
    # 如果是 epoch 的最後一個 slot，更新種子
    if is_last_slot_of_epoch(state.slot):
        new_seed = sha256(
            state.seed + encode_int(epoch) + new_mix
        )
        state.seed = new_seed
    
    return state


def get_seed(state: RANDAOState, epoch: int) -> bytes32:
    """
    獲取指定 epoch 的隨機種子
    
    公式：
    seed(epoch) = RANDAO(seed(epoch-1), epoch-1, mix(epoch-1))
    
    這是一個遞迴定義，確保：
    1. 每個 epoch 的種子依賴於所有前一個 epoch 的混合值
    2. 攻擊者無法預測未來的種子，除非控制所有相關提議者
    """
    if epoch == 0:
        return GENESIS_RANDAO_SEED
    
    # 從狀態獲取前一個 epoch 的混合值
    prev_mix = state.randao_mixes.get(epoch - 1, bytes32(0))
    
    # 計算新種子
    return sha256(
        state.seed + encode_int(epoch - 1) + prev_mix
    )

4.2 RANDAO 安全性分析

命題 4：RANDAO 的不可預測性

定理：在以下條件下，攻擊者無法預測未來 epoch 的 RANDAO 種子：

1. 攻擊者控制少於 1/2 的驗證者權重
2. 至少有一個誠實驗證者參與 epoch

數學證明：

設：
- A = 攻擊者控制的驗證者集合
- H = 誠實驗證者集合
- r_i = 第 i 個驗證者的 RANDAO 揭示值
- R = ⊕_{i} r_i  （最終混合值）

攻擊者試圖預測 R。

觀察：
- 攻擊者知道她自己的揭示值：r_a
- 攻擊者不知道誠實驗證者的揭示值：r_h

R = r_a ⊕ r_h ⊕ (⊕_{其他驗證者} r_i)

攻擊者知道的值：
K = r_a

攻擊者不知道的值：
U = r_h ⊕ (⊕_{其他驗證者} r_i)

由於異或運算的特性：
- 對於均勻隨機的 r_h 和 r_i，
- U 的分佈是均勻隨機的，與 K 無關

因此：
P(R = r | K = k) = P(R = r)  （均勻分佈）

攻擊者無法通過 K 獲得關於 R 的信息。

結論：RANDAO 在至少有一個誠實驗證者的情況下是不可預測的。
∎

4.3 RANDAO 的可驗證性

def verify_randao_commitment(
    epoch: int,
    proposer_index: int,
    reveal: bytes32,
    commitment: bytes32,
    randao_sk: bytes32
) -> bool:
    """
    驗證 RANDAO 揭示的承諾
    
    形式化定義：
    
    commit(reveal) = H(reveal)
    
    驗證：
    verify(reveal, commitment) ≡ H(reveal) == commitment
    
    這確保：
    1. 提議者在揭示之前無法知道其他人的揭示值
    2. 提議者必須提交真實的揭示值
    """
    # 重新計算承諾
    computed_commitment = sha256(reveal)
    
    # 驗證承諾匹配
    return computed_commitment == commitment


def verify_randao_reveal(
    proposer_index: int,
    reveal: bytes32,
    seed: bytes32
) -> bool:
    """
    驗證 RANDAO 揭示的有效性
    
    每個提議者需要：
    1. 揭示值與承諾匹配
    2. 揭示值是有效的 BLS 簽名
    
    有效性條件：
    BLS_Verify(
        pubkey[proposer_index],
        domain_DOMAIN_RANDAO,
        reveal,
        signature
    ) == true
    """
    # 獲取提議者公鑰
    pubkey = get_validator_pubkey(proposer_index)
    
    # 驗證 BLS 簽名
    domain = get_domain(DOMAIN_RANDAO, seed)
    return verify_bls_signature(pubkey, domain, reveal)

第五章：驗證者選擇與委派會分配

5.1 驗證者選擇的數學模型

def compute_proposer_index(
    state: GasperState,
    slot: int
) -> ValidatorID:
    """
    計算指定 slot 的區塊提議者
    
    數學公式：
    
    proposer(slot) = 
        validators[
            hash(seed || slot) mod |active_validators|
        ]
    
    其中：
    - seed = RANDAO seed for current epoch
    - slot 是目標 slot 編號
    - |active_validators| 是活躍驗證者數量
    
    這個函數是確定性的：
    - 相同的 slot 總是產生相同的提議者
    - 沒有提議者能夠預測自己何時會被選中
    """
    epoch = slot_to_epoch(slot)
    slot_in_epoch = slot % SLOTS_PER_EPOCH
    
    # 獲取當前 epoch 的 RANDAO 種子和活躍驗證者
    seed = get_seed(state, epoch)
    active_validators = get_active_validators(state, epoch)
    
    # 計算鹽值（防止預測）
    # 引入提案者索引作為額外輸入
    hash_input = seed + encode_int(slot_in_epoch)
    
    # 計算哈希值
    hash_value = sha256(hash_input)
    
    # 轉換為數值
    hash_int = int.from_bytes(hash_value, 'little')
    
    # 選擇驗證者（確定性）
    proposer_index = hash_int % len(active_validators)
    
    return active_validators[proposer_index].id


def compute_committee(
    state: GasperState,
    epoch: int,
    slot: int,
    committee_index: int
) -> List[ValidatorID]:
    """
    計算指定 slot 和委派會索引的委派會成員
    
    數學公式：
    
    committee(slot, i) = 
        shuffle(
            active_validators,
            seed || slot || i
        )[:COMMITTEE_SIZE]
    
    其中：
    - shuffle 是驗證者洗牌函數（基於假隨機排列）
    - seed 是 RANDAO 種子和 epoch 索引的組合
    - COMMITTEE_SIZE 是委派會大小（通常為 128）
    
    洗牌函數的實現：
    使用 Ethereum 2.0 規範中的 `compute_shuffled_index` 函數
    """
    # 獲取 epoch 的隨機種子
    seed = get_seed(state, epoch)
    
    # 添加 slot 和委派會索引到種子
    seed_with_context = sha256(
        seed + encode_int(slot) + encode_int(committee_index)
    )
    
    # 獲取活躍驗證者
    active_validators = get_active_validators(state, epoch)
    validator_indices = list(range(len(active_validators)))
    
    # 計算委派會大小
    committees_per_slot = get_committee_count_per_slot(state, epoch)
    validators_per_committee = len(active_validators) // committees_per_slot
    
    # 計算委派會成員
    committee = []
    for i in range(validators_per_committee):
        shuffled_index = compute_shuffled_index(
            validator_indices,
            (committee_index * validators_per_committee + i) % len(validator_indices),
            seed_with_context
        )
        committee.append(active_validators[shuffled_index].id)
    
    return committee


def compute_shuffled_index(
    validator_indices: List[int],
    index: int,
    seed: bytes32
) -> int:
    """
    計算洗牌後的索引
    
    使用 Swahili 演算法（源自 Ethereum 2.0 規範）：
    
    數學定義：
    
    shuffle(indices, seed) =
        for i in reversed(range(len(indices))):
            if i == 0: break
            seed = hash(seed, i)
            pos = seed % (i + 1)
            swap(indices[i], indices[pos])
        return indices
    
    這個演算法的特點：
    1. 確定性：相同的輸入總是產生相同的輸出
    2. 均勻性：每個位置被選中的概率相等
    3. 不可逆性：無法從輸出推導輸入
    """
    indices = validator_indices.copy()
    n = len(indices)
    
    for i in range(n - 1, 0, -1):
        # 計算鹽值
        seed_with_i = sha256(seed + encode_int(i))
        
        # 轉換為數值
        source = int.from_bytes(seed_with_i, 'little')
        
        # 計算交換位置
        pos = source % (i + 1)
        
        # 交換元素
        indices[i], indices[pos] = indices[pos], indices[i]
    
    return indices[index % n]

5.2 委派會規模的數學推導

命題 5：委派會規模的安全性分析

定理：委派會規模 S 應該滿足以下條件以確保安全性：

1. S × (誠實驗證者比例) > 2S/3  （合理性條件）
2. S 足夠大以防止小團體操縱
3. S 不能過大以避免簽名聚合開銷過高

數學分析：

假設：
- n = 總驗證者數量
- f = 惡意驗證者數量
- h = n - f = 誠實驗證者數量
- S = 委派會規模

合理性概率：
P(> 2S/3 誠實驗證者) = Σ_{k=ceil(2S/3)}^{S} C(S, k) × (h/n)^k × (f/n)^(S-k)

當 S 足夠大時，根據中心極限定理：
P(> 2S/3) ≈ 1 - Φ((2S/3 - μ) / σ)

其中：
μ = S × (h/n)  （期望值）
σ = √(S × (h/n) × (f/n))  （標準差）

為了 P(> 2S/3) > 0.9999（高置信度）：

需要：(2S/3 - μ) / σ > 4

代換：
(2S/3 - S × h/n) / √(S × h/n × f/n) > 4

化簡：
S > 16 × (f/n) × (1 - f/n)^(-2) × (1 - 2f/n)^(-2)

當 f/n = 1/3（最壞情況）：
S > 16 × (1/3) × (2/3)^(-2) × (1/3)^(-2)
S > 16 × (1/3) × (9/4) × 9
S > 108

因此，委派會規模至少需要 108 才能在高惡意比例下保持安全性。

實際選擇：
- 以太坊選擇 S = 128（包含安全邊際）
- 這個規模在實際網路條件下提供了足夠的安全性

第六章：形式化驗證方法論

6.1 TLA+ 規範

以下是 Gasper 共識協議的 TLA+ 形式化規範（簡化版）：

------------------------- MODULE Gasper -------------------------

(* Gasper 共識協議的 TLA+ 規範 *)

CONSTANTS
    (\* 驗證者集合 \*)
    Validators,
    (\* 最大惡意驗證者比例 \*)
    MaxByzantine,
    (\* 區塊哈希集合 \*)
    Blocks,
    (\* Genesis 區塊 \*)
    Genesis

VARIABLES
    (\* 當前紀元 \*)
    epoch,
    (\* 分叉選擇頭 \*)
    forkChoiceHead,
    (\* 合理性狀態映射 \*)
    justified,
    (\* 最終確認狀態映射 \*)
    finalized,
    (\* 驗證者狀態 \*)
    validatorState,
    (\* 認證消息集合 \*)
    attestations,
    (\* 區塊到權重的映射 \*)
    blockWeights

(\* 類型不變量 \*)
TypeOK ==
    /\ epoch \in Nat
    /\ forkChoiceHead \in Blocks
    /\ justified \in [Blocks -> BOOLEAN]
    /\ finalized \in [Blocks -> BOOLEAN]
    /\ validatorState \in [Validators -> {
        "active", "exited", "slashed"}]
    /\ attestations \subseteq Attestation
    /\ blockWeights \in [Blocks -> Nat]

(\* 安全性不變量 \*)
(\* 兩個衝突的區塊不能同時被最終確認 \*)
Safety ==
    \A b1, b2 \in Blocks :
        /\ b1 # b2
        /\ ~IsAncestor(b1, b2)
        /\ ~IsAncestor(b2, b1)
        => ~(finalized[b1] /\ finalized[b2])

(\* 活性不變量 \*)
(\* 如果誠實驗證者持續提出區塊，則區塊最終會被確認 \*)
Liveness ==
    \A b \in Blocks :
        IsProposedByHonest(b)
        => <>finalized[b]

(\* 初始狀態 \*)
Init ==
    /\ epoch = 0
    /\ forkChoiceHead = Genesis
    /\ justified = [b \in Blocks |-> b = Genesis]
    /\ finalized = [b \in Blocks |-> FALSE]
    /\ validatorState = [v \in Validators |-> "active"]
    /\ attestations = {}
    /\ blockWeights = [b \in Blocks |-> 0]

(\* 下一狀態關係 \*)
Next ==
    \E action \in {ProposeBlock, ProcessAttestation, FinalizeCheckpoint} :
        action

(\* 區塊提議動作 \*)
ProposeBlock ==
    /\ \E v \in Validators, b \in Blocks :
        /\ IsProposer(v, epoch, forkChoiceHead)
        /\ validatorState[v] = "active"
        /\ b.parent = forkChoiceHead
        /\ blockWeights' = [blockWeights EXCEPT ![b] = 0]
        /\ attestations' = attestations \cup 
            {CreateAttestation(v, b, epoch)}
        /\ forkChoiceHead' = UpdateForkChoiceHead(
            forkChoiceHead, b, blockWeights')
        /\ UNCHANGED <<epoch, justified, finalized, validatorState>>

(\* 處理認證動作 \*)
ProcessAttestation ==
    /\ \E a \in attestations :
        /\ IsValidAttestation(a)
        /\ validatorState[a.validator] = "active"
        /\ blockWeights' = [blockWeights EXCEPT ![a.target] = 
            blockWeights[a.target] + validatorState[a.validator].weight]
        /\ attestations' = attestations \setminus {a}
        /\ UNCHANGED <<epoch, justified, finalized, validatorState,
                        forkChoiceHead>>

(\* 最終確認動作 \*)
FinalizeCheckpoint ==
    /\ \E c \in Checkpoint :
        /\ JustificationCondition(c)
        /\ justified'[c] = TRUE
        /\ \A parent \in Parents(c) :
            justified'[parent] = TRUE
        /\ c.epoch = epoch - 1
        => finalized'[c] = TRUE
    /\ epoch' = epoch + 1
    /\ UNCHANGED <<forkChoiceHead, attestations, blockWeights,
                    validatorState>>

(\* 合理性條件定義 \*)
JustificationCondition(c) ==
    \E w \in Nat :
        /\ w > 2 * blockWeights[c] / 3
        /\ w = Cardinality({v \in Validators :
            /\ validatorState[v] = "active"
            /\ HasAttestedTo(c, v)})

(\* 配置檢查 \*)
ConfigCheck ==
    MaxByzantine < 1/3

=========================== END MODULE ===========================

6.2 Certora 驗證腳本

以下是使用 Certora Prover 進行 Gasper 安全性驗證的範例腳本：

// Gasper 共識協議的 Certora 驗證規範

// 驗證者結構
struct Validator {
    int effective_balance;
    bool is_slashed;
    int latest_justification_epoch;
    int latest_finalization_epoch;
}

// 區塊結構
struct Block {
    int slot;
    bytes32 block_root;
    Block parent;
}

// 認證結構
struct Attestation {
    int validator_index;
    int slot;
    Block target;
    int source_epoch;
}

// 全域狀態
Validator[] validators;
mapping(int => Block) blocks;
mapping(int => int) block_weights;
mapping(int => bool) justified_blocks;
mapping(int => bool) finalized_blocks;
int current_epoch;
Block fork_choice_head;

// 驗證：安全性
// 兩個衝突的區塊不能同時最終確認
ghost rule no_conflicting_finalization {
    forall (int b1 in blocks) {
        forall (int b2 in blocks) {
            if (finalized_blocks[b1] && finalized_blocks[b2]) {
                assert !(is_conflicting(b1, b2));
            }
        }
    }
}

// 輔助定義：衝突區塊判斷
definition is_conflicting(int b1, int b2) returns bool =
    !(is_ancestor(b1, b2) || is_ancestor(b2, b1));

// 定義：祖先關係
inductive definition is_ancestor(int ancestor, int descendant) {
    if (descendant == GENESIS) {
        return ancestor == GENESIS;
    } else {
        return 
            ancestor == blocks[descendant].parent ||
            is_ancestor(ancestor, blocks[descendant].parent);
    }
}

// 驗證：合理性條件
ghost rule justification_requires_2_3_support {
    forall (int b in blocks) {
        if (justified_blocks[b]) {
            int supporting_weight = calculate_supporting_weight(b);
            int total_weight = get_total_active_weight();
            
            assert supporting_weight > (2 * total_weight) / 3;
        }
    }
}

// 計算支持某區塊的總權重
definition calculate_supporting_weight(int b) returns int =
    sum({ validators[v].effective_balance | 
          v in validators where 
          has_attested_to(v, b) &&
          !validators[v].is_slashed
        });

// 驗證：最終確認條件
ghost rule finalization_requires_consecutive_justification {
    forall (int b in blocks) {
        if (finalized_blocks[b]) {
            int parent_epoch = b.parent.epoch;
            
            // 區塊本身需要合理
            assert justified_blocks[b];
            
            // 父區塊也需要合理
            assert justified_blocks[b.parent];
            
            // epoch 需要連續
            assert b.epoch == parent_epoch + 1;
        }
    }
}

// 驗證：活躍性
// 如果誠實區塊被提出且獲得足夠支持，則最終會被確認
ghost rule liveness_of_honest_blocks {
    // 假設存在一個誠實提出的區塊
    if (exists (int b in blocks) {
        is_proposed_by_honest(b) &&
        has_honest_supermajority(b)
    }) {
        // 那麼該區塊最終會被確認
        assert eventually(finalized_blocks[b]);
    }
}

// 定義：誠實驗證者超級多數
definition has_honest_supermajority(int b) returns bool {
    int honest_weight = 0;
    int total_weight = 0;
    
    for (int v in validators) {
        if (!validators[v].is_slashed) {
            total_weight = total_weight + validators[v].effective_balance;
            if (is_honest(v)) {
                honest_weight = honest_weight + validators[v].effective_balance;
            }
        }
    }
    
    return honest_weight > (2 * total_weight) / 3;
}

第七章：攻擊向量數學分析

7.1 遠程攻擊（Long-Range Attack）

遠程攻擊分析

定義：遠程攻擊是指攻擊者從區塊鏈的早期狀態開始，
試圖建立一條與主鏈競爭的替換鏈。

威脅模型：
- 攻擊者在創始階段是誠實的
- 攻擊者在某個歷史時間點變得不誠實
- 攻擊者保留了歷史私鑰

Gasper 的防禦：

以太坊採用「弱主觀性」（Weak Subjectivity）機制來防禦遠程攻擊。

數學定義：
弱主觀性檢查點（Weak Subjectivity Checkpoint）是這樣一個檢查點，
新節點或長期離線的節點需要從該檢查點開始同步。

定義：弱主觀性週期 WSP（以 epoch 為單位）

設：
- L = 誠實驗證者退出速率
- P = 驗證者質押總量
- D = 存款規模（32 ETH）

則：
WSP = L × P / D

實際取值：
- 以太坊設定 WSP = 2 EPOCHS (= 2 × 32 slots)
- 這意味著節點最多可以離線 2 個 epoch（約 12.8 分鐘）

防禦證明：

假設攻擊者試圖從 WSP 之前的檢查點建立替換鏈。

要成功，攻擊者需要：
1. 控制 > 1/3 的歷史質押（用於阻止最終確認）
2. 或者控制 > 2/3 的歷史質押（用於建立最終確認）

但根據弱主觀性：
- 節點只需要信任 WSP 之內的狀態
- WSP 之內的驗證者集合與當前集合有 > 2/3 重疊
- 因此攻擊者無法在 WSP 範圍內建立有效的替換鏈

7.2 相關性攻擊（Correlation Attack）

相關性攻擊分析

定義：相關性攻擊是指多個驗證者因為相同的外部原因
（如網路問題、軟體 bug）同時離線或行為異常。

數學模型：

設：
- p = 單個驗證者在單個 slot 離線的概率
- n = 驗證者數量
- k = 同時離線的驗證者數量

如果離線事件是獨立的：
P(恰好 k 個離線) = C(n, k) × p^k × (1-p)^(n-k)

如果離線事件是相關的（相關係數 ρ）：
P(恰好 k 個離線) ≈ C(n, k) × (p + ρ × (1-p))^k × (1-p-ρ×(1-p))^(n-k)

當 ρ > 0 時，k 個離線的概率顯著增加。

Gasper 的防禦：

1. 委派會多樣性：
   - 每個 slot 的委派會從整個驗證者集合中隨機選擇
   - 即使部分驗證者離線，其他委派會仍能正常工作

2. 認證聚合：
   - 使用 BLS 簽名聚合來自多個驗證者的認證
   - 即使部分認證延遲，其他認證仍能被處理

3. 最終確認延遲容忍：
   - Gasper 設計能容忍最多 1/3 的驗證者同時離線
   - 離線不會導致網路停止，只會延遲最終確認

結論

本文從形式化驗證的角度，全面分析了以太坊 Gasper 共識機制的安全性與活性：

1. Casper FFG 安全性證明：通過數學推導證明了在惡意驗證者少於 1/3 的條件下，衝突的檢查點不能同時被最終確認。

1. LMD-GHOST 分叉選擇規則：分析了 Greedy 選擇原則的正確性，並提供了活性條件的形式化證明。

1. RANDAO 隨機性：證明了在至少有一個誠實驗證者的條件下，RANDAO 是不可預測且可驗證的。

1. 委派會選擇：通過數學推導確定了委派會規模（128）的安全性邊界。

1. 形式化驗證方法：提供了 TLA+ 和 Certora 兩種形式化驗證工具的規範範例。

Gasper 的設計體現了密碼經濟學協議設計的最佳實踐，通過經濟激勵和密碼學保證的結合，實現了高安全性和活性兼顧的共識機制。

免責聲明： 本網站內容僅供教育與資訊目的，不構成任何投資建議或推薦。在進行任何加密貨幣相關操作前，請自行研究並諮詢專業人士意見。

數據截止日期： 2026-03-25