Prime Field Notes

In 2016, this paper https://eprint.iacr.org/2016/1102 led to a lower security estimate for the BN254 curve. Specifically, its security is now considered to be around 96-bits. https://eprint.iacr.org/2017/334.pdf Many applications recommend switching to BLS curves instead of BN254 for security reasons. We need to take this into consideration when considering a prime field to work on. The reason why BN254 is still used is because of the dependence on Ethereum, but this is not the case for us.

Privacy Preserving Signatures

Introduction

This document analyses the capabilities of an adversary who controls a fraction of DA nodes and attempts to manipulate the data availability perception of validators. Unlike a simple denial-of-service adversary who tries to make data globally unavailable, this adversary exploits the statistical nature of the sampling protocol in two complementary directions.

Attack A — Available → Unavailable (Type II exploitation). The data is genuinely available, but the adversary causes targeted validators to conclude it is unavailable. This exploits Type II error. The adversary benefits by causing honest leaders to waste slots, disrupting liveness, or by creating asymmetric chain views across validators.

Attack B — Unavailable → Available (Type I exploitation). The data is genuinely unavailable or has been withheld by the adversary after dispersal, but the adversary causes targeted validators to conclude it is available. This exploits Type I error. The adversary benefits by inserting unrecoverable data into the chain.

Both attacks are governed by the same underlying combinatorial structure: how many subnetworks the adversary can influence, and how the sampling decision rule responds to that influence. The analysis below derives general formulas in terms of all protocol parameters without fixing any specific numerical values.

Assumption: No-False-Proof Adversary

Throughout this document the adversary is assumed to never send false proofs. Adversarial nodes always respond with cryptographically valid proofs when they hold the data, and stay silent when they do not. The attack strategy — respond or stay silent — is chosen by the adversary depending on the target validator and the attack goal.

The two attacks are special cases of a unified model governed by two independent probabilities:

$p_\text{dis}$ (adversarial dissemination probability) — the probability that a given adversarial node holds a chunk for the targeted blob. This is determined entirely by the encoder's dispersal strategy, independent of sampling. Note that subnetwork assignment is random and cannot be controlled by the adversary — only the decision of which subnetworks to send chunks to is adversarial.
$p_\text{samp}(a, R, t)$ (adversarial sampling probability) — the probability that the validator's $t$ queries within a subnetwork hit at least one adversarial node. This is determined entirely by the sampling mechanism (occupancy $a$, subnetwork size $R$, query count $t$), independent of dispersal.

The probability that a subnetwork produces the adversarially desired outcome is:

$$ P_\text{subnet}(a, R, t, p_\text{dis}) = p_\text{samp}(a, R, t) \times p_\text{dis} $$

The two attacks are special cases of this general form: