lithdew/kademlia-go

Missing buckets on right side

hqm42 opened this issue · 4 comments

hqm42 commented

https://github.com/lithdew/kademlia/blob/3b0f902b24c088a5262c2fae7398c7aa2a39aa24/table.go#L115

I think buckets on the right are not considered until we hit the left border of the address space. Is this intentional?

lithdew commented

It was done intentionally for the time being (this package is still a WIP!) since it's (slightly) simpler than the actual method for finding the closest IDs to a target ID.

The actual method for finding the closest IDs is that it should pop ID entries from the left and right buckets one by one.

That being said, it's a little hard for me to think of an attack vector off the top of my head with the way it's laid out right now. Is there anything immediate you see off the top of your head looking at this implementation?

hqm42 commented

Let's say you start witch m==1 and only buckets 0, 1 and 2 have items.

  • before first iteration we call fill(1)
  • on first iteration l is 0 and r is 2
  • we call fill(l), decrement l and increment r
  • on second iteration l is -1 and r is 3
  • fill will not any items to our result from this point on, as l is out of bounds and bucket 2 has been skipped in first iteration.

This might lead to nodes that can never be discovered.

  • 🎉1
lithdew commented

Let's say you start witch m==1 and only buckets 0, 1 and 2 have items.

  • before first iteration we call fill(1)
  • on first iteration l is 0 and r is 2
  • we call fill(l), decrement l and increment r
  • on second iteration l is -1 and r is 3
  • fill will not any items to our result from this point on, as l is out of bounds and bucket 2 has been skipped in first iteration.

This might lead to nodes that can never be discovered.

Gotcha: you're absolutely right; the relatively small tests I did on peer discovery with the current implementation didn't catch this :).

I'll get a fix out for this momentarily.

lithdew commented

I pushed a commit with a fix, let me know what you think :). If it looks good, I'll also update the table code in NodeJS in https://github.com/lithdew/flatend.

45f8d02