Intrinsic Limits of Nostr Filters

Nostr has an optimization problem. Events can exist anywhere on the network, and clients don't know when to stop looking.

This is the same problem the outbox model aims to solve, but you can do more than just route authors to specific relays. You can make certain judgements about filters themselves.

On Nostr, different filters have different fulfillment criteria.

For example, take the ids filter:

{ "ids": ["1", "2", "3"] }

Since events on Nostr are immutable, and IDs are a hash of the event's content, this filter is inherently fulfilled when we have gathered (and verified) all of the events with these IDs.

So, the above filter can be optimized by adding a limit equal to the number of IDs:

{ "ids": ["1", "2", "3"], "limit": 3 }

The limit is a hint that both clients and relays can use to know when to stop searching. For example, a client who sends this REQ to five relays can short-circuit as soon as the 3 events have been found from any relays, without having to wait for all five relays to EOSE.

Replaceable events by author

A less obvious optimization concerns filters for replaceable events by author, like this:

{ "kinds": [0], "authors": ["alex", "fiatjaf"] }

Kind 0 is a replaceable event, meaning relays should only serve one event of that kind for each author. As a result, the intrinsic limit of the filter is equal to the number of authors in the filter:

{ "kinds": [0], "authors": ["alex", "fiatjaf"], "limit": 2 }

When filtering by multiple replaceable kinds, the intrinsic limit is the number of authors multipied by the number of kinds:

{ "kinds": [0, 3], "authors": ["alex", "fiatjaf"], "limit": 4 }

Adding a single non-replaceable kind to filter makes us lose knowledge about its limit, making the filter potentially infinite again:

{ "kinds": [0, 3, 1], "authors": ["alex", "fiatjaf"] }

Empty filters

A final optimization allows clients to avoid sending filters to a relay at all, because the filter's intrinsic limit is 0. Those filters are listed below.

A filter with an empty kinds array:

{ "kinds": [] }

A filter with an empty authors array:

{ "authors": [] }

A filter with an empty ids array:

{ "ids": [] }

Any other filter that contains contains an empty kinds, authors or ids always has an instrinsic limit of 0:

{ "kinds": [], "authors": ["alex", "fiatjaf"] }

(It doesn't matter that you're searching for authors here. Since no kinds can match, the filter has an intrinsic limit of 0.)

All of these filters can be optimized by adding "limit": 0 to them.

Clients can optimize empty filters by not sending them to relays at all, and relays can optimize them by not querying their database. In both cases, an empty result set is returned.

nostr-tools

A function to calculate the intrinsic limit of a filter has been added to nostr-tools. It looks like this:

/** Calculate the intrinsic limit of a filter. This function may return `Infinity`. */
function getFilterLimit(filter: Filter): number {
  if (filter.ids && !filter.ids.length) return 0
  if (filter.kinds && !filter.kinds.length) return 0
  if (filter.authors && !filter.authors.length) return 0

  return Math.min(
    Math.max(0, filter.limit ?? Infinity),
    filter.ids?.length ?? Infinity,
    filter.authors?.length && filter.kinds?.every(kind => isReplaceableKind(kind))
      ? filter.authors.length * filter.kinds.length
      : Infinity,
  )
}

To use it, you can import it from nostr-tools:

import { getFilterLimit } from 'nostr-tools';

Then before you query a relay, you can modify the filters to add limits, and remove any empty filters:

/** Query a relay using Nostr filters. */
function query(filters: NostrFilter[]): Promise<NostrEvent[]> {
  filters = optimizeFilters(filters);
  return relay.query(filters); // call the relay
}

/** Add a `limit` to each filter if possible, and remove filters that can't produce any events. */
function optimizeFilters(filters: NostrFilter[]): NostrFilter[] {
  return filters.reduce<NostrFilter[]>((acc, filter) => {
    const limit = getFilterLimit(filter);
    if (limit > 0) {
      acc.push(limit === Infinity ? filter : { ...filter, limit });
    }
    return acc;
  }, []);
}

Combined with the Outbox Model

While ids filters are inherently fulfilled when the intrinsic limit is reached, replaceable events by authors can have multiple versions of the events on different relays. So adding a limit does not completely solve the problem on its own.

But combined with an Outbox approach, where specific relays are selected for specific authors, we should be able to stop querying when the intrinsic limit is reached, with reasonable confidence that we have the latest version (or one of the latest versions) of the events. This combined approach helps us resolve content faster and more accurately.