Secure Random Relocation

I agree with both these points.

I ran your test here (although I changed it to use a newer version of rust_sodium since 0.2 doesn’t build libsodium on Windows by default):

desktop i7-2600K @ 3.40GHz - 21317 keys per second

I ran it with --release. Not sure if you did too (the readme doesn’t mention it), but it shouldn’t make much difference since the actual work is being done by the C lib which is already compiled/installed in release mode. Of course, if you test a pure Rust implementation (e.g. Dalek) this will make a huge difference :smiley:

3 Likes

Yes - I can see the appeal. I think this would be a very gnarly job, both from the perspective of what metrics can/should be used to measure health, and how the network can make use of that information securely. Certainly worth fuller consideration a bit further down the line as far as I’m concerned!

1 Like

Just for perspective. The creation of keys is say 30,000 ns, signing is 40,000ns and verifying is circa 100,000ns.A node will have to sign and verify huge numbers of messages as the network grows.

The point is still valid though, that constant time for relocate is neat feature.

4 Likes

Yes thanks for those figures.

as you say the point is to verify that a Node can do these things. But brute-force a key pair is not a normal function of the Node’s operations. Is it?? And a brute-force requires a lot of key gens just to get the small portion matching. Is there an estimate of how many gens (on average) would be required for a small network and for a large one?

2 Likes

I ran Dalek and got about 30K keypairs / second, so about 3 times faster.

2 Likes

It has been in testnets so far.

In a small network of 2 sections the keygen would take 6ms if there were 100,000 sections (say 2 million node network) then the keygen could take about 2 mins, however if we dictate the range within a section this could go up to several 10’s of minutes

see this link for initial working from Ian as well. Data Chains - Deeper Dive

3 Likes

If we use that with the sha3 hash lib we use then it will be faster again, possibly another 2-3 times faster. I may give it a shot.

1 Like

I was meaning that the brute-force is only there for this relocation function and I gather its not used for what we expect of the Node’s operations in the network and vault.

So about 20 gens (30uS each)

And I can already hear the cries of wasting energy with the CPU intensive work nodes have to do :stuck_out_tongue:

3 Likes

Interesting. When I ran my test earlier, Dalek was about twice as slow as sodium when I built with stable Rust (1.23.0) and only a little faster (less than 10%) when I used the latest nightly compiler (1.25.0)! When I mentioned a huge difference, I was meaning comparing debug vs release.

If the Dalek code is going to get pushed to your repo, I’ll try it here too?

I tried that earlier too, and it made almost no difference. I expect it’ll come into play more with the signing/verification.

4 Likes

No that was prob a mistake (don’t do maths and flu together). It would be normally 1-2 gens so 30-60microsecs

3 Likes

And for 100,000 sections it would still be pretty fast: 3 or 4 seconds.

3 Likes

My Dalek results are not from my repo…

$ git clone https://github.com/isislovecruft/ed25519-dalek.git
$ $ cargo bench --features="bench"
...
test ed25519::bench::key_generation  ... bench:  32,651 ns/iter (+/- 760)
...
2 Likes

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:

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.” :slight_smile:

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