Okay, so hear me out. I was listening to Kate Bush's Deeper Understanding while out on a walk. This is a song about someone who develops an unhealthy relationship with their computer via a piece of software which is able to talk back to them. The original version of this song was released in 1989.

The chat interface has now been around for decades. People have built new friendships, fallen in love, and built entire communities through speech bubbles filled with text.

And without that priming, without the education that on the other side of that speech bubble there is a living, breathing person, would any normal person have given LLMs a second look? Or would they have seen how absurd the premise is immediately?

This is but one of the many half baked thoughts I bothered others with after attending BYOW - A Webcraft Meetup. In my corner of the world it feels like I know of a lot of interesting, caring, talented people who for whatever reason never seem to get together. But we're all atomised away from each other. Why is that? The country I live in is dense and small. Is this the dark side of the bicycle, that anything further than 15 minutes away is just too far? (please keep tuning in for my broad and sweeping societal theories).

But back to the BYOW meetup. It was interesting that a lot of people were building shrines. Eulogies, making wishes, shrines to fandoms. There was always this big question of how the author went about the upkeep of the site, how pleasant or unpleasant that was and how they kept up with it anyway.

Speaking of which, while talking about this very website, I admitted that I still hadn't gotten today's update ready and was starting to feel nervous about it. And almost immediately help was offered. I've included a few contributions to this week's update from lovely people I met last night.

~sammy

This week I want to share some thoughts not about Willow but about the Sufficiently Good Media Formats, specifically about the problem of enabling efficient seeking to arbitrary timestamps in an audio or video file. As a bare minimum, you want to wrap the encoded samples in segments, say, of one second each. But how can we enable efficient access to specific segments?

The most straightforward way is to have a table of contents at the start of the file, specifying the location (i.e., the starting byte index) of all segments in sequence. The problem: with this scheme, you cannot emit a file in a single pass over the samples to encode. You have to first encode all samples and track the segment starts in memory, and then jump back to the space for the table of contents and fill it in. This requires O(n) memory, not good. You could also jump back and forth between appending a new segment and seeking to the table of content and adding a single item, but that's pretty inefficient (even when applying the obvious optimisation of batching things). And finally, the whole scheme precludes schemes that simply emit the bytes of the file as a single stream with no backwards-seeking (unless you do two separate passes, one for computing table of contents locations and one for actually appending samples).

A simple alternative would be to have the table of contents at the end of the file instead of the start. This makes it possible to emit everything in a single pass without seeking, but it also necessitates O(n) memory usage. So here are two alternative schemes, which I haven’t seen anywhere in the wild (though, admittedly, I haven’t thoroughly searched either — I’ve mostly had some fun trying to solve this from first principles). Both schemes enable finding arbitrary segments in logarithmic time, and allow for single-pass, O(1)-memory encoding.

The first scheme works by building a backwards skiplist over all segments: each segment specifies the location of the predecessor segment, and the location of another, possibly much older segment: the n-th segment specifies the location of the n-p-th segment, where p is the largest power of two that divides n and is strictly less than n. Finally, the very end of the file specifies the index of the start of the final segment.

This scheme lets you seek to any segment in logarithmic time: you seek to the end, obtain the start of the final segment, seek to there. Then you check whether the non-predecessor link overshoots your target segment. If it does, go to the predecessor segment, otherwise follow the non-predecessor link. Repeat until you find the target.

Producing these files requires O(log(n)) memory: you need to keep a table of the addresses of all segments whose index, in binary notation, consists of a number of ones followed by a number of zeros. Updating that table takes only O(1) amortised time, so the encoding process overall takes only O(n) time, the same as without any segment seeking scheme.

The other scheme is based on self-synchronising codes. First, you make sure that the contents of segments do not contain zero bytes (there are efficient techniques for that). Then, you prefix every segment with a zero byte, followed by its index.

Seeking works by guessing a likely location for the segment you are seeking for, and then scanning forward to the next zero byte and looking up the index of that segment. If you guessed wrong, you take a more refined guess and repeat. This guessing procedure can be simple binary search, it can try to estimate how long most segments are to compute a more likely location, or it can be a hybrid (that would/should combine the worst-case bounds of binary search with the far better average-case behaviour of computing indexes based on average segment length).

In the worst case, this scheme incurs a lot of overhead during seeking, spending time sequentially looking for the next zero byte. But on the other hand, non-adversarial files probably allow for faster seeking than the necessarily logarithmic approach of the skip-list scheme. And emitting these files adds no asymptotic overhead to the encoding process at all, which is quite neat.

I don’t yet know what to go with for the Sufficiently Good Media Formats, and I certainly will not make that decision before properly reviewing the state of the art. But instinctively, I do find the scheme based on self-synchronising codes very appealing...

~Aljoscha

This week I've been working on things that aren't quite ready to be picked apart by the ravenous audience of worm-blossom.org.

The new worm-blossom 'mega bar' is now in operation across the many worm-blossom franchises. We deployed these two weeks ago, but the styling for each site wasn't completely right yet. Now you can skip across the worm-blossom-verse with ease.

I began working on new tutorials for Willow, now that the Store and Willow Drop Format APIs have been published. Writing a tutorial has the unfortunate outcome of making you see the things you've designed from a beginner's viewpoint. New areas for improvement have been identified.

Meanwhile I have been held in the grip of the phrase “nothing special”. When is “nothing special”... well, special? It's when you see how something has been assembled, and that all the parts are in fact quite boring, and that you too could make nothing special yourself if you wanted to.

~sammy

I took all my pondering over the WTP design and cast it into a single specification collection of Rust types for the different message types. This is a fairly dense artefact compared to an actual spec writeup, but I hope I can gather some feedback (from Heni in particular :3) nevertheless.

Aside from a continuous stream of Willow test vector improvements, that’s mostly it. I really hope that the WTP design will stay mostly stable; while it is fun to work on these designs it is also somewhat stressful, and I look forward to fleshing things out without reexamining the foundations all the time.

I will be offline for ten days of vacation now (again, what a decadent summer), for yet another choir trip. I prepared background music and an editorial for next week already, but I won’t be as responsive on the Discord server during that time. Sorry @Freckles =D

~Aljoscha

Reader, it wouldn't be unreasonable to look at last weeks plans of ‘support peers’ and think: that’s just another name for a server. You couldn’t find enough peers, so you had to turn to an always-online machine somewhere. Cop-out.

Well: nuh-uh. In this editorial I will argue that we are doing something meaningfully different from traditional servers.

Servers are (hopefully) characterised by their high uptime, but they are not fungible. If a Mastodon instance’s server is down, we can’t point our mobile client at another server and expect to have the same functionality available to us.

Peers in a p2p network are fungible. We can connect to whatever we can and exchange as much data as possible. But a peer running on a mobile device has only very intermittent uptime. It may only be available when an app is in the foreground, which is not very often at all.

A non-fungible machine with low uptime is just… a crappy server, so that’s not a very interesting combination. But a fungible machine with high-er uptime feels like it’s relatively unexplored.

What kinds of infrastructure are possible when high-uptime peers are fungible? Sure, you get a ‘swarm’ of high-uptime peers that are more resilient to outages, but… how about something more intentional, like a relay of peers turning on and off as solar power becomes available to them?

Servers are also usually far more capable machines than the devices they serve: more processing power, more storage, more authority. But we’d expressly like to enable peers which can provide high uptime but which have other constraints such as low storage or processing power. If we can prioritise the storage of recent data, operators of constrained devices like this are still able to meaningfully pitch in.

And those high uptime peers can even sync with each other! I think it’s meaningfully different from ordinary servers, and I hope we can use this as a tool to change how we think about supporting infrastructure.

~sammy

