As discussed in the introduction, a purely PoR-based blockchain protocol can be insecure if the reputation system is inaccurate. To fortify our ledger against such a situation we do the following: In parallel to the PoR-based blockchain above, we run an independent (and potentially slower) Nakamoto-style ledger protocol. For this purpose, we have chosen to employ a iterated-BFT ledger protocol [17] based on Proof-of-Stake as our fallback. For the rest of this paper, we will thus focus analysis on Proof-of-Stake-based blockchain (in short, PoS-blockchain) but our treatment can be applied to proof-of-work or other iterated-BFT ledger protocols. As we will show, as long as the majority of the stake is in honest hands the fallback PoS blockchain will ensure that an inaccurate (or manipulated) reputation system does not result in an insecure ledger.

5.1 Choosing a Fallback Proof-of-Stake Blockchain

Proof-of-Stake (PoS) is arguably the second most popular underlying assumption for blockchains, having a plethora of works studying various aspects of its security. In particular, iterated BFT protocols based on PoS choose block creators by selecting random committees and does not require dedicated hardware for mining, which makes it close in spirit to our Proof-of-Reputation. A good candidate for our fallback chain is the popular Algorand [50]. The main reason is Algorand’s transaction finality. That is, once a transaction is considered final, it cannot be reverted except with negligible probability. This is compatible with Möbby’s own transaction finality property. The second reason is its programming language Go, which in addition to its ease of learning, compiles to C and thus can more efficiently interoperate with other languages. As we will see, we do not require the full implementation of Algorand, only its basic transaction ledger functionality. For completeness, we describe the blockchain algorithm, where blocks become part of the ledger in Algorand by the following algorithm: First, a committee of block proposers is selected via verifiable random functions (VRFs) [72] with probability according to their stake, and their blocks propagated. A second committee of block verifiers then votes on the blocks, ranking valid blocks by the lowest VRF proof. The block with the supermajority vote is then certified: to certify, a third committee of block certifiers vote on the block. If a block has supermajority, then it and transactions within it are considered final.

5.2 PoR/PoS-hybrid Design

Our PoR/PoS-hybrid design ensures the following: If the reputation system is accurate, i.e., it reflect the actual probabilities that the parties behave honestly, then our protocol will be secure and achieve the claimed efficiency. If the reputation is inaccurate and, as a result, a fork is created, but the honest majority of stake assumption holds, then parties will be able to detect the fork—and agree on this fact—within a small number of rounds. We stress that our design uses the assumptions in a tired manner: as long as the reputation system is accurate, the backup blockchain can neither yield false detection positives nor slow down the progress of the PoR-blockchain, even if the majority stake in the system has shifted to malicious parties (in which case the back-up PoS-blockchain might fork). However, if both accuracy of reputation and honest majority of stake fail, the security of the system cannot be guaranteed as with any construction based on assumptions.

---

---

A high level description of the PoR/PoS hybrid protocol is given in Fig.  9 . Here is how our hybrid ledger works: In every round the reputation parties post to the backup PoS-blockchain, the current slot’s hash pointers. This way every party will be able to efficiently verify their local view by comparing their local hashes to the ones posted on the backup blockchain. If any honest party observes a discrepancy, then she can complain by posting the block in his local PoR-chain, which is inconsistent with the pointer seen on the backup PoS-blockchain, along with the supporting set of signatures. We refer to this complaint as an accusation and to the party that posts it as an accuser. If the accuser fails to present a valid view (i.e., a block with sufficient signatures from the corresponding slot committee) then the accusation is considered invalid and the dispute is resolved in favor of the reputation party that had initially posted the disputed hash pointer, hereafter referred to as the accused party. Otherwise, the accused party will need to respond by posting (as a transaction on the backup PoS-blockchain) his own view of the disputed block. If this party fails, then the dispute is considered resolved in favor of the accuser. Otherwise, if both the accuser and the accused party post support on their claims, every party will be able to observe this fact and detect that the PoR-chain forked. In either case, any such accusation will result in detecting a malicious party: either the accuser, or the accused or some party that issued conflicting signatures on the PoR blockchain. (The detected party’s reputation will be then reduced to 0 and the party will be excluded from the protocol.) The following theorem says that the reputation system is accurate if it reflects, within a negligible error the actual probabilities that the reputation parties are honest (proof in Appendix):

Note that since all honest (non-reputation) parties are connected with the reputation parties via a diffusion network, all that above guarantees will also be offered to them with a delay equal to the maximum delay for any message from a reputation party to reach a non-reputation party in the network.

