Merge pull request #41 from Bytom/dev

[bytom/vapor.git] / vendor / github.com / btcsuite / btcd / blockchain / difficulty.go

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

package blockchain

import (
        "math/big"
        "time"

        "github.com/btcsuite/btcd/chaincfg/chainhash"
)

var (
        // bigOne is 1 represented as a big.Int.  It is defined here to avoid
        // the overhead of creating it multiple times.
        bigOne = big.NewInt(1)

        // oneLsh256 is 1 shifted left 256 bits.  It is defined here to avoid
        // the overhead of creating it multiple times.
        oneLsh256 = new(big.Int).Lsh(bigOne, 256)
)

// HashToBig converts a chainhash.Hash into a big.Int that can be used to
// perform math comparisons.
func HashToBig(hash *chainhash.Hash) *big.Int {
        // A Hash is in little-endian, but the big package wants the bytes in
        // big-endian, so reverse them.
        buf := *hash
        blen := len(buf)
        for i := 0; i < blen/2; i++ {
                buf[i], buf[blen-1-i] = buf[blen-1-i], buf[i]
        }

        return new(big.Int).SetBytes(buf[:])
}

// CompactToBig converts a compact representation of a whole number N to an
// unsigned 32-bit number.  The representation is similar to IEEE754 floating
// point numbers.
//
// Like IEEE754 floating point, there are three basic components: the sign,
// the exponent, and the mantissa.  They are broken out as follows:
//
//      * the most significant 8 bits represent the unsigned base 256 exponent
//      * bit 23 (the 24th bit) represents the sign bit
//      * the least significant 23 bits represent the mantissa
//
//      -------------------------------------------------
//      |   Exponent     |    Sign    |    Mantissa     |
//      -------------------------------------------------
//      | 8 bits [31-24] | 1 bit [23] | 23 bits [22-00] |
//      -------------------------------------------------
//
// The formula to calculate N is:
//      N = (-1^sign) * mantissa * 256^(exponent-3)
//
// This compact form is only used in bitcoin to encode unsigned 256-bit numbers
// which represent difficulty targets, thus there really is not a need for a
// sign bit, but it is implemented here to stay consistent with bitcoind.
func CompactToBig(compact uint32) *big.Int {
        // Extract the mantissa, sign bit, and exponent.
        mantissa := compact & 0x007fffff
        isNegative := compact&0x00800000 != 0
        exponent := uint(compact >> 24)

        // Since the base for the exponent is 256, the exponent can be treated
        // as the number of bytes to represent the full 256-bit number.  So,
        // treat the exponent as the number of bytes and shift the mantissa
        // right or left accordingly.  This is equivalent to:
        // N = mantissa * 256^(exponent-3)
        var bn *big.Int
        if exponent <= 3 {
                mantissa >>= 8 * (3 - exponent)
                bn = big.NewInt(int64(mantissa))
        } else {
                bn = big.NewInt(int64(mantissa))
                bn.Lsh(bn, 8*(exponent-3))
        }

        // Make it negative if the sign bit is set.
        if isNegative {
                bn = bn.Neg(bn)
        }

        return bn
}

// BigToCompact converts a whole number N to a compact representation using
// an unsigned 32-bit number.  The compact representation only provides 23 bits
// of precision, so values larger than (2^23 - 1) only encode the most
// significant digits of the number.  See CompactToBig for details.
func BigToCompact(n *big.Int) uint32 {
        // No need to do any work if it's zero.
        if n.Sign() == 0 {
                return 0
        }

        // Since the base for the exponent is 256, the exponent can be treated
        // as the number of bytes.  So, shift the number right or left
        // accordingly.  This is equivalent to:
        // mantissa = mantissa / 256^(exponent-3)
        var mantissa uint32
        exponent := uint(len(n.Bytes()))
        if exponent <= 3 {
                mantissa = uint32(n.Bits()[0])
                mantissa <<= 8 * (3 - exponent)
        } else {
                // Use a copy to avoid modifying the caller's original number.
                tn := new(big.Int).Set(n)
                mantissa = uint32(tn.Rsh(tn, 8*(exponent-3)).Bits()[0])
        }

        // When the mantissa already has the sign bit set, the number is too
        // large to fit into the available 23-bits, so divide the number by 256
        // and increment the exponent accordingly.
        if mantissa&0x00800000 != 0 {
                mantissa >>= 8
                exponent++
        }

        // Pack the exponent, sign bit, and mantissa into an unsigned 32-bit
        // int and return it.
        compact := uint32(exponent<<24) | mantissa
        if n.Sign() < 0 {
                compact |= 0x00800000
        }
        return compact
}

