Our ledger protocol is among a set of parties = {P₁,…,P_n}. A subset of the parties, called reputation parties, have a distinguished role in the protocol, and are tasked with proposing and confirming blocks to be added in the blockchain. To avoid overcomplicating our description, we describe our protocol here for a static set of parties; in the appendix we discuss how this set can be dynamically updatable, similar to the dynamic participation of [65, 16]. As is common in the blockchain literature, our statements are in the random oracle model, where a hash function is assumed to behave as a random function. As a setup, we assume that all parties have the genesis block which includes sufficient initial randomness and the reference reputation-system. In terms of cryptographic assumptions we will assume existentially unforgeable digital signatures [51] along with pseudorandom function. Efficient (and even post-quantum) variants of these primitives are known to exist under standard complexity assumptions, namely, existence of one-way functions or hardness of lattice problems.

2.1 Communication and Synchrony.

We assume synchronous communication, where messages sent by honest parties in some round are delivered by the beginning of the following round, and a rushing adversary [32]. The protocol timeline which is divided into slots, where each slot consists of a fixed number of rounds. An epoch consist of a predefined number of slots. We assume a cryptographic adversary who gets to actively corrupt parties—i.e., takes full control over them.

Parties have two means of communicating. (1) A diffusion (multicast) network available to everyone in , build by means of a standard flooding/gossiping protocol over a (potentially incomplete but) connected communication graph of unicast channels [18]—this is similar to [74, 18], Ethereum [30], Cardano/Ouroboros [65, 16], Algorand [49], Thunderella [79], etc. For simplicity, we abstract this network by means of a zero-delay multi-cast primitive (cf [18]): When an honest party multicasts a message, this message is delivered to all (honest) parties in the network by the beginning of the following round.² We note that one can use techniques from the blockchain literature [16, 49, 49] to relax this perfect synchrony assumption—at the cost of a stricter feasibility condition on the reputation system. A discussion of such a relaxation is included in the appendix. (2) The second type of communication is among reputation parties. These parties have known physical identities (e.g., IP addresses) and can communicate through direct channels, without flooding (e.g., via TCP/IP). We remark that existence of such channels is not necessary for our security analysis—if they are there, they can be used otherwise, communication via the diffusion network is sufficient for security. However, if they do exist and are used then can considerably reduce the traffic and yield a more scalable/efficient solution, as discussed in the introduction.

2.2 Reputation Systems.

A reputation system Rep for m = O(k) reputation parties from a set = {₁,…,_m} is a family of probability distributions (parameterized by m) over binary reputation vectors of length m, i.e., vectors of the type (h₁,…,h_m) ∈{0,1}^m.³ Each h_i is an indicator bit which takes the value 1 if _i is honest and 0, otherwise. For example, Pr[(h₁,…,h_m) = (0,…,0,1)] = 0.6 means that with probability 0.6 every reputation party except _m is dishonest. We consider two types of reputation systems: A static reputation system is a probability distribution as discussed above. This is similar to the reputation system considered in [13]. A dynamic reputation system instead is a sequence (ensemble) Rep = {Rep_ρ}_ρ∈ℕ of distributions, where each Rep_ρ is a static reputation system for a set _ρ of m_ρ ∈ ℕ reputation parties. Such dynamic reputation systems are useful in an evolving and reactive primitive such as a ledger protocol, where the reputation of parties might change depending on their behavior in the system and/or other exogenous factors.

We focus on the setting where each h_i corresponds to the output of an independent indicator random variable H_i, i.e., whether or not a reputation party _i behaves honestly does not depend on what other reputation parties do. In this case, a static reputation system can be described by a vector of m numbers between 0 and 1, i.e., Rep = (R₁,…,R_m) ∈ [0,1]^m, where the interpretation of Rep is that with probability equal to R_i the party _i will play honestly (i.e., Pr[H_i = 1] = R_i).⁴ We then say that R_i is the reputation of party _i. We refer to such a reputation system as a correlation-free reputation system. In the following we provide more details of the corruption capabilities that a correlation-free reputation system (static or dynamic) gives to the adversary.

