diff options
Diffstat (limited to 'p2p/discover/table.go')
| -rw-r--r-- | p2p/discover/table.go | 54 |
1 files changed, 30 insertions, 24 deletions
diff --git a/p2p/discover/table.go b/p2p/discover/table.go index ae10fed5b..2c9cb80d5 100644 --- a/p2p/discover/table.go +++ b/p2p/discover/table.go @@ -7,20 +7,24 @@ package discover import ( + "crypto/rand" "net" "sort" "sync" "time" + "github.com/ethereum/go-ethereum/common" "github.com/ethereum/go-ethereum/crypto" "github.com/ethereum/go-ethereum/logger" "github.com/ethereum/go-ethereum/logger/glog" ) const ( - alpha = 3 // Kademlia concurrency factor - bucketSize = 16 // Kademlia bucket size - nBuckets = nodeIDBits + 1 // Number of buckets + alpha = 3 // Kademlia concurrency factor + bucketSize = 16 // Kademlia bucket size + hashBits = len(common.Hash{}) * 8 + nBuckets = hashBits + 1 // Number of buckets + maxBondingPingPongs = 10 ) @@ -116,21 +120,23 @@ func (tab *Table) Bootstrap(nodes []*Node) { // Lookup performs a network search for nodes close // to the given target. It approaches the target by querying // nodes that are closer to it on each iteration. -func (tab *Table) Lookup(target NodeID) []*Node { +// The given target does not need to be an actual node +// identifier. +func (tab *Table) Lookup(targetID NodeID) []*Node { var ( + target = crypto.Sha3Hash(targetID[:]) asked = make(map[NodeID]bool) seen = make(map[NodeID]bool) reply = make(chan []*Node, alpha) pendingQueries = 0 ) - // don't query further if we hit the target or ourself. + // don't query further if we hit ourself. // unlikely to happen often in practice. - asked[target] = true asked[tab.self.ID] = true tab.mutex.Lock() // update last lookup stamp (for refresh logic) - tab.buckets[logdist(tab.self.ID, target)].lastLookup = time.Now() + tab.buckets[logdist(tab.self.sha, target)].lastLookup = time.Now() // generate initial result set result := tab.closest(target, bucketSize) tab.mutex.Unlock() @@ -143,7 +149,7 @@ func (tab *Table) Lookup(target NodeID) []*Node { asked[n.ID] = true pendingQueries++ go func() { - r, _ := tab.net.findnode(n.ID, n.addr(), target) + r, _ := tab.net.findnode(n.ID, n.addr(), targetID) reply <- tab.bondall(r) }() } @@ -166,17 +172,16 @@ func (tab *Table) Lookup(target NodeID) []*Node { // refresh performs a lookup for a random target to keep buckets full. func (tab *Table) refresh() { - ld := -1 // logdist of chosen bucket - tab.mutex.Lock() - for i, b := range tab.buckets { - if i > 0 && b.lastLookup.Before(time.Now().Add(-1*time.Hour)) { - ld = i - break - } - } - tab.mutex.Unlock() - - result := tab.Lookup(randomID(tab.self.ID, ld)) + // The Kademlia paper specifies that the bucket refresh should + // perform a refresh in the least recently used bucket. We cannot + // adhere to this because the findnode target is a 512bit value + // (not hash-sized) and it is not easily possible to generate a + // sha3 preimage that falls into a chosen bucket. + // + // We perform a lookup with a random target instead. + var target NodeID + rand.Read(target[:]) + result := tab.Lookup(target) if len(result) == 0 { // Pick a batch of previously know seeds to lookup with seeds := tab.db.querySeeds(10) @@ -196,7 +201,7 @@ func (tab *Table) refresh() { // closest returns the n nodes in the table that are closest to the // given id. The caller must hold tab.mutex. -func (tab *Table) closest(target NodeID, nresults int) *nodesByDistance { +func (tab *Table) closest(target common.Hash, nresults int) *nodesByDistance { // This is a very wasteful way to find the closest nodes but // obviously correct. I believe that tree-based buckets would make // this easier to implement efficiently. @@ -278,7 +283,8 @@ func (tab *Table) bond(pinged bool, id NodeID, addr *net.UDPAddr, tcpPort uint16 } tab.mutex.Lock() defer tab.mutex.Unlock() - if b := tab.buckets[logdist(tab.self.ID, n.ID)]; !b.bump(n) { + b := tab.buckets[logdist(tab.self.sha, n.sha)] + if !b.bump(n) { tab.pingreplace(n, b) } return n, nil @@ -346,7 +352,7 @@ outer: // don't add self. continue } - bucket := tab.buckets[logdist(tab.self.ID, n.ID)] + bucket := tab.buckets[logdist(tab.self.sha, n.sha)] for i := range bucket.entries { if bucket.entries[i].ID == n.ID { // already in bucket @@ -375,13 +381,13 @@ func (b *bucket) bump(n *Node) bool { // distance to target. type nodesByDistance struct { entries []*Node - target NodeID + target common.Hash } // push adds the given node to the list, keeping the total size below maxElems. func (h *nodesByDistance) push(n *Node, maxElems int) { ix := sort.Search(len(h.entries), func(i int) bool { - return distcmp(h.target, h.entries[i].ID, n.ID) > 0 + return distcmp(h.target, h.entries[i].sha, n.sha) > 0 }) if len(h.entries) < maxElems { h.entries = append(h.entries, n) |