diff --git a/src/__phutil_library_map__.php b/src/__phutil_library_map__.php
--- a/src/__phutil_library_map__.php
+++ b/src/__phutil_library_map__.php
@@ -2091,6 +2091,7 @@
     'PhabricatorAuthOneTimeLoginTemporaryTokenType' => 'applications/auth/tokentype/PhabricatorAuthOneTimeLoginTemporaryTokenType.php',
     'PhabricatorAuthPassword' => 'applications/auth/storage/PhabricatorAuthPassword.php',
     'PhabricatorAuthPasswordEditor' => 'applications/auth/editor/PhabricatorAuthPasswordEditor.php',
+    'PhabricatorAuthPasswordEngine' => 'applications/auth/engine/PhabricatorAuthPasswordEngine.php',
     'PhabricatorAuthPasswordPHIDType' => 'applications/auth/phid/PhabricatorAuthPasswordPHIDType.php',
     'PhabricatorAuthPasswordQuery' => 'applications/auth/query/PhabricatorAuthPasswordQuery.php',
     'PhabricatorAuthPasswordResetTemporaryTokenType' => 'applications/auth/tokentype/PhabricatorAuthPasswordResetTemporaryTokenType.php',
@@ -2099,6 +2100,7 @@
     'PhabricatorAuthPasswordTestCase' => 'applications/auth/__tests__/PhabricatorAuthPasswordTestCase.php',
     'PhabricatorAuthPasswordTransaction' => 'applications/auth/storage/PhabricatorAuthPasswordTransaction.php',
     'PhabricatorAuthPasswordTransactionType' => 'applications/auth/xaction/PhabricatorAuthPasswordTransactionType.php',
+    'PhabricatorAuthPasswordUpgradeTransaction' => 'applications/auth/xaction/PhabricatorAuthPasswordUpgradeTransaction.php',
     'PhabricatorAuthProvider' => 'applications/auth/provider/PhabricatorAuthProvider.php',
     'PhabricatorAuthProviderConfig' => 'applications/auth/storage/PhabricatorAuthProviderConfig.php',
     'PhabricatorAuthProviderConfigController' => 'applications/auth/controller/config/PhabricatorAuthProviderConfigController.php',
@@ -7383,14 +7385,16 @@
       'PhabricatorApplicationTransactionInterface',
     ),
     'PhabricatorAuthPasswordEditor' => 'PhabricatorApplicationTransactionEditor',
+    'PhabricatorAuthPasswordEngine' => 'Phobject',
     'PhabricatorAuthPasswordPHIDType' => 'PhabricatorPHIDType',
     'PhabricatorAuthPasswordQuery' => 'PhabricatorCursorPagedPolicyAwareQuery',
     'PhabricatorAuthPasswordResetTemporaryTokenType' => 'PhabricatorAuthTemporaryTokenType',
     'PhabricatorAuthPasswordRevokeTransaction' => 'PhabricatorAuthPasswordTransactionType',
     'PhabricatorAuthPasswordRevoker' => 'PhabricatorAuthRevoker',
     'PhabricatorAuthPasswordTestCase' => 'PhabricatorTestCase',
-    'PhabricatorAuthPasswordTransaction' => 'PhabricatorApplicationTransaction',
+    'PhabricatorAuthPasswordTransaction' => 'PhabricatorModularTransaction',
     'PhabricatorAuthPasswordTransactionType' => 'PhabricatorModularTransactionType',
+    'PhabricatorAuthPasswordUpgradeTransaction' => 'PhabricatorAuthPasswordTransactionType',
     'PhabricatorAuthProvider' => 'Phobject',
     'PhabricatorAuthProviderConfig' => array(
       'PhabricatorAuthDAO',
diff --git a/src/applications/auth/__tests__/PhabricatorAuthPasswordTestCase.php b/src/applications/auth/__tests__/PhabricatorAuthPasswordTestCase.php
--- a/src/applications/auth/__tests__/PhabricatorAuthPasswordTestCase.php
+++ b/src/applications/auth/__tests__/PhabricatorAuthPasswordTestCase.php
@@ -28,4 +28,96 @@
       pht('Bad password should not match.'));
   }
 
