Secure Random Relocation

Yes this is why I am not sure of the term brute force as it gives the impression that it is a significant workload. WE also must consider machine capabilities going forward as they should be increasing quickly sans meltdown and spectre of course :smiley:


19500ns on my machine (i7 3.4 Ghz). just fyi


Ah - I’ve not gone through her code - just a quick skim earlier, but I noticed that her keygen benchmark looks a bit suspect. Specifically the use of the ZeroRng which is “A fake RNG which simply returns zeroes.” :slight_smile:


I see your point about brute force, but it does seem to me like the right term for what we’re doing. We’re not using any sort of algorithm to optimise the number of attempts we make - we’re just taking random shots until one finally scores.


True, but the max force required is the gen time * num sections, if the keys produced are random and equally distributed across the address range. The optimisation is using the fastest method to do that;-) So its not like trying to guess a password.


This is a table of the number of guesses required to generate a key with a certain prefix length (code here).

So to have a 90% chance of guessing a 7-bit prefix means generating 294 keypairs. This corresponds to a network size of about 6K vaults.

              | probability of generating a valid key  |
              |      0.1      0.5    0.9   0.99 0.9999 |              
Prefix Length |                                        | Sections Vaults
            3 |        1        5     17     34     69 |      8    400
            4 |        2       11     36     71    143 |     16    800
            5 |        3       22     73    145    290 |     32     2K
            6 |        7       44    146    292    585 |     64     3K
            7 |       13       88    294    587     1K |    128     6K
            8 |       27      177    588     1K     2K |    256    13K
            9 |       54      355     1K     2K     5K |    512    26K
           10 |      108      709     2K     5K     9K |     1K    51K
           11 |      216       1K     5K     9K    19K |     2K   102K
           12 |      432       3K     9K    19K    38K |     4K   205K
           13 |      863       6K    19K    38K    75K |     8K   410K
           14 |       2K      11K    38K    75K   151K |    16K   819K
           15 |       3K      23K    75K   151K   302K |    33K     2M
           16 |       7K      45K   151K   302K   604K |    66K     3M
           17 |      14K      91K   302K   604K     1M |   131K     7M
           18 |      28K     182K   604K     1M     2M |   262K    13M
           19 |      55K     363K     1M     2M     5M |   524K    26M
           20 |     110K     727K     2M     5M    10M |     1M    52M
           21 |     221K       1M     5M    10M    19M |     2M   105M
           22 |     442K       3M    10M    19M    39M |     4M   210M
           23 |     884K       6M    19M    39M    77M |     8M   419M
           24 |       2M      12M    39M    77M   155M |    17M   839M
           25 |       4M      23M    77M   155M   309M |    34M     2B
           26 |       7M      47M   155M   309M   618M |    67M     3B
           27 |      14M      93M   309M   618M     1B |   134M     7B
           28 |      28M     186M   618M     1B     2B |   268M    13B
           29 |      57M     372M     1B     2B     5B |   537M    27B
           30 |     113M     744M     2B     5B    10B |     1B    54B
           31 |     226M       1B     5B    10B    20B |     2B   107B
           32 |     453M       3B    10B    20B    40B |     4B   215B
           33 |     905M       6B    20B    40B    79B |     9B   429B
           34 |       2B      12B    40B    79B   158B |    17B   859B
           35 |       4B      24B    79B   158B   316B |    34B  1718B
           36 |       7B      48B   158B   316B   633B |    69B  3436B
           37 |      14B      95B   316B   633B  1266B |   137B  6872B
           38 |      29B     191B   633B  1266B  2532B |   275B 13744B
           39 |      58B     381B  1266B  2532B  5063B |   550B 27488B
           40 |     116B     762B  2532B  5063B 10127B |  1100B 54976B

My logic for this table:

Define L as the number of bits in the prefix

Chance of a single key generation being a match

Chance of it not being a match

Chance of nth try not being a match

Chance of nth try being a match
p = 1-(1-1/2^L)^n

rearrange to find n for chance p of a match

1-p = (1-1/2^L)^n

log(1-p) = n * log(1-1/2^L)

n = log(1-p) / log(1-1/2^L)


If you are specifying the section to get key for then it is similar to brute-force a password.

Two sections is like brute force of 1 bit password. 256 sections is like brute-force of a one character password etc.

Not specifying the section would remove the brute-force label though.

And HD keys would be clean and no “lets gen a key and see if it fits” uncouth way.

Thanks for that @mav


Yea I see that different. With this logic if we fill an array of 32 bytes in a loop then it would be brute force filling an array. To me brute force would be a significant & unknown amount of work and time.

