func (b *BlockChain) getReorganizeNodes(node *blockNode) (*list.List, *list.List) {
	attachNodes := list.New()
	detachNodes := list.New()
	if node == nil {
		return detachNodes, attachNodes
	}
	ancestor := node
	for ; ancestor.parent != nil; ancestor = ancestor.parent {
		if ancestor.inMainChain {
			break
		}
		attachNodes.PushFront(ancestor)
	}
	for n := b.bestNode; n != nil && n.parent != nil; n = n.parent {
		if n.hash.IsEqual(ancestor.hash) {
			break
		}
		detachNodes.PushBack(n)
	}
	return detachNodes, attachNodes
}
getReorganizeNodes finds the fork point between the main chain and the passed
node and returns a list of block nodes that would need to be detached from
the main chain and a list of block nodes that would need to be attached to
the fork point (which will be the end of the main chain after detaching the
returned list of block nodes) in order to reorganize the chain such that the
passed node is the new end of the main chain.  The lists will be empty if the
passed node is not on a side chain.

This function MUST be called with the chain state lock held (for reads).
package blockchain
import (
	"container/list"
	"fmt"
	"github.com/bitgo/prova/btcec"
	"github.com/bitgo/prova/chaincfg"
	"github.com/bitgo/prova/chaincfg/chainhash"
	"github.com/bitgo/prova/database"
	"github.com/bitgo/prova/provautil"
	"github.com/bitgo/prova/txscript"
	"github.com/bitgo/prova/wire"
	"math/big"
	"sort"
	"sync"
	"time"
)
const (
	maxOrphanBlocks = 1000
)
type blockNode struct {
	parent *blockNode
	children []*blockNode
	hash *chainhash.Hash
	parentHash *chainhash.Hash
	height uint32
	workSum *big.Int
	inMainChain bool
	version    uint32
	bits       uint32
	nonce      uint64
	timestamp  int64
	merkleRoot chainhash.Hash
	size       uint32
	signature  wire.BlockSignature
	validatingPubKey wire.BlockValidatingPubKey
}
func newBlockNode(blockHeader *wire.BlockHeader, blockHash *chainhash.Hash) *blockNode {
	prevHash := blockHeader.PrevBlock
	node := blockNode{
		hash:             blockHash,
		parentHash:       &prevHash,
		workSum:          CalcWork(blockHeader.Bits),
		height:           blockHeader.Height,
		version:          blockHeader.Version,
		bits:             blockHeader.Bits,
		nonce:            blockHeader.Nonce,
		timestamp:        blockHeader.Timestamp.Unix(),
		merkleRoot:       blockHeader.MerkleRoot,
		validatingPubKey: blockHeader.ValidatingPubKey,
	}
	return &node
}
func (node *blockNode) Header() wire.BlockHeader {
	return wire.BlockHeader{
		Version:          node.version,
		PrevBlock:        *node.parentHash,
		MerkleRoot:       node.merkleRoot,
		Timestamp:        time.Unix(node.timestamp, 0),
		Bits:             node.bits,
		Height:           node.height,
		Size:             node.size,
		Nonce:            node.nonce,
		ValidatingPubKey: node.validatingPubKey,
		Signature:        node.signature,
	}
}
type orphanBlock struct {
	block      *provautil.Block
	expiration time.Time
}
func (b *BlockChain) FetchHeader(hash *chainhash.Hash) (wire.BlockHeader, error) {
	b.chainLock.RLock()
	node, ok := b.index[*hash]
	b.chainLock.RUnlock()
	if ok {
		return node.Header(), nil
	}
	var header *wire.BlockHeader
	err := b.db.View(func(dbTx database.Tx) error {
		var err error
		header, err = dbFetchHeaderByHash(dbTx, hash)
		return err
	})
	if err != nil {
		return wire.BlockHeader{}, err
	}
	return *header, nil
}
func removeChildNode(children []*blockNode, node *blockNode) []*blockNode {
	if node == nil {
		return children
	}
	for i := 0; i < len(children); i++ {
		if children[i].hash.IsEqual(node.hash) {
			copy(children[i:], children[i+1:])
			children[len(children)-1] = nil
			return children[:len(children)-1]
		}
	}
	return children
}
type BestState struct {
	Hash       *chainhash.Hash  
	Height     uint32           
	Bits       uint32           
	BlockSize  uint64           
	NumTxns    uint64           
	TotalTxns  uint64           
	MedianTime time.Time        
}
func newBestState(node *blockNode, blockSize, numTxns, totalTxns uint64,
	medianTime time.Time) *BestState {
	return &BestState{
		Hash:       node.hash,
		Height:     node.height,
		Bits:       node.bits,
		BlockSize:  blockSize,
		NumTxns:    numTxns,
		TotalTxns:  totalTxns,
		MedianTime: medianTime,
	}
}
type BlockChain struct {
	checkpoints         []chaincfg.Checkpoint
	checkpointsByHeight map[uint32]*chaincfg.Checkpoint
	db                  database.DB
	chainParams         *chaincfg.Params
	timeSource          MedianTimeSource
	notifications       NotificationCallback
	sigCache            *txscript.SigCache
	hashCache           *txscript.HashCache
	indexManager        IndexManager
	blocksPerRetarget int32  
	minMemoryNodes    int32
	chainLock sync.RWMutex
	noVerify bool
	bestNode *blockNode
	index    map[chainhash.Hash]*blockNode
	depNodes map[chainhash.Hash][]*blockNode
	threadTips map[provautil.ThreadID]*wire.OutPoint
	lastKeyID btcec.KeyID
	totalSupply uint64
	adminKeySets map[btcec.KeySetType]btcec.PublicKeySet
	aspKeyIdMap btcec.KeyIdMap
	orphanLock   sync.RWMutex
	orphans      map[chainhash.Hash]*orphanBlock
	prevOrphans  map[chainhash.Hash][]*orphanBlock
	oldestOrphan *orphanBlock
	nextCheckpoint  *chaincfg.Checkpoint
	checkpointBlock *provautil.Block
	stateLock     sync.RWMutex
	stateSnapshot *BestState
}
func (b *BlockChain) DisableVerify(disable bool) {
	b.chainLock.Lock()
	b.noVerify = disable
	b.chainLock.Unlock()
}
func (b *BlockChain) HaveBlock(hash *chainhash.Hash) (bool, error) {
	b.chainLock.RLock()
	exists, err := b.blockExists(hash)
	b.chainLock.RUnlock()
	if err != nil {
		return false, err
	}
	return exists || b.IsKnownOrphan(hash), nil
}
func (b *BlockChain) IsKnownOrphan(hash *chainhash.Hash) bool {
	b.orphanLock.RLock()
	_, exists := b.orphans[*hash]
	b.orphanLock.RUnlock()
	return exists
}
func (b *BlockChain) GetOrphanRoot(hash *chainhash.Hash) *chainhash.Hash {
	b.orphanLock.RLock()
	defer b.orphanLock.RUnlock()
	orphanRoot := hash
	prevHash := hash
	for {
		orphan, exists := b.orphans[*prevHash]
		if !exists {
			break
		}
		orphanRoot = prevHash
		prevHash = &orphan.block.MsgBlock().Header.PrevBlock
	}
	return orphanRoot
}
func (b *BlockChain) removeOrphanBlock(orphan *orphanBlock) {
	b.orphanLock.Lock()
	defer b.orphanLock.Unlock()
	orphanHash := orphan.block.Hash()
	delete(b.orphans, *orphanHash)
	prevHash := &orphan.block.MsgBlock().Header.PrevBlock
	orphans := b.prevOrphans[*prevHash]
	for i := 0; i < len(orphans); i++ {
		hash := orphans[i].block.Hash()
		if hash.IsEqual(orphanHash) {
			copy(orphans[i:], orphans[i+1:])
			orphans[len(orphans)-1] = nil
			orphans = orphans[:len(orphans)-1]
			i--
		}
	}
	b.prevOrphans[*prevHash] = orphans
	if len(b.prevOrphans[*prevHash]) == 0 {
		delete(b.prevOrphans, *prevHash)
	}
}
func (b *BlockChain) addOrphanBlock(block *provautil.Block) {
	for _, oBlock := range b.orphans {
		if time.Now().After(oBlock.expiration) {
			b.removeOrphanBlock(oBlock)
			continue
		}
		if b.oldestOrphan == nil || oBlock.expiration.Before(b.oldestOrphan.expiration) {
			b.oldestOrphan = oBlock
		}
	}
	if len(b.orphans)+1 > maxOrphanBlocks {
		b.removeOrphanBlock(b.oldestOrphan)
		b.oldestOrphan = nil
	}
	b.orphanLock.Lock()
	defer b.orphanLock.Unlock()
	expiration := time.Now().Add(time.Hour)
	oBlock := &orphanBlock{
		block:      block,
		expiration: expiration,
	}
	b.orphans[*block.Hash()] = oBlock
	prevHash := &block.MsgBlock().Header.PrevBlock
	b.prevOrphans[*prevHash] = append(b.prevOrphans[*prevHash], oBlock)
	return
}
func (b *BlockChain) loadBlockNode(dbTx database.Tx, hash *chainhash.Hash) (*blockNode, error) {
	blockHeader, err := dbFetchHeaderByHash(dbTx, hash)
	if err != nil {
		return nil, err
	}
	node := newBlockNode(blockHeader, hash)
	node.inMainChain = true
	prevHash := &blockHeader.PrevBlock
	if parentNode, ok := b.index[*prevHash]; ok {
		node.workSum = node.workSum.Add(parentNode.workSum, node.workSum)
		parentNode.children = append(parentNode.children, node)
		node.parent = parentNode
	} else if childNodes, ok := b.depNodes[*hash]; ok {
		node.workSum.Sub(childNodes[0].workSum, node.workSum)
		for _, childNode := range childNodes {
			childNode.parent = node
			node.children = append(node.children, childNode)
		}
	} else {
		str := "loadBlockNode: attempt to insert orphan block %v"
		return nil, AssertError(fmt.Sprintf(str, hash))
	}
	b.index[*hash] = node
	b.depNodes[*prevHash] = append(b.depNodes[*prevHash], node)
	return node, nil
}
func (b *BlockChain) getPrevNodeFromBlock(block *provautil.Block) (*blockNode, error) {
	prevHash := &block.MsgBlock().Header.PrevBlock
	if prevHash.IsEqual(zeroHash) {
		return nil, nil
	}
	if bn, ok := b.index[*prevHash]; ok {
		return bn, nil
	}
	var prevBlockNode *blockNode
	err := b.db.View(func(dbTx database.Tx) error {
		var err error
		prevBlockNode, err = b.loadBlockNode(dbTx, prevHash)
		return err
	})
	return prevBlockNode, err
}
func (b *BlockChain) getPrevNodeFromNode(node *blockNode) (*blockNode, error) {
	if node.parent != nil {
		return node.parent, nil
	}
	if node.hash.IsEqual(b.chainParams.GenesisHash) || node.height == 0 {
		return nil, nil
	}
	var prevBlockNode *blockNode
	err := b.db.View(func(dbTx database.Tx) error {
		var err error
		prevBlockNode, err = b.loadBlockNode(dbTx, node.parentHash)
		return err
	})
	return prevBlockNode, err
}
func (b *BlockChain) relativeNode(anchor *blockNode, distance uint32) (*blockNode, error) {
	var err error
	iterNode := anchor
	err = b.db.View(func(dbTx database.Tx) error {
		for i := distance; i > 0; i-- {
			switch {
			case iterNode.parent != nil:
				iterNode = iterNode.parent
			case iterNode.hash.IsEqual(b.chainParams.GenesisHash):
				return nil
			default:
				iterNode, err = b.loadBlockNode(dbTx,
					iterNode.parentHash)
				if err != nil {
					return err
				}
			}
		}
		return nil
	})
	if err != nil {
		return nil, err
	}
	return iterNode, nil
}
func (b *BlockChain) isMajorityVersion(minVer uint32, startNode *blockNode, numRequired uint64) bool {
	numFound := uint64(0)
	iterNode := startNode
	for i := uint64(0); i < b.chainParams.BlockUpgradeNumToCheck &&
		numFound < numRequired && iterNode != nil; i++ {
		if iterNode.version >= minVer {
			numFound++
		}
		var err error
		iterNode, err = b.getPrevNodeFromNode(iterNode)
		if err != nil {
			break
		}
	}
	return numFound >= numRequired
}
func (b *BlockChain) calcPastMedianTime(startNode *blockNode) (time.Time, error) {
	if startNode == nil {
		return b.chainParams.GenesisBlock.Header.Timestamp, nil
	}
	timestamps := make([]int64, medianTimeBlocks)
	numNodes := 0
	iterNode := startNode
	for i := 0; i < medianTimeBlocks && iterNode != nil; i++ {
		timestamps[i] = iterNode.timestamp
		numNodes++
		var err error
		iterNode, err = b.getPrevNodeFromNode(iterNode)
		if err != nil {
			log.Errorf("getPrevNodeFromNode: %v", err)
			return time.Time{}, err
		}
	}
	timestamps = timestamps[:numNodes]
	sort.Sort(timeSorter(timestamps))
	medianTimestamp := timestamps[numNodes/2]
	return time.Unix(medianTimestamp, 0), nil
}
type SequenceLock struct {
	Seconds     int64
	BlockHeight int32
}
func (b *BlockChain) CalcSequenceLock(tx *provautil.Tx, utxoView *UtxoViewpoint,
	mempool bool) (*SequenceLock, error) {
	b.chainLock.Lock()
	defer b.chainLock.Unlock()
	return b.calcSequenceLock(tx, utxoView, mempool)
}
func (b *BlockChain) calcSequenceLock(tx *provautil.Tx, utxoView *UtxoViewpoint,
	mempool bool) (*SequenceLock, error) {
	mTx := tx.MsgTx()
	sequenceLock := &SequenceLock{Seconds: -1, BlockHeight: -1}
	sequenceLockActive := mTx.Version >= 2 && (mempool || true)
	if !sequenceLockActive || IsCoinBase(tx) {
		return sequenceLock, nil
	}
	nextHeight := b.BestSnapshot().Height + 1
	for txInIndex, txIn := range mTx.TxIn {
		utxo := utxoView.LookupEntry(&txIn.PreviousOutPoint.Hash)
		if utxo == nil {
			str := fmt.Sprintf("unable to find unspent output "+
				"%v referenced from transaction %s:%d",
				txIn.PreviousOutPoint, tx.Hash(), txInIndex)
			return sequenceLock, ruleError(ErrMissingTx, str)
		}
		inputHeight := utxo.BlockHeight()
		if inputHeight == 0x7fffffff {
			inputHeight = nextHeight
		}
		sequenceNum := txIn.Sequence
		relativeLock := int64(sequenceNum & wire.SequenceLockTimeMask)
		switch {
		case sequenceNum&wire.SequenceLockTimeDisabled == wire.SequenceLockTimeDisabled:
			continue
		case sequenceNum&wire.SequenceLockTimeIsSeconds == wire.SequenceLockTimeIsSeconds:
			inputDepth := uint32(b.bestNode.height-inputHeight) + 1
			blockNode, err := b.relativeNode(b.bestNode, inputDepth)
			if err != nil {
				return sequenceLock, err
			}
			medianTime, err := b.calcPastMedianTime(blockNode)
			if err != nil {
				return sequenceLock, err
			}
			timeLockSeconds := (relativeLock << wire.SequenceLockTimeGranularity) - 1
			timeLock := medianTime.Unix() + timeLockSeconds
			if timeLock > sequenceLock.Seconds {
				sequenceLock.Seconds = timeLock
			}
		default:
			blockHeight := int32(inputHeight) + int32(relativeLock-1)
			if blockHeight > sequenceLock.BlockHeight {
				sequenceLock.BlockHeight = blockHeight
			}
		}
	}
	return sequenceLock, nil
}
func LockTimeToSequence(isSeconds bool, locktime uint32) uint32 {
	if !isSeconds {
		return locktime
	}
	return wire.SequenceLockTimeIsSeconds |
		locktime>>wire.SequenceLockTimeGranularity
}