Secure Random Relocation

[mav]

I have two proposals to improve the security of the safe network.

The second depends on the premise of the first, so if the first is not seen as desirable the second one has no relevance. I think together these two ideas are potentially better than the current design for vault relocation.

This is quite a confronting proposal (even to me) so all feedback is most welcome and will be taken in the best spirit.

1. Secure Random Relocation

Motivation

The existing relocation mechanism has several benefits:

1. Vault relocation ensures resources are periodically moved to different parts of the network, preventing deliberate concentration of resources and thus preventing control of consensus.

2. Vaults are relocated to the ‘most in need’ section, which helps the network stay healthy where it matters most depending on the current state of the network at the time of relocation.

But the relocation mechanism has several drawbacks:

1. Vaults are relocated to a neighbouring section which means once the vault is initially located in the network their future possible locations are very restricted [1].

2. Vaults are required to brute-force a public key matching their new section prefix, which becomes expontentially more difficult as the section prefix grows. This is liketly to exclude all but the most powerful participants for large networks [2]. This affects the scalability of the network.

3. The requirement for brute-forcable public keys means targeting a section in order to control consensus is and must always be a viable option.

4. The initial joining mechanism uses a random piece of data from the section (eg the last block hash) to ensure the new location for the vault is random. This is intended to prevent targeting the initial join to any specific section. However, this leaves an attacker with an amount of time (ie the amount of time between blocks) to brute-force their join to a specific section. This window-between-blocks means more powerful attackers have a better chance of succefully targeting a section than weaker attackers. This drawback of using time-dependent-randomness could be eliminated by using an ‘on demand’ source of randomness rather than ‘historical’ source of randomness.

This proposal aims to mitigate these drawbacks without compromising the benefits.

Details

Vaults should be relocated to a random section on the network rather than to the ‘most needy’ neighbour.

The challenge is ensuring the chosen section is indeed random and not targeted.

One possible proposal that works well within the existing design is to have elders each generate 256 random bits, and then XOR all these values together to get a combined random value V.

If V were to be the new public key, find the new section prefix for that hypothetical key.

Send a request to that section for a relocation of the target vault.

The target vault brute-forces a new public key matching the new section prefix and once complete that vault is relocated to the new random section.

Benefits

By combining random numbers from all elders there is no way for any single elder to bias the target section. An attacker would need to control all elders in order to control the relocation mechanism, and controlling all elders is extremely difficult, especially when relocation is random rather than neighbourly. This makes the relocation mechanism even more secure than the quorum mechanism, which is itself already extremely secure.

Targeting a section to control consensus becomes much more difficult, needing about 50% of all nodes for random relocation compared to about 5% for neighbourhood relocation + targeting [1].

Vaults are very evenly distributed through the network due to the statistically even distribution of randomness.

Less coordination between sections is required since there is no need to find the best neighbour. This is especially true when the best neighbour is found via recursion. This means less time required to conduct the relocation, less bandwidth consumption, less computation required since there is no need to measure the suitability of each neighbour.

Drawbacks

The vault is not targeted to the ‘most in need’ section within the neighbourhood, which may lead to some sections doing more work or being in worse condition than if they had help targeted toward them in times of need.

A keypair must still be brute-forced which may exclude some participants, especially in large networks. The time taken to brute-force may also delay the relocation which has run-on effects for the smooth operation of the network.

There may be negative implications for connectedness between sections, which is currently proposed to be on a neighbour basis. This proposal may require communication to any other section on the network, which may be more onerous than maintaining neighbourhood connections.

Considerations

Random relocation solves some problems but leaves others remaining (ie having to brute-force public keys).

The next proposal (HDKeypairs) suggests an efficient means to solving the brute-force issue. It also makes this implementation redundant, removing the need for all elders to agree on a random target. The second proposal is extremely efficient because it a) removes the need to brute-force a public key and b) does not require any cooperation between elders to achieve the desired outcome of random relocation. But it depends on accepting that random relocation is preferable (or at least equal) to neighbourhood relocation.

2. HDKeypairs instead of Keypairs

Motivation

Relocations on the safe network require the relocating vault to brute-force a public key that matches the destination section prefix chosen by the network. For large networks this requirement can become extremely difficult (approx 30m for a network of 1B nodes [2]).

This proposal removes the need for brute-force computation and replaces it with an efficient alternative using Hierarchical Deterministic Keypairs (HDKeypairs).

Currently there is no way for the network to take an existing public key and modify it in such a way that the vault can apply the same modification to the corresponding private key. This would be useful since the network could determine the random modification required and the vault would simply apply that modification rather than have to brute-force a private key that matches the modified public key.

