Proof of Work

KayakNet uses Proof-of-Work (PoW) as an anti-Sybil mechanism to prevent attackers from creating many fake nodes.

What is Proof of Work?

PoW requires nodes to solve a computational puzzle before joining the network. This makes creating many identities expensive.

How It Works

Challenge-Response

New Node                    Existing Node
    │                             │
    │──────── Connect ───────────▶│
    │                             │
    │◀─────── Challenge ──────────│
    │   (random bytes, difficulty) │
    │                             │
    │   [Compute solution]        │
    │                             │
    │──────── Solution ──────────▶│
    │                             │
    │◀─────── Accepted ───────────│
    │   (join network)            │
    │                             │

The Puzzle

Find a nonce such that:

HASH(challenge || nonce) has D leading zero bits

Where:

• challenge = Random 32 bytes from server

• nonce = 64-bit number found by node

• D = Difficulty (number of zero bits required)

• HASH = BLAKE2b-256

Example

Challenge: 0x1234...abcd
Difficulty: 20 (20 leading zero bits)

Node tries:
  nonce=0: HASH = 0xf1a2... (0 zeros) ✗
  nonce=1: HASH = 0x8b3c... (0 zeros) ✗
  ...
  nonce=1485721: HASH = 0x00000f... (20 zeros) ✓

Solution found!

Configuration

Default Settings

Parameter	Value	Description
Difficulty	20	Leading zero bits
Timeout	60s	Max time to solve
Expiry	5min	Challenge validity

Adjusting Difficulty

# Lower difficulty (faster join, less protection)
./kayakd --pow-difficulty 16

# Higher difficulty (slower join, more protection)
./kayakd --pow-difficulty 24

Time to Solve

Difficulty	Average Time	Hardware
16	~100ms	Modern CPU
20	~500ms	Modern CPU
24	~10s	Modern CPU
28	~2min	Modern CPU

Security Properties

What PoW Prevents

1. Sybil Attacks - Creating many fake nodes is expensive

2. Spam - Sending many messages requires many nodes

3. Eclipse Attacks - Surrounding target needs many nodes

Cost Analysis

To create 1000 fake nodes:

• Difficulty 20: ~500 seconds of CPU time

• Difficulty 24: ~3 hours of CPU time

• Plus electricity cost

What PoW Doesn't Prevent

1. Well-funded attackers - Can afford computation

2. Botnet operators - Free computing power

3. ASIC attacks - Specialized hardware

Implementation Details

Hash Function

Using BLAKE2b for:

• Speed (faster than SHA-256)

• Security (256-bit output)

• ASIC resistance (memory-hard)

Nonce Search

func SolvePow(challenge []byte, difficulty int) uint64 {
    target := big.NewInt(1)
    target.Lsh(target, uint(256-difficulty))
    
    var nonce uint64
    for {
        data := append(challenge, uint64ToBytes(nonce)...)
        hash := blake2b.Sum256(data)
        
        if new(big.Int).SetBytes(hash[:]).Cmp(target) < 0 {
            return nonce
        }
        nonce++
    }
}

Verification

func VerifyPow(challenge []byte, nonce uint64, difficulty int) bool {
    data := append(challenge, uint64ToBytes(nonce)...)
    hash := blake2b.Sum256(data)
    
    // Check leading zeros
    leadingZeros := countLeadingZeros(hash[:])
    return leadingZeros >= difficulty
}

Challenge Management

Challenge Generation

func GenerateChallenge() []byte {
    challenge := make([]byte, 32)
    rand.Read(challenge)
    return challenge
}

Challenge Storage

Challenges are stored with:

• Timestamp (for expiry)

• Node public key (to prevent reuse)

• One-time use flag

Rate Limiting

Additional protection:

• Max 5 challenges per IP per minute

• Failed attempts increase cooldown

• IP banning for excessive failures

Alternatives Considered

Why Not Proof of Stake?

• Requires cryptocurrency

• Complexity for users

• Chicken-egg problem

Why Not CAPTCHA?

• Requires human interaction

• Not automatable

• Centralized verification

Why Not Trust on First Use?

• Initial join could be Sybil

• No cost to create nodes

• Easy to abuse

Future Improvements

Planned

1. Adaptive Difficulty - Adjust based on network size

2. Memory-Hard PoW - Better ASIC resistance

3. Stake + PoW - Hybrid approach

Research

• Proof of Space-Time

• VDF (Verifiable Delay Functions)

• Social trust graphs