diff --git a/Documentation/config-gerrit.txt b/Documentation/config-gerrit.txt
index a0e00a5..f82566b 100644
--- a/Documentation/config-gerrit.txt
+++ b/Documentation/config-gerrit.txt
@@ -141,6 +141,14 @@
 directory using either an anonymous request, or the configured
 <<ldap.username,ldap.username>> identity. Gerrit can also use kerberos if
 <<ldap.authentication,ldap.authentication>> is set to `GSSAPI`.
++
+If link:#auth.gitBasicAuthPolicy[`auth.gitBasicAuthPolicy`] is set to `HTTP`,
+the randomly generated HTTP password is used for authentication. On the other hand,
+if link:#auth.gitBasicAuthPolicy[`auth.gitBasicAuthPolicy`] is set to `HTTP_LDAP`,
+the password in the request is first checked against the HTTP password and, if
+it does not match, it is then validated against the LDAP password.
+Service users that only exist in the Gerrit database are authenticated by their
+HTTP passwords.
 
 * `LDAP_BIND`
 +
@@ -164,6 +172,12 @@
 Site owners have to register their application before getting started. Note
 that provider specific plugins must be used with this authentication scheme.
 +
+Git clients may send OAuth 2 access tokens instead of passwords in the Basic
+authentication header. Note that provider specific plugins must be installed to
+facilitate this authentication scheme. If multiple OAuth 2 provider plugins are
+installed one of them must be selected as default with the
+`auth.gitOAuthProvider` option.
++
 * `DEVELOPMENT_BECOME_ANY_ACCOUNT`
 +
 *DO NOT USE*.  Only for use in a development environment.
@@ -279,7 +293,7 @@
 [[auth.httpHeader]]auth.httpHeader::
 +
 HTTP header to trust the username from, or unset to select HTTP basic
-or digest authentication.  Only used if `auth.type` is set to `HTTP`.
+authentication.  Only used if `auth.type` is set to `HTTP`.
 
 [[auth.httpDisplaynameHeader]]auth.httpDisplaynameHeader::
 +
@@ -445,45 +459,16 @@
 the container.
 +
 This parameter only affects git over http traffic. If set to false
-then Gerrit will do the authentication (using DIGEST authentication).
+then Gerrit will do the authentication (using Basic authentication).
 +
 By default this is set to false.
 
-[[auth.gitBasicAuth]]auth.gitBasicAuth::
-+
-If true then Git over HTTP and HTTP/S traffic is authenticated using
-standard BasicAuth. Depending on the configured `auth.type`, credentials
-are validated against the randomly generated HTTP password, against LDAP
-(`auth.type = LDAP`) or against an OAuth 2 provider (`auth.type = OAUTH`).
-+
-This parameter affects git over HTTP traffic and access to the REST
-API. If set to false then Gerrit will authenticate through DIGEST
-authentication and the randomly generated HTTP password in the Gerrit
-database.
-+
-When `auth.type` is `LDAP`, users should authenticate using their LDAP passwords.
-However, if link:#auth.gitBasicAuthPolicy[`auth.gitBasicAuthPolicy`] is set to `HTTP`,
-the randomly generated HTTP password is used exclusively. In the other hand,
-if link:#auth.gitBasicAuthPolicy[`auth.gitBasicAuthPolicy`] is set to `HTTP_LDAP`,
-the password in the request is first checked against the HTTP password and, if
-it does not match, it is then validated against the LDAP password.
-Service users that only exist in the Gerrit database are authenticated by their
-HTTP passwords.
-+
-When `auth.type` is `OAUTH`, Git clients may send OAuth 2 access tokens
-instead of passwords in the Basic authentication header. Note that provider
-specific plugins must be installed to facilitate this authentication scheme.
-If multiple OAuth 2 provider plugins are installed one of them must be
-selected as default with the `auth.gitOAuthProvider` option.
-+
-By default this is set to false.
 
 [[auth.gitBasicAuthPolicy]]auth.gitBasicAuthPolicy::
 +
-When `auth.type` is `LDAP` and BasicAuth (i.e., link:#auth.gitBasicAuth[`auth.gitBasicAuth`]
-is set to true), it allows using either the generated HTTP password, the LDAP
-password or both to authenticate Git over HTTP and REST API requests. The
-supported values are:
+When `auth.type` is `LDAP`, it allows using either the generated HTTP password,
+the LDAP password, or both, to authenticate Git over HTTP and REST API
+requests. The supported values are:
 +
 *`HTTP`
 +
diff --git a/Documentation/config-sso.txt b/Documentation/config-sso.txt
index 5f35d73..04949bf 100644
--- a/Documentation/config-sso.txt
+++ b/Documentation/config-sso.txt
@@ -88,7 +88,7 @@
 Login using the other identity can only be performed after the linking is
 successful.
 
-== HTTP Basic/Digest Authentication
+== HTTP Basic Authentication
 
 When using HTTP authentication, Gerrit assumes that the servlet
 container or the frontend web server has performed all user
diff --git a/Documentation/dev-plugins.txt b/Documentation/dev-plugins.txt
index bb9c5c7..9a289e1 100644
--- a/Documentation/dev-plugins.txt
+++ b/Documentation/dev-plugins.txt
@@ -1443,7 +1443,7 @@
 ----
   curl -X POST -H "Content-Type: application/json" \
     -d '{message: "François", french: true}' \
-    --digest --user joe:secret \
+    --user joe:secret \
     http://host:port/a/changes/1/revisions/1/cookbook~say-hello
   "Bonjour François from change 1, patch set 1!"
 ----
@@ -2451,18 +2451,18 @@
 shows the error dialog. This means currently plugins cannot do any
 error handling and e.g. ignore expected errors.
 
-In the following example the REST endpoint would return '404 Not Found'
-if there is no HTTP password and the Gerrit core UI would display an
-error dialog for this. However having no HTTP password is not an error
-and the plugin may like to handle this case.
+In the following example the REST endpoint would return '404 Not
+Found' if the user has no username and the Gerrit core UI would
+display an error dialog for this. However having no username is
+not an error and the plugin may like to handle this case.
 
 [source,java]
 ----
-new RestApi("accounts").id("self").view("password.http")
+new RestApi("accounts").id("self").view("username")
     .get(new AsyncCallback<NativeString>() {
 
   @Override
-  public void onSuccess(NativeString httpPassword) {
+  public void onSuccess(NativeString username) {
     // TODO
   }
 
diff --git a/Documentation/dev-rest-api.txt b/Documentation/dev-rest-api.txt
index 308d4bd..fec9c97 100644
--- a/Documentation/dev-rest-api.txt
+++ b/Documentation/dev-rest-api.txt
@@ -47,7 +47,7 @@
 Example to set a Gerrit project's link:rest-api-projects.html#set-project-description[description]:
 
 ----
- curl -X PUT --digest --user john:2LlAB3K9B0PF --data-binary @project-desc.txt --header "Content-Type: application/json; charset=UTF-8" http://localhost:8080/a/projects/myproject/description
+ curl -X PUT --user john:2LlAB3K9B0PF --data-binary @project-desc.txt --header "Content-Type: application/json; charset=UTF-8" http://localhost:8080/a/projects/myproject/description
 ----
 
 === Authentication
@@ -56,7 +56,7 @@
 the command line:
 
 ----
- curl --digest --user username:password http://localhost:8080/a/path/to/api/
+ curl --user username:password http://localhost:8080/a/path/to/api/
 ----
 
 This makes it easy to switch users for testing of permissions.
@@ -65,7 +65,7 @@
 file (on Windows, `_netrc`):
 
 ----
- curl --digest -n http://localhost:8080/a/path/to/api/
+ curl -n http://localhost:8080/a/path/to/api/
 ----
 
 In both cases, the password should be the user's link:user-upload.html#http[HTTP password].
@@ -75,7 +75,7 @@
 To verify the headers returned from a REST API call, use `curl` in verbose mode:
 
 ----
-  curl -v -n --digest -X DELETE http://localhost:8080/a/path/to/api/
+  curl -v -n -X DELETE http://localhost:8080/a/path/to/api/
 ----
 
 The headers on both the request and the response will be printed.
diff --git a/Documentation/pgm-LocalUsernamesToLowerCase.txt b/Documentation/pgm-LocalUsernamesToLowerCase.txt
index 1136ced..f295225 100644
--- a/Documentation/pgm-LocalUsernamesToLowerCase.txt
+++ b/Documentation/pgm-LocalUsernamesToLowerCase.txt
@@ -9,7 +9,6 @@
 --
 _java_ -jar gerrit.war _LocalUsernamesToLowerCase
   -d <SITE_PATH>
-  [--threads]
 --
 
 == DESCRIPTION
@@ -40,10 +39,6 @@
 	Location of the gerrit.config file, and all other per-site
 	configuration data, supporting libraries and log files.
 
---threads::
-	Number of threads to perform the scan work with.  Defaults to
-	twice the number of CPUs available.
-
 == CONTEXT
 This command can only be run on a server which has direct
 connectivity to the metadata database.
diff --git a/Documentation/rest-api-accounts.txt b/Documentation/rest-api-accounts.txt
index f1b4abf..d4fa912 100644
--- a/Documentation/rest-api-accounts.txt
+++ b/Documentation/rest-api-accounts.txt
@@ -458,31 +458,6 @@
 
 If the account was already inactive the response is "`409 Conflict`".
 
-[[get-http-password]]
-=== Get HTTP Password
---
-'GET /accounts/link:#account-id[\{account-id\}]/password.http'
---
-
-Retrieves the HTTP password of an account.
-
-.Request
-----
-  GET /accounts/john.doe@example.com/password.http HTTP/1.0
-----
-
-.Response
-----
-  HTTP/1.1 200 OK
-  Content-Disposition: attachment
-  Content-Type: application/json; charset=UTF-8
-
-  )]}'
-  "Qmxlc21ydCB1YmVyIGFsbGVzIGluIGRlciBXZWx0IQ"
-----
-
-If the account does not have an HTTP password the response is "`404 Not Found`".
-
 [[set-http-password]]
 === Set/Generate HTTP Password
 --
@@ -1028,12 +1003,12 @@
   }
 ----
 
-Administrator that has authenticated with digest authentication:
+Administrator that has authenticated with basic authentication:
 
 .Request
 ----
   GET /a/accounts/self/capabilities HTTP/1.0
-  Authorization: Digest username="admin", realm="Gerrit Code Review", nonce="...
+  Authorization: Basic ABCDECF..
 ----
 
 .Response
@@ -1075,7 +1050,7 @@
 .Request
 ----
   GET /a/accounts/self/capabilities?q=createAccount&q=createGroup HTTP/1.0
-  Authorization: Digest username="admin", realm="Gerrit Code Review", nonce="...
+  Authorization: Basic ABCDEF...
 ----
 
 .Response
diff --git a/Documentation/rest-api-config.txt b/Documentation/rest-api-config.txt
index cd4f745..fd35353 100644
--- a/Documentation/rest-api-config.txt
+++ b/Documentation/rest-api-config.txt
@@ -470,9 +470,9 @@
 E.g. this could be used to flush all caches:
 +
 ----
-  for c in $(curl --digest --user jdoe:TNAuLkXsIV7w http://gerrit/a/config/server/caches/?format=TEXT_LIST | base64 -D)
+  for c in $(curl --user jdoe:TNAuLkXsIV7w http://gerrit/a/config/server/caches/?format=TEXT_LIST | base64 -D)
   do
-    curl --digest --user jdoe:TNAuLkXsIV7w -X POST http://gerrit/a/config/server/caches/$c/flush
+    curl --user jdoe:TNAuLkXsIV7w -X POST http://gerrit/a/config/server/caches/$c/flush
   done
 ----
 
@@ -1270,11 +1270,6 @@
 The link:config-gerrit.html#auth.httpPasswordUrl[URL to obtain an HTTP
 password]. Only set if link:config-gerrit.html#auth.type[authentication
 type] is `CUSTOM_EXTENSION`.
-|`is_git_basic_auth`          |optional, not set if `false`|
-Whether link:config-gerrit.html#auth.gitBasicAuth[basic authentication
-is used for Git over HTTP/HTTPS]. Only set if
-link:config-gerrit.html#auth.type[authentication type] is is `LDAP` or
-`LDAP_BIND`.
 |`git_basic_auth_policy`      |optional|
 The link:config-gerrit.html#auth.gitBasicAuthPolicy[policy] to authenticate
 Git over HTTP and REST API requests when
diff --git a/Documentation/rest-api-plugins.txt b/Documentation/rest-api-plugins.txt
index dfe9f0e..ce0fdb7 100644
--- a/Documentation/rest-api-plugins.txt
+++ b/Documentation/rest-api-plugins.txt
@@ -87,7 +87,7 @@
 following curl command can be used:
 
 ----
-  curl --digest --user admin:TNNuLkWsIV8w -X PUT --data-binary @delete-project-2.8.jar 'http://gerrit:8080/a/plugins/delete-project'
+  curl --user admin:TNNuLkWsIV8w -X PUT --data-binary @delete-project-2.8.jar 'http://gerrit:8080/a/plugins/delete-project'
 ----
 
 As response a link:#plugin-info[PluginInfo] entity is returned that
diff --git a/Documentation/rest-api.txt b/Documentation/rest-api.txt
index 7f7e62e..7928512 100644
--- a/Documentation/rest-api.txt
+++ b/Documentation/rest-api.txt
@@ -36,10 +36,8 @@
 `/a/`. For example to authenticate to `/projects/`, request the URL
 `/a/projects/`.
 
-By default Gerrit uses HTTP digest authentication with the HTTP password
-from the user's account settings page. HTTP basic authentication is used
-if link:config-gerrit.html#auth.gitBasicAuth[`auth.gitBasicAuth`] is set
-to true in the Gerrit configuration.
+Gerrit uses HTTP basic authentication with the HTTP password from the
+user's account settings page.
 
 [[preconditions]]
 === Preconditions
diff --git a/Documentation/user-upload.txt b/Documentation/user-upload.txt
index 6d0c47a..9efbb21 100644
--- a/Documentation/user-upload.txt
+++ b/Documentation/user-upload.txt
@@ -18,10 +18,9 @@
 On Gerrit installations that do not support SSH authentication, the
 user must authenticate via HTTP/HTTPS.
 
-When link:config-gerrit.html#auth.gitBasicAuth[gitBasicAuth] is enabled,
-the user is authenticated using standard BasicAuth. Depending on the value of
-link:#auth.gitBasicAuthPolicy[auth.gitBasicAuthPolicy], credentials are
-validated using:
+The user is authenticated using standard BasicAuth. Depending on the
+value of link:#auth.gitBasicAuthPolicy[auth.gitBasicAuthPolicy],
+credentials are validated using:
 
 * The randomly generated HTTP password on the `HTTP Password` tab
   in the user settings page if `gitBasicAuthPolicy` is `HTTP`.
@@ -29,9 +28,10 @@
 * Both, the HTTP and the LDAP passwords (in this order) if `gitBasicAuthPolicy`
   is `HTTP_LDAP`.
 
-When gitBasicAuthPolicy is not `LDAP`, the user's HTTP credentials can be
-accessed within Gerrit by going to `Settings`, and then accessing the `HTTP
-Password` tab.
+When gitBasicAuthPolicy is not `LDAP`, the user's HTTP credentials can
+be regenerated by going to `Settings`, and then accessing the `HTTP
+Password` tab. Revocation can effectively be done by regenerating the
+password and then forgetting it.
 
 For Gerrit installations where an link:config-gerrit.html#auth.httpPasswordUrl[HTTP password URL]
 is configured, the password can be obtained by clicking on `Obtain Password`
diff --git a/gerrit-acceptance-framework/src/test/java/com/google/gerrit/acceptance/AccountCreator.java b/gerrit-acceptance-framework/src/test/java/com/google/gerrit/acceptance/AccountCreator.java
index de0c430..e136bb3 100644
--- a/gerrit-acceptance-framework/src/test/java/com/google/gerrit/acceptance/AccountCreator.java
+++ b/gerrit-acceptance-framework/src/test/java/com/google/gerrit/acceptance/AccountCreator.java
@@ -20,12 +20,13 @@
 
 import com.google.gerrit.common.TimeUtil;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.client.AccountGroup;
 import com.google.gerrit.reviewdb.client.AccountGroupMember;
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.account.AccountByEmailCache;
 import com.google.gerrit.server.account.AccountCache;
+import com.google.gerrit.server.account.ExternalId;
+import com.google.gerrit.server.account.ExternalIdsUpdate;
 import com.google.gerrit.server.account.GroupCache;
 import com.google.gerrit.server.account.VersionedAuthorizedKeys;
 import com.google.gerrit.server.index.account.AccountIndexer;
@@ -39,8 +40,10 @@
 import com.jcraft.jsch.KeyPair;
 import java.io.ByteArrayOutputStream;
 import java.io.UnsupportedEncodingException;
+import java.util.ArrayList;
 import java.util.Collections;
 import java.util.HashMap;
+import java.util.List;
 import java.util.Map;
 
 @Singleton
@@ -54,6 +57,7 @@
   private final AccountCache accountCache;
   private final AccountByEmailCache byEmailCache;
   private final AccountIndexer indexer;
+  private final ExternalIdsUpdate.Server externalIdsUpdate;
 
   @Inject
   AccountCreator(
@@ -63,7 +67,8 @@
       SshKeyCache sshKeyCache,
       AccountCache accountCache,
       AccountByEmailCache byEmailCache,
-      AccountIndexer indexer) {
+      AccountIndexer indexer,
+      ExternalIdsUpdate.Server externalIdsUpdate) {
     accounts = new HashMap<>();
     reviewDbProvider = schema;
     this.authorizedKeys = authorizedKeys;
@@ -72,6 +77,7 @@
     this.accountCache = accountCache;
     this.byEmailCache = byEmailCache;
     this.indexer = indexer;
+    this.externalIdsUpdate = externalIdsUpdate;
   }
 
   public synchronized TestAccount create(
@@ -83,18 +89,14 @@
     try (ReviewDb db = reviewDbProvider.open()) {
       Account.Id id = new Account.Id(db.nextAccountId());
 
-      AccountExternalId extUser =
-          new AccountExternalId(
-              id, new AccountExternalId.Key(AccountExternalId.SCHEME_USERNAME, username));
+      List<ExternalId> extIds = new ArrayList<>(2);
       String httpPass = "http-pass";
-      extUser.setPassword(httpPass);
-      db.accountExternalIds().insert(Collections.singleton(extUser));
+      extIds.add(ExternalId.createUsername(username, id, httpPass));
 
       if (email != null) {
-        AccountExternalId extMailto = new AccountExternalId(id, getEmailKey(email));
-        extMailto.setEmailAddress(email);
-        db.accountExternalIds().insert(Collections.singleton(extMailto));
+        extIds.add(ExternalId.createEmail(id, email));
       }
+      externalIdsUpdate.create().insert(db, extIds);
 
       Account a = new Account(id, TimeUtil.nowTs());
       a.setFullName(fullName);
@@ -157,10 +159,6 @@
     return checkNotNull(accounts.get(username), "No TestAccount created for %s", username);
   }
 
-  private AccountExternalId.Key getEmailKey(String email) {
-    return new AccountExternalId.Key(AccountExternalId.SCHEME_MAILTO, email);
-  }
-
   public static KeyPair genSshKey() throws JSchException {
     JSch jsch = new JSch();
     return KeyPair.genKeyPair(jsch, KeyPair.RSA);
diff --git a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/api/accounts/AccountIT.java b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/api/accounts/AccountIT.java
index 82aa576..0adf1a0 100644
--- a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/api/accounts/AccountIT.java
+++ b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/api/accounts/AccountIT.java
@@ -35,6 +35,7 @@
 import com.google.common.collect.FluentIterable;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
 import com.google.common.io.BaseEncoding;
 import com.google.gerrit.acceptance.AbstractDaemonTest;
 import com.google.gerrit.acceptance.AccountCreator;
@@ -61,8 +62,10 @@
 import com.google.gerrit.gpg.server.GpgKeys;
 import com.google.gerrit.gpg.testutil.TestKey;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.client.RefNames;
+import com.google.gerrit.server.account.AccountByEmailCache;
+import com.google.gerrit.server.account.ExternalId;
+import com.google.gerrit.server.account.ExternalIdsUpdate;
 import com.google.gerrit.server.account.WatchConfig;
 import com.google.gerrit.server.account.WatchConfig.NotifyType;
 import com.google.gerrit.server.config.AllUsersName;
@@ -77,10 +80,10 @@
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
-import java.util.Collections;
 import java.util.EnumSet;
 import java.util.Iterator;
 import java.util.List;
+import java.util.Locale;
 import java.util.Map;
 import java.util.Set;
 import org.bouncycastle.bcpg.ArmoredOutputStream;
@@ -111,10 +114,17 @@
 
   @Inject private AllUsersName allUsers;
 
-  private List<AccountExternalId> savedExternalIds;
+  @Inject private AccountByEmailCache byEmailCache;
+
+  @Inject private ExternalIdsUpdate.User externalIdsUpdateFactory;
+
+  private ExternalIdsUpdate externalIdsUpdate;
+  private List<ExternalId> savedExternalIds;
 
   @Before
   public void saveExternalIds() throws Exception {
+    externalIdsUpdate = externalIdsUpdateFactory.create();
+
     savedExternalIds = new ArrayList<>();
     savedExternalIds.addAll(getExternalIds(admin));
     savedExternalIds.addAll(getExternalIds(user));
@@ -126,9 +136,9 @@
       // savedExternalIds is null when we don't run SSH tests and the assume in
       // @Before in AbstractDaemonTest prevents this class' @Before method from
       // being executed.
-      db.accountExternalIds().delete(getExternalIds(admin));
-      db.accountExternalIds().delete(getExternalIds(user));
-      db.accountExternalIds().insert(savedExternalIds);
+      externalIdsUpdate.delete(db, getExternalIds(admin));
+      externalIdsUpdate.delete(db, getExternalIds(user));
+      externalIdsUpdate.insert(db, savedExternalIds);
     }
     accountCache.evict(admin.getId());
     accountCache.evict(user.getId());
@@ -146,7 +156,7 @@
     }
   }
 
-  private Collection<AccountExternalId> getExternalIds(TestAccount account) throws Exception {
+  private Collection<ExternalId> getExternalIds(TestAccount account) throws Exception {
     return accountCache.get(account.getId()).getExternalIds();
   }
 
@@ -440,11 +450,11 @@
     String email = "foo.bar@example.com";
     String extId1 = "foo:bar";
     String extId2 = "foo:baz";
-    db.accountExternalIds()
-        .insert(
-            ImmutableList.of(
-                createExternalIdWithEmail(extId1, email),
-                createExternalIdWithEmail(extId2, email)));
+    List<ExternalId> extIds =
+        ImmutableList.of(
+            ExternalId.createWithEmail(ExternalId.Key.parse(extId1), admin.id, email),
+            ExternalId.createWithEmail(ExternalId.Key.parse(extId2), admin.id, email));
+    externalIdsUpdateFactory.create().insert(db, extIds);
     accountCache.evict(admin.id);
     assertThat(
             gApi.accounts().self().getExternalIds().stream().map(e -> e.identity).collect(toSet()))
@@ -487,6 +497,29 @@
   }
 
   @Test
