bugfix: E2EE device keys could sometimes not be sent to remote servers (#2466)

* Fix flakey sytest 'Local device key changes get to remote servers'

* Debug logs

* Remove internal/test and use /test only

Remove a lot of ancient code too.

* Use FederationRoomserverAPI in more places

* Use more interfaces in federationapi; begin adding regression test

* Linting

* Add regression test

* Unbreak tests

* ALL THE LOGS

* Fix a race condition which could cause events to not be sent to servers

If a new room event which rewrites state arrives, we remove all joined hosts
then re-calculate them. This wasn't done in a transaction so for a brief period
we would have no joined hosts. During this interim, key change events which arrive
would not be sent to destination servers. This would sporadically fail on sytest.

* Unbreak new tests

* Linting

9 files changed, 418 insertions, 30 deletions

diff --git a/test/event.go b/test/event.go
index 40cb8f0e..73fc656b 100644
--- a/test/event.go
+++ b/test/event.go
@@ -52,6 +52,24 @@ func WithUnsigned(unsigned interface{}) eventModifier {
 	}
 }
 
+func WithKeyID(keyID gomatrixserverlib.KeyID) eventModifier {
+	return func(e *eventMods) {
+		e.keyID = keyID
+	}
+}
+
+func WithPrivateKey(pkey ed25519.PrivateKey) eventModifier {
+	return func(e *eventMods) {
+		e.privKey = pkey
+	}
+}
+
+func WithOrigin(origin gomatrixserverlib.ServerName) eventModifier {
+	return func(e *eventMods) {
+		e.origin = origin
+	}
+}
+
 // Reverse a list of events
 func Reversed(in []*gomatrixserverlib.HeaderedEvent) []*gomatrixserverlib.HeaderedEvent {
 	out := make([]*gomatrixserverlib.HeaderedEvent, len(in))
diff --git a/test/http.go b/test/http.go
index a458a338..37b3648f 100644
--- a/test/http.go
+++ b/test/http.go
@@ -2,10 +2,15 @@ package test
 
 import (
 	"bytes"
+	"context"
 	"encoding/json"
+	"fmt"
 	"io"
+	"net"
 	"net/http"
 	"net/url"
+	"path/filepath"
+	"sync"
 	"testing"
 )
 
@@ -43,3 +48,45 @@ func NewRequest(t *testing.T, method, path string, opts ...HTTPRequestOpt) *http
 	}
 	return req
 }
+
+// ListenAndServe will listen on a random high-numbered port and attach the given router.
+// Returns the base URL to send requests to. Call `cancel` to shutdown the server, which will block until it has closed.
+func ListenAndServe(t *testing.T, router http.Handler, withTLS bool) (apiURL string, cancel func()) {
+	listener, err := net.Listen("tcp", ":0")
+	if err != nil {
+		t.Fatalf("failed to listen: %s", err)
+	}
+	port := listener.Addr().(*net.TCPAddr).Port
+	srv := http.Server{}
+
+	var wg sync.WaitGroup
+	wg.Add(1)
+	go func() {
+		defer wg.Done()
+		srv.Handler = router
+		var err error
+		if withTLS {
+			certFile := filepath.Join(t.TempDir(), "dendrite.cert")
+			keyFile := filepath.Join(t.TempDir(), "dendrite.key")
+			err = NewTLSKey(keyFile, certFile)
+			if err != nil {
+				t.Errorf("failed to make TLS key: %s", err)
+				return
+			}
+			err = srv.ServeTLS(listener, certFile, keyFile)
+		} else {
+			err = srv.Serve(listener)
+		}
+		if err != nil && err != http.ErrServerClosed {
+			t.Logf("Listen failed: %s", err)
+		}
+	}()
+	s := ""
+	if withTLS {
+		s = "s"
+	}
+	return fmt.Sprintf("http%s://localhost:%d", s, port), func() {
+		_ = srv.Shutdown(context.Background())
+		wg.Wait()
+	}
+}
diff --git a/test/keyring.go b/test/keyring.go
new file mode 100644
index 00000000..ed9c3484
--- /dev/null
+++ b/test/keyring.go
@@ -0,0 +1,31 @@
+// Copyright 2020 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.
+
+package test
+
+import (
+	"context"
+
+	"github.com/matrix-org/gomatrixserverlib"
+)
+
+// NopJSONVerifier is a JSONVerifier that verifies nothing and returns no errors.
+type NopJSONVerifier struct {
+	// this verifier verifies nothing
+}
+
+func (t *NopJSONVerifier) VerifyJSONs(ctx context.Context, requests []gomatrixserverlib.VerifyJSONRequest) ([]gomatrixserverlib.VerifyJSONResult, error) {
+	result := make([]gomatrixserverlib.VerifyJSONResult, len(requests))
+	return result, nil
+}
diff --git a/test/keys.go b/test/keys.go
new file mode 100644
index 00000000..75e3800e
--- /dev/null
+++ b/test/keys.go
@@ -0,0 +1,189 @@
+// Copyright 2017 Vector Creations Ltd
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package test
+
+import (
+	"crypto/rand"
+	"crypto/rsa"
+	"crypto/x509"
+	"encoding/base64"
+	"encoding/pem"
+	"errors"
+	"fmt"
+	"io/ioutil"
+	"math/big"
+	"os"
+	"strings"
+	"time"
+)
+
+const (
+	// ServerKeyFile is the name of the file holding the matrix server private key.
+	ServerKeyFile = "server_key.pem"
+	// TLSCertFile is the name of the file holding the TLS certificate used for federation.
+	TLSCertFile = "tls_cert.pem"
+	// TLSKeyFile is the name of the file holding the TLS key used for federation.
+	TLSKeyFile = "tls_key.pem"
+)
+
+// NewMatrixKey generates a new ed25519 matrix server key and writes it to a file.
+func NewMatrixKey(matrixKeyPath string) (err error) {
+	var data [35]byte
+	_, err = rand.Read(data[:])
+	if err != nil {
+		return err
+	}
+	keyOut, err := os.OpenFile(matrixKeyPath, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0600)
+	if err != nil {
+		return err
+	}
+
+	defer (func() {
+		err = keyOut.Close()
+	})()
+
+	keyID := base64.RawURLEncoding.EncodeToString(data[:])
+	keyID = strings.ReplaceAll(keyID, "-", "")
+	keyID = strings.ReplaceAll(keyID, "_", "")
+
+	err = pem.Encode(keyOut, &pem.Block{
+		Type: "MATRIX PRIVATE KEY",
+		Headers: map[string]string{
+			"Key-ID": fmt.Sprintf("ed25519:%s", keyID[:6]),
+		},
+		Bytes: data[3:],
+	})
+	return err
+}
+
+const certificateDuration = time.Hour * 24 * 365 * 10
+
+func generateTLSTemplate(dnsNames []string) (*rsa.PrivateKey, *x509.Certificate, error) {
+	priv, err := rsa.GenerateKey(rand.Reader, 4096)
+	if err != nil {
+		return nil, nil, err
+	}
+
+	notBefore := time.Now()
+	notAfter := notBefore.Add(certificateDuration)
+	serialNumberLimit := new(big.Int).Lsh(big.NewInt(1), 128)
+	serialNumber, err := rand.Int(rand.Reader, serialNumberLimit)
+	if err != nil {
+		return nil, nil, err
+	}
+
+	template := x509.Certificate{
+		SerialNumber:          serialNumber,
+		NotBefore:             notBefore,
+		NotAfter:              notAfter,
+		KeyUsage:              x509.KeyUsageKeyEncipherment | x509.KeyUsageDigitalSignature,
+		ExtKeyUsage:           []x509.ExtKeyUsage{x509.ExtKeyUsageServerAuth},
+		BasicConstraintsValid: true,
+		DNSNames:              dnsNames,
+	}
+	return priv, &template, nil
+}
+
+func writeCertificate(tlsCertPath string, derBytes []byte) error {
+	certOut, err := os.Create(tlsCertPath)
+	if err != nil {
+		return err
+	}
+	defer certOut.Close() // nolint: errcheck
+	return pem.Encode(certOut, &pem.Block{Type: "CERTIFICATE", Bytes: derBytes})
+}
+
+func writePrivateKey(tlsKeyPath string, priv *rsa.PrivateKey) error {
+	keyOut, err := os.OpenFile(tlsKeyPath, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0600)
+	if err != nil {
+		return err
+	}
+	defer keyOut.Close() // nolint: errcheck
+	err = pem.Encode(keyOut, &pem.Block{
+		Type:  "RSA PRIVATE KEY",
+		Bytes: x509.MarshalPKCS1PrivateKey(priv),
+	})
+	return err
+}
+
+// NewTLSKey generates a new RSA TLS key and certificate and writes it to a file.
+func NewTLSKey(tlsKeyPath, tlsCertPath string) error {
+	priv, template, err := generateTLSTemplate(nil)
+	if err != nil {
+		return err
+	}
+
+	// Self-signed certificate: template == parent
+	derBytes, err := x509.CreateCertificate(rand.Reader, template, template, &priv.PublicKey, priv)
+	if err != nil {
+		return err
+	}
+
+	if err = writeCertificate(tlsCertPath, derBytes); err != nil {
+		return err
+	}
+	return writePrivateKey(tlsKeyPath, priv)
+}
+
+func NewTLSKeyWithAuthority(serverName, tlsKeyPath, tlsCertPath, authorityKeyPath, authorityCertPath string) error {
+	priv, template, err := generateTLSTemplate([]string{serverName})
+	if err != nil {
+		return err
+	}
+
+	// load the authority key
+	dat, err := ioutil.ReadFile(authorityKeyPath)
+	if err != nil {
+		return err
+	}
+	block, _ := pem.Decode([]byte(dat))
+	if block == nil || block.Type != "RSA PRIVATE KEY" {
+		return errors.New("authority .key is not a valid pem encoded rsa private key")
+	}
+	authorityPriv, err := x509.ParsePKCS1PrivateKey(block.Bytes)
+	if err != nil {
+		return err
+	}
+
+	// load the authority certificate
+	dat, err = ioutil.ReadFile(authorityCertPath)
+	if err != nil {
+		return err
+	}
+	block, _ = pem.Decode([]byte(dat))
+	if block == nil || block.Type != "CERTIFICATE" {
+		return errors.New("authority .crt is not a valid pem encoded x509 cert")
+	}
+	var caCerts []*x509.Certificate
+	caCerts, err = x509.ParseCertificates(block.Bytes)
+	if err != nil {
+		return err
+	}
+	if len(caCerts) != 1 {
+		return errors.New("authority .crt contains none or more than one cert")
+	}
+	authorityCert := caCerts[0]
+
+	// Sign the new certificate using the authority's key/cert
+	derBytes, err := x509.CreateCertificate(rand.Reader, template, authorityCert, &priv.PublicKey, authorityPriv)
+	if err != nil {
+		return err
+	}
+
+	if err = writeCertificate(tlsCertPath, derBytes); err != nil {
+		return err
+	}
+	return writePrivateKey(tlsKeyPath, priv)
+}
diff --git a/test/room.go b/test/room.go
index 619cb5c9..6ae403b3 100644
--- a/test/room.go
+++ b/test/room.go
@@ -15,7 +15,6 @@
 package test
 
 import (
-	"crypto/ed25519"
 	"encoding/json"
 	"fmt"
 	"sync/atomic"
@@ -35,12 +34,6 @@ var (
 	PresetTrustedPrivateChat Preset = 3
 
 	roomIDCounter = int64(0)
-
-	testKeyID      = gomatrixserverlib.KeyID("ed25519:test")
-	testPrivateKey = ed25519.NewKeyFromSeed([]byte{
-		1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
-		17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
-	})
 )
 
 type Room struct {
@@ -49,22 +42,25 @@ type Room struct {
 	preset  Preset
 	creator *User
 
-	authEvents gomatrixserverlib.AuthEvents
-	events     []*gomatrixserverlib.HeaderedEvent
+	authEvents   gomatrixserverlib.AuthEvents
+	currentState map[string]*gomatrixserverlib.HeaderedEvent
+	events       []*gomatrixserverlib.HeaderedEvent
 }
 
 // Create a new test room. Automatically creates the initial create events.
 func NewRoom(t *testing.T, creator *User, modifiers ...roomModifier) *Room {
 	t.Helper()
 	counter := atomic.AddInt64(&roomIDCounter, 1)
-
-	// set defaults then let roomModifiers override
+	if creator.srvName == "" {
+		t.Fatalf("NewRoom: creator doesn't belong to a server: %+v", *creator)
+	}
 	r := &Room{
-		ID:         fmt.Sprintf("!%d:localhost", counter),
-		creator:    creator,
-		authEvents: gomatrixserverlib.NewAuthEvents(nil),
-		preset:     PresetPublicChat,
-		Version:    gomatrixserverlib.RoomVersionV9,
+		ID:           fmt.Sprintf("!%d:%s", counter, creator.srvName),
+		creator:      creator,
+		authEvents:   gomatrixserverlib.NewAuthEvents(nil),
+		preset:       PresetPublicChat,
+		Version:      gomatrixserverlib.RoomVersionV9,
+		currentState: make(map[string]*gomatrixserverlib.HeaderedEvent),
 	}
 	for _, m := range modifiers {
 		m(t, r)
@@ -73,6 +69,24 @@ func NewRoom(t *testing.T, creator *User, modifiers ...roomModifier) *Room {
 	return r
 }
 
+func (r *Room) MustGetAuthEventRefsForEvent(t *testing.T, needed gomatrixserverlib.StateNeeded) []gomatrixserverlib.EventReference {
+	t.Helper()
+	a, err := needed.AuthEventReferences(&r.authEvents)
+	if err != nil {
+		t.Fatalf("MustGetAuthEvents: %v", err)
+	}
+	return a
+}
+
+func (r *Room) ForwardExtremities() []string {
+	if len(r.events) == 0 {
+		return nil
+	}
+	return []string{
+		r.events[len(r.events)-1].EventID(),
+	}
+}
+
 func (r *Room) insertCreateEvents(t *testing.T) {
 	t.Helper()
 	var joinRule gomatrixserverlib.JoinRuleContent
@@ -88,6 +102,7 @@ func (r *Room) insertCreateEvents(t *testing.T) {
 		joinRule.JoinRule = "public"
 		hisVis.HistoryVisibility = "shared"
 	}
+
 	r.CreateAndInsert(t, r.creator, gomatrixserverlib.MRoomCreate, map[string]interface{}{
 		"creator":      r.creator.ID,
 		"room_version": r.Version,
@@ -112,16 +127,16 @@ func (r *Room) CreateEvent(t *testing.T, creator *User, eventType string, conten
 	}
 
 	if mod.privKey == nil {
-		mod.privKey = testPrivateKey
+		mod.privKey = creator.privKey
 	}
 	if mod.keyID == "" {
-		mod.keyID = testKeyID
+		mod.keyID = creator.keyID
 	}
 	if mod.originServerTS.IsZero() {
 		mod.originServerTS = time.Now()
 	}
 	if mod.origin == "" {
-		mod.origin = gomatrixserverlib.ServerName("localhost")
+		mod.origin = creator.srvName
 	}
 
 	var unsigned gomatrixserverlib.RawJSON
@@ -174,13 +189,14 @@ func (r *Room) CreateEvent(t *testing.T, creator *User, eventType string, conten
 // Add a new event to this room DAG. Not thread-safe.
 func (r *Room) InsertEvent(t *testing.T, he *gomatrixserverlib.HeaderedEvent) {
 	t.Helper()
-	// Add the event to the list of auth events
+	// Add the event to the list of auth/state events
 	r.events = append(r.events, he)
 	if he.StateKey() != nil {
 		err := r.authEvents.AddEvent(he.Unwrap())
 		if err != nil {
 			t.Fatalf("InsertEvent: failed to add event to auth events: %s", err)
 		}
+		r.currentState[he.Type()+" "+*he.StateKey()] = he
 	}
 }
 
@@ -188,6 +204,16 @@ func (r *Room) Events() []*gomatrixserverlib.HeaderedEvent {
 	return r.events
 }
 
+func (r *Room) CurrentState() []*gomatrixserverlib.HeaderedEvent {
+	events := make([]*gomatrixserverlib.HeaderedEvent, len(r.currentState))
+	i := 0
+	for _, e := range r.currentState {
+		events[i] = e
+		i++
+	}
+	return events
+}
+
 func (r *Room) CreateAndInsert(t *testing.T, creator *User, eventType string, content interface{}, mods ...eventModifier) *gomatrixserverlib.HeaderedEvent {
 	t.Helper()
 	he := r.CreateEvent(t, creator, eventType, content, mods...)
diff --git a/test/slice.go b/test/slice.go
new file mode 100644
index 00000000..00c740db
--- /dev/null
+++ b/test/slice.go
@@ -0,0 +1,34 @@
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package test
+
+import "sort"
+
+// UnsortedStringSliceEqual returns true if the slices have same length & elements.
+// Does not modify the given slice.
+func UnsortedStringSliceEqual(first, second []string) bool {
+	if len(first) != len(second) {
+		return false
+	}
+
+	a, b := first[:], second[:]
+	sort.Strings(a)
+	sort.Strings(b)
+	for i := range a {
+		if a[i] != b[i] {
+			return false
+		}
+	}
+
+	return true
+}
diff --git a/test/base.go b/test/testrig/base.go
index 664442c0..facb49f3 100644
--- a/test/base.go
+++ b/test/testrig/base.go
@@ -12,7 +12,7 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-package test
+package testrig
 
 import (
 	"errors"
@@ -24,22 +24,23 @@ import (
 
 	"github.com/matrix-org/dendrite/setup/base"
 	"github.com/matrix-org/dendrite/setup/config"
+	"github.com/matrix-org/dendrite/test"
 	"github.com/nats-io/nats.go"
 )
 
-func CreateBaseDendrite(t *testing.T, dbType DBType) (*base.BaseDendrite, func()) {
+func CreateBaseDendrite(t *testing.T, dbType test.DBType) (*base.BaseDendrite, func()) {
 	var cfg config.Dendrite
 	cfg.Defaults(false)
 	cfg.Global.JetStream.InMemory = true
 
 	switch dbType {
-	case DBTypePostgres:
+	case test.DBTypePostgres:
 		cfg.Global.Defaults(true)   // autogen a signing key
 		cfg.MediaAPI.Defaults(true) // autogen a media path
 		// use a distinct prefix else concurrent postgres/sqlite runs will clash since NATS will use
 		// the file system event with InMemory=true :(
 		cfg.Global.JetStream.TopicPrefix = fmt.Sprintf("Test_%d_", dbType)
-		connStr, close := PrepareDBConnectionString(t, dbType)
+		connStr, close := test.PrepareDBConnectionString(t, dbType)
 		cfg.Global.DatabaseOptions = config.DatabaseOptions{
 			ConnectionString:       config.DataSource(connStr),
 			MaxOpenConnections:     10,
@@ -47,7 +48,7 @@ func CreateBaseDendrite(t *testing.T, dbType DBType) (*base.BaseDendrite, func()
 			ConnMaxLifetimeSeconds: 60,
 		}
 		return base.NewBaseDendrite(&cfg, "Test", base.DisableMetrics), close
-	case DBTypeSQLite:
+	case test.DBTypeSQLite:
 		cfg.Defaults(true) // sets a sqlite db per component
 		// use a distinct prefix else concurrent postgres/sqlite runs will clash since NATS will use
 		// the file system event with InMemory=true :(
diff --git a/test/jetstream.go b/test/testrig/jetstream.go
index 488c22be..74cf9506 100644
--- a/test/jetstream.go
+++ b/test/testrig/jetstream.go
@@ -1,4 +1,4 @@
-package test
+package testrig
 
 import (
 	"encoding/json"
diff --git a/test/user.go b/test/user.go
index 41a66e1c..0020098a 100644
--- a/test/user.go
+++ b/test/user.go
@@ -15,22 +15,64 @@
 package test
 
 import (
+	"crypto/ed25519"
 	"fmt"
 	"sync/atomic"
+	"testing"
+
+	"github.com/matrix-org/gomatrixserverlib"
 )
 
 var (
 	userIDCounter = int64(0)
+
+	serverName = gomatrixserverlib.ServerName("test")
+	keyID      = gomatrixserverlib.KeyID("ed25519:test")
+	privateKey = ed25519.NewKeyFromSeed([]byte{
+		1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
+		17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
+	})
+
+	// private keys that tests can use
+	PrivateKeyA = ed25519.NewKeyFromSeed([]byte{
+		1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
+		17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 77,
+	})
+	PrivateKeyB = ed25519.NewKeyFromSeed([]byte{
+		1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
+		17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 66,
+	})
 )
 
 type User struct {
 	ID string
+	// key ID and private key of the server who has this user, if known.
+	keyID   gomatrixserverlib.KeyID
+	privKey ed25519.PrivateKey
+	srvName gomatrixserverlib.ServerName
+}
+
+type UserOpt func(*User)
+
+func WithSigningServer(srvName gomatrixserverlib.ServerName, keyID gomatrixserverlib.KeyID, privKey ed25519.PrivateKey) UserOpt {
+	return func(u *User) {
+		u.keyID = keyID
+		u.privKey = privKey
+		u.srvName = srvName
+	}
 }
 
-func NewUser() *User {
+func NewUser(t *testing.T, opts ...UserOpt) *User {
 	counter := atomic.AddInt64(&userIDCounter, 1)
-	u := &User{
-		ID: fmt.Sprintf("@%d:localhost", counter),
+	var u User
+	for _, opt := range opts {
+		opt(&u)
+	}
+	if u.keyID == "" || u.srvName == "" || u.privKey == nil {
+		t.Logf("NewUser: missing signing server credentials; using default.")
+		WithSigningServer(serverName, keyID, privateKey)(&u)
 	}
-	return u
+	u.ID = fmt.Sprintf("@%d:%s", counter, u.srvName)
+	t.Logf("NewUser: created user %s", u.ID)
+	return &u
 }