Author Topic: Difficulty Algorithms  (Read 7488 times)

0 Members and 1 Guest are viewing this topic.

Offline barwizi

  • Hero Member
  • *****
  • Posts: 764
  • Noirbits, NoirShares, NoirEx.....lol, noir anyone?
    • View Profile
    • Noirbitstalk.org
Re: Difficulty Algorithms
« Reply #8 on: November 18, 2013, 05:29:35 am »
It appears that we have an average of 2 minute blocks now.   Much better than 30 seconds :)

I think a lot of miners dropped off after the latest difficulty increase.    Those cloud computers get rather expensive at this difficulty level.

Except that ypool still has over 40k workers right now, which is basically what it has had the entire time. So either people still are using HUUUUUUUUUUGE cloud farms or we are still getting raped by botnets.

as you know Protoshares is just the beginning, and after seeing the huge amount of interest it garnered (unexpectedly) i think invictus will let this one run for a while, then implement all the fixes in the next chain.
--Bar--  PiNEJGUv4AZVZkLuF6hV4xwbYTRp5etWWJ

The magical land of crypto, no freebies people.

Offline m0rph

  • Jr. Member
  • **
  • Posts: 33
    • View Profile
Re: Difficulty Algorithms
« Reply #7 on: November 17, 2013, 08:11:51 pm »
It appears that we have an average of 2 minute blocks now.   Much better than 30 seconds :)

I think a lot of miners dropped off after the latest difficulty increase.    Those cloud computers get rather expensive at this difficulty level.

Except that ypool still has over 40k workers right now, which is basically what it has had the entire time. So either people still are using HUUUUUUUUUUGE cloud farms or we are still getting raped by botnets.
PTS - PksM7k6rwZpWGvR1GxSedLZ5k94z54bbqH
BTC - 1CFxbpkBmZGB5RStsCz6Wgbw48GRQyfsFF

Offline bytemaster

Re: Difficulty Algorithms
« Reply #6 on: November 17, 2013, 08:13:23 am »
It appears that we have an average of 2 minute blocks now.   Much better than 30 seconds :)

I think a lot of miners dropped off after the latest difficulty increase.    Those cloud computers get rather expensive at this difficulty level.   
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline barwizi

  • Hero Member
  • *****
  • Posts: 764
  • Noirbits, NoirShares, NoirEx.....lol, noir anyone?
    • View Profile
    • Noirbitstalk.org
Re: Difficulty Algorithms
« Reply #5 on: November 17, 2013, 07:20:51 am »
ah, we once tried a hash based calculation but gave it up as a bad job. At new_block , we'd find that reported hash rates where all conflicting causing massive forking. We decided to do this in short:-

if a block is targeted @ 5 minutes, that means 12 blocks an hour. to compensate for hash swings and lucky breaks we can consider a two hour period. this means adjustment every 24 blocks (this can be even 4 hour periods), going up twice quickly as it goes down. It inconveniences cloud and bot operators due to the quick re-adjustments, benefiting small loyal miners who only feel the brunt when a bot tries to jump in. Otherwise returns will be normal across the board.

We could try hashrate based implementation but if you consider how there are many complaints about clients and latency, it would be prudent to use a metric that has less room for error.



--Bar--  PiNEJGUv4AZVZkLuF6hV4xwbYTRp5etWWJ

The magical land of crypto, no freebies people.

Offline bytemaster

Re: Difficulty Algorithms
« Reply #4 on: November 17, 2013, 07:05:42 am »
https://github.com/InvictusInnovations/BitShares/blob/master/src/blockchain/blockchain_time_keeper.cpp

Code: [Select]
  /**
   *  This is a utility class designed to coordinate
   *  blockchain timestamps and difficulty using
   *  a sliding window.
   * 
   *  Given a set of timestamps and corresponding
   *  proof of work hashes, this class will calculate
   *  the proof of work required for the next
   *  block as well as the minimum allowable
   *  time for the next block.
   *
   *  The difficulty will be adjusted so that the
   *  expected time of finding the next block will
   *  cause the time series to re-sync with the
   *  desired time interval.
   */

With this class I can calculate time and interval while preventing drift.   Ie:  If block 1000 is supposed to happen in 1 year, it will happen in 1 year regardless of short term time drifting caused by increasing or decreasing of hash power in the network.   I need to update it to use hash values rather than difficulty values but other than that it seems to work very well at keeping the timestamps for various blocks within 12 hours of the expected time according to my simulations.

For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline barwizi

  • Hero Member
  • *****
  • Posts: 764
  • Noirbits, NoirShares, NoirEx.....lol, noir anyone?
    • View Profile
    • Noirbitstalk.org
