diff --git a/services/identity/Cargo.lock b/services/identity/Cargo.lock
--- a/services/identity/Cargo.lock
+++ b/services/identity/Cargo.lock
@@ -38,25 +38,32 @@
 ]
 
 [[package]]
-name = "async-stream"
-version = "0.3.5"
+name = "async-io"
+version = "1.13.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "cd56dd203fef61ac097dd65721a419ddccb106b2d2b70ba60a6b529f03961a51"
+checksum = "0fc5b45d93ef0529756f812ca52e44c221b35341892d3dcc34132ac02f3dd2af"
 dependencies = [
- "async-stream-impl",
- "futures-core",
- "pin-project-lite",
+ "async-lock",
+ "autocfg",
+ "cfg-if",
+ "concurrent-queue",
+ "futures-lite",
+ "log",
+ "parking",
+ "polling",
+ "rustix",
+ "slab",
+ "socket2",
+ "waker-fn",
 ]
 
 [[package]]
-name = "async-stream-impl"
-version = "0.3.5"
+name = "async-lock"
+version = "2.7.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "16e62a023e7c117e27523144c5d2459f4397fcc3cab0085af8e2224f643a0193"
+checksum = "fa24f727524730b077666307f2734b4a1a1c57acb79193127dcc8914d5242dd7"
 dependencies = [
- "proc-macro2",
- "quote",
- "syn 2.0.13",
+ "event-listener",
 ]
 
 [[package]]
@@ -452,12 +459,6 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "349a06037c7bf932dd7e7d1f653678b2038b9ad46a74102f1fc7bd7872678cce"
 
-[[package]]
-name = "base64"
-version = "0.13.1"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "9e1b586273c5702936fe7b7d6896644d8be71e6314cfe09d3167c95f712589e8"
-
 [[package]]
 name = "base64"
 version = "0.21.0"
@@ -526,6 +527,12 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "0d261e256854913907f67ed06efbc3338dfe6179796deefc1ff763fc1aee5535"
 
+[[package]]
+name = "bytecount"
+version = "0.6.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2c676a478f63e9fa2dd5368a42f28bba0d6c560b775f38583c8bbaa7fcd67c9c"
+
 [[package]]
 name = "byteorder"
 version = "1.4.3"
@@ -548,6 +555,37 @@
  "either",
 ]
 
+[[package]]
+name = "camino"
+version = "1.1.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "c530edf18f37068ac2d977409ed5cd50d53d73bc653c7647b48eb78976ac9ae2"
+dependencies = [
+ "serde",
+]
+
+[[package]]
+name = "cargo-platform"
+version = "0.1.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "cbdb825da8a5df079a43676dbe042702f1707b1109f713a01420fbb4cc71fa27"
+dependencies = [
+ "serde",
+]
+
+[[package]]
+name = "cargo_metadata"
+version = "0.14.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "4acbb09d9ee8e23699b9634375c72795d095bf268439da88562cf9b501f181fa"
+dependencies = [
+ "camino",
+ "cargo-platform",
+ "semver",
+ "serde",
+ "serde_json",
+]
+
 [[package]]
 name = "cc"
 version = "1.0.79"
@@ -643,10 +681,19 @@
  "log",
  "opaque-ke 2.0.0",
  "rand",
- "tonic 0.8.3",
+ "tonic",
  "wasm-bindgen",
 ]
 
+[[package]]
+name = "concurrent-queue"
+version = "2.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "62ec6771ecfa0762d24683ee5a32ad78487a3d3afdc0fb8cae19d2c5deb50b7c"
+dependencies = [
+ "crossbeam-utils",
+]
+
 [[package]]
 name = "const-oid"
 version = "0.9.2"
@@ -696,6 +743,38 @@
  "libc",
 ]
 
