[VerusCoin.git] / src / chain.cpp

// Copyright (c) 2009-2010 Satoshi Nakamoto
// Copyright (c) 2009-2014 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or https://www.opensource.org/licenses/mit-license.php .

#include "chain.h"

using namespace std;

/**
 * CChain implementation
 */
void CChain::SetTip(CBlockIndex *pindex) {
    lastTip = pindex;
    if (pindex == NULL) {
        vChain.clear();
        mmr.Truncate(0);
        return;
    }
    uint32_t modCount = 0;
    vChain.resize(pindex->GetHeight() + 1);
    while (pindex && vChain[pindex->GetHeight()] != pindex) {
        modCount++;
        vChain[pindex->GetHeight()] = pindex;
        pindex = pindex->pprev;
    }
    mmr.Truncate(vChain.size() - modCount);
    for (int i = (vChain.size() - modCount); i < vChain.size(); i++)
    {
        // add this block to the Merkle Mountain Range
        mmr.Add(vChain[i]->GetBlockMMRNode());
    }
}

// returns false if unable to fast calculate the VerusPOSHash from the header. 
// if it returns false, value is set to 0, but it can still be calculated from the full block
// in that case. the only difference between this and the POS hash for the contest is that it is not divided by the value out
// this is used as a source of entropy
bool CBlockIndex::GetRawVerusPOSHash(uint256 &ret) const
{
    // if below the required height or no storage space in the solution, we can't get
    // a cached txid value to calculate the POSHash from the header
    if (!(CPOSNonce::NewNonceActive(GetHeight()) && IsVerusPOSBlock()))
    {
        ret = uint256();
        return false;
    }

    // if we can calculate, this assumes the protocol that the POSHash calculation is:
    //    hashWriter << ASSETCHAINS_MAGIC;
    //    hashWriter << nNonce; (nNonce is:
    //                           (high 128 bits == low 128 bits of verus hash of low 128 bits of nonce)
    //                           (low 32 bits == compact PoS difficult)
    //                           (mid 96 bits == low 96 bits of HASH(pastHash, txid, voutnum)
    //                              pastHash is hash of height - 100, either PoW hash of block or PoS hash, if new PoS
    //                          )
    //    hashWriter << height;
    //    return hashWriter.GetHash();
    if (nVersion == CBlockHeader::VERUS_V2)
    {
        CVerusHashV2Writer hashWriter = CVerusHashV2Writer(SER_GETHASH, PROTOCOL_VERSION);

        hashWriter << ASSETCHAINS_MAGIC;
        hashWriter << nNonce;
        hashWriter << GetHeight();
        ret = hashWriter.GetHash();
    }
    else
    {
        CVerusHashWriter hashWriter = CVerusHashWriter(SER_GETHASH, PROTOCOL_VERSION);

        hashWriter << ASSETCHAINS_MAGIC;
        hashWriter << nNonce;
        hashWriter << GetHeight();
        ret = hashWriter.GetHash();
    }
    return true;
}

// depending on the height of the block and its type, this returns the POS hash or the POW hash
uint256 CBlockIndex::GetVerusEntropyHashComponent() const
{
    uint256 retVal;
    // if we qualify as PoW, use PoW hash, regardless of PoS state
    if (GetRawVerusPOSHash(retVal))
    {
        // POS hash
        return retVal;
    }
    return GetBlockHash();
}

// if pointers are passed for the int output values, two of them will indicate the height that provides one of two
// entropy values. the other will be -1. if pALTheight is not -1, its block type is the same as the other, which is
// not -1.
uint256 CChain::GetVerusEntropyHash(int forHeight, int *pPOSheight, int *pPOWheight, int *pALTheight) const
{
    uint256 retVal;
    int height = forHeight - 100;

    // we want the last value hashed to be a POW hash to make it difficult to predict at source tx creation, then we hash it with the
    // POS entropy. for old version, we just do what we used to and return the type of hash with the -100 height
    int _posh, _powh, _alth;
    int &posh = pPOSheight ? *pPOSheight : _posh;
    int &powh = pPOWheight ? *pPOWheight : _powh;
    int &alth = pALTheight ? *pALTheight : _alth;
    posh = powh = alth = -1;

    if (!(height >= 0 && height < vChain.size()))
    {
        LogPrintf("%s: invalid height for entropy hash %d, chain height is %d\n", __func__, height, vChain.size() - 1);
        return retVal;
    }
    if (CConstVerusSolutionVector::GetVersionByHeight(forHeight) < CActivationHeight::ACTIVATE_EXTENDEDSTAKE || height < 11)
    {
        if (vChain[height]->IsVerusPOSBlock())
        {
            posh = height;
        }
        else
        {
            powh = height;
        }
        return vChain[height]->GetVerusEntropyHashComponent();
    }

    int i;
    for (i = 0; i < 10; i++)
    {
        if (posh == -1 && vChain[height - i]->IsVerusPOSBlock())
        {
            posh = height - i;
        }
        else if (powh == -1)
        {
            powh = height - i;
        }
        if (posh != -1 && powh != -1)
        {
            break;
        }
    }

    // only one type of block found, set alt
    if (i == 10)
    {
        alth = height - i;
    }

    CVerusHashV2Writer hashWriter = CVerusHashV2Writer(SER_GETHASH, 0);
    if (posh != -1)
    {
        hashWriter << vChain[posh]->GetVerusEntropyHashComponent();
    }
    if (powh != -1)
    {
        hashWriter << vChain[powh]->GetVerusEntropyHashComponent();
    }
    if (alth != -1)
    {
        hashWriter << vChain[alth]->GetVerusEntropyHashComponent();
    }
    return hashWriter.GetHash();
}

CBlockLocator CChain::GetLocator(const CBlockIndex *pindex) const {
    int nStep = 1;
    std::vector<uint256> vHave;
    vHave.reserve(32);

    if (!pindex)
        pindex = Tip();
    while (pindex) {
        vHave.push_back(pindex->GetBlockHash());
        // Stop when we have added the genesis block.
        if (pindex->GetHeight() == 0)
            break;
        // Exponentially larger steps back, plus the genesis block.
        int nHeight = std::max(pindex->GetHeight() - nStep, 0);
        if (Contains(pindex)) {
            // Use O(1) CChain index if possible.
            pindex = (*this)[nHeight];
        } else {
            // Otherwise, use O(log n) skiplist.
            pindex = pindex->GetAncestor(nHeight);
        }
        if (vHave.size() > 10)
            nStep *= 2;
    }

    return CBlockLocator(vHave);
}

const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
    if ( pindex == 0 )
        return(0);
    if (pindex->GetHeight() > Height())
        pindex = pindex->GetAncestor(Height());
    while (pindex && !Contains(pindex))
        pindex = pindex->pprev;
    return pindex;
}

bool CChain::GetBlockProof(ChainMerkleMountainView &view, CMMRProof &retProof, int index) const
{
    CBlockIndex *pindex = (index < 0 || index >= (int)vChain.size()) ? NULL : vChain[index];
    if (pindex)
    {
        retProof << pindex->BlockProofBridge();
        return view.GetProof(retProof, index);
    }
    else
    {
        return false;
    }
}

bool CChain::GetMerkleProof(ChainMerkleMountainView &view, CMMRProof &retProof, int index) const
{
    CBlockIndex *pindex = (index < 0 || index >= (int)vChain.size()) ? NULL : vChain[index];
    if (pindex)
    {
        retProof << pindex->MMRProofBridge();
        return view.GetProof(retProof, index);
    }
    else
    {
        return false;
    }
}

uint256 CChainPower::CompactChainPower() const
{
    arith_uint256 compactPower = (chainStake << 128) + chainWork;
    return ArithToUint256(compactPower);
}

CChainPower::CChainPower(CBlockIndex *pblockIndex)
{
     nHeight = pblockIndex->GetHeight();
     chainStake = arith_uint256(0);
     chainWork = arith_uint256(0);
}

