tickets.go

// Copyright (c) 2015-2022 The Decred developers
// Use of this source code is governed by an ISC
// license that can be found in the LICENSE file.

package stake

import (
	"fmt"

	"github.com/decred/dcrd/blockchain/stake/v5/internal/dbnamespace"
	"github.com/decred/dcrd/blockchain/stake/v5/internal/ticketdb"
	"github.com/decred/dcrd/blockchain/stake/v5/internal/tickettreap"
	"github.com/decred/dcrd/chaincfg/chainhash"
	"github.com/decred/dcrd/database/v3"
	"github.com/decred/dcrd/wire"
)

// UndoTicketDataSlice is a pass through for ticketdb's UndoTicketData, which is
// stored in memory in the node.
type UndoTicketDataSlice []ticketdb.UndoTicketData

// StakeParams defines an interface that is used to provides the parameters
// required working with stake nodes.  These values are typically well-defined
// and unique per network.
type StakeParams interface {
	// VotesPerBlock returns the maximum number of votes a block must contain to
	// receive full subsidy.
	VotesPerBlock() uint16

	// StakeValidationBeginHeight returns the height at which votes become
	// required to extend a block.  This height is the first that will be voted
	// on, but will not include any votes itself.
	StakeValidationBeginHeight() int64

	// StakeEnableHeight returns the height at which the first ticket could
	// possibly mature.
	StakeEnableHeight() int64

	// TicketExpiryBlocks returns the number of blocks after maturity that
	// tickets expire. This will be >= (StakeEnableHeight() +
	// StakeValidationBeginHeight()).
	TicketExpiryBlocks() uint32
}

// Node is in-memory stake data for a node.  It contains a list of database
// updates to be written in the case that the block is inserted in the main
// chain database.  Because of its use of immutable treap data structures, it
// allows for a fast, efficient in-memory representation of the ticket database
// for each node.  It handles connection of and disconnection of new blocks
// simply.
//
// Like the immutable treap structures, stake nodes themselves are considered
// to be immutable.  The connection or disconnection of past or future nodes
// returns a pointer to a new stake node, which must be saved and used
// appropriately.
type Node struct {
	height uint32

	// liveTickets is the treap of the live tickets for this node.
	liveTickets *tickettreap.Immutable

	// missedTickets is the treap of missed tickets for this node.
	missedTickets *tickettreap.Immutable

	// revokedTickets is the treap of revoked tickets for this node.
	revokedTickets *tickettreap.Immutable

	// databaseUndoUpdate is the cache of the database used to undo
	// the current node's addition to the blockchain.
	databaseUndoUpdate UndoTicketDataSlice

	// databaseBlockTickets is the cache of the new tickets to insert
	// into the database.
	databaseBlockTickets ticketdb.TicketHashes

	// nextWinners is the list of the next winners for this block.
	nextWinners []chainhash.Hash

	// finalState is the calculated final state checksum from the live
	// tickets pool.
	finalState [6]byte

	// params is the blockchain stake parameters.
	params StakeParams
}

// UndoData returns the stored UndoTicketDataSlice used to remove this node
// and restore it to the parent state.
func (sn *Node) UndoData() UndoTicketDataSlice {
	return sn.databaseUndoUpdate
}

// NewTickets returns the stored UndoTicketDataSlice used to remove this node
// and restore it to the parent state.
func (sn *Node) NewTickets() []chainhash.Hash {
	return sn.databaseBlockTickets
}

// SpentByBlock returns the tickets that were spent in this block.
func (sn *Node) SpentByBlock() []chainhash.Hash {
	var spent []chainhash.Hash
	for _, undo := range sn.databaseUndoUpdate {
		if undo.Spent {
			spent = append(spent, undo.TicketHash)
		}
	}

	return spent
}

// MissedByBlock returns the tickets that were missed in this block. This
// includes expired tickets and winning tickets that were not spent by a vote.
// Also note that when a miss is later revoked, that ticket hash will also
// appear in the output of this function for the block with the revocation.
func (sn *Node) MissedByBlock() []chainhash.Hash {
	var missed []chainhash.Hash
	for _, undo := range sn.databaseUndoUpdate {
		if undo.Missed {
			missed = append(missed, undo.TicketHash)
		}
	}

	return missed
}

// ExpiredByBlock returns the tickets that expired in this block. This is a
// subset of the missed tickets returned by MissedByBlock. The output only
// includes the initial expiration of the ticket, not when an expired ticket is
// revoked. This is unlike MissedByBlock that includes the revocation as well.
func (sn *Node) ExpiredByBlock() []chainhash.Hash {
	var expired []chainhash.Hash
	for _, undo := range sn.databaseUndoUpdate {
		if undo.Expired && !undo.Revoked {
			expired = append(expired, undo.TicketHash)
		}
	}

	return expired
}

