godave

README

 ____                      
|  _ \  __ ___   _____  
| | | |/ _` \ \ / / _ \ 
| |_| | (_| |\ V /  __/
|____/ \__,_| \_/ \___|

Dave is a distributed key-value store. This is a thin layer over UDP, with many possible decentralised applications.

Packets up to 1424 bytes in length are continuously distributed at random. We call these packets "dats".

Storage is prioritised according to the age and difficulty of the proof-of-work. We call this "mass".

A remote peer earns trust when a new or updated dat is received. The amount of trust earned is equal to the mass of the dat. Trust is used to modify the probability of a peer being randomly selected for a small subset of operations, such as seeding. Trust values are currently not gossiped, as this creates a complex attack vector.



1.      Configurable Settings

UdpLstnAddr     *net.UDPAddr        Listening address:port
Edges           []netip.AddrPort    Bootstrap peers
Epoch           time.Duration       Base cycle period, lower runs faster, using more bandwidth
Prune           int                 Interval between refreshing dat & peer maps
ShardCap        int                 Shard capacity (number of dats per shard/difficulty level)
Log             chan<- []byte       Log message output
LogLvl          LogLvl              Log level
BackupFname     string              Dat table backup filename



2.      Message Operation Codes

GETPEER     Packet containing only the op-code. Remote should reply with NPEER random peer descriptors.
PEER        Packet containing NPEER peer descriptors.
PUT         Packet containing a key, value, time, proof-of-work, salt, signature, and public key.
GET         Packet containing the work hash, remote should reply with a message of op-code DAT, if available.



3.      Binary Serialisation

A message is serialized into binary using protobuf.

Transpiling Protobuf Spec for Go:
#!/bin/bash
protoc --go_out=. dave.proto

FIELD       DESCRIPTION                                 BYTE LENGTH

OP          Operation code.                             1
PEERS       List of peers.                              20*NPEER
VAL         The data.                                   0 | <= 1288
TIME        Little-endian unix milliseconds.            0 | 8
SALT        Random bytes used to solve WORK.            0 | 32
WORK        BLAKE2B256(SALT, BLAKE2B256(VAL, TIME)).    0 | 32
SIG         Ed25519 signature of work.                  0 | 64
PUBKEY      Ed25519 public key.                         0 | 32



4.      Peer Discovery & Liveness

The protocol ensures a cohesive network by combining liveness and peer discovery into a single pair of messages (GETPEER & PEER). A node may reply to a GETPEER message with a PEER message with up to NPEER peer descriptors.



5.      Mass

MASS = DIFFICULTY * (1 / AGE_MILLISECONDS)

Where DIFFICULTY is the number of leading zero bytes in WORK, amd AGE_MILLISECONDS is calculated from message TIME and current time.



6.      Replacement by Mass

Every PRUNE EPOCH, a user defined (ShardCap) number of most massive dats per shard are kept, and the remaining dropped. In this way, mass may be thought of as a property that decays over time.



7.      Sharding

The data structure used to store dats is a [][uint64]. The first dimension is called the shard. Sharding is done to make pruning the map more efficient, as shards can be processed concurrently. The keys are computed by hashing the key with xxHash. The shard is derived by right-shifting the key's hash 56 bits.



8.      Random Push 

Every EPOCH, each node sends one random dat to one random peer, excluding edges. This ensures reliable distribution and sender anonymitiy.

Propagating dats in this way ensures that an adversary is unable to create a timing attack to discern the source of a dat, even with a broad view of network traffic.



9.     Random Push of Recent Dat

Every EPOCH, each node sends one recent dat to one random peer. The dat is read from a ring buffer. The ring buffer is written to when a novel or updated dat is received. This ensures timely dissemination of data, even for large datasets.



10.     Edges

An edge is an ip:port address used to bootstrap to when starting. This entry will not be removed from the peer table, even if the remote becomes unreachable.

Documentation

Index

• Constants
• type Cfg
• type Dave
  • func NewDave(cfg *Cfg) (*Dave, error)
  • func (d *Dave) Kill() <-chan struct{}
  • func (d *Dave) Put(dat *store.Dat) <-chan struct{}
• type LogLevel

Constants

const (
	EPOCH          = 200 * time.Microsecond
	BUF_SIZE       = 1424             // Max packet size, 1500 MTU is typical, avoids packet fragmentation.
	FANOUT         = 5                // Number of peers randomly selected when selecting more than one.
	PROBE          = 8                // Inverse of probability that an untrusted peer is randomly selected.
	NPEER_LIMIT    = 2                // Maximum number of peer descriptors in a PEER message.
	MIN_WORK       = 16               // Minimum amount of acceptable work in number of leading zero bits.
	MAX_TRUST      = 25               // Maximum trust score, ensuring fair trust distribution from feedback.
	PING           = 8 * time.Second  // Time until peers are pinged with a GETPEER message.
	DROP           = 16 * time.Second // Time until silent peers are dropped from the peer table.
	SHARE_DELAY    = 20 * time.Second // Time until new peers are shared. Must be greater than DROP.
	PRUNE          = 10 * time.Second // Period between pruning dats & peers.
	RINGSIZE       = 1000             // Number of dats to store in ring buffer.
	LOGLEVEL_ERROR = LogLevel(0)      // Base log level, for errors & status.
	LOGLEVEL_DEBUG = LogLevel(1)      // Debugging log level.
)

Types

type Cfg

type Cfg struct {
	UdpListenAddr *net.UDPAddr
	Edges         []netip.AddrPort // Bootstrap peers
	ShardCap      int
	BackupFname   string
	Logger        *logger.Logger
}

type Dave

type Dave struct {
	Store *store.Store
	Peers *peer.Store
	// contains filtered or unexported fields
}

func NewDave

func NewDave(cfg *Cfg) (*Dave, error)

func (*Dave) Kill

func (d *Dave) Kill() <-chan struct{}

func (*Dave) Put

func (d *Dave) Put(dat *store.Dat) <-chan struct{}

type LogLevel

type LogLevel int