Albatross - An optimistic consensus algorithm

#1

Albatross - An optimistic consensus algorithm

Nimiq Foundation & Trinkler Software (Vol.3, 2019)

Abstract—The area of distributed ledgers is a vast and quickly developing landscape. At the heart of most distributed ledgers is their consensus protocol. The consensus protocol describes the way participants in a distributed network interact with each other to obtain and agree on a shared state. While classical consensus Byzantine fault tolerant (BFT) algorithms are designed to work in closed, size-limited networks only, modern distributed ledgers – and blockchains in particular – often focus on open, permissionless networks. In this paper, we present a novel blockchain consensus algorithm, called Albatross, inspired by speculative BFT algorithms. Transactions in Albatross benefit from a strong confirmation, and instant confirmations can be achieved as well. We describe the technical specification of Albatross in detail and analyse its security and performance. We conclude that the protocol is secure under regular PBFT security assumptions and has a performance close to the theoretical maximum for single-chain Proof-of-Stake consensus algorithms.

Read the full Albatross paper here: https://katallassos.com/papers/Albatross.pdf

Additional reading on Proof-of-Stake: https://github.com/ethereum/wiki/wiki/Proof-of-Stake-FAQs

Additional reading on CASPER (Ethereum): https://github.com/ethereum/wiki/wiki/Casper-Proof-of-Stake-compendium


Whilst we don’t know the full ramifications of what Albatross entails for Nimiq (yet), there are a number of interesting discussions to be had. Discuss!

To structure discussions there will be a numbering system put in place for each topic. If you have questions / discussion points to add to the list please comment!

Questions & Discussion points

  1. Does PoW inherently give a coin value or does the utility attached to the coin give it value?
  2. Proof-Of-Stake (PoS) as an economic model that makes the rich, richer, and the poor, poorer.
  3. In a PoS system, no capital is at risk which is the opposite of Proof-of-Work (PoW).
  4. Decentralisation: PoS vs PoW
  5. Question on Delay attacks by @kenblazer
2 Likes
#2

PoS is certainly a step in the right direction. Looks very promising and I can’t wait for a proof of concept :ok_hand::ok_hand:

#3

Question: The WP describes the process for dealing with Delay attacks as requiring 2/3 of the validator nodes to request a View Change. Could this make a 34% attack possible? If so, could the 2/3 quorum be a variable instead of a constant that keeps decreasing if the countdown timer gets high enough.

1 Like
#4

