search

ssbc / ssb-db

A database of unforgeable append-only feeds, optimized for efficient replication for peer to peer protocols
https://scuttlebot.io/
MIT License
1.17k stars 75 forks source link

Recency guarantees through signed pings #72

Closed pfrazee closed 6 years ago

pfrazee commented 9 years ago

SSB is an eventually-consistent system on an asynchronous network. Asynchronous means there's no time-bound on delivery: the message can arrive on the other node at any time. Since the wall clock isn't consistent globally, there's no way to know how old the information is. That missing guarantee is called recency.

To provide a recency guarantee, we need a synchronous channel. This is trivial on a local network. On public net, a sync channel can be arranged through proxies (eg pub relays). Once it's established, users can send requests and measure the latency, giving them an upper-bound on how old the response is. This is the recency.

A "signed ping" is a request for the current seq number of a user's feed over the synchronous channel. With the resulting response time, the caller knows roughly how old the feed is. The ping response is signed to prove authorship, and response seq numbers prevent replay attacks. Signed pings can be cached, but they'd have relatively low TTLs (depending on the recency-guarantee needed).

Signed pings only work if both users are reachable. They can be used as heartbeats to provide fault detection. Because the heartbeat includes latest feed seqs, the recency guarantee transfers to the feed's messages, and they become effectively synchronous. Groups of nodes can then implement leader election (eg Raft) using SSB.

jbenet commented 9 years ago

Quick note: the signed ping response should include a random nonce from the requester. 

— Sent from Mailbox

On Wed, Dec 24, 2014 at 8:00 PM, Paul Frazee notifications@github.com wrote:

SSB is an eventually-consistent system on an asynchronous network. Asynchronous means there's no time-bound on delivery: the message can arrive on the other node at any time. Since the wall clock isn't consistent globally, there's no way to know how old the information is. That missing guarantee is called recency. To provide a recency guarantee, we need a synchronous channel. This is trivial on a local network. On public net, a sync channel can be arranged through proxies (eg pub relays). Once it's established, users can send requests and measure the latency, giving them an upper-bound on how old the response is. This is the recency. A "signed ping" is a request for the current seq number of a user's feed over the synchronous channel. With the resulting response time, the caller knows roughly how old the feed is. The ping response is signed to prove authorship, and response seq numbers prevent replay attacks. Signed pings can be cached, but they'd have relatively low TTLs (depending on the recency-guarantee needed).

Signed pings only work if both users are reachable. They can be used as heartbeats to provide fault detection. Because the heartbeat includes latest feed seqs, the recency guarantee transfers to the feed's messages, and they become effectively synchronous. Groups of nodes can then implement leader election (eg Raft) using SSB.

Reply to this email directly or view it on GitHub: https://github.com/ssbc/secure-scuttlebutt/issues/72

pfrazee commented 9 years ago

a nonce would be better than a ping seq

jtremback commented 9 years ago

Why not have a "ping feed"?

pfrazee commented 9 years ago

@jtremback as in post ping messages to your ssb feed?

jtremback commented 9 years ago

Have a separate feed just for pings?

pfrazee commented 9 years ago

ah, because you need the synchronous request/response flow to determine recency

dominictarr commented 9 years ago

Ah, it might be simpler to implement this as ephemeral messages (which have been sitting on the drawing board for a while) you'd just have an ephemeral message every day/hour whatever and if you have the message within that time, then you know you must be up to date.

Even if you do not post for weeks, as long as you are online, you'd post ephemeral heartbeats automatically, and receiving those would prove that the reason you havn't seen a post is because it wasn't created, not because of a network partition. At the same time, because of the way that ephemeral messages are discarded after a ttl these would not clutter the feed.

Question: have we had a discussion about applications that need strong recency support to be viable?

pfrazee commented 9 years ago

how will ttl work for ephemeral messages without a global clock? the premise for signed ping requests is that they use the latency of the sync request/response flow to measure recency without requiring a synced clock. would ephemeral messages have something similar?

the largest strong-recency conversation revolved around proto-money/caps. the idea was that peers may want to distribute information that has time-sensitivity. to deal with that, time-sensitive data could have recency constraints attached to them (which is different than a ttl)

an example with perms: 

9pm dominic says paul can use the bike (recency constraint: 5 minutes)
10pm dominic says paul cant use the bike anymore

so juan has the bike right now, and he sees the 9pm message. at 10:08pm i show up and ask for the bike, and juan's copy of the dominic feed is from 9:58pm (10 minutes old) so he has to ask for latest. either he...

so that's one example. i believe it could be possible to implement leader-based distributed transactions on feeds using the Raft protocol, but i'd need to research that

dominictarr commented 9 years ago

Oh right, now I remember - hmm - oh right so we add acks to the heatbeats and then we have signed pings.

stale[bot] commented 6 years ago

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.