# Decentralized Identity Authentication with Auditability and Privacy
## 5 Privacy-Preserving Protocol
### Intermediate Protocol
#### 5.1.2 Extended Authentication  
Prior to any authentication, the client increments its counter \(cnt\) and generates an ephemeral key pair \(\langle vk_{c},sk_{e}\rangle\leftarrow\mathit{KeyGen}(1^{\lambda})\) (which, as in the previous protocol, is used for replay protection). Then, the clients initiate the process, whose goal is to convince the service that (a) the client's identity is registered with the blockchain, and (b) the authentication process is _consistent_ with the previous authentication of this client. The client prepares the following messages:  
\[\langle tkn_{-1},\gamma_{-1}\rangle\gets VRF_{sk}(cnt-1)\] \[\langle tkn,\gamma\rangle\gets VRF_{sk}(cnt)\] \[tkn\mathit{Req}\leftarrow\langle tkn,\mathit{Sig}_{sk_{e}}(tkn), vk_{e}\rangle\] \[authReq\leftarrow\langle did,\beta^{\mathit{did}},\beta^{ \mathit{txn}_{-1}},cnt,tkn_{-1},\gamma_{-1},\gamma,tkn\mathit{Req}\rangle\]  
and it sends \(authReq\) to the service, which runs the standard authentication of \(vk\) and \(vk_{e}\) (as in the baseline protocol--Section 4.2) and validates the messages, thus verifying (1) that the tokens \(tkn_{-1}\) and \(tkn\) are authentically generated by the client for the inputs \(cnt-1\) and \(cnt\), respectively, i.e., \(\mathit{vrfyVRF}_{sk}(cnt,\mathit{tkn},\gamma)\) and \(\mathit{vrfyVRF}_{vk}(cnt-1,\mathit{tkn}_{-1},\gamma_{-1})\) both output \"True\", (2) that the identity inclusion proof \(\beta^{\mathit{did}}\) is correct and corresponds to \(vk\), (3) that the token inclusion proof \(\beta^{\mathit{tkn}_{-1}}\) corresponds to the authentication token \(tkn_{-1}\)), (4) \(tkn\mathit{Req}\) is signed correctly, and (5) that the authentication token \(tkn\) is not registered in the blockchain.  
For the last check, the service needs to contact the blockchain platform and obtain proof that \(tkn\) was not appended to the blockchain's token set (this can be efficiently realized with authenticated dictionaries [39]). Therefore, the token request \(tkn\mathit{Req}\) is submitted to the blockchain, where nodes only check if the token is not in the token set. (The nodes cannot check \(tkn\)'s authenticity, since it is not accompanied by its corresponding proof \(\gamma\).) If so, \(tkn\) is inserted into the token set, and the blockchain platform returns an inclusion proof \(\beta^{\mathit{txn}}\) (claiming that the \(tkn\mathit{Req}\) was processed correctly and that \(tkn\) became part of the blockchain) to the service, which forwards it to the client (the client will use the proof for the next authentication). With these checks, the service and the client are confident that the previous and current tokens are consistent with each other and that no credential misuse has occurred. Since we assumed the network level in Section 3.3, the request's origin (i.e., the service) cannot be de-anonymized. (This also applies to the requests sent in the final protocol from Section 5.2.) To relax this assumption, the service could use an anonymity network [40] while interacting with the blockchain platform.) At any time, the client can audit its authentications by simply checking whether the next token value \(tkn_{+1}\) that is computed from \(\langle tkn_{+1},\bot\rangle\gets VRF_{sk}(cnt+1)\rangle\) is in the blockchain (if it is, then this implies that its credentials were misused).