CChainPower::CChainPower(CBlockIndex *pblockIndex, const arith_uint256 &stake, const arith_uint256 &work)
{
     nHeight = pblockIndex->GetHeight();
     chainStake = stake;
     chainWork = work;
}

bool operator==(const CChainPower &p1, const CChainPower &p2)
{
    arith_uint256 bigZero = arith_uint256(0);
    arith_uint256 workDivisor = p1.chainWork > p2.chainWork ? p1.chainWork : (p2.chainWork != bigZero ? p2.chainWork : 1);
    arith_uint256 stakeDivisor = p1.chainStake > p2.chainStake ? p1.chainStake : (p2.chainStake != bigZero ? p2.chainStake : 1);

    // use up 16 bits for precision
    return ((p1.chainWork << 16) / workDivisor + (p1.chainStake << 16) / stakeDivisor) ==
            ((p2.chainWork << 16) / workDivisor + (p2.chainStake << 16) / stakeDivisor);
}

bool operator<(const CChainPower &p1, const CChainPower &p2)
{
    arith_uint256 bigZero = arith_uint256(0);
    arith_uint256 workDivisor = p1.chainWork > p2.chainWork ? p1.chainWork : (p2.chainWork != bigZero ? p2.chainWork : 1);
    arith_uint256 stakeDivisor = p1.chainStake > p2.chainStake ? p1.chainStake : (p2.chainStake != bigZero ? p2.chainStake : 1);

    // use up 16 bits for precision
    return ((p1.chainWork << 16) / workDivisor + (p1.chainStake << 16) / stakeDivisor) <
            ((p2.chainWork << 16) / workDivisor + (p2.chainStake << 16) / stakeDivisor);
}

bool operator<=(const CChainPower &p1, const CChainPower &p2)
{
    arith_uint256 bigZero = arith_uint256(0);
    arith_uint256 workDivisor = p1.chainWork > p2.chainWork ? p1.chainWork : (p2.chainWork != bigZero ? p2.chainWork : 1);
    arith_uint256 stakeDivisor = p1.chainStake > p2.chainStake ? p1.chainStake : (p2.chainStake != bigZero ? p2.chainStake : 1);

    // use up 16 bits for precision
    return ((p1.chainWork << 16) / workDivisor + (p1.chainStake << 16) / stakeDivisor) <=
            ((p2.chainWork << 16) / workDivisor + (p2.chainStake << 16) / stakeDivisor);
}

CChainPower CChainPower::ExpandCompactPower(uint256 compactPower, uint32_t height)
{
    return CChainPower(height, UintToArith256(compactPower) >> 128, (UintToArith256(compactPower) << 128) >> 128);
}

/** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
int static inline InvertLowestOne(int n) { return n & (n - 1); }

/** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
int static inline GetSkipHeight(int height) {
    if (height < 2)
        return 0;

    // Determine which height to jump back to. Any number strictly lower than height is acceptable,
    // but the following expression seems to perform well in simulations (max 110 steps to go back
    // up to 2**18 blocks).
    return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
}

CBlockIndex* CBlockIndex::GetAncestor(int height)
{
    if (height > GetHeight() || height < 0)
        return NULL;

    CBlockIndex* pindexWalk = this;
    int heightWalk = GetHeight();
    while ( heightWalk > height && pindexWalk != 0 )
    {
        int heightSkip = GetSkipHeight(heightWalk);
        int heightSkipPrev = GetSkipHeight(heightWalk - 1);
        if (pindexWalk->pskip != NULL &&
            (heightSkip == height ||
             (heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
                                       heightSkipPrev >= height)))) {
            // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
            pindexWalk = pindexWalk->pskip;
            heightWalk = heightSkip;
        } else {
            assert(pindexWalk->pprev);
            pindexWalk = pindexWalk->pprev;
            heightWalk--;
        }
    }
    return pindexWalk;
}

const CBlockIndex* CBlockIndex::GetAncestor(int height) const
{
    return const_cast<CBlockIndex*>(this)->GetAncestor(height);
}

void CBlockIndex::BuildSkip()
{
    if (pprev)
    {
        //printf("building skip - current:\n%s\nprev:\n%s\n", ToString().c_str(), pprev->ToString().c_str());
        pskip = pprev->GetAncestor(GetSkipHeight(GetHeight()));
    }
}
Commit	Line	Data
e8b5f0d5	1	// Copyright (c) 2009-2010 Satoshi Nakamoto
f914f1a7	2	// Copyright (c) 2009-2014 The Bitcoin Core developers
7bec6dd2	3	// Distributed under the MIT software license, see the accompanying
bc909a7a	4	// file COPYING or https://www.opensource.org/licenses/mit-license.php .
e8b5f0d5	5
	6	#include "chain.h"
	7
	8	using namespace std;
	9
2fdc3351 MF	10	/**
	11	* CChain implementation
	12	*/
