Abstract

Proof-of-stake (PoS) has emerged as a natural alternative to the resource-intensive Proof-of-Work (PoW) blockchain, as was recently seen with the Ethereum Merge. PoS-based blockchains require an initial stake distribution among the participants. Typically, this initial stake distribution is called bootstrapping. This paper argues that existing bootstrapping protocols are prone to centralization. To address centralization due to bootstrapping, we propose a novel game Γbootstrap. Next, we define three conditions: (i) Individual Rationality (IR), (ii) Incentive Compatibility (IC), and (iii) (τ,δ,ϵ)− Decentralization that an emph{ideal} bootstrapping protocol must satisfy. (τ,δ,ϵ) are certain parameters to quantify decentralization. Towards this, we propose a novel centralization metric, C-NORM, to measure centralization in a PoS System. We define a centralization game -- Γcent, to analyze the efficacy of centralization metrics. We show that C-NORM effectively captures centralization in the presence of strategic players capable of launching Sybil attacks. With C-NORM, we analyze popular bootstrapping protocols such as Airdrop and Proof-of-Burn (PoB) and prove that they do not satisfy IC and IR, respectively. Motivated by the Ethereum Merge, we study W2SB (a PoW-based bootstrapping protocol) and prove it is ideal. In addition, we conduct synthetic simulations to empirically validate that W2SB bootstrapped PoS is decentralized.

Abstract

Proof-of-Work is a consensus algorithm where miners solve cryptographic puzzles to mine blocks and obtain a reward through some Block Reward Mechanism (BRM). PoW blockchain faces the problem of centralization due to the formation of mining pools, where miners mine blocks as a group and distribute rewards. The rationale is to reduce the risk (variance) in reward while obtaining the same expected block reward. In this work, we address the problem of centralization due to mining pools in PoW blockchain. We propose a two-player game between the new miner joining the system and the PoW blockchain system. We model the utility for the incoming miner as a combination of (i) expected block reward, (ii) risk, and (iii) cost of switching between different mining pools. With this utility structure, we analyze the equilibrium strategy of the incoming miner for different BRMs: (a) memoryless -- block reward is history independent (e.g., Bitcoin) (b) retentive: block reward is history-dependent (e.g., Fruitchains). For memoryless BRMs, we show that depending on the coefficient of switching cost c, the protocol is decentralized when c=0 and centralized when c>c–. In addition, we show the impossibility of constructing a memoryless BRM where solo mining gives a higher payoff than forming/joining mining pools. While retentive BRM in Fruitchains reduces risk in solo mining, the equilibrium strategy for incoming miners is still to join mining pools, leading to centralization. We then propose our novel retentive BRM -- Decent-BRM. We show that under Decent-BRM, incoming miners obtain higher utility in solo mining than joining mining pools. Therefore, no mining pools are formed, and the Pow blockchain using Decent-BRM is decentralized.

Abstract

This paper studies the contextual multi-armed bandit problem with fairness and privacy guarantees in a federated setting. It proposes a collaborative algorithm, Fed-FairX-LinUCB that achieves sublinear fairness regret and can be adapted to ensure differential privacy. The key challenge is designing a communication protocol that balances privacy and regret. The proposed protocol achieves both sub-linear fairness regret and effective use of privacy budget. Experiments validates the efficacy of both Fed-FairX-LinUCB and its private counterpart, Priv-FairX-LinUCB.

Abstract

Proof-of-Stake(PoS) based blockchain protocols have gained popularity due to their higher throughput and low carbon footprint when compared with Proof-of-Work blockchain protocols. The two major parts of blockchain protocols are the selection of the next block proposer and the selection of the longest chain. In PoS the block publishers are selected based on their relative stake. However, PoS-based blockchain protocols may face vulnerability against Fully Adaptive Corruptions. This paper proposes a novel PoS-based blockchain protocol, QuickSync, to achieve security against Fully Adaptive Corruptions while improving performance. Towards this, we propose a metric for each block: block power. We compute the chain power of a chain as the sum of block powers of all the blocks comprising the chain. The chain selection rule selects the chain with the highest chain power as the valid chain. Since the block proposer is not selected upfront, this scheme is resilient to fully adaptive corruptions, which we also show formally. We also ensure that our block power mechanism is resistant to Sybil attacks. We prove the security of QuickSync by showing that it satisfies the common prefix, chain growth, and chain quality properties. Our analysis demonstrates that QuickSync performs better than Bitcoin by order of magnitude on both transactions per second and time to finality.

Abstract

The emergence of smart grid technology has opened the door for wide-scale automation in decision-making. A distribution company, an integral part of a smart grid system, has to procure electricity from the wholesale market and then sell it to customers in the retail market by publishing attractive tariff contracts. It can deploy autonomous agents to make decisions on its behalf. In this work, we describe the tariff contracts generation strategy of one such autonomous agent, which is based on a Contextual Multi-armed Bandit (ConMAB) based learning technique to generate tariff contracts for various types of customers in the retail market of smart grids. We particularly utilize the Exponential-weight algorithm for Exploration and Exploitation (EXP-3) for ConMAB-based learning. We call our proposed strategy GenerateTariffs-EXP3. Our previous work shows that maintaining an appropriate market share in the retail market yields high net revenue. Thus, we first present a game-theoretic analysis that determines an optimal level of market share. Then we train our proposed strategy to achieve and maintain the suggested level of market share by adapting to the market situation and revising the tariff contracts periodically. We validate our proposed strategy in PowerTAC, a close-to real-world smart grid simulator, and showcase that it is able to maintain the suggested market share.