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 static 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 public 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 private 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 private 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 private 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 private 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 private 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 stream = new MemoryStream();
173 var bw = new BinaryWriter(stream);
176 bw.Write(nStakeModifierPrev);
177 hashSelection = CryptoUtils.ComputeHash256(stream.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(ref 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 private static bool GetKernelStakeModifier(ref 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 private static bool GetKernelStakeModifier(ref uint256 hashBlockFrom, out long nStakeModifier)
338 uint nStakeModifierHeight = 0;
339 uint nStakeModifierTime = 0;
341 return GetKernelStakeModifier(ref 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 if (!GetKernelStakeModifier(ref hashBlockFrom, out nStakeModifier))
373 var stream = new MemoryStream();
374 var bw = new BinaryWriter(stream);
376 // Coinstake kernel (input 0) must meet the formula
378 // hash(nStakeModifier + txPrev.block.nTime + txPrev.offset + txPrev.nTime + txPrev.vout.n + nTime) < bnTarget * nCoinDayWeight
380 // This ensures that the chance of getting a coinstake is proportional to the
381 // amount of coin age one owns.
383 // Note that "+" is not arithmetic operation here, this means concatenation of byte arrays.
385 // Check https://github.com/novacoin-project/novacoin/wiki/Kernel for additional information.
387 bw.Write(nStakeModifier);
388 bw.Write(nTimeBlockFrom);
389 bw.Write(nTxPrevOffset);
390 bw.Write(txPrev.nTime);
394 hashProofOfStake = CryptoUtils.ComputeHash256(stream.ToArray());
397 // Now check if proof-of-stake hash meets target protocol
398 return targetProofOfStake >= hashProofOfStake;
401 // Get time weight using supplied timestamps
402 static ulong GetWeight(ulong nIntervalBeginning, ulong nIntervalEnd)
404 // Kernel hash weight starts from 0 at the 30-day min age
405 // this change increases active coins participating the hash and helps
406 // to secure the network when proof-of-stake difficulty is low
408 // Maximum TimeWeight is 90 days.
410 return Math.Min(nIntervalEnd - nIntervalBeginning - nStakeMinAge, nStakeMaxAge);
414 /// Calculate stake modifier checksum.
416 /// <param name="cursorBlock">Block cursor.</param>
417 /// <returns>Checksum value.</returns>
418 public static uint GetModifierChecksum(CBlockStoreItem cursorBlock)
420 Contract.Assert(cursorBlock.prev != null || (uint256)cursorBlock.Hash == NetInfo.nHashGenesisBlock);
422 var stream = new MemoryStream();
423 var bw = new BinaryWriter(stream);
425 // Kernel hash for proof-of-stake or zero bytes array for proof-of-work
426 byte[] proofBytes = cursorBlock.IsProofOfStake ? cursorBlock.hashProofOfStake : new byte[32];
428 // Hash previous checksum with flags, hashProofOfStake and nStakeModifier
429 if (cursorBlock.prev != null)
431 bw.Write(cursorBlock.prev.nStakeModifierChecksum);
434 bw.Write((uint)cursorBlock.BlockTypeFlag);
435 bw.Write(proofBytes);
436 bw.Write(cursorBlock.nStakeModifier);
438 uint256 hashChecksum = CryptoUtils.ComputeHash256(stream.ToArray());
441 hashChecksum >>= (256 - 32);
443 return hashChecksum.Low32;
446 public static bool CheckProofOfStake(CTransaction tx, uint nBits, out uint256 hashProofOfStake, out uint256 targetProofOfStake)
448 hashProofOfStake = targetProofOfStake = 0;
452 return false; // called on non-coinstake
455 // Kernel (input 0) must match the stake hash target per coin age (nBits)
456 CTxIn txin = tx.vin[0];
462 if (!CBlockStore.Instance.GetBlockByTransactionID(txin.prevout.hash, out block, out nBlockPos))
464 return false; // unable to read block of previous transaction
468 CTransaction txPrev = null;
470 // Iterate through vtx array
471 var nTxPrevIndex = Array.FindIndex(block.vtx, txItem => txItem.Hash == txin.prevout.hash);
473 if (nTxPrevIndex == -1)
475 return false; // No such transaction found in the block
478 txPrev = block.vtx[nTxPrevIndex];
479 nTxPos = nBlockPos + block.GetTxOffset(nTxPrevIndex);
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