#1767 closed enhancement (fixed)

update Announcement "timestamp": sequence number?

Reported by: warner Owned by: warner
Priority: major Milestone: 1.10.0
Component: code-network Version: 1.9.1
Keywords: forward-compatibility introduction time blocker Cc:
Launchpad Bug:

Description (last modified by warner)

One proposal that came out of #1765 was to change the current Announcement's "timestamp"-like field to be a sequence number instead of an actual clock value. This field is used by both the Introducer (server) and the IntroducerClient to decide when to replace a previous announcement with the same (pubkey, servicename) index, so it needs to be orderable and mostly monotonically-increasing. (it's ok if a publisher briefly uses a lower value than it did previously, as long as it's also ok for other subscribers to ignore that message, which generally means the publisher needs to periodically update their messages).

A timestamp (plus periodic updates) is a simple, cheap way to achieve this property. The only rollback would be for a timequake (when the publisher's clock has been adjusted backwards, maybe by NTP being turned on for the first time), and that will eventually be resolved when the new-time increases beyond the old-time of the last update (so rolling the clock back by one hour means one hour of stale announcements).

#1765 specifically discourages comparing this "timestamp" against anybody else's clock (since clocks are never really synchronized). So it really doesn't need to be a clock: it could just be a sequence number. The advantage of a seqnum would be that it would reveal less information about the client (which might help a de-anonymyzing attacker correlate the tahoe node's behavior with other externally-visible things).

The disadvantage is that we'd have to manage the counter ourselves, and tolerate node restarts which don't maintain the saved counter state. We want to make sure folks can back up their nodes by just recording some static private keys, and don't need to constantly be saving their updated counters.

The proposal is to do the following:

  • use a separate counter for each service-name
  • store the current counter values in NODEDIR/private/announcement.counters, one line per service, like: storage: 12
  • initialize all counters to 0 at node creation
  • increment the counter each time IntroducerClient.publish is called
  • if we receive a valid signed announcement from our own pubkey:
    • if the seqnum is higher than our current value, set our counter to one greater than the received value, and re-publish
    • if the seqnum is equal to our current value, but the signed message body is different, do the same: set the counter to one greater than the received value, and re-publish
    • if the seqnum is lower, or (equal and the message is identical), do nothing

In conjunction with the gossip protocol from #1765, that ought to converge. Nodes that are restored from backup (and thus experience a "counterquake") will send stale announcements for a little while (which everyone else will ignore) until they hear back their own earlier (higher-seqnum) announcements, at which point they'll advance their counters enough to become fresh again.

One requirement this imposes on clients is that anyone who publishes a record for service-name=X must also subscribe to service-name=X. Otherwise they won't know to update their counters after a counterquake. Alternatively, we could require that anyone else who receives message they recognize as stale must immediately send back the fresh version, even if the publisher wasn't subscribed to hear about them. This would require some changes to the APIs, as publishers and subscribers are quite distinct right now.

It might be easier if we only had one counter for the whole node, instead of separate counters for each service-name. Then receipt of *any* message with a higher counter would trigger the updates. (when gossip-introduction happens, all nodes will subscribe to "grid-control", so we don't need to require specific loopback rules). My concern is that we might announce (counter=0, service-name=storage, data=X) and (counter=0, service-name=grid-control, data=Y), then have a quake, then some small thing changes about the storage server but not about grid-control. When the node comes back, it will announce (counter=0, storage, data=Z) but still (counter=0, grid-control, data=Y). If we aren't subscribed to "storage", we'll see the grid-control loopback and conclude that we've converged, and not replace the stale storage/data=X announcement. Maybe requiring a nonce be added to grid-control messages would avoid this.

I want to get this change into 1.10, even though the #68/#1765 gossip-introducer won't happen until later, so that old 1.10 clients can continue to correctly update themselves in a gossipy world. Also, since the current implementation uses a clock, I'd like to switch to smaller integers as quickly as possible, so there are fewer nodes which have ever used a (large) time.time() and will thus have problems updating those announcements.

Change History (18)

comment:1 Changed at 2012-07-05T02:37:39Z by zooko

  • Milestone changed from 1.10.0 to 1.11.0
  • Version changed from 1.9.1 to cloud-branch

+1

comment:2 Changed at 2012-07-05T15:01:22Z by zooko

  • Milestone changed from 1.11.0 to 1.10.0
  • Version changed from cloud-branch to 1.9.1

comment:3 Changed at 2012-09-04T17:03:40Z by warner

  • Keywords maybe-fixed added

comment:4 Changed at 2012-09-05T00:08:47Z by warner

  • Keywords maybe-fixed removed
  • Status changed from new to assigned

The current code (in revision 15c95c2e) uses time.time(), so this proposed change has not yet been implemented.

comment:5 follow-up: Changed at 2012-09-05T00:17:25Z by warner

  • Description modified (diff)

fixed some typos in the description.

Two other thoughts:

  • if two nodes are somehow configured with the same private key, they'll fight over the announcements: each inbound announcement will trigger an outbound one with the higher seqnum, and they won't ever converge because they'll undoubtedly have different swissnums for the storage-server FURLs. They'll just chase each other up to infinity.
  • it's probably ok to just switch to a locally-managed persistent counter for 1.10 . I think we can safely defer the feedback/quake-handling code until later.

comment:6 Changed at 2012-09-05T03:10:40Z by davidsarah

The one-counter-per-node variant seems simplest.

comment:7 Changed at 2012-11-22T01:14:36Z by davidsarah

  • Keywords forward-compatibility introduction time added

comment:8 Changed at 2012-12-06T16:33:29Z by warner

  • Priority changed from normal to major

I wanted to make sure this makes it into 1.10, as it makes forward-compatibility easier.

comment:9 Changed at 2012-12-13T17:52:34Z by zooko

  • Keywords blocker added

comment:10 Changed at 2013-03-07T16:04:55Z by zooko

Let's open a separate ticket for subscribing to announcements about your own types of services, noticing an announcement about yourself, and updating your counter to be newer than the counter in that announcement.

comment:11 Changed at 2013-03-07T16:05:38Z by zooko

I didn't understand the weird issue about having a single counter per-node rather than one counter per service, and how this could lead to some subtle failure when one service has changed and another hasn't. Therefore, I concluded that having a counter per service is simpler. ☺

comment:12 Changed at 2013-03-07T16:34:25Z by davidsarah

Brian wrote:

It might be easier if we only had one counter for the whole node, instead of separate counters for each service-name. Then receipt of *any* message with a higher counter would trigger the updates. (when gossip-introduction happens, all nodes will subscribe to "grid-control", so we don't need to require specific loopback rules). My concern is that we might announce (counter=0, service-name=storage, data=X) and (counter=0, service-name=grid-control, data=Y), then have a quake, then some small thing changes about the storage server but not about grid-control. When the node comes back, it will announce (counter=0, storage, data=Z) but still (counter=0, grid-control, data=Y).

Ah, for "one-counter-per-node", I was thinking that the counter would be incremented whenever we encode a service announcement. So we would announce (counter=0, service-name=storage, data=X) then (counter=1, service-name=grid-control, data=Y), and the above situation couldn't occur.

comment:13 Changed at 2013-03-07T16:46:00Z by zooko

Okay, I'm +½ on one-counter-per-node, with davidsarah's variant (increment the counter once per service), and I'm +½ on one-counter-per-service.

comment:14 Changed at 2013-03-16T08:01:10Z by warner

Hm. If we increment the counter with each announcement, we could still get into the same trap:

  • announce (0,storage,X)
  • announce (1,grid-control,Y)
  • rewind to a backup
  • restart
  • announce (0,storage,Z) [ignored by others: seqnum not newer]
  • announce (1,grid-control,Y) [ignored by others]
  • hear back the earlier (1,grid-control,Y)
  • looks just like our recent announcement, so don't provoke a retransmit

Also I think we'd need to store (at least in RAM) a separate counter for each service, so we could recognize when announcements are newer than anything we've ever created. Ideally we want the very first message from our previous life to trigger re-encodings of everything we might publish.

I'm +1 on one-counter-per-node. I think I'm +1 on using the same counter value for all announcements (i.e. every time we update any service, we increment the counter, write it to disk, then publish a full set of announcements for all services, all using the same counter value). Then if we hear back any announcement with a higher counter value, or an equal counter but different contents, we trigger new announcements with the next higher counter. I *think* that will let any single message-from-the-future trigger an update, and will also correctly ignore echoes of any current message. I'm also +1 on adding a nonce to each announcement (created when we encode the message, stored in RAM only, not persistent), so we can distinguish messages from two different reboots that happen to otherwise contain the same contents.

comment:15 Changed at 2013-03-16T16:05:24Z by warner

I thought of a better example. Suppose we have 4 services A/B/C/D, and we've been publishing them for a while:

  • (10,service=A,data=dA1) (11,B,dB1) (12,C,dC1) (13,D,dD1)
  • now we shut down services B and C and stop announcing them
  • now the node crashes and loses its counter
  • the new node wakes up and publishes its remaining services
    • with a new counter
    • with new data for service A
  • (0,service=A,data=dA2) [ignored by others]
  • (1,D,dD1) [ignored by others]
  • node hears back the earlier (10,A,dA1), but isn't subscribed to hear about the others
  • node increments counter to 10+1=11
  • announce (11,A,dA2) (12,D,dD1)
  • node doesn't realize it's service D is out-of-date, and other nodes will continue to ignore announcements for a while

Also, I'm thinking the nonce is important, and should basically be part of the counter. So every time you increment the counter, you also make a new nonce, and the announcement's seqnum= field is a two-element list of (counter, nonce). The comparison rule says that recipients ignore announcements with counters that are lower than or equal than what they currently know about. They also ignore announcements which are identical to what they're currently heard. In the future, when a recipient sees a lower-or-equal counter in a non-identical announcement, they can send back a copy of their current copy, to let the sender know that they need to update their counter. The nonce distinguishes reuses of the same counter value (just without any sense of ordering).

seqnum+nonce is the same trick I used in Foolscap during reconnections, to tell whether you're talking to the same peer that you were just connected to, or to a newly rebooted instance of that peer. I think we use similar rules over there.

comment:16 in reply to: ↑ 5 Changed at 2013-03-19T01:57:24Z by AmmonRs

Replying to warner:

  • if two nodes are somehow configured with the same private key, they'll fight over the announcements: each inbound announcement will trigger an outbound one with the higher seqnum, and they won't ever converge because they'll undoubtedly have different swissnums for the storage-server FURLs. They'll just chase each other up to infinity.

if an attacker were able to get a node's private key, they could use the seqnum as a DoS attack, by making the node increment the counter until it looped, at which point all other nodes would forever ignore that node. probably not something to worry about, since if the private key is leaked, there are bigger problems, but something to consider.

comment:17 Changed at 2013-03-19T07:38:16Z by warner

AmmonRs: yeah, good point. I don't think there's much we could do about it.. even without sequence numbers, they could just keep re-publishing a bad address until the server admin gave up (sort of a manual version of the same attack).

comment:18 Changed at 2013-03-19T07:46:26Z by warner

  • Resolution set to fixed
  • Status changed from assigned to closed

I landed 3e26c78e a few hours ago to close this. I've opened #1933 to cover the future-todo items listed above.

Note: See TracTickets for help on using tickets.