This proposal suggests a modification scheme for public keys that can be directly applied to private keys, thus avoiding the need to brute-force the private key.

Design

What is desired is a way to easily pick a new keypair that is known to relocate to a different section, but does not involve sharing the private key.

This can be achieved using the same ideas found in Bitcoin BIP32 HD keys [3].

1. The vault derives a HD private / public keypair

   For this example, the entropy used to obtain the initial keypair is BIP39 mnemonic abandon abandon ability. In practice the root HDkeypair would be sourced from any secure entropy.

   The root / original hdkey is generated by the vault:

   HDprivkey:
   xprv9s21ZrQH143K2jkGDCeTLgRewT9F2pH5JZs2zDmmjXes34geVnFiuNa8KTvY5WoYvdn4Ag6oYRoB6cXtc43NgJAEqDXf51xPm6fhiMCKwpi
   HDpubkey:
   xpub661MyMwAqRbcFDpjKEBThpNPVUyjSGzvfnndncBPHsBqus1o3KZyTAtcAmnxBFRv4eTrHGa4iNoDq8CfHrWYgMcpT3CDQb5bFZdVfny5KQc

   This HDkeypair has corresponding public / private keys which can be used for naming and signing etc [4].
   pubkey:
   038cf4c61fa8f5beabe58e2c223c3e1f31faa232baa6d4a54319c1744ed3c87900
   privkey (WIF encoded here but is regular bits at the lowest level):
   KwzcZnkHocMpY4SWU2ErUktSgiq6npZ8fNzV8uiXp4Vr6AFh62Ma

2. The xpub is shared to the network, the xprv is kept secret to the vault.

3. Upon needing to relocate, the network gives the vault a random derivation depth, for this example 185 is used. This may be sourced any way, eg the last byte of the latest block hash.

   The network derives the new HDpubkey from the existing HDpubkey using the random depth 185. This gives the new HDpubkey for the vault to use.

   The network derives the new HDpubkey from prior HDpubkey at depth 185, which is
   xpub69ZVZQzP4T8n5hTjoDSkvCPAXh9h6bdYJoKwzjBVMH2Rq1oeH1H7DULiJC6k1Kh5w4XDGjrCdLpyMuupPHWuJ1Jeb7KwmB3RBB5FaRDyD2j
   and gives new pubkey
   031de1cd9cc3e401a7f9eeb9c1201cc7889439abbfd9d9df672822b0d9bebf888c

   3a (option targeting step). Instead of generating one key at the random depth (eg key 185) the section can generate ten keys starting at the random depth (eg keys 185, 186, 187… 194). The ten sections corresponding to these pubkeys can be checked for their health and the one with the most need for a relocation can be selected.

4. The vault can use the random derivation depth supplied by the network to derive their new HDprivkey from prior HDprivkey at depth 185, which is
   xprv9va99uTVE5aUsDPGhBukZ4SRyfKCh8ugwaQMCLmsnwVSxDUVjTxrfg2ESuN6Qi9ND1efMWYLTNFCS9iwvMEeU4PQzXgeCuErY9UCLijwD7M
   This gives new privkey
   KyGz1AVBvMa1ebSaX5RWfCCiNKuu4rgFjq6MzKz96RNjHniBpoVs
   The vault also can also derive the same HDpubkey and pubkey as the network.

   The vault and the network are both in sync with a new keypair and no need to bruteforce a new private key.

5. The current section for the vault can locate the matching section for the new public key, then request that section to accept the newly renamed vault. The new section can confirm the randomness of the relocation based on the latest datachain block (or whatever random source is utilised). The vault is immediately able to sign messages for the new public key derived by the network. The public key is not just used to determine the new section prefix, it’s the actual public key the vault must use.

6. This can be repeated again for the next relocation, continually extending the derivation path with new random depths sourced from the network. The vault and network are traversing a key-tree rather than a sequential set of keys.

Benefits

The network is never exposed to the private key so retains security.

The vault is not required to brute force a private key that matches a random section prefix so is very fast for both the vault and the network.

Removing the brute-force means performing relocation is constant-time regardless of the size of the network or the computational power of the vault or luck of the find. This improves the equality of participants and removes advantage from having access to greater resources.

The relocation is securely random since the network decides the random portion, not the vault. This means a) there is no ability for the vault to modify or manipulate the result in any way and b) it’s extremely fast to obtain the new keypair in a secure way.

The inability to move far away from the neighbourhood is removed. Vaults may move anywhere in the network and should result in a very even distribution of vaults regardless of how the vault initially attempts to place itself in the network.

