Line data    Source code

       1             : // Copyright (c) 2018-2025 The Dash Core developers
       2             : // Distributed under the MIT/X11 software license, see the accompanying
       3             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4             : 
       5             : #ifndef DASH_CRYPTO_BLS_BATCHVERIFIER_H
       6             : #define DASH_CRYPTO_BLS_BATCHVERIFIER_H
       7             : 
       8             : #include <bls/bls.h>
       9             : 
      10             : #include <map>
      11             : #include <vector>
      12             : 
      13             : template<typename SourceId, typename MessageId>
      14             : class CBLSBatchVerifier
      15             : {
      16             : private:
      17             :     struct Message {
      18             :         MessageId msgId;
      19             :         uint256 msgHash;
      20             :         CBLSSignature sig;
      21             :         CBLSPublicKey pubKey;
      22             :     };
      23             : 
      24             :     using MessageMap = std::map<MessageId, Message>;
      25             :     using MessageMapIterator = typename MessageMap::iterator;
      26             :     using MessagesBySourceMap = std::map<SourceId, std::vector<MessageMapIterator>>;
      27             : 
      28             :     bool secureVerification;
      29             :     bool perMessageFallback;
      30             :     size_t subBatchSize;
      31             : 
      32             :     MessageMap messages;
      33             :     MessagesBySourceMap messagesBySource;
      34             : 
      35             : public:
      36             :     std::set<SourceId> badSources;
      37             :     std::set<MessageId> badMessages;
      38             : 
      39             : public:
      40       75873 :     CBLSBatchVerifier(bool _secureVerification, bool _perMessageFallback, size_t _subBatchSize = 0) :
      41       25291 :             secureVerification(_secureVerification),
      42       25291 :             perMessageFallback(_perMessageFallback),
      43       25291 :             subBatchSize(_subBatchSize)
      44       25291 :     {
      45       50582 :     }
      46             : 
      47       45877 :     void PushMessage(const SourceId& sourceId, const MessageId& msgId, const uint256& msgHash, const CBLSSignature& sig, const CBLSPublicKey& pubKey)
      48             :     {
      49       45877 :         assert(sig.IsValid() && pubKey.IsValid());
      50             : 
      51       45877 :         auto it = messages.emplace(msgId, Message{msgId, msgHash, sig, pubKey}).first;
      52       45877 :         messagesBySource[sourceId].emplace_back(it);
      53             : 
      54       45877 :         if (subBatchSize != 0 && messages.size() >= subBatchSize) {
      55           0 :             Verify();
      56           0 :             ClearMessages();
      57           0 :         }
      58       45877 :     }
      59             : 
      60           0 :     void ClearMessages()
      61             :     {
      62           0 :         messages.clear();
      63           0 :         messagesBySource.clear();
      64           0 :     }
      65             : 
      66         805 :     size_t GetUniqueSourceCount() const
      67             :     {
      68         805 :         return messagesBySource.size();
      69             :     }
      70             : 
      71       25291 :     void Verify()
      72             :     {
      73       25291 :         std::map<uint256, std::vector<MessageMapIterator>> byMessageHash;
      74             : 
      75       67253 :         for (auto it = messages.begin(); it != messages.end(); ++it) {
      76       41962 :             byMessageHash[it->second.msgHash].emplace_back(it);
      77       41962 :         }
      78             : 
      79       25291 :         if (VerifyBatch(byMessageHash)) {
      80             :             // full batch is valid
      81       25255 :             return;
      82             :         }
      83             : 
      84             :         // revert to per-source verification
      85         512 :         for (const auto& [from, message_map] : messagesBySource) {
      86         166 :             bool batchValid = false;
      87             : 
      88             :             // no need to verify it again if there was just one source
      89         166 :             if (messagesBySource.size() != 1) {
      90         164 :                 byMessageHash.clear();
      91         416 :                 for (auto it = message_map.begin(); it != message_map.end(); ++it) {
      92         252 :                     byMessageHash[(*it)->second.msgHash].emplace_back(*it);
      93         252 :                 }
      94         164 :                 batchValid = VerifyBatch(byMessageHash);
      95         164 :             }
      96         166 :             if (!batchValid) {
      97          76 :                 badSources.emplace(from);
      98             : 
      99          38 :                 if (perMessageFallback) {
     100             :                     // revert to per-message verification
     101          20 :                     if (message_map.size() == 1) {
     102             :                         // no need to re-verify a single message
     103          32 :                         badMessages.emplace(message_map[0]->second.msgId);
     104          16 :                     } else {
     105          20 :                         for (const auto& msgIt : message_map) {
     106          16 :                             if (badMessages.count(msgIt->first)) {
     107             :                                 // same message might be invalid from different source, so no need to re-verify it
     108           0 :                                 continue;
     109             :                             }
     110             : 
     111          16 :                             const auto& msg = msgIt->second;
     112          16 :                             if (!msg.sig.VerifyInsecure(msg.pubKey, msg.msgHash)) {
     113           4 :                                 badMessages.emplace(msg.msgId);
     114           4 :                             }
     115             :                         }
     116             :                     }
     117          20 :                 }
     118          38 :             }
     119             :         }
     120       25291 :     }
     121             : 
     122             : private:
     123             :     // All Verify methods take ownership of the passed byMessageHash map and thus might modify the map. This is to avoid
     124             :     // unnecessary copies
     125             : 
     126       25455 :     bool VerifyBatch(std::map<uint256, std::vector<MessageMapIterator>>& byMessageHash)
     127             :     {
     128       25455 :         if (secureVerification) {
     129         108 :             return VerifyBatchSecure(byMessageHash);
     130             :         } else {
     131       25347 :             return VerifyBatchInsecure(byMessageHash);
     132             :         }
     133       25455 :     }
     134             : 
     135       25347 :     bool VerifyBatchInsecure(const std::map<uint256, std::vector<MessageMapIterator>>& byMessageHash)
     136             :     {
     137       25347 :         std::vector<CBLSSignature> sigsToAggregate;
     138       25347 :         std::vector<uint256> msgHashes;
     139       25347 :         std::vector<CBLSPublicKey> pubKeys;
     140       25347 :         std::set<MessageId> dups;
     141             : 
     142       25347 :         msgHashes.reserve(messages.size());
     143       25347 :         pubKeys.reserve(messages.size());
     144       25347 :         sigsToAggregate.reserve(messages.size());
     145             : 
     146       25347 :         std::vector<CBLSPublicKey> pubKeysToAggregate;
     147      102049 :         for (const auto& [msgHash, vec_message_it] : byMessageHash) {
     148       38351 :             pubKeysToAggregate.clear();
     149       38351 :             pubKeysToAggregate.reserve(vec_message_it.size());
     150             : 
     151       80257 :             for (const auto& msgIt : vec_message_it) {
     152       41906 :                 const auto& msg = msgIt->second;
     153             : 
     154       41906 :                 if (!dups.emplace(msg.msgId).second) {
     155           0 :                     continue;
     156             :                 }
     157             : 
     158       41906 :                 sigsToAggregate.push_back(msg.sig);
     159       41906 :                 pubKeysToAggregate.push_back(msg.pubKey);
     160             :             }
     161             : 
     162       38351 :             CBLSPublicKey aggPubKey = CBLSPublicKey::AggregateInsecure(pubKeysToAggregate);
     163             : 
     164       38351 :             if (!aggPubKey.IsValid()) {
     165             :                 // only duplicates for this msgHash
     166           0 :                 continue;
     167             :             }
     168             : 
     169       38351 :             msgHashes.emplace_back(msgHash);
     170       38351 :             pubKeys.emplace_back(aggPubKey);
     171             :         }
     172             : 
     173       25347 :         if (msgHashes.empty()) {
     174         556 :             return true;
     175             :         }
     176             : 
     177       24791 :         CBLSSignature aggSig = CBLSSignature::AggregateInsecure(sigsToAggregate);
     178       24791 :         return aggSig.VerifyInsecureAggregated(pubKeys, msgHashes);
     179       25347 :     }
     180             : 
     181         108 :     bool VerifyBatchSecure(std::map<uint256, std::vector<MessageMapIterator>>& byMessageHash)
     182             :     {
     183             :         // Loop until the byMessageHash map is empty, which means that all messages were verified
     184             :         // The secure form of verification will only aggregate one message for the same message hash, even if multiple
     185             :         // exist (signed with different keys). This avoids the rogue public key attack.
     186             :         // This is slower than the insecure form as it requires more pairings
     187         224 :         while (!byMessageHash.empty()) {
     188         148 :             if (!VerifyBatchSecureStep(byMessageHash)) {
     189          32 :                 return false;
     190             :             }
     191             :         }
     192          76 :         return true;
     193         108 :     }
     194             : 
     195         148 :     bool VerifyBatchSecureStep(std::map<uint256, std::vector<MessageMapIterator>>& byMessageHash)
     196             :     {
     197         148 :         std::vector<CBLSSignature> sigsToAggregate;
     198         148 :         std::vector<uint256> msgHashes;
     199         148 :         std::vector<CBLSPublicKey> pubKeys;
     200         148 :         std::set<MessageId> dups;
     201             : 
     202         148 :         msgHashes.reserve(messages.size());
     203         148 :         pubKeys.reserve(messages.size());
     204         148 :         sigsToAggregate.reserve(messages.size());
     205             : 
     206         420 :         for (auto it = byMessageHash.begin(); it != byMessageHash.end(); ) {
     207         272 :             const auto& msgHash = it->first;
     208         272 :             auto& messageIts = it->second;
     209         272 :             const auto& msg = messageIts.back()->second;
     210             : 
     211         272 :             if (dups.emplace(msg.msgId).second) {
     212         272 :                 msgHashes.emplace_back(msgHash);
     213         272 :                 pubKeys.emplace_back(msg.pubKey);
     214         272 :                 sigsToAggregate.push_back(msg.sig);
     215         272 :             }
     216             : 
     217         272 :             messageIts.pop_back();
     218         272 :             if (messageIts.empty()) {
     219         224 :                 it = byMessageHash.erase(it);
     220         224 :             } else {
     221          48 :                 ++it;
     222             :             }
     223             :         }
     224             : 
     225         148 :         assert(!msgHashes.empty());
     226             : 
     227         148 :         CBLSSignature aggSig = CBLSSignature::AggregateInsecure(sigsToAggregate);
     228         148 :         return aggSig.VerifyInsecureAggregated(pubKeys, msgHashes);
     229         148 :     }
     230             : };
     231             : 
     232             : #endif //DASH_CRYPTO_BLS_BATCHVERIFIER_H