| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
8 | Authors: @aparnalocked, @AlexisGauba, @snarkyzk, @MaazUddin11, @mechanism_labs | |||||||||||||||||||||||
9 | Created by Mechanism Labs | Tendermint | Thunderella | Algorand (Gilad) | Casper FFG | Dfinity | Ouroboros Genesis | Casper TFG | ||||||||||||||||
10 | Model | Network Synchrony model | Partial Synchrony in proposal & asynchrony in rounds once block is proposed | Asynchronous optimistic fast path with fully synchronous underlying blockchain thus the protocol is ultimately synchronous | Safety under partial synchrony such that after an asynchronous period, the network must be strongly synchronous for a reasonably long period again. The protocol ensures liveness under synchrony. | Does not provide a comprehensive discussion of synchrony, but states that all clients have local clocks that are perfectly synchronized with any discrepancy treated as part of a known communication delay. | Practically operates in partial synchrony, however is only formally proven in synchrony. | Guarantees safety under semi-synchrony | Asynchronous safety in that blocks won't be reverted due to the arbitrary timing of future events, and provides liveness given some synchrony assumption | |||||||||||||||
11 | Adversarial Model | Mildly adaptive advesary controlling up to 1/3 classically Byzantine nodes. | Mildly adaptive adversary handling adaptive security with erasures in the random oracle model. The adversary is in charge of scheduling message delivery such that they cannot modify contents broadcast by honest parties, but can reorder and delay them. | Tolerates an adversary between a mildly adaptive and strongly adaptive adversary in that the adversary may temporarily fully control the network and immediately corrupt users in targeted attacks because of immediate player replaceability. | Does not discuss the idea of an adversary. If attackers wholly control the proposal mechanism, Casper protects against finalizing two conflicting checkpoints, but the attackers could prevent Casper from finalizing any future checkpoints. | The protocol can tolerate a mildly adaptive adversary. | Slightly less than strongly adaptive adversary under assumption of majority stake being held and upper bound on message delay (∆). Adversay can corrupt any participant at any moment. Desynchronised parties have their stake counted as adversarial until at least some d rounds pass and they are considered fully synchronized again | Safety proof holds with arbitrary byzantine behavior and the types of Byzantine behavior nodes might see include crash faults, nodes generating invalid messages, and equivocation | ||||||||||||||||
12 | ||||||||||||||||||||||||
13 | General Solution - Steps and Challenges | Proposer / Committee Election & Random Generation | Tendermint has a new proposer every round, however, this proposer is not selected through randomness. Rather, the proposer is elected via deterministic round robin between validators (those who have staked) such that there is one proposer per round who proposes a block. Given the deterministic nature of proposer selection, network participants can determine who the proposer is in any given round. The committee is likewise deterministically selected and composed of validators. Validators are those who have deposited their coins to a contract, demonstrating their willingness to participate in the network as validators. There is no randomness being generated as part of this process. | Thunderella elects a proposer in the BFT overlay subset of the protocol, however the specific method of selecting a proposer is decided by the implementing application. Committee Selection methods are also left up to the decision of the application as well, however three different options are suggested: 1) Implement a Random Oracle which is secure against slow corruptions either using a hash function, a function that takes any input and returns fixed-size output, and seeding it like in Snow White or a pseudorandom function (PRF), a function family which cannot be significantly distinguished by an efficient algorithm from a truly random oracle, like in Sleepy. 2) Implement a Random Oracle and VRF which is secure against adaptive corruptions using Algorand's model. Using recent validators to form committee as long as the underlying blockchain is fair. This method is secure against slow corruptions. In all cases, if there are too many validators eligible to vote, the protocol considers random down-selection to reduce bandwidth consumption. This down-selection can be conducted with a random oracle or random oracle and VRF. A random oracle is an abstract black-box that generates truly random numbers. A verifiable random function (VRF) is a psuedo-random function where each output is unpredictable given the knowledge of all prior outputs. Each output has publicly verifiable proofs of output correctness. | Algorand chooses committee members and leaders randomly among all users based on the users’ weights using a technique called cryptographic sortition. This is a private non-interactive method where every user in the system can independently determine if they are in the committee by running the VRF on their private key + info from blockchain. The VRF generates a proof which the user can include in their message to prove to other users that he is in the committee. Multiple people can be selected as proposers and a person may be given multiple votes in a committee (based on their proportion of stake). Using the VRF : VRFsk(x) returns two values: a hash h and a proof p. The hash h is uniquely determined by a validator's secret key sk and x, but is indistinguishable from random to anyone that does not know sk. The proof p allows someone to check that the hash of x by person with public key pk matches the hash h without knowing sk. VRF provides these properties even if pk and sk are chosen by an attacker. Thus an attacker doesnt know if a person was chosen until they send a message which includes the hash and proof. Selection of Committee size: The committee size is based on a calculation which depends on the number of honest nodes in algorand, the threshold of honest users in the committee and the acceptable probabilty in which there will be more than the threshold number of malicious users in the committee. | FFG maintains a validator-set by locking up a validator’s “deposit” as a means of showing they have stake in the system. Anyone can self-select into the validator pool as long as they meet the minimum staking requirement (exact amount has yet to be decided upon). The protocol does not have a proposer and does not employ any method of randomness generation. | Source of Randmoness: Decentralized Randomness beacon using Threshold Relay 1) Setup: The following things are done in the setup stage: 1.1Distributed Key Gen is run for BLS to setup group public key 1.2 The threshold t of n signatures that are needed for generating randomness is determined 1.3 The secret key shares are distributed. 1.4 There is a verification vector that gets committed to the blockchain. The public key for the group can be derived as follows from the verification vector: 2) Signing Process: When the first notarization for round r-1 is seen, all the nodes enter the next round and try to compute the randomness using equation: When any node receives at least t valid signatures, it can recover the randomness for that round by running the threshold recovery algorithm. Random beacon output in one round chooses the committee for the next round according to a threshold relay technique. The sub-committee size is chosen based on the equation below: Threshold relay is used to split nodes into multiple groups. One of the m groups each of size n is chosen as the committee for beacon protocols and notorizations in that round. The comittee for beacon protocol is responsible for generating randomness for round r + 1 and the notorizations comittee runs the protocol. | Initialization: Called by a party to become operational. If called on 1) Genesis block - party calls initialization functionality to claim its stake (exact method not mentioned) or 2) Non-Genesis block: party queries initialization functionality to receive genesis block and uses the stake distribution to determine the threshold for each stakeholder to potentially become a slot leader (i.e. the committee) Staking Procedure Uses a VRF to locally elect slot (round) leader using secret key, slot index, and epoc randomness --> outputs a hash h and a proof p - if output hash below certain threshold, then party is eligible slot leader - Can be multiple leaders (usually one) - Converge upon single chain using new chain selection rule - No "committee" members only a few leaders Other - "Stake distribution and epoch randomness updated at the beginning of each epoch" - "Honest parties are mandated to update their private key in each slot" - VRF and KES (key evolving signature scheme) are employed | TFG does not specify any particular method of proposer or committee election method, and does not rely on random generation although some liveness strategies that they may employ may require some randomness. | |||||||||||||||
14 | Propagation & Creation of Blocks | Consensus proceeds, as follows, in multiple rounds such that each round has one proposer: 1) First, a proposer is chosen from the validator-set to propose a new block. 2) Then that proposer compiles and proposes a block. 3) The next step is a Pre-Vote: if 2/3 validators agree on the aforementioned block, then the protocol moves onto the pre-commit stage. 4)In the Pre-Commit phase, if 2/3 of validators agree on the same block that was pre-voted, then all honest nodes commit that block and move to new block height (starting the process at step 1 again). If a block is not proposed in time or block does not receive enough votes in the pre-vote or pre-commit, then a new round occurs where a new block is proposed at the same height. | The 'fast path' of the protocol has an accelerator, which acts as the proposer in proposing blocks, and a committee, which verifies proposed blocks. If the Accelerator and 3/4 of the committee is honest, then the protocol proceeds as follows: 1) The Accelerator proposes transactions with associated sequence numbers. 2) The Accelerator signs transactions and sends these to the rest of the committee. If a 2/3 supermajority of the committee acknowledges then the transaction is considered notarized. If either of the above does not hold, the protocol enters slow mode, falling back to the underlying blockchain and their protocol for creating blocks and propagating them. | There is at least one block proposed. To minimize cost of gossiping unnecessary blocks, a sortition hash is used to prioritize block proposals. (priority of a block = priority of user who proposed block = arg max sub_user index hash(hash output of vrf || sub user index))) Since each user can be chosen multiple times in a round to be a proposer or in the committee, each time is given a new index and key pair. sub user index refers to this. The agreement protocol consist of two phases: 1.BA* reduces the problem of agreeing on a block to agreement on one of two options by narrowing down one non-empty proposed block to agree on. 2. BA* reaches agreement on one of these options: either agreeing on a proposed block, or agreeing on an empty block. | This version of Casper is simply an overlay that helps with finality on an already existing blockchain. The actual propagation and creation of blocks is assumed to occur in the underlying system. FFG currently relies on the underlying PoW system. It plans to eventually move to something that is “more efficient” (eg. Round-robin style signing). | Producing a random beacon output (described above): The random beacon output for round r determines a priority ranking of all registered clients and determines the comitee members. Producing block proposals 1. selects the heaviest valid chain C with len C = r that it knows of 2. the new proposed block Br references the last block on C and is composed of the selected transactions. This block is then broadcast to request for notarizations. Producing block notarizations A proposed block B is considered valid for round r if rd B = r and there is a valid block B' such that: 1) prvB=H(B') and rdB' = rdB-1, 2) ntB is a notarization of B', (3) dat B is valid After BlockTime, the each member of the notary comittee signs all highest priority blocks for the current round that it has received and broadcasts a signature message for this block to the entire network, it keeps doing this process until it observes a notorization for the current round. The notorization signals the start of a new round. Notorizations help enforce timely publications. | Chain-Based Protocol: blocks are created by a randomly elected slot leader(s) that are then appended to the end of the blockchain (longest chain); over time blocks are continually added to this longest chain guaranteeing liveness via consensus Staking Procedure - slot leader creates and signs block then broadcasts the new chain to peers - each block broadcasted contains VRF output of lottery and proof of eligibility to be slot leader - each participant in the network can then verify the leader election and choose to accept this new longest chain or not | Validators create blocks according to any strategy ensuring liveness with some synchrony assumption and less than some number of faulty nodes. Blocks are gossiped from there. No specific recommendations are currently provided on a strategy for block creation ensuring the above parameters although some validator strategies are in the works. | ||||||||||||||||
15 | Finality | A block achieves absolute finality if it achieves 2/3 or more pre votes and pre commits. This process continues indefinitely unless 1/3 or more validators become unresponsive, in which case the network halts. Above, we see that this protocol prefers consistency over availability. | Any maximum sequence of transactions with no gaps that has been notarized is considered fully confirmed output. Transactions are considered probablisitically finalized after it's some k blocks deep into the slow chain, where k is the security parameter specified by the implementing protocol. | Strong Synchrony: BA* designates consensus on value V as final if the algorithm reached in the first step, and if enough users observed this consensus being reached i.e in a strongly synchronous setting. A block that is a predecessor of a finalized block also becomes finalized. Final blocks guarantee that no other block could have reached consensus in the same round. This means that all final blocks are totally ordered with respect to one another, since (1) blocks form a linear chain, and (2) there can be exactly one final block at any given position in the chain. Weak Synchrony: In the case of weak synchrony, BA* may have forks and thus may only be able to reach tentative consensus. To resolve these forks, Algorand periodically proposes a fork that all users should agree on, and uses BA* to reach consensus on whether all users should, indeed, switch to this fork. All users passively keep track of all forks and at every time interval they run the recovery protocol (where they agree on forks instead of blocks) to sync up the system. | The most important aspect is that even if a malicious attacker has control of the underlying proposal mechanism, FFG will not finalize conflicting checkpoints. It uses BFT theory to prevent finalization on any block or checkpoint without a 2/3 supermajority. It does so by using a unique stitching mechanism via a “Forward validator-set” and a “Rear validator-set” to show how the overlap of the two ensures at least 2/3 of the members of any dynamically changing validator-set agree on the same block. A supermajority link is an ordered pair of checkpoints (a, b) such that 2/3 of validators have published votes with that pair. The source(a) and target(b) do not need to be contiguous. | Optimistic Finality through Notorizations: Only notarized blocks can be included in a chain. Client only notarizes the highest-ranked one with respect to a publicly verifiable ranking algorithm driven by the random beacon. Notarization can be seen as optimistic consensus, usually only one block gets notarized & can be detected after one subsequent block plus a relay time. Whenever the broadcast network functions normally a transaction is final in the consensus after two notarized confirmations plus a network traversal time. However, notarization is not consensus because it is possible, due to adverse timing, for more than one block to get notarized at a given height. The finalization protocol is passive and independent from the notarization protocol. | Since this PoS model is chain-based, its finality is probabilistic and is dependent upon this new chain selection rule. Novel Chain Selection Rule: 1) Short Range (up to k blocks): follow longest chain 2) Long Range (more than k blocks): use plenitude rule --> choose the denser of the chains right after fork occurs from current chain | Any two nodes can make final decisions as soon as they detect safety on blocks that would require greater than their fault tolerance threshold weight of nodes to equivocate before a conflicting block could be finalized. When nodes equivocate, a fault tolerance threshold is reached, so if the amount of safety on a block is greater than the node’s fault tolerance threshold, the node is safe to make a decision on it. Fault tolerance thresholds are subjective in that different nodes can have different fault tolerance thresholds. In the case two nodes have different fault tolerance thresholds t \& t', then they have consensus safety if the union of their views has less than min(t, t') faults. | ||||||||||||||||
16 | Handling Churn (Joining and Leaving) | Tendermint handles rotating validator sets by allowing for updating the set of validators by specifying public keys and updated voting power for a new set of validators. To remove validators, the protocol simply sets their voting power to 0. Validators that haven't signed for a protocol specified number of blocks, are considered timed out and implicitly unbonded. When validators stake, they lock up their funds for a particular bonding period. To unlock their funds, they must specify their intent to do so and then wait for a 2-3 month unbonding period. This allows for the knowledge of how the validator set will change and mitigates the nothing at stake problem. | Thunderella handles churn as it supports robust committee reconfiguration defending against posterior corrupts. Robust committee reconfiguration means that committees in Thunderella are chosen such that each committee remains honest although not necessarily online until the honest chains are roughly the clock time for the current txn(c) + 4 * security parameter(k) (c + 4k), since notarization transactions are only considered legitimate if included in the blockchain by length (c + 2k). Posterior corruptions refer to a set of users possibly holding majority of stake sometime in past selling their stake at some point & from that point onwards such that they might be incentivized to act maliciously (eg. fork & double spend old money). Thunderella suggests the following reconfiguration approaches: 1) Use underlying blockchain to establish IDs of recent miners and have recently only miners form the committee 2) Have stakeholders act as committee | Joining: Gossip peers are replaced every round, so if you get disconnected this replacement helps a node recover. To help new nodes catch up, Algorand generates a certificate (an aggregate of votes from the last step of BA* except the final step which allows any user to reach the same conclusion by processing the votes) for every block that was agreed upon by BA*. Certificates speeds up the validation process of old blocks for new nodes. A node can also request a collection of votes on the final step of a block (but only really needs to ask this for the latest block because if the last block was final, everything before it was also finalized). Leaving: Algorand assumes that most honest nodes (e.g., 95%) can send messages that will be received by most other honest nodes (e.g., 95%) within a known time bound. This requires most nodes to be online. Further nodes need to be online to know if they were chosen to be in the committee/ proposer of every round | Dynamic validator-sets are handled using the idea of a dynasty of a block, the number of finalized checkpoints from the root to the parent of the current block. A new validator is required to include a “deposit” for their stake in a block with dynasty d. That new validator will join the validator-set at the first block with dynasty d + 2. Similarly, a retiring validator must include a “withdraw” in block with dynasty d and will actually be removed from the validator-set at dynasty d + 2. Any validator that leaves the validator-set will have their corresponding public key forever forbidden from rejoining that validator-set again. This is done as a means of reducing overhead in terms of handling entry/exit/re-entry and not as a form of punishment or deterrence. At the start of block with dynasty d + 2, the retiring validator’s stake is locked up for a long time (on the order of 3-4 months worth of blocks) as a safety guarantee. Any violation of protocol policy will cause these funds to be taken away i.e. slashed. | Epochs: The block produced in the first round of each epoch is a registry block (also called key frame) and contains a summary of all new registrations and de-registrations of nodes that happened during the previous epoch that just ended. Registration: A node can request to join the network (i.e. register) or leave the network (i.e. de-register) by sub- mitting a special transaction for that purpose. A registration transaction contains the public key of the new node plus an endorsement proving that it was allowed to form. The registration gets activated in e + 2 epochs once tha transaction is included in the blockchain. Pooling: A system parameter, M_max, governs how many different pools can form during an epoch. Members of the pool create a registration transaction for G which contains the tuple x = (e, j, pkG ) and has to be included in the blockchain in epoch e to get registered. Pools are automatically de-registered after a certain time period. | Epochs: an R num of slots are collected into an epoch. Idea is that it allows the usage of stake reference points that are old enough to be stable. In epoch ep, the stake distribution to determine the threshold used to elect slot leaders is the distribution from epoch ep-2. Epoch randomness is updated at the beginning of each epoch and is derived as a hash of additional VRF values from blocks from the first two thirds of epoch ep-1. Registration/Deregistration - Any node is required to register with its resources in order to participate in the protocol by doing the following (note: deregistration is a very similar process): - Registering with Random Oracle and Clock is straightforward - Registering with ledger - check if registered with Rand. Oracle and Clock - register with other functionalities - store current time (for last time this party was connected to all resources) | TFG handles validator set rotation with dynamically changing sets of consensus forming nodes and / or their weights. The safety proof holds with dynamic validator sets. Future validators cannot affect the fork choice of blocks before they were introduced, or they would affect the safety of those blocks. Thus, the validator selection method adds a weight map to each block that specifies the validator set for the fork choice from among its children, as they cannot affect blocks in the past. This allows for the rotation of validator sets without requiring that the rotation is finalized. | ||||||||||||||||
17 | ||||||||||||||||||||||||
18 | 3) Security of different schemes for random generation | Biasable | Tendermint uses a deterministic round-robin protocol scheme to choose proposers; there is no randomness in the protocol whatsoever. Proposers are elected deterministically, through a heap sort based on the voting power and number of times the validator was chosen. The protocol can only be biased by adding or removing stake since that is the only input the adversary can access. The protocol cannot be biased instantaneously because of the long time it takes for a validator to unbond i.e remove stake from the system or bond i.e add stake to the system. Nevertheless, an attacker can plan ahead to bias the choice of proposer in a longer time frame. | Thunderella proposes two methods of randomness generation: i) a Random Oracle instantiated by a Hash Function or ii) a Random Oracle with a VRF similar to what is used by Algorand. In both methods the randomness seed is biasable. In the Random Oracle scheme instatiated with a Hash Function described, a proposer is determined by the equation: H^{nonce}(pk, q) < D_p where H is the Hash function which is used as the Random Oracle, pk is the public key of the validator, q is the given time-step and nonce is the source of entropy to the hash function. The nonce is chosen by the proposer of the previous block. The difficulty parameter D_p is set such that a committee member is elected as the proposer with probability w in a single time step. If the adversary proposes a block, she can bias the nonce used to generate entropy for the hash function of the next round, thus biasing the proposer elected in the next block. However, to mitigate the biasability of the randomness scheme, the same nonce is used in the Hash function to select proposers for r rounds rather than to merely select the next proposer. This makes it computationally harder for an adversary to brute force a nonce that will enable them to be the proposer for the next r rounds. While this strategy guarantees only a polynomial security loss, it comes with a predictability trade-off discussed later. This scheme results in being able to tolerate only a slow adaptive adversary | Algorithm: every user u selected for block proposal also computes a proposed seed for round r as : The vrf proof and the seed for round r is included in the block added in round r-1 by that respective proposer. If the seed doesnt verify with the given vrf, then everyone computes the seed as Hash(seed_(r-1)||r) Thus, the secret key of each user has to be chosen well in advance to ensure that they can't bias or predict the seed. Biasable: When the network is not strongly synchronous, the attacker has complete control over the links, and can therefore drop block proposals and force users to agree on empty blocks, such that future selection seeds can be computed. Algorand thus requires the weak synchrony assumption that in every period of length b, there must be a strongly synchronous period of length s < b for the protocol to be unbiasable. As long as s is suitably large enough that at least one honest block was produced in a time period of b, an adversary u choosing a key sku cannot bias the seed for round r | TODO: RANDAO | In several protocols adversaries usually abort protocol to invoke the fall back mechanism, thus intorduce bias. The threshold scheme is unbiasable because the threshold is chosen in a way that ensures an adversary cannot abort the protocol by preventing a threshold signature (the source of randomness) from being created.This requires t to be chosen according to the equation: f <= n - t f := amount of signatures adversary has n := total signatures in the scheme t := threshold of signatures required to generate randomness | Leader Election Algorithm: each party locally evaluates a VRF using their secret key and the inputs - the current slot index and the epoch randomness. If the output y of the VRF is less than some threshold T, then the party is eligible to be leader and can then generate a proof p to prove his election. The output y and proof p are both revealed along with the new block that the leader broadcasts. Epoch Randomness (ηep): updated at the beginning of each epoch; the randomness of the epoch is derived from hashing the previous epoch randomness, the current epoch number, and the output of certain values from the first 2/3 blocks of the previous epoch Biasable: - It is possible that an adversary can generate the right values to place in the first 2/3 blocks of the current epoch in order to bias the next epoch randomness --> essentially a form of stake grinding - Given the novel chain selection rule, it is possible that an adversary that successfully biases the epoch randomness may do so as to elect himself multiple times in a future epoch, thereby allowing him to carry out a selfish mining attack wherein he can create a personal longest chain (for short range selection) or possibly create multiple blocks in a short amount of time to add density to his chain (for long range selection) | Randomness is necessary for specifying some validator strategies - the team is focusing on the consensus problem at the moment with generating randomness for validator sets as future work. | |||||||||||||||
19 | Predictable | Adaptive key generation attack, unless utilize method from Snow White where public keys must be registered on blockchain before random nonce is generated to seed a new random oracle. | In all scenarios that the randomness is biasable, it is also predictable. | TODO: RANDAO | The randomness for round r-1 is not predictable by the adversary before at least one honest node has advanced to round r . | The Epoch Randomness is predictable, but only for the last 1/3 of any epoch; as by this point, all the required inputs into the Hash function to determine the next epoch randomness are publicly available | Randomness is necessary for specifying some validator strategies - the team is focusing on the consensus problem at the moment with generating randomness for validator sets as future work. | |||||||||||||||||
20 | Revealed in the current round | Use of a deterministic random algorithm means the randomness seed is revealed well ahead of every round and the proposer can be determined ahead of time. | When Thunderella uses a Random Oracle instantiated as a Hash function, because the same nonce is reused as entropy during an epoch, it leads to the randomness seed being leaked ahead of the start of a new round. This enables an adversary to corrupt or DoS proposers. The analysis of the Random Oracle with the VRF case is similar to that of Algorand. | Only once a block has been proposed is the new seed and a VRF proof to verify it publicly known. This ensures that the proposer and the randomness seed is not leaked ahead of time. This guarantee ensures that Algorand can defend against DoS attacks on proposers and is adaptively secure in a model with erasures, even with instantaneous corruption. | TODO: RANDAO | The randomness seed is revealed once any honest validator has advanced to round r. While the time gap between an honest validator advancing and the new round officially starting is small, this gap is sufficient for an adversary with significant computational resources to identify and DoS proposers. This is the reason Dfinity can only tolerate mildly adaptive adversaries and not instantaneous corruptions. | Similar to Algorand, the slot proposer is only revealed at the time of block propagation when the proposer attaches their VRF proof with the block. This ensures Ouroboros Genesis can defend against DoS attacks on the proposers and like Algorand is adaptively secure in a model with erasures, even with instantaneous corruption. | Randomness is necessary for specifying some validator strategies - the team is focusing on the consensus problem at the moment with generating randomness for validator sets as future work. | ||||||||||||||||
21 | ||||||||||||||||||||||||
22 | Insert Network Attacks (any attacks at the block propagation layer) | DDoS 1/3 of validators, Can keep DOSing the next proposer because of the Round Robin Deterministic Algorithm until you become a proposer | Attacks: 1. DDOS the leader for that round. 2. Nodes have no incentive to make proposals. It is less work to just let other people do the work ofblock creation, it is easier (less expensive) to just vote on the created blocks. 3. Nodes have no incentive to gossip messages around in the protocol 4. When someone new is joining a network, an adversary can buy time by providing a certificate which says BA* completed after a large number of steps and in the mean time he can find a step in BA* where he controls majority and sign of and say that was the certificate step for a block. Defense: 1. Even if you DDOS some subset of the people, the protoocl will proceed because everyone has to make a proposal and the proposals are weighted at every step. Thus if upto 1/3rd validators are DDOSed, the protocol will still proceed by picking the minimum hash weighted proposal received. 2. Right now no defense has been mentioned. Could be fixed through and incentive scheme that rewards the chosen proposal. 3. If nodes stop gossiping, the protocol will stop being live and the price of algorand tokens will drop, this means the value of their stake goes down, which is a greater cost than the cost of keeping the protocol live and running by gossiping messages. 4. The way to prevent this is by having a huge committee that the possibility of such a step is negligible. | Unclear | The time it takes to gossip around the finalized messages is much slower in comparison with the time for the fast consensus. Would need some model to keep all the nodes up to date on the latest view of the blockchain | Adversary can delay messages for an arbitrary number of rounds up to ∆ rounds | ||||||||||||||||||
23 | ||||||||||||||||||||||||
24 | 4) Finalization guarantees | Compare for paper on what guarantee they provide | Any block that has received both 2/3 or more pre-votes and pre-commits is finalized. | Note that in Thunderella, finality is different from confirmation and is fundamentally cotingent on the realization of the underlying state replication protocol. Here, we look at confirmation, which means committment to publication in the underlying slow chain. Any maximum sequence of transactions with no gaps that has been notarized is considered fully confirmed output. If 3/4 of the fast-path committee is honest and online and the proposer is honest then valid transactions are instantly confirmed. However, this fast path confirmation is different from finality. This confirmation is considered to be optimistic finality, while transactions are only fully finalized once they are recorded on the underlying blockchain. In the case that the underlying blockchain is chain-based, the transactions are probablistically final once they are incorporated into the blockchain, but in the case that the underlying blockchain is BFT based, the transactions are finalized via the considerations of the underlying blockchain. | Algorand can achieve probabalistic, not absolute, finality. As long as the attacker controls less than 1/3 of the monetary value, Algorand can guarantee that the probability for forks is negligible, as this allows the protocol to operate in strong synchrony, reaching definitive agreement on each block. In weak synchrony, Algorand may fork, but uses BA* to come to agreement on which fork to choose periodically proposing a fork for the committee to vote on. As such, transactions in Algorand are eventually finalized when the protocol returns to strong synchrony. Moreover, Algorand is able to experimentally deduce that when there is an 80% fraction of honest users, an adversary would need 20% of Algorand currency to create a fork. | In Casper FFG, finality is achieved when a 2/3 supermajority of the committee by stake sign a block given that fewer than 1/3 of committee are Byzantine. Casper FFG is built such that it will never finalize conflicting checkpoints even if an adversary has control over the blockchain's proposal mechanism. However, since FFG provides safety and the proposal mechanism provides liveness, the aforementioned adversary could prevent Casper from finalizing future checkpoints. | In Dfinity, the probability of finality increases as the block weight on a chain increases. This assumes that for each round r, there is a time when we can rule out any further notarized blocks being received. At this rule out time, we can finalize round r because we know that the notarized blocks already contain all the chain tips that can possibly survive beyond round r. There is a gaurantee of near-instant finality as under normal operation in round r, every transaction included in a block for round r is final for an observer after two confirmations plus the maximum network roundtrip time 2∆ (or network propogation delay). | Genesis can achieve probabalistic, not absolute, finality. This is based on the chain-selection rule. The paper includes pseudocode for a simulator, which is used for proofs provided the paper. However, there are no results or metrics that show the outcome of the simulation. | TFG achieves finality under validators with different fault tolerance thresholds. That is, the protocol is asynchronously safe and BFT allowing for validators to have different fault tolerance thresholds. | |||||||||||||||
25 | Compare for the results if it is provided | N/A | N/A | As long as the attacker controls less than 1/3 of the monetary value, Algorand can guarantee that the probability for forks is negligible, as this allows the protocol to operate in strong synchrony, reaching definitive agreement on each block. In weak synchrony, Algorand may fork, but uses BA* to come to agreement on which fork to choose periodically proposing a fork for validators to vote on. As such, transactions in Algorand are eventually finalized when the protocol returns to strong synchrony. Moreover, Algorand is able to experimentally deduce that an adversary would need 20% of Algorand currency to create a fork. | N/A | N/A | N/A | N/A | ||||||||||||||||
26 | ||||||||||||||||||||||||
27 | 5) Scalability comparison | Latency / Throughput if provided | N/A | N/A | Results from implementation: dissemination time grows with the diameter of that component, which is logarithmic in the number of users, Latency increases as block size inceases per round, even with 50k users and 1000 VMs an expensive round can be completed in around 100 seconds Lowest Throughput is 2Mb block in 22 seconds | N/A | Gaurantees near-instant finality: Under normal operation in round r, every transaction included in a block for round r is nal for an observer after two con rmations plus the maximum network roundtrip time 2 ∆ (or network propogation delay) | N/A | N/A | |||||||||||||||
28 | ||||||||||||||||||||||||
29 | 6) Handling Churn (join and leave) | Tendermint allows for rotating committees, however, as it requires locking periods, meaning that validators are bound the system for a 2-3 month period, the amount of churn the protocol allows for is limited. Moreover, offline validators are considered timed out and are implicitly unbonded, removing them from the validator-set, unlike sleepy protocols, in which offline nodes are still considered to be part of the validator-set, allowing for greater flexibility in churn. | Thunderella allows for committee rotation supporting sleepy consensus in that committee are chosen such that each committee remains honest although not necessarily online until the honest chains are roughly the clock time for the current txn(c) + 4 * security parameter(k) (c + 4k). As such, Thunderella supports more flexibility in churn than protocols that don't support the sleepy paradigm. | Algorand allows for flexibility in the joining the protocol, but requires a significantly lower amount of validators allowed to leave the protocol to maintain liveness as 95 or more of validators must be online to maintain strong synchrony. | Casper FFG allows for validators to join and leave the protocol within a certain time period, and when validators first stake, their funds are locked up between 3 - 4 months. Validators that deposit in dynasty d are added in dynasty d + 2 and validators that exit in dynasty s are removed in dynasty d + 2. As such, FFG is similar to Tendermint in that it allows for dynamic churn within the constraints of lock up periods. | Dfinity allows for validators to request to join and leave within e + 2 epochs once the special de-registration transaction has been submitted. As such, Dfinity supports flexible churn but validators must wait a certain period of time before being able to join or leave. Moreover, offline validators are considered adversarial as validators must submit special transactions in order to leave. | In Genesis, validators only need the genesis block to re-build blockchain without external verification (similar to many PoW protocols). But they need to interact with external parties to synchronise with the system and continue to participate. Validators must complete a registration process and once a validator has completed the process they can engage in the protocol. For validators to leave, they must go through a similar deregistration process. As such, Genesis allows of flexibility in churn depending on how long the registration and deregistration processes take. | TFG handles validator-set rotation with dynamically changing sets of consensus forming nodes and or their weights in the case that the validator selection method adds a weight map to each block that specifies the validator-set for the fork choice from among its children. This allows for the rotation of validator-sets without requiring that the rotation is finalized. As such, TFG handles churn in that a different validator-set is allowed per fork choice. | ||||||||||||||||
30 | ||||||||||||||||||||||||
31 | 7) Economic Model | Reward / Punishment / Slashing | N/A | Block reward & txn fees distributed to recent set of fruits (preserves fairness) - no punishment / slashing specificed | N/A | Reward scheme is planned; hasn't been made yet Slashing exists - Conditions 1) a validator must not publish two distinct votes for the same target height 2) a validator must not vote within the span of its other votes | N/A | N/A | N/A | |||||||||||||||
32 | Nash Equilibirum Structure | N/A | ε-Nash equilibrium for reward scheme above against any coalition that controls only a minority of computing power, thus as long as an adversary controls less than the minority of computation power, cannot gain more than ε over its fair share of rewards (wait, what is the scheme) | N/A | N/A | N/A | N/A | N/A | ||||||||||||||||
33 | ||||||||||||||||||||||||
34 | 8) Results | Network Partition Resolution | In the event of a network partition, Tendermint prioritizes consistency over availibility. That is, no additional blocks will be confirmed or finalized until the partition is resolved. | In the event of a network partition, the fast path conditions fail to be upheld and the protocol would fall back to the underlying blockchain, upholding the underlying blockchain's partition resolution conditions. As Thunderella falls back to a synchronous underlying blockchain, it prioritizes availability as synchronous blockchains are not consistent in the case of a network partition. | In the event of a network partition, Algorand ensures safety, implying that it prioritizes consistency over availability. Indeed, Algorand prefers to produce empty blocks generating unproductive liveness, rather than sacrificing on safety. | In the event of a network partition, FFG drains non-active users of their stake over time in order to recovery liveness. FFG prioritizes consistency in that it does not allow for checkpoint finalization without a 2/3 supermajority of validators. If a partition violates the former condition, finalization will not occur. | Network partitions are implicitly detectable by the protocol, since if the network splits in two halves of about the same size, this will automatically cause the random beacon to pause within a few blocks so that none of the sides can continue, prioritizing consistency. The random beacon will automatically resume once the network reconnects. If the network splits in a way that one component is larger than half of the network, the protocol may continue in that one large component but will pause in all other components. This assumes that a group is a good sampling of the network. | The Ouoroboros paper series does not explicitly mention how the protocol reacts in the face of a partition, however, a node that is out of sync with the protocol will be considered adversarial until at least some function of ∆ rounds has passed (where ∆ refers to the propogation delay). Thus, it seems as though the protocol prioritizes consistency. | In the event of a network partition, Casper TFG prioritizes availability, however, validators are unable to detect safety on blocks made during a partition thus there is the chance of reversion. Safety in TFG is dependent on the maximum length it takes for the safety oracle to determine the estimate as safe. In asynchrony, this is unbounded, but with any liveness strategy that works in at least a partially synchronous network, it is bounded. | |||||||||||||||
35 | ||||||||||||||||||||||||
36 | ||||||||||||||||||||||||
37 | ||||||||||||||||||||||||
38 | ||||||||||||||||||||||||
39 | ||||||||||||||||||||||||
40 | ||||||||||||||||||||||||
41 | ||||||||||||||||||||||||
42 | ||||||||||||||||||||||||
43 | ||||||||||||||||||||||||
44 | ||||||||||||||||||||||||
45 | ||||||||||||||||||||||||
46 | ||||||||||||||||||||||||
47 | ||||||||||||||||||||||||
48 | ||||||||||||||||||||||||
49 | ||||||||||||||||||||||||
50 | ||||||||||||||||||||||||
51 | ||||||||||||||||||||||||
52 | ||||||||||||||||||||||||
53 | ||||||||||||||||||||||||
54 | ||||||||||||||||||||||||
55 | ||||||||||||||||||||||||
56 | ||||||||||||||||||||||||
57 | ||||||||||||||||||||||||
58 | ||||||||||||||||||||||||
59 | ||||||||||||||||||||||||
60 | ||||||||||||||||||||||||
61 | ||||||||||||||||||||||||
62 | ||||||||||||||||||||||||
63 | ||||||||||||||||||||||||
64 | ||||||||||||||||||||||||
65 | ||||||||||||||||||||||||
66 | ||||||||||||||||||||||||
67 | ||||||||||||||||||||||||
68 | ||||||||||||||||||||||||
69 | ||||||||||||||||||||||||
70 | ||||||||||||||||||||||||
71 | ||||||||||||||||||||||||
72 | ||||||||||||||||||||||||
73 | ||||||||||||||||||||||||
74 | ||||||||||||||||||||||||
75 | ||||||||||||||||||||||||
76 | ||||||||||||||||||||||||
77 | ||||||||||||||||||||||||
78 | ||||||||||||||||||||||||
79 | ||||||||||||||||||||||||
80 | ||||||||||||||||||||||||
81 | ||||||||||||||||||||||||
82 | ||||||||||||||||||||||||
83 | ||||||||||||||||||||||||
84 | ||||||||||||||||||||||||
85 | ||||||||||||||||||||||||
86 | ||||||||||||||||||||||||
87 | ||||||||||||||||||||||||
88 | ||||||||||||||||||||||||
89 | ||||||||||||||||||||||||
90 | ||||||||||||||||||||||||
91 | ||||||||||||||||||||||||
92 | ||||||||||||||||||||||||
93 | ||||||||||||||||||||||||
94 | ||||||||||||||||||||||||
95 | ||||||||||||||||||||||||
96 | ||||||||||||||||||||||||
97 | ||||||||||||||||||||||||
98 | ||||||||||||||||||||||||
99 | ||||||||||||||||||||||||
100 | ||||||||||||||||||||||||
101 | ||||||||||||||||||||||||
102 | ||||||||||||||||||||||||
103 | ||||||||||||||||||||||||
104 | ||||||||||||||||||||||||
105 | ||||||||||||||||||||||||
106 | ||||||||||||||||||||||||
107 | ||||||||||||||||||||||||