Proof of Prestige

Michał Król; Alberto Sonnino; Mustafa Al-Bassam; Argyrios G. Tasiopoulos; and Ioannis Psaras, University College London (UCL)

IEEE Blockchain Technical Briefs, September 2019

Discuss this topic on IEEE Collabratec

 

Introduction

Cryptocurrencies rely heavily on the blockchain technology that acts as a peer-to-peer, distributed database. In this database, each cryptocurrency stores essential information such as the amount of money of each user and a list of transactions. However, for the system to work correctly, the database must remain consistent across multiple copies. This is achieved by using different kinds of consensus protocols.

Multiple cryptocurrencies (i.e., Bitcoin and Ethereum) are secured using Proof-of-Work (PoW) protocols, initially introduced by Bitcoin [8]. In PoW, miners try to solve difficult cryptographic puzzles. Once a miner finds a solution to the puzzle, they gain the right to append a new block to the blockchain, discover (mine) new coins and collect fees from transactions included in the block. PoW incentivizes users to commit resources to secure the transactions and binds users’ mining power to a physical resource (i.e., computation capacity), thus preventing the generation of multiple fake identities by one party (Sybil Attack).

While PoW proved to be able to secure a global payment system, it has several drawbacks, the first one being inefficient use of resources. Bitcoin’s PoW consumes huge and growing amounts of electricity surpassing the electricity consumption of entire countries. Proof-of-Stake (PoS) was recently proposed to deal with this problem [5–7]; the power of each miner and thus their probability of mining a new block is proportional to their stake—the amount of coins in the wallet. The winner can therefore be chosen using a variation of the weighted round-robin algorithm without wasting resources on solving cryptographic puzzles [6]. While being much more resource saving, PoS allows rich users to collect the majority of the fees and concentration of too much power within few nodes causes the network to lose its decentralization.

In PoW, users perform tasks (solve the crypto-puzzles) that serve only securing the blockchain and are useless outside of the system. However, a recent trend sees cryptocurrencies as an incentive method for users to perform useful work [2,3]. For instance, Filecoin [4] rewards miners for storing files of other users, while Golem [1] allows to rent out processing power and perform someone’s computation-heavy tasks for a reward. The vision is to create a distributed system, where miners are incentivized to participate in the network, do useful work, secure the transactions and automatically receive rewards when tasks are completed. Apart from Quality of Service comparable to centralized solutions, there are two additional factors that must be taken into account in decentralized systems to make them successful. First, the system must be economically viable, which means that miners need to collect lower fees than their cloud-based counterparts such as Google or Amazon. For miners using general-purpose hardware this can be difficult to achieve. Second, the system must be able to automatically verify tasks, to release payments only when the tasks are truly completed. While completion of some tasks (such as file storage) can be proved to a 3rd party (e.g., using zk-SNARKS), in many cases this is impossible (e.g., a file transfer between two untrusted parties).

To address those issues in PoS blockchains, we have developed Proof of Prestige (PoP) that aims to be a building block of cryptocurrencies based on useful work [9]. In our system, users mining power increases when performing useful work allowing them to collect more coins in the future. Furthermore, users for whom tasks were performed do not have to pay workers with coins, making the system a more appealing alternative for cloud-based, fee-free systems. Finally, PoP can be used with a wide range of tasks that are difficult to prove and remains secure again Sybil and collusion attacks.

Proof of Prestige

In PoP, apart from coins, each user has a certain amount of prestige associated with their account. Prestige is much more volatile than coins, can be considered as a renewable resource and is slowly generated from money. Prestige is important, because it determines the probability of mining the next block, similar to stake in PoS. The probability of each user mining a block is thus proportional to their prestige. Mining a new block, in turn, allows users to collect transaction fees, discover new coins and thus increase their total amount of coins. Prestige and coins are thus related and can influence one another.