+  public function testPasswordEngine() {
+    $password1 = new PhutilOpaqueEnvelope('the quick');
+    $password2 = new PhutilOpaqueEnvelope('brown fox');
+
+    $user = $this->generateNewTestUser();
+    $test_type = PhabricatorAuthPassword::PASSWORD_TYPE_TEST;
+    $account_type = PhabricatorAuthPassword::PASSWORD_TYPE_ACCOUNT;
+    $content_source = $this->newContentSource();
+
+    $engine = id(new PhabricatorAuthPasswordEngine())
+      ->setViewer($user)
+      ->setContentSource($content_source)
+      ->setPasswordType($test_type)
+      ->setObject($user);
+
+    $account_engine = id(new PhabricatorAuthPasswordEngine())
+      ->setViewer($user)
+      ->setContentSource($content_source)
+      ->setPasswordType($account_type)
+      ->setObject($user);
+
+    // We haven't set any passwords yet, so both passwords should be
+    // invalid.
+    $this->assertFalse($engine->isValidPassword($password1));
+    $this->assertFalse($engine->isValidPassword($password2));
+
+    $pass = PhabricatorAuthPassword::initializeNewPassword($user, $test_type)
+      ->setPassword($password1, $user)
+      ->save();
+
+    // The password should now be valid.
+    $this->assertTrue($engine->isValidPassword($password1));
+    $this->assertFalse($engine->isValidPassword($password2));
+
+    // But, since the password is a "test" password, it should not be a valid
+    // "account" password.
+    $this->assertFalse($account_engine->isValidPassword($password1));
+    $this->assertFalse($account_engine->isValidPassword($password2));
+
+    // Both passwords are unique for the "test" engine, since an active
+    // password of a given type doesn't collide with itself.
+    $this->assertTrue($engine->isUniquePassword($password1));
+    $this->assertTrue($engine->isUniquePassword($password2));
+
+    // The "test" password is no longer unique for the "account" engine.
+    $this->assertFalse($account_engine->isUniquePassword($password1));
+    $this->assertTrue($account_engine->isUniquePassword($password2));
+
+    $this->revokePassword($user, $pass);
+
+    // Now that we've revoked the password, it should no longer be valid.
+    $this->assertFalse($engine->isValidPassword($password1));
+    $this->assertFalse($engine->isValidPassword($password2));
+
+    // But it should be a revoked password.
+    $this->assertTrue($engine->isRevokedPassword($password1));
+    $this->assertFalse($engine->isRevokedPassword($password2));
+
+    // It should be revoked for both roles: revoking a "test" password also
+    // prevents you from choosing it as a new "account" password.
+    $this->assertTrue($account_engine->isRevokedPassword($password1));
+    $this->assertFalse($account_engine->isValidPassword($password2));
+
+    // The revoked password makes this password non-unique for all account
+    // types.
+    $this->assertFalse($engine->isUniquePassword($password1));
+    $this->assertTrue($engine->isUniquePassword($password2));
+    $this->assertFalse($account_engine->isUniquePassword($password1));
+    $this->assertTrue($account_engine->isUniquePassword($password2));
+  }
+
+  private function revokePassword(
+    PhabricatorUser $actor,
+    PhabricatorAuthPassword $password) {
+
+    $content_source = $this->newContentSource();
+    $revoke_type = PhabricatorAuthPasswordRevokeTransaction::TRANSACTIONTYPE;
+
+    $xactions = array();
+
+    $xactions[] = $password->getApplicationTransactionTemplate()
+      ->setTransactionType($revoke_type)
+      ->setNewValue(true);
+
+    $editor = $password->getApplicationTransactionEditor()
+      ->setActor($actor)
+      ->setContinueOnNoEffect(true)
+      ->setContinueOnMissingFields(true)
+      ->setContentSource($content_source)
+      ->applyTransactions($password, $xactions);
+  }
+
 }
