Please enable JavaScript.
Coggle requires JavaScript to display documents.
Trust with trust: Distributed systems & Consensus - Coggle Diagram
Trust with trust: Distributed systems & Consensus
issues
unknown nodes on a network
untrusting
but need to agree on something
Nakamoto Consensus
a new paradigm of distributed consensus
proof of stake
focuses
distributed system
proof of stake
Nakamoto consensus
voting based consensus
federated consensus
Distributed systems
deploy blockchain across a network
agree on a common truth without trusting a centralized authority
trust protocols and math behind
starting from design formalism
Leslie Lamport:
time, clock, ordering of events in a distributed system
two events can happen at separate times in parallel and not intervene each others
causality
what it means for one take place before another in logical or physical sense
e.g. detection of error and error correction
safety
it will not happen
liveness
it will eventually happen
it requires regulation; otherwise troublesome
blockchain is a specific type of distributed systems
two components in common understanding
nodes
separate (distancing) machines or processes
messages passing with arrows or edges (in graph theory)
info moves between machines
machines may or may not be connected directly or indirectly
machines are working well as a whole
vs a single system
all separate machines working for a common goal
more reliable even some of them are faulty or crashed down
components processing information concurrently
rather one step at a time
NO global clock
each node maintain its own time
potential problems
dropped messages
failed processor
protocols to ensure the job done, even processor failure happened
consensus algorithm
based on some input, nodes have to agree on the output
achieving validity, agreement, and termination
validity means any value decided upon must be processed by one of processes
safety
honest nodes will not decide on trivial, random or different values
agreement means all non-faulty processes must agree on the same value
it will not accept inconsistent results
safety
termination means all non-faulty nodes will eventually decide on some values
liveness
to specify what must happen for the system to be considered correct
all non-faulty nodes will decide on a value
CAP theorem of trilemma by Eric Brewer
consistency
every node provides the most recent state of the system
if no, it will not respond
safety
no node will provide an outdated state
no two nodes provide different states at any given time
avaliability
every node has constant read and write access
liveness
allow to make updates or retrieval from the system without delay
partition tolerence
partition means any two nodes cannot communicate with each other on the network
unbounded network latency --> message cannot get to the recipients
safety
the system will not stop functioning even with certain partition
trilemma
only two properties would be true at any given time
intersections between properties
challenges
Byzantine Generals' problem
consensus issue
fail-stop fault
Voting based Consensus algorithm
a solution to the traditional distributed system
classical consensus of distributed system
mathematical reasoning
formal proof
few nodes
a series of rounds
processing explicitly votes on new updates to the system
Paxos
a consensus algorithm by Lesilie Lamport 1989 who was the author of Byzantine Generals problems, and time, clocks, ordering events in distributed system
root of entire consensus algorithm
implementation could vary
the basic is
Paxos parliament to pass decrees,
each legislator maintain a ledger
legislators: proposers, acceptors, learners
a key majority of acceptors are quorum that must vote for a new bill
Federal consensus algorithm
protocols - several rounds till reaching a consensus
each round
prepare
citizens to proposers --> decree to parliament
decree has a number and value
accept
Parliament -> distributed database;
citizen -> client program;
current law -> database state
assumptions:
no node subvert the protocol
messages are delivered without corruption
only for fail-stop scenario, not Byzantine faults
Raft
alternative to Paxos
leader based approach
JP Morgan Quorum
enterprise version of Ethereum
a raft-based consensus faster than proof-of-work algorithm
one elected leader, communicating directly the client
orchestrating the sending messages to other nodes
maintaining log replications on other servers of the cluster
leads tills it disconnected or fails
sending heartbeat messages in a frequency to other nodes
not hearing the heartbeat --> assuming it's dead
first node to timeout becomes the leader
accepts the request from the client and oversees all other nodes
Practical Byzantine Fault Tolerance (PBFT)
1999, by Miguel Castro and Barbara Lisvkov
handles less than one third of Byzantine faults
3f+1 total nodes
the system handle f Byzantine faults
in 1984, Sun Microsystem
BTF-NFS
main phases
pre-prepare
client send request to the primary node
the primary node sends out a pre-prepared message which consists of sequence number, signature, metadata, to other nodes for getting preapared
confirm to prepare (nodes except the primary one, sending message to others
if a node accepts the pre-prepared message, then it send out a prepared message to every node
Commit
after prepared, all nodes except the fault one, sending out a committed message to others.
If a node receives f+1 valid commit messages, then carry out the client request and send out the reply to the client
the client waits for at least f+1 reply
nature
voting is done explicitly with a known set of nodes or participants
Nakamoto Consensus algorithm
a solution to the new distributed system
white paper in 2008 to propose a new consensus way
voting implicitly
random lottery based on consumed resources for making an update to the system
requiring miners' hash power for proposing the next block
Bitcoin's proof of work mechanism
elect a leader to propose a new block by lottery
unknown and untrusted peers
anyone can join or leave the network
allowing to send false or corrupted messages
a user may have multiple private/public keys for virtual identities
voting power in association with the scarce resources - computational power
pay to play style
longest chain policy
a fork resolution policy
voting-based refers to consensus mechanism requiring explicit votes from nodes on the next update
Byzantine Fault Tolerance (BFT) based proof of Stake
proof of stake
validators consuming native currency
proof of activity
hybrid consensus
proof of work
miners solve and submit blocks to the system
proof of stake
block header contains data of a random group of validators who are required to sign the new block
block fee and rewards are share among miners and validators
proof of burn
send the Bitcoin to an irretrievable address
paying the transaction fee to no one
proof of space
consuming storage space
low energy cost
using disk space to solve problems
proof of capacity
a memory hard proof of work protocol
proof of elapse time
users consume time
waiting for a random time
nature
voting is done implicitly through the use of resources, implying not all participants may be known
Proof of authority
permissioned
non-production
used in Kovan and Rinkeby Ethereum testnets
resources consumed - identity
political centralized systems
consensus obtained by independent pre-selected validators
oracle network
formation of a validator based on the confirmation of personal data
https://changelly.com/blog/what-is-poa-network/
advantages
significantly reduce the transaction fees, and the use of smart contract
ensure fast network operation
proof of stake
background
concerns over energy cost and scalability
economic stake
more coins more stewardship
validators
create a block pointing to the previous block
get block rewards and transaction fee
get the approval from the rest of the network
chain based proof of stake (PoS) algorithm
those who have more coins are more likely chosen to be the validator
proportional to the stake invested from the groups of already existing validators
why choose availability over consistency?
BFT based proof of stake (PoS) algorithm
choose consistency over availability
the first step is same
randomly choose an validator based on the proportion of stake invested
create and propose a new block to the rest of the network
if two third of voting power or total stake say yes, it will accept the block
otherwise, it choose a new validator to propose a new block and repeat the voting again
in 2014, Tendermint published
used in blockchain network Cosmos
two stage voting process
favor satety (consistency)
by Jae Kwon
academic rigor
a chosen set of validators of a specific size at any given point with bonded state
globally known and predefined validator set
weakly synchronous
timeout issue
application blockchain interface --> tendermint consensus engine
own native token
a generalized middleware for replicating applications on many machines
scalability issue to a large number of validators
used in production in private, permissioned environment, in Cosmos
three rounds of consensus processes
two third of validator set must vote for the proposed block
1st round: the rest of validators prevote block (valid) or nil (invalid block or failed to respond in time)
2nd round - precommit
precommiting the block requires two third prevote for the block (polka); otherwise, prcommit nil
3rd round - new (block) height phase and select another validator to propose a new block using round-robin selection algorithm
has a global predefined set of validators
at a height of blockchain, an validator is chosen randomly based on the proportion of bonded token, to propose a new block
if two thirds of validators premitted the block, the block is committed. otherwise, a new voting round starts.
energy efficient and fast
favor consistency over availablity
Casper has two versions
Casper the Friendly Ghost
a consensus protocol - a Correct by Construction CBC methodology
pure PoS
from scratch to satisfy the certain safety proof
the implementation requires a much drastic overhaul
PoS checkpoint every epoch (50 blocks)
Casper the Finality Gadget
a chain and BFT-based Proof of Stake & Proof of Work Hybrid
Vitalik 's Casper
is taking a step-wise approach to upgrade Ethereum to cast out the PoW approach
GHOST protocol is Ethereum solution to its fast block times
when compared to block propagation rates and latency, forks would occur more. some valid block might have to be cast off because another block has validated earlier.
the castaway block called uncle block as it might not be included in the longest chain but represent some computation done with it.
so, GHOST protocol will calculate which has the most accumulative work done , in order to fork resolving policy.
Casper is a planned upgrade to Ethereum
from PoW to PoS
Casper FFG - overlay PoS to PoW
Federated consensus algorithm
nature
using explicit voting to avoid consuming resources much like PoW
but allowing anyone to participate without being Sybil attacks
essential concepts
quorum - a set of nodes sufficient to reach agreement
In PBFT, over two thirds of the voters
how to choose peers to trust without central authority
how to choose a quorum in decentralized way?
Federated Byzantine Agreement
latency is low because it consumes less computational power
first cryptocurrency of Ripple uses this consensus
real time gross settlement system currency exchange
remittance network
allows banks to send money to oversea branches in low fees
distributed ledger across financial institutions
permissioned ledger
banks are required to authenticate before accessing to Ripple Ledger
offer quick and decentralized cross border payments to big financial institutions
allow banks to self-select trusted peers and maintain a collective history of transaction
Note: distributed ledger is not necessarily to be blockchain system
the data structure is not a blockchain
validating nodes take part in consensus whereas tracking nodes maintain the transaction history
individual nodes decide their own quorum
Stellar
public version of Ripple
open source protocol for exchange money
platform connecting banks, payment systems, and people
open ledger
non-profit distribution of wealth
quorum slices
subset of a quorum can convince one particular node of agreement
individual nodes can decide which to include in their quorum slice
quorum intersections
form a larger quorum and ensure consensus through the entire network
multiple quorum slices join together
otherwise, we get disjoint quorum slices
trust those who are popular and existed for a while