Extended version of the paper "Consistent Hashing and Random Trees" with proofs
Answering my own question.

I found that the authors never published an extended version with proofs.

The closest thing to an extended paper is,


  Rina Panigrahy. Relieving hot spots on the worldwide web. 1997. 1


which was the Master's thesis of Rina Panigrahy (under Prof. Karger &amp; Prof. Smith), who's also a co-author of the paper under discussion.  It is a good, detailed reference to the original paper with all the proofs I needed.