Node Join Queue discussion and ideas around node membership

Features
24

I think the problem remains that if you let everyone in and this is accompanied by a large enough stampede of bad nodes (in proportion to network size - so worse in the beginning), then as sections split to manage the Infants you can run out of proven Adults, and so proven Elders, and end up with sections that are dominated by bad Elders (sleepers) which will then wait until the section is worth messing with.

I’ve forgotten what the benefits to an attacker of ‘owning’ a section are, so not sure if it will be a worthwhile attack.

3 Likes
25

A simple quiz of some sort? Random questions but obvious answers a human would know…

Or I suppose this can also be easily gamed in the future?

1 Like
26

Any reason why a central server couldn’t be used to assist with the management of invite codes during bootstrap?

That may make it much simpler to track whether or not a code has been used or not.

Bootstrap period is very sensitive time for network … I think of it like a parent holding on to the back of the bicycle as their kid learns balance. So Maidsafe using a clearnet ‘tether’ to assist in getting things started seems like it would be okay.

1 Like
27

but if they are just treading water, then they do not behave as normal nodes, just stand on their lonesome thinking until old enough to engage with real work.

Perhaps if there is a certain type of work that is useful and simple and not ciritcal, that could be thrown at these new nodes?.. so, not data storage but communications. That way bad actors might also be put off because not only are they inhibited from the work they want to disrupt but they are still contributing positively. Unclear exactly what actions are not critical but perhaps there are options for this??.. live streaming perhaps.

1 Like
28

I think the point of accepting these nodes is that they are asked to do normal work, i.e. store data, and will be evicted if they misbehave. But they can’t earn until they pass the age threshold.

It’s simpler than allowing all nodes to join and having to track a level of debt which is gradually paid down through rewards.

6 Likes
29

Caching and managing ddos duty :slight_smile: I like this idea. More complexity in distinguishing node types is a malus though.

4 Likes
30

This is the core issue imo. We can make nodes wait around and demand they are patient by only allowing them to reap rewards after a long time. We can punish bad nodes. This promotes good behavior and trains new benevolent node operators, it handles the basic cases but only goes so far. The real challenge is the long term sleeper threat and making sure that it is not financially or physically possible for someone to create enough nodes to gain >33% control of the network elders.

2 Likes
31

Tldr: I’ve warmed up a lot to the “store only when capacity is needed” idea. No solution will be perfect and can be adjusted to reach a good equilibrium. There’s substantial risk though that an adversary can use any weakness in the token economics to afford to upload a lot of data and flood the network with sybil nodes. This risk can be countered by ensuring that it’s highly costly for any one party to amass a large amount of tokens (whether by farming or buying on the markets) and that farming is highly popular and easy to partake in (so that the sheer number of nodes from average people overwhelm any one adversary).

The goal being to have as large a network as possible, which would provide capacity and be better able to absorb any attempt by a byzantine party to take over the network, I didn’t like the idea of only allowing more nodes onto the network when current member nodes are full. So I was going to suggest that MaidSafe run the network until a very large size (1,000’s of nodes) then allow trusted forum members to also add a large quantity of nodes. Then after that stage, with the network having 10’s of thousands of nodes, it should be open to everyone so that going forward all nodes are accepted. A problem with this approach is that it would provide a substantial advantage over the long term to insiders and early adopters, but no solution is going to be perfect.

But thinking more about it, I now like the “accept nodes when capacity is low” quite a bit. The strategy is essentially employing economic cost for sybil defense, which is one of the most effective sybil defenses (if not the best). The strategy has a second benefit, i.e., it essentially is also pushing farmers to bootstrap storage on the network (i.e., if you want to become a farmer faster, you either store data onto the network yourself or you advertise the network so that others store data on it). Now, how do we ensure the network grows to a very large size without first waiting for its services to be first popular? Because the economic cost for sybil defense strategy here is a bit different from that used in say Bitcoin with pow, several factors need to be accounted for including:

1) Limit on node size
This will be important to estimate how much data should be uploaded to obtain membership. Such visibility will be helpful to farmers as they would have a consistent formula for obtaining full membership onto the network. Setting a limit on node size will also allow the network’s growth rate as well as its economics to be modeled more accurately.

