Fluence co-founder: how to secure a distributed database

Before personal computers, computing resources were provided by a number of terminals. These terminals don't need much hardware, as long as they can connect to the host, just like the light clients in the blockchain

When the hardware became cheap enough, computing resources began to shift to the client -- media, games, office packages, science toolkits -- all running on the desktop. Today, most computing has moved to the cloud. By connecting to the cloud, the browser now plays a similar role to the terminal of the past, a pattern that could well be extended to billions of users.

A large number of computers in multiple data centers make up the cloud, connected to a high-throughput network, ready to provide computing resources and service requests. This is called IaaS - infrastructure as a service. The cloud provider is responsible for monitoring and repairing this infrastructure so that developers can focus on developing software.

Cloud computing is more than just infrastructure. Most importantly, the cloud provider deploys intermediate services: databases, message queues, lambda functions, data processing engines. Although these services do not interact directly with the end user, they form an important part of the software architecture, often referred to as PaaS - platform as a service.

In general, the middle service of the cloud is actually an existing open source package contained within the managed service. For example, AWS providesRDSMySQL and postgresql as popular databases; Managed version,MSKAct as a message queue. Managed version, as wellElastiCacheAs a managed version of Redis and Memcached.

If there are so many different open source libraries and frameworks, why are developers using hosted cloud services? Because it's much easier to use them than to do all the manual DevOps required. The cloud provider is responsible for configuring the hardware, scheduling backups and replicates, connecting to monitoring and alert systems, and restoring services in the event of problems. In addition, managed services integrate perfectly with each other and allow users to easily and quickly build new applications.

However, this convenience comes at the cost of locking developers in with the cloud provider. The more cloud services developers use, the more vulnerable they become to various cloud providers.

The Web 3 protocol reduces reliance on middlemen, is not too complex, and gives developers the same intuitive and simple experience as traditional cloud providers. In this case, the hosting service is a separate protocol. For example, object storage services like AWS S3 can be replaced by Filecoin, Swarm, or Arweave, key management service AWS KMS by NuCypher, and media streaming service AWS Elemental MediaConnect by LivePeer.

So what might a distributed cloud service look like?

Distributed cloud dream

A distributed cloud runs on a network of untrusted nodes, where the software is completely decoupled from the underlying hardware and anyone with the resources can run the hardware. Open source packages like Redis, MySQL, Kafka, or Spark can be ported to the distributed cloud, providing services just like the traditional cloud.

There is no need to re-implement the hundreds of open source tools and libraries created earlier - they can only run on a fragmented infrastructure. Because these services will run on an open network, they will be able to integrate seamlessly with each other.

Finally, run-time problems will be monitored and fixed by more community developers than private cloud deployments. The open source community will be able to collaborate and not only write code, but also run code.

Why hasn't this idea become a reality? To answer this question, we need to consider what constitutes the cloud on a fundamental basis. While the cloud may consist of a number of different services and protocols, you can only find a few key components on top of it: computing, data storage, and networking.

Decentralized data storage seems to be a near-solved problem: Filecoin, Swarm, and Arweave guarantee data availability and durability, and potentially cheaper and more powerful than traditional cloud storage.

Computational decentralization is much more difficult, but there are several different ways to run any Turing complete program:

Fat client (also known as full node) : the client has all the data needed to run the program and perform the calculation locally, effectively making the client full node. The data itself can be downloaded from a decentralized store or found from other network nodes.

Although simple, this approach is not always appropriate for the current model, with the server carrying most of the workload and limited network throughput between the client and server.

Zero-knowledge proof: the full node can execute the program locally and then provide the client with proof that the calculation is executed correctly. Ideally, the client should spend few resources validating the evidence provided, and the overhead of preparing such evidence across the node side should be negligible.

Unfortunately, at present, computing zero-knowledge proofs may require orders of magnitude more resources than performing the calculations themselves. Therefore, it is difficult to use this method for large-scale calculations.

Thin client + merckle proof: for any cursor-based data structure, you can build merckle proof to retrieve some of its stored data. The client may download only the pieces of data it is interested in from the dispersed network, verify that the retrieval is correct, perform the calculation, and send the results back to the network. Thus, bandwidth consumption is kept low and client resources are used carefully.

For example, this is a method used by OrbitDB - a serverless database for storing data in IPFS and using CRDT for synchronization between different clients & NBSP; OrbitDB allows developers to use fairly complex data structures: in addition to key-value storage, it supports variable and immutable logging, counters, and even search capabilities. 

However, for many use cases, this approach is not possible. For example, to handle temporary aggregate queries or join operations, the client essentially needs to be a full node, because such query types typically require reading a large number of rows from one or more tables, which need to be transferred to the client.

Thin client + blockchain: finally, the computation can be run in the blockchain, where multiple nodes run the same program and verify each other. The more nodes run the same calculation, the more secure the system will be. This is because most nodes are less likely to do evil as the number of nodes increases.

In ethereum, the number of nodes can run into the thousands, making ethereum a very secure but less cost-effective system than the cloud. Blockchain sharding can significantly reduce the number of nodes needed to run the same computation, but is this reduction sufficient to meet the efficiencies of cloud-level costs?

We should also note that in the thin client + merkel proof method (and the fat client method), the parties willing to use the result of the calculation need to trust the party performing the calculation. Essentially, the calculation came from an oracle: merckle proved unable to stop a malicious client that had downloaded 5 in one block, downloaded 3 in another, and sent 6 back to the scatter store as a sum. This means that only a zero-knowledge proof and a thin-client + blockchain approach can provide sufficient composability in a trust-free environment.

Distributed database gap

Let's get back to reality and consider a special but very useful cloud middleware - managed database services. In addition to being a great model that combines computing and storage, databases are one of the most common cloud services - almost every program USES SQL or NoSQL databases.

It's worth noting that we haven't seen a decentralized version of AWS RDS (hosted MySQL and PostgreSQL) or AWS Elasticache (hosted Redis and Memcached).

Why is that? The reason is that databases are more than just storage; & have spent They're also about computing. In addition to the aggregate query and join operations already mentioned in this article, the database can also run stored procedures and user scripts, perform bulk data updates, and apply built-in and user-defined functions.

Coupled with the need to quickly process requests and store large amounts of data, porting open source databases to a decentralized environment can be challenging. The sharding approach seems to be the most practical, but before we finally get down to it, let's examine how much redundancy cloud databases typically have.

Redundancy in a cloud environment

First, cloud databases typically use multiple copies for high availability and, in some cases, increased read throughput. Typically, one of these copies is specified as the primary copy and provides all read and write requests, while the other copies are used as the standby database: if the primary copy fails, one of the standby databases replaces it. In addition, although the standby databases do not provide write requests, they can still respond to read-only queries, allowing them to parallelize some of the load.

Which replicators are commonly used? It depends on the type of workload, but for AWS RDS 2× replication (one primary copy and one standby copy) is typically used for online transaction processing and may increase the mix of transaction processing and analysis queries. Deployment of Cassandra (a popular distributed NoSQL database) can provide three times the replication of mission-critical data for standard and five-fold replication. In general, it seems that 2-by-5 redundancy is common.

Second, in addition to database replication, backups are often used. In this case, a snapshot of the database state is periodically taken and uploaded to an external storage service, such as AWS S3. If a snapshot is taken every day, the external storage may retain the snapshot value of the previous week.

We should also note here that external storage is also likely to have some redundancy. While there is no exact figure for the number of copies of each storage object that AWS S3 has, based on its 99.99999999999% persistence guarantee, we can assume that there are usually at least three different devices that should retain the same data.

If replication is already in place, why back up? One of the most critical reasons is that backups allow you to restore the state of the database at a specific point in time. This can be useful, for example, if someone accidentally issues the DROP TABLE command and then repeats it among all copies of the TABLE that are in possession. With the help of a separate undo log, such a command cannot be easily rolled back - but using the latest snapshot can restore at least some of the stored data.

In summary, we assume that the cloud database requires two to five times as much redundancy as the primary/standby replica plus some external storage of 3× replicated database snapshots. Can we repeat this with a fragmented blockchain? For the sake of simplicity, let's forget about cross-sharding transactions for a moment - many Web applications use only one database instance.

Categorize your budget

Let's say we've budgeted for only five to ten times as much redundancy. Can we do this by rolling out only seven Byzantine consensus based validators, each with a copy of the database? Unfortunately, it's not that simple - sharding like this is not very safe.

Isolated debris secure

Assume that a small number of p nodes in the network are malicious. Many Byzantine consensus engines (such as Tendermint) can tolerate k malicious nodes in a slice consisting of n = 3k + 1 nodes. Conversely, it can be argued that if n-k (that is, 2n / 3) or more nodes in the shard are malicious, they can take over the shard completely and "tolerate" honest nodes. Assuming that nodes in sharding are randomly sampled from the network, the probability of sharding takeover is:

For a model sharding with seven nodes, only five malicious nodes are needed to catch it. Let's assume that the percentage of malicious nodes in the network is 10%. By substituting these values into the formula above, we get a splitter takeover probability of approximately 0.017%. Even for AD hoc applications without stringent security requirements, this may be too high.

How can we prevent this? In some design, if honest node with a two-thirds majority in the shard, they can cut down those who signed the node error state transition of deposits. But in our case, the malicious nodes can perform any state transition they want without having to talk to the honest node.

In addition, due to the malicious nodes are closely connected, only when they represent a two-thirds majority of the fragments, they can coordinate and misconduct - basically, when malicious nodes without any risky behavior. This means that without some external oversight, the thin client may never know that the shard is dishonest.

Protect fragmentation with a Shared validator pool

To protect sharding, whether they have only a few nodes or a few hundred, two techniques are commonly used: validator rotation and fisherman nodes. In essence, these techniques are very similar: a node in the network verifies that sharding only performs the correct state transitions. If the validation node finds an incorrect state transition, it can challenge the situation. In this case, if the validation node can prove that the status update is incorrect, the node that approved the wrong conversion loses its savings.

One option is to verify that the node replaces another node in the shard (in this case, we say that the validator set has been rotated) and replay the last few transactions that the shard did. Another option for validating the node is to remain independent, with the fish incorrectly transitioning between states in the hope of being rewarded differently. Either way, the idea remains the same: sharding is protected not only by the nodes that belong to it but by the entire network.

Sounds good, right? But how do you transfer sharding transaction history to a newly added verifier node or fisherman? One problem is that if the number of nodes in a shard is small, history and state transfers can place an excessive load on the shard, impeding its ability to process transactions in real time. Another problem is that malicious nodes in the captured shard may refuse to share incriminating evidence altogether.

The salvation of decentralized storage

One solution is to store the shard's transaction history externally. Consider the following: whenever a block is processed by sharding, it can upload the block to a decentralized storage network and provide interested customers with proof that the block has indeed been uploaded and correctly uploaded. After uploading the block, the decentralized storage network is responsible for providing the stored data on request. Check out this Swarm article for more information on how the protocol performs this responsibility.

Now, fishermen can download different pieces of transaction history from a decentralized store, double count, and challenge incorrect state transitions. As a side effect, the fishermen calculate the new state, which they can then upload as a snapshot to a decentralized store. This snapshot can then be used as a starting point for further validation or as a backup if the entire shard fails.

Validator rotation can be implemented in a similar way: the new validator will download the required parts of the state and transaction history from the decentralized store without overloading the sharding. In addition, even if the entire sharding fails, you can restore it using data from the scattered storage as a backup.

Note that because the fisherman in this design is disconnected from the debris, the fisherman can be selected completely randomly. Thus, while the shard is processing transactions, it does not know whether it will be validated by honest or malicious fishermen, which puts significant pressure on the shard node to act honestly. We will also provide a hint here (mentioned in the following post) to prevent the fishermen from knowing whether their verdict will be re-verified.

Validate games and consistent "consensus"