Detecting Liveness Attacks The above design detects safety violations, i.e., forks, but does not detect the following attack on liveness: A flawed reputation system might allow the attacker controlling a majority of slot committee members to prevent the blockchain from advancing, by not issuing a block signed with sufficiently many signatures. Nonetheless, a mild additional assumption on the accuracy of the reputation system, i.e., that within a polylogarithmic number of rounds an honest-majority committee will be elected, allows to break this deadlock and detect such an attack. In a nutshell, to make sure the above attack to liveness is exposed we employ the following mechanism: In every round, if a reputation party does not receive any block with majority support from the current committee in the last round of BlockAnnounce, then it issues a complaint on the fallback chain. If for any upcoming round ρ there have been complaints posted on the main chain by a majority of the members of BA corresponding to round ρ, then the parties decide that the PoR-blockchain has halted. This ensure that at the latest when the next honest majority committee is elected, the above liveness attack will be exposed. We refer to Sec.  5.4 for a more detailed discussion.

5.3 PoR/PoS Hybrid Protocol

Figure  B describes our PoR/PoS-Hybrid Blockchain Protocol for static reputation.

---

---

5.4 Countering Liveness Attacks

Our safety-violation detection mechanism does not prevent the following attack on liveness in the fallback case: A flawed reputation system might allow the attacker controlling a majority of round committees to prevent the blockchain from advancing, by not issuing a block signed with sufficiently many signatures.

We remark that in order to attack liveness as above, the adversary will need to allow no honest reputation party to learn the contents of the current block, as otherwise that honest party will diffuse it to their network and therefore, (1) every reputation party will learn it within one round—since they are connected by a direct channels— and (2) every party will adopt it in time Δ_max + Δ_round, where Δ_max is the maximum delay for any message from a reputation party to reach a non-reputation party in the network and Δ_round is the round duration/time-out.

To make sure the above attack to liveness is exposed we employ the following mechanism: In every round, if a reputation party does not receive any block with majority support from the current committee in the last round of BlockAnnounce, then it issues a complaint on the fallback chain. If for any upcoming round ρ there have been complaints posted on the main chain by a majority in ρ, then the parties detect the halt (and, as above, an external protocol for recalibrating reputations can be employed).

The above mechanism ensures that under a very weak assumption on the accuracy of the reputation system, i.e., that an honest-majority committee is elected within a polylogarithmic number of rounds, any such halt will be detected by the system. Note that as long as the reputation is accurate, the fallback chain will never induce such a detection, as all committees will have honest majority and therefore no honest party complains. Note, also, that our lottery will satisfy the above assumption under very realistic assumptions on the the reputation, e.g., that a constant fraction of the reputations in each of the the high tiers is correct. We refer to the full version of this work for a detailed treatment.

Notwithstanding, the above mechanism does not prevent the following attack on liveness: A flawed reputation system might allow the attacker controlling a majority of slot committee members to prevent the blockchain from advancing, by not issuing a block signed with sufficiently many signatures. Nonetheless, a very mild assumption on the accuracy reputation allows to break this deadlock and detect such an attack. In a nutshell, to make sure the above attack to liveness is exposed we employ the following mechanism: In every round, if a reputation party does not receive any block with majority support from the current committee in the last round of BlockAnnounce, then it issues a complaint on the fallback chain. If for any upcoming round ρ there have been complaints posted on the main chain by a majority of the members in ρ, then the parties detect the halt (and, as above, an external protocol for recalibrating reputations can be employed). This ensure that at the latest when the next honest majority committee is elected, the above liveness attack will be exposed.

5.5 Reboostrapping from PoS

Our above hybrid design ensures that if any of the two independent assumptions—i.e., quality/accuracy of the reputation system and honest majority of stake—holds, then no fork will settle on the distributed ledger—i.e., any fork will be quickly detected. This will be guaranteed by our protocol. This property suffices to ensure that the system does not preserve deep forks, which in case of cryptocurrencies can lead to double spending. Additionally, we can even add support for recovery, not just detection, as follows: If malfunction of the PoR-blockchain is confirmed, then, as long as the majority of the stake is in honest hands, the parties will be able to will be able to reinitialize the reputation system (see Section  6 ) and restart the PoR-blockchain from the point before the detected misbehavior.

^a  Note that for simplicity we will separate the staking keys from the reputation keys. In reality, a reputation party can use its staking key as its reputation key.↩

^b  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.↩

^c  Note that the slot in the PoS chain might be different than the slot in the PoR-chain. To make this distinction explicit we will refer to the former as a PoS-slot and to the latter as a PoR-slot↩