b7ae2c17	13	void CChain::SetTip(CBlockIndex *pindex) {
37ad6886	14	lastTip = pindex;
e8b5f0d5	15	if (pindex == NULL) {
e8b5f0d5	16	vChain.clear();
b2a98c42	17	mmr.Truncate(0);
b7ae2c17	18	return;
e8b5f0d5	19	}
b2a98c42	20	uint32_t modCount = 0;
4b729ec5	21	vChain.resize(pindex->GetHeight() + 1);
4b729ec5	22	while (pindex && vChain[pindex->GetHeight()] != pindex) {
b2a98c42	23	modCount++;
4b729ec5	24	vChain[pindex->GetHeight()] = pindex;
e8b5f0d5	25	pindex = pindex->pprev;
e8b5f0d5	26	}
b2a98c42 MT	27	mmr.Truncate(vChain.size() - modCount);
	28	for (int i = (vChain.size() - modCount); i < vChain.size(); i++)
	29	{
	30	// add this block to the Merkle Mountain Range
56fe75cb	31	mmr.Add(vChain[i]->GetBlockMMRNode());
b2a98c42 MT	32	}
	33	}
	34
	35	// returns false if unable to fast calculate the VerusPOSHash from the header.
	36	// if it returns false, value is set to 0, but it can still be calculated from the full block
	37	// in that case. the only difference between this and the POS hash for the contest is that it is not divided by the value out
	38	// this is used as a source of entropy
	39	bool CBlockIndex::GetRawVerusPOSHash(uint256 &ret) const
	40	{
	41	// if below the required height or no storage space in the solution, we can't get
	42	// a cached txid value to calculate the POSHash from the header
	43	if (!(CPOSNonce::NewNonceActive(GetHeight()) && IsVerusPOSBlock()))
	44	{
	45	ret = uint256();
	46	return false;
	47	}
	48
	49	// if we can calculate, this assumes the protocol that the POSHash calculation is:
	50	// hashWriter << ASSETCHAINS_MAGIC;
	51	// hashWriter << nNonce; (nNonce is:
	52	// (high 128 bits == low 128 bits of verus hash of low 128 bits of nonce)
	53	// (low 32 bits == compact PoS difficult)
	54	// (mid 96 bits == low 96 bits of HASH(pastHash, txid, voutnum)
	55	// pastHash is hash of height - 100, either PoW hash of block or PoS hash, if new PoS
	56	// )
	57	// hashWriter << height;
	58	// return hashWriter.GetHash();
	59	if (nVersion == CBlockHeader::VERUS_V2)
	60	{
	61	CVerusHashV2Writer hashWriter = CVerusHashV2Writer(SER_GETHASH, PROTOCOL_VERSION);
	62
	63	hashWriter << ASSETCHAINS_MAGIC;
	64	hashWriter << nNonce;
	65	hashWriter << GetHeight();
	66	ret = hashWriter.GetHash();
	67	}
	68	else
	69	{
	70	CVerusHashWriter hashWriter = CVerusHashWriter(SER_GETHASH, PROTOCOL_VERSION);
	71
	72	hashWriter << ASSETCHAINS_MAGIC;
	73	hashWriter << nNonce;
	74	hashWriter << GetHeight();
	75	ret = hashWriter.GetHash();
	76	}
	77	return true;
	78	}
	79
	80	// depending on the height of the block and its type, this returns the POS hash or the POW hash