Re: Difficulty Algorithms
« Reply #3 on: November 17, 2013, 07:00:43 am »
Can you summarize your algorithm so I don't have to reverse engineer the code?

ok, gimme a few minutes, need some coffee
--Bar--  PiNEJGUv4AZVZkLuF6hV4xwbYTRp5etWWJ

The magical land of crypto, no freebies people.

Offline bytemaster

Re: Difficulty Algorithms
« Reply #2 on: November 17, 2013, 06:57:12 am »
Can you summarize your algorithm so I don't have to reverse engineer the code?
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline barwizi

  • Hero Member
  • *****
  • Posts: 764
  • Noirbits, NoirShares, NoirEx.....lol, noir anyone?
    • View Profile
    • Noirbitstalk.org
Difficulty Algorithms
« Reply #1 on: November 17, 2013, 06:43:01 am »
First and foremost i'd like to start by suggesting that the difficulty part of the code be seperated into it's own file....eg difficulty.cpp.

This would be the first step in creating an easy to adjust difficulty system as you can just write one, test it and then "plug" it in by replacing the current version. See NRB (MY COPY PASTE COIN) for how that works.

this is the one we use there

it can be edited to meet the requirements of any and all coins that use the bitcoin codebase.

Code: [Select]
#include <vector>
#include "diff.h"

const struct SRetargetParams* CMainNetDiff::sRules = new SRetargetParams(3600, 120);
const struct SRetargetParams* COldNetDiff::sRules = new SRetargetParams(7200, 120);

const CBigNum CDiffProvider::bnProofOfWorkLimit(~uint256(0) >> 20);

CDiff* CDiffProvider::pnewDiff = NULL;
CDiff* CDiffProvider::pdynDiff = NULL;
CDiff* CDiffProvider::poldDiff = NULL;
CDiff* CDiffProvider::ptestDiff = NULL;

double CDiff::GetDifficulty(const CBlockIndex* blockindex = NULL)
{
// Floating point number that is a multiple of the minimum difficulty,
// minimum difficulty = 1.0.
if (blockindex == NULL)
{
if (pindexBest == NULL)
return 1.0;
else
blockindex = pindexBest;
}

return GetDifficultyFromTargetBits(blockindex->nBits);
}

struct TargetSpan
{
double difficulty;
double hashes;
int time;
};

static int CalculateHashrate(CBlockIndex* first, CBlockIndex* last)
{
double timeDiff = last->GetBlockTime() - first->GetBlockTime();
double timePerBlock = timeDiff / (last->nHeight - first->nHeight);

return (int) (CDiff::GetDifficultyFromTargetBits(last->nBits) * pow(2.0, 32) / timePerBlock);
}

json_spirit::Value CDiff::GetNetworkHashPS(int lookup)
{
if (pindexBest == NULL)
        return 0;

// If lookup is -1, then use blocks since last difficulty change.
if (lookup <= 0)
{
int nInterval = this->GetRules()->nInterval;
lookup = pindexBest->nHeight % nInterval + 1;
}

// If lookup is larger than chain, then set it to chain length.
if (lookup > pindexBest->nHeight)
lookup = pindexBest->nHeight;

CBlockIndex* pindexPrev = pindexBest;
CBlockIndex* plastRetarget = pindexBest;
std::vector<TargetSpan> spans;

for (int i = 0; i < lookup; i++)
{
pindexPrev = pindexPrev->pprev;

if (pindexPrev->nBits != plastRetarget->nBits || i + 1 == lookup)
{
TargetSpan span;
span.difficulty = CDiff::GetDifficultyFromTargetBits(plastRetarget->nBits);
span.time = plastRetarget->GetBlockTime() - pindexPrev->GetBlockTime();
span.hashes = span.difficulty * pow(2.0, 32) * (plastRetarget->nHeight - pindexPrev->nHeight);

spans.push_back(span);
plastRetarget = pindexPrev;
}
}

double hashes = 0;
int totalTime = 0;
for (std::vector<TargetSpan>::iterator it = spans.begin(); it != spans.end(); ++it)
{
hashes += (*it).hashes;
totalTime += (*it).time;
}

return (boost::int64_t)(hashes / totalTime);
}

bool COldNetDiff::ShouldApplyRetarget(const CBlockIndex* pindexLast, const CBlock* pblock)
{
bool bShouldRetarget = false;

// We have reached retarget height
bShouldRetarget |= (pindexLast->nHeight + 1) % sRules->nInterval == 0;

return bShouldRetarget;
}

