A fresh attempt for Classification
Part 3 — The four Dimensions for the taxonomy: 2. Sybil Attack Prevention Mechanisms
This article is the third part of the bigger story about Distributed Decentralized Systems. For the first and second part click the hyperlinks.
Helix-Foundation -All rights reserved
II — 2. Sybil Attack Prevention Mechanisms
The whole idea behind this type of mechanism is to avoid spam or Denial of Service (DoS) attacks. Sybil¹ attack is a malicious attempt preventing finality. One of the key ideas of cryptography is to provide security by means of operations that are (relatively) affordable to honest parties but prohibitively costly to adversaries.
The consensus scientist, Emin G. Sirer, at Cornell University, Ithaca, explains [Sirer]: “… the big design decisions in coins aren’t between PoW vs. PoS. They are between the consensus protocols themselves, as they determine performance, scale, energy expenditure, and security.”
And, he continues:
“Ok, there is a terribly wrong framework emerging around consensus protocols. People think that PoW and PoS are consensus protocols and that they are the only two consensus protocols out there. This is false. Let me explain. Proof-of-Work and Proof-of-Stake are **Sybil control mechanisms**. PoS doesn’t achieve consensus by itself. It has to be coupled with a protocol, such as pBFT, or Ben-Or, or Tendermint/Cosmos, or Avalanche, to make decisions. PoW, by itself, isn’t a consensus mechanism. In BTC/BCH, it works with the heaviest/”longest” chain selection rule to achieve consensus. PoW by itself can be used to thwart spam. PoW doesn’t get your agreement, it gets your rate limiting.”
There are many consensus protocols (mechanisms), and there are many Sybil Control mechanisms. These two kinds of mechanisms are distinct and separate. A system or coin will end up combining one with the other. Of course, not all combinations make sense. But many combos are possible. For example, one could use Avalanche either with PoW or PoS, if necessary. One could use a PoS coin, which had in it a PoW mechanism to make sure that a rogue but staked actor does not flood the network layer.
What about DAGs — when he was asked, Prof. Sirer replied:
“That refers to a third component in system design: the data structure you build via consensus and with the help of your own Sybil deterrence mechanism. One could use PoW + DAG + modified heaviest chain such as GHOST — a conflict-resolution procedure for the blockchain. One could also use PoS + DAG + Avalanche, as in Ava coin. Or do PoS + multisets + Avalanche just as well. Or do PoS + forests or chain + Snowball. All are very similar, only one has a DAG. Certain combos are just more efficient.”
From Proof of Work to Proof of Useful Work …
– Proof of Work (PoW)
At a high level, a Proof of Work² involves three algorithms [Ball, Rosen, Sabin, Vasudevan, 2017]:
· Gen(1^n) is a randomized algorithm that produces a challenge c.
· Solve(c) is an algorithm that solves the challenge c, producing a solution s.
· Verify(c, s) is a (possibly randomized) algorithm that verifies the solution s to c.
While Gen and Verify should run very quickly, there should be a notion of hardness for Solve’s runtime. More specifically, for some pre-specified length of working time, say t(n), Solve should be able to produce solutions that Verify accepts, but any attempted solutions produced by an algorithm running in less time (e.g. t(n)^1−ε for any ε > 0) should be rejected by Verify with high probability. Thus, valid solutions ‘prove’ that t(n) work was completed in creating them. This hardness condition should also typically be extended for so that it is also not possible to amortize work over a large number of challenges.
Stated as is, however, these “solutions” don’t actually solve anything. One of the most commonly used PoWs, such as in Bitcoin, is simply to find a value s so that hashing it together with the given challenge (e.g. with SHA-256) maps to anything with a certain amount of leading 0’s. Not only the hardness of this problem is based on the heuristic belief that SHA-256 seems to behave unpredictably, but such an arbitrarily denned value s is useless [Ball, Roseny, Sabinz, Vasudevan, 2017].
PoW is a mechanism that demands the usage of some finite/scarce/expensive resource to ensure that a request is genuine. A captcha, for instance, is a (human level) PoW consisting of your brain trying to figure out what those hieroglyphs say.
– Proof of useful Work (uPoW; PouC)
Proofs of useful Work — here synonymously used for Proof of Useful Computation, PouC — aim to achieve the following two desiderata simultaneously:
1. Hardness: Challenges can be issued such that responding to them correctly is (conditionally) guaranteed to necessitate actual work.
2. Usefulness: Computational tasks can be delegated as challenges to the workers such that the solution to the delegated task can be quickly and verifiably reconstructed from the workers’ response [Ball et al. 2017].
Usefulness can be viewed through the lens of a verifiable delegation of computation, which allows useful problem instances to be delegated with quickly re-constructible solutions, yet has not been concerned with any notion of average-case hardness. The main challenge facing as a designer of a Proof of useful Work, then, is to marry hardness and usefulness for as large as possible a class of functions f, and with as much control as possible on the hardness parameter.
PoW on its own typically achieves just the hardness property. As it has a way to quickly generate challenges of desired difficulty such that a solver is guaranteed to expend a certain amount of (non-amortizable) work in producing an easily verifiable solution.
Unfortunately, the generated challenges are typically random and detached from any fixed delegable instance x that someone may want to learn some f(x) for. Thus — on top of generating, solving, and verifying challenges — we must further generate challenges dependent on x to define a usefulness property: that solutions to challenges generated according to x can allow for the reconstruction of f(x). The authors [Ball et al. 2017] formalize this and give a definition of Proofs of Useful Work (uPoW). Syntactically, the definition involves four algorithms:
· Gen(x) is a randomized algorithm that takes an instance x and produces a challenge cx.
· Solve(cx) is an algorithm that solves the challenge cx, producing a solution sketch s.
· Verify(cx; s) is a randomized algorithm that verifies the solution sketch s to the challenge cx.
· Recon(cx; s) is an algorithm that given a valid s for cx reconstructs f(x).
– Proof of Stake (PoS)
PoS is another mechanism, preventing Sybil attacks, where external (universal) resources (hardware and electricity like in PoW) are replaced with the external (cryptocurrency) resources, e.g. ETH, BTC, HLX³. The idea is: one has to acquire a certain amount of crypto in order to produce a block. Instead of providing proof of having spent time and energy in mining (“work”), the basic idea of a PoS-based consensus protocol relies on distributing the rights to participate in the validation process on the basis of the amount of money the users have in the blockchain. Therefore, the consumption of energy in a PoS protocol reduces basically to the election of block proposers and transaction verification which is negligible in comparison to a PoW based system, and is per se not prone to mining power concentration — but prone to plutocracy. In PoS, validators create a deposit (a bond) of coins which allows them to propose and vote on new blocks.
– delegated Proof of Stake (dPoS)
The PoS mechanism is affected by the “nothing at stake” issue. As described in [Tasca & Tessone, 2019], “because there is little cost in working on several chains, unlike in PoW, one could abuse the system by voting for multiple blockchain-histories, which would prevent the consensus from ever resolving (double spending). This problem can be addressed by delegated Proof of Stake (dPoS), a generic term describing an evolution of the basic PoS consensus (utilized in, e.g., Casper by Ethereum, and Tendermint) where blocks are forged by predetermined users delegated by the user who has the actual stake. These forgers are rewarded for their duty and are punished for malicious behavior (such as participation in double-spending attacks). This principle of pre-authorized forgers is generalized by the Proof-of-Authority mechanism”.
– Proof of Authority (PoAut)
Here, a set of authorities are empowered to collaborate in a trustless manner. Therefore, some nodes are exclusively allowed to create new blocks and secure the blockchain. Those nodes will receive a set of private keys that will be used to “sign” the new blocks, acting as trusted signers. Thus, every block (or header) that a client sees can be matched against the list of trusted signers. Typically, PoAut mechanisms fit well for consortium private networks where some preselected real entities (i.e., the authorities) are allowed to control the content that is added to the public registry. In this article, we will limit our examples for the description of Sybil mechanisms to just a few. Thus, for a more comprehensive set of explanations such as Proof of Capacity, Proof of Space, Proof of Storage, Proof of Burn, we would like to refer to [Tasca & Tessone 2019].
– Proof of SpaceTime (PoST)
PoST is a mechanism that is closely related to Proof of Capacity with its different alternatives called proof-of-space or proof-of-storage. However, PoST differs from proof-of capacity in that PoST allows network participants to prove that they have spent a “SpaceTime” resource, meaning that they have allocated storage capacity to the network over a period of time. Formally, the PoST resource is defined as a trade-off between CPU work and space-time. The basic idea is that, under reasonable cost assumptions, a rational user will prefer to use the lower-cost space-time resource over CPU work. Compared to a PoW, a PoST requires less energy use, as the “difficulty” can be increased by extending the time period over which data is stored without increasing computation costs. Also, the PoST differs from Proof of Space as the time-element is implicit Proof of Space. For example, in Spacemesh⁴, they consider of Proof of Space protocols as PoST protocols with a fixed initialization cost that depends linearly on the space used [Moran & Orlov, 2016].
References
Ball, M., Rosen, A., Sabin, M., Vasudevan, P. N. (2017) — Proofs of Useful Work — Feb 27, 2017, https://eprint.iacr.org/2017/203.pdf
Bano, S., Sonnino, A., Al-Bassam, M., Azouvi, S., McCorry, P., Meiklejohn, S., and Danezis, G. (2017) — SoK: Consensus in the Age of Blockchains, University College London, United Kingdom & The Alan Turing Institute, 2017
Helix, (2019) — HelixMesh Protocol, V 1.0, April 5th, 2019 — Helix Cognitive Computing Team. Available at www.hlx.ai
Moran, T., Orlov, I., (2016) — General Rational Proofs of Space-Time. https://eprint.iacr.org/2016/035.pdf
Sirer, E. G. — from his Twitter account: https://twitter.com/el33th4xor/status/1006931658338177024?lang=en
SoK, (2017) — SoK: MetaAnalysis of Alternative Consensus Protocols for Blockchains https://github.com/Mechanism-Labs/MetaAnalysis-of-Alternative-Consensus-Protocols/blob/master/MetaAnalysis.pdf
Tasca, P., Tessone, C. J., (2019) — A Taxonomy of Blockchain Technologies: Principles of Identification and Classification. Ledger Journal. LEDGER VOL 4 (2019) 1–39 ISSN 2379–5980 (online) — DOI 10.5195/LEDGER
¹ The term Sybil comes from Sybil Dorsett, a pseudonym of a book character written by Flora Rheta Schreibe (1973) that suffers from multiple personality disorder.
² It is worth to mention, that PoW caused probably the biggest confusion in the consensus terminology because it plays a distinctive role in the Nakamoto protocol: The computers that secure the blockchains and add new transactions to the ledger are known as miners. These miners have a monetary incentive to come to a consensus with other miners regarding the ledger’s history by mining on the ”longest chain” (i.e., Nakamoto Consensus) is backed by the PoW [Bano et al. 2017]. And, while PoW in Nakamoto (e.g. Bitcoin implementation) functions as both a Sybil control mechanism, and as a source of randomness to select a block maker, other proof-of-mechanisms, e.g. PoS — see below –, only serve as a Sybil control mechanism and thus require a separate randomness protocol for choosing proposers [SoK, 2017].
³ HLX is the currency used by HelixMesh protocol of [www.hlx.ai]
