kadcast

README

A Kadcast implementation in pure Golang

p2p/kadcast package is an attempt to implement kadcast protocol specification from https://eprint.iacr.org/2019/876.pdf. It basically includes Kademlia routing state and Message propagation algorithm. For the purpose of message propagation, Raptor Codes RFC5053 implementation from gofountain is used instead of the recommended fountain code - RaptorQ (more details pkg/util/nativeutils/rcudp/README.md).

Usage

---

Configuration

# By enabling it, node will join an experimental kadcast network
# In addition, topics.Block and topics.Tx will be propagated in kadcast network
# NB: The messages propagated in kadcast are not propagated in gossip
enabled=false

# Enable/Disable RC-UDP transport
raptor=false

# Both listeners (UDP and TCP) are binding on this local addr
# NB The addr should be reachable from outside
address="127.0.0.1:7100"

# Maximum delegates per bucket 
# System parameter β from protocol
maxDelegatesNum=3

# Example list of bootstarpping nodes
bootstrappers=["voucher.dusk.network:9090","voucher.dusk.network:9091"]

Code snippet

# Initiate kadcast message propagation
event = message.NewWithHeader(topics.Block, *buf, []byte{255})
eventBus.Publish(topics.Kadcast, event)

Message Propagation flow

---

1. Publish topics.Kadcast event with message payload and kadcast height
2. kadcast.Writer handles topics.Kadcast event
3. kadcast.Writer serialize the event into Kadcast Wire Message of type Broadcast
4. kadcast.Writer performs kadcast propagation algorithm where transport protocol is

• RC-UDP, if kadcast.raptor=true (config)
• TCP Dial and Send, if kadcast.raptor=false

Transport protocols

---

Current version of kadcast supports two different methods of sending/receiving a message to/from a kadcast peer - TCP Dial and Send and RC-UDP send.

TCP Dial and Send

On each write to a peer, kadcast.Writer establishes a new TCP connection, sends the Kadcast Wire Message and closes the connection. As this is pretty heavy approach, it's useful on testbed testing where latency is ideal.

Raptor Code UDP

RC-UDP (Raptor Code UDP) is UDP-based protocol where each UDP packet on the wire packs a single encoding symbol. See also pkg/util/nativeutils/rcudp/README.md

Kadcast Wire Messages

---

Kadcast wire message contains of a header and a payload. While header is mandatory and it has the same structure for all types of messages, payload depends on msgType and could be empty.

Message Header structure

Size	1	16	4	2	2
Desc	MsgType	SrcPeerID	SrcPeerNonce	SrcPeerPort	Reserved

MsgType:

Ping	0x00
Pong	0x01
FindNodes	0x02
Nodes	0x03
Broadcast	0x0A

Broadcast Message Payload

Size	1	up to 250000
Desc	Kadcast Height	DUSK_PROTOCOL_FRAME

Nodes Message Payload

Size	2	4	2	16	...
Desc	Entries Number	IP	Port	PeerID	...

Ping Message Payload
Empty

Pong Message Payload
Empty

FindNodes Message Payload
Empty

* The structure of DUSK_PROTOCOL_FRAME is the same as Gossip processor can read. See also pkg/p2p/wire/protocol

Maintainer and Kademlia Routing State

---

Maintainer is a component that is responsible to build and maintain the Kadcast Routing State. It is a UDP server that handles the folling messages Types - Ping, Pong, FindNodes and FindNodes.

FindNodes-Nodes Message Flow (pseudo peers A and B)

1. Peer_A sends FindNodes message with its PeerID
2. Peer_B Maintainer handles FindNodes
3. Peer_B Maintainer registers Peer_A
4. Peer_B Maintainer tries to get K closest peers to Peer_A
5. Peer_B Maintainer responds with Nodes message with K_Closest_Peers list and its own PeerID
6. Peer_A handles Nodes message
7. Peer_A registers Peer_B
8. Peer_A starts Ping-Pong message flow for each received PeerID from K_Closest_Peers list

Ping-Pong Message Flow (pseudo peers A and B)

1. Peer_A sends Ping message with its PeerID
2. Peer_B Maintainer handles Ping message from PeerA.
3. Peer_B Maintainer registers PeerA
4. Peer_B Maintainer responses with Pong message that includes its PeerID
5. Peer_A Maintainer handles Pong message and registers Peer_B

Collecting Message

---

1. On receiving Kadcast Wire Message, kadcast.Reader (TCPReader or RaptorCodeReader)
2. kadcast.Writer handles topics.Kadcast event
3. kadcast.Writer serialize the event into Kadcast Wire Message of type Broadcast
4. kadcast.Writer performs kadcast propagation algorithm where transport protocol is

• RC-UDP, if kadcast.raptor=true (config)
• TCP Dial and Send, if kadcast.raptor=false

Documentation

Index

• Constants
• Variables
• func ComputeDistance(peer1, peer2 encoding.PeerInfo) (uint16, [16]byte)
• func DidNetworkReceivedMsg(nodes []*Node, senderIndex int, sentBlock *block.Block) bool
• func GetOutboundIP() net.IP
• func InitBootstrap(router *RoutingTable, bootNodes []encoding.PeerInfo) error
• func JoinNetwork(router *RoutingTable, bootstrapAddrs []string)
• func StartNetworkDiscovery(router *RoutingTable, d time.Duration)
• func TestReceivedMsgOnce(t *testing.T, nodes []*Node, i int, blk *block.Block)
• func TraceRoutingState(r *RoutingTable)
• type ByXORDist
  • func (a ByXORDist) Len() int
  • func (a ByXORDist) Less(i int, j int) bool
  • func (a ByXORDist) Swap(i, j int)
• type Maintainer
  • func NewMaintainer(rtable *RoutingTable) *Maintainer
  • func (m *Maintainer) Close() error
  • func (m *Maintainer) Serve()
• type Node
  • func TestNetwork(num int, basePort int) ([]*Node, error)
  • func TestNode(port int) *Node
• type Peer
  • func NewPeer(eventBus *eventbus.EventBus, g *protocol.Gossip, dp *dupemap.DupeMap, ...) *Peer
  • func (p *Peer) Close()
  • func (p *Peer) Launch(addr string, bootstrapAddrs []string, beta uint8)
• type PeerSort
• type RaptorCodeReader
  • func NewRaptorCodeReader(lpeerInfo encoding.PeerInfo, publisher eventbus.Publisher, ...) *RaptorCodeReader
  • func (r *RaptorCodeReader) Close() error
  • func (r *RaptorCodeReader) Serve()
• type Reader
  • func NewReader(lpeerInfo encoding.PeerInfo, publisher eventbus.Publisher, ...) *Reader
  • func (r *Reader) Close() error
  • func (r *Reader) Serve()
• type RoutingTable
  • func MakeRoutingTable(address string) RoutingTable
  • func TestRouter(port uint16, id [16]byte) *RoutingTable
  • func (rt *RoutingTable) GetTotalPeers() uint64
• type Tree
• type Writer
  • func NewWriter(router *RoutingTable, subscriber eventbus.Subscriber, gossip *protocol.Gossip, ...) *Writer
  • func (w *Writer) Close() error
  • func (w *Writer) Serve()
  • func (w *Writer) Write(m message.Message) error

Constants

const (

	// MaxTCPacketSize is the max size allowed of TCP packet.
	MaxTCPacketSize = 500000

	// MaxUDPacketSize max size of a UDP packet. As per default MTU 1500, UDP
	// packet should be up to 1472 bytes.
	MaxUDPacketSize = 1472
)

const Alpha int = 3

Alpha is the number of nodes to which a node will ask for new nodes with `FIND_NODES` messages.

const InitHeight byte = 128

InitHeight sets the default initial height for a broadcast process.

const (
	// MaxFrameSize is set based on max block size expected.
	MaxFrameSize = 500000
)

Variables

var DefaultAlphaClosestNodes int = 1

DefaultAlphaClosestNodes the node looks up the α closest nodes regarding the XOR-metric in its own buckets.

var DefaultKNumber int = 20

DefaultKNumber is the K number of peers that a node will send on a `FIND_NODES` message.

var DefaultMaxBetaDelegates uint8 = 3

DefaultMaxBetaDelegates maximum number of delegates per bucket.

var DefaultMaxBucketPeers uint8 = 25

DefaultMaxBucketPeers is the maximum number of peers that a `bucket` can hold.

var ErrExceedMaxLen = errors.New("message size exceeds max frame length")

ErrExceedMaxLen is the error thrown if the message size exceeds the max frame length.

Functions

func ComputeDistance

func ComputeDistance(peer1, peer2 encoding.PeerInfo) (uint16, [16]byte)

ComputeDistance returns both bucket number and XOR distance between two Peers.

func DidNetworkReceivedMsg

func DidNetworkReceivedMsg(nodes []*Node, senderIndex int, sentBlock *block.Block) bool

DidNetworkReceivedMsg checks if all network nodes have received the msgPayload only once.

func GetOutboundIP

func GetOutboundIP() net.IP

GetOutboundIP returns local address.

func InitBootstrap

func InitBootstrap(router *RoutingTable, bootNodes []encoding.PeerInfo) error

InitBootstrap inits the Bootstrapping process by sending a `PING` message to every bootstrapping node repeatedly. If it tried 3 or more times and no new `Peers` were added, it panics. Otherways, it returns `nil` and logs the Number of peers the node is connected to at the end of the process.

func JoinNetwork

func JoinNetwork(router *RoutingTable, bootstrapAddrs []string)

JoinNetwork makes attempts to join the network based on the configured bootstrapping nodes.

func StartNetworkDiscovery

func StartNetworkDiscovery(router *RoutingTable, d time.Duration)

StartNetworkDiscovery triggers the network discovery process. The node basically sends `FIND_NODES` messages to the nodes it is currently connected to and evaluates the `Peers` that were added on each iteration. If the closest peer to ours is the same during two iterations of the `FIND_NODES` message, we finish the process logging the ammout of peers we are currently connected to. Otherways, if the closest Peer on two consecutive iterations changes, we keep queriyng the `alpha` closest nodes with `FIND_NODES` messages.

func TestReceivedMsgOnce

func TestReceivedMsgOnce(t *testing.T, nodes []*Node, i int, blk *block.Block)

TestReceivedMsgOnce check periodically (up to 7 sec) if network has received the message.

func TraceRoutingState

func TraceRoutingState(r *RoutingTable)

TraceRoutingState logs the routing table of a peer.

Types

type ByXORDist

type ByXORDist []PeerSort

ByXORDist implements sort.Interface based on the IdDistance respective to myPeerId.

func (ByXORDist) Len

func (a ByXORDist) Len() int

func (ByXORDist) Less

func (a ByXORDist) Less(i int, j int) bool

func (ByXORDist) Swap

func (a ByXORDist) Swap(i, j int)

type Maintainer

type Maintainer struct {
	// contains filtered or unexported fields
}

Maintainer is responsible for building and maintaining Kadcast routing state.

func NewMaintainer

func NewMaintainer(rtable *RoutingTable) *Maintainer

NewMaintainer returns a UDP Reader for maintaining routing state up-to-date.

func (*Maintainer) Close

func (m *Maintainer) Close() error

Close terminates udp read loop. Even terminated, there might be some processPacket routines still running a job.

func (*Maintainer) Serve

func (m *Maintainer) Serve()

Serve starts maintainer main loop of listening and handling UDP packets.

type Node

type Node struct {
	Router   *RoutingTable
	EventBus *eventbus.EventBus

	Lock       sync.RWMutex
	Blocks     []*block.Block
	Duplicated bool
}

Node a very limited instance of a node running kadcast peer only.

func TestNetwork

func TestNetwork(num int, basePort int) ([]*Node, error)

TestNetwork initiates kadcast network bootstraping of N nodes. This will run a set of nodes bound on local addresses (port per node), execute bootstrapping and network discovery.

func TestNode

func TestNode(port int) *Node

