Source-linked AI summary
Auction Mechanisms in Cloud/Fog Computing Resource Allocation for Public Blockchain Networks
Yutao Jiao, Ping Wang, Dusit Niyato, Kongrath Suankaewmanee
TL;DR
PoW blockchain miners with limited local resources need cloud/fog computing, creating a resource-allocation and pricing problem under competition and network effects. The paper develops truthful auction mechanisms for constant- and multi-demand bidding, achieving optimal social welfare in the constant-demand case and approximate, efficient welfare maximization in the multi-demand case. Simulations show practical resource-trading strategies for the CFP and guidance for blockchain protocol design.
Problem
Limited mobile-device computing resources motivate cloud/fog offloading, but allocating and pricing resources among competing miners must account for blockchain network effects and allocative externalities.
Method
The paper models hash power and network effects from a real-world mobile blockchain experiment and designs auction mechanisms for constant-demand and multi-demand miners.
Results
The constant-demand auction achieves optimal social welfare, while the multi-demand problem is NP-hard and receives an approximate mechanism that is truthful, individually rational, and computationally efficient.
Takeaways & Limitations
The proposed mechanisms support practical and efficient computing-resource trading strategies for the CFP and offer guidance for blockchain protocol design.
Takeaways & Limitations
The model considers energy and computational constraints under an ideal communication environment, leaving communication constraints important for practical implementation.
Abstract
from arXiv · showhide
As an emerging decentralized secure data management platform, blockchain has gained much popularity recently. To maintain a canonical state of blockchain data record, proof-of-work based consensus protocols provide the nodes, referred to as miners, in the network with incentives for confirming new block of transactions through a process of "block mining" by solving a cryptographic puzzle. Under the circumstance of limited local computing resources, e.g., mobile devices, it is natural for rational miners, i.e., consensus nodes, to offload computational tasks for proof of work to the cloud/fog computing servers. Therefore, we focus on the trading between the cloud/fog computing service provider and miners, and propose an auction-based market model for efficient computing resource allocation. In particular, we consider a proof-of-work based blockchain network. Due to the competition among miners in the blockchain network, the allocative externalities are particularly taken into account when designing the auction mechanisms. Specifically, we consider two bidding schemes: the constant-demand scheme where each miner bids for a fixed quantity of resources, and the multi-demand scheme where the miners can submit their preferable demands and bids. For the constant-demand bidding scheme, we propose an auction mechanism that achieves optimal social welfare. In the multi-demand bidding scheme, the social welfare maximization problem is NP-hard. Therefore, we design an approximate algorithm which guarantees the truthfulness, individual rationality and computational efficiency. Through extensive simulations, we show that our proposed auction mechanisms with the two bidding schemes can efficiently maximize the social welfare of the blockchain network and provide effective strategies for the cloud/fog computing service provider.
I. INTRODUCTION
The paper motivates auction-based cloud/fog resource allocation for PoW blockchain miners and incorporates competition, network effects, and allocative externalities. It formulates mechanisms for constant- and multi-demand bidding, supported by characteristic functions, optimal or approximate algorithms, and simulations.
- Motivation: Mobile and IoT devices cannot afford the continuous high computing power required for PoW mining, motivating cloud/fog offloading.Cloud/fog services can alleviate this computational bottleneck and enable blockchain-based DApps.
- Motivation: The resource market must balance service congestion and provider operating costs against maintaining blockchain integrity and incentivizing miners.The paper frames resource allocation and pricing as social-welfare problems between the CFP and miners.
- Research focus: The auction model incorporates competition among miners, blockchain network effects, and allocative externalities into resource allocation.Allocative externalities occur when allocation affects miners’ valuations.
- Mechanisms: The paper studies constant-demand and multi-demand bidding schemes; the former admits an optimal algorithm, while the latter is NP-hard and requires approximation.The multi-demand formulation is equivalent to non-monotone submodular maximization with knapsack constraints.
- System model: Real-world mobile blockchain experiments define and verify hash-power and network-effects functions for the system model.The functions relate mining success to computing power and blockchain security to total invested resources.
- Evaluation: Simulations indicate that the proposed mechanisms support practical CFP resource-trading strategies and provide guidance for blockchain protocol design.The paper presents this as the first investigation of blockchain resource management and pricing in an auction-based market.
A. Cloud/Fog Computing Resource Trading
The resource-trading model describes how miners’ allocated computing resources affect hash power, mining rewards, propagation, and blockchain network value. It connects these relationships to a CFP-operated market for supporting blockchain-based DApps.
- System assumptions: The model assumes one CFP supplies computing resources to miners who use blockchain-based DApps to record and verify transactional data.Miners are computationally lightweight devices and do not execute mining tasks locally.
- Mining model: Miner hash power is calculated from its allocated resources and demand, while its mining probability depends on other miners’ allocated computing resources.The resulting probability is described as a linear fractional function of resource allocation.
- Rewards: A miner’s token reward combines a fixed mining bonus and a transaction fee determined by block size and a predefined fee rate.The reward is received when mining succeeds and the block reaches consensus promptly.
- Mining model: A larger block requires more propagation and verification time, increasing delay and the chance that the block becomes orphaned.The mining tournament follows a Poisson process with average block time λ.
- Business ecosystem: The blockchain developer sets the mining bonus, transaction-fee rate, and average block time while miners perform mining in the deployed network.Rewards may originate from tokens paid by DApp users to the blockchain network.
- Network effects: Greater participation and resource investment improve blockchain security, increasing network value and therefore the value miners assign to rewards.The network-effects function is monotonically increasing with diminishing returns over the feasible domain.
D. Miner’s Valuation on Cloud/Fog Computing Resources
The paper models miners’ cloud/fog resource valuations before and after allocation, then uses social-welfare maximization to allocate resources and set prices. The model is illustrated through a blockchain-based mobile data crowdsourcing application.
- Valuation Model: Miners submit bids based on expected rewards and requested resource quantities before observing network effects or other miners’ allocations.Their ex-ante valuation is based on protocol parameters, expected reward, and demand; network effects are evaluated after allocation.
- Resource Allocation: The CFP maximizes social welfare by selecting winning miners and determining prices under its available resource constraint.Social welfare is defined from miners’ ex-post valuations and the CFP’s total service cost.
- Auction Design: The auction considers constant-demand and multi-demand schemes while targeting truthfulness, individual rationality, and computational efficiency.The constant-demand scheme fixes each miner’s requested quantity, whereas the multi-demand scheme allows multiple requested quantities.
- Example Application: A mobile crowdsourcing blockchain lets users trade sensing data through smart contracts while miners purchase cloud/fog resources to support proof-of-work.Winning miners receive allocated resources, join the miner network, and contribute to block verification and consensus.
IV. AUCTION-BASED MECHANISM FOR CONSTANT-DEMAND MINERS
For miners requesting the same fixed quantity, the CDB auction selects winners by increasing social welfare and calculates service prices using VCG payments. The mechanism is globally optimal, truthful, computationally efficient, and individually rational.
- Constant-Demand Formulation: In the constant-demand scheme, every miner requests the same quantity q, and the CFP optimizes winner selection and allocation.Each miner’s demand is q units with q ∈ (0, D).
- Truthful Payments: The mechanism is truthful because it combines monotone winner selection with VCG-based critical payments.For each winner, the payment is computed by excluding that miner and re-executing winner selection to measure its social cost.
- Winner Selection: The CDB auction sorts bids in descending order and sequentially adds miners while social welfare remains nondecreasing and nonnegative.The algorithm outputs the resulting winner set M and allocation x.
- Optimality: Algorithm 1 produces a globally optimal resource allocation for the constant-demand social-welfare maximization problem.The optimality claim is established through a contradiction argument based on the algorithm’s winner-set construction.
- Efficiency and Rationality: The CDB auction is computationally efficient and individually rational, with total complexity O(min^3(D/q, N) + N log N).Sorting costs O(N log N), while repeated winner selection determines the polynomial-time payment calculation.
V. AUCTION-BASED MECHANISMS FOR MULTI-DEMAND MINERS
The multi-demand scheme extends the auction setting to miners requesting multiple quantities of cloud/fog computing resources. This provides a more general demand model than the constant-demand case.
- Multi-Demand Setting: The multi-demand setting considers miners that request multiple quantities of cloud/fog computing resources.It is introduced as a more general scenario than the fixed-demand case.
- Demand Model: Miners in this setting have non-fixed resource requests rather than a single common demand quantity.The passage contrasts this scenario with the earlier constant-demand formulation.
- Auction Scope: The section focuses on auction mechanisms for allocating cloud/fog resources when miner demands are heterogeneous.The multi-demand scheme addresses variation in the quantities requested by miners.
A. Social Welfare Maximization for the Blockchain Network
The multi-demand winner-selection problem is NP-hard and can be expressed as non-monotone submodular maximization with a knapsack constraint. The proposed FRLS-based approach is computationally efficient and individually rational but does not guarantee truthful bidding.
- The winner-selection problem is a nonlinear integer program with linear constraints, making optimal solution finding NP-hard.
- The social welfare function S(M) is submodular because its marginal contribution S_u(M) is monotonically decreasing.
- The multi-demand formulation is non-monotone submodular maximization with knapsack constraints imposed by the limited resource supply.
- The FRLS algorithm uses fractional relaxation, local search, and rounding to obtain a (0.2 −η)-approximate solution.
- The FRLS auction is polynomial-time and individually rational, but it cannot guarantee truthfulness.
B. Multi-Demand miners in Blockchain networks (MDB) Auction
The MDB auction targets truthful allocation for multi-demand miners by combining single-minded bidding with monotonicity and critical-payment requirements. Its design introduces marginal social welfare density as the basis for allocation and payment decisions.
- The MDB auction restricts bidders to single-minded preferences, allocating each winner exactly its requested d_i items and nothing to losing bidders.
- Truthfulness requires monotonicity and critical payment in the multi-unit, single-minded setting.
- Marginal social welfare density measures miner i’s marginal social welfare contribution and supports the MDB auction’s allocation design.
1) Auction design:
The MDB auction greedily selects multi-demand winners by ordering miners according to marginal social welfare density, then determines winner-specific payments through a re-executed selection process.
- The MDB auction takes miners’ demand and bid profiles as input and outputs resource allocations x and service prices p.
- The allocation procedure repeatedly selects the remaining miner with maximum density while respecting capacity and nonnegative-density conditions.
- Miners are sorted in non-increasing density order, and winners are selected while total demand remains within capacity D.
- For each winner, the auction re-executes selection without that miner to determine a payment threshold based on alternative winners’ densities.
- The resulting ex-ante price and final payment are derived from the winner’s minimum bid and allocative externalities.
- The MDB auction is presented as computationally efficient, individually rational, and truthful.
2) Properties of MDB Auction:
The MDB auction satisfies computational-efficiency, individual-rationality, and truthfulness properties. Truthfulness is established through monotone selection and critical-value payments, with submodularity supporting the monotonicity arguments.
- The MDB auction is computationally efficient, with winner selection taking O(N^2) time and the overall algorithm dominated by an O(N^3) payment process.
- The MDB auction is individually rational, ensuring that winners’ payments do not exceed their ex-ante values.
- The MDB auction is truthful because its selection rule is monotone and its ex-ante payment is a critical value.
- A higher bid increases a miner’s density and cannot reduce its winning prospects in the density ordering.
- A miner’s density decreases with its demand, supporting monotonicity with respect to requested resource quantity.
- The critical ex-ante payment is the minimum bid needed to remain a winner when other miners’ bids are fixed.
VI. EXPERIMENTAL RESULTS AND PERFORMANCE EVALUATION
The section evaluates the proposed auction mechanisms through experiments and simulations, examining function verification, social-welfare performance, and parameter impacts.
- Experiments verify the proposed hash power and network effects functions before evaluating auction performance.The evaluation also examines social-welfare maximization and provides decision-making strategies for the CFP and blockchain developer.
A. Verification for Hash Power Function and Network Effects Function
The experiments test the hash power and network effects functions using a mobile blockchain implementation with miners connected to a computing server.
- A mobile blockchain client was implemented on three Android devices acting as miners requesting computing service from a server.
- Hash power is tested by varying one miner’s CPU demand while fixing the other two miners’ demands at 40 and 60.The experiment measures the probability of successfully mining a block under different computing-resource amounts.
- Network effects are tested by adding a fixed-power attacker and varying honest miners’ total CPU resources.Attack success is measured by counting fake blocks joining the chain per 10,000 generated blocks.
B. Numerical Results
The numerical evaluation compares auction mechanisms under controlled demand distributions and default parameters, using repeated measurements with confidence intervals.
- Each miner’s block size is uniformly distributed over (0, 1024], while MDB and FRLS miners submit demands uniformly distributed over [β1D, β2D].
- 600 instances are averaged for each measurement except Fig. 6a, with associated 95% confidence intervals reported.The default parameter values are given in Table II.
- Setting q = 10, β1 = 0, and β2 = 0.02 makes expected MDB demand equal to constant CDB demand, enabling performance comparison.
- Table III compares MDB and FRLS auctions in social-welfare maximization.
1) Evaluation of MDB auction versus FRLS auction in terms of social welfare maximization:
The evaluation compares MDB, FRLS, and CDB auctions across social welfare, satisfaction, parameter sensitivity, miner utility, and demand dispersion. Results show tradeoffs between welfare, fairness, computational economics, and demand flexibility.
- Evaluation of MDB auction versus FRLS auction in terms of social welfare maximization:: MDB produces lower social welfare than FRLS for few miners but slightly higher welfare as the interested-miner group grows.MDB preserves individual rationality and truthfulness, whereas FRLS has only a worst-case theoretical approximation guarantee.
- Evaluation of MDB auction versus FRLS auction in terms of social welfare maximization:: As N increases, social welfare rises while satisfaction rate falls and welfare growth slows because competition intensifies and winner density decreases.
- Evaluation of MDB auction versus FRLS auction in terms of social welfare maximization:: MDB achieves more social welfare than CDB, while CDB is relatively fairer because MDB relaxes demand restrictions.
- 3) Impact of the unit cost c, the fixed bonus T , the transaction fee rate r and the block time: Social welfare decreases linearly as unit cost c increases, rises nearly proportionally with fixed bonus T and transaction fee rate r, and increases with block time λ.Increasing T and r amplifies the welfare difference between CDB and MDB; increasing λ yields diminishing marginal gains.
- 4) Miner’s utility and individual demand constraints in the MDB auction:: A miner’s utility remains zero until its true demand exceeds a selection threshold, after which winning yields positive utility.For the same demand, larger block size gives higher utility and makes selection easier in MDB.
- 4) Miner’s utility and individual demand constraints in the MDB auction:: Social welfare increases with demand dispersion θ as miners gain more freedom to submit desired demands in MDB.
- The proposed CDB and MDB auctions are truthful, individually rational, computationally efficient, and designed to solve social-welfare maximization.The paper models allocative externalities from miner competition and total hash-power network effects.
- The analysis assumes an ideal communication environment while considering energy and computational constraints in PoW-based public blockchains.Limited bandwidth is identified as a practical factor affecting miner utility, block broadcasting, and blockchain throughput.