Slow comparison of public_key_type

[nathanielhourt]

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)
• [x] 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]

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.