Implement auditing

[masomel]

Auditing is a protocol necessary for detection of equivocation. It includes an auditor component, a separate entity that is supposed to check a key server's STR history. The idea is that anybody should be able to run an auditor (regardless of whether they also run a key server), so this implementation will require an executable.

Auditing protocol server-side:

• Key server sends every new STR to the auditors
• The auditors verify the hash chain

Auditing protocol client-side:

• Client receives new STR from the key server
• Client queries n auditors for the key server's STR for the same epoch
• Client ensures that all STRs are consistent

Open questions:

• Auditor discovery: How do servers and clients find auditors? How do auditors keep track of key servers?
  • It's probably OK to pin known auditors for now
• How many auditors do we need to ensure equivocation detection? See Appendix B of the paper.

Implementation steps:

• Auditor-client protocol
• Auditor-server protocol
• Auditor application layer
• Incorporate auditing into client application layer
• Incorporate auditing into directory application layer
• Create documentation for implementing other auditor models based on the generic auditor API

[vqhuy]

Key server sends every new STR to the auditors

I thought the auditors just act like a client? If not, do we need a consensus algorithm for the server and auditors?

[masomel]

I thought the auditors just act like a client?

By this you mean that the auditors will query the key server at the beginning of every epoch like clients do?

If not, do we need a consensus algorithm for the server and auditors?

I think we might need consensus anyway for keeping track of running auditors (much like Tor uses to keep track of running relays). But the protocol itself shouldn't require any consensus algorithm.

[vqhuy]

By this you mean that the auditors will query the key server at the beginning of every epoch like clients do?

Yes.

I think we might need consensus anyway for keeping track of running auditors

I think more about the consensus for the STRs between the key server and auditors. I would like to let the keyserver actively broadcast its STRs to the auditors rather than let the auditors query the key server at the beginning of each epoch. I don't know if we go this way, we can avoid the Clock synchronization issue or not ...

[eledra89]

Can publishing STRs to a global append-only ledger like blockchain solve the problem ?
EthIKS already did that didn't they.

If the Identity Provider publishes only the STR in a transaction to a blockchain (not the whole data structure like EthIKS). Each client can then implement a lightweight wallet which tracks only their interested transactions from the blockchain network.

This way, there is no need for a separate audition protocol.

[liamsi]

Thanks a lot for your feedback!

Each client can then implement a lightweight wallet which tracks only their interested transactions from the blockchain network.

Won't clients still need to follow and verify the whole (bitcoin)-blockchain to get similar security guarantees as with querying (several) auditors? I know there are the SPV clients. I'm not really familiar with the concept but as far as I know they trust proxies/certain nodes in the network? If there are more advanced techniques can you share pointers to them?
I know that @keybase does sth very similar as you describe but I'm not sure even their client follows/queries the blockchain.
Also I heard that @blockstack uses some form of skip-list to make querying faster/less bandwidth consuming. It's definitely worth to look how much data clients need to download in their system (for later): http://www.cs.princeton.edu/~mfreed/docs/blockstack-atc16.pdf /cc @masomel @c633 @c633

I feel that committing to the bitcoin blockchain could be a cool addition to to an auditing mechanism but not really a replacement (at least not currently). Maybe some sort of pro-active "auditing" using CoSi/collective signing or similar approaches could make retro-active auditing obsolete in the future.

[liamsi]

@LongNguyenHoang89 If you feel like it: We certainly would be happy if you/someone comes up with a pull-request where the client commits STRs to the bitcoin blockchain and where clients (optionally) queries/follows the blockchain (instead of auditors). I think it would be a very cool (optional) addition.

[eledra89]

@liamsi, The SPV client will conect to the Bitcoin P2P network like other nodes but only collect transactions that it is interested in by sending a filter to other nodes in the network.
https://en.bitcoin.it/wiki/Network#Thin_SPV_Clients

As you mentioned, we need a list of trusted nodes. Generally, client should be able to connect to any full Bitcoin node they want. We can provide a recommendation for popular nodes though.

I feel that no matter how you solve the auditor problem, you still need a kind of gossiping/P2P network for them to maintain a consistent view of the system which is similar to blockchain anyway. It would be straight forward if each server broadcasts its STRs in a transaction on Bitcoin where every nodes, CONIKS auditor or not, can agree upon. An overlay structure like Blockstack virtualchain could certainly help with the bandwidth problem.

Our team in INRIA, France is working on CONIKS and blockchain, mainly about this auditing and trust recovery. As we know from @masomel last month, you are switching from the Java implementation to coniks-go. We will have a proposal for the blockchain integration and pull request very soon in the coming weeks.

[masomel]

I would like to let the keyserver actively broadcast its STRs to the auditors rather than let the auditors query the key server at the beginning of each epoch.

This is what we describe in the paper, and what I am planning on implementing as well. The issue I point out is about key servers discovering the auditors that they need to publish the STRs in the first place.

@LongNguyenHoang89 Thanks for your suggestions, and I look forward to your upcoming proposal to integrate with the blockchain. However, I share the same concerns with @liamsi about what is required of clients in that model. Firstly, the purpose of auditors isn't to reach consensus over what is the current state of a key server's directory. Their main purpose is to make equivocation checks more efficient for clients so they do as little computation as possible to detect equivocation. We actually considered publishing STRs on the blockchain when we were designing and evaluating CONIKS for our paper. We decided against it since our security properties are different (yet complementary) and because we believed the auditor model we ultimately chose was simpler in terms of the protocols and the performance and still gives us the desired consistency guarantees.

I'm not very familiar with SPVs, but the idea of having to rely on trusted nodes to return the transactions the clients are interested in gives me pause. I suspect that it would still be possible for a malicious proxy to equivocate about an STR; what's to stop a malicious proxy from returning an STR that isn't on the longest branch of the blockchain? One advantage I think our auditor model has is that auditors aren't trusted, so even if a key server equivocates and auditors collude, the protocol still guarantees a detection of this attack with high probability. Also, to my understanding, using a wallet in order to follow Bitcoin transactions would require each client to manage an additional key, no? This also raises a concern since it wouldn't make sense to manage those keys in CONIKS, so out-of-band key management would be needed, which in turn defeats the purpose of using CONIKS in the first place.

So, as @liamsi mentioned above, I believe that an auditing mechanism that uses the Blockchain could be a nice extension to the current protocol. I can imagine how some users who already use Bitcoin would be very interested in such an option. But blockchain-based auditing doesn't replace auditing entirely. I think that a good candidate for proactive attack detection would be collective signing (CoSi), which, if I've understood correctly, could actually obviate the need for blockchain-based auditing as well.

[eledra89]

Thanks !
We will try to address those comment on the coming proposal