routing

package
v0.0.0-...-a42b203 Latest Latest
Warning

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

 Go to latest Published: Aug 4, 2017 License: MIT Imports: 23 Imported by: 0

README

routing

Build Status MIT licensed GoDoc

The routing package implements authentication+validation of channel announcements, pruning of the channel graph, path finding within the network, sending outgoing payments into the network and synchronizing new peers to our channel graph state.

Installation and Updating

$ go get -u github.com/lightningnetwork/lnd/routing

Documentation

Index

Constants

View Source 
const (
	// ErrNoPathFound is returned when a path to the target destination
	// does not exist in the graph.
	ErrNoPathFound errorCode = iota

	// ErrNoRouteFound is returned when the router is unable to find a
	// valid route to the target destination after fees and time-lock
	// limitations are factored in.
	ErrNoRouteFound

	// ErrInsufficientCapacity is returned when a path if found, yet the
	// capacity of one of the channels in the path is insufficient to carry
	// the payment.
	ErrInsufficientCapacity

	// ErrMaxHopsExceeded is returned when a candidate path is found, but
	// the length of that path exceeds HopLimit.
	ErrMaxHopsExceeded

	// ErrTargetNotInNetwork is returned when the target of a path-finding
	// or payment attempt isn't known to be within the current version of
	// the channel graph.
	ErrTargetNotInNetwork

	// ErrOutdated is returned when the routing update already have
	// been applied.
	ErrOutdated

	// ErrIgnored is returned when the update have been ignored because
	// this update can't bring us something new, or because a node
	// announcement was given for node not found in any channel.
	ErrIgnored
)
View Source 
const (
	// HopLimit is the maximum number hops that is permissible as a route.
	// Any potential paths found that lie above this limit will be rejected
	// with an error. This value is computed using the current fixed-size
	// packet length of the Sphinx construction.
	HopLimit = 20
)

Variables

This section is empty.

Functions

func DisableLog 

func DisableLog()

DisableLog disables all library log output. Logging output is disabled by by default until UseLogger is called.

func IsError 

func IsError(e interface{}, codes ...errorCode) bool

IsError is a helper function which is needed to have ability to check that returned error has specific error code.

func UseLogger 

func UseLogger(logger btclog.Logger)

UseLogger uses a specified Logger to output package logging info. This should be used in preference to SetLogWriter if the caller is also using btclog.

Types

type ChannelEdgeUpdate 

type ChannelEdgeUpdate struct {
	// ChanID is the unique short channel ID for the channel. This encodes
	// where in the blockchain the channel's funding transaction was
	// originally confirmed.
	ChanID uint64

	// ChanPoint is the outpoint which represents the multi-sig funding
	// output for the channel.
	ChanPoint wire.OutPoint

	// Capacity is the capacity of the newly created channel.
	Capacity btcutil.Amount

	// MinHTLC is the minimum HTLC amount that this channel will forward.
	MinHTLC btcutil.Amount

	// BaseFee is the base fee that will charged for all HTLC's forwarded
	// across the this channel direction.
	BaseFee btcutil.Amount

	// FeeRate is the fee rate that will be shared for all HTLC's forwarded
	// across this channel direction.
	FeeRate btcutil.Amount

	// TimeLockDelta is the time-lock expressed in blocks that will be
	// added to outgoing HTLC's from incoming HTLC's. This value is the
	// difference of the incoming and outgoing HTLC's time-locks routed
	// through this hop.
	TimeLockDelta uint16

	// AdvertisingNode is the node that's advertising this edge.
	AdvertisingNode *btcec.PublicKey

	// ConnectingNode is the node that the advertising node connects to.
	ConnectingNode *btcec.PublicKey
}

ChannelEdgeUpdate is an update for a new channel within the ChannelGraph. This update is sent out once a new authenticated channel edge is discovered within the network. These updates are directional, so if a channel is fully public, then there will be two updates sent out: one for each direction within the channel. Each update will carry that particular routing edge policy for the channel direction.

An edge is a channel in the direction of AdvertisingNode -> ConnectingNode.

