libp2p / libp2p/specs

Introduce a 32-bytes key type without additional hashing to Kademlia DHT

Open
#421 10 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
No language data
Stars
1.8k
Forks
320
Avg merge
11d 15h
Merged PRs (30d)
1

Description

Moved from the rust implementation issue as requested by @mxinden.

Description

We need to use DHT to find closest peers with exact PeerId to the exact key value in our network. Currently, both rust and reference golang implementations seem to hash both PeerId and all the provided keys regardless of the initial format (using SHA256 hasher) to get 32-bytes hash before computing the XOR-distance. But what if we pre-hash our data and provide the 32-bytes as PeerId and 32-bytes key value as they are? Is it possible to have an additional way to create keys to calculate the XOR-distance without the additional hashing?

In our use case we attach semantics to both PeerId and look-up keys (related to local data ranges), but the second hashing destroys that. Currently, I use unsafe memory operations to bypass such a limitation but there should be a better way. Also, I don't see any limitations to this change in the original Kademlia paper.

Please, advise - is it possible to add exact keys(without the second hashing) to kademlia operations?

Motivation

This change will enable use-cases that depend on unmodified peer IDs or look-up keys.

Current Implementation

The current implementation hashes the provided keys even if the underlying data is 32-bytes array.

Are you planning to do it yourself in a pull request?

If the proposed enhancement looks reasonable we could implement it.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reviewing the linked rust implementation issue and the current Kademlia specification and implementations mentioned in this report. Determine whether 32-byte PeerIds and lookup keys can avoid additional hashing, including API and compatibility implications. Done means reaching a clear feasibility decision and documenting the required specification or implementation changes.

Written by the indexing model from the issue text.

Assessment

Domain
distributed-systems, networking
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.