// ExpiringNextBlock returns the tickets that will expire in the next block.
func (sn *Node) ExpiringNextBlock() []chainhash.Hash {
	// Determine the height of tickets that will expire in the next block.
	nextBlockHeight := sn.height + 1
	toExpireHeight := uint32(0)
	if nextBlockHeight > sn.params.TicketExpiryBlocks() {
		toExpireHeight = nextBlockHeight - sn.params.TicketExpiryBlocks()
	}

	// Create a map of the winning ticket hashes.
	winners := sn.Winners()
	winningHashes := make(map[chainhash.Hash]struct{}, sn.params.VotesPerBlock())
	for _, ticketHash := range winners {
		winningHashes[ticketHash] = struct{}{}
	}

	// Find all tickets in the live ticket treap that are set to expire next
	// block.
	var expiringNextBlockHashes []chainhash.Hash
	sn.liveTickets.ForEachByHeight(toExpireHeight+1, func(k tickettreap.Key, v *tickettreap.Value) bool {
		// Since ForEachByHeight iterates all elements in the tree _less_ than a
		// given height, continue if the height is not equal to the height that is
		// set to expire next block.
		//
		// Note that this should never get hit since any height less than the height
		// that is set to expire next block should have already expired and been
		// moved out of the live ticket treap.
		if v.Height != toExpireHeight {
			return true
		}

		// Don't include winning tickets since they will either vote or be missed in
		// the next block rather than become expired.
		ticketHash := chainhash.Hash(k)
		if _, ok := winningHashes[ticketHash]; ok {
			return true
		}

		expiringNextBlockHashes = append(expiringNextBlockHashes, ticketHash)
		return true
	})

	return expiringNextBlockHashes
}

// ExistsLiveTicket returns whether or not a ticket exists in the live ticket
// treap for this stake node.
func (sn *Node) ExistsLiveTicket(ticket chainhash.Hash) bool {
	return sn.liveTickets.Has(tickettreap.Key(ticket))
}

// LiveTickets returns the list of live tickets for this stake node.
func (sn *Node) LiveTickets() []chainhash.Hash {
	tickets := make([]chainhash.Hash, sn.liveTickets.Len())
	i := 0
	sn.liveTickets.ForEach(func(k tickettreap.Key, v *tickettreap.Value) bool {
		tickets[i] = chainhash.Hash(k)
		i++
		return true
	})

	return tickets
}

// PoolSize returns the size of the live ticket pool.
func (sn *Node) PoolSize() int {
	return sn.liveTickets.Len()
}

// ExistsMissedTicket returns whether or not a ticket exists in the missed
// ticket treap for this stake node.
func (sn *Node) ExistsMissedTicket(ticket chainhash.Hash) bool {
	return sn.missedTickets.Has(tickettreap.Key(ticket))
}

// MissedTickets returns the list of missed tickets for this stake node.
func (sn *Node) MissedTickets() []chainhash.Hash {
	tickets := make([]chainhash.Hash, sn.missedTickets.Len())
	i := 0
	sn.missedTickets.ForEach(func(k tickettreap.Key, v *tickettreap.Value) bool {
		tickets[i] = chainhash.Hash(k)
		i++
		return true
	})

	return tickets
}

// ExistsRevokedTicket returns whether or not a ticket exists in the revoked
// ticket treap for this stake node.
func (sn *Node) ExistsRevokedTicket(ticket chainhash.Hash) bool {
	return sn.revokedTickets.Has(tickettreap.Key(ticket))
}

// RevokedTickets returns the list of revoked tickets for this stake node.
func (sn *Node) RevokedTickets() []*chainhash.Hash {
	tickets := make([]*chainhash.Hash, sn.revokedTickets.Len())
	i := 0
	sn.revokedTickets.ForEach(func(k tickettreap.Key, v *tickettreap.Value) bool {
		h := chainhash.Hash(k)
		tickets[i] = &h
		i++
		return true
	})

	return tickets
}

// ExistsExpiredTicket returns whether or not a ticket was ever expired from
// the perspective of this stake node.
func (sn *Node) ExistsExpiredTicket(ticket chainhash.Hash) bool {
	v := sn.missedTickets.Get(tickettreap.Key(ticket))
	if v != nil && v.Expired {
		return true
	}
	v = sn.revokedTickets.Get(tickettreap.Key(ticket))
	if v != nil && v.Expired {
		return true
	}

	return false
}

// Winners returns the current list of winners for this stake node, which
// can vote on this node.
func (sn *Node) Winners() []chainhash.Hash {
	return sn.nextWinners
}

// FinalState returns the final state lottery checksum of the node.
func (sn *Node) FinalState() [6]byte {
	return sn.finalState
}

// Height returns the height of the node.
func (sn *Node) Height() uint32 {
	return sn.height
}

// genesisNode returns a pointer to the initialized ticket database for the
// genesis block.
func genesisNode(params StakeParams) *Node {
	return &Node{
		height:               0,
		liveTickets:          &tickettreap.Immutable{},
		missedTickets:        &tickettreap.Immutable{},
		revokedTickets:       &tickettreap.Immutable{},
		databaseUndoUpdate:   make([]ticketdb.UndoTicketData, 0),
		databaseBlockTickets: make(ticketdb.TicketHashes, 0),
		nextWinners:          make([]chainhash.Hash, 0),
		params:               params,
	}
}

// ResetDatabase resets the ticket database back to the genesis block.
func ResetDatabase(dbTx database.Tx, params StakeParams, genesisHash *chainhash.Hash) error {
	// Remove all of the database buckets.
	err := ticketdb.DbRemoveAllBuckets(dbTx)
	if err != nil {
		return err
	}

	// Initialize the database.
	_, err = InitDatabaseState(dbTx, params, genesisHash)
	return err
}

// InitDatabaseState initializes the chain with the best state being the
// genesis block.
func InitDatabaseState(dbTx database.Tx, params StakeParams, genesisHash *chainhash.Hash) (*Node, error) {
	// Create the database.
	err := ticketdb.DbCreate(dbTx)
	if err != nil {
		return nil, err
	}

	// Write the new block undo and new tickets data to the
	// database for the genesis block.
	genesis := genesisNode(params)
	err = ticketdb.DbPutBlockUndoData(dbTx, genesis.height,
		genesis.databaseUndoUpdate)
	if err != nil {
		return nil, err
	}

	err = ticketdb.DbPutNewTickets(dbTx, genesis.height,
		genesis.databaseBlockTickets)
	if err != nil {
		return nil, err
	}

	// Write the new best state to the database.
	nextWinners := make([]chainhash.Hash, int(genesis.params.VotesPerBlock()))
	err = ticketdb.DbPutBestState(dbTx, ticketdb.BestChainState{
		Hash:        *genesisHash,
		Height:      genesis.height,
		Live:        uint32(genesis.liveTickets.Len()),
		Missed:      uint64(genesis.missedTickets.Len()),
		Revoked:     uint64(genesis.revokedTickets.Len()),
		PerBlock:    genesis.params.VotesPerBlock(),
		NextWinners: nextWinners,
	})
	if err != nil {
		return nil, err
	}

	return genesis, nil
}

// LoadBestNode is used when the blockchain is initialized, to get the initial
// stake node from the database bucket.  The blockchain must pass the height
// and the blockHash to confirm that the ticket database is on the same
// location in the blockchain as the blockchain itself.  This function also
// checks to ensure that the database has not failed the upgrade process and
// reports the current version.  Upgrades are also handled by this function,
// when they become applicable.
func LoadBestNode(dbTx database.Tx, height uint32, blockHash chainhash.Hash, header wire.BlockHeader, params StakeParams) (*Node, error) {
	info, err := ticketdb.DbFetchDatabaseInfo(dbTx)
	if err != nil {
		return nil, err
	}

	// Compare the tip and make sure it matches.
	state, err := ticketdb.DbFetchBestState(dbTx)
	if err != nil {
		return nil, err
	}
	if state.Hash != blockHash || state.Height != height {
		str := "best state corruption"
		return nil, stakeRuleError(ErrDatabaseCorrupt, str)
	}

	// Restore the best node treaps form the database.
	node := new(Node)
	node.height = height
	node.params = params
	node.liveTickets, err = ticketdb.DbLoadAllTickets(dbTx,
		dbnamespace.LiveTicketsBucketName)
	if err != nil {
		return nil, err
	}
	if node.liveTickets.Len() != int(state.Live) {
		str := fmt.Sprintf("live tickets corruption (got %v in state but "+
			"loaded %v)", int(state.Live), node.liveTickets.Len())
		return nil, stakeRuleError(ErrDatabaseCorrupt, str)
	}
	node.missedTickets, err = ticketdb.DbLoadAllTickets(dbTx,
		dbnamespace.MissedTicketsBucketName)
	if err != nil {
		return nil, err
	}
	if node.missedTickets.Len() != int(state.Missed) {
		str := fmt.Sprintf("missed tickets corruption (got %v in state but "+
			"loaded %v)", int(state.Missed), node.missedTickets.Len())
		return nil, stakeRuleError(ErrDatabaseCorrupt, str)
	}
	node.revokedTickets, err = ticketdb.DbLoadAllTickets(dbTx,
		dbnamespace.RevokedTicketsBucketName)
	if err != nil {
		return nil, err
	}
	if node.revokedTickets.Len() != int(state.Revoked) {
		str := fmt.Sprintf("revoked tickets corruption (got %v in state but "+
			"loaded %v)", int(state.Revoked), node.revokedTickets.Len())
		return nil, stakeRuleError(ErrDatabaseCorrupt, str)
	}

	// Restore the node undo and new tickets data.
	node.databaseUndoUpdate, err = ticketdb.DbFetchBlockUndoData(dbTx, height)
	if err != nil {
		return nil, err
	}
	node.databaseBlockTickets, err = ticketdb.DbFetchNewTickets(dbTx, height)
	if err != nil {
		return nil, err
	}

	// Restore the next winners for the node.
	node.nextWinners = make([]chainhash.Hash, 0)
	if node.height >= uint32(params.StakeValidationBeginHeight()-1) {
		node.nextWinners = make([]chainhash.Hash, len(state.NextWinners))
		copy(node.nextWinners, state.NextWinners)

		// Calculate the final state from the block header.
		stateBuffer := make([]byte, 0,
			(params.VotesPerBlock()+1)*chainhash.HashSize)
		for _, ticketHash := range node.nextWinners {
			stateBuffer = append(stateBuffer, ticketHash[:]...)
		}
		hB, err := header.Bytes()
		if err != nil {
			return nil, err
		}
		prng := NewHash256PRNG(hB)
		_, err = findTicketIdxs(node.liveTickets.Len(),
			params.VotesPerBlock(), prng)
		if err != nil {
			return nil, err
		}
		lastHash := prng.StateHash()
		stateBuffer = append(stateBuffer, lastHash[:]...)
		copy(node.finalState[:], chainhash.HashB(stateBuffer)[0:6])
	}

	log.Infof("Stake database version %v loaded", info.Version)

	return node, nil
}