type ChannelGraphSource 

type ChannelGraphSource interface {
	// AddNode is used to add information about a node to the router
	// database. If the node with this pubkey is not present in an existing
	// channel, it will be ignored.
	AddNode(node *channeldb.LightningNode) error

	// AddEdge is used to add edge/channel to the topology of the router,
	// after all information about channel will be gathered this
	// edge/channel might be used in construction of payment path.
	AddEdge(edge *channeldb.ChannelEdgeInfo) error

	// AddProof updates the channel edge info with proof which is needed to
	// properly announce the edge to the rest of the network.
	AddProof(chanID lnwire.ShortChannelID, proof *channeldb.ChannelAuthProof) error

	// UpdateEdge is used to update edge information, without this message
	// edge considered as not fully constructed.
	UpdateEdge(policy *channeldb.ChannelEdgePolicy) error

	// ForAllOutgoingChannels is used to iterate over all channels
	// eminating from the "source" node which is the center of the
	// star-graph.
	ForAllOutgoingChannels(cb func(c *channeldb.ChannelEdgePolicy) error) error

	// CurrentBlockHeight returns the block height from POV of the router
	// subsystem.
	CurrentBlockHeight() (uint32, error)

	// GetChannelByID return the channel by the channel id.
	GetChannelByID(chanID lnwire.ShortChannelID) (*channeldb.ChannelEdgeInfo,
		*channeldb.ChannelEdgePolicy, *channeldb.ChannelEdgePolicy, error)

	// ForEachNode is used to iterate over every node in the known graph.
	ForEachNode(func(node *channeldb.LightningNode) error) error

	// ForEachChannel is used to iterate over every channel in the known
	// graph.
	ForEachChannel(func(chanInfo *channeldb.ChannelEdgeInfo,
		e1, e2 *channeldb.ChannelEdgePolicy) error) error
}

ChannelGraphSource represent the source of information about the topology of lightning network, it responsible for addition of nodes, edges and applying edges updates, return the current block with with out topology is synchronized.

type ChannelHop 

type ChannelHop struct {
	// Capacity is the total capacity of the channel being traversed. This
	// value is expressed for stability in satoshis.
	Capacity btcutil.Amount

	// Chain is a 32-byte has that denotes the base blockchain network of
	// the channel. The 32-byte hash is the "genesis" block of the
	// blockchain, or the very first block in the chain.
	//
	// TODO(roasbeef): store chain within edge info/policy in database.
	Chain chainhash.Hash

	*channeldb.ChannelEdgePolicy
}

ChannelHop is an intermediate hop within the network with a greater multi-hop payment route. This struct contains the relevant routing policy of the particular edge, as well as the total capacity, and origin chain of the channel itself.

type ChannelRouter 

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

ChannelRouter is the layer 3 router within the Lightning stack. Below the ChannelRouter is the HtlcSwitch, and below that is the Bitcoin blockchain itself. The primary role of the ChannelRouter is to respond to queries for potential routes that can support a payment amount, and also general graph reachability questions. The router will prune the channel graph automatically as new blocks are discovered which spend certain known funding outpoints, thereby closing their respective channels.

func New 

func New(cfg Config) (*ChannelRouter, error)

New creates a new instance of the ChannelRouter with the specified configuration parameters. As part of initialization, if the router detects that the channel graph isn't fully in sync with the latest UTXO (since the channel graph is a subset of the UTXO set) set, then the router will proceed to fully sync to the latest state of the UTXO set.

func (*ChannelRouter) AddEdge 

func (r *ChannelRouter) AddEdge(edge *channeldb.ChannelEdgeInfo) error

AddEdge is used to add edge/channel to the topology of the router, after all information about channel will be gathered this edge/channel might be used in construction of payment path.

NOTE: This method is part of the ChannelGraphSource interface.

func (*ChannelRouter) AddNode 

func (r *ChannelRouter) AddNode(node *channeldb.LightningNode) error

AddNode is used to add information about a node to the router database. If the node with this pubkey is not present in an existing channel, it will be ignored.

