> For the complete documentation index, see [llms.txt](https://cvnnt.gitbook.io/documentation/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cvnnt.gitbook.io/documentation/algorithms-and-cryptography/eaac.md). # EAAC {% hint style="info" %} Note: This chapter is currently under development. {% endhint %} **EAAC (Expensive to Attack in the Absence of Collapse)** **system** is a distributed system where every attack on the system is expensive for the attacker in the absence of collapse of the system itself. EAAC property of the distributed system offers punishment for the attack in such a way, that while the attacker themselves are harmed for the proven violations, punishment avoids collateral damage to the system' honest participants. A distributed system that guarantees the EAAC property is considered “more economically secure” than one that does not. ### Formal definition of the quasi-permissionless setting Let $$\mathcal{P}$$ is a potentially infinite set of players where each player $$p\in\mathcal{P}$$ is allocated a non-empty and potentially infinite set of identifiers $$id(p)$$, time is divided into discrete timeslots $$t=1,2,\dots$$ ,each player $$p\in\mathcal{P}$$ may or may not be active at each timeslot, a player allocation is a function specifying $$id(p)$$ for each $$p\in\mathcal{P}$$ and the timeslots at which each player $$p\in\mathcal{P}$$ is active. Consider the distributed system$$(\Sigma,\mathcal{O},\mathcal{C},\mathcal{S})$$, where $$\Sigma$$ is the state machine diagram determining honest players, $$\mathcal{O}= {𝑂\_1,\dots,𝑂\_𝑧}$$ is a (possibly empty) set of oracles which are utilized to capture idealized cryptographic primitives, $$\mathcal{C}$$ is a confirmation rule, a function that takes as input an arbitrary set of messages $$M$$ and returns a sequence $$\mathrm{T}$$ of the transactions among those messages, $$\mathcal{S}= {\mathrm{S}\_1,\dots,\mathrm{S}\_𝑗}$$ is a set of stake allocation functions where $$\mathrm{S}(\mathrm{S}^*,\mathrm{T}, id)(\in \mathbb{N})$$ is the stake owned by identifier $$id$$ in a sequence of transactions $$\mathrm{T}$$. $$\mathrm{S}(\mathrm{S}^*,\mathrm{T})$$ denotes the function which on input $$id$$ gives output $$\mathrm{S}(\mathrm{S}^*,\mathrm{T}, id)(\in \mathbb{N})$$. If $$\mathrm{T}$$ is a sequence of transactions, then $$\mathrm{T}*\mathtt{tr}$$ denotes the sequence $$\mathrm{T}$$ concatenated with $$\mathtt{tr}$$. **The quasi-permissionless setting** insists on activity from every honest player that possesses any amount of any form of stake listed in the distributed system description. In other words, an execution of the system is consistent with the quasi-permissionless setting if, for each stake allocation function $$\mathrm{S}\in\mathcal{S}$$: Whenever player $$p\in\mathcal{P}$$ is honest and active at $$t$$, with the set of transactions $$\mathrm{T}$$ confirmed for $$p$$ at $$t$$ in this execution, every honest player that is assigned a non-zero amount of stake by $$\mathrm{S}(\mathrm{S}^\*,\mathrm{T})$$ is active at $$t$$. ### Resources and adversary restriction Distributed system validation requires resources, which can either be external or on-chain. External resources are the hardware, while on-chain resources are those such as validation stake that are statefully recorded on-chain and can be taken as part of punishment for proven misbehaviour. Permitter oracles (permitters) are required for modeling external resources, but not for on-chain resources. A distributed system may use a finite set of permitters amongst the oracles in $$\mathcal{O}$$. For each execution, and for each permitter oracle $$O$$ there is a corresponding resource allocation, denoted $$R^O$$ that befits an “external” resource thus is undetermined. Each player $$p\in\mathcal{P}$$ at each timeslot $$t$$ is assigned with some amount of the external resource $$R^O(p,t)\in\mathbb{N}$$ that is $$p$$'s balance at $$t$$. Because balances are unknown to the system, an inactive player might as well have a zero balance $$R^O(p,t)=0$$ whenever $$p$$ is not active at $$t$$. For each $$t$$ $$R^O(t):=\sum\_pR^O(p,t)$$. An arbitrary value $$R\_{max}^O$$ is given as a system input (determined value), and the system must function for any given value of $$R\_{max}^O\geq 1$$. Let $$B$$ denote the set of Byzantine players and define $$R\_B^O(t):=\sum\_{p\in B}R^O(p,t)$$. For $$\rho\in\[0,1]$$ $$R^O$$ is $$\rho$$-bounded if the following conditions are satisfied for all $$t$$: * $$R^O(t)\in\[1, R\_{max}^O]$$ * $$R\_B^O(t)/R^O(t)\leq \rho$$ The smaller the value of $$\rho$$, the more severe the restriction on the combined “power” of the Byzantine players. If all resource allocations corresponding to permitters in $$\mathcal{O}$$ are $$\rho$$-bounded, then the adversary is externally $$\rho$$-bounded. ### 𝜌-bounded adversary definition A system execution is $$\rho$$-bounded if: * The adversary is externally $$\rho$$-bounded; * For every honest player $$p\in\mathcal{P}$$ at timeslot $$t$$, if the set of transactions $$\mathrm{T}$$ that are confirmed for $$p$$ at $$t$$ in this execution, then at most a $$\rho$$ fraction of the stake allocated to players active at $$t$$ by $$\mathrm{S}(\mathrm{S}^\*,\mathrm{T})$$ is allocated to Byzantine players. In other words, for each stake allocation function $$S\in\mathcal{S}$$, and among active players, Byzantine players never control more than a $$\rho$$ fraction of the stake. Consider the adversary is 𝜌-bounded in terms of attention restriction to $$\rho$$-bounded executions. A distributed system is $$\rho$$-resilient when it is live and consistent under the assumption that the adversary is $$\rho$$-bounded. A distributed system is $$\rho$$-resilient for liveness when it is live under the assumption that the adversary is $$\rho$$-bounded. A distributed system is $$\rho$$-resilient for consistency when it is consistent under the assumption that the adversary is $$\rho$$-bounded. ### Canonical PoS investment function For an on-chain resource $$i$$ that corresponds to some form of stake, investment function$$R\_i(p,t)$$ may depend on the current state of the distributed system that controls the resource, meaning the sets of messages that have been received by each player $$p\in\mathcal{P}$$ by timeslot $$t$$. $$R\_i(p,t)$$ should update once a resource-changing transaction has been “sufficiently processed” by the system. Given a single resource, representing the amount of stake that a player $$p\in \mathcal{P}$$ has locked up in escrow, and the resource balance of a player $$p$$ that changes only through staking and unstaking transactions, a canonical investment function $$R(p,t)$$ increases by $$x$$ after a valid staking transaction (with staking amount $$x$$) is first confirmed by some honest player ( or, more globally, “sufficiently processed” by the system, possibly after a delay), and decreases by $$x$$ after a valid unstaking transaction is first confirmed by some honest player (again, more globally, “sufficiently processed” by the system, possibly after a delay). Such a function is $$\Gamma$$-liquid, where $$\Gamma$$ is the maximum delay before the investment function reflects a newly confirmed staking or unstaking transaction. ### Valuation function A valuation function in general is a nonnegative function $$v$$ of a set $$P$$ of players, a timeslot $$t$$, player investments at that time $$R\_i(p,t)$$, market prices at that time $$C\_i(t)$$, and the sets of messages that have been received by each player by that time. Canonical PoS valuation function is also consistency-respecting (it is defined only for timeslots $$t$$ at which consistency holds (i.e., if $$\mathrm{T}$$ and $$\mathrm{T}'$$ are the confirmed transactions for honest $$p$$ and $$p'$$ at $$t$$ , then one of $$\mathrm{T}, \mathrm{T}'$$ is a prefix of the other), and, at timeslots at which consistency does hold, the valuation function equals the value of the as-yet-unslashed stake-in-escrow of the players in question (at the current market prices). ### EAAC property formal definition Assuming that a consistency violation does not affect the market prices of the relevant resources, consider a fixed price $$C\_i$$ for each resource (instead of an arbitrary price sequence $${C\_i(t)}\_{t\geq 1}$$). A protocol is EAAC with respect to investment functions $$\mathrm{R}*i(\cdot,\cdot)*{i\in\[k]}$$ and valuation function $$v$$ in a given setting if, for every choice $${C\_i}\_{i\in\[k]}$$ of fixed resource prices, every external resource $$i$$, and every choice $${\mathrm{R}*i(p,t)}*{p\in P, t\geq1}$$of players’ investments in $$i$$: \- for every execution of the protocol consistent with the setting and every timeslot $$t\geq 1$$, $$v(H,t,{\mathrm{R}*i(p,t)}*{p\in H, i\in\[k]}, {C\_i}*{i\in\[k]}, \mathcal{M})\geq \displaystyle\sum*{p\in H}\sum\_{i=1}^k\mathrm{R}\_i(p,t)\cdot C\_i$$ , where $$H$$ denotes the set of honest players and $$\mathcal{M}$$ is the sets of messages received by each player by timeslot $$t$$ in the execution. This property means requires honest players can always recoup resourses they may have invested (e.g., they are never slashed in a proof-of-stake protocol). \- and for every execution of the protocol consistent with the setting with a consistency violation that is first seen by honest players at a timeslot $$t^*$$ , there exists a timeslot $$t\_f\geq t^*$$ such that: $$v(B,t\_f,{\mathrm{R}*i(p,t\_f)}*{p\in B, i\in\[k]}, {C\_i}*{i\in\[k]}, \mathcal{M})< \displaystyle\sum*{p\in B}\sum\_{i=1}^k\mathrm{R}\_i(p,t\_f)\cdot C\_i$$ , where $$B$$ denotes the set of Byzantine players and $$\mathcal{M}$$ is the sets of messages received by each player by timeslot $$t$$ in the execution. This property requires an attacker is unable to fully cash out, with some of their investment lost to the protocol. Let $$v(H,t,{\mathrm{R}*i(p,t)}*{p\in H, i\in\[k]}, {C\_i}\_{i\in\[k]}, \mathcal{M})=\alpha\_H$$, $$v(B,t\_f,{\mathrm{R}*i(p,t\_f)}*{p\in B, i\in\[k]}, {C\_i}\_{i\in\[k]}, \mathcal{M})=\alpha\_B$$ , the EAAC condition states that $$\alpha\_H\geq 1$$ should always hold (i.e., if attacks are expensive, it’s for the right reasons, not due to collapse) and that $$\alpha\_B <1$$ should hold at some point after a consistency violation (i.e., attacks are indeed expensive). If the property $$\alpha\_B< \displaystyle\sum\_{p\in B}\sum\_{i=1}^k\mathrm{R}\_i(p,t\_f)\cdot C\_i$$ is always satisfied with some $$\alpha\_B\leq\alpha <1$$, then the system is $$\alpha$$-EAAC (with respect to $$\mathrm{R}*i(\cdot,\cdot)*{i\in\[k]}$$ and $$v$$). ### Provable slashing guarantees While protocols are commonly expected to be live and consistent in the partial synchrony model with a liveness parameter $$T\_l$$ determined by some small value of $$\Delta$$ (e.g. of the order of 1 second), it may also be reasonable to assume that messages will always eventually be delivered, either via the communication network or some “out-of-band” mechanism, within some sufficiently large time bound (of the order of a day or a week). Consider the distributed system that is live and consistent in partial synchrony (for some small $$\Delta$$) so long as the adversary is $$\rho$$-bounded for $$\rho < \frac{1}{3}$$, and which, furthermore, implement slashing when the adversary owns more than $$\frac{1}{3}$$ of the resources but message delivery prior to GST always occurs within some large known time bound $$\Delta^\*$$(which may not be $$O(\Delta)$$). The distributed system is $$(\rho,\rho^*)$$-EAAC with respect to investment functions $$\mathrm{R}*i(\cdot,\cdot)*{i\in\[k]}$$ and valuation function $$v$$ if it satisfies the following two conditions, given any determined values of $$\Delta$$ and $$\Delta^*\geq\Delta$$ , and where$$\rho^\*$$ is determined: 1. The distributed system is live and consistent for the partial synchrony model with respect to $$\Delta$$, so long as the adversary is $$\rho$$-bounded. Thus the liveness parameter $$T\_l$$ may depend on $$\Delta$$ and other determined inputs, but is independent of $$\Delta^*$$. In particular, $$\Delta^*$$ may be much larger than $$T\_l$$ . 2. The distributed system is EAAC (with respect to $$\mathrm{R}*i(\cdot,\cdot)*{i\in\[k]}$$ and $$v$$ ) so long as the adversary is $$\rho^*$$- bounded and message delays prior to GST are always at most $$\Delta^*$$(i.e., if $$p$$ disseminates $$m$$ at $$t$$, and if $$p' \neq p$$ is active at $$t'\geq t+\Delta^\*$$, then $$p'$$ receives that dissemination at a timeslot $$t\_r\leq t'$$ ). If under the 2-nd condition the distributed system is $$\alpha$$-EAAC, then the distributed system is $$(\alpha, \rho, \rho^\*)$$-EAAC (with respect to $$\mathrm{R}*i(\cdot,\cdot)*{i\in\[k]}$$ and $$v$$ ) . ### Non-trivial EAAC distributed system in the quasi-permissionless setting For every $$\rho<\frac{1}{3}$$ and $$\rho^*<\frac{2}{3}$$ , there exists a PoS distributed system for the quasi-permissionless setting that is $$(\alpha,\rho,\rho^*)$$-EAAC with respect to a canonical PoS investment function and a canonical PoS valuation function, where $$\alpha=\max{0, \frac{\rho^*-1/3}{\rho^*}}$$.