// CalcWork calculates a work value from difficulty bits.  Bitcoin increases
// the difficulty for generating a block by decreasing the value which the
// generated hash must be less than.  This difficulty target is stored in each
// block header using a compact representation as described in the documentation
// for CompactToBig.  The main chain is selected by choosing the chain that has
// the most proof of work (highest difficulty).  Since a lower target difficulty
// value equates to higher actual difficulty, the work value which will be
// accumulated must be the inverse of the difficulty.  Also, in order to avoid
// potential division by zero and really small floating point numbers, the
// result adds 1 to the denominator and multiplies the numerator by 2^256.
func CalcWork(bits uint32) *big.Int {
        // Return a work value of zero if the passed difficulty bits represent
        // a negative number. Note this should not happen in practice with valid
        // blocks, but an invalid block could trigger it.
        difficultyNum := CompactToBig(bits)
        if difficultyNum.Sign() <= 0 {
                return big.NewInt(0)
        }

        // (1 << 256) / (difficultyNum + 1)
        denominator := new(big.Int).Add(difficultyNum, bigOne)
        return new(big.Int).Div(oneLsh256, denominator)
}

// calcEasiestDifficulty calculates the easiest possible difficulty that a block
// can have given starting difficulty bits and a duration.  It is mainly used to
// verify that claimed proof of work by a block is sane as compared to a
// known good checkpoint.
func (b *BlockChain) calcEasiestDifficulty(bits uint32, duration time.Duration) uint32 {
        // Convert types used in the calculations below.
        durationVal := int64(duration / time.Second)
        adjustmentFactor := big.NewInt(b.chainParams.RetargetAdjustmentFactor)

        // The test network rules allow minimum difficulty blocks after more
        // than twice the desired amount of time needed to generate a block has
        // elapsed.
        if b.chainParams.ReduceMinDifficulty {
                reductionTime := int64(b.chainParams.MinDiffReductionTime /
                        time.Second)
                if durationVal > reductionTime {
                        return b.chainParams.PowLimitBits
                }
        }

        // Since easier difficulty equates to higher numbers, the easiest
        // difficulty for a given duration is the largest value possible given
        // the number of retargets for the duration and starting difficulty
        // multiplied by the max adjustment factor.
        newTarget := CompactToBig(bits)
        for durationVal > 0 && newTarget.Cmp(b.chainParams.PowLimit) < 0 {
                newTarget.Mul(newTarget, adjustmentFactor)
                durationVal -= b.maxRetargetTimespan
        }

        // Limit new value to the proof of work limit.
        if newTarget.Cmp(b.chainParams.PowLimit) > 0 {
                newTarget.Set(b.chainParams.PowLimit)
        }

        return BigToCompact(newTarget)
}

// findPrevTestNetDifficulty returns the difficulty of the previous block which
// did not have the special testnet minimum difficulty rule applied.
//
// This function MUST be called with the chain state lock held (for writes).
func (b *BlockChain) findPrevTestNetDifficulty(startNode *blockNode) uint32 {
        // Search backwards through the chain for the last block without
        // the special rule applied.
        iterNode := startNode
        for iterNode != nil && iterNode.height%b.blocksPerRetarget != 0 &&
                iterNode.bits == b.chainParams.PowLimitBits {

                iterNode = iterNode.parent
        }

        // Return the found difficulty or the minimum difficulty if no
        // appropriate block was found.
        lastBits := b.chainParams.PowLimitBits
        if iterNode != nil {
                lastBits = iterNode.bits
        }
        return lastBits
}