A good chunk of my worm-blossom time this week went into the Willow test vector repository. Before this week, that repo held inputs and expected outputs for a few Willow encodings, some of them outdated and thus actively misleading. Now everything is up-to-date again. Additionally, I started adding test data for more than just encodings: there is now also a directory for data-model related functions, such as determining whether an entry should overwrite another, or computing the lexicographic successor of a path (a task less trivial than it initially sounds).

There has been a flurry of other tasks on my mind, to the point where I started to feel a bit overwhelmed. Writing them all down is probably going to help, so here we go:

• WTP design:
  • handling proofs of knowing the secret for a write capability,
  • unifying the different messages that all request entries as much as possible,
  • determining how/whether peers should pre-announce which features they implement,
  • mapping out which messages can be sent as responses to which other messages,
• the ed25519 ambiguity issue of willow25
• updating to the new major version of the ed25519 implementation we use in our Rust work,
• mildly panicking about quantum computers breaking ed25519 in the not-entirely-unreasonably-far future,
• planning Rust traits for Willow stores that allow aggregating metadata (for RBSR) and for splitting 3d-ranges into smaller ranges containing roughly equally many entries (again for RBSR),
• more media file format details (in particular, I’m still exploring different mechanisms for enabling efficient seeking in audio/video files),
• the Macromania website,
• some macromania macros I should really write sooner rather than later (macros for integrating and possibly transforming assets for websites, macros for referencing these assets),
• a data base file format for 3d Willow entry storage,
• the prerequisite 3d-zip-tree work I need for that,
• providing recommended ways of encrypting Willow data (and metadata) at rest as part of Willow25 (we already have generic designs, but no specific instantiation for Willow25 yet),
• API and implementation designs for this encryption work in Rust,
• figuring out how to make encrypted sneakerwebsites a thing (in a backwards-compatible way, ideally),
• work on my writeup of p2p design principles/lessons,
• plans for the first birthday of worm-blossom.org,
• idle thoughts around more intentional background music tracks in the next year,
• adding more Willow (and Bab) test vectors,
• planning some test vector improvements,
• sketching a design for a Willow-powered alternative to Email (that I will probably write more about in the future), and
• a whole bunch of encryption issues pertaining to that Email alternative.
• Bonus stuff:
  • sketching a type system for an object-oriented programming language where there are no concrete object types but only interface constraints,
  • sketching an engine for web-technology-powered text-based single-player RPGs, with beepbox integration for (reactive) soundtracks,
  • reflecting on Hannah Arendt’s On Revolution and how her thoughts on the origins and nature relate to technical protocol.

Jup, okay, in retrospect I can tell why I was feeling a bit stressed out this week.

~Aljoscha

Back in March, Aljoscha and myself huddled at a hotel bar with adz, glyph, and sam from p2panda. We’d decided we were going to draft and submit a new grant proposal hours before said grant’s deadline. Collaboration between our projects had always seemed like a bit of a utopian idea, but we finally had convergent goals.

“Project title?” said Aljoscha, hovering his mouse over the empty form input.
“Hmmm… put Pillow” said adz. “We can always change it later”.

Pillow is a new collaboration between p2panda and worm-blossom. It’s a way for p2panda apps to quickly store and retrieve data from highly available peers. These highly available peers don’t know anything about p2panda data, but they do have decentralised, capability-powered permissions, can happily evict stale data, and can efficiently sync with each other. That’s because they’re Willow peers!

In this grant we’ll be implementing WTP, meaning that at long last Willow peers will be able to sync over the internet via range-based set reconciliation. We’ll also be developing WTP-powered servers with web interfaces for configuring capabilities, data eviction, and viewing storage usage.

The first users of these Willow ‘support peers’ will be p2panda apps, which will be able to interface with them via Pillow. The idea is that the Willow-powered peers don’t need to do all the stuff a p2panda peer usually does, and will be freed up to act as oblivious (but permissioned) storage.

Not only will we be working with the pandas on this project, but we’ll also be bringing a new member into worm-blossom (more on that later).

In the meantime, I’m getting back on my feet and using those feet to make silly announcement videos.

~sammy

