diff --git a/mercurial/setdiscovery.py b/mercurial/setdiscovery.py
--- a/mercurial/setdiscovery.py
+++ b/mercurial/setdiscovery.py
@@ -134,6 +134,8 @@ def findcommonheads(ui, local, remote,
     roundtrips += 1
     ownheads = dag.heads()
     sample = _limitsample(ownheads, initialsamplesize)
+    # indices between sample and externalized version must match
+    sample = list(sample)
     if remote.local():
         # stopgap until we have a proper localpeer that supports batch()
         srvheadhashes = remote.heads()