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, out long nStakeModifier, out uint nStakeModifierHeight, out uint nStakeModifierTime)
 299         {
 300             nStakeModifier = 0;
 301             nStakeModifierTime = 0;
 302             nStakeModifierHeight = 0;
 303
 304             var cursorFrom = CBlockStore.Instance.GetMapCursor(hashBlockFrom);
 305             if (cursorFrom == null)
 306             {
 307                 return false; // Block not indexed
 308             }
 309
 310             nStakeModifierHeight = cursorFrom.nHeight;
 311             nStakeModifierTime = cursorFrom.nTime;
 312
 313             long nStakeModifierSelectionInterval = GetStakeModifierSelectionInterval();
 314             CBlockStoreItem cursor = cursorFrom;
 315
 316             // loop to find the stake modifier later by a selection interval
 317             while (nStakeModifierTime < cursorFrom.nTime + nStakeModifierSelectionInterval)
 318             {
 319                 if (cursor.next == null)
 320                 {
 321                     // reached best block; may happen if node is behind on block chain
 322                     return false;
 323                 }
 324                 cursor = cursor.next;
 325                 if (cursor.GeneratedStakeModifier)
 326                 {
 327                     nStakeModifierHeight = cursor.nHeight;
 328                     nStakeModifierTime = cursor.nTime;
 329                 }
 330             }
 331             nStakeModifier = cursor.nStakeModifier;
 332
 333             return true;
 334         }
 335
 336         public static bool GetKernelStakeModifier(uint256 hashBlockFrom, out long nStakeModifier)
 337         {
 338             uint nStakeModifierHeight = 0;
 339             uint nStakeModifierTime = 0;
 340
 341             return GetKernelStakeModifier(hashBlockFrom, out nStakeModifier, out nStakeModifierHeight, out nStakeModifierTime);
 342         }
 343
 344         public static bool CheckStakeKernelHash(uint nBits, uint256 hashBlockFrom, uint nTimeBlockFrom, uint nTxPrevOffset, CTransaction txPrev, COutPoint prevout, uint nTimeTx, out uint256 hashProofOfStake, out uint256 targetProofOfStake)
 345         {
 346             hashProofOfStake = targetProofOfStake = 0;
 347
 348             if (nTimeTx < txPrev.nTime)
 349             {
 350                 return false; // Transaction timestamp violation
 351             }
 352
 353             if (nTimeBlockFrom + nStakeMinAge > nTimeTx) // Min age requirement
 354             {
 355                 return false; // Min age violation
 356             }
 357
 358             uint256 nTargetPerCoinDay = 0;
 359             nTargetPerCoinDay.Compact = nBits;
 360
 361             ulong nValueIn = txPrev.vout[prevout.n].nValue;
 362             uint256 nCoinDayWeight = new uint256(nValueIn) * GetWeight(txPrev.nTime, nTimeTx) / CTransaction.nCoin / (24 * 60 * 60);
 363
 364             targetProofOfStake = nCoinDayWeight * nTargetPerCoinDay;
 365
 366             // Calculate hash
 367             long nStakeModifier;
 368             uint nStakeModifierTime;
 369             uint nStakeModifierHeight;
 370             if (!GetKernelStakeModifier(hashBlockFrom, out nStakeModifier, out nStakeModifierHeight, out nStakeModifierTime))
 371             {
 372                 return false;
 373             }
 374
 375             MemoryStream s = new MemoryStream();
 376             BinaryWriter w = new BinaryWriter(s);
 377
 378             w.Write(nStakeModifier);
 379             w.Write(nTimeBlockFrom);
 380             w.Write(nTxPrevOffset);
 381             w.Write(txPrev.nTime);
 382             w.Write(prevout.n);
 383             w.Write(nTimeTx);
 384
 385             hashProofOfStake = CryptoUtils.ComputeHash256(s.ToArray());
 386             w.Close();
 387
 388             // Now check if proof-of-stake hash meets target protocol
 389             if (hashProofOfStake > targetProofOfStake)
 390                 return false;
 391
 392             return true;
 393         }
 394
 395         // Get time weight using supplied timestamps
 396         static ulong GetWeight(ulong nIntervalBeginning, ulong nIntervalEnd)
 397         {
 398             // Kernel hash weight starts from 0 at the 30-day min age
 399             // this change increases active coins participating the hash and helps
 400             // to secure the network when proof-of-stake difficulty is low
 401             //
 402             // Maximum TimeWeight is 90 days.
 403
 404             return Math.Min(nIntervalEnd - nIntervalBeginning - nStakeMinAge, nStakeMaxAge);
 405         }
 406
 407         internal static uint GetStakeModifierChecksum(ref CBlockStoreItem itemTemplate)
 408         {
 409             Contract.Assert(itemTemplate.prev != null || (uint256)itemTemplate.Hash == NetInfo.nHashGenesisBlock);
 410
 411             // Hash previous checksum with flags, hashProofOfStake and nStakeModifier
 412             MemoryStream ss = new MemoryStream();
 413             BinaryWriter writer = new BinaryWriter(ss);
 414
 415             if (itemTemplate.prev != null)
 416             {
 417                 writer.Write(itemTemplate.prev.nStakeModifierChecksum);
 418             }
 419
 420             writer.Write((uint)itemTemplate.BlockTypeFlag);
 421
 422             if (itemTemplate.IsProofOfStake)
 423             {
 424                 writer.Write(itemTemplate.hashProofOfStake);
 425             }
 426             else
 427             {
 428                 writer.Write(new uint256(0));
 429             }
 430             writer.Write(itemTemplate.nStakeModifier);
 431
 432             uint256 hashChecksum = CryptoUtils.ComputeHash256(ss.ToArray());
 433             writer.Close();
 434
 435             hashChecksum >>= (256 - 32);
 436
 437             return (uint)hashChecksum.Low64;
 438         }
 439
 440         public static bool CheckProofOfStake(CTransaction tx, uint nBits, out uint256 hashProofOfStake, out uint256 targetProofOfStake)
 441         {
 442             hashProofOfStake = targetProofOfStake = 0;
 443
 444             if (!tx.IsCoinStake)
 445             {
 446                 return false; // called on non-coinstake
 447             }
 448
 449             // Kernel (input 0) must match the stake hash target per coin age (nBits)
 450             CTxIn txin = tx.vin[0];
 451
 452             // Read block header
 453
 454             long nBlockPos;
 455             CBlock block;
 456             if (!CBlockStore.Instance.GetBlockByTransactionID(txin.prevout.hash, out block, out nBlockPos))
 457             {
 458                 return false; // unable to read block of previous transaction
 459             }
 460
 461             long nTxPos = 0;
 462             CTransaction txPrev = null;
 463
 464             // Iterate through vtx array
 465             for (var i = 0; i < block.vtx.Length; i++)
 466             {
 467                 if (block.vtx[i].Hash == txin.prevout.hash)
 468                 {
 469                     txPrev = block.vtx[i];
 470                     nTxPos = nBlockPos + block.GetTxOffset(i);
 471
 472                     break;
 473                 }
 474             }
 475
 476             if (txPrev == null)
 477             {
 478                 return false; // No such transaction found in the block
 479             }
 480
 481             if (!ScriptCode.VerifyScript(txin.scriptSig, txPrev.vout[txin.prevout.n].scriptPubKey, tx, 0, (int)scriptflag.SCRIPT_VERIFY_P2SH, 0))
 482             {
 483                 return false; // vin[0] signature check failed
 484             }
 485
 486             if (!CheckStakeKernelHash(nBits, block.header.Hash, block.header.nTime, (uint)(nTxPos - nBlockPos), txPrev, txin.prevout, tx.nTime, out hashProofOfStake, out targetProofOfStake))
 487             {
 488                 return false; // check kernel failed on coinstake
 489             }
 490
 491             return true;
 492         }
 493     }
 494 }