Figure 13 describes our PoR-Blockchain Protocol for static reputation reputation

RepBC(,,Rep,Bρ-1,ρ,δ,ϵ,L = O(1)) Every party receives the genesis block which includes: an encoding of the reputation system Rep, and the public keys of all initial reputation parties. Let ρBA denote the number of (clock) rounds that each invocation of BlockAnnounce takes to complete.a Each slot in our protocol will be ρBA clock-rounds. Without loss of generalize, we assume that the protocol starts when the global clock round is 1. Extending the blockchain: In the ρth slot: 1. Let Bρ-1 denote the block adopted in the previous slot (where B0 is the genesis block): 2. The parties execute BlockAnnounce(,,Rep,Bρ-1,ρ,δ,ϵ,L) to announce and agree on the ρ-th slot block.

Fig. 13: The Reputation-based Blockchain (Static Reputation)

B.1 Proof of Theorem 3

Proof (sketch). First we observe that if the reputation system is accurate, then it reflects the probabilities that parties are not corrupted. Hence, the block announcing protocol will always select an honest-majority committee and the block supported by that committee will be added on the PoR-blockchain. Additionally, since the majority in each such committee is honest, the adversary is able to produce valid signatures from less than a 1∕2-fraction of the parties in that committee. Hence no party might see any valid conflict on the PoS chain. This proves safety. Block liveness is straightforward since in each slot the honest majority will endorse a new (potentially empty) block. Transaction liveness holds because once a transaction is heard by all honest reputation parties, it will be included in the next slot in which one of the parties in BC is honest. Since the parties in the BC are chosen randomly from an honest majority set BA, the probability that in ℓ consecutive slots’ BC there is no honest party will be 2^-ℓ|BC| .

If on the other hand the reputation system is inaccurate, then we show that no fork can be sustained for more than 2k blocks of the backup PoS-blockchain, as long as the majority of stake is in honest hands. Indeed, assume that the PoR-chain forks at some point (i.e., safety is violated). This means that there are two honest reputation parties _i and _j who see PoR chains that fork on, say, the q-th block of the PoR-chain. The honest majority of stake ensures [39, 16] that within k blocks, from the round when the q-th PoR-block was created, there will be a block contributed to the PoS-chain by an honest party, say P. This party’s block will have to support the view of at most one of _i or _j (whichever is on P’s view of the PoR-blockchain). Once this block settles, i.e., enters the common prefix [48, 16]—this happens within in at most 2k blocks from round q [16]—it will be seen by both _i and _j and will trigger a dispute. At this point, the party in {_i,_j} who sees his view being disputed will broadcast the block in support of his view. By the transaction liveness of the PoS-chain, this block will be added to the state of the PoS chain within k blocks and will be seen by everyone within another 2k blocks. Hence, within 4k blocks the fork will be publicly detected.

^a  Recall that for simplicity we describe the protocol with deterministic Byzantine Agreement; using the techniques from [37] we can extend our treatment to use randomized—and more round-efficient—protocols.↩