NOTE: This method is part of the ChannelGraphSource interface.

func (*ChannelRouter) AddProof 

func (r *ChannelRouter) AddProof(chanID lnwire.ShortChannelID,
	proof *channeldb.ChannelAuthProof) error

AddProof updates the channel edge info with proof which is needed to properly announce the edge to the rest of the network.

NOTE: This method is part of the ChannelGraphSource interface.

func (*ChannelRouter) CurrentBlockHeight 

func (r *ChannelRouter) CurrentBlockHeight() (uint32, error)

CurrentBlockHeight returns the block height from POV of the router subsystem.

NOTE: This method is part of the ChannelGraphSource interface.

func (*ChannelRouter) FindRoutes 

func (r *ChannelRouter) FindRoutes(target *btcec.PublicKey, amt btcutil.Amount) ([]*Route, error)

FindRoutes attempts to query the ChannelRouter for the all available paths to a particular target destination which is able to send `amt` after factoring in channel capacities and cumulative fees along each route route. To find all eligible paths, we use a modified version of Yen's algorithm which itself uses a modified version of Dijkstra's algorithm within its inner loop. Once we have a set of candidate routes, we calculate the required fee and time lock values running backwards along the route. The route that will be ranked the highest is the one with the lowest cumulative fee along the route.

func (*ChannelRouter) ForAllOutgoingChannels 

func (r *ChannelRouter) ForAllOutgoingChannels(cb func(c *channeldb.ChannelEdgePolicy) error) error

ForAllOutgoingChannels is used to iterate over all outgiong channel owned by the router.

NOTE: This method is part of the ChannelGraphSource interface.

func (*ChannelRouter) ForEachChannel 

func (r *ChannelRouter) ForEachChannel(cb func(chanInfo *channeldb.ChannelEdgeInfo,
	e1, e2 *channeldb.ChannelEdgePolicy) error) error

ForEachChannel is used to iterate over every known edge (channel) within our view of the channel graph.

NOTE: This method is part of the ChannelGraphSource interface.

func (*ChannelRouter) ForEachNode 

func (r *ChannelRouter) ForEachNode(cb func(*channeldb.LightningNode) error) error

ForEachNode is used to iterate over every node in router topology.

NOTE: This method is part of the ChannelGraphSource interface.

func (*ChannelRouter) GetChannelByID 

func (r *ChannelRouter) GetChannelByID(chanID lnwire.ShortChannelID) (
	*channeldb.ChannelEdgeInfo,
	*channeldb.ChannelEdgePolicy,
	*channeldb.ChannelEdgePolicy, error)

GetChannelByID return the channel by the channel id.

NOTE: This method is part of the ChannelGraphSource interface.

func (*ChannelRouter) SendPayment 

func (r *ChannelRouter) SendPayment(payment *LightningPayment) ([32]byte, *Route, error)

SendPayment attempts to send a payment as described within the passed LightningPayment. This function is blocking and will return either: when the payment is successful, or all candidates routes have been attempted and resulted in a failed payment. If the payment succeeds, then a non-nil Route will be returned which describes the path the successful payment traversed within the network to reach the destination. Additionally, the payment preimage will also be returned.

func (*ChannelRouter) Start 

func (r *ChannelRouter) Start() error

Start launches all the goroutines the ChannelRouter requires to carry out its duties. If the router has already been started, then this method is a noop.

func (*ChannelRouter) Stop 

func (r *ChannelRouter) Stop() error

Stop signals the ChannelRouter to gracefully halt all routines. This method will *block* until all goroutines have excited. If the channel router has already stopped then this method will return immediately.

func (*ChannelRouter) SubscribeTopology 

func (r *ChannelRouter) SubscribeTopology() (*TopologyClient, error)

SubscribeTopology returns a new topology client which can be used by the caller to receive notifications when ever a change in the channel graph topology occurs. Changes that will be sent at notifications include: new nodes appearing, node updating their attributes, new channels, channels closing, and updates in the routing policies of a channel's directed edges.

func (*ChannelRouter) UpdateEdge 

func (r *ChannelRouter) UpdateEdge(update *channeldb.ChannelEdgePolicy) error

UpdateEdge is used to update edge information, without this message edge considered as not fully constructed.

NOTE: This method is part of the ChannelGraphSource interface.

type ClosedChanSummary 

type ClosedChanSummary struct {
	// ChanID is the short-channel ID which uniquely identifies the
	// channel.
	ChanID uint64

	// Capacity was the total capacity of the channel before it was closed.
	Capacity btcutil.Amount

	// ClosedHeight is the height in the chain that the channel was closed
	// at.
	ClosedHeight uint32

	// ChanPoint is the funding point, or the multi-sig utxo which
	// previously represented the channel.
	ChanPoint wire.OutPoint
}

ClosedChanSummary is a summary of a channel that was detected as being closed by monitoring the blockchain. Once a channel's funding point has been spent, the channel will automatically be marked as closed by the ChainNotifier.

TODO(roasbeef): add nodes involved?

type Config 

type Config struct {
	// Graph is the channel graph that the ChannelRouter will use to gather
	// metrics from and also to carry out path finding queries.
	// TODO(roasbeef): make into an interface
	Graph *channeldb.ChannelGraph

	// Chain is the router's source to the most up-to-date blockchain data.
	// All incoming advertised channels will be checked against the chain
	// to ensure that the channels advertised are still open.
	Chain lnwallet.BlockChainIO

	// ChainView is an instance of a FilteredChainView which is used to
	// watch the sub-set of the UTXO set (the set of active channels) that
	// we need in order to properly maintain the channel graph.
	ChainView chainview.FilteredChainView

	// FeeSchema is the set fee schema that will be announced on to the
	// network.
	// TODO(roasbeef): should either be in discovery or switch
	FeeSchema *FeeSchema

	// SendToSwitch is a function that directs a link-layer switch to
	// forward a fully encoded payment to the first hop in the route
	// denoted by its public key. A non-nil error is to be returned if the
	// payment was unsuccessful.
	SendToSwitch func(firstHop *btcec.PublicKey, htlcAdd *lnwire.UpdateAddHTLC,
		circuit *sphinx.Circuit) ([sha256.Size]byte, error)
}

Config defines the configuration for the ChannelRouter. ALL elements within the configuration MUST be non-nil for the ChannelRouter to carry out its duties.

type FeeSchema 

type FeeSchema struct {

	// BaseFee is the base amount that will be chained for ANY payment
	// forwarded.
	BaseFee btcutil.Amount

	// FeeRate is the rate that will be charged for forwarding payments.
	// The fee rate has a granularity of 1/1000 th of a mili-satoshi, or a
	// millionth of a satoshi.
	FeeRate btcutil.Amount
}

FeeSchema is the set fee configuration for a Lighting Node on the network. Using the coefficients described within he schema, the required fee to forward outgoing payments can be derived.

TODO(roasbeef): should be in switch instead?

type Hop 

type Hop struct {
	// Channel is the active payment channel edge that this hop will travel
	// along.
	Channel *ChannelHop

	// OutgoingTimeLock is the timelock value that should be used when
	// crafting the _outgoing_ HTLC from this hop.
	OutgoingTimeLock uint32

	// AmtToForward is the amount that this hop will forward to the next
	// hop. This value is less than the value that the incoming HTLC
	// carries as a fee will be subtracted by the hop.
	AmtToForward btcutil.Amount

	// Fee is the total fee that this hop will subtract from the incoming
	// payment, this difference nets the hop fees for forwarding the
	// payment.
	Fee btcutil.Amount
}

Hop represents the forwarding details at a particular position within the final route. This struct houses the values necessary to create the HTLC which will travel along this hop, and also encode the per-hop payload included within the Sphinx packet.

type LightningPayment 

type LightningPayment struct {
	// Target is the node in which the payment should be routed towards.
	Target *btcec.PublicKey

	// Amount is the value of the payment to send through the network in
	// satoshis.
	// TODO(roasbeef): this should be milli satoshis
	Amount btcutil.Amount

	// PaymentHash is the r-hash value to use within the HTLC extended to
	// the first hop.
	PaymentHash [32]byte
}

LightningPayment describes a payment to be sent through the network to the final destination.

type NetworkNodeUpdate 

type NetworkNodeUpdate struct {
	// Addresses is a slice of all the node's known addresses.
	Addresses []net.Addr

	// IdentityKey is the identity public key of the target node. This is
	// used to encrypt onion blobs as well as to authenticate any new
	// updates.
	IdentityKey *btcec.PublicKey

	// GlobalFeatures is a set of opaque bytes that describe the set of
	// features supported by the node.
	GlobalFeatures []byte

	// Alias is the alias or nick name of the node.
	Alias string
}

NetworkNodeUpdate is an update for a node within the Lightning Network. A NetworkNodeUpdate is sent out either when a new node joins the network, or a node broadcasts a new update with a newer time stamp that supersedes it's old update. All updates are properly authenticated.

type Route 

type Route struct {
	// TotalTimeLock is the cumulative (final) time lock across the entire
	// route. This is the CLTV value that should be extended to the first
	// hop in the route. All other hops will decrement the time-lock as
	// advertised, leaving enough time for all hops to wait for or present
	// the payment preimage to complete the payment.
	TotalTimeLock uint32

	// TotalFees is the sum of the fees paid at each hop within the final
	// route. In the case of a one-hop payment, this value will be zero as
	// we don't need to pay a fee it ourself.
	TotalFees btcutil.Amount

	// TotalAmount is the total amount of funds required to complete a
	// payment over this route. This value includes the cumulative fees at
	// each hop. As a result, the HTLC extended to the first-hop in the
	// route will need to have at least this many satoshis, otherwise the
	// route will fail at an intermediate node due to an insufficient
	// amount of fees.
	TotalAmount btcutil.Amount

	// Hops contains details concerning the specific forwarding details at
	// each hop.
	Hops []*Hop
}

Route represents a path through the channel graph which runs over one or more channels in succession. This struct carries all the information required to craft the Sphinx onion packet, and send the payment along the first hop in the path. A route is only selected as valid if all the channels have sufficient capacity to carry the initial payment amount after fees are accounted for.

func (*Route) ToHopPayloads 

func (r *Route) ToHopPayloads() []sphinx.HopData

ToHopPayloads converts a complete route into the series of per-hop payloads that is to be encoded within each HTLC using an opaque Sphinx packet.

type TopologyChange 

type TopologyChange struct {
	// NodeUpdates is a slice of nodes which are either new to the channel
	// graph, or have had their attributes updated in an authenticated
	// manner.
	NodeUpdates []*NetworkNodeUpdate

	// ChanelEdgeUpdates is a slice of channel edges which are either newly
	// opened and authenticated, or have had their routing policies
	// updated.
	ChannelEdgeUpdates []*ChannelEdgeUpdate

	// ClosedChannels contains a slice of close channel summaries which
	// described which block a channel was closed at, and also carry
	// supplemental information such as the capacity of the former channel.
	ClosedChannels []*ClosedChanSummary
}

TopologyChange represents a new set of modifications to the channel graph. Topology changes will be dispatched in real-time as the ChannelGraph validates and process modifications to the authenticated channel graph.

type TopologyClient 

type TopologyClient struct {
	// TopologyChanges is a receive only channel that new channel graph
	// updates will be sent over.
	//
	// TODO(roasbeef): chan for each update type instead?
	TopologyChanges <-chan *TopologyChange

	// Cancel is a function closure that should be executed when the client
	// wishes to cancel their notification intent. Doing so allows the
	// ChannelRouter to free up resources.
	Cancel func()
}

TopologyClient represents an intent to receive notifications from the channel router regarding changes to the topology of the channel graph. The TopologyChanges channel will be sent upon with new updates to the channel graph in real-time as they're encountered.

Source Files

View all Source files

Directories

Path Synopsis

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.