Implement protocol for adding contacts remotely

Subtask of #1230 (closed).