Rounding errors lead to incorrect result from CalcOrder

[wizeguyy]

Original report from Halborn in HAL-18, copied here for reference:

Description

It is well known that integers division rounds down when the division is not exact. As such, it is always recommended to do all operations (specially multiplications) before dividing to avoid losing precission. However, in the context of calculating the deltaS of a header and its associated position within hierarchies of chains, it accumulates multiple divisions before multiplication each losing precission of up to each layer thresholdS. Because of that, it is possible for a valid header to be on, say, a REGION but due to the loss of precission, when comparing against the intrinsic entropy of the header, the code may treat such a header as if it came from a lower layer, effectively invalidating it.

Proof of Concept

This flaw affects both implementations, blake3pow and progpow's function CalcOrder, as it implements the same logic.

When calculating the deltaS for a given layer, either PRIME, REGION or ZONE, the equations are (roughly) as follows:

deltaS = SUM(parentDeltaS in lower layers)
deltaS = deltaS + intrinsicS
deltaSTarget = entropyTarget(expansionNumber) / 2
deltaSTarget = deltaSTarget * thresholdS

The main point of precission loss is in the division by two if the returned entropy target is not divisible, so the error will increase depending on the thresholdS of the given layer, returning a value less than expected if done under floating point numbers. As such, those headers will fall to a lower layer even though they should be executed on a higher one, invalidating those headers.

https://github.com/dominant-strategies/go-quai/blob/814efb3eddd4086be6dffd557825f1c554536e35/consensus/blake3pow/poem.go#L35C1-L64C41

https://github.com/dominant-strategies/go-quai/blob/814efb3eddd4086be6dffd557825f1c554536e35/consensus/progpow/poem.go#L36C1-L65C41

// Get entropy reduction of this header
intrinsicS := progpow.IntrinsicLogS(powHash)
target := new(big.Int).Div(common.Big2e256, header.Difficulty())
zoneThresholdS := progpow.IntrinsicLogS(common.BytesToHash(target.Bytes()))

// PRIME
// PrimeEntropyThreshold number of zone blocks times the intrinsic logs of
// the given header determines the prime block
totalDeltaSPrime := new(big.Int).Add(header.ParentDeltaS(common.REGION_CTX), header.ParentDeltaS(common.ZONE_CTX))
totalDeltaSPrime = new(big.Int).Add(totalDeltaSPrime, intrinsicS)
primeDeltaSTarget := new(big.Int).Div(params.PrimeEntropyTarget(expansionNum), big2) <===== here
primeDeltaSTarget = new(big.Int).Mul(zoneThresholdS, primeDeltaSTarget)

primeBlockEntropyThreshold := new(big.Int).Add(zoneThresholdS, common.BitsToBigBits(params.PrimeEntropyTarget(expansionNum)))
if intrinsicS.Cmp(primeBlockEntropyThreshold) > 0 && totalDeltaSPrime.Cmp(primeDeltaSTarget) > 0 {
    return intrinsicS, common.PRIME_CTX, nil
}

// REGION
// Compute the total accumulated entropy since the last region block
totalDeltaSRegion := new(big.Int).Add(header.ParentDeltaS(common.ZONE_CTX), intrinsicS)
regionDeltaSTarget := new(big.Int).Div(params.RegionEntropyTarget(expansionNum), big2) <===== here
regionDeltaSTarget = new(big.Int).Mul(zoneThresholdS, regionDeltaSTarget)
regionBlockEntropyThreshold := new(big.Int).Add(zoneThresholdS, common.BitsToBigBits(params.RegionEntropyTarget(expansionNum)))
if intrinsicS.Cmp(regionBlockEntropyThreshold) > 0 && totalDeltaSRegion.Cmp(regionDeltaSTarget) > 0 {
    return intrinsicS, common.REGION_CTX, nil
}

// Zone case
return intrinsicS, common.ZONE_CTX, nil

[wizeguyy]

@gameofpointers can you link the PR?

[gameofpointers]

https://github.com/dominant-strategies/go-quai/pull/2355/commits/0c4571de4812fc4f117ad7ec13a0555efe47a6a9 this is the commit that went in https://github.com/dominant-strategies/go-quai/pull/2355 PR