auctions.rs 61.7 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Copyright 2019-2020 Parity Technologies (UK) Ltd.
// This file is part of Polkadot.

// Polkadot is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// Polkadot is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with Polkadot.  If not, see <http://www.gnu.org/licenses/>.

//! Auctioning system to determine the set of Parachains in operation. This includes logic for the
//! auctioning mechanism and for reserving balance as part of the "payment". Unreserving the balance
//! happens elsewhere.

Shawn Tabrizi's avatar
Shawn Tabrizi committed
21
22
23
24
use crate::{
	slot_range::SlotRange,
	traits::{AuctionStatus, Auctioneer, LeaseError, Leaser, Registrar},
};
25
use frame_support::{
Shawn Tabrizi's avatar
Shawn Tabrizi committed
26
27
28
29
	dispatch::DispatchResult,
	ensure,
	traits::{Currency, Get, Randomness, ReservableCurrency},
	weights::Weight,
30
};
31
pub use pallet::*;
Shawn Tabrizi's avatar
Shawn Tabrizi committed
32
33
34
35
use parity_scale_codec::Decode;
use primitives::v1::Id as ParaId;
use sp_runtime::traits::{CheckedSub, One, Saturating, Zero};
use sp_std::{mem::swap, prelude::*};
36
37

type CurrencyOf<T> = <<T as Config>::Leaser as Leaser>::Currency;
Shawn Tabrizi's avatar
Shawn Tabrizi committed
38
39
40
type BalanceOf<T> = <<<T as Config>::Leaser as Leaser>::Currency as Currency<
	<T as frame_system::Config>::AccountId,
>>::Balance;
41
42
43
44

pub trait WeightInfo {
	fn new_auction() -> Weight;
	fn bid() -> Weight;
45
	fn cancel_auction() -> Weight;
46
47
48
49
50
	fn on_initialize() -> Weight;
}

pub struct TestWeightInfo;
impl WeightInfo for TestWeightInfo {
Shawn Tabrizi's avatar
Shawn Tabrizi committed
51
52
53
54
55
56
57
58
59
60
61
62
	fn new_auction() -> Weight {
		0
	}
	fn bid() -> Weight {
		0
	}
	fn cancel_auction() -> Weight {
		0
	}
	fn on_initialize() -> Weight {
		0
	}
63
64
65
66
67
68
69
}

/// An auction index. We count auctions in this type.
pub type AuctionIndex = u32;

type LeasePeriodOf<T> = <<T as Config>::Leaser as Leaser>::LeasePeriod;
// Winning data type. This encodes the top bidders of each range together with their bid.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
70
71
type WinningData<T> = [Option<(<T as frame_system::Config>::AccountId, ParaId, BalanceOf<T>)>;
	SlotRange::SLOT_RANGE_COUNT];
72
73
// Winners data type. This encodes each of the final winners of a parachain auction, the parachain
// index assigned to them, their winning bid and the range that they won.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
74
75
type WinnersData<T> =
	Vec<(<T as frame_system::Config>::AccountId, ParaId, BalanceOf<T>, SlotRange)>;
76

77
78
79
#[frame_support::pallet]
pub mod pallet {
	use super::*;
Shawn Tabrizi's avatar
Shawn Tabrizi committed
80
81
	use frame_support::{pallet_prelude::*, traits::EnsureOrigin, weights::DispatchClass};
	use frame_system::{ensure_root, ensure_signed, pallet_prelude::*};
82
83
84
85
86
87
88
89
90
91

	#[pallet::pallet]
	#[pallet::generate_store(pub(super) trait Store)]
	pub struct Pallet<T>(_);

	/// The module's configuration trait.
	#[pallet::config]
	pub trait Config: frame_system::Config {
		/// The overarching event type.
		type Event: From<Event<Self>> + IsType<<Self as frame_system::Config>::Event>;
92

93
		/// The type representing the leasing system.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
94
		type Leaser: Leaser<AccountId = Self::AccountId, LeasePeriod = Self::BlockNumber>;
95
96

		/// The parachain registrar type.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
97
		type Registrar: Registrar<AccountId = Self::AccountId>;
98
99
100
101
102
103

		/// The number of blocks over which an auction may be retroactively ended.
		#[pallet::constant]
		type EndingPeriod: Get<Self::BlockNumber>;

		/// The length of each sample to take during the ending period.
104
		///
Denis_P's avatar
Denis_P committed
105
		/// `EndingPeriod` / `SampleLength` = Total # of Samples
106
107
108
109
110
111
112
113
114
115
116
		#[pallet::constant]
		type SampleLength: Get<Self::BlockNumber>;

		/// Something that provides randomness in the runtime.
		type Randomness: Randomness<Self::Hash, Self::BlockNumber>;

		/// The origin which may initiate auctions.
		type InitiateOrigin: EnsureOrigin<Self::Origin>;

		/// Weight Information for the Extrinsics in the Pallet
		type WeightInfo: WeightInfo;
117
118
	}

119
120
121
122
123
124
125
126
127
	#[pallet::event]
	#[pallet::generate_deposit(pub(super) fn deposit_event)]
	#[pallet::metadata(
		T::AccountId = "AccountId",
		T::BlockNumber = "BlockNumber",
		LeasePeriodOf<T> = "LeasePeriod",
		BalanceOf<T> = "Balance",
	)]
	pub enum Event<T: Config> {
128
129
		/// An auction started. Provides its index and the block number where it will begin to
		/// close and the first lease period of the quadruplet that is auctioned.
Denis_P's avatar
Denis_P committed
130
		/// `[auction_index, lease_period, ending]`
131
		AuctionStarted(AuctionIndex, LeasePeriodOf<T>, T::BlockNumber),
Denis_P's avatar
Denis_P committed
132
		/// An auction ended. All funds become unreserved. `[auction_index]`
133
134
		AuctionClosed(AuctionIndex),
		/// Funds were reserved for a winning bid. First balance is the extra amount reserved.
Denis_P's avatar
Denis_P committed
135
		/// Second is the total. `[bidder, extra_reserved, total_amount]`
136
		Reserved(T::AccountId, BalanceOf<T>, BalanceOf<T>),
Denis_P's avatar
Denis_P committed
137
		/// Funds were unreserved since bidder is no longer active. `[bidder, amount]`
138
		Unreserved(T::AccountId, BalanceOf<T>),
139
140
		/// Someone attempted to lease the same slot twice for a parachain. The amount is held in reserve
		/// but no parachain slot has been leased.
Denis_P's avatar
Denis_P committed
141
		/// `[parachain_id, leaser, amount]`
142
		ReserveConfiscated(ParaId, T::AccountId, BalanceOf<T>),
143
		/// A new bid has been accepted as the current winner.
Denis_P's avatar
Denis_P committed
144
		/// `[who, para_id, amount, first_slot, last_slot]`
145
		BidAccepted(T::AccountId, ParaId, BalanceOf<T>, LeasePeriodOf<T>, LeasePeriodOf<T>),
146
		/// The winning offset was chosen for an auction. This will map into the `Winning` storage map.
Denis_P's avatar
Denis_P committed
147
		/// `[auction_index, block_number]`
148
		WinningOffset(AuctionIndex, T::BlockNumber),
149
150
	}

151
152
	#[pallet::error]
	pub enum Error<T> {
153
154
155
156
		/// This auction is already in progress.
		AuctionInProgress,
		/// The lease period is in the past.
		LeasePeriodInPast,
157
158
		/// Para is not registered
		ParaNotRegistered,
159
160
161
162
163
164
		/// Not a current auction.
		NotCurrentAuction,
		/// Not an auction.
		NotAuction,
		/// Auction has already ended.
		AuctionEnded,
165
166
		/// The para is already leased out for part of this range.
		AlreadyLeasedOut,
167
168
	}

169
170
171
172
	/// Number of auctions started so far.
	#[pallet::storage]
	#[pallet::getter(fn auction_counter)]
	pub type AuctionCounter<T> = StorageValue<_, AuctionIndex, ValueQuery>;