Previously, we mentioned that validation nodes can prove incorrect state transitions. Is it possible to do this in a cost-effective way? The answer is "yes" : one approach is to use truebit-style verification games: if two nodes disagree on how a transaction should be updated, it should be possible to find processing for a single virtual machine instruction if they disagree. Once such an instruction is found, you can ask an external, trusted judge (for example, ethereum) to repeat it to figure out the right way to handle the instruction.

Note that in this case, only a small portion of the computation is processed on the chain, so the judgment is not overloaded. In addition, you can find questionable instructions by disputing nodes with the help of n-ary searches - that is, without much computational overhead.

Note that validating the game mechanics requires only an honest node to catch malicious behavior. In other words, the shard nodes and the fishermen must agree on how to make the transition.

Let's find out the probability of malicious behavior that goes completely unnoticed. Suppose that in addition to the fragment consisting of n nodes, we have m fishermen independently verifying the fragment. Malicious behavior is detected only if the debris is taken over and all fishermen are malicious:

If we separate the computational resource budget between the four nodes and the three fisherman nodes in the shard and keep our assumption that 10% of the nodes in the network are malicious, the probability of ignoring bad behavior becomes 0.00037%. This probability is two orders of magnitude lower than our previous naive models!

Malicious behavior economy

If the shard node cannot coordinate with the fisherman node at all, this possibility will further decrease. Imagine some malicious node being able to take over a shard. We also assume that these nodes have merged $1,000 over the network. Finally, let's assume that the sharding nodes are reasonable and perform the wrong state transition only if their gains outweigh their losses.

If the three fisherman nodes later verify the fragment, the probability of the malicious node being captured and losing its benefit is 1-0.13 = 99.9%. Now, let's calculate how many malicious sharding nodes they need to get before their behavior becomes economically profitable.

If we assume that they only profit when their actions are ignored and the trading history of the pieces is not recovered, then in 999 out of 1,000 they will lose $1,000 in shares and make nothing. In 1 out of 1000 cases, they will receive $x, which should cover all bets they lost. Solving this simple equation, we learned that the malicious sharding node needs to earn at least $999,000 to break even. In other words, the transaction volume of the shard must exceed $1 million to make the attack meaningful!

This sounds too good to be true, and we agree: the economic model for malicious behavior in hybrid systems is much more complex. Unfortunately, although the shard nodes do not know the fishermen in advance and therefore cannot initiate an early dialogue, some less honest fishermen may contact the shard nodes if they find incorrect behavior. The fishermen can then demand a fee from the debris nodes to remain silent. We'll consider the economic details of this and other attacks in further posts.

Put it all together

Fluence Labs is working to bring the distributed cloud closer to reality by combining a fragmented blockchain approach with a decentralized storage network, trusted judgment, and a classic client-server model to deploy a decentralized database network that is cost-effective. Traditional clouds.

Fluence is a hybrid solution, and we mentioned different aspects earlier in this article. The Fluence network is divided into small shards, each responsible for a separate database. These sharding uploads transactions to a decentralized store, and then the Shared fisherman pool validates the uploaded transaction history. This validation is performed asynchronously with the transaction, allowing request service latency to remain low and the user experience to be smooth.

The shard composition in the Fluence network does not change frequently, which avoids excessive data transfer when a new verifier joins the shard. Instead, fishermen rotate constantly, which improves overall network security. If any node does not agree on how to process the transaction, it initiates a dispute over the ethereum blockchain, which is resolved by validating the game mechanics.

WebAssembly ACTS as the target virtual machine, allowing for the migration of many well-written open source databases to the Fluence network in combination with cost efficiency. In fact, we just ported Redis and now look forward to porting a production-level SQL database (there is already a product & NBSP; --LlamaDB), such as SQLite.

We should also note that deferred validation in our architecture allows Fluence to conduct efficient and secure cross-database transactions, but that is the topic of the next article, as well as some specifics about Fluence architecture.

Source:https://medium.com/fluence-network/securing-decentralized-databases-part-i-6736d2a4b2f4

Welcome to join the official BlockBeats community:

Telegram Subscription Group: https://t.me/theblockbeats

Telegram Discussion Group: https://t.me/BlockBeats_App

Official Twitter Account: https://twitter.com/BlockBeatsAsia