dag

package
v0.0.0-...-c56c372 Latest Latest
Warning

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

 Go to latest Published: Mar 9, 2021 License: Unlicense Imports: 8 Imported by: 0

README

phantom

ISC License

Overview

Package phantom implements the PHANTOM and Greedy PHANTOM protocols for blockdag ordering and coloring.

Protocol Files
PHANTOM graph.go, coloring.go
Greedy PHANTOM greedygraphmem.go

In soterd, the blocks are connected to each other in a directed acyclic graph (BlockDAG), not a chain. This means that a block may have multiple parent blocks, and they may be at different heights. Using a blockdag allows for mining to be more inclusive, and increases transaction throughput in comparison to a blockchain. All blocks are attached to the BlockDAG, so it's important to be able to differentiate between blocks that contain legitimate transactions and blocks that don't. This is where PHANTOM comes in.

PHANTOM is a protocol authored by Yonatan Sompolinsky and Aviv Zohar, which can help color and sort a dag. The coloring allows us to order nodes in terms of well-connected to the bulk of the graph, to less-connected. For a BlockDAG, a block's legitimacy is associated with its connectedness, so by ordering well-connected blocks before less-connected blocks, and treating the first matching transaction from genesis block as the valid one, we can guard against fraudulant transactions/double spending attempts published to the network by bad actors.

Greedy PHANTOM is a newer protocol authored by Aviv Yaish, which attempts to improve the efficiency of PHANTOM.

By combining the use of a BlockDAG with a coloring/sorting protocol, we can improve transaction throughput vs a blockchain by allowing more blocks to be accepted, while guarding against fraudulent transactions.

How PHANTOM works

  1. Determine a set of well-connected nodes in the dag.
    • Use the node's past and future to determine how well-connected the block is.
  2. Traverse through dag, following parent/child relationships. The well-connected (blue) set is used to determine what order the nodes will be in. Nodes not in the blue-set (red nodes) will be ordered later.
  3. Produce an ordering for the dag.

How Greedy PHANTOM works

Greedy PHANTOM is the same concept as PHANTOM, with some modifications to make it more efficient.

  • Coloring is inherited from a node's 'bluest' (most well-connected) parent (hence the "Greedy"). This is called the coloring parent.
  • The bluest tip of the graph is called the coloring tip.
  • Coloring and sorting is incremental, in that only changes not processed by the node's coloring parent are processed when a node is added to the dag.
    • This uses a coloring chain, a set of blocks following coloring parents.

Here is a gif demonstrating the coloring of a dag with greedy phantom:

greedy phantom coloring

In this image:

  • Green node: The coloring tip of the graph
  • Blue nodes: Nodes in the blue set, from the perspective of the new node. (nodes that are well-connected to the bulk of the graph)
  • Red nodes: Nodes outside of the blue set, from the perspective of the new node. (nodes that are less-connected to the bulk of the graph)
  • Dotted-line nodes: The colouring chain of the graph. (a set of bluest nodes spanning from the colouring tip to genesis)

Note how some nodes flip back and forth between blue and red; How well-connected they appear to be from new tips can change as the graph grows. As more blocks are generated the coloring of the graph from the perspective of the tips should stabilize, and the sort order/coloring can be considered more authoritative. For transactions, having a grace period matching this stabilization time would help avoid bad actors from executing timing attacks against the BlockDAG.

PHANTOM vs Greedy PHANTOM

Pros of PHANTOM
  • Its implementation is easier to work with than Greedy PHANTOM.
Cons of PHANTOM
  • Time spent coloring/sorting is an issue, because the future of each node is evaluated, and the future of a node will grow indefinitely.

In order to use caching to limit the coloring/sorting time, boundaries have to be defined for:

  • How many generations below the tips will we allow new nodes to connect to old ones? (70? 200? any past node?)
    • Once this is defined, the past sort-order can be below that threshold can be made permanent. Then we can restrict the evaluation of the dag to nodes above the threshold.
  • How many generations into the future from a node, would be used for determining if it's in the blue-set.
    • Limiting how far into a node's future we look may influencing the coloring/sorting results, so this is not ideal.