The problem in Proposal 1 of the time-between-blocks giving more powerful attackers some advantage over less powerful attackers is now removed. Once the initial HDKeypair is decided there is no way to affect the distribution of possible future keys regardless how much time passes between the random data being known and the join being initiated. Future relocations will be evenly and randomly distributed so there’s no benefit to starting in a particular part of the network.

All existing operations remain as currently designed, eg signing and verifying messages, use of public keys as names, datachain structure and operation, ageing etc.

HDpubkeys need not be stored in blocks. They must be kept in memory for the purpose of deriving future keys, but do not add data to any permanent storage requirements.

Drawbacks

Vaults cannot be relocated to the part of the network needing the most help so there may be times where some parts of the network that are less healthy than others.

HDPubkeys are larger than pubkeys (approx 512 vs 256 bits) so have some additional overhead for memory and bandwidth etc compared to plain pubkeys.

Derivation requires some additional computation for the section compared to purely random keys, but is negligible (perhaps even a slight improvement depending on the specific method for obtaining a purely random key).

There may be complications in deciding the new depth to use, especially around the time new blocks are being proposed / finalised. But this complication applies to all consensus operations so this technique would be comparable to most other alternatives. In theory the depth could be constant without affecting the security, eg 0, but this is something for further discussion.

The design of a BIP32-like mechanism for EdDSA keys has not yet been formalised.

---

Open Questions

Which is preferable: targeted relocation or random relocation?

On one hand targeted is good because it lets vaults relocate to the place they are most needed by the network (eg to prevent a merge or assist a split or enhance section equality).

On the other hand random is fine because it should balance the network well in a natural and statistical way. ‘Bad health’ should be unlikely and temporary with secure random relocation.

I think further investigation is needed. It requires having an agreed concept of ‘sickness’ or ‘health’ and then seeing how much the targeted relocation mechanism benefits the health vs the cost of brute-force pubkey generation and all that goes with that.

Personal thoughts

I strongly suspect that the network will rarely become unhealthy, especially with random relocation. I also strongly suspect that the cost of needing to brute-force private keys is not worth the supposed benefits.

I think it’s flawed to measure ‘sickness’ for the purpose of helping via relocation. This implies that enough of the factors of health can be known for the measure to be meaningful. However I think many of the important measures of health are not possible to measure. For example the network can’t know if vaults are coordinating between themselves out-of-channel, or know if an attacker is performing an offline analysis for some kind of unique targeting attacking.

I think having simple but certain mechanisms (in this case HDKeypairs for random relocation) is the safest way to account for unknown variables in the health of the network. I also think random relocation is a more elegant solution than the conditions and meddling of neighbourhood relocation.

I can see the appeal of ‘intervention’ and optimization of the relocations, but to my intuition the risks and costs of being able to make it work are too high compared to the benefit.

References

[1] Analysing the google attack - #63 by mav - Blog Posts - Autonomi Forum (Safe) and Analysing the google attack - #65 by mav - Blog Posts - Autonomi Forum (Safe)
neighbourhood-based relocation means vaults can only ever be reassigned to a very small subset of the network. If an attacker can target one part of the network their vaults are likely to stay concentrated there rather than spread evenly across the network.

[2] Data Chains - Deeper Dive - #28 by mav and following posts
the need for brute-forcing pubkeys and how easy or hard that might be.

[3] bips/bip-0032.mediawiki at master · bitcoin/bips · GitHub
note BIP32 operates on ECDSA keys whereas the SAFE network uses EdDSA so the details may need some tweaking. But BIP32 provides an implemented platform upon which the idea can be demonstrated.

[4] http://bip32.org/
tool for working with BIP32 HDKeypairs

[rob]

In point 4 of the drawbacks

@mav

However, this leaves an attacker with the an amount of time (ie the amount of time between blocks) to brute-force their join to a specific section.

You seem to be missing part of this sentence. “with the an amount of time”

[rob]

Excellent work again @mav

@mav

On the other hand random is fine because it should balance the network well in a natural and statistical way. ‘Bad health’ should be unlikely and temporary with secure random relocation.

I think this is an area of your excellent proposal that needs consideration.

In stats as you likely know there will be in a large enough sample sections, there will be sections that end up getting few relocations to it.

So I feel we would need to consider methods to quickly relocate vaults that end up in very healthy sections. So maybe after a short time (so many section events) in a section with more than enough nodes the vault is relocated again.

Thus there is a tendency for vaults to end up in the sections actually needing more nodes.

So there would need a mechanism to stop the vault being relocated too many times because of this.

[dirvine]

HDKeypairs is an excellent idea, it satisfies another area we have not covered yet. So very cool indeed.

I think part 2 is extremely promising as a randomising step for relocate. I need to think further though (trying to sleep of the flu just now). The depth can be calculated based on the age actually (the age will increase by 1 on a relocate, potentially allowing age to be a depth factor).

The trigger is important, we already have the mod division trick with PeerLost type events and that is fine, but does not allow the network to grow properly. Put and Update of data though is interesting. @Viv and I were discussing this earlier today and it does allow much more/faster ageing, but less likely to be game-able, as long as we do not use mod division of an event hash for that part. I mean not allow a client to do an action that it knows the trigger value will age one of its own peers. However for data we have all the items and versions already so no need for mod division or traversing the chain.

Note: On that traversing part, just imagine for now data floats to the top of the chain, so each node joining gets all the data and must sign it, thereby we know its resources are good enough and we have its sigs for the new elders (if it were to be an elder). So resource proof is actually testing if a peer cna do the appropriate work, pretty nice. Anyway it means all the data is signed by the current elders and not spread through the chain. That allows many things like efficient pruning of the chain etc.

From our current perspective though it means we can say we have X data items and Y versions (which we can add for instance) to figure out the trigger for Put based relocate triggers, which would be in addition to churn triggers (which are good for DOS mitigation amongst others).

So with these triggers the hash of a churn event or Put/Edit request (which costs safecoin, another nice effect) we have a random relocate, however as with the current routing master (i.e. tested in the field) it would be nice perhaps to also allow balanced relocate. This gives the best of both worlds for new/small networks, but less so as the network grows.

This last part is the point of discussion here I think, whether to drop balanced relocate or not. There are strong arguments for doing so from this proposal, but we have seen issues with small network in testnets. However perhaps we need to start much larger testnets before allowing churn (i.e. we invest and start several thousand nodes instead of 100 or so).

I hope these initial thoughts help, when my head is more clear I will make much more sense, honest

Anyway extremely good proposal Ian, I like it a lot and as they say in Galway, it not a million miles away from Mary Heurons

Great when the proposals come from folk who understand eventual consistency, its like a breath of fresh air. I suspect this is very close to what is implemented actually, but the HDkeys do need a bit of investigation, but it is defo something like this I was needing for another bit further down the road, so thanks a lot for that one.

[jlpell]

I’m still not up to speed on all the details of how the network implements relocation.
However, based on my intuition @mav’s description along with @rob’s comments sounds similar to poisson disk sampling. In terms of geometry, poisson disk sampling has a lot of nice properties, and might be interesting to consider from an XOR space perspective.

https://www.jasondavies.com/maps/random-points/

GitHub - njanakiev/poisson-disk-sampling: Fast Poisson Disk Sampling implementation in...

Poisson Disk Sampling

[mav]

@dirvine

The depth can be calculated based on the age actually (the age will increase by 1 on a relocate, potentially allowing age to be a depth factor).

Predictable depths such as age (or constant 0 as per the original post) are not going to be secure for this because it allows brute-forcing not just of the current section but all future sections!

So there must be randomness in the depth. This adds a lot of strength since brute-forcing becomes much harder.

Predictable depth using age for depth (bad)
Age  Derivation Path  Possible Keys
1    m/1              1
2    m/1/2            1
3    m/1/2/3          1
...
n   m/1/2/3.../n      1

Random depth r between 0 and R (good)
Age  Derivation Path  Possible Keys
1    m/r1             r
2    m/r1/r2          r^2
3    m/r1/r2/r3       r^3
...
n    m/r1/r2/r3../rn  r^n

R can be chosen depending how much work is desired to prevent brute-forcing the future possible sections.

[tfa]

@mav

Which is preferable: targeted relocation or random relocation?

We can have both if the destination section generated from your proposal (either 1 or 2) changes the relocated address to another one belonging to a neighbouring section of the destination section more in need of a new node. I think something similar is currently implemented in routing code.

So the choice is not limited to relocate a node to a either a neighbouring unhealthy section or a random distant section. We can have both if the destination section changes the address to the least healthy of its neighbours (and itself).

[happybeing]

Superb @mav, wish I had something relevant to add but I do love reading this stuff and I guess some of it sticks. Well done yet again.

It’s also reassuring to me - and others I’m sure - when we have this level of dialogue with David and the team. It’s more valuable than any white paper, in judging the health of the project.

[dirvine]

So back out of bed for a wee while. From what I can see we have a few options, like much of routing design these days its choosing 1 of a few, most of which reach a good level of security. I will try and break it down a wee bit to keep the convo on track. @mav I don’t want to burden you here so don’t feel any pressure to back off or get more involved, just be where you are comfy, but your input is superb, really superb.