2) Definition of node fullness
Great that it moved from 80% to 50%. It probably should decrease even further. I don’t know what the right value should be. 1% so that if the standard node size is 100Gb, a farmer would have to upload a maximum 1Gb of data to ensure that at least 1 member node becomes full? I feel an optimal number can be modeled as a function of the upload cost and the token emission to ensure that the number is sufficiently high to be costly for an adversary to “fill” member nodes at scale but sufficiently low to ensure an average person can “fill” a member node in order to become a farmer.

3) Cost of upload
Needs to be sufficiently high so that an adversary cannot afford to flood the network with data and thus with its nodes. Risk that there’s an initial high cost for an adversary but it’s essentially free after that (i.e., as long as they can afford to upload a large enough amount of data and get their nodes on, they can now earn enough tokens to continually upload more data and have even more nodes accepted). Token supply and emission (item 4 below) can help here as well as popularity of farming (item 5).

4) Distribution of the token
Needs to be very difficult for one party to be able to accumulate a large amount that they could then use to flood the network with data and thus nodes. Serious consideration need given to the pros/cons of having the vast majority of the token supply be earned by potentially dormant adversaries that can later use it to attack the network versus ensuring that the maximum that can be earned by farming is the same or less than the proportion distributed amongst MaidSafe, early backers, ICO participants, and market participants over the years for the proxy token. The latter option doesn’t preclude that there might be a potential adversary who’s already acquired a large amount of the proxy token, but is that likely considering how many left the project for dead and more importantly is it more likely that an adversary, now seeing that the network is actually possible, can try to acquire a large proportion of tokens to wreack havoc if the supply or its emission aren’t controlled.

5) Popularity of farming
If farming on Safe Network is popular, it would help counter any one party’s attempt at taking over the network by diluting their nodes with the sheer mass of nodes from everyone else. How can that be achieved? Marketing? High token price to attract droves of traditional crypto miners? How about data hoarders, tech-minded, hobbyists, futurists, torrent seeders? How should they best be reached so they can support the network with nodes?
This factor (and 6 below) can blunt can blunt the other risks substantially.

6) Ease of participation
If it’s very easy to join the network / become a farmer, the average person will more readily help the network versus an adversary who will be advantaged by a difficult to join process as they will more likely have the patience, know-how, and resources to overcome any such difficulty (and at scale).

5 Likes
32

Whatever method is used it MUST allow headless systems to run a node without human intervention.

5 Likes
33

Not really been mentioned by name much until @Bogard post above, so just to be clear, I’m pretty sure the ultimate purpose of the ideas we’re talking about is defence against this sort of thing:

I know @mav did some maths a couple of years ago showing how many nodes an attacker would need on the whole network, in order to control a section. I think that will have changed a little bit now with needing a super majority for a section, but the principles are no doubt similar.

I imagine in theory an attacker would build up enough nodes with their software behaving according to network rules until they were confident they had a super majority in at least one section, and then the nodes would try to collaborate in order to achieve whatever ends the attacker was aiming for.

The measures already in place such as node ageing and only allowing nodes to join when required (plus others measures?) will provide different levels of protection at different sizes of the network obviously. Would be interesting if the team had any data on this sort of thing.

Yeah, I guess this is quite an important question, but I imagine the answer is ‘very bad things!’ such as minting SNTs, losing or stealing data.

Would also be interesting to know if the network as a whole has any defences if a section is successfully attacked.

No answers from me, just thought it was worth looking at the bigger picture before the discussion gets bogged down in any specific solutions such as proof of human or whatever.

2 Likes
34

One view into some of this is here https://github.com/maidsafe/sn_routing_sims we did that about 2 years ago to prove node age was strong enough on it’s own and with section size (only looking at this angle) of 60 sybil was unfeasible. Adding in the economic’s as @Bogard discussed above adds a lot more. So we have gone now for smaller but more numerous sections for now. The section sizes may tweak again, depending on load of Adults and Elders. When that completes we will then have some math done again on sybil, but maths cannot readily grab and understand economic protections.

