Novacoin/CBlock.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 using System;
  20 using System.Text;
  21 using System.Collections.Generic;
  22 using System.Diagnostics.Contracts;
  23 using System.IO;
  24 using System.Numerics;
  25
  26 namespace Novacoin
  27 {
  28     [Serializable]
  29     public class BlockException : Exception
  30     {
  31         public BlockException()
  32         {
  33         }
  34
  35         public BlockException(string message)
  36                 : base(message)
  37         {
  38         }
  39
  40         public BlockException(string message, Exception inner)
  41                 : base(message, inner)
  42         {
  43         }
  44     }
  45
  46     /// <summary>
  47     /// Represents the block. Block consists of header, transaction array and header signature.
  48     /// </summary>
  49     public class CBlock
  50         {
  51         /// <summary>
  52         /// Maximum block size is 1Mb.
  53         /// </summary>
  54         public const uint nMaxBlockSize = 1000000;
  55
  56         /// <summary>
  57         /// Sanity threshold for amount of sigops.
  58         /// </summary>
  59         public const uint nMaxSigOps = 20000;
  60
  61                 /// <summary>
  62                 /// Block header.
  63                 /// </summary>
  64                 public CBlockHeader header;
  65
  66                 /// <summary>
  67                 /// Transactions array.
  68                 /// </summary>
  69                 public CTransaction[] vtx;
  70
  71         /// <summary>
  72         /// Block header signature.
  73         /// </summary>
  74         public byte[] signature = new byte[0];
  75
  76         /// <summary>
  77         /// Copy constructor.
  78         /// </summary>
  79         /// <param name="b">CBlock instance.</param>
  80         public CBlock(CBlock b)
  81         {
  82             header = new CBlockHeader(b.header);
  83             vtx = new CTransaction[b.vtx.Length];
  84
  85             for (int i = 0; i < b.vtx.Length; i++)
  86             {
  87                 vtx[i] = new CTransaction(b.vtx[i]);
  88             }
  89
  90             signature = new byte[b.signature.Length];
  91             b.signature.CopyTo(signature, 0);
  92         }
  93
  94         /// <summary>
  95         /// Parse byte sequence and initialize new block instance
  96         /// </summary>
  97         /// <param name="blockBytes">Bytes sequence.</param>
  98                 public CBlock (byte[] blockBytes)
  99                 {
 100             try
 101             {
 102                 var stream = new MemoryStream(blockBytes);
 103                 var reader = new BinaryReader(stream);
 104
 105                 // Fill the block header fields
 106                 header = new CBlockHeader(ref reader);
 107
 108                 // Parse transactions list
 109                 vtx = CTransaction.ReadTransactionsList(ref reader);
 110
 111                 // Read block signature
 112                 signature = reader.ReadBytes((int)VarInt.ReadVarInt(ref reader));
 113
 114                 reader.Close();
 115             }
 116             catch (Exception e)
 117             {
 118                 throw new BlockException("Deserialization failed", e);
 119             }
 120                 }
 121
 122         public CBlock()
 123         {
 124             // Initialize empty array of transactions. Please note that such
 125             // configuration is not valid real block since it has to provide
 126             // at least one transaction.
 127             vtx = new CTransaction[0];
 128         }
 129
 130         public bool CheckBlock(bool fCheckPOW = true, bool fCheckMerkleRoot = true, bool fCheckSig = true)
 131         {
 132             var uniqueTX = new List<uint256>(); // tx hashes
 133             uint nSigOps = 0; // total sigops
 134
 135             // Basic sanity checkings
 136             if (vtx.Length == 0 || Size > nMaxBlockSize)
 137             {
 138                 return false;
 139             }
 140
 141             bool fProofOfStake = IsProofOfStake;
 142
 143             // First transaction must be coinbase, the rest must not be
 144             if (!vtx[0].IsCoinBase)
 145             {
 146                 return false;
 147             }
 148
 149             if (!vtx[0].CheckTransaction())
 150             {
 151                 return false;
 152             }
 153
 154             uniqueTX.Add(vtx[0].Hash);
 155             nSigOps += vtx[0].LegacySigOpCount;
 156
 157             if (fProofOfStake)
 158             {
 159                 // Proof-of-STake related checkings. Note that we know here that 1st transactions is coinstake. We don't need
 160                 //   check the type of 1st transaction because it's performed earlier by IsProofOfStake()
 161
 162                 // nNonce must be zero for proof-of-stake blocks
 163                 if (header.nNonce != 0)
 164                 {
 165                     return false;
 166                 }
 167
 168                 // Coinbase output should be empty if proof-of-stake block
 169                 if (vtx[0].vout.Length != 1 || !vtx[0].vout[0].IsEmpty)
 170                 {
 171                     return false;
 172                 }
 173
 174                 // Check coinstake timestamp
 175                 if (header.nTime != vtx[1].nTime)
 176                 {
 177                     return false;
 178                 }
 179
 180                 // Check proof-of-stake block signature
 181                 if (fCheckSig && !SignatureOK)
 182                 {
 183                     return false;
 184                 }
 185
 186                 if (!vtx[1].CheckTransaction())
 187                 {
 188                     return false;
 189                 }
 190
 191                 uniqueTX.Add(vtx[1].Hash);
 192                 nSigOps += vtx[1].LegacySigOpCount;
 193             }
 194             else
 195             {
 196                 // Check proof of work matches claimed amount
 197                 if (fCheckPOW && !CheckProofOfWork(header.Hash, header.nBits))
 198                 {
 199                     return false;
 200                 }
 201
 202                 // Check timestamp
 203                 if (header.nTime > NetInfo.FutureDrift(NetInfo.GetAdjustedTime()))
 204                 {
 205                     return false;
 206                 }
 207
 208                 // Check coinbase timestamp
 209                 if (header.nTime < NetInfo.PastDrift(vtx[0].nTime))
 210                 {
 211                     return false;
 212                 }
 213             }
 214
 215             // Iterate all transactions starting from second for proof-of-stake block
 216             //    or first for proof-of-work block
 217             for (int i = fProofOfStake ? 2 : 1; i < vtx.Length; i++)
 218             {
 219                 var tx = vtx[i];
 220
 221                 // Reject coinbase transactions at non-zero index
 222                 if (tx.IsCoinBase)
 223                 {
 224                     return false;
 225                 }
 226
 227                 // Reject coinstake transactions at index != 1
 228                 if (tx.IsCoinStake)
 229                 {
 230                     return false;
 231                 }
 232
 233                 // Check transaction timestamp
 234                 if (header.nTime < tx.nTime)
 235                 {
 236                     return false;
 237                 }
 238
 239                 // Check transaction consistency
 240                 if (!tx.CheckTransaction())
 241                 {
 242                     return false;
 243                 }
 244
 245                 // Add transaction hash into list of unique transaction IDs
 246                 uniqueTX.Add(tx.Hash);
 247
 248                 // Calculate sigops count
 249                 nSigOps += tx.LegacySigOpCount;
 250             }
 251
 252             // Check for duplicate txids.
 253             if (uniqueTX.Count != vtx.Length)
 254             {
 255                 return false;
 256             }
 257
 258             // Reject block if validation would consume too much resources.
 259             if (nSigOps > nMaxSigOps)
 260             {
 261                 return false;
 262             }
 263
 264             // Check merkle root
 265             if (fCheckMerkleRoot && hashMerkleRoot != header.merkleRoot)
 266             {
 267                 return false;
 268             }
 269
 270             return true;
 271         }
 272
 273         private bool CheckProofOfWork(uint256 hash, uint nBits)
 274         {
 275             uint256 nTarget = new uint256();
 276             nTarget.Compact = nBits;
 277
 278             // Check range
 279             if (nTarget > NetInfo.nProofOfWorkLimit)
 280             {
 281                 // nBits below minimum work
 282                 return false;
 283             }
 284
 285             // Check proof of work matches claimed amount
 286             if (hash > nTarget)
 287             {
 288                 //  hash doesn't match nBits
 289                 return false;
 290             }
 291
 292             return true;
 293         }
 294
 295         /// <summary>
 296         /// Is this a Proof-of-Stake block?
 297         /// </summary>
 298         public bool IsProofOfStake
 299         {
 300             get
 301             {
 302                 return (vtx.Length > 1 && vtx[1].IsCoinStake);
 303             }
 304         }
 305
 306         /// <summary>
 307         /// Was this signed correctly?
 308         /// </summary>
 309         public bool SignatureOK
 310         {
 311             get
 312             {
 313                 if (IsProofOfStake)
 314                 {
 315                     if (signature.Length == 0)
 316                     {
 317                         return false; // No signature
 318                     }
 319
 320                     txnouttype whichType;
 321                     IList<byte[]> solutions;
 322
 323                     if (!ScriptCode.Solver(vtx[1].vout[1].scriptPubKey, out whichType, out solutions))
 324                     {
 325                         return false; // No solutions found
 326                     }
 327
 328                     if (whichType == txnouttype.TX_PUBKEY)
 329                     {
 330                         CPubKey pubkey;
 331
 332                         try
 333                         {
 334                             pubkey = new CPubKey(solutions[0]);
 335                         }
 336                         catch (Exception)
 337                         {
 338                             return false; // Error while loading public key
 339                         }
 340
 341                         return pubkey.VerifySignature(header.Hash, signature);
 342                     }
 343                 }
 344                 else
 345                 {
 346                     // Proof-of-Work blocks have no signature
 347
 348                     return true;
 349                 }
 350
 351                 return false;
 352             }
 353         }
 354
 355         /// <summary>
 356         /// Get instance as sequence of bytes
 357         /// </summary>
 358         /// <returns>Byte sequence</returns>
 359         public static implicit operator byte[] (CBlock b)
 360         {
 361             var stream = new MemoryStream();
 362             var writer = new BinaryWriter(stream);
 363
 364             writer.Write(b.header);
 365             writer.Write(VarInt.EncodeVarInt(b.vtx.LongLength));
 366
 367             foreach (var tx in b.vtx)
 368             {
 369                 writer.Write(tx);
 370             }
 371
 372             writer.Write(VarInt.EncodeVarInt(b.signature.LongLength));
 373             writer.Write(b.signature);
 374
 375             var resultBytes = stream.ToArray();
 376
 377             writer.Close();
 378
 379             return resultBytes;
 380         }
 381
 382         /// <summary>
 383         /// Serialized size
 384         /// </summary>
 385         public int Size
 386         {
 387             get
 388             {
 389                 int nSize = 80 + VarInt.GetEncodedSize(vtx.Length); // CBlockHeader + NumTx
 390
 391                 foreach (var tx in vtx)
 392                 {
 393                     nSize += tx.Size;
 394                 }
 395
 396                 nSize += VarInt.GetEncodedSize(signature.Length) + signature.Length;
 397
 398                 return nSize;
 399             }
 400         }
 401
 402         /// <summary>
 403         /// Get transaction offset inside block.
 404         /// </summary>
 405         /// <param name="nTx">Transaction index.</param>
 406         /// <returns>Offset in bytes from the beginning of block header.</returns>
 407         public int GetTxOffset(int nTx)
 408         {
 409             Contract.Requires<ArgumentException>(nTx >= 0 && nTx < vtx.Length, "Transaction index you've specified is incorrect.");
 410
 411             int nOffset = 80 + VarInt.GetEncodedSize(vtx.Length); // CBlockHeader + NumTx
 412
 413             for (int i = 0; i < nTx; i++)
 414             {
 415                 nOffset += vtx[i].Size;
 416             }
 417
 418             return nOffset;
 419         }
 420
 421         /// <summary>
 422         /// Merkle root
 423         /// </summary>
 424         public uint256 hashMerkleRoot
 425         {
 426             get {
 427
 428                 var merkleTree = new List<byte>();
 429
 430                 foreach (var tx in vtx)
 431                 {
 432                     merkleTree.AddRange(CryptoUtils.ComputeHash256(tx));
 433                 }
 434
 435                 int levelOffset = 0;
 436                 for (int nLevelSize = vtx.Length; nLevelSize > 1; nLevelSize = (nLevelSize + 1) / 2)
 437                 {
 438                     for (int nLeft = 0; nLeft < nLevelSize; nLeft += 2)
 439                     {
 440                         int nRight = Math.Min(nLeft + 1, nLevelSize - 1);
 441
 442                         var left = merkleTree.GetRange((levelOffset + nLeft) * 32, 32).ToArray();
 443                         var right = merkleTree.GetRange((levelOffset + nRight) * 32, 32).ToArray();
 444
 445                         merkleTree.AddRange(CryptoUtils.ComputeHash256(ref left, ref right));
 446                     }
 447                     levelOffset += nLevelSize;
 448                 }
 449
 450                 return (merkleTree.Count == 0) ? 0 : (uint256)merkleTree.GetRange(merkleTree.Count-32, 32).ToArray();
 451             }
 452         }
 453
 454         public override string ToString()
 455         {
 456             var sb = new StringBuilder();
 457
 458             sb.AppendFormat("CBlock(\n header={0},\n", header.ToString());
 459
 460             foreach(var tx in vtx)
 461             {
 462                 sb.AppendFormat("{0}", tx.ToString());
 463             }
 464
 465             if (IsProofOfStake)
 466             {
 467                 sb.AppendFormat(", signature={0}, signatureOK={1}\n", Interop.ToHex(signature), SignatureOK);
 468             }
 469
 470             sb.Append(")");
 471
 472             return sb.ToString();
 473         }
 474
 475         /// <summary>
 476         /// Calculate proof-of-work reward.
 477         /// </summary>
 478         /// <param name="nBits">Packed difficulty representation.</param>
 479         /// <param name="nFees">Amount of fees.</param>
 480         /// <returns>Reward value.</returns>
 481         public static ulong GetProofOfWorkReward(uint nBits, ulong nFees)
 482         {
 483             // NovaCoin: subsidy is cut in half every 64x multiply of PoW difficulty
 484             // A reasonably continuous curve is used to avoid shock to market
 485             // (nSubsidyLimit / nSubsidy) ** 6 == bnProofOfWorkLimit / bnTarget
 486             //
 487             // Human readable form:
 488             //
 489             // nSubsidy = 100 / (diff ^ 1/6)
 490             //
 491             // Please note that we're using bisection to find an approximate solutuion
 492
 493             BigInteger bnSubsidyLimit = NetInfo.nMaxMintProofOfWork;
 494
 495             uint256 nTarget = 0;
 496             nTarget.Compact = nBits;
 497
 498             BigInteger bnTarget = new BigInteger(nTarget);
 499             BigInteger bnTargetLimit = new BigInteger(NetInfo.nProofOfWorkLimit);
 500
 501             BigInteger bnLowerBound = CTransaction.nCent;
 502             BigInteger bnUpperBound = bnSubsidyLimit;
 503
 504             while (bnLowerBound + CTransaction.nCent <= bnUpperBound)
 505             {
 506                 BigInteger bnMidValue = (bnLowerBound + bnUpperBound) / 2;
 507                 if (bnMidValue * bnMidValue * bnMidValue * bnMidValue * bnMidValue * bnMidValue * bnTargetLimit > bnSubsidyLimit * bnSubsidyLimit * bnSubsidyLimit * bnSubsidyLimit * bnSubsidyLimit * bnSubsidyLimit * bnTarget)
 508                     bnUpperBound = bnMidValue;
 509                 else
 510                     bnLowerBound = bnMidValue;
 511             }
 512
 513             ulong nSubsidy = (ulong)bnUpperBound;
 514             nSubsidy = (nSubsidy / CTransaction.nCent) * CTransaction.nCent;
 515
 516
 517             return Math.Min(nSubsidy, NetInfo.nMaxMintProofOfWork) + nFees;
 518         }
 519
 520         internal static ulong GetProofOfStakeReward(ulong nCoinAge, uint nBits, uint nTime)
 521         {
 522             throw new NotImplementedException();
 523         }
 524     }
 525 }
 526