The Stellar Consensus Protocol: A Federated Model For Internet-Level Consensus
Last calendar week in our seminar nosotros discussed the Stellar consensus paper.
The newspaper is long, 32 pages. It looks similar the newspaper is written the way the protocol is conceived together with reasoned about. First comes a department on the federated Byzantine understanding (FBA) model, which talks most quorum slices together with the quorums that lawsuit from them. The side yesteryear side department talks most the requirements for quorum intersections, together with defines the dispensable sets alongside associated theorems. Then comes the federated voting section, alongside subsections titled: Voting alongside opened upward membership, Blocking sets, Accepting statements, Accepting is non enough, Statement confirmation, together with Liveness together with neutralization. On page 19, the Stellar Consensus Protocol (SCP) department starts, alongside to a greater extent than definitions together with the proofs intertwined alongside the protocol description. At this point, the reader is already overwhelmed, trying to hold inwards his hear theories most how the previous nineteen pages powerfulness connect dorsum to this protocol, together with is confronted alongside the chore of reading through a nine pages long SCP protocol section.
The newspaper would last significantly improved if it was rewritten top-down: non inwards a way the protocol is conceived together with proved, but inwards a reader-friendly mode prioritizing the clear communication of the protocol basics.
It was difficult reading through this paper, together with I didn't read it thoroughly. Here is what I understand:
SCP is a Federation-based Byzantine Agreement (FBA) protocol which allows opened upward membership instead of requiring unopen membership. In a federated opened upward membership model, nosotros don't know the lay out of nodes inwards the entire organization or all of their identities. Nodes may bring together together with leave.
One way to bargain alongside opened upward membership is Proof-of-Work based blockchains every bit inwards BitCoin. That has problems alongside excessive unloosen energy consumption, inscalability of throughput, together with due to probabilistic nature of the commit long hold off times to stimulate got a skillful guarantee of irreversibility of a transaction.
SCP does non role proof-of-work based blockchains. It adapts the PBFT protocol to move inwards an opened upward membership federated environment. PBFT is a 3-phase deterministic byzantine consensus protocol. It has similarities alongside Paxos: inwards fact if y'all extend Paxos which only tolerates crash faults to tolerate byzantine faults, y'all larn pretty much the PBFT protocol.
To this end, each node specifies a quorum acre inwards its config file. The quorum acre consists of the nodes it trusts, together with hopefully last a various well-balanced portfolio. By declaring its quorum slice, this node says that it finds the consortium of these nodes (not necessarily individually each one) trustworthy, together with volition rely on this consortium to convince itself of the understanding together with volition rely on them to bless/endorse its transactions. Traditional non-federated Byzantine understanding requires all nodes to convey the same slices, inwards FBA the cardinal excogitation is enabling each node to chose its ain quorum acre set.
These quorum slices are used for constructing quorums. A quorum is a laid of nodes sufficient to achieve agreement.
For safety, whatever ii quorums inwards the network involve to intersect, together with the intersection should incorporate nonByzantine nodes. If the quorum intersection consists exclusively of Byzantine nodes, together with hence SCP cannot guarantee safety.
The onus is on the users to supply skillful quorum slices. SCP does non supply a way to banking concern agree the soundness/integrity of quorum slices which give ascent to quorums. Again if the quorum intersection consists exclusively of Byzantine nodes, security is violated together with SCP doesn't convey responsibleness of that. To quote the paper: "SCP tin dismiss only guarantee security when nodes pick out adequate quorum slices."
The SCP protocol starts alongside a nomination phase, which if run long enough, eventually produces the same laid of candidate values at every intact node, which way nodes tin dismiss combine the candidate values inwards a deterministic way to create a unmarried composite value for the slot. Upon predicted/approximated convergence of nomination phase, the nodes get-go the ballot stage to perform federated voting (PBFT) to commit together with abort ballots associated alongside composite values.
When intact nodes concur to commit a ballot, the value associated alongside the ballot volition last externalized for the slot inwards question. When they concur to abort a ballot, the ballot's value becomes irrelevant. If a ballot gets stuck inwards a nation where 1 or to a greater extent than intact nodes cannot commit or abort it, together with hence nodes campaign in 1 lawsuit again alongside a higher ballot; they associate the novel ballot alongside the same value every bit the stuck 1 inwards instance whatever node believes the stuck ballot was committed.
Safety results from ensuring that all stuck together with committed ballots are associated alongside the same value. Liveness follows from the fact that a stuck ballot tin dismiss last neutralized yesteryear moving to a higher ballot. The skillful tidings most SCP is that provided that the quorum status is satisfied, whatever committed conclusion is straightaway irreversible.
Here are some videos on SCP (well generally the motivation together with setup of Federated Byzantine Agreement without the SCP protocol description): https://www.youtube.com/watch?v=mB9UW7HK8pc and https://www.youtube.com/watch?v=zTI1HAWDHIg.
That the quorums involve to intersect is a limitation. If the quorum selections are non done carefully, y'all may involve bulk quorums for the system, together with PBFT based protocol would endure later on xx nodes inwards quorum together with xl nodes inwards the system. But at that topographic point are ameliorate ways to select your quorum slices: Instead of a apartment organization if y'all role a hierarchical system, alongside tier 1 nodes, tier 2 nodes, tier iii nodes, together with pick out your quorums through this hierarchy y'all tin dismiss satisfy the quorum belongings alongside most log(N) nodes inwards contrast to N/2 nodes. Hierarchies genuinely move pretty good for scaling. Think of a tree alongside 10 children per node, at degree four at that topographic point volition 10,000 nodes, together with degree five 100,000 nodes.
2. There has been a lot of compass off quorum systems together with probabilistic quorum systems. Can those last employed to help alongside the scalability occupation inwards SCP?
Maybe fifty-fifty some graph algorithms tin dismiss last relevant, similar the "Sparse Partitions" move yesteryear Baruch Awerbuch together with David Peleg.
3. Is it possible to come upward up alongside a service for SCP that provides checks together with prevents nodes from selecting bad quorum slices that Pb to bad quorums?
But why would y'all tryst that service, that service itself should last built inwards a trustless way.
4. How tin dismiss nosotros implement sharding per services inwards SCP?
In the SCP model described inwards the newspaper all transactions are related together with potentially interfering/dependent on each other since at that topographic point is no sharding per services considered. How tin dismiss nosotros implement sharding back upward for SCP that provides parallelism within the services but besides allows occasional cross service transactions together with prevents double spending. Would it last possible to build something similar to the Aspen model for SCP?
The newspaper is long, 32 pages. It looks similar the newspaper is written the way the protocol is conceived together with reasoned about. First comes a department on the federated Byzantine understanding (FBA) model, which talks most quorum slices together with the quorums that lawsuit from them. The side yesteryear side department talks most the requirements for quorum intersections, together with defines the dispensable sets alongside associated theorems. Then comes the federated voting section, alongside subsections titled: Voting alongside opened upward membership, Blocking sets, Accepting statements, Accepting is non enough, Statement confirmation, together with Liveness together with neutralization. On page 19, the Stellar Consensus Protocol (SCP) department starts, alongside to a greater extent than definitions together with the proofs intertwined alongside the protocol description. At this point, the reader is already overwhelmed, trying to hold inwards his hear theories most how the previous nineteen pages powerfulness connect dorsum to this protocol, together with is confronted alongside the chore of reading through a nine pages long SCP protocol section.
The newspaper would last significantly improved if it was rewritten top-down: non inwards a way the protocol is conceived together with proved, but inwards a reader-friendly mode prioritizing the clear communication of the protocol basics.
It was difficult reading through this paper, together with I didn't read it thoroughly. Here is what I understand:
Stellar Consensus Protocol is PBFT which uses quorums derived from quorum slices of federated participants, instead of traditional quorums from a unopen laid of participants.
It would last overnice if SCP provided a machinery that prevents participants from selecting bad quorum slices that Pb to bad quorums.
Background together with context
Traditional Byzantine Agreement protocols stimulate got unopen membership: the lay out of participating nodes together with their identities (via world private keys or via non-transferable symmetric-key MACs) are fixed.SCP is a Federation-based Byzantine Agreement (FBA) protocol which allows opened upward membership instead of requiring unopen membership. In a federated opened upward membership model, nosotros don't know the lay out of nodes inwards the entire organization or all of their identities. Nodes may bring together together with leave.
One way to bargain alongside opened upward membership is Proof-of-Work based blockchains every bit inwards BitCoin. That has problems alongside excessive unloosen energy consumption, inscalability of throughput, together with due to probabilistic nature of the commit long hold off times to stimulate got a skillful guarantee of irreversibility of a transaction.
SCP does non role proof-of-work based blockchains. It adapts the PBFT protocol to move inwards an opened upward membership federated environment. PBFT is a 3-phase deterministic byzantine consensus protocol. It has similarities alongside Paxos: inwards fact if y'all extend Paxos which only tolerates crash faults to tolerate byzantine faults, y'all larn pretty much the PBFT protocol.
The federated model
The federated model way that a node tin dismiss stimulate got a PBFT/consensus understanding alongside a laid of nodes it specifies, without involving all the nodes inwards the network inwards this agreement.To this end, each node specifies a quorum acre inwards its config file. The quorum acre consists of the nodes it trusts, together with hopefully last a various well-balanced portfolio. By declaring its quorum slice, this node says that it finds the consortium of these nodes (not necessarily individually each one) trustworthy, together with volition rely on this consortium to convince itself of the understanding together with volition rely on them to bless/endorse its transactions. Traditional non-federated Byzantine understanding requires all nodes to convey the same slices, inwards FBA the cardinal excogitation is enabling each node to chose its ain quorum acre set.
These quorum slices are used for constructing quorums. A quorum is a laid of nodes sufficient to achieve agreement.
For safety, whatever ii quorums inwards the network involve to intersect, together with the intersection should incorporate nonByzantine nodes. If the quorum intersection consists exclusively of Byzantine nodes, together with hence SCP cannot guarantee safety.
The onus is on the users to supply skillful quorum slices. SCP does non supply a way to banking concern agree the soundness/integrity of quorum slices which give ascent to quorums. Again if the quorum intersection consists exclusively of Byzantine nodes, security is violated together with SCP doesn't convey responsibleness of that. To quote the paper: "SCP tin dismiss only guarantee security when nodes pick out adequate quorum slices."
The SCP protocol starts alongside a nomination phase, which if run long enough, eventually produces the same laid of candidate values at every intact node, which way nodes tin dismiss combine the candidate values inwards a deterministic way to create a unmarried composite value for the slot. Upon predicted/approximated convergence of nomination phase, the nodes get-go the ballot stage to perform federated voting (PBFT) to commit together with abort ballots associated alongside composite values.
When intact nodes concur to commit a ballot, the value associated alongside the ballot volition last externalized for the slot inwards question. When they concur to abort a ballot, the ballot's value becomes irrelevant. If a ballot gets stuck inwards a nation where 1 or to a greater extent than intact nodes cannot commit or abort it, together with hence nodes campaign in 1 lawsuit again alongside a higher ballot; they associate the novel ballot alongside the same value every bit the stuck 1 inwards instance whatever node believes the stuck ballot was committed.
Safety results from ensuring that all stuck together with committed ballots are associated alongside the same value. Liveness follows from the fact that a stuck ballot tin dismiss last neutralized yesteryear moving to a higher ballot. The skillful tidings most SCP is that provided that the quorum status is satisfied, whatever committed conclusion is straightaway irreversible.
Here are some videos on SCP (well generally the motivation together with setup of Federated Byzantine Agreement without the SCP protocol description): https://www.youtube.com/watch?v=mB9UW7HK8pc and https://www.youtube.com/watch?v=zTI1HAWDHIg.
MAD questions
1. What are the scalability limits of SCP?That the quorums involve to intersect is a limitation. If the quorum selections are non done carefully, y'all may involve bulk quorums for the system, together with PBFT based protocol would endure later on xx nodes inwards quorum together with xl nodes inwards the system. But at that topographic point are ameliorate ways to select your quorum slices: Instead of a apartment organization if y'all role a hierarchical system, alongside tier 1 nodes, tier 2 nodes, tier iii nodes, together with pick out your quorums through this hierarchy y'all tin dismiss satisfy the quorum belongings alongside most log(N) nodes inwards contrast to N/2 nodes. Hierarchies genuinely move pretty good for scaling. Think of a tree alongside 10 children per node, at degree four at that topographic point volition 10,000 nodes, together with degree five 100,000 nodes.
2. There has been a lot of compass off quorum systems together with probabilistic quorum systems. Can those last employed to help alongside the scalability occupation inwards SCP?
Maybe fifty-fifty some graph algorithms tin dismiss last relevant, similar the "Sparse Partitions" move yesteryear Baruch Awerbuch together with David Peleg.
But why would y'all tryst that service, that service itself should last built inwards a trustless way.
4. How tin dismiss nosotros implement sharding per services inwards SCP?
In the SCP model described inwards the newspaper all transactions are related together with potentially interfering/dependent on each other since at that topographic point is no sharding per services considered. How tin dismiss nosotros implement sharding back upward for SCP that provides parallelism within the services but besides allows occasional cross service transactions together with prevents double spending. Would it last possible to build something similar to the Aspen model for SCP?
0 Response to "The Stellar Consensus Protocol: A Federated Model For Internet-Level Consensus"
Post a Comment