Blockchains solve a hard problem: how to ensure consensus across a distributed, decentralised network, where messages arrive out of order if at all, where individual nodes may fail, and where a certain proportion may be actively malicious.
The original blockchain, bitcoin, was designed to support a novel digital currency, and the issue its consensus algorithm solved was preventing double-spend. It also successfully introduced game theory for security: adversaries would have to spend more money on an attack than they could expect to gain financially. All this and the original protocol was just a few hundred lines of code.
But this achievement came at a high cost in terms of energy use and performance.
With bitcoin, a new leader is required to verify each block of transactions, that leader being the first device to complete a computationally heavy challenge (Proof of Work, PoW). As a result, the blockchain's throughput is painfully slow at around seven transactions per second (Visa claims it can do 56,000) and the whole process is massively wasteful of energy. These drawbacks have been surmounted, to some degree, in newer blockchain designs using overlay networks, sharding and different types of "proofs of" and by non-blockchain directed acyclic graphs (DAGs), but each requires tradeoffs in terms of centralisation, complexity or security.
A group of researchers led by computer scientist Professor Rachid Guerraoui of Swiss University Ecole Polytechnique Fédérale de Lausanne (EPFL) decided to look afresh at the problem. Is this gargantuan security apparatus, in which every node in a network of thousands or millions must come to a consensus about the ordering of events, really necessary everytime someone makes a purchase? Could a leaderless mechanism be applied to the problem instead? If so, could it be guaranteed to be reliably consistent, even when a certain number of nodes are malicious or faulty (Byzantine)?
Network-wide consensus is overkill for simple asset transfers
The headline answer, published in an initial paper last year, is that network-wide consensus is overkill for simple asset transfers. If cryptocurrencies could be rebooted, all the fossil fuels burned by miners of bitcoin and its clones could be left in the ground and Visa-level transaction speeds could be achieved without any loss of security or reliance on centralised control. As compact as Satoshi's original bitcoin protocol itself, the few hundred lines of code that make up their Asynchronous Trusted Transfers (AT2) algorithm could solve some of the tricky problems that have plagued decentralised token-based networks from the off.
AT2 can be used to validate transactions within two different decentralised networking scenarios: (1) permissioned or small unpermissioned networks, and (2) global scale unpermissioned networks. In the first case, the algorithm uses quorum for validating actions, whereby a certain proportion of the network's nodes must agree an action is correct before it can take place. The second scenario, networks made up of very large number of machines (nodes), uses probabilistic sampling. Instead of asking all nodes it checks a number of randomly selected nodes for their viewpoint. This is much more efficient and scalable than the deterministic quorum but carries a tiny (ca. 10-15) possibility of failure.
Doing away with network-wide consensus means AT2 sidesteps the bane of decentralised networks, the FLP Impossibility - the theory that in a fully asynchronous system, a deterministic consensus algorithm cannot be safe, live and fault-tolerant.
Computing caught up with Matteo Monti, who worked on the statistical aspects of AT2, and by email with Guerraoui to find out more. We also spoke to David Irvine of networking firm MaidSafe, which has adopted AT2 to simplify its consensus process.
We asked Monti (pictured) to summarise the innovation that AT2 brings to the table.
"What we noticed is that there's a specific subclass of problems that can be solved on a decentralised, distributed network without requiring consensus," he said. "The main use for consensus at the moment, cryptocurrency transactions, is part of that class. We can solve this using a weaker abstraction and in doing so you gain the ability to work in a completely asynchronous environment."
Bitcoin doesn't even solve consensus well. It solves eventual consensus which an even weaker abstraction, he added, whereas AT2 can guarantee strong eventual consistency. Another issue it tackles is PoW's incentivization model which means that improvements in technology do not translate into a better performing network.
"With bitcoin, the bottleneck is always electricity. If everyone doubles their computational speed it's not going to change the efficiency of the network. Everyone's competing not to compute but to waste energy."
In place of PoW, AT2 uses ‘Proof of Bandwidth', i.e. evidence of recent interaction, to verify that a node is real. Since it doesn't rely on consensus, the performance of AT2 should allow messaging speeds across the network that approach the theoretical maximum, and improvements in hardware will translate into better overall performance.
Blockchains like bitcoin are extremely resilient against Sybil attacks; bitcoin is still running after all, in the face of unwavering opposition from powerful nation states and bankers. Sybil attacks are a major vulnerability in permissionless decentralised networks where anyone can join anonymously, but there are others too.
Monti said the most challenging aspect of designing the AT2 algorithm was distilling all the potential types of dangerous Byzantine behaviour into a manageable set so they could be treated using probability theory. As a result of studying many possible failure scenarios, including Sybil, the algorithm is able to quickly react to deviations from the norm.
Other security features flow from the fact that each network node needs to know only a limited amount about its counterparts for the system to function. For example, the randomness used in sampling operations is generated locally on the calling device rather than on the network, making this vector hard to utilise by an attacker looking to influence events.
Signals are passed across the network via a messaging system called Byzantine Reliable Broadcasting (BRB) a gossip-based method by which nodes can quickly and reliably come to an agreement about a message even if some are Byzantine.
The moment you implement an economic disadvantage to attacking the system, it means that you failed to make it impossible to attack the system
As a result of these features, AT2 does not rely on economic game theory for security, said Monti.
"I'd go as far as saying that the moment you need to implement an economic disadvantage to attacking the system, it means that you failed to make it impossible to attack the system. We don't care about your interests in attacking the system. What we want to achieve is a proof that no matter what you do, the system will not be compromised."
AT2 starts with the simple idea that rather than requiring the whole network to maintain a time-ordered record of my transactions (as with a blockchain or DAG), the only person who needs to keep that tally is me.
If I decide to spend some money, I merely announce that fact to the network over BRB and this request will be held in a memory snapshot escrow. Depending on the network type, a representative sample or a quorum of other nodes then check my balance and inspect my ordered transaction history to ensure that the funds haven't already been spent (each transaction has a unique sequential ID) and provided all is correct the transaction is guaranteed to go through, even if up to a third of those validators are malicious. If I try to cheat, the transaction will be blocked.
Monti likens a wallet on an AT2 network to a social media timeline.
"What we've proved, essentially, is that you can have a cryptocurrency on Twitter," he explained.
"A payment works in two steps. First, there's a withdrawal from my account via a tweet, then the second step is a deposit, or a retweet. I tweet a message saying I want to pay Bob. Bob then retweets this message on his own timeline, and in the act of retweeting he's depositing money in his account.
"So everyone has their own independent timeline and while the messages - my tweets - are strictly ordered, that's only in my own timeline; I don't care about ordering relative to other timelines. If I try to pay someone else, it will be obvious by the sequence of tweets in my account, and my account only, whether I can perform that payment.
"In contrast, consensus effectively squeezes all of the messages into a unique timeline on which everybody agrees. But this is overkill, you don't need it. We can prove that it still works even if the ordering is partial and not total, and this enables us to switch from consensus to reliable broadcast."
But of course, nothing comes for free. AT2 can verify exchanges of tokenised assets, but aside from arrangements between a small number of opted-in parties, it does not have the ability to support smart contracts of the type that are viable on ethereum and other blockchains, because this does require network-wide consensus. Guerraoui said his team is working on "refinements and extensions" to support such functionality in the future.
AT2 is still pretty ‘cutting edge'. Three papers have been accepted for peer review the latest published in February, but it provides the sort of efficiencies and simplifications that could bring real progress. Guerraoui said AT2 has "received interest from many groups including companies ‘selling' blockchain approaches, as well as companies and organisations using such approaches".
One organisation that has already picked up on the potential of AT2 is Scotland's MaidSafe, creator of the SAFE Network. MaidSafe is already using AT2 to replace its Parsec consensus algorithm, which testing showed was indeed overkill for many network operations. CEO David Irvine said he and his colleagues came across AT2 while working on another way of propagating changes to data without consensus, conflict-free data replicated types (CRDTs), promptly forked the code and started to apply it.
SAFE, currently in Alpha, is a sharded network, meaning it's subdivided into small semi-autonomous sections. On a network level, the way it works is that trusted 'elder' nodes vote on a requested action then pass instructions to other sections to carry it out.
AT2 allows the initial task of accumulating the votes for an action, which had been done by the elders using a consensus algorithm, to be moved off the network and onto the requesting client which is much more lightweight and efficient. Once a quorum of votes has been gathered, the client simply resubmits the request and the elders will ensure it's carried out. The system is much simpler and should be more secure too. "It's 200 lines of logic compared to 15,000 for a start," Irvine said.
It certainly falls into the category of ‘why didn't I think of that?'
AT2 is not just used to validate token transfers. By the same mechanism, it can also be used to authorise requests to store or change data. Together with CRDTs, which guarantee that such changes cannot fail, this makes for a very tight and efficient ship, said Irvine.
"AT2 is for us a missing link. The difficulty of several nodes agreeing is simplified by the initiator taking on the effort of accumulating quorum votes. It seems so simple but in fact, it's an amazing innovation. It certainly falls into the category of 'why didn't I think of that?'."
App designed to safeguard children online was the result of two years' toil at AI's cutting edge, says product manager Jon Howard
Interview: CNCF head Priyanka Sharma - 'The arc of innovation is long and it bends towards true open source'
Cloud Native Computing Foundation's new general manager on developer trends, collaboration and disappointment over Google's surprise decision not to donate its Istio project
Evaluating open source projects and repositories is a time-consuming and unreliable process that can be greatly improved by an intelligent platform approach
Acquisition will support SUSE's ambitions in application management
GitHub says it has found the problem and is working to resolve it.