-
-
owned this note
-
Published
Linked with GitHub
# Faster Ethash check against difficulty
## Check against boundary using integer division
Ethereum [Yellow Paper](https://ethereum.github.io/yellowpaper/paper.pdf) in section 11.5 defines PoW difficulty check as
$$
n \leq \frac{2^{256}}{H_d}
$$
where $n$ is Ethash final hash and $H_d$ is current block difficulty.
The $\frac{2^{256}}{H_d}$ is called _boundary_. In practical implementations integer division is used to validate the check.
$$
n \leq \left\lfloor\frac{2^{256}}{H_d}\right\rfloor
$$
This is correct because of the following fact ([proof](https://proofwiki.org/wiki/Number_not_less_than_Integer_iff_Floor_not_less_than_Integer)):
$$
x \in \mathbb{R}, n \in \mathbb{Z}: n \leq x \iff n \leq \left\lfloor x \right\rfloor
$$
## Check against difficulty using multiplication
We can avoid using big integer division (which is slow and complex to implement) by transforming the orignal check formula into:
$$
nH_d \leq 2^{256}
$$
### Benefits
1. Integer division has been replaced with multiplication. The 256 x 256 -> 512 multiplication is straight forward to implement.
2. Degenerated values of difficulty ($0$ and $1$) do not require special handling.
### Implementation
This has been implemented in [ethash 0.8.0](https://github.com/chfast/ethash/releases/tag/v0.8.0).
## Side notes
1. The check $nH_d \leq 2^{256}$ can be further decomposed into $nH_d \lt 2^{256} \lor nH_d = 2^{256}$ where the first part is 256-bit multiplication overflow check and the second part is very unlikely (or even impossible considering the difficulty update formula).
2. The difficulty values on Ethereum Mainnet safely stay within 64-bit boundaries. Therefore, optimized path can be used for such values for both integer division and multiplication.