The adversary’s corruption capabilities are specified by the reputation system. A static reputation-bounded adversary for reputation system Rep, also referred to as a static Rep-adversary, corrupts the set of parties at the beginning of the protocol according to Rep, and sticks to this choice. In particular, given a reputation system Rep for m reputation parties, corruption with a static adversary occurs as follows: A vector (h₁,…,h_m) ∈{0,1}^m is sampled according to the distribution defined in Rep, and for each h_i = 0 the reputation party _i ∈ is corrupted by the adversary. For dynamic reputation systems, a stronger type of adversary, which we call epoch-resettable adversary corrupts a completely new set of parties at the beginning of each epoch, according to the reputation system at the beginning of that epoch—this is similarly to mobile adversaries [77]. Here we focus our analysis to the static case; an extension to epoch-resettable adversaries is discussed in the appendix.

2.3 Establishing and Updating the Reputation System

Möbby users will always be able to send and receive tokens without having reputation; however, only parties with non-zero reputation, who mark themselves as available will be able to participate in the PoR protocol. At initial mainnet launch, the reputation of parties is decided by the genesis block, PoR participation is restricted to core Möbby nodes, and no block reward is distributed. Taking a gradual approach to decentralization ensures the stability of our blockchain. In the decentralized phase, parties will be able to obtain initial reputation via known external reputation sources, such as known reputation aggregate sites like Yelp and Amazon. An individual party’s reputation can then increase by importing reputation from external reputation sources. This will account for a small fraction of the party’s reputation on our PoR blockchain. Moreover, a party can increase their reputation by participating correctly in the PoR protocol, or having an endorsed reputation party participate honestly in the protocol. The reputation increase from an endorsement is distributed among the endorsed party and their endorsers. Lastly, a party’s effective reputation is increased when they receive reputation endorsements from other parties.

On the other hand, parties can lose reputation by being accused with evidence of misbehaviour in the PoR or fallback PoS protocols—an example of evidence being signatures of two conflicting transaction sets in the PoR protocol. This significantly reduces the party’s reputation. A party can also lose reputation by endorsing a reputation party, who misbehaves in the PoR or PoS protocols (even if the endorser does not misbehave themselves). While the reputation penalty is less for the endorsers than the misbehaving party, this penalty incentivizes parties to only endorse parties who they trust to behave honestly and prevent attackers from taking advantage of the endorsement system. Lastly, a party’s effective reputation is decreased if they lose endorsements from other parties.

---

---

2.4 PoR-blockchain

We assume a (dynamically updatable) set of parties where a subset ⊆ of them are special parties called reputation parties. The parties wish to leverage the reputation of the reputation parties to securely maintain a ledger containing a sequence of blocks, each block containing a collection of messages that can represent arbitrary data (throughout this paper, we refer to this data as transactions).⁵

Informally, a reputation system for a party set is similar to a probabilistic adversary structure [47]: It assigns to each subset of a probability that this subset is corrupted by the adversary—we consider active, aka Byzantine, corruption. In its simplest form, which we refer to as static correlation-free, a reputation system can be described by a vector of || independent boolean random variables. The probability that the ith variable is 1 is the probability that the i-th party in —in a given canonical ordering, e.g., using the party-IDs—is honest. This is similar to independent reputation systems investigated in [13]. We also extend this notion by allowing the reputation to evolve as rounds advance, yielding a dynamic reputation system. The update happens in an epoch-based manner, where an epoch consists of a fixed number of rounds. To capture feasibility of PoR-based consensus, we introduce the notion of a feasible reputation system (cf. Definition 2) which for static reputation systems requires that there is a party-sampling algorithm, such that the probability that a super-majority of the selected parties is honest is overwhelming. (This is analogous to the feasibility condition from [13].)

Our ledger protocol proceeds in rounds. Each block is associated with a slot, where a slot lasts a predefined number of rounds. We use the reputation system as follows (we restrict the discussion here to static correlation-free reputation): The contents of the genesis block—which is assumed to be available to any party joining the protocol and includes the (initial) reputation system along with a random nonce—are hashed to generate common randomness used in the first epoch. Since every party is assumed access to the genesis block, every party can locally run a lottery which is “biased” by the parties’ reputation using these coins to choose a committee for each slot. (For dynamic reputation, the contents of an epoch are used to extracts coins for the following epoch.)

