This analysis compares Algorand to Proof of Kernel Work. Proof of Kernel Work was created by the research team at XAIN AG to produce a low energy yet secure consensus mechanism.
Algorand is permissionless blockchain that uses a Pure Proof of Stake Consensus Mechanism
"Every user can play any role in the protocol in proportion to their stake"
Algorand has 3 embodiments, for the purpose of this comparison, the points of difference are essentially the same whichever form is used. I will look at the embodiment that assumes the honest-majority-of-money assumption.
Proof of Kernel Work is a blockchain consensus mechanism created by the XAIN research team in 2017.
PoKW could be used with any blockchain, though the initial implementation was on Ethereum, starting with a software fork of the go-ethereum client.
Algorand and PoKW share some common concepts and stages, most notably the use of cryptographic sortition to select a committee of validators.
Each round corresponds to one block starting with a whitelist of accounts and the current blockchain history
For both PoKW and Algorand, a new committee is formed for each round.
= total number of users
= number of users in whitelist
= number of users on committee
= target committee size
= number of honest users
is the block at height r
is the hash of the previous block
= seed at blockheight r
is the set of transactions at blockheight r
= ith committee member at blockheight r
is the PoW nonce for block
is the digital signature of the message m with the private key that corresponds to the public key
refers to the real number in the open interval obtained by interpreting as the mantissa of that real number over the binary representation of reals
For PoKW we use the term user synonymously with public key, a person having two public keys would be seen as two users. For Algorand the participation is proportional to the user’s balance.
Cryptographic sortition uses a seed available in each block to produce a verifiable random function (VRF) which selects verifiers into a committee.
In PoKW there are 2 possibilities for seed selection
In each round every user calculates the seed for round as
Here an adversary cannot predict the seeds for subsequent blocks
If there is an empty block (because an malicious leader in the previous round produced an invalid block) however, the seed is calculated as .
Thus an adversary could predict the seed for the next block, having produced an invalid block in he current round.
Although this is less secure, there could be an advantage to having predictable seeds, in that users could predict in advance when they would be selected to the commitee and then go offline until that block height, or ensure that they are online at a particular block height.
For PoKW, at blockheight , user in the whitelist calculates the following to determine if it is a member of the committee for that block
If this evaluates to true, then the user is eligible for the committee at that block height.
Algorand uses tokens to in the sortition function, for a particular account a larger token balance will increase the chances of being selected to the committee.
PoKW does not have a native token, each account in the whitelist has an equal probability of being selected in each round.
In both Algorand and PoKW it is assumed that hash function H is a random oracle, thus the committee is a random subset of the total users of the system.
“Algorand works in a very tough setting, Algorand works efficiently and securely even in a totally permissionless environment, where arbitrarily many users are allowed to join the system at any time, without any vetting or permission of any kind. Of course, Algorand works even better in a permissioned environment.”[1:1]
Under the Honest Majority of Money assumption,
Any Adversary may
PoKW works in a less tough setting of a permissioned (and usually private) network.
Taking the Proof of Work stage where any user on the committee may be a miner, we have the assumptions that
Any Adversary may
Since Algorand, has multiple rounds in consensus, it is vulnerable from message withholding or disruption, whereas PoKW can proceed albeit with an increase in fork frequency.
PoKW has the standard Ethereum block header plus the following fields:
“Algorand’s blockchain may fork only with negligible probability (i.e., less than one in a trillion)”
Two blocks can never be added to the chain at once because only one block can have the required threshold of committee votes. At most, one block is certified and written to the chain in a given round. Accordingly, all transactions are final in Algorand. When the consensus protocol decides on a block, this decision is never changed. Every honest user soon learns of this decision, and no honest user ever thinks that a different block at the same height was chosen.
For Algorand based the probability of the consensus mechanism resulting in a fork at each round is <
For the Ethereum based PoKW implementation forks follow the expected Ethereum frequency, roughly 5%, there is no notion of uncle blocks, since there is no economic reward to produce blocks, uncle blocks give no advantage.
For both Algorand and PoKW, such forks can be resolved by the heuristic of “following the longest chain”
The major differences between PoKW and Algorand are:
Kiayias,Russel,David, and Oliynycov.Ouroburos: A provablysecure proof-of-stake protocol.
Pass and Shi.[The Sleepy Model of Consensus.] (https://eprint.iacr.org/2016/918.pdf)