56fe75cb	81	uint256 CBlockIndex::GetVerusEntropyHashComponent() const
b2a98c42 MT	82	{
	83	uint256 retVal;
	84	// if we qualify as PoW, use PoW hash, regardless of PoS state
	85	if (GetRawVerusPOSHash(retVal))
	86	{
	87	// POS hash
	88	return retVal;
	89	}
	90	return GetBlockHash();
e8b5f0d5	91	}
e8b5f0d5	92
56fe75cb	93	// if pointers are passed for the int output values, two of them will indicate the height that provides one of two
	94	// entropy values. the other will be -1. if pALTheight is not -1, its block type is the same as the other, which is
	95	// not -1.
	96	uint256 CChain::GetVerusEntropyHash(int forHeight, int pPOSheight, int pPOWheight, int *pALTheight) const
	97	{
	98	uint256 retVal;
	99	int height = forHeight - 100;
	100
	101	// we want the last value hashed to be a POW hash to make it difficult to predict at source tx creation, then we hash it with the
	102	// POS entropy. for old version, we just do what we used to and return the type of hash with the -100 height
	103	int _posh, _powh, _alth;
	104	int &posh = pPOSheight ? *pPOSheight : _posh;
	105	int &powh = pPOWheight ? *pPOWheight : _powh;
	106	int &alth = pALTheight ? *pALTheight : _alth;
	107	posh = powh = alth = -1;
	108
	109	if (!(height >= 0 && height < vChain.size()))
	110	{
	111	LogPrintf("%s: invalid height for entropy hash %d, chain height is %d\n", __func__, height, vChain.size() - 1);
	112	return retVal;
	113	}
6e7fb01d	114	if (CConstVerusSolutionVector::GetVersionByHeight(forHeight) < CActivationHeight::ACTIVATE_EXTENDEDSTAKE \|\| height < 11)
56fe75cb	115	{
	116	if (vChain[height]->IsVerusPOSBlock())
	117	{
	118	posh = height;
	119	}
	120	else
	121	{
	122	powh = height;
	123	}
	124	return vChain[height]->GetVerusEntropyHashComponent();
	125	}
	126
af521e42	127	int i;
af521e42	128	for (i = 0; i < 10; i++)
56fe75cb	129	{
	130	if (posh == -1 && vChain[height - i]->IsVerusPOSBlock())
	131	{
	132	posh = height - i;
	133	}
	134	else if (powh == -1)
	135	{
	136	powh = height - i;
	137	}
5fd488ca	138	if (posh != -1 && powh != -1)
	139	{
	140	break;
	141	}
56fe75cb	142	}
7695dab4	143
5fd488ca	144	// only one type of block found, set alt
af521e42	145	if (i == 10)
	146	{
	147	alth = height - i;
	148	}
56fe75cb	149
	150	CVerusHashV2Writer hashWriter = CVerusHashV2Writer(SER_GETHASH, 0);
	151	if (posh != -1)
	152	{
	153	hashWriter << vChain[posh]->GetVerusEntropyHashComponent();
	154	}
	155	if (powh != -1)
	156	{
	157	hashWriter << vChain[powh]->GetVerusEntropyHashComponent();
	158	}
	159	if (alth != -1)
	160	{
	161	hashWriter << vChain[alth]->GetVerusEntropyHashComponent();
	162	}
	163	return hashWriter.GetHash();
	164	}
	165