Relocation Trigger

This should alert the section that a peer of a certain age should relocate. So far we have simulated using churn only and this is not enough really to allow growth of the network as it ties in membership with age and tends towards stagnation. So adding in something else that is non deterministic but random needs to be found. This is not a case of the group creating random data as that is too hard and needs a lot of rounds of agreement plus deciding who goes first creating that etc. Basically it is much better to find randomness in normal operation, that is fast secure and reliable.

For churn randomness we use a mod division trick, so mod div the churn events hash with node age (oldest to youngest). This is good and means we do not need to traverse huge chunks of the chain to look at how many events each node has been around for and make calculations on the exact count etc. So the mod div woks a treat her, especially as nodes are unlikely to win anything by self sacrifice in favour of another node that is an attacking partner in a section. So nice and neat, but not enough events to allow age to grow.

So we add in another event series to allow this, the obvious one is Get but that is game-able as an attackers clients can Get stuff a lot to have age grow for attack nodes in a group (not as simple really, but can happen). Therefore we choose mutation events. These are good as they cost safecoin to happen. Now though if we use the mod div rule here the attacker would manipulate a data item to cause the relocate, so we cannot do that. Instead we actually count data items stored and the version numbers of them all. This gives us a nice hard to game solution.

There are some small issues here though as this is ever growing so needs a small trick to deal with young nodes who will have an age less than total data, so this count has to be from a node appears until it ages and not simply total count of data if you see what I mean. Anyway that is a small (but important) issue.

Relocation mechanism

This is where there are a few ideas that complete/compliment and I think we can break them down as this.

Use the relocation trigger hash as random input to Algorithm.

Algorithm A - Use HDkeys

Here the node will be given some data and have to use this to create (very easily) a new public key based on this input data. This removes work from the key generation,

Pro - less work for node [ but we are not sure the work required is all that difficult anyway ]
Con - Does not allow balanced relocate [ We are not certain balanced relocate is required in large enough networks ]

Algorithm B - Use normal keys and force a range

Here we tell the node to create a key in a range of a section we will relocate them to. As we are defining the destination the network can target the section the node goes to.

Pro: Can allow balanced relocate [ again in large network may not be required]
Con: May be difficult when network is huge [ is this good or bad? ], also gives attacker some “space” to create a key in, they may find a pattern there that benefits them, such as selecting keys that will all split together (but we defeat that right now using the internal group range to locate the node to)]

These last 2 points are the one that we need to dig deeper into really, I don’t see any of them weaker than the other right now so we should dive deeper. I suspect the more scope an attacker has to create keys then that is the worst, but that opinion could rightly be challenged.

I hope this helps.

[Edit, in terms of key generation work, if we do switch to dalek rust lib for this (which I want to) then we can create approx 32 million keys per second on a commodity pc, which I think we can improve on, so I do not think that the “work” is going to be a blocker in any case. ]

[mav]

@dirvine

Con - [HDKeys] Does not allow balanced relocate [ We are not certain balanced relocate is required in large enough networks ]

I have added step 3a to the HDKeypair proposal

3a (option targeting step). Instead of generating one key at the random depth (eg key 185) the section can generate ten keys starting at the random depth (eg keys 185, 186, 187… 194). The ten sections corresponding to these pubkeys can be checked for their health and the one with the most need for a relocation can be selected.

Can Neighbours Be Removed?

The HDKeypair proposal requires eliminating the idea of neighbours. Is that even possible?

The good side of neighbours

Neighbours is a simple way to determine ‘the right to negotiate’. It’s easy for a section to check if a proposed relocation is valid, since it will come from a section in that neighbourhood. This neighbourhood check is very simple and fast (one bit different in the prefix).

Relocation requests can’t be spoofed because they’re signed by the neighbouring sections elders. Since all neighbour elders are already known by every neighbouring section it’s easy to verify their signatures without needing any extra network activity.

The bad side of neighbours

The problem with neighbours is relocations require brute-forcing a keypair that matches the neighbour section. There’s no simple operation to an existing privkey that allows it to produce a neighbouring pubkey. So brute force is required which scales exponentially and may cause problems for relocations on large networks.

Replacing Neighbours with HDKeypairs

Determining ‘the right to negotiate’ is very important, since it filters out the need for a lot of network activity. Only valid requests need to undergo the negotiation process. Random relocation means the neighbour check for validity of a relocation is no longer relevant; the request may come from anywhere on the network. There must be a fast local-only way to judge whether an incoming relocation has the right to negotiate.

