validation.rb in bitcoin-ruby-0.0.6

- old
+ new

@@ -1,27 +1,19 @@
 # encoding: ascii-8bit
 
+# Validates blocks and transactions before they are accepted into the local blockchain.
+# There are two modes of validation, "syntax" and "context". "syntax" validates everything
+# that can be validated without access to the rest of the blockchain, for example that the
+# block hash matches the claimed difficulty, and the tx hashes add up to the given merkle
+# root, etc. The "context" rules include the checks that need to cross-reference data
+# against the local database, like comparing the difficulty target to the last blocks, or
+# checking for doublespends. (Suggestions for better names for these modes are welcome!)
+# Everything accepted into the local storage should at least be syntax-validated, but it
+# should be possible to skip context-validation when the current block is already known,
+# for example when checkpoints are used.
 module Bitcoin::Validation
-
-  # maximum size of a block (in bytes)
-  MAX_BLOCK_SIZE = 1_000_000
-
-  # maximum number of signature operations in a block
-  MAX_BLOCK_SIGOPS = MAX_BLOCK_SIZE / 50
-
-  # maximum integer value
-  INT_MAX = 0xffffffff
-
-  # number of confirmations required before coinbase tx can be spent
-  COINBASE_MATURITY = 100
-
-  # interval (in blocks) for difficulty retarget
-  RETARGET = 2016
-
-  # interval (in blocks) for mining reward reduction
-  REWARD_DROP = 210_000
-
+    
   class ValidationError < StandardError
   end
 
 
   class Block
@@ -36,10 +28,15 @@
     if Bitcoin.namecoin?
       RULES[:syntax] -= [:bits, :coinbase, :coinbase_scriptsig, :mrkl_root]
       RULES[:context] -= [:difficulty, :coinbase_value]
     end
 
+    if Bitcoin.litecoin?
+      RULES[:syntax] -= [:bits]
+      RULES[:syntax] += [:scrypt_bits]
+    end
+
     # validate block rules. +opts+ are:
     # rules:: which rulesets to validate (default: [:syntax, :context])
     # raise_errors:: whether to raise ValidationError on failure (default: false)
     def validate(opts = {})
       return true  if KNOWN_EXCEPTIONS.include?(block.hash)
@@ -80,10 +77,17 @@
       actual = block.hash.to_i(16)
       expected = Bitcoin.decode_compact_bits(block.bits).to_i(16)
       actual <= expected || [actual, expected]
     end
 
+    # check that block hash matches claimed bits using Scrypt hash
+    def scrypt_bits
+      actual = block.recalc_block_scrypt_hash.to_i(16)
+      expected = Bitcoin.decode_compact_bits(block.bits).to_i(16)
+      actual <= expected || [actual, expected]
+    end
+
     # check that block time is not greater than max
     def max_timestamp
       time, max = block.time, Time.now.to_i + 2*60*60
       time < max || [time, max]
     end
@@ -100,11 +104,11 @@
       size.between?(2,100) || [size, 2, 100]
     end
 
     # check that coinbase value is valid; no more than reward + fees
     def coinbase_value