e8b5f0d5	166	CBlockLocator CChain::GetLocator(const CBlockIndex *pindex) const {
	167	int nStep = 1;
	168	std::vector<uint256> vHave;
	169	vHave.reserve(32);
	170
	171	if (!pindex)
	172	pindex = Tip();
	173	while (pindex) {
	174	vHave.push_back(pindex->GetBlockHash());
	175	// Stop when we have added the genesis block.
4b729ec5	176	if (pindex->GetHeight() == 0)
e8b5f0d5	177	break;
e8b5f0d5	178	// Exponentially larger steps back, plus the genesis block.
4b729ec5	179	int nHeight = std::max(pindex->GetHeight() - nStep, 0);
e8b5f0d5	180	if (Contains(pindex)) {
	181	// Use O(1) CChain index if possible.
	182	pindex = (*this)[nHeight];
	183	} else {
	184	// Otherwise, use O(log n) skiplist.
	185	pindex = pindex->GetAncestor(nHeight);
	186	}
	187	if (vHave.size() > 10)
	188	nStep *= 2;
	189	}
	190
	191	return CBlockLocator(vHave);
	192	}
	193
	194	const CBlockIndex CChain::FindFork(const CBlockIndex pindex) const {
df473cc2	195	if ( pindex == 0 )
df473cc2	196	return(0);
4b729ec5	197	if (pindex->GetHeight() > Height())
e8b5f0d5	198	pindex = pindex->GetAncestor(Height());
	199	while (pindex && !Contains(pindex))
	200	pindex = pindex->pprev;
	201	return pindex;
	202	}
5ea3bc06	203
e8b83707	204	bool CChain::GetBlockProof(ChainMerkleMountainView &view, CMMRProof &retProof, int index) const
	205	{
	206	CBlockIndex *pindex = (index < 0 \|\| index >= (int)vChain.size()) ? NULL : vChain[index];
	207	if (pindex)
	208	{
	209	retProof << pindex->BlockProofBridge();
	210	return view.GetProof(retProof, index);
	211	}
	212	else
	213	{
	214	return false;
	215	}
	216	}
	217
	218	bool CChain::GetMerkleProof(ChainMerkleMountainView &view, CMMRProof &retProof, int index) const
	219	{
	220	CBlockIndex *pindex = (index < 0 \|\| index >= (int)vChain.size()) ? NULL : vChain[index];
	221	if (pindex)
	222	{
	223	retProof << pindex->MMRProofBridge();
	224	return view.GetProof(retProof, index);
	225	}
	226	else
	227	{
	228	return false;
	229	}
	230	}
	231
c8c684e9	232	uint256 CChainPower::CompactChainPower() const
	233	{
	234	arith_uint256 compactPower = (chainStake << 128) + chainWork;
	235	return ArithToUint256(compactPower);
	236	}
	237
4b729ec5	238	CChainPower::CChainPower(CBlockIndex *pblockIndex)
	239	{
	240	nHeight = pblockIndex->GetHeight();
	241	chainStake = arith_uint256(0);
	242	chainWork = arith_uint256(0);
	243	}
	244
	245	CChainPower::CChainPower(CBlockIndex *pblockIndex, const arith_uint256 &stake, const arith_uint256 &work)
	246	{
	247	nHeight = pblockIndex->GetHeight();
	248	chainStake = stake;
	249	chainWork = work;
	250	}
	251
	252	bool operator==(const CChainPower &p1, const CChainPower &p2)
	253	{
	254	arith_uint256 bigZero = arith_uint256(0);
	255	arith_uint256 workDivisor = p1.chainWork > p2.chainWork ? p1.chainWork : (p2.chainWork != bigZero ? p2.chainWork : 1);
	256	arith_uint256 stakeDivisor = p1.chainStake > p2.chainStake ? p1.chainStake : (p2.chainStake != bigZero ? p2.chainStake : 1);
	257
	258	// use up 16 bits for precision
	259	return ((p1.chainWork << 16) / workDivisor + (p1.chainStake << 16) / stakeDivisor) ==
	260	((p2.chainWork << 16) / workDivisor + (p2.chainStake << 16) / stakeDivisor);
	261	}
	262
	263	bool operator<(const CChainPower &p1, const CChainPower &p2)
	264	{
	265	arith_uint256 bigZero = arith_uint256(0);
	266	arith_uint256 workDivisor = p1.chainWork > p2.chainWork ? p1.chainWork : (p2.chainWork != bigZero ? p2.chainWork : 1);
	267	arith_uint256 stakeDivisor = p1.chainStake > p2.chainStake ? p1.chainStake : (p2.chainStake != bigZero ? p2.chainStake : 1);
	268
	269	// use up 16 bits for precision
	270	return ((p1.chainWork << 16) / workDivisor + (p1.chainStake << 16) / stakeDivisor) <
	271	((p2.chainWork << 16) / workDivisor + (p2.chainStake << 16) / stakeDivisor);
	272	}
	273
	274	bool operator<=(const CChainPower &p1, const CChainPower &p2)
	275	{
	276	arith_uint256 bigZero = arith_uint256(0);
	277	arith_uint256 workDivisor = p1.chainWork > p2.chainWork ? p1.chainWork : (p2.chainWork != bigZero ? p2.chainWork : 1);
	278	arith_uint256 stakeDivisor = p1.chainStake > p2.chainStake ? p1.chainStake : (p2.chainStake != bigZero ? p2.chainStake : 1);
	279
	280	// use up 16 bits for precision
	281	return ((p1.chainWork << 16) / workDivisor + (p1.chainStake << 16) / stakeDivisor) <=
	282	((p2.chainWork << 16) / workDivisor + (p2.chainStake << 16) / stakeDivisor);
	283	}
	284
