Avoid pre-compressing points and remove the need for operator< #29

codablock · 2018-09-21T07:09:57Z

operator< was the only reason why BLSSignature and BLSPublicKey had too keep internal serialized data up-to-data. This required calling of CompressPoint even if the data was never actually needed.

This PR is a set of refactorings which in the end remove the need for operator< and then finally removes the operator and the data field.

It also includes a few other refactorings to reduce the amount of copying and serialization needed when sorting public keys and signatures. There is also a fix for a memory leak included.

I also removed the stl-like api (begin/end/size) as the classes were probably never intended to be used in a stl-compatible manner (and thus should not imply compatibility if there is none really). I had to change the python tests for this, but could not test these changes as tests currently fail on master as well.

The result of this PR is that copying and moving around signatures and public keys gets a lot faster. We rely on this to be fast internally as we use a lot of paralellism where ownership of objects is important.

42f4660 is a fix for relic, which I also create a PR for in relic.

mariano54 · 2018-09-21T14:56:48Z

Python bindings tests are passing on my machine

mariano54 · 2018-09-21T14:15:02Z

src/aggregationinfo.cpp

        }
    }
    // Pks are sorted by message then pk
-    std::sort(begin(sortedKeys), end(sortedKeys), BLSUtil::BytesCompare80());


Are we using BytesCompare80 anymore? If not we can remove it from BLSUtil

still used in SortIntoVectors

mariano54 · 2018-09-21T14:18:46Z

src/blspublickey.cpp

 }

-const uint8_t* BLSPublicKey::begin() const {
+std::vector<uint8_t> BLSPublicKey::Serialize() const {


Why do we need a second serialize method?

for convenience (otherwise you'd have to do std::vector<uint8_t> b; b.resize(size); pk.Serialize(b.data())

as a replacement when begin/end/size was needed (which I removed).

mariano54 · 2018-09-21T14:20:04Z

src/bls.cpp

    bn_new(order);
    g2_get_ord(order);

+    std::vector<uint8_t> pkBuffer;


Why use a vector here instead of the array?

array seems cleaner and more consistent with the rest of the code

And other places where arrays are replaced by vectors

With arrays you mean dynamically allocated arrays as used before or std::array?

I prefer the use of std::vector<uint8_t> over new[] whenever possible. I actually prefer to not use new/new[] at all, simply because it is one of the main sources for memory related bugs. The memory leak that I fixed in fdf15f9 was such an example. With std::vector you've generally on the secure side of things and also get a lot of flexibility (e.g. everything from std can be used, or the < which makes sorting simpler). You also have better control about ownership of buffers/arrays, as you can always pass around ownership with std::move/std::swap.

About consistency: I noticed this as well and actually started a refactoring of all places where new[] was used...but stopped in the middle as it got too much. Would you consider using std::vector in the future (for all new things) and gradually move new[] to std::vector step by step?

Yes I tend to use arrays as I'm more used to c, I prefer simpler language features, but this rationale makes sense. @fchirica what do you think about this approach?

Is there any performance overhead for using vectors?

With modern C++ (starting with C++11), the overhead is neglectable. Only when iterating byte-by-byte, you'd be able to measure a performance impact. But usually, you'd use stuff from std:: to perform operations, which all have specialized implementations to work fast on primitive data types.

It's however very important to pass vectors by reference, as otherwise you end up copying them over and over. Returning vectors by-value depends on the place it is used. If the vector is from the stack, the C++ compiler will will use return value optimization (avoiding a copy). If you return a member variable, it will be copied.

If you put vectors in maps or other vectors, always use m.emplace(k, vec) and v2.emplace_back(vec). If the vector is not required after adding it to another container, use m.emplace(std::move(vec)) and v2.emplace_back(std::move(vec)), which will basically swap (very fast) the contents of the inserted vector into the new position in the target container. Generally, always prefer emplace over push/insert (it avoids unnecessary copies).

If using vectors in vectors, make sure to v.reserve(expectedSize) in advance, otherwise it might end up copying stuff unnecessarily.

@codablock do you have some backup for the negligible overhead of std::vector with C++11?
Another alternative is to use std::unique_ptr. This avoids the memory bugs and ensures that the size is set and fixed for all time. Thus making the code easier to understand than using std::vector (across the board) where the size could be set at any place or time. With std::vector it can be harder to know whether additional elements have been added or not later.

mariano54 · 2018-09-21T14:35:59Z

src/bls.cpp

-    uint8_t *pkBuffer = new uint8_t[BLSPublicKey::PUBLIC_KEY_SIZE
-                                    * (pubKeys.size())];
+                      std::vector<std::vector<uint8_t>> const &serPubKeys,
+                      std::vector<size_t> const& sorted) {


Maybe rename sorted to sortedIndeces

mariano54 · 2018-09-21T14:38:50Z

src/blssignature.hpp

    // Serializes ONLY the 96 byte public key. It does not serialize
    // the aggregation info.
    void Serialize(uint8_t* buffer) const;
+    std::vector<uint8_t> Serialize() const;


If we want to keep both serialize, we should also do it for other classes like ExtendedPubKey, ChainCode, etc

mariano54 · 2018-09-23T17:53:17Z

Other c++ crypto libraries I've seen, use pointers, for example https://github.com/weidai11/cryptopp.

I'm open to switching to vectors, but I think this requires more thought and should be done in a different PR, which keeps everything consistent. @codablock could you use arrays for this PR instead? This bug fix and refactoring is still definitely useful.

…td::vector

sortKey was never freed, using std::vector now. Also avoiding unnecessary copies.

Avoid unnecessary copies and serialization.

Avoid unnecessary copies and serialization

codablock · 2018-09-24T10:29:50Z

Rebased on master on added commits to revert back to uint8_t*

* feat: added back in private keys from BIP32 Seed * feat: added in unit test

mariano54 requested review from fchirica and mariano54 September 21, 2018 14:25

mariano54 closed this Sep 21, 2018

mariano54 reopened this Sep 21, 2018

mariano54 reviewed Sep 21, 2018

View reviewed changes

codablock added 12 commits September 24, 2018 12:29

Correctly initialize norm flag in ep2_set_infty

693dc72

Replace stl-like container apis with Serialize method which returns s…

572995f

…td::vector

Remove the operator< from BLSPublicKey and BLSSignature

fe35cb1

Don't pre-compress points and don't maintain serialized data

d05746f

Fix memory leak and optimize sorting in AggregateSigsSecure

75ec095

sortKey was never freed, using std::vector now. Also avoiding unnecessary copies.

Optimize sorting in SecureMergeInfos

4c2421c

Avoid unnecessary copies and serialization.

Optimize sorting in AggregateSigsInternal and remove old HashPubKeys

e81063d

Avoid unnecessary copies and serialization

Update python bindings (no size() and <)

69b3174

Rename sorted to sortedIndices

c05933c

Add "std::vector<uint8_t> Serialize() const" to other classes as well

481ad17

Deduplicate code for BLSUtil::BytesCompare

0e08972

Revert to using uint8_t* instead of std::vector<uint8_t>

6dea302

mariano54 approved these changes Sep 24, 2018

View reviewed changes

mariano54 merged commit 658b619 into Chia-Network:master Sep 24, 2018

codablock deleted the pr_noprecompress branch October 19, 2018 13:35

nmarley pushed a commit to nmarley/bls-signatures that referenced this pull request Jun 4, 2022

feat: added back in private keys from BIP32 Seed (Chia-Network#29)

c599027

* feat: added back in private keys from BIP32 Seed * feat: added in unit test

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Avoid pre-compressing points and remove the need for operator< #29

Avoid pre-compressing points and remove the need for operator< #29

codablock commented Sep 21, 2018

mariano54 commented Sep 21, 2018

mariano54 Sep 21, 2018

codablock Sep 21, 2018

mariano54 Sep 21, 2018

codablock Sep 21, 2018

mariano54 Sep 21, 2018

mariano54 Sep 21, 2018

mariano54 Sep 21, 2018

codablock Sep 21, 2018

mariano54 Sep 21, 2018

codablock Sep 21, 2018

jonspock Sep 22, 2018

mariano54 Sep 21, 2018

codablock Sep 21, 2018

mariano54 Sep 21, 2018

codablock Sep 21, 2018

mariano54 commented Sep 23, 2018

codablock commented Sep 24, 2018

Avoid pre-compressing points and remove the need for operator< #29

Avoid pre-compressing points and remove the need for operator< #29

Conversation

codablock commented Sep 21, 2018

mariano54 commented Sep 21, 2018

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

mariano54 commented Sep 23, 2018

codablock commented Sep 24, 2018