This can be achieved with HDkeypairs. The request to relocate will contain the target vault’s current pubkey, current hdpubkey, and random depth chosen by the section. This allows the new section to derive the new pubkey and confirm it belongs to the section. If that derivation doesn’t fit the section, ‘the right to negotiate’ is lost and the request is rejected. If the derivation matches, the section can confirm the random depth is chosen correctly (maybe involving a datachain lookup) and the elder signatures match the elders of that section (via network lookup) and this would confirm the relocation validity.

This makes it hard to submit fake relocation requests to a section, even though the section has no idea who the elders are in the requesting section. If an attacker does decide to brute force a relocation request that’s valid but for a non-existing vault, the request would still be discarded after some network lookups to discover if the request contains data for vaults that don’t exist. The cost to create a fake request is much higher than the cost needed invalidate it (ie the cost of network lookups).

So I think whilst neighbour based relocation is great because it’s impossible to perform spoofed relocation attacks, random relocation via hdkeypairs is ‘very hard’ to the point where it should be unviable (needs further investigation of cost / benefit to this attack though).

Scaling performance as the network grows

I’ve been advocating very strongly to make it ‘easy to join’, but here I’m taking a step back and considering the other side (just leading with this disclaimer to avoid any confusion from mixed messages).

The number of neighbours grows with network size, and thus the number of connections to maintain also grows with network size.

There are also more hops required for every request to get to their destination. This takes more work to process each request.

So I think there is a strong case that as the network grows it should require more work before being able to join and participate, since there is more work required for completing the day-to-day operations. The added difficulty of brute-forcing longer and longer prefixes is actually not that bad, since vaults need to have higher performance just to do regular network operations.

Even though the individual actions that provide end-user operation don’t change in difficulty, the sum of those activities across the network does increase. So the individual actions must always be getting faster as the network grows to provide a consistent level of performance to users.

If vaults never improve their performance the network gets slower as it grows.

I do feel there’s a need for measured performance improvements of vaults as the network grows. This may come via punishment for not performing well enough, but maybe can be a little more proactive than that.

That’s not to say performance needs to improve exponentially (as required to brute-force pubkeys). It’s also not to say the fundamental operations should have built-in unscalable design.

My current thinking is the best balance for this problem is to implement constant-time fundamentals (eg HD key generation) with adjustable difficulties pinned to those operations (eg adjustable-difficulty PoW or PoStake or PoSignature or proof-of-X).

I’m proposing a decoupling, but I haven’t yet decided on words for the concepts being decoupled. This is still a primitive idea in my mind. But I can agree performance improvements need to be considered alongside improving inclusiveness.

As @Viv said in the other forum, “Allowing everyone to join with ease while it sounds great might also not be the best for the network if these nodes didn’t help much but increase the hops for general operation.”

[dirvine]

@mav

This can be achieved with HDkeypairs. The request to relocate will contain the target vault’s current pubkey, current hdpubkey, and random depth chosen by the section. This allows the new section to derive the new pubkey and confirm it belongs to the section. If that derivation doesn’t fit the section, ‘the right to negotiate’ is lost and the request is rejected. If the derivation matches, the section can confirm the random depth is chosen correctly (maybe involving a datachain lookup) and the elder signatures match the elders of that section (via network lookup) and this would confirm the relocation validity.

This is interesting and I agree, to add the neighbour based mechanism also does something else though. It makes secure message xfer … well secure. As a message goes from group to group (log n groups) then we can transfer messages across the network securely. This can include the members of a remote group amongst others (basically anything). So just to note that.

@mav

So I think whilst neighbour based relocation is great because it’s impossible to perform spoofed relocation attacks, random relocation via hdkeypairs is ‘very hard’ to the point where it should be unviable (needs further investigation of cost / benefit to this attack though).

100% agree.

@mav

The number of neighbours grows with network size, and thus the number of connections to maintain also grows with network size.

This is something we are aware of and I advocate as well. We talk a lot of small nodes joining and I agree, but also caveat that a small node in 5 years would be a supercomputer today (with moors law etc.). So I see your notion/dilemma/observation here but just a note that this network cannot design or accommodate fro today, but for tomorrow. So if the network grows huge in a few years the minimum requirement may seem high today, but tiny then. Like a RP3 is very powerful today compared with the rpi1. Never mind the efficiency savings code will make. Again though just a note.

@mav

If vaults never improve their performance the network gets slower as it grows.

So upgrades to hardware will follow network growth, if that makes sense.

@mav