c8c684e9	285	CChainPower CChainPower::ExpandCompactPower(uint256 compactPower, uint32_t height)
b2a98c42 MT	286	{
	287	return CChainPower(height, UintToArith256(compactPower) >> 128, (UintToArith256(compactPower) << 128) >> 128);
	288	}
4b729ec5	289
5ea3bc06 PW	290	/** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
	291	int static inline InvertLowestOne(int n) { return n & (n - 1); }
	292
	293	/** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
	294	int static inline GetSkipHeight(int height) {
	295	if (height < 2)
	296	return 0;
	297
	298	// Determine which height to jump back to. Any number strictly lower than height is acceptable,
	299	// but the following expression seems to perform well in simulations (max 110 steps to go back
	300	// up to 2**18 blocks).
	301	return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
	302	}
	303
	304	CBlockIndex* CBlockIndex::GetAncestor(int height)
	305	{
4b729ec5	306	if (height > GetHeight() \|\| height < 0)
5ea3bc06 PW	307	return NULL;
	308
	309	CBlockIndex* pindexWalk = this;
4b729ec5	310	int heightWalk = GetHeight();
5298d41f	311	while ( heightWalk > height && pindexWalk != 0 )
5298d41f	312	{
5ea3bc06 PW	313	int heightSkip = GetSkipHeight(heightWalk);
5ea3bc06 PW	314	int heightSkipPrev = GetSkipHeight(heightWalk - 1);
bfa832c7 PW	315	if (pindexWalk->pskip != NULL &&
	316	(heightSkip == height \|\|
	317	(heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
	318	heightSkipPrev >= height)))) {
5ea3bc06 PW	319	// Only follow pskip if pprev->pskip isn't better than pskip->pprev.
	320	pindexWalk = pindexWalk->pskip;
	321	heightWalk = heightSkip;
	322	} else {
7b1acda3	323	assert(pindexWalk->pprev);
5ea3bc06 PW	324	pindexWalk = pindexWalk->pprev;
	325	heightWalk--;
	326	}
	327	}
	328	return pindexWalk;
	329	}
	330
	331	const CBlockIndex* CBlockIndex::GetAncestor(int height) const
	332	{
	333	return const_cast<CBlockIndex*>(this)->GetAncestor(height);
	334	}
	335
	336	void CBlockIndex::BuildSkip()
	337	{
	338	if (pprev)
08d46b7f	339	{
1403a5da	340	//printf("building skip - current:\n%s\nprev:\n%s\n", ToString().c_str(), pprev->ToString().c_str());
4b729ec5	341	pskip = pprev->GetAncestor(GetSkipHeight(GetHeight()));
08d46b7f	342	}
5ea3bc06	343	}