7 Likes
35

Thanks David. I’d have thought the economic protections were relatively easy to quantify though, in addition to the pure network elements. Or at least, to estimate the cost of an attack at different sizes of the network.

1 Like
36

Is there any problems with having no limits on the amount of infants joining,but then just leave them to do something costly like proof of work while they’re waiting to be promoted to adults?

The promotion to adults could maybe also be probabilistic, so it would pick at random an infant over a certain node age, maybe with probility to be picked increasing as node age increases.

2 Likes
37

To add to this, there is a very detailed analysis from the routing sims:

SAFE Network Sybil Resistance Introduction

You’ll need to log in to hackmd to read it, but it’s free to register.

3 Likes
38

Maybe give them some fake data that elders can check via hash every now and again - help to prove their hardware/uptime etc. Maybe a feedback report as well on what the elder sees - give the infant info on how to improve their odds of getting upgraded.

1 Like
39

And we’ve been talking about a few of the known defense mechanisms already.
Quoted from tbe wiki:

“Known approaches to Sybil attack prevention include identity validation, social trust graph algorithms, or economic costs, personhood validation, and application-specific defenses”

Anyone know about some unknown approaches? :cowboy_hat_face:

2 Likes
40

Yeah, of course. I just thought from the OP and the discussion it might not be clear that it was all part of a bigger picture.

2 Likes
41

Node age :smiley: :smiley:

2 Likes
42

Here’s an interesting joining/queue idea that tackles a few things all at once.

The benefits:

  • allows nodes to immediately begin doing useful work, no waiting (pre-filling, auditing).
  • provides a ‘fair’ selection of the next node to be moved from the queue to the section.
  • adds a layer of audit for existing nodes.
  • improves data redundancy (but not in a reliably accountable way)

The join process:

  • The node joins and is put in the queue for their future section
  • The node pre-fills with chunks by repeating the audit process (described below)
  • As the node fills up, it signs each pre-filled chunk with their name/keyair and submits their ‘best’ (smallest value) signature to the elders to determine their place in the queue. More pre-filled chunks gives more chances to reach the front of the queue, so nodes will really want to pre-fill. More details of this below.
  • When a new node is needed by the section, the node with the best signature is added to the section. The node already has most of (or all of) the chunks they need because of the audit/pre-filling process, so there’s almost no stress on the section during churn.

The audit process:

  • Request 10 (?) sequential chunk names (only the names, not the data)
  • Make the same request for sequential names to the next closest node (which should return the same 10 names since it’s close and chunks are redundant)
  • Any discrepancy in names can be shown between these close nodes to elders to deal with it (allow adults to fix missing data or extra data, maybe punish but unlikely)
  • The node requests the data for these chunk names and stores the data locally; when the node joins it would become responsible for those chunks so it will need them in the future anyway.
  • For each chunk received the queued node signs it with their own node name/keypair and if it’s their new ‘best’ signature they submit it to the elders of the section to hopefully improve their place in the queue. Since the signature value can’t be known in advance this adds an element of randomness to the position in the queue, but queue position should on average be roughly proportional to the number of chunks a node has pre-filled.
  • The node requests the next 10 sequential chunk names following on from the last name of the previous lot
  • The node repeats this until either a) the node is full or b) the end of the chunk list is reached. In either case the queued node repeats the audit process from the start in case new chunks have arrived in the meantime.

The queue:

  • Elders keep track of the ‘best’ (smallest value) valid signature of each queued node.
  • When a new node is needed (whatever the reason) the first node in the queue is removed from the queue and added to the section, giving a new leader in the queue.
  • Question: should we allow nodes to know their place in the queue? Should we allow nodes to know the value for the ‘best’ signatures ahead of them? I’m not sure.
  • Requests for 10 sequential names is not bandwidth or cpu intensive so queued nodes do not pose significant overhead to other nodes.
  • Audits allow nodes that are missing chunks to be detected and notified to re-fetch that data. I don’t know if punishment would be part of the audit process, maybe it could, but my main intention is to increase data robustness rather than find faults.

