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