Add minisketch subtree and integrate into build/test

fanquake commented at 7:08 am on September 28, 2021: member

This takes over #21859, which has recently switched to my integration branch. A few more build issues came up (and have been fixed) since, and after discussing with sipa it was decided I would open a PR to shepherd any final changes through.

This adds a src/minisketch subtree, taken from the master branch of https://github.com/sipa/minisketch, to prepare for Erlay implementation (see #21515). It gets configured for just supporting 32-bit fields (the only ones we’re interested in in the context of Erlay), and some code on top is added:

A very basic unit test (just to make sure compilation & running works; actual correctness checking is done through minisketch’s own tests).

A wrapper in minisketchwrapper.{cpp,h} that runs a benchmark to determine which field implementation to use.

Only changes since my last update to the branch in the previous PR have been rebasing on master and fixing an issue with a header in an introduced file.

fanquake added the label Build system on Sep 28, 2021

fanquake added the label Upstream on Sep 28, 2021

fanquake added the label DrahtBot Guix build requested on Sep 28, 2021

fanquake added this to the milestone 23.0 on Sep 28, 2021

fanquake added this to the "Blockers" column in a project

fanquake force-pushed on Sep 28, 2021

theuni commented at 4:33 pm on September 28, 2021: member

Looks like at least one reason this is failing is because clmul detection is inaccurate here. This was apparently fixed upstream by this commit. Pulling in that change should fix that problem.

As a follow-up, we could split the feature detection from minisketch’s configure.ac out into an m4 file that both minisketch and downstream projects include. That would prevent these types of out-of-sync issues. Edit: I worked on this for a while and it’s more trouble than it’s worth. A little copy/paste is probably more straightforward here.

DrahtBot commented at 6:22 pm on September 28, 2021: member

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#23473 (build: boring autotools cleanup by fanquake)
#23462 (test: Enable SC2046 and SC2086 shellcheck rules by hebasto)
#23345 (build: Drop unneeded dependencies for bitcoin-wallet tool by hebasto)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

theuni commented at 8:24 pm on September 28, 2021: member

It looks like https://github.com/bitcoin/bitcoin/pull/23114/checks?check_run_id=3731233027 might’ve caught a real minisketch bug?

sipa commented at 8:29 pm on September 28, 2021: member

@theuni It’s not; unsigned overflow is well-defined (but our sanitizer is overly strict). In this case it’s computing “A - B + C”, where the overall result is positive, but (A - B) is negative. Reordering the expression, or turning off the unsigned overflow sanitizer would be possible solutions.

sipa commented at 9:05 pm on September 28, 2021: member

See https://github.com/sipa/minisketch/pull/49

fanquake force-pushed on Sep 29, 2021

fanquake commented at 3:24 am on September 29, 2021: member

Looks like at least one reason this is failing is because clmul detection is inaccurate here. This was apparently fixed upstream by this commit. Pulling in that change should fix that problem.

I’ve pulled in the improved clmul detection. That should fix the failing 32 bit CentOS 8 and multiprocess builds. I’ve also made a change that should fix the failing Win64 CI.

theuni commented at 12:59 pm on September 29, 2021: member

@fanquake Could you pull in a temp/hack version of sipa/minisketch#49 here to see if it makes the sanitizer happy?

MarcoFalke commented at 1:10 pm on September 29, 2021: member

It is not allowed to link anything other than the fuzz tests with --enable-fuzz-binary, which explains the fuzz CI failure.

DrahtBot removed the label DrahtBot Guix build requested on Sep 29, 2021

theuni commented at 3:47 pm on September 29, 2021: member

Thanks for the pointer, @MarcoFalke. @fanquake: You can take (and squash) https://github.com/theuni/bitcoin/commit/aaa53f23e624f6804e451f3f20981898a50d83a0 which should fix that in the simplest way.

in src/minisketchwrapper.cpp:31 in d855a4e0be outdated

26+
27+    uint32_t max_impl = Minisketch::MaxImplementation();
28+    for (uint32_t impl = 0; impl <= max_impl; ++impl) {
29+        std::vector<int64_t> benches;
30+        uint64_t offset = 0;
31+        /* Run a little benchmark with capacity 32, adding 184 entries, and decoding 16 of them once. */

theuni commented at 4:14 pm on September 29, 2021:

I think this should be “decoding 11”?

sipa commented at 4:19 pm on September 29, 2021:

Yup.

fanquake commented at 0:59 am on September 30, 2021:

Fixed in next push.

in src/minisketchwrapper.cpp:42 in d855a4e0be outdated

37+                sketch.Add(e*1337 + b*13337 + offset);
38+            }
39+            for (uint64_t e = 0; e < 84; ++e) {
40+                sketch.Add(e*1337 + b*13337 + offset);
41+            }
42+            offset += (*sketch.Decode(32))[0];

theuni commented at 4:49 pm on September 29, 2021:

Why use the optional version of Decode if the value is ignored?

Also, what’s the offset’s purpose here? It’s not obvious to me what will be in [0].

naumenkogs commented at 12:48 pm on October 21, 2021:

Also, what’s the offset’s purpose here? It’s not obvious to me what will be in [0].

From my reading, it seems to give a random deterministic value?

sipa commented at 12:51 pm on October 21, 2021:

It’s just to make sure the inputs to the algorithm are vaguely randomized (and also, so the compiler can’t optimize the decode call out).

sipa commented at 12:53 pm on October 21, 2021:

As for why the optional version: no strong reason, but this avoids a separate temporary variable to place the result in.

fanquake force-pushed on Sep 30, 2021

fanquake commented at 1:20 am on September 30, 2021: member

@fanquake Could you pull in a temp/hack version of sipa/minisketch#49 here to see if it makes the sanitizer happy?

Cherry-picked sipa/minisketch#49 and sipa/minisketch/pull/51 (minus the CI change) for testing.

@fanquake: You can take (and squash) theuni@aaa53f2 which should fix that in the simplest way.

Integrated this change.

Rebased on master to resolve a conflict.

theuni commented at 3:08 am on September 30, 2021: member

I don’t understand the problem here. Does the sanitizer want the high bits masked off before shifting or something?

 0minisketch/src/fields/../int_utils.h:21:62: runtime error: left shift of 3092242204026410023 by 13 places cannot be represented in type 'uint64_t' (aka 'unsigned long')
 1    [#0](/bitcoin-bitcoin/0/) 0x55d2cf04cec8 in unsigned long Rot<13>(unsigned long) minisketch/src/fields/../int_utils.h:21:62
 2    [#1](/bitcoin-bitcoin/1/) 0x55d2cf04cec8 in SipHashRound(unsigned long&, unsigned long&, unsigned long&, unsigned long&) minisketch/src/fields/../int_utils.h:24:20
 3    [#2](/bitcoin-bitcoin/2/) 0x55d2cf051892 in SipHash(unsigned long, unsigned long, unsigned long) minisketch/src/fields/../int_utils.h:37:5
 4    [#3](/bitcoin-bitcoin/3/) 0x55d2cf04a775 in (anonymous namespace)::Field<unsigned int, 32, 141u, RecLinTrans<unsigned int, 6, 6, 5, 5, 5, 5>, RecLinTrans<unsigned int, 4, 4, 4, 4, 4, 4, 4, 4>, &((anonymous namespace)::SQR_TABLE_32), &((anonymous namespace)::QRT_TABLE_32)>::FromSeed(unsigned long) const minisketch/src/fields/generic_common_impl.h:55:29
 5    [#4](/bitcoin-bitcoin/4/) 0x55d2cf04a775 in SketchImpl<(anonymous namespace)::Field<unsigned int, 32, 141u, RecLinTrans<unsigned int, 6, 6, 5, 5, 5, 5>, RecLinTrans<unsigned int, 4, 4, 4, 4, 4, 4, 4, 4>, &((anonymous namespace)::SQR_TABLE_32), &((anonymous namespace)::QRT_TABLE_32)> >::SketchImpl<>(int, int) minisketch/src/fields/../sketch_impl.h:365:27
 6    [#5](/bitcoin-bitcoin/5/) 0x55d2cf04a775 in ConstructGeneric4Bytes(int, int) minisketch/src/fields/generic_4bytes.cpp:120:25
 7    [#6](/bitcoin-bitcoin/6/) 0x55d2cf047616 in (anonymous namespace)::Construct(int, int) minisketch/src/minisketch.cpp:94:20
 8    [#7](/bitcoin-bitcoin/7/) 0x55d2cf04737c in minisketch_implementation_supported minisketch/src/minisketch.cpp:371:26
 9    [#8](/bitcoin-bitcoin/8/) 0x55d2cf039ea8 in Minisketch::ImplementationSupported(unsigned int, unsigned int) minisketch/src/../include/minisketch.h:218:99
10    [#9](/bitcoin-bitcoin/9/) 0x55d2cf039ea8 in (anonymous namespace)::CreateSketches(unsigned int, unsigned long) minisketch/src/test.cpp:34:13
11    [#10](/bitcoin-bitcoin/10/) 0x55d2cf037933 in (anonymous namespace)::TestRandomized(unsigned int, unsigned long, unsigned long) minisketch/src/test.cpp:140:25
12    [#11](/bitcoin-bitcoin/11/) 0x55d2cf0362f7 in main minisketch/src/test.cpp:297:9
13    [#12](/bitcoin-bitcoin/12/) 0x7fd662883564 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x28564)
14    [#13](/bitcoin-bitcoin/13/) 0x55d2cef873fd in _start (/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/minisketch/test+0x4c3fd)

sipa commented at 3:11 am on September 30, 2021: member

@theuni Yes, exactly. That’s not going to happen. We should just not enable unsigned integer sanitizer - it’s going to cause alarm bells all over the place.

MarcoFalke commented at 5:30 am on September 30, 2021: member

The sanitizer error can be fixed by disabling the sanitizer or adding a suppression to test/supp...

practicalswift commented at 8:13 am on September 30, 2021: contributor

Some of the suppressions we apply for crypto/ might be appropriate for minisketch/:

0$ grep crypto/ test/sanitizer_suppressions/ubsan
1unsigned-integer-overflow:crypto/
2implicit-integer-sign-change:crypto/
3implicit-signed-integer-truncation:crypto/
4implicit-unsigned-integer-truncation:crypto/
5shift-base:crypto/

theuni commented at 4:14 pm on September 30, 2021: member

@theuni Yes, exactly. That’s not going to happen. We should just not enable unsigned integer sanitizer - it’s going to cause alarm bells all over the place.

Yeah, I’d go as far as to call this warning harmful. Afaik this shift is well-defined. I guess i can imagine wanting to split the << operator into two logical operations, but I would expect to have to opt-in a little harder for something like that.

I’d be ok with -fno-sanitize=unsigned-shift-base (assuming that’s the right knob) anywhere we use the undefined sanitizer.

Edit: and -fno-sanitize=unsigned-integer-overflow

sipa commented at 4:27 pm on September 30, 2021: member

@theuni Right, in C and C++, unsigned integer types are defined (and intended) to act as integers modulo 2N, while signed types are intended to act as just integers in general. To make sure that signed integer behavior matches actual integers, the language doesn’t specify what happens when they overflow/underflow (in some cases, it’s UB; in some cases it’s implementation-defined behavior).

This is problematic: sometimes you actually want the mod 2N behavior, and sometimes you’re just operating on unsigned integers which you know will never overflow. IMHO, there should just be two distinct types for that in the language, but for whatever reasons, that’s not the case in C/C++. The sanitizers cannot tell the difference either, so you have to tell it whether you want integers that act mod 2N, or whether you want unbounded unsigned integer-like behavior. Unfortunately, certain codebases, especially ones that include cryptographic code, have a mix of both. So the solution is either not enabling unsigned integer sanitizers at all (making it assume mod behavior for everything; the default), or enabling it and having suppressions for places where mod behavior is desired.

So to be clear: we explicitly enable unsigned integer sanitizers in Bitcoin Core, which causes it to trigger for things that are perfectly well-defined behavior (but potentially still red flags, if mod behavior is not desired). We could just not do that, but I guess there are large portions on the codebase where these red flags are interesting to see.

theuni commented at 4:55 pm on September 30, 2021: member

From IRC:

0<cfields> sipa: blah, good point about mixed-use codebases. I guess https://github.com/sipa/minisketch/pull/51 is kinda a counterpoint to disabling the warning wholesale, as it pointed out something legal but logically broken.
1<sipa> cfields: FWIW, libsecp256k1 does assume that some signed integer behavior is actually well-defined (and it has compile-time assertions to check that), which means it's not fully C language neutral
2<sipa> (not UB though; only parts of signed integer behavior that are implementation defined)
3<sipa> cfields: but i do think that we probably want to disable unsigned-integer sanitizers wholesale for minisketch
4<laanwj> disabling unsigned-integer sanitizers for cryptographic code makes a lot of sense
5<cfields> ACK, will just do it there. I'm still surprised that this happens rarely enough for our tests to pass with only a few exceptions. Guess it is pretty specific to crypto/mathy stuff.

So, @practicalswift’s and @MarcoFalke’s suggestion sounds good. I’ll push that change up.

theuni commented at 7:51 pm on September 30, 2021: member

Ok, this should be sufficient: https://github.com/theuni/bitcoin/commit/9e8bdea298ed25077ae75742fe26308d99103346 Edit: removed unnecessary shift-base.

The minisketch change is no longer required.

I think this should be enough to make c-i happy 🤞

fanquake force-pushed on Oct 1, 2021

fanquake commented at 2:38 am on October 1, 2021: member

Dropped https://github.com/sipa/minisketch/pull/49, now that has been closed upstream. Pulled in https://github.com/theuni/bitcoin/commit/9e8bdea298ed25077ae75742fe26308d99103346 to add some ubsan suppressions.

fanquake force-pushed on Oct 1, 2021

fanquake commented at 3:34 am on October 1, 2021: member

Edit: removed unnecessary shift-base.

I’ve re-added this after dropping sipa/minisketch#49.

theuni commented at 3:17 am on October 2, 2021: member

sipa/minisketch#51 has been merged upstream, that should be the last thing needed.

fanquake force-pushed on Oct 3, 2021

fanquake commented at 3:38 am on October 3, 2021: member

I’ve rebased, updated the subtree to include https://github.com/sipa/minisketch/pull/51, and dropped the cherry-pick of that change.

fanquake added the label DrahtBot Guix build requested on Oct 3, 2021

luke-jr commented at 6:05 pm on October 3, 2021: member

Concept NACK to using a subtree for non-concensus-critical libraries.

At the very least, there should be a way to use a system install.

DrahtBot removed the label DrahtBot Guix build requested on Oct 4, 2021

MarcoFalke deleted a comment on Oct 5, 2021

in doc/developer-notes.md:1003 in 20df31d486 outdated

 998@@ -999,6 +999,9 @@ Current subtrees include:
 999   - Subtree at https://github.com/bitcoin-core/univalue-subtree ; maintained by Core contributors.
1000   - Deviates from upstream https://github.com/jgarzik/univalue.
1001 
1002+- src/minisketch
1003+  - Upstream at https://github.com/sipa/minisketch ; actively maintained by Core contributors.

theuni commented at 4:53 pm on October 6, 2021:

I suppose we’ll want this to graduate from https://github.com/sipa to https://github.com/bitcoin-core sometime soon before/after merging this. I don’t really care much either way.

in src/Makefile.am:27 in 20df31d486 outdated

23@@ -24,7 +24,7 @@ else
24 LIBUNIVALUE = $(UNIVALUE_LIBS)
25 endif
26 
27-BITCOIN_INCLUDES=-I$(builddir) -I$(srcdir)/secp256k1/include $(BDB_CPPFLAGS) $(BOOST_CPPFLAGS) $(LEVELDB_CPPFLAGS)
28+BITCOIN_INCLUDES=-I$(builddir) -I$(srcdir)/minisketch/include -I$(srcdir)/secp256k1/include $(BDB_CPPFLAGS) $(BOOST_CPPFLAGS) $(LEVELDB_CPPFLAGS)

theuni commented at 4:58 pm on October 6, 2021:

This is probably only strictly necessary in a few places and is overkill to list globally. As a follow-up, we might want to constrain the includes.

fanquake commented at 4:48 am on October 7, 2021:

Sure. Also reminded me that we could add a MINISKETCH_INCLUDE_DIR_INT var upstream, and use that. Opened a PR: https://github.com/sipa/minisketch/pull/52.

fanquake commented at 5:26 am on October 12, 2021:

Now using MINISKETCH_INCLUDE_DIR_INT from upstream.

in src/Makefile.am:798 in 20df31d486 outdated

794@@ -795,6 +795,7 @@ $(top_srcdir)/$(subdir)/config/bitcoin-config.h.in:  $(am__configure_deps)
795 
796 clean-local:
797 	-$(MAKE) -C secp256k1 clean
798+	-$(MAKE) -C minisketch clean

theuni commented at 5:01 pm on October 6, 2021:

No need for this as minisketch deps are integrated. This is actually probably just failing quietly (rules starting with - are allowed to fail).

fanquake commented at 4:40 am on October 7, 2021:

Thanks. Fixed in next push.

theuni commented at 10:50 pm on October 6, 2021: member

Thanks to everyone who’s helped to get this ready!

This integration looks good to me other than a few nits, with the assumption that minisketch itself is sane as I have not reviewed it fully.

fanquake force-pushed on Oct 7, 2021

laanwj commented at 2:55 pm on October 7, 2021: member

Build system changes-review ACK 9089c6fc639fd57490ea321cce93b491a3a1e418 Haven’t reviewed minisketch itself.

fanquake force-pushed on Oct 12, 2021

fanquake added the label DrahtBot Guix build requested on Oct 12, 2021

in configure.ac:1002 in 1442434556 outdated

 997@@ -980,18 +998,21 @@ AC_CHECK_DECLS([bswap_16, bswap_32, bswap_64],,,
 998                  #endif])
 999 
1000 AC_MSG_CHECKING(for __builtin_clzl)
1001+
1002+have_clzl=

dongcarl commented at 2:50 pm on October 12, 2021:

Probably a bit clearer to do have_clzl=no in the ELSE case?

fanquake commented at 6:33 am on October 20, 2021:

Moved into the else case on next push.

in configure.ac:985 in 1442434556 outdated

1014   (void) __builtin_clzll(0);
1015   ]])],
1016- [ AC_MSG_RESULT(yes); AC_DEFINE(HAVE_BUILTIN_CLZLL, 1, [Define this symbol if you have __builtin_clzll])],
1017+ [ AC_MSG_RESULT(yes); have_clzll=yes; AC_DEFINE(HAVE_BUILTIN_CLZLL, 1, [Define this symbol if you have __builtin_clzll])],
1018  [ AC_MSG_RESULT(no)]
1019 )

dongcarl commented at 3:10 pm on October 12, 2021:

These seem different from the tests here: https://github.com/sipa/minisketch/blob/89629eb2c7e262b39ba489b93b111760baded4b3/configure.ac#L77-L89

Are there scenarios in which the two tests will differ in opinion?

sipa commented at 3:02 am on October 17, 2021:

It seems the Bitcoin Core configure has a single define to indicate whether all of clz/clzl/clzll are available, while the Minisketch one tests for individual ones.

I don’t think there are practical systems that have one but not all.

theuni commented at 5:40 pm on October 19, 2021:

@sipa I think you got the checks backwards :)

Agree that they’re probably all-or-nothing in practice though. I see __builtin_clzll already supported in gcc 4.1, released in 2006 (I didn’t bother going back any further). We should probably coalesce on one test or another, but I don’t really care which.

in src/Makefile.am:659 in 55f0f914d2 outdated

654@@ -655,7 +655,8 @@ bitcoin_bin_ldadd = \
655   $(LIBLEVELDB) \
656   $(LIBLEVELDB_SSE42) \
657   $(LIBMEMENV) \
658-  $(LIBSECP256K1)
659+  $(LIBSECP256K1) \
660+  $(MINISKETCH_LIBS)

dongcarl commented at 3:19 pm on October 12, 2021:

Seems like this would mean the bitcoin-wallet tool also LDADDs minisketch, which doesn’t sound right to me since it’s an offline tool.

I think either bitcoin-wallet should not LDADD bitcoin_bin_ldadd or MINISKETCH_LIBS belong somewhere else.

theuni commented at 5:43 pm on October 19, 2021:

Agree. This commit probably should not have made it in; it was just meant to demonstrate that linking works. We should instead add the dep as-needed.

fanquake commented at 6:43 am on October 20, 2021:

bitcoin-wallet never used to LDADD bitcoin_bin_ldadd, but that changed in #18677. I think we could probably revert to not LDADD’ing it, and specify a more concrete list of libraries. I will propose that separately, but for now, will drop this commit, and add the lib in the right place, in the commits it’s needed.

fanquake commented at 7:09 am on October 20, 2021:

Actually, this is just going away entirely for now.

DrahtBot removed the label DrahtBot Guix build requested on Oct 17, 2021

fanquake referenced this in commit a7f28af437 on Oct 20, 2021

DrahtBot added the label Needs rebase on Oct 20, 2021

fanquake force-pushed on Oct 20, 2021

DrahtBot removed the label Needs rebase on Oct 20, 2021

MarcoFalke deleted a comment on Oct 20, 2021

theuni commented at 5:33 pm on October 20, 2021: member

Buildsystem/wrapper re-ACK f22af45cb89af46b20ce5764055b87801f2c6ae7.

My remaining wrapper nit isn’t a big deal.

Squashed 'src/minisketch/' content from commit 89629eb2c7

git-subtree-dir: src/minisketch
git-subtree-split: 89629eb2c7e262b39ba489b93b111760baded4b3

b6487dc4ef

Merge commit 'b6487dc4ef47ec9ea894eceac25f37d0b806f8aa' as 'src/minisketch' 07f0a61ef7

build: add configure checks for minisketch

AC_DEFINE'd values won't be passed down to minisketch because it does not
use bitcoin-config.h. Thus we need a way to know if we should manually add
defines for minisketch files.

b2904ceb85

build: add minisketch build file and include it 8bc166d5b1

Add MSVC build configuration for libminisketch 0eb7928ab8

Add minisketch dependency 0659f12b13

Add basic minisketch tests ee9dc71c1b

Add thin Minisketch wrapper to pick best implementation 54b5e1aeab

ubsan: add minisketch exceptions 29173d6c6c

fanquake force-pushed on Oct 21, 2021

fanquake commented at 3:23 am on October 21, 2021: member

Guix Build:

 0bash-5.1# find guix-build-$(git rev-parse --short=12 HEAD)/output/ -type f -print0 | env LC_ALL=C sort -z | xargs -r0 sha256sum
 189b9bc3994ee82f15eb522c6085c88e9d14e1f12887eb64b8fa6eafdba6f78ed  guix-build-29173d6c6ca0/output/aarch64-linux-gnu/SHA256SUMS.part
 22b1689ee1c37759663bc08c86c0c39e09a9567b7dcfb153af6d3c15bb6483081  guix-build-29173d6c6ca0/output/aarch64-linux-gnu/bitcoin-29173d6c6ca0-aarch64-linux-gnu-debug.tar.gz
 3a58477250142ffc319684f935589058431df8239a7123dfd6976fa6553812975  guix-build-29173d6c6ca0/output/aarch64-linux-gnu/bitcoin-29173d6c6ca0-aarch64-linux-gnu.tar.gz
 443dafdb7d6d2d4d5048505addc9ebe9eaa9a99e915f5b6538e761fbeef1a6a10  guix-build-29173d6c6ca0/output/arm-linux-gnueabihf/SHA256SUMS.part
 54a56f45d91ce0c2cd667f2f7dd05a32778359fdb31598569aa0a331207db4320  guix-build-29173d6c6ca0/output/arm-linux-gnueabihf/bitcoin-29173d6c6ca0-arm-linux-gnueabihf-debug.tar.gz
 613f2ffbbf04b17cf0114428e34d8da3a9c0d695e0701e3ee3bb3797e407002db  guix-build-29173d6c6ca0/output/arm-linux-gnueabihf/bitcoin-29173d6c6ca0-arm-linux-gnueabihf.tar.gz
 70d20ba62b54469109a7e1767678742c211bf7ac995c5a0fb4a31b5310bdcb144  guix-build-29173d6c6ca0/output/dist-archive/bitcoin-29173d6c6ca0.tar.gz
 8e5d4c1223fa6494399368d57148d65c1ea8f8178c7c4ac4050c2f9fc15c4c34e  guix-build-29173d6c6ca0/output/powerpc64-linux-gnu/SHA256SUMS.part
 9be31fe98d97e3d1bbf55eefd0e752eb3903141040c3f42cecc5a147ba535124f  guix-build-29173d6c6ca0/output/powerpc64-linux-gnu/bitcoin-29173d6c6ca0-powerpc64-linux-gnu-debug.tar.gz
1000a7594ed7f4a24cf2b4cb03356630d94dd1053712d913c7218db301ffbd8a8d  guix-build-29173d6c6ca0/output/powerpc64-linux-gnu/bitcoin-29173d6c6ca0-powerpc64-linux-gnu.tar.gz
112785c709c05710b6db7aa6f0210cda0897c896fe23e883ae9f02aab0b758e906  guix-build-29173d6c6ca0/output/powerpc64le-linux-gnu/SHA256SUMS.part
12483b81890ba35813fa8c1e1670581e3b574e5cca3c487effc2ba43e82e1b935e  guix-build-29173d6c6ca0/output/powerpc64le-linux-gnu/bitcoin-29173d6c6ca0-powerpc64le-linux-gnu-debug.tar.gz
133f2d8a25e38086b030200a56098c5ff427c4f1d851c114476656cfcf038bf567  guix-build-29173d6c6ca0/output/powerpc64le-linux-gnu/bitcoin-29173d6c6ca0-powerpc64le-linux-gnu.tar.gz
148bacce59257057d40bb84f6f62cb3992f3bb5ce61ef2ed57a5dcf20b4c143097  guix-build-29173d6c6ca0/output/riscv64-linux-gnu/SHA256SUMS.part
15fe3a19b8cac2a42fbbd6ed1a67b5942eca9e8218656c438bb7bd909a53ca4aee  guix-build-29173d6c6ca0/output/riscv64-linux-gnu/bitcoin-29173d6c6ca0-riscv64-linux-gnu-debug.tar.gz
164954f8a05b2674cdbb6a24d95d31126cbdfe64f4f4dfda2d860f2cc4935d34c4  guix-build-29173d6c6ca0/output/riscv64-linux-gnu/bitcoin-29173d6c6ca0-riscv64-linux-gnu.tar.gz
170fd610c9147cb714d43c1c59872f981ba1e46108c89ab6c7813bd7f0089c87dc  guix-build-29173d6c6ca0/output/x86_64-apple-darwin19/SHA256SUMS.part
18fc7fd5ad415c18e4eb7e8796a4ba8ae9a61e178a4f7f7a987a983e6294f89379  guix-build-29173d6c6ca0/output/x86_64-apple-darwin19/bitcoin-29173d6c6ca0-osx-unsigned.dmg
19dfa4d38cbd10c3b69bd0906895bd3113764fa5f5f3b10ec632769bf0fb5b396c  guix-build-29173d6c6ca0/output/x86_64-apple-darwin19/bitcoin-29173d6c6ca0-osx-unsigned.tar.gz
20abeda851f9165d3c4175f23c1b08c1a455d632bc8f17fd2b5412301c2971a69a  guix-build-29173d6c6ca0/output/x86_64-apple-darwin19/bitcoin-29173d6c6ca0-osx64.tar.gz
21866a0258831e01b407c24485b7073806ed53b2edae907f12474ba8c873dac18d  guix-build-29173d6c6ca0/output/x86_64-linux-gnu/SHA256SUMS.part
22bbf7f367929d5a3226de0ff96148e5eddd05495c18fb159a2fcc89632c07d44c  guix-build-29173d6c6ca0/output/x86_64-linux-gnu/bitcoin-29173d6c6ca0-x86_64-linux-gnu-debug.tar.gz
23e94592e85bd84bc346d30b08b163b55d640783bc530cfcdb7553e15c7b59a17d  guix-build-29173d6c6ca0/output/x86_64-linux-gnu/bitcoin-29173d6c6ca0-x86_64-linux-gnu.tar.gz
242ea5e404e6ac8ac1634a8a27fc49b230602d3c4ad3caa3e7f9ebfce0ee2df5f2  guix-build-29173d6c6ca0/output/x86_64-w64-mingw32/SHA256SUMS.part
25fdaeea7e6f2884ef49f901718d0e1d4a81768fa63d5de49ef47357470cfa2197  guix-build-29173d6c6ca0/output/x86_64-w64-mingw32/bitcoin-29173d6c6ca0-win-unsigned.tar.gz
2633dd8a2b69f7cdf3aa05df2b39908483ec07affb8034a1f2f5a76ebca2877389  guix-build-29173d6c6ca0/output/x86_64-w64-mingw32/bitcoin-29173d6c6ca0-win64-debug.zip
27e724eda8888fa2017430abb50fb146c934ec686cde13a555835dfc33ae228a70  guix-build-29173d6c6ca0/output/x86_64-w64-mingw32/bitcoin-29173d6c6ca0-win64-setup-unsigned.exe
282adf2e26c2faf588078822b0b41601f5aabdfabd9c998de4e50b325bd9e3ef36  guix-build-29173d6c6ca0/output/x86_64-w64-mingw32/bitcoin-29173d6c6ca0-win64.zip

in src/minisketchwrapper.cpp:49 in 54b5e1aeab outdated

44+            benches.push_back(stop - start);
45+        }
46+        /* Remember which implementation has the best median benchmark time. */
47+        if (!benches.empty()) {
48+            std::sort(benches.begin(), benches.end());
49+            if (!best || best->first > benches[5]) {

naumenkogs commented at 12:53 pm on October 21, 2021:

Where does [5] come from?

sipa commented at 12:56 pm on October 21, 2021:

It’s the middle of the 11 benchmarks (we’re trying to find the implementation with the best median benchmark score).

michaelfolkson commented at 3:33 pm on October 22, 2021: contributor

Concept ACK, Approach ACK

For the benefit of reviewers who weren’t at the Core dev IRC meeting yesterday the build stuff seems to be pretty much ready (thanks to @theuni, @fanquake @dongcarl etc).

It seems like we are in the final phase of testing for the Minisketch library now pre-merge and hence previous PR review clubs (Python 1 and 2, C++ 3) may be a useful resource for reviewers. Reviews and testing the library should (presumably) be posted on this PR.

Once this is (hopefully) merged that opens the door to a greater review focus on the Erlay PR. It seems to me that that PR has been waiting on this to get to a final(ish) state.

in src/minisketchwrapper.h:13 in 54b5e1aeab outdated

 8+#include <minisketch.h>
 9+#include <cstddef>
10+#include <cstdint>
11+
12+/** Wrapper around Minisketch::Minisketch(32, implementation, capacity). */
13+Minisketch MakeMinisketch32(size_t capacity);

naumenkogs commented at 3:01 pm on October 25, 2021:

Can this wrapper also encapsulate minisketch_compute_max_elements? This is the only library-level function that’s gonna be leaked into txreconciliation.cpp. See how I use it:

0        size_t max_elements = minisketch_compute_max_elements(RECON_FIELD_SIZE, remote_sketch_capacity, RECON_FALSE_POSITIVE_COEF);
1        std::vector<uint64_t> differences(max_elements);
2        if (local_sketch.Merge(remote_sketch).Decode(differences)) {

I don’t think there’s a way to avoid it? Or maybe it’s fine to have it leaked?

naumenkogs commented at 4:53 am on October 26, 2021:

This can be done later though.

naumenkogs commented at 4:55 am on October 26, 2021: member

ACK 29173d6c6ca0cc3be9fa6bf2409a509ffea1a02a

low-key reviewed the build system integration (as much as i can)
reviewed the new tests
made sure it’s the right minisketch
made sure that it builds
made sure it can be called from net_processing which is needed for erlay.

jarolrod commented at 1:44 am on November 3, 2021: member

Contributing GUIX hashes, mine match @fanquake

 089b9bc3994ee82f15eb522c6085c88e9d14e1f12887eb64b8fa6eafdba6f78ed  guix-build-29173d6c6ca0/output/aarch64-linux-gnu/SHA256SUMS.part
 12b1689ee1c37759663bc08c86c0c39e09a9567b7dcfb153af6d3c15bb6483081  guix-build-29173d6c6ca0/output/aarch64-linux-gnu/bitcoin-29173d6c6ca0-aarch64-linux-gnu-debug.tar.gz
 2a58477250142ffc319684f935589058431df8239a7123dfd6976fa6553812975  guix-build-29173d6c6ca0/output/aarch64-linux-gnu/bitcoin-29173d6c6ca0-aarch64-linux-gnu.tar.gz
 343dafdb7d6d2d4d5048505addc9ebe9eaa9a99e915f5b6538e761fbeef1a6a10  guix-build-29173d6c6ca0/output/arm-linux-gnueabihf/SHA256SUMS.part
 44a56f45d91ce0c2cd667f2f7dd05a32778359fdb31598569aa0a331207db4320  guix-build-29173d6c6ca0/output/arm-linux-gnueabihf/bitcoin-29173d6c6ca0-arm-linux-gnueabihf-debug.tar.gz
 513f2ffbbf04b17cf0114428e34d8da3a9c0d695e0701e3ee3bb3797e407002db  guix-build-29173d6c6ca0/output/arm-linux-gnueabihf/bitcoin-29173d6c6ca0-arm-linux-gnueabihf.tar.gz
 60d20ba62b54469109a7e1767678742c211bf7ac995c5a0fb4a31b5310bdcb144  guix-build-29173d6c6ca0/output/dist-archive/bitcoin-29173d6c6ca0.tar.gz
 7e5d4c1223fa6494399368d57148d65c1ea8f8178c7c4ac4050c2f9fc15c4c34e  guix-build-29173d6c6ca0/output/powerpc64-linux-gnu/SHA256SUMS.part
 8be31fe98d97e3d1bbf55eefd0e752eb3903141040c3f42cecc5a147ba535124f  guix-build-29173d6c6ca0/output/powerpc64-linux-gnu/bitcoin-29173d6c6ca0-powerpc64-linux-gnu-debug.tar.gz
 900a7594ed7f4a24cf2b4cb03356630d94dd1053712d913c7218db301ffbd8a8d  guix-build-29173d6c6ca0/output/powerpc64-linux-gnu/bitcoin-29173d6c6ca0-powerpc64-linux-gnu.tar.gz
102785c709c05710b6db7aa6f0210cda0897c896fe23e883ae9f02aab0b758e906  guix-build-29173d6c6ca0/output/powerpc64le-linux-gnu/SHA256SUMS.part
11483b81890ba35813fa8c1e1670581e3b574e5cca3c487effc2ba43e82e1b935e  guix-build-29173d6c6ca0/output/powerpc64le-linux-gnu/bitcoin-29173d6c6ca0-powerpc64le-linux-gnu-debug.tar.gz
123f2d8a25e38086b030200a56098c5ff427c4f1d851c114476656cfcf038bf567  guix-build-29173d6c6ca0/output/powerpc64le-linux-gnu/bitcoin-29173d6c6ca0-powerpc64le-linux-gnu.tar.gz
138bacce59257057d40bb84f6f62cb3992f3bb5ce61ef2ed57a5dcf20b4c143097  guix-build-29173d6c6ca0/output/riscv64-linux-gnu/SHA256SUMS.part
14fe3a19b8cac2a42fbbd6ed1a67b5942eca9e8218656c438bb7bd909a53ca4aee  guix-build-29173d6c6ca0/output/riscv64-linux-gnu/bitcoin-29173d6c6ca0-riscv64-linux-gnu-debug.tar.gz
154954f8a05b2674cdbb6a24d95d31126cbdfe64f4f4dfda2d860f2cc4935d34c4  guix-build-29173d6c6ca0/output/riscv64-linux-gnu/bitcoin-29173d6c6ca0-riscv64-linux-gnu.tar.gz
160fd610c9147cb714d43c1c59872f981ba1e46108c89ab6c7813bd7f0089c87dc  guix-build-29173d6c6ca0/output/x86_64-apple-darwin19/SHA256SUMS.part
17fc7fd5ad415c18e4eb7e8796a4ba8ae9a61e178a4f7f7a987a983e6294f89379  guix-build-29173d6c6ca0/output/x86_64-apple-darwin19/bitcoin-29173d6c6ca0-osx-unsigned.dmg
18dfa4d38cbd10c3b69bd0906895bd3113764fa5f5f3b10ec632769bf0fb5b396c  guix-build-29173d6c6ca0/output/x86_64-apple-darwin19/bitcoin-29173d6c6ca0-osx-unsigned.tar.gz
19abeda851f9165d3c4175f23c1b08c1a455d632bc8f17fd2b5412301c2971a69a  guix-build-29173d6c6ca0/output/x86_64-apple-darwin19/bitcoin-29173d6c6ca0-osx64.tar.gz
20866a0258831e01b407c24485b7073806ed53b2edae907f12474ba8c873dac18d  guix-build-29173d6c6ca0/output/x86_64-linux-gnu/SHA256SUMS.part
21bbf7f367929d5a3226de0ff96148e5eddd05495c18fb159a2fcc89632c07d44c  guix-build-29173d6c6ca0/output/x86_64-linux-gnu/bitcoin-29173d6c6ca0-x86_64-linux-gnu-debug.tar.gz
22e94592e85bd84bc346d30b08b163b55d640783bc530cfcdb7553e15c7b59a17d  guix-build-29173d6c6ca0/output/x86_64-linux-gnu/bitcoin-29173d6c6ca0-x86_64-linux-gnu.tar.gz
232ea5e404e6ac8ac1634a8a27fc49b230602d3c4ad3caa3e7f9ebfce0ee2df5f2  guix-build-29173d6c6ca0/output/x86_64-w64-mingw32/SHA256SUMS.part
24fdaeea7e6f2884ef49f901718d0e1d4a81768fa63d5de49ef47357470cfa2197  guix-build-29173d6c6ca0/output/x86_64-w64-mingw32/bitcoin-29173d6c6ca0-win-unsigned.tar.gz
2533dd8a2b69f7cdf3aa05df2b39908483ec07affb8034a1f2f5a76ebca2877389  guix-build-29173d6c6ca0/output/x86_64-w64-mingw32/bitcoin-29173d6c6ca0-win64-debug.zip
26e724eda8888fa2017430abb50fb146c934ec686cde13a555835dfc33ae228a70  guix-build-29173d6c6ca0/output/x86_64-w64-mingw32/bitcoin-29173d6c6ca0-win64-setup-unsigned.exe
272adf2e26c2faf588078822b0b41601f5aabdfabd9c998de4e50b325bd9e3ef36  guix-build-29173d6c6ca0/output/x86_64-w64-mingw32/bitcoin-29173d6c6ca0-win64.zip

fanquake merged this on Nov 12, 2021

fanquake closed this on Nov 12, 2021

fanquake removed this from the "Blockers" column in a project

fanquake deleted the branch on Nov 12, 2021

sidhujag referenced this in commit 7fa0e71083 on Nov 12, 2021

dekm referenced this in commit c61f8f651d on Oct 27, 2022

DrahtBot locked this on Nov 12, 2022

Add minisketch subtree and integrate into build/test #23114

Conflicts