Each coin generates one prestige point per block for its current owner.  At the same time, in order to avoid prestige increasing indefinitely, we introduce prestige decay. The decay determines what percentage of current prestige is lost with each block. The amount of prestige can thus grow, but only up to a certain threshold where prestige generated from coins evens the decay. We call this threshold a static value (Figure 1). The more coins, the higher the corresponding static value.

Figure 1. Prestige Fluctuation over time. Spikes indicate file transfers. Increasing prestige indicates a node has sent a file, while decreasing prestige indicates a node has received a file.

To get more prestige, users have to perform some useful work acknowledged by other users. Imagine file distribution tasks. We would like to incentivize users to distribute some content in a peer-to-peer manner without file recipients having to spend their coins. In PoP, when a sender transmits a file to a recipient, a predefined amount of prestige will be transferred back from the recipient to the sender. Let’s say that Alice and Bob have 10 coins and 100 prestige each. In this case the static value is 100 prestige for both of them. When Alice sends a file to Bob, her prestige will be increased to 110, while Bob’s prestige will now be 90. The system will effectuate the prestige transfer only if both Bob and Alice confirm the file transfer. The atomic swap file transfer for confirmation can be achieved using existing fair exchange protocols [3, 10].

This effectively means that Alice will now have increased mining power, while Bob will be less likely to mine the new block (and be rewarded by the system). Note, however, that this is only a temporary state. Bob is now below his static value, which means that his prestige will start increasing over time. On the other hand, Alice is now above her static value, so the amount of her prestige will gradually decline. After a certain amount of time, they will both reach their static values again. However, before that point is reached, Alice will have increased chance of mining new blocks and collect rewards. In PoP, users who invested heavily into the system by acquiring tokens, collect higher rewards. However, by performing multiple services for others, even workers with low amount of coins can collect significant amounts of prestige surpassing rich, but lazy users.

Furthermore, for cases where benefiting from a service, allows the beneficiary to perform useful work for others (e.g., seeding in a content distribution system), we introduce the concept of Progressive Mining. In Progressive Mining, contributors are rewarded by their own useful work, but also for work performed by their beneficiaries. That is, if Alice performs a service for Bob, Alice will receive some prestige for each service performed by Bob and for other users (Figure 2). The scheme can be seen as a Directed Acyclic Graph (DAG) with users as nodes and edges representing useful work performed for subsequent users. In this case, Prestige is flowing from the leaves towards the root with intermediary nodes retaining a part of it.  The amount of retained value is based on each node’s own prestige compared to the prestige sum of its predecessors. It is fully resistant to topology manipulation using Sybil identities that do not have any prestige. Users also cannot increase their prestige gain by spreading their coins (and thus gain prestige) over several artificial identities.

Figure 2. Comparison between simple and progressive mining.

Conclusion

Introducing a renewable resource (i.e., the temporary increase/decrease function integrated in prestige) allows us to securely reward users performing useful work for other system participants without making beneficiaries spend their coins. File propagators can now send files to multiple users, increase their prestige and have a higher probability of receiving rewards from the network. On the other hand, recipients can receive unlimited number of files (being limited only in terms of frequency of receiving files).

In contrast to Proof of Stake, PoP allows poor, but active users to acquire significant amount of prestige and collect rewards. Furthermore, the scheme can be used with a vast variety of tasks. The whole scheme protects against Sybil attacks. Fake identities will not have any prestige to transfer, so they cannot provide any benefits for the miners. Recall that prestige is bought with coins, hence, in order to have prestige, the fake accounts will need to be “loaded” with virtual coins. Effectively, malicious users would have to pay in order to create fake identities, clearly not an attractive route for fraudsters.

 

References

[1] “Golem whitepaper.” https://golem.network/doc/Golemwhitepaper.pdf, 2016.

[2] Hanke, Timo, Mahnush Movahedi, and Dominic Williams. "Dfinity technology overview series, consensus system." arXiv preprint arXiv:1805.04548 (2018).

[3] Al-Bassam, Mustafa, et al. "Airtnt: Fair exchange payment for outsourced secure enclave computations." arXiv preprint arXiv:1805.06411 (2018).

