You are reading content from Scuttlebutt
@Dominic %/EThAC4NGH+N3CDLqhd1x4U0WrznzRFJ0HHQSmXjRBU=.sha256

idea: compact feed/message id

I don't know why I didn't think of this earlier.
ssb has message references that are just hashes. sometimes it seemed like it would be handy to know the feed:sequence pair but including that [feed, sequence, hash] would make a giant id, that was ugly.

but what if that id could be about the same size as the message id?

inspiration: XOR linked list is a doubly linked list that stores the previous and next pointers XOR'd together so it takes the space of only a singly linked list but can still be traversed in either direction. you just need to know the addresses of two adjacent nodes.

So, XOR(feed, hash) then when you get the message, you can hash it, xor that with and you'll have the feed. which is also in the message - making this a fully verifyable secure identifier.

of course, we'd rather know the feed before downloading the message. if we truncate the hash a few bytes, and xor it shifted along then the first few bytes will be clear bytes from the feed, so we can check if it's a feed we know, XOR that feed with the id, and get the hash.

The chance of knowing two feeds with the same prefix would be low, but if you had a checksum in their also, lets say 4 bytes from hash(feed, msg_hash) then you could test each candidate feed and check that the checksum works out.

Assuming that the protocol allows you to request the message via the compact id, it wouldn't actually be important to compute the msg_hash on it's own, but it would be important to be able to verify the feed id.

createCompactId(feed_id, msg_hash, sequence) {
  spacer = [0, 0, 0, 0]
  checksum = truncate(hash(feed_id |,truncate(msg_hash, 12) , sequence), 4)
  return concat(
    slice(feed_id, 0, 4),
    XOR(slice(feed_id, 4, 32), concat(spacer, checksum, sequence, truncate(hash, 4*3)))
extractFeed(compactId, feeds) {
  candidates = feeds.lookup(truncate(compactId, 4))
  return candidates.find((feed_id){
   not_feed = XOR(compact, feed_id)
   checksum = slice(not_feed, 4, 8) //32 bit integer
   sequence = slice(not_feed, 8, 12)
   msg_hash_truncated = slice(not_feed, 12, 32)
   if(compactId == hash(feed_id , msg_hash_truncated, sequence)
   return [feed_id, sequence, msg_hash_truncated]

we can truncate the hash, and it's still secure enough to identify the message, but we cannot truncate the public key and still verify a signature. So the message hash is truncated to make room for the other data.

@Dominic %IBsJxh9HiaXGi4MLhebe2tACPb6jDwTug3gIEzipfi4=.sha256

I think @cft will like this idea!

User has not chosen to be hosted publicly
Join Scuttlebutt now