Novacoin/StakeModifier.cs

   1 \feff/**
   2 *  Novacoin classes library
   3 *  Copyright (C) 2015 Alex D. (balthazar.ad@gmail.com)
   4
   5 *  This program is free software: you can redistribute it and/or modify
   6 *  it under the terms of the GNU Affero General Public License as
   7 *  published by the Free Software Foundation, either version 3 of the
   8 *  License, or (at your option) any later version.
   9
  10 *  This program is distributed in the hope that it will be useful,
  11 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 *  GNU Affero General Public License for more details.
  14
  15 *  You should have received a copy of the GNU Affero General Public License
  16 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17 */
  18
  19
  20 using System;
  21 using System.Collections.Generic;
  22 using System.Diagnostics.Contracts;
  23 using System.IO;
  24 using System.Linq;
  25
  26 namespace Novacoin
  27 {
  28     /// <summary>
  29     /// Stake modifier calculation. Doesn't work properly, for now.
  30     /// </summary>
  31     public class StakeModifier
  32     {
  33         /// <summary>
  34         /// 30 days as zero time weight
  35         /// </summary>
  36         public const uint nStakeMinAge = 60 * 60 * 24 * 30;
  37
  38         /// <summary>
  39         /// 90 days as full weight
  40         /// </summary>
  41         public const uint nStakeMaxAge = 60 * 60 * 24 * 90;
  42
  43         /// <summary>
  44         /// 10-minute stakes spacing
  45         /// </summary>
  46         public const uint nStakeTargetSpacing = 10 * 60;
  47
  48         /// <summary>
  49         /// Time to elapse before new modifier is computed
  50         /// </summary>
  51         public const uint nModifierInterval = 6 * 60 * 60;
  52
  53         /// <summary>
  54         /// Ratio of group interval length between the last group and the first group
  55         /// </summary>
  56         public const int nModifierIntervalRatio = 3;
  57
  58         /// <summary>
  59         /// Protocol switch time for fixed kernel modifier interval
  60         ///
  61         /// Mon, 20 Oct 2014 00:00:00 GMT
  62         /// </summary>
  63         internal const uint nModifierSwitchTime = 1413763200;
  64
  65         /// <summary>
  66         /// Whether the given block is subject to new modifier protocol
  67         /// </summary>
  68         /// <param name="nTimeBlock">Block timestamp</param>
  69         /// <returns>Result</returns>
  70         internal static bool IsFixedModifierInterval(uint nTimeBlock)
  71         {
  72             return (nTimeBlock >= nModifierSwitchTime);
  73         }
  74
  75         /// <summary>
  76         /// Get the last stake modifier and its generation time from a given block
  77         /// </summary>
  78         /// <param name="cursor">Block cursor</param>
  79         /// <param name="nStakeModifier">Stake modifier (ref)</param>
  80         /// <param name="nModifierTime">Stake modifier generation time (ref)</param>
  81         /// <returns></returns>
  82         internal static bool GetLastStakeModifier(CBlockStoreItem cursor, ref long nStakeModifier, ref uint nModifierTime)
  83         {
  84             if (cursor == null)
  85             {
  86                 return false;
  87             }
  88
  89             while (cursor != null && cursor.prev != null && !cursor.GeneratedStakeModifier)
  90             {
  91                 cursor = cursor.prev;
  92             }
  93
  94             if (!cursor.GeneratedStakeModifier)
  95             {
  96                 return false;  // no generation at genesis block
  97             }
  98
  99             nStakeModifier = cursor.nStakeModifier;
 100             nModifierTime = cursor.nTime;
 101
 102             return true;
 103         }
 104
 105         /// <summary>
 106         /// Get selection interval section (in seconds)
 107         /// </summary>
 108         /// <param name="nSection"></param>
 109         /// <returns></returns>
 110         internal static long GetStakeModifierSelectionIntervalSection(int nSection)
 111         {
 112             Contract.Assert(nSection >= 0 && nSection < 64);
 113             return (nModifierInterval * 63 / (63 + ((63 - nSection) * (nModifierIntervalRatio - 1))));
 114         }
 115
 116         /// <summary>
 117         /// Get stake modifier selection interval (in seconds)
 118         /// </summary>
 119         /// <returns></returns>
 120         internal static long GetStakeModifierSelectionInterval()
 121         {
 122             long nSelectionInterval = 0;
 123             for (int nSection = 0; nSection < 64; nSection++)
 124                 nSelectionInterval += GetStakeModifierSelectionIntervalSection(nSection);
 125             return nSelectionInterval;
 126         }
 127
 128
 129         /// <summary>
 130         /// Select a block from the candidate blocks in vSortedByTimestamp, excluding
 131         /// already selected blocks in vSelectedBlocks, and with timestamp
 132         /// up to nSelectionIntervalStop.
 133         /// </summary>
 134         /// <param name="sortedByTimestamp"></param>
 135         /// <param name="mapSelectedBlocks"></param>
 136         /// <param name="nSelectionIntervalStop">Upper boundary for timestamp value.</param>
 137         /// <param name="nStakeModifierPrev">Previous value of stake modifier.</param>
 138         /// <param name="selectedCursor">Selection result.</param>
 139         /// <returns></returns>
 140         internal static bool SelectBlockFromCandidates(List<Tuple<uint, uint256>> sortedByTimestamp, Dictionary<uint256, CBlockStoreItem> mapSelectedBlocks, long nSelectionIntervalStop, long nStakeModifierPrev, ref CBlockStoreItem selectedCursor)
 141         {
 142             bool fSelected = false;
 143             uint256 hashBest = 0;
 144             selectedCursor = null;
 145             foreach (var item in sortedByTimestamp)
 146             {
 147                 CBlockStoreItem cursor = CBlockStore.Instance.GetMapCursor(item.Item2);
 148
 149                 if (cursor == null)
 150                 {
 151                     return false; // Failed to find block index for candidate block
 152                 }
 153
 154                 if (fSelected && cursor.nTime > nSelectionIntervalStop)
 155                 {
 156                     break;
 157                 }
 158
 159                 uint256 selectedBlockHash = cursor.Hash;
 160
 161                 if (mapSelectedBlocks.Count(pair => pair.Key == selectedBlockHash) > 0)
 162                 {
 163                     continue;
 164                 }
 165
 166                 // compute the selection hash by hashing its proof-hash and the
 167                 // previous proof-of-stake modifier
 168
 169                 var hashProof = cursor.IsProofOfStake ? (uint256)cursor.hashProofOfStake : selectedBlockHash;
 170                 uint256 hashSelection;
 171
 172                 var s = new MemoryStream();
 173                 var writer = new BinaryWriter(s);
 174
 175                 writer.Write(hashProof);
 176                 writer.Write(nStakeModifierPrev);
 177                 hashSelection = CryptoUtils.ComputeHash256(s.ToArray());
 178                 writer.Close();
 179
 180                 // the selection hash is divided by 2**32 so that proof-of-stake block
 181                 // is always favored over proof-of-work block. this is to preserve
 182                 // the energy efficiency property
 183                 if (cursor.IsProofOfStake)
 184                     hashSelection >>= 32;
 185                 if (fSelected && hashSelection < hashBest)
 186                 {
 187                     hashBest = hashSelection;
 188                     selectedCursor = cursor;
 189                 }
 190                 else if (!fSelected)
 191                 {
 192                     fSelected = true;
 193                     hashBest = hashSelection;
 194                     selectedCursor = cursor;
 195                 }
 196             }
 197
 198             return fSelected;
 199         }
 200
 201         /// <summary>
 202         /// Stake Modifier (hash modifier of proof-of-stake):
 203         /// The purpose of stake modifier is to prevent a txout (coin) owner from
 204         /// computing future proof-of-stake generated by this txout at the time
 205         /// of transaction confirmation. To meet kernel protocol, the txout
 206         /// must hash with a future stake modifier to generate the proof.
 207         /// Stake modifier consists of bits each of which is contributed from a
 208         /// selected block of a given block group in the past.
 209         /// The selection of a block is based on a hash of the block's proof-hash and
 210         /// the previous stake modifier.
 211         /// Stake modifier is recomputed at a fixed time interval instead of every
 212         /// block. This is to make it difficult for an attacker to gain control of
 213         /// additional bits in the stake modifier, even after generating a chain of
 214         /// blocks.
 215         /// </summary>
 216         public static bool ComputeNextStakeModifier(CBlockStoreItem cursorCurrent, ref long nStakeModifier, ref bool fGeneratedStakeModifier)
 217         {
 218             nStakeModifier = 0;
 219             fGeneratedStakeModifier = false;
 220             CBlockStoreItem cursorPrev = cursorCurrent.prev;
 221             if (cursorPrev == null)
 222             {
 223                 fGeneratedStakeModifier = true;
 224                 return true;  // genesis block's modifier is 0
 225             }
 226
 227             // First find current stake modifier and its generation block time
 228             // if it's not old enough, return the same stake modifier
 229             uint nModifierTime = 0;
 230             if (!GetLastStakeModifier(cursorPrev, ref nStakeModifier, ref nModifierTime))
 231                 return false; // Unable to get last modifier
 232             if (nModifierTime / nModifierInterval >= cursorPrev.nTime / nModifierInterval)
 233             {
 234                 // no new interval keep current modifier
 235                 return true;
 236             }
 237             if (nModifierTime / nModifierInterval >= cursorCurrent.nTime / nModifierInterval)
 238             {
 239                 // fixed interval protocol requires current block timestamp also be in a different modifier interval
 240                 if (IsFixedModifierInterval(cursorCurrent.nTime))
 241                 {
 242                     // no new interval keep current modifier
 243                     return true;
 244                 }
 245                 else
 246                 {
 247                     // old modifier not meeting fixed modifier interval
 248                 }
 249             }
 250
 251             // Sort candidate blocks by timestamp
 252             List<Tuple<uint, uint256>> vSortedByTimestamp = new List<Tuple<uint, uint256>>();
 253             // vSortedByTimestamp.reserve(64 * nModifierInterval / nStakeTargetSpacing);
 254
 255             long nSelectionInterval = GetStakeModifierSelectionInterval();
 256             long nSelectionIntervalStart = (cursorPrev.nTime / nModifierInterval) * nModifierInterval - nSelectionInterval;
 257
 258             CBlockStoreItem cursor = cursorPrev;
 259             while (cursor != null && cursor.nTime >= nSelectionIntervalStart)
 260             {
 261                 vSortedByTimestamp.Add(new Tuple<uint, uint256>(cursor.nTime, cursor.Hash));
 262                 cursor = cursor.prev;
 263             }
 264             uint nHeightFirstCandidate = cursor != null ? (cursor.nHeight + 1) : 0;
 265             vSortedByTimestamp.Reverse();
 266             vSortedByTimestamp.Sort((x, y) => x.Item1.CompareTo(y.Item1));
 267
 268             // Select 64 blocks from candidate blocks to generate stake modifier
 269             long nStakeModifierNew = 0;
 270             long nSelectionIntervalStop = nSelectionIntervalStart;
 271             Dictionary<uint256, CBlockStoreItem> mapSelectedBlocks = new Dictionary<uint256, CBlockStoreItem>();
 272             for (int nRound = 0; nRound < Math.Min(64, (int)vSortedByTimestamp.Count); nRound++)
 273             {
 274                 // add an interval section to the current selection round
 275                 nSelectionIntervalStop += GetStakeModifierSelectionIntervalSection(nRound);
 276                 // select a block from the candidates of current round
 277                 if (!SelectBlockFromCandidates(vSortedByTimestamp, mapSelectedBlocks, nSelectionIntervalStop, nStakeModifier, ref cursor))
 278                 {
 279                     return false; // unable to select block
 280                 }
 281
 282                 // write the entropy bit of the selected block
 283                 nStakeModifierNew |= (((long)cursor.StakeEntropyBit) << nRound);
 284
 285                 // add the selected block from candidates to selected list
 286                 mapSelectedBlocks.Add(cursor.Hash, cursor);
 287             }
 288
 289             nStakeModifier = nStakeModifierNew;
 290             fGeneratedStakeModifier = true;
 291             return true;
 292         }
 293
 294         /// <summary>
 295         /// The stake modifier used to hash for a stake kernel is chosen as the stake
 296         /// modifier about a selection interval later than the coin generating the kernel
 297         /// </summary>
 298         static bool GetKernelStakeModifier(uint256 hashBlockFrom, ref long nStakeModifier, ref uint nStakeModifierHeight, ref uint nStakeModifierTime)
 299         {
 300             nStakeModifier = 0;
 301             var cursorFrom = CBlockStore.Instance.GetMapCursor(hashBlockFrom);
 302             if (cursorFrom == null)
 303             {
 304                 return false; // Block not indexed
 305             }
 306
 307             nStakeModifierHeight = cursorFrom.nHeight;
 308             nStakeModifierTime = cursorFrom.nTime;
 309
 310             long nStakeModifierSelectionInterval = GetStakeModifierSelectionInterval();
 311             CBlockStoreItem cursor = cursorFrom;
 312
 313             // loop to find the stake modifier later by a selection interval
 314             while (nStakeModifierTime < cursorFrom.nTime + nStakeModifierSelectionInterval)
 315             {
 316                 if (cursor.next == null)
 317                 {
 318                     // reached best block; may happen if node is behind on block chain
 319                     return false;
 320                 }
 321                 cursor = cursor.next;
 322                 if (cursor.GeneratedStakeModifier)
 323                 {
 324                     nStakeModifierHeight = cursor.nHeight;
 325                     nStakeModifierTime = cursor.nTime;
 326                 }
 327             }
 328             nStakeModifier = cursor.nStakeModifier;
 329
 330             return true;
 331         }
 332
 333         public static bool GetKernelStakeModifier(uint256 hashBlockFrom, ref long nStakeModifier)
 334         {
 335             uint nStakeModifierHeight = 0;
 336             uint nStakeModifierTime = 0;
 337
 338             return GetKernelStakeModifier(hashBlockFrom, ref nStakeModifier, ref nStakeModifierHeight, ref nStakeModifierTime);
 339         }
 340
 341         public static bool CheckStakeKernelHash(uint nBits, uint256 hashBlockFrom, uint nTimeBlockFrom, uint nTxPrevOffset, CTransaction txPrev, COutPoint prevout, uint nTimeTx, ref uint256 hashProofOfStake, ref uint256 targetProofOfStake)
 342         {
 343             if (nTimeTx < txPrev.nTime)
 344             {
 345                 return false; // Transaction timestamp violation
 346             }
 347
 348             if (nTimeBlockFrom + nStakeMinAge > nTimeTx) // Min age requirement
 349             {
 350                 return false; // Min age violation
 351             }
 352
 353             uint256 nTargetPerCoinDay = 0;
 354             nTargetPerCoinDay.Compact = nBits;
 355
 356             ulong nValueIn = txPrev.vout[prevout.n].nValue;
 357             uint256 nCoinDayWeight = new uint256(nValueIn) * GetWeight(txPrev.nTime, nTimeTx) / CTransaction.nCoin / (24 * 60 * 60);
 358
 359             targetProofOfStake = nCoinDayWeight * nTargetPerCoinDay;
 360
 361             // Calculate hash
 362             long nStakeModifier = 0;
 363             uint nStakeModifierHeight = 0;
 364             uint nStakeModifierTime = 0;
 365             if (!GetKernelStakeModifier(hashBlockFrom, ref nStakeModifier, ref nStakeModifierHeight, ref nStakeModifierTime))
 366             {
 367                 return false;
 368             }
 369
 370             MemoryStream s = new MemoryStream();
 371             BinaryWriter w = new BinaryWriter(s);
 372
 373             w.Write(nStakeModifier);
 374             w.Write(nTimeBlockFrom);
 375             w.Write(nTxPrevOffset);
 376             w.Write(txPrev.nTime);
 377             w.Write(prevout.n);
 378             w.Write(nTimeTx);
 379
 380             hashProofOfStake = CryptoUtils.ComputeHash256(s.ToArray());
 381             w.Close();
 382
 383             // Now check if proof-of-stake hash meets target protocol
 384             if (hashProofOfStake > targetProofOfStake)
 385                 return false;
 386
 387             return true;
 388         }
 389
 390         // Get time weight using supplied timestamps
 391         static ulong GetWeight(ulong nIntervalBeginning, ulong nIntervalEnd)
 392         {
 393             // Kernel hash weight starts from 0 at the 30-day min age
 394             // this change increases active coins participating the hash and helps
 395             // to secure the network when proof-of-stake difficulty is low
 396             //
 397             // Maximum TimeWeight is 90 days.
 398
 399             return Math.Min(nIntervalEnd - nIntervalBeginning - nStakeMinAge, nStakeMaxAge);
 400         }
 401
 402         internal static uint GetStakeModifierChecksum(CBlockStoreItem itemTemplate)
 403         {
 404             Contract.Assert(itemTemplate.prev != null || (uint256)itemTemplate.Hash == NetInfo.nHashGenesisBlock);
 405
 406             // Hash previous checksum with flags, hashProofOfStake and nStakeModifier
 407             MemoryStream ss = new MemoryStream();
 408             BinaryWriter writer = new BinaryWriter(ss);
 409
 410             if (itemTemplate.prev != null)
 411             {
 412                 writer.Write(itemTemplate.prev.nStakeModifierChecksum);
 413             }
 414
 415             writer.Write((uint)itemTemplate.BlockTypeFlag);
 416
 417             if (itemTemplate.IsProofOfStake)
 418             {
 419                 writer.Write(itemTemplate.hashProofOfStake);
 420             }
 421             else
 422             {
 423                 writer.Write(new uint256(0));
 424             }
 425             writer.Write(itemTemplate.nStakeModifier);
 426
 427             uint256 hashChecksum = CryptoUtils.ComputeHash256(ss.ToArray());
 428             writer.Close();
 429
 430             hashChecksum >>= (256 - 32);
 431
 432             return (uint)hashChecksum.Low64;
 433         }
 434
 435         internal static bool CheckProofOfStake(CTransaction tx, uint nBits, ref uint256 hashProofOfStake, ref uint256 targetProofOfStake)
 436         {
 437             if (!tx.IsCoinStake)
 438             {
 439                 return false; // called on non-coinstake
 440             }
 441
 442             // Kernel (input 0) must match the stake hash target per coin age (nBits)
 443             CTxIn txin = tx.vin[0];
 444
 445             // Read block header
 446
 447             CBlock block = null;
 448             CTransaction txPrev = null;
 449             long nBlockPos = 0, nTxPos = 0;
 450
 451             if (!CBlockStore.Instance.GetBlockByTransactionID(txin.prevout.hash, ref block, ref txPrev, ref nBlockPos, ref nTxPos))
 452             {
 453                 return false; // unable to read block of previous transaction
 454             }
 455
 456             if (!ScriptCode.VerifyScript(txin.scriptSig, txPrev.vout[txin.prevout.n].scriptPubKey, tx, 0, (int)scriptflag.SCRIPT_VERIFY_P2SH, 0))
 457             {
 458                 return false; // vin[0] signature check failed
 459             }
 460
 461             if (!CheckStakeKernelHash(nBits, block.header.Hash, block.header.nTime, (uint)(nTxPos - nBlockPos), txPrev, txin.prevout, tx.nTime, ref hashProofOfStake, ref targetProofOfStake))
 462             {
 463                 return false; // check kernel failed on coinstake
 464             }
 465
 466             return true;
 467         }
 468     }
 469 }