State Channels: Use Cases and Applications

As I explained in the previous blog, the State Channel solves blockchain scalability, transaction fees, and privacy concerns. In this blog, we’ll look at the potential use cases that can be implemented as decentralized applications (DApps) using State Channels and the approach involved.

For a quick recap of the previous blog, the State Channel is a technique designed to allow users to make multiple transactions without committing all of them to the Blockchain. In the traditional State Channel, the Smart-Contracts defines the initial state of the State Channel. Users can carry out an infinite number of transactions outside the Blockchain by making continuous changes, starting from the initial state. Any user can send the latest state as a closing statement to Smart-Contract on the Blockchain. Also, users can verify each state transition validity using Smart-Contract on the Blockchain.

The State Channel off-chain gives instant-finality and data-privacy with negligible transaction fees. This, in turn, has gone a long way in terms of establishing their importance in case of DApps scalability. Gaming DApps can use the scalability potential of State Channels, wherein participants either buy or sell game artefacts or indulge in gambling like in case of card games. Likewise, video streaming DApps can use State Channels to facilitate applications on a pay-per-use basis. Domains such as Supply Chain Management and P2P micro-payments can also benefit from the scalability and privacy potential of State Channels.

Use Case of State Channels: Supply Chain Management

Our businesses have widened globally, complicating the whole ecosystem of supply chain management. Let us consider the case of the food supply chain. Have we ever imagined the source from where we get our food?

The supply chain in the food industry is defined by associating the following:

  • Crop Origination
  • Food Processing at Refineries
  • Distribution of processed food to retailers
  • Selling of Food Items to Consumers

Since the food supply chain consists of millions of people worldwide with tons of raw materials and food crops, it becomes challenging for the food manufacturers and consumers to know where the different components of the food item belong.

The supply chain’s contracts can be quite complicated, costly, and susceptible to errors due to the involvement of paper-based trails for the change of ownership, letters of credit, bills of lading, and complicated payment terms. Therefore, we can use State Channels to bring in transparency and real-time traceability in the whole supply chain system.

How do State Channels Help?

Supply chain management consists of raw materials, manufacturing, distribution, and consumers. The quality of each raw material, the manufacturing processes, and distributors are tagged uniquely using Hashing algorithms.

Any product includes various raw materials and goes through different manufacturing processes. At the end of the production cycle, they are delivered to the consumer. Therefore, the product off-chain state should keep a record of raw materials, manufacturing processes, and shipping processes.

Figure (1): – State Channel between Supplier and Manufacturer

A Supplier supplies different raw materials to the manufacturer. This process will run in its separate State Channel. By the end of the process of purchasing, the manufacturer receives raw materials from different suppliers. Since these states were finalized already, they will be updated on the Blockchain and represented by the Non-Fungible tokens.

Figure (2): – State Channel for manufacturing Process

The manufacturing step includes multiple processes and consumes a variety of raw materials. When the product is ready, its state will consist of used raw materials token tag from the previous ERC20 tokens and processes tag. The Distribution process will deliver products to retailers, and the end consumer can get it from the retailer.

Figure (3): – State Channel for the delivery process

Figure (4): – State Channel for Retailer

In each process, the off-chain states can include different details and can be verified using a specific verification pattern. These details can be either product’s raw materials, manufacturing process information, or payment information. Therefore, the final state will update the ownership of the product and transfer the equivalent coins to the respected wallets on the Blockchain.

Here, we do not need to attach original letters of credit, bills of lading on the Blockchain. Instead, we should attach hash of that document on the Blockchain, so that users can compare document hash with hash updated on the Blockchain and verify authenticity of the original bills.

In Figure (4), the consumer can verify the product manufacturing details and the delivery process using the finalized state of Figure (3) State Channel. The finalized state from Figure (2) State Channel can be linked-to the verification process of the State Channel in Figure (3). The finalized state of the raw materials purchasing process from Figure (1) State Channel will be attached to the product being made in the State Channel in Figure (2).

This will bring transparency, privacy, and cost reduction in the whole supply chain management.

DApp Components

DApp built using State Channels would be based on a similar set of components, every DApp consists of a user DB component to ensure off-chain states security and a client application responsible for interacting with the Blockchain smart contract and with other participants.

The Smart contract defines the details that are going to be a part of the state structure. The same state structure will be used in the digital signature and verification process. Example: – A State Channel structure for chess game must hold chessboard state, chessboard id, and the Smart-Contract address.

The client application opens a State Channel on the Blockchain, and then the smart contract will initialize the State Channel using given inputs and predefined business logic. This business logic could require an on-chain confirmation from other participants before the State Channel goes into the active state. Once State Channel is activated, the initial state has been updated and available to all participants on the Blockchain. The client applications use this initial state and start off-chain transactions among them. The client applications must keep the latest off-chain state precisely for that they can use separate secure DB components. The non-tempered latest state will prevent all malicious actions of other participants.

Figure (5) shows a simplified architectural overview for a State Channel DApp.

Figure (5): – State Channel Generic Architecture

Conclusion

State Channels trade-off speed, finality, and transaction cost along with unparalleled security. We kept off-chain transaction states in a separate DB component to minimize the security trade-off. We make sure the uniqueness of the state details across the Smart-Contracts on the Blockchain network to prevent replay attacks.

I hope you find this article useful and insightful. To deep dive into some of our work around State Channels, you can check out the GitHub repository. Happy reading!

References

State Channels: An Introduction to Off-chain Transactions

In recent years, Blockchain technology has become a running theme, although the worldwide acceptance of this technology is still inconclusive due to its scalability, anonymity, and transaction costs. In this article, I will make you understand how the issues mentioned above are restricting Blockchain adoption across everyday applications. Let us assume that Alice and Bob are playing a game of chess that is designed at the top of Blockchain technology. For making a move, a player obliges to pay the transaction fee and wait for the move confirmation on the Blockchain as the chess move requires state changes and state changes need to be committed on the Blockchain. Such confirmation time and validation fee inclusion make Blockchain technology inaccessible to tiny hands. Even if we omit the transaction fee issue, the `current Blockchain solutions are not scalable for decentralized applications (DApps). State channel addresses these concerns without significantly increasing the risk of any participant.

What is the State Channel?

State channel is a technique designed to allow users to make multiple Blockchain transactions such as state changes or money transfers, without committing all of the transactions to the Blockchain. In the traditional state channel, only two transactions are added to the Blockchain, but an infinite or almost infinite number of transactions can be made between the participants. Example: In a Chess game built on top of state channels, the chess game beginning move and closing move should be committed on the Blockchain. All other moves can be made off-chain without the involvement of the Blockchain. These off-chain transactions do not require a fee with instant finality.

A  Payment channel is one implementation of the state channels, which deals with money transfers. A state channel is a smart-contract that enforces predefined rules for off-chain transactions. Each transaction creates a new state based on the previous state, signed by each party, which is cryptographically provable on the blockchain. Every new state makes the last state invalid since the smart-contract acknowledges only the highest state as a valid state.

State channels don’t have a “direction” because they are a generalization and a more powerful version of payment channels. Consider a unidirectional channel as one whose state is simply one state value: “Alice’s payment to Bob”. Consider a bidirectional channel as one that has two state values: “Alice’s balance” and “Bob’s balance”.

Working of State channels

In a state channel application, each party must sign an initial (opening) channel transaction, and deposit money according to application business logic. Users need to pay predefined transaction cost each time they either open a new channel or deposit money into the active channel. A deposit transaction deducts money from the depositor’s account and transfers it to the smart-contract address. This depositing mechanism will ensure that there will be no double-spent occur in on-chain or off-chain network. The smart-contract is not authorized to mint or destroy money, therefore in each valid state, all participants combined money equals total deposited money no more and no less. Figure (1) demonstrates a generic idea of the State Channels.

FIGURE(1):- STATE CHANNEL GENERIC SOLUTION

Let us re-consider the example cited above. Alice and Bob want to open one payment channel since they are playing a tic-tac-toe game, and after each game, they want to transfer money. Initially, they both signed the opening transaction and deposited 100 and 100 cash on the board. Alice and Bob are expected to pay transaction fees only at the time of channel opening, and now they can play the infinite number of game rounds without paying transaction fees with instant transaction finality. Assuming they decide to leave the game after the nth round, and the latest state was Alice 75 and Bob 125. Either Alice or Bob can send a channel closing transaction with the latest valid cryptographic state. It will take some time and transaction cost to validate this closing transaction, and the transaction, in turn, will send cash back to the respective wallet.

Payment Channel benefits over on-chain transactions

Cheap

Participants pay validator fees at the time of opening and closing channels. All other transactions are free even though the number of transactions is hundreds or thousands.

Instant Finality

On average, Bitcoin will take about 10 minutes to complete the transaction, and Ethereum will take 15 seconds to 5 minutes if you pay the regular gas price. That means if Alice made a move, the game would stop until the move is confirmed on the chain. On the contrary, payment channel transaction finality depends on the bandwidth of the network, more the bandwidth faster the finality.

Privacy

All on-transactions are registered in the Blockchain ledger and are available in the public domain. Anyone can analyze these Blockchain data and get insights into the individual. On the contrary, state channel off-chain transactions are not committed in the Blockchain except for opening and closing transactions that give participants a considerable degree of privacy.

Scalable

Off-chain transactions do not change the on-chain state, therefore the payment channel Apps are scalable. And if we can build a network of payment channels like the Raiden Network or the Lightning Network, then we don’t have to open a direct channel between the two parties if there is some indirect channel that leads to scalability.

Security

Security of payment channel states depends on how the smart- contract validates the states, what information is included in the states such as (1) state nonce, (2) smart-contract address, (3) channel Id, (4) state and stakeholder status, etc. Each participant shall make a digital signature to validate the current state. The aim of including this information in the state is to make each state universally unique like UUIDS. The smart contracts address and channel id, together used to prevent cross-contract and in-contract replay attacks.

Remaining Challenges

The Payment Channel will lock down the deposited money in the smart-contract and release it after the channel has closed. No one wants to lock up a massive amount of capital in a smart-contract that makes payment channels useful for micro-payments. Each state compels all participants to sign, which is why one offline participant can stop the processing of the payment channel.

I hope you found this article to be insightful and useful. To deep dive into some of our work around state channels, you can check out the GitHub repository.

Should a blockchain node save all the transaction logs?

Introduction:

Blockchain is a technology that drives all the cryptocurrencies. In every one of them, a set of validator nodes are responsible for validating all the transactions. The validators are assumed to be rational and self-interested, i.e. they are only interested in making as much money possible for themselves. Under such assumptions, it is generally assumed that a required majority of the validators would agree on the sequence of transactions that have ever happened on the blockchain.

However, such blockchain validator nodes are generally expensive in terms of the size of the disk space they need. The oldest and most popular cryptocurrency Bitcoin, for example, needs about 200 GB of disk space to store the entire transaction log. This makes it necessary to have a high-speed connection and a lot of time to even get started on mining or validation. This is a problem that prompted researchers to suggest sharding as a solution, i.e. storing only part of the log in each node, but storing the entire log as a whole. Sharding comes with its own challenges when it comes to validating transactions.

But, does it make sense for a node to store the transaction log starting all the way from the genesis block? This is an important question that needs to be answered before such solutions are crafted.

To understand whether saving all the transaction log is possible/necessary, we consider the following points –

1. Is it necessary to store the entire transaction log to validate transactions?
2. Is it more secure to store the transaction log than not storing it?
3. Is it possible to incentivize the validator nodes to store the log?

We take on these points in the rest of the article.

Is it necessary to store the entire transaction log to validate transactions?

To validate a transaction, the only thing that a node needs is to know that state of the blockchain right before the transaction. It is immaterial how that state was achieved. So, it is enough to store the state after each block. In fact, we can go even further – since the blocks that have been mined a long time before the current time are hardly ever going to be undone, it is safe to delete all the previous blocks.

The natural question that comes to our mind is if it would somehow compromise the safety of the blockchain, i.e. – would it somehow make the blockchain to approve a transaction that is not correct based on the current state of the blockchain? To answer this question, we move onto the next section.

Is it more secure to store the transaction log than not storing it?

When thinking about it, we need to think in terms of security of the whole transactions and not just the part on the blockchain. Most transactions have two parts – a payment on blockchain and the receipt of something of value in exchange. The second part of the transaction is not stored in the blockchain. This means the seller that sells the product or the service in exchange for some cryptocurrency relies on the blockchain not to revert the transaction after he/she provides the product or the service. This, in turn, means that there has to be a reasonable time after which the transaction must become completely immutable requiring the block in which it is included to be immutable too. In other words, we need some finality of the transaction and the block. When a block is finalized in some form or other, it is okay to forget what happened before that and simply continue as if that block is the genesis block. This in general means that the transaction history must be stored only up to a short period of time. In the case of Bitcoin, people normally assume that a block is pretty much finalized after an hour of time, so it makes sense to delete all the history before that. That means, in the case of Bitcoin, a validator only needs the list of UTXOs at the end of each of the last few blocks.

We now turn towards our final point.

Is it possible to incentivize the validator nodes to store the log?

As stated earlier, the validators are assumed to be selfish and rational. Which means, they need to be paid or rewarded for doing anything. Since the validators only get paid in cryptocurrency for mining the blocks in all public blockchains, that’s the only thing they should be doing. We have also seen that the storage of the data is not necessary for doing the job of validating. Therefore, there is no incentive for any validator to store the entirety of the transaction logs starting from the genesis. If we indeed want the rational validator to store the entire history of the transactions, we must sufficiently incentivize the validators to do so. We may want to require proof of storage of all the transactions in a block for it to be considered valid. Is it possible to do it? Yes indeed, if we change the proof-of-work consensus protocol as follows –
1. Let a block being proposed be B and the corresponding proof-of-work be p. This means that p is the nounce such that hash(B||p) < threshold.
2. Let the number of transactions before that block be N.
3. Let h = hash(B||hash(p)), where || means concatenation.
4. Compute the remainder r when h is divided by N. Since, h is typically a 256-bit number, it must be the case that h is way greater than N, so this means r is less than both h and N and can be considered a random sample from the set of natural numbers less than N.
5. Let the transaction with the sequence number r be tr. The transactions are indexed from 0 to N-1.
6. Now, the block proposal must be (B||p|| tr ) for it to be considered valid.

It is easy to see that if the validator does not store all of the logs of transactions, it would need more effort to generate valid blocks since it has to throw away all the proof-of-work and start over if the corresponding transaction is not stored by it. More specifically, if a validator stores on a fraction f of all the history, it has to throw away the proof-of-work 1/f times on an average, significantly reducing its average mining reward for the same amount of processing power. It is, therefore, most efficient for any validator to simply store all the transactions from the genesis block. But, such a system is not currently used, so the validators are really doing a social service by still storing all the transactions. However, from our discussion on security, it is clear that such a modification can be quite unnecessary.

Another issue is that when a new validator joins, it must download the entire transaction log from its peers. The peers, however, are not incentivized at all to provide this data to their new peer. They are simply adding a competing mining power while also burdening their own bandwidth to broadcast the information. The least we can do is to relieve them from having to broadcast the entirety of the history of transactions.

Conclusion:

We can see that it is possible to mandate the storage of all the transaction history if we choose to design the blockchain in such a way. However, it seems quite unnecessary and cumbersome. It may even provide more motivation for the existing miners to provide the needed data to any new joiners. We have also seen that there is no advantage of storing the transaction history in terms of the security of the blockchain, so we might as well not want to do so.

Plasma Cash DApp Use Case

The Plasma Framework solves the privacy and scalability issues of the public Ethereum blockchain. In this blog, we will take a closer look at the possible use cases that can be implemented as decentralized application (DApp) using Plasma Cash, and how can those be implemented.

Plasma Cash Use Cases

Plasma Cash converts all deposit tokens into a non-fungible-token (NFT), wherein each NFT token holds a unique and stagnant behavior. Therefore, Plasma Cash can be an ideal fit for applications where assets aren’t divided and ownership is changed frequently. Gaming Dapps can use the scalability potential of Plasma Cash where users exchange game objects modeled as token, for instance any character’s card, suit, or any power. In addition, non-gaming models can also benefit from the scalability and privacy potential of Plasma Cash. For example- Artifact review workflow application (developed as DApp) in an Enterprise, where a given artifact is transferred between users and the artifact can hold one of the states, namely Created, Submitted, Rejected, Accepted, and many more.

Document Review Workflow Use Case

In any enterprise, artifacts such as Product (Service) specifications, quotations, proposals, etc. are created and transferred to multiple departments for evaluation. Each stake holder can reverse it conclusively, accept it, or transfer it ahead, and Plasma Cash is the best fit for an application like this. Here, the artifacts can be modeled as NFT tokens and state changes are similar to NFT ownership transfers. The final state will be transferred to the Ethereum parent chain.

 

Figure (1) shows a simplified workflow of an artifact.

Consider a document created by a user and the document owner has submitted it to another user for review. In this step, the document moves from ‘created’ state to ‘submitted’ state. After successful review, the reviewer will send this document for publication to the third user and the document moves from the ‘submitted’ state to the ‘reviewed’ state. Post publication, the document state is changed to ‘published’ state.

The deposit function of the plasma contract will take document hash as the input and produces an equivalent NFT token as output. As document state is altered, it’s equivalent NFT token goes through corresponding state changes; after publishing the document, the NFT token will be transferred to the Ethereum parent chain using the plasma contract exit function.

DApp Components

DApp built using plasma would be based on a similar set of components i.e. every DApp consists of an operator process, a user component to ensure child chain security to arrest double spend, and a client application responsible for interacting with the child and the parent chain.

The client application deposits a token to the Plasma Chain smart contract on the parent chain, then the smart contract will return an unsigned integer and emit a DEPOSIT event. So far, DApp only has UID knowledge and DApp needs to fetch the deposit block index. For that, DApp needs to monitor all the upcoming blocks on the child chain and check whether the upcoming block has a deposit block with the same UID. The block index is the utmost important property either for security or transferring it to another user. The user component maintains all token’s UID of the user and corresponding block index details and watches the child chain at least once during the exit period. The user component fetches all the upcoming blocks and smart contract states to check incoming tokens, or if anyone has tried an invalid exit or a double-spent, and then, raise counter action appropriately.

Conclusion

We are working on Plasma Cash for use-cases where we need to change one or more states including NFT transfer. In case we have got you interested enough, do check out our work on the GitHub repository.

Plasma Cash Side Chain

Problem with the current solution (blockchain)

Blockchain gives us a reliable, trust-less secure system with no central governance. In spite of having such capabilities, enterprises do not prefer to use public blockchain for building solutions. The primary reasons for this are privacy and scalability. Since all blockchain data is publicly available, one can use blockchain analytic tools to get insights such as a linked public address, spending habits of a user or public address and then who transferred what to whom. The second reason is that scalability is a critical issue with any blockchain. Currently, blockchains handle [3-30] transactions per second, which is nowhere near the mainstream centralized payment system. Example: Visa processes around 1700 transactions per second.

Proposed Solution

Since privacy and scalability are major and widely known interests in the blockchain community, all are trying to solve it in their own way. Joseph Poon and Vitalik Buterin came up with the idea of a child chain called Plasma. A plasma framework is a smart contract that will be deployed on the Ethereum main chain (parent chain). The smart contract will enforce the child chain to follow predefined rules. The plasma child chain is not empowered to create or burn any artifacts such as fungible ERC 20 tokens or non-fungible ERC 721 tokens (NFT). Therefore, to operate on the plasma child chain, users need to transfer their parent chain ERC tokens to the plasma child chain. The plasma child chain is built on the top of the parent chain in a way that whenever it appends a block in the child chain, it must add the Merkle root of that block to the smart contract on the parent chain otherwise that block will be invalid. The plasma framework will solve the privacy problem since no transactional data history will be added to the public parent blockchain. It is using Proof of Authority consensus so that it is far better scalable in terms of transactions per second and will have all the benefits of blockchain technology.

 

Figure (1) shows different variants of the Plasma Framework. Since the idea of the plasma child chain came up, the whole Ethereum community is working on improvements. Therefore, today, multiple designs of plasma framework exist such as Plasma-MVP, Plasma-MoreVP, Plasma-Cash. Individual plasma also has multiple variants with slightly different use-cases.

 

 

Figure (2) shows the generic idea of the Plasma Framework. Each variant of the Plasma Framework implements its Smart Contract using this abstract idea. Therefore, each Plasma smart contract implements the following interface.

Interface:

  • DEPOSIT
  • EXIT
  • CHALLENGE

Including the above-mentioned function, all methods/functions of the smart contract can have different implementation depending on the idea of that Plasma variant.

For example – In Plasma-MVP users must sign a transaction when they make a transfer and again when it gets confirmed. Therefore, for a single successful transfer, the user must sign it twice. Plasma Cash users need to sign only once for a transaction, and each token behaves like NFT.

Plasma Cash

We are working on the Plasma Cash framework and building a decentralized application (DApp) on top of it. The Authority (The Operator) of the child chain is the public address who deployed the smart contract to the parent chain. Only the operator has the authority to append a block into the child chain. The operator can append a block in two ways. First, when a deposit occurs in the parent chain, then the operator will create a block having one UTXO equivalent to the deposited amount. The other way is to create a block by including all token transfer transactions. The smart contract emits a distinct event for each activity in the parent chain so that users listening to the smart contract will get to know all state changes of the smart contract. These events are like meta-data of the child chain.

Let’s take an example of how useful these events are. Assume a user deposited an asset to the plasma smart contract if the operator will not listen to events from the smart contract, it will never get to know that a deposit transaction happened on the parent chain and will not include that transaction’s equivalent NFT token to the child chain. That is why it is necessary for the child chain operator and for the users to listen to the smart contract events.

Once a token is added to the child chain, it can be transferred to any user. The plasma cash is UTXO based model. Therefore, transferring a token implies spending a UTXO and creating another UXTO which holds new ownership. Whenever a user wants to create a transfer request, it will need to provide the UTXO details such as UTXO’s unique ID (UID) and the index of the block in which the UTXO was created.

At any time in the future, a user can transfer its token from the child chain to the parent chain. This process is called the Exit process.  The exit process can be initiated by a token owner to the smart contract on the parent chain. The exit process consumes the given token from the child chain and molds it into the equivalent amount to the parent chain.

 

 

The operator performed all safety validations on the child chain side, and the Plasma smart contract handles all the security checks on the parent chain side. The operator keeps all UTXO states; therefore all double-spent and invalid state transition attempts can be rejected. Figure (3) shows the legitimate operator case. Assuming the operator is behaving according to the predefined rules, there will be no case of block withholding scenario so that the only way of either stealing money from the child chain is invalid Exit request on the Plasma Smart contract. The Plasma smart contract enforces the whole exit process.

 

 

Figure (4) shows the invalid exit scenario and related activities on the child chain and the parent chain. Since the parent chain holds no transactional details of the plasma child chain, therefore, the smart contract will not be able to confirm or decline the upcoming exit requests. Plasma smart contract adds all upcoming exit requests to a waiting queue and either confirm or reject after a predefined waiting period.  This waiting period is described as the Exit Period. The exit request refers to a UTXO, and the UTXO describes a unique NFT token and the owner details. All exit requests referring to different NFT tokens are independent of others and can be processed in likewise order. However, exit requests referring to the same NFT token can cause stealing if they are processed in likewise order. The plasma smart contract evaluates all exit requests in priority order. The priority order is calculated using the exit request’s UTXO details. The exit request referring to UTXO with a lower block index will be executed with a higher priority. Therefore, the last valid token owner can always successfully transfer it to the parent chain.

In the case of the legitimate operator, there will be no invalid transfer possible in the child chain. As described earlier, the only possibility will be an invalid exit request on the parent chain. Any invalid exit request will only finalize after the exit period is over and if there is no valid challenge raised with Merkle proof against it. Merkle proof is the valid transfer history of the NFT token in the Plasma child chain, and it can be either calculated or retrieved. Therefore, valid owners must look at exit requests and need to raise the challenge so.

 

 

In the case of the malicious operator, the operator can accept double-spent and invalid state transitions and include these invalid transactions in the upcoming block. Figure (5) shows the malicious operator scenario. The operator can also withhold a block that symbolizes a block that is added to the child chain but available to users. Due to withholding the blocks, users are not able to decide how to react now. Since an invalid exit request referring to either double-spent or invalid state transition UTXO cannot be declined via any challenge with Merkle proof. When these situations occur, affected users will only have one option to create an exit request referring to the last valid UTXO. In the above-mentioned scenario, no invalid exit request can be executed as finalized if the owner is observing the token states.

This extra burden on users makes the child chain independent of the operator for security.

All security points are mathematically proven in the white paper by Joseph Poon & Vitalik Buterin.

Architecture

 

 

The figure (6) exhibits a simplified architectural overview for a side chain DApp.

Conclusion

If you are curious to see our work, check out the GitHub repository.

In the upcoming blog, I will cover the possible use-cases and DApp implementation of Plasma Cash.

Decentralized Applications – Utilizing the Power of Blockchain Technology

A decentralized application (dapp, Dapp, dApp or DApp) is a computer application that runs on a distributed computing system.

Dapps, by definition, are regular/web/mobile applications built on top of a p2p network with below characteristics

  • Completely Open Source – to gain the trust of potential users and increase transparency
  • No Central Point of Failure – Application data cryptographically stored across all the nodes.
  • Cryptographic Tokens (app currency)- the Dapps must use cryptographic tokens for application usage and incentivization.
  • Decentralized Consensus – to support a trustless environment; and a mechanism to achieve consensus.

In this series of blogs, I am going to describe the common architectural components that constitute a Dapp. A real-world use case will be presented where scarce resources are shared in a distributed and trustless environment with no central authority or intermediaries. Afterwards, I will be providing code snippets of the Dapp built on top of EOSIO blockchain framework using a simple React.js web app along with reference to the git-repo.

Architectural Components

At the very basic, a Dapp has two components. Frontend and Backend. The frontend is a regular web application created using HTML/CSS and other web technologies. However, instead of interacting with a centralized backend server, they interact with blockchain node using smart contract(s). The application data in Dapp is stored in a decentralized way and the wallet-based mechanism is used instead of login/password to store user information in a secure way. In most real-world applications, there is also a need for some backend module where non-transactional/non-critical data is stored and utilized by front-end.

Since a smart contract cannot interact with the outside world, a trusted (and most often decentralized) service is used to fetch live data such as stock price or weather update. These trusted services are called oracles.

Blockchain Node

A full blockchain node stores a full copy of blockchain transactions, current state and blockchain protocol implementation along with API endpoints for clients. This validator node (or minor in bitcoin terms) is responsible for validation of transactions and generation of blocks.

Smart Contract

A smart contract is a cryptographically secure code segment on blockchain executed by validator node when a client triggers some action on that contract. This action takes the blockchain from one valid state to another and requires some incentive for the validator to consume his resource for taking up this task.

Wallet

User management in blockchain is done in a decentralized and secure way using the concepts of public-private key cryptography. Users use their private keys to sign all the transactions and publish a public key for anyone to verify. This allows for password-less authentication across web services and the private key is never revealed to the server or third parties. This private key is never shared with anyone.

These keys are stored safely in a wallet on the user’s mobile or computer and used by the user application while sending transactions.

Techniques like hardware wallets and custodial wallets can be utilized for specific use cases.

Web/Mobile Application

The frontend is a regular HTML/CSS/Javascript application which uses client javascript libraries like web3.js (for ethereum) and EOS.js (for EOSIO) to connect to the blockchain server via JSON RPC protocol and utilize the wallet functionalities for transactions.

Data Storage

1 KB of storage (in form of contract code or data fields) costs 0.032 ETH on Ethereum. In EOS, a user needs to stake 0.053 EOS to access 1KB of memory.

As we can see, Blockchain is not suitable for storing application data as this data needs to be replicated across all network nodes. We need an alternative storage mechanism that is price efficient and follows the distributed systems philosophy of blockchain.

IPFS is designed to create the content-addressable, p2p method of storing and sharing file data. I used IPFS as a mechanism to store our application data such as available parking spaces and retrieve using the generated hash code.

Couple of caveats that we need to take care of:

  • At least one IPFS node should be up and have accepted to store my data.
  • If the data contents are changed, hash codes need to be updated in an application as the stored hash codes are not valid anymore. This can be resolved using IPNS

Communication

Most blockchain frameworks provide ways for one smart contract to execute the action on another contract. This is useful in scenarios where one transaction needs to be triggered by another or there are dependent transactions that need to be executed in sequence.

To communicate some blockchain event to a front-end app, there are different mechanisms provided which differ across blockchains. Most of them provide block-level event notification which can be used to either update the front-end or execute some backend job.

Conclusion

In this blog, we explored the architecture of a common Dapp. In the next part, we will continue with a real-world use case of the blockchain, ParkAssist – a distributed parking space sharing application.

GoSig BFT Consensus Protocol for Block chain Simplified

What is a BFT consensus protocol?

Any blockchain must organize the transactions in a linear order of the time of their execution, which may be different from their time of submission. Instead of trying to achieve consensus on individual transactions, it is more efficient to group them in blocks which are a finite ordered list of transactions. If a block is accepted as valid and a consensus has been achieved, that means the same thing as achieving a consensus on all of the included transactions in the mentioned order. Blocks are ordered in a sequence which is aptly named as a block-chain or simply blockchain. The chain has a beginning called the genesis block. Everyone starts off with the belief that the genesis block is valid.

The distance of any block from the genesis block in term of the number of blocks in-between is called the height of the block. The height of the genesis block can be set as zero. The height of the first block after that is one, and so on. The job of the blockchain protocol is to make sure that every honest party agrees on the block that is acceptable given any particular height.

In a BFT protocol, each participating party sends messages to other parties in a prescribed manner until they come to a conclusion about a certain candidate block. There is the requirement that once an honest party is able to decide a certain transaction to be valid and agreed upon, no other honest party would deny that. Each honest party confirms a consensus by making sure that a large majority of other parties (honest or dishonest) agree to the same block for that particular height. The consensus algorithm is run fresh for each height, one after another.

Each party needs to know the public key of the other parties to validate their signatures. Otherwise, one single dishonest party can send the P-messages on behalf of everyone to create a consensus of his choice.

Why use a BFT protocol?

Blockchain BFT protocols provide a better way of achieving block consensus than the proof of work used in Bitcoin.

A theorem from Fisher, Lynch and Paterson rules out any possibility of achieving a consensus with even one faulty process in a completely asynchronous setting. So, in order to have a consensus, we assume some form of weak synchrony. Weak synchrony implies that the processes have almost synchronized time and the network is connected for some time during which the messages are guaranteed to be delivered within a specified amount of time.

BFT protocols have the following advantages over proof of work algorithm used in Bitcoin –

  1. There are two properties that we need for consensus, safety and liveness.  Bitcoin guarantees liveness under any condition, but safety is guaranteed only when the network is connected. On the other hand, BFT provides safety under any condition and liveness when the network is connected.
  2. Proof of Work consumes a huge amount of computation resources. In contrast, BFT does not require such expensive computation.

The only drawback is that the chain must know all of the miner’s public keys. This can be resolved by doing a Proof of Stake algorithm along with the consensus. Currently out of the scope of this blog.

GoSig BFT protocol

GoSig is a BFT consensus protocol that provides security even in the public network.

In this blog, I will try to develop the protocol in steps to explain the concepts behind it.

As discussed in the previous section, the GoSig protocol must satisfy the 2 properties of consensus i.e Safety and Liveness.

  1. Safety: Whenever any honest user commits a block for a given height, no other honest user can commit a different block at the same height even when the attacker has full control of the network. This ensures that the commits are final and unchangeable. So once a transaction is included in a block committed by any honest user, he knows for sure that that transaction cannot be undone. Note that only the honest party himself can know that since any other party cannot know whether he is honest or not and a dishonest party can do anything including committing something for no good reason. The protocol needs to ensure this property even when the attacker has full control of the network and can create an arbitrary number of network partitions.
  2. Liveness: It should always be possible to commit a new block by all honest parties at the next height as long the network connection works, i.e. the attacker loses control of the network. Basically, this condition is about not getting into a deadlock. This is important for the chain to proceed. Of course, the parties cannot commit if the network does not forward their P messages, so this has to only work when the network is connected.

Step 1 – A first cut BFT algorithm:

We assume that 2 third users are honest. Every user is able to make a choice somehow or the other. There is a possibility of not all choices are visible to every honest user when the network is fragmented or due to delay in the network.

Based on the above assumptions, every honest user should automatically agree on a choice as long as the network is connected.

Let’s look at what happens when the network is broken. For every height, any honest party does the following.

  1. The honest party selects one from the possible choices for the next block and chooses one of them by some deterministic means.
  2. The honest party then broadcasts a signed P message for his chosen block and waits for the others to broadcast theirs.

When the honest user receives 2f+1 votes from other parties for any particular choice for the block, he commits this block as the chosen one.

Let us see if the above algorithm satisfies the ‘safety’ property. If any block receives 2f+1 P messages, at least f+1 of them must be from honest parties, because the maximum number of dishonest parties are the only f. These honest parties will never send P message for a different block. So the maximum number of P messages that can be produced for any other block must be (3f+1) – (f+1) = 2f which is not sufficient for a commit. So, if some block is committed for a certain height by an honest party, no other block can be committed by any honest party. So the first condition is satisfied. This is great!

However, it might happen that the honest parties accidentally chose more than one different candidates for the next block. For example f honest users may P message candidate_1 and f+1 users may end up P messaging candidate_2.  The attacker simply does not do anything and enjoys what’s going on the system. In this case, no choice of the block has sufficient P messages for commit, so the system is stuck. The second property of liveness has been violated even when the network is connected.

Step 2 – Network Deadlock

We need some way to get out of the above deadlock situation. The obvious idea is of course to restart the whole protocol over whenever there is such kind of a deadlock. The problem with this is its impossible to know when a deadlock has happened from just incoming P-messages.

Suppose we conclude that a deadlock has happened after receiving some s P-messages from different parties and the party still fails to commit.  Now, let’s say in some case f honest users may P message candidate_1 and f+1 users may end up P messaging candidate_2. This is obviously a deadlock and hence these 2f+1 messages must be able to detect it and hence s ≤ 2f+1.

Suppose, now in a different situation 2f (group A) honest users have P-messaged candidate_1 and 1 (group B) honest user did not P-message anything yet (because he is yet to receive the possible candidates). Now, the attacker can send a P-message candidate_2 to group A which would convince the group A to abort (it has 2f+1 P-messages and still cannot commit, and s ≤ 2f+1). After group A aborts this and restarts the protocol, suppose they all decide candidate_2 (maybe because they have come to know of candidate_2 now). So group A now has 2f P-messages for candidate_2. The attacker now provides 1 P-message for candidate_2 so that group A can now commit candidate_2.

Notice that all this time, group B has not been able to either abort or commit any block. So, now the attacker can replay the recording of the first round for group A (showing evidence of 2f P-messages from group A for candidate_1 from his saved messages collected from the round) and adds his own 1 P-message for candidate_1. This provides 2f+1 messages for candidate_1 to group B and hence group B commits candidate_1. In effect, group A committed candiate_2 and group B committed candidate_1 for the same height. This breaks our condition 1.

The easiest solution to this problem is to timeout around after some reasonable time if a commit cannot be achieved before that. As long as the clocks of each processor are more or less same, this should make sure everyone is in the same retry round. This assumption is a synchrony assumption called partial synchrony. We will go into more details about it later. For the time being, let us just assume that all nodes maintain the exact same time and message propagation time is zero for any message.

The next proposed solution is very simple.

  1. The honest party selects one from the possible choices for the next block and chooses one of them by some deterministic means.
  2. The honest party then broadcasts a signed P message for his chosen block and waits for the others to broadcast theirs.
  3. When the honest party receives 2f+1 P-votes from other parties for any particular choice for the block, he commits this block as the chosen one.
  4. When an honest party has passed a fixed amount of round time (say R), he forgets everything and restarts the process from step 1.

It solves our liveness problem, but the safety property is broken now. Suppose 2f+1 parties send P-messages for candidate_1. The messages reach only 1 honest party who commits candiate_1. The rest of the user waits until R time has passed and restarts the process where they can easily commit candidate_2 with one P-message from the attacker.

Step 3 – Adding tentative commit of TC messages:

To avoid both of the problems, we need to put one extra step of messages that we would call the tentative commit or TC messages. The idea is to separate P-messaging for a different block in the new round and actually committing a block in the previous round. Sometimes a user needs to observe the new round while he still did not decide anything for his current choice for the candidate block. Every honest user does the following in every round.

  1. The honest party selects one from the possible choices for the next block and chooses one of them by some deterministic means. If he has TC-ed a block in any previous round, he must P the same block again if that is one of the candidates, otherwise, he does not P anything.
  2. The honest party then broadcasts a signed P message for his chosen block and waits for the others to broadcast theirs.
  3. When the honest party receives 2f+1 P-votes from other parties for any particular choice for the block, he sends a TC message that contains a proof of all the P-messages. Basically, he copies all the signatures contained in each of the P-messages for the same candidate block. This is to ensure that a dishonest user cannot create a TC message without first receiving 2f+1 P messages for the same candidate. After this, he would send no more P messages for the higher round for a different block (but will do it if he sees the same block suggested by the leader).
  4. Whenever a user sees any TC message in a round, he immediately TC-messages the same block. This is easy, he simply copies the proof of P-messages and signs it.
  5. Whenever a user finds 2f+1 TC messages for the same block for the current round and the current height, he commits it.
  6. When an honest party has passed a fixed amount of round time (say R), he forgets everything and restarts the process from step 1. If the user has TC-ed a block in this round, he must keep proposing and P-voting the same block in later rounds until he TC-ed for a different block in a later round.

This was much more complicated than the previous one. This is mostly because it has a new step and lots of nuances. Let’s see how this satisfies the safety and the liveness properties.

Safety property: We need to prove that if any honest party commits a block, there would be no more commits at the same height. This ensures that there is only one possible commit for any height.

When an honest party commits a block, he must have observed 2f+1 TC messages for the same block. Since the attacker can only send f of them, f+1 TC messages must have come from honest users. These honest users will never P-vote for the same height for a different block. So, any further rounds can only have a maximum of 2f P-votes for any other block which would not even be sufficient for a TC message. Without any TC message for any other block, no honest user will commit any other block at any further round, proving our case. Two different commits cannot, of course, happen at the same block because of the fact that it is not possible to make TC message for two different candidates at the same height. If basically proves that even though honest parties can commit a block for the same height in different rounds, they would always commit the same block.

Liveness property: We need to make sure that no matter what happens in the network and message order and whatever the messages sent by the attacker, when the network recovers, all honest users will commit some block. We break it into the following cases.

  1. If no TC-messages are sent in any round before it is over, there is no change in the system. The whole process just restarts. This won’t go on forever as in every round there is a probability of this not happening.
  2. If there are some TC-messages created, 2f+1 P-messages must be present in this round supporting the same candidate, because the proof of 2f+1 P-messages is contained in the TC message. f+1 of them must be sent by honest parties. Hence the maximum number of P-votes for a different candidate in the same round is 2f which is not enough to create a TC-message. So, if a round has one TC message, it does not have any other supporting a different candidate. This means the TC messages in the same round always support the same candidate. This makes it okay to forward a TC-message whenever an honest party sees it.
  3. If the TC-ed users are honest, he would eventually be promoted to the leader when the network is connected, at which point he would P-message the same block and everyone will agree.
  4. Since an honest user always signs a TC-message that he sees in around, when the network is connected, every honest user will see such message and will send TC-message supporting the same block. Since there are at least 2f+1 honest parties and there is only one candidate that can get TC-messages, this candidate will get 2f+1 TC-messages when the network is connected.

Now that we have a way to achieve consensus, I would delve into how block proposals are created by any party.

Creating the block proposals:

Given that blocks can be proposed by anyone, we need to handle the following situations

  1. If the attacker is allowed to create lots of block at any point in time, the attacker will keep creating too many blocks to simply burden the system with too much processing. Such an attack is called a denial of service attack.
  2. If the attacker can create too many blocks in a round to consider, it would become improbable for all honest users to agree on which one to P-message, thus making the system go on forever without committing anything.

To tackle the first problem, we allow one party to suggest only one candidate per round, and that too only after a commit happened for a previous height. So, to suggest a candidate, any user has to first prove that there was a commit that happened in the previous round. Since a candidate will eventually but definitely get committed after 2f+1 TC-messages for the same has been broadcasted, we require that those TC-messages be presented while suggesting a new block for the next height. So, any valid new candidate suggestion for the height h must contain 2f+1 TC-messages.

To tackle the second problem, a small set of leaders are selected at random. This ensures that less number of blocks are proposed, thereby increasing the probability of commit. The random selection must be publicly verifiable to be random, otherwise, the attacker will simply choose random numbers that favour him and simply claim that he got those numbers randomly.

One way to get a publicly verifiable random number for any party would be to simply concatenate current height, current round and the party’s public key and take the hash of it. Since cryptographic hashes have uniform random distribution, this makes a good source of the random number. We say a party has been selected as a leader if his random number for the round is less than a certain value which is chosen based on the fraction of parties to be chosen as leaders per round on average. If the maximum value of a hash is N and the fraction of parties chosen as a leader be x, then the condition for selection would be H<x/N, where H is the random number for the given party (H=Hash(height||round||publickey)).

Although the above idea works, Jing Chen et. al., the creators of the Algorand algorithm had a better idea. They used a technique called a verifiable random number that has all the properties of what we had suggested, and it cannot be known to any other party before the owner of the private key discloses it. Instead of taking the hash of the concatenation of the height, round and public key, they start with the hash of the concatenation of height and round. They then use a unique signature algorithm to sign this hash using the party’s private key. A unique signature has no random element and there is only one valid signature for a single message. RSA is one such signature algorithm. Another is quite a new one called the BLS signature. They then sign the hash using the party’s private key. The random number H=Hash(S) where S=Signpry(Hash(height||round)) . The signature S is included with the random number as a proof so that it is publicly verifiable that the hash is correctly generated and the generator has no way to control it. Since the signature can only be generated by the owner of the private key, other parties cannot know about it until he discloses it.

The leader must include the signature as part of his candidate suggestion. This makes sure that the leader cannot be identified before he already made the suggestion. That way, he cannot be corrupted by the attacker beforehand.

To increase the likelihood of every honest user P-messaging the same candidate, we need to find a deterministic way to choose between multiple candidates. A simple rule can be that we choose the one with the minimum value of the verifiable random number in the first suggestion.

Now that we have a working BFT algorithm, I would like to dive into the details of network delay and clock delay.

Handling delays and timing tolerance:

Let T be the maximum difference between any two parties, S be the maximum network delay for receiving a message when the network is connected, R is the time for each round, M be the maximum processing time for each round. We consider the following under full network connectivity.

  1. When a round starts, the honest leaders wait for T time so that everyone is in the same round.
  2. After this, they broadcast their candidates by P-messaging them.
  3. It takes S time for everyone to get this message.
  4. Everyone then P-messages the correct choice.
  5. It takes S time for everyone to receive all P-messages.
  6. Everyone then TC-messages the block.
  7. It takes S time for everyone to receive the TC-messages and commit it.
  8. Let the maximum amount of time taken for processing be M

So in total, R must be greater than T+3S+M. This will always ensure a commit under full network connectivity while allowing the system to work fast.

Summary:

The correct protocol I have described here is the Gosig protocol proposed in the paper https://arxiv.org/pdf/1802.01315.pdf by Li, Wang and Chen (I changed a few little details, but they don’t matter). We went step by step into developing a working BFT protocol that can be used in a blockchain. There are quite a few others with somewhat different approaches, we do not cover them here.

Why BFT protocols cannot have 1/3 dishonest parties

Introduction:

Any blockchain must organize the transactions in a linear order of the time of their execution, which may be different from their time of submission. Instead of trying to achieve consensus on individual transactions, it is more efficient to group them in blocks which are a finite ordered list of transactions. If a block is accepted as valid and a consensus has been achieved, that means the same thing as achieving a consensus on all of the included transactions in the mentioned order. Blocks are ordered in a sequence which is aptly named as a block-chain or simply blockchain. The chain has a beginning called the genesis block. Everyone starts off with the belief that the genesis block is valid.

The distance of any block from the genesis block in term of the number of blocks in-between is called the height of the block. The height of the genesis block can be set as zero. The height of the first block after that is one, and so on. The job of the blockchain protocol is to make sure that every honest party agrees on the block that is acceptable given any particular height.

At the heart of any blockchain, is a system that needs to agree on the system state. When multiple actors with equal privilege need to maintain a set of records, they must agree on whether some record is part of such database. This is very straightforward in a perfectly connected system with only honest parties, but it gets complicated with unreliable network and dishonest parties trying to gain from the insecurities of the system. More specifically, since honest parties cannot guarantee communication with the other honest parties and neither can they tell between honest and dishonest parties, a trivial protocol will let a dishonest party convince two different honest parties two different states of the system that cannot be true together. For example, an attacker in Bitcoin may try to make an honest party believe that he paid 1 BTC to A and make another honest party believe that he paid 1 BTC to B, where he only had 1 BTC to begin with. Such a system would allow the dishonest party to receive services from both A and B each worth 1 BTC by spending only 1 BTC altogether. In blockchain terms, such a transaction is called a double spend and a blockchain would always intend to stop such attacks. Getting multiple honest parties to agree on the correct state of the system while some dishonest parties are present is called a consensus algorithm. We will look closely into a particular kind of consensus protocol.

Bitcoin and Ethereum achieve consensus by something called a proof of work. Basically, any party can declare himself to be a leader deciding which one of the several possible correct sets of transactions is valid by solving a cryptographic puzzle ensuring some processing has been done by such party. Since there is a large reward for such a party successfully being selected as the leader, it creates a competitive environment where several parties compete to be chosen as a leader. However, since a leader is not allowed to pack conflicting/invalid transactions in the block (a block is an ordered list of valid transactions proposed by the leader), this creates only one valid chain of transactions. However, this allows some temporary disagreement between different honest parties (also known as a temporary fork), which get resolved as time goes on. It is not difficult to come by resources explaining PoW based blockchain, the reader can simply read such articles to know more unless he is already familiar with such concepts. In this blog, we dive deep into a different kind of consensus algorithm – byzantine fault tolerance or BFT.

BFT Consensus

In a BFT or a Byzantine Fault Tolerant consensus protocol, each participating party sends messages to other parties in a prescribed manner until they come to a conclusion about a certain candidate block. There is the requirement that once an honest party is able to decide a certain transaction to be valid and agreed upon, no other honest party would deny that. Each honest party confirms a consensus by making sure that a large majority of other parties (honest or dishonest) agrees to the same block for that particular height. The consensus algorithm is run fresh for each height, one after another.

The basic idea is as follows –

For every height –

  1. Some parties create a candidate block by compiling an ordered list of transactions. How they choose such transactions and which parties are allowed to make suggestions would be discussed later.
  2. After an honest party receives a set of candidate blocks, he chooses one of them – (by some mechanism that would that would not be discussed in this blog). He then lets others know about his choices by sending a signed message. We will call such a message as a P-message.
  3. When an honest party receives a certain number of P-messages from other parties for a particular block (among all the choices), he goes on to say that he has achieved consensus on that particular choice of a block for the current height by what is called as committing the block.
  4. The protocol is then repeated for the next height.

Note that each party needs to know the public key of the other parties to validate their signatures. Otherwise, one single dishonest party can send the P-messages on behalf of everyone to create a consensus of his choice.

The system cannot of course work with an arbitrary number of dishonest parties, there must be a limit for the maximum number of dishonest parties the system can be protected against. In the following section, we will discuss this limit.

Maximum number of dishonest users for achieving consensus

Before we get to limits, we need to state the conditions the protocol needs to satisfy:

  1. Safety: Whenever any honest user commits a block for a given height, no other honest user can commit a different block at the same height even when the attacker has full control of the network. This ensures that the commits are final and unchangeable. So once a transaction is included in a block committed by any honest user, he knows for sure that that transaction cannot be undone. Note that only the honest party himself can know that since any other party cannot know whether he is honest or not and a dishonest party can do anything including committing something for no good reason. The protocol needs to ensure this property even when the attacker has full control of the network and can create an arbitrary number of network partitions.
  2. Liveness: It should always be possible to commit a new block by all honest parties at the next height as long the network connection works, i.e. the attacker loses control of the network. Basically, this condition is about not getting into a deadlock. This is important for the chain to proceed. Of course, the parties cannot commit if the network does not forward their P messages, so this has to only work when the network is connected.

That being said, we try to figure out the maximum number of dishonest user any system can support to achieve consensus. Let us assume that any honest user needs to see P messages for the same block for the given height from a t fraction of the total number of parties. That is if there are a total of N parties, the honest users would look for more than t/N P messages supporting the same block before they commit the block. Let us also assume that z is the maximum fraction of dishonest parties that the protocol can support.

We first see what is required to achieve condition 1. We already assumed that the attacker has full control of the network. We also assume that the dishonest parties make a coalition among themselves to form a combined attacker. The aim of the attacker is to make two different honest users commit two different blocks. The attacker partitions the network into three groups. One containing x/N honest users (we will call this partition A), one containing the rest of the honest users (partition B) and the last partition containing all the dishonest parties (partition C). This means the fraction of parties in partition B is (1-x-z). Note that the attacker can control the network and all delivery of messages, but cannot create a P message on behalf of an honest user. Now the attacker tries to make both of those partitions commit different blocks for the same height.

Since the attacker can have z fraction of P messages for both blocks, the total fraction of P messages the attacker can achieve for a block in partition A is x+z. Similarly, the total fraction of P messages the attacker can create in partition B is z+(1-x-z) = 1-x. Since any BFT protocol needs to make sure that conflicting blocks cannot be committed, at least one of them must be less than or equal to t.

Since the attacker can choose any value for x, it must be so that for any value of x either  x+z ≤ t  or 1-x ≤ t.

The reader can now note that the logical condition (A or B) to be true means either A has to be true or B has to be true. This means if A is false, then B must be true. This is the same thing as (not A) ⟹ B.

So, for all x, (x+z ≤ t  or 1-x ≤ t) is the same thing as saying for all x, x+z > t ⟹ 1-x ≤ t.

This can be simplified as  x+z > t ⟹ x+z ≥ 1-t+z  (1) .

When stated this way we can see that this condition would be met if t ≥ 1-t+z or 2t -1≥ z or z ≤ 2t-1 (2).

That would get what we want. But we have to prove that this condition is really necessary.

Suppose it is not true that z ≤ 2t-1; so, it must be true that z> 2t-1.

We will create a condition where x+z > t but x+z < 1-t+z  thus violating (1). The minimum possible value for x+z is of course z and maximum is 1. The attacker can choose any value for x such that x+z is in that range. Suppose,  m = max(z, t)  and the attacker chooses x = (m + 1-t+z)/2 -z so that x + z = (m + 1-t+z)/2 .

We have assumed that z > 2t-1 , so 1-2t + z > 0 or 1-t+z > t > 0 (3) . Hence, since m   =  max(z, t), x + z = (m + 1-t+z)/2 > z. This means such an x is admissible.

Also, 1-t+z > t (according to 3)  and since t<1  (as it a fraction), 1-t+z > z (4). (3) and (4)  together implies  1-t+z > max(z, t) =m or  m < 1-t+z  (5). Hence, x + z = (m + 1-t+z)/2 < ((1-t+z) + 1-t+z)/2 = 1-t+z.

Basically, since x + z  is the mean of  1-t+z  and m,  and since 1-t+z > m, it must be that m < x+z < 1-t+z . Observe that m=max(z,t) we have t  ≤  m < x+z < 1-t+z  which achieves the contradiction. Hence, we have proved that it has to be the case that z ≤ 2t-1 according to  (2).

Now, let us consider condition 2. It simply says that when the network is connected, the commit must be possible. So, the fraction of honest parties must be able to cause a commit. This means (x+(1-z-x)) = 1-z > t  or z < 1-t . The following diagram shows the allowable values for z.

The fraction of dishonest user is marked in green. The maximum possible value for z  is of course just below the intersection of the lines z = 1-t and z = 2t-1. We say ‘just below’ and not on the intersection because z < 1-t and so z cannot be on this line. If the intersection is at t=t0, we have 1-t0 = 2t0 -1 or 3t0 = 2 or t0 = ⅔ . Hence, z < 1-t0  = 1-⅔ = ⅓ . Hence the maximum fraction of dishonest users have to be less than ⅓ and that would be achieved when t= ⅔. So if there are f dishonest parties in the system, there must be at least 2f+1 honest parties, so that the total number of parties is 3f+1 which makes the number of dishonest parties strictly less

than the ⅓ fraction of the total number of parties. This also means the threshold here is floor(⅔(3f+1)) which is 2f+1 We will count the users in terms of  f from now on.

Summary: The red line in the above graph is the safety line. The z  below that can maintain the safety of the chain. The blue line is the liveness line. The z  below that can maintain liveness of the chain. Since both must be maintained, only the green area is allowed for the value of z. The maximum value of z  is, of course, the apex which is reached when z = ⅓. In fact, z must be less than for reasons described earlier.

EOS Demux using PostgreSQL

I have been looking for EOS demux implementation using PostgreSQL but found none. So I thought of writing this short tutorial explaining how we can implement EOS demux using PostgreSQL. Those who don’t know about EOS Demux please have a look at the article explaining the same in a very intuitive way.  https://github.com/EOSIO/demux-js.

 

A short explanation of EOS Demux: Demux architecture allows application developers to use traditional Mongo or Postgres SQL databases in a way that means the data stored in them is still verifiable by the blockchain. This enables the best of both worlds: the flexibility and speed of traditional databases, coupled with the trust and immutable properties of a blockchain. The overall flow of an application looks as follows:

 

To use PostgreSQL as a data store we need to use massive.js. So go ahead and install massive.js using the following command

> npm i massive --save
To demonstrate the working of PostgreSQL based demux implementation we are going to use a very basic contract. The contract is about a blog, using which user can do CRUD operation on the blog. As blog data is big we are going to store the blog data into PostgreSQL and metadata related to the blog like user, email etc. will be a part of the blockchain. Blockchain maintains all the information which
are required to make blog entry verifiable and secure. Following is the contract.
#include <eosiolib/eosio.hpp>

#include <eosiolib/multi_index.hpp>

#include <eosiolib/types.hpp>

#include <eosiolib/print.hpp>

#include <eosiolib/system.h>

//using namespace eosio;


class blog_contract : public eosio::contract{

    public:


    blog_contract(account_name self) : eosio::contract(self),

          bloges(self, self){}


        /// @abi action

        void create(account_name author, uint64_t id, std::string email, const std::string& data){

            require_auth(author);

            blogs.emplace(author, [&](auto& new_blog) {

                new_blog.id = id;

                new_blog.author = author;

            });

        }

        //.. destroy, show and update actions .. 


    private :

        /// @abi table blog i64

        struct blog{

            uint64_t id;

            uint64_t author;

            uint64_t primary_key() const {

                return id;

            }

            EOSLIB_SERIALIZE(blog,(id)(author));

        };

        typedef eosio::multi_index<N(blog), blog> blog_table;

        blog_table blogs;

};


EOSIO_ABI( blog_contract, (create)(destroy)(show)(update) )
If you look closely at ‘create’ function of the contract, you would notice that the function’s signature contains blog data as one of the parameters but we are not storing the blog data as part of EOS’ database. The purpose of having blog data as part of the function signature is that it gets available to be stored in PostgreSQL. Whatever we mentioned as function parameters, those parameter’s data will be available to the action handler. Looking at the diagram ‘Action watcher’ keeps looking for any change in blockchain via ‘Action Reader’. Whenever there is any action happened in the Blockchain, Action watcher delegate that action to ‘Action Handler’. Then ‘Action Handler’ further calls ‘updaters’ and ‘effects’ which actually execute necessary action code. Based upon the discussion the configuration looks as follows:
//First get the postgreSQL instance via massive as follows:
const massive = require('massive');

let db;

massive({
 host: host,
 port: port,
 database: database, 
 user: user,
 password: password 
}).then(instance => {
 db = instance;
 return Promise.resolve(db);
}).catch(e => {
 console.log(e)
 console.log('error while getting massive instance')
 });
Let’s define Updaters and Effects
//Updaters
function createBlog(db, payload, blockInfo, context){
 db.blog_data.insert({
 id : payload.data.id,
 author : payload.data.author,
 data : payload.data.data, //Storing blog data
 email : payload.data.email
 }).then(new_blog => {
 console.log('blog created')
 }).catch(err => {
 console.log('error while inserting data')
 })
}

//Register blockchain Actions to which this update will be called.

const updaters = [{
 actionType: "blogger.p::create",
 updater: createProfile}
]

module.exports = updaters
//Effects
function logUpdate(state, payload, blockInfo, context) {
 console.info(“blog created\n")
}
const effects = [
{
 actionType: "blogger.p::create",
 effect: logUpdate,
}
]

module.exports = effects
Now create MassiveActionHandler, Action Reader, and Action Watcher as follows:
const {
 readers: {
 eos: { NodeosActionReader }
 },
 handlers :{
 postgres : { MassiveActionHandler }
 },
 watchers: { BaseActionWatcher }
 } = require('demux-js')

const actionHandler = new MassiveActionHandler(
 updaters,
 effects,
 db
)

const actionReader = new NodeosActionReader(
 httpEndpoint,
 0, // Start at most recent blocks
)


const actionWatcher = new BaseActionWatcher(
 actionReader,
 actionHandler,
500,
)
actionWatcher.watch()
You also need to make sure the following table exists in PostgreSQL, which keeps track of block number up to which action has already been taken.
CREATE TABLE _index_state (
 id serial PRIMARY KEY,
 block_number integer NOT NULL,
 block_hash text NOT NULL,
 is_replay boolean NOT NULL
);