kademlia

package
v0.0.0-...-c9037bb Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: May 3, 2021 License: MIT Imports: 13 Imported by: 0

Documentation

Overview

Package kademlia is a noise implementation of the routing and discovery portion of the Kademlia protocol, with minor improvements suggested by the S/Kademlia paper.

Index

Constants

View Source
const BucketSize int = 16

BucketSize returns the capacity, or the total number of peer ID entries a single routing table bucket may hold.

Variables

View Source
var ErrBucketFull = errors.New("bucket is full")

ErrBucketFull is returned when a routing table bucket is at max capacity.

Functions

func PrefixDiff

func PrefixDiff(a, b []byte, n int) int

PrefixDiff counts the number of equal prefixed bits of a and b.

func PrefixLen

func PrefixLen(a []byte) int

PrefixLen returns the number of prefixed zero bits of a.

func SortByDistance

func SortByDistance(id noise.PublicKey, ids []noise.ID) []noise.ID

SortByDistance sorts ids by descending XOR distance with respect to id.

func XOR

func XOR(a, b []byte) []byte

XOR allocates a new byte slice with the computed result of XOR(a, b).

Types

type FindNodeRequest

type FindNodeRequest struct {
	Target noise.PublicKey
}

FindNodeRequest represents a FIND_NODE RPC call in the Kademlia specification. It contains a target public key to which a peer is supposed to respond with a slice of IDs that neighbor the target ID w.r.t. XOR distance.

func UnmarshalFindNodeRequest

func UnmarshalFindNodeRequest(buf []byte) (FindNodeRequest, error)

UnmarshalFindNodeRequest decodes buf, which must be the exact size of a public key, into a FindNodeRequest. It throws an io.ErrUnexpectedEOF if buf is malformed.

func (FindNodeRequest) Marshal

func (r FindNodeRequest) Marshal() []byte

Marshal implements noise.Serializable and returns the public key of the target for this search request as a byte slice.

type FindNodeResponse

type FindNodeResponse struct {
	Results []noise.ID
}

FindNodeResponse returns the results of a FIND_NODE RPC call which comprises of the IDs of peers closest to a target public key specified in a FindNodeRequest.

func UnmarshalFindNodeResponse

func UnmarshalFindNodeResponse(buf []byte) (FindNodeResponse, error)

UnmarshalFindNodeResponse decodes buf, which is expected to encode a list of closest peer ID results, into a FindNodeResponse. It throws an io.ErrUnexpectedEOF if buf is malformed.

func (FindNodeResponse) Marshal

func (r FindNodeResponse) Marshal() []byte

Marshal implements noise.Serializable and encodes the list of closest peer ID results into a byte representative of the length of the list, concatenated with the serialized byte representation of the peer IDs themselves.

type Iterator

type Iterator struct {
	sync.Mutex
	// contains filtered or unexported fields
}

Iterator represents a S/Kademlia overlay network iterator over all peers that may be discovered in the network. It is used for peer discovery, and for finding peers by their public key over an overlay network.

func NewIterator

func NewIterator(node *noise.Node, table *Table, opts ...IteratorOption) *Iterator

NewIterator instantiates a new overlay network iterator bounded to a node and routing table that may be optionally configured with a variadic list of functional options.

func (*Iterator) Find

func (it *Iterator) Find(target noise.PublicKey) []noise.ID

Find attempts to salvage through the Kademlia overlay network through the peers of the node this iterator is bound to for a target public key. It blocks the current goroutine until the search is complete.

type IteratorOption

type IteratorOption func(it *Iterator)

IteratorOption represents a functional option which may be passed to NewIterator, or to (*Protocol).Find or (*Protocol).Discover to configure Iterator.

func WithIteratorLogger

func WithIteratorLogger(logger *zap.Logger) IteratorOption

WithIteratorLogger configures the logger instance for an iterator. By default, the logger used is the logger of the node which the iterator is bound to.

func WithIteratorLookupTimeout

func WithIteratorLookupTimeout(lookupTimeout time.Duration) IteratorOption

