On 12/09/17 22:34, Arne Babenhauserheide wrote: > > Matthew John Toseland <matt...@toselandcs.co.uk> writes: >> But we need *something* in this approximate area. > > I fully agree with that. I think however that we need to be careful not > to require user interaction for that. Users already added the friend, we > can’t require more than maintaining the friend connections. Otherwise > that would be the next bottleneck.
What makes you think we'd need user interaction?
If there is any deconfliction it's all at the client level, not the
node. The client can enforce any appropriate rules and decide to cast a
vote by reinserting the block it most prefers. The user might get
involved if there's a dispute about e.g. eliminating spammers.
Lets try to flesh out a proposal for scarce SSKs of some kind...
Proposal 0: Bundles
-------------------
If an SSK insert has maximum HTL, we pre-route it along a fixed
pseudo-random path, which ideally doesn't change for a given source
node. It only uses friend connections, and stays at max HTL until a
pseudo-random termination point (always the same node on a static
network). After that it turns into an ordinary insert.
The point here is that we provide as few samples as possible for a
correlation attack. If we receive a request, we know there is a fairly
high chance (say 10%) that it came from the peer, but receiving more
requests tells us nothing more. At least in the absence of churn.
There are tricks we can use to compensate for churn by using shadow
nodes so that even if we can't route it to fixed peer A, we route it to
fixed peer B instead, but the following hop is the same (possibly using
FOAF connections and proof of previous arrangements and whatever).
We might want to use this for CHKs too, but it would have negligible
performance impact for SSKs, and SSKs are more predictable. For CHKs
performance matters much more, although perhaps given the downstream
relaying it's not that bad.
Proposal 1: Scarce SSKs with global (per-node) scarcity
-------------------------------------------------------
SSK inserts can have a "scarce" flag.
For SSK inserts which have this flag:
On each hop during the pre-routing phase, we check whether we have
recently relayed a scarce request from that peer. If so, we terminate
the insert; they'll have to wait. We can make the condition more
generous to allow announcing multiple identities, be more flexible with
relaying when friend degree varies, etc.
Once we exit the pre-routing phase, we check whether the data is
popular. Popular means that lots of our peers are waiting for it. If it
is not popular, we handle it as a normal insert, returning the existing
data etc. So if nobody is listening you can insert however many keys you
want. This implies scarcity needs to be in fairly large granularity.
If we have the data, then the key will not be popular, as we've already
served the data to everyone waiting.
If the key is popular (and we don't have the data), we broadcast it to
everyone waiting. They will continue the broadcast, provided that the
key is popular from their point of view too.
We should probably use a different keyspace for scarce SSKs. But the
basic property here is that IF the key is popular, THEN the bad guys
only get N shots at it, where N is the number of friends they have.
This is adequate for announcement of new WoT identities, provided there
is a single global queue. For per-user announcement queues it would not
work well since they would not be popular enough.
Proposal 2: Scarce SSKs with per-key scarcity and multiple versions
-------------------------------------------------------------------
"Popular" is redefined to include the key has recently been in demand,
even though we have the data now.
If the key is popular, even if we have the data, we broadcast it.
Hence we can have many versions of the key, and they all get propagated
to sufficiently interested clients. Clients then need to decide what to
do with all the different versions themselves. There will be a time
limit after which the key is no longer regarded as popular, and we just
reject new inserts as usual, to simplify implementation and reduce the
amount of sensitive data we need to keep.
The pre-routing scarce relay check is changed to be per-{peer,key}, so
that if we have recently relayed an insert for that specific key from
that specific peer, then we terminate it. Hence each key makes up a
separate scarcity area. This arguably has advantages for anonymity when
using multiple scarcity-reliant services.
This proposal also only amplifies the attacker's efforts by a factor of
N, where N is the number of friends he has.
I don't think we can separate the per-key-scarcity property here from
the multiple-versions property. But both are potentially useful.
Proposal 3: Scarce SSKs with voting
-----------------------------------
We keep track of how many times each version of the popular scarce key
has been inserted (that is, how many peers have sent us an insert for
it). Once the time limit expires, the most popular key is stored, and
only that version is served to requests.
Clients have additional complexity in that they need to decide which
version they prefer, and insert it. But for some applications, such as
maintaining complex distributed data structures, this can be entirely or
almost entirely automated.
signature.asc
Description: OpenPGP digital signature
