jbenet / jbenet/random-ideas

Compact proofs of retrievability in DSHTs

Open
#10 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
No language data
Stars
328
Forks
12
PR merge metrics
No merged PRs in 30d

Description

Use [compact proofs of retrievability](http://cseweb.ucsd.edu/~hovav/dist/verstore.pdf) to validate value advertisements in DSHTs
### Motivation

DSHTs (and other content delivery networks) are used to index mappings from a `key` to a set of nodes who can serve the `value`. Meaning, instead of storing `{ key : value }` pairs -- which can get very costly on the DSHT if `value` is large -- they store `{ key : [ nodes_who_have_value ] }`. The DSHT's client queries for a key, receives a set of nodes (id and network addresses) and can request the value from those nodes directly, usually over some other protocol (e.g. CFS, BitTorrent, HTTP).

Such setups have a significant vulnerability: malicious nodes may advertise possession of a particular `(key, value)` pair, be listed in the DSHT, and deny all requests from users. This is problematic because malicious nodes can cause honest nodes to direct other honest nodes to malicious nodes.

This attack is somewhat mitigated by: (a) long-running presence of honest nodes (kademlia), (b) costly sybill generation (s/kademlia), and (c) share ratio trackers (bittorrent).
### Setup

I propose including a compact proof of retrievability along with value possession advertisements. This would add slight overhead to every key stored in the DSTH, but would allow both DSHT relays and clients to validate a `(key, node, proof)` tuple before serving or using it.

The `proof` should be computed based on the individual node (e.g. taking the node_id as a seed into the challenge). And, ideally, new per re-advertisement (kademlia expires mappings, having nodes re-advertise to persist them).

Additionally, every would-be hoster should be able to respond to online PoR request. Meaning, add the following RPC:

```
valueProof(key) -> compact proof of retrievabiliy
```
#### Overhead

``` js
// from storing
{ key: [ (node_id, node_addr) ] }

// to storing
{ key: [ (node_id, node_addr, proof) ] }`
{ key + '_proof_pk': proof_pk }
```

A compact PoR proof is usually around 10-20 bytes. This cost is per-advertisement. For comparison, node ids are usually 20-32 bytes, addresses are 6-18 bytes ({udp,tcp}/IPv{4,6}). Also requires storing a per-key PoR public key (`proof_pk`), witch which challenges are computed/proofs verified.

Contributor guide

No contributing guide indexed for this repository

Research direction

The issue names no implementation files, tests, or existing entry points. Start by reading the linked compact-proof-of-retrievability paper and locating the DSHT advertisement and RPC paths; done would require a decided design for proof generation, storage, validation, re-advertisement, and the valueProof(key) response.

Written by the indexing model from the issue text.

Assessment

Domain
cryptography, distributed-systems, security
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.