diff --git a/src/applications/auth/engine/PhabricatorAuthPasswordEngine.php b/src/applications/auth/engine/PhabricatorAuthPasswordEngine.php
new file mode 100644
--- /dev/null
+++ b/src/applications/auth/engine/PhabricatorAuthPasswordEngine.php
@@ -0,0 +1,240 @@
+<?php
+
+final class PhabricatorAuthPasswordEngine
+  extends Phobject {
+
+  private $viewer;
+  private $contentSource;
+  private $object;
+  private $passwordType;
+  private $upgradeHashers = true;
+
+  public function setViewer(PhabricatorUser $viewer) {
+    $this->viewer = $viewer;
+    return $this;
+  }
+
+  public function getViewer() {
+    return $this->viewer;
+  }
+
+  public function setContentSource(PhabricatorContentSource $content_source) {
+    $this->contentSource = $content_source;
+    return $this;
+  }
+
+  public function getContentSource() {
+    return $this->contentSource;
+  }
+
+  public function setObject($object) {
+    $this->object = $object;
+    return $this;
+  }
+
+  public function getObject() {
+    return $this->object;
+  }
+
+  public function setPasswordType($password_type) {
+    $this->passwordType = $password_type;
+    return $this;
+  }
+
+  public function getPasswordType() {
+    return $this->passwordType;
+  }
+
+  public function setUpgradeHashers($upgrade_hashers) {
+    $this->upgradeHashers = $upgrade_hashers;
+    return $this;
+  }
+
+  public function getUpgradeHashers() {
+    return $this->upgradeHashers;
+  }
+
+  public function isValidPassword(PhutilOpaqueEnvelope $envelope) {
+    $this->requireSetup();
+
+    $password_type = $this->getPasswordType();
+
+    $passwords = $this->newQuery()
+      ->withPasswordTypes(array($password_type))
+      ->withIsRevoked(false)
+      ->execute();
+
+    $matches = $this->getMatches($envelope, $passwords);
+    if (!$matches) {
+      return false;
+    }
+
+    if ($this->shouldUpgradeHashers()) {
+      $this->upgradeHashers($envelope, $matches);
+    }
+
+    return true;
+  }
+
+  public function isUniquePassword(PhutilOpaqueEnvelope $envelope) {
+    $this->requireSetup();
+
+    $password_type = $this->getPasswordType();
+
+    // To test that the password is unique, we're loading all active and
+    // revoked passwords for all roles for the given user, then throwing out
+    // the active passwords for the current role (so a password can't
+    // collide with itself).
+
+    // Note that two different objects can have the same password (say,
+    // users @alice and @bailey). We're only preventing @alice from using
+    // the same password for everything.
+
+    $passwords = $this->newQuery()
+      ->execute();
+
+    foreach ($passwords as $key => $password) {
+      $same_type = ($password->getPasswordType() === $password_type);
+      $is_active = !$password->getIsRevoked();
+
+      if ($same_type && $is_active) {
+        unset($passwords[$key]);
+      }
+    }
+
+    $matches = $this->getMatches($envelope, $passwords);
+
+    return !$matches;
+  }
+
+  public function isRevokedPassword(PhutilOpaqueEnvelope $envelope) {
+    $this->requireSetup();
+
+    // To test if a password is revoked, we're loading all revoked passwords
+    // across all roles for the given user. If a password was revoked in one
+    // role, you can't reuse it in a different role.
+
+    $passwords = $this->newQuery()
+      ->withIsRevoked(true)
+      ->execute();
+
+    $matches = $this->getMatches($envelope, $passwords);
+
+    return (bool)$matches;
+  }
+
+  private function requireSetup() {
+    if (!$this->getObject()) {
+      throw new PhutilInvalidStateException('setObject');
+    }
+
+    if (!$this->getPasswordType()) {
+      throw new PhutilInvalidStateException('setPasswordType');
+    }
+
+    if (!$this->getViewer()) {
+      throw new PhutilInvalidStateException('setViewer');
+    }
+
+    if ($this->shouldUpgradeHashers()) {
+      if (!$this->getContentSource()) {
+        throw new PhutilInvalidStateException('setContentSource');
+      }
+    }
+  }
+
+  private function shouldUpgradeHashers() {
+    if (!$this->getUpgradeHashers()) {
+      return false;
+    }
+
+    if (PhabricatorEnv::isReadOnly()) {
+      // Don't try to upgrade hashers if we're in read-only mode, since we
+      // won't be able to write the new hash to the database.
+      return false;
+    }
+
+    return true;
+  }
+
+  private function newQuery() {
+    $viewer = $this->getViewer();
+    $object = $this->getObject();
+    $password_type = $this->getPasswordType();
+
+    return id(new PhabricatorAuthPasswordQuery())
+      ->setViewer($viewer)
+      ->withObjectPHIDs(array($object->getPHID()));
+  }
+
+  private function getMatches(
+    PhutilOpaqueEnvelope $envelope,
+    array $passwords) {
+
+    $object = $this->getObject();
+
+    $matches = array();
+    foreach ($passwords as $password) {
+      try {
+        $is_match = $password->comparePassword($envelope, $object);
+      } catch (PhabricatorPasswordHasherUnavailableException $ex) {
+        $is_match = false;
+      }
+
+      if ($is_match) {
+        $matches[] = $password;
+      }
+    }
+
+    return $matches;
+  }
+
+  private function upgradeHashers(
+    PhutilOpaqueEnvelope $envelope,
+    array $passwords) {
+
+    assert_instances_of($passwords, 'PhabricatorAuthPassword');
+
+    $need_upgrade = array();
+    foreach ($passwords as $password) {
+      if (!$password->canUpgrade()) {
+        continue;
+      }
+      $need_upgrade[] = $password;
+    }
+
+    if (!$need_upgrade) {
+      return;
+    }
+
+    $upgrade_type = PhabricatorAuthPasswordUpgradeTransaction::TRANSACTIONTYPE;
+    $viewer = $this->getViewer();
+    $content_source = $this->getContentSource();
+
+    $unguarded = AphrontWriteGuard::beginScopedUnguardedWrites();
+    foreach ($need_upgrade as $password) {
+
+      // This does the actual upgrade. We then apply a transaction to make
+      // the upgrade more visible and auditable.
+      $old_hasher = $password->getHasher();
+      $password->upgradePasswordHasher($envelope, $this->getObject());
+      $new_hasher = $password->getHasher();
+
+      $xactions = array();
+
+      $xactions[] = $password->getApplicationTransactionTemplate()
+        ->setTransactionType($upgrade_type)
+        ->setOldValue($old_hasher->getHashName())
+        ->setNewValue($new_hasher->getHashName());
+
+      $editor = $password->getApplicationTransactionEditor()
+        ->setActor($viewer)
+        ->setContinueOnNoEffect(true)
+        ->setContinueOnMissingFields(true)
+        ->setContentSource($content_source)
+        ->applyTransactions($password, $xactions);
+    }
+    unset($unguarded);
+  }
+
+}
diff --git a/src/applications/auth/storage/PhabricatorAuthPassword.php b/src/applications/auth/storage/PhabricatorAuthPassword.php
--- a/src/applications/auth/storage/PhabricatorAuthPassword.php
+++ b/src/applications/auth/storage/PhabricatorAuthPassword.php
@@ -58,11 +58,46 @@
     return $this;
   }
 