173

174
175
176
177
178
179
180
181
182
183
184
185
186
	/// Information relating to the current auction, if there is one.
	///
	/// The first item in the tuple is the lease period index that the first of the four
	/// contiguous lease periods on auction is for. The second is the block number when the
	/// auction will "begin to end", i.e. the first block of the Ending Period of the auction.
	#[pallet::storage]
	#[pallet::getter(fn auction_info)]
	pub type AuctionInfo<T: Config> = StorageValue<_, (LeasePeriodOf<T>, T::BlockNumber)>;

	/// Amounts currently reserved in the accounts of the bidders currently winning
	/// (sub-)ranges.
	#[pallet::storage]
	#[pallet::getter(fn reserved_amounts)]
Shawn Tabrizi's avatar
Shawn Tabrizi committed
187
188
	pub type ReservedAmounts<T: Config> =
		StorageMap<_, Twox64Concat, (T::AccountId, ParaId), BalanceOf<T>>;
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203

	/// The winning bids for each of the 10 ranges at each sample in the final Ending Period of
	/// the current auction. The map's key is the 0-based index into the Sample Size. The
	/// first sample of the ending period is 0; the last is `Sample Size - 1`.
	#[pallet::storage]
	#[pallet::getter(fn winning)]
	pub type Winning<T: Config> = StorageMap<_, Twox64Concat, T::BlockNumber, WinningData<T>>;

	#[pallet::extra_constants]
	impl<T: Config> Pallet<T> {
		//TODO: rename to snake case after https://github.com/paritytech/substrate/issues/8826 fixed.
		#[allow(non_snake_case)]
		fn SlotRangeCount() -> u32 {
			SlotRange::SLOT_RANGE_COUNT as u32
		}
204

205
206
207
208
209
210
		//TODO: rename to snake case after https://github.com/paritytech/substrate/issues/8826 fixed.
		#[allow(non_snake_case)]
		fn LeasePeriodsPerSlot() -> u32 {
			SlotRange::LEASE_PERIODS_PER_SLOT as u32
		}
	}
211

212
213
	#[pallet::hooks]
	impl<T: Config> Hooks<BlockNumberFor<T>> for Pallet<T> {
214
215
216
217
218
219
		fn on_initialize(n: T::BlockNumber) -> Weight {
			let mut weight = T::DbWeight::get().reads(1);

			// If the current auction was in its ending period last block, then ensure that the (sub-)range
			// winner information is duplicated from the previous block in case no bids happened in the
			// last block.
220
			if let AuctionStatus::EndingPeriod(offset, _sub_sample) = Self::auction_status(n) {
221
222
223
				weight = weight.saturating_add(T::DbWeight::get().reads(1));
				if !Winning::<T>::contains_key(&offset) {
					weight = weight.saturating_add(T::DbWeight::get().writes(1));
Shawn Tabrizi's avatar
Shawn Tabrizi committed
224
225
226
227
					let winning_data = offset
						.checked_sub(&One::one())
						.and_then(Winning::<T>::get)
						.unwrap_or([Self::EMPTY; SlotRange::SLOT_RANGE_COUNT]);
228
229
230
231
232
233
234
235
					Winning::<T>::insert(offset, winning_data);
				}
			}

			// Check to see if an auction just ended.
			if let Some((winning_ranges, auction_lease_period_index)) = Self::check_auction_end(n) {
				// Auction is ended now. We have the winning ranges and the lease period index which
				// acts as the offset. Handle it.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
236
				Self::manage_auction_end(auction_lease_period_index, winning_ranges);
237
238
239
240
241
				weight = weight.saturating_add(T::WeightInfo::on_initialize());
			}

			weight
		}
242
	}
243

244
245
	#[pallet::call]
	impl<T: Config> Pallet<T> {
246
247
248
249
250
		/// Create a new auction.
		///
		/// This can only happen when there isn't already an auction in progress and may only be
		/// called by the root origin. Accepts the `duration` of this auction and the
		/// `lease_period_index` of the initial lease period of the four that are to be auctioned.
251
252
253
254
255
256
		#[pallet::weight((T::WeightInfo::new_auction(), DispatchClass::Operational))]
		pub fn new_auction(
			origin: OriginFor<T>,
			#[pallet::compact] duration: T::BlockNumber,
			#[pallet::compact] lease_period_index: LeasePeriodOf<T>,
		) -> DispatchResult {
257
			T::InitiateOrigin::ensure_origin(origin)?;
258
			Self::do_new_auction(duration, lease_period_index)
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
		}

		/// Make a new bid from an account (including a parachain account) for deploying a new
		/// parachain.
		///
		/// Multiple simultaneous bids from the same bidder are allowed only as long as all active
		/// bids overlap each other (i.e. are mutually exclusive). Bids cannot be redacted.
		///
		/// - `sub` is the sub-bidder ID, allowing for multiple competing bids to be made by (and
		/// funded by) the same account.
		/// - `auction_index` is the index of the auction to bid on. Should just be the present
		/// value of `AuctionCounter`.
		/// - `first_slot` is the first lease period index of the range to bid on. This is the
		/// absolute lease period index value, not an auction-specific offset.
		/// - `last_slot` is the last lease period index of the range to bid on. This is the
		/// absolute lease period index value, not an auction-specific offset.
		/// - `amount` is the amount to bid to be held as deposit for the parachain should the
		/// bid win. This amount is held throughout the range.
277
278
279
280
281
282
283
		#[pallet::weight(T::WeightInfo::bid())]
		pub fn bid(
			origin: OriginFor<T>,
			#[pallet::compact] para: ParaId,
			#[pallet::compact] auction_index: AuctionIndex,
			#[pallet::compact] first_slot: LeasePeriodOf<T>,
			#[pallet::compact] last_slot: LeasePeriodOf<T>,
Shawn Tabrizi's avatar
Shawn Tabrizi committed
284
			#[pallet::compact] amount: BalanceOf<T>,
285
		) -> DispatchResult {
286
287
			let who = ensure_signed(origin)?;
			Self::handle_bid(who, para, auction_index, first_slot, last_slot, amount)?;
288
			Ok(())
289
		}
290
291
292
293

		/// Cancel an in-progress auction.
		///
		/// Can only be called by Root origin.
294
295
		#[pallet::weight(T::WeightInfo::cancel_auction())]
		pub fn cancel_auction(origin: OriginFor<T>) -> DispatchResult {
296
297
298
299
300
			ensure_root(origin)?;
			// Unreserve all bids.
			for ((bidder, _), amount) in ReservedAmounts::<T>::drain() {
				CurrencyOf::<T>::unreserve(&bidder, amount);
			}
301
			Winning::<T>::remove_all(None);
302
			AuctionInfo::<T>::kill();
303
			Ok(())
304
		}
305
306
307
	}
}

308
impl<T: Config> Auctioneer for Pallet<T> {
309
310
311
312
313
314
315
316
317
318
319
320
	type AccountId = T::AccountId;
	type BlockNumber = T::BlockNumber;
	type LeasePeriod = T::BlockNumber;
	type Currency = CurrencyOf<T>;

	fn new_auction(
		duration: T::BlockNumber,
		lease_period_index: LeasePeriodOf<T>,
	) -> DispatchResult {
		Self::do_new_auction(duration, lease_period_index)
	}

321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
	// Returns the status of the auction given the current block number.
	fn auction_status(now: Self::BlockNumber) -> AuctionStatus<Self::BlockNumber> {
		let early_end = match AuctionInfo::<T>::get() {
			Some((_, early_end)) => early_end,
			None => return AuctionStatus::NotStarted,
		};

		let after_early_end = match now.checked_sub(&early_end) {
			Some(after_early_end) => after_early_end,
			None => return AuctionStatus::StartingPeriod,
		};

		let ending_period = T::EndingPeriod::get();
		if after_early_end < ending_period {
			let sample_length = T::SampleLength::get().max(One::one());
			let sample = after_early_end / sample_length;
			let sub_sample = after_early_end % sample_length;
			return AuctionStatus::EndingPeriod(sample, sub_sample)
		} else {
			// This is safe because of the comparison operator above
			return AuctionStatus::VrfDelay(after_early_end - ending_period)
342
343
344
345
346
347
348
349
350
351
		}
	}

	fn place_bid(
		bidder: T::AccountId,
		para: ParaId,
		first_slot: LeasePeriodOf<T>,
		last_slot: LeasePeriodOf<T>,
		amount: BalanceOf<T>,
	) -> DispatchResult {
352
		Self::handle_bid(bidder, para, AuctionCounter::<T>::get(), first_slot, last_slot, amount)
353
354
355
356
357
	}

	fn lease_period_index() -> Self::LeasePeriod {
		T::Leaser::lease_period_index()
	}
358
359
360
361
362
363
364
365

	fn lease_period() -> Self::LeasePeriod {
		T::Leaser::lease_period()
	}

	fn has_won_an_auction(para: ParaId, bidder: &T::AccountId) -> bool {
		!T::Leaser::deposit_held(para, bidder).is_zero()
	}
366
367
}

368
impl<T: Config> Pallet<T> {
369
370
371
	// A trick to allow me to initialize large arrays with nothing in them.
	const EMPTY: Option<(<T as frame_system::Config>::AccountId, ParaId, BalanceOf<T>)> = None;

372
373
374
375
376
377
378
379
380
	/// Create a new auction.
	///
	/// This can only happen when there isn't already an auction in progress. Accepts the `duration`
	/// of this auction and the `lease_period_index` of the initial lease period of the four that
	/// are to be auctioned.
	fn do_new_auction(
		duration: T::BlockNumber,
		lease_period_index: LeasePeriodOf<T>,
	) -> DispatchResult {
381
382
		let maybe_auction = AuctionInfo::<T>::get();
		ensure!(maybe_auction.is_none(), Error::<T>::AuctionInProgress);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
383
384
385
386
		ensure!(
			lease_period_index >= T::Leaser::lease_period_index(),
			Error::<T>::LeasePeriodInPast
		);
387
388

		// Bump the counter.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
389
390
391
392
		let n = AuctionCounter::<T>::mutate(|n| {
			*n += 1;
			*n
		});
393
394

		// Set the information.
395
		let ending = frame_system::Pallet::<T>::block_number().saturating_add(duration);
396
397
		AuctionInfo::<T>::put((lease_period_index, ending));

398
		Self::deposit_event(Event::<T>::AuctionStarted(n, lease_period_index, ending));
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
		Ok(())
	}

	/// Actually place a bid in the current auction.
	///
	/// - `bidder`: The account that will be funding this bid.
	/// - `auction_index`: The auction index of the bid. For this to succeed, must equal
	/// the current value of `AuctionCounter`.
	/// - `first_slot`: The first lease period index of the range to be bid on.
	/// - `last_slot`: The last lease period index of the range to be bid on (inclusive).
	/// - `amount`: The total amount to be the bid for deposit over the range.
	pub fn handle_bid(
		bidder: T::AccountId,
		para: ParaId,
		auction_index: u32,
		first_slot: LeasePeriodOf<T>,
		last_slot: LeasePeriodOf<T>,
		amount: BalanceOf<T>,
	) -> DispatchResult {
418
419
		// Ensure para is registered before placing a bid on it.
		ensure!(T::Registrar::is_registered(para), Error::<T>::ParaNotRegistered);
420
		// Bidding on latest auction.
421
		ensure!(auction_index == AuctionCounter::<T>::get(), Error::<T>::NotCurrentAuction);
422
		// Assume it's actually an auction (this should never fail because of above).
423
		let (first_lease_period, _) = AuctionInfo::<T>::get().ok_or(Error::<T>::NotAuction)?;
424

425
426
427
428
429
430
431
432
433
434
		// Get the auction status and the current sample block. For the starting period, the sample
		// block is zero.
		let auction_status = Self::auction_status(frame_system::Pallet::<T>::block_number());
		// The offset into the ending samples of the auction.
		let offset = match auction_status {
			AuctionStatus::NotStarted => return Err(Error::<T>::AuctionEnded.into()),
			AuctionStatus::StartingPeriod => Zero::zero(),
			AuctionStatus::EndingPeriod(o, _) => o,
			AuctionStatus::VrfDelay(_) => return Err(Error::<T>::AuctionEnded.into()),
		};
435

436
		// We also make sure that the bid is not for any existing leases the para already has.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
437
438
439
440
		ensure!(
			!T::Leaser::already_leased(para, first_slot, last_slot),
			Error::<T>::AlreadyLeasedOut
		);
441

442
443
444
445
		// Our range.
		let range = SlotRange::new_bounded(first_lease_period, first_slot, last_slot)?;
		// Range as an array index.
		let range_index = range as u8 as usize;
446

447
448
449
		// The current winning ranges.
		let mut current_winning = Winning::<T>::get(offset)
			.or_else(|| offset.checked_sub(&One::one()).and_then(Winning::<T>::get))
450
			.unwrap_or([Self::EMPTY; SlotRange::SLOT_RANGE_COUNT]);
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472

		// If this bid beat the previous winner of our range.
		if current_winning[range_index].as_ref().map_or(true, |last| amount > last.2) {
			// Ok; we are the new winner of this range - reserve the additional amount and record.

			// Get the amount already held on deposit if this is a renewal bid (i.e. there's
			// an existing lease on the same para by the same leaser).
			let existing_lease_deposit = T::Leaser::deposit_held(para, &bidder);
			let reserve_required = amount.saturating_sub(existing_lease_deposit);

			// Get the amount already reserved in any prior and still active bids by us.
			let bidder_para = (bidder.clone(), para);
			let already_reserved = ReservedAmounts::<T>::get(&bidder_para).unwrap_or_default();

			// If these don't already cover the bid...
			if let Some(additional) = reserve_required.checked_sub(&already_reserved) {
				// ...then reserve some more funds from their account, failing if there's not
				// enough funds.
				CurrencyOf::<T>::reserve(&bidder, additional)?;
				// ...and record the amount reserved.
				ReservedAmounts::<T>::insert(&bidder_para, reserve_required);

473
				Self::deposit_event(Event::<T>::Reserved(
474
475
476
477
478
479
					bidder.clone(),
					additional,
					reserve_required,
				));
			}

480
481
			// Return any funds reserved for the previous winner if we are not in the ending period
			// and they no longer have any active bids.
482
483
484
			let mut outgoing_winner = Some((bidder.clone(), para, amount));
			swap(&mut current_winning[range_index], &mut outgoing_winner);
			if let Some((who, para, _amount)) = outgoing_winner {
Shawn Tabrizi's avatar
Shawn Tabrizi committed
485
486
487
488
489
				if auction_status.is_starting() &&
					current_winning
						.iter()
						.filter_map(Option::as_ref)
						.all(|&(ref other, other_para, _)| other != &who || other_para != para)
490
491
492
493
494
495
				{
					// Previous bidder is no longer winning any ranges: unreserve their funds.
					if let Some(amount) = ReservedAmounts::<T>::take(&(who.clone(), para)) {
						// It really should be reserved; there's not much we can do here on fail.
						let err_amt = CurrencyOf::<T>::unreserve(&who, amount);
						debug_assert!(err_amt.is_zero());
496
						Self::deposit_event(Event::<T>::Unreserved(who, amount));
497
498
499
500
501
502
					}
				}
			}

			// Update the range winner.
			Winning::<T>::insert(offset, &current_winning);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
503
504
505
			Self::deposit_event(Event::<T>::BidAccepted(
				bidder, para, amount, first_slot, last_slot,
			));
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
		}
		Ok(())
	}

