On 13/09/17 19:56, Matthew John Toseland wrote:
>
>
> On 13/09/17 19:51, Matthew John Toseland wrote:
>> 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.
>>
> One important point: well-behaved clients maximise their privacy by
> sticking to the rules, i.e. only sending one scarce insert. Spammers can
> use every link to broadcast their spam, and thus have to refuse
> requests, but in doing so they have less anonymity with respect to
> nearby Mallories.
>
> If the fixed insert path is weak, we get issues there, we may want to
> solve them with multiple fixed paths, tradeoff with security, or go for
> some kind of verification... these things can get arbitrarily complex...
> but bundles are IMHO essential even on darknet, and the rest is worth
> seriously considering, if only as a basis for WoT announcement.
>
Some more points:
- We probably don't want to turn scarce inserts into ordinary inserts at
all. We should provide an API that allows falling back onto ordinary
inserts while an app isn't popular enough to use scarce inserts. But if
we're e.g. creating a new key every day, the attacker will just try to
insert to the key slightly before everyone else starts requesting, as an
ordinary insert. If he can't do the insert until after everyone is
requesting it, then he can't insert ahead.
- I think the multi-version variant actually solves a lot of problems
even with WoT announcement. If we receive every insert, that will
include the bad guy's 100 or so fake identities, but it will also
include the legitimate announcements, even if they weren't started at
the very moment when we started polling for new data. Whereas with the
global variant we are treating it as a race, which he may be able to win
fairly consistently with a smallish number of connections, e.g. by doing
the same insert on all his connections as soon as it becomes possible.
signature.asc
Description: OpenPGP digital signature