The above implicit lottery is used to elect a slot committee BAⁱ for each slot i, which is responsible for gathering all known transactions at the beginning of the slot that have not yet been inserted in the blockchain, and proposing the block corresponding to this slot along with evidence to enable all parties to agree on this block. More concretely, in every slot, every party in a random subset BCⁱ of BAⁱ pools all new and valid transactions received by the blockchain users into a set, and broadcasts this set to BAⁱ, by means of a byzantine broadcast protocol. The union of the tractions broadcasted by BCⁱ is then signed by every member of BAⁱ and circulated to the whole party set who accept it if and only if it has at least |BAⁱ|∕2 signatures from parties in BAⁱ. As long as for each of the slot committees the majority of its members is honest—a property which will be induced by an accurate and feasible reputation system—the above consensus protocol will achieve agreement on the proposed block.

Of prime importance in our construction, and a novelty of our PoR-ledger, is a mechanism which ensures an intuitive notion of inclusivity. For clarity, we focus our description and analysis on static correlation-free reputation systems. Different ways to extend our result to dynamic and correlated adversaries are discussed in the appendix. As proved in [13], for any feasible static correlation-free reputation system, the following sampler, denoted as Amax, outputs a committee with honest majority: Order the parties according to their reputation and choose a sufficient number (cf.  [13]) of reputation parties with the highest reputations. The above simple Amax algorithm is optimal (up to negligible error) for minimizing the risk of electing a dishonest-majority committee, but it suffers from the following issues: First, if some malicious party establishes (e.g., by behaving honestly) a high reputation, then this party will be included in almost every committee. Second, the approach lacks a natural fairness property which would give all parties voting power according to their reputation (even to parties with low reputation). Such a fairness property is important for sustainable decentralization, as it does not deter participation of parties with low reputation making the overall system more inclusive. ⁶ We propose and instantiate an appropriate notion of reputation fairness, termed PoR-fairness, which addresses the above concerns. The idea behind PoR-fairness is that every reputation party should get a “fair” chance to be part of each slot-i committee BAⁱ. Defining such a notion turns out to be non-trivial (cf. Section 3.1). Intuitively, a reputation-based lottery (i.e., committee selection protocol) is reputation-fair, if, (1) on average, the representation of parties on the selected committee becomes higher, the more likely those parties are to be honest (according to their reputation); (2) this representation increases as the ratio of parties with higher over parties with lower reputation increases; and (3) the probabilities of parties included in the lottery increase proportionally to their reputation. Realizing such a reputation-fair lottery also turns out to be a challenging task and a core technical contribution of our work.

2.5 Proof-of-Stake Fallback

Arguably, reputation is a subjective and manipulable resource. For instance, the way reputation of new parties is assigned might be flawed or a malicious party might act honestly to build up its reputation, and then use its earned trust to attack the system. We address this in the following way: We back our PoR-blockchain with a light-weight use of a (Proof-of-Stake) Nakamoto-style blockchain⁷ which will ensure that if the reputation system fails to provide security, this will be observed and agreed upon on the Nakamoto-chain. This ensures that reputation parties, who try to actively cheat (e.g., sign conflicting messages) or abstain to hurt liveness or safety, will be exposed on the fallback chain.

The idea for our fallback is as follows: Parties report on the fallback chain (an appropriate hash of) their view of the PoR-blockchain. If any party observes an inconsistency of this with its own view, it contest the reported view, by posting an accusation along with appropriate evidence (signatures and hash-pointers). The original reporting party is then expected to respond to this accusation by the contents and signatures of the disputed block. Once the accusation is answered, it will either expose one of the two disputing parties as a cheater, or it will expose a misbehavior on the PoR-chain (e.g., signing conflicting messages). In either case the exposed party gets its reputation zeroed out and is excluded from the system.

This fallback mechanism fortifies the security of the blockchain under an independent backup assumption, e.g., majority of honest stake. Note that the fallback blockchain is not used for communicating transactions, but only digests (hashes) of blocks from the main, reputation chain as discussed below. Furthermore, it does not need to run in a synchronized manner with the main PoR-chain. This allows a very light-weight use of the fallback chain, which as it is a black-box use, can even be outsourced to an existing Nakamoto-style chain. We refer to this type of blockchain design as a PoR/PoS-Hybrid Blockchain. We remark that the generic fallback mechanism allows to recover from safety attacks. By an additional assumption on the quality of the reputation system we can also prevent liveness attacks as discussed in Section 5.2.

⁷  As discussed above, here we focus on a proof-of-stake Nakamoto-style blockchain, e.g., [ 65 ], but our fallback uses the Nakamoto blockchain in a blackbox manner and can therefore be instantiated using any blockchain that realizes a Bitcoin-style transaction ledger [ 18 ].↩