pow.go raw

   1  package neutrino
   2  
   3  import (
   4  	"fmt"
   5  	"math/big"
   6  	"sort"
   7  	"time"
   8  
   9  	"git.smesh.lol/nostrino/pkg/btcwire"
  10  	"git.smesh.lol/nostrino/pkg/crypto/chainhash"
  11  )
  12  
  13  // validateHeader checks linkage, proof of work, median-time-past and the
  14  // expected difficulty bits for a header that will be stored at height.
  15  func (c *Client) validateHeader(height uint32, h *btcwire.BlockHeader, prev chainhash.Hash) error {
  16  	if h.PrevBlock != prev {
  17  		return fmt.Errorf("neutrino: header %d does not link to %s", height, prev)
  18  	}
  19  	if !h.CheckProofOfWork() {
  20  		return fmt.Errorf("neutrino: header %d fails proof of work", height)
  21  	}
  22  	now := time.Now().Unix()
  23  	if int64(h.Timestamp) > now+2*60*60 {
  24  		return fmt.Errorf("neutrino: header %d is more than two hours in the future", height)
  25  	}
  26  	if err := c.checkMedianTimePast(height, h); err != nil {
  27  		return err
  28  	}
  29  	return c.checkDifficulty(height, h)
  30  }
  31  
  32  // checkMedianTimePast enforces the rule that a block's timestamp is greater
  33  // than the median of the previous eleven. With a checkpoint anchor there may
  34  // be fewer than eleven headers; the check starts once enough context exists.
  35  func (c *Client) checkMedianTimePast(height uint32, h *btcwire.BlockHeader) error {
  36  	if height < 11 {
  37  		return nil
  38  	}
  39  	var times [11]uint32
  40  	for i := uint32(1); i <= 11; i++ {
  41  		prev, ok := c.store.Header(height - i)
  42  		if !ok {
  43  			return nil
  44  		}
  45  		times[i-1] = prev.Timestamp
  46  	}
  47  	sorted := times[:]
  48  	sort.Slice(sorted, func(i, j int) bool { return sorted[i] < sorted[j] })
  49  	median := sorted[5]
  50  	if h.Timestamp <= median {
  51  		return fmt.Errorf("neutrino: header %d timestamp %d is not after median %d", height, h.Timestamp, median)
  52  	}
  53  	return nil
  54  }
  55  
  56  // checkDifficulty compares the header's bits with the expected value. It
  57  // returns nil when the profile or the available history does not determine
  58  // the value (the first retarget window after a checkpoint).
  59  func (c *Client) checkDifficulty(height uint32, h *btcwire.BlockHeader) error {
  60  	expected, ok := c.expectedBits(height, h)
  61  	if !ok {
  62  		return nil
  63  	}
  64  	if h.Bits != expected {
  65  		return fmt.Errorf("neutrino: header %d bits %08x, want %08x", height, h.Bits, expected)
  66  	}
  67  	return nil
  68  }
  69  
  70  func (c *Client) expectedBits(height uint32, h *btcwire.BlockHeader) (uint32, bool) {
  71  	p := c.cfg.Profile
  72  	if height == 0 {
  73  		return p.PowLimitBits, true
  74  	}
  75  	if p.NoRetarget {
  76  		return p.PowLimitBits, true
  77  	}
  78  	prev, ok := c.store.Header(height - 1)
  79  	if !ok {
  80  		if height == 1 {
  81  			return c.cfg.Profile.GenesisHeader.Bits, true
  82  		}
  83  		return 0, false
  84  	}
  85  	interval := p.RetargetInterval
  86  	if p.MinDifficulty && height%interval != 0 {
  87  		if int64(h.Timestamp) > int64(prev.Timestamp)+2*p.TargetSpacing {
  88  			return p.PowLimitBits, true
  89  		}
  90  	}
  91  	if interval == 0 || height%interval != 0 {
  92  		return prev.Bits, true
  93  	}
  94  	first, ok := c.store.Header(height - interval)
  95  	if !ok {
  96  		// The checkpoint is inside the first retarget window; the first block
  97  		// of the window is not available. Trust the peer's bits for this
  98  		// boundary and verify every later one.
  99  		return 0, false
 100  	}
 101  	actual := int64(prev.Timestamp) - int64(first.Timestamp)
 102  	min := p.TargetTimespan / 4
 103  	max := p.TargetTimespan * 4
 104  	if actual < min {
 105  		actual = min
 106  	}
 107  	if actual > max {
 108  		actual = max
 109  	}
 110  	oldTarget, err := btcwire.CompactToBig(prev.Bits)
 111  	if err != nil {
 112  		return 0, false
 113  	}
 114  	next := new(big.Int).Mul(oldTarget, big.NewInt(actual))
 115  	next.Div(next, big.NewInt(p.TargetTimespan))
 116  	limit, err := btcwire.CompactToBig(p.PowLimitBits)
 117  	if err != nil {
 118  		return 0, false
 119  	}
 120  	if next.Cmp(limit) > 0 {
 121  		next = limit
 122  	}
 123  	return BigToCompact(next), true
 124  }
 125  
 126  // BigToCompact encodes a target as Bitcoin's compact "bits" representation.
 127  func BigToCompact(n *big.Int) uint32 {
 128  	if n == nil || n.Sign() == 0 {
 129  		return 0
 130  	}
 131  	bytes := n.Bytes()
 132  	size := uint32(len(bytes))
 133  	var mantissa uint32
 134  	if size <= 3 {
 135  		v := new(big.Int).SetBytes(bytes)
 136  		mantissa = uint32(v.Uint64()) << (8 * (3 - size))
 137  	} else {
 138  		v := new(big.Int).Rsh(n, uint(8*(size-3)))
 139  		mantissa = uint32(v.Uint64())
 140  	}
 141  	if mantissa&0x00800000 != 0 {
 142  		mantissa >>= 8
 143  		size++
 144  	}
 145  	return mantissa | size<<24
 146  }
 147