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         168 :     CBLSBatchVerifier(bool _secureVerification, bool _perMessageFallback, size_t _subBatchSize = 0) :
      41          56 :             secureVerification(_secureVerification),
      42          56 :             perMessageFallback(_perMessageFallback),
      43          56 :             subBatchSize(_subBatchSize)
      44          56 :     {
      45         112 :     }
      46             : 
      47         368 :     void PushMessage(const SourceId& sourceId, const MessageId& msgId, const uint256& msgHash, const CBLSSignature& sig, const CBLSPublicKey& pubKey)
      48             :     {
      49         368 :         assert(sig.IsValid() && pubKey.IsValid());
      50             : 
      51         368 :         auto it = messages.emplace(msgId, Message{msgId, msgHash, sig, pubKey}).first;
      52         368 :         messagesBySource[sourceId].emplace_back(it);
      53             : 
      54         368 :         if (subBatchSize != 0 && messages.size() >= subBatchSize) {
      55           0 :             Verify();
      56           0 :             ClearMessages();
      57           0 :         }
      58         368 :     }
      59             : 
      60           0 :     void ClearMessages()
      61             :     {
      62           0 :         messages.clear();
      63           0 :         messagesBySource.clear();
      64           0 :     }
      65             : 
      66           0 :     size_t GetUniqueSourceCount() const
      67             :     {
      68           0 :         return messagesBySource.size();
      69             :     }
      70             : 
      71          56 :     void Verify()
      72             :     {
      73          56 :         std::map<uint256, std::vector<MessageMapIterator>> byMessageHash;
      74             : 
      75         424 :         for (auto it = messages.begin(); it != messages.end(); ++it) {
      76         368 :             byMessageHash[it->second.msgHash].emplace_back(it);
      77         368 :         }
      78             : 
      79          56 :         if (VerifyBatch(byMessageHash)) {
      80             :             // full batch is valid
      81          24 :             return;
      82             :         }
      83             : 
      84             :         // revert to per-source verification
      85         488 :         for (const auto& [from, message_map] : messagesBySource) {
      86         160 :             bool batchValid = false;
      87             : 
      88             :             // no need to verify it again if there was just one source
      89         160 :             if (messagesBySource.size() != 1) {
      90         160 :                 byMessageHash.clear();
      91         408 :                 for (auto it = message_map.begin(); it != message_map.end(); ++it) {
      92         248 :                     byMessageHash[(*it)->second.msgHash].emplace_back(*it);
      93         248 :                 }
      94         160 :                 batchValid = VerifyBatch(byMessageHash);
      95         160 :             }
      96         160 :             if (!batchValid) {
      97          64 :                 badSources.emplace(from);
      98             : 
      99          32 :                 if (perMessageFallback) {
     100             :                     // revert to per-message verification
     101          16 :                     if (message_map.size() == 1) {
     102             :                         // no need to re-verify a single message
     103          24 :                         badMessages.emplace(message_map[0]->second.msgId);
     104          12 :                     } 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          16 :                 }
     118          32 :             }
     119             :         }
     120          56 :     }
     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         216 :     bool VerifyBatch(std::map<uint256, std::vector<MessageMapIterator>>& byMessageHash)
     127             :     {
     128         216 :         if (secureVerification) {
     129         108 :             return VerifyBatchSecure(byMessageHash);
     130             :         } else {
     131         108 :             return VerifyBatchInsecure(byMessageHash);
     132             :         }
     133         216 :     }
     134             : 
     135         108 :     bool VerifyBatchInsecure(const std::map<uint256, std::vector<MessageMapIterator>>& byMessageHash)
     136             :     {
     137         108 :         std::vector<CBLSSignature> sigsToAggregate;
     138         108 :         std::vector<uint256> msgHashes;
     139         108 :         std::vector<CBLSPublicKey> pubKeys;
     140         108 :         std::set<MessageId> dups;
     141             : 
     142         108 :         msgHashes.reserve(messages.size());
     143         108 :         pubKeys.reserve(messages.size());
     144         108 :         sigsToAggregate.reserve(messages.size());
     145             : 
     146         108 :         std::vector<CBLSPublicKey> pubKeysToAggregate;
     147         572 :         for (const auto& [msgHash, vec_message_it] : byMessageHash) {
     148         232 :             pubKeysToAggregate.clear();
     149         232 :             pubKeysToAggregate.reserve(vec_message_it.size());
     150             : 
     151         540 :             for (const auto& msgIt : vec_message_it) {
     152         308 :                 const auto& msg = msgIt->second;
     153             : 
     154         308 :                 if (!dups.emplace(msg.msgId).second) {
     155           0 :                     continue;
     156             :                 }
     157             : 
     158         308 :                 sigsToAggregate.push_back(msg.sig);
     159         308 :                 pubKeysToAggregate.push_back(msg.pubKey);
     160             :             }
     161             : 
     162         232 :             CBLSPublicKey aggPubKey = CBLSPublicKey::AggregateInsecure(pubKeysToAggregate);
     163             : 
     164         232 :             if (!aggPubKey.IsValid()) {
     165             :                 // only duplicates for this msgHash
     166           0 :                 continue;
     167             :             }
     168             : 
     169         232 :             msgHashes.emplace_back(msgHash);
     170         232 :             pubKeys.emplace_back(aggPubKey);
     171             :         }
     172             : 
     173         108 :         if (msgHashes.empty()) {
     174           0 :             return true;
     175             :         }
     176             : 
     177         108 :         CBLSSignature aggSig = CBLSSignature::AggregateInsecure(sigsToAggregate);
     178         108 :         return aggSig.VerifyInsecureAggregated(pubKeys, msgHashes);
     179         108 :     }
     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