I just came home from a productive walk with some realisations about message encodings for the WTP. These center around statefulness of peers, optimised relative encodings, and request cancellation.

The most basic requests are purely stateless: a peer issues the request, and then simply discards all state that pertains to it. Consequently, the (encoding of the) response must be fully self-contained. First realisation: such responses are indistinguishable from eagerly pushed messages — a peer might as well send such responses without ever having received a corresponding request, and the other peer would be unable to tell. I spent the past two weeks trying to argue against eagerly pushed messages, and now I feel a bit silly.

The other option are stateful requests: a peer issues a request, assigns it a request id, and keeps some state associated with the request. The response contains the request id, and can refer to the state for more efficient encodings. For example, when requesting a Willow entry in a specific namespace, the response encoding can omit that namespace. Second realisation: protocols can easily support both modes of operation. Requests can simply indicate whether responses should be standalone (allowing for stateless requesters) or whether they should be optimised (forcing the requester to keep state).

Moving on to message cancellation: as far I can tell, cancellation (by the requester) serves two important purposes. The obvious one is that it can prevent large responses from being sent only to be discarded upon arrival. The second, less obvious purpose is that cancellation allows the requester to free up any state it had to keep around to be able to decode and process an eventual response. This leads to the rather obvious third realisation: there is no sensible notion of cancellation for stateless requests — if a peer does not even record that it sent a request, it cannot later cancel it. And there is no state for it to free up anyway (though preventing pointless responses would still be desirable, of course).

For stateful requests, there is a more interesting dynamic going on. When using optimised response encodings that rely on state kept by the requester, the requestor cannot immediately clean up its state after sending a cancellation. Concurrently to sending the cancellation, the other peer might have sent a response, after all. And decoding that response requires the old state. Hence, realisation number four: stateful requests imply that cancellations must be confirmed by the other peer before state can be cleared.

This, frankly, is not great. Thankfully, there is a way by which to combine efficient encodings of responses to stateful requests with immediate, non-interactive cancellation: prefixing responses with their length allows the receiver to discard the response from the communication channel and then keep decoding the next messages even after having cleaned up the state that would have been required to properly parse the response. This was realisation number five.

I'm happy with this outcome: letting peers indicate whether their requests are stateful or stateless allows for incremental implementation of a protocol, by starting with the easier-to-implement stateless variants only. And stateful messages with their more efficient responses still do not force requesters to keep around state until their peer cooperates. This is a lot better than what the current Willow Confidential Sync draft offers (mandatory stateful encodings, mandatory cooperative cancellation).

What remains is a final meta realisation: it feels odd that I needed to come up with these approaches myself, after years of being active in the space. We really need better teaching material. I know I'm slightly peculiar in my emphasis on (bounded) state management in communication protocols, and I know that using state for optimising message encodings is a topic that will be skipped by anyone who wants to simply use a serialisation library and not think about encodings at all. But still, everything I've been writing about today is fundamental to how communication works. Guess I need to add yet another article-to-write to my todo list =S

~Aljoscha

It is now a few hours after writing my first editorial, and the consequences of these realisations for the WTP are starting to sink in. The initial WTP draft had both RequestGet messages for requesting individual entries (and the corresponding ResponseGet messages) and RequestPut messages for eagerly pushing an entry to the other peer. Here is the key insight: ResponseGet and RequestPut carry the same information. The only difference is that RequestPut uses an absolute encoding, whereas ResponseGet uses an encoding relative to the corresponding RequestGet message. In a design where the same messages can be encoded either absolutely or relatively, these two message types can merge into a single type.

And this can be an overarching design theme for the WTP. Instead of thinking of messages in terms of requests and responses, as many messages as possible should admit both absolute and relative encodings. Specifically this means:

• Asking for an entry (and/or its payload): absolute only.
• Sending an entry: absolute, or relative to anything that asks for one or more entries.
• Sending a (part of a) payload: absolute, or relative to a message asking for a payload.
• Asking for all entries in an area or range (and optionally supplying metadata — fingerprint, entry count, and/or total payload lengths — about one's own entries in that area or range): absolute, or relative to a message asking for a super-area or super-range.
• Cancelling a “request”: relative to anything asking for one or more entries.

I want to note that where I write “absolute” encoding, that is only meant in the sense that the encoding is not relative to a dynamically indicated message. To make the encodings as efficient as possible, the spec might still use relative encodings even for standalone messages. To give an example: peers could be mandated to remember the last entry they sent. Each send-entry message could then be encoded relative to the previously-sent entry, allowing, for example, to indicate with a single bit that the current entry has the same namespace id as the previous one. The crucial point is that such encodings require only a constant amount of space, irrespective of the behaviour at runtime, whereas encodings relative to any previous message would require tracking state proportional to the number of previous messages. Another application of this technique will allow transmitting payload slices while keeping the corresponding entry and/or slice start purely implicit.

Aside from a certain elegance, breaking up the request-response dichotomy has a tangible benefit: this design allows peers to express and run both symmetric and asymmetric range-based set reconciliation. The old design was restricted to client-driven asymmetric reconciliation only, exactly because requests for ranges could not be sent in response to other such requests.

THIS IS SHAPING UP NICELY, I AM QUITE EXCITED!

~Aljoscha

This week I have a gazillion things to share; I blame the fact that I took a proper vacation for the first time in ages.

After planning for a long time, we stripped out all generics from our Rust Willow implementation. This makes things, well, less generic, but also provides a tangible and honestly rather necessary reduction in complexity. The pull request ends up reducing our lines-of-code by about 15000. We have published the new code as willow25 0.7.0, and we have deprecated the old, generic willow_data_model and meadowcap crates.

On the WTP side of things, I realised that there is little reason to keep the protocol asymmetric. If both peers are allowed to request entries, that might even be another way of removing RequestPut messages from the protocol. But this decision is sufficiently fundamental that I have postponed working on the WTP until Sammy has enough time on her hands again to have her say as well.

So instead I turned back to my media file format designs. I have now specified exactly how to encode samples. All that is left now are the boring details of format-specific metadata. With the exception of settling on the sample predictor for audio, all the hard work is now done.

And as part of that work, I nerd-sniped myself into thinking about the role of magic numbers in file systems. So I wrote down a half-specification half-rant document that overthinks the topic quite a bit. Turns out I harbour strong feelings about magic numbers (who doesn't, right? Right?), to the point where Emmy and Miaourt had to make me tone down the polemics. Thank you folks =S

Speaking of overthinking things in a good way, I'd like to draw attention to this sneakerweb PR about presenting a sneakerweb collection in a random order. Somehow that premise escalated into a discussion of social dynamics, non-uniform sampling, and time complexity of various algorithm choices. In a good way.

There's been some other progress on the sneakerweb as well, with Emmy spearheading the modestly-named WIP: fix-all-the-things pull request. At the end of that PR will be the release of version 1.2.0, bringing some new features and making the sneakerweb work in Chrome and Edge. Thank you, Emmy (and sorry that I have somewhat dropped out of the loop regarding the state of the sneakerweb implementation)!

~Aljoscha

This week I’ve been with the kids. It’s summer holidays and a lot of their friends are away, so we’ve spent pretty much the whole week together. I didn’t even try to work, it wouldn’t have been any good.

The kids have a vague notion of what I do. It involves computers, they know that much. My older kid knows it involves ‘networks’. Mostly they know that I have a blog with fun music by Aljoscha, and comics which they like (their favourite is this one), and that my work means I bring home lots of stickers.

Several years ago I was a consultant working with commercial clients. After my son was born and started to become a little more conscious of the world, I started to get this sense of “I want my kid to think I’m cool” (I know, I’m doomed to failure, but I’m going to try). And I just couldn’t imagine my kids thinking it was cool that I made React apps for shoe stores (which back then was really pretty lucrative).

So I gave up doing the safe thing.

~sammy

The day before I headed to my vacation, I had an idea for a blog post that I started feverishly drafting. And now that I returned, the first thing I did was to complete it. It starts from a simple idea: what happens if you structure a programming language design around the broadcasting of information rather than calling methods on specific objects? This starting point has some interesting implications, from abandoning the notion of object identity, to spatial computing based on active broadcast rather than passive sensing. Read the full post on Broadcast-Based Programming here =).

I am slowly returning to more practical worm-blossom concerns now, in particular I want to start fleshing out the WTP into a full specification.

The WTP has three types of requests: RequestGet (analogous to HTTP GET), RequestGetMany (for requesting areas or 3d ranges), and RequestPut (analogoues to HTTP PUT). For a while, I was seriously considering to remove RequestPut, turning the WTP into a purely pull-based, read-only protocol. But while this has a certain elegance, it would force application developers to use a separate protocol (such as dripdrop) to write any (new) entries to a peer. In that world, you would either need to multiplex connections or to open multiple physical connections. And that would add complexity that outweighs the minimalism and orthogonality we would have achieved by trimming down the WTP.

With this decision made, here are the next steps toward a completed WTP:

• Rework the start-of-connection message flow. The current definitions assume that the very first thing every client has to do is to prove that they have the secret for the public key they will use in their read capabilities. But RequestPut messages do not involve read capabilities at all, and I can easily imagine write-only clients that never work with any read capabilities. And such clients shouldn’t be forced to do useless signature computations, nor should they have to wait for a server challenge before they can start issuing requests.
• Remove non-Bab usage. Partial verification is such a good feature that I do not want to encourage implementations that skip it. So no raw indexing into payloads by byte offset without Bab verification metadata.
• Define the responses to GetMany requests.
• Define encodings for everything. Surely this will be quick.
• Sketch Rust types for all request and response types. Use this to guide the way the spec defines things; currently the spec describes many optional fields together with rules for when they have to be present based on the values of other fields, and this would be much nicer to define in terms of enums.
• Pester Sammy to design a logotype.

And with that, we would have a completely specified and half-implemented WTP already. And we are already brainstorming applications we would like to implement that would be enabled by this.

~Aljoscha

Multiple people* have now confronted us about how confusing it is to navigate the family of worm-blossom websites. That there should be some kind of unified navigation between the worm-blossom, Willow, Bab, and sneakerweb sites. And being between projects, that seems like the perfect thing to do.

We'll see when it gets done. It's summer holidays and I'm with the kids next week. Many things simmering but nothing to report.

* Christine, and Aljoscha's dad

~sammy

I am still on vacation. But you know how zoologists determine whether an animal is kept in a way appropriate for its species by observing whether it retreats into passivity or whether it is active, exploratory, and playful? By that same metric, I am having a great vacation.

~Aljoscha

I'm not on vacation. But I'm not really on top of it yet. So this week, part eight of “Why is it called worm-blossom?”.

~sammy

Readers, this week Aljoscha and I are on holiday. So I've done what I can this week to evoke the feeling of my holiday, a summer break in a family home full of old paintings and photographs of times long past. Aljoscha's buggered off for this week's update, and good for him.

Last week I promised a truckload of impressions from Dweb camp, but to be honest most of those remaining reflections are about presentations I saw and the speakers I met, and I would like to share accompanying recordings of them, and I'm waiting for those to become available.

Instead I've been enjoying the intellectual slack you get from being on holiday. First there is just collapse, catching of breath, recuperation. But then after a few days you pick up the thread again, start laying out little patterns on the floor, experimenting with interesting knots. And before you know it, you're 'just doing a little bit of research'.

The next phase of Willow will be about exploring what sits just above the extreme latency of the Willow Drop Format and sneakerweb. So: networked communication. My plan is to use the sneakerweb itself to find the limits of comfort, the point where you say "this is fun, but I really don't want to do this with USB keys anymore". I think it will be really nice to use our own tools to do research in this way (I think this is what people call “drinking your own champagne”).

~sammy