Thinking with ink, spreadsheets for exploring scenarios, and a local-first key agreement protocol

Happy new year! In this newsletter we have three updates representing the full gamut of research happening at the lab: a project from the programmable ink track, a spreadsheet for exploring scenarios, and a new algorithm for local-first authorization.

First, a couple announcements:

The Automerge team will be hosting a community call on February 20. Come hear about progress on Automerge 3! A new multi-document sync system, end-to-end encryption, read-only document support, and massive improvements in memory usage and load/save performance.

Local-First Conf is coming back after a successful inaugural event last year. This year’s conference will be May 27-28 in Berlin; tickets are still available.

Pulling the thread on Inkling

There’s an early exploratory stage of every project where ideas are soft, where you’re guided by hunches and reckons. Maybe you have a concrete problem to solve and you’re not sure where to start. Or maybe you’re being pulled along by the desire for how things ought to be. This is a time of loose thinking, where the notes you write are scrawled and the drawings you make are sketchy.

On the ink track, we often find ourselves in this mode — we cherish it. After all, we’re trying to make tools that support this kind of thinking. In the fall of 2023, we spent a few months chasing down some rogue ideas about how this sort of tool ought to feel. We figured out how to build a constraint system powered by relaxation that performed well and wouldn’t blow up in our faces (like all the previous ones had). We figured out how to turn these constraints into tangible things you could touch and toggle and tug at with all your fingers. We revived some old ideas from Crosscut that felt amenable to relaxation-based computation. This all came together in a little prototype we called Inkling.

In the past few months, Inkling was demoed at the LIVE conference and then open-sourced. We’ve now put together a little page on our website — not a polished essay; something more exploratory — that pulls back the curtain on the Inkling project. Take a look.

Ambsheets: spreadsheets for exploring scenarios

From calculating monthly budgets to planning dream vacations, spreadsheets are our trusted companions as we navigate life’s complex decisions—a playground for thinking, where possibilities come to life through numbers.

Spreadsheets are particularly useful for thinking through financial models, budgets, or any situation that involves considering lots of possible scenarios. Instead of laboriously redoing a bunch of math, you can quickly ask “what if?” questions and see the effects.

But, as great as spreadsheets already are for this task, we think they could be even better. In our Ambsheets project, we are exploring a small extension to the spreadsheet: what if a single cell could hold multiple values at once?

Suppose you’re moving to a new city, and you want to figure out how much you can afford to spend on your car, apartment, and other essentials each month. You start out by making a spreadsheet summing up the various line items.

Now, you want to consider two scenarios for possible cars you might lease.How might you compare those scenarios? In traditional spreadsheets you might need to temporarily try entering different values, or restructure the sheet to accommodate the scenarios.

But in an ambsheet, you can simply enter two possible values for the price of the car:

The new value of B3, {500,1200}, means either 500 or 1200. We call this an amb value, and it represents one dimension in our possibility space. Amb values flow through the computation just like regular values and don’t require any special treatment in formulas. Cell B7, whose formula is SUM(B3:B5), now evaluates to either $3,318 or $4,018.

We think this simple idea could make spreadsheets more powerful for thinking through problems that involve multiple scenarios. To learn more about how amb values work and how they compare to existing spreadsheets, check out the lab note introducing the project: A spreadsheet for exploring scenarios

A new protocol for local-first key agreement

For many documents, you want to collaborate with a trusted group and no others. The default for Automerge today is if someone knows the URL, they can read and write to that document. We needed a way to encrypt documents for groups of collaborators that change over time, and importantly concurrently and without a single source of truth. How do we transparently keep a group’s read access up to date?

Of course, we only want folks with at least read access to be able to view our documents, but not sync servers and other infrastructure. This means we need a way to encrypt and decrypt our documents, including when they are shared via semi-trusted sync servers. This in turn requires a way for our dynamic group to agree on keys for encryption and decryption over time. If a key is compromised, we also want to limit the amount of past and future data an attacker can gain access to.

Forward Secrecy and Post-Compromise Security.png

Messaging Layer Security (MLS) has an answer for this called TreeKEM. But it’s not a fit for our local-first use case since it requires a central server to order operations and choose winners. There are concurrent solutions that are closer to our requirements, but still not the fit we were looking for.

Beekem Path.png

To adapt these techniques to our use case, we designed our own variant of TreeKEM called BeeKEM. It’s designed for local-first applications that require end-to-end encryption for groups on the order of thousands of members. Decryption in BeeKEM is very efficient in the case where one device updates at a time, and scales linearly with the number of concurrent updates at any given time. This means that the usual case scales logorithmically like TreeKEM, but gains the ability to merge concurrently updated trees unlike TreeKEM in exchange for some extra computation.

To read more details about the underlying protocol, read our lab note: Group Key Agreement with BeeKEM

What’s another open tab?