// hashInSlice determines if a hash exists in a slice of hashes.
func hashInSlice(h chainhash.Hash, list []chainhash.Hash) bool {
	for _, hash := range list {
		if h == hash {
			return true
		}
	}

	return false
}

// safeGet fetches a pointer to the data for the key in the treap, then
// copies the value so that the original pointer to the key is never written
// to accidentally later.
func safeGet(t *tickettreap.Immutable, k tickettreap.Key) (*tickettreap.Value, error) {
	// TODO: This function could also check to make sure the states of the
	//       ticket treap value are valid.

	v := t.Get(k)
	if v == nil {
		str := fmt.Sprintf("ticket %v was supposed to be in the passed "+
			"treap, but could not be found", chainhash.Hash(k))
		return nil, stakeRuleError(ErrMissingTicket, str)
	}

	return &tickettreap.Value{
		Height:  v.Height,
		Missed:  v.Missed,
		Revoked: v.Revoked,
		Spent:   v.Spent,
		Expired: v.Expired,
	}, nil
}

// safePut is used to put a value into an immutable ticket treap, returning
// the mutated, immutable treap given as a result.  It first checks to see if
// there is already this key in the treap. If there is, it returns an error.
func safePut(t *tickettreap.Immutable, k tickettreap.Key, v *tickettreap.Value) (*tickettreap.Immutable, error) {
	// TODO This function could also check to make sure the states of the ticket
	//      treap value are valid.

	if t.Has(k) {
		str := fmt.Sprintf("attempted to insert duplicate key %v into treap",
			chainhash.Hash(k))
		return nil, stakeRuleError(ErrDuplicateTicket, str)
	}

	return t.Put(k, v), nil
}

// safeDelete is used to delete a value in an immutable ticket treap, returning
// the mutated, immutable treap given as a result.  It first checks to see if
// the key exists in the treap. If it does not, it returns an error.
func safeDelete(t *tickettreap.Immutable, k tickettreap.Key) (*tickettreap.Immutable, error) {
	if !t.Has(k) {
		str := fmt.Sprintf("attempted to delete non-existing key %v "+
			"from treap", chainhash.Hash(k))
		return nil, stakeRuleError(ErrMissingTicket, str)
	}

	return t.Delete(k), nil
}