+[[package]]
+name = "crossbeam-channel"
+version = "0.5.8"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a33c2bf77f2df06183c3aa30d1e96c0695a313d4f9c453cc3762a6db39f99200"
+dependencies = [
+ "cfg-if",
+ "crossbeam-utils",
+]
+
+[[package]]
+name = "crossbeam-epoch"
+version = "0.9.14"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "46bd5f3f85273295a9d14aedfb86f6aadbff6d8f5295c4a9edb08e819dcf5695"
+dependencies = [
+ "autocfg",
+ "cfg-if",
+ "crossbeam-utils",
+ "memoffset",
+ "scopeguard",
+]
+
+[[package]]
+name = "crossbeam-utils"
+version = "0.8.15"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3c063cd8cc95f5c377ed0d4b49a4b21f632396ff690e8470c29b3359b346984b"
+dependencies = [
+ "cfg-if",
+]
+
 [[package]]
 name = "crypto-bigint"
 version = "0.2.5"
@@ -953,6 +1032,21 @@
  "libc",
 ]
 
+[[package]]
+name = "error-chain"
+version = "0.12.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2d2f06b9cac1506ece98fe3231e3cc9c4410ec3d5b1f24ae1c8946f0742cdefc"
+dependencies = [
+ "version_check",
+]
+
+[[package]]
+name = "event-listener"
+version = "2.5.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0206175f82b8d6bf6652ff7d71a1e27fd2e4efde587fd368662814d6ec1d9ce0"
+
 [[package]]
 name = "fastrand"
 version = "1.9.0"
@@ -1018,6 +1112,27 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "4bca583b7e26f571124fe5b7561d49cb2868d79116cfa0eefce955557c6fee8c"
 
+[[package]]
+name = "futures-io"
+version = "0.3.28"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "4fff74096e71ed47f8e023204cfd0aa1289cd54ae5430a9523be060cdb849964"
+
+[[package]]
+name = "futures-lite"
+version = "1.13.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "49a9d51ce47660b1e808d3c990b4709f2f415d928835a17dfd16991515c46bce"
+dependencies = [
+ "fastrand",
+ "futures-core",
+ "futures-io",
+ "memchr",
+ "parking",
+ "pin-project-lite",
+ "waker-fn",
+]
+
 [[package]]
 name = "futures-macro"
 version = "0.3.28"
@@ -1090,6 +1205,12 @@
  "wasm-bindgen",
 ]
 
+[[package]]
+name = "glob"
+version = "0.3.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d2fabcfbdc87f4758337ca535fb41a6d701b65693ce38287d856d1674551ec9b"
+
 [[package]]
 name = "group"
 version = "0.10.0"
@@ -1342,6 +1463,7 @@
  "derive_more",
  "futures-core",
  "hex",
+ "moka",
  "once_cell",
  "opaque-ke 1.2.0",
  "prost",
@@ -1351,11 +1473,12 @@
  "siwe",
  "tokio",
  "tokio-stream",
- "tonic 0.9.1",
+ "tonic",
  "tonic-build",
  "tonic-web",
  "tracing",
  "tracing-subscriber",
+ "uuid",
 ]
 
 [[package]]
@@ -1469,6 +1592,16 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "d59d8c75012853d2e872fb56bc8a2e53718e2cafe1a4c823143141c6d90c322f"
 
+[[package]]
+name = "lock_api"
+version = "0.4.9"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "435011366fe56583b16cf956f9df0095b405b82d76425bc8981c0e22e60ec4df"
+dependencies = [
+ "autocfg",
+ "scopeguard",
+]
+
 [[package]]
 name = "log"
 version = "0.4.17"
@@ -1478,6 +1611,15 @@
  "cfg-if",
 ]
 
+[[package]]
+name = "mach2"
+version = "0.4.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6d0d1830bcd151a6fc4aea1369af235b36c1528fe976b8ff678683c9995eade8"
+dependencies = [
+ "libc",
+]
+
 [[package]]
 name = "matchit"
 version = "0.7.0"
