Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Slow comparison of public_key_type #375

Open
1 of 16 tasks
nathanielhourt opened this issue Aug 24, 2020 · 1 comment
Open
1 of 16 tasks

Slow comparison of public_key_type #375

nathanielhourt opened this issue Aug 24, 2020 · 1 comment

Comments

@nathanielhourt
Copy link

nathanielhourt commented Aug 24, 2020

Bug Description
public_key_type has no operator< implementation, but it can be implicitly converted to address (at the cost of a SHA512 calculation) which does. Thus any set or map keyed on public_key_type does two SHA512 calculations per operator< call. This is ridiculously slow.

Impacts
Describe which portion(s) of Peerplays may be impacted by this bug. Please tick at least one box.

  • API (the application programming interface)
  • Build (the build process or something prior to compiled code)
  • CLI (the command line wallet)
  • Deployment (the deployment process after building such as Docker, Gitlab, etc.)
  • P2P (the peer-to-peer network for transaction/block propagation)
  • Performance (system or user efficiency, etc.)
  • Protocol (the blockchain logic, consensus, validation, etc.)
  • Security (the security of system or user data, etc.)
  • UX (the User Experience)
  • Other (please add below)

Additional Context (optional)
Benching code:

BOOST_AUTO_TEST_CASE(public_key_type_comparison) {
    flat_set<public_key_type> s1;

    for (int i = 0; i < 5; ++i)
        s1.insert(fc::ecc::private_key::generate().get_public_key());

    flat_set<public_key_type, pubkey_comparator> s2(s1.begin(), s1.end());

    const int rounds = 1'000'000;

    auto start = fc::time_point::now();
    for (int i = 0; i < rounds; ++i)
        BOOST_CHECK(s1.contains(*s1.begin()));
    auto end = fc::time_point::now();

    wlog("public_key_type default comparion: ${rounds} rounds in ${ms} ms",
         ("rounds", rounds)("ms", (end-start).count()/1000));

    start = fc::time_point::now();
    for (int i = 0; i < rounds; ++i)
        BOOST_CHECK(s2.contains(*s2.begin()));
    end = fc::time_point::now();

    wlog("public_key_type proper comparion: ${rounds} rounds in ${ms} ms",
         ("rounds", rounds)("ms", (end-start).count()/1000));
}

Output:

83440ms th_a       performance_tests.cpp:67      test_method          ] public_key_type default comparion: 1000000 rounds in 5637 ms
83772ms th_a       performance_tests.cpp:75      test_method          ] public_key_type proper comparion: 1000000 rounds in 332 ms

PBSA / Developer tasks

  • Evaluate / Prioritize Bug Report
  • Refine User Stories / Requirements
  • Define Test Cases
  • Design / Develop Solution
  • Perform QA/Testing
  • Update Documentation
@nathanielhourt
Copy link
Author

nathanielhourt commented Aug 25, 2020

As it turns out, this issue has been known to BitShares for at least a couple of years and they haven't fixed it because it may affect consensus. See BitShares #2248 for more information. For this reason, it is not safe to implement the most obvious solution, as in #377. Unfortunately, it does not appear as though BitShares has identified exactly which locations of the code may be susceptible to forking if the sorting order of public_key_types is changed.

If Peerplays wishes to fix this issue, probably the safest and simplest way is to add a constructor to pubkey_comparator which takes a callback to get the current blockchain time, i.e. a std::function<fc::time_point_sec()> and call that to compare the current time against the hardfork time each time the comparator is invoked, to determine which less-than operation to use. Then all comparisons of public_key_type should be converted to use pubkey_comparator.

To find all comparisons of public_key_type, add the following to its definition, like in #377:

    template<bool OK = false>
    friend bool operator< (const public_key_type& p1, const public_key_type& p2) {
        static_assert(OK, "Use pubkey_comparator instead!");
        return false;
    }

The compiler will throw an error giving the location of each use of the operator. Convert each location to use pubkey_comparator until no errors persist.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant