Improve resiliency in increasingly decentralized Algorand

[pao-beep]

Status

Today the increasing online stake is getting decentralized by others other than algorand foundation and technology holding a majority of stake and we are moving to a type of p2p where relays are optional and less professional but more independent unknown parties are running nodes for rewards compared to 2020. Nevertheless, there are 2 entities controlling ~40% of online stake posing a security risk. Today on algorand only one entity(kiln or AF) holding 20-24% can very highly likely halt the chain and/or severely degrade performance if they go offline at once or deviate from the protocol. The 20% is based on our hard coded h parameter at 80% and committee thresholds. Surprisingly there hasn't been concrete explanations and reasons why these figures were chosen or why it shouldn't be adjusted by protocol developers anywhere. In an increasingly decentralized network with increasing unknown parties, increasing vary nodes, increasing varying hardware, p2p etc this 20% threshold is low. In an environment where networks are being evaluated by institutions and government warming up to crypto currencies and what each has to offer, seeing majority of other networks tolerating more than 20% might cast an unintended poor light on our cherished network, algorand.

Expected

Given that safety is rare to violate and currently on algorand requires far more entities and coordination especially in light of our innovative selection, we should expect more liveness violations given the environment we are increasingly heading towards.

Solution

To combat this we should tolerate (25-30%] of online stake going offline at once/deviating from protocol which is closer to theoretical minimums that can still guarantee consistency. We can either adjust our h parameter and/or adjust our committee thresholds and sizes. We can for example still maintain our h parameter value but adjust committee thresholds to be ~68% of committee sizes. We can also adjust our h parameter to be (70-75%] which should cause an increase to committee sizes. All this means is that the protocol can tolerate more so long as theoretical minimums are not exceeded.

Dependencies

Protocol developers and designers. It's possible that we might lose just a little bit of speed if we increase committee sizes.

Urgency

I think it's critical as p2p is nearing completion, more independent stake is getting online and nodes run by less attentive people eg I've seen a 45 million stake get suspended. Kiln is one of the largest online staking holders(20%). Recently Kiln had a security breach occur in September 2025, where a sophisticated attacker bypassed security measures and stole customer funds from the staking provider. What if this happens to their algorand nodes where instead of funds stolen nodes go offline instantly

[joe-p]

I recommend anyone interested in this topic to check out this paper

This is largely outside my area of expertise, but my understanding is that the relationship between that 20% number and the committee sizes are non-linear. Going from 20% to 30% would be a jump in order of magnitude of committee sizes. The current numbers were chosen as a good balance between liveness and scalability. We could potentially increase committees by a small number, but small increases would have an even smaller relative change on the liveness threshold.

[pao-beep]

@joe-p in that paper they actually recommend increasing committee sizes for late, redo and down committees for their liveness bounds to be meaningful. Yes committee sizes will increase but it's not exponential and thresholds could be adjusted without touching h

[joe-p]

Yes increasing committee sizes strengthens liveness but it comes at a cost. For example, keeping the current safety gap we have today and tolerate 30% offline stake we'd need to 16x the committee sizes. Of course we could also consider reducing the safety-liveness gap, but Algorand's strict choice of safety over liveness is quite valuable imo and decreasing the gap seems counter-productive to that philosophy.

[pao-beep]

@joe-p where are you getting 16x from? You're not getting more ~3x in committee sizes even in the most extreme case. It should be noted that committee sizes are not nodes but the algo tokens themselves. With these changes it's still strict safety over liveness, we are not losing that at all

[derbear]

If you are interested in playing with the parameters, we (mostly via @fabrice102) have a SageMath notebook that might be helpful (and which corresponds with the analysis in our paper).

https://github.com/fabrice102/analyzing-algorand

[joe-p]

Thanks @derbear!

@pao-beep Using the notebook with a threshold of 68% and an alpha of 30% (h = 70%) results in the committee sizes needing to be increased by ~32x to meet the same safety and liveness bounds.

https://github.com/joe-p/analyzing-algorand/blob/alpha_.3/proba.ipynb

[joe-p]

With an alpha of .25 we get more reasonable numbers: 3x increase in committee size with a threshold of 0.72

https://github.com/joe-p/analyzing-algorand/blob/alpha_.25/proba.ipynb

While certainly better than alpha = .3, I think 3x committee sizes is a hard sell for a 5% buffer.

[pao-beep]

@derbear thanks so much! That's great

@joe-p I'll try on my end but getting half way to 30% i.e from 20 to 25 is a good sell for me with just 3x. Again it's the algos not nodes. At 25% it at least mitigates a single entity now from nuking algorand it's not a far off concern. And it's a better threshold in the environment we are increasingly heading towards as outlined earlier. If anything, we should at least follow through on the recommendation of Derek's and Fabrice's paper you shared.

[joe-p]

I'll try on my end but getting half way to 30% i.e from 20 to 25 is a good sell for me with just 3x. Again it's the algos not nodes. At 25% it at least mitigates a single entity now from nuking algorand it's not a far off concern. And it's a better threshold in the environment we are increasingly heading towards as outlined earlier.

Right initially I was thinking that 3x committee sizes means 3x bandwidth/compute for each step, but I realize that is worst case scenario where none of the votes are weighted. We'd have to crunch the numbers, but real world bandwidth/compute would probably be much less than 3x.

One thing to also consider is that lowering committee thresholds does lower the stake percentage required to effectively cause a safety failure (double spend/fork).

If anything, we should at least follow through on the recommendation of Derek's and Fabrice's paper you shared.

Just speculating, but my guess is that the down vote committee is already so large a increase in this committee that has a meaningful impact on in the liveness is not worth the tradeoff. 2^-12 is still a fairly low probability and failure here results in slower recovery, not sustained loss of liveness.

I think it first needs to be decided if we want to increase alpha and then decide if/how we want to change committee sizes.

[pao-beep]

One thing to also consider is that lowering committee thresholds does lower the stake percentage required to effectively cause a safety failure (double spend/fork).

So far as it's above 66% there's no fork. for better confidence I said 70% but 75% is also good for now

If anything, we should at least follow through on the recommendation of Derek's and Fabrice's paper you shared.

Just speculating, but my guess is that the down vote committee is already so large a increase in this committee that has a meaningful impact on in the liveness is not worth the tradeoff. 2^-12 is still a fairly low probability and failure here results in slower recovery, not sustained loss of liveness.

I think it first needs to be decided if we want to increase alpha and then decide if/how we want to change committee sizes.

Recovery is to mitigate liveness so we don't want it to fail so if a larger committee guarantees liveness with a higher confidence all the better.

[pao-beep]

Here are some result from running the book by searching for values between 1000 and 9000 , a ~1.5x increase is not too big of a deal to get good security highlighted in bold. This is just soft vote committee but the results won't be too different for cert and next which are the most important. NN = int(1.5e3) negl=0

Probability of safety failure for soft-vote committee:
Searching for E and T with pflog2 < 2^-128 (alpha=0.300000000000000)