int64 COldNetDiff::GetActualTimespan(const CBlockIndex* pindexFirst, const CBlockIndex* pindexLast)
{
int64 nActualTimespan = 0;
int64 nActualTimespanMax = 0;
int64 nActualTimespanMin = 0;

if (pindexLast->nHeight > COINFIX1_BLOCK)
{
// obtain average actual timespan
nActualTimespan = (pindexLast->GetBlockTime() - pindexFirst->GetBlockTime()) / nRetargetHistoryFact;
}
else
{
nActualTimespan = pindexLast->GetBlockTime() - pindexFirst->GetBlockTime();
}

nActualTimespanMin = sRules->nTargetTimespan / 4;
nActualTimespanMax = sRules->nTargetTimespan * 4;

printf("  nActualTimespan = %"PRI64d"  before bounds\n", nActualTimespan);

if (nActualTimespan > nActualTimespanMax) nActualTimespan = nActualTimespanMax;
if (nActualTimespan < nActualTimespanMin) nActualTimespan = nActualTimespanMin;

return nActualTimespan;
}

const CBlockIndex* COldNetDiff::GetFirstBlock(const CBlockIndex* pindexLast)
{
const CBlockIndex* pindexFirst = pindexLast;
for (int i = 0; pindexFirst && i < GetBlocksToGoBack(pindexLast); i++)
{
pindexFirst = pindexFirst->pprev;
}

assert(pindexFirst);

return pindexFirst;
}

int COldNetDiff::GetBlocksToGoBack(const CBlockIndex* pindexLast)
{
// Fixes an issue where a 51% attack can change difficulty at will.
// Go back the full period unless it's the first retarget after genesis. Code courtesy of Art Forz
int nBlocksToGoBack = sRules->nInterval - 1;

if ((pindexLast->nHeight + 1) != sRules->nInterval)
{
nBlocksToGoBack = sRules->nInterval;
}

if (pindexLast->nHeight > COINFIX1_BLOCK)
{
nBlocksToGoBack = nRetargetHistoryFact * sRules->nInterval;
}

return nBlocksToGoBack;
}

//
// minimum amount of work that could possibly be required nTime after
// minimum work required was nBase
//
unsigned int COldNetDiff::ComputeMinWork(unsigned int nBase, int64 nTime)
{
CBigNum bnResult;
bnResult.SetCompact(nBase);

while (nTime > 0 && bnResult < bnProofOfWorkLimit)
{
bnResult *= 4;
nTime -= sRules->nTargetTimespan * 4;
}

if (bnResult > bnProofOfWorkLimit)
bnResult = bnProofOfWorkLimit;

printf("COldDiff -- ComputeMinWork requested\n");
printf("nTargetTimespan = %"PRI64d"\n", sRules->nTargetTimespan);
printf("bnResult:  %08x  %s\n", bnResult.GetCompact(), bnResult.getuint256().ToString().c_str());

return bnResult.GetCompact();
}

unsigned int COldNetDiff::GetNextWorkRequired(const CBlockIndex* pindexLast, const CBlock* pblock)
{
// Genesis block
if (pindexLast == NULL)
return nProofOfWorkLimit;

bool bretarget = ShouldApplyRetarget(pindexLast, pblock);

// Check if we should retarget diff.
if (!bretarget)
{
return pindexLast->nBits;
}

// Limit adjustment step
int64 nActualTimespan = GetActualTimespan(GetFirstBlock(pindexLast), pindexLast);

// Retarget
CBigNum bnNew;
bnNew.SetCompact(pindexLast->nBits);
bnNew *= nActualTimespan;
bnNew /= sRules->nTargetTimespan;

if (bnNew > bnProofOfWorkLimit)
bnNew = bnProofOfWorkLimit;

// Debug print
printf("COldDiff -- GetNextWorkRequired RETARGET\n");
printf("nTargetTimespan = %"PRI64d"    nActualTimespan = %"PRI64d"\n", sRules->nTargetTimespan, nActualTimespan);
printf("Before: %08x  %s\n", pindexLast->nBits, CBigNum().SetCompact(pindexLast->nBits).getuint256().ToString().c_str());
printf("After:  %08x  %s\n", bnNew.GetCompact(), bnNew.getuint256().ToString().c_str());

return bnNew.GetCompact();
}

const SRetargetParams* COldNetDiff::GetRules()
{
return sRules;
}

bool CMainNetDiff::ShouldApplyRetarget(const CBlockIndex* pindexLast, const CBlock* pblock)
{
bool bShouldRetarget = false;

// We have exceeded max. time for current difficulty, change (hard limit)
bShouldRetarget |= (pindexLast->nTime + nMaxTimeInterval) < pblock->nTime;
// We have reached retarget height
bShouldRetarget |= (pindexLast->nHeight + 1) % sRules->nInterval == 0;

return bShouldRetarget;
}

int64 CMainNetDiff::GetActualTimespan(const CBlockIndex* pindexFirst, const CBlockIndex* pindexLast)
{
int64 nActualTimespan = 0;
int64 nActualTimespanMax = 0;
int64 nActualTimespanMin = 0;

nActualTimespan = pindexLast->GetBlockTime() - pindexFirst->GetBlockTime();

// FeatherCoin's cap system.
// For diff. increase
nActualTimespanMin = (nActualTimespan * 55) / 99;
// For diff. decrease
nActualTimespanMax = (nActualTimespan * 99) / 55;

printf("  nActualTimespan = %"PRI64d"  before bounds\n", nActualTimespan);

if (nActualTimespan > nActualTimespanMax) nActualTimespan = nActualTimespanMax;
if (nActualTimespan < nActualTimespanMin) nActualTimespan = nActualTimespanMin;

return nActualTimespan;
}

const CBlockIndex* CMainNetDiff::GetFirstBlock(const CBlockIndex* pindexLast)
{
const CBlockIndex* pindexFirst = pindexLast;
for (int i = 0; pindexFirst && i < GetBlocksToGoBack(pindexLast); i++)
{
pindexFirst = pindexFirst->pprev;
}

assert(pindexFirst);

return pindexFirst;
}

int CMainNetDiff::GetBlocksToGoBack(const CBlockIndex* pindexLast)
{
// Fixes an issue where a 51% attack can change difficulty at will.
// Go back the full period unless it's the first retarget after genesis. Code courtesy of Art Forz
int nBlocksToGoBack = sRules->nInterval - 1;

if ((pindexLast->nHeight + 1) != sRules->nInterval)
{
nBlocksToGoBack = sRules->nInterval;
}

return nBlocksToGoBack;
}

//
// minimum amount of work that could possibly be required nTime after
// minimum work required was nBase
//
unsigned int CMainNetDiff::ComputeMinWork(unsigned int nBase, int64 nTime)
{
CBigNum bnResult;
bnResult.SetCompact(nBase);

while (nTime > 0 && bnResult < bnProofOfWorkLimit)
{
bnResult *= 4;
nTime -= sRules->nTargetTimespan * 4;
}

if (bnResult > bnProofOfWorkLimit)
bnResult = bnProofOfWorkLimit;

printf("CMainNetDiff -- ComputeMinWork requested\n");
printf("nTargetTimespan = %"PRI64d"\n", sRules->nTargetTimespan);
printf("bnResult:  %08x  %s\n", bnResult.GetCompact(), bnResult.getuint256().ToString().c_str());

return bnResult.GetCompact();
}

unsigned int CMainNetDiff::GetNextWorkRequired(const CBlockIndex* pindexLast, const CBlock* pblock)
{
// Genesis block
if (pindexLast == NULL)
return nProofOfWorkLimit;

// Check if we should retarget diff.
if (!ShouldApplyRetarget(pindexLast, pblock))
{
return pindexLast->nBits;
}

// Limit adjustment step
int64 nActualTimespan = GetActualTimespan(GetFirstBlock(pindexLast), pindexLast);

// Retarget
CBigNum bnNew;
bnNew.SetCompact(pindexLast->nBits);
bnNew *= nActualTimespan;
bnNew /= sRules->nTargetTimespan;

if (bnNew > bnProofOfWorkLimit)
bnNew = bnProofOfWorkLimit;

/// debug print
printf("CMainNetDiff -- GetNextWorkRequired RETARGET\n");
printf("nTargetTimespan = %"PRI64d"    nActualTimespan = %"PRI64d"\n", sRules->nTargetTimespan, nActualTimespan);
printf("Before: %08x  %s\n", pindexLast->nBits, CBigNum().SetCompact(pindexLast->nBits).getuint256().ToString().c_str());
printf("After:  %08x  %s\n", bnNew.GetCompact(), bnNew.getuint256().ToString().c_str());

return bnNew.GetCompact();
}

const SRetargetParams* CMainNetDiff::GetRules()
{
return sRules;
}

// DYNAMIC DIFF

