SERVER-53403 Support validating cluster times with keys from external_validation_keys

16 files changed, 531 insertions, 147 deletions

diff --git a/src/mongo/db/SConscript b/src/mongo/db/SConscript
index 9efd5ee394a..21c3d4ee6dd 100644
--- a/src/mongo/db/SConscript
+++ b/src/mongo/db/SConscript
@@ -2404,6 +2404,7 @@ envWithAsio.CppUnitTest(
     ],
     LIBDEPS=[
         'auth/authmocks',
+        'keys_collection_client_direct',
         's/config_server_test_fixture',
         'vector_clock',
     ],
diff --git a/src/mongo/db/key_generator.cpp b/src/mongo/db/key_generator.cpp
index a108d1cd4a9..4fddf1eb119 100644
--- a/src/mongo/db/key_generator.cpp
+++ b/src/mongo/db/key_generator.cpp
@@ -84,7 +84,7 @@ Status KeyGenerator::generateNewKeysIfNeeded(OperationContext* opCtx) {
     }
 
     const auto currentTime = VectorClock::get(opCtx)->getTime();
-    auto keyStatus = _client->getNewKeys(opCtx, _purpose, currentTime.clusterTime(), false);
+    auto keyStatus = _client->getNewInternalKeys(opCtx, _purpose, currentTime.clusterTime(), false);
 
     if (!keyStatus.isOK()) {
         return keyStatus.getStatus();
diff --git a/src/mongo/db/keys_collection_cache.cpp b/src/mongo/db/keys_collection_cache.cpp
index 5cf62f8da12..87f9e798a33 100644
--- a/src/mongo/db/keys_collection_cache.cpp
+++ b/src/mongo/db/keys_collection_cache.cpp
@@ -42,20 +42,6 @@ KeysCollectionCache::KeysCollectionCache(std::string purpose, KeysCollectionClie
     : _purpose(std::move(purpose)), _client(client) {}
 
 StatusWith<KeysCollectionDocument> KeysCollectionCache::refresh(OperationContext* opCtx) {
-    LogicalTime newerThanThis;
-
-    decltype(_cache)::size_type originalSize = 0;
-
-    {
-        stdx::lock_guard<Latch> lk(_cacheMutex);
-        auto iter = _cache.crbegin();
-        if (iter != _cache.crend()) {
-            newerThanThis = iter->second.getExpiresAt();
-        }
-
-        originalSize = _cache.size();
-    }
-
     // Don't allow this to read during initial sync because it will read at the initialDataTimestamp
     // and that could conflict with reconstructing prepared transactions using the
     // initialDataTimestamp as the prepareTimestamp.
@@ -65,7 +51,32 @@ StatusWith<KeysCollectionDocument> KeysCollectionCache::refresh(OperationContext
                 "Cannot refresh keys collection cache during initial sync"};
     }
 
-    auto refreshStatus = _client->getNewKeys(opCtx, _purpose, newerThanThis, true);
+    auto refreshStatus = _refreshExternalKeys(opCtx);
+
+    if (!refreshStatus.isOK()) {
+        return refreshStatus;
+    }
+
+    return _refreshInternalKeys(opCtx);
+}
+
+
+StatusWith<KeysCollectionDocument> KeysCollectionCache::_refreshInternalKeys(
+    OperationContext* opCtx) {
+    LogicalTime newerThanThis;
+    decltype(_internalKeysCache)::size_type originalSize = 0;
+
+    {
+        stdx::lock_guard<Latch> lk(_cacheMutex);
+        auto iter = _internalKeysCache.crbegin();
+        if (iter != _internalKeysCache.crend()) {
+            newerThanThis = iter->second.getExpiresAt();
+        }
+
+        originalSize = _internalKeysCache.size();
+    }
+
+    auto refreshStatus = _client->getNewInternalKeys(opCtx, _purpose, newerThanThis, true);
 
     if (!refreshStatus.isOK()) {
         return refreshStatus.getStatus();
@@ -74,9 +85,9 @@ StatusWith<KeysCollectionDocument> KeysCollectionCache::refresh(OperationContext
     auto& newKeys = refreshStatus.getValue();
 
     stdx::lock_guard<Latch> lk(_cacheMutex);
-    if (originalSize > _cache.size()) {
-        // _cache cleared while we getting the new keys, just return the newest key without
-        // touching the _cache so the next refresh will populate it properly.
+    if (originalSize > _internalKeysCache.size()) {
+        // _internalKeysCache cleared while we were getting the new keys, just return the newest key
+        // without touching the _internalKeysCache so the next refresh will populate it properly.
         // Note: newKeys are sorted.
         if (!newKeys.empty()) {
             return std::move(newKeys.back());
@@ -84,38 +95,95 @@ StatusWith<KeysCollectionDocument> KeysCollectionCache::refresh(OperationContext
     }
 
     for (auto&& key : newKeys) {
-        _cache.emplace(std::make_pair(key.getExpiresAt(), std::move(key)));
+        _internalKeysCache.emplace(std::make_pair(key.getExpiresAt(), std::move(key)));
     }
 
-    if (_cache.empty()) {
+    if (_internalKeysCache.empty()) {
         return {ErrorCodes::KeyNotFound, "No keys found after refresh"};
     }
 
-    return _cache.crbegin()->second;
+    return _internalKeysCache.crbegin()->second;
+}
+
+Status KeysCollectionCache::_refreshExternalKeys(OperationContext* opCtx) {
+    decltype(_externalKeysCache)::size_type originalSize = 0;
+
+    {
+        stdx::lock_guard<Latch> lk(_cacheMutex);
+        originalSize = _externalKeysCache.size();
+    }
+
+    auto refreshStatus = _client->getNewExternalKeys(opCtx, _purpose, LogicalTime(), true);
+
+    if (!refreshStatus.isOK()) {
+        return refreshStatus.getStatus();
+    }
+
+    auto& newKeys = refreshStatus.getValue();
+
+    stdx::lock_guard<Latch> lk(_cacheMutex);
+    if (originalSize > _externalKeysCache.size()) {
+        // _externalKeysCache cleared while we were getting the new keys, just return so the next
+        // refresh will populate it properly.
+        return Status::OK();
+    }
+
+    for (auto&& key : newKeys) {
+        _externalKeysCache[key.getKeyId()].emplace(key.getReplicaSetName(), std::move(key));
+    }
+
+    return Status::OK();
 }
 
-StatusWith<KeysCollectionDocument> KeysCollectionCache::getKeyById(long long keyId,
-                                                                   const LogicalTime& forThisTime) {
+StatusWith<KeysCollectionDocument> KeysCollectionCache::getInternalKeyById(
+    long long keyId, const LogicalTime& forThisTime) {
     stdx::lock_guard<Latch> lk(_cacheMutex);
 
-    for (auto iter = _cache.lower_bound(forThisTime); iter != _cache.cend(); ++iter) {
+    for (auto iter = _internalKeysCache.lower_bound(forThisTime); iter != _internalKeysCache.cend();
+         ++iter) {
         if (iter->second.getKeyId() == keyId) {
             return iter->second;
         }
     }
 
     return {ErrorCodes::KeyNotFound,
-            str::stream() << "Cache Reader No keys found for " << _purpose
+            str::stream() << "Cache Reader No internal keys found for " << _purpose
                           << " that is valid for time: " << forThisTime.toString()
                           << " with id: " << keyId};
 }
 
-StatusWith<KeysCollectionDocument> KeysCollectionCache::getKey(const LogicalTime& forThisTime) {
+StatusWith<std::vector<ExternalKeysCollectionDocument>> KeysCollectionCache::getExternalKeysById(
+    long long keyId, const LogicalTime& forThisTime) {
+    stdx::lock_guard<Latch> lk(_cacheMutex);
+    std::vector<ExternalKeysCollectionDocument> keys;
+
+    auto keysIter = _externalKeysCache.find(keyId);
+
+    if (keysIter == _externalKeysCache.end()) {
+        return {ErrorCodes::KeyNotFound,
+                str::stream() << "Cache Reader No external keys found for " << _purpose
+                              << " with id: " << keyId};
+    }
+
+    invariant(!keysIter->second.empty());
+
+    for (auto keyIter = keysIter->second.begin(); keyIter != keysIter->second.end(); keyIter++) {
+        auto key = keyIter->second;
+        if (key.getExpiresAt() > forThisTime) {
+            keys.push_back(key);
+        }
+    }
+
+    return std::move(keys);
+}
+
+StatusWith<KeysCollectionDocument> KeysCollectionCache::getInternalKey(
+    const LogicalTime& forThisTime) {
     stdx::lock_guard<Latch> lk(_cacheMutex);
 
-    auto iter = _cache.upper_bound(forThisTime);
+    auto iter = _internalKeysCache.upper_bound(forThisTime);
 
-    if (iter == _cache.cend()) {
+    if (iter == _internalKeysCache.cend()) {
         return {ErrorCodes::KeyNotFound,
                 str::stream() << "No key found that is valid for " << forThisTime.toString()};
     }
@@ -127,7 +195,8 @@ void KeysCollectionCache::resetCache() {
     // keys that read with non majority readConcern level can be rolled back.
     if (!_client->supportsMajorityReads()) {
         stdx::lock_guard<Latch> lk(_cacheMutex);
-        _cache.clear();
+        _internalKeysCache.clear();
+        _externalKeysCache.clear();
     }
 }
 
diff --git a/src/mongo/db/keys_collection_cache.h b/src/mongo/db/keys_collection_cache.h
index 17c532b72fa..a37b4e45c65 100644
--- a/src/mongo/db/keys_collection_cache.h
+++ b/src/mongo/db/keys_collection_cache.h
@@ -55,8 +55,27 @@ public:
      */
     StatusWith<KeysCollectionDocument> refresh(OperationContext* opCtx);
 
-    StatusWith<KeysCollectionDocument> getKey(const LogicalTime& forThisTime);
-    StatusWith<KeysCollectionDocument> getKeyById(long long keyId, const LogicalTime& forThisTime);
+    /**
+     * Returns the internal key (see definition below) with an expiresAt value greater than
+     * forThisTime. Returns KeyNotFound if there is no such key.
+     */
+    StatusWith<KeysCollectionDocument> getInternalKey(const LogicalTime& forThisTime);
+
+    /**
+     * Returns the internal key (see definition below) with the given keyId and an expiresAt value
+     * greater than forThisTime. There should only be one matching key since keyId is unique for
+     * keys generated within a cluster. Returns KeyNotFound if there is no such key.
+     */
+    StatusWith<KeysCollectionDocument> getInternalKeyById(long long keyId,
+                                                          const LogicalTime& forThisTime);
+
+    /**
+     * Returns the external keys (see definition below) with the given keyId and an expiresAt value
+     * greater than forThisTime. There are a variable number of matching keys since keyId is not
+     * necessarily unique across clusters. Returns KeyNotFound if there are no such keys.
+     */
+    StatusWith<std::vector<ExternalKeysCollectionDocument>> getExternalKeysById(
+        long long keyId, const LogicalTime& forThisTime);
 
     /**
      * Resets the cache of keys if the client doesnt allow readConcern level:majority reads.
@@ -65,11 +84,33 @@ public:
     void resetCache();
 
 private:
+    /**
+     * Checks if there are new internal key documents (see definition below) with expiresAt greater
+     * than the latest internal key document's expiresAt. Returns KeyNotFound if _internalKeysCache
+     * is empty after refresh.
+     */
+    StatusWith<KeysCollectionDocument> _refreshInternalKeys(OperationContext* opCtx);
+
+    /**
+     * Checks if there are new external key documents (see definition below). Does not return
+     * KeyNotFound if _externalKeysCache is empty after refresh.
+     */
+    Status _refreshExternalKeys(OperationContext* opCtx);
+
     const std::string _purpose;
     KeysCollectionClient* const _client;
 
     Mutex _cacheMutex = MONGO_MAKE_LATCH("KeysCollectionCache::_cacheMutex");
-    std::map<LogicalTime, KeysCollectionDocument> _cache;  // expiresAt -> KeysDocument
+
+    // Stores keys for signing and validating cluster times created by the cluster that this node
+    // is in.
+    std::map<LogicalTime, KeysCollectionDocument> _internalKeysCache;  // expiresAt -> KeysDocument
+
+    // Stores keys for validating cluster times created by other clusters. These key documents
+    // cannot be stored in a regular map like _internalKeysCache since expiresAt and keyId are not
+    // necessarily unique across clusters so there is chance of collision.
+    stdx::unordered_map<long long, StringMap<ExternalKeysCollectionDocument>>
+        _externalKeysCache;  // keyId -> (replicaSetName -> ExternalKeysDocument)
 };
 
 }  // namespace mongo
diff --git a/src/mongo/db/keys_collection_cache_test.cpp b/src/mongo/db/keys_collection_cache_test.cpp
index a1d0732ae9f..34008907fdb 100644
--- a/src/mongo/db/keys_collection_cache_test.cpp
+++ b/src/mongo/db/keys_collection_cache_test.cpp
@@ -29,8 +29,10 @@
 
 #include "mongo/platform/basic.h"
 
+#include "mongo/db/dbhelpers.h"
 #include "mongo/db/jsobj.h"
 #include "mongo/db/keys_collection_cache.h"
+#include "mongo/db/keys_collection_client_direct.h"
 #include "mongo/db/keys_collection_client_sharded.h"
 #include "mongo/db/keys_collection_document_gen.h"
 #include "mongo/db/operation_context.h"
@@ -50,31 +52,72 @@ protected:
 
         _catalogClient = std::make_unique<KeysCollectionClientSharded>(
             Grid::get(operationContext())->catalogClient());
+
+        _directClient = std::make_unique<KeysCollectionClientDirect>();
     }
 
     KeysCollectionClient* catalogClient() const {
         return _catalogClient.get();
     }
 
+    KeysCollectionClient* directClient() const {
+        return _directClient.get();
+    }
+
+    void insertDocument(OperationContext* opCtx, const NamespaceString& nss, const BSONObj& doc) {
+        AutoGetCollection coll(opCtx, nss, MODE_IX);
+        auto updateResult = Helpers::upsert(opCtx, nss.toString(), doc);
+        ASSERT_EQ(0, updateResult.numDocsModified);
+    }
+
 private:
     std::unique_ptr<KeysCollectionClient> _catalogClient;
+    std::unique_ptr<KeysCollectionClient> _directClient;
 };
 
-TEST_F(CacheTest, ErrorsIfCacheIsEmpty) {
+TEST_F(CacheTest, GetInternalKeyErrorsIfInternalKeysCacheIsEmpty) {
+    KeysCollectionCache cache("test", catalogClient());
+    auto status = cache.getInternalKey(LogicalTime(Timestamp(1, 0))).getStatus();
+    ASSERT_EQ(ErrorCodes::KeyNotFound, status.code());
+    ASSERT_FALSE(status.reason().empty());
+}
+
+TEST_F(CacheTest, GetInternalKeyByIdErrorsIfInternalKeysCacheIsEmpty) {
     KeysCollectionCache cache("test", catalogClient());
-    auto status = cache.getKey(LogicalTime(Timestamp(1, 0))).getStatus();
+    auto status = cache.getInternalKeyById(1, LogicalTime(Timestamp(1, 0))).getStatus();
     ASSERT_EQ(ErrorCodes::KeyNotFound, status.code());
     ASSERT_FALSE(status.reason().empty());
 }
 
-TEST_F(CacheTest, RefreshErrorsIfCacheIsEmpty) {
+TEST_F(CacheTest, GetExternalKeysByIdErrorsIfExternalKeysCacheIsEmpty) {
+    KeysCollectionCache cache("test", catalogClient());
+    auto status = cache.getExternalKeysById(1, LogicalTime(Timestamp(1, 0))).getStatus();
+    ASSERT_EQ(ErrorCodes::KeyNotFound, status.code());
+    ASSERT_FALSE(status.reason().empty());
+}
+
+TEST_F(CacheTest, RefreshErrorsIfInternalCacheIsEmpty) {
     KeysCollectionCache cache("test", catalogClient());
     auto status = cache.refresh(operationContext()).getStatus();
     ASSERT_EQ(ErrorCodes::KeyNotFound, status.code());
     ASSERT_FALSE(status.reason().empty());
 }
 
-TEST_F(CacheTest, GetKeyShouldReturnCorrectKeyAfterRefresh) {
+TEST_F(CacheTest, RefreshDoesNotErrorIfExternalKeysCacheIsEmpty) {
+    KeysCollectionCache cache("test", catalogClient());
+
+    KeysCollectionDocument origKey1(1);
+    origKey1.setKeysCollectionDocumentBase(
+        {"test", TimeProofService::generateRandomKey(), LogicalTime(Timestamp(105, 0))});
+    ASSERT_OK(insertToConfigCollection(
+        operationContext(), NamespaceString::kKeysCollectionNamespace, origKey1.toBSON()));
+
+    auto status = cache.refresh(operationContext()).getStatus();
+    ASSERT_OK(status);
+}
+
+
+TEST_F(CacheTest, GetKeyShouldReturnCorrectKeyAfterRefreshSharded) {
     KeysCollectionCache cache("test", catalogClient());
 
     KeysCollectionDocument origKey1(1);
@@ -94,19 +137,114 @@ TEST_F(CacheTest, GetKeyShouldReturnCorrectKeyAfterRefresh) {
         ASSERT_EQ(Timestamp(105, 0), key.getExpiresAt().asTimestamp());
     }
 
-    auto status = cache.getKey(LogicalTime(Timestamp(1, 0)));
-    ASSERT_OK(status.getStatus());
+    auto swInternalKey = cache.getInternalKey(LogicalTime(Timestamp(1, 0)));
+    ASSERT_OK(swInternalKey.getStatus());
 
     {
-        auto key = status.getValue();
+        auto key = swInternalKey.getValue();
         ASSERT_EQ(1, key.getKeyId());
         ASSERT_EQ(origKey1.getKey(), key.getKey());
         ASSERT_EQ("test", key.getPurpose());
         ASSERT_EQ(Timestamp(105, 0), key.getExpiresAt().asTimestamp());
     }
+
+    swInternalKey = cache.getInternalKeyById(1, LogicalTime(Timestamp(1, 0)));
+    ASSERT_OK(swInternalKey.getStatus());
+
+    {
+        auto key = swInternalKey.getValue();
+        ASSERT_EQ(1, key.getKeyId());
+        ASSERT_EQ(origKey1.getKey(), key.getKey());
+        ASSERT_EQ("test", key.getPurpose());
+        ASSERT_EQ(Timestamp(105, 0), key.getExpiresAt().asTimestamp());
+    }
+
+    auto swExternalKeys = cache.getExternalKeysById(1, LogicalTime(Timestamp(1, 0)));
+    ASSERT_EQ(ErrorCodes::KeyNotFound, swExternalKeys.getStatus());
 }
 
-TEST_F(CacheTest, GetKeyShouldReturnErrorIfNoKeyIsValidForGivenTime) {
+TEST_F(CacheTest, GetKeyShouldReturnCorrectKeysAfterRefreshDirectClient) {
+    KeysCollectionCache cache("test", directClient());
+
+    KeysCollectionDocument origKey0(1);
+    origKey0.setKeysCollectionDocumentBase(
+        {"test", TimeProofService::generateRandomKey(), LogicalTime(Timestamp(105, 0))});
+    insertDocument(
+        operationContext(), NamespaceString::kKeysCollectionNamespace, origKey0.toBSON());
+
+    // Use external keys with the same keyId and expiresAt as the internal key to test that the
+    // cache correctly tackles key collisions.
+    ExternalKeysCollectionDocument origKey1(OID::gen(), 1, "replicaSetName1");
+    origKey1.setKeysCollectionDocumentBase(
+        {"test", TimeProofService::generateRandomKey(), LogicalTime(Timestamp(105, 0))});
+    insertDocument(
+        operationContext(), NamespaceString::kExternalKeysCollectionNamespace, origKey1.toBSON());
+
+    ExternalKeysCollectionDocument origKey2(OID::gen(), 1, "replicaSetName2");
+    origKey2.setKeysCollectionDocumentBase(
+        {"test", TimeProofService::generateRandomKey(), LogicalTime(Timestamp(105, 0))});
+    insertDocument(
+        operationContext(), NamespaceString::kExternalKeysCollectionNamespace, origKey2.toBSON());
+
+    auto refreshStatus = cache.refresh(operationContext());
+    ASSERT_OK(refreshStatus.getStatus());
+
+    // refresh() should return the internal key.
+    {
+        auto key = refreshStatus.getValue();
+        ASSERT_EQ(1, key.getKeyId());
+        ASSERT_EQ(origKey0.getKey(), key.getKey());
+        ASSERT_EQ("test", key.getPurpose());
+        ASSERT_EQ(Timestamp(105, 0), key.getExpiresAt().asTimestamp());
+    }
+
+    auto swInternalKey = cache.getInternalKey(LogicalTime(Timestamp(1, 0)));
+    ASSERT_OK(swInternalKey.getStatus());
+
+    {
+        auto key = swInternalKey.getValue();
+        ASSERT_EQ(1, key.getKeyId());
+        ASSERT_EQ(origKey0.getKey(), key.getKey());
+        ASSERT_EQ("test", key.getPurpose());
+        ASSERT_EQ(Timestamp(105, 0), key.getExpiresAt().asTimestamp());
+    }
+
+    swInternalKey = cache.getInternalKeyById(1, LogicalTime(Timestamp(1, 0)));
+    ASSERT_OK(swInternalKey.getStatus());
+
+    {
+        auto key = swInternalKey.getValue();
+        ASSERT_EQ(1, key.getKeyId());
+        ASSERT_EQ(origKey0.getKey(), key.getKey());
+        ASSERT_EQ("test", key.getPurpose());
+        ASSERT_EQ(Timestamp(105, 0), key.getExpiresAt().asTimestamp());
+    }
+
+    auto swExternalKeys = cache.getExternalKeysById(1, LogicalTime(Timestamp(1, 0)));
+    ASSERT_OK(swExternalKeys.getStatus());
+
+    {
+        std::map<OID, ExternalKeysCollectionDocument> expectedKeys = {
+            {origKey1.getId(), origKey1},
+            {origKey2.getId(), origKey2},
+        };
+
+        auto keys = swExternalKeys.getValue();
+        ASSERT_EQ(expectedKeys.size(), keys.size());
+
+        for (const auto& key : keys) {
+            auto iter = expectedKeys.find(key.getId());
+            ASSERT(iter != expectedKeys.end());
+
+            auto expectedKey = iter->second;
+            ASSERT_EQ(expectedKey.getId(), key.getId());
+            ASSERT_EQ(expectedKey.getPurpose(), key.getPurpose());
+            ASSERT_EQ(expectedKey.getExpiresAt().asTimestamp(), key.getExpiresAt().asTimestamp());
+        }
+    }
+}
+
+TEST_F(CacheTest, GetInternalKeyShouldReturnErrorIfNoKeyIsValidForGivenTime) {
     KeysCollectionCache cache("test", catalogClient());
 
     KeysCollectionDocument origKey1(1);
@@ -126,11 +264,11 @@ TEST_F(CacheTest, GetKeyShouldReturnErrorIfNoKeyIsValidForGivenTime) {
         ASSERT_EQ(Timestamp(105, 0), key.getExpiresAt().asTimestamp());
     }
 
-    auto status = cache.getKey(LogicalTime(Timestamp(110, 0)));
-    ASSERT_EQ(ErrorCodes::KeyNotFound, status.getStatus());
+    auto swKey = cache.getInternalKey(LogicalTime(Timestamp(110, 0)));
+    ASSERT_EQ(ErrorCodes::KeyNotFound, swKey.getStatus());
 }
 
-TEST_F(CacheTest, GetKeyShouldReturnOldestKeyPossible) {
+TEST_F(CacheTest, GetInternalKeyShouldReturnOldestKeyPossible) {
     KeysCollectionCache cache("test", catalogClient());
 
     KeysCollectionDocument origKey0(0);
@@ -162,11 +300,11 @@ TEST_F(CacheTest, GetKeyShouldReturnOldestKeyPossible) {
         ASSERT_EQ(Timestamp(110, 0), key.getExpiresAt().asTimestamp());
     }
 
-    auto keyStatus = cache.getKey(LogicalTime(Timestamp(103, 1)));
-    ASSERT_OK(keyStatus.getStatus());
+    auto swKey = cache.getInternalKey(LogicalTime(Timestamp(103, 1)));
+    ASSERT_OK(swKey.getStatus());
 
     {
-        auto key = keyStatus.getValue();
+        auto key = swKey.getValue();
         ASSERT_EQ(1, key.getKeyId());
         ASSERT_EQ(origKey1.getKey(), key.getKey());
         ASSERT_EQ("test", key.getPurpose());
@@ -174,7 +312,7 @@ TEST_F(CacheTest, GetKeyShouldReturnOldestKeyPossible) {
     }
 }
 
-TEST_F(CacheTest, RefreshShouldNotGetKeysForOtherPurpose) {
+TEST_F(CacheTest, RefreshShouldNotGetInternalKeysForOtherPurpose) {
     KeysCollectionCache cache("test", catalogClient());
 
     KeysCollectionDocument origKey0(0);
@@ -187,8 +325,8 @@ TEST_F(CacheTest, RefreshShouldNotGetKeysForOtherPurpose) {
         auto refreshStatus = cache.refresh(operationContext());
         ASSERT_EQ(ErrorCodes::KeyNotFound, refreshStatus.getStatus());
 
-        auto emptyKeyStatus = cache.getKey(LogicalTime(Timestamp(50, 0)));
-        ASSERT_EQ(ErrorCodes::KeyNotFound, emptyKeyStatus.getStatus());
+        auto swKey = cache.getInternalKey(LogicalTime(Timestamp(50, 0)));
+        ASSERT_EQ(ErrorCodes::KeyNotFound, swKey.getStatus());
     }
 
     KeysCollectionDocument origKey1(1);
@@ -208,11 +346,11 @@ TEST_F(CacheTest, RefreshShouldNotGetKeysForOtherPurpose) {
         ASSERT_EQ(Timestamp(105, 0), key.getExpiresAt().asTimestamp());
     }
 
-    auto keyStatus = cache.getKey(LogicalTime(Timestamp(60, 1)));
-    ASSERT_OK(keyStatus.getStatus());
+    auto swKey = cache.getInternalKey(LogicalTime(Timestamp(60, 1)));
+    ASSERT_OK(swKey.getStatus());
 
     {
-        auto key = keyStatus.getValue();
+        auto key = swKey.getValue();
         ASSERT_EQ(1, key.getKeyId());
         ASSERT_EQ(origKey1.getKey(), key.getKey());
         ASSERT_EQ("test", key.getPurpose());
@@ -220,6 +358,54 @@ TEST_F(CacheTest, RefreshShouldNotGetKeysForOtherPurpose) {
     }
 }
 
+TEST_F(CacheTest, RefreshShouldNotGetExternalKeysForOtherPurpose) {
+    KeysCollectionCache cache("test", directClient());
+
+    KeysCollectionDocument origKey0(0);
+    origKey0.setKeysCollectionDocumentBase(
+        {"test", TimeProofService::generateRandomKey(), LogicalTime(Timestamp(100, 0))});
+    insertDocument(
+        operationContext(), NamespaceString::kKeysCollectionNamespace, origKey0.toBSON());
+
+    ExternalKeysCollectionDocument origKey1(OID::gen(), 1, "replicaSetName1");
+    origKey1.setKeysCollectionDocumentBase(
+        {"dummy", TimeProofService::generateRandomKey(), LogicalTime(Timestamp(105, 0))});
+    insertDocument(
+        operationContext(), NamespaceString::kExternalKeysCollectionNamespace, origKey1.toBSON());
+
+    {
+        auto refreshStatus = cache.refresh(operationContext());
+        ASSERT_OK(refreshStatus.getStatus());
+
+        auto swKey = cache.getExternalKeysById(1, LogicalTime(Timestamp(1, 0)));
+        ASSERT_EQ(ErrorCodes::KeyNotFound, swKey.getStatus());
+    }
+
+    ExternalKeysCollectionDocument origKey2(OID::gen(), 2, "replicaSetName1");
+    origKey2.setKeysCollectionDocumentBase(
+        {"test", TimeProofService::generateRandomKey(), LogicalTime(Timestamp(110, 0))});
+    insertDocument(
+        operationContext(), NamespaceString::kExternalKeysCollectionNamespace, origKey2.toBSON());
+
+    {
+        auto refreshStatus = cache.refresh(operationContext());
+        ASSERT_OK(refreshStatus.getStatus());
+
+        auto swKeys = cache.getExternalKeysById(2, LogicalTime(Timestamp(1, 0)));
+        ASSERT_OK(swKeys.getStatus());
+
+        auto keys = swKeys.getValue();
+        ASSERT_EQ(1, keys.size());
+
+        auto key = keys.front();
+        ASSERT_EQ(2, key.getKeyId());
+        ASSERT_EQ(origKey2.getId(), key.getId());
+        ASSERT_EQ(origKey2.getKey(), key.getKey());
+        ASSERT_EQ("test", key.getPurpose());
+        ASSERT_EQ(Timestamp(110, 0), key.getExpiresAt().asTimestamp());
+    }
+}
+
 TEST_F(CacheTest, RefreshCanIncrementallyGetNewKeys) {
     KeysCollectionCache cache("test", catalogClient());
 
@@ -240,8 +426,8 @@ TEST_F(CacheTest, RefreshCanIncrementallyGetNewKeys) {
         ASSERT_EQ("test", key.getPurpose());
         ASSERT_EQ(Timestamp(100, 0), key.getExpiresAt().asTimestamp());
 
-        auto keyStatus = cache.getKey(LogicalTime(Timestamp(112, 1)));
-        ASSERT_EQ(ErrorCodes::KeyNotFound, keyStatus.getStatus());
+        auto swKey = cache.getInternalKey(LogicalTime(Timestamp(112, 1)));
+        ASSERT_EQ(ErrorCodes::KeyNotFound, swKey.getStatus());
     }
 
     KeysCollectionDocument origKey1(1);
@@ -268,9 +454,10 @@ TEST_F(CacheTest, RefreshCanIncrementallyGetNewKeys) {
     }
 
     {
-        auto keyStatus = cache.getKey(LogicalTime(Timestamp(108, 1)));
+        auto swKey = cache.getInternalKey(LogicalTime(Timestamp(108, 1)));
+        ASSERT_OK(swKey.getStatus());
 
-        auto key = keyStatus.getValue();
+        auto key = swKey.getValue();
         ASSERT_EQ(2, key.getKeyId());
         ASSERT_EQ(origKey2.getKey(), key.getKey());
         ASSERT_EQ("test", key.getPurpose());
diff --git a/src/mongo/db/keys_collection_client.h b/src/mongo/db/keys_collection_client.h
index a805300da2b..7bb4f16341d 100644
--- a/src/mongo/db/keys_collection_client.h
+++ b/src/mongo/db/keys_collection_client.h
@@ -46,10 +46,22 @@ public:
     virtual ~KeysCollectionClient() = default;
 
     /**
-     * Returns keys for the given purpose and with an expiresAt value greater than newerThanThis,
-     * using readConcern level majority if possible.
+     * Returns internal keys (keys for signing and validating cluster times created by nodes in the
+     * clusters that this node is in) that match the given purpose and have an expiresAt value
+     * greater than newerThanThis. Uses readConcern level majority if possible.
      */
-    virtual StatusWith<std::vector<KeysCollectionDocument>> getNewKeys(
+    virtual StatusWith<std::vector<KeysCollectionDocument>> getNewInternalKeys(
+        OperationContext* opCtx,
+        StringData purpose,
+        const LogicalTime& newerThanThis,
+        bool useMajority) = 0;
+
+    /**
+     * Returns external keys (validation-only keys copied from other clusters) that match the given
+     * purpose and have an expiresAt value greater than newerThanThis. Uses readConcern level
+     * majority if possible.
+     */
+    virtual StatusWith<std::vector<ExternalKeysCollectionDocument>> getNewExternalKeys(
         OperationContext* opCtx,
         StringData purpose,
         const LogicalTime& newerThanThis,
diff --git a/src/mongo/db/keys_collection_client_direct.cpp b/src/mongo/db/keys_collection_client_direct.cpp
index 4b90c8bb23f..af1e90d57a5 100644
--- a/src/mongo/db/keys_collection_client_direct.cpp
+++ b/src/mongo/db/keys_collection_client_direct.cpp
@@ -72,13 +72,35 @@ bool isRetriableError(ErrorCodes::Error code, Shard::RetryPolicy options) {
 
 KeysCollectionClientDirect::KeysCollectionClientDirect() : _rsLocalClient() {}
 
-StatusWith<std::vector<KeysCollectionDocument>> KeysCollectionClientDirect::getNewKeys(
+StatusWith<std::vector<KeysCollectionDocument>> KeysCollectionClientDirect::getNewInternalKeys(
     OperationContext* opCtx,
     StringData purpose,
     const LogicalTime& newerThanThis,
     bool useMajority) {
+    return _getNewKeys<KeysCollectionDocument>(
+        opCtx, NamespaceString::kKeysCollectionNamespace, purpose, newerThanThis, useMajority);
+}
 
+StatusWith<std::vector<ExternalKeysCollectionDocument>>
+KeysCollectionClientDirect::getNewExternalKeys(OperationContext* opCtx,
+                                               StringData purpose,
+                                               const LogicalTime& newerThanThis,
+                                               bool useMajority) {
+    return _getNewKeys<ExternalKeysCollectionDocument>(
+        opCtx,
+        NamespaceString::kExternalKeysCollectionNamespace,
+        purpose,
+        newerThanThis,
+        useMajority);
+}
 
+template <typename KeyDocumentType>
+StatusWith<std::vector<KeyDocumentType>> KeysCollectionClientDirect::_getNewKeys(
+    OperationContext* opCtx,
+    const NamespaceString& nss,
+    StringData purpose,
+    const LogicalTime& newerThanThis,
+    bool useMajority) {
     BSONObjBuilder queryBuilder;
     queryBuilder.append("purpose", purpose);
     queryBuilder.append("expiresAt", BSON("$gt" << newerThanThis.asTimestamp()));
@@ -91,7 +113,7 @@ StatusWith<std::vector<KeysCollectionDocument>> KeysCollectionClientDirect::getN
     auto findStatus = _query(opCtx,
                              ReadPreferenceSetting(ReadPreference::Nearest, TagSet{}),
                              readConcern,
-                             NamespaceString::kKeysCollectionNamespace,
+                             nss,
                              queryBuilder.obj(),
                              BSON("expiresAt" << 1),
                              boost::none);
@@ -101,11 +123,11 @@ StatusWith<std::vector<KeysCollectionDocument>> KeysCollectionClientDirect::getN
     }
 
     const auto& keyDocs = findStatus.getValue().docs;
-    std::vector<KeysCollectionDocument> keys;
+    std::vector<KeyDocumentType> keys;
     for (auto&& keyDoc : keyDocs) {
-        KeysCollectionDocument key;
+        KeyDocumentType key;
         try {
-            key = KeysCollectionDocument::parse(IDLParserErrorContext("keyDoc"), keyDoc);
+            key = KeyDocumentType::parse(IDLParserErrorContext("keyDoc"), keyDoc);
         } catch (...) {
             return exceptionToStatus();
         }
diff --git a/src/mongo/db/keys_collection_client_direct.h b/src/mongo/db/keys_collection_client_direct.h
index 3b101d99167..9cd71aad750 100644
--- a/src/mongo/db/keys_collection_client_direct.h
+++ b/src/mongo/db/keys_collection_client_direct.h
@@ -45,13 +45,24 @@ class KeysCollectionClientDirect : public KeysCollectionClient {
 public:
     KeysCollectionClientDirect();
     /**
-     * Returns keys for the given purpose and with an expiresAt value greater than newerThanThis,
-     * using readConcern level majority if possible.
+     * Returns keys in admin.system.keys that match the given purpose and have an expiresAt value
+     * greater than newerThanThis. Uses readConcern level majority if possible.
      */
-    StatusWith<std::vector<KeysCollectionDocument>> getNewKeys(OperationContext* opCtx,
-                                                               StringData purpose,
-                                                               const LogicalTime& newerThanThis,
-                                                               bool useMajority) override;
+    StatusWith<std::vector<KeysCollectionDocument>> getNewInternalKeys(
+        OperationContext* opCtx,
+        StringData purpose,
+        const LogicalTime& newerThanThis,
+        bool useMajority) override;
+
+    /**
+     * Returns keys in admin.system.external_validation_keys that match the given purpose and have
+     * an expiresAt value greater than newerThanThis. Uses readConcern level majority if possible.
+     */
+    StatusWith<std::vector<ExternalKeysCollectionDocument>> getNewExternalKeys(
+        OperationContext* opCtx,
+        StringData purpose,
+        const LogicalTime& newerThanThis,
+        bool useMajority) override;
 
     /**
      * Directly inserts a key document to the storage
@@ -67,6 +78,17 @@ public:
     }
 
 private:
+    /**
+     * Returns keys in the given collection that match the given purpose and have an expiresAt value
+     * greater than newerThanThis, using readConcern level majority if possible.
+     */
+    template <typename KeyDocumentType>
+    StatusWith<std::vector<KeyDocumentType>> _getNewKeys(OperationContext* opCtx,
+                                                         const NamespaceString& nss,
+                                                         StringData purpose,
+                                                         const LogicalTime& newerThanThis,
+                                                         bool useMajority);
+
     StatusWith<Shard::QueryResponse> _query(OperationContext* opCtx,
                                             const ReadPreferenceSetting& readPref,
                                             const repl::ReadConcernLevel& readConcernLevel,
diff --git a/src/mongo/db/keys_collection_client_sharded.cpp b/src/mongo/db/keys_collection_client_sharded.cpp
index 08f56481b19..7db511bcaca 100644
--- a/src/mongo/db/keys_collection_client_sharded.cpp
+++ b/src/mongo/db/keys_collection_client_sharded.cpp
@@ -39,7 +39,7 @@ KeysCollectionClientSharded::KeysCollectionClientSharded(ShardingCatalogClient*
     : _catalogClient(client) {}
 
 
-StatusWith<std::vector<KeysCollectionDocument>> KeysCollectionClientSharded::getNewKeys(
+StatusWith<std::vector<KeysCollectionDocument>> KeysCollectionClientSharded::getNewInternalKeys(
     OperationContext* opCtx,
     StringData purpose,
     const LogicalTime& newerThanThis,
@@ -49,6 +49,14 @@ StatusWith<std::vector<KeysCollectionDocument>> KeysCollectionClientSharded::get
         opCtx, purpose, newerThanThis, repl::ReadConcernLevel::kMajorityReadConcern);
 }
 
+StatusWith<std::vector<ExternalKeysCollectionDocument>>
+KeysCollectionClientSharded::getNewExternalKeys(OperationContext* opCtx,
+                                                StringData purpose,
+                                                const LogicalTime& newerThanThis,
+                                                bool useMajority) {
+    return std::vector<ExternalKeysCollectionDocument>{};
+}
+
 Status KeysCollectionClientSharded::insertNewKey(OperationContext* opCtx, const BSONObj& doc) {
     return _catalogClient->insertConfigDocument(opCtx,
                                                 NamespaceString::kKeysCollectionNamespace,
diff --git a/src/mongo/db/keys_collection_client_sharded.h b/src/mongo/db/keys_collection_client_sharded.h
index 111948e0139..5ab20a626cd 100644
--- a/src/mongo/db/keys_collection_client_sharded.h
+++ b/src/mongo/db/keys_collection_client_sharded.h
@@ -40,13 +40,25 @@ public:
     KeysCollectionClientSharded(ShardingCatalogClient*);
 
     /**
-     * Returns keys for the given purpose and with an expiresAt value greater than newerThanThis,
-     * using readConcern level majority if possible.
+     * Returns keys in the config server's admin.system.keys that match the given purpose and have
+     * an expiresAt value greater than newerThanThis. Uses readConcern level majority if possible.
      */
-    StatusWith<std::vector<KeysCollectionDocument>> getNewKeys(OperationContext* opCtx,
-                                                               StringData purpose,
-                                                               const LogicalTime& newerThanThis,
-                                                               bool useMajority) override;
+    StatusWith<std::vector<KeysCollectionDocument>> getNewInternalKeys(
+        OperationContext* opCtx,
+        StringData purpose,
+        const LogicalTime& newerThanThis,
+        bool useMajority) override;
+
+    /**
+     * Returns validation-only keys copied from other clusters that match the given purpose
+     * and have an expiresAt value greater than newerThanThis. Uses readConcern level majority if
+     * possible. Currently, a sharded cluster never copies cluster time keys from other clusters.
+     */
+    StatusWith<std::vector<ExternalKeysCollectionDocument>> getNewExternalKeys(
+        OperationContext* opCtx,
+        StringData purpose,
+        const LogicalTime& newerThanThis,
+        bool useMajority) override;
 
     /**
      * Directly inserts a key document to the storage
diff --git a/src/mongo/db/keys_collection_manager.cpp b/src/mongo/db/keys_collection_manager.cpp
index 45d81b2aa96..e03984f4808 100644
--- a/src/mongo/db/keys_collection_manager.cpp
+++ b/src/mongo/db/keys_collection_manager.cpp
@@ -97,43 +97,49 @@ KeysCollectionManager::KeysCollectionManager(std::string purpose,
       _keysCache(_purpose, _client.get()) {}
 
 
-StatusWith<KeysCollectionDocument> KeysCollectionManager::getKeyForValidation(
+StatusWith<std::vector<KeysCollectionDocument>> KeysCollectionManager::getKeysForValidation(
     OperationContext* opCtx, long long keyId, const LogicalTime& forThisTime) {
-    auto keyStatus = _getKeyWithKeyIdCheck(keyId, forThisTime);
+    auto swInternalKey = _keysCache.getInternalKeyById(keyId, forThisTime);
 
-    if (keyStatus != ErrorCodes::KeyNotFound) {
-        return keyStatus;
+    if (swInternalKey == ErrorCodes::KeyNotFound) {
+        _refresher.refreshNow(opCtx);
+        swInternalKey = _keysCache.getInternalKeyById(keyId, forThisTime);
     }
 
-    _refresher.refreshNow(opCtx);
+    std::vector<KeysCollectionDocument> keys;
 
-    return _getKeyWithKeyIdCheck(keyId, forThisTime);
-}
+    if (swInternalKey.isOK()) {
+        keys.push_back(std::move(swInternalKey.getValue()));
+    }
 
-StatusWith<KeysCollectionDocument> KeysCollectionManager::getKeyForSigning(
-    OperationContext* opCtx, const LogicalTime& forThisTime) {
-    return _getKey(forThisTime);
-}
+    auto swExternalKeys = _keysCache.getExternalKeysById(keyId, forThisTime);
 
-StatusWith<KeysCollectionDocument> KeysCollectionManager::_getKeyWithKeyIdCheck(
-    long long keyId, const LogicalTime& forThisTime) {
-    auto keyStatus = _keysCache.getKeyById(keyId, forThisTime);
+    if (swExternalKeys.isOK()) {
+        for (auto& externalKey : swExternalKeys.getValue()) {
+            KeysCollectionDocument key(externalKey.getKeyId());
+            key.setKeysCollectionDocumentBase(externalKey.getKeysCollectionDocumentBase());
+            keys.push_back(std::move(key));
+        };
+    }
 
-    if (!keyStatus.isOK()) {
-        return keyStatus;
+    if (keys.empty()) {
+        return {ErrorCodes::KeyNotFound,
+                str::stream() << "No keys found for " << _purpose << " that is valid for time: "
+                              << forThisTime.toString() << " with id: " << keyId};
     }
 
-    return keyStatus.getValue();
+    return std::move(keys);
 }
 
-StatusWith<KeysCollectionDocument> KeysCollectionManager::_getKey(const LogicalTime& forThisTime) {
-    auto keyStatus = _keysCache.getKey(forThisTime);
+StatusWith<KeysCollectionDocument> KeysCollectionManager::getKeyForSigning(
+    OperationContext* opCtx, const LogicalTime& forThisTime) {
+    auto swKey = _keysCache.getInternalKey(forThisTime);
 
-    if (!keyStatus.isOK()) {
-        return keyStatus;
+    if (!swKey.isOK()) {
+        return swKey;
     }
 
-    const auto& key = keyStatus.getValue();
+    const auto& key = swKey.getValue();
 
     if (key.getExpiresAt() < forThisTime) {
         return {ErrorCodes::KeyNotFound,
diff --git a/src/mongo/db/keys_collection_manager.h b/src/mongo/db/keys_collection_manager.h
index 2bb3ca00744..73caf91fff9 100644
--- a/src/mongo/db/keys_collection_manager.h
+++ b/src/mongo/db/keys_collection_manager.h
@@ -75,20 +75,18 @@ public:
                           Seconds keyValidForInterval);
 
     /**
-     * Return a key that is valid for the given time and also matches the keyId. Note that this call
-     * can block if it will need to do a refresh.
+     * Returns the validation keys that are valid for the given time and also match the keyId. Does
+     * a blocking refresh if there is no matching internal key. If there is a matching internal key,
+     * includes it as first key in the resulting vector.
      *
-     * Throws ErrorCode::ExceededTimeLimit if it times out.
+     * Throws ExceededTimeLimit if the refresh times out, and KeyNotFound if there are no such keys.
      */
-    StatusWith<KeysCollectionDocument> getKeyForValidation(OperationContext* opCtx,
-                                                           long long keyId,
-                                                           const LogicalTime& forThisTime);
+    StatusWith<std::vector<KeysCollectionDocument>> getKeysForValidation(
+        OperationContext* opCtx, long long keyId, const LogicalTime& forThisTime);
 
     /**
-     * Returns a key that is valid for the given time. Note that unlike getKeyForValidation, this
-     * will never do a refresh.
-     *
-     * Throws ErrorCode::ExceededTimeLimit if it times out.
+     * Returns the signing key that is valid for the given time. Note that unlike
+     * getKeysForValidation, this will never do a refresh.
      */
     StatusWith<KeysCollectionDocument> getKeyForSigning(OperationContext* opCtx,
                                                         const LogicalTime& forThisTime);
@@ -194,17 +192,6 @@ private:
         bool _inShutdown = false;
     };
 
-    /**
-     * Return a key that is valid for the given time and also matches the keyId.
-     */
-    StatusWith<KeysCollectionDocument> _getKeyWithKeyIdCheck(long long keyId,
-                                                             const LogicalTime& forThisTime);
-
-    /**
-     * Return a key that is valid for the given time.
-     */
-    StatusWith<KeysCollectionDocument> _getKey(const LogicalTime& forThisTime);
-
     std::unique_ptr<KeysCollectionClient> _client;
     const std::string _purpose;
     const Seconds _keyValidForInterval;
diff --git a/src/mongo/db/keys_collection_manager_sharding_test.cpp b/src/mongo/db/keys_collection_manager_sharding_test.cpp
index 290934396d4..a51ca4f7b38 100644
--- a/src/mongo/db/keys_collection_manager_sharding_test.cpp
+++ b/src/mongo/db/keys_collection_manager_sharding_test.cpp
@@ -80,7 +80,7 @@ TEST_F(KeysManagerShardedTest, GetKeyForValidationTimesOutIfRefresherIsNotRunnin
                                               ErrorCodes::ExceededTimeLimit);
 
     ASSERT_THROWS(
-        keyManager()->getKeyForValidation(operationContext(), 1, LogicalTime(Timestamp(100, 0))),
+        keyManager()->getKeysForValidation(operationContext(), 1, LogicalTime(Timestamp(100, 0))),
         DBException);
 }
 
@@ -88,7 +88,7 @@ TEST_F(KeysManagerShardedTest, GetKeyForValidationErrorsIfKeyDoesntExist) {
     keyManager()->startMonitoring(getServiceContext());
 
     auto keyStatus =
-        keyManager()->getKeyForValidation(operationContext(), 1, LogicalTime(Timestamp(100, 0)));
+        keyManager()->getKeysForValidation(operationContext(), 1, LogicalTime(Timestamp(100, 0)));
     ASSERT_EQ(ErrorCodes::KeyNotFound, keyStatus.getStatus());
 }
 
@@ -102,10 +102,10 @@ TEST_F(KeysManagerShardedTest, GetKeyWithSingleKey) {
         operationContext(), NamespaceString::kKeysCollectionNamespace, origKey1.toBSON()));
 
     auto keyStatus =
-        keyManager()->getKeyForValidation(operationContext(), 1, LogicalTime(Timestamp(100, 0)));
+        keyManager()->getKeysForValidation(operationContext(), 1, LogicalTime(Timestamp(100, 0)));
     ASSERT_OK(keyStatus.getStatus());
 
-    auto key = keyStatus.getValue();
+    auto key = keyStatus.getValue().front();
     ASSERT_EQ(1, key.getKeyId());
     ASSERT_EQ(origKey1.getKey(), key.getKey());
     ASSERT_EQ(Timestamp(105, 0), key.getExpiresAt().asTimestamp());
@@ -127,19 +127,19 @@ TEST_F(KeysManagerShardedTest, GetKeyWithMultipleKeys) {
         operationContext(), NamespaceString::kKeysCollectionNamespace, origKey2.toBSON()));
 
     auto keyStatus =
-        keyManager()->getKeyForValidation(operationContext(), 1, LogicalTime(Timestamp(100, 0)));
+        keyManager()->getKeysForValidation(operationContext(), 1, LogicalTime(Timestamp(100, 0)));
     ASSERT_OK(keyStatus.getStatus());
 
-    auto key = keyStatus.getValue();
+    auto key = keyStatus.getValue().front();
     ASSERT_EQ(1, key.getKeyId());
     ASSERT_EQ(origKey1.getKey(), key.getKey());
     ASSERT_EQ(Timestamp(105, 0), key.getExpiresAt().asTimestamp());
 
     keyStatus =
-        keyManager()->getKeyForValidation(operationContext(), 2, LogicalTime(Timestamp(100, 0)));
+        keyManager()->getKeysForValidation(operationContext(), 2, LogicalTime(Timestamp(100, 0)));
     ASSERT_OK(keyStatus.getStatus());
 
-    key = keyStatus.getValue();
+    key = keyStatus.getValue().front();
     ASSERT_EQ(2, key.getKeyId());
     ASSERT_EQ(origKey2.getKey(), key.getKey());
     ASSERT_EQ(Timestamp(205, 0), key.getExpiresAt().asTimestamp());
@@ -155,7 +155,7 @@ TEST_F(KeysManagerShardedTest, GetKeyShouldErrorIfKeyIdMismatchKey) {
         operationContext(), NamespaceString::kKeysCollectionNamespace, origKey1.toBSON()));
 
     auto keyStatus =
-        keyManager()->getKeyForValidation(operationContext(), 2, LogicalTime(Timestamp(100, 0)));
+        keyManager()->getKeysForValidation(operationContext(), 2, LogicalTime(Timestamp(100, 0)));
     ASSERT_EQ(ErrorCodes::KeyNotFound, keyStatus.getStatus());
 }
 
@@ -174,22 +174,22 @@ TEST_F(KeysManagerShardedTest, GetKeyWithoutRefreshShouldReturnRightKey) {
         operationContext(), NamespaceString::kKeysCollectionNamespace, origKey2.toBSON()));
 
     {
-        auto keyStatus = keyManager()->getKeyForValidation(
+        auto keyStatus = keyManager()->getKeysForValidation(
             operationContext(), 1, LogicalTime(Timestamp(100, 0)));
         ASSERT_OK(keyStatus.getStatus());
 
-        auto key = keyStatus.getValue();
+        auto key = keyStatus.getValue().front();
         ASSERT_EQ(1, key.getKeyId());
         ASSERT_EQ(origKey1.getKey(), key.getKey());
         ASSERT_EQ(Timestamp(105, 0), key.getExpiresAt().asTimestamp());
     }
 
     {
-        auto keyStatus = keyManager()->getKeyForValidation(
+        auto keyStatus = keyManager()->getKeysForValidation(
             operationContext(), 2, LogicalTime(Timestamp(105, 0)));
         ASSERT_OK(keyStatus.getStatus());
 
-        auto key = keyStatus.getValue();
+        auto key = keyStatus.getValue().front();
         ASSERT_EQ(2, key.getKeyId());
         ASSERT_EQ(origKey2.getKey(), key.getKey());
         ASSERT_EQ(Timestamp(110, 0), key.getExpiresAt().asTimestamp());
@@ -311,10 +311,10 @@ TEST_F(KeysManagerShardedTest, ShouldStillBeAbleToUpdateCacheEvenIfItCantCreateK
     }
 
     auto keyStatus =
-        keyManager()->getKeyForValidation(operationContext(), 1, LogicalTime(Timestamp(100, 0)));
+        keyManager()->getKeysForValidation(operationContext(), 1, LogicalTime(Timestamp(100, 0)));
     ASSERT_OK(keyStatus.getStatus());
 
-    auto key = keyStatus.getValue();
+    auto key = keyStatus.getValue().front();
     ASSERT_EQ(1, key.getKeyId());
     ASSERT_EQ(origKey1.getKey(), key.getKey());
     ASSERT_EQ(Timestamp(105, 0), key.getExpiresAt().asTimestamp());
@@ -330,7 +330,7 @@ TEST_F(KeysManagerShardedTest, ShouldNotCreateKeysWithDisableKeyGenerationFailPo
         keyManager()->enableKeyGenerator(operationContext(), true);
 
         keyManager()->refreshNow(operationContext());
-        auto keyStatus = keyManager()->getKeyForValidation(
+        auto keyStatus = keyManager()->getKeysForValidation(
             operationContext(), 1, LogicalTime(Timestamp(100, 0)));
         ASSERT_EQ(ErrorCodes::KeyNotFound, keyStatus.getStatus());
     }
@@ -353,7 +353,7 @@ TEST_F(KeysManagerShardedTest, HasSeenKeysIsFalseUntilKeysAreFound) {
         keyManager()->enableKeyGenerator(operationContext(), true);
 
         keyManager()->refreshNow(operationContext());
-        auto keyStatus = keyManager()->getKeyForValidation(
+        auto keyStatus = keyManager()->getKeysForValidation(
             operationContext(), 1, LogicalTime(Timestamp(100, 0)));
         ASSERT_EQ(ErrorCodes::KeyNotFound, keyStatus.getStatus());
 
diff --git a/src/mongo/db/logical_time_validator.cpp b/src/mongo/db/logical_time_validator.cpp
index c56a3a146f0..d2b8866a79c 100644
--- a/src/mongo/db/logical_time_validator.cpp
+++ b/src/mongo/db/logical_time_validator.cpp
@@ -164,23 +164,34 @@ Status LogicalTimeValidator::validate(OperationContext* opCtx, const SignedLogic
         }
     }
 
-    auto keyStatus =
-        _getKeyManagerCopy()->getKeyForValidation(opCtx, newTime.getKeyId(), newTime.getTime());
-    uassertStatusOK(keyStatus.getStatus());
+    auto keyStatusWith =
+        _getKeyManagerCopy()->getKeysForValidation(opCtx, newTime.getKeyId(), newTime.getTime());
+    auto status = keyStatusWith.getStatus();
 
-    const auto& key = keyStatus.getValue().getKey();
+    if (!status.isOK()) {
+        return status;
+    }
+
+    auto keys = keyStatusWith.getValue();
+    invariant(!keys.empty());
 
     const auto newProof = newTime.getProof();
     // Cluster time is only sent if a server's clock can verify and sign cluster times, so any
     // received cluster times should have proofs.
     invariant(newProof);
 
-    auto res = _timeProofService.checkProof(newTime.getTime(), newProof.get(), key);
-    if (res != Status::OK()) {
-        return res;
+    auto firstError = Status::OK();
+    for (const auto& key : keys) {
+        auto proofStatus =
+            _timeProofService.checkProof(newTime.getTime(), newProof.get(), key.getKey());
+        if (proofStatus.isOK()) {
+            return Status::OK();
+        } else if (firstError.isOK()) {
+            firstError = proofStatus;
+        }
     }
 
-    return Status::OK();
+    return firstError;
 }
 
 void LogicalTimeValidator::init(ServiceContext* service) {
diff --git a/src/mongo/db/logical_time_validator.h b/src/mongo/db/logical_time_validator.h
index 1e8fbac9933..1b78c51d1f5 100644
--- a/src/mongo/db/logical_time_validator.h
+++ b/src/mongo/db/logical_time_validator.h
@@ -71,7 +71,7 @@ public:
     SignedLogicalTime signLogicalTime(OperationContext* opCtx, const LogicalTime& newTime);
 
     /**
-     * Returns true if the signature of newTime is valid.
+     * Validates the signature of newTime and returns the resulting status.
      */
     Status validate(OperationContext* opCtx, const SignedLogicalTime& newTime);
 
diff --git a/src/mongo/db/namespace_string.cpp b/src/mongo/db/namespace_string.cpp
index d25886e4904..eea72c9e3f8 100644
--- a/src/mongo/db/namespace_string.cpp
+++ b/src/mongo/db/namespace_string.cpp
@@ -132,6 +132,12 @@ bool NamespaceString::isLegalClientSystemNS() const {
             return true;
         if (coll() == "system.backup_users")
             return true;
+        if (coll() == kExternalKeysCollectionNamespace.coll()) {
+            // TODO (SERVER-53404): This was added to allow client in an integration test to
+            // manually insert the key document into this system collection. Remove this when the
+            // tenant migration donor does the copying by itself.
+            return true;
+        }
     } else if (db() == kConfigDb) {
         if (coll() == "system.sessions")
             return true;