Pros of Greedy PHANTOM
  • By not looking at a node's future, time spent coloring/sorting of nodes scales better than PHANTOM as the dag grows in size.
Cons of Greedy PHANTOM
  • The coloring/sorting implementation is more complicated than PHANTOM. It may be harder to understand coloring/sorting flow, to maintain without introducing issues.
Other comparisons
  • Our implementation of PHANTOM determines coloring/sorting on-demand (not when nodes are added to the dag). Greedy PHANTOM determines coloring/sorting as nodes are added to the dag, so there's more up-front computation.

Why we choose Greedy PHANTOM

Greedy PHANTOM looks like it has potential for performing better than PHANTOM as the dag grows.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func GetIds 

func GetIds(nodes []*Node) []string

GetIds returns the ids of the given nodes

func OrderDAG 

func OrderDAG(g *Graph, genesisNode *Node, k int, blueSetCache *BlueSetCache, minHeight int32, orderCache *OrderCache) ([]*Node, []*Node, error)

OrderDAG returns the graphs' tips and order

Types

type BlueSetCache 

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

func NewBlueSetCache 

func NewBlueSetCache() *BlueSetCache

func (*BlueSetCache) Add 

func (blueset *BlueSetCache) Add(n *Node, set *nodeSet)

Add the node associated with the set to the cache

func (*BlueSetCache) Expire 

func (blueset *BlueSetCache) Expire(amt int)

Expire removes a number of entries from the cache

func (*BlueSetCache) GetBlueNodes 

func (blueset *BlueSetCache) GetBlueNodes(n *Node) []*Node

func (*BlueSetCache) GetBlueSet 

func (blueset *BlueSetCache) GetBlueSet(n *Node) *nodeSet

GetBlueSet returns the nodeSet associated with the node

func (*BlueSetCache) InCache 

func (blueset *BlueSetCache) InCache(n *Node) bool

InCache returns true if the node is in the blueset cache

func (*BlueSetCache) String 

func (blueSet *BlueSetCache) String() string

String returns a string representing the current cache state

type ChainMap 

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

func NewChainMap 

func NewChainMap(elements ...interface{}) *ChainMap

NewChainMap returns a new ChainMap

func (*ChainMap) Contains 

func (cm *ChainMap) Contains(key string) bool

Contains returns true when it finds that the key exists in the first matching map in the ChainMap. If the element is itself a chainmap, its members are parsed first.

func (*ChainMap) Get 

func (cm *ChainMap) Get(key string) (int, bool)

Get returns the first match from the sequence of members in the ChainMap. Returns true if a match was found.

func (*ChainMap) Keys 

func (cm *ChainMap) Keys() *OrderedStringSet

Keys returns an OrderedStringSet of keys from the ChainMap

func (*ChainMap) Pop 

func (cm *ChainMap) Pop() []string

Pop removes and returns the elements of the last entry of the ChainMap

func (*ChainMap) Remove 

func (cm *ChainMap) Remove(key string)

Remove removes an item from all OrderMaps in the ChainMap

type Graph 

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

GRAPH

func NewGraph 

func NewGraph() *Graph

func (*Graph) AddEdge 

func (g *Graph) AddEdge(n1 *Node, n2 *Node) bool

func (*Graph) AddEdgeById 

func (g *Graph) AddEdgeById(n1 string, n2 string) bool

func (*Graph) AddEdgesById 

func (g *Graph) AddEdgesById(n1 string, parents []string) []bool

func (*Graph) AddNode 

func (g *Graph) AddNode(n *Node) bool

func (*Graph) AddNodeById 

func (g *Graph) AddNodeById(id string) bool

func (*Graph) GetAnticone 

func (g *Graph) GetAnticone(node *Node) *nodeSet

GetAnticone returns anticone of node on g: set of all nodes of g - past(node) - future(node) - node

func (*Graph) GetAnticoneWithHorizon 