int64 CDynamicDiff::GetActualTimespan(const CBlockIndex* pindexFirst, const CBlockIndex* pindexLast)
{
int64 nActualTimespan = 0;
int64 nActualTimespanMax = 0;
int64 nActualTimespanMin = 0;

if (false && GetAdjustedTime() - pindexLast->GetBlockTime() > CMainNetDiff::sRules->nTargetTimespan * 10)
{
nActualTimespan = GetAdjustedTime() - pindexFirst->GetBlockTime();
}
else
{
nActualTimespan = pindexLast->GetBlockTime() - pindexFirst->GetBlockTime();
}

// FeatherCoin's cap system.
// For diff. increase
nActualTimespanMin = (nActualTimespan * 55) / 99;
// For diff. decrease
nActualTimespanMax = (nActualTimespan * 99) / 55;

printf("  nActualTimespan = %"PRI64d"  before bounds\n", nActualTimespan);

if (nActualTimespan > nActualTimespanMax) nActualTimespan = nActualTimespanMax;
if (nActualTimespan < nActualTimespanMin) nActualTimespan = nActualTimespanMin;

return nActualTimespan;
}

bool CDynamicDiff::ShouldApplyRetarget(const CBlockIndex* pindexLast, const CBlock* pblock)
{
const CBlockIndex* pindexFirst = pindexLast;

if (false && GetAdjustedTime() - pindexLast->GetBlockTime() > CMainNetDiff::sRules->nTargetTimespan * 5)
return true;

int64 nLookup = CMainNetDiff::sRules->nInterval * 4;
int i = 0;
    for (i = 0; i < nLookup && pindexFirst->pprev != NULL; i++)
{
pindexFirst = pindexFirst->pprev;
}

    double meanTime = (pindexLast->nTime - pindexFirst->nTime) / i;
    double targetTime = CMainNetDiff::sRules->nTargetSpacing;
    double squaredDiffs = 0;

    pindexFirst = pindexLast;
    for (i = 0; i < nLookup && pindexFirst->pprev != NULL; i++)
    {
        squaredDiffs += pow((meanTime - (pindexFirst->nTime - pindexFirst->pprev->nTime)), 2);
        pindexFirst = pindexFirst->pprev;
    }

    double maxDeviation = 2 * sqrt(squaredDiffs / i);

    return (meanTime > targetTime + maxDeviation || meanTime < targetTime - maxDeviation);
}

//
// minimum amount of work that could possibly be required nTime after
// minimum work required was nBase
//
unsigned int CTestNetDiff::ComputeMinWork(unsigned int nBase, int64 nTime)
{
// Testnet has min-difficulty blocks
// after nTargetSpacing*2 time between blocks:
if (nTime > pparentRules->GetRules()->nTargetSpacing * 2)
return bnProofOfWorkLimit.GetCompact();

return pparentRules->ComputeMinWork(nBase, nTime);
}

unsigned int CTestNetDiff::GetNextWorkRequired(const CBlockIndex* pindexLast, const CBlock* pblock)
{
if (!pparentRules->ShouldApplyRetarget(pindexLast, pblock))
{
return GetTestNetNextTarget(pindexLast, pblock);
}

return pparentRules->GetNextWorkRequired(pindexLast, pblock);
}

unsigned int CTestNetDiff::GetTestNetNextTarget(const CBlockIndex* pindexLast, const CBlock* pblock)
{
const SRetargetParams* rules = pparentRules->GetRules();
// If the new block's timestamp is more than 2* 10 minutes
// then allow mining of a min-difficulty block.
if (pblock->nTime > pindexLast->nTime + rules->nTargetSpacing * 2)
{
return nProofOfWorkLimit;
}
else
{
// Return the last non-special-min-difficulty-rules-block
const CBlockIndex* pindex = pindexLast;
while (pindex->pprev && pindex->nHeight % rules->nInterval != 0 && pindex->nBits == nProofOfWorkLimit)
{
pindex = pindex->pprev;
}
return pindex->nBits;
}
}

const SRetargetParams* CTestNetDiff::GetRules()
{
return pparentRules->GetRules();
}

bool CTestNetDiff::ShouldApplyRetarget(const CBlockIndex* pindexLast, const CBlock* pblock)
{
return pparentRules->ShouldApplyRetarget(pindexLast, pblock);
}

it was written by a guy on BTT and has proven to be adaquately responsive to changes in hash power, it became necessary to use this after the advent of multi-pools that would throw insane hash power in a small period of time and raise the difficulty , then leave and await coinchoose/coinwarz again.
« Last Edit: November 17, 2013, 06:59:59 am by barwizi »
--Bar--  PiNEJGUv4AZVZkLuF6hV4xwbYTRp5etWWJ

The magical land of crypto, no freebies people.