E=4400, T=3345 (T/E=0.760) -> pflog2 = 2^-107.910
E=4500, T=3421 (T/E=0.760) -> pflog2 = 2^-123.478
E=4600, T=3451 (T/E=0.750) -> pflog2 = 2^-114.323
E=4600, T=3497 (T/E=0.760) -> pflog2 = 2^-141.705
E=4700, T=3526 (T/E=0.750) -> pflog2 = 2^-132.335
E=4700, T=3573 (T/E=0.760) -> pflog2 = 2^-162.436
E=4800, T=3601 (T/E=0.750) -> pflog2 = 2^-152.725
E=4800, T=3649 (T/E=0.760) -> pflog2 = 2^-185.522
E=4900, T=3676 (T/E=0.750) -> pflog2 = 2^-175.356
E=4900, T=3725 (T/E=0.760) -> pflog2 = 2^-210.827
E=5000, T=3751 (T/E=0.750) -> pflog2 = 2^-200.101
E=5000, T=3801 (T/E=0.760) -> pflog2 = 2^-238.223
E=5100, T=3826 (T/E=0.750) -> pflog2 = 2^-226.840
E=5100, T=3877 (T/E=0.760) -> pflog2 = 2^-267.592
E=5200, T=3901 (T/E=0.750) -> pflog2 = 2^-255.465
E=5200, T=3953 (T/E=0.760) -> pflog2 = 2^-298.826
E=5300, T=3976 (T/E=0.750) -> pflog2 = 2^-285.873
E=5300, T=4029 (T/E=0.760) -> pflog2 = 2^-331.824
E=5400, T=4051 (T/E=0.750) -> pflog2 = 2^-317.971
E=5400, T=4105 (T/E=0.760) -> pflog2 = 2^-366.494
E=5500, T=4126 (T/E=0.750) -> pflog2 = 2^-351.672
E=5500, T=4181 (T/E=0.760) -> pflog2 = 2^-402.751
E=5600, T=4201 (T/E=0.750) -> pflog2 = 2^-386.895
E=5600, T=4257 (T/E=0.760) -> pflog2 = 2^-440.514
E=5700, T=4276 (T/E=0.750) -> pflog2 = 2^-423.565
E=5700, T=4333 (T/E=0.760) -> pflog2 = 2^-479.710
E=5800, T=3867 (T/E=0.667) -> pflog2 = 2^-111.438
E=5800, T=4351 (T/E=0.750) -> pflog2 = 2^-461.613
E=5800, T=4409 (T/E=0.760) -> pflog2 = 2^-520.270
E=5900, T=3934 (T/E=0.667) -> pflog2 = 2^-131.260
E=5900, T=4426 (T/E=0.750) -> pflog2 = 2^-500.975
E=5900, T=4485 (T/E=0.760) -> pflog2 = 2^-562.130
E=6000, T=4001 (T/E=0.667) -> pflog2 = 2^-152.470
E=6000, T=4501 (T/E=0.750) -> pflog2 = 2^-541.589
E=6000, T=4561 (T/E=0.760) -> pflog2 = 2^-605.231
E=6100, T=4067 (T/E=0.667) -> pflog2 = 2^-174.466
E=6100, T=4576 (T/E=0.750) -> pflog2 = 2^-583.399
E=6100, T=4637 (T/E=0.760) -> pflog2 = 2^-649.517
E=6200, T=4134 (T/E=0.667) -> pflog2 = 2^-198.237
E=6200, T=4651 (T/E=0.750) -> pflog2 = 2^-626.354
E=6200, T=4713 (T/E=0.760) -> pflog2 = 2^-694.936
E=6300, T=4201 (T/E=0.667) -> pflog2 = 2^-223.216
E=6300, T=4726 (T/E=0.750) -> pflog2 = 2^-670.402
E=6300, T=4789 (T/E=0.760) -> pflog2 = 2^-741.439
E=6400, T=4267 (T/E=0.667) -> pflog2 = 2^-248.739
E=6400, T=4801 (T/E=0.750) -> pflog2 = 2^-715.499
E=6400, T=4865 (T/E=0.760) -> pflog2 = 2^-788.982
E=6500, T=4334 (T/E=0.667) -> pflog2 = 2^-275.958
E=6500, T=4876 (T/E=0.750) -> pflog2 = 2^-761.600
E=6500, T=4941 (T/E=0.760) -> pflog2 = 2^-837.520
E=6600, T=4401 (T/E=0.667) -> pflog2 = 2^-304.239
E=6600, T=4951 (T/E=0.750) -> pflog2 = 2^-808.665
E=6600, T=5017 (T/E=0.760) -> pflog2 = 2^-887.013
E=6700, T=4467 (T/E=0.667) -> pflog2 = 2^-332.856
E=6700, T=5026 (T/E=0.750) -> pflog2 = 2^-856.656
E=6700, T=5093 (T/E=0.760) -> pflog2 = 2^-937.424
E=6800, T=4534 (T/E=0.667) -> pflog2 = 2^-363.110
E=6800, T=5101 (T/E=0.750) -> pflog2 = 2^-905.535
E=6800, T=5169 (T/E=0.760) -> pflog2 = 2^-988.717
E=6900, T=4601 (T/E=0.667) -> pflog2 = 2^-394.303
E=6900, T=5176 (T/E=0.750) -> pflog2 = 2^-955.270
E=6900, T=5245 (T/E=0.760) -> pflog2 = 2^-1040.858
E=7000, T=4667 (T/E=0.667) -> pflog2 = 2^-425.655
E=7000, T=5251 (T/E=0.750) -> pflog2 = 2^-1005.828
E=7000, T=5321 (T/E=0.760) -> pflog2 = 2^ nan
E=7100, T=4734 (T/E=0.667) -> pflog2 = 2^-458.598
E=7100, T=5326 (T/E=0.750) -> pflog2 = 2^-1057.178
E=7100, T=5397 (T/E=0.760) -> pflog2 = 2^ nan
E=7200, T=4801 (T/E=0.667) -> pflog2 = 2^-492.378
E=7200, T=5401 (T/E=0.750) -> pflog2 = 2^ nan
E=7200, T=5473 (T/E=0.760) -> pflog2 = 2^ nan
E=7300, T=4867 (T/E=0.667) -> pflog2 = 2^-526.163
E=7300, T=5476 (T/E=0.750) -> pflog2 = 2^ nan
E=7300, T=5549 (T/E=0.760) -> pflog2 = 2^ nan
E=7400, T=4934 (T/E=0.667) -> pflog2 = 2^-561.505
E=7400, T=5551 (T/E=0.750) -> pflog2 = 2^ nan
E=7400, T=5625 (T/E=0.760) -> pflog2 = 2^ nan
E=7500, T=5001 (T/E=0.667) -> pflog2 = 2^-597.596
E=7500, T=5626 (T/E=0.750) -> pflog2 = 2^ nan
E=7500, T=5701 (T/E=0.760) -> pflog2 = 2^ nan
E=7600, T=5067 (T/E=0.667) -> pflog2 = 2^-633.560
E=7600, T=5701 (T/E=0.750) -> pflog2 = 2^ nan
E=7600, T=5777 (T/E=0.760) -> pflog2 = 2^ nan
E=7700, T=5134 (T/E=0.667) -> pflog2 = 2^-671.054
E=7700, T=5776 (T/E=0.750) -> pflog2 = 2^ nan
E=7700, T=5853 (T/E=0.760) -> pflog2 = 2^ nan
E=7800, T=5201 (T/E=0.667) -> pflog2 = 2^-709.222
E=7800, T=5851 (T/E=0.750) -> pflog2 = 2^ nan
E=7800, T=5929 (T/E=0.760) -> pflog2 = 2^ nan
E=7900, T=5267 (T/E=0.667) -> pflog2 = 2^-747.147
E=7900, T=5926 (T/E=0.750) -> pflog2 = 2^ nan
E=7900, T=6005 (T/E=0.760) -> pflog2 = 2^ nan
E=8000, T=5334 (T/E=0.667) -> pflog2 = 2^-786.583
E=8000, T=6001 (T/E=0.750) -> pflog2 = 2^ nan
E=8000, T=6081 (T/E=0.760) -> pflog2 = 2^ nan
E=8100, T=5401 (T/E=0.667) -> pflog2 = 2^-826.628
E=8100, T=6076 (T/E=0.750) -> pflog2 = 2^ nan
E=8100, T=6157 (T/E=0.760) -> pflog2 = 2^ nan
E=8200, T=5467 (T/E=0.667) -> pflog2 = 2^-866.328
E=8200, T=6151 (T/E=0.750) -> pflog2 = 2^ nan
E=8200, T=6233 (T/E=0.760) -> pflog2 = 2^ nan
E=8300, T=5534 (T/E=0.667) -> pflog2 = 2^-907.522
E=8300, T=6226 (T/E=0.750) -> pflog2 = 2^ nan
E=8300, T=6309 (T/E=0.760) -> pflog2 = 2^ nan
E=8400, T=5601 (T/E=0.667) -> pflog2 = 2^-949.271
E=8400, T=6301 (T/E=0.750) -> pflog2 = 2^ nan
E=8400, T=6385 (T/E=0.760) -> pflog2 = 2^ nan
E=8500, T=5667 (T/E=0.667) -> pflog2 = 2^-990.584
E=8500, T=6376 (T/E=0.750) -> pflog2 = 2^ nan
E=8500, T=6461 (T/E=0.760) -> pflog2 = 2^ nan
E=8600, T=5734 (T/E=0.667) -> pflog2 = 2^-1033.380
E=8600, T=6451 (T/E=0.750) -> pflog2 = 2^ nan
E=8600, T=6537 (T/E=0.760) -> pflog2 = 2^ nan
E=8700, T=5801 (T/E=0.667) -> pflog2 = 2^ nan
E=8700, T=6526 (T/E=0.750) -> pflog2 = 2^ nan
E=8700, T=6613 (T/E=0.760) -> pflog2 = 2^ nan
E=8800, T=5867 (T/E=0.667) -> pflog2 = 2^ nan
E=8800, T=6601 (T/E=0.750) -> pflog2 = 2^ nan
E=8800, T=6689 (T/E=0.760) -> pflog2 = 2^ nan
E=8900, T=5934 (T/E=0.667) -> pflog2 = 2^ nan
E=8900, T=6676 (T/E=0.750) -> pflog2 = 2^ nan
E=8900, T=6765 (T/E=0.760) -> pflog2 = 2^ nan
E=9000, T=6001 (T/E=0.667) -> pflog2 = 2^ nan
E=9000, T=6751 (T/E=0.750) -> pflog2 = 2^ nan
E=9000, T=6841 (T/E=0.760) -> pflog2 = 2^ nan

