We can also extend our analysis for announcing the blocks in each slot, and thereby our ledger protocol, to cope with epoch-resettable adversaries. In fact, as long as the reputation system ensemble is a sequence of independent (static) reputation systems, we do not need to make any modification to the protocol other than requiring the parties to refresh their key in each epoch; this can be done interactively, by posting a new key on the blockchain in every epoch and erasing the previous key, or non-interactively by using a forward secure signature scheme [21, 58]. Indeed, although the epoch-resettable adversary will able to predict the next epoch’s committees, he is still bound to select his corrupted parties independently according to their (new) reputation. As long as all reputation vectors (i.e., for each epoch) are feasible, such an adversary will be unable to have a corrupted majority committee chosen, except with negligible probability.

However the above assumption that reputation-vectors of different epoch are independent, might fall short in capturing situations, where malicious parties might try to manipulate their reputation (e.g., by temporarily playing honestly) depending on the protocol’s history. Under the assumption that reputation for the next epoch is already define in the one-but-last slot of the current epoch¹⁶ we can tolerate an epoch-resettable adversary by modifying the way this randomness is selected as follows: We adapt the block announcing protocol to have every party in any committee include, in addition to his transaction pool, a fresh random nonce, and the concatenation of all these nonces is included to the block along with the union of the transactions posted by BC. (The corresponding protocol is given in Figure 14). As the distribution of the reputation vector is decided before the last slot, the choice of all parties in the next epoch will be independent of this distribution and therefore the same guarantees as before will apply.

BlockAnnounce(,,Rep,Bρ-1,ρ,δ,ϵ,L = O(1)): Let ρ denote the reputation parties in Slot ρ. 1. Extract the concatenation of randomness r-1 from the blocks of the previous epoch. 2. Using the above randomness rρ-1,a each party in locally runs the reputation-fair lottery L(,Rep, (c1,…,cm + 1),δ,ϵ,h(rρ-1||0)), where the cjs are as in Theorem 1, to sample a set BA ⊂ ρ (of size polylog(n)); out of this set, the parties choose a random subset BC of constant size L = O(1) by invoking RandSet(BA,L; h(rρ-1||1)). 3. Each party i ∈BC acts as sender in an invocation of Broadcast with receivers the parties in BA and input i’s current transaction pool Ti along with a random nonce ri; i removes the broadcasted transactions from its local transaction pool. 4. All parties in BA compute Y = (,r), where = Validate(TH,T) for T = ∪pi∈BCTi and r is the concatenation of all broadcasted ri’s. If some party j ∈BA did not broadcast a valid message in the previous round of the protocol, then all parties in BA set Tj = {(abort,j)} and rj = 0. 5. Every j ∈BA signs h(Y,h = h(Bρ-1),ρ), where Bρ-1 is a hash pointer to the block of the previous round and sends it to every party in BC. 6. Each i ∈BC: If for some (Y,h,ρ), where ρ is the current slot and h = h(Bρ-1) is a valid hash pointer to the previous block, i receives at least |BA|∕2 signatures from parties in BA on (Y,h), then i multicasts (Y,h,ρ) along with all the corresponding signatures to all nodes in . 7. Each Pi ∈: Upon receiving any (Y,h,ρ) along with signatures on it from at least |BA|∕2 parties from BA, create a block consisting of (Y,h,ρ) and the related signatures and add this block to the blockchain as the current slot’s block and mark the current slot as completed.

Fig. 14: Block announcing protocol for Slot ρ for an epoch resettable adversary 

Unfortunately, the above idea is still problematic. Indeed, since with an epoch resettable adversary the corrupted set is “reset” at the beginning of each epoch, the adversary across two epochs might be able to take keys he learned in the first of the two epoch and use them at the beginning slot of the second epoch (before parties have had a chance to erase) thereby effectively holding the keys of a majority of the parties in the latter epoch, even when both epoch’s reputation systems are ϵ-feasible.

To counter this scenarios, we consider the following strengthening of the notion of ϵ-feasibility:

Note that in the above definition, the corrupted parties are chosen according to Rep from the entire reputation-party set , and independently of the coins of A. (Indeed, otherwise it would be trivial to always corrupt a majority.)

It is easy to verify that if the reputation systems corresponding to all epochs are strongly ϵ-feasible, then the probability that the adversary in two consecutive epochs can launch the above attach (i.e., using the keys learned in the first of the two epochs exceed a minority of corruptions in the second one) is negligible. This is true as long as the two epochs have the same (distribution on the) size of committees, since even if all corrupted parties from the first epoch are selected in the second one, still the adversary will not be able to reach more than a minority of corruptions (since in each epoch at most 1∕4 - ϵ fraction is corrupted).

Since in each epoch the adversary needs to release the parties from the previous epoch which are not newly corrupted, we can have the parties refresh their signing keys in each epoch—either by erasing the old keys and posting new ones on the blockchain or by using a forward-secure signature scheme—thereby ensuring that the adversary can never corrupt a majority. It is easy to verify that the above modification ensures security of our construction against epoch-resettable adversaries.