I’m proposing a decoupling, but I haven’t yet decided on words for the concepts being decoupled. This is still a primitive idea in my mind. But I can agree performance improvements need to be considered alongside improving inclusiveness.

In the near future I see dynamic group sizes with varying requirements on ability, for now though I think this decoupling would be something we strive for. Not to delay launch as it wont, but to make the system simpler. I a hugely behind breaking things down and decoupling (even really enticing coupled algorithms).

Anyway, this is not so much an answer as a bunch of notions, that I hope helps.

[rreive]

poisson in French means fish. adapted to the SAFE network, what might works is we might want to think about “schooling” or containing the boundaries of the randomness generated by the poisson random distribution with advice (current and forward trending/predicted state of areas of the network) gleaned router information which considers a larger statistical sample of current network sickness or health in a randomized sampling of areas, ie- a couple of newly define areas which show up as sick areas would be also included in the bigger school with more than a couple of healthy areas with all of them treated together as the overall collective target (school) of possible candidates for relocation of the vault, so depending on the degree of sickness or health you can have the network randomly skew “the spew” of new vaults to the newly created school of targets, then have the network randomly and shortly thereafter take another random set of area samples of sick/health, which do include nearby areas as well sick and healthy to create a new set of targets for random vault relations

The key is to keep changing up the schools… in random time intervals

We did this to great effect @ Cloakware when I worked there to essentially create new builds of target mobile devices with different hardware and software associated locks for every release randomly distributing the distribution of the devices to different geo locations and through different channels, all the time at random intervals, so that even if one device got cracked (and it never did) is was would have to be with a huge supercomputer… Cloakware is now Iredeto (a Dutch/Chinese firm with the brains in Ottawa , Canada) but they have kept the Cloakware brand name, back in 2007 and 2008 we were doing this for the biggest company names that start with A and N for millions of mobile devices and collecting hack free bonuses per quarter doing it) The basic premise is the same only it would be done in real network time for SAFE, so this Poisson approach could definitely work for SAFE with some clever integration into what the routers know at the time visa vis network sickness/health to create a random fair relocation of the vault keeping anyone from dominating to win more Safecoin… again my 2 cents, nice suggestion! it surely would fit with what @mav is suggesting R2

[Fraser]

An interesting point for sure.

From my own perspective, I have a notion that this might better suit vaults with a track record rather than newly-joined ones. What I mean is that if we’re able to have the network maintain health metrics on sections of the network, it’d be well placed to identify optimal vaults to relocate so that the best balance is met (i.e. it doesn’t relocate an exceptionally healthy vault to a weaker area if that would cause the source section to become sicker than the target one)

Relocating vaults in any non-random way though always makes me twitchy! (in-house, I’m less a fan of targeted relocation than some of the rest of the team I think) It opens the door to attackers just that little bit wider

[digipl]

I’m wrong or are you proposing to completely eliminate the concept of neighbourhood in the Safe network? (Basically change an essential part of the Disjoin Sections RFC)

Because the concept of neighbourhood, as I see it, is more than “the right to negotiate”. It is the cornerstone that structures the entire network and, among other things, allows:

.-An uniform distribution and an structuration that allows to know the distance between groups, the right directions to send messages and the number of hops.
.-An split or join, of sections, with clear rules
.-A growth of the route table known in advance (one more section each time the network doubles in size).
.-An approximate idea of the total size of the network

I’m concerned about the possible negative consequences of such a fundamental change.
In fact, I still do not understand why can not use HDKeypairs for relocations (brilliant idea) while maintaining the concept of neighbourhood.

[rob]

@digipl

I’m wrong or are you proposing to completely eliminate the concept of neighbourhood in the Safe network?

I saw it as removing the neighbourhood (limitation) for relocating a node. This is what the proposal is about.

I didn’t see any need to remove neighbourhood for the other functionality/workings.

[Qi_Ma]

@mav : a superb post again

just wondering regarding the brutal force key generation part.
If the generating time is concerned, a vault could generate key-pairs in background thread during free time and pick-one that fits the relocation requirement.
So basically, with small sized network, the key-pairs is generated on-demand; with large sized network, key-pairs are prepared in advance.
This way, the storage capacity is also somehow get evaluated.

Also, as the vault needs to prepare key-pair each time got a prefix length changed, or after a relocation. So the vault is also under-taken measured performance improvements as the network grows while carry out normal network duty ?

[Fraser]

HDKeypairs is news to me, so I have a bunch of research to do there, but on the face of it sounds like a great solution. I’m personally in favour of random relocation for much the same reasons as @mav (reduced target address space and key generation expense), but as with many topics there’s loads of debate in-house about it. I agree with the keygen calculations in Data Chains - Deeper Dive - #28 by mav and actually wrote a quick test to confirm these.