Effect on attackers:

  • Attackers must do the audit process or they will never be at the front of the queue and therefore never join. So their workload per node becomes quite substantial.
  • The opportunities to reach the front of the queue are proportional to the number of chunks fetched/stored during audit. So a faster node has a better chance to be at the front of the queue, but it’s not 1,000,000x better chance like asic vs gpu in bitcoin mining (fast node as in faster signing or faster bandwidth/latency).
  • Any advantage attackers find in the audit process to try to ‘jump the queue’ (eg asicboost in bitcoin) can be directly used to benefit the network since the signatures they must generate are the same type of work as they do when they’re adults/elders.
  • Since there are finite chunks per section the chances for each node to jump to the front of the queue is also finite. So an attacker cannot possibly have 1,000,000x more chances to reach the front of the queue than any other node.
  • Queued node would make requests for their pre-fill chunks from a normal ‘anonymous’ client, so there’s no way for malicious existing nodes to deny data to queued nodes since all requests for the data look the same.

This potentially also greatly improves redundancy since if the queued nodes are also storing the network authority that allowed the chunks to be stored in the first place, queued nodes become yet another source of data recovery in the case of catastrophic failure.

To zoom out a bit, I don’t think there’s any way to stop attackers at the queue. We can only stop them when we know they are attackers (ie they become faulty). Best way to handle faults is to be inherently fault tolerant, and crdts brb at2 etc go a long way toward this. The section wallets are still a risk, but we can almost certainly remove them, so elders eventually hopefully won’t have any responsibility beyond signatory work. We need to also look at making mutable data safer from malicious elders but I’m sure we can do that too (just haven’t got to writing down ideas yet).

I personally prefer all people to be able to join the network in some sort of way, no idling in the queue. I reckon the queue concept above allows newcomers to see progress and do something meaningful, while also making it very difficult for an attacker to get a cheap and easy foothold. The queued nodes don’t earn reward but they do contribute meaningful work.

I also (probably against popular opinion) accept that companies and datacenters will have a proportionately different role than individuals. I don’t think that’s necessarily wrong or bad. If a company has 1000x the resources of an individual I see no reason why they shouldn’t have 1000x the responsibility. That’s just normal and logical. What I would hate is if that company could exclude anyone, an individual, or a smaller company, or a larger company. I feel the potential for exclusion is a much bigger problem than too much inclusion.

12 Likes
43

We could do this (we also have the algo to check chunks are actually stored, in fact I will put this here…)

  1. Node Gets some chunks given to it (for Infants let’s say X closest to his name).
  2. Elders know who has what chunks.
  3. Elders then request a node takes random data (sig/hash of known message) and prepends (important to prepend not append as sha3 is spongy)
  4. Node hashes chunk and returns hash as proof.
  5. Elders compare with several other nodes who also hold that chunk and finds outliers
  6. Outliers directly tested by retrieving the chunk and killing them if they don’t have it.

A few things to consider

  • can Infants just get a chunk when they ask (we can prevent that))
  • How much Elder work is this?

Then I suppose in terms of store more get higher up the queue ? I think skewing towards bigger nodes may be troublesome (weird as it sounds). What about infants get a chunk with every new infant trying to join? Then we know the “eldest” of them?

Q - Should we prioritise those nodes hanging around more?

I suspect we don’t directly but weight them positively.

Then we can do something like select the closest Infant we need (close in address to a lost node or a full node), so random, but also take into account weight (how long have they been there and are they really holding chunks?) in a roulette wheel type selection. So select 10 (say) and weight each of them wrt data held (time waiting) and choose? However we cannot do a roulette wheel here as we need all Elders to agree on same Infant!

Or do we? What happens if they all choose different Infants and we let them all in? So we could add up to ELDER_SIZE nodes instead of a single node, also bad guys will select the bad Infants to join.

Is it bad, it’s a consideration.

To remove this we change the roulette wheel to a deterministic algorithm that calculates # chunks held and xor close to the hole we are trying to fill (the lost/full node).

Anyway, very fast brainstorm, but hopefully more info. I feel we are on the right track here and great to look at this knowing we will impl it in days :slight_smile:

11 Likes