Page MenuHomePhabricator
Differential D11150

Add MuHash3072 implementation
ClosedPublic
Actions

Authored by PiRK on Mar 9 2022, 16:54.

Details

Reviewers
Fabien
Group Reviewers
Restricted Project
Commits
rABC465584c0e51b: Add MuHash3072 implementation
Summary

General context (see core#18000):

This is a step in the way of implementing an index of coin statistics with the goal of making the response time of the gettxoutsetinfo RPC call dramatically faster. Currently, this RPC is scanning the full UTXO set every time it is called which makes it hard to use for users that want to continually check the coin supply or compare UTXO set hashes between different nodes. It is especially challenging in periods of multiple quickly mined blocks, even relatively fast machines.

build: Check for 128 bit integer support

https://github.com/bitcoin/bitcoin/pull/19145/commits/2474645f3b15687e7f196b89eb935d6e6a98a9da

crypto: Add Num3072 implementation

Num3072 is a specialized bignum implementation used in MuHash3072.

https://github.com/bitcoin/bitcoin/pull/19055/commits/0b4d290bf5b0a4d156c523431bf89aaa9ffe92e5

crypto: Add MuHash3072 implementation

https://github.com/bitcoin/bitcoin/pull/19055/commits/adc708c98dbf03b1735edc91f813a36580781a95

test: Add MuHash3072 unit tests

https://github.com/bitcoin/bitcoin/pull/19055/commits/7b1242229d1fcc9277238a3aefb3431061c82bfa

test: Change MuHash Python implementation to match cpp version again

https://github.com/bitcoin/bitcoin/pull/19055/commits/9815332d5158d69a94abeaf465a2c07bd8e43359

Co-authored-by: Pieter Wuille <pieter.wuille@gmail.com>
Co-authored-by: Anthony Towns <aj@erisian.com.au>

This is a partial backport of core#19055

Test Plan

ninja check check-functional

Diff Detail

Event Timeline

PiRK created this revision.Mar 9 2022, 16:54
Herald added a reviewer: Restricted Project. · View Herald TranscriptMar 9 2022, 16:54
teamcity edited the summary of this revision. (Show Details)Mar 9 2022, 16:54
Harbormaster completed remote builds in B18438: Diff 32642.Mar 9 2022, 16:55
teamcity added a comment.Mar 9 2022, 16:55
Build Bitcoin ABC Diffs / Diff Testing (build-clang) failed.

Tail of the build log:

Build 'Bitcoin ABC Diffs / Diff Testing' #43683, branch 'refs/tags/phabricator/diff/32642'
Triggered 2022-03-09 16:54:54 by 'Phabricator Staging (phabricator-staging)'
Started 2022-03-09 16:54:59 on agent 'buildagent1'
Finished 2022-03-09 16:55:03 with status FAILURE 'Snapshot dependency failed to start: Automated Deployments / Bitcoin ABC Infra / Bitcoin-ABC Infra Checkout'
VCS revisions: 'PhabBitcoinAbcStagingRo' (Git, instance id 18): 'N/A' (checkout rules: '+:. => ./bitcoin-abc')
TeamCity URL https://build.bitcoinabc.org/viewLog.html?buildId=364269&buildTypeId=BitcoinABC_BitcoinAbcStaging 
TeamCity server version is 2019.2.4 (build 72059), server timezone: GMT (UTC)

[16:54:54]E: bt15 (running for 9s)
[16:54:54]i: TeamCity server version is 2019.2.4 (build 72059)
[16:54:54] : Collecting changes in 2 VCS roots
[16:54:54] :	 [Collecting changes in 2 VCS roots] VCS Root details
[16:54:54] :		 [VCS Root details] "phab-bitcoin-abc-staging-ro" {instance id=18, parent internal id=14, parent id=PhabBitcoinAbcStagingRo, description: "https://reviews.bitcoinabc.org/source/bitcoin-abc-staging.git#refs/heads/master"}
[16:54:54] :		 [VCS Root details] "abc-infrastructure" {instance id=7, parent internal id=7, parent id=AutomatedDeployments_BitcoinAbcDeveloperTools_AbcInfrastructure, description: "ssh://vcs@reviews.bitcoinabc.org:2221/source/infrastructure.git#refs/heads/master"}
[16:54:59] : The build is removed from the queue to be prepared for the start
[16:55:03]W: This build has not been started because some of the builds it depends on failed to start
[16:55:03]E: Snapshot dependency "Automated Deployments / Bitcoin ABC Infra / Bitcoin-ABC Infra Checkout" failed
[16:55:03] : Build finished
teamcity added a comment.Mar 9 2022, 16:55
Build Bitcoin ABC Diffs / Diff Testing (lint-circular-dependencies) failed.

Tail of the build log:

Build 'Bitcoin ABC Diffs / Diff Testing' #43684, branch 'refs/tags/phabricator/diff/32642'
Triggered 2022-03-09 16:54:54 by 'Phabricator Staging (phabricator-staging)'
Started 2022-03-09 16:55:28 on agent 'buildagent1'
Finished 2022-03-09 16:55:33 with status FAILURE 'Snapshot dependency failed to start: Automated Deployments / Bitcoin ABC Infra / Bitcoin-ABC Infra Checkout'
VCS revisions: 'PhabBitcoinAbcStagingRo' (Git, instance id 18): 'N/A' (checkout rules: '+:. => ./bitcoin-abc')
TeamCity URL https://build.bitcoinabc.org/viewLog.html?buildId=364279&buildTypeId=BitcoinABC_BitcoinAbcStaging 
TeamCity server version is 2019.2.4 (build 72059), server timezone: GMT (UTC)

[16:54:55]E: bt15 (running for 38s)
[16:54:55]i: TeamCity server version is 2019.2.4 (build 72059)
[16:54:55] : Collecting changes in 2 VCS roots (31s)
[16:54:55] :	 [Collecting changes in 2 VCS roots] VCS Root details
[16:54:55] :		 [VCS Root details] "phab-bitcoin-abc-staging-ro" {instance id=18, parent internal id=14, parent id=PhabBitcoinAbcStagingRo, description: "https://reviews.bitcoinabc.org/source/bitcoin-abc-staging.git#refs/heads/master"}
[16:54:55] :		 [VCS Root details] "abc-infrastructure" {instance id=7, parent internal id=7, parent id=AutomatedDeployments_BitcoinAbcDeveloperTools_AbcInfrastructure, description: "ssh://vcs@reviews.bitcoinabc.org:2221/source/infrastructure.git#refs/heads/master"}
[16:54:55]i:	 [Collecting changes in 2 VCS roots] Loading current repository state for VCS root 'phab-bitcoin-abc-staging-ro' (31s)
[16:55:28] : The build is removed from the queue to be prepared for the start
[16:55:33]W: This build has not been started because some of the builds it depends on failed to start
[16:55:33]E: Snapshot dependency "Automated Deployments / Bitcoin ABC Infra / Bitcoin-ABC Infra Checkout" failed
[16:55:33] : Build finished
teamcity added a comment.Mar 9 2022, 16:55
Build Bitcoin ABC Diffs / Diff Testing (build-without-wallet) failed.

Tail of the build log:

Build 'Bitcoin ABC Diffs / Diff Testing' #43687, branch 'refs/tags/phabricator/diff/32642'
Triggered 2022-03-09 16:54:54 by 'Phabricator Staging (phabricator-staging)'
Started 2022-03-09 16:55:32 on agent 'buildagent4'
Finished 2022-03-09 16:55:38 with status FAILURE 'Snapshot dependency failed to start: Automated Deployments / Bitcoin ABC Infra / Bitcoin-ABC Infra Checkout'
VCS revisions: 'PhabBitcoinAbcStagingRo' (Git, instance id 18): 'N/A' (checkout rules: '+:. => ./bitcoin-abc')
TeamCity URL https://build.bitcoinabc.org/viewLog.html?buildId=364277&buildTypeId=BitcoinABC_BitcoinAbcStaging 
TeamCity server version is 2019.2.4 (build 72059), server timezone: GMT (UTC)

[16:54:54]E: bt15 (running for 43s)
[16:54:54]i: TeamCity server version is 2019.2.4 (build 72059)
[16:54:54] : Collecting changes in 2 VCS roots (35s)
[16:54:54] :	 [Collecting changes in 2 VCS roots] VCS Root details
[16:54:54] :		 [VCS Root details] "phab-bitcoin-abc-staging-ro" {instance id=18, parent internal id=14, parent id=PhabBitcoinAbcStagingRo, description: "https://reviews.bitcoinabc.org/source/bitcoin-abc-staging.git#refs/heads/master"}
[16:54:54] :		 [VCS Root details] "abc-infrastructure" {instance id=7, parent internal id=7, parent id=AutomatedDeployments_BitcoinAbcDeveloperTools_AbcInfrastructure, description: "ssh://vcs@reviews.bitcoinabc.org:2221/source/infrastructure.git#refs/heads/master"}
[16:55:32] : The build is removed from the queue to be prepared for the start
[16:55:38]W: This build has not been started because some of the builds it depends on failed to start
[16:55:38]E: Snapshot dependency "Automated Deployments / Bitcoin ABC Infra / Bitcoin-ABC Infra Checkout" failed
[16:55:38] : Build finished
PiRK updated this revision to Diff 32644.Mar 9 2022, 17:25

fix definition of HAVE___INT128. Move the type detection code to config/CMakLists.txt and export the variable in bitcoin-config.h.cmake.in

Harbormaster completed remote builds in B18440: Diff 32644.Mar 9 2022, 17:26
teamcity added a comment.Mar 9 2022, 17:26
Build Bitcoin ABC Diffs / Diff Testing (build-clang) failed.

Tail of the build log:

Build 'Bitcoin ABC Diffs / Diff Testing' #43690, branch 'refs/tags/phabricator/diff/32644'
Triggered 2022-03-09 17:26:03 by 'Phabricator Staging (phabricator-staging)'
Started 2022-03-09 17:26:05 on agent 'buildagent1'
Finished 2022-03-09 17:26:10 with status FAILURE 'Snapshot dependency failed to start: Automated Deployments / Bitcoin ABC Infra / Bitcoin-ABC Infra Checkout'
VCS revisions: 'PhabBitcoinAbcStagingRo' (Git, instance id 18): 'N/A' (checkout rules: '+:. => ./bitcoin-abc')
TeamCity URL https://build.bitcoinabc.org/viewLog.html?buildId=364283&buildTypeId=BitcoinABC_BitcoinAbcStaging 
TeamCity server version is 2019.2.4 (build 72059), server timezone: GMT (UTC)

[17:26:03]E: bt15 (running for 6s)
[17:26:03]i: TeamCity server version is 2019.2.4 (build 72059)
[17:26:03] : Collecting changes in 2 VCS roots
[17:26:03] :	 [Collecting changes in 2 VCS roots] VCS Root details
[17:26:03] :		 [VCS Root details] "phab-bitcoin-abc-staging-ro" {instance id=18, parent internal id=14, parent id=PhabBitcoinAbcStagingRo, description: "https://reviews.bitcoinabc.org/source/bitcoin-abc-staging.git#refs/heads/master"}
[17:26:03] :		 [VCS Root details] "abc-infrastructure" {instance id=7, parent internal id=7, parent id=AutomatedDeployments_BitcoinAbcDeveloperTools_AbcInfrastructure, description: "ssh://vcs@reviews.bitcoinabc.org:2221/source/infrastructure.git#refs/heads/master"}
[17:26:05] : The build is removed from the queue to be prepared for the start
[17:26:10]W: This build has not been started because some of the builds it depends on failed to start
[17:26:10]E: Snapshot dependency "Automated Deployments / Bitcoin ABC Infra / Bitcoin-ABC Infra Checkout" failed
[17:26:10] : Build finished
teamcity added a comment.Mar 9 2022, 17:26
Build Bitcoin ABC Diffs / Diff Testing (lint-circular-dependencies) failed.

Tail of the build log:

Build 'Bitcoin ABC Diffs / Diff Testing' #43691, branch 'refs/tags/phabricator/diff/32644'
Triggered 2022-03-09 17:26:04 by 'Phabricator Staging (phabricator-staging)'
Started 2022-03-09 17:26:13 on agent 'buildagent1'
Finished 2022-03-09 17:26:17 with status FAILURE 'Snapshot dependency failed to start: Automated Deployments / Bitcoin ABC Infra / Bitcoin-ABC Infra Checkout'
VCS revisions: 'PhabBitcoinAbcStagingRo' (Git, instance id 18): 'N/A' (checkout rules: '+:. => ./bitcoin-abc')
TeamCity URL https://build.bitcoinabc.org/viewLog.html?buildId=364293&buildTypeId=BitcoinABC_BitcoinAbcStaging 
TeamCity server version is 2019.2.4 (build 72059), server timezone: GMT (UTC)

[17:26:04]E: bt15 (running for 13s)
[17:26:04]i: TeamCity server version is 2019.2.4 (build 72059)
[17:26:04] : Collecting changes in 2 VCS roots (7s)
[17:26:04] :	 [Collecting changes in 2 VCS roots] VCS Root details
[17:26:04] :		 [VCS Root details] "phab-bitcoin-abc-staging-ro" {instance id=18, parent internal id=14, parent id=PhabBitcoinAbcStagingRo, description: "https://reviews.bitcoinabc.org/source/bitcoin-abc-staging.git#refs/heads/master"}
[17:26:04] :		 [VCS Root details] "abc-infrastructure" {instance id=7, parent internal id=7, parent id=AutomatedDeployments_BitcoinAbcDeveloperTools_AbcInfrastructure, description: "ssh://vcs@reviews.bitcoinabc.org:2221/source/infrastructure.git#refs/heads/master"}
[17:26:13] : The build is removed from the queue to be prepared for the start
[17:26:17]W: This build has not been started because some of the builds it depends on failed to start
[17:26:17]E: Snapshot dependency "Automated Deployments / Bitcoin ABC Infra / Bitcoin-ABC Infra Checkout" failed
[17:26:17] : Build finished
teamcity added a comment.Mar 9 2022, 17:26
Build Bitcoin ABC Diffs / Diff Testing (build-clang-tidy) failed.

Tail of the build log:

Build 'Bitcoin ABC Diffs / Diff Testing' #43692, branch 'refs/tags/phabricator/diff/32644'
Triggered 2022-03-09 17:26:03 by 'Phabricator Staging (phabricator-staging)'
Started 2022-03-09 17:26:22 on agent 'buildagent1'
Finished 2022-03-09 17:26:26 with status FAILURE 'Snapshot dependency failed to start: Automated Deployments / Bitcoin ABC Infra / Bitcoin-ABC Infra Checkout'
VCS revisions: 'PhabBitcoinAbcStagingRo' (Git, instance id 18): 'N/A' (checkout rules: '+:. => ./bitcoin-abc')
TeamCity URL https://build.bitcoinabc.org/viewLog.html?buildId=364285&buildTypeId=BitcoinABC_BitcoinAbcStaging 
TeamCity server version is 2019.2.4 (build 72059), server timezone: GMT (UTC)

[17:26:03]E: bt15 (running for 22s)
[17:26:03]i: TeamCity server version is 2019.2.4 (build 72059)
[17:26:03] : Collecting changes in 2 VCS roots (15s)
[17:26:03] :	 [Collecting changes in 2 VCS roots] VCS Root details
[17:26:03] :		 [VCS Root details] "phab-bitcoin-abc-staging-ro" {instance id=18, parent internal id=14, parent id=PhabBitcoinAbcStagingRo, description: "https://reviews.bitcoinabc.org/source/bitcoin-abc-staging.git#refs/heads/master"}
[17:26:03] :		 [VCS Root details] "abc-infrastructure" {instance id=7, parent internal id=7, parent id=AutomatedDeployments_BitcoinAbcDeveloperTools_AbcInfrastructure, description: "ssh://vcs@reviews.bitcoinabc.org:2221/source/infrastructure.git#refs/heads/master"}
[17:26:22] : The build is removed from the queue to be prepared for the start
[17:26:26]W: This build has not been started because some of the builds it depends on failed to start
[17:26:26]E: Snapshot dependency "Automated Deployments / Bitcoin ABC Infra / Bitcoin-ABC Infra Checkout" failed
[17:26:26] : Build finished
teamcity added a comment.Mar 9 2022, 17:26
Build Bitcoin ABC Diffs / Diff Testing (build-without-wallet) failed.

Tail of the build log:

Build 'Bitcoin ABC Diffs / Diff Testing' #43693, branch 'refs/tags/phabricator/diff/32644'
Triggered 2022-03-09 17:26:04 by 'Phabricator Staging (phabricator-staging)'
Started 2022-03-09 17:26:41 on agent 'buildagent3'
Finished 2022-03-09 17:26:46 with status FAILURE 'Snapshot dependency failed to start: Automated Deployments / Bitcoin ABC Infra / Bitcoin-ABC Infra Checkout'
VCS revisions: 'PhabBitcoinAbcStagingRo' (Git, instance id 18): 'N/A' (checkout rules: '+:. => ./bitcoin-abc')
TeamCity URL https://build.bitcoinabc.org/viewLog.html?buildId=364291&buildTypeId=BitcoinABC_BitcoinAbcStaging 
TeamCity server version is 2019.2.4 (build 72059), server timezone: GMT (UTC)

[17:26:04]E: bt15 (running for 42s)
[17:26:04]i: TeamCity server version is 2019.2.4 (build 72059)
[17:26:04] : Collecting changes in 2 VCS roots (35s)
[17:26:04] :	 [Collecting changes in 2 VCS roots] VCS Root details
[17:26:04] :		 [VCS Root details] "phab-bitcoin-abc-staging-ro" {instance id=18, parent internal id=14, parent id=PhabBitcoinAbcStagingRo, description: "https://reviews.bitcoinabc.org/source/bitcoin-abc-staging.git#refs/heads/master"}
[17:26:04] :		 [VCS Root details] "abc-infrastructure" {instance id=7, parent internal id=7, parent id=AutomatedDeployments_BitcoinAbcDeveloperTools_AbcInfrastructure, description: "ssh://vcs@reviews.bitcoinabc.org:2221/source/infrastructure.git#refs/heads/master"}
[17:26:04]i:	 [Collecting changes in 2 VCS roots] Loading current repository state for VCS root 'phab-bitcoin-abc-staging-ro' (31s)
[17:26:04]i:	 [Collecting changes in 2 VCS roots] Loading current repository state for VCS root 'abc-infrastructure' (35s)
[17:26:41] : The build is removed from the queue to be prepared for the start
[17:26:46]W: This build has not been started because some of the builds it depends on failed to start
[17:26:46]E: Snapshot dependency "Automated Deployments / Bitcoin ABC Infra / Bitcoin-ABC Infra Checkout" failed
[17:26:46] : Build finished
PiRK added a child revision: D11153: bench: Add Muhash benchmarks.Mar 10 2022, 09:48
PiRK mentioned this in D11149: Add a CHashWriter::GetSHA256() method to compute a single sha256.Mar 10 2022, 10:26
PiRK published this revision for review.Mar 10 2022, 16:41
PiRK edited the summary of this revision. (Show Details)Mar 10 2022, 16:45
PiRK edited the summary of this revision. (Show Details)
PiRK edited the summary of this revision. (Show Details)
PiRK updated this revision to Diff 32654.Mar 11 2022, 07:29
PiRK edited the summary of this revision. (Show Details)

rebase

Harbormaster completed remote builds in B18447: Diff 32654.Mar 11 2022, 07:51
PiRK added a child revision: D11155: refactor: Improve encapsulation between MuHash3072 and Num3072.Mar 11 2022, 09:18
Fabien requested changes to this revision.Mar 11 2022, 11:02
Fabien added a subscriber: Fabien.

This is also a backport of commit 589f958662a2dcaacdb9a66f1088c74828a39577: https://github.com/bitcoin/bitcoin/pull/19055/commits/589f958662a2dcaacdb9a66f1088c74828a39577

src/config/CMakeLists.txt
259

That's not a useful comment

src/config/bitcoin-config.h.cmake.in
91

Macro likestamp:

src/crypto/muhash.cpp
156

nit: move on its line

157

This should be moved below so it is clear the above comment apply to the block. This is c++, but written as c89

226

layout

279

dito

323

I guess the compiler can determine this at build time

336

move the comment

src/crypto/muhash.h
98

#include <span.h>, or better forward declare it

This revision now requires changes to proceed.Mar 11 2022, 11:02
Fabien added a comment.Mar 11 2022, 11:02

@bot build-ubsan

teamcity awarded a token.Mar 11 2022, 11:04
PiRK edited the summary of this revision. (Show Details)Mar 11 2022, 12:50
PiRK updated this revision to Diff 32665.Mar 11 2022, 14:00

address comments

Harbormaster completed remote builds in B18457: Diff 32665.Mar 11 2022, 14:13
Fabien accepted this revision.Mar 12 2022, 07:26
This revision is now accepted and ready to land.Mar 12 2022, 07:26
Closed by commit rABC465584c0e51b: Add MuHash3072 implementation (authored by Fabian Jahr <fjahr@protonmail.com>, committed by PiRK). · Explain WhyMar 14 2022, 07:45
This revision was automatically updated to reflect the committed changes.
PiRK added a commit: rABC465584c0e51b: Add MuHash3072 implementation.

Revision Contents
Changeset List

PathSize
src/
config/
4 lines
2 lines
crypto/
1 line
128 lines
370 lines
test/
143 lines
test/
functional/
test_framework/
15 lines

Diff 32654

View Options

src/config/CMakeLists.txt

Loading...
View Options

src/config/bitcoin-config.h.cmake.in

Loading...
View Options

src/crypto/CMakeLists.txt

Loading...
View Options

src/crypto/muhash.h

Loading...
View Options

src/crypto/muhash.cpp

Loading...
View Options

src/test/crypto_tests.cpp

Loading...
View Options

test/functional/test_framework/muhash.py

Loading...