Perhaps as @tfa suggests, a combination of random then targeted would be OK, although any deviation from pure random makes me uneasy.

There was an idea a while back (not even sure if it was discussed in-house, let alone properly documented) to have the section agree a random 256 bit number and this would be XORed with the relocating peer’s public key to provide its new address. This has the drawback of probably requiring the random portion to be part of the peer’s name, doubling the name’s size, but otherwise is conceptually similar in many ways to @mav’s proposal.

I’m less convinced about this though:

@mav

One possible proposal that works well within the existing design is to have elders each generate 256 random bits, and then XOR all these values together to get a combined random value V.

I think a single malicious vault would be able to wait for all its peers to present their random bytes, then craft its own bytes to suit whatever target address it wants. As @dirvine mentioned, the hash of a churn event or Put/Edit request is probably a better source.

[Viv]

@Fraser

a combination of random then targeted would be OK,

We were discussing this in the other forum too couple days back. but in that post was also meaning recursion for balance after the first hop.

@Fraser

As @dirvine mentioned, the hash of a churn event or Put/Edit request is probably a better source.

Still think this might have to almost be an AND of those factors rather than OR personally to prevent stalling, but want to see how the simulation results come out to give that some context. Hopefully @bart gets those soon-ish

[mav]

@digipl

are you proposing to completely eliminate the concept of neighbourhood in the Safe network

No. Sorry I missed a vital bit of context to the post:

“The HDKeypair proposal requires eliminating the idea of neighbours for relocations.”

Thanks for bringing up this ambiguity.

The current secure messaging using neighbours would still apply to all other messaging.

I admit to slightly overreaching on the relocation request idea. Using a different messaging mechanism is probably not necessary and it’s probably better to just use the existing messaging. But I wanted to put the idea out because who knows what it might influence in other ways.

@Qi_Ma

If the generating time is concerned, a vault could generate key-pairs in background thread during free time and pick-one that fits the relocation requirement.

Agreed. Key generation can happen in the background which is a nice property to have, especially since unused keys may be kept and used later if needed. No work need ever be discarded.

But there’s no bound on what keys are needed, since neighbours may be found recursively so it’s not enough just to generate a key for each current neighbour section.

This means there should always be a constant background thread finding keys. That seems a bit ugly.

It eventually leads to the unpleasant idea that if the network becomes very large there’ll probably be a ‘market for keys’ pop up where you’ll be able to buy a key matching the relocation section from someone who has brute forced it on powerful specialized hardware. This breaks security because the private key is no longer secret. Who would buy a key?! The same people who set their bitcoin transaction fees to 0 then wonder why ‘it doesn’t work’… I think someone just wanting to earn safecoin would gladly buy a precomputed key if it means they can remove a roadblock to earning more safecoin. Overall I think the pubkey-brute-force concept potentially comes with some very ugly incentives.

My main point with hdkeypairs is not so much ‘can it be made cheaper’ but ‘we should use constant time instead of linear or exponential time algorithms’ where we can. It’s a scalability thing, not an economics thing.

@Qi_Ma

the vault is also under-taken measured performance improvements as the network grows while carry out normal network duty ?

True, but the performance for ‘generate a keypair’ isn’t really meaningful to the day-to-day requirement of ‘managing data’. So I think separating ‘measuring performance’ from ‘network operations’ is a good idea. It’s a bit arbitrary to use keypair generation as measure for performance.

@Fraser

I think a single malicious vault would be able to wait for all its peers to present their random bytes, then craft its own bytes to suit whatever target address it wants.

Good point. Agreed.

@Fraser

I agree with the keygen calculations in Data Chains - Deeper Dive and actually wrote a quick test to confirm these.

I have also done a quick test using iancoleman/ed25519_brute_force (which uses rust_sodium).

2014 laptop  i7-4500U @ 1.80GHz - 5851 keys per second

2017 desktop i7-7700  @ 3.60GHz - 9119 keys per second

Might tidy up the reporting a bit and put it on the main forum to crowdsource some data.

[dirvine]

@mav

My main point with hdkeypairs is not so much ‘can it be made cheaper’ but ‘we should use constant time instead of linear or exponential time algorithms’ where we can. It’s a scalability thing, not an economics thing.

I suspect this point is critical in your proposal and not really understood.

We did a bit of testing today and 10,000 keys per second with dalek (nightly) seems reasonable. Be nice to test that on a rpi3, I may run one up.

Also using the hash of mutation events and churn events will give us the random data for depth. This will be an agreed (consensus) ransom data element.