[wip] feat: willow implementation

[Frando]

Description

Work in progress! Implementation of https://willowprotocol.org/ for iroh

Protocol

The protocol module contains the data structures and basic interactions as defined by the Willow specs. It is IO-less and not generic, all types are concrete.

• [x] Willow data model proto::willow
  • [x] Use willow-rs (see #2616 )
• Meadowcap proto::meadowcap
  • [x] Use willow-rs (see #2616 )
• [x] Groupings proto::groupings
  • [x] Use willow-rs (see #2616 )
• Willow Geneal Sync Protocol (WGSP) proto::sync
  • [x] Most message type structs written down
  • [x] Private Area Intersection
  • [ ] Cryptographic fingerprint (uses only XOR atm)
  • [ ] Protocol-compliant encoding

Session

The session module contains the implementation of the WGPS protocol session.

• [x] Session setup
• [x] Private area intersection
• [x] Set reconciliation
• [ ] Resource control
  • [x] Binding resources
  • [ ] Freeing resources
  • [x] Issue initial guarantees
  • [x] Respect issued guarantees
  • [ ] Issue new guarantees
• [x] Live data mode between two peers
  • [x] Subscribe to new inserts and send to active sessions
  • [x] Only send entries for matcing shared areas of interest
• [ ] Verified streaming for payloads with bao outboards embedded
• [ ] Payload requests
• [ ] ~~Live data mode in a swarm setting~~

Net

The net module opens sessions over iroh-net QUIC connections.

• [x] Commitment exchange
• [x] Separate channels for each logical channel
• [x] Basic session lifecycle (allow to close sessions)
• [x] Properly terminate connections gracefully (fixed by #2599)
• [x] Properly deal with simultaenous connections by only using one of them deterministicaly (fixed by #2599)
• [x] Do not drop intents if the session is about to be closed when submitting a new intent (fixed by #2599)

Store

The store module contains backing stores for entries and keys

• Store traits and generic functionality
  • [x] Entry store trait
  • [x] Key store trait
  • [x] Use iroh-blobs for payload storage
  • [ ] Store capabilities by hash and do reference counting
  • [ ] Expose hook to prevent GC of payloads and/or do reference counting for payloads
• [x] PoC memory store
• [ ] move store to own thread & sessions to local pools
• [ ] redb store
  • [ ] port @rklaehn's redb PoC
  • [ ] figure out if the traits need to change for our delayed commit strategy
  • [ ] add commit to the store trait
• [ ] subscriptions
  • [ ] reliable/persistent subscriptions

Engine

• [x] PeerManager (1 session peer peer only)
• [x] Intents
  • [ ] changing between ReconcileOnce and Live modes

Other

• [ ] How can builder APIs be done nicely over FFI

Breaking Changes

Once we integrate, this will be a very much breaking changes for everything around docs: This will break not only APIs, but also the protocol and the storage. We cannot offer automatic migration even, because signatures change. How exactly we deal with this situation is tbd. Likely we will offer an out-of-tree tool to migrate data from the old iroh-docs to the new willow iroh-docs.

Notes & open questions

Change checklist

• [ ] Self-review.
• [ ] Documentation updates if relevant.
• [ ] Tests if relevant.
• [ ] All breaking changes documented.

[github-actions[bot]]

Documentation for this PR has been generated and is available at: https://n0-computer.github.io/iroh/pr/2231/docs/iroh/

Last updated: 2024-09-09T10:39:31Z

[Frando]

I merged #2616 into this branch! iroh-willow is now based on willow-rs.

Will copy-paste the PR description of #2616 because it contains context and notes/TODOs that shouldn't get lost:

Description

Adopts willow-rs in iroh-willow:

• Use the types from willow-data-model. Our implementations are replaced by type aliases onto the willow-data-model types with the generics filled in.
• Use meadowcap. Our implementations are replaced by type aliases onto the meadowcap types with the generics filled in.

The PR is large and not well readable because I adapted the module structure to be closer to willow-rs as well in the same go (a bit non-ideal, but I was already having to go over most imports once, so did it in one go). I will merge this as soon as all tests are green, and then refine in the main willow PR (#2231).

Breaking Changes

Many public types from iroh-willow are now type aliases instead of structs.

Notes & open questions

Based on #2231 and currently uses willow-rs git dependency with two PRs merged in: https://github.com/earthstar-project/willow-rs/pull/45 and https://github.com/earthstar-project/willow-rs/pull/46

Generics

Type aliases work well in many regards, but they don't really hide all the generics well, they appear in compiler error messages and rust-analyzer doc hovers etc and make all that quite unreadable. We talked about this a bit, and will have to improve the story at least for the public client API, and potentially also for ourselves working in the internals.

• We can newtype wrap everything, then the generics are gone. But the cost is that we'd have to reimplement and forward all methods.
• Maybe there's ways to reduce the generics in iroh-willow itself, by using a zerosized struct that implements a trait with associated types instead.

Encodings

This PR does not yet include spec-compliant encodings for WGPS messages, it still uses postcard with serde as an interim solution. To make this work with the willow-rs types which don't implement serde, I added wrapper types that takes the willow-encoding and maps them into serde. The proper encodings will still have to be written, same for the integration of ufotofu encoding with our in-memory pipe.

Key types

We currently have UserId and UserPublicKey types (and same for namespace): Id is a wrapper around [u8; 32], wheres PublicKey is the ed25519_dalek::VerifyingKey. Converting from Id to PublicKey is fallible (because not all 32 bytes are valid ed pubkeys) and non-free (it involves numeric operations). Before this PR, we used PublicKey in meadowcap and Id in data-model. This is no longer possible because the generics have to map on the same time. We now use Id everywhere and convert to PublicKey on demand.

This is non-ideal because the conversion will happen far more often than needed. However willow currently assumes a non-fallible successor() function when a UserId (UserPublicKey) is used as a subspace id.

What we likely want is an in-memory LRU cache for the converted versions. Or a type where the numeric pubkey is optional, but that would either need mutable access to the key for operations, or interior mutability.