	/// Some when the auction's end is known (with the end block number). None if it is unknown.
	/// If `Some` then the block number must be at most the previous block and at least the
	/// previous block minus `T::EndingPeriod::get()`.
	///
	/// This mutates the state, cleaning up `AuctionInfo` and `Winning` in the case of an auction
	/// ending. An immediately subsequent call with the same argument will always return `None`.
	fn check_auction_end(now: T::BlockNumber) -> Option<(WinningData<T>, LeasePeriodOf<T>)> {
		if let Some((lease_period_index, early_end)) = AuctionInfo::<T>::get() {
			let ending_period = T::EndingPeriod::get();
			let late_end = early_end.saturating_add(ending_period);
			let is_ended = now >= late_end;
			if is_ended {
				// auction definitely ended.
				// check to see if we can determine the actual ending point.
				let (raw_offset, known_since) = T::Randomness::random(&b"para_auction"[..]);

				if late_end <= known_since {
					// Our random seed was known only after the auction ended. Good to use.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
528
529
530
531
532
533
					let raw_offset_block_number = <T::BlockNumber>::decode(
						&mut raw_offset.as_ref(),
					)
					.expect("secure hashes should always be bigger than the block number; qed");
					let offset = (raw_offset_block_number % ending_period) /
						T::SampleLength::get().max(One::one());
534

535
536
					let auction_counter = AuctionCounter::<T>::get();
					Self::deposit_event(Event::<T>::WinningOffset(auction_counter, offset));
Shawn Tabrizi's avatar
Shawn Tabrizi committed
537
538
					let res = Winning::<T>::get(offset)
						.unwrap_or([Self::EMPTY; SlotRange::SLOT_RANGE_COUNT]);
539
540
					// This `remove_all` statement should remove at most `EndingPeriod` / `SampleLength` items,
					// which should be bounded and sensibly configured in the runtime.
541
					Winning::<T>::remove_all(None);
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
					AuctionInfo::<T>::kill();
					return Some((res, lease_period_index))
				}
			}
		}
		None
	}

	/// Auction just ended. We have the current lease period, the auction's lease period (which
	/// is guaranteed to be at least the current period) and the bidders that were winning each
	/// range at the time of the auction's close.
	fn manage_auction_end(
		auction_lease_period_index: LeasePeriodOf<T>,
		winning_ranges: WinningData<T>,
	) {
		// First, unreserve all amounts that were reserved for the bids. We will later re-reserve the
		// amounts from the bidders that ended up being assigned the slot so there's no need to
		// special-case them here.
560
		for ((bidder, _), amount) in ReservedAmounts::<T>::drain() {
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
			CurrencyOf::<T>::unreserve(&bidder, amount);
		}

		// Next, calculate the winning combination of slots and thus the final winners of the
		// auction.
		let winners = Self::calculate_winners(winning_ranges);

		// Go through those winners and re-reserve their bid, updating our table of deposits
		// accordingly.
		for (leaser, para, amount, range) in winners.into_iter() {
			let begin_offset = LeasePeriodOf::<T>::from(range.as_pair().0 as u32);
			let period_begin = auction_lease_period_index + begin_offset;
			let period_count = LeasePeriodOf::<T>::from(range.len() as u32);

			match T::Leaser::lease_out(para, &leaser, amount, period_begin, period_count) {
				Err(LeaseError::ReserveFailed) | Err(LeaseError::AlreadyEnded) => {
					// Should never happen since we just unreserved this amount (and our offset is from the
					// present period). But if it does, there's not much we can do.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
579
				},
580
581
582
583
				Err(LeaseError::AlreadyLeased) => {
					// The leaser attempted to get a second lease on the same para ID, possibly griefing us. Let's
					// keep the amount reserved and let governance sort it out.
					if CurrencyOf::<T>::reserve(&leaser, amount).is_ok() {
584
						Self::deposit_event(Event::<T>::ReserveConfiscated(para, leaser, amount));
585
					}
Shawn Tabrizi's avatar
Shawn Tabrizi committed
586
				},
587
588
589
590
				Ok(()) => {}, // Nothing to report.
			}
		}

591
		Self::deposit_event(Event::<T>::AuctionClosed(AuctionCounter::<T>::get()));
592
593
594
595
596
	}

	/// Calculate the final winners from the winning slots.
	///
	/// This is a simple dynamic programming algorithm designed by Al, the original code is at:
Denis_P's avatar
Denis_P committed
597
	/// `https://github.com/w3f/consensus/blob/master/NPoS/auctiondynamicthing.py`
Shawn Tabrizi's avatar
Shawn Tabrizi committed
598
	fn calculate_winners(mut winning: WinningData<T>) -> WinnersData<T> {
599
		let winning_ranges = {
Shawn Tabrizi's avatar
Shawn Tabrizi committed
600
601
			let mut best_winners_ending_at: [(Vec<SlotRange>, BalanceOf<T>);
				SlotRange::LEASE_PERIODS_PER_SLOT] = Default::default();
602
			let best_bid = |range: SlotRange| {
Shawn Tabrizi's avatar
Shawn Tabrizi committed
603
604
				winning[range as u8 as usize]
					.as_ref()
605
606
					.map(|(_, _, amount)| *amount * (range.len() as u32).into())
			};
607
			for i in 0..SlotRange::LEASE_PERIODS_PER_SLOT {
608
609
610
611
612
613
				let r = SlotRange::new_bounded(0, 0, i as u32).expect("`i < 4`; qed");
				if let Some(bid) = best_bid(r) {
					best_winners_ending_at[i] = (vec![r], bid);
				}
				for j in 0..i {
					let r = SlotRange::new_bounded(0, j as u32 + 1, i as u32)
614
						.expect("`i < LPPS`; `j < i`; `j + 1 < LPPS`; qed");
615
616
617
618
619
620
621
622
623
624
625
626
627
628
					if let Some(mut bid) = best_bid(r) {
						bid += best_winners_ending_at[j].1;
						if bid > best_winners_ending_at[i].1 {
							let mut new_winners = best_winners_ending_at[j].0.clone();
							new_winners.push(r);
							best_winners_ending_at[i] = (new_winners, bid);
						}
					} else {
						if best_winners_ending_at[j].1 > best_winners_ending_at[i].1 {
							best_winners_ending_at[i] = best_winners_ending_at[j].clone();
						}
					}
				}
			}
629
			best_winners_ending_at[SlotRange::LEASE_PERIODS_PER_SLOT - 1].0.clone()
630
631
		};

Shawn Tabrizi's avatar
Shawn Tabrizi committed
632
633
634
635
636
637
638
639
640
641
642
643
644
645
		winning_ranges
			.into_iter()
			.map(|range| {
				let mut final_winner = Default::default();
				swap(
					&mut final_winner,
					winning[range as u8 as usize]
						.as_mut()
						.expect("none values are filtered out in previous logic; qed"),
				);
				let (bidder, para, amount) = final_winner;
				(bidder, para, amount, range)
			})
			.collect::<Vec<_>>()
646
647
648
649
650
651
652
	}
}

/// tests for this module
#[cfg(test)]
mod tests {
	use super::*;
Shawn Tabrizi's avatar
Shawn Tabrizi committed
653
	use crate::{auctions, mock::TestRegistrar};
654
	use frame_support::{
Shawn Tabrizi's avatar
Shawn Tabrizi committed
655
		assert_noop, assert_ok, assert_storage_noop,
656
		dispatch::DispatchError::BadOrigin,
Shawn Tabrizi's avatar
Shawn Tabrizi committed
657
658
		ord_parameter_types, parameter_types,
		traits::{OnFinalize, OnInitialize},
659
	};
Shawn Tabrizi's avatar
Shawn Tabrizi committed
660
	use frame_system::{EnsureOneOf, EnsureRoot, EnsureSignedBy};
661
662
	use pallet_balances;
	use primitives::v1::{BlockNumber, Header, Id as ParaId};
Shawn Tabrizi's avatar
Shawn Tabrizi committed
663
664
665
	use sp_core::H256;
	use sp_runtime::traits::{BlakeTwo256, IdentityLookup};
	use std::{cell::RefCell, collections::BTreeMap};
666
667
668
669
670
671
672
673
674
675