// connectNode connects a child to a parent stake node, returning the
// modified stake node for the child.  It is important to keep in mind that
// the argument node is the parent node, and that the child stake node is
// returned after subsequent modification of the parent node's immutable
// data.
func connectNode(node *Node, lotteryIV chainhash.Hash, ticketsVoted, revokedTickets, newTickets []chainhash.Hash) (*Node, error) {
	if node == nil {
		return nil, fmt.Errorf("missing stake node pointer input when connecting")
	}

	connectedNode := &Node{
		height:               node.height + 1,
		liveTickets:          node.liveTickets,
		missedTickets:        node.missedTickets,
		revokedTickets:       node.revokedTickets,
		databaseUndoUpdate:   make(UndoTicketDataSlice, 0),
		databaseBlockTickets: newTickets,
		nextWinners:          make([]chainhash.Hash, 0),
		params:               node.params,
	}

	// We only have to deal with vote-related issues and expiry after
	// StakeEnabledHeight.
	var err error
	if connectedNode.height >= uint32(connectedNode.params.StakeEnableHeight()) {
		// Basic sanity check.
		for i := range ticketsVoted {
			if !hashInSlice(ticketsVoted[i], node.nextWinners) {
				str := fmt.Sprintf("unknown ticket %v spent in block",
					ticketsVoted[i])
				return nil, stakeRuleError(ErrUnknownTicketSpent, str)
			}
		}

		// Iterate through all possible winners and construct the undo data,
		// updating the live and missed ticket treaps as necessary.  We need
		// to copy the value here so we don't modify it in the previous treap.
		for _, ticket := range node.nextWinners {
			k := tickettreap.Key(ticket)
			v, err := safeGet(connectedNode.liveTickets, k)
			if err != nil {
				return nil, err
			}

			// If it's spent in this block, mark it as being spent.  Otherwise,
			// it was missed.  Spent tickets are dropped from the live ticket
			// bucket, while missed tickets are pushed to the missed ticket
			// bucket.  Because we already know from the above check that the
			// ticket should still be in the live tickets treap, we probably
			// do not have to use the safe delete functions, but do so anyway
			// just to be safe.
			if hashInSlice(ticket, ticketsVoted) {
				v.Spent = true
				v.Missed = false
				connectedNode.liveTickets, err =
					safeDelete(connectedNode.liveTickets, k)
				if err != nil {
					return nil, err
				}
			} else {
				v.Spent = false
				v.Missed = true
				connectedNode.liveTickets, err =
					safeDelete(connectedNode.liveTickets, k)
				if err != nil {
					return nil, err
				}
				connectedNode.missedTickets, err =
					safePut(connectedNode.missedTickets, k, v)
				if err != nil {
					return nil, err
				}
			}

			connectedNode.databaseUndoUpdate =
				append(connectedNode.databaseUndoUpdate, ticketdb.UndoTicketData{
					TicketHash:   ticket,
					TicketHeight: v.Height,
					Missed:       v.Missed,
					Revoked:      v.Revoked,
					Spent:        v.Spent,
					Expired:      v.Expired,
				})
		}

		// Find the expiring tickets and drop them as well.  We already know what
		// the winners are from the cached information in the previous block, so
		// no drop the results of that here.
		toExpireHeight := uint32(0)
		if connectedNode.height > connectedNode.params.TicketExpiryBlocks() {
			toExpireHeight = connectedNode.height -
				connectedNode.params.TicketExpiryBlocks()
		}

		connectedNode.liveTickets.ForEachByHeight(toExpireHeight+1, func(treapKey tickettreap.Key, value *tickettreap.Value) bool {
			// Make a copy of the value.
			v := *value
			v.Missed = true
			v.Expired = true
			connectedNode.liveTickets, err =
				safeDelete(connectedNode.liveTickets, treapKey)
			if err != nil {
				return false
			}
			connectedNode.missedTickets, err =
				safePut(connectedNode.missedTickets, treapKey, &v)
			if err != nil {
				return false
			}

			ticketHash := chainhash.Hash(treapKey)
			connectedNode.databaseUndoUpdate =
				append(connectedNode.databaseUndoUpdate, ticketdb.UndoTicketData{
					TicketHash:   ticketHash,
					TicketHeight: v.Height,
					Missed:       v.Missed,
					Revoked:      v.Revoked,
					Spent:        v.Spent,
					Expired:      v.Expired,
				})

			return true
		})

		if err != nil {
			return nil, err
		}

		// Process all the revocations, moving them from the missed to the
		// revoked treap and recording them in the undo data.
		for _, revokedTicket := range revokedTickets {
			v, err := safeGet(connectedNode.missedTickets,
				tickettreap.Key(revokedTicket))
			if err != nil {
				return nil, err
			}
			v.Revoked = true
			connectedNode.missedTickets, err =
				safeDelete(connectedNode.missedTickets,
					tickettreap.Key(revokedTicket))
			if err != nil {
				return nil, err
			}
			connectedNode.revokedTickets, err =
				safePut(connectedNode.revokedTickets,
					tickettreap.Key(revokedTicket), v)
			if err != nil {
				return nil, err
			}

			connectedNode.databaseUndoUpdate =
				append(connectedNode.databaseUndoUpdate, ticketdb.UndoTicketData{
					TicketHash:   revokedTicket,
					TicketHeight: v.Height,
					Missed:       v.Missed,
					Revoked:      v.Revoked,
					Spent:        v.Spent,
					Expired:      v.Expired,
				})
		}
	}

	// Add all the new tickets.
	for _, newTicket := range newTickets {
		k := tickettreap.Key(newTicket)
		v := &tickettreap.Value{
			Height:  connectedNode.height,
			Missed:  false,
			Revoked: false,
			Spent:   false,
			Expired: false,
		}
		connectedNode.liveTickets, err =
			safePut(connectedNode.liveTickets, k, v)
		if err != nil {
			return nil, err
		}

		connectedNode.databaseUndoUpdate =
			append(connectedNode.databaseUndoUpdate, ticketdb.UndoTicketData{
				TicketHash:   newTicket,
				TicketHeight: v.Height,
				Missed:       v.Missed,
				Revoked:      v.Revoked,
				Spent:        v.Spent,
				Expired:      v.Expired,
			})
	}

	// The first block voted on is at StakeValidationHeight, so begin calculating
	// winners at the block before StakeValidationHeight.
	if connectedNode.height >=
		uint32(connectedNode.params.StakeValidationBeginHeight()-1) {
		// Find the next set of winners.
		prng := NewHash256PRNGFromIV(lotteryIV)
		idxs, err := findTicketIdxs(connectedNode.liveTickets.Len(),
			connectedNode.params.VotesPerBlock(), prng)
		if err != nil {
			return nil, err
		}

		stateBuffer := make([]byte, 0,
			(connectedNode.params.VotesPerBlock()+1)*chainhash.HashSize)
		nextWinnersKeys, err := fetchWinners(idxs, connectedNode.liveTickets)
		if err != nil {
			return nil, err
		}

		for _, treapKey := range nextWinnersKeys {
			ticketHash := chainhash.Hash(*treapKey)
			connectedNode.nextWinners = append(connectedNode.nextWinners,
				ticketHash)
			stateBuffer = append(stateBuffer, ticketHash[:]...)
		}
		lastHash := prng.StateHash()
		stateBuffer = append(stateBuffer, lastHash[:]...)
		copy(connectedNode.finalState[:], chainhash.HashB(stateBuffer)[0:6])
	}

	return connectedNode, nil
}