[joe-p]

You are forgetting about liveness. T/E cannot be below 1 - alpha. If it is below 1 - alpha, the adversary stake can halt the network indefinitely because the honest stake doesn't have enough stake to meet the thresholds. If you use those numbers in the notebook you'll see B1 and B2 occur with 100% probability.

Edit: Meant the other way around, 1-alpha cannot be below T/E

[pao-beep]

T/E can be below 1 - alpha. In fact it is today on mainnet with T/E= .~75 which is below 1 - alpha at .8. I didn't try liveness because you need to be above ~.75 threshold to get it and so once .75 is achieved you have it. it's certainly not the 32x or 16x you gave. did you even try it. even when I used the real values of "negl" with 256 bit security the committee size is ~2.5 in favor of my intuition of 3x.

[joe-p]

Sorry, brain is still a bit fried from a fever... it's the other way around. 1 - alpha cannot be less than T/E. In other words, there must be enough honest stake to meet the thresholds. When alpha = .3, 70% of the stake is honest. If only 70% of the stake is honest, they cannot reach the quorum if the threshold is 76.5%. If they can't reach the quorum, the network halts indefinitely. This is shown by B1/B2 in the notebook.

I didn't try liveness because you need to be above ~.75 threshold to get it and so once .75 is achieved you have it. it's certainly not the 32x or 16x you gave. did you even try it. even when I used the real values of "negl" with 256 bit security the committee size is ~2.5 in favor of my intuition of 3x.

I think there's a fundamental misunderstanding of what these numbers mean. You can't say you are testing for alpha = 0.3 and then say "once .75 is achieved you have it." alpha = .3 means you DO NOT have .75, you only have .70. This is why it's a 100% liveness failure.

If you want to get the committee sizes to tolerate 30% adversary stake, you must set alpha = .3 and ensure you meet both safety AND liveness. Your output above shows safety, but nothing about liveness.

I didn't try liveness

did you even try it

Yes, I created a notebook with alpha = .3. You can see it here: https://github.com/joe-p/analyzing-algorand/blob/alpha_.3/proba.ipynb

I recommend you use the notebook to verify both safety and liveness.