Rethinking Collaborative Trust for Verifiably Decentralized Blockchain Systems Yunqi Zhang and Shaileshh Bojja Venkatakrishnan
arXiv:2606.29826v1 [cs.CR] 29 Jun 2026
The Ohio State University {zhang.8678, bojjavenkatakrishnan.2}@osu.edu
Abstract. Despite the promise of decentralization, measurement studies have identified a conspicuous lack of decentralization in blockchains. Centralization has been observed in almost all layers of the blockchain, in decentralized applications, and in decentralized autonomous organizations. In many cases, it is practically impossible to definitively determine the extent of centralization in the system. While multiple works have proposed methods to decrease centralization, by and large blockchains continue to be significantly centralized. In this paper, we develop a general framework for building verifiably decentralized blockchain systems. Our framework is motivated by the core observation that the richness and diversity of collaborative interactions between users—rather than resource uniformity—captures the essence and extent of decentralization in a blockchain system. Existing blockchains do not have any incentive mechanisms to encourage intercoalition collaboration, which directly contributes to centralization. We propose a novel reward design that incentivizes users to collaborate with other users without forming isolated coalitions. Technically, our method uses a Sybil-resistant asymmetric Shapley value for reward attribution within a collaboration group, and the theory of expander graphs for measuring and enforcing decentralization. Our framework is general and can be adapted to alleviate centralization in any layer, application, or decentralized organization. It also has important implications beyond the topic of centralization. For example, we show that our solution can naturally address the blockchain scalability problem. We also identify a new class of decentralized collaborative applications that have hitherto been unexplored in blockchains.
1
Introduction
In its more than 15 years of existence, blockchains have matured significantly as a flexible, open, transparent, and secure platform for hosting a wide array of decentralized applications [75]. Compared to the first blockchain—Bitcoin— today’s blockchains excel at achieving superior transaction throughput, lower confirmation latency, support for diverse applications, more efficient resource consumption and sharing, and improved community governance. This has been possible in large part due to the intensive research from both academia and the industry, which has resulted in innovations in new consensus protocols, layer-2
scaling methods, cryptography, incentive design, networking, and beyond [53,30]. Today blockchains have a market capitalization exceeding 2 trillion dollars, and millions of daily users worldwide. Despite the stellar progress, blockchains remain a niche technology enthusiastically adopted by a small section of the consumer population and mostly ignored by the rest [6]. The reasons for this behavior are complex and multifaceted; the poor scalability of blockchains is often cited as one of the main technological reasons for its practical limitations. However, in many blockchains adoption remains poor (relative to centralized counterparts) even after significantly improving scalability, cost, and performance efficiency [15]. A noteworthy example is from the domain of decentralized physical infrastructure networks (DePINs). Due to its crowd-sourced design, many DePINs provide resources— including essential resources such as compute, storage, network, etc.—to endusers at a cost that is a fraction (e.g., 1/10-th) of the cost of the same resource from a centralized provider [95]. And yet, it is the centralized services that enjoy the larger user base across the board and by far [8]. In addition to protocol improvements, the blockchain industry has also innovated on novel applications. E.g., due to the growing demand for AI, in recent years a number of blockchains have focused (or, in some cases, pivoted to) on providing decentralized AI services. Time and again such innovations are touted as the next “killer app” for blockchains. Whether true or not, the remarks seem to suggest that perhaps a “killer app” for blockchains does not exist as of yet [12,4,3]. In this paper we present a novel blockchain incentive paradigm that enables new types of decentralized applications while improving existing applications. At the heart of our proposal is a fundamental redefinition of what “decentralization” means in blockchains. It is widely accepted that blockchains are transparent, secure, and decentralized. Transparency is by design: all blocks are publicly visible and can be verified by anyone. Many blockchains also provide strong mathematical guarantees for the security of their systems. However, the third property—decentralization—is tricky to verify or provide guarantees for. It is fundamentally challenging (and practically impossible) to verify whether a group of nodes is colluding. This is true even if there are strong signals indicative of decentralization such as: the network is open and permissionless, there are thousands of worldwide nodes running on independent infrastructure providers, key governance decisions are made democratically, the amount of resource (such as stake) owned by any one node is a tiny fraction of the overall resources available on the chain, historical measurements show a lack of distinct clusters on the network topology, and there are no catastrophic chain reversal or other fatal attacks. Therefore, decentralization in blockchains today is really more of a commonly held belief (or, not!) than a verifiable property. In blockchains, collusion is often viewed as an undesirable behavior that enables attacks detrimental to chain security [1]. Collusions are also at the heart of why blockchains become centralized. We focus on a particularly important type of a collusion in which a coalition of nodes—over time—pool their resources, actively collaborate, improve service efficiency, and slowly dominate the market2
place (e.g., the block mining market) making it difficult for smaller players with fewer resources to compete. We claim that this commonplace phenomenon— which we term ossification—is a dominant factor in determining how decentralized a blockchain is. Ossification is rampant in today’s blockchains. A familiar example is the emergence of mining pools, wherein nodes have an incentive to join a pool and lower reward variance rather than operate alone. Ossification is beneficial for an economy outside of blockchains. It is the process by which centralized organizations form partnerships, invest in the partnerships, and over time grow to become industry behemoths. To ossify is the natural driving force in an economy. It leads to streamlining of processes, improving efficiency, leveraging the economy of scale and network effects to provide services (or, goods) at a lower cost. However, in blockchains ossification is a centralizing force that must be resisted. Unfortunately, today’s blockchains have no mechanisms to resist ossification and have largely succumbed to the ossifying forces across the protocol stack. We define a decentralized system as a system where there is no incentive for any subset of nodes to ossify. To make a blockchain system ossificationresistant requires new incentive mechanisms beyond what is available in existing blockchains. We propose a novel reward mechanism in which nodes are rewarded for collaboratively performing tasks (such as mining a block, or providing an application’s service) with a diverse set of users. The reward mechanism is Sybil resistant: a party cannot pretend to collaborate with others when it is really just collaborating with itself. Importantly, our mechanism encourages collaboration with diverse entities over time while penalizing static collusion sets. By defining collaborations as a rooted directed acyclic graph (DAG), we compute rewards as an asymmetric Shapley value with carefully chosen DAG-dependent weights to provide Sybil resistance. Unlike existing blockchains where collaborations (e.g., committee assignments) are algorithmically computed, we leave the choice of collaboration and collaborators as a subjective decision made solely by the users. Any faults in the provided service leads to the slashing of only the collaboration initiator and not the individual collaborators. The implications of our mechanism design are many. It is naturally ossificationresistant as a group of nodes that consistently collaborate only with each other and not with other nodes will be penalized. Without ossification, even small players (e.g., nodes with a relatively low stake) can compete by forming collaborations with other nodes. Moreover, it is in the interest of the nodes to be as inclusive as possible in their collaborations. Instead of an economy of competition which leads to centralization, we can have an economy of inclusiveness, collaboration, and community. Forbidding ossification does not mean innovation and efficiency within the system would stagnate. Nodes still compete with each other which encourages innovation, except now all the other nodes are also involved in the competition via collaborations. However, we highlight that there are important differences in the type of services suitable for an unossified economy compared to an ossified one. In a successful ossified coalition, participants have deep-rooted trust rela3
tionships with each other, lower communication barriers, and highly optimized service methods developed from years of experience in the domain. Conversely, services where efficiency, quality or cost is important may even require ossification. Such services, we claim, are therefore unsuitable for implementation on blockchains. E.g., a cloud service implemented on a blockchain will not be able to match the efficiency of centralized cloud providers, unless there is some ossification in the blockchain itself (e.g., in a layer-2 used by the service). A caveat is such services can still be suitable for blockchains if the primary value comes not from the efficiency of the service but from transparency, security, and decentralization of the service. That is to say, e.g., if a less efficient but transparent, secure, and decentralized cloud is valuable for certain use cases it may well be implemented on a blockchain. On the other hand, services where the human qualities of trust, creativity, relationship and connection, common sense, intelligence, morality and ethics, empathy etc.—to name a few—are important can benefit from implementation on an unossified blockchain. E.g., a service where users can query, interact, or obtain services from coalitions of experts around the world in a certain domain can benefit as a blockchain application.1 As a simple example, we can have a service where patients interact with and obtain wholistic advice from a collaborative group of doctors from various specialties, rather than having to interact with one doctor at a time through time-consuming referrals. As before, such services can be implemented in an ossified manner as well. But an unossified service offers unique properties such as lower subjective bias, a higher trust and radical creativity, which are hard to achieve in an entrenched centralized organization. For instance, many Web-2 platforms exist today that allow end users to connect with and obtain services from domain experts.2 But such interactions are often with individual experts or an ossified team of experts, and seldom with a “random sample” of experts. This is because a centralized platform provides no incentives for experts to collaborate with a diverse set of other experts. We note that the type of services we claim as being suitable for blockchains are not necessarily new—many social network blockchains already exist today; trusted execution services have been the hallmark of blockchains since the beginning; many blockchains and dapps exist for purchasing creative digital media or art. However, even if the application is not new, our anti-ossification incentives can create a fundamentally different incentive structure for collaborating service providers and consequently a rich, human service experience for its end-users. A secondary benefit of our proposed design, is that it naturally solves the scalability problem of blockchains. By collaboratively creating a block, a group of miners can process a much greater number of transactions compared to publishing the blocks solo. The design that emerges is different from existing scaling solutions like sharding, or DAG-consensus methods. In sharding too a group of miners (from different shards) process transactions in parallel to increase 1
The word expert is used loosely to mean a person or an organization that is skilled at providing a certain type of good or service. 2 Examples include Amazon, Fiverr, tele-health platforms etc.
4
throughput. However, a miner is algorithmically assigned to a shard which creates a forced collaboration. E.g., a miner that has previously misbehaved (and, perhaps slashed as a result) can continue to be assigned to shards if it has sufficient stake. This creates a situation where honest miners are forced to collaborate with a known miscreant. In contrast, miners subjectively choose their collaborators in our proposed design. A known miscreant node is unlikely to be voluntarily chosen for a collaboration by an honest node. Changing identity by adopting a fresh public key and transferring stake does not help the miscreant. Our proposed method assigns an importance score to each public key. The importance is a measure of how much a node has collaborated with a diverse set of nodes in the past. Unlike tokens, importance is algorithmically earned over time and cannot be transferred between accounts easily. A miner can, among other factors, consider the importance of a node while choosing collaborators to avoid miscreants. Similar to sharding, in our proposed method a resource constrained node can verify the full blockchain only with the help of other collaborators or more capable nodes. It is also possible to reduce the confirmation latency of transactions. By letting nodes work in coalition groups, we can effectively reduce the number of votes necessary to confirm transactions, thus improving latency. In summary, we make the following contributions in this paper: 1. We propose a fundamental redefinition of decentralization in blockchains as the extent of collaborative interaction that happens between diverse sets of users in the network, regardless of how skewed resources are distributed across the users. 2. Using block proposal as a concrete example, we provide an incentive mechanism that encourages decentralization. Under this scheme, we show that nodes do not have an incentive to form coalitions. 3. We show how blockchain scalability can be improved naturally using our proposed framework. 4. We provide discussions on extending our framework to other applications, such as decentralized autonomous organizations and smart contracts.
2
Centralization in Blockchains
Centralization is a property of the state of a blockchain system at a particular instant in time. It refers to the concentration of a resource essential for system operation—such as wealth, network infrastructure, or voting power—on the hands of a small number of users. A number of measurement studies have identified centralization occurring in multiple layers of the protocol stack of Bitcoin and other blockchains [85,52,83,23,26,51,26]. These layers include, but are not limited to, consensus [68,26,62], network [76,91,82,47,19], wealth [37,44], governance [24,60,21], geography [70,65], exchanges [29], and equipment [38,56,81,43]. The prevailing sentiments about centralization in blockchains are: (1) centralization is undesirable as it does not align with the core ethos of blockchains, (2) centralization eases the possibility of collusion attacks thereby weakening security, and (3) centralization may not be completely avoidable. For example, 5
in Kwon et al. [66], the authors define a mathematical notion of decentralization based on how evenly resource is distributed across the users. They state that collusion attacks are more difficult if the resource power is more evenly distributed. A key result of the paper is that a fully decentralized system is impossible when there is no “Sybil cost”, i.e., when there is no extra cost for Sybil users to operate additional nodes. The paper argues that public blockchains today do not have a Sybil cost, and therefore are susceptible to centralization. The problem of how to achieve a positive Sybil cost without relying on a trusted-third party for identity management is left as an open question. To remedy the centralization problem, researchers have proposed many techniques such as using a non-linear function (e.g., square root of stake) for computing voting power [74], ASIC-resistant hash functions in proof-of-work chains [36], quadratic voting in DAOs [40], and reward sharing schemes for fair formation of stake pools [32]. In a way, all of these methods are techniques by which the symptoms of centralization can be managed. In this paper, we take a complementary approach to centralization prevention. We identify the core root-cause process by which centralization occurs, and propose mechanisms to stop the process. At any given time instant, a blockchain may be centralized due to multiple reasons: (1) the network could have strong centralization at genesis, which carries over through time; (2) entities external to the network (e.g., the government, law enforcement agencies, or a major ISP) may force certain users to have a disproportionately high (or, low) amount of resources and create centralization; (3) centralization can happen because economically it is the “best” strategy for the users. The first two reasons are beyond our control. We focus on the third case.
2.1
Centralization via Ossification
In a free market, the objective of any seller is to provide a good or service of the highest quality at the cheapest possible price.3 Achieving a high product quality at a low price is challenging: it requires the manufacturing or the service process to be as efficient as possible which occurs when the seller invests money, time, and effort into optimizing the manufacturing or service pipeline. In many cases, providing competitive service is only possible through a coalition of sellers rather than by an individual.4 A coalition may be preferred if the service requires a diverse set of skills or expertise from different domains, which may be difficult for a single individual to have. A coalition may also be preferred to increase profits through economy of scale or reduce loss through risk pooling. As with individual sellers, to improve service efficiency in a coalition its members invest 3
Technically the objective of a seller is to maximize profits, which can be done by improving product quality while reducing cost. 4 We use the word seller as a general term to mean members of the service providing coalition.
6
capital, time, and effort.5 Today’s markets are full of coalitions, in the form of partnerships, companies, corporations, and cooperatives. We identify three essential properties of coalitions in free markets (and in many mixed markets existing today). Property 1. The coalition forms because a coalition is necessary to provide a competitive service in the market and/or due to economic factors. The coalition may upsize or downsize in reaction to market changes. Property 2. Members of the coalition collaborate over time pooling effort and capital to increase service efficiency and product value. Property 3. Members of the coalition rarely collaborate with competing coalitions in the market for providing service. This process by which coalitions form and are sustained represents a key centralizing force in today’s economy. Smaller coalitions can also be present internally within a larger coalition. E.g., a large company which is itself a coalition may internally consist of smaller coalitions in the form of divisions or departments. However, in this case the smaller coalitions arise not due to market competition but due to the internal organization and division of labor of the larger company. Furthermore, there is typically at least some (if not, a lot of) collaboration between the smaller coalitions (divisions) in such a case. Therefore, Property 3 above is not true for these coalitions. We are primarily interested in coalitions that arise due to market forces, and which satisfy the Properties 1, 2, and 3. We use the term ossification to denote the process by which competing coalitions form in a market (Fig. 1).6 Definition 1. Ossification is the process by which a coalition forms and is sustained in a market while satisfying Properties 1, 2, and 3. The word ossification is justified because members of a coalition develop strong trust relationships with each other over time as they collaborate to compete in the market. Internal processes, communication pathways, overheads etc. are streamlined, and the coalition functions as a well-oiled machine. The strong collaboration among members over a long time leads to highly efficient products or services (extremely high quality at low cost), that is difficult to match by other smaller coalitions or coalitions that have not been around for as long. Many of the services and products that we enjoy today—smartphones, cloud services, healthcare facilities, supermarkets, airplanes etc.—are all the result of ossified coalitions. One could argue that ossification is, in fact, necessary to some extent to achieve the level of expertise needed to develop a complex service or product (such as the smartphone, or the cloud). 5
Capital can also come from external sources (e.g., investors). Similarly, service can involve effort from external bodies (e.g., contractors). We do not consider these as part of the coalition. 6 The term is inspired by network ossification, which denotes the slow rigidification of the Internet architecture and protocols.
7
time
time
Fig. 1: Sellers in a market have a natural tendency to ossify over time due to economic forces. Each blue dot represents a seller. The red clusters represent coalitions formed due to ossification.
Ossification is generally viewed as a favorable process, so long as it does not lead to monopolies and done in the interest of consumers. However, ossification has some drawbacks as well. As members of an ossified coalition actively collaborate to provide the best possible service, they typically do not collaborate with competitors in the same market.7 At first glance, this is almost a trivial statement. Why collaborate with a rival against whom one is directly competing? From the point of view of the consumers, a collaboration between coalitions holding diverse viewpoints can potentially result in effective cross-pollination of ideas, lower bias, and produce creative breakthroughs that otherwise do not happen. In an ordinary market, the pressure on a coalition is to achieve the highest efficiency and earn the most amount of profits. This focus on a singular goal can cloud the coalition from exploring avenues that do not contribute to increasing efficiency in obvious ways. Coalitions that do focus on exploratory topics tend to be really affluent and constitute a minority. Not all products and services are a result of ossified coalitions. For example, in the movie industry (e.g., Hollywood), rarely do we see the same cast and crew collaborate over multiple projects. The creative foundations needed to make a movie are gained by encouraging collaborations between different sets of people for different movies. As in other markets, ossification happens in blockchains as well. The examples of centralization in blockchains cited at the beginning of this section—such as the formation of mining pools, or the centralization of voting power in DAOs— can be attributed directly or indirectly to ossification. It is, therefore, valuable to devise methods that discourage or eliminate ossification in blockchains.
3
Decentralization in Blockchains
The word decentralization is often used in blockchains to mean the absence of centralization. Just as centralization is a function of time and can happen due to many reasons, it follows that decentralization is also a function of time 7
Collaborations between competitors do occur on mutually beneficial issues. But even in those cases collaboration on the actual end-product on which the companies are competing is rare.
8
(a) Ossified market.
(b) Decentralized market.
Fig. 2: The collaboration graph in an ossified (left) and decentralized (right) market. Each dot is a seller, while the edges represent the presence of interaction between users. In (a), the red clusters are the ossified coalitions.
and can happen due to any of those reasons. We argue that this is not a very useful definition for decentralization. Consider a fully homogeneous proof-ofwork blockchain network in which all nodes have the exact same amount of resources and uniform all-to-all network connectivity. Suppose a fraction (say, 30%) of the nodes form a coalition and engage in selfish mining. Intuitively, the resulting network is not fully decentralized. However, by all resource measures the network appears to be fully decentralized. We conclude that an accurate definition of decentralization must consider not only the resource distribution across nodes, but also the intention of nodes to collaborate with other nodes in the network. We formalize this idea below. Consider a set of free agents in a market, where a free agent is an entity (a person, a group, or an organization) capable of making a decision of their own free will. We do not require the decisions that free agents take to be rational; but it is important that the decisions are taken by the free agents out of their own accord and not forced upon them (e.g., by a regulator, or by an algorithm in the case of blockchains). We assume agents are free to choose who they want to collaborate with—a property which we call as freedom of choice. Even if the agents can make decisions of their own, in many cases the agents don’t have freedom of choice. E.g., geopolitical reasons can prevent trade between companies in certain regions of the world; or, in a sharded blockchain the specific shard that a node is assigned to (i.e., its collaborators) is algorithmically computed and outside of the control of the node. Our definition of decentralization is applicable for free agents that have freedom of choice. Definition 2. A market with free agents having the freedom of choice is decentralized, if for any subset of free agents there is a ‘significant’ amount of collaboration between the subset and its complement. The definition naturally forbids ossified coalitions where members collaborate only with other members of the coalition, and not with others. What ‘signifi9
cant’ amount of collaboration means is application dependent. We provide a more precise definition for the block proposal application in §5. In short, we define decentralization not as the absence of centralization but as the presence of voluntary, value-adding interactions and collaborations between participants (Fig. 2). There are some similarities and differences between the old definition of decentralization and Definition 2. Similarities. Just like the old definition, our new definition is also a continuous measure of decentralization. A system can be 0% decentralized, 100% decentralized, or fall anywhere in between. Our definition is not precise and can be implemented in multiple ways in practice. In a fully decentralized market, the “collaboration graph”—computed as the pairs of free agents that have collaborated during the time horizon of interest—must look like an expander graph. If not, measuring to what extent the collaboration graph resembles an expander graph provides the extent of decentralization in the network. In certain cases, if the network is small, it is possible for each free agent to collaborate with all the other free agents within a reasonable amount of time. We do not place any constraints on the sparsity or maximum degree of the collaboration graph. Depending on the application, this constraint may be added. Differences. In the old definition, the extent of decentralization can be measured at any given time instant. In our new definition, we can measure the extent of decentralization only over a time horizon (like ossification). Our definition is applicable only to systems that have human (or, organizations controlled by humans) participants. We cannot use the definition for a network of machines that don’t have free will (e.g., a private blockchain managed by a single entity). Our definition is complementary to the old definition. For instance, we can consider a network where all the nodes are highly collaborative, but the resource distribution is highly non-uniform. Such a network is centralized per the old definition, but decentralized according to our definition. It is possible to develop a hybrid definition that considers both resource distribution and collaboration. However, the utility of the old definition is limited to just quantitatively measuring how resources are concentrated in the network. The definition does not naturally suggest any mechanisms by which the resource concentration can be mitigated. Definition 2, on the other hand, is more general in the sense that it not only provides a measure to quantify decentralization but also presents a natural method to prevent centralization from happening in the first place via the typical process of ossification (as we will see in the coming sections).8 The old definition is a worst-case measure. If resources are concentrated in the hands of a few, those few could attack the system, not that they would. Since we cannot predict the behavior we err on the side of caution, and require all resources to be uniformly distributed. Our definition is a typical-case measure. Even if resources are concentrated at the hands of a few, if those few are willing to collaborate with everyone in the network, we feel there is no need for worry. In the worst case, collaborations can abruptly stop and the nodes in power can turn evil. But 8
Atypical processes of centralization cannot be avoided even by our scheme.
10
in the typical case, so long as the nodes do not have an economic incentive to turn evil, we believe they will not turn evil. Discussion. An important aspect in Definition 2 is that the collaborations have to be made voluntarily by the nodes, and not forced by external factors. In other words, we observe when given a choice who the nodes choose to work with. If a certain group of nodes form a clique and choose to work only with other members of the group, we call the network as centralized. If each node voluntarily collaborates with all other nodes, we call the network as decentralized. The idea of encouraging greater collaboration to combat monopolies, encourage creativity, reduce bias, or to enforce a desired shared culture has been voiced by many experts from various disciplines in the past [2,41,16,93,45,28,10]. The focus of this paper is to formalize this idea into a mathematical framework, which can then be used for decentralizing blockchains. In the following, the word decentralization means decentralization as per Definition 2. Where there is ambiguity, we call our definition as “collaborative” decentralization and the old definition as “resource” decentralization.
4
System Model and Problem Statement
The ideas we have presented thus far are general and can be applied to any layer of the blockchain protocol stack (we hypothesize there are applications beyond blockchains as well, where this could be applied). However, for concreteness we first focus on a key application area: the consensus protocol. System model. We consider a blockchain system comprising of a set of nodes V , with n = |V |. Assuming a proof-of-stake P (PoS) system for concreteness, each node v ∈ V has a stake of sv ≥ 0 with v∈V sv = 1. Time proceeds in discrete rounds, t = 0, 1, . . ., with one block published each round. Let V [t] ∈ V be the proposer assigned to be the block publisher for round t. The probability that V [t] = v for a node v ∈ V at time t is sv . R[t] is the block proposer reward that the proposer V [t] gets at round t for publishing the block. In addition to the block proposer reward, the proposer also receives transaction fees as a reward. We do not model transaction fee rewards for the time being. A fraction of the nodes with a total stake of up to 1/3 may be malicious in the system. Each node has a public-private key pair. Digital signatures are secure. We assume the block size can be arbitrarily increased in size to accommodate any additional metadata required by a proposed algorithm, without hurting the block dissemination time. We also assume nodes have unlimited compute capacity. In later sections, we discuss the actual overhead introduced by our proposed method and discuss possible optimizations for practice. Problem statement. We seek to design a block reward computation mechanism for R[t] such that there is no incentive for ossification. That is, for any subset S ⊂ V , if the nodes in V pool their resources (stake), it must result in a lower reward for each node compared to following the protocol. In today’s blockchains, the expected reward for a node is identical whether or not it joins a 11
stake pool. It is only the variance in reward that decreases upon joining a stake pool. What we require in our problem is the expected reward for a node should be strictly lower if it joins a stake pool, compared to not joining a pool (more precisely, ossifying with a pool).
5
Block Production and Reward Mechanism
5.1
Overview
We present a method by which any PoS consensus protocol can be extended to allow a block to be jointly proposed by a subset of nodes, instead of a single node. Our extension requires a real-valued state for each node, a global state capturing the collaboration patterns between the nodes, a new field in the block header, and a modification of the block reward computation mechanism. It does not alter the core consensus protocol or diminish its security. Before a block is published, the block publisher invites other nodes of its choice to collaborate on the block publication. When the block is published, the signatures of all the collaborators are included within the block header in addition to the block proposer’s signature. We introduce a new real-valued state associated with each node called importance, that measures the amount of collaboration a node has done over time. When a node collaborates with a publisher, a part of the node’s importance goes to the publisher when the block is published. Unlike payment tokens, importance can be transferred only via collaboration and that too at a slow, fixed rate. A constant-rate “tax” on the nodes decays their importance slowly. A node can increase its importance when it is a block publisher by collaborating with other nodes. A node can also increase its importance through a “tax refund” if it is well-behaved and has suffered a loss in importance due to collaboration. The amount of importance received from the tax refund depends on the importance of the nodes it collaborates with, and the overall collaboration graph of the network. The publisher of the block receives a reward that is proportional to the total importance of all the collaborators (including the publisher) in the block. The publisher may choose to allocate a portion of this reward to its collaborators. If the block produced is incorrect, only the publisher is slashed. The collaborators do not get slashed. We explain these ideas in more detail in the following. Alternative solutions are possible by considering variations of these ideas. 5.2
Importance
Importance is a real-valued state associated with each node that tracks the extent to which the node has collaborated with other nodes. For a node v ∈ V , we let Iv [t] ≥ 0 be the importance of v at the beginning of round t. Importance is a conserved quantity. It can neither be created nor destroyed. It can only be transferred to or received from another node. 12
The collector node. In addition to the nodes V , we introduce a hypothetical node c which we call the collector. The collector node has its own associated importance Ic [t] ≥ 0 at the beginning of round t. The collector node collects a tax in importance from all the nodes at each round. For a system parameter β ∈ (0, 1), the tax collected from any node v ∈ V at round t is βIv [t]. The collector also gives importance back to the network in the form of a tax refund awarded to certain well-behaved nodes. The exact amount awarded and who it is awarded to depends on the collaboration patterns of the nodes, and will be discussed later. If a node is idle, i.e., it is not a frequent publisher (due to low stake) and it is not a frequent collaborator, the node will eventually lose all of its importance to the collector. If a group of nodes form an ossified coalition, with each node in the group only collaborating with other nodes in the group, the aggregate importance of the entire group goes to zero. We set the total amount of importance P in the network (including the collector) to 2. So, we have the invariance v∈V Iv [t] + Ic [t] = 2 for all time t ≥ 0. We also set Ic [0] = 1. 5.3
Collaboration DAG
Before a block at round t is published by V [t], the publisher negotiates with other nodes of its choice to form a collaboration set S[t] ⊆ V with V [t] ∈ S[t]. The reason it is a negotiation will be clear shortly. The collaboration set is organized as a directed acylic graph (DAG) D[t] with the vertices being the nodes in S[t] and V [t] as the root. This DAG D[t] is published in the block header at time t, including signatures of the members in S[t] attesting to the DAG structure. The block reward R[t] earned by the publisher V [t] is set as X R[t] = Iv [t](1 − β), (1) v∈D[t]
i.e., the block reward equals the total importance of the collaboration set after paying tax to the collector. The block reward is awarded only to the publisher V [t]. Each non-root node in the DAG D[t] pays an importance fee to all of its predecessors in the DAG, and receives an importance free from its successors in the DAG. For each v ∈ D[t], let Iv′ [t] be the importance of v after sending importance to its predecessors and receiving importance from its successors. We design the importance transfer mechanism such that it satisfies the following properties. Property 4 (Conservation of importance). The total importance P of the ′nodes in the DAG before and after the transfer is the same, i.e., v∈D[t] Iv [t] = P v∈D[t] Iv [t](1 − β). Therefore, a collaboration among Sybil nodes—regardless of the DAG structure— cannot increase the total amount of importance of the Sybils. Property 5 (Slow transfer of importance). For a DAG with a total stake of s and a total importance of i, the maximum amount of importance a node can receive 13
in the DAG is αis/ϵ, where ϵ is the smallest denomination of the blockchain’s native token and α ∈ (0, 1) is a system parameter governing importance transfer within the DAG (see Appendix A). Importance captures the long term collaboration behavior of a node and is, therefore, slow varying. This allows nodes to form stable collaboration relationships with peers. From a security standpoint, a slow varying importance increases the cost of certain attacks for the Sybils. E.g., if a Sybil node forges an incorrect signature during collaboration causing the publisher to get slashed, it cannot immediately assume a new identity with the same stake and importance as before. Property 6 (Fairness). Let S ⊂ D[t] be any path-closed subset of nodes containing V [t], i.e., for any u, v ∈ S and for any path from u to v in D[t], the path is contained in S. We have X X (Iv′ [t] − Iv [t](1 − β)) ≥ 0 ≥ (Iv′ [t] − Iv [t](1 − β)). (2) v∈S
v∈D[t]\S
For any node v ∈ D[t], the final importance value of v is lower bounded as Iv′ [t] ≥ Iv [t](1 − β)(1 −
α X su ). ϵ
(3)
u∈Q(v)
The closer a node is to the root of the DAG, the more importance it receives from the nodes below it. Nodes close to the sink(s) of the DAG lose importance to the nodes above them. The root of the DAG receives the most importance. Such a mechanism not only provides the root with an incentive to gather a large collaboration set, but it also gives each node of the DAG an incentive to find more collaborators of their own. Thus, the collaboration set itself can be collaboratively (and hierarchically) built, which reduces overhead on the root and allows for rapid construction of large collaboration sets. For many applications, it may suffice to just have a root and one level of child nodes below it. We use a DAG as it is general and can support a flexible range of applications. Property 7 (Sybil resistance). Consider any node v ∈ D[t]. Suppose v is replaced by any DAG A[t] with total stake sv and total importance Iv [t](1 − β). The total fraction of importance received by A[t] exceeds the fraction of importance received by v in the original DAG by a factor that is at most 1+
2 sv α2 sv 3 2 ( ϵ2 − ϵ ) + O(α ) sv
(1 − (1 − α) ϵ ))
,
(4)
which goes to 1 as α → 0. Here ‘replaced by a DAG’ means the parents of v in the original DAG have edges to all the roots of the new DAG; and the sinks of the new DAG have edges to all the children of v in the original DAG. Due to this property, a Sybil user cannot 14
a
a
b
c
b
d
c
e
e
(a)
(b)
d
Fig. 3: (a) Example of a collaboration DAG. (b) Each node in the DAG transfers a fraction of its importance to its ancestors in the DAG.
hope to game the protocol by pretending to be distinct users. There is also a social aspect to Sybil resistance. A single adversary may create multiple Sybil personalities hoping the victim trusts at least one or a few of these personalities. We do not model this attack or behavior. An honest entity can also run multiple nodes. But, the honest node would be publicly transparent about its ownership of those nodes. Importance transfer mechanism. We illustrate the importance transfer mechanism on directed trees, as it is easier to understand. The general case of importance transfer on DAGs is discussed in Appendix A (Fig. 3). Consider a directed, rooted tree D[t] with the publisher V [t] as the root. Consider any node v ∈ D[t]. The importance of v after taxation is Iv [t](1 − β). Let V [t], v1 , v2 , . . . , vk , v be the path to reach v from the root. Node v first transfers a fraction (1 − (1 − α)sV [t] /ϵ ) of its available importance to V [t]. Out of the remaining importance, it transfers a fraction (1 − (1 − α)sv1 /ϵ ) to v1 . The process repeats until v has transferred importance to all the nodes on the path V [t], v1 , . . . , vk . If α is small relative to the stake values, the quantity (1 − (1 − α)s/ϵ ) can be approximated as αs/ϵ. The above process can, therefore, be approximated as node v sending an importance of Iv [t](1 − α)αsV [t] /ϵ to node V [t], an importance of Iv [t](1 − α)αsv1 /ϵ to node v1 , Iv [t](1 − α)αsv2 /ϵ to node v2 , and so on, till node vk . Each node in the tree transfers importance this way to all of its predecessors. The root node only receives importance. In practice, for a small value of α we can use β = 100α/ϵ. Theorem 1. The importance transfer scheme satisfies Properties 4, 5, 6, and 7. (Proof in Appendix A.4). Our importance transfer is identical to an asymmetric Shapley value with the permutation weights chosen to provide Sybil resistance. For any subset S ⊆ D[t], define the utility u(S) of S as the total importance of all the nodes reachable 15
from S (including the total importance of S itself), i.e., u(S) =
X
Iv [t](1 − β).
(5)
v∈D[t]:∃u∈S such that v is reachable from u
The utility function is a monotone, submodular function and has an associated polymatroid. For any permutation (vσ(1) , vσ(2) , . . . , vσ(|D[t]|) ) of the nodes in D[t], where σ is the permutation function, the greedy solution of xvσ(i) = u({vσ(1) , vσ(2) , . . . , vσ(i) }) − u({vσ(1) , vσ(2) , . . . , vσ(i−1) }),
(6)
is a corner point on the base of the polymatroid. The standard symmetric Shapley value, in addition to being computationally expensive, does not satisfy Property 7. We, therefore, consider a non-standard asymmetric Shapley value by choosing a subset of permutation to average over instead of all possible permutations. Details are provided in Appendix A. Incentives. To maximize the block rewards, the publisher has an incentive to form and use a large collaboration set (large, in the sense of importance). The publisher may give a portion of the the block reward to itsP collaborators. E.g., for a parameter γ ∈ (0, 1) the publisher keeps IV [t] (1 − β) + v∈D[t]:v̸=V [t] Iv [t](1 − β)γ of the reward, and each node v ∈ D[t], v ̸= V [t] receives Iv [t](1 − β)(1 − γ) of reward. Other reward allocations are possible. The parameters (e.g., γ) of the reward allocation can be determined through a private negotiation between the publisher and the collaborators. During the negotiations, the publisher can also decide the exact structure of the DAG and which collaborator goes where in the DAG. It is completely up to the publisher to invite a node to be a collaborator. It is also up to the invited node whether to accept the invitation or not. A node loses a fraction β of its importance each round to taxes, regardless of whether it is part of the collaboration set or not. If the node rejects an invitation to collaborate, it loses its tax and gains no monetary reward. If the node accepts the invitation, depending on its location in the DAG it may overall lose or gain importance. However, the node can receive monetary compensation from the publisher. Thus, there is an incentive for the node to join a collaboration as it can benefit the node by increasing its importance and/or providing a monetary reward. Who a node chooses to collaborate with has important implications on the overall rewards earned by the node. E.g., if the node is going to be a publisher soon, the node may not want to spend its importance in the current round; or, if the node wants to maximize its tax refund (§5.4), But in all cases, it is detrimental to the node to not collaborate at all, or to collaborate only with a fixed, ossified coalition. Making collaborations useful. In our discussion so far, the value of collaboratively producing blocks is to prevent ossification. However, collaborators can also be tasked with doing additional useful work during the block production process such as executing transactions. We discuss how this idea can be used to scale the blockchain in §6. 16
tax fraction 𝛽
collector
tax refund
Fig. 4: A β fraction of importance is collected as tax from all the nodes at the beginning of a round. Nodes that are part of the maximal expander receive a tax refund at the end of the round, provided the total stake of the expander is at least 0.5.
5.4
Tax Refund
The collector node collects a tax each round for a few reasons: (1) it removes importance out of idle or unused nodes, (2) it forces nodes to join a collaboration, (3) it allows for the importance of an ossified coalition to go to zero, and (4) it can be used to enforce an all-to-all collaboration paradigm. We discuss the fourth point here. Tax collected by the collector is transferred back to well-behaving nodes in the form of a tax refund (otherwise, the total importance of all the nodes will go to zero). A key challenge here is in identifying which nodes are well behaved, and how much to offer in refunds to those nodes. To solve this, we consider an interaction graph G[t] for each round t. Each node v ∈ V is a vertex in G[t]. At genesis, the graph G[0] does not have any edges. At time t, the graph G[t] can be derived from G[t − 1] as follows. For any two nodes u, v ∈ V , let I(u,v) [t] be the amount of importance transferred from u to v at round t. We set I(u,v) [t] = 0 if u∈ / D[t] or v ∈ / D[t]. For any edge (u, v) ∈ G[t] and for any time t, let w(u,v) [t] be the weight of the edge (u, v) at time t in G[t]. The weight of all the edges is set to zero at genesis. Then, w(u,v) [t] = (1 − α)w(u,v) [t − 1] + αI(u,v) [t],
(7)
for all u, v ∈ D[t] and for all time t. The edge weight w(u,v) [t] is an exponentiallyweighted moving average of the importance transferred from u to v. For each node, the interaction graph measures how much importance the node has sent and received through collaborations in roughly the last 1/α rounds. Once we have G[t], we derive a maximal subgraph G′ [t] from G[t] that is an ϕexpander for a decentralization parameter ϕ. Since G′ [t] is a ϕ-expander, for any 17
subset S ⊂ G′ [t], we have P P min( (u,v)∈G[t]:u∈S,v∈V \S w(u,v) [t], (u,v)∈G[t]:u∈V \S,v∈S w(u,v) [t]) P P ≥ ϕ. min( u∈S Iu′ [t], u∈V \S Iu′ [t])
(8)
Recent works have proposed efficient near-linear time randomized expander decomposition algorithms [48,86,90,20]. If the total stake in G′ [t] is less than 50%, none of the nodes receive a tax refund at round t. If the total stake ′ of G′P [t] is greater than 50%, each node receives an importance of Pv ∈ G [t] ′ Iv [t]( v∈G′ [t] sv )α(Ic [t] + (2 − Ic [t])β)/( v∈G′ [t] Iv′ [t]) from the collector, where (Ic [t]+(2−Ic [t])β) denotes the importance of the collector after taxing the nodes at round t. Tax refunds are issued at the end of a round (Fig. 4). Rationale. The expander graph G′ [t]P(if it exists) ensures that any subset of P ′ nodes S ⊂ G [t] with v∈S Iv′ [t] ≤ 0.5 v∈G′ [t] Iv′ [t] has outgoing edges of weight P of at least ϕ v∈S Iv′ [t]. Thus, a set of malicious nodes cannot refuse to collaborate with honest nodes, without losing their importance refunds. 5.5
Analysis
Consider an ossified P set of nodes S ⊂ V . We say a collaboration between S and P V \S is ϕout -weak if (u,v):u∈S,v∈V \S w(u,v) [t] ≤ ϕout v∈S Iv′ [t] for all time t. Theorem 2 (Preventing ossification). Consider an ossified set of nodes S ⊂ V having an , ϕout -weak collaboration with V \S with ϕout < ϕ. Then, the total importance of the set S is bounded as P X 2α u∈S su P P . (9) lim sup Iu [t] ≤ β(ϵ − α u∈S su ) + α u∈S su t→∞ u∈S
(Proof in Appendix B.1). By choosing a tax rate β that is significantly larger than α (e.g., β = 100α/ϵ), we can ensure that coalitions that do not strongly collaborate with others outside the group achieve a small eventual importance. By a similar argument as above, we can show that if a set S has no collaborations with V \S, the importance of S goes to zero. P Corollary 1. For an ossified set of nodes S ⊂ V with (u,v):u∈V \S,v∈S w(u,v) [t] = P 0, we have lim supt→∞ u∈S Iu [t] = 0. We say a subset S ⊂ V achieves a strong collaboration with itself if the total P stake of S is at least 0.5, i.e., u∈S su > 0.5, and P P min( (u,v)∈G[t]:u∈S ′ ,v∈S\S ′ w(u,v) [t], (u,v)∈G[t]:u∈S\S ′ ,v∈S ′ w(u,v) [t]) P P ≥ ϕ, min( u∈S ′ Iu′ [t], u∈S\S ′ Iu′ [t]) (10) 18
for all S ′ ⊂ S and for all time t. If S has a strong collaboration internally but has a weak collaboration with V \S, then G′ [t] = S for all t and the total amount of importance in S grows to a large value. We first show the following Lemma. Lemma 1. The importance of the collector is at least 1, i.e., Ic [t] ≥ 1 ∀t > 0. (Proof in Appendix B.2). Pt ′ Let wv [t] = (1 − α)wv [t − 1] + αIv [t − 1] = t′ =0 α(1 − α)t−t Iv [t]. That is, wv [t] captures the average importance of v over the past roughly 1/α rounds. We provide a lower bound for the average importance of S in the following. Theorem 3 (Rewarding decentralization). Consider a set of nodes S ⊂ V . If (1) S has a strong collaboration with itself, (2) S has a ϕout -weak collaboration with S ′ for any S ′ ⊆ V \S, and (3) S ′ has a ϕout -weak collaboration with S for any S ′ ⊆ V \S, where ϕout < ϕ then lim inf t→∞
X
wv [t] ≥ (
v∈S
X v∈S
sv )
(2 − 4β + 6β 2 − 2β 3 ) ϕout − . 2−β β
(11)
(Proof in Appendix B.3). 5.6
Attacks
Ossification attack by inclusion. A set of malicious nodes V \S can collaborate only with a small, targetted set of victim nodes S ′ ⊂ S without collaborating with any node from S\S ′ . The idea here being if we consider the overall set S ′ ∪ (V \S), it has a poor conductance in G[t]. However, if the set S ′ has a strong conductance in G′ [t](S) (i.e., S ′ is well connected with S\S ′ ), it will still be included in the maximal expander subgraph G′ [t]. The nodes in V \S will be excluded from G′ [t]. This attack, therefore, would not work. Ossification attack by exclusion. Another attack is the nodes in V \S can collaborate only with nodes in S\S ′ , and not collaborate with any node from S ′ for a target set S ′ ⊂ S. In this case, even if G[t](S) and G[t]((S\S ′ ) ∪ (V \S)) are expanders, the overall graph G[t] may not be an expander. Therfore, it is possible that some nodes in S ′ are excluded from G′ [t] (some or all nodes in V \S may be included in G′ [t]). Suppose V \S has a total stake of 33%. For this attack to work, the target set S ′ must be sufficiently large. E.g., if S ′ contains just 1% of the stake, the overall graph G[t] might still be an expander. However, if S ′ includes, say, 33% of stake then it is possible that some nodes of S ′ are excluded from G′ [t]. We believe the solution to this attack is sociological, rather than algorithmic. When a collaboration rift between two (or, more) factions is detected in the network, it is in the interest of the neutral set of nodes (S\S ′ ) to ensure that the stake of the maximal expander in G[t] does not drop below 50%. Moreover, the presence of non-collaborating factions increases the centralization of the network which ultimately diminishes the value of the blockchain to end users. Keeping these considerations in mind, the neutral set of nodes can decide 19
on an appropriate collaboration strategy for the network, such as (1) encouraging the factions to collaborate with each other, or be isolated, (2) choose one of the factions and increase collaborations with them while reducing collaborations with the other. Betrayal attack. An attacker can pretend to be a trustworthy node(s) and collaborate with a large fraction of the honest nodes. Eventually, the attacker deliberately includes an illegal operation in a block of an honest publisher (e.g., invalid signature) with whom the attacker is collaborating and causes the publisher to get slashed. The attacker than attempts to create a new public key identity, and transfers all of its stake to it. The attacker then tries to rejoin the network as a new person. However, unlike stake, transferring importance (1) takes time, and (2) cannot be anonymized (i.e., no anonymous mixers are available for importance transfer). Therefore, the network can easily know the new identities the attacker is trying to take and blacklist them too. Edge weight amplification attack. The weight w(u,v) [t] of an edge (u, v) ∈ G[t] has memory of past importance transfers from u to v. Suppose the nodes v, v1 , v2 , . . . , vk are all controlled by the attacker. From v, the attacker can transfer i amount of importance to v1 which can then send the importance back to v. Node v can then send this importance to v2 which, once again, can send the importance back to v, and so on. If the memory of edge weights is long, it would appear as if node v has transferred a net of ki importance to other nodes, when, in fact, it is the same pot of importance that is being sent back and forth. If honest nodes do not engage in this behavior, the edge weights of the outgoing edges from the attacker nodes can be severely inflated in value giving the attackers an unfair advantage. However, in our proposed solution the rate at which the edge weight memory decays (i.e., α) is exactly the same as the rate at which a node can transfer its importance to another node. Therefore, by the time it takes for node v to substantially transfer its importance to node v1 , the memory of the previous transfer that node v made of the same importance decays down to zero in the edge weight. We leave a rigorous analysis of these attacks to future work. Namesake collaboration. Nodes can form coalitions (pools) with each pool having a leader. Nodes retain their stake and importance and do not transfer them to their pool leader. The pool leaders negotiate collaboration agreements with each other on behalf of their pool members. Pool leaders may also do the bulk of the actual collaboration work (e.g., transaction execution), requesting their members only for a signature at the end. Members transfer a portion of their reward to the pool leader. In this case, the true trust relationships exist only between the pool leaders, and between a pool leader and its pool members, even if the collaboration graph G[t] looks like an expander. However, a pool member that is capable of doing the computational work by itself can bypass its pool leader and engage in the collaboration by itself, thus avoiding the pool leader fees. To prevent “lazy” pool members from delegating the collaboration process to their pool leaders, a stronger collaboration verification system beyond just signatures may be necessary. 20
6
Scaling Blockchain Performance
Collaborations in a decentralized blockchain can be used to scale the performance of the blockchain. In the following we outline a method for scaling throughput; as before, other solutions are possible. Our method is inspired by blockchain sharding, but has subtle differences. We partition the public key address space into k tracks, for a global parameter k ∈ N, k > 0. The parameter k can be increased or decreased as needed by the network. A node in the network, depending on its capacity, stores the states and processes transactions from only a small number (e.g., 1) of tracks. A node is free to choose which track(s) it desires to operate on. There is a single global blockchain (unlike sharding), with blocks published by proposers following a PoS protocol. A block proposer collaborates with other nodes operating in different tracks to collaboratively build a block. Each block has a sequence of transactions, where a transaction can be from any track. Note that publishers are not required to collaborate or include transactions from all tracks, though it is in their interest to do them. Cross-track transactions are divided into multiple single track transactions (e.g., with the help of bridge addresses). All component transactions of a cross-track transaction are included and executed within the same block. Nodes operating in a track are connected to other nodes in the track through a p2p network. After a block is prepared, a collaborator node collects transactions in the block that belong to its track and broadcasts them in its network. The block proposer is slashed if the block contains an invalid transaction or execution. If a node does not have the capacity to store data from all tracks, it can verify the correctness of a block only with the help of collaborating nodes from other tracks. Depending on the number of tracks and size of collaborations desired, the throughput of the blockchain can be significantly increased. Our solution can be likened to a multi-threaded execution model, where each collaborator processes a single (or, a few) thread (track) within a block. A fundamental problem in blockchain sharding is how to avoid a (super)majority of validators in a shard from being adversarial. Common solutions to this problem include frequently and randomly re-assigning nodes to different shards; and, hiding the identity of the nodes until after they have proposed their block [35]. In our proposed solution, as long as there is at least one collaboration of nodes that are all honest and which collectively operate on all tracks, any invalid transaction or execution in any of the tracks can be caught and the publisher of that block can be slashed. Another fundamental problem in sharding is ensure atomicity of cross-shard transactions. In our solution, cross-track transactions are executed on a single block providing atomicity. The mechanisms needed to prevent ossification as outlined in §5 are necessary for the scaling method in this section to work. If blocks are allowed to be collaboratively built without the mechanisms of §5, a node would be incentivized to join an ossified pool. This increases the amount of ossification in the network making the system centralized. 21
7
Interactive Decentralized Applications
A blockchain is inherently a collaborative application as proposers collaboratively build a ledger of transactions. However, the amount of interaction that happens among the nodes during this collaboration is poor. A block is constructed by a node independently without any interaction with the other nodes. After the block is constructed it is broadcast to the network. As a stylized example, if there were a network switch available to which all nodes are connected, then a node would only ever need to interact and address messages to this network switch for broadcast. In contrast, collaborations in an ossified coalition often involve a significant amount of direct peer-to-peer and group interactions. Our model of a decentralized blockchain allows for interactive applications in a natural way. Consider a decentralized blockchain comprising of free agents with each free agent having certain resources (e.g., compute). When free agents collaborate, they pool their resources and interact to provide a service. Any service that can be provided collaboratively by free agents, and which can be verified by collaborations of other free agents can be realized on the blockchain. In general, the more the resources that are pooled in a collaboration, the ‘better’ is the scope and quality of services that can be provided. Pooling resources to enhance the service quality is hardly new—many centralized organizations (e.g., cloud providers) do this at scale and with an efficiency that cannot be matched by collaborations whose resources are separated geographically and connected through low-bandwidth public Internet links. We claim that trying to mimic the applications offered by centralized providers on a blockchain can see widespread adoption only when the quality of service of the application itself is less important than the application being decentralized. For most people and for most applications existing today, this property seems to be not true. E.g., the number of users of centralized social media is significantly higher than the number of users using decentralized social media. When free agents collaborate they not only pool their physical resources they also pool their human capabilities including the intelligence, skills and expertise that they have. These human capabilities can be used, for instance, to inform machine inputs for computing the overall service outputs. The presence of a wide range of human capabilities in the system, which can be pooled together through diverse, decentralized collaborations can be a valuable service in many domains to end users. Such a service is unlikely to exist through a centralized organization today; or, even if it exists the number, independence and diversity of free agents that can be supported on a blockchain can be significantly greater than those of the free agents operating out of a single centralized organization. This results in collaborations that have a lower overall bias and increased innovation in the decentralized service. All collaborations have value whether they happen due to ossification or not. In an ossified coalition, the outputs of the collaboration are colored by the objective of maximizing efficiency to succeed in the market. In an ossified market, coalitions are acutely aware of market trends and what other coalitions are do22
ing. The exit of one coalition from the market is generally favorable to the other coalitions. In a decentralized collaboration, the outputs of the collaboration are colored by the objective of providing a level of service that is acceptable to a majority of service providers in the overall decentralized system. For the same type of service, what is acceptable to a majority of providers in a decentralized system can be very different from what is acceptable to a few (e.g., the leadership) in an ossified coalition. For example, a decentralized system may place a greater emphasis on shared principles, values, and practices even if those come at the cost of increasing service price or reducing profits. In our proposed method, the most important behavior needed to increase rewards is maintaining good trust relationships with other free agents. An entity (or a collection of entities) that seeks to compete with others by restricting collaborations to themselves will fail to get a good reward. Thus, our system discourages selfish behavior and forces participants to consider the overall wellbeing of the network. In certain cases, it may be counterproductive to use a large collaboration set. It is possible to limit the maximum size of collaborations allowed on our blockchain. Collaborations between free agents from domains that don’t normally interact can produce novel outcomes of benefit to end users. While many experts have voiced the increasing need for such collaborations (e.g., see [17]), in practice lack of adequate economic incentives prevents them from happening. An “exploratory” collaboration is financially risky and is afforded only by large corporations today. A decentralized blockchain can provide a platform where the risk of exploration is absorbed by the other “exploitative” collaborations happening on chain, thus, encouraging innovation.
8
Preventing On-Chain Merchant Ossification
Smart contracts have helped create markets for various services in multiple domains including DeFi, social networks, gaming, NFTs etc [9]. E.g., prominent services offered by major providers in the DeFi domain comprises of decentralized exchanges, lending and borrowing, liquid staking and restaking services (among others). If we focus on any one type of service, we see that the market forces once again encourage ossification with a small number of big providers dominating the market [54]. On-chain markets are unique as services are guaranteed to be available as long as the blockchain is live, most services make their code open source, many services are governed by DAOs, and the market itself is permissionless with a low entry barrier. Nevertheless, when a large fraction of the market share is held by a single organization, it becomes susceptible to attacks such as token theft [13,34,7,11], undesirable protocol changes [14], smart contract bugs [61] and rugpulls [5]. The smart contract services landscape can also be decentralized to prevent these attacks, and encourage greater collaboration between the service provider community. We follow the ideas of §5 to provide a solution sketch. Consider a set of providers P providing an on-chain service (e.g., lending). In a decentralized (Definition 2) service, when a user submits a service request it is randomly routed 23
to one of the provider’s (e.g., with a probablity proportional to the provider’s current market share) service smart contract. The chosen provider’s smart contract collaborates with other providers’ smart contracts to provide the service. As in §5, we can assign an importance value and a market share value (analogous to stake in §5) to each provider. The reward schemes can also be designed analogous to §5. Note that unlike anti-trust laws, our mechanism does not seek to divide a large organization into smaller ones. If any of the providers in P are already heavily ossified, we don’t try to (nor can we) split it up. Instead our protocol merely encourages strong collaboration between the existing providers in P . In other words, we try to prevent any further ossification from happening in the future, but we cannot do anything about the ossification that has already happened in the past. To realize the above solution in today’s blockchains, we would require additional smart contracts and methods. E.g., we would need a smart contract that receives user requests and directs them to a random provider’s contract. We would need to keep track of the provider set P and do all the computations associated with calculating the importance. Doing all computations on chain may be expensive in existing blockchains. Since all on-chain activity is public, it may be possible to do the importance computations offline and feed it to the chain via oracles. It is also essential that the service operations are clearly defined with standardized interfaces so that multiple providers can inter-operate seamlessly. To derive the full intended benefit of our decentralized service, it is important that providers develop their smart contracts independently without directly copying the source code from a single reference.
9
Decentralized Organizations
Many organizations exist today that are collectively managed by its members— such as worker cooperatives or credit unions—and in the case of blockchains, decentralized autonomous organizations (DAOs). In these collectives, key decisions about how to steer the organization are democratically made while the revenue earned is shared between the members. Depending on the organization’s structure, a portion of the revenue may be directly awarded to the members; or, the members could indirectly benefit through increasing value of their membership stake (e.g., governance tokens). Each of these organizations can, fundamentally, be seen as a market where members compete for votes. Consider a voting in a DAO for a decision where the possible choices are A or B. Here, the proponents of A and the proponents of B are the two sellers. The undecided voters are the buyers. In many cases, whether A wins or B wins, to a large extent, depends on how effectively their respective proponents are able to convince the undecided voters on the benefits of those choices (i.e., the campaign). As with other markets we have discussed, campaigning can heavily benefit from ossification. When proponents of a choice (A or B) pool together their resources (time, money, effort etc.), they can execute a campaign that is much more efficient compared to what an individual 24
member can do alone. Therefore, we claim that most—if not all—of the collectives today are internally ossified. In particular, measurement studies have shown that DAOs, contrary to their name, are not decentralized and often suffer from strong centralization with a significant voting share controlled by just a small number of parties. The ideas we have outlined in this paper allow us to construct collectives that are resistant to ossification and achieve decentralization in the sense of Definition 2. Members can be incentivized to engage in unossified collaborative discussions about the voting issues at hand. Undecided voters can learn about the issues from the collaborations, before deciding what to vote for. Our incentives ensure that collaboration sets contain proponents from multiple voting choices, and not just a single choice. This provides an opportunity for the undecided voters to receive an unbiased opinion about the voting choices directly from the proponents of the choices. In some DAOs, revenue is split proportional to the number of governance tokens a member has. In addition to the voting market mentioned above, in these DAOs another market arises: a market for buying and selling governance tokens. At any time instant, there may be members that are looking to sell their governance token and others that are looking to purchase them. In this market, the sellers are those looking to purchase the governance tokens and the buyers are the those selling their tokens. The seller with the best bid (i.e., highest) receives the token. Once again, the efficiency of the seller (the bid value) can be improved through ossification. By pooling funds, an ossified coalition can purchase a significantly greater number of governance token than what an individual user can. Thus, in this market we can expect centralizing clusters of members to arise that own most of the governance tokens. If the members of a coalition are ideologically aligned, the same coalition can engage as a single ossified entity in the token buy-sell market and in the voting campaign market. Here too, we can use our ideas to combat ossification.
10
Discussion
Blockchains are trustless—it is sufficient for a user to have trust that the majority of users are honest without requiring to individually trust any user. This core principle has informed blockchain design and innovation over the years. Even in layer-2 methods where users are required to trust an individual provider (e.g., the sequencer in a rollup), mechanisms are provided through which the provider is slashed for misbehavior. Our proposed method is a marked departure from this status quo. Not only do we ask nodes to individually trust (a small number of) other nodes to form collaborations, we explicitly slash only the publisher even if it a collaborating node that provably deviated from protocol. From the various examples highlighted in the paper, we have seen that despite being a trustless system, trust relationships in the form of ossified coalitions almost invariably occur because it is the rational action for users seeking to maximize their payoffs. These trust relationships are hard to detect, disincentivize, or ban. 25
It is, therefore, natural to try to have mechanisms that encourage the trust relationships to be in a way that is beneficial for the overall system. Another key property of blockchains is pseudonymity. In our proposed method, users need a platform through which they can discover, interact, and form partnerships with other users. Even if the platform supports anonymous interaction, the process of collaboration can reveal private information about a user. How to enable users to collaborate while keeping their identities anonymous is an important question. Sybil users can flood the communication platform with spam. Filtering out the spam is necessary to allow for meaningful trust relationships to form between honest nodes. Historically, human societies and organizations have been structured to have a small (relative to the size of the organization), centralized leadership. This is true even in the ossified coalitions occurring on blockchains. When users are asked to collaboratively perform tasks, it is likely that a similar leadership-worker segregation structure emerges in the system. That is, some users may prefer to lead while others prefer to be led. This is particularly important in applications where collaborations require significant human-to-human interaction. The impact of such a segregation on the decentralization and value provided by the network is an important aspect that needs to be studied. In our proposed method, a user can have a fixed set of collaborators as long as the overall collaboration graph is an expander. For certain applications, there may be value in frequently changing the collaboration set of a user over time. How to design the reward mechanism so that it looks at not only the connectivity of the collaboration graph, but also its dynamism is an interesting open question.
10.1
The Value of Decentralization
Our work prompts a re-visit to the question of what is the value of decentralization in blockchains. The common response to this question is: (1) decentralization eliminates single points of failure making the network more resilient to attacks and failures; (2) it provides transparency with verifiable audit trails over an immutable, public ledger; (3) it eliminates the need for trusted intermediaries for executing contracts; (4) it is resistant to censorship as no single entity controls access to the data; (5) it provides credible neutrality where the network’s core algorithms apply equally to all participants without discrimination. Intuitively, a blockchain that is controlled by just 4 large coalitions with a 1000 validators per coalition is less decentralized than a blockchain with 4000 independent validators. However, the above five principles are equally applicable to both of these cases as long as a (super-)majority of the validators are honest. The argument that the network with 4 coalitions is more susceptible to failures or attacks requires the additional assumption that members of a coalition share a common leadership, infrastructure, software etc. If members of a coalition don’t share anything in common, except that each member has trust relationships only with other members of the same coalition, it is hard to argue that the scenario with 26
the 4 coalitions is more susceptible to failures or attacks.9 Therefore, there must be a benefit to decentralization beyond the five principles listed above. We identify incentivized altruism as the additional property satisfied by decentralized systems. In incentivized altruism, members perform actions that are beneficial to the overall network in exchange for a direct or indirect compensation. Unlike regular actions which provide an immediate profit for the member (e.g., mining a block), an altruistic action incurs a non-negative cost (positive or zero) for the member in the short term and may be profitable only in the long run. E.g., in today’s blockchains (e.g., Bitcoin), nodes help forward blocks and other messages which benefits the entire network. Even if the forwarding node is not rewarded directly for its actions, if the node holds tokens it can indirectly benefit by contributing to an increase in the token’s value by maintaining a healthy network. Users also altruistically contribute to the blockchain by writing open-source software for the clients, wallets, Web-2 interfaces etc. Members also help other members through messaging platforms like Discord, posting tutorials, and organizing conferences. In our proposed method, altruism extends even further as nodes help other nodes in the service execution directly on chain. On the other hand, in centralized coalitions members of a coalition interact with and help only members of the same coalition for service execution. The impact of (incentivized) altruism on provider behavior, service quality, and earned rewards is an interesting direction for future work. Altruism provide two distinct advantages to the network. First, nodes can enhance the amount of service and the quality of service provided by collaborating with other nodes. This is particularly useful for newly joined nodes who may not have adequate resources at the beginning. Second, altruism enhances the economic stability of the network. A node—even if it is a well-established one—can occasionally experience unforeseen technological or economic challenges (e.g., hardware failure due to a natural disaster, or a sudden financial hardship). During such times, the altruistic benefactors can help dampen the service impact to end users by helping the affected node. In a way, the benefactors act as a low-premium insurance policy providing valuable assistance at times of need. The benefits of collaborative decentralization extend to security as well. In a network where nodes have a strong social collaboration, the negative impact of Sybil attacks can be significantly ameliorated. E.g., in a proof-of-work chain if a private chain attack originates from a user(s) outside of the core collaboration graph, it can be easily ignored even if it contains more work than the honest chain. Such overriding “social consensus” decisions have been made by members of various blockchains in the past on a need basis depending on the severity of the security issue. 10.2
Cross-Chain Collaboration
Ossification can occur at the level of blockchains, with different blockchains competing to offer the same type of services. Even if each blockchain is individually 9
We assume a member is willing to interact only with a member it trusts. A global “network switch”—to which all members are connected—is trusted by all members.
27
decentralized internally, ossification across chains can cause a small number of blockchains to emerge as the dominant providers with an overwhelming market share (e.g., today Bitcoin holds > 50% of the market capitalization across cryptocurrencies). The full benefits of decentralization can be realized only if decentralization is present at all levels. This implies there must be a degree of collaboration and altruism present across blockchains, while avoiding the formation of any blockchain-level coalitions. Within an individual blockchain, collaboration and altruism can be codified as law forcing this desired behavior from the users. Eliciting such behavior outside of a chain appears challenging. The difficulty arises due to two key questions: (1) what is the incentive for a blockchain to altruistically help other blockchains? (2) what does it mean (i.e., how can) for a blockchain to help other blockchains? An immediate but unsatisfactory answer to (1) is “blockchains must help other blockchains because it is in the spirit of (collaborative) decentralization.” Newly built chains can certainly benefit from the assistance of well-established chains. However, providing and receiving assistance can benefit even well-established chains. If each blockchain collaborates with other blockchains it trusts, the core group of blockchains in the blockchain-level collaboration graph can achieve greater resilience and stability to adverse events that would not be possible without collaboration. The core group can also be insulated against catastrophic events occurring outside of the group, such as the crash of a certain token. The overall public trust on the core group increases, which benefits all the members of the group. A blockchain can help another blockchain in many ways. It could provide financial assistance, investments, help with securing the other chain, share knowledge and experience, etc. We leave a systematic analysis of these potential solution ideas to both questions for future work.
11
Related Work
Our work has connections to prior research and ideas from various disciplines including economics, sociology, psychology and political science. We do not attempt to provide an exhaustive list of related works from those fields due to the authors’ limited expertise in those areas. We hope follow-up works from experts in these areas can help bridge any gaps to our work. Nevertheless, we provide a small sample of papers that are relevant. The concept of ossification, as presented in this paper, is a well-documented phenomenon in economics. Autor et al. [22] provides an analysis on the rise of “superstar” firms and their impact on the labor share. The book Frank et al. [50] discusses winner-take-all markets where even a small difference in performance results in enormous differences in the reward. Eisenmann et al. [42] study the strong network effects in twosided markets. Haskel et al. [58] present the impact of the infinite-scalability of intangible assets and how they enable superstar firms. The necessity of altruism for a well-functioning economy is increasingly being discussed by economists [80]. Becker [25] proposed the famous “rotten kid 28
theorem” that shows even selfish members of a family will act for the welfare of the family if the family head is altruistic. Andreoni [18] introduced the notion of a “warm glow” as an intrinsic utility derived by altruists challenging the pure selfless motivations of altruists. Fehr et al. [46] rejects the long-held hypothesis that self-interest is the sole motivator for all people. It shows how individuals are sometimes willing to sacrifice personal gain to ensure equity, punish wrongdoers, or to help others. Bramoullé et al. [31] study the production patterns that emerge when people are modeled as altruistic and care about the well being of friends and family. It shows how altruistic lending acts as a vital economic cushion during crises and allows the economy to rebound faster when the crises pass. Simon [59,89] argues that if individuals acted purely selfishly, the sheer computational resources required to design perfect, cheat-proof contracts and monitor compliance would overwhelm any economic network. The idea that collaborating with random or loosely connected people sparks creativity has been well-studied in sociology, economics, and organizational psychology. Granovetter [55] proposed that casual acquaintances (weak ties) are more valuable than close friends (strong ties) for moving new information and novel opportunities across different social networks. Burt [33] identifies “structural holes”—the empty space between disconnected groups of people—and argues that individuals who bridge these holes are more likely synthesize creative and valuable ideas. It is also worth mentioning John Stuart Mills’s [72] opinion that “it is hardly possible to overrate the value ... of placing human beings in contact with persons dissimilar to themselves, and with modes of thought and action unlike those with which they are familiar .... Such communication has always been, and is peculiarly in the present age, one of the primary sources of progress.” Fleming [49] proposed that the vast majority of breakthroughs are not entirely new to the world; rather, they are novel, often surprising recombinations of existing technologies or concepts. It argues that teams with varied technical expertise and backgrounds are much more likely to generate extreme creative outcomes. Yokoo et al. [96] analyze solution concepts for coalition games in a Sybil (termed a “false name” attack in the paper) setting. They show that the classical Shapley value is not Sybil resistant, and propose a novel solution concept that is Sybil and coalition resistant. The paper does not provide an efficient algorithm for computing the proposed solution. The paper also shows that Sybil resistance can be achieved by defining characteristic functions on “skills” (i.e., stake) rather than on agents. Later works have developed compact representations and linear-programming based algorithms for computing the solution, but it remains exponential time in the worst case [78,77]. Lee et al. [67] provide an efficient approximation algorithm for computing their proposed “faithful” Shapley value that is resistant to false-name attacks. Roig et al. [71] show that there is no solution that simultaneously satisfies efficiency, symmetry, null player, additivity, and Sybil-proofness. In the domain of blockchains, reputation systems have been used as a basic tool for determining the trustworthiness of users [57]. A reputation score for a 29
user is computed based on the feedback (positive or negative) received about the user from other users. Our idea of importance differs from a reputation score in that importance is computed algorithmically based on a user’s behavior while reputation is computed from user feedback. Decentralized reputation systems use a blockchain for recording and updating user reputation scores [39,99]. Key research works in this direction have proposed solutions for dealing with Sybil attacks, collusion attacks, re-entry attacks, and bad-mouthing attacks [27]. Reputation has also been used as an alternative to stake for developing proof of reputation consensus protocols [79,100]. A number of recent works have proposed measures for mitigating centralization in blockchains [64]. Kiayias et al. study reward sharing schemes modeled as a oceanic game [63]. Comparing the Shapley mechanism against the standard proportional scheme, they show that the Shapley value is a competitive alternative that has increased Sybil resistance while providing decentralization. Middleware solutions such as Eigenlayer [69,92] promote decentralization by allowing validators to use their same staked tokens for securing multiple services. Liquid staking protocols (e.g., Lido) allows validators to retain their ETH even while staking them, thereby lowering the barrier to becoming a validator [87]. For proof-of-work chains, Miller et al. [73] propose “non-outsourceable puzzles” which create a disincentive for pool operators to outsource mining work. Distributed mining pools [84] use a decentralized coordinator (e.g., implemented as a smart contract) to replace the centralized coordinator of conventional pools. The idea that Sybil nodes have weak social relationships with honest nodes has been used to design Sybil protection systems [98,97].
References 1. The Meaning of Decentralization (2017), https://medium.com/@VitalikButer in/the-meaning-of-decentralization-a0c92b76a274 2. Demis Hassabis Interview (2024), https://www.nobelprize.org/prizes/chem istry/2024/hassabis/interview/ 3. Is Crypto’s Killer App Finally Here? (2024), https://www.forbes.com/sites/c hristiancatalini/2024/02/19/is-cryptos-killer-app-finally-here/ 4. Stablecoins: the first ’killer app’ for Blockchain? (2025), https://www.kcl.ac.u k/news/stablecoins-the-first-killer-app-for-blockchain 5. AnubisDAO Investors Lose $60 Million in Alleged Rug Pull (2026), https://decr ypt.co/84924/anubisdao-investors-lose-60-million-in-alleged-rug-pull 6. Blockchain Adoption Statistics 2026 -Market Size & Trends) (2026), https://ww w.demandsage.com/blockchain-statistics/ 7. DeFi Project bZx Exploited for Second Time in a Week, Loses $630K in Ether (2026), https://www.coindesk.com/markets/2020/02/18/defi-project-bzx-e xploited-for-second-time-in-a-week-loses-630k-in-ether 8. DePIN: Evaluating the Real-World Utility and Future of Decentralized Physical Infrastructure Networks (2026), https://blockeden.xyz/blog/2026/03/21/de pin-march-2026-reality-check-650-projects-19b-market-cap-revenue/ 9. Ethereum Apps (2026), https://ethereum.org/apps/ 10. NINeS 2027: Statement of Purpose (2026), https://nines-conference.org/sop
30
11. Oracle Manipulation Attacks are Rising, Creating a Unique Concern for DeFi (2026), https://www.chainalysis.com/blog/oracle-manipulation-attacks-r ising/ 12. Privacy emerges as crypto’s next ’killer app,’ with Arc, Canton and Tempo topping $1 billion in funding (2026), https://www.coindesk.com/business/2026/0 5/12/privacy-emerges-as-crypto-s-next-killer-app-with-arc-canton-a nd-tempo-topping-usd1-billion-in-funding 13. Revisiting Beanstalk Farms Exploit (2026), https://www.certik.com/blog/re visiting-beanstalk-farms-exploit 14. The Compound Finance Governance Attack: A Recap and Its Implications (2026), https://research.despread.io/compound-finance-governance-a ttack/ 15. The Ultimate List of Cloud Computing Stats for 2026: Market Growth, Adoption & Security Trends (2026), https://softjourn.com/insights/cloud-computi ng-stats 16. Vitalik Buterin Urges Ethereum to Build “Sanctuary Technologies” Against Digital Control (2026), https://www.mexc.com/news/850200 17. Alon, N., Bloom, T.F., Gowers, W., Litt, D., Sawin, W., Shankar, A., Tsimerman, J., Wang, V., Wood, M.M.: Remarks on the disproof of the unit distance conjecture. arXiv preprint arXiv:2605.20695 (2026) 18. Andreoni, J.: Impure altruism and donations to public goods: A theory of warmglow giving. The economic journal 100(401), 464–477 (1990) 19. Apostolaki, M., Zohar, A., Vanbever, L.: Hijacking bitcoin: Routing attacks on cryptocurrencies. In: 2017 IEEE symposium on security and privacy (SP). pp. 375–392. IEEE (2017) 20. Arvestad, I.: Near-linear time expander decomposition in practice (2022) 21. Atzori, M.: Blockchain technology and decentralized governance: Is the state still necessary? Available at SSRN 2709713 (2015) 22. Autor, D., Dorn, D., Katz, L.F., Patterson, C., Van Reenen, J.: The fall of the labor share and the rise of superstar firms. The Quarterly journal of economics 135(2), 645–709 (2020) 23. Azouvi, S., Maller, M., Meiklejohn, S.: Egalitarian society or benevolent dictatorship: The state of cryptocurrency governance. In: International conference on financial cryptography and data security. pp. 127–143. Springer (2018) 24. Beck, R., Müller-Bloch, C., King, J.L.: Governance in the blockchain economy: A framework and research agenda. Journal of the association for information systems 19(10), 1 (2018) 25. Becker, G.S.: A theory of social interactions. Journal of political economy 82(6), 1063–1093 (1974) 26. Beikverdi, A., Song, J.: Trend of centralization in bitcoin’s distributed network. In: 2015 IEEE/ACIS 16th international conference on software engineering, artificial intelligence, networking and parallel/distributed computing (SNPD). pp. 1–6. IEEE (2015) 27. Bellini, E., Iraqi, Y., Damiani, E.: Blockchain-based distributed trust and reputation management systems: A survey. Ieee Access 8, 21127–21151 (2020) 28. Berners-Lee, T.: Weaving the Web: The original design and ultimate destiny of the World Wide Web by its inventor. Harper San Francisco (1999) 29. Böhme, R., Christin, N., Edelman, B., Moore, T.: Bitcoin: Economics, technology, and governance. Journal of economic Perspectives 29(2), 213–238 (2015)
31
30. Bonneau, J., Miller, A., Clark, J., Narayanan, A., Kroll, J.A., Felten, E.W.: Sok: Research perspectives and challenges for bitcoin and cryptocurrencies. In: 2015 IEEE symposium on security and privacy. pp. 104–121. IEEE (2015) 31. Bramoullé, Y., Kranton, R.E.: Altruism networks and economic relations. Journal of Economic Behavior & Organization 226, 106687 (2024) 32. Brünjes, L., Kiayias, A., Koutsoupias, E., Stouka, A.P.: Reward sharing schemes for stake pools. In: 2020 IEEE european symposium on security and privacy (EuroS&p). pp. 256–275. IEEE (2020) 33. Burt, R.S.: Structural holes and good ideas. American journal of sociology 110(2), 349–399 (2004) 34. Caldarelli, G., Ellul, J.: The blockchain oracle problem in decentralized finance—a multivocal approach. Applied Sciences 11(16), 7572 (2021) 35. Chen, J., Micali, S.: Algorand. arXiv preprint arXiv:1607.01341 (2016) 36. Cho, H.: Asic-resistance of multi-hash proof-of-work mechanisms for blockchain consensus protocols. IEEE Access 6, 66210–66222 (2018) 37. Chohan, U.W.: Cryptocurrencies and inequality. In: Cryptofinance: A new currency for a new economy, pp. 49–62. World Scientific (2022) 38. Dai, M., Zhang, S., Wang, H., Jin, S.: A low storage room requirement framework for distributed ledger in blockchain. IEEE Access 6, 22970–22975 (2018). https: //doi.org/10.1109/ACCESS.2018.2814624 39. Dennis, R., Owen, G.: Rep on the block: A next generation reputation system based on the blockchain. In: 2015 10th International Conference for Internet Technology and Secured Transactions (ICITST). pp. 131–138. IEEE (2015) 40. Dimitri, N.: Quadratic voting in blockchain governance. Information 13(6), 305 (2022) 41. Doudna, J.: A viable path toward responsible use. Issues in science and technology 36(3), 37–39 (2020) 42. Eisenmann, T.R., Parker, G., Van Alstyne, M.W.: Strategies for two sided markets. Harvard Business Review, Vol. October (2006) 43. Ekblaw, A., Barabas, C., Harvey-Buschel, J., Lippman, A.: Bitcoin and the myth of decentralization: Socio-technical proposals for restoring network integrity. 2016 IEEE 1st International Workshops on Foundations and Applications of Self* Systems (FAS*W) pp. 18–23 (2016), https://api.semanticscholar.org/CorpusID: 17589942 44. Fanti, G., Kogan, L., Oh, S., Ruan, K., Viswanath, P., Wang, G.: Compounding of wealth in proof-of-stake cryptocurrencies. In: International conference on financial cryptography and data security. pp. 42–61. Springer (2019) 45. Farmer, P.: Pathologies of power: Health, human rights, and the new war on the poor, vol. 4. Univ of California Press (2004) 46. Fehr, E., Schmidt, K.M.: The economics of fairness, reciprocity and altruism– experimental evidence and new theories. Economics 20, 49 (2005) 47. Feld, S., Schönfeld, M., Werner, M.: Analyzing the deployment of bitcoin’s p2p network under an as-level perspective. Procedia Computer Science 32, 1121–1126 (2014) 48. Fleischmann, H., Li, G.Z., Li, J.: Improved directed expander decompositions. arXiv preprint arXiv:2507.09729 (2025) 49. Fleming, L.: Breakthroughs and the ‘long tail’of innovation. MIT Sloan Management Review (2007) 50. Frank, R.H., Cook, P.J.: The winner-take-all society: Why the few at the top get so much more than the rest of us. Random House (2010)
32
51. Gencer, A.E., Basu, S., Eyal, I., Van Renesse, R., Sirer, E.G.: Decentralization in bitcoin and ethereum networks. In: International conference on financial cryptography and data security. pp. 439–457. Springer (2018) 52. Gervais, A., Karame, G.O., Capkun, V., Capkun, S.: Is bitcoin a decentralized currency? IEEE security & privacy 12(3), 54–60 (2014) 53. Gervais, A., Karame, G.O., Wüst, K., Glykantzis, V., Ritzdorf, H., Capkun, S.: On the security and performance of proof of work blockchains. In: Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. pp. 3–16 (2016) 54. Gogol, K., Velner, Y., Kraner, B., Tessone, C.: Sok: liquid staking tokens (lsts) and emerging trends in restaking. arXiv preprint arXiv:2404.00644 (2024) 55. Granovetter, M.S.: The strength of weak ties. American journal of sociology 78(6), 1360–1380 (1973) 56. Guo, Z., Gao, Z., Mei, H., Zhao, M., Yang, J.: Design and optimization for storage mechanism of the public blockchain based on redundant residual number system. IEEE Access 7, 98546–98554 (2019). https://doi.org/10.1109/ACCESS.2019. 2930125 57. Hasan, O., Brunie, L., Bertino, E.: Privacy-preserving reputation systems based on blockchain and other cryptographic building blocks: A survey. ACM Computing Surveys (CSUR) 55(2), 1–37 (2022) 58. Haskel, J., Westlake, S.: Capitalism without capital: The rise of the intangible economy (2017) 59. Herbert, A.S.: Models of Man. Social and Rational (1957) 60. Hsieh, Y.Y., Vergne, J.P.J., Wang, S.: The internal and external governance of blockchain-based organizations: Evidence from cryptocurrencies. In: Bitcoin and beyond, pp. 48–68. Routledge (2017) 61. Jiao, T., Xu, Z., Qi, M., Wen, S., Xiang, Y., Nan, G.: A survey of ethereum smart contract security: Attacks and detection. Distributed Ledger Technologies: Research and Practice 3(3), 1–28 (2024) 62. Judmayer, A., Zamyatin, A., Stifter, N., Voyiatzis, A.G., Weippl, E.: Merged mining: Curse or cure? In: Garcia-Alfaro, J., Navarro-Arribas, G., Hartenstein, H., Herrera-Joancomartí, J. (eds.) Data Privacy Management, Cryptocurrencies and Blockchain Technology. pp. 316–333. Springer International Publishing, Cham (2017) 63. Kiayias, A., Koutsoupias, E., Markakis, E., Tsamopoulos, P.: Pool formation in oceanic games: Shapley value and proportional sharing. arXiv preprint arXiv:2505.04422 (2025) 64. Kiffer, L.C.: Centralization in Blockchains: Causes and Mitigations. Ph.D. thesis, Northeastern University (2022) 65. Kim, S.K., Ma, Z., Murali, S., Mason, J., Miller, A., Bailey, M.: Measuring ethereum network peers. In: Proceedings of the Internet Measurement Conference 2018. pp. 91–104 (2018) 66. Kwon, Y., Liu, J., Kim, M., Song, D., Kim, Y.: Impossibility of full decentralization in permissionless blockchains. In: Proceedings of the 1st ACM Conference on Advances in Financial Technologies. pp. 110–123 (2019) 67. Lee, K., Liu, Z., Tang, W., Zhang, Y.: Faithful group shapley value. Advances in Neural Information Processing Systems 38, 162852–162870 (2026) 68. Lewenberg, Y., Bachrach, Y., Sompolinsky, Y., Zohar, A., Rosenschein, J.S.: Bitcoin mining pools: A cooperative game theoretic analysis. In: Proceedings of the 2015 international conference on autonomous agents and multiagent systems. pp. 919–927 (2015)
33
69. Li, L.: Mitigating challenges in ethereum’s proof-of-stake consensus: Evaluating the impact of eigenlayer and lido. arXiv preprint arXiv:2410.23422 (2024) 70. Mao, Y., Venkatakrishnan, S.B.: Less is more: Understanding network bias in proof-of-work blockchains. Mathematics 11(23), 4741 (2023) 71. Mazorra, B., Della Penna, N.: Towards optimal prior-free permissionless rebate mechanisms, with applications to automated market makers & combinatorial orderflow auctions. arXiv preprint arXiv:2306.17024 (2023) 72. Mill, J.S.: Principles of political economy. D. Appleton (1885) 73. Miller, A., Kosba, A., Katz, J., Shi, E.: Nonoutsourceable scratch-off puzzles to discourage bitcoin mining coalitions. In: Proceedings of the 22Nd acm sigsac conference on computer and communications security. pp. 680–691 (2015) 74. Motepalli, S., Jacobsen, H.A.: Decentralization in pos blockchain consensus: Quantification and advancement. IEEE Transactions on Network and Service Management (2025) 75. Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system (2008) 76. Neudecker, T., Hartenstein, H.: Network layer aspects of permissionless blockchains. IEEE Communications Surveys & Tutorials 21(1), 838–857 (2018) 77. Ohta, N., Conitzer, V., Satoh, Y., Iwasaki, A., Yokoo, M.: Anonymity-proof shapley value: extending shapley value for coalitional games in open environments. In: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 2. pp. 927–934 (2008) 78. Ohta, N., Iwasaki, A., Yokoo, M., Maruono, K., Conitzer, V., Sandholm, T.: A compact representation scheme for coalitional games in open anonymous environments. In: AAAI. vol. 6, pp. 697–702 (2006) 79. de Oliveira, M.T., Reis, L.H., Medeiros, D.S., Carrano, R.C., Olabarriaga, S.D., Mattos, D.M.: Blockchain reputation-based consensus: A scalable and resilient mechanism for distributed mistrusting applications. Computer Networks 179, 107367 (2020) 80. Park, D.H.M.: Altruistic Economics: Why this is a Sound Alternative to NeoClassical Economic. Ph.D. thesis, Carnegie Mellon University (2010) 81. Raman, R.K., Varshney, L.R.: Dynamic distributed storage for scaling blockchains (2018), https://arxiv.org/abs/1711.07617 82. Roubini, N.: Blockchain isn’t about democracy and decentralisation–it’s about greed. The Guardian 15 (2018) 83. Sai, A.R., Buckley, J., Fitzgerald, B., Le Gear, A.: Taxonomy of centralization in public blockchain systems: A systematic literature review. Information Processing & Management 58(4), 102584 (2021) 84. Sakurai, A., Shudo, K.: Fiberpool: Leveraging multiple blockchains for decentralized pooled mining. arXiv preprint arXiv:2501.15459 (2025) 85. Sapirshtein, A., Sompolinsky, Y., Zohar, A.: Optimal selfish mining strategies in bitcoin. In: International conference on financial cryptography and data security. pp. 515–532. Springer (2016) 86. Saranurak, T., Wang, D.: Expander decomposition and pruning: Faster, stronger, and simpler. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 2616–2635. SIAM (2019) 87. Scharnowski, S., Jahanshahloo, H.: The economics of liquid staking derivatives: Basis determinants and price discovery. Journal of Futures Markets 45(2), 91–117 (2025) 88. Schrijver, A., et al.: Combinatorial optimization: polyhedra and efficiency, vol. 24. Springer (2003)
34
89. Simon, H.A.: A mechanism for social selection and successful altruism. Science 250(4988), 1665–1668 (1990) 90. Sulser, A.L., Gutenberg, M.P.: Near-optimal algorithm for directed expander decompositions. arXiv preprint arXiv:2403.04542 (2024) 91. Tapsell, J., Akram, R.N., Markantonakis, K.: An evaluation of the security of the bitcoin peer-to-peer network. In: 2018 IEEE international conference on internet of things (IThings) and IEEE green computing and communications (GreenCom) and IEEE cyber, physical and social computing (CPSCom) and IEEE smart data (SmartData). pp. 1057–1062. IEEE (2018) 92. Team, E.: Eigenlayer: The restaking collective. White paper 1(1), 1–19 (2024) 93. Torvalds, L.: Just for fun: The story of an accidental revolutionary. Harper Audio (2001) 94. Winter, E.: The shapley value. Handbook of game theory with economic applications 3, 2025–2054 (2002) 95. Wu, Z., Lin, B., Nikiforakis, N., Balasubramanian, A.: Degrees of decentralized freedom: Comparing modern decentralized storage platforms. In: 2025 9th Network Traffic Measurement and Analysis Conference (TMA). pp. 1–11. IEEE (2025) 96. Yokoo, M., Conitzer, V., Sandholm, T., Ohta, N., Iwasaki, A.: Coalitional games in open anonymous environments. In: AAAI. vol. 5, pp. 509–514 (2005) 97. Yu, H., Gibbons, P.B., Kaminsky, M., Xiao, F.: Sybillimit: A near-optimal social network defense against sybil attacks. In: 2008 IEEE Symposium on Security and Privacy (sp 2008). pp. 3–17. IEEE (2008) 98. Yu, H., Kaminsky, M., Gibbons, P.B., Flaxman, A.: Sybilguard: defending against sybil attacks via social networks. In: Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications. pp. 267–278 (2006) 99. Zhou, Z., Wang, M., Yang, C.N., Fu, Z., Sun, X., Wu, Q.J.: Blockchain-based decentralized reputation system in e-commerce environment. Future Generation Computer Systems 124, 155–167 (2021) 100. Zhuang, Q., Liu, Y., Chen, L., Ai, Z.: Proof of reputation: A reputation-based consensus protocol for blockchain based systems. In: Proceedings of the 1st International Electronics Communication Conference. pp. 131–138 (2019)
A
Importance Transfer in a DAG
A.1
Preliminaries
Let us assume all nodes have the same stake for the time being. Consider a DAG D[t] of collaborators with a root node V [t]. The importance of a node v ∈ D[t] after tax is Iv [t](1 − β). For any subset S ⊆ D[t], define the utility u(S) of S as the total importance of all the nodes reachable from S (including the total importance of S itself), i.e., X u(S) = Iv [t](1 − β). (12) v∈D[t]:∃u∈S such that v is reachable from u
We define u({}) = 0. We have the following proposition. 35
Proposition 1. The utility function u : 2D[t] → R defined in Equation (12) is a monotone, submodular function. Proof. Consider any two subsets S1 , S2 with S1 ⊆ S2 ⊂ D[t]. Let v ∈ D[t]\S2 be any node not in S2 . Let T1 be the set of nodes reachable by v (including v) but not by S1 . Similarly, let T2 be the set of nodes reachable by v (including v) but not by S2 . It is easy to see that X Iv′ [t](1 − β), u(Si ∪ {v}) − u(Si ) = (13) v ′ ∈Ti
for i = 1, 2. Consider any v ′ ∈ T2 . This means there is no node from S2 that can reach v ′ . Since S1 ⊆ S2 , it follows that there is no node from S1 that can reach v ′ . Therefore, v ′ ∈ T1 . Since any node v ′ ∈ T2 is also in T1 , we have T2 ⊆ T1 . Thus, u(S1 ∪ {v}) − u(S1 ) ≥ u(S2 ∪ {v}) − u(S2 ),
(14)
which shows that u is submodular. We also have that u(S1 ) ≤ u(S2 ) since any node that reachable by S1 is also reachable by S2 . This shows that u is monotonic. ⊔ ⊓ We are interested in transferring the importance between different nodes in D[t]. For any v ∈ D[t], let Iv′ [t] be the importance of v after the transfer. To compute how importance is transferred, we consider the convex region defined by the following, X Iv′ [t] ≤ u(S), ∀S ⊂ D[t] (15) v∈S
X
Iv′ [t] = u(D[t]).
(16)
v∈D[t]
The inequalities (15) and (16) define the base of the polymatroid defined by u. We choose a point on the base that satisfies Properties 4–7. For any permutation σ of the nodes in D[t], the greedy solution given by Iv′ σ(i) = u({vσ(1) , vσ(2) , . . . , vσ(i) }) − u({vσ(1) , vσ(2) , . . . , vσ(i−1) }),
(17)
for all i ∈ {1, 2, . . . , |D[t]|} is a corner point on the base of the polymatroid. Conversely, for any corner point of the base, there exists a permutation whose solution coincides with the corner point [88]. For a permutation σ, let I ′ (σ) be the solution vector obtained by the greedy algorithm following the order σ. By the convexity of the base of the polymatroid, for any two permutations σ1 and σ2 , the solution δI ′ (σ1 ) + (1 − δ)I ′ (σ2 ) for δ ∈ (0, 1) is also on the base. The Shapley value [94] is the average of I ′ (σ) averaged over all possible permutations. In addition to being computationally expensive, the Shapley value does not guarantee that the solution computed is fair or Sybil resistant. 36
Our solution uses the DAG topology to derive a weighting for the permutations such that the resultant solution is fair and Sybil resistant. For any node v ∈ D[t], let Γ (v) denote the children of v in D[t]. We hierarchically construct the permutations and their weights as follows. 1. We first partition D[t] into two sets: the root V [t] and the rest of the DAG D[t]\V [t]. The sequence (V [t], D[t]\V [t]) receives a weight of α, while the sequence (D[t]\V [t], V [t]) receives a weight of 1 − α. The set D[t]\V [t] will be further partitioned and ordered in the subsequent steps with additions weights. 2. Let v1 , v2 , . . . , v|Γ (V [t])| be the nodes in Γ (V [t]). For any vi for i = 1, 2, . . . , |Γ (V [t])|, let R(vi ) be the set of nodes reachable from vi in D[t] including vi . Consider any permutation σ of the nodes in Γ (V [t]). We partition and order D[t]\V [t] as (R(vσ(1) ), R(vσ(2) )\R(vσ(1) ), R(vσ(3) )\{R(vσ(1) )∪R(vσ(2) )}, . . .) with each permutation receiving a weight of 1/|Γ (V [t])|!. If any of R(vσ(i) )\{R(vσ(1) )∪ R(vσ(2) ) . . . R(vσ(i−1) )} is empty we omit that entry in the ordering. 3. For any i = 1, 2, . . . , |Γ (V [t])|, the subgraph induced by the vertices R(vσ(i) )\{R(vσ(1) )∪ R(vσ(2) ) . . . R(vσ(i−1) )} is a DAG with root vσ(i) . We repeats steps 1 and 2 for all the |Γ (V [t])| DAGs.
A.2
Simplifying the Algorithm
Consider a node v ∈ D[t] and any permutation σ of the nodes in D[t]. In σ, let p(v) be the first appearing predecessor node of v (i.e., any node that can reach v in D[t]). If there are no predecessor nodes appearing before v in σ, we set p(v) = ϕ (null). If p(v) is not null for σ, then in the greedy solution for ′ σ the importance of v is counted towards the solution for p(v), i.e., Ip(v) [t] for σ is a summation of importance of nodes one of which is v. If p(v) is null, the importance of v is counted towards the solution for v. In any of our permutations, by construction, the importance of v can only be counted towards the solution for v or any of v’s predecessors. For any specific predecessor u of v, let Q(u) ⊂ D[t] be the nodes in D[t] than can reach u (excluding u). For p(v) to be equal to u in σ, none of the nodes in Q(u) must appear before u in the permutation. Consider any path V [t], v1 , v2 , . . . , vk , u from the root to u. The chance of the root V [t] appearing after u in the permutation is (1 − α). The chance of both V [t] and v1 appearing after u in the permutation is (1 − α)2 /|Q(u) ∩ Γ (V [t])|. Similarly, for any vi on the path, the chance of V [t], v1 , . . . , vi appearing after u in the permutation is (1 − α)i+1 /(|Q(u) ∩ Γ (V [t])| ∗ |Q(u) ∩ Γ (v1 )| ∗ . . . ∗ |Q(u) ∩ Γ (vi−1 )|). Finally the chance of u appearing before v but V [t], v1 , . . . , vk appearing after v in the permutation is (1−α)k+1 α/(|Q(u)∩Γ (V [t])|∗|Q(u)∩Γ (v1 )|∗. . .∗|Q(u)∩Γ (vk )|). Let P(u) be the set of all paths from the root V [t] to u in D[t]. The total fraction of importance that node v “pays” to node u in the asymmetric Shapley 37
value solution is X (V [t],v1 ,...,vk ,u)∈P(u)
(1 − α)k+1 α . (|Q(u) ∩ Γ (V [t])| ∗ |Q(u) ∩ Γ (v1 )| ∗ . . . ∗ |Q(u) ∩ Γ (vk )|) (18)
Instead of enumerating all permutations and explicitly computing the greedy solutions and then averaging them to compute the Shapley value solution, we can instead adopt the following simpler but equivalent solution motivated by Equation (18). Recall Iv [t](1 − β) is the initial importance of a node v after tax but before the DAG importance transfer. Consider the DAG DQ(v) [t] induced by Q(v) on D[t]. For any edge (u, u′ ) ∈ DQ(v) [t] associate an edge weight w(u, u′ ) = (1 − α)/|Γ (u)|. The payment algorithm for any node v ∈ D[t] is as follows. 1. All edges in DQ(v) [t] are marked “unvisited”. The importance iu received by any node u in DQ(v) [t] from v is set to 0. 2. v pays an amount Iv [t](1 − β)α to the root V [t], i.e., iV [t] ← Iv [t](1 − β)α. 3. Consider any unvisited edge (u, u′ ) ∈ DQ(v) [t] such that all incoming edges to node u are visited. Let iu be the total importance received by u from v. The importance received by u′ from v is incremented as iu′ ← iu′ + iu ∗ w(u, u′ ). Mark edge (u, u′ ) as visited. 4. Repeat step 3 until all edges in DQ(v) [t] are visited. A.3
Accounting for Stake
The algorithm presented in §A.2 assumes all nodes have the same stake. In this section, we explain how the previous algorithm can be modified if nodes have heterogeneous stake. For any node v ∈ D[t], let sv be the stake of v. Without loss of generality, assume sv is an integer multiple of a small constant ϵ for all v. Given a collaboration dag D[t] where the nodes have heterogeneous stake, we convert it into another DAG D′ [t] where the nodes have homogeneous stake. Consider a node v ∈ D[t] with stake sv . Let Γin (v) be the set of parents of v and Γ (v) is the set of children of v in D[t]. To compute D′ [t] we replace each node node v by a chain of sv /ϵ nodes with a total importance of Iv (1 − β) (how the importance is distributed among the nodes in the chain does not matter). The last node of v’s chain has outgoing edges to the first node of the chains of v’s children in D[t]. We then apply the algorithm of §A.2 on D′ [t]. The modified algorithm for D[t] is given below. 1. All edges in DQ(v) [t] are marked “unvisited”. The importance iu received by any node u in DQ(v) [t] from v is set to 0. 2. v pays an amount Iv [t](1 − β)(1 − (1 − α)sV [t] /ϵ ) to the root V [t], i.e., iV [t] ← Iv [t](1 − β)(1 − (1 − α)sV [t] /ϵ ). 3. Consider any unvisited edge (u, u′ ) ∈ DQ(v) [t] such that all incoming edges to node u are visited. Let iu be the total importance received by u from v. 38
The importance received by u′ from v is incremented as iu′ ← iu′ +
iu (1 − α)su /ϵ (1 − (1 − α)su′ /ϵ ) ∗ . s /ϵ |Γ (u)| 1 − (1 − α) u
(19)
Mark edge (u, u′ ) as visited. 4. Repeat step 3 until all edges in DQ(v) [t] are visited. A.4
Proof of Theorem 1
Proof. Since our importance transfer solution is a point on the base of the submodular polymatroid, Property 4 is trivially true. Next, we show Property 6. Consider any path-closed subset S ⊂ D[t] containing V [t]. This means for any node v ∈ S all the predecessors of v are also in S. By the algorithm in §A.3, v transfers its importance to its predecessors, which are nodes in S. None P of the nodes S transfer their importance to a node outside of S. Therefore, v∈S (Iv′ [t] − Iv [t](1 − β)) ≥ 0. On the other hand, the nodes in D[t]\S transfer importance to their predecessors in S. However, the nodes in D[t]\S doP not receive any additional importance from any node outside of D[t]\S. Hence, v∈D[t]\S (Iv′ [t] − Iv [t](1 − β)) ≤ 0. To prove Equation (3), consider the predecessors Q(v) of any node v ∈ D[t]. Let u ∈ Q(v) be any node. The fraction of importance transferred from v to u is sV [t] +
X path (V [t],u1 ,...,uk ,u))∈D[t]
Pk i=1 sui
su
ϵ (1 − α) (1 − (1 − α) ϵ ) |Q(u) ∩ Γ (V [t])| ∗ |Q(u) ∩ Γ (u1 )| ∗ . . . ∗ |Q(u) ∩ Γ (uk )| su
≤
X path (V [t],u1 ,...,uk ,u))∈D[t]
(1 − (1 − α) ϵ ) |Q(u) ∩ Γ (V [t])| ∗ |Q(u) ∩ Γ (u1 )| ∗ . . . ∗ |Q(u) ∩ Γ (uk )|
su
= (1 − (1 − α) ϵ ).
(20)
For any node u ∈ D[t]\Q(v), the importance transferred from v is 0. Hence, X
Iv′ [t] ≥ Iv [t](1 − β)(1 −
su
(1 − (1 − α) ϵ ))
u∈Q(v)
X
≥ Iv [t](1 − β)(1 −
(1 − (1 −
u∈Q(v)
= Iv [t](1 − β)(1 −
α X su ). ϵ
αsu ))) ϵ (21)
u∈Q(v)
Next, we show Property 5. For any two nodes u, v ∈ D[t], by the same argument as used for Equation (20), the total fraction of importance transferred su from v to u is at most (1 − (1 − α) ϵ ) ≤ αsu /ϵ. The total amount of importance received by u from v is at most Iv [t](1−β)αsu /ϵ. The total amount of importance 39
received by u is bounded as X α α X Iv [t](1 − β) su ≤ Iv [t](1 − β)su ϵ ϵ v∈D[t] v∈D[t] X X α Iv [t](1 − β) sv′ . ≤ ϵ ′
(22)
v ∈D[t]
v∈D[t]
Next, we show Property 7. The fraction of importance received by v before being replaced by a DAG from any node u ∈ R(v) is sV [t] +
X path (V [t],u1 ,...,uk ,v))∈D[t]
Pk i=1 sui ϵ
sv
(1 − (1 − α) ϵ ) (1 − α) . |Q(v) ∩ Γ (V [t])| ∗ |Q(v) ∩ Γ (u1 )| ∗ . . . ∗ |Q(v) ∩ Γ (uk )| (23)
Let A[t] be the DAG that node v is replaced as and w a parent of node v in D[t]. If v is replaced by A[t] and u0 is a root of A[t], for any path (V [t], u1 , . . . , uk , v) to sv v in the original DAG, the term (1 − (1 − α) ϵ )/|Q(v) ∩ Γ (uk )| in Equation (23) is replaced by Pk i=0 sui
X
X
v ′ ∈A[t] (u0 ,u1 ,...,uk ,v ′ ))∈A[t]
s ′ v
(1 − (1 − α) ϵ ) (1 − α) ϵ ′ ′ |Q(v ) ∩ Γ (w)||Q(v ) ∩ Γ (u0 )| ∗ . . . ∗ |Q(v ′ ) ∩ Γ (uk )| s
s
X (1 − (1 − α) vϵ ′ ) X (1 − (1 − α) vϵ ′ ) ≤ ≤ |Q(v ′ ) ∩ Γ (w)| |Q(v) ∩ Γ (w)| ′ ′ v ∈A[t]
≤
v ∈A[t]
(1 − (1 − α)
sv ϵ
2
P 2 s2 s ) + α2 ( ϵ2v − v′ ∈A[t] ϵv2′ ) + O(α3 ) |Q(v) ∩ Γ (w)| (24)
≤
(1 − (1 − α)
2
sv ϵ
s2v ϵ2
) + α2 ( − sϵv ) + O(α3 ) , |Q(v) ∩ Γ (w)|
(25)
where inequality (24) follows from the Taylor series approximation for the funcs ′ v tion f (x) = (1 − x) ϵ . Therefore, the maximum factor by which the fraction of importance received by v can increase is at most 1+
2 sv α2 sv 3 2 ( ϵ2 − ϵ ) + O(α ) sv
(1 − (1 − α) ϵ ))
,
which tends to 0 as α → 0. A.5
(26) ⊔ ⊓
Non-asymptotic Sybil Resistance at the Cost of Fairness.
Consider the following approximation to the importance transfer algorithm presented in §A.3. 40
a
b
c
e
(a)
a
d
Node
Stake
Importance (after tax)
a
0.1
0.05
b
0.2
0.2
c
0.05
0.1
d
0.3
0.2
e
0.1
0.05
(b)
𝑖!
b
d
c 𝑖"
𝑖#
𝑖$
e
(c)
Fig. 5: (a) Collaboration DAG D[t]. (b) Stake and importance of nodes initially after tax. (c) Node e transfers importance to all its ancestors in D[t].
1. All edges in DQ(v) [t] are marked “unvisited”. The importance iu received by any node u in DQ(v) [t] from v is set to 0. αs 2. v pays an amount Iv [t](1 − β) Vϵ [t] to the root V [t], i.e., iV [t] ← Iv [t](1 − αsV [t] β) ϵ . 3. Consider any unvisited edge (u, u′ ) ∈ DQ(v) [t] such that all incoming edges to node u are visited. Let iu be the total importance received by u from v. The importance received by u′ from v is incremented as iu′ ← iu′ +
αsu′ iu ϵ ∗ . αsu ϵ|Γ (u)|
(27)
Mark edge (u, u′ ) as visited. 4. Repeat step 3 until all edges in DQ(v) [t] are visited. For the same DAG D[t], the fraction of importance transferred by a node v ∈ D[t] to its predecessors is slightly greater in this algorithm compared to the algorithm in §A.3. In the algorithm of §A.3, if Iv [t] > 0 for a node v, then its importance Iv′ [t] after the transfer is also guaranteed to be positive. However, in the algorithm above the importance of a node can become zero for a sufficiently large value of α. Hence, the algorithm above is more unfair compared to the one in §A.3. However, unlike the algorithm in §A.3 which only has asymptotic sybil resistance (Property 7), the algorithm above has sybil resistance for any constant α > 0. The algorithm above is also more computationally efficient compared to the algorithm in §A.3. In practice, the algorithm presented above may be used with a reasonable value for α to guarantee that the importance of nodes at the bottom of the DAG do not go to zero. E.g., if it is known (or, enforced) that the total stake of any DAG D[t] is at most s for 0 < s < 1, we can use α = ϵ/(2s).
A.6
Example
Consider the DAG shown in Fig. 5a. The stake and the initial importance of the nodes after tax is shown in Fig. 5b. Consider node e. The ancestors of node e are the nodes a, b, c and d. The fractions of importance that node e transfers to 41
each of those nodes are given by: ia = 1 − (1 − α)sa /ϵ ib = ia
(1 − α)sa /ϵ (1 − (1 − α)sb /ϵ ) 3(1 − (1 − α)sa /ϵ )
ic = ia
(1 − α)sa /ϵ (1 − (1 − α)sc /ϵ ) (1 − α)sb /ϵ (1 − (1 − α)sc /ϵ ) + i b 3(1 − (1 − α)sa /ϵ ) 2(1 − (1 − α)sb /ϵ )
id = ia
(1 − α)sa /ϵ (1 − (1 − α)sd /ϵ ) . 3(1 − (1 − α)sa /ϵ )
(28)
Using ϵ = 0.001 and α = ϵ/2, we have ia = 0.049, ib = 0.030, ic = 0.011, id = 0.044. Thus, node e transfers a total fraction of 0.134 of its importance to its ancestor nodes. We can similarly compute the fraction of importance transferred by each of the nodes b, c and d to their ancestors. Node b transfers a fraction 0.049 of its importance to node a. Node c transfers a fraction 0.049 to node a and a fraction 0.030 to node b. Node d transfers a fraction 0.049 to node a. The final importance of nodes a, b, c, d and e after the transfer is 0.077, 0.195, 0.093, 0.192 and 0.043 respectively.
B
Analysis
B.1
Proof of Theorem 2
P P ′ Proof. Since (u,v):u∈S,v∈V \S w(u,v) [t] < ϕ u∈S Iu [t], the set S is excluded ′ from the maximal expanderPsubgraph G [t] (if it exists) for all t. Therefore, the nodes in S effectively lose u∈S Iu [t]β importance in tax each round, without the importance being refunded at the end P of the round. The maximum amount of importance available with V \S is 2 − u∈S Iu [t](1 − β) after tax. Therefore, the maximum that S can receive in a round from V \S is at P amount of importance P most α( u∈S su )(2 − u∈S Iu [t](1 − β))/ϵ. Assuming a large initial importance for S, the importance of S continues to decrease until the importance lost by S due to tax is smaller than the importance gained by S from V \S. That is, X α X ( su )(2 − Iu [t](1 − β)), ϵ u∈S u∈S u∈S P X 2α u∈S su P P =⇒ Iu [t] ≤ . β(ϵ − α u∈S su ) + α u∈S su X
Iu [t]β ≤
(29) (30)
u∈S
⊔ ⊓ 42
B.2
Proof of Lemma 1
P Proof. At the beginning of each round the collector gains v∈V Iv [t]β importance from taxes. At the end of a round the collector loses P X X Iv′ [t]( v∈G′ [t] sv )β(Ic [t] + (2 − Ic [t])β) P = ( sv )β(Ic [t] + (2 − Ic [t])β) ′ v∈G′ [t] Iv [t] ′ ′ v∈G [t]
v∈G [t]
(31) importance to G′ [t]. Therefore, X X Ic [t + 1] = Ic [t] + Iv [t]β − ( sv )β(Ic [t] + (2 − Ic [t])β), v∈V
(32)
v∈G′ [t]
P for all t ≥ 0. Since importance is conserved, we have v∈V Iv [t] = 2 − Ic [t] for all t ≥ 0. Therefore, Equation (32) becomes X Ic [t + 1] = Ic [t] + (2 − Ic [t])β − ( sv )β(Ic [t] + (2 − Ic [t])β). (33) v∈G′ [t]
P P We have Ic [t + 1] ≥ Ic [t] if Ic [t] ≤ (2 − 2β v∈G′ [t] sv )/(1 + v∈G′ [t] sv (1 − β)). Since, P 2 − 2β v∈G′ [t] sv 2 − 2β P , (34) ≥ 1 + v∈G′ [t] sv (1 − β) 2−β if Ic [t] drops below (2−2β)/(2−β), Ic [t+1] is guaranteed to be bigger than Ic [t]. If Ic [t] is slightly above the threshold of (2 − 2β)/(2 − β), Ic [t + 1] can undershoot below the threshold by a maximum of 2β after which it must increase. Therefore, we conclude that Ic [t] ≥
2 − 2β − 2β ≈ 1, 2−β
⊔ ⊓
for all time t > 0. B.3
(35)
Proof of Theorem 3
Proof. Consider the subgraph G[t](S ∪ S ′ ) of G[t] spanned by S ∪ S ′ for any s′ ⊆ V \S. The conductance of the cut S ′ in the subgraph is at most P P ϕout min( v∈S Iv′ [t], v∈S ′ Iv′ [t]) P P < ϕ. (36) min( v∈S Iv′ [t], v∈S ′ Iv′ [t]) Therefore, G′ [t](S ∪ S ′ ) cannot be a ϕ-expander for any S ′ ⊆ V \S. On the other hand, the subgraph spanned by S is an expander with a total stake > 0.5. Hence, G′ [t] = G[t](S). 43
P P At time t, S loses v∈S Iv [t]β importance to the collector. P It gains ( v∈S sv )β(Ic [t]+ (2−Ic [t])β) importance back as a tax refund. It also loses (u,v):u∈S,v∈V \S I(u,v) [t] importance to V \S through collaborations (if any). Hence, X X X X Iv [t + 1] = Iv [t](1 − β) + ( sv )β(Ic [t] + (2 − Ic [t])β) − I(u,v) [t] v∈S
v∈S
≥
X
v∈S
Iv [t](1 − β) + (
v∈S
X
(u,v):u∈S,v∈V \S 2
sv )
v∈S
3
β(2 − 4β + 6β − 2β ) − 2−β
X
I(u,v) [t],
(u,v):u∈S,v∈V \S
(37) where the second inquality follows from Lemma 1. From inequality (37) above, we have X X wv [t + 1] − α(1 − α)t+1 Iv [0] ≥ wv [t](1 − β) v∈S
+(
X
v∈S
v∈S
β(2 − 4β + 6β 2 − 2β 3 ) (1 − (1 − α)t+1 ) − sv ) 2−β
X
w(u,v) [t]
(u,v):u∈S,v∈V \S
(38) ≥
X
wv [t](1 − β)
v∈S
+(
X
v∈S
sv )
X β(2 − 4β + 6β 2 − 2β 3 ) (1 − (1 − α)t+1 ) − ϕout Iv′ [t] 2−β v∈S
(39) ≥
X
wv [t](1 − β)
v∈S
+(
X
v∈S
sv )
β(2 − 4β + 6β 2 − 2β 3 ) (1 − (1 − α)t+1 ) − ϕout , 2−β (40)
where inequality (39) follows due to the weak collaboration between S and V \S and inequality (40) follows from Lemma 1. Taking lim inf on both sides of the inequality above and using the property that lim inf t→∞ (x[t] + y[t]) ≥ lim inf t→∞ x[t] + lim inf t→∞ y[t] for any two sequences x[t] and [t], we have lim inf t→∞
X v∈S
wv [t] ≥ (1 − β) lim inf t→∞
=⇒ lim inf t→∞
X
wv [t] + (
v∈S
X
X
sv )
β(2 − 4β + 6β 2 − 2β 3 ) − ϕout 2−β
sv )
(2 − 4β + 6β 2 − 2β 3 ) ϕout − . 2−β β
v∈S
wv [t] ≥ (
v∈S
X
v∈S
(41) ⊔ ⊓
44