Accounting for "optimistic" provers who have more than n_f, but less than n_p elements

[amesgen]

Citing from the introductory text of the ALBA paper:

More formally, let $R$ be a predicate. We explore succinct arguments of knowledge for a prover who knows a set $S_p$ of values that satisfy $R$ such that $|Sp| \ge n_p$ and wants to convince a verifier that $|S_p| > n_f$, where $n_f$ is somewhat smaller than $n_p$. Because $n_f < n_p$, the verifier obtains a lower bound approximation to the actual cardinality of $S_p$; hence we call this primitive an Approximate Lower Bound Argument or ALBA.

[...]

Let $\lambda$ be the parameter that controls soundness and completeness: the honest prover (who possesses a set of weight $n_p$) will fail with probability $2^{−\lambda}$ and the dishonest prover (who possesses a set of weight at most $n_f$) will succeed with, say, also probability $2^{-\lambda}$.

My understanding of this is that provers who have more than $n_f$, but less than $n_p$ elements satisfying $R$ (so $n_f < |S_p| < n_p$) are out-of-scope for the soundness and completeness properties. In particlar, under the confidence guaranteed by the security parameter, upon successfully verifying a proof, the verifier only learns that the prover has more than $n_f$ elements; but not something stronger, for example whether the prover actually had (close to) $n_p$ elements.

Therefore, it is natural to ask how easy it is for an "optimistic" prover, who only has $|S_p|$ elements with $n_f < |S_p| < n_p$, to still create a valid proof. The goal of this thread is to understand how such (adversarial) optimistic provers impact the ALBA parameterization choices for potential applications.

---

The most general strategy for such an optimistic prover is to simply try all possible proofs in order to find one that is valid. Lemma 3 (slightly modified) can be used to analyze this: In the scheme from Section 3.2.2 ("Generalization to small $n_p$"), there are $r \cdot d \cdot {|S_p|}^u$ possible proofs, and each one is valid with probability ${(1/n_p)}^u \cdot q$, so by the union bound, we get

$$ r \cdot {\left( \frac{|S_p|}{n_p} \right)}^u\cdot qd $$

as an upper bound on the probability that such a prover can create a valid proof.

---

As a concrete example, consider the parameters $n_p = 0.8 \cdot n = 720$ and $n_f = 0.2 \cdot n = 180$ where $n = 900$ as well as $\lambda = 128$. Based on Corollary 3, this yields $u = 70$, $d = 5567$, $q \approx 0.000893$ and $r = 128$.

Generally, the success probability increases exponentially the larger $S_p$ gets. We can see that the upper bounds on the success probability of the prover are non-negligible for values noticeably smaller than $n_p$, for example 1.8% for $|S_p| = 620$ or 0.005% for $|S_p| = 570$. For $|S_p| = 400$, we get a bound of 8.6e-16, which is quite low, but still orders of magnitude larger than the configured security parameter of $2^{-128}$ (rougly 3e-39).

If we imagine the context to be a voting scheme with $n = 900$ votes and a share of adversarial voters, where a valid ALBA proof signals that some quorum has been met, this has the following implications for example:

• In addition to the possibility of the adversary getting $n_p$ votes, there also is the possibility of getting less than $n_p$ and then getting lucky so to produce a valid ALBA proof.
  • In particular, this becomes relevant when there is a possibility that the honest votes are split across e.g. two options, and the adversary can then vote for one or even both of them, in order to get closer to $n_p$ votes than they could with their votes alone.
• Suppose that honest participants only attempt to create an ALBA proof when they have at least some minimum number of votes. Suppose that an adversary is eligible for sufficiently many votes such that the honest participants do not reach this threshold. Then the adversary might still be able to create a valid ALBA proof, causing confusion at the very least.

The "easy" option to address problems like this (avoiding any complicated analysis) would be to make $n_f$ so large that just by the soundness of ALBA, one does not have to worry about optimistic provers. However, this might result in the ratio $n_p / n_f$ to be so small that ALBA becomes less or even unappealing for the particular application.

---

matplotlib script for the graph above

#!/usr/bin/env nix-shell
#! nix-shell -i python3 --pure
#! nix-shell -p "python3.withPackages (ps: [ ps.matplotlib ps.scipy ])"
#! nix-shell -I nixpkgs=https://github.com/NixOS/nixpkgs/archive/5e0ca22929f3342b19569b21b2f3462f053e497b.tar.gz

from math import *
import matplotlib.pyplot as plt
import numpy as np

lam = 128  # security parameter
n = 900
n_p = int(0.8 * n)
n_f = int(0.2 * n)

print(f"n_p = {n_p}, n_f = {n_f}, λ = {lam}")