// ConnectNode connects a stake node to the node and returns a pointer
// to the stake node of the child.
func (sn *Node) ConnectNode(lotteryIV chainhash.Hash, ticketsVoted, revokedTickets, newTickets []chainhash.Hash) (*Node, error) {
	return connectNode(sn, lotteryIV, ticketsVoted, revokedTickets,
		newTickets)
}

// disconnectNode disconnects a stake node from itself and returns the state of
// the parent node.  The database transaction should be included if the
// UndoTicketDataSlice or tickets are nil in order to look up the undo data or
// tickets from the database.
func disconnectNode(node *Node, parentLotteryIV chainhash.Hash, parentUtds UndoTicketDataSlice, parentTickets []chainhash.Hash, dbTx database.Tx) (*Node, error) {
	// Edge case for the parent being the genesis block.
	if node.height == 1 {
		return genesisNode(node.params), nil
	}

	if node == nil {
		return nil, fmt.Errorf("missing stake node pointer input when " +
			"disconnecting")
	}

	// The undo ticket slice is normally stored in memory for the most
	// recent blocks and the sidechain, but it may be the case that it
	// is missing because it's in the mainchain and very old (thus
	// outside the node cache).  In this case, restore this data from
	// disk.
	if parentUtds == nil || parentTickets == nil {
		if dbTx == nil {
			str := "needed to look up undo data in the database, but " +
				"no dbtx passed"
			return nil, stakeRuleError(ErrMissingDatabaseTx, str)
		}

		var err error
		parentUtds, err = ticketdb.DbFetchBlockUndoData(dbTx, node.height-1)
		if err != nil {
			return nil, err
		}

		parentTickets, err = ticketdb.DbFetchNewTickets(dbTx, node.height-1)
		if err != nil {
			return nil, err
		}
	}

	votesPerBlock := node.params.VotesPerBlock()
	restoredNode := &Node{
		height:               node.height - 1,
		liveTickets:          node.liveTickets,
		missedTickets:        node.missedTickets,
		revokedTickets:       node.revokedTickets,
		databaseUndoUpdate:   parentUtds,
		databaseBlockTickets: parentTickets,
		nextWinners:          make([]chainhash.Hash, 0, votesPerBlock),
		params:               node.params,
	}

	// Iterate through the block undo data and write all database changes to the
	// respective treap, reversing all the changes added when the child block was
	// added to the chain.
	//
	// Note that the undo data must be applied in reverse order since there may
	// be multiple changes for the same ticket.  For example, when the automatic
	// revocations agenda is enabled a ticket can become missed and revoked in the
	// same block.  This is recorded as two separate entries in the undo data and
	// must be processed in reverse order when disconnecting.
	winners := make([]chainhash.Hash, 0, votesPerBlock)
	for i := len(node.databaseUndoUpdate) - 1; i >= 0; i-- {
		undo := node.databaseUndoUpdate[i]
		var err error
		k := tickettreap.Key(undo.TicketHash)
		v := &tickettreap.Value{
			Height:  undo.TicketHeight,
			Missed:  undo.Missed,
			Revoked: undo.Revoked,
			Spent:   undo.Spent,
			Expired: undo.Expired,
		}

		switch {
		// All flags are unset; this is a newly added ticket.
		// Remove it from the list of live tickets.
		case !undo.Missed && !undo.Revoked && !undo.Spent:
			restoredNode.liveTickets, err =
				safeDelete(restoredNode.liveTickets, k)
			if err != nil {
				return nil, err
			}

		// The ticket was missed and revoked.  It needs to
		// be moved from the revoked ticket treap to the
		// missed ticket treap.
		case undo.Missed && undo.Revoked:
			v.Revoked = false
			restoredNode.revokedTickets, err =
				safeDelete(restoredNode.revokedTickets, k)
			if err != nil {
				return nil, err
			}
			restoredNode.missedTickets, err =
				safePut(restoredNode.missedTickets, k, v)
			if err != nil {
				return nil, err
			}

		// The ticket was missed and was previously live.
		// Remove it from the missed tickets bucket and
		// move it to the live tickets bucket.
		case undo.Missed && !undo.Revoked:
			// Expired tickets could never have been
			// winners.
			if !undo.Expired {
				winners = append(winners, undo.TicketHash)
			} else {
				v.Expired = false
			}
			v.Missed = false
			restoredNode.missedTickets, err =
				safeDelete(restoredNode.missedTickets, k)
			if err != nil {
				return nil, err
			}
			restoredNode.liveTickets, err =
				safePut(restoredNode.liveTickets, k, v)
			if err != nil {
				return nil, err
			}

		// The ticket was spent.  Reinsert it into the live
		// tickets treap and add it to the list of next
		// winners.
		case undo.Spent:
			v.Spent = false
			winners = append(winners, undo.TicketHash)
			restoredNode.liveTickets, err =
				safePut(restoredNode.liveTickets, k, v)
			if err != nil {
				return nil, err
			}

		default:
			str := "unknown ticket state in undo data"
			return nil, stakeRuleError(ErrMemoryCorruption, str)
		}
	}

	// Set the next winners on the restored node.  The winners are appended in
	// reverse order since the undo data is applied in reverse above.
	numWinners := len(winners)
	stateBuffer := make([]byte, 0, (numWinners+1)*chainhash.HashSize)
	for i := numWinners - 1; i >= 0; i-- {
		winner := winners[i]
		restoredNode.nextWinners = append(restoredNode.nextWinners, winner)
		stateBuffer = append(stateBuffer, winner[:]...)
	}

	if node.height >= uint32(node.params.StakeValidationBeginHeight()) {
		prng := NewHash256PRNGFromIV(parentLotteryIV)
		_, err := findTicketIdxs(restoredNode.liveTickets.Len(),
			node.params.VotesPerBlock(), prng)
		if err != nil {
			return nil, err
		}
		lastHash := prng.StateHash()
		stateBuffer = append(stateBuffer, lastHash[:]...)
		copy(restoredNode.finalState[:], chainhash.HashB(stateBuffer)[0:6])
	}

	return restoredNode, nil
}