// calcNextRequiredDifficulty calculates the required difficulty for the block
// after the passed previous block node based on the difficulty retarget rules.
// This function differs from the exported CalcNextRequiredDifficulty in that
// the exported version uses the current best chain as the previous block node
// while this function accepts any block node.
func (b *BlockChain) calcNextRequiredDifficulty(lastNode *blockNode, newBlockTime time.Time) (uint32, error) {
        // Genesis block.
        if lastNode == nil {
                return b.chainParams.PowLimitBits, nil
        }

        // Return the previous block's difficulty requirements if this block
        // is not at a difficulty retarget interval.
        if (lastNode.height+1)%b.blocksPerRetarget != 0 {
                // For networks that support it, allow special reduction of the
                // required difficulty once too much time has elapsed without
                // mining a block.
                if b.chainParams.ReduceMinDifficulty {
                        // Return minimum difficulty when more than the desired
                        // amount of time has elapsed without mining a block.
                        reductionTime := int64(b.chainParams.MinDiffReductionTime /
                                time.Second)
                        allowMinTime := lastNode.timestamp + reductionTime
                        if newBlockTime.Unix() > allowMinTime {
                                return b.chainParams.PowLimitBits, nil
                        }

                        // The block was mined within the desired timeframe, so
                        // return the difficulty for the last block which did
                        // not have the special minimum difficulty rule applied.
                        return b.findPrevTestNetDifficulty(lastNode), nil
                }

                // For the main network (or any unrecognized networks), simply
                // return the previous block's difficulty requirements.
                return lastNode.bits, nil
        }

        // Get the block node at the previous retarget (targetTimespan days
        // worth of blocks).
        firstNode := lastNode.RelativeAncestor(b.blocksPerRetarget - 1)
        if firstNode == nil {
                return 0, AssertError("unable to obtain previous retarget block")
        }

        // Limit the amount of adjustment that can occur to the previous
        // difficulty.
        actualTimespan := lastNode.timestamp - firstNode.timestamp
        adjustedTimespan := actualTimespan
        if actualTimespan < b.minRetargetTimespan {
                adjustedTimespan = b.minRetargetTimespan
        } else if actualTimespan > b.maxRetargetTimespan {
                adjustedTimespan = b.maxRetargetTimespan
        }

        // Calculate new target difficulty as:
        //  currentDifficulty * (adjustedTimespan / targetTimespan)
        // The result uses integer division which means it will be slightly
        // rounded down.  Bitcoind also uses integer division to calculate this
        // result.
        oldTarget := CompactToBig(lastNode.bits)
        newTarget := new(big.Int).Mul(oldTarget, big.NewInt(adjustedTimespan))
        targetTimeSpan := int64(b.chainParams.TargetTimespan / time.Second)
        newTarget.Div(newTarget, big.NewInt(targetTimeSpan))

        // Limit new value to the proof of work limit.
        if newTarget.Cmp(b.chainParams.PowLimit) > 0 {
                newTarget.Set(b.chainParams.PowLimit)
        }

        // Log new target difficulty and return it.  The new target logging is
        // intentionally converting the bits back to a number instead of using
        // newTarget since conversion to the compact representation loses
        // precision.
        newTargetBits := BigToCompact(newTarget)
        log.Debugf("Difficulty retarget at block height %d", lastNode.height+1)
        log.Debugf("Old target %08x (%064x)", lastNode.bits, oldTarget)
        log.Debugf("New target %08x (%064x)", newTargetBits, CompactToBig(newTargetBits))
        log.Debugf("Actual timespan %v, adjusted timespan %v, target timespan %v",
                time.Duration(actualTimespan)*time.Second,
                time.Duration(adjustedTimespan)*time.Second,
                b.chainParams.TargetTimespan)

        return newTargetBits, nil
}

// CalcNextRequiredDifficulty calculates the required difficulty for the block
// after the end of the current best chain based on the difficulty retarget
// rules.
//
// This function is safe for concurrent access.
func (b *BlockChain) CalcNextRequiredDifficulty(timestamp time.Time) (uint32, error) {
        b.chainLock.Lock()
        difficulty, err := b.calcNextRequiredDifficulty(b.bestChain.Tip(), timestamp)
        b.chainLock.Unlock()
        return difficulty, err
}