diff options
author | Martin Schanzenbach <schanzen@gnunet.org> | 2023-10-19 09:54:35 +0200 |
---|---|---|
committer | Martin Schanzenbach <schanzen@gnunet.org> | 2023-10-19 09:54:35 +0200 |
commit | 98c00bad3d29a80c514818615c224a29307400cc (patch) | |
tree | 75681e421f4aec753eb509c037ed6e353447cc73 /src/consensus/consensus-simulation.py.in | |
parent | b7a1d4379ebcff1c878d068cbd8df34fd16d81d4 (diff) | |
download | gnunet-98c00bad3d29a80c514818615c224a29307400cc.tar.gz gnunet-98c00bad3d29a80c514818615c224a29307400cc.zip |
BUILD: Move set/consensus/secretsharing to contrib/service
Diffstat (limited to 'src/consensus/consensus-simulation.py.in')
-rw-r--r-- | src/consensus/consensus-simulation.py.in | 112 |
1 files changed, 0 insertions, 112 deletions
diff --git a/src/consensus/consensus-simulation.py.in b/src/consensus/consensus-simulation.py.in deleted file mode 100644 index 272a52da2..000000000 --- a/src/consensus/consensus-simulation.py.in +++ /dev/null | |||
@@ -1,112 +0,0 @@ | |||
1 | #!@PYTHONEXE@ | ||
2 | # This file is part of GNUnet | ||
3 | # (C) 2013, 2018 Christian Grothoff (and other contributing authors) | ||
4 | # | ||
5 | # GNUnet is free software: you can redistribute it and/or modify it | ||
6 | # under the terms of the GNU Affero General Public License as published | ||
7 | # by the Free Software Foundation, either version 3 of the License, | ||
8 | # or (at your option) any later version. | ||
9 | # | ||
10 | # GNUnet is distributed in the hope that it will be useful, but | ||
11 | # WITHOUT ANY WARRANTY; without even the implied warranty of | ||
12 | # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
13 | # Affero General Public License for more details. | ||
14 | # | ||
15 | # You should have received a copy of the GNU Affero General Public License | ||
16 | # along with this program. If not, see <http://www.gnu.org/licenses/>. | ||
17 | # | ||
18 | # SPDX-License-Identifier: AGPL3.0-or-later | ||
19 | |||
20 | import argparse | ||
21 | import random | ||
22 | from math import ceil, log, floor | ||
23 | |||
24 | |||
25 | def bsc(n): | ||
26 | """ count the bits set in n""" | ||
27 | l = n.bit_length() | ||
28 | c = 0 | ||
29 | x = 1 | ||
30 | for _ in range(0, l): | ||
31 | if n & x: | ||
32 | c = c + 1 | ||
33 | x = x << 1 | ||
34 | return c | ||
35 | |||
36 | |||
37 | def simulate(k, n, verbose): | ||
38 | assert k < n | ||
39 | largest_arc = int(2**ceil(log(n, 2))) // 2 | ||
40 | num_ghosts = (2 * largest_arc) - n | ||
41 | if verbose: | ||
42 | print("we have", num_ghosts, "ghost peers") | ||
43 | # n.b. all peers with idx<k are evil | ||
44 | peers = list(range(n)) | ||
45 | info = [1 << x for x in range(n)] | ||
46 | |||
47 | def done_p(): | ||
48 | for x in range(k, n): | ||
49 | if bsc(info[x]) < n - k: | ||
50 | return False | ||
51 | return True | ||
52 | |||
53 | rounds = 0 | ||
54 | while not done_p(): | ||
55 | if verbose: | ||
56 | print("-- round --") | ||
57 | arc = 1 | ||
58 | while arc <= largest_arc: | ||
59 | if verbose: | ||
60 | print("-- subround --") | ||
61 | new_info = [x for x in info] | ||
62 | for peer_physical in range(n): | ||
63 | peer_logical = peers[peer_physical] | ||
64 | peer_type = None | ||
65 | partner_logical = (peer_logical + arc) % n | ||
66 | partner_physical = peers.index(partner_logical) | ||
67 | if peer_physical < k or partner_physical < k: | ||
68 | if verbose: | ||
69 | print( | ||
70 | "bad peer in connection", peer_physical, "--", | ||
71 | partner_physical | ||
72 | ) | ||
73 | continue | ||
74 | if peer_logical & arc == 0: | ||
75 | # we are outgoing | ||
76 | if verbose: | ||
77 | print(peer_physical, "connects to", partner_physical) | ||
78 | peer_type = "outgoing" | ||
79 | if peer_logical < num_ghosts: | ||
80 | # we have a ghost, check if the peer who connects | ||
81 | # to our ghost is actually outgoing | ||
82 | ghost_partner_logical = (peer_logical - arc) % n | ||
83 | if ghost_partner_logical & arc == 0: | ||
84 | peer_type = peer_type + ", ghost incoming" | ||
85 | new_info[peer_physical] = new_info[peer_physical] | info[ | ||
86 | peer_physical] | info[partner_physical] | ||
87 | new_info[partner_physical | ||
88 | ] = new_info[partner_physical] | info[ | ||
89 | peer_physical] | info[partner_physical] | ||
90 | else: | ||
91 | peer_type = "incoming" | ||
92 | if verbose > 1: | ||
93 | print("type of", str(peer_physical) + ":", peer_type) | ||
94 | info = new_info | ||
95 | arc = arc << 1 | ||
96 | rounds = rounds + 1 | ||
97 | random.shuffle(peers) | ||
98 | return rounds | ||
99 | |||
100 | |||
101 | if __name__ == "__main__": | ||
102 | parser = argparse.ArgumentParser() | ||
103 | parser.add_argument("k", metavar="k", type=int, help="#(bad peers)") | ||
104 | parser.add_argument("n", metavar="n", type=int, help="#(all peers)") | ||
105 | parser.add_argument("r", metavar="r", type=int, help="#(rounds)") | ||
106 | parser.add_argument('--verbose', '-v', action='count') | ||
107 | |||
108 | args = parser.parse_args() | ||
109 | sum = 0.0 | ||
110 | for n in range(0, args.r): | ||
111 | sum += simulate(args.k, args.n, args.verbose) | ||
112 | print(sum // args.r) | ||