func (g *Graph) GetAnticoneWithHorizon(node *Node, horizon int) *nodeSet

GetAnticoneWithHorizon returns the anticone of node on the graph, limited in the past to the depth of ancestor nodes given by horizon.

anticone of node on g: set of all nodes of g - past(node) - future(node) - node

func (*Graph) GetMissingNodes 

func (g *Graph) GetMissingNodes(subtips []string) []string

func (*Graph) GetNodeById 

func (g *Graph) GetNodeById(nodeId string) *Node

func (*Graph) GetPast 

func (g *Graph) GetPast(node2 *Node) *Graph

GetPast returns a sub graph with node's parents as tips

func (*Graph) GetPastWithHorizon 

func (g *Graph) GetPastWithHorizon(node2 *Node, horizon int) *Graph

func (*Graph) GetSize 

func (g *Graph) GetSize() int

func (*Graph) GetTips 

func (g *Graph) GetTips() []*Node

func (*Graph) GetVirtual 

func (g *Graph) GetVirtual() *Graph

GetVirtual returns a copy of the graph with a virtual node at the end, whose parents are the tips of the graph

func (*Graph) PrintGraph 

func (g *Graph) PrintGraph() string

func (*Graph) RemoveTip 

func (g *Graph) RemoveTip(n1 *Node)

func (*Graph) RemoveTipById 

func (g *Graph) RemoveTipById(nodeId string)

type GreedyGraphMem 

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

GreedyGraph represents a graph of nodes, using Greedy PHANTOM colouring

func NewGreedyGraphMem 

func NewGreedyGraphMem(k int) (*GreedyGraphMem, error)

NewGreedyGraphMem returns a GreedyGraphMem

func (*GreedyGraphMem) Add 

func (g *GreedyGraphMem) Add(id string, parents []string) (bool, error)

Add adds a node to the graph with the given parents, then updates coloring and graph order

func (*GreedyGraphMem) AddEdge 

func (g *GreedyGraphMem) AddEdge(a, b string) (bool, error)

AddEdge adds an edge from node a to b. (b is parent of a) Returns true if the edge was added.

func (*GreedyGraphMem) AddMultiEdge 

func (g *GreedyGraphMem) AddMultiEdge(a string, parents []string) (bool, error)

AddMultiEdgeById adds an edge from node with id a to nodes in parents. Returns true if all edges were added.

func (*GreedyGraphMem) AddNode 

func (g *GreedyGraphMem) AddNode(id string) (bool, error)

AddNode adds a node to the graph Returns true if the node was added.

func (*GreedyGraphMem) ColoringOrder 

func (g *GreedyGraphMem) ColoringOrder() (*OrderedStringSet, error)

ColoringOrder returns the coloring order of the graph

func (*GreedyGraphMem) Height 

func (g *GreedyGraphMem) Height(id string) (int, error)

Height returns the min, max height of the node

func (*GreedyGraphMem) NodeExists 

func (g *GreedyGraphMem) NodeExists(id string) (bool, error)

NodeExists returns true if the node exists in the graph

func (*GreedyGraphMem) Nodes 

func (g *GreedyGraphMem) Nodes() []string

Nodes returns all nodes in the graph

func (*GreedyGraphMem) Order 

func (g *GreedyGraphMem) Order() ([]string, error)

Order returns the topological order of the graph

func (*GreedyGraphMem) Parents 

func (g *GreedyGraphMem) Parents(id string) ([]string, error)

Parents returns the parents of the node

func (*GreedyGraphMem) Past 

func (g *GreedyGraphMem) Past(id string) ([]string, error)

Past returns the past of the node

func (*GreedyGraphMem) RemoveEdge 

func (g *GreedyGraphMem) RemoveEdge(a, b string) bool

RemoveEdge removes an edge from node a to b. b is not parent of a a is not child of b Returns true if the edge was removed.

func (*GreedyGraphMem) RemoveTip 

func (g *GreedyGraphMem) RemoveTip(id string) error

RemoveTip removes a tip from the graph.

func (*GreedyGraphMem) TipDiff 

