element-hq / element-hq/synapse

synapse allows an infinite number of one-time-keys to be uploaded, leading to inefficient `/keys/claim`

Open
#15,366 0 comments 0 reactions 0 assignees View on GitHub
A-E2EE O-Uncommon S-Minor T-Defect
Dominant language
Python
Stars
4.6k
Forks
600
Avg merge
5d 22h
Merged PRs (30d)
51

Description

This issue has been migrated from [#15366](https://github.com/matrix-org/synapse/issues/15366).

---

Synapse imposes no limit on the number of one-time-keys which can be uploaded. Apart from the storage, that's a problem because `/keys/claim` isn't terribly efficient when there are lots of matching keys in the database:

```
explain
DELETE FROM e2e_one_time_keys_json
WHERE user_id = '@richvdh:matrix.org' AND device_id = 'KUMOTFKFVU' AND algorithm = 'signed_curve25519'
AND key_id IN (
SELECT key_id FROM e2e_one_time_keys_json
WHERE user_id = '@richvdh:matrix.org' AND device_id = 'KUMOTFKFVU' AND algorithm = 'signed_curve25519'
LIMIT 1
)
RETURNING key_id, key_json;

----------------------------------------------------------------------------------------------------------------------------------------------------------------------
Delete on e2e_one_time_keys_json (cost=1.40..9.47 rows=1 width=37)
-> Nested Loop Semi Join (cost=1.40..9.47 rows=1 width=37)
Join Filter: (e2e_one_time_keys_json.key_id = "ANY_subquery".key_id)
-> Index Scan using e2e_one_time_keys_json_uniqueness on e2e_one_time_keys_json (cost=0.70..4.72 rows=1 width=13)
Index Cond: ((user_id = '@richvdh:matrix.org'::text) AND (device_id = 'KUMOTFKFVU'::text) AND (algorithm = 'signed_curve25519'::text))
-> Subquery Scan on "ANY_subquery" (cost=0.70..4.73 rows=1 width=38)
-> Limit (cost=0.70..4.72 rows=1 width=7)
-> Index Only Scan using e2e_one_time_keys_json_uniqueness on e2e_one_time_keys_json e2e_one_time_keys_json_1 (cost=0.70..4.72 rows=1 width=7)
Index Cond: ((user_id = '@richvdh:matrix.org'::text) AND (device_id = 'KUMOTFKFVU'::text) AND (algorithm = 'signed_curve25519'::text))
(9 rows)

```

it looks like neither of those index scans use the key_id in the index. It can take several seconds for a user with 10K one-time keys.

Replacing the `IN` with `=` fixes that, but I haven't tested on sqlite.

Suggest we fix the query *and* stop users uploading more than 200 or so OTKs per device.

Contributor guide

Open the contributing guide

Research direction

Start at the `/keys/claim` query and the one-time-key upload handling described in the issue. Compare the shown DELETE query with SQLite behavior, then verify that claiming remains efficient with many keys and that uploads are limited to roughly 200 keys per device.

Written by the indexing model from the issue text.

Assessment

Tech stack
postgresql, python, sqlite
Domain
backend-api-design, databases, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.