WithIteratorLookupTimeout sets the max duration to wait until we declare a lookup request sent in amidst a single disjoint lookup to have timed out. By default, it is set to 3 seconds.

func WithIteratorMaxNumResults

func WithIteratorMaxNumResults(maxNumResults int) IteratorOption

WithIteratorMaxNumResults sets the max number of resultant peer IDs from a single (*Iterator).Find call. By default, it is set to the max capacity of a routing table bucket which is 16 based on the S/Kademlia paper.

func WithIteratorNumParallelLookups

func WithIteratorNumParallelLookups(numParallelLookups int) IteratorOption

WithIteratorNumParallelLookups sets the max number of parallel disjoint lookups that may occur at once while executing (*Iterator).Find. By default, it is set to 3 based on the S/Kademlia paper.

func WithIteratorNumParallelRequestsPerLookup

func WithIteratorNumParallelRequestsPerLookup(numParallelRequestsPerLookup int) IteratorOption

WithIteratorNumParallelRequestsPerLookup sets the max number of parallel requests a single disjoint lookup may make during the execution of (*Iterator).Find. By default, it is set to 8 based on the S/Kademlia paper.

type Ping

type Ping struct{}

Ping represents an empty ping message.

func UnmarshalPing

func UnmarshalPing([]byte) (Ping, error)

UnmarshalPing returns a Ping instance and never throws an error.

func (Ping) Marshal

func (r Ping) Marshal() []byte

Marshal implements noise.Serializable and returns a nil byte slice.

type Pong

type Pong struct{}

Pong represents an empty pong message.

func UnmarshalPong

func UnmarshalPong([]byte) (Pong, error)

UnmarshalPong returns a Pong instance and never throws an error.

func (Pong) Marshal

func (r Pong) Marshal() []byte

Marshal implements noise.Serializable and returns a nil byte slice.

type Protocol

type Protocol struct {
	eventemitter.EventEmitter
	// contains filtered or unexported fields
}

Protocol implements routing/discovery portion of the Kademlia protocol with improvements suggested by the S/Kademlia paper. It is expected that Protocol is bound to a noise.Node via (*noise.Node).Bind before the node starts listening for incoming peers.

func New

func New(opts ...ProtocolOption) *Protocol

New returns a new instance of the Kademlia protocol.

func (*Protocol) Ack

func (p *Protocol) Ack(id noise.ID)

Ack attempts to insert a peer ID into your nodes routing table. If the routing table bucket in which your peer ID was expected to be inserted on is full, the peer ID at the tail of the bucket is pinged. If the ping fails, the peer ID at the tail of the bucket is evicted and your peer ID is inserted to the head of the bucket.

func (*Protocol) Bind

func (p *Protocol) Bind(node *noise.Node) error

Bind registers messages Ping, Pong, FindNodeRequest, FindNodeResponse, and handles them by registering the (*Protocol).Handle Handler.

func (*Protocol) Discover

func (p *Protocol) Discover(opts ...IteratorOption) []noise.ID

Discover attempts to discover new peers to your node through peers your node already knows about by calling the FIND_NODE S/Kademlia RPC call with your nodes ID.

func (*Protocol) Find

func (p *Protocol) Find(target noise.PublicKey, opts ...IteratorOption) []noise.ID

Find executes the FIND_NODE S/Kademlia RPC call to find the closest peers to some given target public key. It returns the IDs of the closest peers it finds.

func (*Protocol) Handle

func (p *Protocol) Handle(ctx noise.HandlerContext) error

Handle implements noise.Protocol and handles Ping and FindNodeRequest messages.

func (*Protocol) OnMessageRecv

func (p *Protocol) OnMessageRecv(client *noise.Client)

OnMessageRecv implements noise.Protocol and attempts to push the position in which the clients ID resides in your nodes' routing table's to the head of the bucket it reside within.

func (*Protocol) OnMessageSent

func (p *Protocol) OnMessageSent(client *noise.Client)

OnMessageSent implements noise.Protocol and attempts to push the position in which the clients ID resides in your nodes' routing table's to the head of the bucket it reside within.