func (g *GreedyGraphMem) TipDiff(subTips []string) ([]string, error)

TipDiff returns the unioned antiPast of the given subTips; nodes from the future of those subTips to the tips of the graph, including non-adjacent nodes.

func (*GreedyGraphMem) Tips 

func (g *GreedyGraphMem) Tips() ([]string, error)

Tips returns the tip nodes of the graph

func (*GreedyGraphMem) ToString 

func (g *GreedyGraphMem) ToString() (string, error)

ToString returns a string representation of the graph

type Node 

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

NODE in the BlockDAG case: parent of the node has an edge from the node to it: node -> parent child of the node has an edge from it to the node: child -> node

func SortNodes 

func SortNodes(nodes []*Node) []*Node

SortNodes returns a slice of the nodes that are alphabetically-sorted (useful for sorting orderedNodeSet.elements())

func (*Node) GetId 

func (n *Node) GetId() string

type NodeGraphCache 

type NodeGraphCache struct {
	Name string

	sync.RWMutex
	// contains filtered or unexported fields
}

func NewNodeGraphCache 

func NewNodeGraphCache(name string) *NodeGraphCache

NewNodeGraphCache returns a NodeGraphCache, which can be used to help reduce repetitive computation for Node connectivity.

func (*NodeGraphCache) Add 

func (ngc *NodeGraphCache) Add(n *Node, g *Graph)

Add adds an entry to the past cache

func (*NodeGraphCache) Delete 

func (ngc *NodeGraphCache) Delete(n *Node)

Delete deletes an entry from the cache

func (*NodeGraphCache) Expire 

func (ngc *NodeGraphCache) Expire(amt int)

Expire removes a number of least-used entries from the cache

func (*NodeGraphCache) Get 

func (ngc *NodeGraphCache) Get(n *Node) (*NodeGraphCacheEntry, bool)

Get returns a cache entry and bool indicating cache hit or miss. Entry is nil if not found.

type NodeGraphCacheEntry 

type NodeGraphCacheEntry struct {
	// Having a pointer to the Node makes working with sorted entries easier.
	Node  *Node
	Graph *Graph
	// contains filtered or unexported fields
}

type OrderCache 

type OrderCache struct {

	// Methods use locks to ensure stable access to the cache between goroutines
	sync.RWMutex
	// contains filtered or unexported fields
}

func NewOrderCache 

func NewOrderCache() *OrderCache

NewOrderCache returns an orderCache, which can be used to help reduce repetitive computation as dag size increases

func (*OrderCache) Add 

func (oc *OrderCache) Add(height int32, tips, order []*Node) error

Add adds the entry to the cache

func (*OrderCache) CanAdd 

func (oc *OrderCache) CanAdd(height int32) (string, bool)

canAdd returns true if it looks like it's ok to add an entry to the cache at the given height

func (*OrderCache) Expire 

func (oc *OrderCache) Expire(amt int)

Expire removes the lowest n entries from the cache

func (*OrderCache) Get 

func (oc *OrderCache) Get(height int32) (*OrderCacheEntry, bool)

Get returns a cache entry appropriate for the height, and whether a matching cache entry was found

func (*OrderCache) Heights 

func (oc *OrderCache) Heights() []int32

Heights returns a slice of cache heights, sorted from lowest to highest

func (*OrderCache) MaxHeight 

func (oc *OrderCache) MaxHeight() (int32, bool)

MaxHeight returns the height of the highest cache entry, and if there are entries

func (*OrderCache) Size 

func (oc *OrderCache) Size() int

Size returns the size of the orderCache

type OrderCacheEntry 

type OrderCacheEntry struct {
	Tips  []*Node
	Order []*Node
}

type OrderMap 

type OrderMap map[string]int

OrderMap maps a string to an int

func (OrderMap) Add 

func (om OrderMap) Add(keys ...string)

Add the keys to the OrderMap, starting from the maximum order value + 1

func (OrderMap) Clear 

func (om OrderMap) Clear()

Clear removes all keys from the OrderMap

