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.
MarcoFalke
commented at 7:28 am on May 5, 2021:
member
From ci:
01SUMMARY: MemorySanitizer: use-of-uninitialized-value /tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/minisketch/src/fields/clmul_common_impl.h:23:23 in unsigned int (anonymous namespace)::MulWithClMulReduce<unsigned int, 32, 141u>(unsigned int, unsigned int)
2 ORIGIN: invalid (0). Might be a bug in MemorySanitizer origin tracking.
3 This could still be a bug in your code, too!
sipsorcery
commented at 2:31 pm on May 5, 2021:
member
Attached diff adds a minisketch project to the msvc build config. I did make a few small code changes to minisketch.h and minisketch.cpp to remove a warning and change the location for a header.
DrahtBot added the label
Needs rebase
on May 5, 2021
jnewbery
commented at 9:56 am on May 6, 2021:
member
Do minisketch’s own tests get run when running make check from bitcoin’s base directory? I think it’d be good to modify make check to only run the base bitcoin tests, and then have another build target (make check_all?) that also runs the subtree unit tests. Those subtrees only get updated every few months. I expect many developers run make check many times a day and it seems wasteful to rerun the same unmodified tests on the same unmodified subtrees every time.
MarcoFalke
commented at 10:12 am on May 6, 2021:
member
CI would need to run them, though. As this is the only place where sanitizers are run regularly.
sipa force-pushed
on May 7, 2021
sipa force-pushed
on May 7, 2021
sipa force-pushed
on May 7, 2021
sipa force-pushed
on May 7, 2021
sipa force-pushed
on May 7, 2021
sipa force-pushed
on May 7, 2021
sipa force-pushed
on May 7, 2021
sipa force-pushed
on May 7, 2021
DrahtBot removed the label
Needs rebase
on May 7, 2021
sipa force-pushed
on May 7, 2021
sipa force-pushed
on May 7, 2021
DrahtBot
commented at 9:10 am on May 7, 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:
#22646 ([POC] Tighter Univalue integration, remove --with-system-univalue by fanquake)
#21515 (Erlay: bandwidth-efficient transaction relay protocol by naumenkogs)
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.
MarcoFalke
commented at 9:18 am on May 7, 2021:
member
Failure on arm: ./build-aux/test-driver: line 107: ./test-verify: cannot execute binary file: Exec format error
You might have to modify the ./ci/test/wrap-qemu.sh script.
At least one issue remains: when running the minisketch tests, wine can’t find libgcc and other dlls. In minisketch’s own CI that’s worked around by passing CXXFLAGS=-static -static-libgcc -static-libstdc++, but it’s a bit ugly to pass that through to the sub-configure (a) only for the win64 cirrus build and (b) without doing that for non-minisketch targets. Anyone have a suggestion?
Make wine find the necessary dll’s somehow?
Just pass CXXFLAGS=-static -static-libgcc -static-libstdc++ in general to the win64 cirrus configure?
I have no idea how src/test/test_bitcoin.exe avoids this problem, but perhaps its solution is usable too?
practicalswift
commented at 8:22 pm on May 7, 2021:
contributor
Concept ACK
Very nice work sipa, gmaxwell and naumenkogs!
Is it mentioned somewhere in the documentation that Minisketch::Add is not an idempotent operation?
In other words that …
0sketch.Add(i);
… does not have the same effect as …
0sketch.Add(i);
1sketch.Add(i);
FWIW I couldn’t find any such note in src/minisketch/include/minisketch.h :)
@practicalswift It’s explained in https://github.com/sipa/minisketch/#readme at least, and inherent to symmetric set reconciliation. I don’t think the header file should try to explain set reconciliation in detail, but if you have specific suggestions to improve the header, feel free to PR them (in the minisketch repo).
practicalswift
commented at 9:57 pm on May 7, 2021:
contributor
@practicalswift It’s explained in https://github.com/sipa/minisketch/#readme at least, and inherent to symmetric set reconciliation. I don’t think the header file should try to explain set reconciliation in detail, but if you have specific suggestions to improve the header, feel free to PR them (in the minisketch repo).
I think the following should be enough to help avoid unnecessary mistakes in calling code in the hypothetical scenario that the library user is not familiar with set reconciliation details. Submitted as https://github.com/sipa/minisketch/pull/38.
0diff --git a/include/minisketch.h b/include/minisketch.h
1index d73123d..23af18f 100644
2--- a/include/minisketch.h
3+++ b/include/minisketch.h
4@@ -104,6 +104,8 @@ void minisketch_deserialize(minisketch* sketch, const unsigned char* input);
5 * If the element to be added is 0 (after potentially dropping the most significant
6 * bits), then this function is a no-op. Sketches cannot contain an element with
7 * the value 0.
8+ *
9+ * Note that adding the same element a second time removes it again.
10 */
11 void minisketch_add_uint64(minisketch* sketch, uint64_t element);
1213@@ -246,7 +248,7 @@ public:
14 return *this;
15 }
1617- /** See miniksetch_add_element(). */
18+ /** See minisketch_add_uint64(). */
19 Minisketch& Add(uint64_t element) noexcept
20 {
21 minisketch_add_uint64(m_minisketch.get(), element);
sipa force-pushed
on May 7, 2021
sipa force-pushed
on May 8, 2021
sipa force-pushed
on May 8, 2021
sipa force-pushed
on May 8, 2021
practicalswift
commented at 3:12 pm on May 8, 2021:
contributor
Another interface design question:
The Minisketch constructor does not signal constructor failure by throwing.
Is that intentional to allow for use in non-Bitcoin Core environments where using exceptions may not be an option?
I’m a bit worried that the current design might introduce a gotcha/sharp edge which is probably best illustrated by the example below.
To be clear: I understand there is a trade-off here and perhaps this gotcha is a price worth paying for a potentially larger user base of the library outside of Bitcoin Core, but I just want to make sure I fully understand the rationale behind the current interface design :)
Highly optional review club style quiz (target audience: reviewers and library users :))
After reading the documentation in include/minisketch.h a library user might write the following code:
The library user is happy with his/her code: he/she gets the expected results when testing it using a couple of thousand normal test cases. Symmetric set reconciliation is fun! :)
However, the library user becomes a bit sad when an attacker shows up and provides a carefully crafted input which causes a nullptr dereference.
Review club style quiz questions:
What is the attacker input that caused the nullptr dereference?
Where does the nullptr dereference take place?
Did the library user miss anything of importance when reading the documentation in include/minisketch.h?
What is the conventional approach to construction failure and what is the “zombie object” approach? When/why is the latter approach used?
@practicalswift You mean because the construction internally OOMs? If that happens you have bigger problems, I think, as you’d generally use this with capacities of 10s to maybe 1000s. Beyond that, O(n^2) decoding cost starts to make it unusable.
sipa force-pushed
on May 8, 2021
sipa force-pushed
on May 8, 2021
practicalswift
commented at 5:41 pm on May 8, 2021:
contributor
You mean because the construction internally OOMs? If that happens you have bigger problems, I think, as you’d generally use this with capacities of 10s to maybe 1000s. Beyond that, O(n^2) decoding cost starts to make it unusable.
@sipa No, note that the user code in the example is very careful about not processing large inputs, so memory exhaustion or excessive run-time is not the problem here.
The if (remote_capacity > MAX_SKETCH_CAPACITY) { guards against large inputs:
@practicalswift You can use if (sketch) to detect if a sketch is usable, which may be the case for several reasons (field not implemented, implementation number too high or incompatible with field, illegal capacity, OOM, …).
You can use if (sketch) to detect if a sketch is usable, which may be the case for several reasons (field not implemented, implementation number too high or incompatible with field, illegal capacity, OOM, …).
Thanks for updating the documentation. Now the gotcha is documented: that is better :)
I’m aware that operator bool() can be used to check if a Minisketch object is a valid object or a zombie object: I’m just afraid that there is a real risk of “use-before-zombie-check” errors.
My experience is that signalling constructor failure by silently creating a zombie object (instead of throwing) leads to fragile code. Most C++ programmers are used to constructors that either create a fully valid object or throw. Even if the programmer is aware that the somewhat unusual “zombie check idiom” is used it is very easy to miss checking it in at least some code path.
See the current Erlay code txreconciliation.cpp (#21515) as an example. Not all code paths do “zombie checking” using operator bool() before using a newly created Minisketch object.
If we were throwing instead of creating a zombie object in case of constructor failure we wouldn’t have to worry about a potential nullptr dereference here.
That’s why I’m curious about this interface design choice to better understand the trade-offs considered: are we intentionally avoiding throwing to allow for use in non-Bitcoin Core environments where using exceptions may not be an option, or am I missing some other reason for this design choice? :)
@practicalswift Exceptions in my opinion are for exceptional situations - things that couldn’t have been reasonably prevented by the programmer (things like I/O failure, for example), as they can be deep down in a function call stack, and dealing with them along the way there is both inconvenient and pointless. Except for OOM perhaps, none of the cases where Minisketch construction fails are like this - they all indicate the programmer is doing something wrong. It wouldn’t be unreasonable to have assertions for them instead, I guess. OOM is a bit different as it is an exceptional situation, but it’s also one that can’t occur realistically (due to the size of sketches libminisketch can work with) and is almost always a nothing-can-be-done-about-this situation (you’d just terminate as ~all allocations will fail).
MarcoFalke added the label
Needs gitian build
on May 9, 2021
MarcoFalke added the label
Needs Guix build
on May 9, 2021
practicalswift
commented at 10:31 pm on May 9, 2021:
contributor
Assuming that we really don’t want to throw in the constructor:
Perhaps an alternative could be to use the named constructor idiom and return std::optional<Minisketch>? (With std::nullopt being returned if a valid/usable Minisketch object could not constructed.)
To be precise the situation I’m worried about with the current design is when capacity in Minisketch(uint32_t bits, uint32_t implementation, size_t capacity) is indirectly attacker controlled via the attacker provided serialized sketch, and the programmer forgets to check the possibility of a zombie state Minisketch object before using it. Note that if capacity is 0 then an invalid zombie state Minisketch object is created, and using such an invalid Minisketch object will cause a nullptr dereference as the library is currently written.
Note that the programmer is likely to check for a “too large” sketch: he/she is likely to intuitively understand that such a thing might be dangerous, but the fact that a “too small” sketch is dangerous too is a real gotcha IMO :)
Exceptions in my opinion are for exceptional situations - things that couldn’t have been reasonably prevented by the programmer (things like I/O failure, for example), as they can be deep down in a function call stack, and dealing with them along the way there is both inconvenient and pointless.
Thanks for sharing your perspective. I know you’re well aware of all the usual counterarguments, but I’m sharing some links to other perspectives for reviewers who might be unaware :)
Perhaps an alternative could be to use the named constructor idiom and return std::optional
I think that’s rather silly, because that’s effectively what a Minisketch object already is. It is a simple wrapper around std::unique_ptr, and behaves exactly like that (except that the internal object is not accessible).
practicalswift
commented at 10:49 pm on May 9, 2021:
contributor
0Minisketch sketch{32, 0, /* likely to be attacker controlled */ 0};
1sketch.GetCapacity(); // or really any operation on the invalid Minisketch zombie object
… currently yields …
0==30177==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000008 (pc 0x55a2bc704dcb bp 0x7ffe524b6070 sp 0x7ffe524b6040 T0)
1==30177==The signal is caused by a READ memory access.2==30177==Hint: address points to the zero page.3 [#0](/bitcoin-bitcoin/0/) 0x55a2bc704dcb in Sketch::Check() const /home/thomas/bitcoin/src/minisketch/src/sketch.h:24:394 [#1](/bitcoin-bitcoin/1/) 0x55a2bc704dcb in minisketch_capacity /home/thomas/bitcoin/src/minisketch/src/minisketch.cpp:368:85 [#2](/bitcoin-bitcoin/2/) 0x55a2bb3fc61b in Minisketch::GetCapacity() const ./minisketch/include/minisketch.h:239:506…
is equally going to cause problems, if the API user isn’t aware the create call can fail. And when those problems appear, it’ll be obvious where the problem is.
Perhaps a better question is: would removing the capacity==0 edge case not solve more problems?
is equally going to cause problems, if the API user isn’t aware the create call can fail.
is certainly different from returning a bare object that may be in a valid or invalid state. Unwrapping an optional without first checking that it contains a value is very clearly a bug, and should be obvious to any programmer or compiler, even if they don’t know the semantics of the library function that is being called.
sipa referenced this in commit
ba7905f91e
on May 10, 2021
@jnewbery Sure, it’s better at conveying to the API user that the call may fail. But I think that’s the wrong information: it’ll only fail when used incorrectly (*). It’s not something the user should be checking for in the first place - what would be done at runtime with that information? The only thing that needs to happen is fixing the code. Putting an optional around it adds both unnecessary overhead, and the wrong signal IMO.
(*) I admit that capacity=0 was an edge case that could occur at runtime, and would be unexpected. Just merged https://github.com/sipa/minisketch/pull/40 to fix that, will update this PR to reflect that.
practicalswift
commented at 2:13 pm on May 11, 2021:
contributor
Thanks for addressing the capacity=0 edge case. That resolves my concern.
I’m not particularly worried about the other two constructor failure cases (std::bad_alloc and unavailable combination of bits/implementation) since the conditions triggering them are much less likely to be under attacker control.
sipa force-pushed
on May 11, 2021
DrahtBot removed the label
Needs Guix build
on May 12, 2021
MarcoFalke
commented at 2:59 pm on May 12, 2021:
member
0+ make -C src --jobs=1 check-symbols V=1 1make: Entering directory '/distsrc-base/distsrc-202a89b644f0-x86_64-linux-gnu/src' 2Checking glibc back compat... 3CPPFILT=/root/.guix-profile/bin/x86_64-linux-gnu-c++filt /root/.guix-profile/bin/python3.8../contrib/devtools/symbol-check.py bitcoind bitcoin-cli bitcoin-tx bitcoin-wallet bitcoin-util test/test_bitcoin qt/bitcoin-qt
4bitcoind: export of symbol typeinfo for std::ios_base::failure[abi:cxx11] not allowed
5bitcoind: export of symbol VTT for std::basic_ifstream<char, std::char_traits<char>>not allowed
6bitcoind: export of symbol vtable for std::basic_streambuf<char, std::char_traits<char>>not allowed
7bitcoind: export of symbol std::__cxx11::basic_stringbuf<char, std::char_traits<char>, std::allocator<char>>::~basic_stringbuf() not allowed
8bitcoind: export of symbol typeinfo for std::_V2::error_category not allowed
9bitcoind: export of symbol typeinfo for std::invalid_argument not allowed
10bitcoind: export of symbol vtable for std::basic_ifstream<char, std::char_traits<char>>not allowed
11bitcoind: export of symbol typeinfo for std::out_of_range not allowed
12bitcoind: export of symbol std::__cxx11::basic_stringbuf<char, std::char_traits<char>, std::allocator<char>>::~basic_stringbuf() not allowed
13bitcoind: export of symbol std::cerr not allowed
14bitcoind: export of symbol vtable for std::basic_filebuf<char, std::char_traits<char>>not allowed
15bitcoind: export of symbol typeinfo for std::future_error not allowed
16bitcoind: export of symbol vtable for std::__cxx11::basic_stringbuf<char, std::char_traits<char>, std::allocator<char>>not allowed
17bitcoind: export of symbol vtable for std::__cxx11::basic_istringstream<char, std::char_traits<char>, std::allocator<char>>not allowed
18bitcoind: export of symbol std::__cxx11::basic_stringbuf<char, std::char_traits<char>, std::allocator<char>>::~basic_stringbuf() not allowed
19bitcoind: export of symbol typeinfo for std::logic_error not allowed
20bitcoind: export of symbol VTT for std::__cxx11::basic_stringstream<char, std::char_traits<char>, std::allocator<char>>not allowed
21bitcoind: export of symbol std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>::_M_replace(unsigned long, unsigned long, char const*, unsigned long) not allowed
22bitcoind: export of symbol vtable for std::future_error not allowed
23bitcoind: export of symbol typeinfo for std::runtime_error not allowed
24bitcoind: export of symbol std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>::_M_assign(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>const&) not allowed
25bitcoind: export of symbol std::nothrow not allowed
26bitcoind: export of symbol vtable for std::__cxx11::basic_stringstream<char, std::char_traits<char>, std::allocator<char>>not allowed
27bitcoind: export of symbol std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>::_M_mutate(unsigned long, unsigned long, char const*, unsigned long) not allowed
28bitcoind: export of symbol std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>::_M_append(char const*, unsigned long) not allowed
29bitcoind: export of symbol vtable for std::__cxx11::basic_ostringstream<char, std::char_traits<char>, std::allocator<char>>not allowed
30bitcoind: export of symbol VTT for std::__cxx11::basic_istringstream<char, std::char_traits<char>, std::allocator<char>>not allowed
31bitcoind: export of symbol vtable for std::bad_alloc not allowed
32bitcoind: export of symbol typeinfo for std::bad_alloc not allowed
33bitcoind: export of symbol std::ctype<char>::do_widen(char) constnot allowed
34bitcoind: export of symbol vtable for std::basic_ios<char, std::char_traits<char>>not allowed
35bitcoind: export of symbol typeinfo for std::locale::facet not allowed
36bitcoind: export of symbol vtable for std::system_error not allowed
37bitcoind: export of symbol VTT for std::__cxx11::basic_ostringstream<char, std::char_traits<char>, std::allocator<char>>not allowed
38bitcoind: export of symbol typeinfo for long not allowed
39bitcoind: export of symbol vtable for std::ios_base::failure[abi:cxx11] not allowed
40bitcoind: export of symbol typeinfo for short not allowed
41bitcoind: export of symbol typeinfo for unsigned short not allowed
42bitcoind: export of symbol std::cout not allowed
43bitcoind: export of symbol typeinfo for void not allowed
44bitcoind: export of symbol std::num_get<char, std::istreambuf_iterator<char, std::char_traits<char>>>::id not allowed
45bitcoind: export of symbol void std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>::_M_construct<char const*>(char const*, char const*, std::forward_iterator_tag) not allowed
46bitcoind: export of symbol void std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>::_M_construct<char*>(char*, char*, std::forward_iterator_tag) not allowed
47bitcoind: export of symbol vtable for std::num_get<char, std::istreambuf_iterator<char, std::char_traits<char>>>not allowed
48bitcoind: NEEDED library libstdc++.so.6 is not allowed
49bitcoind: failed EXPORTED_SYMBOLS LIBRARY_DEPENDENCIES
Oh, I see. I thought it was a clarification on why it’s complaining about missing libraries (but it may well be related).
The build people will have to take a look.
The great miners and craftsmen of the mountain halls?
sipa force-pushed
on May 12, 2021
sipa force-pushed
on May 12, 2021
sipa force-pushed
on May 13, 2021
sipa force-pushed
on May 13, 2021
sipa force-pushed
on May 13, 2021
practicalswift
commented at 7:05 am on May 13, 2021:
contributor
cr ACKb195ae3af078a9038c7d654a267eb14b9332ae70 modulo CI green: patch looks correct, minisketch is awesome and changes are limited to Makefile.am, build_msvc/, ci/, configure.ac, src/Makefile.*, src/minisketch/, src/minisketchwrapper.cpp, src/minisketchwrapper.h, src/test/minisketch_tests.cpp and test/lint/.
sipa force-pushed
on May 13, 2021
sipa force-pushed
on May 14, 2021
DrahtBot removed the label
Needs gitian build
on May 14, 2021
MarcoFalke deleted a comment
on May 14, 2021
sipa force-pushed
on May 15, 2021
sipa referenced this in commit
4c1d32bfd4
on May 16, 2021
sipa force-pushed
on May 16, 2021
sipa added the label
Needs gitian build
on May 16, 2021
sipa added the label
Needs Guix build
on May 16, 2021
practicalswift
commented at 3:49 pm on May 16, 2021:
contributor
cr re-ACK35049cf2a16a63bd1adf511e8c0ac526be5e4e8a CI now green, patch looks correct, minisketch is still awesome and changes are limited to Makefile.am, build_msvc/, ci/, configure.ac, src/Makefile.*, src/minisketch/, src/minisketchwrapper.cpp, src/minisketchwrapper.h, src/test/minisketch_tests.cpp and test/lint/.
DrahtBot removed the label
Needs gitian build
on May 17, 2021
in
src/minisketchwrapper.cpp:8
in
35049cf2a1outdated
0@@ -0,0 +1,74 @@
1+// Copyright (c) 2021 The Bitcoin Core developers
2+// Distributed under the MIT software license, see the accompanying
3+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4+
5+#include <minisketchwrapper.h>
6+
7+#include <minisketch.h>
8+#include <logging.h>
9+#include <util/time.h>
jnewbery
commented at 11:13 am on May 20, 2021:
member
utACK35049cf2a1
Only reviewed src/minisketchwrapper and src/test/minisketch_tests. Left a few very minor comments that should be ignored unless you need to retouch this branch for any reason.
DrahtBot removed the label
Needs Guix build
on Jun 1, 2021
It appears that linking in libminisketch causes bitcoind and other binaries to suddenly export(?) libstdc++ symbols. This is beyond my skills, I humbly request the services of the Build People.
TheCharlatan
commented at 6:34 pm on June 3, 2021:
member
Edit: Disregard, seems to be an issue with all posted guix builds, so unrelated to minisketch.
Didn’t find anything about libstdc++ being included in the bitcoind binary, but on Ubuntu 18.04 running ldd bitcoind on the provided guix binaries errors on:
0./bitcoind: /lib/x86_64-linux-gnu/libm.so.6: version `GLIBC_2.29' not found (required by ./bitcoind)
1./bitcoind: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.28' not found (required by ./bitcoind)
I guess these need to be wrapped in compat/glibc_compat.cpp? I’m not sure if wrapping glibc functionality is still the workaround used currently. If so, there’s a stackoverflow answer detailing the wrapping of fcntl64: https://stackoverflow.com/questions/58472958/how-to-force-linkage-to-older-libc-fcntl-instead-of-fcntl64/58472959#58472959 . I guess log, pow and exp could be wrapped in the same way log2f is currently wrapped, they are also provided by GLIBC_2.2.5 on x86_64 (though I don’t know about the other architectures, might be a different version for arm).
fanquake
commented at 1:14 am on June 4, 2021:
member
Edit: Disregard, seems to be an issue with all posted guix builds, so unrelated to minisketch.
Indeed, this is #21454, which does need fixing, but is not introduced by this PR.
Well, there is still something making the guix build fail, with this in guix_build.log, which isn’t in master’s build:
0Checking glibc back compat...1Checking glibc back compat...2CPPFILT=/root/.guix-profile/bin/x86_64-linux-gnu-c++filt /root/.guix-profile/bin/python3.8../contrib/devtools/symbol-check.py bitcoind bitcoin-cli bitcoin-tx bitcoin-wallet bitcoin-util test/test_bitcoin qt/bitcoin-qt
3bitcoind: export of symbol typeinfo for std::ios_base::failure[abi:cxx11] not allowed
4...
fanquake
commented at 12:35 pm on June 4, 2021:
member
Well, there is still something making the guix build fail,
Given the symbols that are being exported, is this be some sort of C++ version/ABI incompatibility problem? Will have a closer look shortly.
DrahtBot added the label
Needs rebase
on Jun 7, 2021
sipa force-pushed
on Jul 2, 2021
sipa added the label
Needs Guix build
on Jul 2, 2021
sipa
commented at 11:52 pm on July 2, 2021:
member
I still get these failures in guix that I can’t explain. @dongcarl@fanquake
0qt/bitcoin-qt: symbol operator delete[](void*, unsigned long) from unsupported version CXXABI_1.3.91qt/bitcoin-qt: symbol std::basic_istream<char, std::char_traits<char>>& std::getline<char, std::char_traits<char>, std::allocator<char>>(std::basic_istream<char, std::char_traits<char>>&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>&, char) from unsupported version GLIBCXX_3.4.212qt/bitcoin-qt: symbol std::basic_streambuf<char, std::char_traits<char>>::pbackfail(int) from unsupported version GLIBCXX_3.43qt/bitcoin-qt: symbol std::allocator<char>::allocator(std::allocator<char>const&) from unsupported version GLIBCXX_3.44...
fanquake
commented at 8:58 am on July 6, 2021:
member
I still get these failures in guix that I can’t explain. @dongcarl@fanquake
(don’t merge this yet, as it includes the as-of-yet unmerged sipa/minisketch#44)
DrahtBot added the label
Needs rebase
on Jul 7, 2021
laanwj added this to the "Blockers" column in a project
in
src/minisketch/include/minisketch.h:76
in
f0d322d277outdated
71+MINISKETCH_API minisketch* minisketch_create(uint32_t bits, uint32_t implementation, size_t capacity);
72+
73+/** Get the element size of a sketch in bits. */
74+MINISKETCH_API uint32_t minisketch_bits(const minisketch* sketch);
75+
76+/** Get the capacity of a sketch. */
Reading from the fuzzy paper “Codes and Syndromes”, should one interpret the capacity as the error-correcting distance C (here instantiated as binary BCH codes) ?
Further the documentation says the decoding is always successful when the number of elements in the set is not higher than the capacity, though in fact set size != sketch capacity, as afaiu 0 element are pruned out of the sketch, so shouldn’t documentation says that decoding can be successful even in set size > sketch capacity ?
The distance of the implicit BCH code is 2C+1. I don’t understand the rest of what you’re trying to say.
EDIT: I was wrong earlier; the distance is 2C+1, not C+1.
in
src/minisketch/include/minisketch.h:93
in
f0d322d277outdated
88+ * integer is acceptable, regardless of field size).
89+ *
90+ * When seed is -1, a fixed internal value with predictable behavior is
91+ * used. It is only intended for testing.
92+ */
93+MINISKETCH_API void minisketch_set_seed(minisketch* sketch, uint64_t seed);
IIUC, sketches are initialized by default with std::random_device. If a user has a better source of randomness rather than this implementation-defined pseudo-random number generator, it should rather rely on it ?
If so, I think comment could be clearer about when a user should decide between default random seed and user-provided value.
in
src/minisketch/include/minisketch.h:121
in
f0d322d277outdated
116+/** Add an element to a sketch.
117+ *
118+ * If the element to be added is too large for the sketch, the most significant
119+ * bits of the element are dropped. More precisely, if the element size of
120+ * `sketch` is b bits, then this function adds the unsigned integer represented
121+ * by the b least significant bits of `element` to `sketch`.
Maybe you should point out to protocoltips.md, that’s the only other documentation place where collisions and their risks are explained ?
Zooming out, what’s the collision model we care for Erlay ? I think there was an irc discussion a while back pointing that malicious inputs provoking collisions don’t really matter as if your peer want to fail transaction announcement there is a reduction to stay silent. So it’s more about accidental collisions, what’s the probability here with 32-bit elements, (2^32 / 2^256)^(set _size) ?
This isn’t Bitcoin Core, and I think this is the the most ideomatic approach (especially with the explicit which avoids accidental conversions).
in
src/minisketch/include/minisketch.h:271
in
f0d322d277outdated
266+ {
267+ m_minisketch = std::unique_ptr<minisketch, Deleter>(minisketch_create(bits, implementation, capacity));
268+ }
269+
270+ /** Create a Minisketch object sufficiently large for the specified number of elements at given fpbits.
271+ * It may construct an invalid object, which you may need to check for. */
nit: make the “may” a “must”, at least I interpret the requirement on the non-wrapped construction already as a must “Use operator bool() to check that this isn’t the case before performing any other operations”
See the comment above, which describes the conditions under which an invalid object may be constructed. There are reasonable use cases where you don’t need to check (you already made sure the fieldsize/implementation combination is supported, and you’re ok with treating OOM as a fatal error).
ariard
commented at 1:02 am on July 15, 2021:
member
Let me know if you prefer I review against the source repository.
fanquake
commented at 5:53 am on July 16, 2021:
member
After some discussion with @theuni, we are going to take a different approach to integrating the minisketch subtree, than what is currently proposed here. The new approach will be result in a somewhat cleaner integration, remove the need for running a sub-configure, as well as ensure we are building the minisketch library only using Bitcoin Cores build options, compiler flags etc. I expect there will be a branch demoing the approach available shortly.
It could also be expected that we will follow suit with our other subtrees.
theuni
commented at 2:55 pm on July 16, 2021:
member
That’s a little more definitive than I would’ve put it, but yes, my preference would be tighter integration for the reasons @fanquake mentioned.
@sipaHere’s my original POC demonstrating what I had in mind, matching the approach I’ve suggested for univalue (https://github.com/bitcoin-core/univalue/pull/19). I’ve started working on a more complete version for minisketch, but I’d like to make sure you’re not opposed to doing it that way first. If you’re good with it I can finish up in the next day or two.
sipa
commented at 7:20 pm on July 17, 2021:
member
DrahtBot removed the label
Needs rebase
on Jul 17, 2021
DrahtBot added the label
Needs rebase
on Jul 20, 2021
theuni
commented at 4:29 pm on July 20, 2021:
member
@sipa Is building the non-verify version of the lib and tests sufficient for Core? Or is it useful/necessary to run the -verify version as well along with our tests?
sipa
commented at 7:15 pm on July 20, 2021:
member
@theuni If it’s an issue, I think non-verify is sufficient. The verify mode mostly adds algorithmic property checks, not things that I’d expect to be very architecture/build dependent.
theuni
commented at 8:22 pm on July 20, 2021:
member
It’s not much of an issue, it’s just kinda hacky to build everything twice, especially if it’s unlikely to be as useful as it is running in the upstream tests. I can add it back if there’s a need.
See here for a current integration branch: https://github.com/theuni/bitcoin/commits/minisketch-split . Not sure if it’s easier for you to integrate that into this PR or for me to pull your other changes in on top of mine? I’m happy to do the latter if you’d like.
in
src/minisketch/src/sketch_impl.h:386
in
cf4897c0efoutdated
GeneFerneau
commented at 7:15 pm on July 30, 2021:
May be helpful to add a fuzz harness for sketch deserialization. A large number of security bugs come from deserializing untrusted data.
fanquake
commented at 7:28 am on August 12, 2021:
member
I’ve put together a branch for this. It’s based off current master and includes all the latest changes from upstream minisketch, as well as integrating the changes here with @theuni’s build changes. It’s available here: https://github.com/fanquake/bitcoin/tree/minisketch_integration.
Note that I’ve included some of the review suggestions, as well as squashed one commit (https://github.com/theuni/bitcoin/commit/2fff4ce130ee11bc075e7a50354ce92db26795c2) from Corys branch. I’ve also made some additions to Makefile.minisketch.include, and pruned some unneeded changes from 8311cea203be8b61ae04b37bd323ab2323290180. Also dropped the use of BasicTestingSetup from the added minisketch test.
I’ve opened an issue upstream, https://github.com/sipa/minisketch/issues/46, as now that we’ve got -Wimplicit-fallthrough turned on, we either need to annotate fallthroughs, or suppress the warnings. i.e:
0minisketch/src/minisketch.cpp:104:13: warning: unannotated fall-through between switch labels [-Wimplicit-fallthrough] 1case 2:
2 ^
3minisketch/src/minisketch.cpp:104:13: note: insert '[[fallthrough]];' to silence this warning
4case 2:
5 ^
6[[fallthrough]];
7minisketch/src/minisketch.cpp:104:13: note: insert 'break;' to avoid fall-through
8case 2:
9 ^
10 break;
Squashed 'src/minisketch/' content from commit ea986a869
Merge commit 'faea0b7da0d4cad1856cc669e65e1f643b60354c' as 'src/minisketch'58bcf74e18
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.
1a64c4ef2e
build: add minisketch build file and include it3f841218ff
build: link minisketch into bitcoind85ca7b955d
Add MSVC build configuration for libminisketch0f12876d66
Add minisketch dependency2e5d0cc427
Add basic minisketch testse696deae5f
Add thin Minisketch wrapper to pick best implementation238bf6e8bd
fanquake
commented at 4:55 am on September 16, 2021:
member
theuni
commented at 8:10 pm on September 21, 2021:
Pretty sure there’s no need for this since we’re building it ourselves. IIRC including it here was problematic while I was testing, but I’ve forgotten why.
fanquake
commented at 1:05 am on September 22, 2021:
Yea this isn’t needed, and was breaking make dist. Have dropped it from my branch.
fanquake
commented at 1:05 am on September 22, 2021:
member
This is a metadata mirror of the GitHub repository
bitcoin/bitcoin.
This site is not affiliated with GitHub.
Content is generated from a GitHub metadata backup.
generated: 2024-07-03 10:13 UTC
This site is hosted by @0xB10C More mirrored repositories can be found on mirror.b10c.me