	type UncheckedExtrinsic = frame_system::mocking::MockUncheckedExtrinsic<Test>;
	type Block = frame_system::mocking::MockBlock<Test>;

	frame_support::construct_runtime!(
		pub enum Test where
			Block = Block,
			NodeBlock = Block,
			UncheckedExtrinsic = UncheckedExtrinsic,
		{
676
677
678
			System: frame_system::{Pallet, Call, Config, Storage, Event<T>},
			Balances: pallet_balances::{Pallet, Call, Storage, Config<T>, Event<T>},
			Auctions: auctions::{Pallet, Call, Storage, Event<T>},
679
680
681
682
683
684
685
		}
	);

	parameter_types! {
		pub const BlockHashCount: u32 = 250;
	}
	impl frame_system::Config for Test {
686
		type BaseCallFilter = frame_support::traits::Everything;
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
		type BlockWeights = ();
		type BlockLength = ();
		type DbWeight = ();
		type Origin = Origin;
		type Call = Call;
		type Index = u64;
		type BlockNumber = BlockNumber;
		type Hash = H256;
		type Hashing = BlakeTwo256;
		type AccountId = u64;
		type Lookup = IdentityLookup<Self::AccountId>;
		type Header = Header;
		type Event = Event;
		type BlockHashCount = BlockHashCount;
		type Version = ();
		type PalletInfo = PalletInfo;
		type AccountData = pallet_balances::AccountData<u64>;
		type OnNewAccount = ();
		type OnKilledAccount = ();
		type SystemWeightInfo = ();
		type SS58Prefix = ();
708
		type OnSetCode = ();
709
710
711
712
	}

	parameter_types! {
		pub const ExistentialDeposit: u64 = 1;
Gavin Wood's avatar
Gavin Wood committed
713
		pub const MaxReserves: u32 = 50;
714
715
716
717
718
719
720
721
722
723
	}

	impl pallet_balances::Config for Test {
		type Balance = u64;
		type DustRemoval = ();
		type Event = Event;
		type ExistentialDeposit = ExistentialDeposit;
		type AccountStore = System;
		type WeightInfo = ();
		type MaxLocks = ();
Gavin Wood's avatar
Gavin Wood committed
724
725
		type MaxReserves = MaxReserves;
		type ReserveIdentifier = [u8; 8];
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
	}

	#[derive(Eq, PartialEq, Ord, PartialOrd, Clone, Copy, Debug)]
	pub struct LeaseData {
		leaser: u64,
		amount: u64,
	}

	thread_local! {
		pub static LEASES:
			RefCell<BTreeMap<(ParaId, BlockNumber), LeaseData>> = RefCell::new(BTreeMap::new());
	}

	fn leases() -> Vec<((ParaId, BlockNumber), LeaseData)> {
		LEASES.with(|p| (&*p.borrow()).clone().into_iter().collect::<Vec<_>>())
	}

	pub struct TestLeaser;
	impl Leaser for TestLeaser {
		type AccountId = u64;
		type LeasePeriod = BlockNumber;
		type Currency = Balances;

		fn lease_out(
			para: ParaId,
			leaser: &Self::AccountId,
			amount: <Self::Currency as Currency<Self::AccountId>>::Balance,
			period_begin: Self::LeasePeriod,
			period_count: Self::LeasePeriod,
		) -> Result<(), LeaseError> {
			LEASES.with(|l| {
				let mut leases = l.borrow_mut();
				if period_begin < Self::lease_period_index() {
					return Err(LeaseError::AlreadyEnded)
				}
				for period in period_begin..(period_begin + period_count) {
					if leases.contains_key(&(para, period)) {
						return Err(LeaseError::AlreadyLeased)
					}
					leases.insert((para, period), LeaseData { leaser: leaser.clone(), amount });
				}
				Ok(())
			})
		}

771
772
		fn deposit_held(
			para: ParaId,
Shawn Tabrizi's avatar
Shawn Tabrizi committed
773
			leaser: &Self::AccountId,
774
		) -> <Self::Currency as Currency<Self::AccountId>>::Balance {
Shawn Tabrizi's avatar
Shawn Tabrizi committed
775
776
777
778
779
780
781
782
783
			leases()
				.iter()
				.filter_map(|((id, _period), data)| {
					if id == &para && &data.leaser == leaser {
						Some(data.amount)
					} else {
						None
					}
				})
784
785
786
787
788
789
790
791
792
793
794
				.max()
				.unwrap_or_default()
		}

		fn lease_period() -> Self::LeasePeriod {
			10
		}

		fn lease_period_index() -> Self::LeasePeriod {
			(System::block_number() / Self::lease_period()).into()
		}
795
796
797
798

		fn already_leased(
			para_id: ParaId,
			first_period: Self::LeasePeriod,
Shawn Tabrizi's avatar
Shawn Tabrizi committed
799
			last_period: Self::LeasePeriod,
800
801
		) -> bool {
			leases().into_iter().any(|((para, period), _data)| {
Shawn Tabrizi's avatar
Shawn Tabrizi committed
802
				para == para_id && first_period <= period && period <= last_period
803
804
			})
		}
805
806
	}

Shawn Tabrizi's avatar
Shawn Tabrizi committed
807
	ord_parameter_types! {
808
809
810
		pub const Six: u64 = 6;
	}

Shawn Tabrizi's avatar
Shawn Tabrizi committed
811
	type RootOrSix = EnsureOneOf<u64, EnsureRoot<u64>, EnsureSignedBy<Six, u64>>;
812
813
814
815
816
817
818
819
820
821
822
823
824
825

	thread_local! {
		pub static LAST_RANDOM: RefCell<Option<(H256, u32)>> = RefCell::new(None);
	}
	fn set_last_random(output: H256, known_since: u32) {
		LAST_RANDOM.with(|p| *p.borrow_mut() = Some((output, known_since)))
	}
	pub struct TestPastRandomness;
	impl Randomness<H256, BlockNumber> for TestPastRandomness {
		fn random(_subject: &[u8]) -> (H256, u32) {
			LAST_RANDOM.with(|p| {
				if let Some((output, known_since)) = &*p.borrow() {
					(*output, *known_since)
				} else {
826
					(H256::zero(), frame_system::Pallet::<Test>::block_number())
827
828
829
830
831
				}
			})
		}
	}

Shawn Tabrizi's avatar
Shawn Tabrizi committed
832
	parameter_types! {
833
834
835
836
		pub static EndingPeriod: BlockNumber = 3;
		pub static SampleLength: BlockNumber = 1;
	}

837
838
839
	impl Config for Test {
		type Event = Event;
		type Leaser = TestLeaser;
840
		type Registrar = TestRegistrar<Self>;
841
		type EndingPeriod = EndingPeriod;
842
		type SampleLength = SampleLength;
843
844
845
846
847
848
849
850
851
		type Randomness = TestPastRandomness;
		type InitiateOrigin = RootOrSix;
		type WeightInfo = crate::auctions::TestWeightInfo;
	}

	// This function basically just builds a genesis storage key/value store according to
	// our desired mock up.
	pub fn new_test_ext() -> sp_io::TestExternalities {
		let mut t = frame_system::GenesisConfig::default().build_storage::<Test>().unwrap();
Shawn Tabrizi's avatar
Shawn Tabrizi committed
852
		pallet_balances::GenesisConfig::<Test> {
853
			balances: vec![(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)],
Shawn Tabrizi's avatar
Shawn Tabrizi committed
854
855
856
		}
		.assimilate_storage(&mut t)
		.unwrap();
857
858
859
		let mut ext: sp_io::TestExternalities = t.into();
		ext.execute_with(|| {
			// Register para 0, 1, 2, and 3 for tests
Shawn Tabrizi's avatar
Shawn Tabrizi committed
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
			assert_ok!(TestRegistrar::<Test>::register(
				1,
				0.into(),
				Default::default(),
				Default::default()
			));
			assert_ok!(TestRegistrar::<Test>::register(
				1,
				1.into(),
				Default::default(),
				Default::default()
			));
			assert_ok!(TestRegistrar::<Test>::register(
				1,
				2.into(),
				Default::default(),
				Default::default()
			));
			assert_ok!(TestRegistrar::<Test>::register(
				1,
				3.into(),
				Default::default(),
				Default::default()
			));
884
885
		});
		ext
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
	}

