Byzantine Agreement with Optimal Resilience via Statistical Fraud DetectionByzantine Agreement • June 30th, 2022
Contract Type FiledJune 30th, 2022Proof. Consider the sequence (At)t∈[T ], where A0 = 0, At = At−1 + ΣG(t)2 − 1 ǫ2mf. By Lemma 8, E[ΣG(t)2] ≥ 1 ǫ2mf, so (At)t is a submartingale. Since ΣG(t) is a sum of at most mn coin flips, |At − At−1| = ΣG√(t)2 ≤ mn · c ln n with high probability. By Azuma’s inequality, with high probability, AT ≥