assert n_f < n_p

# From Corollary 3:
u = ceil((lam + log2(lam) + 5 - log2(log2(e))) / log2(n_p / n_f))

# Make sure we are in Case 1 in the proof of Corollary 3.
S_1_bot = n_p / (17**2 / (9 * log2(e)) * u**2) - 7 < 1
S_2_bot = n_p / (17**2 / (9 * log2(e)) * u**2) - 2 < 1
assert S_1_bot or S_2_bot

# With the parameters above, we are in Case 1 in the proof of Corollary 3 (or
# the "≤ λ²" column in Figure 1).
d = ceil(32 * log(12) * u)
q = 2 * log(12) / d
r = ceil(lam)

print(f"u = {u}, d = {d}, q = {q}, r = {r}")

optimistic_prover_success_bound = lambda v: r * (v / n_p) ** u * d * q


fig, ax = plt.subplots(figsize=(9, 6))
X = np.arange(n_f - 10, n_p + 1)
ax.set_title(f"Optimistic ALBA proving for n_p = {n_p}, n_f = {n_f}, λ = {lam}")
ax.set_xlabel("number of elements |S_p| the prover has access to")
ax.grid(True)

ax.set_yscale("log", base=10)
ax.plot(X, np.vectorize(optimistic_prover_success_bound)(X))
ax.set_ylabel("probability (upper bound) to create a valid proof")
ax.tick_params(axis="y")

secax = ax.secondary_yaxis(location="right")
secax.set_yscale("log", base=2)

ax.axvline(x=n_p, linestyle="--", color="red", label="n_p")
ax.axvline(x=n_f, linestyle="--", color="green", label="n_f")
ax.legend()
ax.set_ylim(top=1)

fig.savefig("optimistic-proving.png", dpi=300)

[ghost]

@amesgen I think your analysis is correct, and I wrongly conflated 3 things when I analysed the use of ALBA in the context of Peras: 1/ the expected quorum of 75% of committee size to issue a certificate, 2/ the meaning of $n_p$ and $n_f$ parameters, and 3/ the relationship they have to each other.

There is no reason to set $n_f = S_p - n_p$, where $S_p$ is the expected total set of items, as I initially thought, e.g these are not the same as the expected adversarial stake assumption we usually take into account when analysing the safety of our stuff, and therefore there's no reason to use n_p = 0.8 * stake and n_f = 0.2 * stake.

However, there's also no reason to assume that an adversary can have more items than their expected stake, e.g if we assume the adversary cannot control more than 1/3rd of the stake, then we by setting n_f = 0.33 * stake we should be "safe" because then ALBA guarantees that an adversary "cannot" make a certificate. If we set n_p = 0.75 * stake, our proof will be larger (eg. 60kB assuming each vote is roughly 500 bytes) but still manageable.

Should we want to increase adversarial stake then of course proof size would increase significantly, but then we could also increase $n_p$: with $n_p = 90$ and $n_f = 40$, proof size is still at about 60kB. Obviously, the close we get to 50% the more cumbersome it becomes.

[ghost]

FWIW, I checked what the certificate size would be with $n_p = 900$ and $n_f = 490$ for an average committee size of 1000, and a single vote of 500 bytes, and I got the following results:

% cabal run alba -- prove --n-p 900 --n-f 490 --size 900 --len 500 --security 128
Generating random items
Generating proof Options {size = 900, len = 500, params = Params {λ_sec = 128, λ_rel = 128, n_p = 900, n_f = 490}, input = Nothing, output = "proof.alba"}
Written proof to 'proof.alba' (81298 bytes, 18 retries)

Not great, but still in the range of a block size and there's work underway on ALBA certificates, possibly combined with ZK techniques, to reduce that size. And of course the votes themselves could potentially be improved.

Moreover, in the case of Peras the scenario you outlined @amesgen is extremely unlikely:

1. the cutoff parameter $L$ for selecting block to vote for is meant to ensure that honest votes will have a high probability of having converged on the same chain,
2. the final version of Peras which is still being worked on by the researchers will include a pre-agreement BFT functionality in order to guarantee exactly that.

It seems to me that not all hope is lost and we could adjust the $n_p$ and $n_f$ to be "nicer" and produce smaller proofs.

I will adjust Peras' report according to your comment, and I also created #18 to incorporate the information and model you provided @amesgen into Peras' website.

[amesgen]

Thanks for the replies!

It seems to me that not all hope is lost and we could adjust the $n_p$ and $n_f$ to be "nicer" and produce smaller proofs.

Yes, though it will definitely require careful analysis to be sure that situations that would enable optimistic provers to succeed can only arise with sufficiently low probability 👍

