Hello,
ICP sounds very interesting. I read here that it is a semi-permissioned hybrid blockchain with a unique consensus protocol The Internet Computer for Computer Scientists - Internet Computer Wiki. Specifically, it assumes an asynchronous network with partial synchrony to ensure liveness and that each subnet with n replicas has at maximum f<n/3 malicious ones. In my opinion, this is very close (identical) to the common assumptions of BFT-style consensus protocols, where f>2/3 n + 1 honest validators are required (f<n/3 consensus halts).
In the case of IPC, is n comparable to the number of validators in a BFT PoS network? What are the differences?
IPC performance in terms of TPS seems really good. Is there any public testing similar to the TON blockchain that recently broke the world record for TPS?
In the case of IPC, is n comparable to the number of validators in a BFT PoS network? What are the differences?
Yes itâs the same calculation based on supermajority agreement (more than 2/3 of participants). The main difference is in security models. At PoS every validator has a stake at risk. In IC the stake is with the DAO which is assigning the node provider role to identifiable parties for rewards paid in ICP. Node providers are not anonymous, are expected to host nodes in secure certified data centers and can be made accountable for the gross negligence wrt. security.
PC claims to have a block time of less than one second and a finite time slightly longer than one second L1 comparison - Internet Computer Wiki. How many blocks are needed to have a transaction confirmed? It seems that it depends on the number of replica n.
Once a transaction was included in a block, in a happy case scenario, the finality is expected to happen within one consensus round (which is for most subnets ~1s). However, due to multiple reasons like connectivity issues or faulty nodes, the finality time can take longer. Also the number of replicas in as subnet can have an impact on that as the amount of communication overhead grows with the number of participants. Also, see this breakdown of the finality time.
IPC performance in terms of TPS seems really good. Is there any public testing similar to the TON blockchain that recently broke the world record for TPS ?
We indeed did some tests a year ago. Check out this link.
I just have one last doubt. BFT-style consensus protocols prioritise safety (consistency) over liveness (availability) and require 1 block to reach the finality. In the happy (best case?) scenario, does IPC finality need a consensus round and 1 block? What is the finality in the worst case? How does it depend on the number of replicas? I cannot find this information in your link or in the whitepaper.
Thank you
Hello @alfredino, Iâm not from Dfinity but Iâll try to answer these questions based on what I learned.
In the case of the Internet Computer Consensus (ICC), safety is guaranteed as long as f < n/3 while liveness is guaranteed under the assumption of the network being partially synchronous.
Partially synchronous means that network alternates periods in which the communication delay between replicas is bounded (i.e. network is synchronous), and periods in which the communication delay can take any finite time, but no bound can be assumed (i.e. network is asynchronous). The finality depends on the current network conditions.
In the best case (synchronous network and honest leader for this consensus round), finality is achieved after 3 communication rounds (one for proposing the block, a second for notarizing it and the last to finalize the block). In this scenario, the block is finalized âimmediatelyâ (i.e. right after this consensus round, as soon as enough finalization shares are received).
In the worst case (asynchronous network with finite but unknown communication delay), finality might not be achieved for multiple consensus rounds as no block might receive enough finalization shares to become finalized. However, the chain can still make progress as blocks will still become notarized in each consensus round (as we are assuming that the communication delay is finite). This asynchronous periods (in practice) should not last for too long and therefore once the network goes back to being synchronous a block will become finalized and this will implicitly finalize its ancestor blocks which were notarized (but not finalized) during asynchronicity.
Independently of the network conditions, the ICC guarantees that at any consensus round in which there is a finalized block, there cannot be any other notarized block (for that round) and this is the key to ensure that all finalized blocks are part of the same blockchain. Basically, this means that no matters how âbadâ things go when the network is asynchronous, all replicas will continue to finalize the same blockchain as soon as the network goes back to normal conditions.
In terms of round trips, it does not depend on the number of replicas but of course the more the replicas (and the further they are), the higher the chances of âabove boundâ communication delays.
There are many more details to talk about but I find it hard to expain them clearly without a whiteboard. In case you are interested in continuing the conversation we can find a better way to discuss.
Remember that what I explained is based on my understanding so make sure to double check it. If I misunderstood something, Iâm counting on people from Dfinity to clarify
Exactly, these are the same assumptions and conditions of any BFT style consensus algorithm.
So the IPC consensus algorithm behaves like any other standard BFT. In the case of partial synchrony and a sufficient number of replicas (2/3f+1), each block requires at least 3 rounds to be final and no other confirmation blocks, so no forks are allowed. In case of asynchrony, the network cannot reach consensus and stalls.
Do you have any references explaining these? I could not find any.
Yes, best case is 3 communication rounds (different from consensus rounds).
Kind of, the subnet can still make progress in the sense that blocks will still be notarized and therefore the blockchain can be extended. However, no block might become finalized and therefore these blocks will not be passed to the execution layer. Once a block becomes finalized, the ancestor blocks become implicitly finalized so there is no need to re-propose or re-notarize them (as long as they are in the same chain of the block that became finalized). In this sense, even during asynchronous periods, the blockchain can still make progress and what happened during this time will be executed as soon as the network goes back to being synchronous.
Sorry I started responding 2 days ago, but only had time again today. Thanks @massimoalbarello for addressing questions.
Here is the response I started writing 2 days ago:
In the happy (best case?) scenario, does IPC finality need a consensus round and 1 block? What is the finality in the worst case?
The finality in IC consensus is asynchronous and does not block the next consensus round. A block is considered as final if the supermajority of replicas agree that this block was the only valid proposal they observed in the given consensus round. In a happy case, where there are no connectivity issues among the supermajority of nodes, the elected block maker manages to deliver its block to enough replicas in time. In this case, the supermajority will quickly validate this block and since it will be the only proposal in that round, they will agree on its finality.
However, under less favorable networking conditions, it is possible that the elected block maker only manages to propagate itâs block to a small subset of replicas. In this case, since no block will be validated in time, itâs possible that one of the fall-back block makers will propagate an alternative proposal which might reach more replicas. This will lead to a temporary fork, where multiple proposals will be validated in a single round. In this case, no finality in that particular round can be achieved. So the replicas will keep validating blocks of the next round and then the next one, until they again agree on a single block. Once this happens, this entire branch is considered as final and all other branches get discarded.
This is exactly the situation where the finalization can take more than one round, however the probability of such a situation quickly decreases with every new link of a fork. In practice, we observe on mainnet a finalization within one block in the majority of all cases.
Now to you question how the finality can be impacted by the number of replicas. In the current implementation, all replicas of a subnet participate in the consensus. Consensus requires exchanging many small messages in every round. All of these messages need to be gossiped to each node, then validated individually, potentially aggregated and so on. So the performance cost we expect is linear in the number of nodes.
The behaviour described by you and the other user is the standard behaviour of the BFT consensus algorithm, which favours safety over liveness and does not allow for forks in the hypothesis of partial synchrony.
f>2/3 n + 1 honest nodes/validators are required to reach consensus. They are actually weighted by their stake, so 2/3 of the total stake (although in IPC the nodes do not own any stake, if I understand correctly). If so, this is a standard PoS BFT style consensus.
Now, if the performance cost of message passing between nodes is linear instead of quadratic, IPC has a very efficient algorithm. What are the assumptions/disadvantages of such an approach?
I think reading the beginning until ICC0 (included) is enough to get a good understanding of the protocol but I suggest you to read it all if interested.
I was not involved in work on the consensus protocol (Iâm on the Message Routing team), but my guess is that while the cost of message passing between N nodes is indeed O(N^2) (each node communicates with every other node), the time and effort required for any one node to communicate with the remaining N-1 nodes is O(N).
Thank you. The reading was very interesting. It clarified some of my doubts, but others appeared.
In particular, the ICC protocols enjoy the property known as optimistic responsiveness [PS18], meaning that the protocol will run as fast as the network will allow in those rounds where the leader is honest. For an arbitrary round, where the leader is not honest or δ > âbnd, the round will finish in time O(âbnd +δ) with overwhelming probability.
One disadvantage of Tendermint is that unlike PBFT and HotStuff, it is not optimistically responsive. This can be a problem, since to guarantee liveness, one generally has to choose a network-delay upper bound âbnd that may be significantly larger than the actual network delay δ, and in Tendermint, every round takes time O(âbnd), even when the leader is honest.
Like PBFT and HotStuff, and unlike Tendermint and Algorand, all of the ICC protocols are optimistically responsive. Protocols ICC0 and ICC1 attain a reciprocal throughput of 2δ and a latency of 3δ (when the leader is honest and the network is synchronous). For Protocol ICC2, the numbers increase to 3δ and 4δ, respectively.
Each of the ICC protocols provides safety, even in the asynchronous setting.
So ICC protocols and also PBFT and HotStuff are better than Tendermint and Algorand in the synchronous case and with an honest leader and worse in the asynchronous case and with a non honest leader.
Let us focus on the case with (partial) synchrony and honest leader. The article shows that ICC protocols are able to guarantee liveness, but the CAP theorem proves that it is not possible to achieve all three properties (liveness->availability and safety->consistency) at the same time.
So my question is the same as in the first post: are the ICC protocols like Tendermint and Algorand, i.e. once consensus is reached you have consistency-finality (safety) and the block is added to the chain? Or do they need confirmation blocks before adding it, the only way if they want to maintain availability (liveness)?
Correct. As stated by the article: We also analyze the message complexity of each of the ICC protocols. Message complexity is defined to be the total number of messages sent by all honest parties in any one round â so one party broadcasting a message contributes a term of n to the message complexity. In the worst case, the message complexity is O(n^3). However, we show that in any round where the network is synchronous, the expected message complexity is O(n^2)) â in fact, it is O(n^2) with overwhelming probability. The probability here is taken with respect to the random beacon for that round.
In each of the protocols ICC0 and ICC1, in any one round, each honest party broadcasts O(n) messages in the worst case, where each message is either a signature, a signature share (for a threshold or multi-signature scheme), or a block.
In order to be complete. However, as was demonstrated empirically in [SDV19], this effort may be misplaced: in terms of improving throughput and latency, it is not the communication complexity that is important, but rather, the communication bottlenecks. That is, the relevant measure is not the total number of bits transmitted by all parties, but the maximum number of bits transmitted by any one party.
Mmh not sure Iâm understanding your comment correctly but the CAP theorem refers to the case in which there is a network partition. In the ICC paper I donât remember a discussion about this scenario but if the partition would include > f replicas then also ICC would not be able to make progress (as no blocks would be notarized/finalized).
A block is validated once it becomes notarized but this is not enough to safely pass it to the execution layer. At this point the block is added to one of the blockchains (might be multiple in case the network is asynchronous or leader malicious) but only one of these will become the âagreed uponâ chain once a block is finalized. In this sense, the finalization can be considered a confirmation but I wouldnât look at it like that as a notarized block is not enough for consensus.
So to answer your question, once consensus is reached (i.e. block is finalized), you have finality and there is no need for further confirmations. Safety is always guaranteed as long as f < n/3. Liveness is guaranteed under the partial synchrony assumption.
Again, this is based on my understanding but might be wrong so keep it in mind.
Any blockchain must satisfy the P property of the CAP theorem otherwise it is a centralised, not a distributed database. For this reason there are two possible families of blockchains AP and CP. The former favour availability or liveness and are based on a Nakamoto-style consensus where the finality of a transaction is probabilistic and the longest chain wins, while the latter favour consistency or safety and are based on a BFT-style consensus where the finality of a transaction is absolute and in the presence of consensus a transaction is immediately final.
According to the article, the ICC protocol always satisfies safety in the synchronous and asynchronous case and is therefore a CP blockchain. However, in the synchronous case it also satisfies liveness. This property present only in the partial synchronous case is guaranteed by all BFT-based protocols.
So now I should have clarified my doubts about the finality of the ICP blockchain.