I think here there is possibly more work involved if we force relocation section but less work involved if we used an HDkey to get that section. However the relocating group has a wee bit more work as it then has to get the key from the peer when it is created, agree to it (via consensus) and then send the messages to the new group to expect this peer. If we choose a section and send the expect message to the new section, then the peer does the extra work.


Nice work chap, It may be simpler though. I mean if the network splits into X sections then to get into a section we should only need to generate a max of X keys to get into a section. Well if the key generation is random (as random as SHA etc.).


It’s like bitcoin mining though. You never know what the start of the public key is so you just have to keep trying. Sometimes you’ll be unlucky and it takes more than X guesses. The 50% column is the best one to use since it represents the average number of guesses to find a key.


I guess that’s where using a random byte array provided by the source section and XORing this with the public key would win over the HDKeypairs approach - there’d be mininal cost to the target section and the relocating peer.

The random relocation will have an extra cost of usually being multi-hop, but all these costs will probably be insignificant compared to the effort required to bring the relocated peer up to date once it connects to the target section.


I think the issue is different here. we only need a pub-key with a predictable pattern, which allows us to carry out guess in advance.

As mentioned above. so basicaly you just create a look-up list, and put any key-pair you generated into it, filter out those fall in the same prefix length.
Then when you being asked to relocate, you only need to pick any stored key that having same or longer prefix-length.

A 1GB look-up list could gives you 16M entry slots (only need to store priv-key, assumed to be 512 bits long), i.e. 16M sections. That’s a network size over 0.8B (avg 50 nodes per section as in your table)
And this file can be further indexed by a 2MB block, with each bit represents whether the slot contains a candidate or not.

1 Like

So, you’re saying if our section’s Prefix is e.g. 000, we cache a total of 8 keys, one for each of 000, 001, … 111 on the reasonable assumption that all sections across the network have the same prefix length as us? Then if our section splits, we create more keys until we have a total of 16 cached covering 0000, 0001, … 1111?

So you mean we generate a key pair and if the public key matches an empty slot in this key cache file we store only the private key in the cache? Then if we need it, we regenerate the public key from the private one?

Assuming I’m understanding this approach correctly, I’m not really that keen on it to be honest. I don’t like the cost of the background keygen work, nor the overhead of managing the cache (we’d presumably want to encrypt the cache file if it contains a pile of private keys?) Also, come time to relocate, if the cache didn’t contain a suitable key we’d be stuck with having to create a keypair on the fly, i.e. more or less back at square one.


it does’t store 8 keys first, then 16 keys, then going on. It just assume the max prefix length at beginning and then store any keys. i.e. we store 01011101110100111000110001... at the beginning, then use it for 010 or 01011 etc.

This is kind of sacrifice space for time, and does have the risk of miss hit when network grows super large (unless you want to create a super large lookup file)

I agree this may incur other concerns, such as protection of private key. So this shall be totally optional.

Regarding store private key only, seems I am wrong with that. It has to be the key-pair to be stored. :frowning:
Then in this case it shall be a seed to be stored, and the user has to use a seeded key generator?

1 Like

No, I think libsodium provides the functionality to extract the seed and public key from just the private key. I’m pretty sure that’s not exposed through rust_sodium, but it should be trivial to add it.


Maybe just worth mentioning here about an orthogonal case which could make using HDKey(like) concept more difficult: there’s a rule that each time you get from Adult to Elder (promotion) you need to come up with a new Public-key (which is your ID) in order to make the Live/Gone blocks unique and non-replayable. This new Key ofc has to be chosen in the range given by the Elders who are promoting you and you will need to permute to fit that range. Without this you can have, within the same current prefix, Live(A) -> ... -> Gone(A) -> ... -> Live(A) where Gone(A) can now be replayed (or even Live(A)). So to make it unique, the currently discussed plan is to have Live(A) -> .. -> Gone(A) -> .. -> Live(A-new) -> .. -> Gone(A-new) -> .. -> Live(A-new-new) kind of a strategy. If we stick to this rule then we were contemplating that there will be places where we would require iterative key-generation to fit a range anyway.


Again, the random bytes XORed with the existing public key would allow for unique Live blocks at minimal cost to all involved. In this case, the leading (most significant) bits of the random data would be tweaked to ensure the promoted peer’s new ID fits the target address range.


Yes with a slight side-effect of your ID no longer being you public-key (requiring a separate ID by XORing PK+RandXOR and actual PK to verify us) - which may/may-not be that bad a thing.

This is the part that makes me most uncomfortable about the background work - somehow in my mind it’s highly likely to not fit once a range constraint is given.


I am unconvinced that the work required to generate the correct key is beyond what a node should be able to do easily.