TestNode starts a node for testing purposes. A node is represented by a routing state, TCP listener and UDP listener.

type Peer

type Peer struct {
	// contains filtered or unexported fields
}

Peer is a wrapper of all 2 kadcast processing routing.

func NewPeer

func NewPeer(eventBus *eventbus.EventBus, g *protocol.Gossip, dp *dupemap.DupeMap, raptorCodeEnabled bool) *Peer

NewPeer makes a kadcast peer instance.

func (*Peer) Close

func (p *Peer) Close()

Close terminates peer service.

func (*Peer) Launch

func (p *Peer) Launch(addr string, bootstrapAddrs []string, beta uint8)

Launch starts kadcast service.

type PeerSort

type PeerSort struct {
	// contains filtered or unexported fields
}

PeerSort is a helper type to sort `Peers`.

type RaptorCodeReader

type RaptorCodeReader struct {
	// contains filtered or unexported fields
}

RaptorCodeReader is rc-udp based listener that reads Broadcast messages from the Kadcast network and delegates their processing to the messageRouter.

func NewRaptorCodeReader

func NewRaptorCodeReader(lpeerInfo encoding.PeerInfo, publisher eventbus.Publisher,
	gossip *protocol.Gossip, dupeMap *dupemap.DupeMap) *RaptorCodeReader

NewRaptorCodeReader makes an instance of RaptorCodeReader.

func (*RaptorCodeReader) Close

func (r *RaptorCodeReader) Close() error

Close closes reader TCP listener.

func (*RaptorCodeReader) Serve

func (r *RaptorCodeReader) Serve()

Serve starts accepting and processing TCP connection and packets.

type Reader

type Reader struct {
	// contains filtered or unexported fields
}

Reader is running a TCP listner handling TCP Broadcast packets from kadcast network

On a TCP connection Read a single tcp packet from the accepted connection Validate the packet Extract Gossip Packet Build and Publish eventBus message The alternative to this reader is the RaptorCodeReader that is based on RC-UDP.

func NewReader

func NewReader(lpeerInfo encoding.PeerInfo, publisher eventbus.Publisher, gossip *protocol.Gossip, dupeMap *dupemap.DupeMap) *Reader

NewReader makes a new kadcast reader that handles TCP packets of broadcasting.

func (*Reader) Close

func (r *Reader) Close() error

Close closes reader TCP listener.

func (*Reader) Serve

func (r *Reader) Serve()

Serve starts accepting and processing TCP connection and packets.

type RoutingTable

type RoutingTable struct {
	LpeerInfo encoding.PeerInfo
	// contains filtered or unexported fields
}

RoutingTable holds all of the data needed to interact with the routing data and also the networking utils.

func MakeRoutingTable

func MakeRoutingTable(address string) RoutingTable

MakeRoutingTable allows to create a router which holds the peerInfo and also the routing tree information.

func TestRouter

func TestRouter(port uint16, id [16]byte) *RoutingTable

TestRouter creates a peer router with a fixed id.

func (*RoutingTable) GetTotalPeers

func (rt *RoutingTable) GetTotalPeers() uint64

GetTotalPeers the total amount of peers that a `Peer` is connected to.

type Tree

type Tree struct {
	// contains filtered or unexported fields
}

Tree stores `L` buckets inside of it. This is basically the routing info of every peer.

type Writer

type Writer struct {
	// contains filtered or unexported fields
}

Writer abstracts all of the logic and fields needed to write messages to other network nodes.

func NewWriter

func NewWriter(router *RoutingTable, subscriber eventbus.Subscriber, gossip *protocol.Gossip, raptorCodeEnabled bool) *Writer

NewWriter returns a Writer. It will still need to be initialized by subscribing to the gossip topic with a stream handler, and by running the WriteLoop in a goroutine..

func (*Writer) Close

func (w *Writer) Close() error

Close unsubscribes from eventbus events.

func (*Writer) Serve

func (w *Writer) Serve()

Serve processes any kadcast messaging to the wire.

func (*Writer) Write

func (w *Writer) Write(m message.Message) error

Write expects the actual payload in a marshaled form.