HPA has gathered a panel of cutting-edge thinkers (including me) from the studios for a discussion over lunch at The Garland on October 11th.
This post is the sixth post in a series dedicated to demystifying blockchains. The last post introduced the Proof of Stake. The third post introduced the concept of consensus and classified them into two categories: lottery-based and Byzantine Fault agreement-based protocols. This post presents the most known Byzantine Fault agreement-based consensus: Proof of Work
Byzantine Fault Tolerance is known for about four decades. A Byzantine Fault is any failure of a system. The failure may be that the system is not working, or the system is behaving maliciously. An f-Byzantine Fault-Tolerant network is a network that operates correctly under the assumption that f nodes may be concurrently experiencing Byzantine faults. The nodes are either well-behaving or ill-behaving, i.e., suffering from Byzantine Faults. The network comprises n nodes with a maximum of f ill-behaving nodes.
The best implementation of Byzantine Fault Tolerant system for asynchronous protocols is the Practical Byzantine Fault Tolerance (PBFT). PBFT assumes that the size of the network is at least 3 f + 1.
At any given moment, one node is the primary and the other nodes are replicas. The simplified algorithm operates as follows:
A client sends a request to the primary node for an operation
The primary node broadcasts this request to all replicas
Replicas perform the requested operation and return an answer to the client
The client waits for at least replicas answering the same result. This is the consensus outcome of the operation.
The figure illustrates the basic behavior for the case of a 1-node fault tolerant system. It has at least four nodes. The client sends its request to the primary node. The primary node broadcasts the request of operation to the three other nodes: replica 1, replica 2 and replica 3. As soon as the client receives an affirmative answer from two replicas (in the figure, replica 1 and replica 3), it considers the operation successful. If one replica is failing, the client will still receive proper answers from the two other replicas. If the primary node is failing, then the protocol switches the role of primary to one replica.
The PBFT is well adapted for fixed networks with known trusted entities. As such, it may be useful for blockchain validated by a set of known, approved authorities, i.e., permissioned blockchains. The number of authorities defines the system’s resilience. The minimal size is four which allows for one ill-behaving authority. Each authority has the same level of trust and shares trust with the other authorities.
PBFT is straightforward and robust. The theoretical background is well studied, known for a long time and used by the community. The trust is not linked to the ownership of resources or stakes. It is fast and computationally efficient. There is no notion of mining. It is deterministic. A permissioned blockchain using PBFT can have a very high through output of transactions.
Unfortunately, the trust is not flexible. PBFT requires a pre-established list of collaborating trusted participants. Any new participant requires new settings. This adjustment cannot be dynamic. The consensus of permissionless blockchains cannot employ PBFT. By participants, we mean the validation nodes and not the users of the blockchain. The system does not need to trust the users. It is the role of the validation and consensus to screen bad transactions.
A known weakness is that the system is prone to Sybil attacks. An entity may attempt to register several participants that it controls stealthily. If the cheating entity controls at least f sibyls, then it controls the full system. Therefore, the initial trust in the participants is paramount. In most permissioned blockchains, the likelihood of Sybil attacks is negligible.
Conclusion: PBFT is a well-known, well-studied protocol. For decades, distributed systems have taken their decisions using it. It is fast and computationally efficient. PBFT is an interesting consensus protocol for permissioned blockchain. Some variants of BFT are also available.
M. Castro and B. Liskov, “Practical Byzantine Fault Tolerance,” in Proceedings of the Third Symposium on Operating Systems Design and Implementation, New Orleans, USA, 1999
This post is the fifth post in a series dedicated to demystifying blockchains. The fourth post introduced the most famous lottery-based consensus: Proof of Work (PoW). This post presents another type of lottery-based consensus: Proof of Stake (PoS).
With PoW, the entity that has the highest calculation power has the highest probability to be the elected validator of the block. With PoS, the entity that has the highest stake in the system has the highest probability to become the elected validator of the block. Each potential validator, so called forger, puts some collaterals in escrow. Would the elected validator cheat, then thisvalidator would loose the escrowed collateral. Obviously, the collaterals cannot exceed the validator’s owned wealth.
The security assumption is that the more stakes you have in a system, the more you are expected to defend this system in order not to lose your stake. Thus, the underlying hypothesis is that the highest stakeholders are acting rationally. Furthermore, like with PoW, there is an incentive to forge. The forger who validated a block is rewarded with some coins (and the transaction fees).
PPCoin implemented the first PoS. It uses the concept of coin age. The coin age is the number of coins multiplied by the holding period of these coins. If Alice holds ten coins for 20 days, then her coin age is 200 coin.day. The collateral is a number of coin ages bidded for validating the block. Indeed, Alice bids n coin ages by paying herself these n coins. The forger must solve a kind of PoW, but the challenge is inversely proportional to the collateral, i.e., the space of search decreases when the collateral increases. Thus, the winning forger is most probably the forger with the highest collateral.
Buterin Vitalik, the founder of Ethereum, introduced Casper: a PoS based on Byzantine Fault Tolerance. Casper has a set of volunteer validators. Each validator commits a number of ethers as a deposit. Casper defines an epoch as a set of 100 consecutive blocks. Roughly, Casper validates an epoch once a number of validators whose aggregated deposit represents more than 2/3 of the total deposit validated the epoch. The assumption is that if less than 1/3 of the validators cheated, they would be detected and identified. In that case, the community would remove their escrowed collateral through a hard fork.
The main advantage of PoS is that it consumes far less computing power than a PoW-based system. Usually, PoS has also less latency than PoW. The main latency is for the minimal time that collaterals are escrowed.
According to me, the trust model of PoS is weaker than the trust model of PoW. An ill-behaving majority stakeholder may attempt to use her advantage to take an even more significant stake. Furthermore, the stakeholders are expected to act rationally. This assumption may be weak in case of a state-funded attack which may have objectives other than monetary ones.
Even with a rationale player, there may be some weakness. If the gain of a misapproved transaction exceeds the loss of the escrowed collaterals, it may be a rationale decision to cheat. For instance, PoS is prone to “Nothing at Stake” attack. Alice may have a significant stake at time T0. She cashes all her stake at time T1. At T1, she has no more stake but has gained some benefits. As she has nothing to lose anymore, she may attempt to attack the blockchain at T0 when she had the majority of the stake. She attempts to start a new branch from T0, using all her then available-stake as collateral. Having a higher stake, she has good chance to win and thus begin a new branch where she would own again the already spent stakes. Would she not win, she would have lost nothing. Of course, T0 and T1 must be close.
PoS is faster and less power consuming than PoW. As such, this type of consensus may overcome some of the issues of PoW. Nevertheless, its trust model seems weaker. I foresee that we may see new PoS protocols in the coming years.
Recently, an IBM team presented at ASIA CCS’18 a framework implementing watermark in a Deep Neural Network (DNN) network. Similarly, to what we do in the multimedia space, if a competitor uses or modifies a watermarked model, it should be possible to extract the watermark from the model to prove the ownership.
In a nutshell, the DNN model is trained with the normal set of data to produce the results that everybody would expect and an additional set of data (the watermarks) that produces an “unexpected” result that is known solely to the owner. To prove the ownership, the owner injects in the allegedly “stolen” model the watermarks and verifies whether the observed result is what it expected.
The authors explored thee techniques in the field of image recognition:
- Meaningful content: the watermarks are modified images, for instance by adding a consistently visible mark. The training enforces that the presentation of such visible mark results in a given “unrelated” category.
- Unrelated content: the watermarks are images that are totally unrelated to the task of the model; normally they should be rejected, but the training will enforce a known output for the detection
- Noisy content: the watermarks are images that embed a consistent shaped noise and produce a given known answer.
The approach is interesting. Some remarks inherited from the multimedia space:
- The method of creating the watermarks must remain secret. If the attacker guesses the method, for instance that the system uses a given logo, then the attacker may perhaps wash the watermark. The attacker may untrain the model, by supertraining the watermarked model with generated watermarks that will output an answer different from the one expected by the original owner. As the attacker has uncontrolled, unlimited access to the detector, the attacker can fine tune the model until the detection rate is too low.
- The framework is most probably too expensive to be used for making traitor tracing at a large scale. Nevertheless, I am not sure whether traitor tracing at large scale makes any sense.
- The method is most probably robust against an oracle attack.
- Some of the described methods were related to image recognition but could be ported to other tasks.
- It is possible to embed several successive orthogonal watermarks.
A paper interesting to read as it is probably the beginning of a new field. ML/AI security will be key in the coming years.
Zhang, Jialong, Zhongshu Gu, Jiyong Jang, Hui Wu, Marc Ph. Stoecklin, Heqing Huang, and Ian Molloy. “Protecting Intellectual Property of Deep Neural Networks with Watermarking.” In Proceedings of the 2018 on Asia Conference on Computer and Communications Security, 159–172. ASIACCS ’18. New York, NY, USA: ACM, 2018. https://doi.org/10.1145/3196494.3196550.
This post is the fourth post in a series dedicated to demystifying blockchains. The third post introduced the major concept of consensus and classified them into two categories: lottery-based and Byzantine Fault agreement-based protocols. This post presents the most known lottery-based consensus: Proof of Work (PoW). Most permissionless blockchains, such as Bitcoin or Ethereum use PoW.
The aim of a PoW algorithm is to validate a block in a distributed environment. The PoW is designed so that ill-behaved actors would need to possess the majority of the system’s computing power to validate a forged block, for instance, for implementing double spending. The PoW is information, so called the nonce in Bitcoin parlance, present inside the block to be validated. The verification of the PoW is simple and fast whereas its construction is difficult to compute. The validator must solve the cryptographic puzzle described in the first picture where
- Bi is the block to be validated.
- Target is a value determined by an authority to adjust the difficulty of the challenge. Hash is a cryptographic one-way function. One characteristic of a cryptographic one-way function is collision resistance. Hash is easy to calculate, but given a number y, it is computationally difficult to find x such as Hash(x)=y.
All validators (so-called miners in the Bitcoin ecosystem) try to solve this equation. Currently, for approved cryptographic one-way functions, such as SHA-3, the only known method to solve this equation is brute force attack, i.e., exploring all the possible values systematically. The first miner to solve the equation, i.e., to find a suitable PoW, is elected the winning validator. Furthermore, the winner receives a reward (currently 25 Bitcoins). The parameter Target defines the difficulty of the challenge. Bitcoin defines the minimum number of trailing zeros that the hash must have. This number depends on the expected average solving time and the global mining computation power. In the Bitcoin ecosystem, this value is adjusted every fortnight to have an average validation time of ten minutes. If the global processing power increases too much, the difficulty target adds some zeros. Two interesting consequences:
- For a given block, there is not one unique PoW as the equation as many solutions. The winner is the first to find one solution. Two validators may find “simultaneously” a solution. The branch validation strategy addresses the corresponding problem. A future post will address branching.
- The validation time of one block is not fixed. It depends on the “luck” of the miners.
PoW works because it requires a huge calculation power. An ill-behaving actor that would control the majority of computing power would also control the system. The higher the total processing power of an entity is, the larger the probability of this entity to become the validator of a block is. With the rise of mining pools, the assumption that no entity controls a significant calculation power weakens. A mining pool is an association that federates many miners who share the reward and transaction fees. Mining pools unbalance the odds. It is not unrealistic in tiny environments that a mining pool could control more than half of the total processing power. Therefore, PoW may only be suitable for large deployments.
Finding the PoW is, by construction, computing intensive. To gain efficiency mining usually employs either Graphical Processing Units (GPU) or specialized gear based on custom developed ASICs. This calculation implies a lot of energy consumption. There is no sanctioned estimation of the total energy consumption due to mining. Nevertheless, it is commonly accepted that it is huge. Many mining farms are located in regions where energy is cheap.
PoW is surely not green nor fast.
PoW favors the entity that invests the most effort into validation.
PoW is a robust consensus protocol under the assumption that no entity would control more than 50% of the total mining power. At the time of Bitcoin’s creation, this assumption was valid. Currently, six mining pools have each more than 10% of the total mining power (see https://en.bitcoin.it/wiki/Comparison_of_mining_pools). This assumption may become less robust.
PoW is a huge energy consuming protocol.
This post is the third post in a series dedicated to demystifying blockchains. The second post described the difference between permissionless and permissioned blockchains. It also introduced the concept of validator. This post will present the notion of consensus.
A consensus mechanism or protocol ensures that all nodes of the system agree to a shared, approved state. In the framework of a distributed ledger or blockchain, a consensus mechanism enforces that all participants use the same state or version of the ledger. In other words, it is the mechanism that ensures that every entity agreed on the same transactions and that all copies of the ledger are identical. Consensus protocols are not new. They at the core of many distributed systems and mirroring systems. Nevertheless, permissionless blockchains introduced a new challenge. Not all participants to a permissionless blockchain may be behaving properly.
Two kinds of consensus
There are mainly two categories of consensus mechanism:
- Byzantine Fault agreement-based
The first category is sometimes called the Nakamoto-consensus in honor of the pseudonym of Bitcoin’s founder Nakamoto. The consensus mechanism elects the validator, i.e., the node that decides which is the next block to be appended to the ledger. The election is a lottery draw. The winner is the validator. Each new block requires a new draw. The selection through a lottery reduces the likelihood of an ill-behaving node to validate a forged block. The lottery does not necessarily follow an equiprobable distribution. Each mechanism has its own probability distribution favoring one given characteristics of the winner. Thus, each lottery-consensus has a different trust model. The Proof of Work (PoW), used by Bitcoin, is the most well-known mechanism. There are many other types such as Proof of Stake (PoS), Proof of Space, or Proof of Elapsed Time (PoET). Future posts will explore in details PoW and PoS.
The second category is based on Byzantine Fault Tolerant (BFT) system. BFT systems are designed to operate even if some participants in the protocol are failing. Failure may be involuntary (for instance, a participating node is out of order) or voluntary (for instance, an attacker controls the failing node). BFT employs voting mechanisms to decide the consensus. The used mechanism defines the trust model. It is usually well defined. The Practical Byzantine Fault Tolerant (PBFT) mechanism is the most well-known mechanism. A future post will explore PBFT.
Hybrid consensus mechanisms seem to appear mixing lottery with a pinch of BFT. Casper, the next consensus mechanism of Ethereum is a PoS with some BFT in it.
Lottery or Byzantine Fault Tolerant?
Lottery-based mechanisms are more complex and slower than BFT-mechanisms. Lottery-based consensuses are well fitted for permissionless blockchains. There is no control on the validators. Anybody may participate in the validation. Therefore, the lottery reduces the risk. In a permissioned blockchain, the validators are known. Thus, BFT-consensuses are adequate. Depending on the mechanism, the designer knows how many validators must be compromised or must collude to validate a forged block successfully.
Research on consensus is currently an extremely active field. Unfortunately, many consensus mechanisms are (too) young and their security has not been enough studied. The following chart illustrates relative age of major consensus mechanisms.
If you want to manage your blockchain, then you need to understand the corresponding consensus mechanism. It participates to the trust model of your solution.
I will present this topic at APEX Tech. Check out the full schedule: http://bit.ly/2LtZW7Z