-      reward = ((50.0 / (2 ** (store.get_depth / REWARD_DROP.to_f).floor)) * 1e8).to_i
+      reward = ((50.0 / (2 ** (store.get_depth / Bitcoin::REWARD_DROP.to_f).floor)) * 1e8).to_i
       fees = 0
       block.tx[1..-1].map.with_index do |t, idx|
         val = tx_validators[idx]
         fees += t.in.map.with_index {|i, idx|
           val.prev_txs[idx].out[i.prev_out_index].value rescue 0
@@ -125,11 +129,11 @@
       @prev_block && @prev_block.hash == block.prev_block.reverse_hth
     end
 
     # check that bits satisfy required difficulty
     def difficulty
-      return true  if Bitcoin.network_name == :testnet3
+      return true  if Bitcoin.network[:no_difficulty] == true
       block.bits == next_bits_required || [block.bits, next_bits_required]
     end
 
     # check that timestamp is newer than the median of the last 11 blocks
     def min_timestamp
@@ -144,22 +148,26 @@
       min_time = (rem == 0 ? times[mid-1, 2].inject(:+) / 2.0 : times[mid])
 
       block.time > min_time || [block.time, min_time]
     end
 
-    # check transactions
+    # Run all syntax checks on transactions
     def transactions_syntax
+      # check if there are no double spends within this block
+      return false if block.tx.map(&:in).flatten.map {|i| [i.prev_out, i.prev_out_index] }.uniq! != nil
+
       tx_validators.all?{|v|
         begin
           v.validate(rules: [:syntax], raise_errors: true)
         rescue ValidationError
           store.log.info { $!.message }
           return false
         end
       }
     end
 
+    # Run all context checks on transactions
     def transactions_context
       tx_validators.all?{|v|
         begin
           v.validate(rules: [:context], raise_errors: true)
         rescue ValidationError
@@ -167,25 +175,46 @@
           return false
         end
       }
     end
 
+    # Get validators for all tx objects in the current block
     def tx_validators
-      @tx_validators ||= block.tx[1..-1].map {|tx| tx.validator(store, block) }
+      @tx_validators ||= block.tx[1..-1].map {|tx| tx.validator(store, block, self)}
     end
 
+    # Fetch all prev_txs that will be needed for validation
+    # Used for optimization in tx validators
+    def prev_txs_hash
+      @prev_tx_hash ||= (
+        inputs = block.tx[1..-1].map {|tx| tx.in }.flatten
+        txs = store.get_txs(inputs.map{|i| i.prev_out.reverse_hth })
+        Hash[*txs.map {|tx| [tx.hash, tx] }.flatten]
+      )
+    end
+
+    # Fetch all prev_outs that already have a next_in, i.e. are already spent.
+    def spent_outs_txins
+      @spent_outs_txins ||= (
+        next_ins = store.get_txins_for_txouts(block.tx[1..-1].map(&:in).flatten.map.with_index {|txin, idx| [txin.prev_out.reverse_hth, txin.prev_out_index] })
+        # Only returns next_ins that are in blocks in the main chain
+        next_ins.select {|i| store.get_block_id_for_tx_id(i.tx_id) }
+      )
+    end
+
     def next_bits_required
-      index = (prev_block.depth + 1) / RETARGET
+      retarget = (Bitcoin.network[:retarget_interval] || Bitcoin::RETARGET_INTERVAL)
+      index = (prev_block.depth + 1) / retarget  
       max_target = Bitcoin.decode_compact_bits(Bitcoin.network[:proof_of_work_limit]).to_i(16)
       return Bitcoin.network[:proof_of_work_limit]  if index == 0
-      return prev_block.bits  if (prev_block.depth + 1) % RETARGET != 0
+      return prev_block.bits  if (prev_block.depth + 1) % retarget != 0
       last = store.db[:blk][hash: prev_block.hash.htb.blob]
       first = store.db[:blk][hash: last[:prev_hash].blob]
-      (RETARGET-2).times { first = store.db[:blk][hash: first[:prev_hash].blob] }
+      (retarget - 2).times { first = store.db[:blk][hash: first[:prev_hash].blob] }
 
       nActualTimespan = last[:time] - first[:time]
-      nTargetTimespan = RETARGET * 600
+      nTargetTimespan = retarget * 600
 
       nActualTimespan = [nActualTimespan, nTargetTimespan/4].max
       nActualTimespan = [nActualTimespan, nTargetTimespan*4].min
 
       target = Bitcoin.decode_compact_bits(last[:bits]).to_i(16)
@@ -200,15 +229,15 @@
     ]
 
   end
 
   class Tx
-    attr_accessor :tx, :store, :error
+    attr_accessor :tx, :store, :error, :block_validator
 
     RULES = {
       syntax: [:hash, :lists, :max_size, :output_values, :inputs, :lock_time, :standard],
-      context: [:prev_out, :signatures, :spent, :input_values, :output_sum]
+      context: [:prev_out, :signatures, :not_spent, :input_values, :output_sum]
     }
 
     # validate tx rules. +opts+ are:
     # rules:: which rulesets to validate (default: [:syntax, :context])
     # raise_errors:: whether to raise ValidationError on failure (default: false)
@@ -234,14 +263,18 @@
       "6a26d2ecb67f27d1fa5524763b49029d7106e91e3cc05743073461a719776192",
       # p2sh with invalid inner script, accepted by old miner before 4-2012 switchover (testnet)
       "b3c19d78b4953b694717a47d9852f8ea1ccd4cf93a45ba2e43a0f97d7cdb2655"
     ]
 
-    # setup new validator for given +tx+, validating context with +store+.
-    # also needs the +block+ to find prev_outs for chains of tx inside one block.
-    def initialize tx, store, block = nil
+    # Setup new validator for given +tx+, validating context with +store+.
+    # Also needs the +block+ that includes the tx to be validated, to find
+    # prev_outs for chains of txs inside the block.
+    # Optionally accepts the validator object for the block, to optimize fetching
+    # prev_txs and checking for doublespends.
+    def initialize(tx, store, block = nil, block_validator = nil)
       @tx, @store, @block, @errors = tx, store, block, []