func (*Protocol) OnPeerConnected

func (p *Protocol) OnPeerConnected(client *noise.Client)

OnPeerConnected attempts to acknowledge the new peers existence by placing its entry into your nodes' routing table via (*Protocol).Ack.

func (*Protocol) OnPingFailed

func (p *Protocol) OnPingFailed(addr string, err error)

OnPingFailed evicts peers that your node has failed to dial.

func (*Protocol) Ping

func (p *Protocol) Ping(ctx context.Context, addr string) error

Ping sends a ping request to addr, and returns no error if a pong is received back before ctx has expired/was cancelled. It also throws an error if the connection to addr intermittently drops, or if handshaking with addr should there be no live connection to addr yet fails.

func (*Protocol) Protocol

func (p *Protocol) Protocol() noise.Protocol

Protocol returns a noise.Protocol that may registered to a node via (*noise.Node).Bind.

func (*Protocol) Table

func (p *Protocol) Table() *Table

Table returns this Kademlia overlay's routing table from your nodes perspective.

type ProtocolOption

type ProtocolOption func(p *Protocol)

ProtocolOption represents a functional option which may be passed to New to configure a Protocol.

func WithProtocolLogger

func WithProtocolLogger(logger *zap.Logger) ProtocolOption

WithProtocolLogger configures the logger instance for an iterator. By default, the logger used is the logger of the node which the iterator is bound to.

func WithProtocolPingTimeout

func WithProtocolPingTimeout(pingTimeout time.Duration) ProtocolOption

WithProtocolPingTimeout configures the amount of time to wait for until we declare a ping to have failed. Peers typically either are pinged through a call of (*Protocol).Ping, or in amidst the execution of Kademlia's peer eviction policy. By default, it is set to 3 seconds.

type Table

type Table struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

Table represents a Kademlia routing table.

func NewTable

func NewTable(self noise.ID) *Table

NewTable instantiates a new routing table whose XOR distance metric is defined with respect to some given ID.

func (*Table) Bucket

func (t *Table) Bucket(target noise.PublicKey) []noise.ID

Bucket returns all entries of a bucket where target reside within.

func (*Table) Delete

func (t *Table) Delete(target noise.PublicKey) (noise.ID, bool)

Delete removes target from this routing table. It returns the id of the delted target and true if found, or a zero-value ID and false otherwise.

func (*Table) DeleteByAddress

func (t *Table) DeleteByAddress(target string) (noise.ID, bool)

DeleteByAddress removes the first occurrence of an id with target as its address from this routing table. It returns the id of the deleted target and true if found, or a zero-value ID and false otherwise.

func (*Table) Entries

func (t *Table) Entries() []noise.ID

Entries returns all stored ids in this routing table.

func (*Table) FindClosest

func (t *Table) FindClosest(target noise.PublicKey, k int) []noise.ID

FindClosest returns the k closest peer IDs to target, and sorts them based on how close they are.

func (*Table) Last

func (t *Table) Last(target noise.PublicKey) noise.ID

Last returns the last id of the bucket where target resides within.

func (*Table) NumEntries

func (t *Table) NumEntries() int

NumEntries returns the total amount of ids stored in this routing table.

func (*Table) Peers

func (t *Table) Peers() []noise.ID

Peers returns BucketSize closest peer IDs to the ID which this routing table's distance metric is defined against.

func (*Table) Recorded

func (t *Table) Recorded(target noise.PublicKey) bool

Recorded returns true if target is already recorded in this routing table.

func (*Table) Self

func (t *Table) Self() noise.ID

Self returns the ID which this routing table's XOR distance metric is defined with respect to.

func (*Table) Update

func (t *Table) Update(target noise.ID) (bool, error)

Update attempts to insert the target node/peer ID into this routing table. If the bucket it was expected to be inserted within is full, ErrBucketFull is returned. If the ID already exists in its respective routing table bucket, it is moved to the head of the bucket and false is returned. If the ID has yet to exist, it is appended to the head of its intended bucket and true is returned.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL