subscribe with prefixed filter ids (nip-01)

[offbyn]

I'd like to subscribe to event ids starting with "0" as described in nip-01, but it seems no relays support that yet. Reason: there are some clients that support nip-13 POW and add nonce tag, but filtering by nonce on the client still means that all events are subscribed too which results in lots of bandwidth usage. Therefore I'd like to only subscribe to events starting with '0' or '00'

"ids": <a list of event ids or prefixes>
The ids and authors lists contain lowercase hexadecimal strings, which may either be an exact 64-character match, or a prefix of the event value. A prefix match is when the filter string is an exact string prefix of the event value. The use of prefixes allows for more compact filters where a large number of values are queried, and can provide some privacy for clients that may not want to disclose the exact authors or events they are searching for.

https://github.com/nostr-protocol/nips/blob/master/01.md

example: filter: { ids: ['0'] }

[offbyn]

created this issue also for rust relay scsibug/nostr-rs-relay#104

[hoytech]

This should work for id 00 but not for 0. The problem with 0 is that internally strfry (and I believe nostr-rs-relay too) do not store in the hexadecimal encoding, but instead of decoded bytes (which take up half the space).

Converting hex to bytes is ambiguous when the quantity of hex characters are odd. a could decode to either 0a (what most hex decoders would do) or a0 (which is likely what is intended here). However, note that the "length" of the prefix would need to be half a byte here, which strfry doesn't support. IMO supporting odd-length hexadecimal filters is not worth the trouble.

[ok300]

a could decode to either 0a (what most hex decoders would do) or a0 (which is likely what is intended here)

IMO

filter: { ids: ["a"] }

is intended to mean

filter: { ids: ["a0", "a1", "a2", "a3", ..., "af"] }

Maybe exploding the odd-length prefixes this way is a good heuristic to avoid the ambiguity?

[hoytech]

Yep, that could work. I'm not sure if it's worth doing the work for this though -- If you're querying IDs then why not just send an even number of hex digits?

[Giszmo]

POW can be much more granular than full byte. 0x0000... is 256 times harder to achieve than 0x00.... If you allow half bytes, you still go in increments of 16 from one difficulty to the next.

I think for POW, the prefix is not granular enough. You would need for example a range: pubkey < 0x000454ffffff....

[ok300]

You can very granularly filter by PoW by enumerating the ID prefixes.

See https://github.com/rust-nostr/nostr/blob/master/crates/nostr/src/nips/nip13.rs#L386-L432

For example:

// 5 bits of PoW => 8 prefixes
assert_eq!(get_prefixes_for_difficulty(5), vec!["00", "01", "02", "03", "04", "05", "06", "07");

// 6 bits of PoW => 4 prefixes
assert_eq!(get_prefixes_for_difficulty(6), vec!["00", "01", "02", "03"]);

// 7 bits of PoW => 2 prefixes
assert_eq!(get_prefixes_for_difficulty(7), vec!["00", "01"]);

// 8 bits of PoW => 1 prefix
assert_eq!(get_prefixes_for_difficulty(8), vec!["00"]);

This can be generalized:

• 4k bits of PoW => 1 prefix
• 4k + 1 bits of PoW => 8 prefixes
• 4k + 2 bits => 4 prefixes
• 4k + 3 bits => 2 prefixes

So enumerating 1-8 prefixes can be enough to filter by any PoW.

[offbyn]

00 is completely fine for me as my motivation was to reduce bandwidth when the user only wants to see notes with POW.

In the meantime I found out that rust relay supports it and that there was an issue in which now is fixed, see offbyn/nostr-tools@98ecacd

Reading the rest of the discussion about 'odd-length prefixes' I guess this should probably go into a nip (ideally also prefixes itself would be moved to its own nip so clients could ask relays if they support prefixes).

scsibug/nostr-rs-relay#104 (comment)

Closing this.