// DisconnectNode disconnects a stake node from the node and returns a pointer
// to the stake node of the parent.
func (sn *Node) DisconnectNode(parentLotteryIV chainhash.Hash, parentUtds UndoTicketDataSlice, parentTickets []chainhash.Hash, dbTx database.Tx) (*Node, error) {
	return disconnectNode(sn, parentLotteryIV, parentUtds, parentTickets, dbTx)
}

// WriteConnectedBestNode writes the newly connected best node to the database
// under an atomic database transaction, performing all the necessary writes to
// the database buckets for live, missed, and revoked tickets.
func WriteConnectedBestNode(dbTx database.Tx, node *Node, hash chainhash.Hash) error {
	// Iterate through the block undo data and write all database
	// changes to the respective on-disk map.
	for _, undo := range node.databaseUndoUpdate {
		var err error
		switch {
		// All flags are unset; this is a newly added ticket.
		// Insert it into the live ticket database.
		case !undo.Missed && !undo.Revoked && !undo.Spent:
			err = ticketdb.DbPutTicket(dbTx, dbnamespace.LiveTicketsBucketName,
				&undo.TicketHash, undo.TicketHeight, undo.Missed, undo.Revoked,
				undo.Spent, undo.Expired)
			if err != nil {
				return err
			}

		// The ticket was missed and revoked.  It needs to
		// be moved from the missed ticket bucket to the
		// revoked ticket bucket.
		case undo.Missed && undo.Revoked:
			err = ticketdb.DbDeleteTicket(dbTx,
				dbnamespace.MissedTicketsBucketName,
				&undo.TicketHash)
			if err != nil {
				return err
			}
			err = ticketdb.DbPutTicket(dbTx, dbnamespace.RevokedTicketsBucketName,
				&undo.TicketHash, undo.TicketHeight, undo.Missed, undo.Revoked,
				undo.Spent, undo.Expired)
			if err != nil {
				return err
			}

		// The ticket was missed and was previously live.
		// Move it from the live ticket bucket to the missed
		// ticket bucket.
		case undo.Missed && !undo.Revoked:
			err = ticketdb.DbDeleteTicket(dbTx,
				dbnamespace.LiveTicketsBucketName,
				&undo.TicketHash)
			if err != nil {
				return err
			}
			err = ticketdb.DbPutTicket(dbTx, dbnamespace.MissedTicketsBucketName,
				&undo.TicketHash, undo.TicketHeight, true, undo.Revoked,
				undo.Spent, undo.Expired)
			if err != nil {
				return err
			}

		// The ticket was spent.  Remove it from the live
		// ticket bucket.
		case undo.Spent:
			err = ticketdb.DbDeleteTicket(dbTx, dbnamespace.LiveTicketsBucketName,
				&undo.TicketHash)
			if err != nil {
				return err
			}

		default:
			str := "unknown ticket state in undo data"
			return stakeRuleError(ErrMemoryCorruption, str)
		}
	}

	// Write the new block undo and new tickets data to the
	// database for the given height, potentially overwriting
	// an old entry with the new data.
	err := ticketdb.DbPutBlockUndoData(dbTx, node.height,
		node.databaseUndoUpdate)
	if err != nil {
		return err
	}

	err = ticketdb.DbPutNewTickets(dbTx, node.height,
		node.databaseBlockTickets)
	if err != nil {
		return err
	}

	// Write the new best state to the database.
	nextWinners := make([]chainhash.Hash, int(node.params.VotesPerBlock()))
	if node.height >= uint32(node.params.StakeValidationBeginHeight()-1) {
		for i := range nextWinners {
			nextWinners[i] = node.nextWinners[i]
		}
	}

	return ticketdb.DbPutBestState(dbTx, ticketdb.BestChainState{
		Hash:        hash,
		Height:      node.height,
		Live:        uint32(node.liveTickets.Len()),
		Missed:      uint64(node.missedTickets.Len()),
		Revoked:     uint64(node.revokedTickets.Len()),
		PerBlock:    node.params.VotesPerBlock(),
		NextWinners: nextWinners,
	})
}

