From 12f67828e449407a93bdb3202066003a48a8c276 Mon Sep 17 00:00:00 2001 From: CryptoManiac Date: Thu, 3 Sep 2015 01:38:02 +0300 Subject: [PATCH] StakeModifier class. Extremely experimental and not tested yet. --- Novacoin/CBlockStore.cs | 28 +++- Novacoin/StakeModifier.cs | 385 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 412 insertions(+), 1 deletions(-) create mode 100644 Novacoin/StakeModifier.cs diff --git a/Novacoin/CBlockStore.cs b/Novacoin/CBlockStore.cs index 95f65f3..f780a64 100644 --- a/Novacoin/CBlockStore.cs +++ b/Novacoin/CBlockStore.cs @@ -61,6 +61,11 @@ namespace Novacoin public uint nNonce { get; set; } /// + /// Next block hash. + /// + public byte[] nextHash { get; set; } + + /// /// Block type flags /// public BlockType BlockTypeFlag { get; set; } @@ -76,6 +81,11 @@ namespace Novacoin public byte nEntropyBit { get; set; } /// + /// Proof-of-Stake hash + /// + public byte[] hashProofOfStake { get; set; } + + /// /// Block height /// public uint nHeight { get; set; } @@ -216,6 +226,14 @@ namespace Novacoin } /// + /// Next block cursor + /// + public CBlockStoreItem next + { + get { return CBlockStore.Instance.GetCursor(nextHash); } + } + + /// /// STake modifier generation flag /// public bool GeneratedStakeModifier @@ -223,6 +241,11 @@ namespace Novacoin get { return (BlockTypeFlag & BlockType.BLOCK_STAKE_MODIFIER) != 0; } } + public uint StakeEntropyBit + { + get { return ((uint)(BlockTypeFlag & BlockType.BLOCK_STAKE_ENTROPY) >> 1); } + } + /// /// Sets stake modifier and flag. /// @@ -513,7 +536,10 @@ namespace Novacoin // TODO: compute stake modifier // Add to index - itemTemplate.BlockTypeFlag = block.IsProofOfStake ? BlockType.PROOF_OF_STAKE : BlockType.PROOF_OF_WORK; + if (block.IsProofOfStake) + { + itemTemplate.SetProofOfStake(); + } if (!itemTemplate.WriteToFile(ref writer, ref block)) { diff --git a/Novacoin/StakeModifier.cs b/Novacoin/StakeModifier.cs new file mode 100644 index 0000000..2448497 --- /dev/null +++ b/Novacoin/StakeModifier.cs @@ -0,0 +1,385 @@ +using System; +using System.Collections.Generic; +using System.Diagnostics.Contracts; +using System.IO; +using System.Linq; +using System.Numerics; +using System.Text; +using System.Threading.Tasks; + +namespace Novacoin +{ + public class StakeModifier + { + /// + /// 30 days as zero time weight + /// + public const uint nStakeMinAge = 60 * 60 * 24 * 30; + + /// + /// 90 days as full weight + /// + public const uint nStakeMaxAge = 60 * 60 * 24 * 90; + + /// + /// 10-minute stakes spacing + /// + public const uint nStakeTargetSpacing = 10 * 60; + + /// + /// Time to elapse before new modifier is computed + /// + public const uint nModifierInterval = 6 * 60 * 60; + + /// + /// Ratio of group interval length between the last group and the first group + /// + public const int nModifierIntervalRatio = 3; + + /// + /// Protocol switch time for fixed kernel modifier interval + /// + /// Mon, 20 Oct 2014 00:00:00 GMT + /// + internal const uint nModifierSwitchTime = 1413763200; + + /// + /// Whether the given block is subject to new modifier protocol + /// + /// Block timestamp + /// Result + internal static bool IsFixedModifierInterval(uint nTimeBlock) + { + return (nTimeBlock >= nModifierSwitchTime); + } + + /// + /// Get the last stake modifier and its generation time from a given block + /// + /// Block cursor + /// Stake modifier (ref) + /// Stake modifier generation time (ref) + /// + internal static bool GetLastStakeModifier(CBlockStoreItem cursor, ref long nStakeModifier, ref uint nModifierTime) + { + if (cursor == null) + { + return false; + } + + while (cursor != null && cursor.prev != null && !cursor.GeneratedStakeModifier) + { + cursor = cursor.prev; + } + + if (!cursor.GeneratedStakeModifier) + { + return false; // no generation at genesis block + } + + nStakeModifier = cursor.nStakeModifier; + nModifierTime = cursor.nTime; + + return true; + } + + /// + /// Get selection interval section (in seconds) + /// + /// + /// + internal static long GetStakeModifierSelectionIntervalSection(int nSection) + { + Contract.Assert(nSection >= 0 && nSection < 64); + return (nModifierInterval * 63 / (63 + ((63 - nSection) * (nModifierIntervalRatio - 1)))); + } + + /// + /// Get stake modifier selection interval (in seconds) + /// + /// + static long GetStakeModifierSelectionInterval() + { + long nSelectionInterval = 0; + for (int nSection = 0; nSection < 64; nSection++) + nSelectionInterval += GetStakeModifierSelectionIntervalSection(nSection); + return nSelectionInterval; + } + + + /// + /// Select a block from the candidate blocks in vSortedByTimestamp, excluding + /// already selected blocks in vSelectedBlocks, and with timestamp + /// up to nSelectionIntervalStop. + /// + /// + /// + /// Upper boundary for timestamp value. + /// Previous value of stake modifier. + /// Selection result. + /// + static bool SelectBlockFromCandidates(List> sortedByTimestamp, Dictionary mapSelectedBlocks, long nSelectionIntervalStop, long nStakeModifierPrev, ref CBlockStoreItem selectedCursor) + { + bool fSelected = false; + uint256 hashBest = 0; + selectedCursor = null; + foreach (var item in sortedByTimestamp) + { + CBlockStoreItem cursor = CBlockStore.Instance.GetCursor(item.Item2); + + if (cursor == null) + { + return false; // Failed to find block index for candidate block + } + + if (fSelected && cursor.nTime > nSelectionIntervalStop) + { + break; + } + + uint256 selectedBlockHash = cursor.Hash; + + if (mapSelectedBlocks.Count(pair => pair.Key == selectedBlockHash) > 0) + { + continue; + } + + // compute the selection hash by hashing its proof-hash and the + // previous proof-of-stake modifier + + uint256 hashProof = cursor.IsProofOfStake ? (uint256)cursor.hashProofOfStake : selectedBlockHash; + uint256 hashSelection; + + var s = new MemoryStream(); + var writer = new BinaryWriter(s); + + writer.Write(hashProof); + writer.Write(nStakeModifierPrev); + hashSelection = CryptoUtils.ComputeHash256(s.ToArray()); + writer.Close(); + + // the selection hash is divided by 2**32 so that proof-of-stake block + // is always favored over proof-of-work block. this is to preserve + // the energy efficiency property + if (cursor.IsProofOfStake) + hashSelection >>= 32; + if (fSelected && hashSelection < hashBest) + { + hashBest = hashSelection; + selectedCursor = cursor; + } + else if (!fSelected) + { + fSelected = true; + hashBest = hashSelection; + selectedCursor = cursor; + } + } + + return fSelected; + } + + /// + /// Stake Modifier (hash modifier of proof-of-stake): + /// The purpose of stake modifier is to prevent a txout (coin) owner from + /// computing future proof-of-stake generated by this txout at the time + /// of transaction confirmation. To meet kernel protocol, the txout + /// must hash with a future stake modifier to generate the proof. + /// Stake modifier consists of bits each of which is contributed from a + /// selected block of a given block group in the past. + /// The selection of a block is based on a hash of the block's proof-hash and + /// the previous stake modifier. + /// Stake modifier is recomputed at a fixed time interval instead of every + /// block. This is to make it difficult for an attacker to gain control of + /// additional bits in the stake modifier, even after generating a chain of + /// blocks. + /// + bool ComputeNextStakeModifier(CBlockStoreItem cursorCurrent, ref long nStakeModifier, ref bool fGeneratedStakeModifier) + { + nStakeModifier = 0; + fGeneratedStakeModifier = false; + CBlockStoreItem cursorPrev = cursorCurrent.prev; + if (cursorPrev == null) + { + fGeneratedStakeModifier = true; + return true; // genesis block's modifier is 0 + } + + // First find current stake modifier and its generation block time + // if it's not old enough, return the same stake modifier + uint nModifierTime = 0; + if (!GetLastStakeModifier(cursorPrev, ref nStakeModifier, ref nModifierTime)) + return false; // Unable to get last modifier + if (nModifierTime / nModifierInterval >= cursorPrev.nTime / nModifierInterval) + { + // no new interval keep current modifier + return true; + } + if (nModifierTime / nModifierInterval >= cursorCurrent.nTime / nModifierInterval) + { + // fixed interval protocol requires current block timestamp also be in a different modifier interval + if (IsFixedModifierInterval(cursorCurrent.nTime)) + { + // no new interval keep current modifier + return true; + } + else + { + // old modifier not meeting fixed modifier interval + } + } + + // Sort candidate blocks by timestamp + List> vSortedByTimestamp = new List>(); + // vSortedByTimestamp.reserve(64 * nModifierInterval / nStakeTargetSpacing); + + long nSelectionInterval = GetStakeModifierSelectionInterval(); + long nSelectionIntervalStart = (cursorPrev.nTime / nModifierInterval) * nModifierInterval - nSelectionInterval; + + CBlockStoreItem cursor = cursorPrev; + while (cursor != null && cursor.nTime >= nSelectionIntervalStart) + { + vSortedByTimestamp.Add(new Tuple(cursor.nTime, cursor.Hash)); + cursor = cursor.prev; + } + uint nHeightFirstCandidate = cursor != null ? (cursor.nHeight + 1) : 0; + vSortedByTimestamp.Reverse(); + vSortedByTimestamp.Sort((x, y) => x.Item1.CompareTo(y.Item1)); + + // Select 64 blocks from candidate blocks to generate stake modifier + long nStakeModifierNew = 0; + long nSelectionIntervalStop = nSelectionIntervalStart; + Dictionary mapSelectedBlocks = new Dictionary(); + for (int nRound = 0; nRound < Math.Min(64, (int)vSortedByTimestamp.Count); nRound++) + { + // add an interval section to the current selection round + nSelectionIntervalStop += GetStakeModifierSelectionIntervalSection(nRound); + // select a block from the candidates of current round + if (!SelectBlockFromCandidates(vSortedByTimestamp, mapSelectedBlocks, nSelectionIntervalStop, nStakeModifier, ref cursor)) + { + return false; // unable to select block + } + + // write the entropy bit of the selected block + nStakeModifierNew |= ((cursor.StakeEntropyBit) << nRound); + + // add the selected block from candidates to selected list + mapSelectedBlocks.Add(cursor.Hash, cursor); + } + + nStakeModifier = nStakeModifierNew; + fGeneratedStakeModifier = true; + return true; + } + + /// + /// The stake modifier used to hash for a stake kernel is chosen as the stake + /// modifier about a selection interval later than the coin generating the kernel + /// + static bool GetKernelStakeModifier(uint256 hashBlockFrom, ref long nStakeModifier, ref uint nStakeModifierHeight, ref uint nStakeModifierTime) + { + nStakeModifier = 0; + var cursorFrom = CBlockStore.Instance.GetCursor(hashBlockFrom); + if (cursorFrom == null) + { + return false; // Block not indexed + } + + nStakeModifierHeight = cursorFrom.nHeight; + nStakeModifierTime = cursorFrom.nTime; + + long nStakeModifierSelectionInterval = GetStakeModifierSelectionInterval(); + CBlockStoreItem cursor = cursorFrom; + + // loop to find the stake modifier later by a selection interval + while (nStakeModifierTime < cursorFrom.nTime + nStakeModifierSelectionInterval) + { + if (cursor.next == null) + { + // reached best block; may happen if node is behind on block chain + return false; + } + cursor = cursor.next; + if (cursor.GeneratedStakeModifier) + { + nStakeModifierHeight = cursor.nHeight; + nStakeModifierTime = cursor.nTime; + } + } + nStakeModifier = cursor.nStakeModifier; + + return true; + } + + bool GetKernelStakeModifier(uint256 hashBlockFrom, ref long nStakeModifier) + { + uint nStakeModifierHeight = 0; + uint nStakeModifierTime = 0; + + return GetKernelStakeModifier(hashBlockFrom, ref nStakeModifier, ref nStakeModifierHeight, ref nStakeModifierTime); + } + + bool CheckStakeKernelHash(uint nBits, CBlock blockFrom, uint nTxPrevOffset, CTransaction txPrev, COutPoint prevout, uint nTimeTx, ref uint256 hashProofOfStake, ref uint256 targetProofOfStake) + { + if (nTimeTx < txPrev.nTime) + { + return false; // Transaction timestamp violation + } + + uint nTimeBlockFrom = blockFrom.header.nTime; + if (nTimeBlockFrom + nStakeMinAge > nTimeTx) // Min age requirement + { + return false; // Min age violation + } + + uint256 nTargetPerCoinDay = new uint256(); + nTargetPerCoinDay.Compact = nBits; + + ulong nValueIn = txPrev.vout[prevout.n].nValue; + uint256 hashBlockFrom = blockFrom.header.Hash; + BigInteger bnCoinDayWeight = (long)nValueIn * GetWeight(txPrev.nTime, nTimeTx) / (long)CTransaction.nCoin / (24 * 60 * 60); + + targetProofOfStake = (bnCoinDayWeight * new BigInteger(nTargetPerCoinDay)).ToByteArray(); + + // Calculate hash + long nStakeModifier = 0; + uint nStakeModifierHeight = 0; + uint nStakeModifierTime = 0; + if (!GetKernelStakeModifier(hashBlockFrom, ref nStakeModifier, ref nStakeModifierHeight, ref nStakeModifierTime)) + { + return false; + } + + MemoryStream s = new MemoryStream(); + BinaryWriter w = new BinaryWriter(s); + + w.Write(nStakeModifier); + w.Write(nTimeBlockFrom); + w.Write(nTxPrevOffset); + w.Write(txPrev.nTime); + w.Write(prevout.n); + w.Write(nTimeTx); + + hashProofOfStake = CryptoUtils.ComputeHash256(s.ToArray()); + w.Close(); + + // Now check if proof-of-stake hash meets target protocol + if (hashProofOfStake > targetProofOfStake) + return false; + + return true; + } + + // Get time weight using supplied timestamps + static long GetWeight(long nIntervalBeginning, long nIntervalEnd) + { + // Kernel hash weight starts from 0 at the 30-day min age + // this change increases active coins participating the hash and helps + // to secure the network when proof-of-stake difficulty is low + // + // Maximum TimeWeight is 90 days. + + return Math.Min(nIntervalEnd - nIntervalBeginning - nStakeMinAge, nStakeMaxAge); + } + } +} -- 1.7.1