blockchain, integration, mining, main: Rolling merkle root calculation

[kcalvinalvin]

I saw #1421 and noticed that it was slower than the current function for calculating merkle roots. Just looking to see if the direction I took here is ok.

I replaced everything in rolling_merkle.go with Utreexo structs/functions. The comments and struct names should probably change. FWIW, the main function add is using the same algorithm as the one found in blake3 hash.

Here's the benchstat results. It's about the same/slightly faster than the current merkle root function and allocates even less memory than the function in #1421. The added code is a lot smaller as well.

[I] calvin@bitcoin ~/b/g/u/g/s/g/b/b/blockchain (merkle-calc-fast)> benchstat merkle.txt rolling_merkle.txt
goos: linux
goarch: amd64
pkg: github.com/btcsuite/btcd/blockchain
cpu: AMD Ryzen 5 3600 6-Core Processor              
                │  merkle.txt  │         rolling_merkle.txt          │
                │    sec/op    │    sec/op     vs base               │
Merkle/1000-10    539.0µ ±  2%   542.6µ ±  6%       ~ (p=0.165 n=10)
Merkle/2000-10    1.081m ±  1%   1.078m ±  1%       ~ (p=0.436 n=10)
Merkle/4000-10    2.189m ± 29%   2.180m ±  2%       ~ (p=0.315 n=10)
Merkle/8000-10    4.410m ±  6%   4.352m ±  1%       ~ (p=0.105 n=10)
Merkle/16000-10   8.764m ±  2%   8.859m ± 34%       ~ (p=0.247 n=10)
Merkle/32000-10   17.60m ±  5%   17.29m ±  2%  -1.78% (p=0.007 n=10)
geomean           3.088m         3.078m        -0.34%

                │   merkle.txt   │         rolling_merkle.txt         │
                │      B/op      │    B/op     vs base                │
Merkle/1000-10      48416.0 ± 0%   320.0 ± 0%  -99.34% (p=0.000 n=10)
Merkle/2000-10      96800.0 ± 0%   352.0 ± 0%  -99.64% (p=0.000 n=10)
Merkle/4000-10     193568.0 ± 0%   384.0 ± 0%  -99.80% (p=0.000 n=10)
Merkle/8000-10     387104.0 ± 0%   416.0 ± 0%  -99.89% (p=0.000 n=10)
Merkle/16000-10    774176.0 ± 0%   448.0 ± 0%  -99.94% (p=0.000 n=10)
Merkle/32000-10   1548320.0 ± 0%   480.0 ± 0%  -99.97% (p=0.000 n=10)
geomean             267.3Ki        396.2       -99.86%

                │   merkle.txt   │         rolling_merkle.txt          │
                │   allocs/op    │ allocs/op   vs base                 │
Merkle/1000-10     1002.000 ± 0%   1.000 ± 0%   -99.90% (p=0.000 n=10)
Merkle/2000-10     2002.000 ± 0%   1.000 ± 0%   -99.95% (p=0.000 n=10)
Merkle/4000-10     4002.000 ± 0%   1.000 ± 0%   -99.98% (p=0.000 n=10)
Merkle/8000-10     8002.000 ± 0%   1.000 ± 0%   -99.99% (p=0.000 n=10)
Merkle/16000-10   16002.000 ± 0%   1.000 ± 0%   -99.99% (p=0.000 n=10)
Merkle/32000-10   32002.000 ± 0%   1.000 ± 0%  -100.00% (p=0.000 n=10)
geomean              5.661k        1.000        -99.98%

[coveralls]

Pull Request Test Coverage Report for Build 5612329239

• 87 of 132 (65.91%) changed or added relevant lines in 6 files are covered.
• 9 unchanged lines in 2 files lost coverage.
• Overall coverage increased (+0.02%) to 55.258%

---

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
blockchain/merkle.go	4	5	80.0%
rpcserver.go	0	2	0.0%
blockchain/rolling_merkle.go	81	88	92.05%
mining/mining.go	0	35	0.0%
<!--	Total:	87	132	65.91%	-->

Files with Coverage Reduction	New Missed Lines	%
mining/mining.go	2	8.08%
blockchain/merkle.go	7	31.34%
<!--	Total:	9		-->

Totals
Change from base Build 5525483102:	0.02%
Covered Lines:	26767
Relevant Lines:	48440

---

💛 - Coveralls

[kcalvinalvin]

There was still some Utreexo specific stuff that made it calculate wrong roots. I fixed it in the latest force push.

Still the same results from the benchmarks so the benchstat results are valid.

EDIT: Later push was for witness merkle root calculation.

[Roasbeef]

Concept ACK, great work building on the other optimization with some of the utreexo derived fine tuning!

[kcalvinalvin]

Ready for reviews now!

@Roasbeef

[kcalvinalvin]

I do think there are certain API changes that are necessary for the RMTS to be broadly useful, rather that solely tailored to the block tree verification process.

I strongly disagree making this function more broadly useful as the merkle tree function used for calculating the tx commitment is flawed and has a vulnerability (CVE-2012-2459). It's possible to create a collision using duplicate leaves and it's described in detail at: https://github.com/bitcoin/bitcoin/blob/79e8247ddb166f9b980f40249b7372a502402a4d/src/consensus/merkle.cpp#L8-L41

If anyone wants to use the following code for merkle tree stuff, they should just use https://github.com/utreexo/utreexo as it's essentially the same.

[Roasbeef]

Completed sync tests on mainnet+testnet as a final sanity check!