godave

README

 ____                      
|  _ \  __ ___   _____  
| | | |/ _` \ \ / / _ \ 
| |_| | (_| |\ V /  __/
|____/ \__,_| \_/ \___|
Anonymised continuous packet sharing peer-to-peer network protocol.

Copyright 2024 Joey Innes <joey@inneslabs.uk>

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.



Dave is an open protocol, designed to simply, efficiently, and continuously distribute a hash table in a byzantine environment.

Packets of data up to 1500 bytes in length are continuously pushed and pulled 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".

An amount of trust proportional to the mass of a dat is earned by sending a dat not already in the remote's hash table.
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 not gossiped or weighed into peer sharing.



0.      Constants

MTU         1500        Packet size, reasonable value to avoid packet fragmentation.
FILTERCAP   100000      Cuckoo filter capacity, using 16-bit fingerprints.
FANOUT      3           Max number of peers to send new dats to.
ROUNDS      9           Number of rounds to repeat sending to <=FANOUT peers. Balance speed with FANOUT.
NPEER       2           Max number of peers to share in PEER message. Prevents Eclipse attack.
PROBE       256         Inverse of probability that an untrusted peer will be randomly selected.
EPOCH       65537ns     Base minimum period of the operation cycle. The following are used to modulate operations.
DELAY       28657       Epochs until dats may be shared to a new peer, and until new peers are advertised. Prevents Sybil attack.
PING        8191        Epochs until silent peers are pinged.
DROP        524287      Epochs until silent peers are dropped from the peer table.
PRUNE       60649       Epochs between memory pruning.
SEED        3           Epochs between sending a random dat to one peer, excluding edges. 
EDGE        28657       Epochs between sending a random dat to one random edge.
PULL        32993       Epochs between sending a random get to one peer, excluding edges.

Note: known peer count is also used to modulate frequency of operations, ensuring that the protocol scales well.



1.      User-configurable Settings

Listen      UDP listen ip-port address.
Edges       A slice of edge node ip-port addresses.
DatCap      Number of dats to store. Adjust for available memory.
Log         A string channel for sending log messages.



2.      Operation Codes

GETPEER     Packet containing only the op-code. Remote should reply with NPEER random peer descriptors.
PEER        Packet containing NPEER peer descriptors.
DAT         Packet containing a value, time, and output of the cost function: work, salt.
GET         Packet containing the work hash, remote should reply with a message of op-code DAT, if available.



3.      Packet Message Format

A message is serialized into binary using protobuf. See protobuf spec dave.proto.

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 | <= 1388 when NPEER=2
TIME        Little-endian unix milliseconds.            0 | 8
SALT        Random bytes used to solve WORK.            0 | 32
WORK        BLAKE2B256(BLAKE2B256(VAL, TIME), SALT).    0 | 32



4.      Packet Filter

Dropping packets efficiently is critical for resilience to DoS attack. Cuckoo filters leverage cuckoo hashing to efficiently store fingerprints in a compact hash table, enabling constant-time insertions and lookups. This makes them well-suited for this application.

Packets that deviate from the protocol are detected & dropped without further processing.

The key inserted uniquely into the cuckoo filter:
        
FNV128A(REMOTE_IP, HASH4(REMOTE_PORT), OP)

Failing unique insertion, the packet is dropped.

The cuckoo filter is reset every epoch, therefore each op-code may be sent once per ip-port per epoch.

The number of ports allowed per ip address is limited using a 4-bit multiply-then-shift hash function.



5.      Peer Discovery & Liveness

The protocol ensures a cohesive network by combining liveness and peer discovery into a single pair of direct messages (GETPEER & PEER).

A node replies to a GETPEER message with a PEER message with up to NPEER peer descriptors. 



6.      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.



7.      Replacement by Mass 

Every PRUNE EPOCH, a user defined (DatCap) number of most massive dats are kept, and the remaining dropped.



8.      Random Push 

Every SEED/NPEER 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.

Note: In the current implementation, messages are sent from the main routine and I have not yet finished ensuring resistance to timing attack when sending new dats.



9.      Random Pull

Every PULL/NPEER EPOCH, a message is sent with op-code GET, and a randomly selected work hash already known. This further improves anonymity, at the cost of a small amount of wasted bandwidth.

Documentation

Index

• Constants
• func Btt(b []byte) time.Time
• func Check(val, tim, salt, work []byte) int
• func Mass(work []byte, t time.Time) float64
• func Ttb(t time.Time) []byte
• func Work(val, tim []byte, d int) (work, salt []byte)
• type Cfg
• type Dat
• type Dave
  • func NewDave(cfg *Cfg) (*Dave, error)
  • func (d *Dave) Get(work []byte, timeout time.Duration) <-chan *Dat
  • func (d *Dave) Set(dat Dat) <-chan struct{}

Constants

const (
	MTU       = 1500
	FILTERCAP = 100000
	FANOUT    = 2
	SETROUNDS = 9
	SETNPEER  = 64
	NPEER     = 3
	PROBE     = 16
	EPOCH     = 28657 * time.Nanosecond
	DELAY     = 5039
	PING      = 132049
	DROP      = 524287
	PRUNE     = 65537
	SEED      = 3
	PUSH      = 7
	EDGE      = 131071
	PULL      = 32993
)

Functions

func Btt

func Btt(b []byte) time.Time

func Check

func Check(val, tim, salt, work []byte) int

func Mass

func Mass(work []byte, t time.Time) float64

func Ttb

func Ttb(t time.Time) []byte

func Work

func Work(val, tim []byte, d int) (work, salt []byte)

Types

type Cfg

type Cfg struct {
	Listen *net.UDPAddr
	Edges  []netip.AddrPort
	DatCap uint
	Log    chan<- []byte
}

type Dat

type Dat struct {
	V, S, W []byte // Val, Salt, Work
	Ti      time.Time
}

type Dave

type Dave struct {
	Recv <-chan *dave.M
	// contains filtered or unexported fields
}

func NewDave

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

func (*Dave) Get

func (d *Dave) Get(work []byte, timeout time.Duration) <-chan *Dat

func (*Dave) Set

func (d *Dave) Set(dat Dat) <-chan struct{}