func (OrderMap) Contains 

func (om OrderMap) Contains(key string) bool

Return true if the key exists in the OrderMap

func (OrderMap) Get 

func (om OrderMap) Get(key string) (int, bool)

Return the value of the key in the OrderMap

func (OrderMap) Order 

func (om OrderMap) Order() []string

Order returns the keys of the OrderMap from lowest-value to highest

func (OrderMap) Remove 

func (om OrderMap) Remove(key string)

Remove a key from the OrderMap

func (OrderMap) Set 

func (om OrderMap) Set(key string, value int)

Set the value of the key in the OrderMap

type OrderedStringSet 

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

func NewOrderedStringSet 

func NewOrderedStringSet(members ...string) *OrderedStringSet

NewOrderedStringSet returns a new empty ordered string set

func (*OrderedStringSet) Add 

func (oss *OrderedStringSet) Add(aString string)

Add adds a member to the set if doesn't already exist

func (*OrderedStringSet) Clone 

func (oss *OrderedStringSet) Clone() *OrderedStringSet

Clone returns a copy of the set

func (*OrderedStringSet) Contains 

func (oss *OrderedStringSet) Contains(aString string) bool

Contains returns true if the member is in the set

func (*OrderedStringSet) Difference 

func (oss *OrderedStringSet) Difference(setB *OrderedStringSet) *OrderedStringSet

Difference returns a set with the members of this set that aren't in setB

func (*OrderedStringSet) Elements 

func (oss *OrderedStringSet) Elements() []string

Elements returns members of the set in the order they were added

func (*OrderedStringSet) Intersection 

func (oss *OrderedStringSet) Intersection(setB *OrderedStringSet) *OrderedStringSet

Intersection returns a set with the members that exist in both this set and setB

func (*OrderedStringSet) Remove 

func (oss *OrderedStringSet) Remove(aString string)

Remove removes a member from the set

func (*OrderedStringSet) Size 

func (oss *OrderedStringSet) Size() int

Size returns the number of members in the set

func (*OrderedStringSet) Subset 

func (oss *OrderedStringSet) Subset(setB *OrderedStringSet) bool

Subset returns true if all set members in this set exist in setB (oss ⊆ setB)

func (*OrderedStringSet) Union 

func (oss *OrderedStringSet) Union(setB *OrderedStringSet) *OrderedStringSet

Union returns a set with members in this set or setB

type StringSet 

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

func DecodeStringSet 

func DecodeStringSet(blob []byte) (*StringSet, error)

This decodes a slice of bytes into a new StringSet instance.

This is meant to help load a persisted blueCache entry from disk, and is the opposite of the ss.Encode() method.

func NewStringSet 

func NewStringSet() *StringSet

NewStringSet returns a new StringSet

func (*StringSet) Add 

func (ss *StringSet) Add(aString string)

Add adds an element to the set

func (*StringSet) Contains 

func (ss *StringSet) Contains(aString string) bool

Contains returns true if the element is in the set

func (*StringSet) Difference 

func (ss *StringSet) Difference(other *StringSet) *StringSet

Difference returns set - other

func (*StringSet) Elements 

func (ss *StringSet) Elements() []string

Elements returns elements of set, sorted alphabetically

func (*StringSet) Encode 

func (ss *StringSet) Encode() ([]byte, error)

Encode returns bytes in gob format representing the set members. This is meant to help persist blueSet cache entries to disk.

We specify an Encode() method instead of running gob.NewEncoder().Encode() on the StringSet directly, because gob only encodes exported fields and we'd prefer to keep the set internals unexported.

For the reverse operation, use DecodeStringSet function to create a new StringSet from bytes.

func (*StringSet) Intersection 

func (ss *StringSet) Intersection(other *StringSet) *StringSet

Intersection returns set intersection other

func (*StringSet) Remove 

func (ss *StringSet) Remove(aString string)

Remove removes an element from the set

func (*StringSet) Size 

func (ss *StringSet) Size() int

Size returns the number of elements in the set

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.