3.2. Poset¶
This module implements a poset - a core data structure.
-
class
aleph.data_structures.poset.Poset(n_processes, process_id=None, crp=None, use_tcoin=None, compliance_rules=None)¶ This class is the core data structure of the Aleph protocol.
- Parameters
n_processes (int) – the committee size
process_id (int) – the id of the process owning this poset
crp (CommonRandomPermutation) – an object returning the common random permutation of processes at a given level
use_tcoin (bool) – whether to use threshold coin, mostly so we can disable it for tests
compliance_rules (dict) – a dictionary describing which compliance_rules to use
-
above(U, V)¶ Checks if U >= V.
-
above_within_process(U, V)¶ Checks if there exists a path (possibly U = V) from V to U going only through units created by their creator process. Assumes that U.creator_id = V.creator_id = process_id
Adds coin shares to the prime unit U using the simplified strategy: add the coin_share determined by FAI(U, U.level) to U
- Parameters
U (Unit) – prime unit to which coin shares are added
-
add_tcoin_to_dealing_unit(U)¶ Adds threshold coins for all processes to the unit U. U is supposed to be the dealing unit for this to make sense. NOTE: to not create a new field in the Unit class the coin_shares field is reused to hold treshold coins in dealing units. (There will be no coin shares included at level 0 anyway.)
-
add_unit(U)¶ Add a unit compliant with the rules, what was checked by check_compliance. This method does the following: 0. add the unit U to the poset 1. if it is a dealing unit, add it to self.dealing_units 2. update the lists of maximal elements in the poset. 3. update forking_height 4. if U is prime, add it to prime_units_by_level
- Parameters
U (Unit) – unit to be added to the poset
-
attempt_timing_decision()¶ Tries to find timing units for levels which currently don’t have one. :returns: List of timing units that have been established by this function call (in the order from lower to higher levels)
-
below(U, V)¶ Checks if U <= V.
-
below_within_process(U, V)¶ Checks if there exists a path (possibly U = V) from U to V going only through units created by their creator process. Assumes that U.creator_id = V.creator_id = process_id
-
break_ties(units_list)¶ Produce a linear ordering on the provided units. It is a slightly different implementation than in the arxiv paper to avoid using xor which turns out to be very slow in python. Essentially a sha3 hash is used in place of xor.
- Parameters
units_list (list) – the units to be sorted, should be all units with a given timing round
- Returns
the same set of units in a list ordered linearly
Checks coin shares of a prime unit that is not a dealing unit. This boils down to checking if U has exactly one share if its level is >= consts.ADD_SHARES and zero shares otherwise. At this point there is no point checking whether the share is correct, because that might be because of an dishonest dealer.
- Parameters
U (Unit) – the unit whose shares we are checking
- Returns
True if there is the appropriate number of shares, False otherwise
-
check_compliance(U)¶ Assumes that prepare_unit(U) has been already called. Checks if the unit U is correct and follows the rules of creating units, i.e.: 1. Parents of U are correct (exist in the poset, etc.) 2. U does not provide evidence of its creator forking 3. Satisfies forker-muting policy. 4. Satisfies the expand primes rule. 5. The coinshares are OK, i.e., U contains exactly the coinshares it is supposed to contain.
- Parameters
U (Unit) – unit whose compliance is being tested
- Returns
True if all the checks passed, False otherwise
-
check_expand_primes(U)¶ Checks if the unit U respects the “expand primes” rule. Parents are checked consecutively. The first is just accepted. Then let L be the level of the last checked parent and P the set of prime units of level L below all the parents checked up to now. The next parent must must either have prime units of level L below it that are not in P, or have level greater than L.
- Parameters
U (Unit) – unit that is tested against the expand primes rule
- Returns
Boolean value, True if U respects the rule, False otherwise.
-
check_forker_muting(U)¶ Checks if the unit U respects the forker-muting policy, i.e.: The following situation is not allowed: - There exists a process j, s.t. one of U’s parents was created by j AND - U has as one of the parents a unit that has evidence that j is forking.
- Parameters
U (Unit) – unit that is checked for respecting anti-forking policy
- Returns
Boolean value, True if U respects the forker-muting policy, False otherwise.
-
check_no_self_forking_evidence(U)¶ Checks if the unit U does not provide evidence of its creator forking.
- Parameters
U (Unit) – the unit whose forking evidence is being checked
- Returns
Boolean value, True if U does not provide evidence of its creator forking
-
check_parent_correctness(U)¶ Checks whether U has correct parents: 0. Parents of U exist in the poset 1. The first parent was created by U’s creator and has one less height than U. 2. If U has >=2 parents then all parents are created by pairwise different processes.
- Parameters
U (Unit) – unit whose parents are being checked
- Returns
Boolean value, True if U satisfies the above conditions, False otherwise.
-
check_threshold_coin_included(U)¶ Checks whether the dealing unit U has a threshold coin included. We cannot really check whether it is valid (since the secret keys are encrypted). Instead, we simply make sure whether the dictionary has all necessary fields and the corresponding lists are of appropriate length.
- Parameters
U (Unit) – the unit to check
- Returns
Boolean value, True if U’s threshold coin is correct, False otherwise.
How many coin shares are needed to flip a threshold coin. :returns: the amount of shares needed
-
combine_floors_per_process(units_list, process_id)¶ Combines U.floor[process_id] for all units U in units_list. The result is the set of maximal elements of the union of these lists.
- Parameters
units_list (list) – list of units to be considered
process_id (int) – identification number of a process
- Returns
list U that contains maximal elements of the union of floors of units_list w.r.t. process_id
-
compute_delta(U_c, U)¶ Computes the value of the Delta function from the paper. The value -1 is equivalent to bottom (undefined).
-
compute_pi(U_c, U)¶ Computes the value of the Pi function from the paper. The value -1 is equivalent to bottom (undefined). :param Unit U_c: the unit which we are deciding about :param Unit U: the unit that is making the decision :returns: 0, 1 or -1, as defined in the whitepaper
-
compute_vote(U, U_c)¶ Determine the vote of unit U on popularity of U_c. If the first round of voting is at level L then: - at lvl L the vote is just whether U proves popularity of U_c (i.e. whether U_c <<< U) - at lvl (L+1) the vote is the supermajority of votes of prime ancestors (at level L) - at lvl (L+2) the vote is the supermajority of votes (replaced by default_vote if no supermajority) of prime ancestors (at level L+1) - etc.
-
decide_timing_on_level(level)¶ Decide which prime unit of the given level shall be the timing unit.
- Parameters
level (int) – the level about which we are inquiring
- Returns
the timing unit at this level or (-1) in case when no unit can be chosen yet
-
decide_unit_is_popular(U_c)¶ Decides popularity of U_c (i.e. whether it should be a candidate for a timing unit).
- Parameters
U_c (Unit) – the unit whose popularity we want to investigate
- Returns
one of {-1,0,1}: the decision (0 or 1) in case it follows from our local view of the poset, or -1 if the decision cannot be inferred yet
-
default_vote(U, U_c)¶ Default vote of U on popularity of U_c, as in the fast consensus algorithm.
-
dump_to_file(file_name)¶ Dumps the poset to file in a rather simple format. Units are listed in the same order as the were added to the poset. In addition to parents and creator_id we also include info about the level of each unit and a bit 0/1 whether the unit was a timing unit.
- Parameters
file_name (str) – the name of the file in which the poset is to be saved
-
exists_tc(list_vals, U_c, U_tossing)¶ Computes the exists function from the whitepaper, including the coin toss if necessary.
- Parameters
- Returns
1 or 0 if it is on the list provided, with preference for 1, otherwise the result of the shared coin toss
-
extract_tcoin_from_dealing_unit(U)¶ Extracts and stores the threshold coin from a given unit.
- Parameters
U (Unit) – the dealing unit from which we are extracting the coin
-
first_dealing_unit(V)¶ Returns the first dealing unit (sorted w.r.t. crp at level level(V)) that is below V.
- Parameters
V (Unit) – the unit below which we are looking for a dealing unit
-
get_all_prime_units_by_level(level)¶ Returns a list of all prime units at a given level.
- Parameters
level (int) – the requested level of units
-
get_prime_units_at_level_below_unit(level, U)¶ Returns the set of all prime units at a given level that are below the unit U.
- Parameters
level (int) – the requested level of units
U (Unit) – the unit below which we want the prime units
-
get_prime_units_by_level_per_process(level)¶ Returns a list of all prime units at a given level divided by process. For nonforking processes this should be a list of one-elements lists. :param int level: the requested level of units
-
has_forking_evidence(U, process_id)¶ Checks if U has in its lower cone an evidence that process_id is forking.
- Parameters
U (Unit) – unit to be checked for evidence of process_id forking
process_id (int) – identification number of process to be verified
- Returns
True if forking evidence is present, False otherwise
-
is_prime(U)¶ Check if the unit is prime.
- Parameters
U (Unit) – the unit to be checked for being prime
-
is_quorum(number)¶ Check whether the given number is enough to form a quorum. :returns: True or False
-
level(U)¶ Calculates the level in the poset of the unit U.
- Parameters
U (Unit) – the unit whose level is being requested
- Returns
the computed level
-
precompute_popularity_proof(V)¶ Precomputes the popularity proof for V, to avoid computing many popularity proofs at once. Tries to prove the popularity of the first unit in the common random permutation that is below V.
- Parameters
V (Unit) – the “prover” unit
-
prepare_unit(U)¶ Sets basic fields of U; should be called prior to check_compliance and add_unit methods. This method does the following: 0. set floor field 1. set U’s level
-
proves_popularity(V, U_c)¶ Checks whether V proves that U_c is popular on V’s level (i.e. everyone sees U on this level). More specifically we check whether there are >=2/3 N units W (created by distinct processes) such that 1. W <= V, 2. W has level <=level(V) - 2, or W is a prime unit at level(V)-1, 3. U_c <= W.
-
should_check_rule(rule)¶ Check whether the rule (a string) “forker_muting”, “expand_primes”, etc. should be checked in the check_compliance function. Based on the combination of default values and the compliance_rules dictionary provided as a parameter to the constructor.
- Parameters
rule (str) – the name of the rule to check
- Returns
whether to check the rule
-
super_majority(list_vals)¶ Computes the supermajority function from the whitepaper.
- Parameters
list_vals (list) – the list of values among which we are checking for supermajority
- Returns
1 or 0 if either is a supermajority value on the list provided, -1 (representing bot) if neither is
-
timing_round(k)¶ Return a list of all units with timing round equal k. In other words, all U such that U < T_k but not U < T_(k-1) where T_i is the i-th timing unit.
- Parameters
k (int) – the level of the timing round requested
-
toss_coin(U_c, U_tossing)¶ The coin toss at unit U_tossing (necessarily at level >= consts.ADD_SHARES + 1) With low probability the toss may fail – typically because of adversarial behavior of some process(es).
- Parameters
U_c (unit) – the unit whose popularity decision is being considered by tossing a coin this param is used only in case when the _simple_coin is used, otherwise the result of coin toss is meant to be a function of U_tossing.level only
U_tossing (unit) – the unit that is cossing a toin
- Returns
One of {0, 1} – a (pseudo)random bit, impossible to predict before (U_tossing.level - 1) was reached
-
update_floor(U)¶ Updates floor of the unit U by merging and taking maximums of floors of parents.
- Parameters
U (Unit) – the unit whose floors are being updated
Checks whether the coin share of U agrees with the dealt public key. Note that even if it does not, it does not follow that U.creator_id is adversary – it could be that dealer_id is the cheater.
- Parameters
U (Unit) – the unit whose coin shares are being checked
- Returns
True if the coin share is verified successfully, False otherwise