	fn run_to_block(n: BlockNumber) {
		while System::block_number() < n {
			Auctions::on_finalize(System::block_number());
			Balances::on_finalize(System::block_number());
			System::on_finalize(System::block_number());
			System::set_block_number(System::block_number() + 1);
			System::on_initialize(System::block_number());
			Balances::on_initialize(System::block_number());
			Auctions::on_initialize(System::block_number());
		}
	}

	#[test]
	fn basic_setup_works() {
		new_test_ext().execute_with(|| {
903
			assert_eq!(AuctionCounter::<Test>::get(), 0);
904
			assert_eq!(TestLeaser::deposit_held(0u32.into(), &1), 0);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
905
906
907
908
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::NotStarted
			);
909
910
911

			run_to_block(10);

912
			assert_eq!(AuctionCounter::<Test>::get(), 0);
913
			assert_eq!(TestLeaser::deposit_held(0u32.into(), &1), 0);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
914
915
916
917
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::NotStarted
			);
918
919
920
921
922
923
924
925
926
927
928
		});
	}

	#[test]
	fn can_start_auction() {
		new_test_ext().execute_with(|| {
			run_to_block(1);

			assert_noop!(Auctions::new_auction(Origin::signed(1), 5, 1), BadOrigin);
			assert_ok!(Auctions::new_auction(Origin::signed(6), 5, 1));

929
			assert_eq!(AuctionCounter::<Test>::get(), 1);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
930
931
932
933
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::StartingPeriod
			);
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
		});
	}

	#[test]
	fn bidding_works() {
		new_test_ext().execute_with(|| {
			run_to_block(1);
			assert_ok!(Auctions::new_auction(Origin::signed(6), 5, 1));
			assert_ok!(Auctions::bid(Origin::signed(1), 0.into(), 1, 1, 4, 5));

			assert_eq!(Balances::reserved_balance(1), 5);
			assert_eq!(Balances::free_balance(1), 5);
			assert_eq!(
				Auctions::winning(0).unwrap()[SlotRange::ZeroThree as u8 as usize],
				Some((1, 0.into(), 5))
			);
		});
	}

	#[test]
	fn under_bidding_works() {
		new_test_ext().execute_with(|| {
			run_to_block(1);
			assert_ok!(Auctions::new_auction(Origin::signed(6), 5, 1));

			assert_ok!(Auctions::bid(Origin::signed(1), 0.into(), 1, 1, 4, 5));

Shawn Tabrizi's avatar
Shawn Tabrizi committed
961
962
963
			assert_storage_noop!({
				assert_ok!(Auctions::bid(Origin::signed(2), 0.into(), 1, 1, 4, 1));
			});
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
		});
	}

	#[test]
	fn over_bidding_works() {
		new_test_ext().execute_with(|| {
			run_to_block(1);
			assert_ok!(Auctions::new_auction(Origin::signed(6), 5, 1));
			assert_ok!(Auctions::bid(Origin::signed(1), 0.into(), 1, 1, 4, 5));
			assert_ok!(Auctions::bid(Origin::signed(2), 0.into(), 1, 1, 4, 6));

			assert_eq!(Balances::reserved_balance(1), 0);
			assert_eq!(Balances::free_balance(1), 10);
			assert_eq!(Balances::reserved_balance(2), 6);
			assert_eq!(Balances::free_balance(2), 14);
			assert_eq!(
				Auctions::winning(0).unwrap()[SlotRange::ZeroThree as u8 as usize],
				Some((2, 0.into(), 6))
			);
		});
	}

	#[test]
	fn auction_proceeds_correctly() {
		new_test_ext().execute_with(|| {
			run_to_block(1);

			assert_ok!(Auctions::new_auction(Origin::signed(6), 5, 1));

993
			assert_eq!(AuctionCounter::<Test>::get(), 1);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
994
995
996
997
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::StartingPeriod
			);
998
999

			run_to_block(2);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1000
1001
1002
1003
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::StartingPeriod
			);
1004
1005

			run_to_block(3);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1006
1007
1008
1009
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::StartingPeriod
			);
1010
1011

			run_to_block(4);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1012
1013
1014
1015
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::StartingPeriod
			);
1016
1017

			run_to_block(5);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1018
1019
1020
1021
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::StartingPeriod
			);
1022
1023

			run_to_block(6);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1024
1025
1026
1027
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::EndingPeriod(0, 0)
			);
1028
1029

			run_to_block(7);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1030
1031
1032
1033
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::EndingPeriod(1, 0)
			);
1034
1035

			run_to_block(8);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1036
1037
1038
1039
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::EndingPeriod(2, 0)
			);
1040
1041

			run_to_block(9);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1042
1043
1044
1045
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::NotStarted
			);
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
		});
	}

	#[test]
	fn can_win_auction() {
		new_test_ext().execute_with(|| {
			run_to_block(1);
			assert_ok!(Auctions::new_auction(Origin::signed(6), 5, 1));
			assert_ok!(Auctions::bid(Origin::signed(1), 0.into(), 1, 1, 4, 1));
			assert_eq!(Balances::reserved_balance(1), 1);
			assert_eq!(Balances::free_balance(1), 9);
			run_to_block(9);

Shawn Tabrizi's avatar
Shawn Tabrizi committed
1059
1060
1061
1062
1063
1064
1065
1066
1067
			assert_eq!(
				leases(),
				vec![
					((0.into(), 1), LeaseData { leaser: 1, amount: 1 }),
					((0.into(), 2), LeaseData { leaser: 1, amount: 1 }),
					((0.into(), 3), LeaseData { leaser: 1, amount: 1 }),
					((0.into(), 4), LeaseData { leaser: 1, amount: 1 }),
				]
			);
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
			assert_eq!(TestLeaser::deposit_held(0.into(), &1), 1);
		});
	}

	#[test]
	fn can_win_auction_with_late_randomness() {
		new_test_ext().execute_with(|| {
			run_to_block(1);
			assert_ok!(Auctions::new_auction(Origin::signed(6), 5, 1));
			assert_ok!(Auctions::bid(Origin::signed(1), 0.into(), 1, 1, 4, 1));
			assert_eq!(Balances::reserved_balance(1), 1);
			assert_eq!(Balances::free_balance(1), 9);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1080
1081
1082
1083
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::StartingPeriod
			);
1084
1085
1086
			run_to_block(8);
			// Auction has not yet ended.
			assert_eq!(leases(), vec![]);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1087
1088
1089
1090
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::EndingPeriod(2, 0)
			);
1091
1092
1093
1094
1095
1096
			// This will prevent the auction's winner from being decided in the next block, since the random
			// seed was known before the final bids were made.
			set_last_random(H256::zero(), 8);
			// Auction definitely ended now, but we don't know exactly when in the last 3 blocks yet since
			// no randomness available yet.
			run_to_block(9);
1097
			// Auction has now ended... But auction winner still not yet decided, so no leases yet.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1098
1099
1100
1101
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::VrfDelay(0)
			);
1102
1103
1104
1105
1106
1107
1108
			assert_eq!(leases(), vec![]);

			// Random seed now updated to a value known at block 9, when the auction ended. This means
			// that the winner can now be chosen.
			set_last_random(H256::zero(), 9);
			run_to_block(10);
			// Auction ended and winner selected
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::NotStarted
			);
			assert_eq!(
				leases(),
				vec![
					((0.into(), 1), LeaseData { leaser: 1, amount: 1 }),
					((0.into(), 2), LeaseData { leaser: 1, amount: 1 }),
					((0.into(), 3), LeaseData { leaser: 1, amount: 1 }),
					((0.into(), 4), LeaseData { leaser: 1, amount: 1 }),
				]
			);
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
			assert_eq!(TestLeaser::deposit_held(0.into(), &1), 1);
		});
	}

	#[test]
	fn can_win_incomplete_auction() {
		new_test_ext().execute_with(|| {
			run_to_block(1);
			assert_ok!(Auctions::new_auction(Origin::signed(6), 5, 1));
			assert_ok!(Auctions::bid(Origin::signed(1), 0.into(), 1, 4, 4, 5));
			run_to_block(9);

Shawn Tabrizi's avatar
Shawn Tabrizi committed
1134
			assert_eq!(leases(), vec![((0.into(), 4), LeaseData { leaser: 1, amount: 5 }),]);
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
			assert_eq!(TestLeaser::deposit_held(0.into(), &1), 5);
		});
	}

	#[test]
	fn should_choose_best_combination() {
		new_test_ext().execute_with(|| {
			run_to_block(1);
			assert_ok!(Auctions::new_auction(Origin::signed(6), 5, 1));
			assert_ok!(Auctions::bid(Origin::signed(1), 0.into(), 1, 1, 1, 1));
			assert_ok!(Auctions::bid(Origin::signed(2), 0.into(), 1, 2, 3, 4));
			assert_ok!(Auctions::bid(Origin::signed(3), 0.into(), 1, 4, 4, 2));
			assert_ok!(Auctions::bid(Origin::signed(1), 1.into(), 1, 1, 4, 2));
			run_to_block(9);

Shawn Tabrizi's avatar
Shawn Tabrizi committed
1150
1151
1152
1153
1154
1155
1156
1157
1158
			assert_eq!(
				leases(),
				vec![
					((0.into(), 1), LeaseData { leaser: 1, amount: 1 }),
					((0.into(), 2), LeaseData { leaser: 2, amount: 4 }),
					((0.into(), 3), LeaseData { leaser: 2, amount: 4 }),
					((0.into(), 4), LeaseData { leaser: 3, amount: 2 }),
				]
			);
1159
1160
1161
1162
1163
1164
1165
1166
			assert_eq!(TestLeaser::deposit_held(0.into(), &1), 1);
			assert_eq!(TestLeaser::deposit_held(1.into(), &1), 0);
			assert_eq!(TestLeaser::deposit_held(0.into(), &2), 4);
			assert_eq!(TestLeaser::deposit_held(0.into(), &3), 2);
		});
	}

	#[test]