@@ -1490,6 +1632,15 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "2dffe52ecf27772e601905b7522cb4ef790d2cc203488bbd0e2fe85fcb74566d"
 
+[[package]]
+name = "memoffset"
+version = "0.8.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d61c719bcfbcf5d62b3a09efa6088de8c54bc0bfcd3ea7ae39fcc186108b8de1"
+dependencies = [
+ "autocfg",
+]
+
 [[package]]
 name = "mime"
 version = "0.3.17"
@@ -1514,6 +1665,32 @@
  "windows-sys 0.45.0",
 ]
 
+[[package]]
+name = "moka"
+version = "0.10.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e0d3b8e76a2e4b17de765db9432e377a171c42fbe0512b8bc860ff1bfe2e273b"
+dependencies = [
+ "async-io",
+ "async-lock",
+ "crossbeam-channel",
+ "crossbeam-epoch",
+ "crossbeam-utils",
+ "futures-util",
+ "num_cpus",
+ "once_cell",
+ "parking_lot",
+ "quanta",
+ "rustc_version",
+ "scheduled-thread-pool",
+ "skeptic",
+ "smallvec",
+ "tagptr",
+ "thiserror",
+ "triomphe",
+ "uuid",
+]
+
 [[package]]
 name = "multimap"
 version = "0.8.3"
@@ -1646,6 +1823,35 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "b15813163c1d831bf4a13c3610c05c0d03b39feb07f7e09fa234dac9b15aaf39"
 
+[[package]]
+name = "parking"
+version = "2.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "14f2252c834a40ed9bb5422029649578e63aa341ac401f74e719dd1afda8394e"
+
+[[package]]
+name = "parking_lot"
+version = "0.12.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3742b2c103b9f06bc9fff0a37ff4912935851bee6d36f3c02bcc755bcfec228f"
+dependencies = [
+ "lock_api",
+ "parking_lot_core",
+]
+
+[[package]]
+name = "parking_lot_core"
+version = "0.9.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9069cbb9f99e3a5083476ccb29ceb1de18b9118cafa53e90c9551235de2b9521"
+dependencies = [
+ "cfg-if",
+ "libc",
+ "redox_syscall 0.2.16",
+ "smallvec",
+ "windows-sys 0.45.0",
+]
+
 [[package]]
 name = "password-hash"
 version = "0.4.2"
@@ -1705,6 +1911,22 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "8b870d8c151b6f2fb93e84a13146138f05d02ed11c7e7c54f8826aaaf7c9f184"
 
+[[package]]
+name = "polling"
+version = "2.7.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "4be1c66a6add46bff50935c313dae30a5030cf8385c5206e8a95e9e9def974aa"
+dependencies = [
+ "autocfg",
+ "bitflags",
+ "cfg-if",
+ "concurrent-queue",
+ "libc",
+ "log",
+ "pin-project-lite",
+ "windows-sys 0.48.0",
+]
+
 [[package]]
 name = "ppv-lite86"
 version = "0.2.17"
@@ -1808,6 +2030,33 @@
  "prost",
 ]
 
+[[package]]
+name = "pulldown-cmark"
+version = "0.9.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2d9cc634bc78768157b5cbfe988ffcd1dcba95cd2b2f03a88316c08c6d00ed63"
+dependencies = [
+ "bitflags",
+ "memchr",
+ "unicase",
+]
+
+[[package]]
+name = "quanta"
+version = "0.11.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8cc73c42f9314c4bdce450c77e6f09ecbddefbeddb1b5979ded332a3913ded33"
+dependencies = [
+ "crossbeam-utils",
+ "libc",
+ "mach2",
+ "once_cell",
+ "raw-cpuid",
+ "wasi 0.11.0+wasi-snapshot-preview1",
+ "web-sys",
+ "winapi",
+]
+
 [[package]]
 name = "quote"
 version = "1.0.26"
@@ -1856,6 +2105,24 @@
  "getrandom 0.2.9",
 ]
 
