4.4 Common Prex Recall that the chains constructed by honest players during an execution of iSPoS correspond to tines of a fork, as dened and studied in the previous sections. The random assignment of slots to stakeholders given by F D,F guarantees that the coordinates of the associated characteristic string w LS follow the binomial distribution with probability equal to the adversarial stake. Thus Theorem 4.13 establishes that no execution of the protocol iSPoS can induce two tines (chains) of maximal length with no common prex. In the context of iSPoS, however, we wish to establish a much stronger common prex property: any pair of chains which could, in principle, be presented by the adversary to an honest party must have a recent common prex, in the sense that removing a small number of blocks from the shorter chain results in a prex of the longer chain.

To formally articulate and prove this property, we introduce some further denitions regarding tines and forks. We borrow the truncation operator, described earlier in the paper for chains: for a tine t we let tdk denote the tine obtained by removing the last k edges; if length(t) k, we dene tdk to consist solely of the root. 27 Denition 4.24 (Viability). Let F w be a fork for a string w {0, 1}n and let t be a tine of F . We say that t is viable if, for all honest indices h (t), we have

(Recall that (t) is the label of the terminal vertex of t.) If t is viable, an external (honest) observer witnessing the execution at time (t)if provided the tine t along with all honest tines generated up to time (t)could conceivably select t via the maxvalid() rule. Observe that any honest tine is viable: by denition, the depth of the terminal vertex of an honest tine exceeds that of all prior honest vertices. Denition 4.25 (Divergence). Let F be a fork for a string w {0, 1}. For two viable tines t1 and t2 of F , dene their divergence to be the quantity div(t1, t2) = min i (length(ti) length(t1 t2)) , where t1t2 denotes the common prex of t1 and t2. We overload this notation by dening divergence for F as the maximum over all pairs of viable tines: div(F ) = max t1, t2 viable tines of F div(t1, t2) . Finally, dene the divergence of w to be the maximum such divergence over all all possible forks for w: div(w) = max F w

Observe that if div(t1, t2) k and, say, length(t1) length(t2), the tine tdk 1 is a prex of t2. We rst establish that a string with large divergence must have a large forkable substring. We then apply this in Theorem 4.27 below to conclude that characteristic strings arising from iSPoS are unlikely to have large divergence and, hence, possess the common prex property. Theorem 4.26. Let w {0, 1}. Then there is forkable substring w of w with | w| div(w). Proof. Consider a fork F w and a pair of viable tines (t1, t2) for which div(t1, t2) = div(w) . For simplicity, we assume the tines have been labeled so that (t1) < (t2) and further that |(t2) (t1)| is minimum among all pairs of tines for which (11) holds. We begin by identifying the substring w; the remainder of the proof is devoted to constructing a at fork for w to establish forkability. Let y denote the last vertex on the tine t1 t2, as in the diagram below, and let (cid:44) (y) = (t1 t2). t1 y