A comparative analysis of Proof of Kernel Work and Algorand.

Introduction

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.

Overviews

Algorand

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”[1]

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 (PoKW)

Proof of Kernel Work is a blockchain consensus mechanism created by the XAIN research team in 2017.[2]
PoKW could be used with any blockchain, though the initial implementation was on Ethereum, starting with a software fork of the go-ethereum client.

Commonalities

Algorand and PoKW share some common concepts and stages, most notably the use of cryptographic sortition to select a committee of validators.

Consensus Stages

Stages of Algorand

1. Use cryptographic sortition to select a committee of validators
2. Validators follow a Byzantine agreement protocol to form consensus on the next block.
3. Block Proposal: Accounts propose new blocks to the network
4. Soft Vote: Committee votes on proposals and filters down to one
5. Certify Vote: Separate committee votes to certify the block
6. Each node receives a certificate for the block and writes it to the ledger

Stages of PoKW

Each round corresponds to one block starting with a whitelist of accounts and the current blockchain history

1. Cryptographic sortition is used to select a committee of potential block producers from the whitelist.
2. Committee members may then run the Ethash Proof of Work mechanism to select a leader, who then submits a block (along with proof of committee membership and valid proof of work nonce ) to the network.

For both PoKW and Algorand, a new committee is formed for each round.

Notation used in Algorand and PoKW

𝑛𝑡 = 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
𝐻(𝐵𝑟−1) 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 𝑝𝑘
𝑆𝐼𝐺𝑝𝑘(𝐵𝑟)
0.𝐻(𝑚) refers to the real number in the open interval (0;1) 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 in PoKW and Algorand

Cryptographic sortition uses a seed available in each block to produce a verifiable random function (VRF) which selects verifiers into a committee.

Seed Selection

In PoKW there are 2 possibilities for seed selection (𝑄𝑟)

1. The seed is calculated dependent on the signature of the leader for that block
2. The seed is calculated solely based on the previous seed (i.e. ) 𝑠𝑒𝑒𝑑𝑟=𝐻(𝑠𝑒𝑒𝑑𝑟−1||𝑟)

Algorand VRF function for cryptographic sortition

In each round 𝑟 every user 𝑢 calculates the seed for round 𝑟 as ⟨𝑠𝑒𝑒𝑑𝑟,π⟩←𝑉𝑅𝐹𝑠𝑘𝑢(𝑠𝑒𝑒𝑑𝑟−1||𝑟)
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 𝑠𝑒𝑒𝑑𝑟=𝐻(𝑠𝑒𝑒𝑑𝑟−1||𝑟).
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.

Proof of Work Cryptographic Sortition

For PoKW, at blockheight 𝑟, user 𝑖 in the whitelist calculates the following to determine if it is a member of the committee for that block

0.𝐻(𝑆𝐼𝐺𝑝𝑘𝑖(𝑟,𝑄𝑟))<𝑛𝑐𝑡𝑛𝑤

If this evaluates to true, then the user is eligible for the committee at that block height.

Differences in approach to cryptographic sortition

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.

Security Assumptions

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

“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

1. instantaneously corrupt any user he wants, at any time he wants, provided that, in a permissionless environment, 2/3 of the money in the system belongs to honest user. (In a permissioned environment, irrespective of money, it suffices that 2/3 of the users are honest.)
2. totally control and perfectly coordinate all corrupted users; and
3. schedule the delivery of all messages, provided that each message m sent by a honest user reaches 95% of the honest users within a time λm, which solely depends on the size of m.

Proof of Kernel Work

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

1. Miners are a resource controlled by the governing organization or consortium and have identical hardware. In particular, miners are not rewarded nor need incentive structures.
2. Miners may be corrupted and misbehave, by for example refusing to mine, or taking part in selfish mining.
3. Miners begin the computation of hashes in approximate synchrony:

Any Adversary may

1. instantaneously corrupt any user he wants, at any time he wants, provided that, 51% of the whitelisted users at any one time are honest
2. Totally control and perfectly coordinate all corrupted users

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.

Data Structures

Block Definitions

Algorand

(𝑟,𝑇𝑟,𝑄𝑟,𝐻(𝐵𝑟))

Proof of Kernel Work Additional fields

PoKW has the standard Ethereum block header plus the following fields:
𝑄𝑟,𝑆𝐼𝐺𝑝𝑘(𝐵𝑟)

Finality

Algorand

“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.

Handling non contested forks

For Algorand based the probability of the consensus mechanism resulting in a fork at each round is < 10−18
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”

Summary

The major differences between PoKW and Algorand are:

1. PoKW requires a permissioned setting whereas Algorand can run in a non permissioned setting.
2. Algorand uses a token to allow participation, a larger stake will give a higher probability of becoming a block producer. PoKW has no token, and no reward for block production.
3. Algorand validators follow a Proof of Stake protocol once selected to the committee, whereas PoKW committee members follow a Proof of Work protocol
4. Algorand has faster finality with extremely low probability of a chain reorganisation.

Similar works to PoKW

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)

PoKW Github Repo

Proof of Kernel Work is an open source project promoted by Extropy.

The repo is hosted on Github here : PoKW Repo

White Papers

1. Chen and Miscali : Algorand ↩︎ ↩︎
2. Lundbæk,Beutel,Huth,Jackson, Kirk and Steiner : Proof of Kernel Work ↩︎