+[[package]]
+name = "raw-cpuid"
+version = "10.7.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6c297679cb867470fa8c9f67dbba74a78d78e3e98d7cf2b08d6d71540f797332"
+dependencies = [
+ "bitflags",
+]
+
+[[package]]
+name = "redox_syscall"
+version = "0.2.16"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "fb5a58c1855b4b6819d59012155603f0b22ad30cad752600aadfcb695265519a"
+dependencies = [
+ "bitflags",
+]
+
 [[package]]
 name = "redox_syscall"
 version = "0.3.5"
@@ -1950,7 +2217,7 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "d194b56d58803a43635bdc398cd17e383d6f71f9182b9a192c127ca42494a59b"
 dependencies = [
- "base64 0.21.0",
+ "base64",
 ]
 
 [[package]]
@@ -1965,6 +2232,15 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "f91339c0467de62360649f8d3e185ca8de4224ff281f66000de5eb2a77a79041"
 
+[[package]]
+name = "same-file"
+version = "1.0.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "93fc1dc3aaa9bfed95e02e6eadabb4baf7e3078b0bd1b4d7b6b0b68378900502"
+dependencies = [
+ "winapi-util",
+]
+
 [[package]]
 name = "schannel"
 version = "0.1.21"
@@ -1974,6 +2250,21 @@
  "windows-sys 0.42.0",
 ]
 
+[[package]]
+name = "scheduled-thread-pool"
+version = "0.2.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3cbc66816425a074528352f5789333ecff06ca41b36b0b0efdfbb29edc391a19"
+dependencies = [
+ "parking_lot",
+]
+
+[[package]]
+name = "scopeguard"
+version = "1.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d29ab0c6d3fc0ee92fe66e2d99f700eab17a8d57d1c1d3b748380fb20baa78cd"
+
 [[package]]
 name = "scratch"
 version = "1.0.5"
@@ -2031,6 +2322,9 @@
 version = "1.0.17"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "bebd363326d05ec3e2f532ab7660680f3b02130d780c299bca73469d521bc0ed"
+dependencies = [
+ "serde",
+]
 
 [[package]]
 name = "serde"
@@ -2134,6 +2428,21 @@
  "thiserror",
 ]
 
+[[package]]
+name = "skeptic"
+version = "0.13.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "16d23b015676c90a0f01c197bfdc786c20342c73a0afdda9025adb0bc42940a8"
+dependencies = [
+ "bytecount",
+ "cargo_metadata",
+ "error-chain",
+ "glob",
+ "pulldown-cmark",
+ "tempfile",
+ "walkdir",
+]
+
 [[package]]
 name = "slab"
 version = "0.4.8"
@@ -2205,6 +2514,12 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "2047c6ded9c721764247e62cd3b03c09ffc529b2ba5b10ec482ae507a4a70160"
 
+[[package]]
+name = "tagptr"
+version = "0.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7b2093cf4c8eb1e67749a6762251bc9cd836b6fc171623bd0a9d324d37af2417"
+
 [[package]]
 name = "tempfile"
 version = "3.5.0"
@@ -2213,7 +2528,7 @@
 dependencies = [
  "cfg-if",
  "fastrand",
- "redox_syscall",
+ "redox_syscall 0.3.5",
  "rustix",
  "windows-sys 0.45.0",
 ]
@@ -2374,28 +2689,6 @@
  "tracing",
 ]
 
-[[package]]
-name = "tonic"
-version = "0.8.3"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "8f219fad3b929bef19b1f86fbc0358d35daed8f2cac972037ac0dc10bbb8d5fb"
-dependencies = [
- "async-stream",
- "base64 0.13.1",
- "bytes",
- "futures-core",
- "futures-util",
- "http",
- "http-body",
- "percent-encoding",
- "pin-project",
- "tokio-stream",
- "tokio-util",
- "tower-layer",
- "tower-service",
- "tracing",
-]
-
 [[package]]
 name = "tonic"
 version = "0.9.1"