[4] Protocol Labs. Filecoin: A Decentralized Storage Network. August 2017.

[5] I. Bentov, R. Pass, and E. Shi, “Snow white: Provably secure proofs of stake.,” IACR Cryptology ePrint Archive, vol. 2016, p. 919, 2016.

[6] B. David, P. Gazi, A. Kiayias, and A. Russell, “Ouroboros praos: An adaptively-secure, semi-synchronous proof-of-stake protocol,” IOHK paper, 2017.

[7] A. Kiayias, A. Russell, B. David, and R. Oliynykov, “Ouroboros: A provably secure proof-of-stake blockchain protocol,” in Annual International Cryptology Conference, pp. 357–388, Springer, 2017.

[8] S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” 2008.

[9] M. Król, A. Sonnino, M. Al-Bassam, A. Tasiopoulos, and I. Psaras,  “Proof-of-Prestige A Useful Work Reward System for Unverifiable Tasks,” in IEEE International Conference on Blockchain and Cryptocurrency, IEEE, 2019.

[10] Dziembowski, Stefan, Lisa Eckey, and Sebastian Faust. "Fairswap: How to fairly exchange digital goods." Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2018.

 

---

 

Michał Król is a research associate in the Electrical and Electronic Engineering Department at University College London (UCL). He received his Ph.D. degree in computer science from University Grenoble-Alpes, France, in 2016. His research focus is on the next-generation Internet architecture, information-centric connectivity, and secure device-to-device communication. His current research interests include a variety of topics ranging from distributed ledgers, blockchain, trusted execution environments, and network security.

 

Alberto Sonnino is a Ph.D student in Security Engineering at University College London (UCL). His research interests are in privacy enhancing technologies, scalable distributed ledgers, and cryptography. He was a co-founder and researcher at chainspace.io, which builds a scalable smart contract platform; he is now a Research Scientist at the Blockchain team of Facebook based in London.

 

 

Mustafa Al-Bassam is a PhD student in the Department of Computer Science at University College London (UCL). His research interests include the intersections of peer-to-peer systems, distributed ledgers and information security. His recent research has been focused on scaling distributed ledgers at the base layer, and consensus protocols.

 

 

Argyrios G. Tasiopoulos received the B.Sc. in Informatics and the M.Sc. in Computer Science both from the AUEB. He obtained his Ph.D. degree in Electronic and Electrical Engineering from the University College London, in 2018. He is currently a Research Associate at the EE department of UCL. His research efforts lies at the intersection of operations research, telecommunications, and economics. He is particularly interested in market designs for delivering the next generation of network applications.

 

Ioannis Psaras is an EPSRC Early Career Fellow and Lecturer on computer networks in the Electrical and Electronic Engineering Department at UCL. His interests are in the areas of Internet routing and congestion control, information-centric networks, edge and fog computing, and mobile, opportunistic networks. Lately, he has been investigating the applications of distributed ledger technology and blockchains to networking problems. He has received five Best Paper Awards for his contributions to high-quality conferences and workshops, all in the area of information-centric networks and mobile communications and edge-computing.

 

Editor:

Dr. Shucheng Yu is an Associate Professor of Electrical and Computer Engineering at Stevens Institute of Technology. Before he joined Stevens, Dr. Yu was an associate professor of Computer Science at the University of Arkansas at Little Rock, where he also served as the chair of the Computer Science department and the director of the Computational Research Center of the university. He received his PhD in Electrical and Computer Engineering from Worcester Polytechnic Institute in 2010. His research interest is on cybersecurity in general, with recent focuses on security and privacy for data analytics, security & privacy in smart systems, wireless systems and security. He has published over sixty impactful research articles in academic journals and conference proceedings which have received numerous citations. He has been the editor or guest editor for four international journals, and at the organizing committee for over ten international conferences including IEEE Infocom and IEEE Globecom. He serves the board of trustee for Wireless and Optical Communication Conference (WOCC) and is a member of IEEE and ACM.