We next describe how a PoR-fair lottery can be used to obtain a PoR-blockchain. The ground truth of the 13blockchain is recorded on the genesis block which includes the (initial) set of reputation parties, their public keys, and the corresponding reputation vector. We assume a canonical way of validating transactions submitted in the same round, e.g., if two received transactions which have not-yet been inserted into a block would contradict each other (e.g., correspond to double-spending), a default rule of ignoring both can be adopted. We abstract this by means of a predicate Validate, that takes as input a sequence T (of transactions) along with a current vector T_H of transaction history—composed by concatenating the transactions in the blockchain, and outputs a subset T′⊆ T such that T_H||T′ is a valid sequence of transactions.

An informal description of the protocol is given in Fig.  7 . The idea of the protocol for proposing and agreeing on the block of any given slot is as follows: A small (i.e., polylogarithmic) slot-committee BA is chosen using our above lottery—recall that the lottery will guarantee that the majority in BA is honest and therefore it can run Byzantine agreement protocols (Consensus and Broadcast). From BA a smaller (constant-size) committee BC is randomly chosen to broadcast its transactions to everyone. Note that whenever in our protocol we say that a party P broadcasts a message, we mean that a Byzantine broadcast protocol is executed with P as sender; to avoid confusion we will signify this by saying that that the message is broadcasted by means of protocol Broadcast. We will use multicasting to refer to the process of sending a message through the diffusion network to all parties.

Using Broadcast to communicate the transactions known to BC allows us to agree on the union of all transactions known to these parties. However, broadcasting to the whole player set has a big communication and round overhead. To avoid the overhead we use the following idea: Recall that the parties in BA are all reputation parties and can therefore communicate directly. Thus, instead of directly broadcasting to the whole party set the parties in BC broadcast to the parties in BA. ¹⁴ The security of the broadcast protocol ensures that the parties in BA agree on the broadcasted messages and therefore also on the union. What remains is to extend this agreement to the whole player set. This can be easily done since the majority of the parties in BA is honest: Every party in BA signs the union of the received broadcasted messages and sends it to every party in . The fact that BA has honest majority implies that the only message that might be accepted is this agreed upon union. Hence, once any P ∈ receives such a majority-supported set, he can adopt it as the contents of this slot’s block. The above approach brings an asymptotic reduction on the communication complexity of the protocol from Ω(n²) down to O(nlog ^ϵn), for some constant ϵ > 1. (The worst-case round complexity also has an asymptotic reduction but this depends on the actual reputation system and the choice of protocol Broadcast.) Additionally, the fact that reputation parties communicate over point-to-point (rather than gossiping) network is likely to further to improve the concrete communication complexity, at least for certain network topologies.

A remaining question is: Where does the randomness for the selection of BA and BC come from? For the static reputation-restricted adversary considered here, we extract the randomness for choosing each BA by repeated calls to the random oracle. In the appendix we discuss how we can extend our treatment using standard techniques to tolerate epoch-resettable adversaries. The formal description of the protocol for announcing and agreeing on the next block can be found in Figure  8 . The proof of the following theorem follows the above line of argument and can also be found in Appendix  C.2 .

BlockAnnounce(,,Rep,Bρ-1,ρ,δ,ϵ,L = O(1)): 1. Each party in locally runs the reputation-fair lottery L(,Rep, (c1,…,cm),δ,ϵ,h(ρ||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(ρ||1)). 2. 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; i removes the broadcasted transactions from its local transaction pool. 3. All parties in BA compute = Validate(TH,T) for T = ∪pi∈BCTi. If some party j ∈BC did not broadcast a valid message in the previous round of the protocol, then all parties in BA set Tj = {(abort,j)}. 4. Every j ∈ BA signs h(,h = h(Bρ-1),ρ), where Bρ-1 is the previous block,a and sends it to every party in BC. 5. Each i ∈BC: If i receives at least |BA|∕2 signatures from parties in BA on some (,h), where ρ is the current slot and h = h(Bρ-1) is a valid hash pointer to the previous block, then i multicasts (,h,ρ) along with all the corresponding signatures to all parties in . 6. Each Pi ∈ : Upon receiving any (,h,ρ) along with signatures on it from at least ⌈|BA|∕2⌉ parties from BA, create a block consisting of (,h,ρ) and the related signatures and add this block to the local (blockchain) ledger state as the current slot’s block and mark the current slot as completed.

Fig. 8: Block announcing protocol for Slot ρ

Using BlockAnnounce it is straightforward to build a blockchain-based ledger: In each round parties collect all valid transactions they know and execute BlockAnnounce. For completeness, we provide a description of this simple reputation-based blockchain ledger protocol in Appendix  B . Its security follows directly from the above theorem. We remark that although the above theorem is proven for static reputations and adversaries, its proof can be extended, using standard techniques, to dynamic reputation systems with epoch-resettable adversaries. This extension will also extend the corresponding PoR-based blockchain protocol to that setting.

¹⁴  For clarity in our description we will use a deterministic broadcast protocol for Broadcast, e.g., the Dolev-Strong broadcast protocol [43] for which we know the exact number of rounds. However, since our lottery will ensure honest majority in BA, using the techniques by Cohen et al.  [37, 38], we can replace the round-expensive Dolev-Strong broadcast protocol by an randomized, expected-constant round broadcast protocol for honest majorities, e.g., [63].↩

^a  As is common in blockchains assuming a compact representation of the block, e.g., a Merkle-tree will allow for more efficiency by signing just the root.↩