FPC第二部份 , 第三部份初稿

FPC第二部份 , 第三部份初稿 === # 2.主要內容我們定義兩個事件對應最終共識結果 $H_{i}=\{全部誠實節點到達 i 意見\},\space i=0,1$ 於是 , 聯集 $H_{0} \cup H_{1}$ 代表全部誠實節點有相同的意見 , 即達成共識定義$\varphi_{\beta,q,k}=\frac{\beta-q}{2(1-q)}-e^{-\frac{1}{2}k(\beta-q)^{2}}$ 我們假設 $k$ 足夠大使得 $\varphi_{\beta,q,k} > 0$ 讓 $N$ 是全部誠實節點抵達最終意見所需的回合數下面的結論控制必需的回合數與最終共識達到的機率(即事件$H_{0} \cup H_{1}$發生) ## 定理 2.1 假設 $q < \beta$ $(i)$ 對任何謹慎對手的策略 , 有 (2) (3) $(ii)$ (4) ``` It is important to observe that, for the estimate in (4) to be nontrivial for at least some k , we must have q < 1 − 2β. Also, note that the only diﬀerence between (2) and (4) is that the ψ-term is substituted by the κterm ; as we will see in the proofs, these terms enter into the part which is “responsible” for the estimates on the time until one of the opinions reaches supermajority ; from that moment on , there is essentially no diﬀerence if the adversary is cautious or berserk. ``` 以下這點觀察是重要的 , (4)的估計並不是很明顯 , 至少對某些 $k$ 來講 , 我們必須有 $q < 1-2\beta$ 還有 , 注意到 (2) 與 (4) 的不同是 $\psi$ 項被替換成 $\kappa$ 項 ; 正如我們將在證明看到那樣 , 這些項存在的部份是負責估計其中之一的意見變為絕對多數的時間 ; 到時對手策略是謹慎還是Berserk是沒有差異的 ## 推論 2.2 ``` For a cautious adversary we need that q < β, while for a berserk adversary we also need that q < 1−2β. Recalling also that β must belong to (0,1/2), it is not diﬃcult to see that * for a cautious adversary, for any q < 1/2 and all large enough n we are able to adjust the parameters k,β,m0,l in such a way that the protocol works whp (in particular, a β-value suﬃciently close to 1/2 would work); * however, for a berserk adversary, we are able to do the same only for q < 1/3 (here, β = 1/3 would work). ``` 對手使用謹慎策略 , 我們需要 $q < \beta$ ; 而對手使用berserk策略 , 我們需要 $q < 1-2\beta$ 記得 $\beta$ 是在 $(0,\frac{1}{2})$ 的數 , 不難看出以下兩點 * 對於使用謹慎策略的對手 , 當 $q < \frac{1}{2}$ 和足夠大的 $n$ , 我們可以調整參數:$k,\beta,m_{0},l$ 從而使協定很大機率正常運作(特別的 , $\beta$值接近 $\frac{1}{2}$ 就可以了) * 然而 , 對於使用berserk策略的對手 , 當 $q < \frac{1}{3}$ , 我們一樣可以調整相同的參數讓協定正常運作(這裡 , $\beta=\frac{1}{3}$ 就可以了 ) ## 推論 2.3 ``` One may be interested in asymptotic results, for example, of the following kind: assume that the number of nodes n is ﬁxed (and large), and the proportion of Byzantine nodes q is acceptable (i.e., less than 1/2 for the case of cautious adversary, or less than 1/3 for the case of berserk adversary, as discussed above). We then want to choose the parameters of the protocol in such a way that the probabilities in (2) and (4) are at least 1 − ε(n), where ε(n) is polynomially small in n (i.e., ε(n) = O(n−h) for some h > 0). First, β = 1/3 works in both cases; then, a quick analysis of (2)–(4) shows that one possibility is: chose k = C lnn (with a suﬃciently large constant in front), ` of constant order, and m0 = O lnn lnlnnfor cautious adversary orm 0 = O(lnn) for a berserk one. That is, the overall communicational complexity will be at most Onln2 n lnlnnfor cautious adversary and O(nln2 n) for a berserk one. ``` 一個令人感興趣的近似結果 , 例如以下的討論 , 假設節點數目是固定的(且數目巨大) , 且拜占庭節點的比例 $q$ 是可以接受的 (謹慎對手策略 $q$ 少於 $\frac{1}{2}$ 或 berserk 對手策略 $q$ 少於 $\frac{1}{3}$) 我們想要選擇協定的參數讓(2)和(4)的機率至少有 $1 - \epsilon(n)$ , $\epsilon(n)$ 是多項式小的對於 $n$ (例如 $\epsilon(n)=\mathcal{O}(n^{-h})$ 對某些 $h > 0$) 首先 , $\beta = \frac{1}{3}$ 適用於這兩種情況 ; 簡略分析(2)-(4) , 呈現一種可能性是 : 取 $k=C\ln n$ (有一個足夠大的常數在前面) , $l$ 是常數項 , $m_{0}=\mathcal{O}(\frac{\ln n}{\ln \ln n})$ 對應謹慎對手策略或 $m_{0}=\mathcal{O}(\ln n)$ 對應 berserk 對手策略此時 , 全部節點的通訊複雜度 , 謹慎對手策略最多是 $\mathcal{O}(\frac{n\ln^{2} n}{\ln \ln n})$ , 而 berserk 對手策略最多是 $\mathcal{O}(n\ln^{2} n)$ ``` Next, let ˆ p0 be the initial proportion of 1-opinions among the honest nodes. Our second result shows that if, initially, no signiﬁcant majority of nodes prefer 1, then the ﬁnal consensus will be 0 whp, and if the supermajority of nodes prefer 1, then the ﬁnal consensus will be 1 whp (recall (i)–(ii) in the beginning of Section 1). ``` 接下來 , 讓 $p_{0}$ 是一開始在誠實節點中選擇意見1的比例我們的第二個結果表示 : 如果一開始 , 沒有明顯多的節點選意見1 , 最後共識很大機率會是意見0 ; 如果選意見1的節點是絕對多數 , 最後共識很大機率會是意見1 (回想章節壹一開始的$(i)-(ii)$) ## 定理 2.4 以下的內容 , 我們假設 $q < \beta$ $(i)$ 首先 , 假設 $p_{0}(1-q)+q<a$ , 而且假定 $k$ 是足夠大使得 $e^{-2k(a-P_{0}(1-q)-q)^{2}}\leq \frac{\beta - q}{4(1-q)}$ 那麼 , 我們有 (6) $(ii)$ 現在 , 假設 $p_{0}(1-q)>b$ ,且 $k$ 足夠大使得 $e^{-2k(p_{0}(1-q)-b)^{2}}\leq \frac{\beta -q}{4(1-q)}$ 那就有跟 (6) 相同的估計式對於 $P[H_{1} \cap \{N \leq m_{0}+lu\}]$ ``` We also mention that the estimates (2) and (4) are probably not quite sharp because we have used some union bounds and other “worst-case” arguments when proving them. For example, for n = 1000, k = 20, β = 1/3, ` = m0 = 10, q = 0.1, the system was simulated11 ﬁve thousand times, with all of them resulting in consensus after not more than 44 rounds; for these parameter values, the bounds provided by (2) and (4) are not quite useful. For a more concrete results on the number of necessary rounds until consensus (with diﬀerent parameters), see Figure 1. It is interesting to observe that, in most cases, the protocol ﬁnalizes after the minimal number m0 + ` = 10 of rounds. ``` 我們提到 (2) 與 (4) 的估計大概不是十分的精準 , 因為我們使用一些聯集的邊界與 "壞的情況" 的參數在證明 (2) , (4) 的時候例如 , 對 $n=1000,k=20,\beta=\frac{1}{3},l=m_{0}=10,q=0.1$ , 系統模擬了 5000 次 [11] , 達到共識所需的回合最多不超過 44 次 ; 對以上這些參數 , (2) 與 (4) 所估計的範圍並不是很有用對更多達到共識所需具體的回合數 , 請看圖 1 注意到有趣的一點 : 在許多例子中 , 達到共識所需最小回合數是 $m_{0}+l=10$ :::info 11 : with the simple adversarial strategy “vote for the weakest” aiming to prevent the honest nodes from achieving supermajority of one of the opinions for as long as possible; however, we do not believe that the adversary can invent something radically better since, as we will see below, the adversary loses control completely after such a supermajority is achieved ::: 對手策略 "投票給最少的" , 使得誠實節點達到絕對多數的意見盡可能的拖延然而 , 我們並不相信這樣的策略可以得到更好的結果如同接下來看到的 , 這樣的對抗策略在誠實節點達到絕對多數後將完全喪失控制權 ``` Figure 1: Number of rounds till the protocol ﬁnalizes, with n = 1000, a = 0.75, b = 0.85, m0 = ` = 5, k = 20, and q = 0.1. ``` 圖 1 : 協定最終確定的總回合數 , 在 $n=1000$ , $a=0.75$ , $b=0.85$ , $m_{0}=l=5$ , $k=20$ 和 $q=0.1$ # 3.證明 ``` We start with some preliminaries. Let us recall the Chernoﬀ’s bound for the binomial distribution12: if Sk is a binomial B(k,p) random variable, then for any k and γ with 0 < γ < p < 1, we have (7) where (8) the same estimate (7) also holds for P[k−1Sk ≥ γ] in the case 0 < p < γ < 1. We will also use the Hoeﬀding’s inequality [14], which is not so precise as (7), but is more convenient to use in the case when γ and p are close: if 0 < γ < p < 1, then (9) and, as before, the same estimate also holds for P[k−1Sk ≥ γ] in the case 0 < p < γ < 1. In fact, we will use (9) much more frequently than (7) since it is more tractable analytically (imagine, for example, solving the equation H(γ,p) = c for γ with ﬁxed p and c). ``` 我們從一些證明前的準備開始讓我們回想二項分佈的Chernoﬀ’s bound [12] : 如果 $S_{k}$ 是一個二項分佈 $\mathcal{B}(k,p)$ 的隨機變數 , 那對任何 $k$ 和 $\gamma$ , 且$0 < \gamma < p < 1$ , 我們有 $\mathbb{P}[k^{-1}S_{k} \leq \gamma] \leq exp\{-kH(\gamma,p)\}$ (7) 這裡 $H(\gamma,p)=\gamma \ln\frac{\gamma}{p}+(1-\gamma)\ln\frac{1-\gamma}{1-p} > 0$ 有跟 (7) 相同的估計式對於 $\mathbb{P}[k^{-1}S_{k} \geq \gamma]$ 在 $0 < p < \gamma < 1$ 的情況我們繼續使用 Hoeﬀding’s inequality , 此不等式不是像 (7) 那樣精確 , 但足夠方便用於 $\gamma$ 與 $p$ 接近的情況 : 如果 $0 < \gamma < p < 1$ , 那就有 $\mathbb{P}[k^{-1}S_{k} \leq \gamma] \leq exp\{-2k(p-\gamma)^{2}\}$ (9) , 就像之前的 , 也有相同的估計式對於 $\mathbb{P}[k^{-1}S_{k} \geq \gamma]$ 在 $0 < p < \gamma < 1$ 的情況事實上 , 我們使用 (9) 的次數會比 (7) 多 , 因為 (9) 更容易分析 (想像一個例子 , 解方程 $H(\gamma,p)=c$ 當 $p$ 和 $c$ 是常數) :::info 12 : see e.g. Proposition 5.2 of Chapter 8 of [19], or Section 6 of Chapter I of [21] ::: 12 : 看 [19] 的第 8 章 5.2 命題 , 或 [21] 第 1 章第 6 部份 ``` To better understand the diﬀerence between cautious and berserk adversaries, look at Figure 2. Here, ˆ p is the initial proportion of 1-opinions between the honest nodes, and the crosses mark the proportion of 1-responses to the k queries that the honest nodes obtain. The cautious adversary can choose any ˜ p ∈ [ˆ p(1−q), ˆ p(1−q) + q] (by adjusting the opinions of his nodes appropriately, so that the overall proportion of 1-opinions would be ˜ p), and then those crosses will be (mostly) concentrated in the interval of length of order k−1/2 around ˜ p. On the other hand, the berserk adversary can cause the crosses to be distributed in any way on the whole interval [ˆ p(1−q), ˆ p(1−q) + q], with some of them even going a bit out of it (on the distance of order k−1/2 again). ``` 為了更好理解謹慎與 berserk 對手策略的差異 , 見圖2 這裡 , $\hat{p}$ 是一開始誠實節點中意見為 1 的節點比例 , 而圖中的十字標記表示誠實節點進行 $k$ 次查詢後 , 意見 1 的比例謹慎的對手策略可以取 $\widetilde{p} \in [\hat{p}(1-q),\hat{p}(1-q)+q]$ (藉由適當調整節點的意見 , 使得意見 1 的比例是 $\widetilde{p}$) , 而十字標記集中(大部份)在包含 $\widetilde{p}$ 寬 $k^{-\frac{1}{2}}$ 的區間內另一方面 , berserk 對手策略可以讓這些十字標記是分佈在區間 $[\hat{p}(1-q),\hat{p}(1-q)+q]$ 內任何地方 , 甚至有些超出了這個區間 (距離約 $k^{-\frac{1}{2}}$) ``` Figure 2: What cautious and berserk adversaries can achieve ``` 圖 2 : 謹慎與berserk對手策略可以造成的影響 ``` Next, we need an auxiliary result on a likely outcome of a round in the case when the adversary cannot make the typical proportion of 1-responses to be close to the decision threshold. Let η(j) be the number of 1-responses among k queries that jth honest node receives; in general, the random variables (η(j),j = 1,...,(1−q)n) are not independent, but they are conditionally independent given the adversary’s strategy. (Note that η(j) ∼ B(k, ˜ p) with some possibly random ˜ p if the adversary is cautious, but the situation may be more complicated for a berserk one.) For a ﬁxed λ ∈ (0,1), deﬁne a random variable ˆ p = 1 (1−q)n (1−q)n X j=1 1{η(j) ≥ λk}; so that ˆ p is the new proportion of 1-opinions among the honest nodes, given that the “decision threshold” equals λ. Then, the following result holds: ``` 接下來 , 當對手策略無法使意見 1 的比例接近門檻值 , 我們需要一些輔助的性質在一回合結束後令 $\eta(j)$ 為第 $j$ 個誠實節點接收到意見 1 的數量在 $k$ 次的查詢中 ; 一般來說 , 隨機變數 $\eta(j)$ ($\eta(j),j=1,...,(1-q)n$) 並不是獨立的 , 但它們是條件獨立於給定的對手策略 (注意 $\eta(j)\sim \mathcal{B}(k,\widetilde{p})$ 當對手策略是謹慎的時候 , 然而 berserk 對手策略可能會更複雜) 對一個固定的$\lambda \in (0,1)$ , 定義隨機變數 $\widehat{p}=\frac{1}{(1-q)n}\sum\limits_{j=1}^{(1-q)n}1\{\eta(j)\geq \lambda k\}$ 所以 $\widehat{p}$ 是新的誠實節點意見 1 的比例 , 當給定一個決策門檻 $\lambda$ 時那麼 , 以下結果成立: ## 引理 3.1 ``` Assume that, conditioned on any adversarial strategy, there are some positive c and θ such that η(j) is stochastically dominated by B(k,λ−c) for all j = 1,...,(1−q)n, and P[B(k,λ−c) ≥ λk] ≤ θ. Then, for any v > 0 (10) ``` $(i)$ 假設在任何對手策略的限制下 , 有兩個正數 $c$ 和 $\theta$ 使得 $\eta(j)$ 是被 $\mathcal{B}(k,\lambda-c)$ 隨機主導的當 $j=1,...,(1-q)n$ , 且 $\mathbb{P}[\mathcal{B}(k,\lambda-c) \geq \lambda k] \leq \theta$ 那麼 , 對任意的 $v > 0$ , $\mathbb{P}[\hat{p} > \theta + v] \leq e^{-2(1-q)nv^{2}}$ (10) ``` Assume that, conditioned on any adversarial strategy, η(j) stochastically dominatesB(k,λ+c) for all j = 1,...,(1−q)n, and P[B(k,λ+c) ≤ λk] ≤ θ. Then, for any v > 0 (11) ``` $(ii)$ 假設在任何對手策略的限制下 , $\eta(j)$ 被 $\mathcal{B}(k,\lambda+c)$ 隨機主導當 $j=1,...,(1-q)n$ , 且 $\mathbb{P}[\mathcal{B}(k,\lambda+c) \leq \lambda k] \leq \theta$ 那麼 , 對任意的 $v > 0$ , $\mathbb{P}[\hat{p} < 1-\theta - v] \leq e^{-2(1-q)nv^{2}}$ (11) ``` Proof. For (i), we observe that (1 − q)nˆ p is stochastically dominated by B(n,θ), and then (10) follows from (9). The proof of the part (ii) is completely analogous. Note that, by (9), P[B(k,λ−c) ≥ λk] ≤ e−2kc2 (and the same holds forP [B(k,λ + c) ≤ λk]), so we will normally use Lemma 3.1 with θ = e−2kc2. Another elementary fact we need is ``` 證明對於 $(i)$ , 我們注意到 $(1-q)n\hat{p}$ 是被 $\mathcal{B}(n,\theta)$ 隨機主導的 , 那麼 (10) 是從 (9) 推過來的 $(ii)$ 的證明也是類似的注意到 , 由 (9) , $\mathbb{P}[\mathcal{B}(k,\lambda-c) \geq \lambda k] \leq e^{-2kc^{2}}$(且$\mathbb{P}[\mathcal{B}(k,\lambda+c) \leq \lambda k]$) , 所以用 lemma 3.1 , 令$\theta=e^{-2kc^{2}}$ 另一些需要的事實是 ## 引理 3.2 ``` Let (ξ(j) m ,m ≥ 1),j = 1,...,N be N sequences of independentBernoulli trials 13 with success probability h ∈ (0,1). For j = 1,...,N deﬁne τ(1) j = minm ≥ ` : ξ(j) m = ξ(j) m−1 = ... = ξ(j) m−`+1 = 1 and τ(0) j = minm ≥ ` : ξ(j) m = ξ(j) m−1 = ... = ξ(j) m−`+1 = 0 to be the ﬁrst moments when runs of ` ones (respectively, zeros) are observed in jth sequence. Then, for all u ∈N, P[τ(1) j ≤ `u,τ(1) j < τ(0) j ] ≥ 1−(1−h`)u −1−h h `−1 (12) for all j = 1,...,N, and P[τ(1) j ≤ `u,τ(1) j < τ(0) j ,∀j = 1,...,N] ≥ 1−N(1−h`)u +1−h h `−1. (13) ``` 讓 $(\xi^{(j)}_{m},m \geq 1),j=1,...,N$ 是 $N$ 個獨立的伯努利試驗序列[13]有成功的機率 $h \in (0,1)$ 對 $j=1,...,N$ , 定義 $\tau^{1}_{j}=min\{m \geq l:\xi^{(j)}_{m}=\xi^{(j)}_{m-1}=...=\xi^{(j)}_{m-l+1}=1\}$ 和 $\tau^{0}_{j}=min\{m \geq l:\xi^{(j)}_{m}=\xi^{(j)}_{m-1}=...=\xi^{(j)}_{m-l+1}=0\}$ 是第一次有 $l$ 回的意見 1 (另一個是意見 0)在 $j$ 序列中觀察到然後 , 對全部的 $u \in \mathbb{N}$ , 有 $\mathbb{P}[\tau^{1}_{j}\leq lu,\tau^{1}_{j} \leq \tau^{0}_{j}] \geq 1-(1-h^{l})^{u}-(\frac{1-h}{h})^{l-1}$ (12) 對所有的 $j=1,...,N$ , 有 $\mathbb{P}[\tau^{1}_{j}\leq lu,\tau^{1}_{j} \leq \tau^{0}_{j},\forall j=1,...,N]\geq 1-N\lgroup(1-h^{l})^{u}+(\frac{1-h}{h})^{l-1}\rgroup$ (13) :::info 13 the sequences themselves are not assumed to be independent between each other ::: 13 : 不假設序列彼此獨立 ``` Proof. First, it is clear that P[τ(1) j ≤ `u] ≥ 1−(1−h`)u (14) (divide the time interval [1,`u] into u subintervals of length ` and note that each of these subintervals is all-1 with probability h`). Then, the following is an easy exercise on computing probabilities via conditioning (for the sake of completeness, we prove this fact in the Appendix): P[τ(1) j < τ(0) j ] = 1− (1−h)`−1(1−h`) h`−1 + (1−h)`−1 −(h(1−h))`−1 . (15) Observe that (15) implies that (since 1−h` ≤ 1 and (1−h)`−1 −(h(1−h ))`−1 ≥ 0) P[τ(1) j < τ(0) j ] ≥ 1−1−h h `−1, and so, using the above together with (14) and the union bound, we obtain (12). The relation (13) is then a direct consequence of (12) (again, with the union bound). To prove our main results, we need some additional notation. Let %(j) be the round when the jth (honest) node ﬁnalizes its opinion. Denote Rm = {j : %(j) ≤ m} to be the subset of honest nodes that ﬁnalized their opinions by round m. Let also ˆ ξm(j) be the opinion of jth node after the mth round and ˆ pm = 1 (1−q)n (1−q)n X j=1 ˆ ξm(j) (16) be the proportion of 1-opinions among the honest nodes after the jth round in the original system. ``` 證明 : 首先 , 下面不等式是明顯的 $\mathbb{P}[\tau^{(1)}_{j}\leq lu]\geq 1-(1-h^{l})^{u}$ (14) (分割時間區間 $[1,lu]$ 為 $u$ 個長度為 $l$ 的子區間 , 且注意每個子區間全是意見 1 的機率是 $h^{l}$) 那麼 , 下面結果是簡單的機率計算透過給定的條件(完整的證明結果 , 放在附錄) $\mathbb{P}[\tau^{(1)}_{j}<\tau^{(0)}_{j}]=1-\frac{(1-h)^{l-1}(1-h^{l})}{h^{l-1}+(1-h)^{l-1}-(h(1-h))^{l-1}}$ (15) 明顯 (15) 可以推出(因為 $1-h^{l}\leq 1$ 和 $(1-h)^{l-1}-(h(1-h))^{l-1}\geq 0$) $\mathbb{P}[\tau^{(1)}_{j}<\tau^{(0)}_{j}]\geq 1-(\frac{1-h}{h})^{l-1}$ 接下來 , 使用 (14) 和上面的不等式 , 得到 (12) (13) 是 (12) 的直接結果(再次用上兩個不等式) 為了證明主要的結果 , 我們需要一些新的符號讓 $\varrho(j)$ 是某回合第 $j$ 個誠實節點選擇好最終意見記 $R_{m}=\{j:\varrho(j)\leq m\}$ 是集合第 $j$ 個誠實節點決定最終意見在 $m$ 以下的回合數讓 $\hat{\xi}_{m}(j)$ 是 $j$ 意見在 $m$ 回合 , 且 $\hat{p}_{m}=\frac{1}{(1-q)n}\sum\limits_{j=1}^{(1-q)n}\hat{\xi}_{m}(j)$ 是誠實節點在 $j$ 回合意見 1 的比例 ``` Proof of Theorem 2.1. Let us deﬁne the random variable Ψ = minnm ≥ 1 : ˆ pm ≤ β −q 2(1−q) or ˆ pm ≥ 1− β −q 2(1−q)o (17) to be the round after which the proportion of 1-opinions among the honest nodes either becomes “too small”, or “too large”. We now need the following fact: ``` 定理 2.1 的證明讓我們定義隨機變數 $\Psi=min\{m\geq 1:\hat{p}_{m}\leq \frac{\beta-q}{2(1-q)} \space or \space \hat{p}_{m} \geq 1-\frac{\beta-q}{2(1-q)} \}$ (17) 是某回合後意見 1 誠實節點的比例"太大"或"太小" 我們現在需要下列的事實: ## 引理 3.3 ``` For all s ≤ m0 + `, it holds that (recall (3) and (5)) P[Ψ > s] ≤   ψ(q,β,n,k)s−1, for cautious adversary, κ(q,β,n,k)s−1, for berserk adversary. (18)Proof. Observe that s ≤ m0+` implies that a node cannot ﬁnalize its opinionbefore round s. Consider ﬁrst the case of a cautious adversary. Abbreviate (for this proof) µ = β−q 4(1−q) . Let m ≥ 2 and observe that, for any ﬁxed h ∈ [0,1] we have (recall that Xm ∼ U[β,1−β]) Pe−2k(Xm−h)2 ≥ µ= Ph(Xm −h)2 ≤ lnµ−1 2k i = Phh−rlnµ−1 2k ≤ Xm ≤ h +rlnµ−1 2k i ≤ (1−2β)−1r2lnµ−1 k . (19) Now, assume that ˜ pm−1 = h. Under this, using (9) and (19), we obtain by conditioning on the value of Xm P[ˆ pm ∈ (2µ,1−2µ)] = EP[ˆ pm ∈ (2µ,1−2µ) | Xm] = EP[ˆ pm ∈ (2µ,1−2µ) | Xm]1{e−2k(Xm−h)2 < µ} +P[ˆ pm ∈ (2µ,1−2µ) | Xm]1{e−2k(Xm−h)2 ≥ µ}≤ EP[ˆ pm > 2µ | Xm]1{e−2k(Xm−h)2 < µ,h < Xm} +P[ˆ pm < 1−2µ | Xm]1{e−2k(Xm−h)2 < µ,h > Xm} + 1{e−2k(Xm−h)2 ≥ µ}≤ 2P((1−q)n)−1B((1−q)n,e−2k(1−µ)) < 1−2µ +P[e−2k(Xm−h)2 ≥ µ] ≤ ψ(µ,n,k), (20) recall (3). This implies the ﬁrst comparison in (18). For a berserk adversary, the calculation is quite analogous (recall Figure 2), so we omit it. ``` 對所有 $s \leq m_{0}+l$ , 有兩個結果(回想(3)和(5)) : $\mathbb{P}[\Psi>s]\leq \left\{ \begin{array}{lr}(\psi(q,\beta,n,k))^{s-1} , 在謹慎對手策略\\ (\kappa(q,\beta,n,k))^{s-1} , 在berserk對手策略 \end{array} \right.$ (18) 證明: 注意到 $s \leq m_{0}+l$ 意味著節點沒有在 $s$ 回合前敲定它的意見首先考慮謹慎對手策略記 $\mu=\frac{\beta-q}{4(1-q)}$ , 讓 $m \geq 2$ , 而且注意到 , 對任意的 $h \in [0,1]$ 我們有 (回想 $X_{m} \sim U[\beta,1-\beta]$) (19) 現在 , 假設 $\widetilde{p}_{m-1}=h$ 利用剛才的假設 , 應用 (9) 與 (19) , 我們藉由調整 $X_{m}$ 的數值得到 (20) 回想 (3) , 這意味著 (18) 第一次的對照對berserk對手策略 , 計算十分類似(回想圖2) , 所以省略不講 ``` Figure 3: Transition from ˆ pm to ˆ pm+1: after mth round, being ˆ pm ≤ β−q 2(1−q) , the adversary may “grow” the proportion of 1s to ˆ pm(1−q)+q ≤ β+q 2 . Then, since the diﬀerence between that and “the least possible threshold” β is at least β−q 2 , the probability that an undecided node would have opinion 1 in the next round is at most e−1 2k(β−q)2. Then, with overwhelming probability ˆ pm+1 will be at most β−q 2(1−q) , and so it goes. ``` 圖3: $\hat{p}_{m}$ 轉移到 $\hat{p}_{m+1}$ 的過程: 在 $m$ 回合後 , $\hat{p}_{m} \leq \frac{\beta-q}{2(1-q)}$ 對手策略可能使意見一誠實節點的比例成長為 $\hat{p}_{m}(1-q)+q \leq \frac{\beta+q}{2}$ 因為上式與 "至少機率門檻" $\beta$ 的差距至少是 $\frac{\beta-q}{2}$ , 尚未決定的誠實節點下一回合選意見一的機率最多是 $e^{-\frac{1}{2}k(\beta-q)^{2}}$ 以壓倒的機率 , $\hat{p}_{m+1}$ 最多是 $\frac{\beta-q}{2(1-q)}$ ``` Next, we need a result that shows that if one of the opinions has already reached a supermajority, then this situation is likely to be preserved. ``` 接下來 , 我們需要來證明如果一個意見變成絕對多數 , 這結果很可能會保留到接下來的回合 ## 引理 3.4 ``` Let m ≥ 2; in the following, A will denote a subset of{1,...,(1− q)n}. (i) Let G0 be the event that ˆ pm ≤ β−q 2(1−q) , Rm−1 = A, and ˆ ξm−1(j) = 0 for all j ∈ A. Then Phˆ pm+1 ≤ β −q 2(1−q) G0i≥ 1−e−2(1−q)nϕ2β,q,k. (21) (ii) Let G1 be the event that ˆ pm ≥ 1− β−q 2(1−q) , Rm−1 = A, and ˆ ξm−1(j) = 1 for all j ∈ A. Then Phˆ pm+1 ≥ 1− β −q 2(1−q) G1i≥ 1−e−2(1−q)nϕ2β,q,k. (22) Proof. We prove only part (i), the proof of the other part is completely analogous. Now, look at Figure 3: essentially, this is a direct consequence of Lemma 3.1 with θ = e−2k(β−q 2 )2 = e−1 2k(β−q)2 and v = ϕβ,q,k. Observe also that, if some honest nodes already decided on 0 deﬁnitely, it holds that (1−q)nˆ pm+1 is stochastically dominated by B(1−q)n,e−1 2k(β−q)2. ``` 讓 $m \geq 2$ , 在下面式子中 , 記 $A$ 為 $\{1,...,(1-q)n\}$ 的子集 $(i)$ 讓 $G_{0}$ 是事件 $\hat{p}_{m}\leq \frac{\beta-q}{2(1-q)}$ , $R_{m-1}=A$ , 且 $\hat{\xi}_{m-1}(j)=0$ 對所有 $j \in A$ 那麼 (21) $(ii)$ 讓 $G_{1}$ 是事件 $\hat{p}_{m}\geq 1-\frac{\beta-q}{2(1-q)}$ , $R_{m-1}=A$ , 且 $\hat{\xi}_{m-1}(j)=1$ 對所有的 $j \in A$ 那麼 (22) ``` Proof. We prove only part (i), the proof of the other part is completely analogous. Now, look at Figure 3: essentially, this is a direct consequence of Lemma 3.1 with θ = e−2k(β−q 2 )2 = e−1 2k(β−q)2 and v = ϕβ,q,k. Observe also that, if some honest nodes already decided on 0 deﬁnitely, it holds that (1−q)nˆ pm+1 is stochastically dominated by B(1−q)n,e−1 2k(β−q)2. ``` 證明我們只證明 $(i)$ , $(ii)$ 的證明完全類似現在 , 看向圖3 : 實際上 , 這是 lemma 3.1 直接的推導 , 有 $\theta=e^{-2k(\frac{\beta-q}{2})^{2}}=e^{-\frac{1}{2}k(\beta-q)^{2}}$ 和 $v=\psi_{\beta,q,k}$ 也注意到 , 如果一些誠實節點已經確定是意見0 , 那麼 $(1-q)n\hat{p}_{m+1}$ 是由 $\mathcal{B}((1-q)n,e^{-\frac{1}{2}k(\beta-q)^{2}})$ 隨機支配 ``` Now, we are able to conclude the proof of Theorem 2.1. Let us introduce the random variable Z =     minnm > Ψ : ˆ pm > β−q 2(1−q)o on ˆ pΨ ≤ β−q 2(1−q) , minnm > Ψ : ˆ pm < 1− β−q 2(1−q)o on ˆ pΨ ≥ 1− β−q 2(1−q) (23) to be the ﬁrst moment after Ψ when the honest nodes’ opinion has drifted away from supermajority. Denote also ˆ τ(1) j = minm ≥ m0 + ` : ˆ ξ(j) m = ˆ ξ(j) m−1 = ... = ˆ ξ(j) m−`+1 = 1 and ˆ τ(0) j = minm ≥ m0 + ` : ˆ ξ(j) m = ˆ ξ(j) m−1 = ... = ˆ ξ(j) m−`+1 = 0 . Next, observe that (H0 ∪H1)∩{N ≤ m0 + `u}⊂ D1 ∩D2 ∩D3, where D1 = {Ψ ≤ m0}, D2 = {Z ≥ m0 + `u}, D3 =there is i ∈{0,1} such that ˆ τ(i) j ≤ m0 + `u, ˆ τ(i) j < ˆ τ(1−i) j for all j = 1,...,(1−q)n . To obtain the estimates (2) and (4), it is enough to note that the lower bounds on, respectively, P[D1], P[D2], and P[D3], follow from, respectively, Lemma 3.3, Lemma 3.4, and Lemma 3.2 (and also the union bound). ``` 現在 , 我們能夠說明定理 2.1 的證明讓我們介紹以下的隨機變數 (23) 是在 $\Psi$ 後第一次 , 誠實節點的意見不是之前回合絕對多數的意見記 $\tau^{1}_{j}=min\{m \geq l:\xi^{(j)}_{m}=\xi^{(j)}_{m-1}=...=\xi^{(j)}_{m-l+1}=1\}$ 和 $\tau^{0}_{j}=min\{m \geq l:\xi^{(j)}_{m}=\xi^{(j)}_{m-1}=...=\xi^{(j)}_{m-l+1}=0\}$ 現在 , 注意到 $(H_{0}\cup H_{1})\cap \{\mathcal{N}\leq m_{0}+lu\}\subset D_{1}\cap D_{2}\cap D_{3}$ , 這裡 $D_{1}=\{\Psi\leq m_{0}\}$ , $D_{2}=\{Z\geq m_{0}+lu\}$ , $D_{3}=\{這裡 i\in \{0,1\} 使得 \hat{\tau_{j}}^{(i)}\leq m_{0}+lu,\hat{\tau_{j}}^{(i)}< \hat{\tau_{j}}^{(1-i)} 對所有的 j=1,...,(1-q)n \}$ 為了取得 (2) 和 (4) 的估計 , 需計算 $\mathbb{P}[D_{1}]$ , $\mathbb{P}[D_{2}]$ 和 $\mathbb{P}[D_{3}]$ , 而以上的機率足夠計算出估計的下界接著去計算 , 以上機率分別對應引理 3.3 , 引理 3.4 和引理3.2(還有邊界的約束) ``` Proof of Theorem 2.4. We prove only the part (i); the proof of the other part is completely analogous. In fact, to obtain the proof it is enough to observe that, if a−ˆ p0(1−q)−q > 0 and e−2k(a−ˆ p0(1−q)−q)2 ≤ β−q 4(1−q) , then, by (9), with probability at least 1−exp− 1 8n(β−q)2 4(1−q)it happens that ˆ p1 ≤ β−q 2(1−q) (so, in particular, Ψ = 1); next, the same argument as in the proof of Theorem 2.1 does the work ``` 定理 2.4 的證明我們只證明 $(i)$ , 另一部份的證明完全類似事實上 , 證明是淺顯易見的 , 如果 $a-\hat{p}_{0}(1-q)-q > 0$ 和 $e^{-2k(a-\hat{p}_{0}(1-q)-q)^{2}}\leq \frac{\beta-q}{4(1-q)}$ , 由 (9) , $\hat{p}_{1}\leq \frac{\beta-q}{2(1-q)}$ 發生的機率至少是 $1-exp(-\frac{1}{8}n\frac{(\beta-q)^{2}}{4(1-q)})$ (所以 , 特別是 $\Psi=1$) ; 接下來 , 用相同的方法證明定理 2.1 # 4.結論