+  public function getHasher() {
+    $hash = $this->newPasswordEnvelope();
+    return PhabricatorPasswordHasher::getHasherForHash($hash);
+  }
+
+  public function canUpgrade() {
+    $hash = $this->newPasswordEnvelope();
+    return PhabricatorPasswordHasher::canUpgradeHash($hash);
+  }
+
+  public function upgradePasswordHasher(
+    PhutilOpaqueEnvelope $envelope,
+    PhabricatorUser $object) {
+
+    // Before we make changes, double check that this is really the correct
+    // password. It could be really bad if we "upgraded" a password and changed
+    // the secret!
+
+    if (!$this->comparePassword($envelope, $object)) {
+      throw new Exception(
+        pht(
+          'Attempting to upgrade password hasher, but the password for the '.
+          'upgrade is not the stored credential!'));
+    }
+
+    return $this->setPassword($envelope, $object);
+  }
+
   public function setPassword(
     PhutilOpaqueEnvelope $password,
     PhabricatorUser $object) {
 
     $hasher = PhabricatorPasswordHasher::getBestHasher();
+    return $this->setPasswordWithHasher($password, $object, $hasher);
+  }
+
+  public function setPasswordWithHasher(
+    PhutilOpaqueEnvelope $password,
+    PhabricatorUser $object,
+    PhabricatorPasswordHasher $hasher) {
 
     $digest = $this->digestPassword($password, $object);
     $hash = $hasher->getPasswordHashForStorage($digest);
@@ -76,12 +111,15 @@
     PhabricatorUser $object) {
 
     $digest = $this->digestPassword($password, $object);
-    $raw_hash = $this->getPasswordHash();
-    $hash = new PhutilOpaqueEnvelope($raw_hash);
+    $hash = $this->newPasswordEnvelope();
 
     return PhabricatorPasswordHasher::comparePassword($digest, $hash);
   }
 
+  private function newPasswordEnvelope() {
+    return new PhutilOpaqueEnvelope($this->getPasswordHash());
+  }
+
   private function digestPassword(
     PhutilOpaqueEnvelope $password,
     PhabricatorUser $object) {
diff --git a/src/applications/auth/storage/PhabricatorAuthPasswordTransaction.php b/src/applications/auth/storage/PhabricatorAuthPasswordTransaction.php
--- a/src/applications/auth/storage/PhabricatorAuthPasswordTransaction.php
+++ b/src/applications/auth/storage/PhabricatorAuthPasswordTransaction.php
@@ -1,7 +1,7 @@
 <?php
 
 final class PhabricatorAuthPasswordTransaction
-  extends PhabricatorApplicationTransaction {
+  extends PhabricatorModularTransaction {
 
   public function getApplicationName() {
     return 'auth';
diff --git a/src/applications/auth/xaction/PhabricatorAuthPasswordUpgradeTransaction.php b/src/applications/auth/xaction/PhabricatorAuthPasswordUpgradeTransaction.php
new file mode 100644
--- /dev/null
+++ b/src/applications/auth/xaction/PhabricatorAuthPasswordUpgradeTransaction.php
@@ -0,0 +1,24 @@
+<?php
+
+final class PhabricatorAuthPasswordUpgradeTransaction
+  extends PhabricatorAuthPasswordTransactionType {
+
+  const TRANSACTIONTYPE = 'password.upgrade';
+
+  public function generateOldValue($object) {
+    return $this->getStorage()->getOldValue();
+  }
+
+  public function generateNewValue($object, $value) {
+    return (bool)$value;
+  }
+
+  public function getTitle() {
+    return pht(
+      '%s upgraded the hash algorithm for this password from "%s" to "%s".',
+      $this->renderAuthor(),
+      $this->renderOldValue(),
+      $this->renderNewValue());
+  }
+
+}