Log in

No account? Create an account

December 29th, 2017

eyes black and white

Meta-Decentralized Cryptocurrencies

Dear crypto-currency hacker friends,

I had the following epiphany about decentralizing crypto-currency transactions, into a network of repudiable centralized operations with ultimate decentralized arbitration, thereby achieving ledgers with both high-throughput and high-trustworthiness. I would appreciate you helping me find out whether it is original, already well-known, or well-debunked.

A short URL for this proposal is https://j.mp/MetaDecentCC. A longer write-up that gives more details is at http://fare.tunes.org/computing/mdcc2018.html.

The essential innovation brought by Bitcoin was a way to achieve consensus without centralized management. Unhappily, this consensus is technically very hard to achieve, economically very expensive, and it is slow and has low throughput, etc. Centralized systems are much cheaper to operate, much faster, much more reliable, etc.; but ultimately they are subject to failure or abuse by the operator: overcharging or outright censorship of transactions, double spending on their own transactions, inflation, confiscation, outages, gross negligence, etc. A big question today is how much the advantages of distributed consensus can be combined with those of centralized management without also combining their disadvantages.

I was reading about the Bitcoin Lightning Network, OmniLedger, and other proposals to decentralize crypto-currency payments in a safe yet speedy way. Then I was reminded of the notions of (1) Voice and Exit and (2) Slasher-style denunciations. Voice and Exit are the idea, common among libertarians, that what keeps infrastructure managers honest and efficient is mostly not (a) the ability to "Voice" complaints and maybe cast a tiny vote in picking who the next collective manager will be for everyone, but (b) the ability to individually "Exit" the set of customers of your current service provider, or even of all existing service providers, thus becoming your own provider and possibly that of others (extreme case also called "Enter"). Slasher-style denunciations are the idea that if cheating is possible to some parties, these parties can be motivated not to cheat by having skin in the game that they will lose should their cheating be detected and denounced (this idea was first applied to cryptocurrencies by Vitalik Buterin as part of a proposed Proof-of-Stake protocol called Slasher; I heard about it in the Tezos White Paper).

In a crypto-currency, public key cryptography is used so that funds in a public ledger are assigned each to an entry protected by a publicly recognizable lock. Only the actor who knows the matching secret key (typically called Alice) can sign the checks that spend funds protected by a given lock (in some more advanced cases, it can be a set of actors each with many keys, interacting through a "smart contract"). There is no way within the system to cheat by spending funds controlled by someone else: you may crack their computers or torture them to extract their keys; but supposing that their software, hardware and wetware are secure, remote participants in the protocol cannot rob these funds. Inflation and confiscation, two risks commonly associated with phanæro-currencies (currencies that are not crypto-currencies), can also be written out of the protocol at the time it is designed, before it is adopted; or they can be made to follow predictable patterns that users may accept before they adopt the currency, or reject and the currency with it. The main risks that remain in a cryptographic ledger are: (C) censorship of transactions, with includes gouging of transaction fees under threat, and locking or destruction of funds that thereupon cannot be spent anymore, and (D) double-spending of funds by a malicious actor, who promises to deliver the very same funds simultaneously to multiple recipients and run away with benefits received in exchange before the deceived victims hear the news.

Now, notice that both remaining kinds of bad events require a bad actor, typically called Mallory (or sufficiently incompetent one — here as always, any sufficiently advanced incompetence is indistinguishable from malice). In the case of a centralized chain, the central manager can easily catch small fraudsters and punish them (say by confiscating or destroying their funds); but the central manager may herself become fraudulent, and/or fraudsters will do their damned best to become the central manager (and will eventually succeed). Guarding against these two possible behaviors by Mallory having become the central manager is the one on only (but oh so difficult) purpose of the distributed consensus protocol. If only Alice and her partner Bob could somehow safely let someone trustworthy like Trent guarantee their transactions against small time thieves like Mallory, without Trent himself turning into Mallory! Then they could have very fast transactions at lightning speed, yet that are robust and trustworthy, without a single point of failure or trust.

Therefore, what is ultimately required from the consensus protocol (centralized or decentralized) is a "justice" system that guarantees the right of Exit: if Alice's account is currently managed by Trent who tries to price-gouge her or censor her or otherwise fails to process transactions out of incompetence or dysfunction, then Alice can denounce Trent to Judy, repudiate him as her notary, and either transfer her account to Ted instead, or start her own notary business. (To incentivize Trent not to censor transactions in general and exit transactions in particular, some of the fees associated to the exit transactions would be paid by Trent if the matter reaches Judy, though Alice has to pay at least as much in fees to reach Judy, or else there is an unfair weapon whereby rich operators can pay to bankrupt their competitors with a multiplicative effect.) Once she finds a trustworthy notary willing to record the transaction, Alice can send funds to Bob; and if no notary is willing, Alice can register herself with Judy and self-notarize the transaction; that will be technically more demanding and possibly more expensive due to Judy's fees, but the option is always available, prevents outright censorship or freezing of funds, and sets a cap to how much transaction notaries can gouge before losing all their customers. An additional incentive for notaries to never censor or gouge their customers would be to tie the benefits they receive to the presence of these customers: the ability to charge fees or inflate the money supply (in a limited way); those benefits constitute "skin in the game" the fear of losing which makes a powerful motivator for notaries. (This is another point that Tezos gets well.)

As for the second kind of risk, double-spending, it only happens when Mallory is a notary and signs away the same funds multiple times. When receiving funds from Alice as signed by notary Trent, Bob must make sure to tell everyone about it, and complain loudly and timely to Judy if he hears of a double spending attempt, and wait for long enough that no one else did issue a complaint that Alice and Trent were actually Mallory in disguise who was trying to double-spend. To determine whether a transaction is valid, Bob therefore "only" has to track what the manager Trent said, and wait for Judy to validate what was the (digest of the) official state of transactions notarized by Trent, and check that Judy did not publish a repudiation of Trent by Alice, or a denunciation of Trent's behavior by a double-spending victim. And here's the great advantage of this proposal: it is infinitely faster for Judy to not publish negative messages than it would be for Judy to actually publish positive messages.

To make it costly for Trent to even try to cheat and maybe succeed if there is a glitch in the system, Trent has to put skin in the game by leaving funds under a lock with its name attached. Then, if Trent is otherwise found to have facilitated double-spending, these funds will be lost: half earned by whoever denounced Trent to incentivize denunciation, and half destroyed (Trent could preemptively denounce themselves under a false identity, and avoid losing, if there were no destruction). If Trent himself is not an anonymous node in an anonymized network, but a large well-known corporation with lots to lose should its operations be found to be either fraudulent or incompetent, all the better: more skin to lose in case of either censorship or double-spending attempt, and no ability to profit. And yet if governments try to crack down on such institutions, the ledger can easily fall back a lot smaller servers hiding behind TOR and its rivals or successors. As for regular clients, they can use anonymizing techniques without loss of robustness to the system.

In a degenerate case, there is one very fast high-throughput centralized transaction network, plus a slow low-throughput validation network that keeps it honest and efficient; if and when the centralized transaction network fails, becomes too expensive, or starts cheating, everyone suddenly raises the issue with Judy and moves to a new network; the process may take some time and cost a lot of money, but that these transition costs put a cap on how much the network can suck.

In less degenerate cases, there is a federation of management networks, with fast cheap transfer in-network, and several options of inter-network transfers: go ask Judy to switch notary (slow and expensive but guaranteed), have Trent tell Ted about the transfer, and wait long enough to make sure no one denounced Trent as a double spender to Judy, or if you're in a hurry and/or feeling trusty, pay Faythe, some trusted intermediate with accounts with both Trent and Ted, to do the transfer. When receiving funds from someone you don't fully trust, always wait for Judy to confirm what Trent says. If you must use the services of Faythe, look at how much bail money she left in escrow at various notaries, and decide whether she will want to lose them all so as to indulge in a short-lived spending spree before she gets denounced.

The last issue is: how do you make sure that Judy keeps doing her job, that she is actually listening to denunciations and publishing them, etc., etc.? Well, that's where you need a more traditional Consensus system: instead of being a central authority, which would only push back the issue and leave us with yet another centralized system with extra steps, Judy can be a protocol on top of a decentralized consensus system (or rather THE decentralized consensus system, some of my friends would argue), whether it is based on Proof-of-Work (effective but expensive), Proof-of-Stake (cheaper but more fragile?), or whatever the most trustworthy technique of the day is (today, Bitcoin, tomorrow, the Moon?). Denunciations are therefore published and accepted in a consensual priority order from which the protocol uniquely determines how and in whose favor the ledger is adjusted. Settlement of denunciations would have to have clear precedence and reconciliation rules, which would make the code quite complex, especially since suddenly large swaths of a vastly different blockchain technology has to be made part of the codebase. Ultimately, though, such is the cost of reconciling the advantages of centralized and decentralized: its codebase must contain both the centralized and decentralized systems, plus some code to reconcile the two. If the system has its own decentralized blockchain, early denunciations will be considered as adding sufficient weight to the chain as to make censorship hard; but not in a way that would allow toppling the chain (and thus double spending) using retroactive denunciations.

Note that even when censorship of denunciations somehow happens at the level of Judy, it can become "common knowledge" very soon that certain transactions were fraudulent, at which point the notary disbarred while multiply-spent funds and his bonds are effectively frozen until an uncensored denunciation is published that establishes who gets the reward for proving the fraud. Consensus is only needed to determine who gets the reward, whereas common knowledge is enough to stop people from being defrauded. This in turn means there is little incentive to censor denunciation and positive incentive to publish them. But it also means that people managing serious money should keep listening to consensus-less decentralized chat networks in addition to the consensus. Happily, consensus-less decentralized chat is both cheap and fast. To reduce the incentive for both retroactive cheating (indian giving) and censorship, denunciations can't freeze funds that Judy couldn't prove were multiply spent within the timeout window for a confirmation; but the notary's bond has to remain posted for a much longer time, and is still lost if they were found to double spend. The bond can be made of user subscriptions, that are only released if no fraud was proven for an enter cycle (say one week to one month) after the end of the subscription; if Alice goes to Judy to denounce Trent, and Trent loses the fee he collected from Alice (which causes deflation and/or goes back to a pool that pays miners; Alice does not get the money back, and must pay the miners a fee to invoke Judy.)

I admit that I don't understand the economics of mining enough to say whether my construction can be used with a system that is ultimately cheaper than Bitcoin's Proof-of-Work network at achieving a robust Decentralized Consensus. I would guess that mining costs could be kept proportional to fraud expectation given the suspected (un)trustworthiness of the notaries; but that would mean that fraud would appear when the costs are too much underestimated. Still I do believe my construction manages to combine the throughput of centralized systems with the robustness of decentralized systems, at the same overall cost and latency as existing decentralized systems, and hence much reduced cost per transaction compared to pure decentralized systems, and much improved robustness compared to pure centralized systems. This construction thus uses distributed consensus as an arbiter between competing centralized systems, such that the price paid for consensus is proportional to fraud and/or failure and born by those who are dishonest or make bad decisions instead of being proportional to the active value of the network and born by those who are honest and make good decisions.

Now, please tell me what I have missed, if anything. Is this construction actually robust, or are there flaws I failed to see? Is it original or has someone already proposed it? Even if it basically works, are there hidden costs and issues I have failed to consider?

PS: some of my friends told me that while the specific way I frame this idea might be original, many of the same general concepts are already used in projects to federate blockchains, such as Blockstream Liquid or Ethereum 2.

eyes black and white

December 2017



Powered by LiveJournal.com