summary refs log tree commit diff
diff options
context:
space:
mode:
-rw-r--r--.buildkite/pipeline.yml4
-rw-r--r--INSTALL.md16
-rw-r--r--UPGRADE.rst49
-rw-r--r--changelog.d/5089.bugfix1
-rw-r--r--changelog.d/5221.bugfix1
-rw-r--r--changelog.d/5232.misc2
-rw-r--r--changelog.d/5234.misc2
-rw-r--r--changelog.d/5235.misc2
-rw-r--r--changelog.d/5236.misc2
-rw-r--r--changelog.d/5237.misc2
-rw-r--r--changelog.d/5244.misc2
-rw-r--r--changelog.d/5250.misc2
-rw-r--r--changelog.d/5284.misc1
-rw-r--r--changelog.d/5296.misc2
-rw-r--r--changelog.d/5299.misc2
-rw-r--r--changelog.d/5317.bugfix1
-rw-r--r--changelog.d/5321.bugfix1
-rw-r--r--changelog.d/5324.feature1
-rw-r--r--changelog.d/5328.misc1
-rw-r--r--changelog.d/5332.misc1
-rw-r--r--changelog.d/5333.bugfix1
-rw-r--r--changelog.d/5334.bugfix1
-rw-r--r--changelog.d/5335.bugfix1
-rw-r--r--changelog.d/5340.bugfix2
-rw-r--r--changelog.d/5341.bugfix1
-rw-r--r--changelog.d/5342.bugfix1
-rw-r--r--changelog.d/5343.misc1
-rw-r--r--changelog.d/5344.misc1
-rw-r--r--changelog.d/5347.misc1
-rw-r--r--changelog.d/5348.bugfix1
-rw-r--r--changelog.d/5352.bugfix1
-rw-r--r--changelog.d/5353.misc2
-rw-r--r--changelog.d/5354.bugfix2
-rw-r--r--changelog.d/5355.bugfix1
-rw-r--r--changelog.d/5356.misc1
-rw-r--r--changelog.d/5357.doc1
-rw-r--r--changelog.d/5359.feature1
-rw-r--r--changelog.d/5360.feature1
-rw-r--r--changelog.d/5361.feature1
-rw-r--r--changelog.d/5362.bugfix1
-rw-r--r--changelog.d/5369.bugfix1
-rw-r--r--changelog.d/5370.misc1
-rw-r--r--changelog.d/5371.feature1
-rw-r--r--changelog.d/5374.feature1
-rw-r--r--changelog.d/5377.feature1
-rw-r--r--docs/MSC1711_certificates_FAQ.md17
-rw-r--r--docs/sample_config.yaml127
-rwxr-xr-xscripts/generate_signing_key.py37
-rw-r--r--synapse/api/errors.py9
-rw-r--r--synapse/api/room_versions.py20
-rwxr-xr-xsynapse/app/homeserver.py1
-rw-r--r--synapse/config/emailconfig.py244
-rw-r--r--synapse/config/key.py228
-rw-r--r--synapse/config/server.py16
-rw-r--r--synapse/config/tls.py12
-rw-r--r--synapse/crypto/event_signing.py6
-rw-r--r--synapse/crypto/keyring.py405
-rw-r--r--synapse/federation/federation_base.py41
-rw-r--r--synapse/federation/federation_client.py50
-rw-r--r--synapse/federation/transport/server.py6
-rw-r--r--synapse/groups/attestations.py7
-rw-r--r--synapse/handlers/auth.py64
-rw-r--r--synapse/handlers/federation.py58
-rw-r--r--synapse/handlers/identity.py13
-rw-r--r--synapse/handlers/presence.py19
-rw-r--r--synapse/handlers/stats.py18
-rw-r--r--synapse/handlers/sync.py43
-rw-r--r--synapse/http/matrixfederationclient.py71
-rw-r--r--synapse/push/mailer.py85
-rw-r--r--synapse/push/pusher.py4
-rw-r--r--synapse/python_dependencies.py2
-rw-r--r--synapse/res/templates/password_reset.html9
-rw-r--r--synapse/res/templates/password_reset.txt7
-rw-r--r--synapse/res/templates/password_reset_failure.html6
-rw-r--r--synapse/res/templates/password_reset_success.html6
-rw-r--r--synapse/rest/client/v1/voip.py1
-rw-r--r--synapse/rest/client/v2_alpha/account.py243
-rw-r--r--synapse/rest/client/versions.py1
-rw-r--r--synapse/rest/key/v2/remote_key_resource.py12
-rw-r--r--synapse/storage/_base.py6
-rw-r--r--synapse/storage/events_worker.py37
-rw-r--r--synapse/storage/prepare_database.py2
-rw-r--r--synapse/storage/registration.py290
-rw-r--r--synapse/storage/schema/delta/55/track_threepid_validations.sql31
-rw-r--r--synapse/storage/stats.py16
-rw-r--r--synapse/storage/stream.py12
-rw-r--r--synapse/util/retryutils.py55
-rw-r--r--tests/crypto/test_keyring.py184
-rw-r--r--tests/handlers/test_stats.py62
-rw-r--r--tests/http/federation/test_matrix_federation_agent.py13
-rw-r--r--tests/utils.py1
91 files changed, 2198 insertions, 522 deletions
diff --git a/.buildkite/pipeline.yml b/.buildkite/pipeline.yml
index 44b258dca6..b805b2d839 100644
--- a/.buildkite/pipeline.yml
+++ b/.buildkite/pipeline.yml
@@ -36,8 +36,6 @@ steps:
           image: "python:3.6"
           propagate-environment: true
 
-  - wait
-
   - command:
       - "python -m pip install tox"
       - "tox -e check-sampleconfig"
@@ -46,6 +44,8 @@ steps:
       - docker#v3.0.1:
           image: "python:3.6"
 
+  - wait
+
   - command:
       - "python -m pip install tox"
       - "tox -e py27,codecov"