// WriteDisconnectedBestNode writes the newly connected best node to the database
// under an atomic database transaction, performing all the necessary writes to
// reverse the contents of the database buckets for live, missed, and revoked
// tickets.  It does so by using the parent's block undo data to restore the
// original state in the database.  It also drops new ticket and reversion data
// for any nodes that have a height higher than this one after.
func WriteDisconnectedBestNode(dbTx database.Tx, node *Node, hash chainhash.Hash, childUndoData UndoTicketDataSlice) error {
	// Load the last best node and check to see if its height is above the
	// current node. If it is, drop all reversion data above this incoming
	// node.
	formerBest, err := ticketdb.DbFetchBestState(dbTx)
	if err != nil {
		return err
	}

	if formerBest.Height > node.height {
		for i := formerBest.Height; i > node.height; i-- {
			err := ticketdb.DbDropBlockUndoData(dbTx, i)
			if err != nil {
				return err
			}

			err = ticketdb.DbDropNewTickets(dbTx, i)
			if err != nil {
				return err
			}
		}
	}

	// Iterate through the block undo data and write all database changes to the
	// respective on-disk map, reversing all the changes added when the child
	// block was added to the block chain.
	//
	// Note that the undo data must be applied in reverse order since there may
	// be multiple changes for the same ticket.  For example, when the automatic
	// revocations agenda is enabled a ticket can become missed and revoked in the
	// same block.  This is recorded as two separate entries in the undo data and
	// must be processed in reverse order when disconnecting.
	for i := len(childUndoData) - 1; i >= 0; i-- {
		undo := childUndoData[i]
		var err error
		switch {
		// All flags are unset; this is a newly added ticket.
		// Remove it from the list of live tickets.
		case !undo.Missed && !undo.Revoked && !undo.Spent:
			err = ticketdb.DbDeleteTicket(dbTx, dbnamespace.LiveTicketsBucketName,
				&undo.TicketHash)
			if err != nil {
				return err
			}

		// The ticket was missed and revoked.  It needs to
		// be moved from the revoked ticket treap to the
		// missed ticket treap.
		case undo.Missed && undo.Revoked:
			err = ticketdb.DbDeleteTicket(dbTx,
				dbnamespace.RevokedTicketsBucketName,
				&undo.TicketHash)
			if err != nil {
				return err
			}
			err = ticketdb.DbPutTicket(dbTx, dbnamespace.MissedTicketsBucketName,
				&undo.TicketHash, undo.TicketHeight, undo.Missed, false,
				undo.Spent, undo.Expired)
			if err != nil {
				return err
			}

		// The ticket was missed and was previously live.
		// Remove it from the missed tickets bucket and
		// move it to the live tickets bucket.  We don't
		// know if it was expired or not, so just set that
		// flag to false.
		case undo.Missed && !undo.Revoked:
			err = ticketdb.DbDeleteTicket(dbTx,
				dbnamespace.MissedTicketsBucketName,
				&undo.TicketHash)
			if err != nil {
				return err
			}
			err = ticketdb.DbPutTicket(dbTx, dbnamespace.LiveTicketsBucketName,
				&undo.TicketHash, undo.TicketHeight, false, undo.Revoked,
				undo.Spent, false)
			if err != nil {
				return err
			}

		// The ticket was spent. Reinsert it into the live
		// tickets treap.
		case undo.Spent:
			err = ticketdb.DbPutTicket(dbTx, dbnamespace.LiveTicketsBucketName,
				&undo.TicketHash, undo.TicketHeight, undo.Missed, undo.Revoked,
				false, undo.Expired)
			if err != nil {
				return err
			}

		default:
			str := "unknown ticket state in undo data"
			return stakeRuleError(ErrMemoryCorruption, str)
		}
	}

	// Write the new block undo and new tickets data to the
	// database for the given height, potentially overwriting
	// an old entry with the new data.
	err = ticketdb.DbPutBlockUndoData(dbTx, node.height,
		node.databaseUndoUpdate)
	if err != nil {
		return err
	}

	err = ticketdb.DbPutNewTickets(dbTx, node.height,
		node.databaseBlockTickets)
	if err != nil {
		return err
	}

	// Write the new best state to the database.
	params := node.params
	nextWinners := make([]chainhash.Hash, int(params.VotesPerBlock()))
	if node.height >= uint32(params.StakeValidationBeginHeight()-1) {
		for i := range nextWinners {
			nextWinners[i] = node.nextWinners[i]
		}
	}

	return ticketdb.DbPutBestState(dbTx, ticketdb.BestChainState{
		Hash:        hash,
		Height:      node.height,
		Live:        uint32(node.liveTickets.Len()),
		Missed:      uint64(node.missedTickets.Len()),
		Revoked:     uint64(node.revokedTickets.Len()),
		PerBlock:    params.VotesPerBlock(),
		NextWinners: nextWinners,
	})
}