I will adjust Peras' report according to your comment, and I also created #18 to incorporate the information and model you provided @amesgen into Peras' website.

Sounds great, also happy to help/review 👍

[ghost]

be sure that situations that would enable optimistic provers to succeed can only arise with sufficiently low probability

I would like also to emphasise that while the papers produce theoretical arguments based on <50% adversarial stake, the numbers used in practice seem to actually target a lower amount of stake. For example, following the computations from this paper about settlement time, the 2160 blocks security parameter represents the number of blocks it takes to have less than $2^{-60}$ probability that an adversary controlling less than 35% stake with $10^{18}$ grinding power will be able to revert a transaction.

It seems we don't have a consistent practical definition of what Secure really means, and what adversarial stake we really take into account, in practice.

What could be valuable would be to frame analysis of the ALBA protocol not in terms of probabilities to find a proof, but in terms of computing power to find one with certainty. This would make it possible to recast the security argument of ALBA in the same terms as the one for underlying Praos chain for example, and unify the various probabilities and exponents under a shared terminology.

happy to help/review

That would be great, will tag you once I have the PR ready.

[amesgen]

Yeah, at least as soon as significant nonce grinding comes into the picture, ones needs to consider less adversarial stake to still get a secure system 👍 I agree that it is unsatisfying that there don't seem to be concrete worst case values for adversarial stake/grinding power that one can use; the approach that we have taken so far is to calculate it for a range of adversaries, and if the resulting probabilities are not obviously way too high/low, ask other people (researchers/product people) to make the call on that.

I guess my point was that there is a tradeoff between picking "nice" $n_p$/$n_f$ (that e.g. result in small proofs/certificates) and having to do a more complicated analysis that this is actually secure when assuming certain adversarial resources (stake/grinding power/computational power).

[ghost]

Agreed, and again thanks for the great questions and pointing out that mistake of mine!

[ghost]

Using your formula for probability of finding a proof and some assumptions on hashing power, I found out that with $n_p = 900$, $n_f = 350$, a prover with 490 votes and $10^9$ CPUs would still need $10^7$ seconds to find a proof on average, or 115 days, which might probably be good enough for our use cases (but that would require more careful analysis of the opportunity window for an attacker to produce such an adversarial certificate).

I have put up a PR (#22), it would be great if you could check my computations are sound :)

[tolikzinovyev]

How is the proving time for the adversary so large? Wouldn't the adversary be able to run DFS just like the honest prover? It should be fast if not faster.

[ghost]

You tell me, you invented ALBA :) I just reused @amesgen's computations above, factoring in estimations for hashing power to translate probabilities to time.

[rrtoledo]

I had quite a few discussions on what nf and np with regards to our Peras protocol parameters, more specifically the quorum size which equals 75% of the comittee stake.

Alba is a proof of lower bound (I have seen at least nf elements satisfying a certain relation R). What matters "first" is the choice of nf, then we can consider np value which defines both when we can be sure to produce a proof and the proof size.

An opportunistic prover, who hasn't seen at least np elements, in my mind is not adversarial: he is still computing a proof that he has seen nf elements, but the probability of generating such proof is lower. The real adversary is someone trying to create a certificate with fewer than nf elements. I do not believe we have to worry about race conditions here either, the biggest worry of Peras is to always produce a certificate.

To come back to numbers, we will need to set nf to the quorum size, i.e. 75% of the commitee stake. This is to prevent an attack on Peras, the intersection attack, where the adversary can boost several blocks and in fine create forks. In practice, we may be able to lower this number to 67% if we consider a 35% adversary which as @abailly-iohk mentioned is considered elsewhere.
As for np, we would like to have a np high enough so that the proof size is as low as possible but lowering np should decrease the proving time. What we could for np then is choose the smallest value such that the certificate fits in a block, of course given we can use a whole block.

I have so far dismissed the third main Alba parameter, the security parameter lambda. It is usually set to have 128 bit of security. There might be opportunities to lower it depending on its value in the Peras protocol.

[amesgen]

You are right that decentralized alba is just simple lottery (algorand-like sortition) plus centralized unweighted alba. But what I was trying to say is that the analysis of security and reliability, and therefore parameter derivation, is more complicated. Good news is that it has already been done in the alba paper and my report on slack has nice graphs.

That makes sense, I just wanted to get a feeling for how the parameters turn out in the centralized unweighted setting when setting $n_f = \tau n$ to confirm that the results aren't appealing, and my intuition is that using a variant with weights/decentralization won't make the numbers better. However, when actually constructively choosing ALBA parameters in a setting where $n_f$ can be smaller (e.g. the two-round scheme sketched above), e.g. your report sounds like exactly what should be used.