@@ -2404,7 +2697,7 @@
 dependencies = [
  "async-trait",
  "axum",
- "base64 0.21.0",
+ "base64",
  "bytes",
  "futures-core",
  "futures-util",
@@ -2443,14 +2736,14 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "1ea5a992300fc324dd8c529868ec7b07ac85510431f982e6f716c2cac56701d9"
 dependencies = [
- "base64 0.21.0",
+ "base64",
  "bytes",
  "futures-core",
  "http",
  "http-body",
  "hyper",
  "pin-project",
- "tonic 0.9.1",
+ "tonic",
  "tower-http",
  "tower-layer",
  "tower-service",
@@ -2566,6 +2859,12 @@
  "tracing-log",
 ]
 
+[[package]]
+name = "triomphe"
+version = "0.1.8"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f1ee9bd9239c339d714d657fac840c6d2a4f9c45f4f9ec7b0975113458be78db"
+
 [[package]]
 name = "try-lock"
 version = "0.2.4"
@@ -2578,6 +2877,15 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "497961ef93d974e23eb6f433eb5fe1b7930b659f06d12dec6fc44a8f554c0bba"
 
+[[package]]
+name = "unicase"
+version = "2.6.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "50f37be617794602aabbeee0be4f259dc1778fabe05e2d67ee8f79326d5cb4f6"
+dependencies = [
+ "version_check",
+]
+
 [[package]]
 name = "unicode-ident"
 version = "1.0.8"
@@ -2602,6 +2910,15 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "e8db7427f936968176eaa7cdf81b7f98b980b18495ec28f1b5791ac3bfe3eea9"
 
+[[package]]
+name = "uuid"
+version = "1.3.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5b55a3fef2a1e3b3a00ce878640918820d3c51081576ac657d23af9fc7928fdb"
+dependencies = [
+ "getrandom 0.2.9",
+]
+
 [[package]]
 name = "valuable"
 version = "0.1.0"
@@ -2639,6 +2956,22 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "5c3082ca00d5a5ef149bb8b555a72ae84c9c59f7250f013ac822ac2e49b19c64"
 
+[[package]]
+name = "waker-fn"
+version = "1.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9d5b2c62b4012a3e1eca5a7e077d13b3bf498c4073e33ccd58626607748ceeca"
+
+[[package]]
+name = "walkdir"
+version = "2.3.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "36df944cda56c7d8d8b7496af378e6b16de9284591917d307c9b4d313c44e698"
+dependencies = [
+ "same-file",
+ "winapi-util",
+]
+
 [[package]]
 name = "want"
 version = "0.3.0"
diff --git a/services/identity/Cargo.toml b/services/identity/Cargo.toml
--- a/services/identity/Cargo.toml
+++ b/services/identity/Cargo.toml
@@ -30,6 +30,8 @@
 tonic-web = "0.9.1"
 serde = { version = "1.0.159", features = [ "derive" ] }
 serde_json = "1.0.95"
+moka = { version = "0.10", features = ["future"] }
+uuid = { version = "1.3", features = [ "v4" ] }
 
 [build-dependencies]
 tonic-build = "0.9.1"
diff --git a/services/identity/src/client_service.rs b/services/identity/src/client_service.rs
--- a/services/identity/src/client_service.rs
+++ b/services/identity/src/client_service.rs
@@ -2,6 +2,8 @@
   tonic::include_proto!("identity.client");
 }
 
+use std::str::FromStr;
+
 use crate::{
   client_service::client_proto::{
     DeleteUserRequest, Empty, GenerateNonceResponse, KeyserverKeysRequest,
@@ -17,29 +19,133 @@
     VerifyUserAccessTokenRequest, VerifyUserAccessTokenResponse,
     WalletLoginRequest, WalletLoginResponse,
   },
-  database::{DatabaseClient, Error as DBError},
+  config::CONFIG,
+  database::{DatabaseClient, Error as DBError, KeyPayload},
   nonce::generate_nonce_data,
+  utils::{generate_uuid, username_reserved},
 };
 use aws_sdk_dynamodb::Error as DynamoDBError;
 pub use client_proto::identity_client_service_server::{
   IdentityClientService, IdentityClientServiceServer,
 };