I sent the Albatross paper to Pyrofex www.pyrofex.io. I think pyrofex are very strong and making nice research in consensus protocols and their feedback will be valuable and you may consider doing some research together. They have just released their paper for their POS consensus algorithm if you want to check (https://twitter.com/pyrofex/status/1103464661138038784).

I paste here the comments from Pyrofex to me in their TG channel:

“We looked at it this morning. It looks fine and it might work, but it is basically a way of taking turns at block production. We don’t think any kind of master election style protocol can be made to scale. Also any time you see someone producing a chain instead of a DAG, it’s not gonna scale and they are probably too focused on their protocol and not focused enough on the transaction model.”

“We also recently reviewed Thunder… here is what I sent to a friend who asked us about their protocol…”

"The protocol Thunder is using requires good network conditions to make progress on the fast chain. That is not what Casanova requires. In fact, Casanova remains fast even when network conditions are degraded, because validators can attest to blocks anyway and fix conflicts later when network conditions improve.

When we say “optimistic consensus” what we mean is that Casanova finds consensus under the optimisitic assumption that people aren’t double spending. This has nothing to do with network conditions.

When Thunder says “optimistic conditions” what they mean is that the network is fast and the centralized accelerator is working properly. This has nothing to do with transactions.

Our protocol is going to work much better, IMO. The thing we did that is so unique is we designed a protocol and transaction model that work together, instead of designing them separately. That turned out to make a big difference in complexity for the protocol."

#5

Interesting, I’m going to give their paper a full read at some point today to compare it to Albatross, AFAIK the team haven’t decided (announced) anything regarding the accounting layer that’s suppose to fit on top of Albatross.

1 Like
#6

Albatross algorithm comparison article by pyrofex https://medium.com/pyrofex/other-blockdag-algorithms-44215e3307ab

#7

Forwarded from telegram, originally written by me:

Indeed there’s a lot to discuss with Albatross and 2.0 in general, which is why my general feeling is it’s farther away than we think.

Concerning malicious transactions though, why would a minimum prevent anything. If you’re not staking enough your chances of proposing a block so you can add a malicious transaction is low, and most anyone who wants to propose malicious transactions is going to know they need resources.

I feel like you’re telling me that we need to worry about Joe Schmoe who is adding malicious transactions to the blocks he mines rn but his miner only has 3KH/s. And if Mr Schmoe wanted to really attack the network, he’d get more hashrate just like how if someone really wanted to attack a POS network he’d just get more stake.

A minimum stake Imo only:

  • makes it impossible for honest miners with small balances to participate in the network (so less decentralized)
  • only makes it harder for someone to attack the network, not impossible. And again, anyone who’s pulling an attack that’s worth anything wont be some 18 year old with 500 NIM collected by abusing faucets, but instead someone who’s been in crypto a while and has been saving up NIM for an attack.

A minimum just seems to make the rich richer, practically challenge someone to attack the network (this mirrors my opinion about adding more security to the faucets as well), and keeps out honest miners who only recently found out about NIM.

#8

What do you mean by #3 “In a PoS system, no capital is at risk which is the opposite of Proof-of Work”?

As I understand PoS, rather than earning the right to validate a block by solving a cryptopuzzle (mining) you randomly earn the right to validate the block by having staked your coins. If you try to cheat the system, you lose your stake, hence the security of a PoS model and hence your capital is very much at risk. It’s PoW that has no capital at risk; you have capital tied up in mining rigs of course, but even if you get caught trying to game the system, you can’t have your capital taken away.

2 Likes
#9

Yeah you pretty much summed up PoS perfectly. When this post was made the idea of Albatross was new, many people’s understanding of PoS was surface level at best, and lack of capital at risk was a big point people were worried about.

While you’re right that in PoS your investment goes up in flames if you are caught misbehaving, and in PoW your investment can be reused. But in PoS your investment is in the token which in Nimiqs case is incredibly cheap so it’s cheaper than PoW to attack the network. This is only temporary though so I think PoS has good incentives against malicious nodes.

2 Likes
#10

“In a PoS system, no capital is at risk which is the opposite of Proof-of Work”

While I wouldn’t call it the opposite, it’s true.

With Albatross, your capital is only at risk if you mine a micro block fork with a common digest. In simpler words, you’re breaking the rules if you sign and broadcast two different blocks at the same height during your turn.

Your funds will only be slashed if you deliberately attack the network.

When mining on a PoW chain on the other hand, you invest a part of your capital into expensive mining hardware. With virtually every PoW-based chain, there is a high risk that a cheaper and faster way to mine emerges (GPU, FPGA, ASIC), making your old hardware worth less. Additionally, you are subject to 51% attacks.

2 Likes
#11

Who decides whether you deliberately attack the network?

#12

@robin In Albatross, validators take turns when creating blocks. The order is known in advance. Let’s call it a list of “slots” for now.

Your funds are slashed when relaying two micro blocks on the same slot, thus creating a fork.

As each validator must sign his created blocks, the two signatures of the blocks causing the fork form a valid proof. Albatross calls this a “slash inherent”.

Because only you can sign blocks with your validator private key, the slash inherent can’t be faked (honest stakes are safu).

Furthermore, no honest validator would ever want to create a fork because it creates an inconsistent blockchain state.
A malicious validator might have an incentive to include a transaction (T) in one block (A) but not in the other (B). He relays both blocks in an attempt to have T reverted by causing a rebranch from A to B.

1 Like
#13

Here is what I think : pow is the best way to distribute coins to users , POS main flaw is that it creates coins only to ppl that already have them. 51% attack can be solved with dpow (see Komodo and arrr and other coins using it ) . Tansactions speed should be solved with overly protocols and not at the core first layer , and more importantly when there is a actually need from users to have faster txs.
POS Blockchains don’t have stock and flow economics and they have very poor game theory incentives .

#14

I kind of share the outlook that PoW makes more sense in terms of economics, it encourages liquidity (miners have to pay the electricity/hardware in one way or another and so reinject the coins they mined into the economy) while there are not such spendings involved with PoS (besides minor server costs which don’t need to scale with the stake) which benefits the whole ecosystem.

Worse it actually discourages people to spend their coins even more than the fixed supplies (does not make sense to spend NIM when the entire system incentives you to hold twice as hard as with a PoW coin).

I’m not a big fan on relying on another blockchain like Komodo does either though
AFAIK the only PoS algorithm trying to mitigate these effectss and encouraging liquidity is the one of NEM with PoI (Proof of Importance) but I don’t know how it performs in practice: https://nem.io/NEM_techRef.pdf

In any case, scaling is a necessity but it’s still less important than NIM economics on the long term.

1 Like
#15

This discussion teached me more in 15 minutes of reading, than a month of studying ahahah :grin:

1 Like
#16

POS main flaw is that it creates coins only to ppl that already have them.

This is not an argument for PoW. You can only expect profit with PoW coins if you have cheap electricity and access to specialized hardware. I have little doubt that getting access to enough coins for staking is easier. Even after getting access to the mining hardware, it takes hours to days to set everything up. And after a year, your rig lost at least 25 % in value and profits start to shrink because of rising difficulty. With PoS, you connect to the network with your existing hardware.

Essentially, staking is more accessible and gives the holders the control back they should have had in the first place.

I kind of share the outlook that PoW makes more sense in terms of economics, it encourages liquidity

That’s true, but not viable for the long run. Looking at Bitcoin, while I’m sure mining helped raising the price initially, it isn’t the driving factor behind Bitcoin’s success for sure.

In any case, scaling is a necessity but it’s still less important than NIM economics on the long term.

Nimiq is a payment protocol, so scaling and near-instant transactions are vital for the project’s success in my opinion. They aren’t possible with classic PoW.
You’re correct, scaling is less important than NIM economics. But mining is just a small part of coin economics. Running a highly-accessible payment protocol isn’t.

Also, disclaimer: Personal opinion that doesn’t represent Nimiq’s

#17

Here is what I think about your arguments :
They are all actually less secure , solid and true compered to the test of time pow Blockchain like btc . Simple imagine that instead of Nim your arguing about put btc and it will make all your arguments not relevant ( talking about scaling , distribution , and so on )
Another main point besides what I already mentioned about pow is that it is the best way to determine inflation in a Dynamic way blocks generation speed is influenced by price. Imo this chart illustrate this very well

when the price is high so is the inflation rate and visa versa . IMO We don’t have any coin old enough that uses POS to make reasonable decision about changing consensus to such . What is probably going to happen if you will change to so called better pos consensus is this ,
Another project will come and start using this new pos from day zero probably even forking you or airdroping some % of coins to your current user base and the only thing that will make nimiq better is it’s time advantage … Anyway I am not nosterdamus I simply think and actually sure about that changing consensus as a marketing move (this is how it appears actually ) is a very bad idea . P.s don’t forget or at least be aware of what you are asking for , chance of having : Down time for all nim network , alots of waiting , soon tm mode , pump and dump or dump and dump and market unsuretenty .

#18

Changing to PoS isn’t a marketing move, that’s a bit far fetched. Of course there will be zero downtime and a fluid transition.
No reason to be worried. If you are, feel free to make a Nimiq PoW fork :kissing:

1 Like
#19

Nimiq is a payment protocol, so scaling and near-instant transactions are vital for the project’s success in my opinion. They aren’t possible with classic PoW.

The last sentence is up to debate, PoW scaling is currently in large part limited by infrastructure performances (processing power, bandwith and storage), these will inevitably improve in the future and allow more on-chain transactions, now we can debate if it will ever be enough (but I think it will since the incentive is here).

As for scaling I think we should keep in mind that the goal is to scale enough to keep with the demand, it’s not an engineering race or at least if crypto as a whole is race between protocols then you won’t win it with these numbers only.

I am not a miner myself and would actually benefit way more from staking but I would rather have less power in a better system than more in a worse one.
Now let’s imagine NIM tomorrow becomes a world currency, here would be the situation:

  • Spending is effectively punished as when you spend 1 NIM you don’t only spend 1 NIM but the percentage of the undistributed supply + the fees you could get out of it (by far the biggest problem in terms of game theory). Let’s not talk about the liquidity problem it creates because it would be endless.
  • Rich become richer without risking capital (like miners do) or at best with a slight opportunity cost, but ultimately “print money” with very negligible cost/risk for their capital while the poors become poorer simply because the poor must invest a larger relative chunk of their money to survive (this is already true in the current system but here it’s even more obvious).
  • With the precedent points in mind, staking will lead to the formation of very strong cartels, you could argue the same for PoW though, the difference is that miners can be overpowered by competitors through innovation, validators are effectively unmovable

In any case, yesterday I stumbled upon this paper proposing an alternative mechanism of minting to current PoS with an auction system, funnily it comes from people in the CISPA (the university where a lot of people in Team Nimiq come from, maybe worth to call them @paberr :slight_smile: ): https://eprint.iacr.org/2018/1110.pdf

An auction is a mechanism which runs with some pre-determined rules to sell some item of value.It involves the participation of several parties whose roles are well defined. In the simplest ofsettings, there is a seller who puts an item on sale and more than one interested buyers competewith each other by placing bids, or the cost they are willing to pay for the item. The highestbidder is announced as the winner and is required to pay a certain amount of money and theitem is awarded to this winning buyer. Here we give a brief overview of some of the basicconcepts of auction theory.

Now knowing if there is a compatibility with Albatross is another story but I would be disappointed if Team Nimiq does not come with at least a solution to mitigate the issues coming from the current PoS models.

2 Likes
#20

I understand your points against PoS and we’re definitely open to changes that would improve Albatross. We’re already discussing some changes and interpretations of Albatross.

I will definitely take a look at the paper you linked and have a chat with Nico about it.

5 Likes