By the way, I'm also confused why in https://peras.cardano-scaling.org/docs/reports/tech-report-2/#no-honest-quorum-in-round the 3/4 quorum is fixed while the fraction of adversarial stake f is varied. In reality, if f is small, we also need a smaller quorum. We basically need to avoid the situation where honest votes are split equally among two different blocks and the adversary adds his votes to both sets to certify both blocks. So we need the quorum size tau > (1 - f) / 2 + f = (1 + f) / 2. If f is 50% this gives quorum size 75%, but if f is smaller, the quorum can be smaller.

I am not the author, but that's how I understood it: Peras (at least in the "pre-alpha version" of Peras, ie without any pre-agreement) only provides optimistic fast settlement. We assume a worst case adversarial stake ratio of $f=1/2$, so we need to set the quorum $\tau$ to at least $3/4$. Now:

• An adversary who has more than $1/4=1-\tau$ of the stake but less than $f=1/2$ can effectively disable Peras all the time by preventing quorum formation (by simply abstaining), but they can't compromise the security of the underlying protocol as they still have less than $f=1/2$ of the stake.
• An adversary who has less than $1/4=1-\tau$ of the stake can only prevent honest quorum formation with a small probability. The purpose of this section in the Peras report is to quantify how likely this is going to be the case, in order to choose a sufficiently large committee size to make sure that "weak" adversaries (with e.g. 10% stake) can't disable Peras.

[tolikzinovyev]

Thanks for explanation, it makes sense about optimistic fast settlement. So the problem statement is that we want the adversary to successfully certify two different blocks only with tiny probability even if adversarial stake is 50% (or close to 50), but the protocol should provide fast settlement when adversarial stake is actually much lower? But then I'm confused why https://peras.cardano-scaling.org/docs/reports/tech-report-2/#adversarial-quorum assumes f to be smaller than 25%. It doesn't solve the problem of safety against 50% adversarial stake. Also the threshold tau would need to be higher than 3/4 * expected committee size as there is deviation due to lottery randomness.

The decentralized alba can give proof size as small as ≈ (lambda + log(lambda) + 5) / log(n_p / n_f). For lambda = 128, n_p = 100% stake, n_f = 75% stake, this is 337. Of course, the communication complexity would be large in this case. There is a tradeoff between the two.

[amesgen]

So the problem statement is that we want the adversary to successfully certify two different blocks only with tiny probability even if adversarial stake is 50% (or close to 50), but the protocol should provide fast settlement when adversarial stake is actually much lower?

That's my understanding (where "close to 50%" is a bit fuzzy), maybe someone from the Peras team can confirm this.

But then I'm confused why https://peras.cardano-scaling.org/docs/reports/tech-report-2/#adversarial-quorum assumes f to be smaller than 25%. It doesn't solve the problem of safety against 50% adversarial stake.

Yeah, I agree that it would be useful for this plot to include higher adversarial stake ratios.

The decentralized alba can give proof size as small as ≈ (lambda + log(lambda) + 5) / log(n_p / n_f). For lambda = 128, n_p = 100% stake, n_f = 75% stake, this is 337. Of course, the communication complexity would be large in this case. There is a tradeoff between the two.

Hmm, but setting n_p = 100% stake would then probably make "narrow quorums" unprovable/uncertifiable as mentioned above, right? I.e. suppose that there is a quorum for a block by 80% of the stake. What would be the completeness error to create a corresponding ALBA proof?

[tolikzinovyev]

What would be the completeness error to create a corresponding ALBA proof?

It would be pretty close to 0. To get completeness error 1/2 with n_p / n_f = 80/75, you would need to make proof size 1483.

alba-tradeoff/code$ cargo run --release -- --lamsec=128 --lamrel=1 --ratio=1.066667 --scheme=telescope-bounded calc --target-mu=1000000
    Finished `release` profile [optimized] target(s) in 0.03s
     Running `target/release/decentralized-alba-params --lamsec=128 --lamrel=1 --ratio=1.066667 --scheme=telescope-bounded calc --target-mu=1000000`
u: 1483 mu: 980301

I will share my calculation code in https://github.com/tolikzinovyev/alba-tradeoff with you and @abailly-iohk if you want to try different parameters.

[tolikzinovyev]

For simple lottery it's much worse...

alba-tradeoff/code$ cargo run --release -- --lamsec=128 --lamrel=1 --ratio=1.066667 --scheme=simple-lottery calc 
    Finished `release` profile [optimized] target(s) in 0.10s
     Running `target/release/decentralized-alba-params --lamsec=128 --lamrel=1 --ratio=1.066667 --scheme=simple-lottery calc`
u: 51380 mu: 51647.34936883665