+      @block_validator = block_validator
     end
 
     # check that tx hash matches data
     def hash
       generated_hash = tx.generate_hash(tx.to_payload)
@@ -253,11 +286,11 @@
       (tx.in.any? && tx.out.any?) || [tx.in.size, tx.out.size]
     end
 
     # check that tx size doesn't exceed MAX_BLOCK_SIZE.
     def max_size
-      tx.to_payload.bytesize <= MAX_BLOCK_SIZE || [tx.to_payload.bytesize, MAX_BLOCK_SIZE]
+      tx.to_payload.bytesize <= Bitcoin::MAX_BLOCK_SIZE || [tx.to_payload.bytesize, Bitcoin::MAX_BLOCK_SIZE]
     end
 
     # check that total output value doesn't exceed MAX_MONEY.
     def output_values
       total = tx.out.inject(0) {|e, out| e + out.value }
@@ -270,11 +303,11 @@
       tx.inputs.none?(&:coinbase?) || [tx.inputs.index(tx.inputs.find(&:coinbase?))]
     end
 
     # check that lock_time doesn't exceed INT_MAX
     def lock_time
-      tx.lock_time <= INT_MAX || [tx.lock_time, INT_MAX]
+      tx.lock_time <= Bitcoin::UINT32_MAX || [tx.lock_time, Bitcoin::UINT32_MAX]
     end
 
     # check that min_size is at least 86 bytes
     # (smaller tx can't be valid / do anything useful)
     def min_size
@@ -306,20 +339,27 @@
     def signatures
       sigs = tx.in.map.with_index {|txin, idx| tx.verify_input_signature(idx, prev_txs[idx], (@block ? @block.time : 0)) }
       sigs.all? || sigs.map.with_index {|s, i| s ? nil : i }.compact
     end
 
-    # check that none of the prev_outs are already spent in the main chain
-    def spent
-      spent = tx.in.map.with_index {|txin, idx|
-        next false  if @block && @block.tx.include?(prev_txs[idx])
-        next false  unless next_in = prev_txs[idx].out[txin.prev_out_index].get_next_in
-        next false  unless next_tx = next_in.get_tx
-        next false  unless next_block = next_tx.get_block
-        next_block.chain == Bitcoin::Storage::Backends::StoreBase::MAIN
-      }
-      spent.none? || spent.map.with_index {|s, i| s ? i : nil }
+    # check that none of the prev_outs are already spent in the main chain or in the current block
+    def not_spent
+      # if we received cached spents, use it
+      return block_validator.spent_outs_txins.empty? if block_validator
+
+      # find all spent txouts
+      next_ins = store.get_txins_for_txouts(tx.in.map.with_index {|txin, idx| [txin.prev_out.reverse_hth, txin.prev_out_index] })
+
+      # no txouts found spending these txins, we can safely return true
+      return true if next_ins.empty?
+
+      # there were some txouts spending these txins, verify that they are not on the main chain
+      next_ins.select! {|i| i.get_tx.blk_id } # blk_id is only set for tx in the main chain
+      return true if next_ins.empty?
+
+      # now we know some txouts are already spent, return tx_idxs for debugging purposes
+      return next_ins.map {|i| i.get_prev_out.tx_idx }
     end
 
     # check that the total input value doesn't exceed MAX_MONEY
     def input_values
       total_in < Bitcoin::network[:max_money] || [total_in, Bitcoin::network[:max_money]]
@@ -339,21 +379,12 @@
 
     # collect prev_txs needed to verify the inputs of this tx.
     # only returns tx that are in a block in the main chain or the current block.
     def prev_txs
       @prev_txs ||= tx.in.map {|i|
-        prev_tx = store.get_tx(i.prev_out.reverse_hth)
-        next prev_tx  if store.class.name =~ /UtxoStore/ && prev_tx
-        next nil  if !prev_tx && !@block
-
-        if store.class.name =~ /SequelStore/
-          block = store.db[:blk][id: prev_tx.blk_id]  if prev_tx
-          next prev_tx  if block && block[:chain] == 0
-        else
-          next prev_tx  if prev_tx && prev_tx.get_block && prev_tx.get_block.chain == 0
-        end
-        next  nil if !@block
-        @block.tx.find {|t| t.binary_hash == i.prev_out }
+        prev_tx = block_validator ? block_validator.prev_txs_hash[i.prev_out.reverse_hth] : store.get_tx(i.prev_out.reverse_hth)
+        next prev_tx if prev_tx && prev_tx.blk_id # blk_id is set only if it's in the main chain
+        @block.tx.find {|t| t.binary_hash == i.prev_out } if @block
       }.compact
     end
 
 
     def total_in