Novacoin/StakeModifier.cs

   1 \feffusing System;
   2 using System.Collections.Generic;
   3 using System.Diagnostics.Contracts;
   4 using System.IO;
   5 using System.Linq;
   6
   7 namespace Novacoin
   8 {
   9     public class StakeModifier
  10     {
  11         /// <summary>
  12         /// 30 days as zero time weight
  13         /// </summary>
  14         public const uint nStakeMinAge = 60 * 60 * 24 * 30;
  15
  16         /// <summary>
  17         /// 90 days as full weight
  18         /// </summary>
  19         public const uint nStakeMaxAge = 60 * 60 * 24 * 90;
  20
  21         /// <summary>
  22         /// 10-minute stakes spacing
  23         /// </summary>
  24         public const uint nStakeTargetSpacing = 10 * 60;
  25
  26         /// <summary>
  27         /// Time to elapse before new modifier is computed
  28         /// </summary>
  29         public const uint nModifierInterval = 6 * 60 * 60;
  30
  31         /// <summary>
  32         /// Ratio of group interval length between the last group and the first group
  33         /// </summary>
  34         public const int nModifierIntervalRatio = 3;
  35
  36         /// <summary>
  37         /// Protocol switch time for fixed kernel modifier interval
  38         ///
  39         /// Mon, 20 Oct 2014 00:00:00 GMT
  40         /// </summary>
  41         internal const uint nModifierSwitchTime = 1413763200;
  42
  43         /// <summary>
  44         /// Whether the given block is subject to new modifier protocol
  45         /// </summary>
  46         /// <param name="nTimeBlock">Block timestamp</param>
  47         /// <returns>Result</returns>
  48         internal static bool IsFixedModifierInterval(uint nTimeBlock)
  49         {
  50             return (nTimeBlock >= nModifierSwitchTime);
  51         }
  52
  53         /// <summary>
  54         /// Get the last stake modifier and its generation time from a given block
  55         /// </summary>
  56         /// <param name="cursor">Block cursor</param>
  57         /// <param name="nStakeModifier">Stake modifier (ref)</param>
  58         /// <param name="nModifierTime">Stake modifier generation time (ref)</param>
  59         /// <returns></returns>
  60         internal static bool GetLastStakeModifier(CBlockStoreItem cursor, ref long nStakeModifier, ref uint nModifierTime)
  61         {
  62             if (cursor == null)
  63             {
  64                 return false;
  65             }
  66
  67             while (cursor != null && cursor.prev != null && !cursor.GeneratedStakeModifier)
  68             {
  69                 cursor = cursor.prev;
  70             }
  71
  72             if (!cursor.GeneratedStakeModifier)
  73             {
  74                 return false;  // no generation at genesis block
  75             }
  76
  77             nStakeModifier = cursor.nStakeModifier;
  78             nModifierTime = cursor.nTime;
  79
  80             return true;
  81         }
  82
  83         /// <summary>
  84         /// Get selection interval section (in seconds)
  85         /// </summary>
  86         /// <param name="nSection"></param>
  87         /// <returns></returns>
  88         internal static long GetStakeModifierSelectionIntervalSection(int nSection)
  89         {
  90             Contract.Assert(nSection >= 0 && nSection < 64);
  91             return (nModifierInterval * 63 / (63 + ((63 - nSection) * (nModifierIntervalRatio - 1))));
  92         }
  93
  94         /// <summary>
  95         /// Get stake modifier selection interval (in seconds)
  96         /// </summary>
  97         /// <returns></returns>
  98         static long GetStakeModifierSelectionInterval()
  99         {
 100             long nSelectionInterval = 0;
 101             for (int nSection = 0; nSection < 64; nSection++)
 102                 nSelectionInterval += GetStakeModifierSelectionIntervalSection(nSection);
 103             return nSelectionInterval;
 104         }
 105
 106
 107         /// <summary>
 108         /// Select a block from the candidate blocks in vSortedByTimestamp, excluding
 109         /// already selected blocks in vSelectedBlocks, and with timestamp
 110         /// up to nSelectionIntervalStop.
 111         /// </summary>
 112         /// <param name="sortedByTimestamp"></param>
 113         /// <param name="mapSelectedBlocks"></param>
 114         /// <param name="nSelectionIntervalStop">Upper boundary for timestamp value.</param>
 115         /// <param name="nStakeModifierPrev">Previous value of stake modifier.</param>
 116         /// <param name="selectedCursor">Selection result.</param>
 117         /// <returns></returns>
 118         static bool SelectBlockFromCandidates(List<Tuple<uint, uint256>> sortedByTimestamp, Dictionary<uint256, CBlockStoreItem> mapSelectedBlocks, long nSelectionIntervalStop, long nStakeModifierPrev, ref CBlockStoreItem selectedCursor)
 119         {
 120             bool fSelected = false;
 121             uint256 hashBest = 0;
 122             selectedCursor = null;
 123             foreach (var item in sortedByTimestamp)
 124             {
 125                 CBlockStoreItem cursor = CBlockStore.Instance.GetCursor(item.Item2);
 126
 127                 if (cursor == null)
 128                 {
 129                     return false; // Failed to find block index for candidate block
 130                 }
 131
 132                 if (fSelected && cursor.nTime > nSelectionIntervalStop)
 133                 {
 134                     break;
 135                 }
 136
 137                 uint256 selectedBlockHash = cursor.Hash;
 138
 139                 if (mapSelectedBlocks.Count(pair => pair.Key == selectedBlockHash) > 0)
 140                 {
 141                     continue;
 142                 }
 143
 144                 // compute the selection hash by hashing its proof-hash and the
 145                 // previous proof-of-stake modifier
 146
 147                 var hashProof = cursor.IsProofOfStake ? (uint256)cursor.hashProofOfStake : selectedBlockHash;
 148                 uint256 hashSelection;
 149
 150                 var s = new MemoryStream();
 151                 var writer = new BinaryWriter(s);
 152
 153                 writer.Write(hashProof);
 154                 writer.Write(nStakeModifierPrev);
 155                 hashSelection = CryptoUtils.ComputeHash256(s.ToArray());
 156                 writer.Close();
 157
 158                 // the selection hash is divided by 2**32 so that proof-of-stake block
 159                 // is always favored over proof-of-work block. this is to preserve
 160                 // the energy efficiency property
 161                 if (cursor.IsProofOfStake)
 162                     hashSelection >>= 32;
 163                 if (fSelected && hashSelection < hashBest)
 164                 {
 165                     hashBest = hashSelection;
 166                     selectedCursor = cursor;
 167                 }
 168                 else if (!fSelected)
 169                 {
 170                     fSelected = true;
 171                     hashBest = hashSelection;
 172                     selectedCursor = cursor;
 173                 }
 174             }
 175
 176             return fSelected;
 177         }
 178
 179         /// <summary>
 180         /// Stake Modifier (hash modifier of proof-of-stake):
 181         /// The purpose of stake modifier is to prevent a txout (coin) owner from
 182         /// computing future proof-of-stake generated by this txout at the time
 183         /// of transaction confirmation. To meet kernel protocol, the txout
 184         /// must hash with a future stake modifier to generate the proof.
 185         /// Stake modifier consists of bits each of which is contributed from a
 186         /// selected block of a given block group in the past.
 187         /// The selection of a block is based on a hash of the block's proof-hash and
 188         /// the previous stake modifier.
 189         /// Stake modifier is recomputed at a fixed time interval instead of every
 190         /// block. This is to make it difficult for an attacker to gain control of
 191         /// additional bits in the stake modifier, even after generating a chain of
 192         /// blocks.
 193         /// </summary>
 194         bool ComputeNextStakeModifier(CBlockStoreItem cursorCurrent, ref long nStakeModifier, ref bool fGeneratedStakeModifier)
 195         {
 196             nStakeModifier = 0;
 197             fGeneratedStakeModifier = false;
 198             CBlockStoreItem cursorPrev = cursorCurrent.prev;
 199             if (cursorPrev == null)
 200             {
 201                 fGeneratedStakeModifier = true;
 202                 return true;  // genesis block's modifier is 0
 203             }
 204
 205             // First find current stake modifier and its generation block time
 206             // if it's not old enough, return the same stake modifier
 207             uint nModifierTime = 0;
 208             if (!GetLastStakeModifier(cursorPrev, ref nStakeModifier, ref nModifierTime))
 209                 return false; // Unable to get last modifier
 210             if (nModifierTime / nModifierInterval >= cursorPrev.nTime / nModifierInterval)
 211             {
 212                 // no new interval keep current modifier
 213                 return true;
 214             }
 215             if (nModifierTime / nModifierInterval >= cursorCurrent.nTime / nModifierInterval)
 216             {
 217                 // fixed interval protocol requires current block timestamp also be in a different modifier interval
 218                 if (IsFixedModifierInterval(cursorCurrent.nTime))
 219                 {
 220                     // no new interval keep current modifier
 221                     return true;
 222                 }
 223                 else
 224                 {
 225                     // old modifier not meeting fixed modifier interval
 226                 }
 227             }
 228
 229             // Sort candidate blocks by timestamp
 230             List<Tuple<uint, uint256>> vSortedByTimestamp = new List<Tuple<uint, uint256>>();
 231             // vSortedByTimestamp.reserve(64 * nModifierInterval / nStakeTargetSpacing);
 232
 233             long nSelectionInterval = GetStakeModifierSelectionInterval();
 234             long nSelectionIntervalStart = (cursorPrev.nTime / nModifierInterval) * nModifierInterval - nSelectionInterval;
 235
 236             CBlockStoreItem cursor = cursorPrev;
 237             while (cursor != null && cursor.nTime >= nSelectionIntervalStart)
 238             {
 239                 vSortedByTimestamp.Add(new Tuple<uint, uint256>(cursor.nTime, cursor.Hash));
 240                 cursor = cursor.prev;
 241             }
 242             uint nHeightFirstCandidate = cursor != null ? (cursor.nHeight + 1) : 0;
 243             vSortedByTimestamp.Reverse();
 244             vSortedByTimestamp.Sort((x, y) => x.Item1.CompareTo(y.Item1));
 245
 246             // Select 64 blocks from candidate blocks to generate stake modifier
 247             long nStakeModifierNew = 0;
 248             long nSelectionIntervalStop = nSelectionIntervalStart;
 249             Dictionary<uint256, CBlockStoreItem> mapSelectedBlocks = new Dictionary<uint256, CBlockStoreItem>();
 250             for (int nRound = 0; nRound < Math.Min(64, (int)vSortedByTimestamp.Count); nRound++)
 251             {
 252                 // add an interval section to the current selection round
 253                 nSelectionIntervalStop += GetStakeModifierSelectionIntervalSection(nRound);
 254                 // select a block from the candidates of current round
 255                 if (!SelectBlockFromCandidates(vSortedByTimestamp, mapSelectedBlocks, nSelectionIntervalStop, nStakeModifier, ref cursor))
 256                 {
 257                     return false; // unable to select block
 258                 }
 259
 260                 // write the entropy bit of the selected block
 261                 nStakeModifierNew |= ((cursor.StakeEntropyBit) << nRound);
 262
 263                 // add the selected block from candidates to selected list
 264                 mapSelectedBlocks.Add(cursor.Hash, cursor);
 265             }
 266
 267             nStakeModifier = nStakeModifierNew;
 268             fGeneratedStakeModifier = true;
 269             return true;
 270         }
 271
 272         /// <summary>
 273         /// The stake modifier used to hash for a stake kernel is chosen as the stake
 274         /// modifier about a selection interval later than the coin generating the kernel
 275         /// </summary>
 276         static bool GetKernelStakeModifier(uint256 hashBlockFrom, ref long nStakeModifier, ref uint nStakeModifierHeight, ref uint nStakeModifierTime)
 277         {
 278             nStakeModifier = 0;
 279             var cursorFrom = CBlockStore.Instance.GetCursor(hashBlockFrom);
 280             if (cursorFrom == null)
 281             {
 282                 return false; // Block not indexed
 283             }
 284
 285             nStakeModifierHeight = cursorFrom.nHeight;
 286             nStakeModifierTime = cursorFrom.nTime;
 287
 288             long nStakeModifierSelectionInterval = GetStakeModifierSelectionInterval();
 289             CBlockStoreItem cursor = cursorFrom;
 290
 291             // loop to find the stake modifier later by a selection interval
 292             while (nStakeModifierTime < cursorFrom.nTime + nStakeModifierSelectionInterval)
 293             {
 294                 if (cursor.next == null)
 295                 {
 296                     // reached best block; may happen if node is behind on block chain
 297                     return false;
 298                 }
 299                 cursor = cursor.next;
 300                 if (cursor.GeneratedStakeModifier)
 301                 {
 302                     nStakeModifierHeight = cursor.nHeight;
 303                     nStakeModifierTime = cursor.nTime;
 304                 }
 305             }
 306             nStakeModifier = cursor.nStakeModifier;
 307
 308             return true;
 309         }
 310
 311         bool GetKernelStakeModifier(uint256 hashBlockFrom, ref long nStakeModifier)
 312         {
 313             uint nStakeModifierHeight = 0;
 314             uint nStakeModifierTime = 0;
 315
 316             return GetKernelStakeModifier(hashBlockFrom, ref nStakeModifier, ref nStakeModifierHeight, ref nStakeModifierTime);
 317         }
 318
 319         bool CheckStakeKernelHash(uint nBits, CBlock blockFrom, uint nTxPrevOffset, CTransaction txPrev, COutPoint prevout, uint nTimeTx, ref uint256 hashProofOfStake, ref uint256 targetProofOfStake)
 320         {
 321             if (nTimeTx < txPrev.nTime)
 322             {
 323                 return false; // Transaction timestamp violation
 324             }
 325
 326             uint nTimeBlockFrom = blockFrom.header.nTime;
 327             if (nTimeBlockFrom + nStakeMinAge > nTimeTx) // Min age requirement
 328             {
 329                 return false; // Min age violation
 330             }
 331
 332             uint256 nTargetPerCoinDay = 0;
 333             nTargetPerCoinDay.Compact = nBits;
 334
 335             ulong nValueIn = txPrev.vout[prevout.n].nValue;
 336             uint256 hashBlockFrom = blockFrom.header.Hash;
 337             uint256 nCoinDayWeight = new uint256(nValueIn) * GetWeight(txPrev.nTime, nTimeTx) / CTransaction.nCoin / (24 * 60 * 60);
 338
 339             targetProofOfStake = nCoinDayWeight * nTargetPerCoinDay;
 340
 341             // Calculate hash
 342             long nStakeModifier = 0;
 343             uint nStakeModifierHeight = 0;
 344             uint nStakeModifierTime = 0;
 345             if (!GetKernelStakeModifier(hashBlockFrom, ref nStakeModifier, ref nStakeModifierHeight, ref nStakeModifierTime))
 346             {
 347                 return false;
 348             }
 349
 350             MemoryStream s = new MemoryStream();
 351             BinaryWriter w = new BinaryWriter(s);
 352
 353             w.Write(nStakeModifier);
 354             w.Write(nTimeBlockFrom);
 355             w.Write(nTxPrevOffset);
 356             w.Write(txPrev.nTime);
 357             w.Write(prevout.n);
 358             w.Write(nTimeTx);
 359
 360             hashProofOfStake = CryptoUtils.ComputeHash256(s.ToArray());
 361             w.Close();
 362
 363             // Now check if proof-of-stake hash meets target protocol
 364             if (hashProofOfStake > targetProofOfStake)
 365                 return false;
 366
 367             return true;
 368         }
 369
 370         // Get time weight using supplied timestamps
 371         static ulong GetWeight(ulong nIntervalBeginning, ulong nIntervalEnd)
 372         {
 373             // Kernel hash weight starts from 0 at the 30-day min age
 374             // this change increases active coins participating the hash and helps
 375             // to secure the network when proof-of-stake difficulty is low
 376             //
 377             // Maximum TimeWeight is 90 days.
 378
 379             return Math.Min(nIntervalEnd - nIntervalBeginning - nStakeMinAge, nStakeMaxAge);
 380         }
 381     }
 382 }