+use moka::future::Cache;
 use rand::rngs::OsRng;
 use tonic::Response;
 use tracing::error;
 
+#[derive(Clone)]
+pub enum WorkflowInProgress {
+  Registration(RegistrationState),
+}
+
+#[derive(Clone)]
+pub struct RegistrationState {
+  username: String,
+  device_id_key: String,
+  key_payload: String,
+  key_payload_signature: String,
+  identity_prekey: String,
+  identity_prekey_signature: String,
+  identity_onetime_keys: Vec<String>,
+  notif_prekey: String,
+  notif_prekey_signature: String,
+  notif_onetime_keys: Vec<String>,
+}
+
 #[derive(derive_more::Constructor)]
 pub struct ClientService {
   client: DatabaseClient,
+  cache: Cache<String, WorkflowInProgress>,
 }
 
 #[tonic::async_trait]
 impl IdentityClientService for ClientService {
   async fn register_password_user_start(
     &self,
-    _request: tonic::Request<RegistrationStartRequest>,
+    request: tonic::Request<RegistrationStartRequest>,
   ) -> Result<tonic::Response<RegistrationStartResponse>, tonic::Status> {
-    unimplemented!();
+    let message = request.into_inner();
+    let username_taken = self
+      .client
+      .username_taken(message.username.clone())
+      .await
+      .map_err(handle_db_error)?;
+
+    if username_taken {
+      return Err(tonic::Status::already_exists("username already exists"));
+    }
+
+    let username_reserved =
+      username_reserved(&message.username).await.map_err(|e| {
+        error!("Failed to check if username is reserved: {}", e);
+        tonic::Status::failed_precondition("unexpected error")
+      })?;
+
+    if username_reserved {
+      return Err(tonic::Status::invalid_argument("username reserved"));
+    }
+
+    if let client_proto::RegistrationStartRequest {
+      opaque_registration_request: register_message,
+      username,
+      device_key_upload:
+        Some(client_proto::DeviceKeyUpload {
+          device_key_info:
+            Some(client_proto::IdentityKeyInfo {
+              payload,
+              payload_signature,
+              social_proof: _social_proof,
+            }),
+          identity_upload:
+            Some(client_proto::PreKey {
+              pre_key: identity_prekey,
+              pre_key_signature: identity_prekey_signature,
+            }),
+          notif_upload:
+            Some(client_proto::PreKey {
+              pre_key: notif_prekey,
+              pre_key_signature: notif_prekey_signature,
+            }),
+          onetime_identity_prekeys,
+          onetime_notif_prekeys,
+        }),
+    } = message
+    {
+      let server_registration = comm_opaque2::server::Registration::new();
+      let server_message = server_registration
+        .start(&CONFIG.server_setup, &register_message, username.as_bytes())
+        .map_err(comm_opaque2::grpc::protocol_error_to_grpc_status)?;
+      let key_info = KeyPayload::from_str(&payload)
+        .map_err(|_| tonic::Status::invalid_argument("malformed payload"))?;
+      let registration_state = RegistrationState {
+        username,
+        device_id_key: key_info.primary_identity_public_keys.curve25519,
+        key_payload: payload,
+        key_payload_signature: payload_signature,
+        identity_prekey,
+        identity_prekey_signature,
+        identity_onetime_keys: onetime_identity_prekeys,
+        notif_prekey,
+        notif_prekey_signature,
+        notif_onetime_keys: onetime_notif_prekeys,
+      };
+      let session_id = generate_uuid();
+      self
+        .cache
+        .insert(
+          session_id.clone(),
+          WorkflowInProgress::Registration(registration_state),
+        )
+        .await;
+
+      let response = RegistrationStartResponse {
+        session_id,
+        opaque_registration_response: server_message,
+      };
+      Ok(Response::new(response))
+    } else {
+      Err(tonic::Status::invalid_argument("unexpected message data"))
+    }
   }
 
   async fn register_password_user_finish(
diff --git a/services/identity/src/database.rs b/services/identity/src/database.rs
--- a/services/identity/src/database.rs
+++ b/services/identity/src/database.rs
@@ -34,8 +34,8 @@
 
 #[derive(Serialize, Deserialize)]
 pub struct OlmKeys {
-  curve25519: String,
-  ed25519: String,
+  pub curve25519: String,
+  pub ed25519: String,
 }
 
 #[derive(Serialize, Deserialize)]
@@ -403,10 +403,7 @@
       .map_err(|e| Error::AwsSdk(e.into()))
   }
 
-  pub async fn username_available(
-    &self,
-    username: String,
-  ) -> Result<bool, Error> {
+  pub async fn username_taken(&self, username: String) -> Result<bool, Error> {
     let result = self
       .client
       .get_item()
@@ -417,7 +414,7 @@
       .await
       .map_err(|e| Error::AwsSdk(e.into()))?;
 
-    Ok(result.item.is_none())
+    Ok(result.item.is_some())
   }
 
   pub async fn get_user_id_from_user_info(
diff --git a/services/identity/src/main.rs b/services/identity/src/main.rs
--- a/services/identity/src/main.rs
+++ b/services/identity/src/main.rs
@@ -1,5 +1,8 @@
+use std::time::Duration;
+
 use clap::{Parser, Subcommand};
 use database::DatabaseClient;
+use moka::future::Cache;
 use tonic::transport::Server;
 use tracing_subscriber::FmtSubscriber;
 
@@ -56,8 +59,12 @@
       let addr = IDENTITY_SERVICE_SOCKET_ADDR.parse()?;
       let aws_config = aws_config::from_env().region("us-east-2").load().await;
       let database_client = DatabaseClient::new(&aws_config);
-      let client_service =
-        IdentityClientServiceServer::new(ClientService::new(database_client));
+      let workflow_cache = Cache::builder()
+        .time_to_live(Duration::from_secs(10))
+        .build();
+      let client_service = IdentityClientServiceServer::new(
+        ClientService::new(database_client, workflow_cache),
+      );
       info!("Listening to gRPC traffic on {}", addr);
       Server::builder()
         .accept_http1(true)
diff --git a/services/identity/src/utils/mod.rs b/services/identity/src/utils/mod.rs
--- a/services/identity/src/utils/mod.rs
+++ b/services/identity/src/utils/mod.rs
@@ -1,10 +1,11 @@
 use std::collections::HashSet;
 use std::path::PathBuf;
 use tokio::fs;
+use uuid::Uuid;
 
 use crate::constants::RESERVED_USERNAMES_JSON;
 
-pub async fn get_reserved_usernames_set() -> Result<HashSet<String>, Error> {
+async fn get_reserved_usernames_set() -> Result<HashSet<String>, Error> {
   let path = PathBuf::from(RESERVED_USERNAMES_JSON);
   let contents = fs::read_to_string(path).await?;
   let reserved_usernames: Vec<String> = serde_json::from_str(&contents)?;
@@ -12,6 +13,19 @@
   Ok(reserved_usernames.into_iter().collect())
 }
 
+pub async fn username_reserved(username: &str) -> Result<bool, Error> {
+  let reserved_usernames = get_reserved_usernames_set().await?;
+  Ok(reserved_usernames.contains(username))
+}
+
+pub fn generate_uuid() -> String {
+  let mut buf = [b'\0'; 36];
+  Uuid::new_v4().hyphenated().encode_upper(&mut buf);
+  std::str::from_utf8(&buf)
+    .expect("Unable to create UUID")
+    .to_string()
+}
+
 #[derive(
   Debug, derive_more::Display, derive_more::Error, derive_more::From,
 )]
@@ -19,5 +33,14 @@
   #[display(...)]
   IO(std::io::Error),
   #[display(...)]
-  JSON(serde_json::Error),
+  Json(serde_json::Error),
+}
+
+#[cfg(test)]
+mod tests {
+  use super::*;
+  #[test]
+  fn test_generate_uuid() {
+    generate_uuid();
+  }
 }
diff --git a/shared/comm-opaque2/Cargo.lock b/shared/comm-opaque2/Cargo.lock
--- a/shared/comm-opaque2/Cargo.lock
+++ b/shared/comm-opaque2/Cargo.lock
@@ -13,28 +13,6 @@
  "password-hash",
 ]
 
-[[package]]
-name = "async-stream"
-version = "0.3.4"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "ad445822218ce64be7a341abfb0b1ea43b5c23aa83902542a4542e78309d8e5e"
-dependencies = [
- "async-stream-impl",
- "futures-core",
- "pin-project-lite",
-]
-
-[[package]]
-name = "async-stream-impl"
-version = "0.3.4"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "e4655ae1a7b0cdf149156f780c5bf3f1352bc53cbd9e0a361a7ef7b22947e965"
-dependencies = [
- "proc-macro2",
- "quote",
- "syn",
-]
-
 [[package]]
 name = "autocfg"
 version = "1.1.0"
@@ -49,9 +27,9 @@
 
 [[package]]
 name = "base64"
-version = "0.13.1"
+version = "0.21.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "9e1b586273c5702936fe7b7d6896644d8be71e6314cfe09d3167c95f712589e8"
+checksum = "a4a4ddaa51a5bc52a6948f74c06d20aaaddb71924eab79b8c97a8c556e942d6a"
 
 [[package]]
 name = "base64ct"
@@ -255,12 +233,6 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "86d7a0c1aa76363dac491de0ee99faf6941128376f1cf96f07db7603b7de69dd"
 
-[[package]]
-name = "futures-sink"
-version = "0.3.27"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "ec93083a4aecafb2a80a885c9de1f0ccae9dbd32c2bb54b0c3a65690e0b8d2f2"
-
 [[package]]
 name = "futures-task"
 version = "0.3.27"
@@ -599,27 +571,12 @@
  "tokio",
 ]
 
-[[package]]
-name = "tokio-util"
-version = "0.7.7"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "5427d89453009325de0d8f342c9490009f76e999cb7672d77e46267448f7e6b2"
-dependencies = [
- "bytes",
- "futures-core",
- "futures-sink",
- "pin-project-lite",
- "tokio",
- "tracing",
-]
-
 [[package]]
 name = "tonic"
-version = "0.8.3"
+version = "0.9.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "8f219fad3b929bef19b1f86fbc0358d35daed8f2cac972037ac0dc10bbb8d5fb"
+checksum = "3082666a3a6433f7f511c7192923fa1fe07c69332d3c6a2e6bb040b569199d5a"
 dependencies = [
- "async-stream",
  "base64",
  "bytes",
  "futures-core",
@@ -629,7 +586,6 @@
  "percent-encoding",
  "pin-project",
  "tokio-stream",
- "tokio-util",
  "tower-layer",
  "tower-service",
  "tracing",
diff --git a/shared/comm-opaque2/Cargo.toml b/shared/comm-opaque2/Cargo.toml
--- a/shared/comm-opaque2/Cargo.toml
+++ b/shared/comm-opaque2/Cargo.toml
@@ -8,5 +8,5 @@
 log = "0.4"
 opaque-ke = { version = "2.0", features = [ "argon2" ] }
 rand = "0.8"
-tonic = { version = "0.8", default-features = false }
+tonic = { version = "0.9.1", default-features = false }
 wasm-bindgen = "0.2"