diff --git a/INSTALL.md b/INSTALL.md
index 1934593148..a1ff91a98e 100644
--- a/INSTALL.md
+++ b/INSTALL.md
@@ -5,6 +5,7 @@
   * [Prebuilt packages](#prebuilt-packages)
 * [Setting up Synapse](#setting-up-synapse)
   * [TLS certificates](#tls-certificates)
+  * [Email](#email)
   * [Registering a user](#registering-a-user)
   * [Setting up a TURN server](#setting-up-a-turn-server)
   * [URL previews](#url-previews)
@@ -394,9 +395,22 @@ To configure Synapse to expose an HTTPS port, you will need to edit
   instance, if using certbot, use `fullchain.pem` as your certificate, not
   `cert.pem`).
 
-For those of you upgrading your TLS certificate in readiness for Synapse 1.0,
+For those of you upgrading your TLS certificate for Synapse 1.0 compliance,
 please take a look at [our guide](docs/MSC1711_certificates_FAQ.md#configuring-certificates-for-compatibility-with-synapse-100).
 
+## Email
+
+It is desirable for Synapse to have the capability to send email. For example,
+this is required to support the 'password reset' feature.
+
+To configure an SMTP server for Synapse, modify the configuration section
+headed ``email``, and be sure to have at least the ``smtp_host``, ``smtp_port``
+and ``notif_from`` fields filled out. You may also need to set ``smtp_user``,
+``smtp_pass``, and ``require_transport_security``.
+
+If Synapse is not configured with an SMTP server, password reset via email will
+ be disabled by default.
+
 ## Registering a user
 
 You will need at least one user on your server in order to use a Matrix
diff --git a/UPGRADE.rst b/UPGRADE.rst
index 228222d534..6032a505c9 100644
--- a/UPGRADE.rst
+++ b/UPGRADE.rst
@@ -49,6 +49,55 @@ returned by the Client-Server API:
     # configured on port 443.
     curl -kv https://<host.name>/_matrix/client/versions 2>&1 | grep "Server:"
 
+Upgrading to v1.0
+=================
+
+Validation of TLS certificates
+------------------------------
+
+Synapse v1.0 is the first release to enforce
+validation of TLS certificates for the federation API. It is therefore
+essential that your certificates are correctly configured. See the `FAQ
+<docs/MSC1711_certificates_FAQ.md>`_ for more information.
+
+Note, v1.0 installations will also no longer be able to federate with servers
+that have not correctly configured their certificates.
+
+In rare cases, it may be desirable to disable certificate checking: for
+example, it might be essential to be able to federate with a given legacy
+server in a closed federation. This can be done in one of two ways:-
+
+* Configure the global switch ``federation_verify_certificates`` to ``false``.
+* Configure a whitelist of server domains to trust via ``federation_certificate_verification_whitelist``.
+
+See the `sample configuration file <docs/sample_config.yaml>`_
+for more details on these settings. 
+
+Email
+-----
+When a user requests a password reset, Synapse will send an email to the 
+user to confirm the request.
+
+Previous versions of Synapse delegated the job of sending this email to an
+identity server. If the identity server was somehow malicious or became
+compromised, it would be theoretically possible to hijack an account through
+this means.
+
+Therefore, by default, Synapse v1.0 will send the confirmation email itself. If
+Synapse is not configured with an SMTP server, password reset via email will be
+disabled.
+
+To configure an SMTP server for Synapse, modify the configuration section
+headed ``email``, and be sure to have at least the ``smtp_host``, ``smtp_port``
+and ``notif_from`` fields filled out. You may also need to set ``smtp_user``,
+``smtp_pass``, and ``require_transport_security``.
+
+If you are absolutely certain that you wish to continue using an identity
+server for password resets, set ``trust_identity_server_for_password_resets`` to ``true``.
+
+See the `sample configuration file <docs/sample_config.yaml>`_
+for more details on these settings.
+
 Upgrading to v0.99.0
 ====================
 
diff --git a/changelog.d/5089.bugfix b/changelog.d/5089.bugfix
new file mode 100644
index 0000000000..68643cebb7
--- /dev/null
+++ b/changelog.d/5089.bugfix
@@ -0,0 +1 @@
+Fixes client-server API not sending "m.heroes" to lazy-load /sync requests when a rooms name or its canonical alias are empty. Thanks to @dnaf for this work!
diff --git a/changelog.d/5221.bugfix b/changelog.d/5221.bugfix
new file mode 100644
index 0000000000..03aa363d15
--- /dev/null
+++ b/changelog.d/5221.bugfix
@@ -0,0 +1 @@
+Fix race when backfilling in rooms with worker mode.
diff --git a/changelog.d/5232.misc b/changelog.d/5232.misc
index 1cdc71f095..8336bc55dc 100644
--- a/changelog.d/5232.misc
+++ b/changelog.d/5232.misc
@@ -1 +1 @@
-Run black on synapse.crypto.keyring.
+Preparatory work for key-validity features.
diff --git a/changelog.d/5234.misc b/changelog.d/5234.misc
index 43fbd6f67c..8336bc55dc 100644
--- a/changelog.d/5234.misc
+++ b/changelog.d/5234.misc
@@ -1 +1 @@
-Rewrite store_server_verify_key to store several keys at once.
+Preparatory work for key-validity features.
diff --git a/changelog.d/5235.misc b/changelog.d/5235.misc
index 2296ad2a4f..8336bc55dc 100644
--- a/changelog.d/5235.misc
+++ b/changelog.d/5235.misc
@@ -1 +1 @@
-Remove unused VerifyKey.expired and .time_added fields.
+Preparatory work for key-validity features.
diff --git a/changelog.d/5236.misc b/changelog.d/5236.misc
index cb4417a9f4..8336bc55dc 100644
--- a/changelog.d/5236.misc
+++ b/changelog.d/5236.misc
@@ -1 +1 @@
-Simplify Keyring.process_v2_response.
\ No newline at end of file
+Preparatory work for key-validity features.
diff --git a/changelog.d/5237.misc b/changelog.d/5237.misc
index f4fe3b821b..8336bc55dc 100644
--- a/changelog.d/5237.misc
+++ b/changelog.d/5237.misc
@@ -1 +1 @@
-Store key validity time in the storage layer.
+Preparatory work for key-validity features.
diff --git a/changelog.d/5244.misc b/changelog.d/5244.misc
index 9cc1fb869d..8336bc55dc 100644
--- a/changelog.d/5244.misc
+++ b/changelog.d/5244.misc
@@ -1 +1 @@
-Refactor synapse.crypto.keyring to use a KeyFetcher interface.
+Preparatory work for key-validity features.
diff --git a/changelog.d/5250.misc b/changelog.d/5250.misc
index 575a299a82..8336bc55dc 100644
--- a/changelog.d/5250.misc
+++ b/changelog.d/5250.misc
@@ -1 +1 @@
-Simplification to Keyring.wait_for_previous_lookups.
+Preparatory work for key-validity features.
diff --git a/changelog.d/5284.misc b/changelog.d/5284.misc
new file mode 100644
index 0000000000..c4d42ca3d9
--- /dev/null
+++ b/changelog.d/5284.misc
@@ -0,0 +1 @@
+Improve sample config for monthly active user blocking. 
diff --git a/changelog.d/5296.misc b/changelog.d/5296.misc
index a038a6f7f6..8336bc55dc 100644
--- a/changelog.d/5296.misc
+++ b/changelog.d/5296.misc
@@ -1 +1 @@
-Refactor keyring.VerifyKeyRequest to use attr.s.
+Preparatory work for key-validity features.
diff --git a/changelog.d/5299.misc b/changelog.d/5299.misc
index 53297c768b..8336bc55dc 100644
--- a/changelog.d/5299.misc
+++ b/changelog.d/5299.misc
@@ -1 +1 @@
-Rewrite get_server_verify_keys, again.
+Preparatory work for key-validity features.
diff --git a/changelog.d/5317.bugfix b/changelog.d/5317.bugfix
new file mode 100644
index 0000000000..2709375214
--- /dev/null
+++ b/changelog.d/5317.bugfix
@@ -0,0 +1 @@
+Fix handling of failures when processing incoming events where calling `/event_auth` on remote server fails.
diff --git a/changelog.d/5321.bugfix b/changelog.d/5321.bugfix
new file mode 100644
index 0000000000..943a61956d
--- /dev/null
+++ b/changelog.d/5321.bugfix
@@ -0,0 +1 @@
+Ensure that we have an up-to-date copy of the signing key when validating incoming federation requests.
diff --git a/changelog.d/5324.feature b/changelog.d/5324.feature
new file mode 100644
index 0000000000..01285e965c
--- /dev/null
+++ b/changelog.d/5324.feature
@@ -0,0 +1 @@
+Synapse now more efficiently collates room statistics.
diff --git a/changelog.d/5328.misc b/changelog.d/5328.misc
new file mode 100644
index 0000000000..e1b9dc58a3
--- /dev/null
+++ b/changelog.d/5328.misc
@@ -0,0 +1 @@
+The base classes for the v1 and v2_alpha REST APIs have been unified.
diff --git a/changelog.d/5332.misc b/changelog.d/5332.misc
new file mode 100644
index 0000000000..dcfac4eac9
--- /dev/null
+++ b/changelog.d/5332.misc
@@ -0,0 +1 @@
+Improve docstrings on MatrixFederationClient.
diff --git a/changelog.d/5333.bugfix b/changelog.d/5333.bugfix
new file mode 100644
index 0000000000..cb05a6dd63
--- /dev/null
+++ b/changelog.d/5333.bugfix
@@ -0,0 +1 @@
+Fix various problems which made the signing-key notary server time out for some requests.
\ No newline at end of file
diff --git a/changelog.d/5334.bugfix b/changelog.d/5334.bugfix
new file mode 100644
index 0000000000..ed141e0918
--- /dev/null
+++ b/changelog.d/5334.bugfix
@@ -0,0 +1 @@
+Fix bug which would make certain operations (such as room joins) block for 20 minutes while attemoting to fetch verification keys.
diff --git a/changelog.d/5335.bugfix b/changelog.d/5335.bugfix
new file mode 100644
index 0000000000..7318cbe35e
--- /dev/null
+++ b/changelog.d/5335.bugfix
@@ -0,0 +1 @@
+Fix a bug where we could rapidly mark a server as unreachable even though it was only down for a few minutes.
diff --git a/changelog.d/5340.bugfix b/changelog.d/5340.bugfix
new file mode 100644
index 0000000000..931ee904e1
--- /dev/null
+++ b/changelog.d/5340.bugfix
@@ -0,0 +1,2 @@
+Fix a bug where we could rapidly mark a server as unreachable even though it was only down for a few minutes.
+
diff --git a/changelog.d/5341.bugfix b/changelog.d/5341.bugfix
new file mode 100644
index 0000000000..a7aaa95f39
--- /dev/null
+++ b/changelog.d/5341.bugfix
@@ -0,0 +1 @@
+Fix a bug where account validity renewal emails could only be sent when email notifs were enabled.
diff --git a/changelog.d/5342.bugfix b/changelog.d/5342.bugfix
new file mode 100644
index 0000000000..66a3076292
--- /dev/null
+++ b/changelog.d/5342.bugfix
@@ -0,0 +1 @@
+Fix failure when fetching batches of events during backfill, etc.
diff --git a/changelog.d/5343.misc b/changelog.d/5343.misc
new file mode 100644
index 0000000000..8336bc55dc
--- /dev/null
+++ b/changelog.d/5343.misc
@@ -0,0 +1 @@
+Preparatory work for key-validity features.
diff --git a/changelog.d/5344.misc b/changelog.d/5344.misc
new file mode 100644
index 0000000000..a20c563bf1
--- /dev/null
+++ b/changelog.d/5344.misc
@@ -0,0 +1 @@
+Clean up FederationClient.get_events for clarity.
diff --git a/changelog.d/5347.misc b/changelog.d/5347.misc
new file mode 100644
index 0000000000..8336bc55dc
--- /dev/null
+++ b/changelog.d/5347.misc
@@ -0,0 +1 @@
+Preparatory work for key-validity features.
diff --git a/changelog.d/5348.bugfix b/changelog.d/5348.bugfix
new file mode 100644
index 0000000000..8d396c7990
--- /dev/null
+++ b/changelog.d/5348.bugfix
@@ -0,0 +1 @@
+Add a new room version where the timestamps on events are checked against the validity periods on signing keys.
\ No newline at end of file
diff --git a/changelog.d/5352.bugfix b/changelog.d/5352.bugfix
new file mode 100644
index 0000000000..2ffefe5a68
--- /dev/null
+++ b/changelog.d/5352.bugfix
@@ -0,0 +1 @@
+Fix room stats and presence background updates to correctly handle missing events.
diff --git a/changelog.d/5353.misc b/changelog.d/5353.misc
new file mode 100644
index 0000000000..436245fb11
--- /dev/null
+++ b/changelog.d/5353.misc
@@ -0,0 +1,2 @@
+Various improvements to debug logging.
+
diff --git a/changelog.d/5354.bugfix b/changelog.d/5354.bugfix
new file mode 100644
index 0000000000..0c56032b30
--- /dev/null
+++ b/changelog.d/5354.bugfix
@@ -0,0 +1,2 @@
+Add a new room version where the timestamps on events are checked against the validity periods on signing keys.
+
diff --git a/changelog.d/5355.bugfix b/changelog.d/5355.bugfix
new file mode 100644
index 0000000000..e1955a7403
--- /dev/null
+++ b/changelog.d/5355.bugfix
@@ -0,0 +1 @@
+Include left members in room summaries' heroes.
diff --git a/changelog.d/5356.misc b/changelog.d/5356.misc
new file mode 100644
index 0000000000..8336bc55dc
--- /dev/null
+++ b/changelog.d/5356.misc
@@ -0,0 +1 @@
+Preparatory work for key-validity features.
diff --git a/changelog.d/5357.doc b/changelog.d/5357.doc
new file mode 100644
index 0000000000..27cba49641
--- /dev/null
+++ b/changelog.d/5357.doc
@@ -0,0 +1 @@
+Fix notes about ACME in the MSC1711 faq.
diff --git a/changelog.d/5359.feature b/changelog.d/5359.feature
new file mode 100644
index 0000000000..2a03939834
--- /dev/null
+++ b/changelog.d/5359.feature
@@ -0,0 +1 @@
+Validate federation server TLS certificates by default (implements [MSC1711](https://github.com/matrix-org/matrix-doc/blob/master/proposals/1711-x509-for-federation.md)).
diff --git a/changelog.d/5360.feature b/changelog.d/5360.feature
new file mode 100644
index 0000000000..01fbb3b06d
--- /dev/null
+++ b/changelog.d/5360.feature
@@ -0,0 +1 @@
+Update /_matrix/client/versions to reference support for r0.5.0. 
diff --git a/changelog.d/5361.feature b/changelog.d/5361.feature
new file mode 100644
index 0000000000..10768cdad3
--- /dev/null
+++ b/changelog.d/5361.feature
@@ -0,0 +1 @@
+Add a script to generate new signing-key files.
diff --git a/changelog.d/5362.bugfix b/changelog.d/5362.bugfix
new file mode 100644
index 0000000000..1c8b19182c
--- /dev/null
+++ b/changelog.d/5362.bugfix
@@ -0,0 +1 @@
+Fix `federation_custom_ca_list` configuration option.
diff --git a/changelog.d/5369.bugfix b/changelog.d/5369.bugfix
new file mode 100644
index 0000000000..cc61618f39
--- /dev/null
+++ b/changelog.d/5369.bugfix
@@ -0,0 +1 @@
+Fix missing logcontext warnings on shutdown.
diff --git a/changelog.d/5370.misc b/changelog.d/5370.misc
new file mode 100644
index 0000000000..b0473ef280
--- /dev/null
+++ b/changelog.d/5370.misc
@@ -0,0 +1 @@
+Don't run CI build checks until sample config check has passed.
diff --git a/changelog.d/5371.feature b/changelog.d/5371.feature
new file mode 100644
index 0000000000..7f960630e0
--- /dev/null
+++ b/changelog.d/5371.feature
@@ -0,0 +1 @@
+Update upgrade and installation guides ahead of 1.0.
diff --git a/changelog.d/5374.feature b/changelog.d/5374.feature
new file mode 100644
index 0000000000..17937637ab
--- /dev/null
+++ b/changelog.d/5374.feature
@@ -0,0 +1 @@
+Replace the `perspectives` configuration section with `trusted_key_servers`, and make validating the signatures on responses optional (since TLS will do this job for us).
diff --git a/changelog.d/5377.feature b/changelog.d/5377.feature
new file mode 100644
index 0000000000..6aae41847a
--- /dev/null
+++ b/changelog.d/5377.feature
@@ -0,0 +1 @@
+Add ability to perform password reset via email without trusting the identity server.
diff --git a/docs/MSC1711_certificates_FAQ.md b/docs/MSC1711_certificates_FAQ.md
index ebfb20f5c8..599462bdcb 100644
--- a/docs/MSC1711_certificates_FAQ.md
+++ b/docs/MSC1711_certificates_FAQ.md
@@ -68,16 +68,14 @@ Admins should upgrade and configure a valid CA cert. Homeservers that require a
 .well-known entry (see below), should retain their SRV record and use it
 alongside their .well-known record.
 
-**>= 5th March 2019  - Synapse 1.0.0 is released**
+**10th June 2019  - Synapse 1.0.0 is released**
 
-1.0.0 will land no sooner than 1 month after 0.99.0, leaving server admins one
-month after 5th February to upgrade to 0.99.0 and deploy their certificates. In
+1.0.0 is scheduled for release on 10th June. In
 accordance with the the [S2S spec](https://matrix.org/docs/spec/server_server/r0.1.0.html)
 1.0.0 will enforce certificate validity. This means that any homeserver without a
 valid certificate after this point will no longer be able to federate with
 1.0.0 servers.
 
-
 ## Configuring certificates for compatibility with Synapse 1.0.0
 
 ### If you do not currently have an SRV record
@@ -145,12 +143,11 @@ You can do this with a `.well-known` file as follows:
  1. Keep the SRV record in place - it is needed for backwards compatibility
     with Synapse 0.34 and earlier.
 
- 2. Give synapse a certificate corresponding to the target domain
-    (`customer.example.net` in the above example). Currently Synapse's ACME
-    support [does not support
-    this](https://github.com/matrix-org/synapse/issues/4552), so you will have
-    to acquire a certificate yourself and give it to Synapse via
-    `tls_certificate_path` and `tls_private_key_path`.
+  2. Give Synapse a certificate corresponding to the target domain
+    (`customer.example.net` in the above example). You can either use Synapse's
+    built-in [ACME support](./ACME.md) for this (via the `domain` parameter in
+    the `acme` section), or acquire a certificate yourself and give it to
+    Synapse via `tls_certificate_path` and `tls_private_key_path`.
 
  3. Restart Synapse to ensure the new certificate is loaded.
 
diff --git a/docs/sample_config.yaml b/docs/sample_config.yaml
index 493ea9ee9e..ea73306fb9 100644
--- a/docs/sample_config.yaml
+++ b/docs/sample_config.yaml
@@ -261,6 +261,22 @@ listeners:
 
 # Monthly Active User Blocking
 #
+# Used in cases where the admin or server owner wants to limit to the
+# number of monthly active users.
+#
+# 'limit_usage_by_mau' disables/enables monthly active user blocking. When
+# anabled and a limit is reached the server returns a 'ResourceLimitError'
+# with error type Codes.RESOURCE_LIMIT_EXCEEDED
+#
+# 'max_mau_value' is the hard limit of monthly active users above which
+# the server will start blocking user actions.
+#
+# 'mau_trial_days' is a means to add a grace period for active users. It
+# means that users must be active for this number of days before they
+# can be considered active and guards against the case where lots of users
+# sign up in a short space of time never to return after their initial
+# session.
+#
 #limit_usage_by_mau: False
 #max_mau_value: 50
 #mau_trial_days: 2
@@ -313,12 +329,12 @@ listeners:
 #
 #tls_private_key_path: "CONFDIR/SERVERNAME.tls.key"
 
-# Whether to verify TLS certificates when sending federation traffic.
+# Whether to verify TLS server certificates for outbound federation requests.
 #
-# This currently defaults to `false`, however this will change in
-# Synapse 1.0 when valid federation certificates will be required.
+# Defaults to `true`. To disable certificate verification, uncomment the
+# following line.
 #
-#federation_verify_certificates: true
+#federation_verify_certificates: false
 
 # Skip federation certificate verification on the following whitelist
 # of domains.
@@ -936,12 +952,43 @@ signing_key_path: "CONFDIR/SERVERNAME.signing.key"
 
 # The trusted servers to download signing keys from.
 #
-#perspectives:
-#  servers:
-#    "matrix.org":
-#      verify_keys:
-#        "ed25519:auto":
-#          key: "Noi6WqcDj0QmPxCNQqgezwTlBKrfqehY1u2FyWP9uYw"
+# When we need to fetch a signing key, each server is tried in parallel.
+#
+# Normally, the connection to the key server is validated via TLS certificates.
+# Additional security can be provided by configuring a `verify key`, which
+# will make synapse check that the response is signed by that key.
+#
+# This setting supercedes an older setting named `perspectives`. The old format
+# is still supported for backwards-compatibility, but it is deprecated.
+#
+# Options for each entry in the list include:
+#
+#    server_name: the name of the server. required.
+#
+#    verify_keys: an optional map from key id to base64-encoded public key.
+#       If specified, we will check that the response is signed by at least
+#       one of the given keys.
+#
+#    accept_keys_insecurely: a boolean. Normally, if `verify_keys` is unset,
+#       and federation_verify_certificates is not `true`, synapse will refuse
+#       to start, because this would allow anyone who can spoof DNS responses
+#       to masquerade as the trusted key server. If you know what you are doing
+#       and are sure that your network environment provides a secure connection
+#       to the key server, you can set this to `true` to override this
+#       behaviour.
+#
+# An example configuration might look like:
+#
+#trusted_key_servers:
+#  - server_name: "my_trusted_server.example.com"
+#    verify_keys:
+#      "ed25519:auto": "abcdefghijklmnopqrstuvwxyzabcdefghijklmopqr"
+#  - server_name: "my_other_trusted_server.example.com"
+#
+# The default configuration is:
+#
+#trusted_key_servers:
+#  - server_name: "matrix.org"
 
 
 # Enable SAML2 for registration and login. Uses pysaml2.
@@ -1018,10 +1065,8 @@ password_config:
 
 
 
-# Enable sending emails for notification events or expiry notices
-# Defining a custom URL for Riot is only needed if email notifications
-# should contain links to a self-hosted installation of Riot; when set
-# the "app_name" setting is ignored.
+# Enable sending emails for password resets, notification events or
+# account expiry notices
 #
 # If your SMTP server requires authentication, the optional smtp_user &
 # smtp_pass variables should be used
@@ -1029,22 +1074,64 @@ password_config:
 #email:
 #   enable_notifs: false
 #   smtp_host: "localhost"
-#   smtp_port: 25
+#   smtp_port: 25 # SSL: 465, STARTTLS: 587
 #   smtp_user: "exampleusername"
 #   smtp_pass: "examplepassword"
 #   require_transport_security: False
 #   notif_from: "Your Friendly %(app)s Home Server <noreply@example.com>"
 #   app_name: Matrix
-#   # if template_dir is unset, uses the example templates that are part of
-#   # the Synapse distribution.
+#
+#   # Enable email notifications by default
+#   notif_for_new_users: True
+#
+#   # Defining a custom URL for Riot is only needed if email notifications
+#   # should contain links to a self-hosted installation of Riot; when set
+#   # the "app_name" setting is ignored
+#   riot_base_url: "http://localhost/riot"
+#
+#   # Enable sending password reset emails via the configured, trusted
+#   # identity servers
+#   #
+#   # IMPORTANT! This will give a malicious or overtaken identity server
+#   # the ability to reset passwords for your users! Make absolutely sure
+#   # that you want to do this! It is strongly recommended that password
+#   # reset emails be sent by the homeserver instead
+#   #
+#   # If this option is set to false and SMTP options have not been
+#   # configured, resetting user passwords via email will be disabled
+#   #trust_identity_server_for_password_resets: false
+#
+#   # Configure the time that a validation email or text message code
+#   # will expire after sending
+#   #
+#   # This is currently used for password resets
+#   #validation_token_lifetime: 1h
+#
+#   # Template directory. All template files should be stored within this
+#   # directory
+#   #
 #   #template_dir: res/templates
+#
+#   # Templates for email notifications
+#   #
 #   notif_template_html: notif_mail.html
 #   notif_template_text: notif_mail.txt
-#   # Templates for account expiry notices.
+#
+#   # Templates for account expiry notices
+#   #
 #   expiry_template_html: notice_expiry.html
 #   expiry_template_text: notice_expiry.txt
-#   notif_for_new_users: True
-#   riot_base_url: "http://localhost/riot"
+#
+#   # Templates for password reset emails sent by the homeserver
+#   #
+#   #password_reset_template_html: password_reset.html
+#   #password_reset_template_text: password_reset.txt
+#
+#   # Templates for password reset success and failure pages that a user
+#   # will see after attempting to reset their password
+#   #
+#   #password_reset_template_success_html: password_reset_success.html
+#   #password_reset_template_failure_html: password_reset_failure.html
 
 
 #password_providers:
diff --git a/scripts/generate_signing_key.py b/scripts/generate_signing_key.py
new file mode 100755
index 0000000000..ba3ba97395
--- /dev/null
+++ b/scripts/generate_signing_key.py
@@ -0,0 +1,37 @@
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+# Copyright 2019 The Matrix.org Foundation C.I.C.
+#
+# 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.
+import argparse
+import sys
+
+from signedjson.key import write_signing_keys, generate_signing_key
+
+from synapse.util.stringutils import random_string
+
+if __name__ == "__main__":
+    parser = argparse.ArgumentParser()
+
+    parser.add_argument(
+        "-o", "--output_file",
+
+        type=argparse.FileType('w'),
+        default=sys.stdout,
+        help="Where to write the output to",
+    )
+    args = parser.parse_args()
+
+    key_id = "a_" + random_string(4)
+    key = generate_signing_key(key_id),
+    write_signing_keys(args.output_file, key)
diff --git a/synapse/api/errors.py b/synapse/api/errors.py
index e91697049c..66201d6efe 100644
--- a/synapse/api/errors.py
+++ b/synapse/api/errors.py
@@ -339,6 +339,15 @@ class UnsupportedRoomVersionError(SynapseError):
         )
 
 
+class ThreepidValidationError(SynapseError):
+    """An error raised when there was a problem authorising an event."""
+
+    def __init__(self, *args, **kwargs):
+        if "errcode" not in kwargs:
+            kwargs["errcode"] = Codes.FORBIDDEN
+        super(ThreepidValidationError, self).__init__(*args, **kwargs)
+
+
 class IncompatibleRoomVersionError(SynapseError):
     """A server is trying to join a room whose version it does not support.
 
diff --git a/synapse/api/room_versions.py b/synapse/api/room_versions.py
index 4085bd10b9..d644803d38 100644
--- a/synapse/api/room_versions.py
+++ b/synapse/api/room_versions.py
@@ -50,6 +50,7 @@ class RoomVersion(object):
     disposition = attr.ib()     # str; one of the RoomDispositions
     event_format = attr.ib()    # int; one of the EventFormatVersions
     state_res = attr.ib()       # int; one of the StateResolutionVersions
+    enforce_key_validity = attr.ib()  # bool
 
 
 class RoomVersions(object):
@@ -58,30 +59,35 @@ class RoomVersions(object):
         RoomDisposition.STABLE,
         EventFormatVersions.V1,
         StateResolutionVersions.V1,
-    )
-    STATE_V2_TEST = RoomVersion(
-        "state-v2-test",
-        RoomDisposition.UNSTABLE,
-        EventFormatVersions.V1,
-        StateResolutionVersions.V2,
+        enforce_key_validity=False,
     )
     V2 = RoomVersion(
         "2",
         RoomDisposition.STABLE,
         EventFormatVersions.V1,
         StateResolutionVersions.V2,
+        enforce_key_validity=False,
     )
     V3 = RoomVersion(
         "3",
         RoomDisposition.STABLE,
         EventFormatVersions.V2,
         StateResolutionVersions.V2,
+        enforce_key_validity=False,
     )
     V4 = RoomVersion(
         "4",
         RoomDisposition.STABLE,
         EventFormatVersions.V3,
         StateResolutionVersions.V2,
+        enforce_key_validity=False,
+    )
+    V5 = RoomVersion(
+        "5",
+        RoomDisposition.STABLE,
+        EventFormatVersions.V3,
+        StateResolutionVersions.V2,
+        enforce_key_validity=True,
     )
 
 
@@ -90,7 +96,7 @@ KNOWN_ROOM_VERSIONS = {
         RoomVersions.V1,
         RoomVersions.V2,
         RoomVersions.V3,
-        RoomVersions.STATE_V2_TEST,
         RoomVersions.V4,
+        RoomVersions.V5,
     )
 }   # type: dict[str, RoomVersion]
diff --git a/synapse/app/homeserver.py b/synapse/app/homeserver.py
index 1045d28949..df524a23dd 100755
--- a/synapse/app/homeserver.py
+++ b/synapse/app/homeserver.py
@@ -176,6 +176,7 @@ class SynapseHomeServer(HomeServer):
 
             resources.update({
                 "/_matrix/client/api/v1": client_resource,
+                "/_synapse/password_reset": client_resource,
                 "/_matrix/client/r0": client_resource,
                 "/_matrix/client/unstable": client_resource,
                 "/_matrix/client/v2_alpha": client_resource,
diff --git a/synapse/config/emailconfig.py b/synapse/config/emailconfig.py
index 342a6ce5fd..ae04252906 100644
--- a/synapse/config/emailconfig.py
+++ b/synapse/config/emailconfig.py
@@ -1,5 +1,7 @@
 # -*- coding: utf-8 -*-
-# Copyright 2015, 2016 OpenMarket Ltd
+# Copyright 2015-2016 OpenMarket Ltd
+# Copyright 2017-2018 New Vector Ltd
+# Copyright 2019 The Matrix.org Foundation C.I.C.
 #
 # Licensed under the Apache License, Version 2.0 (the "License");
 # you may not use this file except in compliance with the License.
@@ -29,12 +31,76 @@ logger = logging.getLogger(__name__)
 
 class EmailConfig(Config):
     def read_config(self, config):
+        # TODO: We should separate better the email configuration from the notification
+        # and account validity config.
+
         self.email_enable_notifs = False
 
         email_config = config.get("email", {})
+
+        self.email_smtp_host = email_config.get("smtp_host", None)
+        self.email_smtp_port = email_config.get("smtp_port", None)
+        self.email_smtp_user = email_config.get("smtp_user", None)
+        self.email_smtp_pass = email_config.get("smtp_pass", None)
+        self.require_transport_security = email_config.get(
+            "require_transport_security", False
+        )
+        if "app_name" in email_config:
+            self.email_app_name = email_config["app_name"]
+        else:
+            self.email_app_name = "Matrix"
+
+        # TODO: Rename notif_from to something more generic, or have a separate
+        # from for password resets, message notifications, etc?
+        # Currently the email section is a bit bogged down with settings for
+        # multiple functions. Would be good to split it out into separate
+        # sections and only put the common ones under email:
+        self.email_notif_from = email_config.get("notif_from", None)
+        if self.email_notif_from is not None:
+            # make sure it's valid
+            parsed = email.utils.parseaddr(self.email_notif_from)
+            if parsed[1] == '':
+                raise RuntimeError("Invalid notif_from address")
+
+        template_dir = email_config.get("template_dir")
+        # we need an absolute path, because we change directory after starting (and
+        # we don't yet know what auxilliary templates like mail.css we will need).
+        # (Note that loading as package_resources with jinja.PackageLoader doesn't
+        # work for the same reason.)
+        if not template_dir:
+            template_dir = pkg_resources.resource_filename(
+                'synapse', 'res/templates'
+            )
+
+        self.email_template_dir = os.path.abspath(template_dir)
+
         self.email_enable_notifs = email_config.get("enable_notifs", False)
+        account_validity_renewal_enabled = config.get(
+            "account_validity", {},
+        ).get("renew_at")
 
-        if self.email_enable_notifs:
+        email_trust_identity_server_for_password_resets = email_config.get(
+            "trust_identity_server_for_password_resets", False,
+        )
+        self.email_password_reset_behaviour = (
+            "remote" if email_trust_identity_server_for_password_resets else "local"
+        )
+        if self.email_password_reset_behaviour == "local" and email_config == {}:
+            logger.warn(
+                "User password resets have been disabled due to lack of email config"
+            )
+            self.email_password_reset_behaviour = "off"
+
+        # Get lifetime of a validation token in milliseconds
+        self.email_validation_token_lifetime = self.parse_duration(
+            email_config.get("validation_token_lifetime", "1h")
+        )
+
+        if (
+            self.email_enable_notifs
+            or account_validity_renewal_enabled
+            or self.email_password_reset_behaviour == "local"
+        ):
             # make sure we can import the required deps
             import jinja2
             import bleach
@@ -42,6 +108,68 @@ class EmailConfig(Config):
             jinja2
             bleach
 
+        if self.email_password_reset_behaviour == "local":
+            required = [
+                "smtp_host",
+                "smtp_port",
+                "notif_from",
+            ]
+
+            missing = []
+            for k in required:
+                if k not in email_config:
+                    missing.append(k)
+
+            if (len(missing) > 0):
+                raise RuntimeError(
+                    "email.password_reset_behaviour is set to 'local' "
+                    "but required keys are missing: %s" %
+                    (", ".join(["email." + k for k in missing]),)
+                )
+
+            # Templates for password reset emails
+            self.email_password_reset_template_html = email_config.get(
+                "password_reset_template_html", "password_reset.html",
+            )
+            self.email_password_reset_template_text = email_config.get(
+                "password_reset_template_text", "password_reset.txt",
+            )
+            self.email_password_reset_failure_template = email_config.get(
+                "password_reset_failure_template", "password_reset_failure.html",
+            )
+            # This template does not support any replaceable variables, so we will
+            # read it from the disk once during setup
+            email_password_reset_success_template = email_config.get(
+                "password_reset_success_template", "password_reset_success.html",
+            )
+
+            # Check templates exist
+            for f in [self.email_password_reset_template_html,
+                      self.email_password_reset_template_text,
+                      self.email_password_reset_failure_template,
+                      email_password_reset_success_template]:
+                p = os.path.join(self.email_template_dir, f)
+                if not os.path.isfile(p):
+                    raise ConfigError("Unable to find template file %s" % (p, ))
+
+            # Retrieve content of web templates
+            filepath = os.path.join(
+                self.email_template_dir,
+                email_password_reset_success_template,
+            )
+            self.email_password_reset_success_html_content = self.read_file(
+                filepath,
+                "email.password_reset_template_success_html",
+            )
+
+            if config.get("public_baseurl") is None:
+                raise RuntimeError(
+                    "email.password_reset_behaviour is set to 'local' but no "
+                    "public_baseurl is set. This is necessary to generate password "
+                    "reset links"
+                )
+
+        if self.email_enable_notifs:
             required = [
                 "smtp_host",
                 "smtp_port",
@@ -66,34 +194,13 @@ class EmailConfig(Config):
                     "email.enable_notifs is True but no public_baseurl is set"
                 )
 
-            self.email_smtp_host = email_config["smtp_host"]
-            self.email_smtp_port = email_config["smtp_port"]
-            self.email_notif_from = email_config["notif_from"]
             self.email_notif_template_html = email_config["notif_template_html"]
             self.email_notif_template_text = email_config["notif_template_text"]
-            self.email_expiry_template_html = email_config.get(
-                "expiry_template_html", "notice_expiry.html",
-            )
-            self.email_expiry_template_text = email_config.get(
-                "expiry_template_text", "notice_expiry.txt",
-            )
-
-            template_dir = email_config.get("template_dir")
-            # we need an absolute path, because we change directory after starting (and
-            # we don't yet know what auxilliary templates like mail.css we will need).
-            # (Note that loading as package_resources with jinja.PackageLoader doesn't
-            # work for the same reason.)
-            if not template_dir:
-                template_dir = pkg_resources.resource_filename(
-                    'synapse', 'res/templates'
-                )
-            template_dir = os.path.abspath(template_dir)
 
             for f in self.email_notif_template_text, self.email_notif_template_html:
-                p = os.path.join(template_dir, f)
+                p = os.path.join(self.email_template_dir, f)
                 if not os.path.isfile(p):
                     raise ConfigError("Unable to find email template file %s" % (p, ))
-            self.email_template_dir = template_dir
 
             self.email_notif_for_new_users = email_config.get(
                 "notif_for_new_users", True
@@ -101,35 +208,24 @@ class EmailConfig(Config):
             self.email_riot_base_url = email_config.get(
                 "riot_base_url", None
             )
-            self.email_smtp_user = email_config.get(
-                "smtp_user", None
-            )
-            self.email_smtp_pass = email_config.get(
-                "smtp_pass", None
+
+        if account_validity_renewal_enabled:
+            self.email_expiry_template_html = email_config.get(
+                "expiry_template_html", "notice_expiry.html",
             )
-            self.require_transport_security = email_config.get(
-                "require_transport_security", False
+            self.email_expiry_template_text = email_config.get(
+                "expiry_template_text", "notice_expiry.txt",
             )
-            if "app_name" in email_config:
-                self.email_app_name = email_config["app_name"]
-            else:
-                self.email_app_name = "Matrix"
 
-            # make sure it's valid
-            parsed = email.utils.parseaddr(self.email_notif_from)
-            if parsed[1] == '':
-                raise RuntimeError("Invalid notif_from address")
-        else:
-            self.email_enable_notifs = False
-            # Not much point setting defaults for the rest: it would be an
-            # error for them to be used.
+            for f in self.email_expiry_template_text, self.email_expiry_template_html:
+                p = os.path.join(self.email_template_dir, f)
+                if not os.path.isfile(p):
+                    raise ConfigError("Unable to find email template file %s" % (p, ))
 
     def default_config(self, config_dir_path, server_name, **kwargs):
         return """
-        # Enable sending emails for notification events or expiry notices
-        # Defining a custom URL for Riot is only needed if email notifications
-        # should contain links to a self-hosted installation of Riot; when set
-        # the "app_name" setting is ignored.
+        # Enable sending emails for password resets, notification events or
+        # account expiry notices
         #
         # If your SMTP server requires authentication, the optional smtp_user &
         # smtp_pass variables should be used
@@ -137,20 +233,62 @@ class EmailConfig(Config):
         #email:
         #   enable_notifs: false
         #   smtp_host: "localhost"
-        #   smtp_port: 25
+        #   smtp_port: 25 # SSL: 465, STARTTLS: 587
         #   smtp_user: "exampleusername"
         #   smtp_pass: "examplepassword"
         #   require_transport_security: False
         #   notif_from: "Your Friendly %(app)s Home Server <noreply@example.com>"
         #   app_name: Matrix
-        #   # if template_dir is unset, uses the example templates that are part of
-        #   # the Synapse distribution.
+        #
+        #   # Enable email notifications by default
+        #   notif_for_new_users: True
+        #
+        #   # Defining a custom URL for Riot is only needed if email notifications
+        #   # should contain links to a self-hosted installation of Riot; when set
+        #   # the "app_name" setting is ignored
+        #   riot_base_url: "http://localhost/riot"
+        #
+        #   # Enable sending password reset emails via the configured, trusted
+        #   # identity servers
+        #   #
+        #   # IMPORTANT! This will give a malicious or overtaken identity server
+        #   # the ability to reset passwords for your users! Make absolutely sure
+        #   # that you want to do this! It is strongly recommended that password
+        #   # reset emails be sent by the homeserver instead
+        #   #
+        #   # If this option is set to false and SMTP options have not been
+        #   # configured, resetting user passwords via email will be disabled
+        #   #trust_identity_server_for_password_resets: false
+        #
+        #   # Configure the time that a validation email or text message code
+        #   # will expire after sending
+        #   #
+        #   # This is currently used for password resets
+        #   #validation_token_lifetime: 1h
+        #
+        #   # Template directory. All template files should be stored within this
+        #   # directory
+        #   #
         #   #template_dir: res/templates
+        #
+        #   # Templates for email notifications
+        #   #
         #   notif_template_html: notif_mail.html
         #   notif_template_text: notif_mail.txt
-        #   # Templates for account expiry notices.
+        #
+        #   # Templates for account expiry notices
+        #   #
         #   expiry_template_html: notice_expiry.html
         #   expiry_template_text: notice_expiry.txt
-        #   notif_for_new_users: True
-        #   riot_base_url: "http://localhost/riot"
+        #
+        #   # Templates for password reset emails sent by the homeserver
+        #   #
+        #   #password_reset_template_html: password_reset.html
+        #   #password_reset_template_text: password_reset.txt
+        #
+        #   # Templates for password reset success and failure pages that a user
+        #   # will see after attempting to reset their password
+        #   #
+        #   #password_reset_template_success_html: password_reset_success.html
+        #   #password_reset_template_failure_html: password_reset_failure.html
         """
diff --git a/synapse/config/key.py b/synapse/config/key.py
index eb10259818..aba7092ccd 100644
--- a/synapse/config/key.py
+++ b/synapse/config/key.py
@@ -1,5 +1,6 @@
 # -*- coding: utf-8 -*-
 # Copyright 2015, 2016 OpenMarket Ltd
+# Copyright 2019 The Matrix.org Foundation C.I.C.
 #
 # Licensed under the Apache License, Version 2.0 (the "License");
 # you may not use this file except in compliance with the License.
@@ -17,6 +18,8 @@ import hashlib
 import logging
 import os
 
+import attr
+import jsonschema
 from signedjson.key import (
     NACL_ED25519,
     decode_signing_key_base64,
@@ -32,11 +35,27 @@ from synapse.util.stringutils import random_string, random_string_with_symbols
 
 from ._base import Config, ConfigError
 
+INSECURE_NOTARY_ERROR = """\
+Your server is configured to accept key server responses without signature
+validation or TLS certificate validation. This is likely to be very insecure. If
+you are *sure* you want to do this, set 'accept_keys_insecurely' on the
+keyserver configuration."""
+
+
 logger = logging.getLogger(__name__)
 
 
-class KeyConfig(Config):
+@attr.s
+class TrustedKeyServer(object):
+    # string: name of the server.
+    server_name = attr.ib()
 
+    # dict[str,VerifyKey]|None: map from key id to key object, or None to disable
+    # signature verification.
+    verify_keys = attr.ib(default=None)
+
+
+class KeyConfig(Config):
     def read_config(self, config):
         # the signing key can be specified inline or in a separate file
         if "signing_key" in config:
@@ -49,16 +68,27 @@ class KeyConfig(Config):
             config.get("old_signing_keys", {})
         )
         self.key_refresh_interval = self.parse_duration(
-            config.get("key_refresh_interval", "1d"),
+            config.get("key_refresh_interval", "1d")
         )
-        self.perspectives = self.read_perspectives(
-            config.get("perspectives", {}).get("servers", {
-                "matrix.org": {"verify_keys": {
-                    "ed25519:auto": {
-                        "key": "Noi6WqcDj0QmPxCNQqgezwTlBKrfqehY1u2FyWP9uYw",
-                    }
-                }}
-            })
+
+        # if neither trusted_key_servers nor perspectives are given, use the default.
+        if "perspectives" not in config and "trusted_key_servers" not in config:
+            key_servers = [{"server_name": "matrix.org"}]
+        else:
+            key_servers = config.get("trusted_key_servers", [])
+
+            if not isinstance(key_servers, list):
+                raise ConfigError(
+                    "trusted_key_servers, if given, must be a list, not a %s"
+                    % (type(key_servers).__name__,)
+                )
+
+            # merge the 'perspectives' config into the 'trusted_key_servers' config.
+            key_servers.extend(_perspectives_to_key_servers(config))
+
+        # list of TrustedKeyServer objects
+        self.key_servers = list(
+            _parse_key_servers(key_servers, self.federation_verify_certificates)
         )
 
         self.macaroon_secret_key = config.get(
@@ -78,8 +108,9 @@ class KeyConfig(Config):
         # falsification of values
         self.form_secret = config.get("form_secret", None)
 
-    def default_config(self, config_dir_path, server_name, generate_secrets=False,
-                       **kwargs):
+    def default_config(
+        self, config_dir_path, server_name, generate_secrets=False, **kwargs
+    ):
         base_key_name = os.path.join(config_dir_path, server_name)
 
         if generate_secrets:
@@ -91,7 +122,8 @@ class KeyConfig(Config):
             macaroon_secret_key = "# macaroon_secret_key: <PRIVATE STRING>"
             form_secret = "# form_secret: <PRIVATE STRING>"
 
-        return """\
+        return (
+            """\
         # a secret which is used to sign access tokens. If none is specified,
         # the registration_shared_secret is used, if one is given; otherwise,
         # a secret key is derived from the signing key.
@@ -133,33 +165,53 @@ class KeyConfig(Config):
 
         # The trusted servers to download signing keys from.
         #
-        #perspectives:
-        #  servers:
-        #    "matrix.org":
-        #      verify_keys:
-        #        "ed25519:auto":
-        #          key: "Noi6WqcDj0QmPxCNQqgezwTlBKrfqehY1u2FyWP9uYw"
-        """ % locals()
-
-    def read_perspectives(self, perspectives_servers):
-        servers = {}
-        for server_name, server_config in perspectives_servers.items():
-            for key_id, key_data in server_config["verify_keys"].items():
-                if is_signing_algorithm_supported(key_id):
-                    key_base64 = key_data["key"]
-                    key_bytes = decode_base64(key_base64)
-                    verify_key = decode_verify_key_bytes(key_id, key_bytes)
-                    servers.setdefault(server_name, {})[key_id] = verify_key
-        return servers
+        # When we need to fetch a signing key, each server is tried in parallel.
+        #
+        # Normally, the connection to the key server is validated via TLS certificates.
+        # Additional security can be provided by configuring a `verify key`, which
+        # will make synapse check that the response is signed by that key.
+        #
+        # This setting supercedes an older setting named `perspectives`. The old format
+        # is still supported for backwards-compatibility, but it is deprecated.
+        #
+        # Options for each entry in the list include:
+        #
+        #    server_name: the name of the server. required.
+        #
+        #    verify_keys: an optional map from key id to base64-encoded public key.
+        #       If specified, we will check that the response is signed by at least
+        #       one of the given keys.
+        #
+        #    accept_keys_insecurely: a boolean. Normally, if `verify_keys` is unset,
+        #       and federation_verify_certificates is not `true`, synapse will refuse
+        #       to start, because this would allow anyone who can spoof DNS responses
+        #       to masquerade as the trusted key server. If you know what you are doing
+        #       and are sure that your network environment provides a secure connection
+        #       to the key server, you can set this to `true` to override this
+        #       behaviour.
+        #
+        # An example configuration might look like:
+        #
+        #trusted_key_servers:
+        #  - server_name: "my_trusted_server.example.com"
+        #    verify_keys:
+        #      "ed25519:auto": "abcdefghijklmnopqrstuvwxyzabcdefghijklmopqr"
+        #  - server_name: "my_other_trusted_server.example.com"
+        #
+        # The default configuration is:
+        #
+        #trusted_key_servers:
+        #  - server_name: "matrix.org"
+        """
+            % locals()
+        )
 
     def read_signing_key(self, signing_key_path):
         signing_keys = self.read_file(signing_key_path, "signing_key")
         try:
             return read_signing_keys(signing_keys.splitlines(True))
         except Exception as e:
-            raise ConfigError(
-                "Error reading signing_key: %s" % (str(e))
-            )
+            raise ConfigError("Error reading signing_key: %s" % (str(e)))
 
     def read_old_signing_keys(self, old_signing_keys):
         keys = {}
@@ -182,9 +234,7 @@ class KeyConfig(Config):
         if not self.path_exists(signing_key_path):
             with open(signing_key_path, "w") as signing_key_file:
                 key_id = "a_" + random_string(4)
-                write_signing_keys(
-                    signing_key_file, (generate_signing_key(key_id),),
-                )
+                write_signing_keys(signing_key_file, (generate_signing_key(key_id),))
         else:
             signing_keys = self.read_file(signing_key_path, "signing_key")
             if len(signing_keys.split("\n")[0].split()) == 1:
@@ -194,6 +244,106 @@ class KeyConfig(Config):
                     NACL_ED25519, key_id, signing_keys.split("\n")[0]
                 )
                 with open(signing_key_path, "w") as signing_key_file:
-                    write_signing_keys(
-                        signing_key_file, (key,),
+                    write_signing_keys(signing_key_file, (key,))
+
+
+def _perspectives_to_key_servers(config):
+    """Convert old-style 'perspectives' configs into new-style 'trusted_key_servers'
+
+    Returns an iterable of entries to add to trusted_key_servers.
+    """
+
+    # 'perspectives' looks like:
+    #
+    # {
+    #     "servers": {
+    #         "matrix.org": {
+    #             "verify_keys": {
+    #                 "ed25519:auto": {
+    #                     "key": "Noi6WqcDj0QmPxCNQqgezwTlBKrfqehY1u2FyWP9uYw"
+    #                 }
+    #             }
+    #         }
+    #     }
+    # }
+    #
+    # 'trusted_keys' looks like:
+    #
+    # [
+    #     {
+    #         "server_name": "matrix.org",
+    #         "verify_keys": {
+    #             "ed25519:auto": "Noi6WqcDj0QmPxCNQqgezwTlBKrfqehY1u2FyWP9uYw",
+    #         }
+    #     }
+    # ]
+
+    perspectives_servers = config.get("perspectives", {}).get("servers", {})
+
+    for server_name, server_opts in perspectives_servers.items():
+        trusted_key_server_entry = {"server_name": server_name}
+        verify_keys = server_opts.get("verify_keys")
+        if verify_keys is not None:
+            trusted_key_server_entry["verify_keys"] = {
+                key_id: key_data["key"] for key_id, key_data in verify_keys.items()
+            }
+        yield trusted_key_server_entry
+
+
+TRUSTED_KEY_SERVERS_SCHEMA = {
+    "$schema": "http://json-schema.org/draft-04/schema#",
+    "description": "schema for the trusted_key_servers setting",
+    "type": "array",
+    "items": {
+        "type": "object",
+        "properties": {
+            "server_name": {"type": "string"},
+            "verify_keys": {
+                "type": "object",
+                # each key must be a base64 string
+                "additionalProperties": {"type": "string"},
+            },
+        },
+        "required": ["server_name"],
+    },
+}
+
+
+def _parse_key_servers(key_servers, federation_verify_certificates):
+    try:
+        jsonschema.validate(key_servers, TRUSTED_KEY_SERVERS_SCHEMA)
+    except jsonschema.ValidationError as e:
+        raise ConfigError("Unable to parse 'trusted_key_servers': " + e.message)
+
+    for server in key_servers:
+        server_name = server["server_name"]
+        result = TrustedKeyServer(server_name=server_name)
+
+        verify_keys = server.get("verify_keys")
+        if verify_keys is not None:
+            result.verify_keys = {}
+            for key_id, key_base64 in verify_keys.items():
+                if not is_signing_algorithm_supported(key_id):
+                    raise ConfigError(
+                        "Unsupported signing algorithm on key %s for server %s in "
+                        "trusted_key_servers" % (key_id, server_name)
                     )
+                try:
+                    key_bytes = decode_base64(key_base64)
+                    verify_key = decode_verify_key_bytes(key_id, key_bytes)
+                except Exception as e:
+                    raise ConfigError(
+                        "Unable to parse key %s for server %s in "
+                        "trusted_key_servers: %s" % (key_id, server_name, e)
+                    )
+
+                result.verify_keys[key_id] = verify_key
+
+        if (
+            not verify_keys
+            and not server.get("accept_keys_insecurely")
+            and not federation_verify_certificates
+        ):
+            raise ConfigError(INSECURE_NOTARY_ERROR)
+
+        yield result
diff --git a/synapse/config/server.py b/synapse/config/server.py
index e763e19e15..334921d421 100644
--- a/synapse/config/server.py
+++ b/synapse/config/server.py
@@ -585,6 +585,22 @@ class ServerConfig(Config):
 
         # Monthly Active User Blocking
         #
+        # Used in cases where the admin or server owner wants to limit to the
+        # number of monthly active users.
+        #
+        # 'limit_usage_by_mau' disables/enables monthly active user blocking. When
+        # anabled and a limit is reached the server returns a 'ResourceLimitError'
+        # with error type Codes.RESOURCE_LIMIT_EXCEEDED
+        #
+        # 'max_mau_value' is the hard limit of monthly active users above which
+        # the server will start blocking user actions.
+        #
+        # 'mau_trial_days' is a means to add a grace period for active users. It
+        # means that users must be active for this number of days before they
+        # can be considered active and guards against the case where lots of users
+        # sign up in a short space of time never to return after their initial
+        # session.
+        #
         #limit_usage_by_mau: False
         #max_mau_value: 50
         #mau_trial_days: 2
diff --git a/synapse/config/tls.py b/synapse/config/tls.py
index 72dd5926f9..658f9dd361 100644
--- a/synapse/config/tls.py
+++ b/synapse/config/tls.py
@@ -74,7 +74,7 @@ class TlsConfig(Config):
 
         # Whether to verify certificates on outbound federation traffic
         self.federation_verify_certificates = config.get(
-            "federation_verify_certificates", False,
+            "federation_verify_certificates", True,
         )
 
         # Whitelist of domains to not verify certificates for
@@ -107,7 +107,7 @@ class TlsConfig(Config):
             certs = []
             for ca_file in custom_ca_list:
                 logger.debug("Reading custom CA certificate file: %s", ca_file)
-                content = self.read_file(ca_file)
+                content = self.read_file(ca_file, "federation_custom_ca_list")
 
                 # Parse the CA certificates
                 try:
@@ -241,12 +241,12 @@ class TlsConfig(Config):
         #
         #tls_private_key_path: "%(tls_private_key_path)s"
 
-        # Whether to verify TLS certificates when sending federation traffic.
+        # Whether to verify TLS server certificates for outbound federation requests.
         #
-        # This currently defaults to `false`, however this will change in
-        # Synapse 1.0 when valid federation certificates will be required.
+        # Defaults to `true`. To disable certificate verification, uncomment the
+        # following line.
         #
-        #federation_verify_certificates: true
+        #federation_verify_certificates: false
 
         # Skip federation certificate verification on the following whitelist
         # of domains.
diff --git a/synapse/crypto/event_signing.py b/synapse/crypto/event_signing.py
index 1dfa727fcf..99a586655b 100644
--- a/synapse/crypto/event_signing.py
+++ b/synapse/crypto/event_signing.py
@@ -31,7 +31,11 @@ logger = logging.getLogger(__name__)
 def check_event_content_hash(event, hash_algorithm=hashlib.sha256):
     """Check whether the hash for this PDU matches the contents"""
     name, expected_hash = compute_content_hash(event.get_pdu_json(), hash_algorithm)
-    logger.debug("Expecting hash: %s", encode_base64(expected_hash))
+    logger.debug(
+        "Verifying content hash on %s (expecting: %s)",
+        event.event_id,
+        encode_base64(expected_hash),
+    )
 
     # some malformed events lack a 'hashes'. Protect against it being missing
     # or a weird type by basically treating it the same as an unhashed event.
diff --git a/synapse/crypto/keyring.py b/synapse/crypto/keyring.py
index b2f4cea536..96964b0d50 100644
--- a/synapse/crypto/keyring.py
+++ b/synapse/crypto/keyring.py
@@ -15,6 +15,7 @@
 # limitations under the License.
 
 import logging
+from collections import defaultdict
 
 import six
 from six import raise_from
@@ -45,6 +46,7 @@ from synapse.api.errors import (
 )
 from synapse.storage.keys import FetchKeyResult
 from synapse.util import logcontext, unwrapFirstError
+from synapse.util.async_helpers import yieldable_gather_results
 from synapse.util.logcontext import (
     LoggingContext,
     PreserveLoggingContext,
@@ -58,9 +60,9 @@ logger = logging.getLogger(__name__)
 
 
 @attr.s(slots=True, cmp=False)
-class VerifyKeyRequest(object):
+class VerifyJsonRequest(object):
     """
-    A request for a verify key to verify a JSON object.
+    A request to verify a JSON object.
 
     Attributes:
         server_name(str): The name of the server to verify against.
@@ -70,7 +72,10 @@ class VerifyKeyRequest(object):
 
         json_object(dict): The JSON object to verify.
 
-        deferred(Deferred[str, str, nacl.signing.VerifyKey]):
+        minimum_valid_until_ts (int): time at which we require the signing key to
+            be valid. (0 implies we don't care)
+
+        key_ready (Deferred[str, str, nacl.signing.VerifyKey]):
             A deferred (server_name, key_id, verify_key) tuple that resolves when
             a verify key has been fetched. The deferreds' callbacks are run with no
             logcontext.
@@ -80,9 +85,14 @@ class VerifyKeyRequest(object):
     """
 
     server_name = attr.ib()
-    key_ids = attr.ib()
     json_object = attr.ib()
-    deferred = attr.ib()
+    minimum_valid_until_ts = attr.ib()
+    request_name = attr.ib()
+    key_ids = attr.ib(init=False)
+    key_ready = attr.ib(default=attr.Factory(defer.Deferred))
+
+    def __attrs_post_init__(self):
+        self.key_ids = signature_ids(self.json_object, self.server_name)
 
 
 class KeyLookupError(ValueError):
@@ -90,14 +100,16 @@ class KeyLookupError(ValueError):
 
 
 class Keyring(object):
-    def __init__(self, hs):
+    def __init__(self, hs, key_fetchers=None):
         self.clock = hs.get_clock()
 
-        self._key_fetchers = (
-            StoreKeyFetcher(hs),
-            PerspectivesKeyFetcher(hs),
-            ServerKeyFetcher(hs),
-        )
+        if key_fetchers is None:
+            key_fetchers = (
+                StoreKeyFetcher(hs),
+                PerspectivesKeyFetcher(hs),
+                ServerKeyFetcher(hs),
+            )
+        self._key_fetchers = key_fetchers
 
         # map from server name to Deferred. Has an entry for each server with
         # an ongoing key download; the Deferred completes once the download
@@ -106,51 +118,99 @@ class Keyring(object):
         # These are regular, logcontext-agnostic Deferreds.
         self.key_downloads = {}
 
-    def verify_json_for_server(self, server_name, json_object):
-        return logcontext.make_deferred_yieldable(
-            self.verify_json_objects_for_server([(server_name, json_object)])[0]
-        )
+    def verify_json_for_server(
+        self, server_name, json_object, validity_time, request_name
+    ):
+        """Verify that a JSON object has been signed by a given server
+
+        Args:
+            server_name (str): name of the server which must have signed this object
+
+            json_object (dict): object to be checked
+
+            validity_time (int): timestamp at which we require the signing key to
+                be valid. (0 implies we don't care)
+
+            request_name (str): an identifier for this json object (eg, an event id)
+                for logging.
+
+        Returns:
+            Deferred[None]: completes if the the object was correctly signed, otherwise
+                errbacks with an error
+        """
+        req = VerifyJsonRequest(server_name, json_object, validity_time, request_name)
+        requests = (req,)
+        return logcontext.make_deferred_yieldable(self._verify_objects(requests)[0])
 
     def verify_json_objects_for_server(self, server_and_json):
         """Bulk verifies signatures of json objects, bulk fetching keys as
         necessary.
 
         Args:
-            server_and_json (list): List of pairs of (server_name, json_object)
+            server_and_json (iterable[Tuple[str, dict, int, str]):
+                Iterable of (server_name, json_object, validity_time, request_name)
+                tuples.
+
+                validity_time is a timestamp at which the signing key must be
+                valid.
+
+                request_name is an identifier for this json object (eg, an event id)
+                for logging.
 
         Returns:
-            List<Deferred>: for each input pair, a deferred indicating success
+            List<Deferred[None]>: for each input triplet, a deferred indicating success
                 or failure to verify each json object's signature for the given
                 server_name. The deferreds run their callbacks in the sentinel
                 logcontext.
         """
-        # a list of VerifyKeyRequests
-        verify_requests = []
+        return self._verify_objects(
+            VerifyJsonRequest(server_name, json_object, validity_time, request_name)
+            for server_name, json_object, validity_time, request_name in server_and_json
+        )
+
+    def _verify_objects(self, verify_requests):
+        """Does the work of verify_json_[objects_]for_server
+
+
+        Args:
+            verify_requests (iterable[VerifyJsonRequest]):
+                Iterable of verification requests.
+
+        Returns:
+            List<Deferred[None]>: for each input item, a deferred indicating success
+                or failure to verify each json object's signature for the given
+                server_name. The deferreds run their callbacks in the sentinel
+                logcontext.
+        """
+        # a list of VerifyJsonRequests which are awaiting a key lookup
+        key_lookups = []
         handle = preserve_fn(_handle_key_deferred)
 
-        def process(server_name, json_object):
+        def process(verify_request):
             """Process an entry in the request list
 
-            Given a (server_name, json_object) pair from the request list,
-            adds a key request to verify_requests, and returns a deferred which will
-            complete or fail (in the sentinel context) when verification completes.
+            Adds a key request to key_lookups, and returns a deferred which
+            will complete or fail (in the sentinel context) when verification completes.
             """
-            key_ids = signature_ids(json_object, server_name)
-
-            if not key_ids:
+            if not verify_request.key_ids:
                 return defer.fail(
                     SynapseError(
-                        400, "Not signed by %s" % (server_name,), Codes.UNAUTHORIZED
+                        400,
+                        "Not signed by %s" % (verify_request.server_name,),
+                        Codes.UNAUTHORIZED,
                     )
                 )
 
-            logger.debug("Verifying for %s with key_ids %s", server_name, key_ids)
+            logger.debug(
+                "Verifying %s for %s with key_ids %s, min_validity %i",
+                verify_request.request_name,
+                verify_request.server_name,
+                verify_request.key_ids,
+                verify_request.minimum_valid_until_ts,
+            )
 
             # add the key request to the queue, but don't start it off yet.
-            verify_request = VerifyKeyRequest(
-                server_name, key_ids, json_object, defer.Deferred()
-            )
-            verify_requests.append(verify_request)
+            key_lookups.append(verify_request)
 
             # now run _handle_key_deferred, which will wait for the key request
             # to complete and then do the verification.
@@ -159,13 +219,10 @@ class Keyring(object):
             # wrap it with preserve_fn (aka run_in_background)
             return handle(verify_request)
 
-        results = [
-            process(server_name, json_object)
-            for server_name, json_object in server_and_json
-        ]
+        results = [process(r) for r in verify_requests]
 
-        if verify_requests:
-            run_in_background(self._start_key_lookups, verify_requests)
+        if key_lookups:
+            run_in_background(self._start_key_lookups, key_lookups)
 
         return results
 
@@ -173,10 +230,10 @@ class Keyring(object):
     def _start_key_lookups(self, verify_requests):
         """Sets off the key fetches for each verify request
 
-        Once each fetch completes, verify_request.deferred will be resolved.
+        Once each fetch completes, verify_request.key_ready will be resolved.
 
         Args:
-            verify_requests (List[VerifyKeyRequest]):
+            verify_requests (List[VerifyJsonRequest]):
         """
 
         try:
@@ -219,7 +276,7 @@ class Keyring(object):
                 return res
 
             for verify_request in verify_requests:
-                verify_request.deferred.addBoth(remove_deferreds, verify_request)
+                verify_request.key_ready.addBoth(remove_deferreds, verify_request)
         except Exception:
             logger.exception("Error starting key lookups")
 
@@ -272,16 +329,16 @@ class Keyring(object):
     def _get_server_verify_keys(self, verify_requests):
         """Tries to find at least one key for each verify request
 
-        For each verify_request, verify_request.deferred is called back with
+        For each verify_request, verify_request.key_ready is called back with
         params (server_name, key_id, VerifyKey) if a key is found, or errbacked
         with a SynapseError if none of the keys are found.
 
         Args:
-            verify_requests (list[VerifyKeyRequest]): list of verify requests
+            verify_requests (list[VerifyJsonRequest]): list of verify requests
         """
 
         remaining_requests = set(
-            (rq for rq in verify_requests if not rq.deferred.called)
+            (rq for rq in verify_requests if not rq.key_ready.called)
         )
 
         @defer.inlineCallbacks
@@ -295,11 +352,15 @@ class Keyring(object):
                 # look for any requests which weren't satisfied
                 with PreserveLoggingContext():
                     for verify_request in remaining_requests:
-                        verify_request.deferred.errback(
+                        verify_request.key_ready.errback(
                             SynapseError(
                                 401,
-                                "No key for %s with id %s"
-                                % (verify_request.server_name, verify_request.key_ids),
+                                "No key for %s with ids in %s (min_validity %i)"
+                                % (
+                                    verify_request.server_name,
+                                    verify_request.key_ids,
+                                    verify_request.minimum_valid_until_ts,
+                                ),
                                 Codes.UNAUTHORIZED,
                             )
                         )
@@ -311,8 +372,8 @@ class Keyring(object):
             logger.error("Unexpected error in _get_server_verify_keys: %s", err)
             with PreserveLoggingContext():
                 for verify_request in remaining_requests:
-                    if not verify_request.deferred.called:
-                        verify_request.deferred.errback(err)
+                    if not verify_request.key_ready.called:
+                        verify_request.key_ready.errback(err)
 
         run_in_background(do_iterations).addErrback(on_err)
 
@@ -322,47 +383,66 @@ class Keyring(object):
 
         Args:
             fetcher (KeyFetcher): fetcher to use to fetch the keys
-            remaining_requests (set[VerifyKeyRequest]): outstanding key requests.
-                Any successfully-completed requests will be reomved from the list.
+            remaining_requests (set[VerifyJsonRequest]): outstanding key requests.
+                Any successfully-completed requests will be removed from the list.
         """
-        # dict[str, set(str)]: keys to fetch for each server
-        missing_keys = {}
+        # dict[str, dict[str, int]]: keys to fetch.
+        # server_name -> key_id -> min_valid_ts
+        missing_keys = defaultdict(dict)
+
         for verify_request in remaining_requests:
             # any completed requests should already have been removed
-            assert not verify_request.deferred.called
-            missing_keys.setdefault(verify_request.server_name, set()).update(
-                verify_request.key_ids
-            )
+            assert not verify_request.key_ready.called
+            keys_for_server = missing_keys[verify_request.server_name]
+
+            for key_id in verify_request.key_ids:
+                # If we have several requests for the same key, then we only need to
+                # request that key once, but we should do so with the greatest
+                # min_valid_until_ts of the requests, so that we can satisfy all of
+                # the requests.
+                keys_for_server[key_id] = max(
+                    keys_for_server.get(key_id, -1),
+                    verify_request.minimum_valid_until_ts,
+                )
 
-        results = yield fetcher.get_keys(missing_keys.items())
+        results = yield fetcher.get_keys(missing_keys)
 
         completed = list()
         for verify_request in remaining_requests:
             server_name = verify_request.server_name
 
             # see if any of the keys we got this time are sufficient to
-            # complete this VerifyKeyRequest.
+            # complete this VerifyJsonRequest.
             result_keys = results.get(server_name, {})
             for key_id in verify_request.key_ids:
-                key = result_keys.get(key_id)
-                if key:
-                    with PreserveLoggingContext():
-                        verify_request.deferred.callback(
-                            (server_name, key_id, key.verify_key)
-                        )
-                    completed.append(verify_request)
-                    break
+                fetch_key_result = result_keys.get(key_id)
+                if not fetch_key_result:
+                    # we didn't get a result for this key
+                    continue
+
+                if (
+                    fetch_key_result.valid_until_ts
+                    < verify_request.minimum_valid_until_ts
+                ):
+                    # key was not valid at this point
+                    continue
+
+                with PreserveLoggingContext():
+                    verify_request.key_ready.callback(
+                        (server_name, key_id, fetch_key_result.verify_key)
+                    )
+                completed.append(verify_request)
+                break
 
         remaining_requests.difference_update(completed)
 
 
 class KeyFetcher(object):
-    def get_keys(self, server_name_and_key_ids):
+    def get_keys(self, keys_to_fetch):
         """
         Args:
-            server_name_and_key_ids (iterable[Tuple[str, iterable[str]]]):
-                list of (server_name, iterable[key_id]) tuples to fetch keys for
-                Note that the iterables may be iterated more than once.
+            keys_to_fetch (dict[str, dict[str, int]]):
+                the keys to be fetched. server_name -> key_id -> min_valid_ts
 
         Returns:
             Deferred[dict[str, dict[str, synapse.storage.keys.FetchKeyResult|None]]]:
@@ -378,13 +458,15 @@ class StoreKeyFetcher(KeyFetcher):
         self.store = hs.get_datastore()
 
     @defer.inlineCallbacks
-    def get_keys(self, server_name_and_key_ids):
+    def get_keys(self, keys_to_fetch):
         """see KeyFetcher.get_keys"""
+
         keys_to_fetch = (
             (server_name, key_id)
-            for server_name, key_ids in server_name_and_key_ids
-            for key_id in key_ids
+            for server_name, keys_for_server in keys_to_fetch.items()
+            for key_id in keys_for_server.keys()
         )
+
         res = yield self.store.get_server_verify_keys(keys_to_fetch)
         keys = {}
         for (server_name, key_id), key in res.items():
@@ -398,9 +480,7 @@ class BaseV2KeyFetcher(object):
         self.config = hs.get_config()
 
     @defer.inlineCallbacks
-    def process_v2_response(
-        self, from_server, response_json, time_added_ms
-    ):
+    def process_v2_response(self, from_server, response_json, time_added_ms):
         """Parse a 'Server Keys' structure from the result of a /key request
 
         This is used to parse either the entirety of the response from
@@ -505,25 +585,27 @@ class PerspectivesKeyFetcher(BaseV2KeyFetcher):
         super(PerspectivesKeyFetcher, self).__init__(hs)
         self.clock = hs.get_clock()
         self.client = hs.get_http_client()
-        self.perspective_servers = self.config.perspectives
+        self.key_servers = self.config.key_servers
 
     @defer.inlineCallbacks
-    def get_keys(self, server_name_and_key_ids):
+    def get_keys(self, keys_to_fetch):
         """see KeyFetcher.get_keys"""
 
         @defer.inlineCallbacks
-        def get_key(perspective_name, perspective_keys):
+        def get_key(key_server):
             try:
                 result = yield self.get_server_verify_key_v2_indirect(
-                    server_name_and_key_ids, perspective_name, perspective_keys
+                    keys_to_fetch, key_server
                 )
                 defer.returnValue(result)
             except KeyLookupError as e:
-                logger.warning("Key lookup failed from %r: %s", perspective_name, e)
+                logger.warning(
+                    "Key lookup failed from %r: %s", key_server.server_name, e
+                )
             except Exception as e:
                 logger.exception(
                     "Unable to get key from %r: %s %s",
-                    perspective_name,
+                    key_server.server_name,
                     type(e).__name__,
                     str(e),
                 )
@@ -533,8 +615,8 @@ class PerspectivesKeyFetcher(BaseV2KeyFetcher):
         results = yield logcontext.make_deferred_yieldable(
             defer.gatherResults(
                 [
-                    run_in_background(get_key, p_name, p_keys)
-                    for p_name, p_keys in self.perspective_servers.items()
+                    run_in_background(get_key, server)
+                    for server in self.key_servers
                 ],
                 consumeErrors=True,
             ).addErrback(unwrapFirstError)
@@ -549,15 +631,15 @@ class PerspectivesKeyFetcher(BaseV2KeyFetcher):
 
     @defer.inlineCallbacks
     def get_server_verify_key_v2_indirect(
-        self, server_names_and_key_ids, perspective_name, perspective_keys
+        self, keys_to_fetch, key_server
     ):
         """
         Args:
-            server_names_and_key_ids (iterable[Tuple[str, iterable[str]]]):
-                list of (server_name, iterable[key_id]) tuples to fetch keys for
-            perspective_name (str): name of the notary server to query for the keys
-            perspective_keys (dict[str, VerifyKey]): map of key_id->key for the
-                notary server
+            keys_to_fetch (dict[str, dict[str, int]]):
+                the keys to be fetched. server_name -> key_id -> min_valid_ts
+
+            key_server (synapse.config.key.TrustedKeyServer): notary server to query for
+                the keys
 
         Returns:
             Deferred[dict[str, dict[str, synapse.storage.keys.FetchKeyResult]]]: map
@@ -567,14 +649,13 @@ class PerspectivesKeyFetcher(BaseV2KeyFetcher):
             KeyLookupError if there was an error processing the entire response from
                 the server
         """
+        perspective_name = key_server.server_name
         logger.info(
             "Requesting keys %s from notary server %s",
-            server_names_and_key_ids,
+            keys_to_fetch.items(),
             perspective_name,
         )
-        # TODO(mark): Set the minimum_valid_until_ts to that needed by
-        # the events being validated or the current time if validating
-        # an incoming request.
+
         try:
             query_response = yield self.client.post_json(
                 destination=perspective_name,
@@ -582,12 +663,12 @@ class PerspectivesKeyFetcher(BaseV2KeyFetcher):
                 data={
                     u"server_keys": {
                         server_name: {
-                            key_id: {u"minimum_valid_until_ts": 0} for key_id in key_ids
+                            key_id: {u"minimum_valid_until_ts": min_valid_ts}
+                            for key_id, min_valid_ts in server_keys.items()
                         }
-                        for server_name, key_ids in server_names_and_key_ids
+                        for server_name, server_keys in keys_to_fetch.items()
                     }
                 },
-                long_retries=True,
             )
         except (NotRetryingDestination, RequestSendFailed) as e:
             raise_from(KeyLookupError("Failed to connect to remote server"), e)
@@ -609,11 +690,13 @@ class PerspectivesKeyFetcher(BaseV2KeyFetcher):
                 )
 
             try:
-                processed_response = yield self._process_perspectives_response(
-                    perspective_name,
-                    perspective_keys,
+                self._validate_perspectives_response(
+                    key_server,
                     response,
-                    time_added_ms=time_now_ms,
+                )
+
+                processed_response = yield self.process_v2_response(
+                    perspective_name, response, time_added_ms=time_now_ms
                 )
             except KeyLookupError as e:
                 logger.warning(
@@ -637,28 +720,24 @@ class PerspectivesKeyFetcher(BaseV2KeyFetcher):
 
         defer.returnValue(keys)
 
-    def _process_perspectives_response(
-        self, perspective_name, perspective_keys, response, time_added_ms
+    def _validate_perspectives_response(
+        self, key_server, response,
     ):
-        """Parse a 'Server Keys' structure from the result of a /key/query request
-
-        Checks that the entry is correctly signed by the perspectives server, and then
-        passes over to process_v2_response
+        """Optionally check the signature on the result of a /key/query request
 
         Args:
-            perspective_name (str): the name of the notary server that produced this
-                result
-
-            perspective_keys (dict[str, VerifyKey]): map of key_id->key for the
-                notary server
+            key_server (synapse.config.key.TrustedKeyServer): the notary server that
+                produced this result
 
             response (dict): the json-decoded Server Keys response object
+        """
+        perspective_name = key_server.server_name
+        perspective_keys = key_server.verify_keys
 
-            time_added_ms (int): the timestamp to record in server_keys_json
+        if perspective_keys is None:
+            # signature checking is disabled on this server
+            return
 
-        Returns:
-            Deferred[dict[str, FetchKeyResult]]: map from key_id to result object
-        """
         if (
             u"signatures" not in response
             or perspective_name not in response[u"signatures"]
@@ -671,6 +750,13 @@ class PerspectivesKeyFetcher(BaseV2KeyFetcher):
                 verify_signed_json(response, perspective_name, perspective_keys[key_id])
                 verified = True
 
+                if perspective_name == "matrix.org" and key_id == "ed25519:auto":
+                    logger.warning(
+                        "Trusting trusted_key_server responses signed by the "
+                        "compromised matrix.org signing key 'ed25519:auto'. "
+                        "This is a placebo."
+                    )
+
         if not verified:
             raise KeyLookupError(
                 "Response not signed with a known key: signed with: %r, known keys: %r"
@@ -680,10 +766,6 @@ class PerspectivesKeyFetcher(BaseV2KeyFetcher):
                 )
             )
 
-        return self.process_v2_response(
-            perspective_name, response, time_added_ms=time_added_ms
-        )
-
 
 class ServerKeyFetcher(BaseV2KeyFetcher):
     """KeyFetcher impl which fetches keys from the origin servers"""
@@ -693,34 +775,54 @@ class ServerKeyFetcher(BaseV2KeyFetcher):
         self.clock = hs.get_clock()
         self.client = hs.get_http_client()
 
-    @defer.inlineCallbacks
-    def get_keys(self, server_name_and_key_ids):
-        """see KeyFetcher.get_keys"""
-        results = yield logcontext.make_deferred_yieldable(
-            defer.gatherResults(
-                [
-                    run_in_background(
-                        self.get_server_verify_key_v2_direct, server_name, key_ids
-                    )
-                    for server_name, key_ids in server_name_and_key_ids
-                ],
-                consumeErrors=True,
-            ).addErrback(unwrapFirstError)
-        )
+    def get_keys(self, keys_to_fetch):
+        """
+        Args:
+            keys_to_fetch (dict[str, iterable[str]]):
+                the keys to be fetched. server_name -> key_ids
 
-        merged = {}
-        for result in results:
-            merged.update(result)
+        Returns:
+            Deferred[dict[str, dict[str, synapse.storage.keys.FetchKeyResult|None]]]:
+                map from server_name -> key_id -> FetchKeyResult
+        """
+
+        results = {}
+
+        @defer.inlineCallbacks
+        def get_key(key_to_fetch_item):
+            server_name, key_ids = key_to_fetch_item
+            try:
+                keys = yield self.get_server_verify_key_v2_direct(server_name, key_ids)
+                results[server_name] = keys
+            except KeyLookupError as e:
+                logger.warning(
+                    "Error looking up keys %s from %s: %s", key_ids, server_name, e
+                )
+            except Exception:
+                logger.exception("Error getting keys %s from %s", key_ids, server_name)
 
-        defer.returnValue(
-            {server_name: keys for server_name, keys in merged.items() if keys}
+        return yieldable_gather_results(get_key, keys_to_fetch.items()).addCallback(
+            lambda _: results
         )
 
     @defer.inlineCallbacks
     def get_server_verify_key_v2_direct(self, server_name, key_ids):
+        """
+
+        Args:
+            server_name (str):
+            key_ids (iterable[str]):
+
+        Returns:
+            Deferred[dict[str, FetchKeyResult]]: map from key ID to lookup result
+
+        Raises:
+            KeyLookupError if there was a problem making the lookup
+        """
         keys = {}  # type: dict[str, FetchKeyResult]
 
         for requested_key_id in key_ids:
+            # we may have found this key as a side-effect of asking for another.
             if requested_key_id in keys:
                 continue
 
@@ -731,6 +833,19 @@ class ServerKeyFetcher(BaseV2KeyFetcher):
                     path="/_matrix/key/v2/server/"
                     + urllib.parse.quote(requested_key_id),
                     ignore_backoff=True,
+
+                    # we only give the remote server 10s to respond. It should be an
+                    # easy request to handle, so if it doesn't reply within 10s, it's
+                    # probably not going to.
+                    #
+                    # Furthermore, when we are acting as a notary server, we cannot
+                    # wait all day for all of the origin servers, as the requesting
+                    # server will otherwise time out before we can respond.
+                    #
+                    # (Note that get_json may make 4 attempts, so this can still take
+                    # almost 45 seconds to fetch the headers, plus up to another 60s to
+                    # read the response).
+                    timeout=10000,
                 )
             except (NotRetryingDestination, RequestSendFailed) as e:
                 raise_from(KeyLookupError("Failed to connect to remote server"), e)
@@ -755,7 +870,7 @@ class ServerKeyFetcher(BaseV2KeyFetcher):
             )
             keys.update(response_keys)
 
-        defer.returnValue({server_name: keys})
+        defer.returnValue(keys)
 
 
 @defer.inlineCallbacks
@@ -763,7 +878,7 @@ def _handle_key_deferred(verify_request):
     """Waits for the key to become available, and then performs a verification
 
     Args:
-        verify_request (VerifyKeyRequest):
+        verify_request (VerifyJsonRequest):
 
     Returns:
         Deferred[None]
@@ -773,14 +888,10 @@ def _handle_key_deferred(verify_request):
     """
     server_name = verify_request.server_name
     with PreserveLoggingContext():
-        _, key_id, verify_key = yield verify_request.deferred
+        _, key_id, verify_key = yield verify_request.key_ready
 
     json_object = verify_request.json_object
 
-    logger.debug(
-        "Got key %s %s:%s for server %s, verifying"
-        % (key_id, verify_key.alg, verify_key.version, server_name)
-    )
     try:
         verify_signed_json(json_object, server_name, verify_key)
     except SignatureVerifyException as e:
diff --git a/synapse/federation/federation_base.py b/synapse/federation/federation_base.py
index cffa831d80..fc5cfb7d83 100644
--- a/synapse/federation/federation_base.py
+++ b/synapse/federation/federation_base.py
@@ -223,9 +223,6 @@ def _check_sigs_on_pdus(keyring, room_version, pdus):
            the signatures are valid, or fail (with a SynapseError) if not.
     """
 
-    # (currently this is written assuming the v1 room structure; we'll probably want a
-    # separate function for checking v2 rooms)
-
     # we want to check that the event is signed by:
     #
     # (a) the sender's server
@@ -257,6 +254,10 @@ def _check_sigs_on_pdus(keyring, room_version, pdus):
         for p in pdus
     ]
 
+    v = KNOWN_ROOM_VERSIONS.get(room_version)
+    if not v:
+        raise RuntimeError("Unrecognized room version %s" % (room_version,))
+
     # First we check that the sender event is signed by the sender's domain
     # (except if its a 3pid invite, in which case it may be sent by any server)
     pdus_to_check_sender = [
@@ -264,10 +265,17 @@ def _check_sigs_on_pdus(keyring, room_version, pdus):
         if not _is_invite_via_3pid(p.pdu)
     ]
 
-    more_deferreds = keyring.verify_json_objects_for_server([
-        (p.sender_domain, p.redacted_pdu_json)
-        for p in pdus_to_check_sender
-    ])
+    more_deferreds = keyring.verify_json_objects_for_server(
+        [
+            (
+                p.sender_domain,
+                p.redacted_pdu_json,
+                p.pdu.origin_server_ts if v.enforce_key_validity else 0,
+                p.pdu.event_id,
+            )
+            for p in pdus_to_check_sender
+        ]
+    )
 
     def sender_err(e, pdu_to_check):
         errmsg = "event id %s: unable to verify signature for sender %s: %s" % (
@@ -287,20 +295,23 @@ def _check_sigs_on_pdus(keyring, room_version, pdus):
     # event id's domain (normally only the case for joins/leaves), and add additional
     # checks. Only do this if the room version has a concept of event ID domain
     # (ie, the room version uses old-style non-hash event IDs).
-    v = KNOWN_ROOM_VERSIONS.get(room_version)
-    if not v:
-        raise RuntimeError("Unrecognized room version %s" % (room_version,))
-
     if v.event_format == EventFormatVersions.V1:
         pdus_to_check_event_id = [
             p for p in pdus_to_check
             if p.sender_domain != get_domain_from_id(p.pdu.event_id)
         ]
 
-        more_deferreds = keyring.verify_json_objects_for_server([
-            (get_domain_from_id(p.pdu.event_id), p.redacted_pdu_json)
-            for p in pdus_to_check_event_id
-        ])
+        more_deferreds = keyring.verify_json_objects_for_server(
+            [
+                (
+                    get_domain_from_id(p.pdu.event_id),
+                    p.redacted_pdu_json,
+                    p.pdu.origin_server_ts if v.enforce_key_validity else 0,
+                    p.pdu.event_id,
+                )
+                for p in pdus_to_check_event_id
+            ]
+        )
 
         def event_err(e, pdu_to_check):
             errmsg = (
diff --git a/synapse/federation/federation_client.py b/synapse/federation/federation_client.py
index f3fc897a0a..70573746d6 100644
--- a/synapse/federation/federation_client.py
+++ b/synapse/federation/federation_client.py
@@ -17,7 +17,6 @@
 import copy
 import itertools
 import logging
-import random
 
 from six.moves import range
 
@@ -233,7 +232,8 @@ class FederationClient(FederationBase):
                 moving to the next destination. None indicates no timeout.
 
         Returns:
-            Deferred: Results in the requested PDU.
+            Deferred: Results in the requested PDU, or None if we were unable to find
+               it.
         """
 
         # TODO: Rate limit the number of times we try and get the same event.
@@ -258,7 +258,12 @@ class FederationClient(FederationBase):
                     destination, event_id, timeout=timeout,
                 )
 
-                logger.debug("transaction_data %r", transaction_data)
+                logger.debug(
+                    "retrieved event id %s from %s: %r",
+                    event_id,
+                    destination,
+                    transaction_data,
+                )
 
                 pdu_list = [
                     event_from_pdu_json(p, format_ver, outlier=outlier)
@@ -280,6 +285,7 @@ class FederationClient(FederationBase):
                     "Failed to get PDU %s from %s because %s",
                     event_id, destination, e,
                 )
+                continue
             except NotRetryingDestination as e:
                 logger.info(str(e))
                 continue
@@ -326,12 +332,16 @@ class FederationClient(FederationBase):
             state_event_ids = result["pdu_ids"]
             auth_event_ids = result.get("auth_chain_ids", [])
 
-            fetched_events, failed_to_fetch = yield self.get_events(
-                [destination], room_id, set(state_event_ids + auth_event_ids)
+            fetched_events, failed_to_fetch = yield self.get_events_from_store_or_dest(
+                destination, room_id, set(state_event_ids + auth_event_ids)
             )
 
             if failed_to_fetch:
-                logger.warn("Failed to get %r", failed_to_fetch)
+                logger.warning(
+                    "Failed to fetch missing state/auth events for %s: %s",
+                    room_id,
+                    failed_to_fetch
+                )
 
             event_map = {
                 ev.event_id: ev for ev in fetched_events
@@ -397,27 +407,20 @@ class FederationClient(FederationBase):
         defer.returnValue((signed_pdus, signed_auth))
 
     @defer.inlineCallbacks
-    def get_events(self, destinations, room_id, event_ids, return_local=True):
-        """Fetch events from some remote destinations, checking if we already
-        have them.
+    def get_events_from_store_or_dest(self, destination, room_id, event_ids):
+        """Fetch events from a remote destination, checking if we already have them.
 
         Args:
-            destinations (list)
+            destination (str)
             room_id (str)
             event_ids (list)
-            return_local (bool): Whether to include events we already have in
-                the DB in the returned list of events
 
         Returns:
             Deferred: A deferred resolving to a 2-tuple where the first is a list of
             events and the second is a list of event ids that we failed to fetch.
         """
-        if return_local:
-            seen_events = yield self.store.get_events(event_ids, allow_rejected=True)
-            signed_events = list(seen_events.values())
-        else:
-            seen_events = yield self.store.have_seen_events(event_ids)
-            signed_events = []
+        seen_events = yield self.store.get_events(event_ids, allow_rejected=True)
+        signed_events = list(seen_events.values())
 
         failed_to_fetch = set()
 
@@ -428,10 +431,11 @@ class FederationClient(FederationBase):
         if not missing_events:
             defer.returnValue((signed_events, failed_to_fetch))
 
-        def random_server_list():
-            srvs = list(destinations)
-            random.shuffle(srvs)
-            return srvs
+        logger.debug(
+            "Fetching unknown state/auth events %s for room %s",
+            missing_events,
+            event_ids,
+        )
 
         room_version = yield self.store.get_room_version(room_id)
 
@@ -443,7 +447,7 @@ class FederationClient(FederationBase):
             deferreds = [
                 run_in_background(
                     self.get_pdu,
-                    destinations=random_server_list(),
+                    destinations=[destination],
                     event_id=e_id,
                     room_version=room_version,
                 )
diff --git a/synapse/federation/transport/server.py b/synapse/federation/transport/server.py
index d0efc4e0d3..949a5fb2aa 100644
--- a/synapse/federation/transport/server.py
+++ b/synapse/federation/transport/server.py
@@ -94,6 +94,7 @@ class NoAuthenticationError(AuthenticationError):
 
 class Authenticator(object):
     def __init__(self, hs):
+        self._clock = hs.get_clock()
         self.keyring = hs.get_keyring()
         self.server_name = hs.hostname
         self.store = hs.get_datastore()
@@ -102,6 +103,7 @@ class Authenticator(object):
     # A method just so we can pass 'self' as the authenticator to the Servlets
     @defer.inlineCallbacks
     def authenticate_request(self, request, content):
+        now = self._clock.time_msec()
         json_request = {
             "method": request.method.decode('ascii'),
             "uri": request.uri.decode('ascii'),
@@ -138,7 +140,9 @@ class Authenticator(object):
                 401, "Missing Authorization headers", Codes.UNAUTHORIZED,
             )
 
-        yield self.keyring.verify_json_for_server(origin, json_request)
+        yield self.keyring.verify_json_for_server(
+            origin, json_request, now, "Incoming request"
+        )
 
         logger.info("Request from %s", origin)
         request.authenticated_entity = origin
diff --git a/synapse/groups/attestations.py b/synapse/groups/attestations.py
index 786149be65..e5dda1975f 100644
--- a/synapse/groups/attestations.py
+++ b/synapse/groups/attestations.py
@@ -97,10 +97,13 @@ class GroupAttestationSigning(object):
 
         # TODO: We also want to check that *new* attestations that people give
         # us to store are valid for at least a little while.
-        if valid_until_ms < self.clock.time_msec():
+        now = self.clock.time_msec()
+        if valid_until_ms < now:
             raise SynapseError(400, "Attestation expired")
 
-        yield self.keyring.verify_json_for_server(server_name, attestation)
+        yield self.keyring.verify_json_for_server(
+            server_name, attestation, now, "Group attestation"
+        )
 
     def create_attestation(self, group_id, user_id):
         """Create an attestation for the group_id and user_id with default
diff --git a/synapse/handlers/auth.py b/synapse/handlers/auth.py
index aa5d89a9ac..7f8ddc99c6 100644
--- a/synapse/handlers/auth.py
+++ b/synapse/handlers/auth.py
@@ -162,7 +162,7 @@ class AuthHandler(BaseHandler):
         defer.returnValue(params)
 
     @defer.inlineCallbacks
-    def check_auth(self, flows, clientdict, clientip):
+    def check_auth(self, flows, clientdict, clientip, password_servlet=False):
         """
         Takes a dictionary sent by the client in the login / registration
         protocol and handles the User-Interactive Auth flow.
@@ -186,6 +186,16 @@ class AuthHandler(BaseHandler):
 
             clientip (str): The IP address of the client.
 
+            password_servlet (bool): Whether the request originated from
+                PasswordRestServlet.
+                XXX: This is a temporary hack to distinguish between checking
+                for threepid validations locally (in the case of password
+                resets) and using the identity server (in the case of binding
+                a 3PID during registration). Once we start using the
+                homeserver for both tasks, this distinction will no longer be
+                necessary.
+
+
         Returns:
             defer.Deferred[dict, dict, str]: a deferred tuple of
                 (creds, params, session_id).
@@ -241,7 +251,9 @@ class AuthHandler(BaseHandler):
         if 'type' in authdict:
             login_type = authdict['type']
             try:
-                result = yield self._check_auth_dict(authdict, clientip)
+                result = yield self._check_auth_dict(
+                    authdict, clientip, password_servlet=password_servlet,
+                )
                 if result:
                     creds[login_type] = result
                     self._save_session(session)
@@ -351,7 +363,7 @@ class AuthHandler(BaseHandler):
         return sess.setdefault('serverdict', {}).get(key, default)
 
     @defer.inlineCallbacks
-    def _check_auth_dict(self, authdict, clientip):
+    def _check_auth_dict(self, authdict, clientip, password_servlet=False):
         """Attempt to validate the auth dict provided by a client
 
         Args:
@@ -369,7 +381,13 @@ class AuthHandler(BaseHandler):
         login_type = authdict['type']
         checker = self.checkers.get(login_type)
         if checker is not None:
-            res = yield checker(authdict, clientip)
+            # XXX: Temporary workaround for having Synapse handle password resets
+            # See AuthHandler.check_auth for further details
+            res = yield checker(
+                authdict,
+                clientip=clientip,
+                password_servlet=password_servlet,
+            )
             defer.returnValue(res)
 
         # build a v1-login-style dict out of the authdict and fall back to the
@@ -383,7 +401,7 @@ class AuthHandler(BaseHandler):
         defer.returnValue(canonical_id)
 
     @defer.inlineCallbacks
-    def _check_recaptcha(self, authdict, clientip):
+    def _check_recaptcha(self, authdict, clientip, **kwargs):
         try:
             user_response = authdict["response"]
         except KeyError:
@@ -429,20 +447,20 @@ class AuthHandler(BaseHandler):
                 defer.returnValue(True)
         raise LoginError(401, "", errcode=Codes.UNAUTHORIZED)
 
-    def _check_email_identity(self, authdict, _):
-        return self._check_threepid('email', authdict)
+    def _check_email_identity(self, authdict, **kwargs):
+        return self._check_threepid('email', authdict, **kwargs)
 
-    def _check_msisdn(self, authdict, _):
+    def _check_msisdn(self, authdict, **kwargs):
         return self._check_threepid('msisdn', authdict)
 
-    def _check_dummy_auth(self, authdict, _):
+    def _check_dummy_auth(self, authdict, **kwargs):
         return defer.succeed(True)
 
-    def _check_terms_auth(self, authdict, _):
+    def _check_terms_auth(self, authdict, **kwargs):
         return defer.succeed(True)
 
     @defer.inlineCallbacks
-    def _check_threepid(self, medium, authdict):
+    def _check_threepid(self, medium, authdict, password_servlet=False, **kwargs):
         if 'threepid_creds' not in authdict:
             raise LoginError(400, "Missing threepid_creds", Codes.MISSING_PARAM)
 
@@ -451,7 +469,29 @@ class AuthHandler(BaseHandler):
         identity_handler = self.hs.get_handlers().identity_handler
 
         logger.info("Getting validated threepid. threepidcreds: %r", (threepid_creds,))
-        threepid = yield identity_handler.threepid_from_creds(threepid_creds)
+        if (
+            not password_servlet
+            or self.hs.config.email_password_reset_behaviour == "remote"
+        ):
+            threepid = yield identity_handler.threepid_from_creds(threepid_creds)
+        elif self.hs.config.email_password_reset_behaviour == "local":
+            row = yield self.store.get_threepid_validation_session(
+                medium,
+                threepid_creds["client_secret"],
+                sid=threepid_creds["sid"],
+            )
+
+            threepid = {
+                "medium": row["medium"],
+                "address": row["address"],
+                "validated_at": row["validated_at"],
+            } if row else None
+
+            if row:
+                # Valid threepid returned, delete from the db
+                yield self.store.delete_threepid_session(threepid_creds["sid"])
+        else:
+            raise SynapseError(400, "Password resets are not enabled on this homeserver")
 
         if not threepid:
             raise LoginError(401, "", errcode=Codes.UNAUTHORIZED)
diff --git a/synapse/handlers/federation.py b/synapse/handlers/federation.py
index cf4fad7de0..ac5ca79143 100644
--- a/synapse/handlers/federation.py
+++ b/synapse/handlers/federation.py
@@ -35,6 +35,7 @@ from synapse.api.errors import (
     CodeMessageException,
     FederationDeniedError,
     FederationError,
+    RequestSendFailed,
     StoreError,
     SynapseError,
 )
@@ -2027,9 +2028,21 @@ class FederationHandler(BaseHandler):
         """
         room_version = yield self.store.get_room_version(event.room_id)
 
-        yield self._update_auth_events_and_context_for_auth(
-            origin, event, context, auth_events
-        )
+        try:
+            yield self._update_auth_events_and_context_for_auth(
+                origin, event, context, auth_events
+            )
+        except Exception:
+            # We don't really mind if the above fails, so lets not fail
+            # processing if it does. However, it really shouldn't fail so
+            # let's still log as an exception since we'll still want to fix
+            # any bugs.
+            logger.exception(
+                "Failed to double check auth events for %s with remote. "
+                "Ignoring failure and continuing processing of event.",
+                event.event_id,
+            )
+
         try:
             self.auth.check(room_version, event, auth_events=auth_events)
         except AuthError as e:
@@ -2042,6 +2055,15 @@ class FederationHandler(BaseHandler):
     ):
         """Helper for do_auth. See there for docs.
 
+        Checks whether a given event has the expected auth events. If it
+        doesn't then we talk to the remote server to compare state to see if
+        we can come to a consensus (e.g. if one server missed some valid
+        state).
+
+        This attempts to resovle any potential divergence of state between
+        servers, but is not essential and so failures should not block further
+        processing of the event.
+
         Args:
             origin (str):
             event (synapse.events.EventBase):
@@ -2088,9 +2110,15 @@ class FederationHandler(BaseHandler):
                 missing_auth,
             )
             try:
-                remote_auth_chain = yield self.federation_client.get_event_auth(
-                    origin, event.room_id, event.event_id
-                )
+                try:
+                    remote_auth_chain = yield self.federation_client.get_event_auth(
+                        origin, event.room_id, event.event_id
+                    )
+                except RequestSendFailed as e:
+                    # The other side isn't around or doesn't implement the
+                    # endpoint, so lets just bail out.
+                    logger.info("Failed to get event auth from remote: %s", e)
+                    return
 
                 seen_remotes = yield self.store.have_seen_events(
                     [e.event_id for e in remote_auth_chain]
@@ -2236,12 +2264,18 @@ class FederationHandler(BaseHandler):
 
         try:
             # 2. Get remote difference.
-            result = yield self.federation_client.query_auth(
-                origin,
-                event.room_id,
-                event.event_id,
-                local_auth_chain,
-            )
+            try:
+                result = yield self.federation_client.query_auth(
+                    origin,
+                    event.room_id,
+                    event.event_id,
+                    local_auth_chain,
+                )
+            except RequestSendFailed as e:
+                # The other side isn't around or doesn't implement the
+                # endpoint, so lets just bail out.
+                logger.info("Failed to query auth from remote: %s", e)
+                return
 
             seen_remotes = yield self.store.have_seen_events(
                 [e.event_id for e in result["auth_chain"]]
diff --git a/synapse/handlers/identity.py b/synapse/handlers/identity.py
index 22469486d7..04caf65793 100644
--- a/synapse/handlers/identity.py
+++ b/synapse/handlers/identity.py
@@ -247,7 +247,14 @@ class IdentityHandler(BaseHandler):
         defer.returnValue(changed)
 
     @defer.inlineCallbacks
-    def requestEmailToken(self, id_server, email, client_secret, send_attempt, **kwargs):
+    def requestEmailToken(
+        self,
+        id_server,
+        email,
+        client_secret,
+        send_attempt,
+        next_link=None,
+    ):
         if not self._should_trust_id_server(id_server):
             raise SynapseError(
                 400, "Untrusted ID server '%s'" % id_server,
@@ -259,7 +266,9 @@ class IdentityHandler(BaseHandler):
             'client_secret': client_secret,
             'send_attempt': send_attempt,
         }
-        params.update(kwargs)
+
+        if next_link:
+            params.update({'next_link': next_link})
 
         try:
             data = yield self.http_client.post_json_get_json(
diff --git a/synapse/handlers/presence.py b/synapse/handlers/presence.py
index 6209858bbb..557fb5f83d 100644
--- a/synapse/handlers/presence.py
+++ b/synapse/handlers/presence.py
@@ -158,7 +158,13 @@ class PresenceHandler(object):
         # have not yet been persisted
         self.unpersisted_users_changes = set()
 
-        hs.get_reactor().addSystemEventTrigger("before", "shutdown", self._on_shutdown)
+        hs.get_reactor().addSystemEventTrigger(
+            "before",
+            "shutdown",
+            run_as_background_process,
+            "presence.on_shutdown",
+            self._on_shutdown,
+        )
 
         self.serial_to_user = {}
         self._next_serial = 1
@@ -828,14 +834,17 @@ class PresenceHandler(object):
                 # joins.
                 continue
 
-            event = yield self.store.get_event(event_id)
-            if event.content.get("membership") != Membership.JOIN:
+            event = yield self.store.get_event(event_id, allow_none=True)
+            if not event or event.content.get("membership") != Membership.JOIN:
                 # We only care about joins
                 continue
 
             if prev_event_id:
-                prev_event = yield self.store.get_event(prev_event_id)
-                if prev_event.content.get("membership") == Membership.JOIN:
+                prev_event = yield self.store.get_event(prev_event_id, allow_none=True)
+                if (
+                    prev_event
+                    and prev_event.content.get("membership") == Membership.JOIN
+                ):
                     # Ignore changes to join events.
                     continue
 
diff --git a/synapse/handlers/stats.py b/synapse/handlers/stats.py
index 0e92b405ba..7ad16c8566 100644
--- a/synapse/handlers/stats.py
+++ b/synapse/handlers/stats.py
@@ -115,6 +115,7 @@ class StatsHandler(StateDeltasHandler):
             event_id = delta["event_id"]
             stream_id = delta["stream_id"]
             prev_event_id = delta["prev_event_id"]
+            stream_pos = delta["stream_id"]
 
             logger.debug("Handling: %r %r, %s", typ, state_key, event_id)
 
@@ -136,10 +137,15 @@ class StatsHandler(StateDeltasHandler):
             event_content = {}
 
             if event_id is not None:
-                event_content = (yield self.store.get_event(event_id)).content or {}
+                event = yield self.store.get_event(event_id, allow_none=True)
+                if event:
+                    event_content = event.content or {}
+
+            # We use stream_pos here rather than fetch by event_id as event_id
+            # may be None
+            now = yield self.store.get_received_ts_by_stream_pos(stream_pos)
 
             # quantise time to the nearest bucket
-            now = yield self.store.get_received_ts(event_id)
             now = (now // 1000 // self.stats_bucket_size) * self.stats_bucket_size
 
             if typ == EventTypes.Member:
@@ -149,9 +155,11 @@ class StatsHandler(StateDeltasHandler):
                 # compare them.
                 prev_event_content = {}
                 if prev_event_id is not None:
-                    prev_event_content = (
-                        yield self.store.get_event(prev_event_id)
-                    ).content
+                    prev_event = yield self.store.get_event(
+                        prev_event_id, allow_none=True,
+                    )
+                    if prev_event:
+                        prev_event_content = prev_event.content
 
                 membership = event_content.get("membership", Membership.LEAVE)
                 prev_membership = prev_event_content.get("membership", Membership.LEAVE)
diff --git a/synapse/handlers/sync.py b/synapse/handlers/sync.py
index 1ee9a6e313..62fda0c664 100644
--- a/synapse/handlers/sync.py
+++ b/synapse/handlers/sync.py
@@ -583,30 +583,42 @@ class SyncHandler(object):
         )
 
         # if the room has a name or canonical_alias set, we can skip
-        # calculating heroes.  we assume that if the event has contents, it'll
-        # be a valid name or canonical_alias - i.e. we're checking that they
-        # haven't been "deleted" by blatting {} over the top.
+        # calculating heroes. Empty strings are falsey, so we check
+        # for the "name" value and default to an empty string.
         if name_id:
             name = yield self.store.get_event(name_id, allow_none=True)
-            if name and name.content:
+            if name and name.content.get("name"):
                 defer.returnValue(summary)
 
         if canonical_alias_id:
             canonical_alias = yield self.store.get_event(
                 canonical_alias_id, allow_none=True,
             )
-            if canonical_alias and canonical_alias.content:
+            if canonical_alias and canonical_alias.content.get("alias"):
                 defer.returnValue(summary)
 
+        me = sync_config.user.to_string()
+
         joined_user_ids = [
-            r[0] for r in details.get(Membership.JOIN, empty_ms).members
+            r[0]
+            for r in details.get(Membership.JOIN, empty_ms).members
+            if r[0] != me
         ]
         invited_user_ids = [
-            r[0] for r in details.get(Membership.INVITE, empty_ms).members
+            r[0]
+            for r in details.get(Membership.INVITE, empty_ms).members
+            if r[0] != me
         ]
         gone_user_ids = (
-            [r[0] for r in details.get(Membership.LEAVE, empty_ms).members] +
-            [r[0] for r in details.get(Membership.BAN, empty_ms).members]
+            [
+                r[0]
+                for r in details.get(Membership.LEAVE, empty_ms).members
+                if r[0] != me
+            ] + [
+                r[0]
+                for r in details.get(Membership.BAN, empty_ms).members
+                if r[0] != me
+            ]
         )
 
         # FIXME: only build up a member_ids list for our heroes
@@ -621,22 +633,13 @@ class SyncHandler(object):
                 member_ids[user_id] = event_id
 
         # FIXME: order by stream ordering rather than as returned by SQL
-        me = sync_config.user.to_string()
         if (joined_user_ids or invited_user_ids):
             summary['m.heroes'] = sorted(
-                [
-                    user_id
-                    for user_id in (joined_user_ids + invited_user_ids)
-                    if user_id != me
-                ]
+                [user_id for user_id in (joined_user_ids + invited_user_ids)]
             )[0:5]
         else:
             summary['m.heroes'] = sorted(
-                [
-                    user_id
-                    for user_id in gone_user_ids
-                    if user_id != me
-                ]
+                [user_id for user_id in gone_user_ids]
             )[0:5]
 
         if not sync_config.filter_collection.lazy_load_members():
diff --git a/synapse/http/matrixfederationclient.py b/synapse/http/matrixfederationclient.py
index 8197619a78..663ea72a7a 100644
--- a/synapse/http/matrixfederationclient.py
+++ b/synapse/http/matrixfederationclient.py
@@ -285,7 +285,24 @@ class MatrixFederationHttpClient(object):
             request (MatrixFederationRequest): details of request to be sent
 
             timeout (int|None): number of milliseconds to wait for the response headers
-                (including connecting to the server). 60s by default.
+                (including connecting to the server), *for each attempt*.
+                60s by default.
+
+            long_retries (bool): whether to use the long retry algorithm.
+
+                The regular retry algorithm makes 4 attempts, with intervals
+                [0.5s, 1s, 2s].
+
+                The long retry algorithm makes 11 attempts, with intervals
+                [4s, 16s, 60s, 60s, ...]
+
+                Both algorithms add -20%/+40% jitter to the retry intervals.
+
+                Note that the above intervals are *in addition* to the time spent
+                waiting for the request to complete (up to `timeout` ms).
+
+                NB: the long retry algorithm takes over 20 minutes to complete, with
+                a default timeout of 60s!
 
             ignore_backoff (bool): true to ignore the historical backoff data
                 and try the request anyway.
@@ -566,10 +583,14 @@ class MatrixFederationHttpClient(object):
                 the request body. This will be encoded as JSON.
             json_data_callback (callable): A callable returning the dict to
                 use as the request body.
-            long_retries (bool): A boolean that indicates whether we should
-                retry for a short or long time.
-            timeout(int): How long to try (in ms) the destination for before
-                giving up. None indicates no timeout.
+
+            long_retries (bool): whether to use the long retry algorithm. See
+                docs on _send_request for details.
+
+            timeout (int|None): number of milliseconds to wait for the response headers
+                (including connecting to the server), *for each attempt*.
+                self._default_timeout (60s) by default.
+
             ignore_backoff (bool): true to ignore the historical backoff data
                 and try the request anyway.
             backoff_on_404 (bool): True if we should count a 404 response as
@@ -627,15 +648,22 @@ class MatrixFederationHttpClient(object):
         Args:
             destination (str): The remote server to send the HTTP request
                 to.
+
             path (str): The HTTP path.
+
             data (dict): A dict containing the data that will be used as
                 the request body. This will be encoded as JSON.
-            long_retries (bool): A boolean that indicates whether we should
-                retry for a short or long time.
-            timeout(int): How long to try (in ms) the destination for before
-                giving up. None indicates no timeout.
+
+            long_retries (bool): whether to use the long retry algorithm. See
+                docs on _send_request for details.
+
+            timeout (int|None): number of milliseconds to wait for the response headers
+                (including connecting to the server), *for each attempt*.
+                self._default_timeout (60s) by default.
+
             ignore_backoff (bool): true to ignore the historical backoff data and
                 try the request anyway.
+
             args (dict): query params
         Returns:
             Deferred[dict|list]: Succeeds when we get a 2xx HTTP response. The
@@ -686,14 +714,19 @@ class MatrixFederationHttpClient(object):
         Args:
             destination (str): The remote server to send the HTTP request
                 to.
+
             path (str): The HTTP path.
+
             args (dict|None): A dictionary used to create query strings, defaults to
                 None.
-            timeout (int): How long to try (in ms) the destination for before
-                giving up. None indicates no timeout and that the request will
-                be retried.
+
+            timeout (int|None): number of milliseconds to wait for the response headers
+                (including connecting to the server), *for each attempt*.
+                self._default_timeout (60s) by default.
+
             ignore_backoff (bool): true to ignore the historical backoff data
                 and try the request anyway.
+
             try_trailing_slash_on_400 (bool): True if on a 400 M_UNRECOGNIZED
                 response we should try appending a trailing slash to the end of
                 the request. Workaround for #3622 in Synapse <= v0.99.3.
@@ -742,12 +775,18 @@ class MatrixFederationHttpClient(object):
             destination (str): The remote server to send the HTTP request
                 to.
             path (str): The HTTP path.
-            long_retries (bool): A boolean that indicates whether we should
-                retry for a short or long time.
-            timeout(int): How long to try (in ms) the destination for before
-                giving up. None indicates no timeout.
+
+            long_retries (bool): whether to use the long retry algorithm. See
+                docs on _send_request for details.
+
+            timeout (int|None): number of milliseconds to wait for the response headers
+                (including connecting to the server), *for each attempt*.
+                self._default_timeout (60s) by default.
+
             ignore_backoff (bool): true to ignore the historical backoff data and
                 try the request anyway.
+
+            args (dict): query params
         Returns:
             Deferred[dict|list]: Succeeds when we get a 2xx HTTP response. The
             result will be the decoded JSON body.
diff --git a/synapse/push/mailer.py b/synapse/push/mailer.py
index c269bcf4a4..4bc9eb7313 100644
--- a/synapse/push/mailer.py
+++ b/synapse/push/mailer.py
@@ -80,10 +80,10 @@ ALLOWED_ATTRS = {
 
 
 class Mailer(object):
-    def __init__(self, hs, app_name, notif_template_html, notif_template_text):
+    def __init__(self, hs, app_name, template_html, template_text):
         self.hs = hs
-        self.notif_template_html = notif_template_html
-        self.notif_template_text = notif_template_text
+        self.template_html = template_html
+        self.template_text = template_text
 
         self.sendmail = self.hs.get_sendmail()
         self.store = self.hs.get_datastore()
@@ -94,21 +94,48 @@ class Mailer(object):
         logger.info("Created Mailer for app_name %s" % app_name)
 
     @defer.inlineCallbacks
-    def send_notification_mail(self, app_id, user_id, email_address,
-                               push_actions, reason):
-        try:
-            from_string = self.hs.config.email_notif_from % {
-                "app": self.app_name
-            }
-        except TypeError:
-            from_string = self.hs.config.email_notif_from
+    def send_password_reset_mail(
+        self,
+        email_address,
+        token,
+        client_secret,
+        sid,
+    ):
+        """Send an email with a password reset link to a user
+
+        Args:
+            email_address (str): Email address we're sending the password
+                reset to
+            token (str): Unique token generated by the server to verify
+                password reset email was received
+            client_secret (str): Unique token generated by the client to
+                group together multiple email sending attempts
+            sid (str): The generated session ID
+        """
+        if email.utils.parseaddr(email_address)[1] == '':
+            raise RuntimeError("Invalid 'to' email address")
+
+        link = (
+            self.hs.config.public_baseurl +
+            "_synapse/password_reset/email/submit_token"
+            "?token=%s&client_secret=%s&sid=%s" %
+            (token, client_secret, sid)
+        )
 
-        raw_from = email.utils.parseaddr(from_string)[1]
-        raw_to = email.utils.parseaddr(email_address)[1]
+        template_vars = {
+            "link": link,
+        }
 
-        if raw_to == '':
-            raise RuntimeError("Invalid 'to' address")
+        yield self.send_email(
+            email_address,
+            "[%s] Password Reset Email" % self.hs.config.server_name,
+            template_vars,
+        )
 
+    @defer.inlineCallbacks
+    def send_notification_mail(self, app_id, user_id, email_address,
+                               push_actions, reason):
+        """Send email regarding a user's room notifications"""
         rooms_in_order = deduped_ordered_list(
             [pa['room_id'] for pa in push_actions]
         )
@@ -176,14 +203,36 @@ class Mailer(object):
             "reason": reason,
         }
 
-        html_text = self.notif_template_html.render(**template_vars)
+        yield self.send_email(
+            email_address,
+            "[%s] %s" % (self.app_name, summary_text),
+            template_vars,
+        )
+
+    @defer.inlineCallbacks
+    def send_email(self, email_address, subject, template_vars):
+        """Send an email with the given information and template text"""
+        try:
+            from_string = self.hs.config.email_notif_from % {
+                "app": self.app_name
+            }
+        except TypeError:
+            from_string = self.hs.config.email_notif_from
+
+        raw_from = email.utils.parseaddr(from_string)[1]
+        raw_to = email.utils.parseaddr(email_address)[1]
+
+        if raw_to == '':
+            raise RuntimeError("Invalid 'to' address")
+
+        html_text = self.template_html.render(**template_vars)
         html_part = MIMEText(html_text, "html", "utf8")
 
-        plain_text = self.notif_template_text.render(**template_vars)
+        plain_text = self.template_text.render(**template_vars)
         text_part = MIMEText(plain_text, "plain", "utf8")
 
         multipart_msg = MIMEMultipart('alternative')
-        multipart_msg['Subject'] = "[%s] %s" % (self.app_name, summary_text)
+        multipart_msg['Subject'] = subject
         multipart_msg['From'] = from_string
         multipart_msg['To'] = email_address
         multipart_msg['Date'] = email.utils.formatdate()
diff --git a/synapse/push/pusher.py b/synapse/push/pusher.py
index 14bc7823cf..aff85daeb5 100644
--- a/synapse/push/pusher.py
+++ b/synapse/push/pusher.py
@@ -70,8 +70,8 @@ class PusherFactory(object):
             mailer = Mailer(
                 hs=self.hs,
                 app_name=app_name,
-                notif_template_html=self.notif_template_html,
-                notif_template_text=self.notif_template_text,
+                template_html=self.notif_template_html,
+                template_text=self.notif_template_text,
             )
             self.mailers[app_name] = mailer
         return EmailPusher(self.hs, pusherdict, mailer)
diff --git a/synapse/python_dependencies.py b/synapse/python_dependencies.py
index f64baa4d58..c78f2cb15e 100644
--- a/synapse/python_dependencies.py
+++ b/synapse/python_dependencies.py
@@ -77,7 +77,7 @@ REQUIREMENTS = [
 ]
 
 CONDITIONAL_REQUIREMENTS = {
-    "email.enable_notifs": ["Jinja2>=2.9", "bleach>=1.4.2"],
+    "email": ["Jinja2>=2.9", "bleach>=1.4.2"],
     "matrix-synapse-ldap3": ["matrix-synapse-ldap3>=0.1"],
 
     # we use execute_batch, which arrived in psycopg 2.7.
diff --git a/synapse/res/templates/password_reset.html b/synapse/res/templates/password_reset.html
new file mode 100644
index 0000000000..4fa7b36734
--- /dev/null
+++ b/synapse/res/templates/password_reset.html
@@ -0,0 +1,9 @@
+<html>
+<body>
+    <p>A password reset request has been received for your Matrix account. If this was you, please click the link below to confirm resetting your password:</p>
+
+    <a href="{{ link }}">{{ link }}</a>
+
+    <p>If this was not you, please disregard this email and contact your server administrator. Thank you.</p>
+</body>
+</html>
diff --git a/synapse/res/templates/password_reset.txt b/synapse/res/templates/password_reset.txt
new file mode 100644
index 0000000000..f0deff59a7
--- /dev/null
+++ b/synapse/res/templates/password_reset.txt
@@ -0,0 +1,7 @@
+A password reset request has been received for your Matrix account. If this
+was you, please click the link below to confirm resetting your password:
+
+{{ link }}
+
+If this was not you, please disregard this email and contact your server
+administrator. Thank you.
diff --git a/synapse/res/templates/password_reset_failure.html b/synapse/res/templates/password_reset_failure.html
new file mode 100644
index 0000000000..0b132cf8db
--- /dev/null
+++ b/synapse/res/templates/password_reset_failure.html
@@ -0,0 +1,6 @@
+<html>
+<head></head>
+<body>
+<p>{{ failure_reason }}. Your password has not been reset.</p>
+</body>
+</html>
diff --git a/synapse/res/templates/password_reset_success.html b/synapse/res/templates/password_reset_success.html
new file mode 100644
index 0000000000..7b6fa5e6f0
--- /dev/null
+++ b/synapse/res/templates/password_reset_success.html
@@ -0,0 +1,6 @@
+<html>
+<head></head>
+<body>
+<p>Your password was successfully reset. You may now close this window.</p>
+</body>
+</html>
diff --git a/synapse/rest/client/v1/voip.py b/synapse/rest/client/v1/voip.py
index 0975df84cf..6381049210 100644
--- a/synapse/rest/client/v1/voip.py
+++ b/synapse/rest/client/v1/voip.py
@@ -29,6 +29,7 @@ class VoipRestServlet(RestServlet):
     def __init__(self, hs):
         super(VoipRestServlet, self).__init__()
         self.hs = hs
+        self.auth = hs.get_auth()
 
     @defer.inlineCallbacks
     def on_GET(self, request):
diff --git a/synapse/rest/client/v2_alpha/account.py b/synapse/rest/client/v2_alpha/account.py
index ca35dc3c83..e4c63b69b9 100644
--- a/synapse/rest/client/v2_alpha/account.py
+++ b/synapse/rest/client/v2_alpha/account.py
@@ -15,19 +15,25 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 import logging
+import re
 
 from six.moves import http_client
 
+import jinja2
+
 from twisted.internet import defer
 
 from synapse.api.constants import LoginType
-from synapse.api.errors import Codes, SynapseError
+from synapse.api.errors import Codes, SynapseError, ThreepidValidationError
+from synapse.http.server import finish_request
 from synapse.http.servlet import (
     RestServlet,
     assert_params_in_dict,
     parse_json_object_from_request,
+    parse_string,
 )
 from synapse.util.msisdn import phone_number_to_msisdn
+from synapse.util.stringutils import random_string
 from synapse.util.threepids import check_3pid_allowed
 
 from ._base import client_patterns, interactive_auth_handler
@@ -41,17 +47,42 @@ class EmailPasswordRequestTokenRestServlet(RestServlet):
     def __init__(self, hs):
         super(EmailPasswordRequestTokenRestServlet, self).__init__()
         self.hs = hs
+        self.datastore = hs.get_datastore()
+        self.config = hs.config
         self.identity_handler = hs.get_handlers().identity_handler
 
+        if self.config.email_password_reset_behaviour == "local":
+            from synapse.push.mailer import Mailer, load_jinja2_templates
+            templates = load_jinja2_templates(
+                config=hs.config,
+                template_html_name=hs.config.email_password_reset_template_html,
+                template_text_name=hs.config.email_password_reset_template_text,
+            )
+            self.mailer = Mailer(
+                hs=self.hs,
+                app_name=self.config.email_app_name,
+                template_html=templates[0],
+                template_text=templates[1],
+            )
+
     @defer.inlineCallbacks
     def on_POST(self, request):
+        if self.config.email_password_reset_behaviour == "off":
+            raise SynapseError(400, "Password resets have been disabled on this server")
+
         body = parse_json_object_from_request(request)
 
         assert_params_in_dict(body, [
-            'id_server', 'client_secret', 'email', 'send_attempt'
+            'client_secret', 'email', 'send_attempt'
         ])
 
-        if not check_3pid_allowed(self.hs, "email", body['email']):
+        # Extract params from body
+        client_secret = body["client_secret"]
+        email = body["email"]
+        send_attempt = body["send_attempt"]
+        next_link = body.get("next_link")  # Optional param
+
+        if not check_3pid_allowed(self.hs, "email", email):
             raise SynapseError(
                 403,
                 "Your email domain is not authorized on this server",
@@ -59,15 +90,100 @@ class EmailPasswordRequestTokenRestServlet(RestServlet):
             )
 
         existingUid = yield self.hs.get_datastore().get_user_id_by_threepid(
-            'email', body['email']
+            'email', email,
         )
 
         if existingUid is None:
             raise SynapseError(400, "Email not found", Codes.THREEPID_NOT_FOUND)
 
-        ret = yield self.identity_handler.requestEmailToken(**body)
+        if self.config.email_password_reset_behaviour == "remote":
+            if 'id_server' not in body:
+                raise SynapseError(400, "Missing 'id_server' param in body")
+
+            # Have the identity server handle the password reset flow
+            ret = yield self.identity_handler.requestEmailToken(
+                body["id_server"], email, client_secret, send_attempt, next_link,
+            )
+        else:
+            # Send password reset emails from Synapse
+            sid = yield self.send_password_reset(
+                email, client_secret, send_attempt, next_link,
+            )
+
+            # Wrap the session id in a JSON object
+            ret = {"sid": sid}
+
         defer.returnValue((200, ret))
 
+    @defer.inlineCallbacks
+    def send_password_reset(
+        self,
+        email,
+        client_secret,
+        send_attempt,
+        next_link=None,
+    ):
+        """Send a password reset email
+
+        Args:
+            email (str): The user's email address
+            client_secret (str): The provided client secret
+            send_attempt (int): Which send attempt this is
+
+        Returns:
+            The new session_id upon success
+
+        Raises:
+            SynapseError is an error occurred when sending the email
+        """
+        # Check that this email/client_secret/send_attempt combo is new or
+        # greater than what we've seen previously
+        session = yield self.datastore.get_threepid_validation_session(
+            "email", client_secret, address=email, validated=False,
+        )
+
+        # Check to see if a session already exists and that it is not yet
+        # marked as validated
+        if session and session.get("validated_at") is None:
+            session_id = session['session_id']
+            last_send_attempt = session['last_send_attempt']
+
+            # Check that the send_attempt is higher than previous attempts
+            if send_attempt <= last_send_attempt:
+                # If not, just return a success without sending an email
+                defer.returnValue(session_id)
+        else:
+            # An non-validated session does not exist yet.
+            # Generate a session id
+            session_id = random_string(16)
+
+        # Generate a new validation token
+        token = random_string(32)
+
+        # Send the mail with the link containing the token, client_secret
+        # and session_id
+        try:
+            yield self.mailer.send_password_reset_mail(
+                email, token, client_secret, session_id,
+            )
+        except Exception:
+            logger.exception(
+                "Error sending a password reset email to %s", email,
+            )
+            raise SynapseError(
+                500, "An error was encountered when sending the password reset email"
+            )
+
+        token_expires = (self.hs.clock.time_msec() +
+                         self.config.email_validation_token_lifetime)
+
+        yield self.datastore.start_or_continue_validation_session(
+            "email", email, session_id, client_secret, send_attempt,
+            next_link, token, token_expires,
+        )
+
+        defer.returnValue(session_id)
+
 
 class MsisdnPasswordRequestTokenRestServlet(RestServlet):
     PATTERNS = client_patterns("/account/password/msisdn/requestToken$")
@@ -80,6 +196,9 @@ class MsisdnPasswordRequestTokenRestServlet(RestServlet):
 
     @defer.inlineCallbacks
     def on_POST(self, request):
+        if not self.config.email_password_reset_behaviour == "off":
+            raise SynapseError(400, "Password resets have been disabled on this server")
+
         body = parse_json_object_from_request(request)
 
         assert_params_in_dict(body, [
@@ -107,6 +226,118 @@ class MsisdnPasswordRequestTokenRestServlet(RestServlet):
         defer.returnValue((200, ret))
 
 
+class PasswordResetSubmitTokenServlet(RestServlet):
+    """Handles 3PID validation token submission"""
+    PATTERNS = [
+        re.compile("^/_synapse/password_reset/(?P<medium>[^/]*)/submit_token/*$"),
+    ]
+
+    def __init__(self, hs):
+        """
+        Args:
+            hs (synapse.server.HomeServer): server
+        """
+        super(PasswordResetSubmitTokenServlet, self).__init__()
+        self.hs = hs
+        self.auth = hs.get_auth()
+        self.config = hs.config
+        self.clock = hs.get_clock()
+        self.datastore = hs.get_datastore()
+
+    @defer.inlineCallbacks
+    def on_GET(self, request, medium):
+        if medium != "email":
+            raise SynapseError(
+                400,
+                "This medium is currently not supported for password resets",
+            )
+
+        sid = parse_string(request, "sid")
+        client_secret = parse_string(request, "client_secret")
+        token = parse_string(request, "token")
+
+        # Attempt to validate a 3PID sesssion
+        try:
+            # Mark the session as valid
+            next_link = yield self.datastore.validate_threepid_session(
+                sid,
+                client_secret,
+                token,
+                self.clock.time_msec(),
+            )
+
+            # Perform a 302 redirect if next_link is set
+            if next_link:
+                if next_link.startswith("file:///"):
+                    logger.warn(
+                        "Not redirecting to next_link as it is a local file: address"
+                    )
+                else:
+                    request.setResponseCode(302)
+                    request.setHeader("Location", next_link)
+                    finish_request(request)
+                    defer.returnValue(None)
+
+            # Otherwise show the success template
+            html = self.config.email_password_reset_success_html_content
+            request.setResponseCode(200)
+        except ThreepidValidationError as e:
+            # Show a failure page with a reason
+            html = self.load_jinja2_template(
+                self.config.email_template_dir,
+                self.config.email_password_reset_failure_template,
+                template_vars={
+                    "failure_reason": e.msg,
+                }
+            )
+            request.setResponseCode(e.code)
+
+        request.write(html.encode('utf-8'))
+        finish_request(request)
+        defer.returnValue(None)
+
+    def load_jinja2_template(self, template_dir, template_filename, template_vars):
+        """Loads a jinja2 template with variables to insert
+
+        Args:
+            template_dir (str): The directory where templates are stored
+            template_filename (str): The name of the template in the template_dir
+            template_vars (Dict): Dictionary of keys in the template
+                alongside their values to insert
+
+        Returns:
+            str containing the contents of the rendered template
+        """
+        loader = jinja2.FileSystemLoader(template_dir)
+        env = jinja2.Environment(loader=loader)
+
+        template = env.get_template(template_filename)
+        return template.render(**template_vars)
+
+    @defer.inlineCallbacks
+    def on_POST(self, request, medium):
+        if medium != "email":
+            raise SynapseError(
+                400,
+                "This medium is currently not supported for password resets",
+            )
+
+        body = parse_json_object_from_request(request)
+        assert_params_in_dict(body, [
+            'sid', 'client_secret', 'token',
+        ])
+
+        valid, _ = yield self.datastore.validate_threepid_validation_token(
+            body['sid'],
+            body['client_secret'],
+            body['token'],
+            self.clock.time_msec(),
+        )
+        response_code = 200 if valid else 400
+
+        defer.returnValue((response_code, {"success": valid}))
+
+
 class PasswordRestServlet(RestServlet):
     PATTERNS = client_patterns("/account/password$")
 
@@ -144,6 +375,7 @@ class PasswordRestServlet(RestServlet):
             result, params, _ = yield self.auth_handler.check_auth(
                 [[LoginType.EMAIL_IDENTITY], [LoginType.MSISDN]],
                 body, self.hs.get_ip_from_request(request),
+                password_servlet=True,
             )
 
             if LoginType.EMAIL_IDENTITY in result:
@@ -417,6 +649,7 @@ class WhoamiRestServlet(RestServlet):
 def register_servlets(hs, http_server):
     EmailPasswordRequestTokenRestServlet(hs).register(http_server)
     MsisdnPasswordRequestTokenRestServlet(hs).register(http_server)
+    PasswordResetSubmitTokenServlet(hs).register(http_server)
     PasswordRestServlet(hs).register(http_server)
     DeactivateAccountRestServlet(hs).register(http_server)
     EmailThreepidRequestTokenRestServlet(hs).register(http_server)
diff --git a/synapse/rest/client/versions.py b/synapse/rest/client/versions.py
index 27e7cbf3cc..babbf6a23c 100644
--- a/synapse/rest/client/versions.py
+++ b/synapse/rest/client/versions.py
@@ -39,6 +39,7 @@ class VersionsRestServlet(RestServlet):
                 "r0.2.0",
                 "r0.3.0",
                 "r0.4.0",
+                "r0.5.0",
             ],
             # as per MSC1497:
             "unstable_features": {
diff --git a/synapse/rest/key/v2/remote_key_resource.py b/synapse/rest/key/v2/remote_key_resource.py
index 21c3c807b9..8a730bbc35 100644
--- a/synapse/rest/key/v2/remote_key_resource.py
+++ b/synapse/rest/key/v2/remote_key_resource.py
@@ -20,7 +20,7 @@ from twisted.web.resource import Resource
 from twisted.web.server import NOT_DONE_YET
 
 from synapse.api.errors import Codes, SynapseError
-from synapse.crypto.keyring import KeyLookupError, ServerKeyFetcher
+from synapse.crypto.keyring import ServerKeyFetcher
 from synapse.http.server import respond_with_json_bytes, wrap_json_request_handler
 from synapse.http.servlet import parse_integer, parse_json_object_from_request
 
@@ -215,15 +215,7 @@ class RemoteKey(Resource):
                     json_results.add(bytes(result["key_json"]))
 
         if cache_misses and query_remote_on_cache_miss:
-            for server_name, key_ids in cache_misses.items():
-                try:
-                    yield self.fetcher.get_server_verify_key_v2_direct(
-                        server_name, key_ids
-                    )
-                except KeyLookupError as e:
-                    logger.info("Failed to fetch key: %s", e)
-                except Exception:
-                    logger.exception("Failed to get key for %r", server_name)
+            yield self.fetcher.get_keys(cache_misses)
             yield self.query_keys(
                 request, query, query_remote_on_cache_miss=False
             )
diff --git a/synapse/storage/_base.py b/synapse/storage/_base.py
index 52891bb9eb..ae891aa332 100644
--- a/synapse/storage/_base.py
+++ b/synapse/storage/_base.py
@@ -588,6 +588,10 @@ class SQLBaseStore(object):
         Args:
             table : string giving the table name
             values : dict of new column names and values for them
+            or_ignore : bool stating whether an exception should be raised
+                when a conflicting row already exists. If True, False will be
+                returned by the function instead
+            desc : string giving a description of the transaction
 
         Returns:
             bool: Whether the row was inserted or not. Only useful when
@@ -1228,8 +1232,8 @@ class SQLBaseStore(object):
         )
 
         txn.execute(select_sql, list(keyvalues.values()))
-
         row = txn.fetchone()
+
         if not row:
             if allow_none:
                 return None
diff --git a/synapse/storage/events_worker.py b/synapse/storage/events_worker.py
index 1782428048..cc7df5cf14 100644
--- a/synapse/storage/events_worker.py
+++ b/synapse/storage/events_worker.py
@@ -78,6 +78,43 @@ class EventsWorkerStore(SQLBaseStore):
             desc="get_received_ts",
         )
 
+    def get_received_ts_by_stream_pos(self, stream_ordering):
+        """Given a stream ordering get an approximate timestamp of when it
+        happened.
+
+        This is done by simply taking the received ts of the first event that
+        has a stream ordering greater than or equal to the given stream pos.
+        If none exists returns the current time, on the assumption that it must
+        have happened recently.
+
+        Args:
+            stream_ordering (int)
+
+        Returns:
+            Deferred[int]
+        """
+
+        def _get_approximate_received_ts_txn(txn):
+            sql = """
+                SELECT received_ts FROM events
+                WHERE stream_ordering >= ?
+                LIMIT 1
+            """
+
+            txn.execute(sql, (stream_ordering,))
+            row = txn.fetchone()
+            if row and row[0]:
+                ts = row[0]
+            else:
+                ts = self.clock.time_msec()
+
+            return ts
+
+        return self.runInteraction(
+            "get_approximate_received_ts",
+            _get_approximate_received_ts_txn,
+        )
+
     @defer.inlineCallbacks
     def get_event(
         self,
diff --git a/synapse/storage/prepare_database.py b/synapse/storage/prepare_database.py
index b81c05369f..f2c1bed487 100644
--- a/synapse/storage/prepare_database.py
+++ b/synapse/storage/prepare_database.py
@@ -27,7 +27,7 @@ logger = logging.getLogger(__name__)
 
 # Remember to update this number every time a change is made to database
 # schema files, so the users will be informed on server restarts.
-SCHEMA_VERSION = 54
+SCHEMA_VERSION = 55
 
 dir_path = os.path.abspath(os.path.dirname(__file__))
 
diff --git a/synapse/storage/registration.py b/synapse/storage/registration.py
index 4cf159ba81..9b41cbd757 100644
--- a/synapse/storage/registration.py
+++ b/synapse/storage/registration.py
@@ -17,17 +17,20 @@
 
 import re
 
+from six import iterkeys
 from six.moves import range
 
 from twisted.internet import defer
 
 from synapse.api.constants import UserTypes
-from synapse.api.errors import Codes, StoreError
+from synapse.api.errors import Codes, StoreError, ThreepidValidationError
 from synapse.storage import background_updates
 from synapse.storage._base import SQLBaseStore
 from synapse.types import UserID
 from synapse.util.caches.descriptors import cached, cachedInlineCallbacks
 
+THIRTY_MINUTES_IN_MS = 30 * 60 * 1000
+
 
 class RegistrationWorkerStore(SQLBaseStore):
     def __init__(self, db_conn, hs):
@@ -422,7 +425,7 @@ class RegistrationWorkerStore(SQLBaseStore):
         defer.returnValue(None)
 
     @defer.inlineCallbacks
-    def get_user_id_by_threepid(self, medium, address):
+    def get_user_id_by_threepid(self, medium, address, require_verified=False):
         """Returns user id from threepid
 
         Args:
@@ -595,6 +598,11 @@ class RegistrationStore(
             "user_threepids_grandfather", self._bg_user_threepids_grandfather,
         )
 
+        # Create a background job for culling expired 3PID validity tokens
+        hs.get_clock().looping_call(
+            self.cull_expired_threepid_validation_tokens, THIRTY_MINUTES_IN_MS,
+        )
+
     @defer.inlineCallbacks
     def add_access_token_to_user(self, user_id, token, device_id=None):
         """Adds an access token for the given user.
@@ -963,7 +971,6 @@ class RegistrationStore(
         We do this by grandfathering in existing user threepids assuming that
         they used one of the server configured trusted identity servers.
         """
-
         id_servers = set(self.config.trusted_third_party_id_servers)
 
         def _bg_user_threepids_grandfather_txn(txn):
@@ -984,3 +991,280 @@ class RegistrationStore(
         yield self._end_background_update("user_threepids_grandfather")
 
         defer.returnValue(1)
+
+    def get_threepid_validation_session(
+        self,
+        medium,
+        client_secret,
+        address=None,
+        sid=None,
+        validated=None,
+    ):
+        """Gets a session_id and last_send_attempt (if available) for a
+        client_secret/medium/(address|session_id) combo
+
+        Args:
+            medium (str|None): The medium of the 3PID
+            address (str|None): The address of the 3PID
+            sid (str|None): The ID of the validation session
+            client_secret (str|None): A unique string provided by the client to
+                help identify this validation attempt
+            validated (bool|None): Whether sessions should be filtered by
+                whether they have been validated already or not. None to
+                perform no filtering
+
+        Returns:
+            deferred {str, int}|None: A dict containing the
+                latest session_id and send_attempt count for this 3PID.
+                Otherwise None if there hasn't been a previous attempt
+        """
+        keyvalues = {
+            "medium": medium,
+            "client_secret": client_secret,
+        }
+        if address:
+            keyvalues["address"] = address
+        if sid:
+            keyvalues["session_id"] = sid
+
+        assert(address or sid)
+
+        def get_threepid_validation_session_txn(txn):
+            sql = """
+                SELECT address, session_id, medium, client_secret,
+                last_send_attempt, validated_at
+                FROM threepid_validation_session WHERE %s
+                """ % (" AND ".join("%s = ?" % k for k in iterkeys(keyvalues)),)
+
+            if validated is not None:
+                sql += " AND validated_at IS " + ("NOT NULL" if validated else "NULL")
+
+            sql += " LIMIT 1"
+
+            txn.execute(sql, list(keyvalues.values()))
+            rows = self.cursor_to_dict(txn)
+            if not rows:
+                return None
+
+            return rows[0]
+
+        return self.runInteraction(
+            "get_threepid_validation_session",
+            get_threepid_validation_session_txn,
+        )
+
+    def validate_threepid_session(
+        self,
+        session_id,
+        client_secret,
+        token,
+        current_ts,
+    ):
+        """Attempt to validate a threepid session using a token
+
+        Args:
+            session_id (str): The id of a validation session
+            client_secret (str): A unique string provided by the client to
+                help identify this validation attempt
+            token (str): A validation token
+            current_ts (int): The current unix time in milliseconds. Used for
+                checking token expiry status
+
+        Returns:
+            deferred str|None: A str representing a link to redirect the user
+            to if there is one.
+        """
+        # Insert everything into a transaction in order to run atomically
+        def validate_threepid_session_txn(txn):
+            row = self._simple_select_one_txn(
+                txn,
+                table="threepid_validation_session",
+                keyvalues={"session_id": session_id},
+                retcols=["client_secret", "validated_at"],
+                allow_none=True,
+            )
+
+            if not row:
+                raise ThreepidValidationError(400, "Unknown session_id")
+            retrieved_client_secret = row["client_secret"]
+            validated_at = row["validated_at"]
+
+            if retrieved_client_secret != client_secret:
+                raise ThreepidValidationError(
+                    400, "This client_secret does not match the provided session_id",
+                )
+
+            row = self._simple_select_one_txn(
+                txn,
+                table="threepid_validation_token",
+                keyvalues={"session_id": session_id, "token": token},
+                retcols=["expires", "next_link"],
+                allow_none=True,
+            )
+
+            if not row:
+                raise ThreepidValidationError(
+                    400, "Validation token not found or has expired",
+                )
+            expires = row["expires"]
+            next_link = row["next_link"]
+
+            # If the session is already validated, no need to revalidate
+            if validated_at:
+                return next_link
+
+            if expires <= current_ts:
+                raise ThreepidValidationError(
+                    400, "This token has expired. Please request a new one",
+                )
+
+            # Looks good. Validate the session
+            self._simple_update_txn(
+                txn,
+                table="threepid_validation_session",
+                keyvalues={"session_id": session_id},
+                updatevalues={"validated_at": self.clock.time_msec()},
+            )
+
+            return next_link
+
+        # Return next_link if it exists
+        return self.runInteraction(
+            "validate_threepid_session_txn",
+            validate_threepid_session_txn,
+        )
+
+    def upsert_threepid_validation_session(
+        self,
+        medium,
+        address,
+        client_secret,
+        send_attempt,
+        session_id,
+        validated_at=None,
+    ):
+        """Upsert a threepid validation session
+        Args:
+            medium (str): The medium of the 3PID
+            address (str): The address of the 3PID
+            client_secret (str): A unique string provided by the client to
+                help identify this validation attempt
+            send_attempt (int): The latest send_attempt on this session
+            session_id (str): The id of this validation session
+            validated_at (int|None): The unix timestamp in milliseconds of
+                when the session was marked as valid
+        """
+        insertion_values = {
+            "medium": medium,
+            "address": address,
+            "client_secret": client_secret,
+        }
+
+        if validated_at:
+            insertion_values["validated_at"] = validated_at
+
+        return self._simple_upsert(
+            table="threepid_validation_session",
+            keyvalues={"session_id": session_id},
+            values={"last_send_attempt": send_attempt},
+            insertion_values=insertion_values,
+            desc="upsert_threepid_validation_session",
+        )
+
+    def start_or_continue_validation_session(
+        self,
+        medium,
+        address,
+        session_id,
+        client_secret,
+        send_attempt,
+        next_link,
+        token,
+        token_expires,
+    ):
+        """Creates a new threepid validation session if it does not already
+        exist and associates a new validation token with it
+
+        Args:
+            medium (str): The medium of the 3PID
+            address (str): The address of the 3PID
+            session_id (str): The id of this validation session
+            client_secret (str): A unique string provided by the client to
+                help identify this validation attempt
+            send_attempt (int): The latest send_attempt on this session
+            next_link (str|None): The link to redirect the user to upon
+                successful validation
+            token (str): The validation token
+            token_expires (int): The timestamp for which after the token
+                will no longer be valid
+        """
+        def start_or_continue_validation_session_txn(txn):
+            # Create or update a validation session
+            self._simple_upsert_txn(
+                txn,
+                table="threepid_validation_session",
+                keyvalues={"session_id": session_id},
+                values={"last_send_attempt": send_attempt},
+                insertion_values={
+                    "medium": medium,
+                    "address": address,
+                    "client_secret": client_secret,
+                },
+            )
+
+            # Create a new validation token with this session ID
+            self._simple_insert_txn(
+                txn,
+                table="threepid_validation_token",
+                values={
+                    "session_id": session_id,
+                    "token": token,
+                    "next_link": next_link,
+                    "expires": token_expires,
+                },
+            )
+
+        return self.runInteraction(
+            "start_or_continue_validation_session",
+            start_or_continue_validation_session_txn,
+        )
+
+    def cull_expired_threepid_validation_tokens(self):
+        """Remove threepid validation tokens with expiry dates that have passed"""
+        def cull_expired_threepid_validation_tokens_txn(txn, ts):
+            sql = """
+            DELETE FROM threepid_validation_token WHERE
+            expires < ?
+            """
+            return txn.execute(sql, (ts,))
+
+        return self.runInteraction(
+            "cull_expired_threepid_validation_tokens",
+            cull_expired_threepid_validation_tokens_txn,
+            self.clock.time_msec(),
+        )
+
+    def delete_threepid_session(self, session_id):
+        """Removes a threepid validation session from the database. This can
+        be done after validation has been performed and whatever action was
+        waiting on it has been carried out
+
+        Args:
+            session_id (str): The ID of the session to delete
+        """
+        def delete_threepid_session_txn(txn):
+            self._simple_delete_txn(
+                txn,
+                table="threepid_validation_token",
+                keyvalues={"session_id": session_id},
+            )
+            self._simple_delete_txn(
+                txn,
+                table="threepid_validation_session",
+                keyvalues={"session_id": session_id},
+            )
+
+        return self.runInteraction(
+            "delete_threepid_session",
+            delete_threepid_session_txn,
+        )
diff --git a/synapse/storage/schema/delta/55/track_threepid_validations.sql b/synapse/storage/schema/delta/55/track_threepid_validations.sql
new file mode 100644
index 0000000000..a8eced2e0a
--- /dev/null
+++ b/synapse/storage/schema/delta/55/track_threepid_validations.sql
@@ -0,0 +1,31 @@
+/* Copyright 2019 The Matrix.org Foundation C.I.C.
+ *
+ * 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.
+ */
+CREATE TABLE IF NOT EXISTS threepid_validation_session (
+    session_id TEXT PRIMARY KEY,
+    medium TEXT NOT NULL,
+    address TEXT NOT NULL,
+    client_secret TEXT NOT NULL,
+    last_send_attempt BIGINT NOT NULL,
+    validated_at BIGINT
+);
+
+CREATE TABLE IF NOT EXISTS threepid_validation_token (
+    token TEXT PRIMARY KEY,
+    session_id TEXT NOT NULL,
+    next_link TEXT,
+    expires BIGINT NOT NULL
+);
+
+CREATE INDEX threepid_validation_token_session_id ON threepid_validation_token(session_id);
diff --git a/synapse/storage/stats.py b/synapse/storage/stats.py
index 1c0b183a56..ff266b09b0 100644
--- a/synapse/storage/stats.py
+++ b/synapse/storage/stats.py
@@ -328,6 +328,22 @@ class StatsStore(StateDeltasStore):
             room_id (str)
             fields (dict[str:Any])
         """
+
+        # For whatever reason some of the fields may contain null bytes, which
+        # postgres isn't a fan of, so we replace those fields with null.
+        for col in (
+            "join_rules",
+            "history_visibility",
+            "encryption",
+            "name",
+            "topic",
+            "avatar",
+            "canonical_alias"
+        ):
+            field = fields.get(col)
+            if field and "\0" in field:
+                fields[col] = None
+
         return self._simple_upsert(
             table="room_state",
             keyvalues={"room_id": room_id},
diff --git a/synapse/storage/stream.py b/synapse/storage/stream.py
index 529ad4ea79..6f7f65d96b 100644
--- a/synapse/storage/stream.py
+++ b/synapse/storage/stream.py
@@ -592,8 +592,18 @@ class StreamWorkerStore(EventsWorkerStore, SQLBaseStore):
         )
 
     def get_max_topological_token(self, room_id, stream_key):
+        """Get the max topological token in a room before the given stream
+        ordering.
+
+        Args:
+            room_id (str)
+            stream_key (int)
+
+        Returns:
+            Deferred[int]
+        """
         sql = (
-            "SELECT max(topological_ordering) FROM events"
+            "SELECT coalesce(max(topological_ordering), 0) FROM events"
             " WHERE room_id = ? AND stream_ordering < ?"
         )
         return self._execute(
diff --git a/synapse/util/retryutils.py b/synapse/util/retryutils.py
index 26cce7d197..1a77456498 100644
--- a/synapse/util/retryutils.py
+++ b/synapse/util/retryutils.py
@@ -46,8 +46,7 @@ class NotRetryingDestination(Exception):
 
 
 @defer.inlineCallbacks
-def get_retry_limiter(destination, clock, store, ignore_backoff=False,
-                      **kwargs):
+def get_retry_limiter(destination, clock, store, ignore_backoff=False, **kwargs):
     """For a given destination check if we have previously failed to
     send a request there and are waiting before retrying the destination.
     If we are not ready to retry the destination, this will raise a
@@ -60,8 +59,7 @@ def get_retry_limiter(destination, clock, store, ignore_backoff=False,
         clock (synapse.util.clock): timing source
         store (synapse.storage.transactions.TransactionStore): datastore
         ignore_backoff (bool): true to ignore the historical backoff data and
-            try the request anyway. We will still update the next
-            retry_interval on success/failure.
+            try the request anyway. We will still reset the retry_interval on success.
 
     Example usage:
 
@@ -75,13 +73,12 @@ def get_retry_limiter(destination, clock, store, ignore_backoff=False,
     """
     retry_last_ts, retry_interval = (0, 0)
 
-    retry_timings = yield store.get_destination_retry_timings(
-        destination
-    )
+    retry_timings = yield store.get_destination_retry_timings(destination)
 
     if retry_timings:
         retry_last_ts, retry_interval = (
-            retry_timings["retry_last_ts"], retry_timings["retry_interval"]
+            retry_timings["retry_last_ts"],
+            retry_timings["retry_interval"],
         )
 
         now = int(clock.time_msec())
@@ -93,22 +90,36 @@ def get_retry_limiter(destination, clock, store, ignore_backoff=False,
                 destination=destination,
             )
 
+    # if we are ignoring the backoff data, we should also not increment the backoff
+    # when we get another failure - otherwise a server can very quickly reach the
+    # maximum backoff even though it might only have been down briefly
+    backoff_on_failure = not ignore_backoff
+
     defer.returnValue(
         RetryDestinationLimiter(
             destination,
             clock,
             store,
             retry_interval,
+            backoff_on_failure=backoff_on_failure,
             **kwargs
         )
     )
 
 
 class RetryDestinationLimiter(object):
-    def __init__(self, destination, clock, store, retry_interval,
-                 min_retry_interval=10 * 60 * 1000,
-                 max_retry_interval=24 * 60 * 60 * 1000,
-                 multiplier_retry_interval=5, backoff_on_404=False):
+    def __init__(
+        self,
+        destination,
+        clock,
+        store,
+        retry_interval,
+        min_retry_interval=10 * 60 * 1000,
+        max_retry_interval=24 * 60 * 60 * 1000,
+        multiplier_retry_interval=5,
+        backoff_on_404=False,
+        backoff_on_failure=True,
+    ):
         """Marks the destination as "down" if an exception is thrown in the
         context, except for CodeMessageException with code < 500.
 
@@ -128,6 +139,9 @@ class RetryDestinationLimiter(object):
             multiplier_retry_interval (int): The multiplier to use to increase
                 the retry interval after a failed request.
             backoff_on_404 (bool): Back off if we get a 404
+
+            backoff_on_failure (bool): set to False if we should not increase the
+                retry interval on a failure.
         """
         self.clock = clock
         self.store = store
@@ -138,6 +152,7 @@ class RetryDestinationLimiter(object):
         self.max_retry_interval = max_retry_interval
         self.multiplier_retry_interval = multiplier_retry_interval
         self.backoff_on_404 = backoff_on_404
+        self.backoff_on_failure = backoff_on_failure
 
     def __enter__(self):
         pass
@@ -173,10 +188,13 @@ class RetryDestinationLimiter(object):
             if not self.retry_interval:
                 return
 
-            logger.debug("Connection to %s was successful; clearing backoff",
-                         self.destination)
+            logger.debug(
+                "Connection to %s was successful; clearing backoff", self.destination
+            )
             retry_last_ts = 0
             self.retry_interval = 0
+        elif not self.backoff_on_failure:
+            return
         else:
             # We couldn't connect.
             if self.retry_interval:
@@ -190,7 +208,10 @@ class RetryDestinationLimiter(object):
 
             logger.info(
                 "Connection to %s was unsuccessful (%s(%s)); backoff now %i",
-                self.destination, exc_type, exc_val, self.retry_interval
+                self.destination,
+                exc_type,
+                exc_val,
+                self.retry_interval,
             )
             retry_last_ts = int(self.clock.time_msec())
 
@@ -201,9 +222,7 @@ class RetryDestinationLimiter(object):
                     self.destination, retry_last_ts, self.retry_interval
                 )
             except Exception:
-                logger.exception(
-                    "Failed to store destination_retry_timings",
-                )
+                logger.exception("Failed to store destination_retry_timings")
 
         # we deliberately do this in the background.
         synapse.util.logcontext.run_in_background(store_retry_timings)
diff --git a/tests/crypto/test_keyring.py b/tests/crypto/test_keyring.py
index 3933ad4347..4b1901ce31 100644
--- a/tests/crypto/test_keyring.py
+++ b/tests/crypto/test_keyring.py
@@ -19,16 +19,13 @@ from mock import Mock
 import canonicaljson
 import signedjson.key
 import signedjson.sign
+from signedjson.key import encode_verify_key_base64, get_verify_key
 
 from twisted.internet import defer
 
 from synapse.api.errors import SynapseError
 from synapse.crypto import keyring
-from synapse.crypto.keyring import (
-    KeyLookupError,
-    PerspectivesKeyFetcher,
-    ServerKeyFetcher,
-)
+from synapse.crypto.keyring import PerspectivesKeyFetcher, ServerKeyFetcher
 from synapse.storage.keys import FetchKeyResult
 from synapse.util import logcontext
 from synapse.util.logcontext import LoggingContext
@@ -43,7 +40,7 @@ class MockPerspectiveServer(object):
 
     def get_verify_keys(self):
         vk = signedjson.key.get_verify_key(self.key)
-        return {"%s:%s" % (vk.alg, vk.version): vk}
+        return {"%s:%s" % (vk.alg, vk.version): encode_verify_key_base64(vk)}
 
     def get_signed_key(self, server_name, verify_key):
         key_id = "%s:%s" % (verify_key.alg, verify_key.version)
@@ -51,9 +48,7 @@ class MockPerspectiveServer(object):
             "server_name": server_name,
             "old_verify_keys": {},
             "valid_until_ts": time.time() * 1000 + 3600,
-            "verify_keys": {
-                key_id: {"key": signedjson.key.encode_verify_key_base64(verify_key)}
-            },
+            "verify_keys": {key_id: {"key": encode_verify_key_base64(verify_key)}},
         }
         self.sign_response(res)
         return res
@@ -66,10 +61,18 @@ class KeyringTestCase(unittest.HomeserverTestCase):
     def make_homeserver(self, reactor, clock):
         self.mock_perspective_server = MockPerspectiveServer()
         self.http_client = Mock()
-        hs = self.setup_test_homeserver(handlers=None, http_client=self.http_client)
-        keys = self.mock_perspective_server.get_verify_keys()
-        hs.config.perspectives = {self.mock_perspective_server.server_name: keys}
-        return hs
+
+        config = self.default_config()
+        config["trusted_key_servers"] = [
+            {
+                "server_name": self.mock_perspective_server.server_name,
+                "verify_keys": self.mock_perspective_server.get_verify_keys(),
+            }
+        ]
+
+        return self.setup_test_homeserver(
+            handlers=None, http_client=self.http_client, config=config
+        )
 
     def check_context(self, _, expected):
         self.assertEquals(
@@ -137,7 +140,7 @@ class KeyringTestCase(unittest.HomeserverTestCase):
                 context_11.request = "11"
 
                 res_deferreds = kr.verify_json_objects_for_server(
-                    [("server10", json1), ("server11", {})]
+                    [("server10", json1, 0, "test10"), ("server11", {}, 0, "test11")]
                 )
 
                 # the unsigned json should be rejected pretty quickly
@@ -174,7 +177,7 @@ class KeyringTestCase(unittest.HomeserverTestCase):
                 self.http_client.post_json.return_value = defer.Deferred()
 
                 res_deferreds_2 = kr.verify_json_objects_for_server(
-                    [("server10", json1)]
+                    [("server10", json1, 0, "test")]
                 )
                 res_deferreds_2[0].addBoth(self.check_context, None)
                 yield logcontext.make_deferred_yieldable(res_deferreds_2[0])
@@ -197,31 +200,108 @@ class KeyringTestCase(unittest.HomeserverTestCase):
         kr = keyring.Keyring(self.hs)
 
         key1 = signedjson.key.generate_signing_key(1)
-        key1_id = "%s:%s" % (key1.alg, key1.version)
-
         r = self.hs.datastore.store_server_verify_keys(
             "server9",
             time.time() * 1000,
-            [
-                (
-                    "server9",
-                    key1_id,
-                    FetchKeyResult(signedjson.key.get_verify_key(key1), 1000),
-                ),
-            ],
+            [("server9", get_key_id(key1), FetchKeyResult(get_verify_key(key1), 1000))],
         )
         self.get_success(r)
+
         json1 = {}
         signedjson.sign.sign_json(json1, "server9", key1)
 
         # should fail immediately on an unsigned object
-        d = _verify_json_for_server(kr, "server9", {})
+        d = _verify_json_for_server(kr, "server9", {}, 0, "test unsigned")
         self.failureResultOf(d, SynapseError)
 
-        d = _verify_json_for_server(kr, "server9", json1)
-        self.assertFalse(d.called)
+        # should suceed on a signed object
+        d = _verify_json_for_server(kr, "server9", json1, 500, "test signed")
+        # self.assertFalse(d.called)
         self.get_success(d)
 
+    def test_verify_json_dedupes_key_requests(self):
+        """Two requests for the same key should be deduped."""
+        key1 = signedjson.key.generate_signing_key(1)
+
+        def get_keys(keys_to_fetch):
+            # there should only be one request object (with the max validity)
+            self.assertEqual(keys_to_fetch, {"server1": {get_key_id(key1): 1500}})
+
+            return defer.succeed(
+                {
+                    "server1": {
+                        get_key_id(key1): FetchKeyResult(get_verify_key(key1), 1200)
+                    }
+                }
+            )
+
+        mock_fetcher = keyring.KeyFetcher()
+        mock_fetcher.get_keys = Mock(side_effect=get_keys)
+        kr = keyring.Keyring(self.hs, key_fetchers=(mock_fetcher,))
+
+        json1 = {}
+        signedjson.sign.sign_json(json1, "server1", key1)
+
+        # the first request should succeed; the second should fail because the key
+        # has expired
+        results = kr.verify_json_objects_for_server(
+            [("server1", json1, 500, "test1"), ("server1", json1, 1500, "test2")]
+        )
+        self.assertEqual(len(results), 2)
+        self.get_success(results[0])
+        e = self.get_failure(results[1], SynapseError).value
+        self.assertEqual(e.errcode, "M_UNAUTHORIZED")
+        self.assertEqual(e.code, 401)
+
+        # there should have been a single call to the fetcher
+        mock_fetcher.get_keys.assert_called_once()
+
+    def test_verify_json_falls_back_to_other_fetchers(self):
+        """If the first fetcher cannot provide a recent enough key, we fall back"""
+        key1 = signedjson.key.generate_signing_key(1)
+
+        def get_keys1(keys_to_fetch):
+            self.assertEqual(keys_to_fetch, {"server1": {get_key_id(key1): 1500}})
+            return defer.succeed(
+                {
+                    "server1": {
+                        get_key_id(key1): FetchKeyResult(get_verify_key(key1), 800)
+                    }
+                }
+            )
+
+        def get_keys2(keys_to_fetch):
+            self.assertEqual(keys_to_fetch, {"server1": {get_key_id(key1): 1500}})
+            return defer.succeed(
+                {
+                    "server1": {
+                        get_key_id(key1): FetchKeyResult(get_verify_key(key1), 1200)
+                    }
+                }
+            )
+
+        mock_fetcher1 = keyring.KeyFetcher()
+        mock_fetcher1.get_keys = Mock(side_effect=get_keys1)
+        mock_fetcher2 = keyring.KeyFetcher()
+        mock_fetcher2.get_keys = Mock(side_effect=get_keys2)
+        kr = keyring.Keyring(self.hs, key_fetchers=(mock_fetcher1, mock_fetcher2))
+
+        json1 = {}
+        signedjson.sign.sign_json(json1, "server1", key1)
+
+        results = kr.verify_json_objects_for_server(
+            [("server1", json1, 1200, "test1"), ("server1", json1, 1500, "test2")]
+        )
+        self.assertEqual(len(results), 2)
+        self.get_success(results[0])
+        e = self.get_failure(results[1], SynapseError).value
+        self.assertEqual(e.errcode, "M_UNAUTHORIZED")
+        self.assertEqual(e.code, 401)
+
+        # there should have been a single call to each fetcher
+        mock_fetcher1.get_keys.assert_called_once()
+        mock_fetcher2.get_keys.assert_called_once()
+
 
 class ServerKeyFetcherTestCase(unittest.HomeserverTestCase):
     def make_homeserver(self, reactor, clock):
@@ -260,8 +340,8 @@ class ServerKeyFetcherTestCase(unittest.HomeserverTestCase):
 
         self.http_client.get_json.side_effect = get_json
 
-        server_name_and_key_ids = [(SERVER_NAME, ("key1",))]
-        keys = self.get_success(fetcher.get_keys(server_name_and_key_ids))
+        keys_to_fetch = {SERVER_NAME: {"key1": 0}}
+        keys = self.get_success(fetcher.get_keys(keys_to_fetch))
         k = keys[SERVER_NAME][testverifykey_id]
         self.assertEqual(k.valid_until_ts, VALID_UNTIL_TS)
         self.assertEqual(k.verify_key, testverifykey)
@@ -286,21 +366,29 @@ class ServerKeyFetcherTestCase(unittest.HomeserverTestCase):
             bytes(res["key_json"]), canonicaljson.encode_canonical_json(response)
         )
 
-        # change the server name: it should cause a rejection
+        # change the server name: the result should be ignored
         response["server_name"] = "OTHER_SERVER"
-        self.get_failure(
-            fetcher.get_keys(server_name_and_key_ids), KeyLookupError
-        )
+
+        keys = self.get_success(fetcher.get_keys(keys_to_fetch))
+        self.assertEqual(keys, {})
 
 
 class PerspectivesKeyFetcherTestCase(unittest.HomeserverTestCase):
     def make_homeserver(self, reactor, clock):
         self.mock_perspective_server = MockPerspectiveServer()
         self.http_client = Mock()
-        hs = self.setup_test_homeserver(handlers=None, http_client=self.http_client)
-        keys = self.mock_perspective_server.get_verify_keys()
-        hs.config.perspectives = {self.mock_perspective_server.server_name: keys}
-        return hs
+
+        config = self.default_config()
+        config["trusted_key_servers"] = [
+            {
+                "server_name": self.mock_perspective_server.server_name,
+                "verify_keys": self.mock_perspective_server.get_verify_keys(),
+            }
+        ]
+
+        return self.setup_test_homeserver(
+            handlers=None, http_client=self.http_client, config=config
+        )
 
     def test_get_keys_from_perspectives(self):
         # arbitrarily advance the clock a bit
@@ -342,8 +430,8 @@ class PerspectivesKeyFetcherTestCase(unittest.HomeserverTestCase):
 
         self.http_client.post_json.side_effect = post_json
 
-        server_name_and_key_ids = [(SERVER_NAME, ("key1",))]
-        keys = self.get_success(fetcher.get_keys(server_name_and_key_ids))
+        keys_to_fetch = {SERVER_NAME: {"key1": 0}}
+        keys = self.get_success(fetcher.get_keys(keys_to_fetch))
         self.assertIn(SERVER_NAME, keys)
         k = keys[SERVER_NAME][testverifykey_id]
         self.assertEqual(k.valid_until_ts, VALID_UNTIL_TS)
@@ -365,8 +453,7 @@ class PerspectivesKeyFetcherTestCase(unittest.HomeserverTestCase):
         self.assertEqual(res["ts_valid_until_ms"], VALID_UNTIL_TS)
 
         self.assertEqual(
-            bytes(res["key_json"]),
-            canonicaljson.encode_canonical_json(response),
+            bytes(res["key_json"]), canonicaljson.encode_canonical_json(response)
         )
 
     def test_invalid_perspectives_responses(self):
@@ -401,7 +488,7 @@ class PerspectivesKeyFetcherTestCase(unittest.HomeserverTestCase):
 
         def get_key_from_perspectives(response):
             fetcher = PerspectivesKeyFetcher(self.hs)
-            server_name_and_key_ids = [(SERVER_NAME, ("key1",))]
+            keys_to_fetch = {SERVER_NAME: {"key1": 0}}
 
             def post_json(destination, path, data, **kwargs):
                 self.assertEqual(destination, self.mock_perspective_server.server_name)
@@ -410,9 +497,7 @@ class PerspectivesKeyFetcherTestCase(unittest.HomeserverTestCase):
 
             self.http_client.post_json.side_effect = post_json
 
-            return self.get_success(
-                fetcher.get_keys(server_name_and_key_ids)
-            )
+            return self.get_success(fetcher.get_keys(keys_to_fetch))
 
         # start with a valid response so we can check we are testing the right thing
         response = build_response()
@@ -435,6 +520,11 @@ class PerspectivesKeyFetcherTestCase(unittest.HomeserverTestCase):
         self.assertEqual(keys, {}, "Expected empty dict with missing origin server sig")
 
 
+def get_key_id(key):
+    """Get the matrix ID tag for a given SigningKey or VerifyKey"""
+    return "%s:%s" % (key.alg, key.version)
+
+
 @defer.inlineCallbacks
 def run_in_context(f, *args, **kwargs):
     with LoggingContext("testctx") as ctx:
@@ -445,14 +535,14 @@ def run_in_context(f, *args, **kwargs):
     defer.returnValue(rv)
 
 
-def _verify_json_for_server(keyring, server_name, json_object):
+def _verify_json_for_server(kr, *args):
     """thin wrapper around verify_json_for_server which makes sure it is wrapped
     with the patched defer.inlineCallbacks.
     """
 
     @defer.inlineCallbacks
     def v():
-        rv1 = yield keyring.verify_json_for_server(server_name, json_object)
+        rv1 = yield kr.verify_json_for_server(*args)
         defer.returnValue(rv1)
 
     return run_in_context(v)
diff --git a/tests/handlers/test_stats.py b/tests/handlers/test_stats.py
index 249aba3d59..2710c991cf 100644
--- a/tests/handlers/test_stats.py
+++ b/tests/handlers/test_stats.py
@@ -204,7 +204,7 @@ class StatsRoomTests(unittest.HomeserverTestCase):
             "a2": {"membership": "not a real thing"},
         }
 
-        def get_event(event_id):
+        def get_event(event_id, allow_none=True):
             m = Mock()
             m.content = events[event_id]
             d = defer.Deferred()
@@ -224,7 +224,7 @@ class StatsRoomTests(unittest.HomeserverTestCase):
                 "room_id": "room",
                 "event_id": "a1",
                 "prev_event_id": "a2",
-                "stream_id": "bleb",
+                "stream_id": 60,
             }
         ]
 
@@ -241,7 +241,7 @@ class StatsRoomTests(unittest.HomeserverTestCase):
                 "room_id": "room",
                 "event_id": "a2",
                 "prev_event_id": "a1",
-                "stream_id": "bleb",
+                "stream_id": 100,
             }
         ]
 
@@ -249,3 +249,59 @@ class StatsRoomTests(unittest.HomeserverTestCase):
         self.assertEqual(
             f.value.args[0], "'not a real thing' is not a valid membership"
         )
+
+    def test_redacted_prev_event(self):
+        """
+        If the prev_event does not exist, then it is assumed to be a LEAVE.
+        """
+        u1 = self.register_user("u1", "pass")
+        u1_token = self.login("u1", "pass")
+
+        room_1 = self.helper.create_room_as(u1, tok=u1_token)
+
+        # Do the initial population of the user directory via the background update
+        self._add_background_updates()
+
+        while not self.get_success(self.store.has_completed_background_updates()):
+            self.get_success(self.store.do_next_background_update(100), by=0.1)
+
+        events = {
+            "a1": None,
+            "a2": {"membership": Membership.JOIN},
+        }
+
+        def get_event(event_id, allow_none=True):
+            if events.get(event_id):
+                m = Mock()
+                m.content = events[event_id]
+            else:
+                m = None
+            d = defer.Deferred()
+            self.reactor.callLater(0.0, d.callback, m)
+            return d
+
+        def get_received_ts(event_id):
+            return defer.succeed(1)
+
+        self.store.get_received_ts = get_received_ts
+        self.store.get_event = get_event
+
+        deltas = [
+            {
+                "type": EventTypes.Member,
+                "state_key": "some_user:test",
+                "room_id": room_1,
+                "event_id": "a2",
+                "prev_event_id": "a1",
+                "stream_id": 100,
+            }
+        ]
+
+        # Handle our fake deltas, which has a user going from LEAVE -> JOIN.
+        self.get_success(self.handler._handle_deltas(deltas))
+
+        # One delta, with two joined members -- the room creator, and our fake
+        # user.
+        r = self.get_success(self.store.get_deltas_for_room(room_1, 0))
+        self.assertEqual(len(r), 1)
+        self.assertEqual(r[0]["joined_members"], 2)
diff --git a/tests/http/federation/test_matrix_federation_agent.py b/tests/http/federation/test_matrix_federation_agent.py
index ed0ca079d9..05880a1048 100644
--- a/tests/http/federation/test_matrix_federation_agent.py
+++ b/tests/http/federation/test_matrix_federation_agent.py
@@ -27,6 +27,7 @@ from twisted.web.http import HTTPChannel
 from twisted.web.http_headers import Headers
 from twisted.web.iweb import IPolicyForHTTPS
 
+from synapse.config.homeserver import HomeServerConfig
 from synapse.crypto.context_factory import ClientTLSOptionsFactory
 from synapse.http.federation.matrix_federation_agent import (
     MatrixFederationAgent,
@@ -52,11 +53,17 @@ class MatrixFederationAgentTests(TestCase):
 
         self.well_known_cache = TTLCache("test_cache", timer=self.reactor.seconds)
 
+        # for now, we disable cert verification for the test, since the cert we
+        # present will not be trusted. We should do better here, though.
+        config_dict = default_config("test", parse=False)
+        config_dict["federation_verify_certificates"] = False
+        config_dict["trusted_key_servers"] = []
+        config = HomeServerConfig()
+        config.parse_config_dict(config_dict)
+
         self.agent = MatrixFederationAgent(
             reactor=self.reactor,
-            tls_client_options_factory=ClientTLSOptionsFactory(
-                default_config("test", parse=True)
-            ),
+            tls_client_options_factory=ClientTLSOptionsFactory(config),
             _well_known_tls_policy=TrustingTLSPolicyForHTTPS(),
             _srv_resolver=self.mock_resolver,
             _well_known_cache=self.well_known_cache,
diff --git a/tests/utils.py b/tests/utils.py
index 200c1ceabe..b2817cf22c 100644
--- a/tests/utils.py
+++ b/tests/utils.py
@@ -131,7 +131,6 @@ def default_config(name, parse=False):
         "password_providers": [],
         "worker_replication_url": "",
         "worker_app": None,
-        "email_enable_notifs": False,
         "block_non_admin_invites": False,
         "federation_domain_whitelist": None,
         "filter_timeline_limit": 5000,