kademlia

package
v0.0.0-...-eca426a Latest Latest
Warning

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

 Go to latest Published: May 9, 2022 License: MIT Imports: 13 Imported by: 0

Documentation

Overview

Package kademlia is a GRING 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 (
	OP_ONE_TIME = 0x08 // node information will not be registered in routing table. one time connection
	OP_NEW_CONN = 0x09 // it requires receivers to replace one of his routing table entry with this new node.
	OP_CONN_REQ = 0x10 // it doesn't require receiver to replace. Simply ignore the connection req when the table is full and all entries are alive
	OP_DISCOVER = 0x11 // discovery protocol only registers queried nodes in sender side. Receiver side doesn't register querying nodes.
)

protocol opcode

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 GRING.PublicKey, ids []GRING.ID) []GRING.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 Bulk 

type Bulk struct{}

Bulk represents a large bulk message.

func UnmarshalBulk 

func UnmarshalBulk([]byte) (Bulk, error)

UnmarshalBulk returns a Bulk instance and never throws an error.

func (Bulk) Marshal 

func (r Bulk) Marshal() []byte

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

type BulkAck 

type BulkAck struct{}

BulkAck represents an empty pong message.

func UnmarshalBulkAck 

func UnmarshalBulkAck([]byte) (BulkAck, error)

UnmarshalBulkAck returns a BulkAck instance and never throws an error.

func (BulkAck) Marshal 

func (r BulkAck) Marshal() []byte

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

type Events 

type Events struct {
	// OnPeerAdmitted is called when a peer is admitted to being inserted into your nodes' routing table.
	OnPeerAdmitted func(id GRING.ID)

	// OnPeerActivity is called when your node interacts with a peer, causing the peer's entry in your nodes' routing
	// table to be bumped to the head of its respective bucket.
	OnPeerActivity func(id GRING.ID)

	// OnPeerEvicted is called when your node fails to ping/dial a peer that was previously admitted into your nodes'
	// routing table, which leads to an eviction of the peers ID from your nodes' routing table.
	OnPeerEvicted func(id GRING.ID)

	OnExistingConnection func(id GRING.ID)
}

Events comprise of callbacks that are to be called upon the encountering of various events as a node follows the Kademlia protocol. An Events declaration may be registered to a Protocol upon instantiation through calling New with the WithProtocolEvents functional option.

type FindNodeRequest 

type FindNodeRequest struct {
	Target GRING.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 GRING.Serializable and returns the public key of the target for this search request as a byte slice.

type FindNodeResponse 

type FindNodeResponse struct {
	Results []GRING.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 GRING.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 *GRING.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 GRING.PublicKey) []GRING.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 GRING.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 GRING.Serializable and returns a nil byte slice.

type Protocol 

type Protocol struct {
	// 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 GRING.Node via (*GRING.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 GRING.ID, opcode ...byte)

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 *GRING.Node) error

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

func (*Protocol) DiscoverRandom 

func (p *Protocol) DiscoverRandom(opts ...IteratorOption) []GRING.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) DiscoverTarget 

func (p *Protocol) DiscoverTarget(target GRING.PublicKey, opts ...IteratorOption) []GRING.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 GRING.PublicKey, opts ...IteratorOption) []GRING.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 GRING.HandlerContext) error

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

func (*Protocol) MaxNeighbors 

func (p *Protocol) MaxNeighbors() int

MaxNeighbors returns cap of routing table

func (*Protocol) OnMessageRecv 

func (p *Protocol) OnMessageRecv(client *GRING.Client, opcode ...byte)

OnMessageRecv implements GRING.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 *GRING.Client, opcode ...byte)

OnMessageSent implements GRING.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(isInbound bool, client *GRING.Client, opcode ...byte)

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

func (*Protocol) OnPeerDisconnected 

func (p *Protocol) OnPeerDisconnected(client *GRING.Client)

func (*Protocol) OnPingFailed 

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

OnPingFailed evicts peers that your node has failed to dial.

func (*Protocol) Peers 

func (p *Protocol) Peers()

peers prints out all peers we are already aware of.

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() GRING.Protocol

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

func (*Protocol) RemoveConn 

func (p *Protocol) RemoveConn(id GRING.ID)

func (*Protocol) ReplaceConn 

func (p *Protocol) ReplaceConn(id GRING.ID)

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 WithProtocolEvents 

func WithProtocolEvents(events Events) ProtocolOption

WithProtocolEvents configures an event listener for 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 WithProtocolMaxNeighbors 

func WithProtocolMaxNeighbors(maxNeighbors int) ProtocolOption

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 GRING.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 GRING.PublicKey) []GRING.ID

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

func (*Table) Delete 

func (t *Table) Delete(target GRING.PublicKey) (GRING.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) (GRING.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() []GRING.ID

Entries returns all stored ids in this routing table.

func (*Table) FindClosest 

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

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

func (*Table) FindIDByAddress 

func (t *Table) FindIDByAddress(target string) (GRING.ID, bool)

func (*Table) Last 

func (t *Table) Last(target GRING.PublicKey) GRING.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() []GRING.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 GRING.PublicKey) bool

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

func (*Table) RecordedByString 

func (t *Table) RecordedByString(target string) (GRING.ID, bool)

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

func (*Table) Self 

func (t *Table) Self() GRING.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 GRING.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.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.