2 * Novacoin classes library
3 * Copyright (C) 2015 Alex D. (balthazar.ad@gmail.com)
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.
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.
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/>.
21 using System.Collections.Generic;
22 using System.Diagnostics.Contracts;
29 /// Stake modifier calculation. Doesn't work properly, for now.
31 public class StakeModifier
34 /// 30 days as zero time weight
36 public const uint nStakeMinAge = 60 * 60 * 24 * 30;
39 /// 90 days as full weight
41 public const uint nStakeMaxAge = 60 * 60 * 24 * 90;
44 /// 10-minute stakes spacing
46 public const uint nStakeTargetSpacing = 10 * 60;
49 /// Time to elapse before new modifier is computed
51 public const uint nModifierInterval = 6 * 60 * 60;
54 /// Ratio of group interval length between the last group and the first group
56 public const int nModifierIntervalRatio = 3;
59 /// Protocol switch time for fixed kernel modifier interval
61 /// Mon, 20 Oct 2014 00:00:00 GMT
63 internal const uint nModifierSwitchTime = 1413763200;
66 /// Whether the given block is subject to new modifier protocol
68 /// <param name="nTimeBlock">Block timestamp</param>
69 /// <returns>Result</returns>
70 internal static bool IsFixedModifierInterval(uint nTimeBlock)
72 return (nTimeBlock >= nModifierSwitchTime);
76 /// Get the last stake modifier and its generation time from a given block
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)
89 while (cursor != null && cursor.prev != null && !cursor.GeneratedStakeModifier)
94 if (!cursor.GeneratedStakeModifier)
96 return false; // no generation at genesis block
99 nStakeModifier = cursor.nStakeModifier;
100 nModifierTime = cursor.nTime;
106 /// Get selection interval section (in seconds)
108 /// <param name="nSection"></param>
109 /// <returns></returns>
110 internal static long GetStakeModifierSelectionIntervalSection(int nSection)
112 Contract.Assert(nSection >= 0 && nSection < 64);
113 return (nModifierInterval * 63 / (63 + ((63 - nSection) * (nModifierIntervalRatio - 1))));
117 /// Get stake modifier selection interval (in seconds)
119 /// <returns></returns>
120 internal static long GetStakeModifierSelectionInterval()
122 long nSelectionInterval = 0;
123 for (int nSection = 0; nSection < 64; nSection++)
124 nSelectionInterval += GetStakeModifierSelectionIntervalSection(nSection);
125 return nSelectionInterval;
130 /// Select a block from the candidate blocks in vSortedByTimestamp, excluding
131 /// already selected blocks in vSelectedBlocks, and with timestamp
132 /// up to nSelectionIntervalStop.
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)
142 bool fSelected = false;
143 uint256 hashBest = 0;
144 selectedCursor = null;
145 foreach (var item in sortedByTimestamp)
147 CBlockStoreItem cursor = CBlockStore.Instance.GetMapCursor(item.Item2);
151 return false; // Failed to find block index for candidate block
154 if (fSelected && cursor.nTime > nSelectionIntervalStop)
159 uint256 selectedBlockHash = cursor.Hash;
161 if (mapSelectedBlocks.Count(pair => pair.Key == selectedBlockHash) > 0)
166 // compute the selection hash by hashing its proof-hash and the
167 // previous proof-of-stake modifier
169 var hashProof = cursor.IsProofOfStake ? (uint256)cursor.hashProofOfStake : selectedBlockHash;
170 uint256 hashSelection;
172 var s = new MemoryStream();
173 var writer = new BinaryWriter(s);
175 writer.Write(hashProof);
176 writer.Write(nStakeModifierPrev);
177 hashSelection = CryptoUtils.ComputeHash256(s.ToArray());
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)
187 hashBest = hashSelection;
188 selectedCursor = cursor;
193 hashBest = hashSelection;
194 selectedCursor = cursor;
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
216 public static bool ComputeNextStakeModifier(CBlockStoreItem cursorCurrent, ref long nStakeModifier, ref bool fGeneratedStakeModifier)
219 fGeneratedStakeModifier = false;
220 CBlockStoreItem cursorPrev = cursorCurrent.prev;
221 if (cursorPrev == null)
223 fGeneratedStakeModifier = true;
224 return true; // genesis block's modifier is 0
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)
234 // no new interval keep current modifier
237 if (nModifierTime / nModifierInterval >= cursorCurrent.nTime / nModifierInterval)
239 // fixed interval protocol requires current block timestamp also be in a different modifier interval
240 if (IsFixedModifierInterval(cursorCurrent.nTime))
242 // no new interval keep current modifier
247 // old modifier not meeting fixed modifier interval
251 // Sort candidate blocks by timestamp
252 List<Tuple<uint, uint256>> vSortedByTimestamp = new List<Tuple<uint, uint256>>();
253 // vSortedByTimestamp.reserve(64 * nModifierInterval / nStakeTargetSpacing);
255 long nSelectionInterval = GetStakeModifierSelectionInterval();
256 long nSelectionIntervalStart = (cursorPrev.nTime / nModifierInterval) * nModifierInterval - nSelectionInterval;
258 CBlockStoreItem cursor = cursorPrev;
259 while (cursor != null && cursor.nTime >= nSelectionIntervalStart)
261 vSortedByTimestamp.Add(new Tuple<uint, uint256>(cursor.nTime, cursor.Hash));
262 cursor = cursor.prev;
264 uint nHeightFirstCandidate = cursor != null ? (cursor.nHeight + 1) : 0;
265 vSortedByTimestamp.Reverse();
266 vSortedByTimestamp.Sort((x, y) => x.Item1.CompareTo(y.Item1));
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++)
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))
279 return false; // unable to select block
282 // write the entropy bit of the selected block
283 nStakeModifierNew |= (((long)cursor.StakeEntropyBit) << nRound);
285 // add the selected block from candidates to selected list
286 mapSelectedBlocks.Add(cursor.Hash, cursor);
289 nStakeModifier = nStakeModifierNew;
290 fGeneratedStakeModifier = true;
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
298 static bool GetKernelStakeModifier(uint256 hashBlockFrom, out long nStakeModifier, out uint nStakeModifierHeight, out uint nStakeModifierTime)
301 nStakeModifierTime = 0;
302 nStakeModifierHeight = 0;
304 var cursorFrom = CBlockStore.Instance.GetMapCursor(hashBlockFrom);
305 if (cursorFrom == null)
307 return false; // Block not indexed
310 nStakeModifierHeight = cursorFrom.nHeight;
311 nStakeModifierTime = cursorFrom.nTime;
313 long nStakeModifierSelectionInterval = GetStakeModifierSelectionInterval();
314 CBlockStoreItem cursor = cursorFrom;
316 // loop to find the stake modifier later by a selection interval
317 while (nStakeModifierTime < cursorFrom.nTime + nStakeModifierSelectionInterval)
319 if (cursor.next == null)
321 // reached best block; may happen if node is behind on block chain
324 cursor = cursor.next;
325 if (cursor.GeneratedStakeModifier)
327 nStakeModifierHeight = cursor.nHeight;
328 nStakeModifierTime = cursor.nTime;
331 nStakeModifier = cursor.nStakeModifier;
336 public static bool GetKernelStakeModifier(uint256 hashBlockFrom, out long nStakeModifier)
338 uint nStakeModifierHeight = 0;
339 uint nStakeModifierTime = 0;
341 return GetKernelStakeModifier(hashBlockFrom, out nStakeModifier, out nStakeModifierHeight, out nStakeModifierTime);
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)
346 hashProofOfStake = targetProofOfStake = 0;
348 if (nTimeTx < txPrev.nTime)
350 return false; // Transaction timestamp violation
353 if (nTimeBlockFrom + nStakeMinAge > nTimeTx) // Min age requirement
355 return false; // Min age violation
358 uint256 nTargetPerCoinDay = 0;
359 nTargetPerCoinDay.Compact = nBits;
361 long nValueIn = txPrev.vout[prevout.n].nValue;
362 uint256 nCoinDayWeight = new uint256((ulong)nValueIn) * GetWeight(txPrev.nTime, nTimeTx) / CTransaction.nCoin / (24 * 60 * 60);
364 targetProofOfStake = nCoinDayWeight * nTargetPerCoinDay;
368 uint nStakeModifierTime;
369 uint nStakeModifierHeight;
370 if (!GetKernelStakeModifier(hashBlockFrom, out nStakeModifier, out nStakeModifierHeight, out nStakeModifierTime))
375 MemoryStream s = new MemoryStream();
376 BinaryWriter w = new BinaryWriter(s);
378 w.Write(nStakeModifier);
379 w.Write(nTimeBlockFrom);
380 w.Write(nTxPrevOffset);
381 w.Write(txPrev.nTime);
385 hashProofOfStake = CryptoUtils.ComputeHash256(s.ToArray());
388 // Now check if proof-of-stake hash meets target protocol
389 if (hashProofOfStake > targetProofOfStake)
395 // Get time weight using supplied timestamps
396 static ulong GetWeight(ulong nIntervalBeginning, ulong nIntervalEnd)
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
402 // Maximum TimeWeight is 90 days.
404 return Math.Min(nIntervalEnd - nIntervalBeginning - nStakeMinAge, nStakeMaxAge);
407 internal static uint GetStakeModifierChecksum(ref CBlockStoreItem itemTemplate)
409 Contract.Assert(itemTemplate.prev != null || (uint256)itemTemplate.Hash == NetInfo.nHashGenesisBlock);
411 // Hash previous checksum with flags, hashProofOfStake and nStakeModifier
412 MemoryStream ss = new MemoryStream();
413 BinaryWriter writer = new BinaryWriter(ss);
415 if (itemTemplate.prev != null)
417 writer.Write(itemTemplate.prev.nStakeModifierChecksum);
420 writer.Write((uint)itemTemplate.BlockTypeFlag);
422 if (itemTemplate.IsProofOfStake)
424 writer.Write(itemTemplate.hashProofOfStake);
428 writer.Write(new uint256(0));
430 writer.Write(itemTemplate.nStakeModifier);
432 uint256 hashChecksum = CryptoUtils.ComputeHash256(ss.ToArray());
435 hashChecksum >>= (256 - 32);
437 return (uint)hashChecksum.Low64;
440 public static bool CheckProofOfStake(CTransaction tx, uint nBits, out uint256 hashProofOfStake, out uint256 targetProofOfStake)
442 hashProofOfStake = targetProofOfStake = 0;
446 return false; // called on non-coinstake
449 // Kernel (input 0) must match the stake hash target per coin age (nBits)
450 CTxIn txin = tx.vin[0];
456 if (!CBlockStore.Instance.GetBlockByTransactionID(txin.prevout.hash, out block, out nBlockPos))
458 return false; // unable to read block of previous transaction
462 CTransaction txPrev = null;
464 // Iterate through vtx array
465 for (var i = 0; i < block.vtx.Length; i++)
467 if (block.vtx[i].Hash == txin.prevout.hash)
469 txPrev = block.vtx[i];
470 nTxPos = nBlockPos + block.GetTxOffset(i);
478 return false; // No such transaction found in the block
481 if (!ScriptCode.VerifyScript(txin.scriptSig, txPrev.vout[txin.prevout.n].scriptPubKey, tx, 0, (int)scriptflag.SCRIPT_VERIFY_P2SH, 0))
483 return false; // vin[0] signature check failed
486 if (!CheckStakeKernelHash(nBits, block.header.Hash, block.header.nTime, (uint)(nTxPos - nBlockPos), txPrev, txin.prevout, tx.nTime, out hashProofOfStake, out targetProofOfStake))
488 return false; // check kernel failed on coinstake