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 
3 Likes
19500ns on my machine (i7 3.4 Ghz). just fyi
2 Likes
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.” 
3 Likes
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.
2 Likes
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.
2 Likes
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
1/2^L
Chance of it not being a match
1-1/2^L
Chance of nth try not being a match
(1-1/2^L)^n
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)
5 Likes
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
3 Likes
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.
4 Likes
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.).
3 Likes
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.
4 Likes
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.
3 Likes
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.
2 Likes
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. 
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.
2 Likes
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.
2 Likes
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.
3 Likes
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.
2 Likes
I am unconvinced that the work required to generate the correct key is beyond what a node should be able to do easily.
4 Likes