1167
	fn gap_bid_works() {
1168
1169
		new_test_ext().execute_with(|| {
			run_to_block(1);
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
			assert_ok!(Auctions::new_auction(Origin::signed(6), 5, 1));

			// User 1 will make a bid for period 1 and 4 for the same Para 0
			assert_ok!(Auctions::bid(Origin::signed(1), 0.into(), 1, 1, 1, 1));
			assert_ok!(Auctions::bid(Origin::signed(1), 0.into(), 1, 4, 4, 4));

			// User 2 and 3 will make a bid for para 1 on period 2 and 3 respectively
			assert_ok!(Auctions::bid(Origin::signed(2), 1.into(), 1, 2, 2, 2));
			assert_ok!(Auctions::bid(Origin::signed(3), 1.into(), 1, 3, 3, 3));

			// Total reserved should be the max of the two
			assert_eq!(Balances::reserved_balance(1), 4);

			// Other people are reserved correctly too
			assert_eq!(Balances::reserved_balance(2), 2);
			assert_eq!(Balances::reserved_balance(3), 3);

			// End the auction.
			run_to_block(9);

Shawn Tabrizi's avatar
Shawn Tabrizi committed
1190
1191
1192
1193
1194
1195
1196
1197
1198
			assert_eq!(
				leases(),
				vec![
					((0.into(), 1), LeaseData { leaser: 1, amount: 1 }),
					((0.into(), 4), LeaseData { leaser: 1, amount: 4 }),
					((1.into(), 2), LeaseData { leaser: 2, amount: 2 }),
					((1.into(), 3), LeaseData { leaser: 3, amount: 3 }),
				]
			);
1199
1200
1201
			assert_eq!(TestLeaser::deposit_held(0.into(), &1), 4);
			assert_eq!(TestLeaser::deposit_held(1.into(), &2), 2);
			assert_eq!(TestLeaser::deposit_held(1.into(), &3), 3);
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
		});
	}

	#[test]
	fn deposit_credit_should_work() {
		new_test_ext().execute_with(|| {
			run_to_block(1);
			assert_ok!(Auctions::new_auction(Origin::signed(6), 5, 1));
			assert_ok!(Auctions::bid(Origin::signed(1), 0.into(), 1, 1, 1, 5));
			assert_eq!(Balances::reserved_balance(1), 5);
			run_to_block(10);

Shawn Tabrizi's avatar
Shawn Tabrizi committed
1214
			assert_eq!(leases(), vec![((0.into(), 1), LeaseData { leaser: 1, amount: 5 }),]);
1215
1216
1217
1218
1219
1220
1221
1222
			assert_eq!(TestLeaser::deposit_held(0.into(), &1), 5);

			assert_ok!(Auctions::new_auction(Origin::signed(6), 5, 2));
			assert_ok!(Auctions::bid(Origin::signed(1), 0.into(), 2, 2, 2, 6));
			// Only 1 reserved since we have a deposit credit of 5.
			assert_eq!(Balances::reserved_balance(1), 1);
			run_to_block(20);

Shawn Tabrizi's avatar
Shawn Tabrizi committed
1223
1224
1225
1226
1227
1228
1229
			assert_eq!(
				leases(),
				vec![
					((0.into(), 1), LeaseData { leaser: 1, amount: 5 }),
					((0.into(), 2), LeaseData { leaser: 1, amount: 6 }),
				]
			);
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
			assert_eq!(TestLeaser::deposit_held(0.into(), &1), 6);
		});
	}

	#[test]
	fn deposit_credit_on_alt_para_should_not_count() {
		new_test_ext().execute_with(|| {
			run_to_block(1);
			assert_ok!(Auctions::new_auction(Origin::signed(6), 5, 1));
			assert_ok!(Auctions::bid(Origin::signed(1), 0.into(), 1, 1, 1, 5));
			assert_eq!(Balances::reserved_balance(1), 5);
			run_to_block(10);

Shawn Tabrizi's avatar
Shawn Tabrizi committed
1243
			assert_eq!(leases(), vec![((0.into(), 1), LeaseData { leaser: 1, amount: 5 }),]);
1244
1245
1246
1247
1248
1249
1250
1251
			assert_eq!(TestLeaser::deposit_held(0.into(), &1), 5);

			assert_ok!(Auctions::new_auction(Origin::signed(6), 5, 2));
			assert_ok!(Auctions::bid(Origin::signed(1), 1.into(), 2, 2, 2, 6));
			// 6 reserved since we are bidding on a new para; only works because we don't
			assert_eq!(Balances::reserved_balance(1), 6);
			run_to_block(20);

Shawn Tabrizi's avatar
Shawn Tabrizi committed
1252
1253
1254
1255
1256
1257
1258
			assert_eq!(
				leases(),
				vec![
					((0.into(), 1), LeaseData { leaser: 1, amount: 5 }),
					((1.into(), 2), LeaseData { leaser: 1, amount: 6 }),
				]
			);
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
			assert_eq!(TestLeaser::deposit_held(0.into(), &1), 5);
			assert_eq!(TestLeaser::deposit_held(1.into(), &1), 6);
		});
	}

	#[test]
	fn multiple_bids_work_pre_ending() {
		new_test_ext().execute_with(|| {
			run_to_block(1);

			assert_ok!(Auctions::new_auction(Origin::signed(6), 5, 1));

			for i in 1..6u64 {
				run_to_block(i as _);
				assert_ok!(Auctions::bid(Origin::signed(i), 0.into(), 1, 1, 4, i));
				for j in 1..6 {
					assert_eq!(Balances::reserved_balance(j), if j == i { j } else { 0 });
					assert_eq!(Balances::free_balance(j), if j == i { j * 9 } else { j * 10 });
				}
			}

			run_to_block(9);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1281
1282
1283
1284
1285
1286
1287
1288
1289
			assert_eq!(
				leases(),
				vec![
					((0.into(), 1), LeaseData { leaser: 5, amount: 5 }),
					((0.into(), 2), LeaseData { leaser: 5, amount: 5 }),
					((0.into(), 3), LeaseData { leaser: 5, amount: 5 }),
					((0.into(), 4), LeaseData { leaser: 5, amount: 5 }),
				]
			);
1290
1291
1292
1293
1294
1295
1296
1297
		});
	}

	#[test]
	fn multiple_bids_work_post_ending() {
		new_test_ext().execute_with(|| {
			run_to_block(1);

1298
			assert_ok!(Auctions::new_auction(Origin::signed(6), 0, 1));
1299
1300

			for i in 1..6u64 {
1301
				run_to_block(((i - 1) / 2 + 1) as _);
1302
1303
				assert_ok!(Auctions::bid(Origin::signed(i), 0.into(), 1, 1, 4, i));
				for j in 1..6 {
1304
1305
					assert_eq!(Balances::reserved_balance(j), if j <= i { j } else { 0 });
					assert_eq!(Balances::free_balance(j), if j <= i { j * 9 } else { j * 10 });
1306
1307
				}
			}
1308
1309
1310
			for i in 1..6u64 {
				assert_eq!(ReservedAmounts::<Test>::get((i, ParaId::from(0))).unwrap(), i);
			}
1311

1312
			run_to_block(5);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1313
1314
1315
1316
1317
1318
			assert_eq!(
				leases(),
				(1..=4)
					.map(|i| ((0.into(), i), LeaseData { leaser: 2, amount: 2 }))
					.collect::<Vec<_>>()
			);
1319
1320
1321
1322
1323
		});
	}

	#[test]
	fn incomplete_calculate_winners_works() {
1324
1325
1326
		let mut winning = [None; SlotRange::SLOT_RANGE_COUNT];
		winning[SlotRange::ThreeThree as u8 as usize] = Some((1, 0.into(), 1));

Shawn Tabrizi's avatar
Shawn Tabrizi committed
1327
		let winners = vec![(1, 0.into(), 1, SlotRange::ThreeThree)];
1328
1329
1330
1331
1332
1333

		assert_eq!(Auctions::calculate_winners(winning), winners);
	}

	#[test]
	fn first_incomplete_calculate_winners_works() {
1334
1335
1336
		let mut winning = [None; SlotRange::SLOT_RANGE_COUNT];
		winning[0] = Some((1, 0.into(), 1));

Shawn Tabrizi's avatar
Shawn Tabrizi committed
1337
		let winners = vec![(1, 0.into(), 1, SlotRange::ZeroZero)];
1338
1339
1340
1341
1342
1343

		assert_eq!(Auctions::calculate_winners(winning), winners);
	}

	#[test]
	fn calculate_winners_works() {
1344
1345
1346
1347
1348
1349
1350
		let mut winning = [None; SlotRange::SLOT_RANGE_COUNT];
		winning[SlotRange::ZeroZero as u8 as usize] = Some((2, 0.into(), 2));
		winning[SlotRange::ZeroThree as u8 as usize] = Some((1, 100.into(), 1));
		winning[SlotRange::OneOne as u8 as usize] = Some((3, 1.into(), 1));
		winning[SlotRange::TwoTwo as u8 as usize] = Some((1, 2.into(), 53));
		winning[SlotRange::ThreeThree as u8 as usize] = Some((5, 3.into(), 1));

1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
		let winners = vec![
			(2, 0.into(), 2, SlotRange::ZeroZero),
			(3, 1.into(), 1, SlotRange::OneOne),
			(1, 2.into(), 53, SlotRange::TwoTwo),
			(5, 3.into(), 1, SlotRange::ThreeThree),
		];
		assert_eq!(Auctions::calculate_winners(winning.clone()), winners);

		winning[SlotRange::ZeroOne as u8 as usize] = Some((4, 10.into(), 3));
		let winners = vec![
			(4, 10.into(), 3, SlotRange::ZeroOne),
			(1, 2.into(), 53, SlotRange::TwoTwo),
			(5, 3.into(), 1, SlotRange::ThreeThree),
		];
		assert_eq!(Auctions::calculate_winners(winning.clone()), winners);

		winning[SlotRange::ZeroThree as u8 as usize] = Some((1, 100.into(), 100));
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1368
		let winners = vec![(1, 100.into(), 100, SlotRange::ZeroThree)];
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
		assert_eq!(Auctions::calculate_winners(winning.clone()), winners);
	}

	#[test]
	fn lower_bids_are_correctly_refunded() {
		new_test_ext().execute_with(|| {
			run_to_block(1);
			assert_ok!(Auctions::new_auction(Origin::signed(6), 1, 1));
			let para_1 = ParaId::from(1);
			let para_2 = ParaId::from(2);

			// Make a bid and reserve a balance
			assert_ok!(Auctions::bid(Origin::signed(1), para_1, 1, 1, 4, 10));
			assert_eq!(Balances::reserved_balance(1), 10);
			assert_eq!(ReservedAmounts::<Test>::get((1, para_1)), Some(10));
			assert_eq!(Balances::reserved_balance(2), 0);
			assert_eq!(ReservedAmounts::<Test>::get((2, para_2)), None);

			// Bigger bid, reserves new balance and returns funds
			assert_ok!(Auctions::bid(Origin::signed(2), para_2, 1, 1, 4, 20));
			assert_eq!(Balances::reserved_balance(1), 0);
			assert_eq!(ReservedAmounts::<Test>::get((1, para_1)), None);
			assert_eq!(Balances::reserved_balance(2), 20);
			assert_eq!(ReservedAmounts::<Test>::get((2, para_2)), Some(20));
		});
	}

	#[test]
	fn initialize_winners_in_ending_period_works() {
		new_test_ext().execute_with(|| {
			run_to_block(1);
			assert_ok!(Auctions::new_auction(Origin::signed(6), 9, 1));
			let para_1 = ParaId::from(1);
			let para_2 = ParaId::from(2);
			let para_3 = ParaId::from(3);

			// Make bids
			assert_ok!(Auctions::bid(Origin::signed(1), para_1, 1, 1, 4, 10));
			assert_ok!(Auctions::bid(Origin::signed(2), para_2, 1, 3, 4, 20));

Shawn Tabrizi's avatar
Shawn Tabrizi committed
1409
1410
1411
1412
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::StartingPeriod
			);
1413
1414
1415
1416
			let mut winning = [None; SlotRange::SLOT_RANGE_COUNT];
			winning[SlotRange::ZeroThree as u8 as usize] = Some((1, para_1, 10));
			winning[SlotRange::TwoThree as u8 as usize] = Some((2, para_2, 20));
			assert_eq!(Auctions::winning(0), Some(winning));
1417
1418

			run_to_block(9);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1419
1420
1421
1422
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::StartingPeriod
			);
1423
1424

			run_to_block(10);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1425
1426
1427
1428
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::EndingPeriod(0, 0)
			);
1429
			assert_eq!(Auctions::winning(0), Some(winning));
1430
1431

			run_to_block(11);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1432
1433
1434
1435
			assert_eq!(
				Auctions::auction_status(System::block_number()),
				AuctionStatus::<u32>::EndingPeriod(1, 0)
			);
1436
			assert_eq!(Auctions::winning(1), Some(winning));
1437
1438
1439
			assert_ok!(Auctions::bid(Origin::signed(3), para_3, 1, 3, 4, 30