+  public void lookUpFromCacheByEmail() throws Exception {
+    // exact match with scheme "mailto:"
+    assertEmail(byEmailCache.get(admin.email), admin);
+
+    // exact match with other scheme
+    String email = "foo.bar@example.com";
+    externalIdsUpdateFactory
+        .create()
+        .insert(db, ExternalId.createWithEmail(ExternalId.Key.parse("foo:bar"), admin.id, email));
+    accountCache.evict(admin.id);
+    assertEmail(byEmailCache.get(email), admin);
+
+    // wrong case doesn't match
+    assertThat(byEmailCache.get(admin.email.toUpperCase(Locale.US))).isEmpty();
+
+    // prefix doesn't match
+    assertThat(byEmailCache.get(admin.email.substring(0, admin.email.indexOf('@')))).isEmpty();
+
+    // non-existing doesn't match
+    assertThat(byEmailCache.get("non-existing@example.com")).isEmpty();
+  }
+
+  @Test
   public void putStatus() throws Exception {
     List<String> statuses = ImmutableList.of("OOO", "Busy");
     AccountInfo info;
@@ -680,10 +713,7 @@
   public void addOtherUsersGpgKey_Conflict() throws Exception {
     // Both users have a matching external ID for this key.
     addExternalIdEmail(admin, "test5@example.com");
-    AccountExternalId extId =
-        new AccountExternalId(user.getId(), new AccountExternalId.Key("foo:myId"));
-
-    db.accountExternalIds().insert(Collections.singleton(extId));
+    externalIdsUpdate.insert(db, ExternalId.create("foo", "myId", user.getId()));
     accountCache.evict(user.getId());
 
     TestKey key = validKeyWithSecondUserId();
@@ -883,7 +913,7 @@
     Iterable<String> expectedFps =
         expected.transform(k -> BaseEncoding.base16().encode(k.getPublicKey().getFingerprint()));
     Iterable<String> actualFps =
-        GpgKeys.getGpgExtIds(db, currAccountId).transform(AccountExternalId::getSchemeRest);
+        GpgKeys.getGpgExtIds(db, currAccountId).transform(e -> e.key().id());
     assertThat(actualFps).named("external IDs in database").containsExactlyElementsIn(expectedFps);
 
     // Check raw stored keys.
@@ -908,11 +938,9 @@
 
   private void addExternalIdEmail(TestAccount account, String email) throws Exception {
     checkNotNull(email);
-    AccountExternalId extId =
-        new AccountExternalId(account.getId(), new AccountExternalId.Key(name("test"), email));
-    extId.setEmailAddress(email);
-    db.accountExternalIds().insert(Collections.singleton(extId));
-    // Clear saved AccountState and AccountExternalIds.
+    externalIdsUpdate.insert(
+        db, ExternalId.createWithEmail(name("test"), email, account.getId(), email));
+    // Clear saved AccountState and ExternalIds.
     accountCache.evict(account.getId());
     setApiUser(account);
   }
@@ -932,9 +960,8 @@
     return gApi.accounts().self().getEmails().stream().map(e -> e.email).collect(toSet());
   }
 
-  private AccountExternalId createExternalIdWithEmail(String id, String email) {
-    AccountExternalId extId = new AccountExternalId(admin.id, new AccountExternalId.Key(id));
-    extId.setEmailAddress(email);
-    return extId;
+  private void assertEmail(Set<Account.Id> accounts, TestAccount expectedAccount) {
+    assertThat(accounts).hasSize(1);
+    assertThat(Iterables.getOnlyElement(accounts)).isEqualTo(expectedAccount.getId());
   }
 }
diff --git a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/account/ExternalIdIT.java b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/account/ExternalIdIT.java
index 4272bae..06b8f68 100644
--- a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/account/ExternalIdIT.java
+++ b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/account/ExternalIdIT.java
@@ -15,30 +15,64 @@
 package com.google.gerrit.acceptance.rest.account;
 
 import static com.google.common.truth.Truth.assertThat;
+import static com.google.gerrit.acceptance.GitUtil.fetch;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_USERNAME;
+import static com.google.gerrit.server.group.SystemGroupBackend.REGISTERED_USERS;
+import static org.junit.Assert.fail;
 
+import com.github.rholder.retry.BlockStrategy;
+import com.github.rholder.retry.Retryer;
+import com.github.rholder.retry.RetryerBuilder;
+import com.github.rholder.retry.StopStrategies;
 import com.google.gerrit.acceptance.AbstractDaemonTest;
+import com.google.gerrit.acceptance.PushOneCommit;
 import com.google.gerrit.acceptance.RestResponse;
 import com.google.gerrit.acceptance.Sandboxed;
+import com.google.gerrit.common.data.GlobalCapability;
+import com.google.gerrit.common.data.Permission;
 import com.google.gerrit.extensions.common.AccountExternalIdInfo;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
+import com.google.gerrit.reviewdb.client.RefNames;
+import com.google.gerrit.server.account.ExternalId;
+import com.google.gerrit.server.account.ExternalIds;
+import com.google.gerrit.server.account.ExternalIdsUpdate;
+import com.google.gerrit.server.config.AllUsersName;
+import com.google.gerrit.server.git.LockFailureException;
 import com.google.gson.reflect.TypeToken;
+import com.google.gwtorm.server.OrmException;
+import com.google.inject.Inject;
+import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
+import java.util.concurrent.atomic.AtomicBoolean;
+import java.util.concurrent.atomic.AtomicInteger;
+import org.eclipse.jgit.api.errors.TransportException;
+import org.eclipse.jgit.errors.ConfigInvalidException;
+import org.eclipse.jgit.internal.storage.dfs.InMemoryRepository;
+import org.eclipse.jgit.junit.TestRepository;
 import org.junit.Test;
 
 @Sandboxed
 public class ExternalIdIT extends AbstractDaemonTest {
+  @Inject private AllUsersName allUsers;
+
+  @Inject private ExternalIdsUpdate.Server extIdsUpdate;
+
+  @Inject private ExternalIds externalIds;
+
   @Test
   public void getExternalIDs() throws Exception {
-    Collection<AccountExternalId> expectedIds = accountCache.get(user.getId()).getExternalIds();
+    Collection<ExternalId> expectedIds = accountCache.get(user.getId()).getExternalIds();
 
     List<AccountExternalIdInfo> expectedIdInfos = new ArrayList<>();
-    for (AccountExternalId id : expectedIds) {
-      id.setCanDelete(!id.getExternalId().equals("username:" + user.username));
-      id.setTrusted(true);
-      expectedIdInfos.add(toInfo(id));
+    for (ExternalId id : expectedIds) {
+      AccountExternalIdInfo info = new AccountExternalIdInfo();
+      info.identity = id.key().get();
+      info.emailAddress = id.email();
+      info.canDelete = !id.isScheme(SCHEME_USERNAME) ? true : null;
+      info.trusted = true;
+      expectedIdInfos.add(info);
     }
 
     RestResponse response = userRestSession.get("/accounts/self/external.ids");
@@ -102,12 +136,119 @@
         .isEqualTo(String.format("External id %s does not exist", externalIdStr));
   }
 
-  private static AccountExternalIdInfo toInfo(AccountExternalId id) {
-    AccountExternalIdInfo info = new AccountExternalIdInfo();
-    info.identity = id.getExternalId();
-    info.emailAddress = id.getEmailAddress();
-    info.trusted = id.isTrusted() ? true : null;
-    info.canDelete = id.canDelete() ? true : null;
-    return info;
+  @Test
+  public void fetchExternalIdsBranch() throws Exception {
+    TestRepository<InMemoryRepository> allUsersRepo = cloneProject(allUsers, user);
+
+    // refs/meta/external-ids is only visible to users with the 'Access Database' capability
+    try {
+      fetch(allUsersRepo, RefNames.REFS_EXTERNAL_IDS);
+      fail("expected TransportException");
+    } catch (TransportException e) {
+      assertThat(e.getMessage())
+          .isEqualTo(
+              "Remote does not have " + RefNames.REFS_EXTERNAL_IDS + " available for fetch.");
+    }
+
+    allowGlobalCapabilities(REGISTERED_USERS, GlobalCapability.ACCESS_DATABASE);
+
+    // re-clone to get new request context, otherwise the old global capabilities are still cached
+    // in the IdentifiedUser object
+    allUsersRepo = cloneProject(allUsers, user);
+    fetch(allUsersRepo, RefNames.REFS_EXTERNAL_IDS);
+  }
+
+  @Test
+  public void pushToExternalIdsBranch() throws Exception {
+    grant(Permission.READ, allUsers, RefNames.REFS_EXTERNAL_IDS);
+    grant(Permission.PUSH, allUsers, RefNames.REFS_EXTERNAL_IDS);
+
+    TestRepository<InMemoryRepository> allUsersRepo = cloneProject(allUsers);
+    fetch(allUsersRepo, RefNames.REFS_EXTERNAL_IDS + ":externalIds");
+    allUsersRepo.reset("externalIds");
+    PushOneCommit push = pushFactory.create(db, admin.getIdent(), allUsersRepo);
+    push.to(RefNames.REFS_EXTERNAL_IDS)
+        .assertErrorStatus("not allowed to update " + RefNames.REFS_EXTERNAL_IDS);
+  }
+
+  @Test
+  public void retryOnLockFailure() throws Exception {
+    Retryer<Void> retryer =
+        ExternalIdsUpdate.retryerBuilder()
+            .withBlockStrategy(
+                new BlockStrategy() {
+                  @Override
+                  public void block(long sleepTime) {
+                    // Don't sleep in tests.
+                  }
+                })
+            .build();
+
+    ExternalId.Key fooId = ExternalId.Key.create("foo", "foo");
+    ExternalId.Key barId = ExternalId.Key.create("bar", "bar");
+
+    final AtomicBoolean doneBgUpdate = new AtomicBoolean(false);
+    ExternalIdsUpdate update =
+        new ExternalIdsUpdate(
+            repoManager,
+            allUsers,
+            serverIdent.get(),
+            serverIdent.get(),
+            () -> {
+              if (!doneBgUpdate.getAndSet(true)) {
+                try {
+                  extIdsUpdate.create().insert(db, ExternalId.create(barId, admin.id));
+                } catch (IOException | ConfigInvalidException | OrmException e) {
+                  // Ignore, the successful insertion of the external ID is asserted later
+                }
+              }
+            },
+            retryer);
+    assertThat(doneBgUpdate.get()).isFalse();
+    update.insert(db, ExternalId.create(fooId, admin.id));
+    assertThat(doneBgUpdate.get()).isTrue();
+
+    assertThat(externalIds.get(fooId)).isNotNull();
+    assertThat(externalIds.get(barId)).isNotNull();
+  }
+
+  @Test
+  public void failAfterRetryerGivesUp() throws Exception {
+    ExternalId.Key[] extIdsKeys = {
+      ExternalId.Key.create("foo", "foo"),
+      ExternalId.Key.create("bar", "bar"),
+      ExternalId.Key.create("baz", "baz")
+    };
+    final AtomicInteger bgCounter = new AtomicInteger(0);
+    ExternalIdsUpdate update =
+        new ExternalIdsUpdate(
+            repoManager,
+            allUsers,
+            serverIdent.get(),
+            serverIdent.get(),
+            () -> {
+              try {
+                extIdsUpdate
+                    .create()
+                    .insert(db, ExternalId.create(extIdsKeys[bgCounter.getAndAdd(1)], admin.id));
+              } catch (IOException | ConfigInvalidException | OrmException e) {
+                // Ignore, the successful insertion of the external ID is asserted later
+              }
+            },
+            RetryerBuilder.<Void>newBuilder()
+                .retryIfException(e -> e instanceof LockFailureException)
+                .withStopStrategy(StopStrategies.stopAfterAttempt(extIdsKeys.length))
+                .build());
+    assertThat(bgCounter.get()).isEqualTo(0);
+    try {
+      update.insert(db, ExternalId.create(ExternalId.Key.create("abc", "abc"), admin.id));
+      fail("expected LockFailureException");
+    } catch (LockFailureException e) {
+      // Ignore, expected
+    }
+    assertThat(bgCounter.get()).isEqualTo(extIdsKeys.length);
+    for (ExternalId.Key extIdKey : extIdsKeys) {
+      assertThat(externalIds.get(extIdKey)).isNotNull();
+    }
   }
 }
diff --git a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/config/ServerInfoIT.java b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/config/ServerInfoIT.java
index a4e4437..f51bbf5 100644
--- a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/config/ServerInfoIT.java
+++ b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/config/ServerInfoIT.java
@@ -88,7 +88,6 @@
     assertThat(i.auth.registerText).isNull();
     assertThat(i.auth.editFullNameUrl).isNull();
     assertThat(i.auth.httpPasswordUrl).isNull();
-    assertThat(i.auth.isGitBasicAuth).isNull();
 
     // change
     assertThat(i.change.allowDrafts).isNull();
@@ -163,7 +162,6 @@
     assertThat(i.auth.registerText).isNull();
     assertThat(i.auth.editFullNameUrl).isNull();
     assertThat(i.auth.httpPasswordUrl).isNull();
-    assertThat(i.auth.isGitBasicAuth).isNull();
 
     // change
     assertThat(i.change.allowDrafts).isTrue();
diff --git a/gerrit-extension-api/src/main/java/com/google/gerrit/extensions/common/AuthInfo.java b/gerrit-extension-api/src/main/java/com/google/gerrit/extensions/common/AuthInfo.java
index 9780dd7..79c2250 100644
--- a/gerrit-extension-api/src/main/java/com/google/gerrit/extensions/common/AuthInfo.java
+++ b/gerrit-extension-api/src/main/java/com/google/gerrit/extensions/common/AuthInfo.java
@@ -31,6 +31,5 @@
   public String registerText;
   public String editFullNameUrl;
   public String httpPasswordUrl;
-  public Boolean isGitBasicAuth;
   public GitBasicAuthPolicy gitBasicAuthPolicy;
 }
diff --git a/gerrit-gpg/src/main/java/com/google/gerrit/gpg/GerritPublicKeyChecker.java b/gerrit-gpg/src/main/java/com/google/gerrit/gpg/GerritPublicKeyChecker.java
index b74139a..8e503ee 100644
--- a/gerrit-gpg/src/main/java/com/google/gerrit/gpg/GerritPublicKeyChecker.java
+++ b/gerrit-gpg/src/main/java/com/google/gerrit/gpg/GerritPublicKeyChecker.java
@@ -15,16 +15,16 @@
 package com.google.gerrit.gpg;
 
 import static com.google.gerrit.gpg.PublicKeyStore.keyIdToString;
-import static com.google.gerrit.reviewdb.client.AccountExternalId.SCHEME_GPGKEY;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_GPGKEY;
 
 import com.google.common.base.CharMatcher;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Maps;
 import com.google.common.io.BaseEncoding;
 import com.google.gerrit.common.PageLinks;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.server.IdentifiedUser;
 import com.google.gerrit.server.account.AccountState;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gerrit.server.config.CanonicalWebUrl;
 import com.google.gerrit.server.config.GerritServerConfig;
 import com.google.gerrit.server.query.account.InternalAccountQuery;
@@ -155,8 +155,7 @@
   }
 
   private CheckResult checkIdsForArbitraryUser(PGPPublicKey key) throws PGPException, OrmException {
-    List<AccountState> accountStates =
-        accountQueryProvider.get().byExternalId(toExtIdKey(key).get());
+    List<AccountState> accountStates = accountQueryProvider.get().byExternalId(toExtIdKey(key));
     if (accountStates.isEmpty()) {
       return CheckResult.bad("Key is not associated with any users");
     }
@@ -202,11 +201,11 @@
   private Set<String> getAllowedUserIds(IdentifiedUser user) {
     Set<String> result = new HashSet<>();
     result.addAll(user.getEmailAddresses());
-    for (AccountExternalId extId : user.state().getExternalIds()) {
+    for (ExternalId extId : user.state().getExternalIds()) {
       if (extId.isScheme(SCHEME_GPGKEY)) {
         continue; // Omit GPG keys.
       }
-      result.add(extId.getExternalId());
+      result.add(extId.key().get());
     }
     return result;
   }
@@ -248,8 +247,7 @@
     return sb.toString();
   }
 
-  static AccountExternalId.Key toExtIdKey(PGPPublicKey key) {
-    return new AccountExternalId.Key(
-        SCHEME_GPGKEY, BaseEncoding.base16().encode(key.getFingerprint()));
+  static ExternalId.Key toExtIdKey(PGPPublicKey key) {
+    return ExternalId.Key.create(SCHEME_GPGKEY, BaseEncoding.base16().encode(key.getFingerprint()));
   }
 }
diff --git a/gerrit-gpg/src/main/java/com/google/gerrit/gpg/api/GpgApiAdapterImpl.java b/gerrit-gpg/src/main/java/com/google/gerrit/gpg/api/GpgApiAdapterImpl.java
index 5c1fad5..ba79a6f 100644
--- a/gerrit-gpg/src/main/java/com/google/gerrit/gpg/api/GpgApiAdapterImpl.java
+++ b/gerrit-gpg/src/main/java/com/google/gerrit/gpg/api/GpgApiAdapterImpl.java
@@ -33,6 +33,7 @@
 import java.util.List;
 import java.util.Map;
 import org.bouncycastle.openpgp.PGPException;
+import org.eclipse.jgit.errors.ConfigInvalidException;
 import org.eclipse.jgit.transport.PushCertificate;
 import org.eclipse.jgit.transport.PushCertificateParser;
 
@@ -78,7 +79,7 @@
     in.delete = delete;
     try {
       return postGpgKeys.apply(account, in);
-    } catch (PGPException | OrmException | IOException e) {
+    } catch (PGPException | OrmException | IOException | ConfigInvalidException e) {
       throw new GpgException(e);
     }
   }
diff --git a/gerrit-gpg/src/main/java/com/google/gerrit/gpg/api/GpgKeyApiImpl.java b/gerrit-gpg/src/main/java/com/google/gerrit/gpg/api/GpgKeyApiImpl.java
index e99f900..9aa18fe 100644
--- a/gerrit-gpg/src/main/java/com/google/gerrit/gpg/api/GpgKeyApiImpl.java
+++ b/gerrit-gpg/src/main/java/com/google/gerrit/gpg/api/GpgKeyApiImpl.java
@@ -25,6 +25,7 @@
 import com.google.inject.assistedinject.AssistedInject;
 import java.io.IOException;
 import org.bouncycastle.openpgp.PGPException;
+import org.eclipse.jgit.errors.ConfigInvalidException;
 
 public class GpgKeyApiImpl implements GpgKeyApi {
   public interface Factory {
@@ -55,7 +56,7 @@
   public void delete() throws RestApiException {
     try {
       delete.apply(rsrc, new DeleteGpgKey.Input());
-    } catch (PGPException | OrmException | IOException e) {
+    } catch (PGPException | OrmException | IOException | ConfigInvalidException e) {
       throw new RestApiException("Cannot delete GPG key", e);
     }
   }
diff --git a/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/DeleteGpgKey.java b/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/DeleteGpgKey.java
index 1b797eb..50bf57b 100644
--- a/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/DeleteGpgKey.java
+++ b/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/DeleteGpgKey.java
@@ -15,6 +15,7 @@
 package com.google.gerrit.gpg.server;
 
 import static com.google.gerrit.gpg.PublicKeyStore.keyIdToString;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_GPGKEY;
 
 import com.google.common.io.BaseEncoding;
 import com.google.gerrit.extensions.restapi.ResourceConflictException;
@@ -22,17 +23,18 @@
 import com.google.gerrit.extensions.restapi.RestModifyView;
 import com.google.gerrit.gpg.PublicKeyStore;
 import com.google.gerrit.gpg.server.DeleteGpgKey.Input;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.GerritPersonIdent;
 import com.google.gerrit.server.account.AccountCache;
+import com.google.gerrit.server.account.ExternalId;
+import com.google.gerrit.server.account.ExternalIdsUpdate;
 import com.google.gwtorm.server.OrmException;
 import com.google.inject.Inject;
 import com.google.inject.Provider;
 import java.io.IOException;
-import java.util.Collections;
 import org.bouncycastle.openpgp.PGPException;
 import org.bouncycastle.openpgp.PGPPublicKey;
+import org.eclipse.jgit.errors.ConfigInvalidException;
 import org.eclipse.jgit.lib.CommitBuilder;
 import org.eclipse.jgit.lib.PersonIdent;
 import org.eclipse.jgit.lib.RefUpdate;
@@ -44,27 +46,34 @@
   private final Provider<ReviewDb> db;
   private final Provider<PublicKeyStore> storeProvider;
   private final AccountCache accountCache;
+  private final ExternalIdsUpdate.User externalIdsUpdateFactory;
 
   @Inject
   DeleteGpgKey(
       @GerritPersonIdent Provider<PersonIdent> serverIdent,
       Provider<ReviewDb> db,
       Provider<PublicKeyStore> storeProvider,
-      AccountCache accountCache) {
+      AccountCache accountCache,
+      ExternalIdsUpdate.User externalIdsUpdateFactory) {
     this.serverIdent = serverIdent;
     this.db = db;
     this.storeProvider = storeProvider;
     this.accountCache = accountCache;
+    this.externalIdsUpdateFactory = externalIdsUpdateFactory;
   }
 
   @Override
   public Response<?> apply(GpgKey rsrc, Input input)
-      throws ResourceConflictException, PGPException, OrmException, IOException {
+      throws ResourceConflictException, PGPException, OrmException, IOException,
+          ConfigInvalidException {
     PGPPublicKey key = rsrc.getKeyRing().getPublicKey();
-    AccountExternalId.Key extIdKey =
-        new AccountExternalId.Key(
-            AccountExternalId.SCHEME_GPGKEY, BaseEncoding.base16().encode(key.getFingerprint()));
-    db.get().accountExternalIds().deleteKeys(Collections.singleton(extIdKey));
+    externalIdsUpdateFactory
+        .create()
+        .delete(
+            db.get(),
+            rsrc.getUser().getAccountId(),
+            ExternalId.Key.create(
+                SCHEME_GPGKEY, BaseEncoding.base16().encode(key.getFingerprint())));
     accountCache.evict(rsrc.getUser().getAccountId());
 
     try (PublicKeyStore store = storeProvider.get()) {
diff --git a/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/GpgKeys.java b/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/GpgKeys.java
index 864709c..819ad96 100644
--- a/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/GpgKeys.java
+++ b/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/GpgKeys.java
@@ -14,7 +14,7 @@
 
 package com.google.gerrit.gpg.server;
 
-import static com.google.gerrit.reviewdb.client.AccountExternalId.SCHEME_GPGKEY;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_GPGKEY;
 import static java.nio.charset.StandardCharsets.UTF_8;
 
 import com.google.common.annotations.VisibleForTesting;
@@ -37,10 +37,10 @@
 import com.google.gerrit.gpg.PublicKeyChecker;
 import com.google.gerrit.gpg.PublicKeyStore;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.CurrentUser;
 import com.google.gerrit.server.account.AccountResource;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gwtorm.server.OrmException;
 import com.google.inject.Inject;
 import com.google.inject.Provider;
@@ -114,7 +114,7 @@
     throw new ResourceNotFoundException(id);
   }
 
-  static byte[] parseFingerprint(String str, Iterable<AccountExternalId> existingExtIds)
+  static byte[] parseFingerprint(String str, Iterable<ExternalId> existingExtIds)
       throws ResourceNotFoundException {
     str = CharMatcher.whitespace().removeFrom(str).toUpperCase();
     if ((str.length() != 8 && str.length() != 40)
@@ -122,8 +122,8 @@
       throw new ResourceNotFoundException(str);
     }
     byte[] fp = null;
-    for (AccountExternalId extId : existingExtIds) {
-      String fpStr = extId.getSchemeRest();
+    for (ExternalId extId : existingExtIds) {
+      String fpStr = extId.key().id();
       if (!fpStr.endsWith(str)) {
         continue;
       } else if (fp != null) {
@@ -152,8 +152,8 @@
       checkVisible(self, rsrc);
       Map<String, GpgKeyInfo> keys = new HashMap<>();
       try (PublicKeyStore store = storeProvider.get()) {
-        for (AccountExternalId extId : getGpgExtIds(rsrc)) {
-          String fpStr = extId.getSchemeRest();
+        for (ExternalId extId : getGpgExtIds(rsrc)) {
+          String fpStr = extId.key().id();
           byte[] fp = BaseEncoding.base16().decode(fpStr);
           boolean found = false;
           for (PGPPublicKeyRing keyRing : store.get(keyId(fp))) {
@@ -199,13 +199,14 @@
   }
 
   @VisibleForTesting
-  public static FluentIterable<AccountExternalId> getGpgExtIds(ReviewDb db, Account.Id accountId)
+  public static FluentIterable<ExternalId> getGpgExtIds(ReviewDb db, Account.Id accountId)
       throws OrmException {
-    return FluentIterable.from(db.accountExternalIds().byAccount(accountId))
+    return FluentIterable.from(
+            ExternalId.from(db.accountExternalIds().byAccount(accountId).toList()))
         .filter(in -> in.isScheme(SCHEME_GPGKEY));
   }
 
-  private Iterable<AccountExternalId> getGpgExtIds(AccountResource rsrc) throws OrmException {
+  private Iterable<ExternalId> getGpgExtIds(AccountResource rsrc) throws OrmException {
     return getGpgExtIds(db.get(), rsrc.getUser().getAccountId());
   }
 
diff --git a/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/PostGpgKeys.java b/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/PostGpgKeys.java
index 1c6fc3a..7b825b1 100644
--- a/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/PostGpgKeys.java
+++ b/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/PostGpgKeys.java
@@ -16,12 +16,13 @@
 
 import static com.google.gerrit.gpg.PublicKeyStore.keyIdToString;
 import static com.google.gerrit.gpg.PublicKeyStore.keyToString;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_GPGKEY;
 import static java.nio.charset.StandardCharsets.UTF_8;
+import static java.util.stream.Collectors.toList;
 
 import com.google.common.base.Joiner;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
@@ -39,7 +40,6 @@
 import com.google.gerrit.gpg.PublicKeyStore;
 import com.google.gerrit.gpg.server.PostGpgKeys.Input;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.CurrentUser;
 import com.google.gerrit.server.GerritPersonIdent;
@@ -47,6 +47,8 @@
 import com.google.gerrit.server.account.AccountCache;
 import com.google.gerrit.server.account.AccountResource;
 import com.google.gerrit.server.account.AccountState;
+import com.google.gerrit.server.account.ExternalId;
+import com.google.gerrit.server.account.ExternalIdsUpdate;
 import com.google.gerrit.server.mail.send.AddKeySender;
 import com.google.gerrit.server.query.account.InternalAccountQuery;
 import com.google.gwtorm.server.OrmException;
@@ -66,6 +68,7 @@
 import org.bouncycastle.openpgp.PGPPublicKey;
 import org.bouncycastle.openpgp.PGPPublicKeyRing;
 import org.bouncycastle.openpgp.bc.BcPGPObjectFactory;
+import org.eclipse.jgit.errors.ConfigInvalidException;
 import org.eclipse.jgit.lib.CommitBuilder;
 import org.eclipse.jgit.lib.PersonIdent;
 import org.eclipse.jgit.lib.RefUpdate;
@@ -88,6 +91,7 @@
   private final AddKeySender.Factory addKeyFactory;
   private final AccountCache accountCache;
   private final Provider<InternalAccountQuery> accountQueryProvider;
+  private final ExternalIdsUpdate.User externalIdsUpdateFactory;
 
   @Inject
   PostGpgKeys(
@@ -98,7 +102,8 @@
       GerritPublicKeyChecker.Factory checkerFactory,
       AddKeySender.Factory addKeyFactory,
       AccountCache accountCache,
-      Provider<InternalAccountQuery> accountQueryProvider) {
+      Provider<InternalAccountQuery> accountQueryProvider,
+      ExternalIdsUpdate.User externalIdsUpdateFactory) {
     this.serverIdent = serverIdent;
     this.db = db;
     this.self = self;
@@ -107,48 +112,48 @@
     this.addKeyFactory = addKeyFactory;
     this.accountCache = accountCache;
     this.accountQueryProvider = accountQueryProvider;
+    this.externalIdsUpdateFactory = externalIdsUpdateFactory;
   }
 
   @Override
   public Map<String, GpgKeyInfo> apply(AccountResource rsrc, Input input)
       throws ResourceNotFoundException, BadRequestException, ResourceConflictException,
-          PGPException, OrmException, IOException {
+          PGPException, OrmException, IOException, ConfigInvalidException {
     GpgKeys.checkVisible(self, rsrc);
 
-    List<AccountExternalId> existingExtIds =
+    Collection<ExternalId> existingExtIds =
         GpgKeys.getGpgExtIds(db.get(), rsrc.getUser().getAccountId()).toList();
-
     try (PublicKeyStore store = storeProvider.get()) {
       Set<Fingerprint> toRemove = readKeysToRemove(input, existingExtIds);
       List<PGPPublicKeyRing> newKeys = readKeysToAdd(input, toRemove);
-      List<AccountExternalId> newExtIds = new ArrayList<>(existingExtIds.size());
+      List<ExternalId> newExtIds = new ArrayList<>(existingExtIds.size());
 
       for (PGPPublicKeyRing keyRing : newKeys) {
         PGPPublicKey key = keyRing.getPublicKey();
-        AccountExternalId.Key extIdKey = toExtIdKey(key.getFingerprint());
-        Account account = getAccountByExternalId(extIdKey.get());
+        ExternalId.Key extIdKey = toExtIdKey(key.getFingerprint());
+        Account account = getAccountByExternalId(extIdKey);
         if (account != null) {
           if (!account.getId().equals(rsrc.getUser().getAccountId())) {
             throw new ResourceConflictException("GPG key already associated with another account");
           }
         } else {
-          newExtIds.add(new AccountExternalId(rsrc.getUser().getAccountId(), extIdKey));
+          newExtIds.add(ExternalId.create(extIdKey, rsrc.getUser().getAccountId()));
         }
       }
 
       storeKeys(rsrc, newKeys, toRemove);
-      if (!newExtIds.isEmpty()) {
-        db.get().accountExternalIds().insert(newExtIds);
-      }
-      db.get()
-          .accountExternalIds()
-          .deleteKeys(Iterables.transform(toRemove, fp -> toExtIdKey(fp.get())));
+
+      List<ExternalId.Key> extIdKeysToRemove =
+          toRemove.stream().map(fp -> toExtIdKey(fp.get())).collect(toList());
+      externalIdsUpdateFactory
+          .create()
+          .replace(db.get(), rsrc.getUser().getAccountId(), extIdKeysToRemove, newExtIds);
       accountCache.evict(rsrc.getUser().getAccountId());
       return toJson(newKeys, toRemove, store, rsrc.getUser());
     }
   }
 
-  private Set<Fingerprint> readKeysToRemove(Input input, List<AccountExternalId> existingExtIds) {
+  private Set<Fingerprint> readKeysToRemove(Input input, Collection<ExternalId> existingExtIds) {
     if (input.delete == null || input.delete.isEmpty()) {
       return ImmutableSet.of();
     }
@@ -243,13 +248,12 @@
     }
   }
 
-  private AccountExternalId.Key toExtIdKey(byte[] fp) {
-    return new AccountExternalId.Key(
-        AccountExternalId.SCHEME_GPGKEY, BaseEncoding.base16().encode(fp));
+  private ExternalId.Key toExtIdKey(byte[] fp) {
+    return ExternalId.Key.create(SCHEME_GPGKEY, BaseEncoding.base16().encode(fp));
   }
 
-  private Account getAccountByExternalId(String externalId) throws OrmException {
-    List<AccountState> accountStates = accountQueryProvider.get().byExternalId(externalId);
+  private Account getAccountByExternalId(ExternalId.Key extIdKey) throws OrmException {
+    List<AccountState> accountStates = accountQueryProvider.get().byExternalId(extIdKey);
 
     if (accountStates.isEmpty()) {
       return null;
@@ -257,7 +261,7 @@
 
     if (accountStates.size() > 1) {
       StringBuilder msg = new StringBuilder();
-      msg.append("GPG key ").append(externalId).append(" associated with multiple accounts: ");
+      msg.append("GPG key ").append(extIdKey.get()).append(" associated with multiple accounts: ");
       Joiner.on(", ")
           .appendTo(msg, Lists.transform(accountStates, AccountState.ACCOUNT_ID_FUNCTION));
       log.error(msg.toString());
diff --git a/gerrit-gpg/src/test/java/com/google/gerrit/gpg/GerritPublicKeyCheckerTest.java b/gerrit-gpg/src/test/java/com/google/gerrit/gpg/GerritPublicKeyCheckerTest.java
index 420dd50..862930f 100644
--- a/gerrit-gpg/src/test/java/com/google/gerrit/gpg/GerritPublicKeyCheckerTest.java
+++ b/gerrit-gpg/src/test/java/com/google/gerrit/gpg/GerritPublicKeyCheckerTest.java
@@ -23,7 +23,6 @@
 import static com.google.gerrit.gpg.testutil.TestTrustKeys.keyC;
 import static com.google.gerrit.gpg.testutil.TestTrustKeys.keyD;
 import static com.google.gerrit.gpg.testutil.TestTrustKeys.keyE;
-import static com.google.gerrit.reviewdb.client.AccountExternalId.SCHEME_MAILTO;
 import static org.eclipse.jgit.lib.RefUpdate.Result.FAST_FORWARD;
 import static org.eclipse.jgit.lib.RefUpdate.Result.FORCED;
 import static org.eclipse.jgit.lib.RefUpdate.Result.NEW;
@@ -34,13 +33,14 @@
 import com.google.gerrit.gpg.testutil.TestKey;
 import com.google.gerrit.lifecycle.LifecycleManager;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.CurrentUser;
 import com.google.gerrit.server.IdentifiedUser;
 import com.google.gerrit.server.account.AccountCache;
 import com.google.gerrit.server.account.AccountManager;
 import com.google.gerrit.server.account.AuthRequest;
+import com.google.gerrit.server.account.ExternalId;
+import com.google.gerrit.server.account.ExternalIdsUpdate;
 import com.google.gerrit.server.schema.SchemaCreator;
 import com.google.gerrit.server.util.RequestContext;
 import com.google.gerrit.server.util.ThreadLocalRequestContext;
@@ -55,7 +55,6 @@
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Arrays;
-import java.util.Collections;
 import java.util.List;
 import org.bouncycastle.openpgp.PGPPublicKey;
 import org.bouncycastle.openpgp.PGPPublicKeyRing;
@@ -86,6 +85,8 @@
 
   @Inject private ThreadLocalRequestContext requestContext;
 
+  @Inject private ExternalIdsUpdate.Server externalIdsUpdateFactory;
+
   private LifecycleManager lifecycle;
   private ReviewDb db;
   private Account.Id userId;
@@ -221,7 +222,8 @@
 
   @Test
   public void noExternalIds() throws Exception {
-    db.accountExternalIds().delete(db.accountExternalIds().byAccount(user.getAccountId()));
+    ExternalIdsUpdate externalIdsUpdate = externalIdsUpdateFactory.create();
+    externalIdsUpdate.deleteAll(db, user.getAccountId());
     reloadUser();
 
     TestKey key = validKeyWithSecondUserId();
@@ -234,11 +236,8 @@
     checker = checkerFactory.create().setStore(store).disableTrust();
     assertProblems(
         checker.check(key.getPublicKey()), Status.BAD, "Key is not associated with any users");
-
-    db.accountExternalIds()
-        .insert(
-            Collections.singleton(
-                new AccountExternalId(user.getAccountId(), toExtIdKey(key.getPublicKey()))));
+    externalIdsUpdate.insert(
+        db, ExternalId.create(toExtIdKey(key.getPublicKey()), user.getAccountId()));
     reloadUser();
     assertProblems(checker.check(key.getPublicKey()), Status.BAD, "No identities found for user");
   }
@@ -389,18 +388,15 @@
 
   private void add(PGPPublicKeyRing kr, IdentifiedUser user) throws Exception {
     Account.Id id = user.getAccountId();
-    List<AccountExternalId> newExtIds = new ArrayList<>(2);
-    newExtIds.add(new AccountExternalId(id, toExtIdKey(kr.getPublicKey())));
+    List<ExternalId> newExtIds = new ArrayList<>(2);
+    newExtIds.add(ExternalId.create(toExtIdKey(kr.getPublicKey()), id));
 
     @SuppressWarnings("unchecked")
     String userId = (String) Iterators.getOnlyElement(kr.getPublicKey().getUserIDs(), null);
     if (userId != null) {
       String email = PushCertificateIdent.parse(userId).getEmailAddress();
       assertThat(email).contains("@");
-      AccountExternalId mailto =
-          new AccountExternalId(id, new AccountExternalId.Key(SCHEME_MAILTO, email));
-      mailto.setEmailAddress(email);
-      newExtIds.add(mailto);
+      newExtIds.add(ExternalId.createEmail(id, email));
     }
 
     store.add(kr);
@@ -410,7 +406,7 @@
     cb.setCommitter(ident);
     assertThat(store.save(cb)).isAnyOf(NEW, FAST_FORWARD, FORCED);
 
-    db.accountExternalIds().insert(newExtIds);
+    externalIdsUpdateFactory.create().insert(db, newExtIds);
     accountCache.evict(user.getAccountId());
   }
 
@@ -434,12 +430,9 @@
   }
 
   private void addExternalId(String scheme, String id, String email) throws Exception {
-    AccountExternalId extId =
-        new AccountExternalId(user.getAccountId(), new AccountExternalId.Key(scheme, id));
-    if (email != null) {
-      extId.setEmailAddress(email);
-    }
-    db.accountExternalIds().insert(Collections.singleton(extId));
+    externalIdsUpdateFactory
+        .create()
+        .insert(db, ExternalId.createWithEmail(scheme, id, user.getAccountId(), email));
     reloadUser();
   }
 }
diff --git a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/CacheBasedWebSession.java b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/CacheBasedWebSession.java
index 9a8197a..9676cd3 100644
--- a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/CacheBasedWebSession.java
+++ b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/CacheBasedWebSession.java
@@ -22,12 +22,12 @@
 import com.google.gerrit.httpd.WebSessionManager.Key;
 import com.google.gerrit.httpd.WebSessionManager.Val;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.server.AccessPath;
 import com.google.gerrit.server.AnonymousUser;
 import com.google.gerrit.server.CurrentUser;
 import com.google.gerrit.server.IdentifiedUser;
 import com.google.gerrit.server.account.AuthResult;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gerrit.server.config.AuthConfig;
 import com.google.inject.Provider;
 import com.google.inject.servlet.RequestScoped;
@@ -132,7 +132,7 @@
   }
 
   @Override
-  public AccountExternalId.Key getLastLoginExternalId() {
+  public ExternalId.Key getLastLoginExternalId() {
     return val != null ? val.getExternalId() : null;
   }
 
@@ -149,9 +149,9 @@
   }
 
   @Override
-  public void login(final AuthResult res, final boolean rememberMe) {
-    final Account.Id id = res.getAccountId();
-    final AccountExternalId.Key identity = res.getExternalId();
+  public void login(AuthResult res, boolean rememberMe) {
+    Account.Id id = res.getAccountId();
+    ExternalId.Key identity = res.getExternalId();
 
     if (val != null) {
       manager.destroy(key);
diff --git a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/GitOverHttpModule.java b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/GitOverHttpModule.java
index 4f97783..3be9a12 100644
--- a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/GitOverHttpModule.java
+++ b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/GitOverHttpModule.java
@@ -42,14 +42,10 @@
     Class<? extends Filter> authFilter;
     if (authConfig.isTrustContainerAuth()) {
       authFilter = ContainerAuthFilter.class;
-    } else if (authConfig.isGitBasicAuth()) {
-      if (authConfig.getAuthType() == OAUTH) {
-        authFilter = ProjectOAuthFilter.class;
-      } else {
-        authFilter = ProjectBasicAuthFilter.class;
-      }
+    } else if (authConfig.getAuthType() == OAUTH) {
+      authFilter = ProjectOAuthFilter.class;
     } else {
-      authFilter = ProjectDigestFilter.class;
+      authFilter = ProjectBasicAuthFilter.class;
     }
 
     if (isHttpEnabled()) {
diff --git a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/ProjectBasicAuthFilter.java b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/ProjectBasicAuthFilter.java
index 88f9b4c..57ec9c5 100644
--- a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/ProjectBasicAuthFilter.java
+++ b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/ProjectBasicAuthFilter.java
@@ -140,7 +140,7 @@
     GitBasicAuthPolicy gitBasicAuthPolicy = authConfig.getGitBasicAuthPolicy();
     if (gitBasicAuthPolicy == GitBasicAuthPolicy.HTTP
         || gitBasicAuthPolicy == GitBasicAuthPolicy.HTTP_LDAP) {
-      if (passwordMatchesTheUserGeneratedOne(who, username, password)) {
+      if (who.checkPassword(password, username)) {
         return succeedAuthentication(who);
       }
     }
@@ -157,7 +157,7 @@
       setUserIdentified(whoAuthResult.getAccountId());
       return true;
     } catch (NoSuchUserException e) {
-      if (password.equals(who.getPassword(who.getUserName()))) {
+      if (who.checkPassword(password, who.getUserName())) {
         return succeedAuthentication(who);
       }
       log.warn("Authentication failed for " + username, e);
@@ -193,12 +193,6 @@
     ws.setAccessPathOk(AccessPath.REST_API, true);
   }
 
-  private boolean passwordMatchesTheUserGeneratedOne(
-      AccountState who, String username, String password) {
-    String accountPassword = who.getPassword(username);
-    return accountPassword != null && password != null && accountPassword.equals(password);
-  }
-
   private String encoding(HttpServletRequest req) {
     return MoreObjects.firstNonNull(req.getCharacterEncoding(), UTF_8.name());
   }
diff --git a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/ProjectDigestFilter.java b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/ProjectDigestFilter.java
deleted file mode 100644
index 7da8cda..0000000
--- a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/ProjectDigestFilter.java
+++ /dev/null
@@ -1,337 +0,0 @@
-// Copyright (C) 2010 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-package com.google.gerrit.httpd;
-
-import static java.nio.charset.StandardCharsets.UTF_8;
-import static java.util.concurrent.TimeUnit.HOURS;
-import static java.util.concurrent.TimeUnit.SECONDS;
-import static javax.servlet.http.HttpServletResponse.SC_FORBIDDEN;
-import static javax.servlet.http.HttpServletResponse.SC_INTERNAL_SERVER_ERROR;
-import static javax.servlet.http.HttpServletResponse.SC_UNAUTHORIZED;
-
-import com.google.gerrit.common.Nullable;
-import com.google.gerrit.extensions.registration.DynamicItem;
-import com.google.gerrit.server.AccessPath;
-import com.google.gerrit.server.account.AccountCache;
-import com.google.gerrit.server.account.AccountState;
-import com.google.gerrit.server.config.CanonicalWebUrl;
-import com.google.gerrit.server.config.GerritServerConfig;
-import com.google.gwtjsonrpc.server.SignedToken;
-import com.google.gwtjsonrpc.server.XsrfException;
-import com.google.inject.Inject;
-import com.google.inject.Provider;
-import com.google.inject.Singleton;
-import java.io.IOException;
-import java.security.MessageDigest;
-import java.security.NoSuchAlgorithmException;
-import java.util.Collections;
-import java.util.HashMap;
-import java.util.Locale;
-import java.util.Map;
-import javax.servlet.Filter;
-import javax.servlet.FilterChain;
-import javax.servlet.FilterConfig;
-import javax.servlet.ServletContext;
-import javax.servlet.ServletException;
-import javax.servlet.ServletRequest;
-import javax.servlet.ServletResponse;
-import javax.servlet.http.HttpServletRequest;
-import javax.servlet.http.HttpServletResponse;
-import javax.servlet.http.HttpServletResponseWrapper;
-import org.eclipse.jgit.lib.Config;
-
-/**
- * Authenticates the current user by HTTP digest authentication.
- *
- * <p>The current HTTP request is authenticated by looking up the username from the Authorization
- * header and checking the digest response against the stored password. This filter is intended only
- * to protect the {@link GitOverHttpServlet} and its handled URLs, which provide remote repository
- * access over HTTP.
- *
- * @see <a href="http://www.ietf.org/rfc/rfc2617.txt">RFC 2617</a>
- */
-@Singleton
-class ProjectDigestFilter implements Filter {
-  public static final String REALM_NAME = "Gerrit Code Review";
-  private static final String AUTHORIZATION = "Authorization";
-
-  private final Provider<String> urlProvider;
-  private final DynamicItem<WebSession> session;
-  private final AccountCache accountCache;
-  private final Config config;
-  private final SignedToken tokens;
-  private ServletContext context;
-
-  @Inject
-  ProjectDigestFilter(
-      @CanonicalWebUrl @Nullable Provider<String> urlProvider,
-      DynamicItem<WebSession> session,
-      AccountCache accountCache,
-      @GerritServerConfig Config config)
-      throws XsrfException {
-    this.urlProvider = urlProvider;
-    this.session = session;
-    this.accountCache = accountCache;
-    this.config = config;
-    this.tokens = new SignedToken((int) SECONDS.convert(1, HOURS));
-  }
-
-  @Override
-  public void init(FilterConfig config) {
-    context = config.getServletContext();
-  }
-
-  @Override
-  public void destroy() {}
-
-  @Override
-  public void doFilter(ServletRequest request, ServletResponse response, FilterChain chain)
-      throws IOException, ServletException {
-    HttpServletRequest req = (HttpServletRequest) request;
-    Response rsp = new Response(req, (HttpServletResponse) response);
-
-    if (verify(req, rsp)) {
-      chain.doFilter(req, rsp);
-    }
-  }
-
-  private boolean verify(HttpServletRequest req, Response rsp) throws IOException {
-    final String hdr = req.getHeader(AUTHORIZATION);
-    if (hdr == null || !hdr.startsWith("Digest ")) {
-      // Allow an anonymous connection through, or it might be using a
-      // session cookie instead of digest authentication.
-      return true;
-    }
-
-    final Map<String, String> p = parseAuthorization(hdr);
-    final String user = p.get("username");
-    final String realm = p.get("realm");
-    final String nonce = p.get("nonce");
-    final String uri = p.get("uri");
-    final String response = p.get("response");
-    final String qop = p.get("qop");
-    final String nc = p.get("nc");
-    final String cnonce = p.get("cnonce");
-    final String method = req.getMethod();
-
-    if (user == null //
-        || realm == null //
-        || nonce == null //
-        || uri == null //
-        || response == null //
-        || !"auth".equals(qop) //
-        || !REALM_NAME.equals(realm)) {
-      context.log("Invalid header: " + AUTHORIZATION + ": " + hdr);
-      rsp.sendError(SC_FORBIDDEN);
-      return false;
-    }
-
-    String username = user;
-    if (config.getBoolean("auth", "userNameToLowerCase", false)) {
-      username = username.toLowerCase(Locale.US);
-    }
-
-    final AccountState who = accountCache.getByUsername(username);
-    if (who == null || !who.getAccount().isActive()) {
-      rsp.sendError(SC_UNAUTHORIZED);
-      return false;
-    }
-
-    final String passwd = who.getPassword(username);
-    if (passwd == null) {
-      rsp.sendError(SC_UNAUTHORIZED);
-      return false;
-    }
-
-    final String A1 = user + ":" + realm + ":" + passwd;
-    final String A2 = method + ":" + uri;
-    final String expect = KD(H(A1), nonce + ":" + nc + ":" + cnonce + ":" + qop + ":" + H(A2));
-
-    if (expect.equals(response)) {
-      try {
-        if (tokens.checkToken(nonce, "") != null) {
-          WebSession ws = session.get();
-          ws.setUserAccountId(who.getAccount().getId());
-          ws.setAccessPathOk(AccessPath.GIT, true);
-          ws.setAccessPathOk(AccessPath.REST_API, true);
-          return true;
-        }
-        rsp.stale = true;
-        rsp.sendError(SC_UNAUTHORIZED);
-        return false;
-      } catch (XsrfException e) {
-        context.log("Error validating nonce for digest authentication", e);
-        rsp.sendError(SC_INTERNAL_SERVER_ERROR);
-        return false;
-      }
-    }
-    rsp.sendError(SC_UNAUTHORIZED);
-    return false;
-  }
-
-  private static String H(String data) {
-    MessageDigest md = newMD5();
-    md.update(data.getBytes(UTF_8));
-    return LHEX(md.digest());
-  }
-
-  private static String KD(String secret, String data) {
-    MessageDigest md = newMD5();
-    md.update(secret.getBytes(UTF_8));
-    md.update((byte) ':');
-    md.update(data.getBytes(UTF_8));
-    return LHEX(md.digest());
-  }
-
-  private static MessageDigest newMD5() {
-    try {
-      return MessageDigest.getInstance("MD5");
-    } catch (NoSuchAlgorithmException e) {
-      throw new RuntimeException("No MD5 available", e);
-    }
-  }
-
-  private static final char[] LHEX = {
-    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', //
-    'a', 'b', 'c', 'd', 'e', 'f',
-  };
-
-  private static String LHEX(byte[] bin) {
-    StringBuilder r = new StringBuilder(bin.length * 2);
-    for (byte b : bin) {
-      r.append(LHEX[(b >>> 4) & 0x0f]);
-      r.append(LHEX[b & 0x0f]);
-    }
-    return r.toString();
-  }
-
-  private Map<String, String> parseAuthorization(String auth) {
-    Map<String, String> p = new HashMap<>();
-    int next = "Digest ".length();
-    while (next < auth.length()) {
-      if (next < auth.length() && auth.charAt(next) == ',') {
-        next++;
-      }
-      while (next < auth.length() && Character.isWhitespace(auth.charAt(next))) {
-        next++;
-      }
-
-      int eq = auth.indexOf('=', next);
-      if (eq < 0 || eq + 1 == auth.length()) {
-        return Collections.emptyMap();
-      }
-
-      final String name = auth.substring(next, eq);
-      final String value;
-      if (auth.charAt(eq + 1) == '"') {
-        int dq = auth.indexOf('"', eq + 2);
-        if (dq < 0) {
-          return Collections.emptyMap();
-        }
-        value = auth.substring(eq + 2, dq);
-        next = dq + 1;
-
-      } else {
-        int space = auth.indexOf(' ', eq + 1);
-        int comma = auth.indexOf(',', eq + 1);
-        if (space < 0) {
-          space = auth.length();
-        }
-        if (comma < 0) {
-          comma = auth.length();
-        }
-
-        final int e = Math.min(space, comma);
-        value = auth.substring(eq + 1, e);
-        next = e + 1;
-      }
-      p.put(name, value);
-    }
-    return p;
-  }
-
-  private String newNonce() {
-    try {
-      return tokens.newToken("");
-    } catch (XsrfException e) {
-      throw new RuntimeException("Cannot generate new nonce", e);
-    }
-  }
-
-  class Response extends HttpServletResponseWrapper {
-    private static final String WWW_AUTHENTICATE = "WWW-Authenticate";
-    private final HttpServletRequest req;
-    Boolean stale;
-
-    Response(HttpServletRequest req, HttpServletResponse rsp) {
-      super(rsp);
-      this.req = req;
-    }
-
-    private void status(int sc) {
-      if (sc == SC_UNAUTHORIZED) {
-        StringBuilder v = new StringBuilder();
-        v.append("Digest");
-        v.append(" realm=\"").append(REALM_NAME).append("\"");
-
-        String url = urlProvider.get();
-        if (url == null) {
-          url = req.getContextPath();
-          if (url != null && !url.isEmpty() && !url.endsWith("/")) {
-            url += "/";
-          }
-        }
-        if (url != null && !url.isEmpty()) {
-          v.append(", domain=\"").append(url).append("\"");
-        }
-
-        v.append(", qop=\"auth\"");
-        if (stale != null) {
-          v.append(", stale=").append(stale);
-        }
-        v.append(", nonce=\"").append(newNonce()).append("\"");
-        setHeader(WWW_AUTHENTICATE, v.toString());
-
-      } else if (containsHeader(WWW_AUTHENTICATE)) {
-        setHeader(WWW_AUTHENTICATE, null);
-      }
-    }
-
-    @Override
-    public void sendError(int sc, String msg) throws IOException {
-      status(sc);
-      super.sendError(sc, msg);
-    }
-
-    @Override
-    public void sendError(int sc) throws IOException {
-      status(sc);
-      super.sendError(sc);
-    }
-
-    @Override
-    @Deprecated
-    public void setStatus(int sc, String sm) {
-      status(sc);
-      super.setStatus(sc, sm);
-    }
-
-    @Override
-    public void setStatus(int sc) {
-      status(sc);
-      super.setStatus(sc);
-    }
-  }
-}
diff --git a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/WebSession.java b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/WebSession.java
index 948af29..f1600bc 100644
--- a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/WebSession.java
+++ b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/WebSession.java
@@ -16,10 +16,10 @@
 
 import com.google.gerrit.common.Nullable;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.server.AccessPath;
 import com.google.gerrit.server.CurrentUser;
 import com.google.gerrit.server.account.AuthResult;
+import com.google.gerrit.server.account.ExternalId;
 
 public interface WebSession {
   boolean isSignedIn();
@@ -29,7 +29,7 @@
 
   boolean isValidXGerritAuth(String keyIn);
 
-  AccountExternalId.Key getLastLoginExternalId();
+  ExternalId.Key getLastLoginExternalId();
 
   CurrentUser getUser();
 
diff --git a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/WebSessionManager.java b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/WebSessionManager.java
index 28d12ee..59591cc 100644
--- a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/WebSessionManager.java
+++ b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/WebSessionManager.java
@@ -30,7 +30,7 @@
 
 import com.google.common.cache.Cache;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gerrit.server.config.ConfigUtil;
 import com.google.gerrit.server.config.GerritServerConfig;
 import com.google.inject.Inject;
@@ -98,18 +98,18 @@
     }
   }
 
-  Val createVal(final Key key, final Val val) {
-    final Account.Id who = val.getAccountId();
-    final boolean remember = val.isPersistentCookie();
-    final AccountExternalId.Key lastLogin = val.getExternalId();
+  Val createVal(Key key, Val val) {
+    Account.Id who = val.getAccountId();
+    boolean remember = val.isPersistentCookie();
+    ExternalId.Key lastLogin = val.getExternalId();
     return createVal(key, who, remember, lastLogin, val.sessionId, val.auth);
   }
 
   Val createVal(
-      final Key key,
-      final Account.Id who,
-      final boolean remember,
-      final AccountExternalId.Key lastLogin,
+      Key key,
+      Account.Id who,
+      boolean remember,
+      ExternalId.Key lastLogin,
       String sid,
       String auth) {
     // Refresh the cookie every hour or when it is half-expired.
@@ -191,19 +191,19 @@
     private transient Account.Id accountId;
     private transient long refreshCookieAt;
     private transient boolean persistentCookie;
-    private transient AccountExternalId.Key externalId;
+    private transient ExternalId.Key externalId;
     private transient long expiresAt;
     private transient String sessionId;
     private transient String auth;
 
     Val(
-        final Account.Id accountId,
-        final long refreshCookieAt,
-        final boolean persistentCookie,
-        final AccountExternalId.Key externalId,
-        final long expiresAt,
-        final String sessionId,
-        final String auth) {
+        Account.Id accountId,
+        long refreshCookieAt,
+        boolean persistentCookie,
+        ExternalId.Key externalId,
+        long expiresAt,
+        String sessionId,
+        String auth) {
       this.accountId = accountId;
       this.refreshCookieAt = refreshCookieAt;
       this.persistentCookie = persistentCookie;
@@ -221,7 +221,7 @@
       return accountId;
     }
 
-    AccountExternalId.Key getExternalId() {
+    ExternalId.Key getExternalId() {
       return externalId;
     }
 
@@ -253,7 +253,7 @@
 
       if (externalId != null) {
         writeVarInt32(out, 4);
-        writeString(out, externalId.get());
+        writeString(out, externalId.toString());
       }
 
       if (sessionId != null) {
@@ -289,7 +289,7 @@
             persistentCookie = readVarInt32(in) != 0;
             continue;
           case 4:
-            externalId = new AccountExternalId.Key(readString(in));
+            externalId = ExternalId.Key.parse(readString(in));
             continue;
           case 5:
             sessionId = readString(in);
diff --git a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/auth/become/BecomeAnyAccountLoginServlet.java b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/auth/become/BecomeAnyAccountLoginServlet.java
index d6bc5dc..b7c6be3 100644
--- a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/auth/become/BecomeAnyAccountLoginServlet.java
+++ b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/auth/become/BecomeAnyAccountLoginServlet.java
@@ -14,7 +14,8 @@
 
 package com.google.gerrit.httpd.auth.become;
 
-import static com.google.gerrit.reviewdb.client.AccountExternalId.SCHEME_USERNAME;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_USERNAME;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_UUID;
 
 import com.google.gerrit.common.PageLinks;
 import com.google.gerrit.extensions.registration.DynamicItem;
@@ -23,13 +24,13 @@
 import com.google.gerrit.httpd.WebSession;
 import com.google.gerrit.httpd.template.SiteHeaderFooter;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.account.AccountException;
 import com.google.gerrit.server.account.AccountManager;
 import com.google.gerrit.server.account.AccountState;
 import com.google.gerrit.server.account.AuthRequest;
 import com.google.gerrit.server.account.AuthResult;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gerrit.server.query.account.InternalAccountQuery;
 import com.google.gwtexpui.server.CacheHeaders;
 import com.google.gwtorm.server.OrmException;
@@ -179,17 +180,16 @@
     return null;
   }
 
-  private AuthResult auth(final AccountExternalId account) {
+  private AuthResult auth(Account.Id account) {
     if (account != null) {
-      return new AuthResult(account.getAccountId(), null, false);
+      return new AuthResult(account, null, false);
     }
     return null;
   }
 
   private AuthResult byUserName(final String userName) {
     try {
-      AccountExternalId.Key extKey = new AccountExternalId.Key(SCHEME_USERNAME, userName);
-      List<AccountState> accountStates = accountQuery.byExternalId(extKey.get());
+      List<AccountState> accountStates = accountQuery.byExternalId(SCHEME_USERNAME, userName);
       if (accountStates.isEmpty()) {
         getServletContext().log("No accounts with username " + userName + " found");
         return null;
@@ -198,7 +198,7 @@
         getServletContext().log("Multiple accounts with username " + userName + " found");
         return null;
       }
-      return auth(new AccountExternalId(accountStates.get(0).getAccount().getId(), extKey));
+      return auth(accountStates.get(0).getAccount().getId());
     } catch (OrmException e) {
       getServletContext().log("cannot query account index", e);
       return null;
@@ -231,9 +231,9 @@
   }
 
   private AuthResult create() throws IOException {
-    String fakeId = AccountExternalId.SCHEME_UUID + UUID.randomUUID();
     try {
-      return accountManager.authenticate(new AuthRequest(fakeId));
+      return accountManager.authenticate(
+          new AuthRequest(ExternalId.Key.create(SCHEME_UUID, UUID.randomUUID().toString())));
     } catch (AccountException e) {
       getServletContext().log("cannot create new account", e);
       return null;
diff --git a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/auth/container/HttpAuthFilter.java b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/auth/container/HttpAuthFilter.java
index f921dbc..5a0ed71 100644
--- a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/auth/container/HttpAuthFilter.java
+++ b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/auth/container/HttpAuthFilter.java
@@ -17,7 +17,7 @@
 import static com.google.common.base.MoreObjects.firstNonNull;
 import static com.google.common.base.Strings.emptyToNull;
 import static com.google.common.net.HttpHeaders.AUTHORIZATION;
-import static com.google.gerrit.reviewdb.client.AccountExternalId.SCHEME_GERRIT;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_GERRIT;
 import static java.nio.charset.StandardCharsets.ISO_8859_1;
 import static java.nio.charset.StandardCharsets.UTF_8;
 
@@ -26,7 +26,7 @@
 import com.google.gerrit.httpd.RemoteUserUtil;
 import com.google.gerrit.httpd.WebSession;
 import com.google.gerrit.httpd.raw.HostPageServlet;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gerrit.server.config.AuthConfig;
 import com.google.gwtexpui.server.CacheHeaders;
 import com.google.gwtjsonrpc.server.RPCServletUtils;
@@ -127,8 +127,8 @@
   }
 
   private static boolean correctUser(String user, WebSession session) {
-    AccountExternalId.Key id = session.getLastLoginExternalId();
-    return id != null && id.equals(new AccountExternalId.Key(SCHEME_GERRIT, user));
+    ExternalId.Key id = session.getLastLoginExternalId();
+    return id != null && id.equals(ExternalId.Key.create(SCHEME_GERRIT, user));
   }
 
   String getRemoteUser(HttpServletRequest req) {
diff --git a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/auth/container/HttpLoginServlet.java b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/auth/container/HttpLoginServlet.java
index 7bc5e7c..40b543b 100644
--- a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/auth/container/HttpLoginServlet.java
+++ b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/auth/container/HttpLoginServlet.java
@@ -14,7 +14,7 @@
 
 package com.google.gerrit.httpd.auth.container;
 
-import static com.google.gerrit.reviewdb.client.AccountExternalId.SCHEME_EXTERNAL;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_EXTERNAL;
 import static java.nio.charset.StandardCharsets.UTF_8;
 
 import com.google.gerrit.common.PageLinks;
@@ -23,11 +23,11 @@
 import com.google.gerrit.httpd.HtmlDomUtil;
 import com.google.gerrit.httpd.LoginUrlToken;
 import com.google.gerrit.httpd.WebSession;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.server.account.AccountException;
 import com.google.gerrit.server.account.AccountManager;
 import com.google.gerrit.server.account.AuthRequest;
 import com.google.gerrit.server.account.AuthResult;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gerrit.server.config.AuthConfig;
 import com.google.gwtexpui.server.CacheHeaders;
 import com.google.gwtorm.server.OrmException;
@@ -39,6 +39,7 @@
 import javax.servlet.http.HttpServlet;
 import javax.servlet.http.HttpServletRequest;
 import javax.servlet.http.HttpServletResponse;
+import org.eclipse.jgit.errors.ConfigInvalidException;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 import org.w3c.dom.Document;
@@ -127,7 +128,7 @@
       try {
         log.debug("Associating external identity \"{}\" to user \"{}\"", remoteExternalId, user);
         updateRemoteExternalId(arsp, remoteExternalId);
-      } catch (AccountException | OrmException e) {
+      } catch (AccountException | OrmException | ConfigInvalidException e) {
         log.error(
             "Unable to associate external identity \""
                 + remoteExternalId
@@ -156,12 +157,10 @@
   }
 
   private void updateRemoteExternalId(AuthResult arsp, String remoteAuthToken)
-      throws AccountException, OrmException, IOException {
-    AccountExternalId remoteAuthExtId =
-        new AccountExternalId(
-            arsp.getAccountId(), new AccountExternalId.Key(SCHEME_EXTERNAL, remoteAuthToken));
+      throws AccountException, OrmException, IOException, ConfigInvalidException {
     accountManager.updateLink(
-        arsp.getAccountId(), new AuthRequest(remoteAuthExtId.getExternalId()));
+        arsp.getAccountId(),
+        new AuthRequest(ExternalId.Key.create(SCHEME_EXTERNAL, remoteAuthToken)));
   }
 
   private void replace(Document doc, String name, String value) {
diff --git a/gerrit-oauth/BUILD b/gerrit-oauth/BUILD
index b459c70..0ef89c0 100644
--- a/gerrit-oauth/BUILD
+++ b/gerrit-oauth/BUILD
@@ -22,6 +22,7 @@
         "//lib/commons:codec",
         "//lib/guice",
         "//lib/guice:guice-servlet",
+        "//lib/jgit/org.eclipse.jgit:jgit",
         "//lib/log:api",
     ],
 )
diff --git a/gerrit-oauth/src/main/java/com/google/gerrit/httpd/auth/oauth/OAuthSession.java b/gerrit-oauth/src/main/java/com/google/gerrit/httpd/auth/oauth/OAuthSession.java
index 7cfaf46..0391831 100644
--- a/gerrit-oauth/src/main/java/com/google/gerrit/httpd/auth/oauth/OAuthSession.java
+++ b/gerrit-oauth/src/main/java/com/google/gerrit/httpd/auth/oauth/OAuthSession.java
@@ -31,6 +31,7 @@
 import com.google.gerrit.server.account.AccountManager;
 import com.google.gerrit.server.account.AuthRequest;
 import com.google.gerrit.server.account.AuthResult;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gerrit.server.auth.oauth.OAuthTokenCache;
 import com.google.gwtorm.server.OrmException;
 import com.google.inject.Inject;
@@ -44,6 +45,7 @@
 import javax.servlet.http.HttpServletRequest;
 import javax.servlet.http.HttpServletResponse;
 import org.apache.commons.codec.binary.Base64;
+import org.eclipse.jgit.errors.ConfigInvalidException;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
@@ -124,7 +126,7 @@
 
   private void authenticateAndRedirect(
       HttpServletRequest req, HttpServletResponse rsp, OAuthToken token) throws IOException {
-    AuthRequest areq = new AuthRequest(user.getExternalId());
+    AuthRequest areq = new AuthRequest(ExternalId.Key.parse(user.getExternalId()));
     AuthResult arsp;
     try {
       String claimedIdentifier = user.getClaimedIdentity();
@@ -190,7 +192,7 @@
       log.info("OAuth2: linking claimed identity to {}", claimedId.get().toString());
       try {
         accountManager.link(claimedId.get(), req);
-      } catch (OrmException e) {
+      } catch (OrmException | ConfigInvalidException e) {
         log.error(
             "Cannot link: "
                 + user.getExternalId()
@@ -210,7 +212,7 @@
       throws AccountException, IOException {
     try {
       accountManager.link(identifiedUser.get().getAccountId(), areq);
-    } catch (OrmException e) {
+    } catch (OrmException | ConfigInvalidException e) {
       log.error(
           "Cannot link: "
               + user.getExternalId()
diff --git a/gerrit-openid/src/main/java/com/google/gerrit/httpd/auth/openid/OAuthSessionOverOpenID.java b/gerrit-openid/src/main/java/com/google/gerrit/httpd/auth/openid/OAuthSessionOverOpenID.java
index 4a2ffec..e862bac 100644
--- a/gerrit-openid/src/main/java/com/google/gerrit/httpd/auth/openid/OAuthSessionOverOpenID.java
+++ b/gerrit-openid/src/main/java/com/google/gerrit/httpd/auth/openid/OAuthSessionOverOpenID.java
@@ -31,6 +31,7 @@
 import com.google.gerrit.server.account.AccountException;
 import com.google.gerrit.server.account.AccountManager;
 import com.google.gerrit.server.account.AuthResult;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gwtorm.server.OrmException;
 import com.google.inject.Inject;
 import com.google.inject.Provider;
@@ -43,6 +44,7 @@
 import javax.servlet.http.HttpServletRequest;
 import javax.servlet.http.HttpServletResponse;
 import org.apache.commons.codec.binary.Base64;
+import org.eclipse.jgit.errors.ConfigInvalidException;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
@@ -116,7 +118,8 @@
   private void authenticateAndRedirect(HttpServletRequest req, HttpServletResponse rsp)
       throws IOException {
     com.google.gerrit.server.account.AuthRequest areq =
-        new com.google.gerrit.server.account.AuthRequest(user.getExternalId());
+        new com.google.gerrit.server.account.AuthRequest(
+            ExternalId.Key.parse(user.getExternalId()));
     AuthResult arsp = null;
     try {
       String claimedIdentifier = user.getClaimedIdentity();
@@ -167,7 +170,7 @@
           log.debug("Claimed account already exists: link to it.");
           try {
             accountManager.link(claimedId.get(), areq);
-          } catch (OrmException e) {
+          } catch (OrmException | ConfigInvalidException e) {
             log.error(
                 "Cannot link: "
                     + user.getExternalId()
@@ -186,7 +189,7 @@
         try {
           log.debug("Linking \"{}\" to \"{}\"", user.getExternalId(), accountId);
           accountManager.link(accountId, areq);
-        } catch (OrmException e) {
+        } catch (OrmException | ConfigInvalidException e) {
           log.error("Cannot link: " + user.getExternalId() + " to user identity: " + accountId);
           rsp.sendError(HttpServletResponse.SC_FORBIDDEN);
           return;
diff --git a/gerrit-openid/src/main/java/com/google/gerrit/httpd/auth/openid/OpenIdServiceImpl.java b/gerrit-openid/src/main/java/com/google/gerrit/httpd/auth/openid/OpenIdServiceImpl.java
index dbc0d14..efe8c5f 100644
--- a/gerrit-openid/src/main/java/com/google/gerrit/httpd/auth/openid/OpenIdServiceImpl.java
+++ b/gerrit-openid/src/main/java/com/google/gerrit/httpd/auth/openid/OpenIdServiceImpl.java
@@ -26,6 +26,7 @@
 import com.google.gerrit.server.UrlEncoded;
 import com.google.gerrit.server.account.AccountException;
 import com.google.gerrit.server.account.AccountManager;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gerrit.server.auth.openid.OpenIdProviderPattern;
 import com.google.gerrit.server.config.AuthConfig;
 import com.google.gerrit.server.config.ConfigUtil;
@@ -314,7 +315,7 @@
     }
 
     final com.google.gerrit.server.account.AuthRequest areq =
-        new com.google.gerrit.server.account.AuthRequest(openidIdentifier);
+        new com.google.gerrit.server.account.AuthRequest(ExternalId.Key.parse(openidIdentifier));
 
     if (sregRsp != null) {
       areq.setDisplayName(sregRsp.getAttributeValue("fullname"));
@@ -369,7 +370,7 @@
       // link between the two, so set one up if not present.
       //
       Optional<Account.Id> claimedId = accountManager.lookup(claimedIdentifier);
-      Optional<Account.Id> actualId = accountManager.lookup(areq.getExternalId());
+      Optional<Account.Id> actualId = accountManager.lookup(areq.getExternalIdKey().get());
 
       if (claimedId.isPresent() && actualId.isPresent()) {
         if (claimedId.get().equals(actualId.get())) {
@@ -388,7 +389,7 @@
                   + "  Delgate ID: "
                   + actualId.get()
                   + " is "
-                  + areq.getExternalId());
+                  + areq.getExternalIdKey());
           cancelWithError(req, rsp, "Contact site administrator");
           return;
         }
@@ -398,7 +399,8 @@
         // was missing due to a bug in Gerrit. Link the claimed.
         //
         final com.google.gerrit.server.account.AuthRequest linkReq =
-            new com.google.gerrit.server.account.AuthRequest(claimedIdentifier);
+            new com.google.gerrit.server.account.AuthRequest(
+                ExternalId.Key.parse(claimedIdentifier));
         linkReq.setDisplayName(areq.getDisplayName());
         linkReq.setEmailAddress(areq.getEmailAddress());
         accountManager.link(actualId.get(), linkReq);
@@ -434,7 +436,8 @@
           webSession.get().login(arsp, remember);
           if (arsp.isNew() && claimedIdentifier != null) {
             final com.google.gerrit.server.account.AuthRequest linkReq =
-                new com.google.gerrit.server.account.AuthRequest(claimedIdentifier);
+                new com.google.gerrit.server.account.AuthRequest(
+                    ExternalId.Key.parse(claimedIdentifier));
             linkReq.setDisplayName(areq.getDisplayName());
             linkReq.setEmailAddress(areq.getEmailAddress());
             accountManager.link(arsp.getAccountId(), linkReq);
diff --git a/gerrit-pgm/src/main/java/com/google/gerrit/pgm/LocalUsernamesToLowerCase.java b/gerrit-pgm/src/main/java/com/google/gerrit/pgm/LocalUsernamesToLowerCase.java
index 72b8078..7457f40 100644
--- a/gerrit-pgm/src/main/java/com/google/gerrit/pgm/LocalUsernamesToLowerCase.java
+++ b/gerrit-pgm/src/main/java/com/google/gerrit/pgm/LocalUsernamesToLowerCase.java
@@ -14,115 +14,67 @@
 
 package com.google.gerrit.pgm;
 
+import static com.google.gerrit.server.account.ExternalId.SCHEME_GERRIT;
 import static com.google.gerrit.server.schema.DataSourceProvider.Context.MULTI_USER;
 
 import com.google.gerrit.lifecycle.LifecycleManager;
 import com.google.gerrit.pgm.util.SiteProgram;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.server.ReviewDb;
+import com.google.gerrit.server.account.ExternalId;
+import com.google.gerrit.server.account.ExternalIdsBatchUpdate;
 import com.google.gerrit.server.schema.SchemaVersionCheck;
-import com.google.gwtorm.server.OrmException;
 import com.google.gwtorm.server.SchemaFactory;
 import com.google.inject.Inject;
 import com.google.inject.Injector;
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.List;
+import java.util.Collection;
 import java.util.Locale;
 import org.eclipse.jgit.lib.TextProgressMonitor;
-import org.kohsuke.args4j.Option;
 
 /** Converts the local username for all accounts to lower case */
 public class LocalUsernamesToLowerCase extends SiteProgram {
-  @Option(name = "--threads", usage = "Number of concurrent threads to run")
-  private int threads = 2;
-
   private final LifecycleManager manager = new LifecycleManager();
   private final TextProgressMonitor monitor = new TextProgressMonitor();
-  private List<AccountExternalId> todo;
-
-  private Injector dbInjector;
 
   @Inject private SchemaFactory<ReviewDb> database;
 
+  @Inject private ExternalIdsBatchUpdate externalIdsBatchUpdate;
+
   @Override
   public int run() throws Exception {
-    if (threads <= 0) {
-      threads = 1;
-    }
-
-    dbInjector = createDbInjector(MULTI_USER);
+    Injector dbInjector = createDbInjector(MULTI_USER);
     manager.add(dbInjector, dbInjector.createChildInjector(SchemaVersionCheck.module()));
     manager.start();
     dbInjector.injectMembers(this);
 
     try (ReviewDb db = database.open()) {
-      todo = db.accountExternalIds().all().toList();
-      synchronized (monitor) {
-        monitor.beginTask("Converting local usernames", todo.size());
-      }
-    }
+      Collection<ExternalId> todo = ExternalId.from(db.accountExternalIds().all().toList());
+      monitor.beginTask("Converting local usernames", todo.size());
 
-    final List<Worker> workers = new ArrayList<>(threads);
-    for (int tid = 0; tid < threads; tid++) {
-      Worker t = new Worker();
-      t.start();
-      workers.add(t);
+      for (ExternalId extId : todo) {
+        convertLocalUserToLowerCase(extId);
+        monitor.update(1);
+      }
+
+      externalIdsBatchUpdate.commit(db, "Convert local usernames to lower case");
     }
-    for (Worker t : workers) {
-      t.join();
-    }
-    synchronized (monitor) {
-      monitor.endTask();
-    }
+    monitor.endTask();
     manager.stop();
     return 0;
   }
 
-  private void convertLocalUserToLowerCase(final ReviewDb db, final AccountExternalId extId) {
-    if (extId.isScheme(AccountExternalId.SCHEME_GERRIT)) {
-      final String localUser = extId.getSchemeRest();
-      final String localUserLowerCase = localUser.toLowerCase(Locale.US);
+  private void convertLocalUserToLowerCase(ExternalId extId) {
+    if (extId.isScheme(SCHEME_GERRIT)) {
+      String localUser = extId.key().id();
+      String localUserLowerCase = localUser.toLowerCase(Locale.US);
       if (!localUser.equals(localUserLowerCase)) {
-        final AccountExternalId.Key extIdKeyLowerCase =
-            new AccountExternalId.Key(AccountExternalId.SCHEME_GERRIT, localUserLowerCase);
-        final AccountExternalId extIdLowerCase =
-            new AccountExternalId(extId.getAccountId(), extIdKeyLowerCase);
-        try {
-          db.accountExternalIds().insert(Collections.singleton(extIdLowerCase));
-          db.accountExternalIds().delete(Collections.singleton(extId));
-        } catch (OrmException error) {
-          System.err.println("ERR " + error.getMessage());
-        }
-      }
-    }
-  }
-
-  private AccountExternalId next() {
-    synchronized (todo) {
-      if (todo.isEmpty()) {
-        return null;
-      }
-      return todo.remove(todo.size() - 1);
-    }
-  }
-
-  private class Worker extends Thread {
-    @Override
-    public void run() {
-      try (ReviewDb db = database.open()) {
-        for (; ; ) {
-          final AccountExternalId extId = next();
-          if (extId == null) {
-            break;
-          }
-          convertLocalUserToLowerCase(db, extId);
-          synchronized (monitor) {
-            monitor.update(1);
-          }
-        }
-      } catch (OrmException e) {
-        e.printStackTrace();
+        ExternalId extIdLowerCase =
+            ExternalId.create(
+                SCHEME_GERRIT,
+                localUserLowerCase,
+                extId.accountId(),
+                extId.email(),
+                extId.password());
+        externalIdsBatchUpdate.replace(extId, extIdLowerCase);
       }
     }
   }
diff --git a/gerrit-pgm/src/main/java/com/google/gerrit/pgm/init/ExternalIdsOnInit.java b/gerrit-pgm/src/main/java/com/google/gerrit/pgm/init/ExternalIdsOnInit.java
new file mode 100644
index 0000000..86c5f45e
--- /dev/null
+++ b/gerrit-pgm/src/main/java/com/google/gerrit/pgm/init/ExternalIdsOnInit.java
@@ -0,0 +1,85 @@
+// Copyright (C) 2016 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.pgm.init;
+
+import static com.google.gerrit.server.account.ExternalId.toAccountExternalIds;
+
+import com.google.gerrit.pgm.init.api.InitFlags;
+import com.google.gerrit.reviewdb.server.ReviewDb;
+import com.google.gerrit.server.GerritPersonIdentProvider;
+import com.google.gerrit.server.account.ExternalId;
+import com.google.gerrit.server.account.ExternalIds;
+import com.google.gerrit.server.account.ExternalIdsUpdate;
+import com.google.gerrit.server.config.SitePaths;
+import com.google.gwtorm.server.OrmException;
+import com.google.inject.Inject;
+import java.io.File;
+import java.io.IOException;
+import java.nio.file.Path;
+import java.util.Collection;
+import org.eclipse.jgit.errors.ConfigInvalidException;
+import org.eclipse.jgit.internal.storage.file.FileRepository;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectInserter;
+import org.eclipse.jgit.lib.PersonIdent;
+import org.eclipse.jgit.lib.Repository;
+import org.eclipse.jgit.lib.RepositoryCache.FileKey;
+import org.eclipse.jgit.notes.NoteMap;
+import org.eclipse.jgit.revwalk.RevWalk;
+import org.eclipse.jgit.util.FS;
+
+public class ExternalIdsOnInit {
+  private final InitFlags flags;
+  private final SitePaths site;
+  private final String allUsers;
+
+  @Inject
+  public ExternalIdsOnInit(InitFlags flags, SitePaths site, AllUsersNameOnInitProvider allUsers) {
+    this.flags = flags;
+    this.site = site;
+    this.allUsers = allUsers.get();
+  }
+
+  public synchronized void insert(ReviewDb db, String commitMessage, Collection<ExternalId> extIds)
+      throws OrmException, IOException, ConfigInvalidException {
+    db.accountExternalIds().insert(toAccountExternalIds(extIds));
+
+    File path = getPath();
+    if (path != null) {
+      try (Repository repo = new FileRepository(path);
+          RevWalk rw = new RevWalk(repo);
+          ObjectInserter ins = repo.newObjectInserter()) {
+        ObjectId rev = ExternalIds.readRevision(repo);
+
+        NoteMap noteMap = ExternalIds.readNoteMap(rw, rev);
+        for (ExternalId extId : extIds) {
+          ExternalIdsUpdate.insert(rw, ins, noteMap, extId);
+        }
+
+        PersonIdent serverIdent = new GerritPersonIdentProvider(flags.cfg).get();
+        ExternalIdsUpdate.commit(
+            repo, rw, ins, rev, noteMap, commitMessage, serverIdent, serverIdent);
+      }
+    }
+  }
+
+  private File getPath() {
+    Path basePath = site.resolve(flags.cfg.getString("gerrit", null, "basePath"));
+    if (basePath == null) {
+      throw new IllegalStateException("gerrit.basePath must be configured");
+    }
+    return FileKey.resolve(basePath.resolve(allUsers).toFile(), FS.DETECTED);
+  }
+}
diff --git a/gerrit-pgm/src/main/java/com/google/gerrit/pgm/init/InitAdminUser.java b/gerrit-pgm/src/main/java/com/google/gerrit/pgm/init/InitAdminUser.java
index 2fe4ec3..68b2b96 100644
--- a/gerrit-pgm/src/main/java/com/google/gerrit/pgm/init/InitAdminUser.java
+++ b/gerrit-pgm/src/main/java/com/google/gerrit/pgm/init/InitAdminUser.java
@@ -23,13 +23,13 @@
 import com.google.gerrit.pgm.init.api.InitFlags;
 import com.google.gerrit.pgm.init.api.InitStep;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.client.AccountGroup;
 import com.google.gerrit.reviewdb.client.AccountGroupMember;
 import com.google.gerrit.reviewdb.client.AccountGroupName;
 import com.google.gerrit.reviewdb.client.AccountSshKey;
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.account.AccountState;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gerrit.server.index.account.AccountIndex;
 import com.google.gerrit.server.index.account.AccountIndexCollection;
 import com.google.gwtorm.server.SchemaFactory;
@@ -48,15 +48,20 @@
   private final ConsoleUI ui;
   private final InitFlags flags;
   private final VersionedAuthorizedKeysOnInit.Factory authorizedKeysFactory;
+  private final ExternalIdsOnInit externalIds;
   private SchemaFactory<ReviewDb> dbFactory;
   private AccountIndexCollection indexCollection;
 
   @Inject
   InitAdminUser(
-      InitFlags flags, ConsoleUI ui, VersionedAuthorizedKeysOnInit.Factory authorizedKeysFactory) {
+      InitFlags flags,
+      ConsoleUI ui,
+      VersionedAuthorizedKeysOnInit.Factory authorizedKeysFactory,
+      ExternalIdsOnInit externalIds) {
     this.flags = flags;
     this.ui = ui;
     this.authorizedKeysFactory = authorizedKeysFactory;
+    this.externalIds = externalIds;
   }
 
   @Override
@@ -90,24 +95,13 @@
           AccountSshKey sshKey = readSshKey(id);
           String email = readEmail(sshKey);
 
-          List<AccountExternalId> extIds = new ArrayList<>(2);
-          AccountExternalId extUser =
-              new AccountExternalId(
-                  id, new AccountExternalId.Key(AccountExternalId.SCHEME_USERNAME, username));
-          if (!Strings.isNullOrEmpty(httpPassword)) {
-            extUser.setPassword(httpPassword);
-          }
-          extIds.add(extUser);
-          db.accountExternalIds().insert(Collections.singleton(extUser));
+          List<ExternalId> extIds = new ArrayList<>(2);
+          extIds.add(ExternalId.createUsername(username, id, httpPassword));
 
           if (email != null) {
-            AccountExternalId extMailto =
-                new AccountExternalId(
-                    id, new AccountExternalId.Key(AccountExternalId.SCHEME_MAILTO, email));
-            extMailto.setEmailAddress(email);
-            extIds.add(extMailto);
-            db.accountExternalIds().insert(Collections.singleton(extMailto));
+            extIds.add(ExternalId.createEmail(id, email));
           }
+          externalIds.insert(db, "Add external IDs for initial admin user", extIds);
 
           Account a = new Account(id, TimeUtil.nowTs());
           a.setFullName(name);
@@ -123,7 +117,7 @@
           if (sshKey != null) {
             VersionedAuthorizedKeysOnInit authorizedKeys = authorizedKeysFactory.create(id).load();
             authorizedKeys.addKey(sshKey.getSshPublicKey());
-            authorizedKeys.save("Added SSH key for initial admin user\n");
+            authorizedKeys.save("Add SSH key for initial admin user\n");
           }
 
           AccountGroup adminGroup = db.accountGroups().get(adminGroupName.getId());
diff --git a/gerrit-reviewdb/src/main/java/com/google/gerrit/reviewdb/client/Account.java b/gerrit-reviewdb/src/main/java/com/google/gerrit/reviewdb/client/Account.java
index 4e457e1..fb8e296 100644
--- a/gerrit-reviewdb/src/main/java/com/google/gerrit/reviewdb/client/Account.java
+++ b/gerrit-reviewdb/src/main/java/com/google/gerrit/reviewdb/client/Account.java
@@ -25,16 +25,16 @@
 /**
  * Information about a single user.
  *
- * <p>A user may have multiple identities they can use to login to Gerrit (see {@link
- * AccountExternalId}), but in such cases they always map back to a single Account entity.
+ * <p>A user may have multiple identities they can use to login to Gerrit (see ExternalId), but in
+ * such cases they always map back to a single Account entity.
  *
  * <p>Entities "owned" by an Account (that is, their primary key contains the {@link Account.Id} key
  * as part of their key structure):
  *
  * <ul>
- *   <li>{@link AccountExternalId}: OpenID identities and email addresses known to be registered to
- *       this user. Multiple records can exist when the user has more than one public identity, such
- *       as a work and a personal email address.
+ *   <li>ExternalId: OpenID identities and email addresses known to be registered to this user.
+ *       Multiple records can exist when the user has more than one public identity, such as a work
+ *       and a personal email address.
  *   <li>{@link AccountGroupMember}: membership of the user in a specific human managed {@link
  *       AccountGroup}. Multiple records can exist when the user is a member of more than one group.
  *   <li>{@link AccountSshKey}: user's public SSH keys, for authentication through the internal SSH
diff --git a/gerrit-reviewdb/src/main/java/com/google/gerrit/reviewdb/client/AccountExternalId.java b/gerrit-reviewdb/src/main/java/com/google/gerrit/reviewdb/client/AccountExternalId.java
index a789580..3c8f2fa 100644
--- a/gerrit-reviewdb/src/main/java/com/google/gerrit/reviewdb/client/AccountExternalId.java
+++ b/gerrit-reviewdb/src/main/java/com/google/gerrit/reviewdb/client/AccountExternalId.java
@@ -17,6 +17,7 @@
 import com.google.gerrit.extensions.client.AuthType;
 import com.google.gwtorm.client.Column;
 import com.google.gwtorm.client.StringKey;
+import java.util.Objects;
 
 /** Association of an external account identifier to a local {@link Account}. */
 public final class AccountExternalId {
@@ -87,6 +88,8 @@
   @Column(id = 3, notNull = false)
   protected String emailAddress;
 
+  // Encoded version of the hashed and salted password, to be interpreted by the
+  // {@link HashedPassword} class.
   @Column(id = 4, notNull = false)
   protected String password;
 
@@ -140,12 +143,12 @@
     return null != scheme ? getExternalId().substring(scheme.length() + 1) : null;
   }
 
-  public String getPassword() {
-    return password;
+  public void setPassword(String hashed) {
+    password = hashed;
   }
 
-  public void setPassword(String p) {
-    password = p;
+  public String getPassword() {
+    return password;
   }
 
   public boolean isTrusted() {
@@ -163,4 +166,21 @@
   public void setCanDelete(final boolean t) {
     canDelete = t;
   }
+
+  @Override
+  public boolean equals(Object o) {
+    if (o instanceof AccountExternalId) {
+      AccountExternalId extId = (AccountExternalId) o;
+      return Objects.equals(key, extId.key)
+          && Objects.equals(accountId, extId.accountId)
+          && Objects.equals(emailAddress, extId.emailAddress)
+          && Objects.equals(password, extId.password);
+    }
+    return false;
+  }
+
+  @Override
+  public int hashCode() {
+    return Objects.hash(key, accountId, emailAddress, password);
+  }
 }
diff --git a/gerrit-reviewdb/src/main/java/com/google/gerrit/reviewdb/client/RefNames.java b/gerrit-reviewdb/src/main/java/com/google/gerrit/reviewdb/client/RefNames.java
index 176d6a9..b892e3d 100644
--- a/gerrit-reviewdb/src/main/java/com/google/gerrit/reviewdb/client/RefNames.java
+++ b/gerrit-reviewdb/src/main/java/com/google/gerrit/reviewdb/client/RefNames.java
@@ -34,6 +34,9 @@
   /** Configuration settings for a project {@code refs/meta/config} */
   public static final String REFS_CONFIG = "refs/meta/config";
 
+  /** Note tree listing external IDs */
+  public static final String REFS_EXTERNAL_IDS = "refs/meta/external-ids";
+
   /** Preference settings for a user {@code refs/users} */
   public static final String REFS_USERS = "refs/users/";
 
diff --git a/gerrit-server/BUILD b/gerrit-server/BUILD
index be45591..058ca02 100644
--- a/gerrit-server/BUILD
+++ b/gerrit-server/BUILD
@@ -230,9 +230,11 @@
         "//lib:guava",
         "//lib:guava-retrying",
         "//lib:protobuf",
+        "//lib/bouncycastle:bcprov",
         "//lib/dropwizard:dropwizard-core",
         "//lib/guice:guice-assistedinject",
         "//lib/prolog:runtime",
+        "//lib/commons:codec",
     ],
 )
 
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/CurrentUser.java b/gerrit-server/src/main/java/com/google/gerrit/server/CurrentUser.java
index ebed0f9..029b54d 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/CurrentUser.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/CurrentUser.java
@@ -16,8 +16,8 @@
 
 import com.google.gerrit.common.Nullable;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.server.account.CapabilityControl;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gerrit.server.account.GroupMembership;
 import com.google.inject.servlet.RequestScoped;
 import java.util.function.Consumer;
@@ -44,7 +44,7 @@
   private AccessPath accessPath = AccessPath.UNKNOWN;
 
   private CapabilityControl capabilities;
-  private PropertyKey<AccountExternalId.Key> lastLoginExternalIdPropertyKey = PropertyKey.create();
+  private PropertyKey<ExternalId.Key> lastLoginExternalIdPropertyKey = PropertyKey.create();
 
   protected CurrentUser(CapabilityControl.Factory capabilityControlFactory) {
     this.capabilityControlFactory = capabilityControlFactory;
@@ -151,11 +151,11 @@
    */
   public <T> void put(PropertyKey<T> key, @Nullable T value) {}
 
-  public void setLastLoginExternalIdKey(AccountExternalId.Key externalIdKey) {
+  public void setLastLoginExternalIdKey(ExternalId.Key externalIdKey) {
     put(lastLoginExternalIdPropertyKey, externalIdKey);
   }
 
-  public AccountExternalId.Key getLastLoginExternalIdKey() {
+  public ExternalId.Key getLastLoginExternalIdKey() {
     return get(lastLoginExternalIdPropertyKey);
   }
 }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/AbstractRealm.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/AbstractRealm.java
index 3ba457c..0f9ec8d 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/AbstractRealm.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/AbstractRealm.java
@@ -17,7 +17,6 @@
 import com.google.common.base.Strings;
 import com.google.common.collect.Sets;
 import com.google.gerrit.extensions.client.AccountFieldName;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.server.IdentifiedUser;
 import com.google.gerrit.server.mail.send.EmailSender;
 import com.google.inject.Inject;
@@ -53,8 +52,8 @@
 
   @Override
   public boolean hasEmailAddress(IdentifiedUser user, String email) {
-    for (AccountExternalId ext : user.state().getExternalIds()) {
-      if (email != null && email.equalsIgnoreCase(ext.getEmailAddress())) {
+    for (ExternalId ext : user.state().getExternalIds()) {
+      if (email != null && email.equalsIgnoreCase(ext.email())) {
         return true;
       }
     }
@@ -63,11 +62,11 @@
 
   @Override
   public Set<String> getEmailAddresses(IdentifiedUser user) {
-    Collection<AccountExternalId> ids = user.state().getExternalIds();
+    Collection<ExternalId> ids = user.state().getExternalIds();
     Set<String> emails = Sets.newHashSetWithExpectedSize(ids.size());
-    for (AccountExternalId ext : ids) {
-      if (!Strings.isNullOrEmpty(ext.getEmailAddress())) {
-        emails.add(ext.getEmailAddress());
+    for (ExternalId ext : ids) {
+      if (!Strings.isNullOrEmpty(ext.email())) {
+        emails.add(ext.email());
       }
     }
     return emails;
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountByEmailCacheImpl.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountByEmailCacheImpl.java
index 56c41e0..d45ecd8 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountByEmailCacheImpl.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountByEmailCacheImpl.java
@@ -18,7 +18,6 @@
 import com.google.common.cache.LoadingCache;
 import com.google.common.collect.ImmutableSet;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.cache.CacheModule;
 import com.google.gerrit.server.query.account.InternalAccountQuery;
@@ -94,12 +93,15 @@
         for (Account a : db.accounts().byPreferredEmail(email)) {
           r.add(a.getId());
         }
-        for (AccountState accountState :
-            accountQueryProvider
-                .get()
-                .byExternalId(
-                    (new AccountExternalId.Key(AccountExternalId.SCHEME_MAILTO, email)).get())) {
-          r.add(accountState.getAccount().getId());
+        for (AccountState accountState : accountQueryProvider.get().byEmailPrefix(email)) {
+          if (accountState
+              .getExternalIds()
+              .stream()
+              .filter(e -> email.equals(e.email()))
+              .findAny()
+              .isPresent()) {
+            r.add(accountState.getAccount().getId());
+          }
         }
         return ImmutableSet.copyOf(r);
       }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountCacheImpl.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountCacheImpl.java
index 535dfcb..245a0be 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountCacheImpl.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountCacheImpl.java
@@ -14,13 +14,14 @@
 
 package com.google.gerrit.server.account;
 
+import static com.google.gerrit.server.account.ExternalId.SCHEME_USERNAME;
+
 import com.google.common.cache.CacheLoader;
 import com.google.common.cache.LoadingCache;
 import com.google.common.collect.ImmutableSet;
 import com.google.gerrit.common.TimeUtil;
 import com.google.gerrit.extensions.client.GeneralPreferencesInfo;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.client.AccountGroup;
 import com.google.gerrit.reviewdb.client.AccountGroupMember;
 import com.google.gerrit.reviewdb.server.ReviewDb;
@@ -38,7 +39,6 @@
 import com.google.inject.TypeLiteral;
 import com.google.inject.name.Named;
 import java.io.IOException;
-import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
@@ -138,9 +138,9 @@
   private static AccountState missing(Account.Id accountId) {
     Account account = new Account(accountId, TimeUtil.nowTs());
     account.setActive(false);
-    Collection<AccountExternalId> ids = Collections.emptySet();
     Set<AccountGroup.UUID> anon = ImmutableSet.of();
-    return new AccountState(account, anon, ids, new HashMap<ProjectWatchKey, Set<NotifyType>>());
+    return new AccountState(
+        account, anon, Collections.emptySet(), new HashMap<ProjectWatchKey, Set<NotifyType>>());
   }
 
   static class ByIdLoader extends CacheLoader<Account.Id, AccountState> {
@@ -184,8 +184,8 @@
         return missing(who);
       }
 
-      Collection<AccountExternalId> externalIds =
-          Collections.unmodifiableCollection(db.accountExternalIds().byAccount(who).toList());
+      Set<ExternalId> externalIds =
+          ExternalId.from(db.accountExternalIds().byAccount(who).toList());
 
       Set<AccountGroup.UUID> internalGroups = new HashSet<>();
       for (AccountGroupMember g : db.accountGroupMembers().byAccount(who)) {
@@ -219,11 +219,8 @@
 
     @Override
     public Optional<Account.Id> load(String username) throws Exception {
-      AccountExternalId.Key key =
-          new AccountExternalId.Key( //
-              AccountExternalId.SCHEME_USERNAME, //
-              username);
-      AccountState accountState = accountQueryProvider.get().oneByExternalId(key.get());
+      AccountState accountState =
+          accountQueryProvider.get().oneByExternalId(SCHEME_USERNAME, username);
       return Optional.ofNullable(accountState).map(s -> s.getAccount().getId());
     }
   }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountManager.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountManager.java
index 9bbf8ac..77d28f9 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountManager.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountManager.java
@@ -14,6 +14,8 @@
 
 package com.google.gerrit.server.account;
 
+import static java.util.stream.Collectors.toSet;
+
 import com.google.common.base.Strings;
 import com.google.gerrit.audit.AuditService;
 import com.google.gerrit.common.TimeUtil;
@@ -23,7 +25,6 @@
 import com.google.gerrit.common.errors.NameAlreadyUsedException;
 import com.google.gerrit.extensions.client.AccountFieldName;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.client.AccountGroup;
 import com.google.gerrit.reviewdb.client.AccountGroupMember;
 import com.google.gerrit.reviewdb.server.ReviewDb;
@@ -31,17 +32,16 @@
 import com.google.gerrit.server.project.ProjectCache;
 import com.google.gerrit.server.query.account.InternalAccountQuery;
 import com.google.gwtorm.server.OrmException;
-import com.google.gwtorm.server.ResultSet;
 import com.google.gwtorm.server.SchemaFactory;
 import com.google.inject.Inject;
 import com.google.inject.Provider;
 import com.google.inject.Singleton;
 import java.io.IOException;
-import java.util.ArrayList;
+import java.util.Collection;
 import java.util.Collections;
-import java.util.List;
 import java.util.Optional;
 import java.util.concurrent.atomic.AtomicBoolean;
+import org.eclipse.jgit.errors.ConfigInvalidException;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
@@ -60,6 +60,7 @@
   private final AtomicBoolean awaitsFirstAccountCheck;
   private final AuditService auditService;
   private final Provider<InternalAccountQuery> accountQueryProvider;
+  private final ExternalIdsUpdate.Server externalIdsUpdateFactory;
 
   @Inject
   AccountManager(
@@ -71,7 +72,8 @@
       ChangeUserName.Factory changeUserNameFactory,
       ProjectCache projectCache,
       AuditService auditService,
-      Provider<InternalAccountQuery> accountQueryProvider) {
+      Provider<InternalAccountQuery> accountQueryProvider,
+      ExternalIdsUpdate.Server externalIdsUpdateFactory) {
     this.schema = schema;
     this.byIdCache = byIdCache;
     this.byEmailCache = byEmailCache;
@@ -82,6 +84,7 @@
     this.awaitsFirstAccountCheck = new AtomicBoolean(true);
     this.auditService = auditService;
     this.accountQueryProvider = accountQueryProvider;
+    this.externalIdsUpdateFactory = externalIdsUpdateFactory;
   }
 
   /** @return user identified by this external identity string */
@@ -108,8 +111,7 @@
     who = realm.authenticate(who);
     try {
       try (ReviewDb db = schema.open()) {
-        AccountExternalId.Key key = id(who);
-        AccountExternalId id = getAccountExternalId(key);
+        ExternalId id = findExternalId(who.getExternalIdKey());
         if (id == null) {
           // New account, automatically create and return.
           //
@@ -117,25 +119,25 @@
         }
 
         // Account exists
-        Account act = byIdCache.get(id.getAccountId()).getAccount();
+        Account act = byIdCache.get(id.accountId()).getAccount();
         if (!act.isActive()) {
           throw new AccountException("Authentication error, account inactive");
         }
 
         // return the identity to the caller.
         update(db, who, id);
-        return new AuthResult(id.getAccountId(), key, false);
+        return new AuthResult(id.accountId(), who.getExternalIdKey(), false);
       }
-    } catch (OrmException e) {
+    } catch (OrmException | ConfigInvalidException e) {
       throw new AccountException("Authentication error", e);
     }
   }
 
-  private AccountExternalId getAccountExternalId(AccountExternalId.Key key) throws OrmException {
-    AccountState accountState = accountQueryProvider.get().oneByExternalId(key.get());
+  private ExternalId findExternalId(ExternalId.Key key) throws OrmException {
+    AccountState accountState = accountQueryProvider.get().oneByExternalId(key);
     if (accountState != null) {
-      for (AccountExternalId extId : accountState.getExternalIds()) {
-        if (extId.getKey().equals(key)) {
+      for (ExternalId extId : accountState.getExternalIds()) {
+        if (extId.key().equals(key)) {
           return extId;
         }
       }
@@ -143,24 +145,28 @@
     return null;
   }
 
-  private void update(ReviewDb db, AuthRequest who, AccountExternalId extId)
-      throws OrmException, IOException {
-    IdentifiedUser user = userFactory.create(extId.getAccountId());
+  private void update(ReviewDb db, AuthRequest who, ExternalId extId)
+      throws OrmException, IOException, ConfigInvalidException {
+    IdentifiedUser user = userFactory.create(extId.accountId());
     Account toUpdate = null;
 
     // If the email address was modified by the authentication provider,
     // update our records to match the changed email.
     //
     String newEmail = who.getEmailAddress();
-    String oldEmail = extId.getEmailAddress();
+    String oldEmail = extId.email();
     if (newEmail != null && !newEmail.equals(oldEmail)) {
       if (oldEmail != null && oldEmail.equals(user.getAccount().getPreferredEmail())) {
         toUpdate = load(toUpdate, user.getAccountId(), db);
         toUpdate.setPreferredEmail(newEmail);
       }
 
-      extId.setEmailAddress(newEmail);
-      db.accountExternalIds().update(Collections.singleton(extId));
+      externalIdsUpdateFactory
+          .create()
+          .replace(
+              db,
+              extId,
+              ExternalId.create(extId.key(), extId.accountId(), newEmail, extId.password()));
     }
 
     if (!realm.allowsEdit(AccountFieldName.FULL_NAME)
@@ -206,14 +212,14 @@
   }
 
   private AuthResult create(ReviewDb db, AuthRequest who)
-      throws OrmException, AccountException, IOException {
+      throws OrmException, AccountException, IOException, ConfigInvalidException {
     Account.Id newId = new Account.Id(db.nextAccountId());
     Account account = new Account(newId, TimeUtil.nowTs());
-    AccountExternalId extId = createId(newId, who);
 
-    extId.setEmailAddress(who.getEmailAddress());
+    ExternalId extId =
+        ExternalId.createWithEmail(who.getExternalIdKey(), newId, who.getEmailAddress());
     account.setFullName(who.getDisplayName());
-    account.setPreferredEmail(extId.getEmailAddress());
+    account.setPreferredEmail(extId.email());
 
     boolean isFirstAccount =
         awaitsFirstAccountCheck.getAndSet(false) && db.accounts().anyAccounts().toList().isEmpty();
@@ -221,18 +227,19 @@
     try {
       db.accounts().upsert(Collections.singleton(account));
 
-      AccountExternalId existingExtId = db.accountExternalIds().get(extId.getKey());
-      if (existingExtId != null && !existingExtId.getAccountId().equals(extId.getAccountId())) {
+      ExternalId existingExtId =
+          ExternalId.from(db.accountExternalIds().get(extId.key().asAccountExternalIdKey()));
+      if (existingExtId != null && !existingExtId.accountId().equals(extId.accountId())) {
         // external ID is assigned to another account, do not overwrite
         db.accounts().delete(Collections.singleton(account));
         throw new AccountException(
             "Cannot assign external ID \""
-                + extId.getExternalId()
+                + extId.key().get()
                 + "\" to account "
                 + newId
                 + "; external ID already in use.");
       }
-      db.accountExternalIds().upsert(Collections.singleton(extId));
+      externalIdsUpdateFactory.create().upsert(db, extId);
     } finally {
       // If adding the account failed, it may be that it actually was the
       // first account. So we reset the 'check for first account'-guard, as
@@ -291,7 +298,7 @@
     byEmailCache.evict(account.getPreferredEmail());
     byIdCache.evict(account.getId());
     realm.onCreateAccount(who, account);
-    return new AuthResult(newId, extId.getKey(), true);
+    return new AuthResult(newId, extId.key(), true);
   }
 
   /**
@@ -313,11 +320,11 @@
   private void handleSettingUserNameFailure(
       ReviewDb db,
       Account account,
-      AccountExternalId extId,
+      ExternalId extId,
       String errorMessage,
       Exception e,
       boolean logException)
-      throws AccountUserNameException, OrmException {
+      throws AccountUserNameException, OrmException, IOException, ConfigInvalidException {
     if (logException) {
       log.error(errorMessage, e);
     } else {
@@ -333,16 +340,11 @@
       // this is why the best we can do here is to fail early and cleanup
       // the database
       db.accounts().delete(Collections.singleton(account));
-      db.accountExternalIds().delete(Collections.singleton(extId));
+      externalIdsUpdateFactory.create().delete(db, extId);
       throw new AccountUserNameException(errorMessage, e);
     }
   }
 
-  private static AccountExternalId createId(Account.Id newId, AuthRequest who) {
-    String ext = who.getExternalId();
-    return new AccountExternalId(newId, new AccountExternalId.Key(ext));
-  }
-
   /**
    * Link another authentication identity to an existing account.
    *
@@ -353,19 +355,19 @@
    *     this time.
    */
   public AuthResult link(Account.Id to, AuthRequest who)
-      throws AccountException, OrmException, IOException {
+      throws AccountException, OrmException, IOException, ConfigInvalidException {
     try (ReviewDb db = schema.open()) {
-      AccountExternalId.Key key = id(who);
-      AccountExternalId extId = getAccountExternalId(key);
+      ExternalId extId = findExternalId(who.getExternalIdKey());
       if (extId != null) {
-        if (!extId.getAccountId().equals(to)) {
+        if (!extId.accountId().equals(to)) {
           throw new AccountException("Identity in use by another account");
         }
         update(db, who, extId);
       } else {
-        extId = createId(to, who);
-        extId.setEmailAddress(who.getEmailAddress());
-        db.accountExternalIds().insert(Collections.singleton(extId));
+        externalIdsUpdateFactory
+            .create()
+            .insert(
+                db, ExternalId.createWithEmail(who.getExternalIdKey(), to, who.getEmailAddress()));
 
         if (who.getEmailAddress() != null) {
           Account a = db.accounts().get(to);
@@ -381,7 +383,7 @@
         byIdCache.evict(to);
       }
 
-      return new AuthResult(to, key, false);
+      return new AuthResult(to, who.getExternalIdKey(), false);
     }
   }
 
@@ -399,31 +401,28 @@
    *     this time.
    */
   public AuthResult updateLink(Account.Id to, AuthRequest who)
-      throws OrmException, AccountException, IOException {
+      throws OrmException, AccountException, IOException, ConfigInvalidException {
     try (ReviewDb db = schema.open()) {
-      AccountExternalId.Key key = id(who);
-      List<AccountExternalId.Key> filteredKeysByScheme =
-          filterKeysByScheme(key.getScheme(), db.accountExternalIds().byAccount(to));
-      if (!filteredKeysByScheme.isEmpty()
-          && (filteredKeysByScheme.size() > 1 || !filteredKeysByScheme.contains(key))) {
-        db.accountExternalIds().deleteKeys(filteredKeysByScheme);
+      Collection<ExternalId> filteredExtIdsByScheme =
+          ExternalId.from(db.accountExternalIds().byAccount(to).toList())
+              .stream()
+              .filter(e -> e.isScheme(who.getExternalIdKey().scheme()))
+              .collect(toSet());
+
+      if (!filteredExtIdsByScheme.isEmpty()
+          && (filteredExtIdsByScheme.size() > 1
+              || !filteredExtIdsByScheme
+                  .stream()
+                  .filter(e -> e.key().equals(who.getExternalIdKey()))
+                  .findAny()
+                  .isPresent())) {
+        externalIdsUpdateFactory.create().delete(db, filteredExtIdsByScheme);
       }
       byIdCache.evict(to);
       return link(to, who);
     }
   }
 
-  private List<AccountExternalId.Key> filterKeysByScheme(
-      String keyScheme, ResultSet<AccountExternalId> externalIds) {
-    List<AccountExternalId.Key> filteredExternalIds = new ArrayList<>();
-    for (AccountExternalId accountExternalId : externalIds) {
-      if (accountExternalId.isScheme(keyScheme)) {
-        filteredExternalIds.add(accountExternalId.getKey());
-      }
-    }
-    return filteredExternalIds;
-  }
-
   /**
    * Unlink an authentication identity from an existing account.
    *
@@ -434,15 +433,15 @@
    *     at this time.
    */
   public AuthResult unlink(Account.Id from, AuthRequest who)
-      throws AccountException, OrmException, IOException {
+      throws AccountException, OrmException, IOException, ConfigInvalidException {
     try (ReviewDb db = schema.open()) {
-      AccountExternalId.Key key = id(who);
-      AccountExternalId extId = getAccountExternalId(key);
+      ExternalId extId = findExternalId(who.getExternalIdKey());
       if (extId != null) {
-        if (!extId.getAccountId().equals(from)) {
-          throw new AccountException("Identity '" + key.get() + "' in use by another account");
+        if (!extId.accountId().equals(from)) {
+          throw new AccountException(
+              "Identity '" + who.getExternalIdKey().get() + "' in use by another account");
         }
-        db.accountExternalIds().delete(Collections.singleton(extId));
+        externalIdsUpdateFactory.create().delete(db, extId);
 
         if (who.getEmailAddress() != null) {
           Account a = db.accounts().get(from);
@@ -456,14 +455,10 @@
         }
 
       } else {
-        throw new AccountException("Identity '" + key.get() + "' not found");
+        throw new AccountException("Identity '" + who.getExternalIdKey().get() + "' not found");
       }
 
-      return new AuthResult(from, key, false);
+      return new AuthResult(from, who.getExternalIdKey(), false);
     }
   }
-
-  private static AccountExternalId.Key id(AuthRequest who) {
-    return new AccountExternalId.Key(who.getExternalId());
-  }
 }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountState.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountState.java
index b811c84..4b9b0fb 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountState.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountState.java
@@ -14,15 +14,15 @@
 
 package com.google.gerrit.server.account;
 
-import static com.google.gerrit.reviewdb.client.AccountExternalId.SCHEME_MAILTO;
-import static com.google.gerrit.reviewdb.client.AccountExternalId.SCHEME_USERNAME;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_MAILTO;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_USERNAME;
 
 import com.google.common.base.Function;
+import com.google.common.base.Strings;
 import com.google.common.cache.Cache;
 import com.google.common.cache.CacheBuilder;
 import com.google.gerrit.common.Nullable;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.client.AccountGroup;
 import com.google.gerrit.server.CurrentUser.PropertyKey;
 import com.google.gerrit.server.IdentifiedUser;
@@ -32,21 +32,26 @@
 import java.util.HashSet;
 import java.util.Map;
 import java.util.Set;
+import org.apache.commons.codec.DecoderException;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
 
 public class AccountState {
+  private static final Logger logger = LoggerFactory.getLogger(AccountState.class);
+
   public static final Function<AccountState, Account.Id> ACCOUNT_ID_FUNCTION =
       a -> a.getAccount().getId();
 
   private final Account account;
   private final Set<AccountGroup.UUID> internalGroups;
-  private final Collection<AccountExternalId> externalIds;
+  private final Collection<ExternalId> externalIds;
   private final Map<ProjectWatchKey, Set<NotifyType>> projectWatches;
   private Cache<IdentifiedUser.PropertyKey<Object>, Object> properties;
 
   public AccountState(
       Account account,
       Set<AccountGroup.UUID> actualGroups,
-      Collection<AccountExternalId> externalIds,
+      Collection<ExternalId> externalIds,
       Map<ProjectWatchKey, Set<NotifyType>> projectWatches) {
     this.account = account;
     this.internalGroups = actualGroups;
@@ -63,25 +68,38 @@
   /**
    * Get the username, if one has been declared for this user.
    *
-   * <p>The username is the {@link AccountExternalId} using the scheme {@link
-   * AccountExternalId#SCHEME_USERNAME}.
+   * <p>The username is the {@link ExternalId} using the scheme {@link ExternalId#SCHEME_USERNAME}.
    */
   public String getUserName() {
     return account.getUserName();
   }
 
-  /** @return the password matching the requested username; or null. */
-  public String getPassword(String username) {
-    for (AccountExternalId id : getExternalIds()) {
-      if (id.isScheme(AccountExternalId.SCHEME_USERNAME) && username.equals(id.getSchemeRest())) {
-        return id.getPassword();
+  public boolean checkPassword(String password, String username) {
+    if (password == null) {
+      return false;
+    }
+    for (ExternalId id : getExternalIds()) {
+      // Only process the "username:$USER" entry, which is unique.
+      if (!id.isScheme(SCHEME_USERNAME) || !username.equals(id.key().id())) {
+        continue;
+      }
+
+      String hashedStr = id.password();
+      if (!Strings.isNullOrEmpty(hashedStr)) {
+        try {
+          return HashedPassword.decode(hashedStr).checkPassword(password);
+        } catch (DecoderException e) {
+          logger.error(
+              String.format("DecoderException for user %s: %s ", username, e.getMessage()));
+          return false;
+        }
       }
     }
-    return null;
+    return false;
   }
 
   /** The external identities that identify the account holder. */
-  public Collection<AccountExternalId> getExternalIds() {
+  public Collection<ExternalId> getExternalIds() {
     return externalIds;
   }
 
@@ -95,20 +113,20 @@
     return internalGroups;
   }
 
-  public static String getUserName(Collection<AccountExternalId> ids) {
-    for (AccountExternalId id : ids) {
-      if (id.isScheme(SCHEME_USERNAME)) {
-        return id.getSchemeRest();
+  public static String getUserName(Collection<ExternalId> ids) {
+    for (ExternalId extId : ids) {
+      if (extId.isScheme(SCHEME_USERNAME)) {
+        return extId.key().id();
       }
     }
     return null;
   }
 
-  public static Set<String> getEmails(Collection<AccountExternalId> ids) {
+  public static Set<String> getEmails(Collection<ExternalId> ids) {
     Set<String> emails = new HashSet<>();
-    for (AccountExternalId id : ids) {
-      if (id.isScheme(SCHEME_MAILTO)) {
-        emails.add(id.getSchemeRest());
+    for (ExternalId extId : ids) {
+      if (extId.isScheme(SCHEME_MAILTO)) {
+        emails.add(extId.key().id());
       }
     }
     return emails;
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/AuthRequest.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/AuthRequest.java
index 1431640..d1dd4b0 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/AuthRequest.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/AuthRequest.java
@@ -14,11 +14,9 @@
 
 package com.google.gerrit.server.account;
 
-import static com.google.gerrit.reviewdb.client.AccountExternalId.SCHEME_EXTERNAL;
-import static com.google.gerrit.reviewdb.client.AccountExternalId.SCHEME_GERRIT;
-import static com.google.gerrit.reviewdb.client.AccountExternalId.SCHEME_MAILTO;
-
-import com.google.gerrit.reviewdb.client.AccountExternalId;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_EXTERNAL;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_GERRIT;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_MAILTO;
 
 /**
  * Information for {@link AccountManager#authenticate(AuthRequest)}.
@@ -30,17 +28,15 @@
  */
 public class AuthRequest {
   /** Create a request for a local username, such as from LDAP. */
-  public static AuthRequest forUser(final String username) {
-    final AccountExternalId.Key i = new AccountExternalId.Key(SCHEME_GERRIT, username);
-    final AuthRequest r = new AuthRequest(i.get());
+  public static AuthRequest forUser(String username) {
+    AuthRequest r = new AuthRequest(ExternalId.Key.create(SCHEME_GERRIT, username));
     r.setUserName(username);
     return r;
   }
 
   /** Create a request for an external username. */
   public static AuthRequest forExternalUser(String username) {
-    AccountExternalId.Key i = new AccountExternalId.Key(SCHEME_EXTERNAL, username);
-    AuthRequest r = new AuthRequest(i.get());
+    AuthRequest r = new AuthRequest(ExternalId.Key.create(SCHEME_EXTERNAL, username));
     r.setUserName(username);
     return r;
   }
@@ -51,14 +47,13 @@
    * <p>This type of request should be used only to attach a new email address to an existing user
    * account.
    */
-  public static AuthRequest forEmail(final String email) {
-    final AccountExternalId.Key i = new AccountExternalId.Key(SCHEME_MAILTO, email);
-    final AuthRequest r = new AuthRequest(i.get());
+  public static AuthRequest forEmail(String email) {
+    AuthRequest r = new AuthRequest(ExternalId.Key.create(SCHEME_MAILTO, email));
     r.setEmailAddress(email);
     return r;
   }
 
-  private String externalId;
+  private ExternalId.Key externalId;
   private String password;
   private String displayName;
   private String emailAddress;
@@ -67,29 +62,24 @@
   private String authPlugin;
   private String authProvider;
 
-  public AuthRequest(final String externalId) {
+  public AuthRequest(ExternalId.Key externalId) {
     this.externalId = externalId;
   }
 
-  public String getExternalId() {
+  public ExternalId.Key getExternalIdKey() {
     return externalId;
   }
 
-  public boolean isScheme(final String scheme) {
-    return getExternalId().startsWith(scheme);
-  }
-
   public String getLocalUser() {
-    if (isScheme(SCHEME_GERRIT)) {
-      return getExternalId().substring(SCHEME_GERRIT.length());
+    if (externalId.isScheme(SCHEME_GERRIT)) {
+      return externalId.id();
     }
     return null;
   }
 
-  public void setLocalUser(final String localUser) {
-    if (isScheme(SCHEME_GERRIT)) {
-      final AccountExternalId.Key key = new AccountExternalId.Key(SCHEME_GERRIT, localUser);
-      externalId = key.get();
+  public void setLocalUser(String localUser) {
+    if (externalId.isScheme(SCHEME_GERRIT)) {
+      externalId = ExternalId.Key.create(SCHEME_GERRIT, localUser);
     }
   }
 
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/AuthResult.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/AuthResult.java
index 1e75b63..4aced52 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/AuthResult.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/AuthResult.java
@@ -15,16 +15,14 @@
 package com.google.gerrit.server.account;
 
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 
 /** Result from {@link AccountManager#authenticate(AuthRequest)}. */
 public class AuthResult {
   private final Account.Id accountId;
-  private final AccountExternalId.Key externalId;
+  private final ExternalId.Key externalId;
   private final boolean isNew;
 
-  public AuthResult(
-      final Account.Id accountId, final AccountExternalId.Key externalId, final boolean isNew) {
+  public AuthResult(Account.Id accountId, ExternalId.Key externalId, boolean isNew) {
     this.accountId = accountId;
     this.externalId = externalId;
     this.isNew = isNew;
@@ -36,7 +34,7 @@
   }
 
   /** External identity used to authenticate the user. */
-  public AccountExternalId.Key getExternalId() {
+  public ExternalId.Key getExternalId() {
     return externalId;
   }
 
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/ChangeUserName.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/ChangeUserName.java
index 39c732e..f60ee45 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/ChangeUserName.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/ChangeUserName.java
@@ -14,12 +14,12 @@
 
 package com.google.gerrit.server.account;
 
-import static com.google.gerrit.reviewdb.client.AccountExternalId.SCHEME_USERNAME;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_USERNAME;
+import static java.util.stream.Collectors.toSet;
 
 import com.google.gerrit.common.Nullable;
 import com.google.gerrit.common.errors.NameAlreadyUsedException;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.IdentifiedUser;
 import com.google.gerrit.server.ssh.SshKeyCache;
@@ -29,11 +29,10 @@
 import com.google.inject.Inject;
 import com.google.inject.assistedinject.Assisted;
 import java.io.IOException;
-import java.util.ArrayList;
 import java.util.Collection;
-import java.util.Collections;
 import java.util.concurrent.Callable;
 import java.util.regex.Pattern;
+import org.eclipse.jgit.errors.ConfigInvalidException;
 
 /** Operation to change the username of an account. */
 public class ChangeUserName implements Callable<VoidResult> {
@@ -48,6 +47,7 @@
 
   private final AccountCache accountCache;
   private final SshKeyCache sshKeyCache;
+  private final ExternalIdsUpdate.Server externalIdsUpdateFactory;
 
   private final ReviewDb db;
   private final IdentifiedUser user;
@@ -55,14 +55,15 @@
 
   @Inject
   ChangeUserName(
-      final AccountCache accountCache,
-      final SshKeyCache sshKeyCache,
-      @Assisted final ReviewDb db,
-      @Assisted final IdentifiedUser user,
-      @Nullable @Assisted final String newUsername) {
+      AccountCache accountCache,
+      SshKeyCache sshKeyCache,
+      ExternalIdsUpdate.Server externalIdsUpdateFactory,
+      @Assisted ReviewDb db,
+      @Assisted IdentifiedUser user,
+      @Nullable @Assisted String newUsername) {
     this.accountCache = accountCache;
     this.sshKeyCache = sshKeyCache;
-
+    this.externalIdsUpdateFactory = externalIdsUpdateFactory;
     this.db = db;
     this.user = user;
     this.newUsername = newUsername;
@@ -70,33 +71,38 @@
 
   @Override
   public VoidResult call()
-      throws OrmException, NameAlreadyUsedException, InvalidUserNameException, IOException {
-    final Collection<AccountExternalId> old = old();
+      throws OrmException, NameAlreadyUsedException, InvalidUserNameException, IOException,
+          ConfigInvalidException {
+    Collection<ExternalId> old =
+        ExternalId.from(db.accountExternalIds().byAccount(user.getAccountId()).toList())
+            .stream()
+            .filter(e -> e.isScheme(SCHEME_USERNAME))
+            .collect(toSet());
     if (!old.isEmpty()) {
       throw new IllegalStateException(USERNAME_CANNOT_BE_CHANGED);
     }
 
+    ExternalIdsUpdate externalIdsUpdate = externalIdsUpdateFactory.create();
     if (newUsername != null && !newUsername.isEmpty()) {
       if (!USER_NAME_PATTERN.matcher(newUsername).matches()) {
         throw new InvalidUserNameException();
       }
 
-      final AccountExternalId.Key key = new AccountExternalId.Key(SCHEME_USERNAME, newUsername);
+      ExternalId.Key key = ExternalId.Key.create(SCHEME_USERNAME, newUsername);
       try {
-        final AccountExternalId id = new AccountExternalId(user.getAccountId(), key);
-
-        for (AccountExternalId i : old) {
-          if (i.getPassword() != null) {
-            id.setPassword(i.getPassword());
+        String password = null;
+        for (ExternalId i : old) {
+          if (i.password() != null) {
+            password = i.password();
           }
         }
-
-        db.accountExternalIds().insert(Collections.singleton(id));
+        externalIdsUpdate.insert(db, ExternalId.create(key, user.getAccountId(), null, password));
       } catch (OrmDuplicateKeyException dupeErr) {
         // If we are using this identity, don't report the exception.
         //
-        AccountExternalId other = db.accountExternalIds().get(key);
-        if (other != null && other.getAccountId().equals(user.getAccountId())) {
+        ExternalId other =
+            ExternalId.from(db.accountExternalIds().get(key.asAccountExternalIdKey()));
+        if (other != null && other.accountId().equals(user.getAccountId())) {
           return VoidResult.INSTANCE;
         }
 
@@ -108,10 +114,10 @@
 
     // If we have any older user names, remove them.
     //
-    db.accountExternalIds().delete(old);
-    for (AccountExternalId i : old) {
-      sshKeyCache.evict(i.getSchemeRest());
-      accountCache.evictByUsername(i.getSchemeRest());
+    externalIdsUpdate.delete(db, old);
+    for (ExternalId extId : old) {
+      sshKeyCache.evict(extId.key().id());
+      accountCache.evictByUsername(extId.key().id());
     }
 
     accountCache.evict(user.getAccountId());
@@ -119,14 +125,4 @@
     sshKeyCache.evict(newUsername);
     return VoidResult.INSTANCE;
   }
-
-  private Collection<AccountExternalId> old() throws OrmException {
-    final Collection<AccountExternalId> r = new ArrayList<>(1);
-    for (AccountExternalId i : db.accountExternalIds().byAccount(user.getAccountId())) {
-      if (i.isScheme(SCHEME_USERNAME)) {
-        r.add(i);
-      }
-    }
-    return r;
-  }
 }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/CreateAccount.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/CreateAccount.java
index 45f9183..9e7e9a4d 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/CreateAccount.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/CreateAccount.java
@@ -14,6 +14,8 @@
 
 package com.google.gerrit.server.account;
 
+import static com.google.gerrit.server.account.ExternalId.SCHEME_MAILTO;
+
 import com.google.gerrit.audit.AuditService;
 import com.google.gerrit.common.TimeUtil;
 import com.google.gerrit.common.data.GlobalCapability;
@@ -30,7 +32,6 @@
 import com.google.gerrit.extensions.restapi.TopLevelResource;
 import com.google.gerrit.extensions.restapi.UnprocessableEntityException;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.client.AccountGroup;
 import com.google.gerrit.reviewdb.client.AccountGroupMember;
 import com.google.gerrit.reviewdb.server.ReviewDb;
@@ -70,6 +71,7 @@
   private final AccountLoader.Factory infoLoader;
   private final DynamicSet<AccountExternalIdCreator> externalIdCreators;
   private final AuditService auditService;
+  private final ExternalIdsUpdate.User externalIdsUpdateFactory;
   private final String username;
 
   @Inject
@@ -85,6 +87,7 @@
       AccountLoader.Factory infoLoader,
       DynamicSet<AccountExternalIdCreator> externalIdCreators,
       AuditService auditService,
+      ExternalIdsUpdate.User externalIdsUpdateFactory,
       @Assisted String username) {
     this.db = db;
     this.currentUser = currentUser;
@@ -97,6 +100,7 @@
     this.infoLoader = infoLoader;
     this.externalIdCreators = externalIdCreators;
     this.auditService = auditService;
+    this.externalIdsUpdateFactory = externalIdsUpdateFactory;
     this.username = username;
   }
 
@@ -120,19 +124,14 @@
 
     Account.Id id = new Account.Id(db.nextAccountId());
 
-    AccountExternalId extUser =
-        new AccountExternalId(
-            id, new AccountExternalId.Key(AccountExternalId.SCHEME_USERNAME, username));
-
-    if (input.httpPassword != null) {
-      extUser.setPassword(input.httpPassword);
-    }
-
-    if (db.accountExternalIds().get(extUser.getKey()) != null) {
+    ExternalId extUser = ExternalId.createUsername(username, id, input.httpPassword);
+    if (db.accountExternalIds().get(extUser.key().asAccountExternalIdKey()) != null) {
       throw new ResourceConflictException("username '" + username + "' already exists");
     }
     if (input.email != null) {
-      if (db.accountExternalIds().get(getEmailKey(input.email)) != null) {
+      if (db.accountExternalIds()
+              .get(ExternalId.Key.create(SCHEME_MAILTO, input.email).asAccountExternalIdKey())
+          != null) {
         throw new UnprocessableEntityException("email '" + input.email + "' already exists");
       }
       if (!OutgoingEmailValidator.isValid(input.email)) {
@@ -140,27 +139,26 @@
       }
     }
 
-    List<AccountExternalId> externalIds = new ArrayList<>();
-    externalIds.add(extUser);
+    List<ExternalId> extIds = new ArrayList<>();
+    extIds.add(extUser);
     for (AccountExternalIdCreator c : externalIdCreators) {
-      externalIds.addAll(c.create(id, username, input.email));
+      extIds.addAll(c.create(id, username, input.email));
     }
 
+    ExternalIdsUpdate externalIdsUpdate = externalIdsUpdateFactory.create();
     try {
-      db.accountExternalIds().insert(externalIds);
+      externalIdsUpdate.insert(db, extIds);
     } catch (OrmDuplicateKeyException duplicateKey) {
       throw new ResourceConflictException("username '" + username + "' already exists");
     }
 
     if (input.email != null) {
-      AccountExternalId extMailto = new AccountExternalId(id, getEmailKey(input.email));
-      extMailto.setEmailAddress(input.email);
       try {
-        db.accountExternalIds().insert(Collections.singleton(extMailto));
+        externalIdsUpdate.insert(db, ExternalId.createEmail(id, input.email));
       } catch (OrmDuplicateKeyException duplicateKey) {
         try {
-          db.accountExternalIds().delete(Collections.singleton(extUser));
-        } catch (OrmException cleanupError) {
+          externalIdsUpdate.delete(db, extUser);
+        } catch (IOException | ConfigInvalidException | OrmException cleanupError) {
           // Ignored
         }
         throw new UnprocessableEntityException("email '" + input.email + "' already exists");
@@ -208,8 +206,4 @@
     }
     return groupIds;
   }
-
-  private AccountExternalId.Key getEmailKey(String email) {
-    return new AccountExternalId.Key(AccountExternalId.SCHEME_MAILTO, email);
-  }
 }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/CreateEmail.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/CreateEmail.java
index 005630c..b1a5d3b 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/CreateEmail.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/CreateEmail.java
@@ -37,6 +37,7 @@
 import com.google.inject.Provider;
 import com.google.inject.assistedinject.Assisted;
 import java.io.IOException;
+import org.eclipse.jgit.errors.ConfigInvalidException;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
@@ -77,7 +78,7 @@
   public Response<EmailInfo> apply(AccountResource rsrc, EmailInput input)
       throws AuthException, BadRequestException, ResourceConflictException,
           ResourceNotFoundException, OrmException, EmailException, MethodNotAllowedException,
-          IOException {
+          IOException, ConfigInvalidException {
     if (self.get() != rsrc.getUser() && !self.get().getCapabilities().canModifyAccount()) {
       throw new AuthException("not allowed to add email address");
     }
@@ -104,7 +105,7 @@
   public Response<EmailInfo> apply(IdentifiedUser user, EmailInput input)
       throws AuthException, BadRequestException, ResourceConflictException,
           ResourceNotFoundException, OrmException, EmailException, MethodNotAllowedException,
-          IOException {
+          IOException, ConfigInvalidException {
     if (input.email != null && !email.equals(input.email)) {
       throw new BadRequestException("email address must match URL");
     }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/DeleteEmail.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/DeleteEmail.java
index 8541cf8..794a2c1 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/DeleteEmail.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/DeleteEmail.java
@@ -23,7 +23,6 @@
 import com.google.gerrit.extensions.restapi.ResourceNotFoundException;
 import com.google.gerrit.extensions.restapi.Response;
 import com.google.gerrit.extensions.restapi.RestModifyView;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.CurrentUser;
 import com.google.gerrit.server.IdentifiedUser;
@@ -34,6 +33,7 @@
 import com.google.inject.Singleton;
 import java.io.IOException;
 import java.util.Set;
+import org.eclipse.jgit.errors.ConfigInvalidException;
 
 @Singleton
 public class DeleteEmail implements RestModifyView<AccountResource.Email, Input> {
@@ -59,7 +59,7 @@
   @Override
   public Response<?> apply(AccountResource.Email rsrc, Input input)
       throws AuthException, ResourceNotFoundException, ResourceConflictException,
-          MethodNotAllowedException, OrmException, IOException {
+          MethodNotAllowedException, OrmException, IOException, ConfigInvalidException {
     if (self.get() != rsrc.getUser() && !self.get().getCapabilities().canModifyAccount()) {
       throw new AuthException("not allowed to delete email address");
     }
@@ -68,27 +68,28 @@
 
   public Response<?> apply(IdentifiedUser user, String email)
       throws ResourceNotFoundException, ResourceConflictException, MethodNotAllowedException,
-          OrmException, IOException {
+          OrmException, IOException, ConfigInvalidException {
     if (!realm.allowsEdit(AccountFieldName.REGISTER_NEW_EMAIL)) {
       throw new MethodNotAllowedException("realm does not allow deleting emails");
     }
 
-    Set<AccountExternalId> extIds =
+    Set<ExternalId> extIds =
         dbProvider
             .get()
             .accountExternalIds()
             .byAccount(user.getAccountId())
             .toList()
             .stream()
-            .filter(e -> email.equals(e.getEmailAddress()))
+            .map(ExternalId::from)
+            .filter(e -> email.equals(e.email()))
             .collect(toSet());
     if (extIds.isEmpty()) {
       throw new ResourceNotFoundException(email);
     }
 
     try {
-      for (AccountExternalId extId : extIds) {
-        AuthRequest authRequest = new AuthRequest(extId.getKey().get());
+      for (ExternalId extId : extIds) {
+        AuthRequest authRequest = new AuthRequest(extId.key());
         authRequest.setEmailAddress(email);
         accountManager.unlink(user.getAccountId(), authRequest);
       }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/DeleteExternalIds.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/DeleteExternalIds.java
index 55e0581..aff843a 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/DeleteExternalIds.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/DeleteExternalIds.java
@@ -14,7 +14,7 @@
 
 package com.google.gerrit.server.account;
 
-import static com.google.gerrit.reviewdb.client.AccountExternalId.SCHEME_USERNAME;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_USERNAME;
 
 import com.google.gerrit.extensions.restapi.AuthException;
 import com.google.gerrit.extensions.restapi.BadRequestException;
@@ -24,44 +24,42 @@
 import com.google.gerrit.extensions.restapi.RestModifyView;
 import com.google.gerrit.extensions.restapi.UnprocessableEntityException;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.CurrentUser;
 import com.google.gwtorm.server.OrmException;
 import com.google.inject.Inject;
 import com.google.inject.Provider;
-import com.google.inject.Singleton;
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Map;
 import java.util.stream.Collectors;
+import org.eclipse.jgit.errors.ConfigInvalidException;
 
-@Singleton
 public class DeleteExternalIds implements RestModifyView<AccountResource, List<String>> {
-  private final Provider<ReviewDb> db;
   private final AccountByEmailCache accountByEmailCache;
   private final AccountCache accountCache;
+  private final ExternalIdsUpdate.User externalIdsUpdateFactory;
   private final Provider<CurrentUser> self;
   private final Provider<ReviewDb> dbProvider;
 
   @Inject
   DeleteExternalIds(
-      Provider<ReviewDb> db,
       AccountByEmailCache accountByEmailCache,
       AccountCache accountCache,
+      ExternalIdsUpdate.User externalIdsUpdateFactory,
       Provider<CurrentUser> self,
       Provider<ReviewDb> dbProvider) {
-    this.db = db;
     this.accountByEmailCache = accountByEmailCache;
     this.accountCache = accountCache;
+    this.externalIdsUpdateFactory = externalIdsUpdateFactory;
     this.self = self;
     this.dbProvider = dbProvider;
   }
 
   @Override
   public Response<?> apply(AccountResource resource, List<String> externalIds)
-      throws RestApiException, IOException, OrmException {
+      throws RestApiException, IOException, OrmException, ConfigInvalidException {
     if (self.get() != resource.getUser()) {
       throw new AuthException("not allowed to delete external IDs");
     }
@@ -71,18 +69,20 @@
     }
 
     Account.Id accountId = resource.getUser().getAccountId();
-    Map<AccountExternalId.Key, AccountExternalId> externalIdMap =
-        db.get()
+    Map<ExternalId.Key, ExternalId> externalIdMap =
+        dbProvider
+            .get()
             .accountExternalIds()
             .byAccount(resource.getUser().getAccountId())
             .toList()
             .stream()
-            .collect(Collectors.toMap(i -> i.getKey(), i -> i));
+            .map(ExternalId::from)
+            .collect(Collectors.toMap(i -> i.key(), i -> i));
 
-    List<AccountExternalId> toDelete = new ArrayList<>();
-    AccountExternalId.Key last = resource.getUser().getLastLoginExternalIdKey();
+    List<ExternalId> toDelete = new ArrayList<>();
+    ExternalId.Key last = resource.getUser().getLastLoginExternalIdKey();
     for (String externalIdStr : externalIds) {
-      AccountExternalId id = externalIdMap.get(new AccountExternalId.Key(externalIdStr));
+      ExternalId id = externalIdMap.get(ExternalId.Key.parse(externalIdStr));
 
       if (id == null) {
         throw new UnprocessableEntityException(
@@ -90,7 +90,7 @@
       }
 
       if ((!id.isScheme(SCHEME_USERNAME))
-          && ((last == null) || (!last.get().equals(id.getExternalId())))) {
+          && ((last == null) || (!last.get().equals(id.key().get())))) {
         toDelete.add(id);
       } else {
         throw new ResourceConflictException(
@@ -99,10 +99,10 @@
     }
 
     if (!toDelete.isEmpty()) {
-      dbProvider.get().accountExternalIds().delete(toDelete);
+      externalIdsUpdateFactory.create().delete(dbProvider.get(), toDelete);
       accountCache.evict(accountId);
-      for (AccountExternalId e : toDelete) {
-        accountByEmailCache.evict(e.getEmailAddress());
+      for (ExternalId e : toDelete) {
+        accountByEmailCache.evict(e.email());
       }
     }
 
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/ExternalId.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/ExternalId.java
new file mode 100644
index 0000000..45129e3
--- /dev/null
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/ExternalId.java
@@ -0,0 +1,321 @@
+// Copyright (C) 2016 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.server.account;
+
+import static java.nio.charset.StandardCharsets.UTF_8;
+import static java.util.stream.Collectors.toSet;
+
+import com.google.auto.value.AutoValue;
+import com.google.common.base.Strings;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
+import com.google.common.hash.Hashing;
+import com.google.common.primitives.Ints;
+import com.google.gerrit.common.Nullable;
+import com.google.gerrit.extensions.client.AuthType;
+import com.google.gerrit.reviewdb.client.Account;
+import com.google.gerrit.reviewdb.client.AccountExternalId;
+import java.util.Collection;
+import java.util.Set;
+import org.eclipse.jgit.errors.ConfigInvalidException;
+import org.eclipse.jgit.lib.Config;
+import org.eclipse.jgit.lib.ObjectId;
+
+@AutoValue
+public abstract class ExternalId {
+  private static final String EXTERNAL_ID_SECTION = "externalId";
+  private static final String ACCOUNT_ID_KEY = "accountId";
+  private static final String EMAIL_KEY = "email";
+  private static final String PASSWORD_KEY = "password";
+
+  /**
+   * Scheme used for {@link AuthType#LDAP}, {@link AuthType#CLIENT_SSL_CERT_LDAP}, {@link
+   * AuthType#HTTP_LDAP}, and {@link AuthType#LDAP_BIND} usernames.
+   *
+   * <p>The name {@code gerrit:} was a very poor choice.
+   */
+  public static final String SCHEME_GERRIT = "gerrit";
+
+  /** Scheme used for randomly created identities constructed by a UUID. */
+  public static final String SCHEME_UUID = "uuid";
+
+  /** Scheme used to represent only an email address. */
+  public static final String SCHEME_MAILTO = "mailto";
+
+  /** Scheme for the username used to authenticate an account, e.g. over SSH. */
+  public static final String SCHEME_USERNAME = "username";
+
+  /** Scheme used for GPG public keys. */
+  public static final String SCHEME_GPGKEY = "gpgkey";
+
+  /** Scheme for external auth used during authentication, e.g. OAuth Token */
+  public static final String SCHEME_EXTERNAL = "external";
+
+  @AutoValue
+  public abstract static class Key {
+    public static Key create(@Nullable String scheme, String id) {
+      return new AutoValue_ExternalId_Key(scheme, id);
+    }
+
+    public static ExternalId.Key from(AccountExternalId.Key externalIdKey) {
+      return parse(externalIdKey.get());
+    }
+
+    /**
+     * Parses an external ID key from a string in the format "scheme:id" or "id".
+     *
+     * @return the parsed external ID key
+     */
+    public static Key parse(String externalId) {
+      int c = externalId.indexOf(':');
+      if (c < 1 || c >= externalId.length() - 1) {
+        return create(null, externalId);
+      }
+      return create(externalId.substring(0, c), externalId.substring(c + 1));
+    }
+
+    public static Set<AccountExternalId.Key> toAccountExternalIdKeys(
+        Collection<ExternalId.Key> extIdKeys) {
+      return extIdKeys.stream().map(k -> k.asAccountExternalIdKey()).collect(toSet());
+    }
+
+    public abstract @Nullable String scheme();
+
+    public abstract String id();
+
+    public boolean isScheme(String scheme) {
+      return scheme.equals(scheme());
+    }
+
+    public AccountExternalId.Key asAccountExternalIdKey() {
+      if (scheme() != null) {
+        return new AccountExternalId.Key(scheme(), id());
+      }
+      return new AccountExternalId.Key(id());
+    }
+
+    /**
+     * Returns the SHA1 of the external ID that is used as note ID in the refs/meta/external-ids
+     * notes branch.
+     */
+    public ObjectId sha1() {
+      return ObjectId.fromRaw(Hashing.sha1().hashString(get(), UTF_8).asBytes());
+    }
+
+    /**
+     * Exports this external ID key as string with the format "scheme:id", or "id" id scheme is
+     * null.
+     *
+     * <p>This string representation is used as subsection name in the Git config file that stores
+     * the external ID.
+     */
+    public String get() {
+      if (scheme() != null) {
+        return scheme() + ":" + id();
+      }
+      return id();
+    }
+
+    @Override
+    public String toString() {
+      return get();
+    }
+  }
+
+  public static ExternalId create(String scheme, String id, Account.Id accountId) {
+    return new AutoValue_ExternalId(Key.create(scheme, id), accountId, null, null);
+  }
+
+  public static ExternalId create(
+      String scheme,
+      String id,
+      Account.Id accountId,
+      @Nullable String email,
+      @Nullable String hashedPassword) {
+    return create(Key.create(scheme, id), accountId, email, hashedPassword);
+  }
+
+  public static ExternalId create(Key key, Account.Id accountId) {
+    return create(key, accountId, null, null);
+  }
+
+  public static ExternalId create(
+      Key key, Account.Id accountId, @Nullable String email, @Nullable String hashedPassword) {
+    return new AutoValue_ExternalId(key, accountId, email, hashedPassword);
+  }
+
+  public static ExternalId createWithPassword(
+      Key key, Account.Id accountId, @Nullable String email, String plainPassword) {
+    plainPassword = Strings.emptyToNull(plainPassword);
+    String hashedPassword =
+        plainPassword != null ? HashedPassword.fromPassword(plainPassword).encode() : null;
+    return create(key, accountId, email, hashedPassword);
+  }
+
+  public static ExternalId createUsername(String id, Account.Id accountId, String plainPassword) {
+    return createWithPassword(Key.create(SCHEME_USERNAME, id), accountId, null, plainPassword);
+  }
+
+  public static ExternalId createWithEmail(
+      String scheme, String id, Account.Id accountId, String email) {
+    return createWithEmail(Key.create(scheme, id), accountId, email);
+  }
+
+  public static ExternalId createWithEmail(Key key, Account.Id accountId, String email) {
+    return new AutoValue_ExternalId(key, accountId, email, null);
+  }
+
+  public static ExternalId createEmail(Account.Id accountId, String email) {
+    return createWithEmail(SCHEME_MAILTO, email, accountId, email);
+  }
+
+  /**
+   * Parses an external ID from a byte array that contain the external ID as an Git config file
+   * text.
+   *
+   * <p>The Git config must have exactly one externalId subsection with an accountId and optionally
+   * email and password:
+   *
+   * <pre>
+   * [externalId "username:jdoe"]
+   *   accountId = 1003407
+   *   email = jdoe@example.com
+   *   password = bcrypt:4:LCbmSBDivK/hhGVQMfkDpA==:XcWn0pKYSVU/UJgOvhidkEtmqCp6oKB7
+   * </pre>
+   */
+  public static ExternalId parse(String noteId, byte[] raw) throws ConfigInvalidException {
+    Config externalIdConfig = new Config();
+    try {
+      externalIdConfig.fromText(new String(raw, UTF_8));
+    } catch (ConfigInvalidException e) {
+      throw invalidConfig(noteId, e.getMessage());
+    }
+
+    Set<String> externalIdKeys = externalIdConfig.getSubsections(EXTERNAL_ID_SECTION);
+    if (externalIdKeys.size() != 1) {
+      throw invalidConfig(
+          noteId,
+          String.format(
+              "Expected exactly 1 %s section, found %d",
+              EXTERNAL_ID_SECTION, externalIdKeys.size()));
+    }
+
+    String externalIdKeyStr = Iterables.getOnlyElement(externalIdKeys);
+    Key externalIdKey = Key.parse(externalIdKeyStr);
+    if (externalIdKey == null) {
+      throw invalidConfig(noteId, String.format("Invalid external id: %s", externalIdKeyStr));
+    }
+
+    String accountIdStr =
+        externalIdConfig.getString(EXTERNAL_ID_SECTION, externalIdKeyStr, ACCOUNT_ID_KEY);
+    String email = externalIdConfig.getString(EXTERNAL_ID_SECTION, externalIdKeyStr, EMAIL_KEY);
+    String password =
+        externalIdConfig.getString(EXTERNAL_ID_SECTION, externalIdKeyStr, PASSWORD_KEY);
+    if (accountIdStr == null) {
+      throw invalidConfig(
+          noteId,
+          String.format(
+              "Missing value for %s.%s.%s", EXTERNAL_ID_SECTION, externalIdKeyStr, ACCOUNT_ID_KEY));
+    }
+    Integer accountId = Ints.tryParse(accountIdStr);
+    if (accountId == null) {
+      throw invalidConfig(
+          noteId,
+          String.format(
+              "Value %s for %s.%s.%s is invalid, expected account ID",
+              accountIdStr, EXTERNAL_ID_SECTION, externalIdKeyStr, ACCOUNT_ID_KEY));
+    }
+
+    return new AutoValue_ExternalId(externalIdKey, new Account.Id(accountId), email, password);
+  }
+
+  private static ConfigInvalidException invalidConfig(String noteId, String message) {
+    return new ConfigInvalidException(
+        String.format("Invalid external id config for note %s: %s", noteId, message));
+  }
+
+  public static ExternalId from(AccountExternalId externalId) {
+    if (externalId == null) {
+      return null;
+    }
+
+    return new AutoValue_ExternalId(
+        ExternalId.Key.parse(externalId.getExternalId()),
+        externalId.getAccountId(),
+        externalId.getEmailAddress(),
+        externalId.getPassword());
+  }
+
+  public static Set<ExternalId> from(Collection<AccountExternalId> externalIds) {
+    if (externalIds == null) {
+      return ImmutableSet.of();
+    }
+    return externalIds.stream().map(ExternalId::from).collect(toSet());
+  }
+
+  public static Set<AccountExternalId> toAccountExternalIds(Collection<ExternalId> extIds) {
+    return extIds.stream().map(e -> e.asAccountExternalId()).collect(toSet());
+  }
+
+  public abstract Key key();
+
+  public abstract Account.Id accountId();
+
+  public abstract @Nullable String email();
+
+  public abstract @Nullable String password();
+
+  public boolean isScheme(String scheme) {
+    return key().isScheme(scheme);
+  }
+
+  public AccountExternalId asAccountExternalId() {
+    AccountExternalId extId = new AccountExternalId(accountId(), key().asAccountExternalIdKey());
+    extId.setEmailAddress(email());
+    extId.setPassword(password());
+    return extId;
+  }
+
+  /**
+   * Exports this external ID as Git config file text.
+   *
+   * <p>The Git config has exactly one externalId subsection with an accountId and optionally email
+   * and password:
+   *
+   * <pre>
+   * [externalId "username:jdoe"]
+   *   accountId = 1003407
+   *   email = jdoe@example.com
+   *   password = bcrypt:4:LCbmSBDivK/hhGVQMfkDpA==:XcWn0pKYSVU/UJgOvhidkEtmqCp6oKB7
+   * </pre>
+   */
+  @Override
+  public String toString() {
+    Config c = new Config();
+    writeToConfig(c);
+    return c.toText();
+  }
+
+  public void writeToConfig(Config c) {
+    String externalIdKey = key().get();
+    c.setInt(EXTERNAL_ID_SECTION, externalIdKey, ACCOUNT_ID_KEY, accountId().get());
+    if (email() != null) {
+      c.setString(EXTERNAL_ID_SECTION, externalIdKey, EMAIL_KEY, email());
+    }
+    if (password() != null) {
+      c.setString(EXTERNAL_ID_SECTION, externalIdKey, PASSWORD_KEY, password());
+    }
+  }
+}
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/ExternalIds.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/ExternalIds.java
new file mode 100644
index 0000000..c937935
--- /dev/null
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/ExternalIds.java
@@ -0,0 +1,105 @@
+// Copyright (C) 2016 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.server.account;
+
+import static org.eclipse.jgit.lib.Constants.OBJ_BLOB;
+
+import com.google.gerrit.common.Nullable;
+import com.google.gerrit.reviewdb.client.RefNames;
+import com.google.gerrit.server.config.AllUsersName;
+import com.google.gerrit.server.git.GitRepositoryManager;
+import com.google.inject.Inject;
+import com.google.inject.Singleton;
+import java.io.IOException;
+import org.eclipse.jgit.errors.ConfigInvalidException;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.Ref;
+import org.eclipse.jgit.lib.Repository;
+import org.eclipse.jgit.notes.NoteMap;
+import org.eclipse.jgit.revwalk.RevWalk;
+
+/**
+ * Class to read external IDs from NoteDb.
+ *
+ * <p>In NoteDb external IDs are stored in the All-Users repository in a Git Notes branch called
+ * refs/meta/external-ids where the sha1 of the external ID is used as note name. Each note content
+ * is a git config file that contains an external ID. It has exactly one externalId subsection with
+ * an accountId and optionally email and password:
+ *
+ * <pre>
+ * [externalId "username:jdoe"]
+ *   accountId = 1003407
+ *   email = jdoe@example.com
+ *   password = bcrypt:4:LCbmSBDivK/hhGVQMfkDpA==:XcWn0pKYSVU/UJgOvhidkEtmqCp6oKB7
+ * </pre>
+ */
+@Singleton
+public class ExternalIds {
+  public static final int MAX_NOTE_SZ = 1 << 19;
+
+  public static ObjectId readRevision(Repository repo) throws IOException {
+    Ref ref = repo.exactRef(RefNames.REFS_EXTERNAL_IDS);
+    return ref != null ? ref.getObjectId() : ObjectId.zeroId();
+  }
+
+  public static NoteMap readNoteMap(RevWalk rw, ObjectId rev) throws IOException {
+    if (!rev.equals(ObjectId.zeroId())) {
+      return NoteMap.read(rw.getObjectReader(), rw.parseCommit(rev));
+    }
+    return NoteMap.newEmptyMap();
+  }
+
+  private final GitRepositoryManager repoManager;
+  private final AllUsersName allUsersName;
+
+  @Inject
+  public ExternalIds(GitRepositoryManager repoManager, AllUsersName allUsersName) {
+    this.repoManager = repoManager;
+    this.allUsersName = allUsersName;
+  }
+
+  public ObjectId readRevision() throws IOException {
+    try (Repository repo = repoManager.openRepository(allUsersName)) {
+      return readRevision(repo);
+    }
+  }
+
+  /** Reads and returns the specified external ID. */
+  @Nullable
+  public ExternalId get(ExternalId.Key key) throws IOException, ConfigInvalidException {
+    try (Repository repo = repoManager.openRepository(allUsersName);
+        RevWalk rw = new RevWalk(repo)) {
+      ObjectId rev = readRevision(repo);
+      if (rev.equals(ObjectId.zeroId())) {
+        return null;
+      }
+
+      return parse(key, rw, rev);
+    }
+  }
+
+  private ExternalId parse(ExternalId.Key key, RevWalk rw, ObjectId rev)
+      throws IOException, ConfigInvalidException {
+    NoteMap noteMap = readNoteMap(rw, rev);
+    ObjectId noteId = key.sha1();
+    if (!noteMap.contains(noteId)) {
+      return null;
+    }
+
+    byte[] raw =
+        rw.getObjectReader().open(noteMap.get(noteId), OBJ_BLOB).getCachedBytes(MAX_NOTE_SZ);
+    return ExternalId.parse(noteId.name(), raw);
+  }
+}
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/ExternalIdsBatchUpdate.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/ExternalIdsBatchUpdate.java
new file mode 100644
index 0000000..531e562
--- /dev/null
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/ExternalIdsBatchUpdate.java
@@ -0,0 +1,116 @@
+// Copyright (C) 2016 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.server.account;
+
+import static com.google.gerrit.server.account.ExternalId.toAccountExternalIds;
+
+import com.google.common.collect.ImmutableSet;
+import com.google.gerrit.reviewdb.server.ReviewDb;
+import com.google.gerrit.server.GerritPersonIdent;
+import com.google.gerrit.server.config.AllUsersName;
+import com.google.gerrit.server.git.GitRepositoryManager;
+import com.google.gwtorm.server.OrmException;
+import com.google.inject.Inject;
+import java.io.IOException;
+import java.util.HashSet;
+import java.util.Set;
+import org.eclipse.jgit.errors.ConfigInvalidException;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectInserter;
+import org.eclipse.jgit.lib.PersonIdent;
+import org.eclipse.jgit.lib.Repository;
+import org.eclipse.jgit.notes.NoteMap;
+import org.eclipse.jgit.revwalk.RevWalk;
+
+/**
+ * This class allows to do batch updates to external IDs.
+ *
+ * <p>For NoteDb all updates will result in a single commit to the refs/meta/external-ids branch.
+ * This means callers can prepare many updates by invoking {@link #replace(ExternalId, ExternalId)}
+ * multiple times and when {@link ExternalIdsBatchUpdate#commit(ReviewDb, String)} is invoked a
+ * single NoteDb commit is created that contains all the prepared updates.
+ */
+public class ExternalIdsBatchUpdate {
+  private final GitRepositoryManager repoManager;
+  private final AllUsersName allUsersName;
+  private final PersonIdent serverIdent;
+  private final Set<ExternalId> toAdd = new HashSet<>();
+  private final Set<ExternalId> toDelete = new HashSet<>();
+
+  @Inject
+  public ExternalIdsBatchUpdate(
+      GitRepositoryManager repoManager,
+      AllUsersName allUsersName,
+      @GerritPersonIdent PersonIdent serverIdent) {
+    this.repoManager = repoManager;
+    this.allUsersName = allUsersName;
+    this.serverIdent = serverIdent;
+  }
+
+  /**
+   * Adds an external ID replacement to the batch.
+   *
+   * <p>The actual replacement is only done when {@link #commit(ReviewDb, String)} is invoked.
+   */
+  public void replace(ExternalId extIdToDelete, ExternalId extIdToAdd) {
+    ExternalIdsUpdate.checkSameAccount(ImmutableSet.of(extIdToDelete, extIdToAdd));
+    toAdd.add(extIdToAdd);
+    toDelete.add(extIdToDelete);
+  }
+
+  /**
+   * Commits this batch.
+   *
+   * <p>This means external ID replacements which were prepared by invoking {@link
+   * #replace(ExternalId, ExternalId)} are now executed. Deletion of external IDs is done before
+   * adding the new external IDs. This means if an external ID is specified for deletion and an
+   * external ID with the same key is specified to be added, the old external ID with that key is
+   * deleted first and then the new external ID is added (so the external ID for that key is
+   * replaced).
+   *
+   * <p>For NoteDb a single commit is created that contains all the external ID updates.
+   */
+  public void commit(ReviewDb db, String commitMessage)
+      throws IOException, OrmException, ConfigInvalidException {
+    if (toDelete.isEmpty() && toAdd.isEmpty()) {
+      return;
+    }
+
+    db.accountExternalIds().delete(toAccountExternalIds(toDelete));
+    db.accountExternalIds().insert(toAccountExternalIds(toAdd));
+
+    try (Repository repo = repoManager.openRepository(allUsersName);
+        RevWalk rw = new RevWalk(repo);
+        ObjectInserter ins = repo.newObjectInserter()) {
+      ObjectId rev = ExternalIds.readRevision(repo);
+
+      NoteMap noteMap = ExternalIds.readNoteMap(rw, rev);
+
+      for (ExternalId extId : toDelete) {
+        ExternalIdsUpdate.remove(rw, noteMap, extId);
+      }
+
+      for (ExternalId extId : toAdd) {
+        ExternalIdsUpdate.insert(rw, ins, noteMap, extId);
+      }
+
+      ExternalIdsUpdate.commit(
+          repo, rw, ins, rev, noteMap, commitMessage, serverIdent, serverIdent);
+    }
+
+    toAdd.clear();
+    toDelete.clear();
+  }
+}
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/ExternalIdsUpdate.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/ExternalIdsUpdate.java
new file mode 100644
index 0000000..c09dc11
--- /dev/null
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/ExternalIdsUpdate.java
@@ -0,0 +1,636 @@
+// Copyright (C) 2016 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.server.account;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.base.Preconditions.checkState;
+import static com.google.gerrit.server.account.ExternalId.Key.toAccountExternalIdKeys;
+import static com.google.gerrit.server.account.ExternalId.toAccountExternalIds;
+import static com.google.gerrit.server.account.ExternalIds.MAX_NOTE_SZ;
+import static com.google.gerrit.server.account.ExternalIds.readNoteMap;
+import static com.google.gerrit.server.account.ExternalIds.readRevision;
+import static java.nio.charset.StandardCharsets.UTF_8;
+import static java.util.stream.Collectors.toSet;
+import static org.eclipse.jgit.lib.Constants.OBJ_BLOB;
+import static org.eclipse.jgit.lib.Constants.OBJ_TREE;
+
+import com.github.rholder.retry.RetryException;
+import com.github.rholder.retry.Retryer;
+import com.github.rholder.retry.RetryerBuilder;
+import com.github.rholder.retry.StopStrategies;
+import com.github.rholder.retry.WaitStrategies;
+import com.google.auto.value.AutoValue;
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Throwables;
+import com.google.common.collect.Iterables;
+import com.google.common.util.concurrent.Runnables;
+import com.google.gerrit.common.Nullable;
+import com.google.gerrit.reviewdb.client.Account;
+import com.google.gerrit.reviewdb.client.RefNames;
+import com.google.gerrit.reviewdb.server.ReviewDb;
+import com.google.gerrit.server.GerritPersonIdent;
+import com.google.gerrit.server.IdentifiedUser;
+import com.google.gerrit.server.config.AllUsersName;
+import com.google.gerrit.server.git.GitRepositoryManager;
+import com.google.gerrit.server.git.LockFailureException;
+import com.google.gwtorm.server.OrmDuplicateKeyException;
+import com.google.gwtorm.server.OrmException;
+import com.google.inject.Inject;
+import com.google.inject.Provider;
+import com.google.inject.Singleton;
+import java.io.IOException;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.concurrent.Callable;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.TimeUnit;
+import org.eclipse.jgit.errors.ConfigInvalidException;
+import org.eclipse.jgit.lib.CommitBuilder;
+import org.eclipse.jgit.lib.Config;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectInserter;
+import org.eclipse.jgit.lib.PersonIdent;
+import org.eclipse.jgit.lib.RefUpdate;
+import org.eclipse.jgit.lib.Repository;
+import org.eclipse.jgit.notes.NoteMap;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.revwalk.RevWalk;
+
+/**
+ * Updates externalIds in ReviewDb and NoteDb.
+ *
+ * <p>In NoteDb external IDs are stored in the All-Users repository in a Git Notes branch called
+ * refs/meta/external-ids where the sha1 of the external ID is used as note name. Each note content
+ * is a git config file that contains an external ID. It has exactly one externalId subsection with
+ * an accountId and optionally email and password:
+ *
+ * <pre>
+ * [externalId "username:jdoe"]
+ *   accountId = 1003407
+ *   email = jdoe@example.com
+ *   password = bcrypt:4:LCbmSBDivK/hhGVQMfkDpA==:XcWn0pKYSVU/UJgOvhidkEtmqCp6oKB7
+ * </pre>
+ *
+ * For NoteDb each method call results in one commit on refs/meta/external-ids branch.
+ */
+public class ExternalIdsUpdate {
+  private static final String COMMIT_MSG = "Update external IDs";
+
+  /**
+   * Factory to create an ExternalIdsUpdate instance for updating external IDs by the Gerrit server.
+   *
+   * <p>The Gerrit server identity will be used as author and committer for all commits that update
+   * the external IDs.
+   */
+  @Singleton
+  public static class Server {
+    private final GitRepositoryManager repoManager;
+    private final AllUsersName allUsersName;
+    private final Provider<PersonIdent> serverIdent;
+
+    @Inject
+    public Server(
+        GitRepositoryManager repoManager,
+        AllUsersName allUsersName,
+        @GerritPersonIdent Provider<PersonIdent> serverIdent) {
+      this.repoManager = repoManager;
+      this.allUsersName = allUsersName;
+      this.serverIdent = serverIdent;
+    }
+
+    public ExternalIdsUpdate create() {
+      PersonIdent i = serverIdent.get();
+      return new ExternalIdsUpdate(repoManager, allUsersName, i, i);
+    }
+  }
+
+  /**
+   * Factory to create an ExternalIdsUpdate instance for updating external IDs by the current user.
+   *
+   * <p>The identity of the current user will be used as author for all commits that update the
+   * external IDs. The Gerrit server identity will be used as committer.
+   */
+  @Singleton
+  public static class User {
+    private final GitRepositoryManager repoManager;
+    private final AllUsersName allUsersName;
+    private final Provider<PersonIdent> serverIdent;
+    private final Provider<IdentifiedUser> identifiedUser;
+
+    @Inject
+    public User(
+        GitRepositoryManager repoManager,
+        AllUsersName allUsersName,
+        @GerritPersonIdent Provider<PersonIdent> serverIdent,
+        Provider<IdentifiedUser> identifiedUser) {
+      this.repoManager = repoManager;
+      this.allUsersName = allUsersName;
+      this.serverIdent = serverIdent;
+      this.identifiedUser = identifiedUser;
+    }
+
+    public ExternalIdsUpdate create() {
+      PersonIdent i = serverIdent.get();
+      return new ExternalIdsUpdate(
+          repoManager, allUsersName, createPersonIdent(i, identifiedUser.get()), i);
+    }
+
+    private PersonIdent createPersonIdent(PersonIdent ident, IdentifiedUser user) {
+      return user.newCommitterIdent(ident.getWhen(), ident.getTimeZone());
+    }
+  }
+
+  @VisibleForTesting
+  public static RetryerBuilder<Void> retryerBuilder() {
+    return RetryerBuilder.<Void>newBuilder()
+        .retryIfException(e -> e instanceof LockFailureException)
+        .withWaitStrategy(
+            WaitStrategies.join(
+                WaitStrategies.exponentialWait(2, TimeUnit.SECONDS),
+                WaitStrategies.randomWait(50, TimeUnit.MILLISECONDS)))
+        .withStopStrategy(StopStrategies.stopAfterDelay(10, TimeUnit.SECONDS));
+  }
+
+  private static final Retryer<Void> RETRYER = retryerBuilder().build();
+
+  private final GitRepositoryManager repoManager;
+  private final AllUsersName allUsersName;
+  private final PersonIdent committerIdent;
+  private final PersonIdent authorIdent;
+  private final Runnable afterReadRevision;
+  private final Retryer<Void> retryer;
+
+  private ExternalIdsUpdate(
+      GitRepositoryManager repoManager,
+      AllUsersName allUsersName,
+      PersonIdent committerIdent,
+      PersonIdent authorIdent) {
+    this(repoManager, allUsersName, committerIdent, authorIdent, Runnables.doNothing(), RETRYER);
+  }
+
+  @VisibleForTesting
+  public ExternalIdsUpdate(
+      GitRepositoryManager repoManager,
+      AllUsersName allUsersName,
+      PersonIdent committerIdent,
+      PersonIdent authorIdent,
+      Runnable afterReadRevision,
+      Retryer<Void> retryer) {
+    this.repoManager = checkNotNull(repoManager, "repoManager");
+    this.allUsersName = checkNotNull(allUsersName, "allUsersName");
+    this.committerIdent = checkNotNull(committerIdent, "committerIdent");
+    this.authorIdent = checkNotNull(authorIdent, "authorIdent");
+    this.afterReadRevision = checkNotNull(afterReadRevision, "afterReadRevision");
+    this.retryer = checkNotNull(retryer, "retryer");
+  }
+
+  /**
+   * Inserts a new external ID.
+   *
+   * <p>If the external ID already exists, the insert fails with {@link OrmDuplicateKeyException}.
+   */
+  public void insert(ReviewDb db, ExternalId extId)
+      throws IOException, ConfigInvalidException, OrmException {
+    insert(db, Collections.singleton(extId));
+  }
+
+  /**
+   * Inserts new external IDs.
+   *
+   * <p>If any of the external ID already exists, the insert fails with {@link
+   * OrmDuplicateKeyException}.
+   */
+  public void insert(ReviewDb db, Collection<ExternalId> extIds)
+      throws IOException, ConfigInvalidException, OrmException {
+    db.accountExternalIds().insert(toAccountExternalIds(extIds));
+
+    updateNoteMap(
+        o -> {
+          for (ExternalId extId : extIds) {
+            insert(o.rw(), o.ins(), o.noteMap(), extId);
+          }
+        });
+  }
+
+  /**
+   * Inserts or updates an external ID.
+   *
+   * <p>If the external ID already exists, it is overwritten, otherwise it is inserted.
+   */
+  public void upsert(ReviewDb db, ExternalId extId)
+      throws IOException, ConfigInvalidException, OrmException {
+    upsert(db, Collections.singleton(extId));
+  }
+
+  /**
+   * Inserts or updates external IDs.
+   *
+   * <p>If any of the external IDs already exists, it is overwritten. New external IDs are inserted.
+   */
+  public void upsert(ReviewDb db, Collection<ExternalId> extIds)
+      throws IOException, ConfigInvalidException, OrmException {
+    db.accountExternalIds().upsert(toAccountExternalIds(extIds));
+
+    updateNoteMap(
+        o -> {
+          for (ExternalId extId : extIds) {
+            upsert(o.rw(), o.ins(), o.noteMap(), extId);
+          }
+        });
+  }
+
+  /**
+   * Deletes an external ID.
+   *
+   * <p>The deletion fails with {@link IllegalStateException} if there is an existing external ID
+   * that has the same key, but otherwise doesn't match the specified external ID.
+   */
+  public void delete(ReviewDb db, ExternalId extId)
+      throws IOException, ConfigInvalidException, OrmException {
+    delete(db, Collections.singleton(extId));
+  }
+
+  /**
+   * Deletes external IDs.
+   *
+   * <p>The deletion fails with {@link IllegalStateException} if there is an existing external ID
+   * that has the same key as any of the external IDs that should be deleted, but otherwise doesn't
+   * match the that external ID.
+   */
+  public void delete(ReviewDb db, Collection<ExternalId> extIds)
+      throws IOException, ConfigInvalidException, OrmException {
+    db.accountExternalIds().delete(toAccountExternalIds(extIds));
+
+    updateNoteMap(
+        o -> {
+          for (ExternalId extId : extIds) {
+            remove(o.rw(), o.noteMap(), extId);
+          }
+        });
+  }
+
+  /**
+   * Delete an external ID by key.
+   *
+   * <p>The external ID is only deleted if it belongs to the specified account. If it belongs to
+   * another account the deletion fails with {@link IllegalStateException}.
+   */
+  public void delete(ReviewDb db, Account.Id accountId, ExternalId.Key extIdKey)
+      throws IOException, ConfigInvalidException, OrmException {
+    delete(db, accountId, Collections.singleton(extIdKey));
+  }
+
+  /**
+   * Delete external IDs by external ID key.
+   *
+   * <p>The external IDs are only deleted if they belongs to the specified account. If any of the
+   * external IDs belongs to another account the deletion fails with {@link IllegalStateException}.
+   */
+  public void delete(ReviewDb db, Account.Id accountId, Collection<ExternalId.Key> extIdKeys)
+      throws IOException, ConfigInvalidException, OrmException {
+    db.accountExternalIds().deleteKeys(toAccountExternalIdKeys(extIdKeys));
+
+    updateNoteMap(
+        o -> {
+          for (ExternalId.Key extIdKey : extIdKeys) {
+            remove(o.rw(), o.noteMap(), accountId, extIdKey);
+          }
+        });
+  }
+
+  /** Deletes all external IDs of the specified account. */
+  public void deleteAll(ReviewDb db, Account.Id accountId)
+      throws IOException, ConfigInvalidException, OrmException {
+    delete(db, ExternalId.from(db.accountExternalIds().byAccount(accountId).toList()));
+  }
+
+  /**
+   * Replaces external IDs for an account by external ID keys.
+   *
+   * <p>Deletion of external IDs is done before adding the new external IDs. This means if an
+   * external ID key is specified for deletion and an external ID with the same key is specified to
+   * be added, the old external ID with that key is deleted first and then the new external ID is
+   * added (so the external ID for that key is replaced).
+   *
+   * <p>If any of the specified external IDs belongs to another account the replacement fails with
+   * {@link IllegalStateException}.
+   */
+  public void replace(
+      ReviewDb db,
+      Account.Id accountId,
+      Collection<ExternalId.Key> toDelete,
+      Collection<ExternalId> toAdd)
+      throws IOException, ConfigInvalidException, OrmException {
+    checkSameAccount(toAdd, accountId);
+
+    db.accountExternalIds().deleteKeys(toAccountExternalIdKeys(toDelete));
+    db.accountExternalIds().insert(toAccountExternalIds(toAdd));
+
+    updateNoteMap(
+        o -> {
+          for (ExternalId.Key extIdKey : toDelete) {
+            remove(o.rw(), o.noteMap(), accountId, extIdKey);
+          }
+
+          for (ExternalId extId : toAdd) {
+            insert(o.rw(), o.ins(), o.noteMap(), extId);
+          }
+        });
+  }
+
+  /**
+   * Replaces an external ID.
+   *
+   * <p>If the specified external IDs belongs to different accounts the replacement fails with
+   * {@link IllegalStateException}.
+   */
+  public void replace(ReviewDb db, ExternalId toDelete, ExternalId toAdd)
+      throws IOException, ConfigInvalidException, OrmException {
+    replace(db, Collections.singleton(toDelete), Collections.singleton(toAdd));
+  }
+
+  /**
+   * Replaces external IDs.
+   *
+   * <p>Deletion of external IDs is done before adding the new external IDs. This means if an
+   * external ID is specified for deletion and an external ID with the same key is specified to be
+   * added, the old external ID with that key is deleted first and then the new external ID is added
+   * (so the external ID for that key is replaced).
+   *
+   * <p>If the specified external IDs belong to different accounts the replacement fails with {@link
+   * IllegalStateException}.
+   */
+  public void replace(ReviewDb db, Collection<ExternalId> toDelete, Collection<ExternalId> toAdd)
+      throws IOException, ConfigInvalidException, OrmException {
+    Account.Id accountId = checkSameAccount(Iterables.concat(toDelete, toAdd));
+    if (accountId == null) {
+      // toDelete and toAdd are empty -> nothing to do
+      return;
+    }
+
+    replace(db, accountId, toDelete.stream().map(e -> e.key()).collect(toSet()), toAdd);
+  }
+
+  /**
+   * Checks that all specified external IDs belong to the same account.
+   *
+   * @return the ID of the account to which all specified external IDs belong.
+   */
+  public static Account.Id checkSameAccount(Iterable<ExternalId> extIds) {
+    return checkSameAccount(extIds, null);
+  }
+
+  /**
+   * Checks that all specified external IDs belong to specified account. If no account is specified
+   * it is checked that all specified external IDs belong to the same account.
+   *
+   * @return the ID of the account to which all specified external IDs belong.
+   */
+  public static Account.Id checkSameAccount(
+      Iterable<ExternalId> extIds, @Nullable Account.Id accountId) {
+    for (ExternalId extId : extIds) {
+      if (accountId == null) {
+        accountId = extId.accountId();
+        continue;
+      }
+      checkState(
+          accountId.equals(extId.accountId()),
+          "external id %s belongs to account %s, expected account %s",
+          extId.key().get(),
+          extId.accountId().get(),
+          accountId.get());
+    }
+    return accountId;
+  }
+
+  /**
+   * Inserts a new external ID and sets it in the note map.
+   *
+   * <p>If the external ID already exists, the insert fails with {@link OrmDuplicateKeyException}.
+   */
+  public static void insert(RevWalk rw, ObjectInserter ins, NoteMap noteMap, ExternalId extId)
+      throws OrmDuplicateKeyException, ConfigInvalidException, IOException {
+    if (noteMap.contains(extId.key().sha1())) {
+      throw new OrmDuplicateKeyException(
+          String.format("external id %s already exists", extId.key().get()));
+    }
+    upsert(rw, ins, noteMap, extId);
+  }
+
+  /**
+   * Insert or updates an new external ID and sets it in the note map.
+   *
+   * <p>If the external ID already exists it is overwritten.
+   */
+  private static void upsert(RevWalk rw, ObjectInserter ins, NoteMap noteMap, ExternalId extId)
+      throws IOException, ConfigInvalidException {
+    ObjectId noteId = extId.key().sha1();
+    Config c = new Config();
+    if (noteMap.contains(extId.key().sha1())) {
+      byte[] raw =
+          rw.getObjectReader().open(noteMap.get(noteId), OBJ_BLOB).getCachedBytes(MAX_NOTE_SZ);
+      try {
+        c.fromText(new String(raw, UTF_8));
+      } catch (ConfigInvalidException e) {
+        throw new ConfigInvalidException(
+            String.format("Invalid external id config for note %s: %s", noteId, e.getMessage()));
+      }
+    }
+    extId.writeToConfig(c);
+    byte[] raw = c.toText().getBytes(UTF_8);
+    ObjectId dataBlob = ins.insert(OBJ_BLOB, raw);
+    noteMap.set(noteId, dataBlob);
+  }
+
+  /**
+   * Removes an external ID from the note map.
+   *
+   * <p>The removal fails with {@link IllegalStateException} if there is an existing external ID
+   * that has the same key, but otherwise doesn't match the specified external ID.
+   */
+  public static void remove(RevWalk rw, NoteMap noteMap, ExternalId extId)
+      throws IOException, ConfigInvalidException {
+    ObjectId noteId = extId.key().sha1();
+    if (!noteMap.contains(noteId)) {
+      return;
+    }
+
+    byte[] raw =
+        rw.getObjectReader().open(noteMap.get(noteId), OBJ_BLOB).getCachedBytes(MAX_NOTE_SZ);
+    ExternalId actualExtId = ExternalId.parse(noteId.name(), raw);
+    checkState(
+        extId.equals(actualExtId),
+        "external id %s should be removed, but it's not matching the actual external id %s",
+        extId.toString(),
+        actualExtId.toString());
+    noteMap.remove(noteId);
+  }
+
+  /**
+   * Removes an external ID from the note map by external ID key.
+   *
+   * <p>The external ID is only deleted if it belongs to the specified account. If the external IDs
+   * belongs to another account the deletion fails with {@link IllegalStateException}.
+   */
+  private static void remove(
+      RevWalk rw, NoteMap noteMap, Account.Id accountId, ExternalId.Key extIdKey)
+      throws IOException, ConfigInvalidException {
+    ObjectId noteId = extIdKey.sha1();
+    if (!noteMap.contains(noteId)) {
+      return;
+    }
+
+    byte[] raw =
+        rw.getObjectReader().open(noteMap.get(noteId), OBJ_BLOB).getCachedBytes(MAX_NOTE_SZ);
+    ExternalId extId = ExternalId.parse(noteId.name(), raw);
+    checkState(
+        accountId.equals(extId.accountId()),
+        "external id %s should be removed for account %s,"
+            + " but external id belongs to account %s",
+        extIdKey.get(),
+        accountId.get(),
+        extId.accountId().get());
+    noteMap.remove(noteId);
+  }
+
+  private void updateNoteMap(MyConsumer<OpenRepo> update)
+      throws IOException, ConfigInvalidException, OrmException {
+    try (Repository repo = repoManager.openRepository(allUsersName);
+        RevWalk rw = new RevWalk(repo);
+        ObjectInserter ins = repo.newObjectInserter()) {
+      retryer.call(new TryNoteMapUpdate(repo, rw, ins, update));
+    } catch (ExecutionException | RetryException e) {
+      if (e.getCause() != null) {
+        Throwables.throwIfInstanceOf(e.getCause(), IOException.class);
+        Throwables.throwIfInstanceOf(e.getCause(), ConfigInvalidException.class);
+        Throwables.throwIfInstanceOf(e.getCause(), OrmException.class);
+      }
+      throw new OrmException(e);
+    }
+  }
+
+  private void commit(
+      Repository repo, RevWalk rw, ObjectInserter ins, ObjectId rev, NoteMap noteMap)
+      throws IOException {
+    commit(repo, rw, ins, rev, noteMap, COMMIT_MSG, committerIdent, authorIdent);
+  }
+
+  /** Commits updates to the external IDs. */
+  public static void commit(
+      Repository repo,
+      RevWalk rw,
+      ObjectInserter ins,
+      ObjectId rev,
+      NoteMap noteMap,
+      String commitMessage,
+      PersonIdent committerIdent,
+      PersonIdent authorIdent)
+      throws IOException {
+    CommitBuilder cb = new CommitBuilder();
+    cb.setMessage(commitMessage);
+    cb.setTreeId(noteMap.writeTree(ins));
+    cb.setAuthor(authorIdent);
+    cb.setCommitter(committerIdent);
+    if (!rev.equals(ObjectId.zeroId())) {
+      cb.setParentId(rev);
+    } else {
+      cb.setParentIds(); // Ref is currently nonexistent, commit has no parents.
+    }
+    if (cb.getTreeId() == null) {
+      if (rev.equals(ObjectId.zeroId())) {
+        cb.setTreeId(emptyTree(ins)); // No parent, assume empty tree.
+      } else {
+        RevCommit p = rw.parseCommit(rev);
+        cb.setTreeId(p.getTree()); // Copy tree from parent.
+      }
+    }
+    ObjectId commitId = ins.insert(cb);
+    ins.flush();
+
+    RefUpdate u = repo.updateRef(RefNames.REFS_EXTERNAL_IDS);
+    u.setRefLogIdent(committerIdent);
+    u.setRefLogMessage("Update external IDs", false);
+    u.setExpectedOldObjectId(rev);
+    u.setNewObjectId(commitId);
+    RefUpdate.Result res = u.update();
+    switch (res) {
+      case NEW:
+      case FAST_FORWARD:
+      case NO_CHANGE:
+      case RENAMED:
+      case FORCED:
+        break;
+      case LOCK_FAILURE:
+        throw new LockFailureException("Updating external IDs failed with " + res);
+      case IO_FAILURE:
+      case NOT_ATTEMPTED:
+      case REJECTED:
+      case REJECTED_CURRENT_BRANCH:
+      default:
+        throw new IOException("Updating external IDs failed with " + res);
+    }
+  }
+
+  private static ObjectId emptyTree(ObjectInserter ins) throws IOException {
+    return ins.insert(OBJ_TREE, new byte[] {});
+  }
+
+  private static interface MyConsumer<T> {
+    void accept(T t) throws IOException, ConfigInvalidException, OrmException;
+  }
+
+  @AutoValue
+  abstract static class OpenRepo {
+    static OpenRepo create(Repository repo, RevWalk rw, ObjectInserter ins, NoteMap noteMap) {
+      return new AutoValue_ExternalIdsUpdate_OpenRepo(repo, rw, ins, noteMap);
+    }
+
+    abstract Repository repo();
+
+    abstract RevWalk rw();
+
+    abstract ObjectInserter ins();
+
+    abstract NoteMap noteMap();
+  }
+
+  private class TryNoteMapUpdate implements Callable<Void> {
+    private final Repository repo;
+    private final RevWalk rw;
+    private final ObjectInserter ins;
+    private final MyConsumer<OpenRepo> update;
+
+    private TryNoteMapUpdate(
+        Repository repo, RevWalk rw, ObjectInserter ins, MyConsumer<OpenRepo> update) {
+      this.repo = repo;
+      this.rw = rw;
+      this.ins = ins;
+      this.update = update;
+    }
+
+    @Override
+    public Void call() throws Exception {
+      ObjectId rev = readRevision(repo);
+
+      afterReadRevision.run();
+
+      NoteMap noteMap = readNoteMap(rw, rev);
+      update.accept(OpenRepo.create(repo, rw, ins, noteMap));
+
+      commit(repo, rw, ins, rev, noteMap);
+      return null;
+    }
+  }
+}
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/GetExternalIds.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/GetExternalIds.java
index e215c9b..6ea911f 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/GetExternalIds.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/GetExternalIds.java
@@ -14,7 +14,7 @@
 
 package com.google.gerrit.server.account;
 
-import static com.google.gerrit.reviewdb.client.AccountExternalId.SCHEME_USERNAME;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_USERNAME;
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Lists;
@@ -22,7 +22,6 @@
 import com.google.gerrit.extensions.restapi.AuthException;
 import com.google.gerrit.extensions.restapi.RestApiException;
 import com.google.gerrit.extensions.restapi.RestReadView;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.CurrentUser;
 import com.google.gerrit.server.config.AuthConfig;
@@ -54,22 +53,23 @@
       throw new AuthException("not allowed to get external IDs");
     }
 
-    Collection<AccountExternalId> ids =
-        db.get().accountExternalIds().byAccount(resource.getUser().getAccountId()).toList();
+    Collection<ExternalId> ids =
+        ExternalId.from(
+            db.get().accountExternalIds().byAccount(resource.getUser().getAccountId()).toList());
     if (ids.isEmpty()) {
       return ImmutableList.of();
     }
     List<AccountExternalIdInfo> result = Lists.newArrayListWithCapacity(ids.size());
-    for (AccountExternalId id : ids) {
+    for (ExternalId id : ids) {
       AccountExternalIdInfo info = new AccountExternalIdInfo();
-      info.identity = id.getExternalId();
-      info.emailAddress = id.getEmailAddress();
+      info.identity = id.key().get();
+      info.emailAddress = id.email();
       info.trusted = toBoolean(authConfig.isIdentityTrustable(Collections.singleton(id)));
       // The identity can be deleted only if its not the one used to
       // establish this web session, and if only if an identity was
       // actually used to establish this web session.
       if (!id.isScheme(SCHEME_USERNAME)) {
-        AccountExternalId.Key last = resource.getUser().getLastLoginExternalIdKey();
+        ExternalId.Key last = resource.getUser().getLastLoginExternalIdKey();
         info.canDelete = toBoolean(last == null || !last.get().equals(info.identity));
       }
       result.add(info);
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/GetHttpPassword.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/GetHttpPassword.java
deleted file mode 100644
index 135cdf6..0000000
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/GetHttpPassword.java
+++ /dev/null
@@ -1,50 +0,0 @@
-// Copyright (C) 2013 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-package com.google.gerrit.server.account;
-
-import com.google.gerrit.extensions.restapi.AuthException;
-import com.google.gerrit.extensions.restapi.ResourceNotFoundException;
-import com.google.gerrit.extensions.restapi.RestReadView;
-import com.google.gerrit.server.CurrentUser;
-import com.google.inject.Inject;
-import com.google.inject.Provider;
-import com.google.inject.Singleton;
-
-@Singleton
-public class GetHttpPassword implements RestReadView<AccountResource> {
-
-  private final Provider<CurrentUser> self;
-
-  @Inject
-  GetHttpPassword(Provider<CurrentUser> self) {
-    this.self = self;
-  }
-
-  @Override
-  public String apply(AccountResource rsrc) throws AuthException, ResourceNotFoundException {
-    if (self.get() != rsrc.getUser() && !self.get().getCapabilities().canAdministrateServer()) {
-      throw new AuthException("not allowed to get http password");
-    }
-    AccountState s = rsrc.getUser().state();
-    if (s.getUserName() == null) {
-      throw new ResourceNotFoundException();
-    }
-    String p = s.getPassword(s.getUserName());
-    if (p == null) {
-      throw new ResourceNotFoundException();
-    }
-    return p;
-  }
-}
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/HashedPassword.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/HashedPassword.java
new file mode 100644
index 0000000..0323f4e
--- /dev/null
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/HashedPassword.java
@@ -0,0 +1,116 @@
+// Copyright (C) 2017 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.server.account;
+
+import com.google.common.base.Preconditions;
+import com.google.common.io.BaseEncoding;
+import com.google.common.primitives.Ints;
+import java.nio.charset.StandardCharsets;
+import java.security.SecureRandom;
+import org.apache.commons.codec.DecoderException;
+import org.bouncycastle.crypto.generators.BCrypt;
+import org.bouncycastle.util.Arrays;
+
+/**
+ * Holds logic for salted, hashed passwords. It uses BCrypt from BouncyCastle, which truncates
+ * passwords at 72 bytes.
+ */
+public class HashedPassword {
+  private static final String ALGORITHM_PREFIX = "bcrypt:";
+  private static final SecureRandom secureRandom = new SecureRandom();
+  private static final BaseEncoding codec = BaseEncoding.base64();
+
+  // bcrypt uses 2^cost rounds. Since we use a generated random password, no need
+  // for a high cost.
+  private static final int DEFAULT_COST = 4;
+
+  /**
+   * decodes a hashed password encoded with {@link #encode}.
+   *
+   * @throws DecoderException if input is malformed.
+   */
+  public static HashedPassword decode(String encoded) throws DecoderException {
+    if (!encoded.startsWith(ALGORITHM_PREFIX)) {
+      throw new DecoderException("unrecognized algorithm");
+    }
+
+    String[] fields = encoded.split(":");
+    if (fields.length != 4) {
+      throw new DecoderException("want 4 fields");
+    }
+
+    Integer cost = Ints.tryParse(fields[1]);
+    if (cost == null) {
+      throw new DecoderException("cost parse failed");
+    }
+
+    if (!(cost >= 4 && cost < 32)) {
+      throw new DecoderException("cost should be 4..31 inclusive, got " + cost);
+    }
+
+    byte[] salt = codec.decode(fields[2]);
+    if (salt.length != 16) {
+      throw new DecoderException("salt should be 16 bytes, got " + salt.length);
+    }
+    return new HashedPassword(codec.decode(fields[3]), salt, cost);
+  }
+
+  private static byte[] hashPassword(String password, byte[] salt, int cost) {
+    byte[] pwBytes = password.getBytes(StandardCharsets.UTF_8);
+
+    return BCrypt.generate(pwBytes, salt, cost);
+  }
+
+  public static HashedPassword fromPassword(String password) {
+    byte[] salt = newSalt();
+
+    return new HashedPassword(hashPassword(password, salt, DEFAULT_COST), salt, DEFAULT_COST);
+  }
+
+  private static byte[] newSalt() {
+    byte[] bytes = new byte[16];
+    secureRandom.nextBytes(bytes);
+    return bytes;
+  }
+
+  private byte[] salt;
+  private byte[] hashed;
+  private int cost;
+
+  private HashedPassword(byte[] hashed, byte[] salt, int cost) {
+    this.salt = salt;
+    this.hashed = hashed;
+    this.cost = cost;
+
+    Preconditions.checkState(cost >= 4 && cost < 32);
+
+    // salt must be 128 bit.
+    Preconditions.checkState(salt.length == 16);
+  }
+
+  /**
+   * Serialize the hashed password and its parameters for persistent storage.
+   *
+   * @return one-line string encoding the hash and salt.
+   */
+  public String encode() {
+    return ALGORITHM_PREFIX + cost + ":" + codec.encode(salt) + ":" + codec.encode(hashed);
+  }
+
+  public boolean checkPassword(String password) {
+    // Constant-time comparison, because we're paranoid.
+    return Arrays.areEqual(hashPassword(password, salt, cost), hashed);
+  }
+}
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/InternalAccountDirectory.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/InternalAccountDirectory.java
index 88eb8fa..7791a2e 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/InternalAccountDirectory.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/InternalAccountDirectory.java
@@ -20,7 +20,6 @@
 import com.google.gerrit.extensions.common.AvatarInfo;
 import com.google.gerrit.extensions.registration.DynamicItem;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.server.IdentifiedUser;
 import com.google.gerrit.server.avatar.AvatarProvider;
 import com.google.inject.AbstractModule;
@@ -74,7 +73,7 @@
   private void fill(
       AccountInfo info,
       Account account,
-      @Nullable Collection<AccountExternalId> externalIds,
+      @Nullable Collection<ExternalId> externalIds,
       Set<FillOptions> options) {
     if (options.contains(FillOptions.ID)) {
       info._accountId = account.getId().get();
@@ -124,8 +123,7 @@
     }
   }
 
-  public List<String> getSecondaryEmails(
-      Account account, Collection<AccountExternalId> externalIds) {
+  public List<String> getSecondaryEmails(Account account, Collection<ExternalId> externalIds) {
     List<String> emails = new ArrayList<>(AccountState.getEmails(externalIds));
     if (account.getPreferredEmail() != null) {
       emails.remove(account.getPreferredEmail());
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/Module.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/Module.java
index 0080e34..775ce6d 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/Module.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/Module.java
@@ -56,7 +56,6 @@
     put(EMAIL_KIND).to(PutEmail.class);
     delete(EMAIL_KIND).to(DeleteEmail.class);
     put(EMAIL_KIND, "preferred").to(PutPreferred.class);
-    get(ACCOUNT_KIND, "password.http").to(GetHttpPassword.class);
     put(ACCOUNT_KIND, "password.http").to(PutHttpPassword.class);
     delete(ACCOUNT_KIND, "password.http").to(PutHttpPassword.class);
     child(ACCOUNT_KIND, "sshkeys").to(SshKeys.class);
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/PutHttpPassword.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/PutHttpPassword.java
index 311c12b..435671f 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/PutHttpPassword.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/PutHttpPassword.java
@@ -14,7 +14,7 @@
 
 package com.google.gerrit.server.account;
 
-import static com.google.gerrit.reviewdb.client.AccountExternalId.SCHEME_USERNAME;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_USERNAME;
 
 import com.google.common.base.Strings;
 import com.google.gerrit.extensions.restapi.AuthException;
@@ -22,7 +22,6 @@
 import com.google.gerrit.extensions.restapi.ResourceNotFoundException;
 import com.google.gerrit.extensions.restapi.Response;
 import com.google.gerrit.extensions.restapi.RestModifyView;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.CurrentUser;
 import com.google.gerrit.server.IdentifiedUser;
@@ -30,14 +29,12 @@
 import com.google.gwtorm.server.OrmException;
 import com.google.inject.Inject;
 import com.google.inject.Provider;
-import com.google.inject.Singleton;
 import java.io.IOException;
 import java.security.NoSuchAlgorithmException;
 import java.security.SecureRandom;
-import java.util.Collections;
 import org.apache.commons.codec.binary.Base64;
+import org.eclipse.jgit.errors.ConfigInvalidException;
 
-@Singleton
 public class PutHttpPassword implements RestModifyView<AccountResource, Input> {
   public static class Input {
     public String httpPassword;
@@ -58,19 +55,24 @@
   private final Provider<CurrentUser> self;
   private final Provider<ReviewDb> dbProvider;
   private final AccountCache accountCache;
+  private final ExternalIdsUpdate.User externalIdsUpdate;
 
   @Inject
   PutHttpPassword(
-      Provider<CurrentUser> self, Provider<ReviewDb> dbProvider, AccountCache accountCache) {
+      Provider<CurrentUser> self,
+      Provider<ReviewDb> dbProvider,
+      AccountCache accountCache,
+      ExternalIdsUpdate.User externalIdsUpdate) {
     this.self = self;
     this.dbProvider = dbProvider;
     this.accountCache = accountCache;
+    this.externalIdsUpdate = externalIdsUpdate;
   }
 
   @Override
   public Response<String> apply(AccountResource rsrc, Input input)
       throws AuthException, ResourceNotFoundException, ResourceConflictException, OrmException,
-          IOException {
+          IOException, ConfigInvalidException {
     if (input == null) {
       input = new Input();
     }
@@ -100,21 +102,26 @@
   }
 
   public Response<String> apply(IdentifiedUser user, String newPassword)
-      throws ResourceNotFoundException, ResourceConflictException, OrmException, IOException {
+      throws ResourceNotFoundException, ResourceConflictException, OrmException, IOException,
+          ConfigInvalidException {
     if (user.getUserName() == null) {
       throw new ResourceConflictException("username must be set");
     }
 
-    AccountExternalId id =
-        dbProvider
-            .get()
-            .accountExternalIds()
-            .get(new AccountExternalId.Key(SCHEME_USERNAME, user.getUserName()));
-    if (id == null) {
+    ExternalId extId =
+        ExternalId.from(
+            dbProvider
+                .get()
+                .accountExternalIds()
+                .get(
+                    ExternalId.Key.create(SCHEME_USERNAME, user.getUserName())
+                        .asAccountExternalIdKey()));
+    if (extId == null) {
       throw new ResourceNotFoundException();
     }
-    id.setPassword(newPassword);
-    dbProvider.get().accountExternalIds().update(Collections.singleton(id));
+    ExternalId newExtId =
+        ExternalId.createWithPassword(extId.key(), extId.accountId(), extId.email(), newPassword);
+    externalIdsUpdate.create().upsert(dbProvider.get(), newExtId);
     accountCache.evict(user.getAccountId());
 
     return Strings.isNullOrEmpty(newPassword) ? Response.<String>none() : Response.ok(newPassword);
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/PutUsername.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/PutUsername.java
index 9be57d9..e3a3c12 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/PutUsername.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/PutUsername.java
@@ -30,6 +30,7 @@
 import com.google.inject.Provider;
 import com.google.inject.Singleton;
 import java.io.IOException;
+import org.eclipse.jgit.errors.ConfigInvalidException;
 
 @Singleton
 public class PutUsername implements RestModifyView<AccountResource, Input> {
@@ -57,7 +58,7 @@
   @Override
   public String apply(AccountResource rsrc, Input input)
       throws AuthException, MethodNotAllowedException, UnprocessableEntityException,
-          ResourceConflictException, OrmException, IOException {
+          ResourceConflictException, OrmException, IOException, ConfigInvalidException {
     if (self.get() != rsrc.getUser() && !self.get().getCapabilities().canAdministrateServer()) {
       throw new AuthException("not allowed to set username");
     }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/api/accounts/AccountApiImpl.java b/gerrit-server/src/main/java/com/google/gerrit/server/api/accounts/AccountApiImpl.java
index 7b8637c..430b6b7 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/api/accounts/AccountApiImpl.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/api/accounts/AccountApiImpl.java
@@ -372,7 +372,7 @@
     AccountResource.Email rsrc = new AccountResource.Email(account.getUser(), input.email);
     try {
       createEmailFactory.create(input.email).apply(rsrc, input);
-    } catch (EmailException | OrmException | IOException e) {
+    } catch (EmailException | OrmException | IOException | ConfigInvalidException e) {
       throw new RestApiException("Cannot add email", e);
     }
   }
@@ -382,7 +382,7 @@
     AccountResource.Email rsrc = new AccountResource.Email(account.getUser(), email);
     try {
       deleteEmail.apply(rsrc, null);
-    } catch (OrmException | IOException e) {
+    } catch (OrmException | IOException | ConfigInvalidException e) {
       throw new RestApiException("Cannot delete email", e);
     }
   }
@@ -494,7 +494,7 @@
   public void deleteExternalIds(List<String> externalIds) throws RestApiException {
     try {
       deleteExternalIds.apply(account, externalIds);
-    } catch (IOException | OrmException e) {
+    } catch (IOException | OrmException | ConfigInvalidException e) {
       throw new RestApiException("Cannot delete external IDs", e);
     }
   }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/api/accounts/AccountExternalIdCreator.java b/gerrit-server/src/main/java/com/google/gerrit/server/api/accounts/AccountExternalIdCreator.java
index 8be7c4d..2d90853 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/api/accounts/AccountExternalIdCreator.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/api/accounts/AccountExternalIdCreator.java
@@ -15,7 +15,7 @@
 package com.google.gerrit.server.api.accounts;
 
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
+import com.google.gerrit.server.account.ExternalId;
 import java.util.List;
 
 public interface AccountExternalIdCreator {
@@ -28,5 +28,5 @@
    * @param email an optional email address to assign to the external identifiers, or {@code null}.
    * @return a list of external identifiers, or an empty list.
    */
-  List<AccountExternalId> create(Account.Id id, String username, String email);
+  List<ExternalId> create(Account.Id id, String username, String email);
 }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/auth/AuthRequest.java b/gerrit-server/src/main/java/com/google/gerrit/server/auth/AuthRequest.java
index c933190..71c5d26 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/auth/AuthRequest.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/auth/AuthRequest.java
@@ -15,7 +15,6 @@
 package com.google.gerrit.server.auth;
 
 import com.google.gerrit.common.Nullable;
-import java.util.Objects;
 
 /** Defines an abstract request for user authentication to Gerrit. */
 public abstract class AuthRequest {
@@ -46,10 +45,4 @@
   public final String getPassword() {
     return password;
   }
-
-  public void checkPassword(String pwd) throws AuthException {
-    if (!Objects.equals(getPassword(), pwd)) {
-      throw new InvalidCredentialsException();
-    }
-  }
 }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/auth/InternalAuthBackend.java b/gerrit-server/src/main/java/com/google/gerrit/server/auth/InternalAuthBackend.java
index 3f2938f..508bf31 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/auth/InternalAuthBackend.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/auth/InternalAuthBackend.java
@@ -38,6 +38,7 @@
     return "gerrit";
   }
 
+  // TODO(gerritcodereview-team): This function has no coverage.
   @Override
   public AuthUser authenticate(AuthRequest req)
       throws MissingCredentialsException, InvalidCredentialsException, UnknownUserException,
@@ -63,7 +64,9 @@
               + ": account inactive or not provisioned in Gerrit");
     }
 
-    req.checkPassword(who.getPassword(username));
+    if (!who.checkPassword(req.getPassword(), username)) {
+      throw new InvalidCredentialsException();
+    }
     return new AuthUser(AuthUser.UUID.create(username), username);
   }
 }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/auth/ldap/LdapGroupBackend.java b/gerrit-server/src/main/java/com/google/gerrit/server/auth/ldap/LdapGroupBackend.java
index 8511318..7feb745 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/auth/ldap/LdapGroupBackend.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/auth/ldap/LdapGroupBackend.java
@@ -14,6 +14,7 @@
 
 package com.google.gerrit.server.auth.ldap;
 
+import static com.google.gerrit.server.account.ExternalId.SCHEME_GERRIT;
 import static com.google.gerrit.server.account.GroupBackends.GROUP_REF_NAME_COMPARATOR;
 import static com.google.gerrit.server.auth.ldap.Helper.LDAP_UUID;
 import static com.google.gerrit.server.auth.ldap.LdapModule.GROUP_CACHE;
@@ -25,10 +26,10 @@
 import com.google.gerrit.common.data.GroupDescription;
 import com.google.gerrit.common.data.GroupReference;
 import com.google.gerrit.common.data.ParameterizedString;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.client.AccountGroup;
 import com.google.gerrit.server.CurrentUser;
 import com.google.gerrit.server.IdentifiedUser;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gerrit.server.account.GroupBackend;
 import com.google.gerrit.server.account.GroupMembership;
 import com.google.gerrit.server.auth.ldap.Helper.LdapSchema;
@@ -180,10 +181,10 @@
     return new LdapGroupMembership(membershipCache, projectCache, id);
   }
 
-  private static String findId(final Collection<AccountExternalId> ids) {
-    for (final AccountExternalId i : ids) {
-      if (i.isScheme(AccountExternalId.SCHEME_GERRIT)) {
-        return i.getSchemeRest();
+  private static String findId(Collection<ExternalId> extIds) {
+    for (ExternalId extId : extIds) {
+      if (extId.isScheme(SCHEME_GERRIT)) {
+        return extId.key().id();
       }
     }
     return null;
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/auth/ldap/LdapRealm.java b/gerrit-server/src/main/java/com/google/gerrit/server/auth/ldap/LdapRealm.java
index 0e05330..66b279f 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/auth/ldap/LdapRealm.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/auth/ldap/LdapRealm.java
@@ -14,7 +14,7 @@
 
 package com.google.gerrit.server.auth.ldap;
 
-import static com.google.gerrit.reviewdb.client.AccountExternalId.SCHEME_GERRIT;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_GERRIT;
 
 import com.google.common.base.Strings;
 import com.google.common.cache.CacheLoader;
@@ -24,13 +24,13 @@
 import com.google.gerrit.extensions.client.AccountFieldName;
 import com.google.gerrit.extensions.client.AuthType;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.client.AccountGroup;
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.account.AbstractRealm;
 import com.google.gerrit.server.account.AccountException;
 import com.google.gerrit.server.account.AuthRequest;
 import com.google.gerrit.server.account.EmailExpander;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gerrit.server.account.GroupBackends;
 import com.google.gerrit.server.auth.AuthenticationUnavailableException;
 import com.google.gerrit.server.config.AuthConfig;
@@ -329,8 +329,12 @@
     public Optional<Account.Id> load(String username) throws Exception {
       try (ReviewDb db = schema.open()) {
         return Optional.ofNullable(
-                db.accountExternalIds().get(new AccountExternalId.Key(SCHEME_GERRIT, username)))
-            .map(AccountExternalId::getAccountId);
+                ExternalId.from(
+                    db.accountExternalIds()
+                        .get(
+                            ExternalId.Key.create(SCHEME_GERRIT, username)
+                                .asAccountExternalIdKey())))
+            .map(ExternalId::accountId);
       }
     }
   }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/auth/openid/OpenIdProviderPattern.java b/gerrit-server/src/main/java/com/google/gerrit/server/auth/openid/OpenIdProviderPattern.java
index 4350037..d30e667 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/auth/openid/OpenIdProviderPattern.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/auth/openid/OpenIdProviderPattern.java
@@ -14,7 +14,7 @@
 
 package com.google.gerrit.server.auth.openid;
 
-import com.google.gerrit.reviewdb.client.AccountExternalId;
+import com.google.gerrit.server.account.ExternalId;
 
 public class OpenIdProviderPattern {
   public static OpenIdProviderPattern create(String pattern) {
@@ -33,8 +33,8 @@
     return regex ? id.matches(pattern) : id.startsWith(pattern);
   }
 
-  public boolean matches(AccountExternalId id) {
-    return matches(id.getExternalId());
+  public boolean matches(ExternalId extId) {
+    return matches(extId.key().get());
   }
 
   @Override
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/config/AuthConfig.java b/gerrit-server/src/main/java/com/google/gerrit/server/config/AuthConfig.java
index db7d567..cc9133e 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/config/AuthConfig.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/config/AuthConfig.java
@@ -14,9 +14,13 @@
 
 package com.google.gerrit.server.config;
 
+import static com.google.gerrit.server.account.ExternalId.SCHEME_MAILTO;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_USERNAME;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_UUID;
+
 import com.google.gerrit.extensions.client.AuthType;
 import com.google.gerrit.extensions.client.GitBasicAuthPolicy;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gerrit.server.auth.openid.OpenIdProviderPattern;
 import com.google.gwtjsonrpc.server.SignedToken;
 import com.google.gwtjsonrpc.server.XsrfException;
@@ -44,7 +48,6 @@
   private final boolean trustContainerAuth;
   private final boolean enableRunAs;
   private final boolean userNameToLowerCase;
-  private final boolean gitBasicAuth;
   private final boolean useContributorAgreements;
   private final String loginUrl;
   private final String loginText;
@@ -88,7 +91,6 @@
     cookieSecure = cfg.getBoolean("auth", "cookiesecure", false);
     trustContainerAuth = cfg.getBoolean("auth", "trustContainerAuth", false);
     enableRunAs = cfg.getBoolean("auth", null, "enableRunAs", true);
-    gitBasicAuth = cfg.getBoolean("auth", "gitBasicAuth", false);
     gitBasicAuthPolicy = getBasicAuthPolicy(cfg);
     useContributorAgreements = cfg.getBoolean("auth", "contributoragreements", false);
     userNameToLowerCase = cfg.getBoolean("auth", "userNameToLowerCase", false);
@@ -223,11 +225,6 @@
     return userNameToLowerCase;
   }
 
-  /** Whether git-over-http should use Gerrit basic authentication scheme. */
-  public boolean isGitBasicAuth() {
-    return gitBasicAuth;
-  }
-
   public GitBasicAuthPolicy getGitBasicAuthPolicy() {
     return gitBasicAuthPolicy;
   }
@@ -237,7 +234,7 @@
     return useContributorAgreements;
   }
 
-  public boolean isIdentityTrustable(final Collection<AccountExternalId> ids) {
+  public boolean isIdentityTrustable(Collection<ExternalId> ids) {
     switch (getAuthType()) {
       case DEVELOPMENT_BECOME_ANY_ACCOUNT:
       case HTTP:
@@ -258,7 +255,7 @@
       case OPENID:
         // All identities must be trusted in order to trust the account.
         //
-        for (final AccountExternalId e : ids) {
+        for (ExternalId e : ids) {
           if (!isTrusted(e)) {
             return false;
           }
@@ -272,8 +269,8 @@
     }
   }
 
-  private boolean isTrusted(final AccountExternalId id) {
-    if (id.isScheme(AccountExternalId.SCHEME_MAILTO)) {
+  private boolean isTrusted(ExternalId id) {
+    if (id.isScheme(SCHEME_MAILTO)) {
       // mailto identities are created by sending a unique validation
       // token to the address and asking them to come back to the site
       // with that token.
@@ -281,20 +278,20 @@
       return true;
     }
 
-    if (id.isScheme(AccountExternalId.SCHEME_UUID)) {
+    if (id.isScheme(SCHEME_UUID)) {
       // UUID identities are absolutely meaningless and cannot be
       // constructed through any normal login process we use.
       //
       return true;
     }
 
-    if (id.isScheme(AccountExternalId.SCHEME_USERNAME)) {
+    if (id.isScheme(SCHEME_USERNAME)) {
       // We can trust their username, its local to our server only.
       //
       return true;
     }
 
-    for (final OpenIdProviderPattern p : trustedOpenIDs) {
+    for (OpenIdProviderPattern p : trustedOpenIDs) {
       if (p.matches(id)) {
         return true;
       }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/config/ConfirmEmail.java b/gerrit-server/src/main/java/com/google/gerrit/server/config/ConfirmEmail.java
index 35c9012..1044bbb 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/config/ConfirmEmail.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/config/ConfirmEmail.java
@@ -30,6 +30,7 @@
 import com.google.inject.Provider;
 import com.google.inject.Singleton;
 import java.io.IOException;
+import org.eclipse.jgit.errors.ConfigInvalidException;
 
 @Singleton
 public class ConfirmEmail implements RestModifyView<ConfigResource, Input> {
@@ -54,7 +55,7 @@
   @Override
   public Response<?> apply(ConfigResource rsrc, Input input)
       throws AuthException, UnprocessableEntityException, AccountException, OrmException,
-          IOException {
+          IOException, ConfigInvalidException {
     CurrentUser user = self.get();
     if (!user.isIdentifiedUser()) {
       throw new AuthException("Authentication required");
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/config/GetServerInfo.java b/gerrit-server/src/main/java/com/google/gerrit/server/config/GetServerInfo.java
index 2ecbb54..2f68140 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/config/GetServerInfo.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/config/GetServerInfo.java
@@ -156,7 +156,6 @@
     info.useContributorAgreements = toBoolean(cfg.isUseContributorAgreements());
     info.editableAccountFields = new ArrayList<>(realm.getEditableFields());
     info.switchAccountUrl = cfg.getSwitchAccountUrl();
-    info.isGitBasicAuth = toBoolean(cfg.isGitBasicAuth());
     info.gitBasicAuthPolicy = cfg.getGitBasicAuthPolicy();
 
     if (info.useContributorAgreements != null) {
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/git/VisibleRefFilter.java b/gerrit-server/src/main/java/com/google/gerrit/server/git/VisibleRefFilter.java
index e55deda..47d416c 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/git/VisibleRefFilter.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/git/VisibleRefFilter.java
@@ -110,7 +110,8 @@
       String name = ref.getName();
       Change.Id changeId;
       Account.Id accountId;
-      if (name.startsWith(REFS_CACHE_AUTOMERGE) || (!showMetadata && isMetadata(name))) {
+      if (name.startsWith(REFS_CACHE_AUTOMERGE)
+          || (!showMetadata && isMetadata(projectCtl, name))) {
         continue;
       } else if (RefNames.isRefsEdit(name)) {
         // Edits are visible only to the owning user, if change is visible.
@@ -138,6 +139,12 @@
         if (viewMetadata) {
           result.put(name, ref);
         }
+      } else if (projectCtl.getProjectState().isAllUsers()
+          && name.equals(RefNames.REFS_EXTERNAL_IDS)) {
+        // The notes branch with the external IDs of all users must not be exposed to normal users.
+        if (viewMetadata) {
+          result.put(name, ref);
+        }
       } else if (projectCtl.controlForRef(ref.getLeaf().getName()).isVisible()) {
         // Use the leaf to lookup the control data. If the reference is
         // symbolic we want the control around the final target. If its
@@ -264,8 +271,10 @@
     }
   }
 
-  private static boolean isMetadata(String name) {
-    return name.startsWith(REFS_CHANGES) || RefNames.isRefsEdit(name);
+  private static boolean isMetadata(ProjectControl projectCtl, String name) {
+    return name.startsWith(REFS_CHANGES)
+        || RefNames.isRefsEdit(name)
+        || (projectCtl.getProjectState().isAllUsers() && name.equals(RefNames.REFS_EXTERNAL_IDS));
   }
 
   private static boolean isTag(Ref ref) {
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/git/validators/CommitValidators.java b/gerrit-server/src/main/java/com/google/gerrit/server/git/validators/CommitValidators.java
index 1dd025f..630dd32 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/git/validators/CommitValidators.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/git/validators/CommitValidators.java
@@ -134,7 +134,8 @@
                     refControl, canonicalWebUrl, installCommitMsgHookCommand, sshInfo),
                 new ConfigValidator(refControl, repo, allUsers),
                 new BannedCommitsValidator(rejectCommits),
-                new PluginCommitValidationListener(pluginValidators)));
+                new PluginCommitValidationListener(pluginValidators),
+                new BlockExternalIdUpdateListener(allUsers)));
       }
     }
 
@@ -149,7 +150,8 @@
               new ChangeIdValidator(
                   refControl, canonicalWebUrl, installCommitMsgHookCommand, sshInfo),
               new ConfigValidator(refControl, repo, allUsers),
-              new PluginCommitValidationListener(pluginValidators)));
+              new PluginCommitValidationListener(pluginValidators),
+              new BlockExternalIdUpdateListener(allUsers)));
     }
 
     private CommitValidators forMergedCommits(RefControl refControl) {
@@ -617,6 +619,25 @@
     }
   }
 
+  /** Blocks any update to refs/meta/external-ids */
+  public static class BlockExternalIdUpdateListener implements CommitValidationListener {
+    private final AllUsersName allUsers;
+
+    public BlockExternalIdUpdateListener(AllUsersName allUsers) {
+      this.allUsers = allUsers;
+    }
+
+    @Override
+    public List<CommitValidationMessage> onCommitReceived(CommitReceivedEvent receiveEvent)
+        throws CommitValidationException {
+      if (allUsers.equals(receiveEvent.project.getNameKey())
+          && RefNames.REFS_EXTERNAL_IDS.equals(receiveEvent.refName)) {
+        throw new CommitValidationException("not allowed to update " + RefNames.REFS_EXTERNAL_IDS);
+      }
+      return Collections.emptyList();
+    }
+  }
+
   private static CommitValidationMessage getInvalidEmailError(
       RevCommit c,
       String type,
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/index/account/AccountField.java b/gerrit-server/src/main/java/com/google/gerrit/server/index/account/AccountField.java
index b9d78e0..e3de170 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/index/account/AccountField.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/index/account/AccountField.java
@@ -18,8 +18,8 @@
 import com.google.common.base.Strings;
 import com.google.common.collect.FluentIterable;
 import com.google.common.collect.Iterables;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.server.account.AccountState;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gerrit.server.index.FieldDef;
 import com.google.gerrit.server.index.FieldType;
 import com.google.gerrit.server.index.SchemaUtil;
@@ -42,7 +42,7 @@
       new FieldDef.Repeatable<AccountState, String>("external_id", FieldType.EXACT, false) {
         @Override
         public Iterable<String> get(AccountState input, FillArgs args) {
-          return Iterables.transform(input.getExternalIds(), id -> id.getKey().get());
+          return Iterables.transform(input.getExternalIds(), id -> id.key().get());
         }
       };
 
@@ -54,8 +54,7 @@
           String fullName = input.getAccount().getFullName();
           Set<String> parts =
               SchemaUtil.getNameParts(
-                  fullName,
-                  Iterables.transform(input.getExternalIds(), AccountExternalId::getEmailAddress));
+                  fullName, Iterables.transform(input.getExternalIds(), ExternalId::email));
 
           // Additional values not currently added by getPersonParts.
           // TODO(dborowitz): Move to getPersonParts and remove this hack.
@@ -87,7 +86,7 @@
         @Override
         public Iterable<String> get(AccountState input, FillArgs args) {
           return FluentIterable.from(input.getExternalIds())
-              .transform(AccountExternalId::getEmailAddress)
+              .transform(ExternalId::email)
               .append(Collections.singleton(input.getAccount().getPreferredEmail()))
               .filter(Predicates.notNull())
               .transform(String::toLowerCase)
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/query/account/InternalAccountQuery.java b/gerrit-server/src/main/java/com/google/gerrit/server/query/account/InternalAccountQuery.java
index 1c336d4..c2b92aa 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/query/account/InternalAccountQuery.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/query/account/InternalAccountQuery.java
@@ -18,6 +18,7 @@
 import com.google.common.collect.Lists;
 import com.google.gerrit.reviewdb.client.Project;
 import com.google.gerrit.server.account.AccountState;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gerrit.server.index.IndexConfig;
 import com.google.gerrit.server.index.account.AccountIndexCollection;
 import com.google.gerrit.server.query.InternalQuery;
@@ -67,11 +68,27 @@
     return query(AccountPredicates.defaultPredicate(query));
   }
 
-  public List<AccountState> byExternalId(String externalId) throws OrmException {
-    return query(AccountPredicates.externalId(externalId));
+  public List<AccountState> byEmailPrefix(String emailPrefix) throws OrmException {
+    return query(AccountPredicates.email(emailPrefix));
+  }
+
+  public List<AccountState> byExternalId(String scheme, String id) throws OrmException {
+    return byExternalId(ExternalId.Key.create(scheme, id));
+  }
+
+  public List<AccountState> byExternalId(ExternalId.Key externalId) throws OrmException {
+    return query(AccountPredicates.externalId(externalId.toString()));
   }
 
   public AccountState oneByExternalId(String externalId) throws OrmException {
+    return oneByExternalId(ExternalId.Key.parse(externalId));
+  }
+
+  public AccountState oneByExternalId(String scheme, String id) throws OrmException {
+    return oneByExternalId(ExternalId.Key.create(scheme, id));
+  }
+
+  public AccountState oneByExternalId(ExternalId.Key externalId) throws OrmException {
     List<AccountState> accountStates = byExternalId(externalId);
     if (accountStates.size() == 1) {
       return accountStates.get(0);
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/schema/AclUtil.java b/gerrit-server/src/main/java/com/google/gerrit/server/schema/AclUtil.java
index 97b4e51..3b87fb6 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/schema/AclUtil.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/schema/AclUtil.java
@@ -56,6 +56,18 @@
     }
   }
 
+  public static void block(
+      ProjectConfig config, AccessSection section, String permission, GroupReference... groupList) {
+    Permission p = section.getPermission(permission, true);
+    for (GroupReference group : groupList) {
+      if (group != null) {
+        PermissionRule r = rule(config, group);
+        r.setBlock();
+        p.add(r);
+      }
+    }
+  }
+
   public static void grant(
       ProjectConfig config,
       AccessSection section,
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/schema/SchemaVersion.java b/gerrit-server/src/main/java/com/google/gerrit/server/schema/SchemaVersion.java
index e2d16d8..a67a8a9 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/schema/SchemaVersion.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/schema/SchemaVersion.java
@@ -35,7 +35,7 @@
 /** A version of the database schema. */
 public abstract class SchemaVersion {
   /** The current schema version. */
-  public static final Class<Schema_141> C = Schema_141.class;
+  public static final Class<Schema_142> C = Schema_142.class;
 
   public static int getBinaryVersion() {
     return guessVersion(C);
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/schema/Schema_142.java b/gerrit-server/src/main/java/com/google/gerrit/server/schema/Schema_142.java
new file mode 100644
index 0000000..df808df
--- /dev/null
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/schema/Schema_142.java
@@ -0,0 +1,49 @@
+// Copyright (C) 2017 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.server.schema;
+
+import com.google.gerrit.reviewdb.client.AccountExternalId;
+import com.google.gerrit.reviewdb.server.ReviewDb;
+import com.google.gerrit.server.account.HashedPassword;
+import com.google.gwtorm.server.OrmException;
+import com.google.inject.Inject;
+import com.google.inject.Provider;
+import java.sql.SQLException;
+import java.util.List;
+
+public class Schema_142 extends SchemaVersion {
+  @Inject
+  Schema_142(Provider<Schema_141> prior) {
+    super(prior);
+  }
+
+  @Override
+  protected void migrateData(ReviewDb db, UpdateUI ui) throws OrmException, SQLException {
+    List<AccountExternalId> newIds = db.accountExternalIds().all().toList();
+    for (AccountExternalId id : newIds) {
+      if (!id.isScheme(AccountExternalId.SCHEME_USERNAME)) {
+        continue;
+      }
+
+      String password = id.getPassword();
+      if (password != null) {
+        HashedPassword hashed = HashedPassword.fromPassword(password);
+        id.setPassword(hashed.encode());
+      }
+    }
+
+    db.accountExternalIds().upsert(newIds);
+  }
+}
diff --git a/gerrit-server/src/main/resources/com/google/gerrit/server/tools/root/scripts/preview_submit_test.sh b/gerrit-server/src/main/resources/com/google/gerrit/server/tools/root/scripts/preview_submit_test.sh
index d76c239..0d8b97f 100644
--- a/gerrit-server/src/main/resources/com/google/gerrit/server/tools/root/scripts/preview_submit_test.sh
+++ b/gerrit-server/src/main/resources/com/google/gerrit/server/tools/root/scripts/preview_submit_test.sh
@@ -36,7 +36,7 @@
         exit 1
 fi
 
-curl --digest -u $gerrituser -w '%{http_code}' -o preview \
+curl -u $gerrituser -w '%{http_code}' -o preview \
     $server/a/changes/$changeId/revisions/current/preview_submit?format=tgz >http_code
 if ! grep 200 http_code >/dev/null
 then
diff --git a/gerrit-server/src/test/java/com/google/gerrit/server/account/HashedPasswordTest.java b/gerrit-server/src/test/java/com/google/gerrit/server/account/HashedPasswordTest.java
new file mode 100644
index 0000000..4955c06
--- /dev/null
+++ b/gerrit-server/src/test/java/com/google/gerrit/server/account/HashedPasswordTest.java
@@ -0,0 +1,64 @@
+// Copyright (C) 2017 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.server.account;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import com.google.common.base.Strings;
+import org.apache.commons.codec.DecoderException;
+import org.junit.Test;
+
+public class HashedPasswordTest {
+
+  @Test
+  public void encodeOneLine() throws Exception {
+    String password = "secret";
+    HashedPassword hashed = HashedPassword.fromPassword(password);
+    assertThat(hashed.encode()).doesNotContain("\n");
+    assertThat(hashed.encode()).doesNotContain("\r");
+  }
+
+  @Test
+  public void encodeDecode() throws Exception {
+    String password = "secret";
+    HashedPassword hashed = HashedPassword.fromPassword(password);
+    HashedPassword roundtrip = HashedPassword.decode(hashed.encode());
+    assertThat(hashed.encode()).isEqualTo(roundtrip.encode());
+    assertThat(roundtrip.checkPassword(password)).isTrue();
+    assertThat(roundtrip.checkPassword("not the password")).isFalse();
+  }
+
+  @Test(expected = DecoderException.class)
+  public void invalidDecode() throws Exception {
+    HashedPassword.decode("invalid");
+  }
+
+  @Test
+  public void lengthLimit() throws Exception {
+    String password = Strings.repeat("1", 72);
+
+    // make sure it fits in varchar(255).
+    assertThat(HashedPassword.fromPassword(password).encode().length()).isLessThan(255);
+  }
+
+  @Test
+  public void basicFunctionality() throws Exception {
+    String password = "secret";
+    HashedPassword hashed = HashedPassword.fromPassword(password);
+
+    assertThat(hashed.checkPassword("false")).isFalse();
+    assertThat(hashed.checkPassword(password)).isTrue();
+  }
+}
diff --git a/gerrit-server/src/test/java/com/google/gerrit/server/mail/send/FromAddressGeneratorProviderTest.java b/gerrit-server/src/test/java/com/google/gerrit/server/mail/send/FromAddressGeneratorProviderTest.java
index ca8dc0c6..a7b37a8 100644
--- a/gerrit-server/src/test/java/com/google/gerrit/server/mail/send/FromAddressGeneratorProviderTest.java
+++ b/gerrit-server/src/test/java/com/google/gerrit/server/mail/send/FromAddressGeneratorProviderTest.java
@@ -23,18 +23,13 @@
 
 import com.google.gerrit.common.TimeUtil;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
-import com.google.gerrit.reviewdb.client.AccountGroup;
 import com.google.gerrit.server.account.AccountCache;
 import com.google.gerrit.server.account.AccountState;
-import com.google.gerrit.server.account.WatchConfig.NotifyType;
-import com.google.gerrit.server.account.WatchConfig.ProjectWatchKey;
 import com.google.gerrit.server.mail.Address;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.List;
-import java.util.Set;
 import org.eclipse.jgit.lib.Config;
 import org.eclipse.jgit.lib.PersonIdent;
 import org.junit.Before;
@@ -388,9 +383,6 @@
     account.setFullName(name);
     account.setPreferredEmail(email);
     return new AccountState(
-        account,
-        Collections.<AccountGroup.UUID>emptySet(),
-        Collections.<AccountExternalId>emptySet(),
-        new HashMap<ProjectWatchKey, Set<NotifyType>>());
+        account, Collections.emptySet(), Collections.emptySet(), new HashMap<>());
   }
 }
diff --git a/gerrit-server/src/test/java/com/google/gerrit/testutil/FakeAccountCache.java b/gerrit-server/src/test/java/com/google/gerrit/testutil/FakeAccountCache.java
index d495c77..d81d441 100644
--- a/gerrit-server/src/test/java/com/google/gerrit/testutil/FakeAccountCache.java
+++ b/gerrit-server/src/test/java/com/google/gerrit/testutil/FakeAccountCache.java
@@ -17,15 +17,10 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.gerrit.common.TimeUtil;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
-import com.google.gerrit.reviewdb.client.AccountGroup;
 import com.google.gerrit.server.account.AccountCache;
 import com.google.gerrit.server.account.AccountState;
-import com.google.gerrit.server.account.WatchConfig.NotifyType;
-import com.google.gerrit.server.account.WatchConfig.ProjectWatchKey;
 import java.util.HashMap;
 import java.util.Map;
-import java.util.Set;
 
 /** Fake implementation of {@link AccountCache} for testing. */
 public class FakeAccountCache implements AccountCache {
@@ -81,10 +76,6 @@
   }
 
   private static AccountState newState(Account account) {
-    return new AccountState(
-        account,
-        ImmutableSet.<AccountGroup.UUID>of(),
-        ImmutableSet.<AccountExternalId>of(),
-        new HashMap<ProjectWatchKey, Set<NotifyType>>());
+    return new AccountState(account, ImmutableSet.of(), ImmutableSet.of(), new HashMap<>());
   }
 }
diff --git a/gerrit-sshd/src/main/java/com/google/gerrit/sshd/SshKeyCacheImpl.java b/gerrit-sshd/src/main/java/com/google/gerrit/sshd/SshKeyCacheImpl.java
index 45193f3..837865e 100644
--- a/gerrit-sshd/src/main/java/com/google/gerrit/sshd/SshKeyCacheImpl.java
+++ b/gerrit-sshd/src/main/java/com/google/gerrit/sshd/SshKeyCacheImpl.java
@@ -14,13 +14,13 @@
 
 package com.google.gerrit.sshd;
 
-import static com.google.gerrit.reviewdb.client.AccountExternalId.SCHEME_USERNAME;
+import static com.google.gerrit.server.account.ExternalId.SCHEME_USERNAME;
 
 import com.google.common.cache.CacheLoader;
 import com.google.common.cache.LoadingCache;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.client.AccountSshKey;
 import com.google.gerrit.reviewdb.server.ReviewDb;
+import com.google.gerrit.server.account.ExternalId;
 import com.google.gerrit.server.account.VersionedAuthorizedKeys;
 import com.google.gerrit.server.cache.CacheModule;
 import com.google.gerrit.server.ssh.SshKeyCache;
@@ -103,14 +103,17 @@
     @Override
     public Iterable<SshKeyCacheEntry> load(String username) throws Exception {
       try (ReviewDb db = schema.open()) {
-        AccountExternalId.Key key = new AccountExternalId.Key(SCHEME_USERNAME, username);
-        AccountExternalId user = db.accountExternalIds().get(key);
+        ExternalId user =
+            ExternalId.from(
+                db.accountExternalIds()
+                    .get(
+                        ExternalId.Key.create(SCHEME_USERNAME, username).asAccountExternalIdKey()));
         if (user == null) {
           return NO_SUCH_USER;
         }
 
         List<SshKeyCacheEntry> kl = new ArrayList<>(4);
-        for (AccountSshKey k : authorizedKeys.getKeys(user.getAccountId())) {
+        for (AccountSshKey k : authorizedKeys.getKeys(user.accountId())) {
           if (k.isValid()) {
             add(kl, k);
           }
diff --git a/gerrit-sshd/src/main/java/com/google/gerrit/sshd/commands/SetAccountCommand.java b/gerrit-sshd/src/main/java/com/google/gerrit/sshd/commands/SetAccountCommand.java
index 5fccb81..21591dd 100644
--- a/gerrit-sshd/src/main/java/com/google/gerrit/sshd/commands/SetAccountCommand.java
+++ b/gerrit-sshd/src/main/java/com/google/gerrit/sshd/commands/SetAccountCommand.java
@@ -263,7 +263,7 @@
   }
 
   private void addEmail(String email)
-      throws UnloggedFailure, RestApiException, OrmException, IOException {
+      throws UnloggedFailure, RestApiException, OrmException, IOException, ConfigInvalidException {
     EmailInput in = new EmailInput();
     in.email = email;
     in.noConfirmation = true;
@@ -274,7 +274,8 @@
     }
   }
 
-  private void deleteEmail(String email) throws RestApiException, OrmException, IOException {
+  private void deleteEmail(String email)
+      throws RestApiException, OrmException, IOException, ConfigInvalidException {
     if (email.equals("ALL")) {
       List<EmailInfo> emails = getEmails.apply(rsrc);
       for (EmailInfo e : emails) {
diff --git a/plugins/cookbook-plugin b/plugins/cookbook-plugin
index 85083bc..e6d7594 160000
--- a/plugins/cookbook-plugin
+++ b/plugins/cookbook-plugin
@@ -1 +1 @@
-Subproject commit 85083bc964ca00437e8695ec7335df9b87f28465
+Subproject commit e6d7594621d87859a0e6af361cac1fc3173c3588