[Cryptography] Almost decentralized currency

L. M. Goodman lmgoodman at hushmail.com
Mon Jun 23 20:33:55 EDT 2014


The premise behind Bitcoin is that once a user discovers the genesis hash (or the last checkpoint) of the blockchain, he can reconstitute the canonical blockchain by picking the chain where the most hashing power has been used. The difficulty required to build blocks is adjusted depending on the amount of mining happening. This is an attempt to entangle the chain with time. However, this only works if more than half of the computing power is constantly mining on the main branch. As Ben Laurie points out, convergence is only guaranteed when half the computing power in the universe is dedicated to mining Bitcoin.

As an alternative, he suggests a network of mintlets using an asynchronous Byzantine agreement protocol to maintain the current state of the currency. 

Bitcoin's proof of work system implies that participants need to trust no one, a priori. Yet, a posteriori, they end up placing their trust in very few mining operators. In which world are Ghash.io and Eligius less likely to collude or be compromised than a set of trusted signers such as the EFF, the FSF, Google, Goldman Sachs, Al Jazeera, the University of Hong-Kong, etc?

In fact, the mintlet proposal can be hardened by specifying that the mintlets maintain a pointer to the head of a blockchain instead of a mere state. If transactions within the blockchain include references to previous blocks, any shenanigans from the mints will be glaringly obvious to the world. Should the mints try to undo a transaction, they would need to invalidate many blocks infuriating a lot of people. The blockchain would be restored from a backup and more trustworthy mints chosen.

However, such proposals are likely to face opposition from the adopters of cryptocurrencies. Right or wrong, they strongly value the fact that no one holds a privileged position in Bitcoin. A system of trusted mintlets, though it could be far more efficient and far more secure looks too hierarchical to them. The "burn the banks" crowd would claim that such a currency is owned by the mints and reject it.

Can we still have an efficient cryptocurrency that does not rely on a proof-of-work system or on trusted mintlets? I believe so.

Social networks provide a peer to peer fabric of trust that can be leveraged for a cryptocurrency. Imagine a peer to peer network of pseudonymous peers establishing trust links between one another. If such a network could reach a consensus without allowing malicious nodes to take control of the consensus, then it could maintain a pointer to the head of a blockchain, and serve as a ground truth to determine the state of a ledger.

Unfortunately, Byzantine agreement protocols would not be sufficient here. A Sybil attack is trivial, and a very large number of fake participants could be generated. However, it is difficult for a malicious attacker to create links between his sock puppets and honest nodes. Indeed, if honest nodes overwhelmingly peers with nodes they trust, the cut set between the honest nodes and the malicious nodes will be small.

As it turns out, there are many papers offering scheme for Sybil defense in social networks. They rely on the fact that real social networks are fast mixing. This typically means that after O(log n) random steps from an honest node, the probability distribution of the landing node is very close to the limiting probability distribution. An honest node is much more likely to reach another honest node in O(log n) hops than to reach a Sybil node.

One such algorithm is SybilLimit https://www.comp.nus.edu.sg/~yuhf/yuh-sybillimit.pdf
As long as the number of edges between honest nodes and malicious node is o(n/log n) (where n is the number of honest node), it only accepts  O(log n) Sybil nodes (per malicious connection) as honest. Furthermore, this algorithm can be run in a completely local manner, between the trusted peers. The impact malicious nodes can have on the consensus only depends on the attacker's ability to receive trust from honest nodes, which is hard to obtain.

Such a network could let honest node maintain a consensus over the current head of a blockchain and offer a robust cryptocurrency that is far safer and more efficient than proof-of-work, while appealing to people looking for a non hierarchical protocol.



More information about the cryptography mailing list