Proof of funds for cryptocurrency custody: third-party attestations (part III)

[continued from part II]

Assets and liabilities

Before delving into the options for proving that a cryptocurrency custodian has all customer funds in storage, a few word on what exactly we are trying to demonstrate. As before, there are individual customers who deposited varying amounts of cryptocurrency for safekeeping with the custodian. Those account balances are on the  liabilities side of the accounting books— money owed to customers. They are tracked on an internal, private ledger maintained by the custodian. (For reasons explained earlier, the state of this ledger is not reflected on the public blockchain.) The custodian also controls some blockchain addresses where funds are logically kept; these are the assets. The objective is proving that custodian assets are approximately equal to its liabilities.

The fine print: time, currencies and drift

A few clarifications are in order. First, the comparison is always done at a specific point in time. Customer balances are in a state of constant flux: new deposits arriving, withdrawals leaving the wallet and at least in the case of exchange, trading activity resulting in funds changing hands among customers. To avoid discrepancies caused by such fluctuations, it is important to fix a reference time when answering questions such as “how much bitcoin does customer Alice have?” (This can get tricky for cryptocurrencies due to confirmation times: when the customer can sends bitcoin, there is usually a delay between those funds appearing in the custodian wallet and being credited to the customer. The former happens when the very first block containing that transaction is mined, while the latter may follow a few blocks later to allow for sufficient confirmation.)

Second, the comparison must be done independently for each cryptocurrency. In other words, bitcoin balances are reconciled on their own, independent of ether, litecoin or any other asset the custodian holds for that customer. The alternative is converting everything to notional dollar figure and only comparing totals. While that may appear to provide the same assurance regarding customer funds, it obscures important information. When a customer entrusts the custodian with 1 bitcoin, they expect the custodian to hold exactly 1 bitcoin and not that figure converted to equivalent amount of some other currency. Given the high volatility of cryptocurrencies, businesses engaged in that type of arbitrage activity would be exposed to risk from exchange rates moving in the wrong direction. Performing reconciliation independently for each supported currency demonstrates that no such conversions are taking place behind the scenes or necessary to satisfy customer liabilities.

Finally, why the qualifier “approximately” in the objective statement?  Because there are at least two factors that can cause the numbers to diverge slightly in either direction:

  • Handling of fees. When customers withdraw, the custodian creates a transaction that includes not only the specific amount requested by the customer but also a transaction fee paid to miners for maintaining the blockchain. A “round-trip” of 1 bitcoin deposited and later withdrawn will draw on slightly more than 1 bitcoin in assets. (In case that sounds unfair, consider that the customer also had to pony up slightly more than 1 bitcoin on the way in.) Whether the fees are negligible or not in the grand scheme of things depends on several factors including blockchain congestion, transaction patterns and exchange rate. Recall one of the most counter-intuitive aspects of blockchain economics: mining fees are a function of blockchain space consumed by a transaction, not the value transferred. An inefficiently constructed 0.0001BTC transfer can cost more in fees than one sending 1000BTC. Many small withdrawals are worse than one withdrawal for the same total.
    Depending on how the custodian accounts for fees    — eating the cost, fully passing it on to the customer or something in between— it can result in a drift between assets and liabilities. In late 2017 when bitcoin fees spiked precipitously, many cryptocurrency businesses responded by adopting a less generous stance towards absorbing fees and cracking down on abusive withdrawal patterns.
  • Custodian business model. The way a custodian collects revenue for its services can also result in drift between blockchain assets and liabilities. Consider an exchange that allows trading bitcoin against ethereum. Typically both the buyer and seller are charged a commission as percentage of the value involved in the trade. If Alice sold 1 bitcoin in exchange for 40 ether from Bob, both Alice and Bob pay a commission to the exchange. (Not to be confused with mining fees, which are only relevant for transactions that hit the blockchain.) Which currency those commissions are charged in determines the direction blockchain balances could differ from ledger balances. Here is an over-simplified example: the exchange can treat Alice’s original offer as 0.999 bitcoin, charging her 10 basis points, while crediting Bob 0.998 bitcoin after settlement, charging him the same 10 basis points. As far as the internal ledger is concerned, the original 1BTC owned by Alice became 0.998BTC owned by Bob after the trade executed. Of course 0.002BTC did not vanish into thin air. It is still there on the blockchain— the only ground truth that matters for monetary value— associated with some address controlled by the exchange. But from an accounting perspective, it is no longer on the liabilities side of the ledger. The net effect is blockchain balances will exceed ledger balances over time, with the excess corresponding to revenue earned by the exchange.

I. Trusted third-party attestations

In this model, the custodian hires an independent party trusted by its customer base to perform the comparison of assets/liabilities and provide a written statement of their findings that can be shared with customers. The custodian is responsible for providing all necessary information required by the trusted third-party (TTP for short) to perform the comparison. In particular, they must be given access to:

  1. Snapshot of internal ledger at a predetermined point in time
  2. List of blockchain addresses used by the custodian at that same instant for each cryptocurrency
  3. Proof that those addresses are indeed controlled by the custodian (This proof can take different forms as described earlier.)
  4. If the custodian also deals in fiat currencies, access to bank statements or equivalent supporting documentation to verify those balances

If everything checks out, the third-party can provide a written statement to the effect that the custodian has demonstrated control over an amount of cryptocurrency equal to their outstanding liabilities. Everyone with access to that statement is free to form their own opinion regarding the assertions, based on their opinion of the author. Assuming a competent TTP with expertise in traditional accounting and cryptocurrency, this model has the advantage of following standard practices for proving the integrity of financial statements. It is common for management to bring in an impartial third-party to look over the accounting and perform additional due diligence to vet statements made by that management team about the financials of the company. While that third-party is faced with the challenge of carefully scrutinizing company records, for everyone else including customers, the problem is greatly simplified. They need only focus on the final outcome, the report stating whether that independent examination successfully verified statements made by the company.

What could go wrong with this approach in the case of cryptocurrency? There is the obvious element of trust in the entity performing the review. But assuming an honest TTP with stellar reputation, there is a more subtle element of trust in the custodian for correct execution of step #1 above.

The problem is TTP can not verify its version of ledger is identical to what individual customers are seeing. The custodian could tell Alice that her account balance is 10BTC while TTP is given a version of the ledger crediting her with only 9BTC. Short of reaching out to customers and asking what they expect their balance to have been at a particular time, TTP can not ascertain liabilities were captured accurately. Aside from sheer impracticality— have you ever received a call from the auditor of your FDIC-insured bank asking what you think your account balance ought to be?— this would raise serious privacy issues. Keep in mind that balancing the books does not require TTP to learn anything about the identity of individual account holders. Instead of using a real name such as “Alice” or “Acme Trading LLC” the ledger shared with TTP can represent customers with pseudonymous identifiers. (Of course even this leaks some information: for example if it is known that a given hedge-fund or high net-worth individual uses a particular custodian, their total balance may be gleamed from the pseudonymous data as the highest value.) Actually exposing the identity or contact information of customers to TTP is problematic.

Likewise even disclosing total assets under management as part of the attestation would not help reassure customers that their funds are accounted for. This is because only the custodian has a global view of liabilities across all customers. Individual customers only get a “local” picture of their own slice. For example they may receive periodic account statements or have a web page where they can view their balances. But short of collective action involving every single customer, they can not infer the expected total assets under management from their own balance. Consider a simplified scenario where the custodian only has two customers: Alice and Bob. Alice has 10BTC in her account. Suppose an accounting firm vouches for the fact that the custodian successfully demonstrated control of 15BTC on the blockchain. Does Alice get peace of mind? No because she has no idea of Bob’s balance or for that matter the existence of Bob. If Bob holds a balance of 5BTC or less, all is well. But if Bob also had 10BTC on deposit, there is a problem: each customer sees total AUM exceeding their own balance— a necessary but not sufficient condition— while total liabilities exceed total assets.

These limitations inspired a search for alternative models where customers can independently verify that their own funds are properly accounted for. One approach from 2015 using zero-knowledge proofs will be the subject of the next post.

[continued]

CP

QuadrigaCX and Hanlon’s razor for cryptocurrency custodians

Another one bites the dust

Just in time for a series of posts on proof-of-funds for cryptocurrency custodians, news has emerged that the Canadian exchange QuadrigaCX has gone out of business and customers are unable to get their funds on deposit. The plot thickens after Coindesk started investigating and discovered a filing attributing the problems to the passing away of the exchange founder while traveling. According to the affidavit, customer funds were stored on a single laptop—thankfully still in the possession of the Quadriga team— but the password required to access that device and unlock the cryptocurrency storage were only known to the founder.

Suspicious circumstances surround the incident. To pick on three examples:

  1. Quadriga previously claimed to use a multi-signature design for cold storage. Instead of using a single cryptographic key, multisig distributes control of funds across N secret keys such that access to any quorum M ≤ N is sufficient to authorize a transaction. As the moniker “multi” implies N is greater than 1, it is difficult to see how the loss of just one laptop alone could result in complete loss of access to funds. (Unless that is all keys were stored on the same device; technically this qualifies as “multisig” in letter but not in spirit. The whole point of multiple keys is risk diversification: force attackers to perform additional work to get more than one key while also building resilience against failure/loss of individual keys. Keeping all keys on the same hardware achieves neither.
  2. Even if Quadriga used this degenerate design that achieves “multisig” in name only, the idea of storing over $100M USD on a system accessible to only one person defies the imagination. Well-run companies strive for redundancy in operation, seeking to avoid key-person risks where one person has an outsized level of influence on the success of the enterprise. If employee Bob is the only person in the entire organization who can perform a vital business function, the company is going to have a bad-hair day when Bob goes on vacation, quits to join a competitor, retires— or gets hit by a bus. In fact, that last morbid scenario has inspired the concept of “bus factor” for projects, quantifying the level of dependence on specific individuals with irreplaceable capabilities. Surely Quadriga management would have recognized the massive risk posed by their cold storage having exactly 1 authorized user and no redundancy beyond a single laptop? Putting aside personnel issues, what happens if that laptop experiences a hardware failure? Some commentators have also pointed out that the founder had a chronic medical condition that has also been listed as the cause of death. This is irrelevant: the bus-factor captures chance events not dependent on individual behavior. Careening buses do not discriminate based on prior conditions.
  3. Quadriga is also having difficulties accessing its fiat currency accounts, due to ongoing legal disputes. This is completely orthogonal to the problem of accessing cryptocurrency storage: even if the deceased founder had been the only authorized signatory for those accounts, the laws of mathematics do not prevent transferring ownership of funds to the executor. Experiencing problems with both cryptocurrency due to technical reasons at the same time as experiencing problems with fiat due to litigation at the same time is an unlikely coincidence.

The burden of proof

“Never attribute to malice that which can be explained by incompetence”— Hanlon’s razor

Looking past the present uncertainty, we can ask how Quadriga will substantiate its claim that funds have become inaccessible. In other words, what type of evidence is required to prove beyond reasonable doubt that the current dilemma is the result of an honest mistake around key-person risk (in both of senses of “key”) and not outright fraud? There are at least four pieces of evidence required:

  • List of wallet addresses. While the cryptographic keys controlling these addresses may be locked away in a laptop with unknown password, the addresses themselves are not secret information. For each cryptocurrency (bitcoin, litecoin, ethereum, …) Quadriga should be able to produce an inventory of all hot & cold addresses currently used to custody customer funds.
  • Sufficient funds to account for all customer deposits. While some addresses are no longer under Quadriga control due to inaccessible keys, blockchain balances must show that in principle all depositors could get paid in full if those addresses were accessible.
  • An argument for the correctness of the address list. This is the trickiest part, required to compensate for the missing proof that specified addresses are still under Quadriga control. Without that constraint, Quadriga can simply point to a random pile of funds on the blockchain— consider that there exist individual addresses storing more funds than all of Quadriga’s liabilities— and claim those as part of their own wallet. (Given privacy considerations, one can not rely on the legitimate owners to step forward and challenge bogus assertions.) This argument is bound to be imprecise, relying on heuristics and to some extent information volunteered by customers about their own deposits. Hot and cold wallets for a custodian are likely to exhibit high-degree of clustering. Hot wallet addresses send excess funds to cold wallet, and cold addresses replenish hot wallet when liquidity is running low. Starting with a self-identified customer deposit, we can trace funds on the blockchain. For example, suppose a Quadriga customer publicly volunteers the information that they deposited funds from origin address O123. The expected pattern on blockchain would be  O123 → Habc moving funds to hot-wallet, followed by a sweep transaction Habc → Cxyz securing the excess in a cold wallet address and perhaps eventually followed by Cxyz → H456 replenishing a different hot-wallet address when liquidity runs low. Every occurrence of an address in these patterns will lend additional credibility to Quadriga claiming that address as part of its wallet.
  • Permanent inactivity. This is a part of the demonstration that remains open-ended. If cryptographic keys controlling addresses are irretrievably lost, the expectation is those addresses never appear as the source for any future transaction on the blockchain. Any movement of money originating out of those supposedly frozen addresses would give the lie to the assertion that corresponding keys are missing. On the one hand, showing that the funds are indeed “stuck” is an easy way to refute the exit scam accusations. It is not exactly a very successful scam if the perpetrator goes out of business without getting to keep any customer funds. On the other hand, it means Quadriga will never have any finality or closure in its defense: years from today, the eventual movement of those funds could reveal that it was an exit scam after all— albeit one orchestrated by extraordinarily patient crooks, waiting years for their payoff.

Can Quadriga build a convincing argument? Time will tell. It is very likely that parts of the raw data will be reconstructed independently by outside individuals, without any participation from the company itself. Not surprisingly, the suspicious circumstances have already inspired armchair forensic accountants to conduct their own blockchain research to locate customer funds. One such examination has tentatively concluded that statements made by Quadriga management are not consistent with blockchain activity, to put it mildly. Time is running out for Quadriga to furnish its own evidence to refute these allegations, as the public narrative is shifting from an astonishment at incompetence to outrage fueled by increasing suspicion of malice.

CP

 

Where are the coins? Proof of funds for cryptocurrency custody (part II)

[continued from part I]

The challenge of commingled funds

Consider an exchange that allows trading bitcoin against another currency such as USD. For efficiency and scaling reasons, these trades will typically take place off-chain, on internal ledgers maintained by the exchange. That is, when Bob buys BTC from Alice in exchange for USD, that trade executes on private systems managed by the exchange, not visible to the outside world. Placing/modifying/cancelling orders does not update any blockchain state, and neither does the successful execution of a trade when bid/ask prices cross. That means when Alice and Bob are informed that their trade has executed successfully, there will not be not be any blockchain transaction taking funds from an address allocated to Alice and moving them to some other address exclusively reserved for Bob.

Why? Because given the capacity of common public blockchains, it would greatly limit trade latency, frequency and volume to require 1:1 correspondence between trading activity and blockchain state,  For example Bitcoin can process on the order of 10 transactions per second, depending on assumptions about segwit adoption. If every trade were reflected on chain, USD/BTC order books for the top five exchanges alone would account for 10% of that throughput. Putting that in perspective, USD/BTC is just one possible order-book involving bitcoin, and a tiny fraction of the overall bitcoin spot-trading volume. (Because unregulated exchanges have difficulty obtaining/keeping banking services required to accept fiat, crypto-to-crypto trading dwarfs comparable crypto-to-fiat activity.)

Deposits, withdrawals and blockchain state

Once trades are not reflected one-to-one on chain, the idea of dedicated addresses also goes out the window. At first this is counter-intuitive because, deposit addresses are typically unique. Every customer is given one or more unique address to use when sending funds to the exchange. This is used to simplify the problem of distinguishing deposits coming from customers. Recall that an exchange monitoring the blockchain only sees a sequence of transactions and must somehow identify those that correspond to an incoming customer deposit. While we can imagine elaborate schemes where customers state their intention ahead of time (“deposit will arrive from this specified address for this specified amount around this block number”) or use the equivalent of a memo-field in bitcoin transactions to indicate the account to credit for incoming funds, there is a much more user-friendly solution: disambiguate by destination address. When Alice wants to deposit funds, she is given a unique address controlled by the custodian. All bitcoin sent to that address is recognized as a deposit from Alice. Similarly when Bob wants to deposit funds, he gets a different unique address and any funds sent there are credited to Bob.

This may create the appearance of unique customer addresses but the model breaks-down immediately once trading and withdrawals enter into the picture. Suppose Alice deposits bitcoin to her unique address and later executes a trade to sell that to Bob. Recall that this trade will not be reflected on the blockchain even after it is executed. Some of the funds sitting on Alice’s deposit address no longer belong to Alice. Meanwhile Bob is the proud owner of some bitcoin, even if all of his deposit addresses have zero balance as far as blockchain state is concerned. Later when Bob wants to withdraw some of his shiny new coins, the transaction could originate from any combination of exchange-controlled addresses that combine for the requested amount. It does not have to be one of Bob’s own deposit addresses. It does not have to be the original address associated with Alice that supplied the bitcoin Bob acquired in the trade. In fact, there is complex optimization problem around spend-candidate management: given a wallet with large number of addresses and multiple unspent transactions for each address, what is the right combination of UTXO for sending N bitcoins?” The optimal answer for that question is very unlikely to coincide with the internal trading history of how the bitcoin changed hands inside the exchange ledger.

Bottom line: for large-scale cryptocurrency custody, customers have no way of confirming their balance from blockchain state alone. Their custodian could assert that they have 2.5 bitcoins on deposit but the customer can not verify this by looking up the balance of some addresses, secure in the knowledge that all funds residing at those addresses are earmarked for that customer.

Tangent: deposits, withdrawals and misattributions

One consequence of the design described above is that third-parties monitoring the blockchain can get confused by observed patterns and misattribute intent.

Suppose a given blockchain address has been associated with malicious activity: for example it is used to collect payouts from a ransomware scheme. Later a transfer is observed from this suspicious address into Alice’s deposit address at some custodian and credited to her account. Does that mean Alice is implicated in the shenanigans? Not necessarily. Once an address appears on the blockchain, anyone is free to send funds there. Recall that Alice does not have to notify the exchange ahead of time about her intention to deposit. Any blockchain transactions observed sending funds to that address are automatically credited to her account— that means transitions initiated by Alice, but also by someone mistyping an address (granted, this is unlikely because addresses have a checksum that reduce the chance of a typo resulting in another valid address) but more importantly, anyone else who wishes to send a “gift” to Alice. This is not at all an uncommon: high-balance addresses in bitcoin often receive spam contributions. That means one must be careful about jumping to conclusions about evidence of relationship between sender/recipient based on a deposit, especially when the amounts are nominal.

Another example of misattribution going in the other direction. Often transactions originating from an address are assumed to speak “authoritatively” for the intentions of that address. During the controversial Ethereum hard-fork, a virtual poll was setup to gauge support for the fork. Users could vote by sending a nominal amount from their address, to different addresses corresponding to “yes” and “no” options. Of course this being cryptocurrency, voting rights were determined by the distinctly antidemocratic metric of money: the higher the ether balance of the address involved, the greater weight assigned to the vote. Given the hot-wallet management strategy for commingled accounts, it is easy to see how this can be gamed. Any customer can ask to withdraw funds from their cryptocurrency custodian and specify their choice of vote as destination.  While the nominal amount of ETH will come out of that particular individuals’ account (no free-riding allowed) the weight of the vote will be completely out of whack with reality. Because the withdrawal is coming from an address controlled by the exchange, it is likely to have a much larger balance that the individual “voting” and those tallying the votes will incorrectly assume this one vote as representing a much larger pool of money.

Proof-of-funds for omnibus wallets

With this background on typical custody designs for cryptocurrency in large scale systems, we can not turn to ways the custodian can convince customers that all of their funds are still in storage. At a high-level there are three options:

  1. Bring in a trusted third-party. This borrows on the standard practice of independent audits in finance. The auditor is hired by the custodian and given full access to both its internal ledger of customer balances and blockchain addresses.
  2. Use cryptographic protocols to publish public proofs of assets and demonstrate those assets equal or exceed customer balance. There is no trusted third-party required for verifying the assertions, but it requires participation by individual customers to confirm their own balance is represented in the proof.
  3. Hybrid designs, combining elements of third-party statements and public proof. Instead of 100% public verifiability, these options allow customers to independently verify some aspects of the solvency criteria while relying on assertions made by independent auditor for others.

[continued]

CP

 

Where are the coins? Proof of funds for cryptocurrency custody (part I)

An earlier post looked at limitations inherent in a do-it-yourself audit of cryptocurrency custodians, such as the recent Proof of Keys event. Left unanswered is what better solutions exist for achieving the same objective. It turns out there is a wide-range of options here, ranging from very low-tech, traditional solutions relying on trusted third-parties to sophisticated cryptographic protocols relying on customers to individually verify their balances.

Simple custody

To better appreciate the challenge involved in proving control of funds, it is instructive to tackle a simplified scenario first before looking at more realistic custody scenarios. Suppose Alice is storing bitcoin on behalf of Bob. Bob requires periodic assurance that the funds are still there. In other words, that Alice did not suffer a security breach, abscond with the funds or start an unauthorized lending business on the side, using the funds under management as operating capital. One would expect that if there is any advantage to using a public blockchain, this would be it: since the blockchain is a public, transparent ledger of all balances in the ecosystem, it ought to be possible for Alice to verify her own balance. That intuition is accurate but there are a number of qualifications and pitfalls.

First, Alice must reserve dedicated addresses for Bob and share those addresses with Bob. It does not have to be a single address; Bob’s funds can be spread across multiple Bitcoin addresses but they must never be commingled with other funds such as Alice’s own money. Armed with knowledge of the addresses, Bob can periodically check blockchain state to verify those addresses still have the expected balance, with the understanding that the whole balance belongs to him.

But this is only one piece of the puzzle. Presumably Bob seeks assurance over time that Alice is still in full control of those addresses. That is, if Bob were to ask for his funds back, Alice would be able to execute a transfer. Since control of funds in cryptocurrency boils down to control of cryptographic keys, this is a question of key management: does Alice still have control over the secret keys corresponding to those addresses? (Note this is a decidedly different from proving that Alice would execute such a transfer if asked; it is only proving capability. In a custodial arrangement, Alice can always choose to hold funds hostage. That is a contractual risk Bob is accepting, outside the purview of blockchain rules.) Again there are different ways for Alice to provide this assurance.

Naive solution with test transactions

One obvious solution is to conduct a round-trip transaction for a nominal amount. For each address used, Alice sends a tiny small of assets in custody to an address controlled by Bob and Bob returns them back immediately to the same address. Completing that two-way exchange creates a persuasive that Alice is in possession of private keys.

While this naive approach provides solid proof of solvency, it has significant limitations. It is wildly inefficient; blockchain transfers incur transaction fees and compete for scarce block space. Bob is stuck with handling bitcoin, even if temporarily and for small amounts— the very obligation he hoped to outsource to Alice in the first place. The pattern of round-trips visible on the blockchain undermines the privacy of participants, by linking their addresses over recurring transactions. Finally a single round-trip can not establish redundancy of keys used in multi-signature addresses. Recall that the multisig feature in Bitcoin allows using a quorum of keys to control funds. Commonly designated as M-of-N, the designation stands for having a total of N different keys, of which any subset M are sufficient to authorize  transactions. This creates a complication for proofs: signing a transaction requires only M keys and therefore can not prove that the signer had access to all N keys unless M=N. The distinction matters, because one of the major benefits of multisig is redundancy. For example in 2-of-5 arrangement, the custodian can lose access to three keys and still retain control of funds. Such redundancy is highly desirable in custody scenarios for additional peace of mind of the customer, and so is being able to demonstrate control over all keys. Using the naive approach would introduce even greater inefficiency, by repeating the transaction with different subsets of keys until all N make an appearance on the blockchain.

Refinements with cryptographic protocols

A better approach involves directly proving possession of private keys. Again this can be done with varying degrees of sophistication. In the simplest case, Alice signs a mutually-agreed on message with every private-key for every address. (Note the message must be generated carefully such that neither side can 100% control its contents or predict the outcome. Otherwise Alice can reuse ancient signatures from the past as current proof, or Bob can use the opportunity to sign a valid bitcoin transactions that takes away the funds.) It also means Alice has to also disclose the constituent public-keys that make up each address. Recall that the Bitcoin address is constructed as a one-way hash of keys or complex scripts containing keys; without knowledge of that original construction, Bob can not confirm the mapping between public-keys and bitcoin addresses associated with his funds.

One advantage of this approach is that the proof takes place entirely between Alice and Bob; there is no publicly visible trace on the blockchain, no transaction fees or other overhead that would limit how frequently it can be performed.

Cryptographic techniques exist for further refining the idea. For example, it can be made more efficient by using a single signature to prove possession of multiple ECDSA keys at once. This is done by synthesizing a single public-key as the linear combination of multiple keys— although such protocols are not compatible with commonly available cryptographic hardware. Or going in the direction of increased deniability, Alice can use interactive zero-knowledge proofs instead of a signature to prove that she has control of specific keys, without giving Bob any record that he could use to convince someone else that Alice controls those keys.

Scaling this out to multiple customers creates additional pitfalls. For example, if Alice has the same arrangement with both Bob and Carol for custodying funds, there is a new way to cheat the proof. A single address can be used to convince both Bob and Carol that their money is still under the control of the custodian, even though the funds are being double-counted towards both customers. (Especially when using approach #2 above, which creates no visible traces on the blockchain. Using #1 would alert another customer that an address allegedly reserved for their exclusive use is appearing in transactions they did not authorize.) A simple solution here is for Bob and Carol to require that their dedicated addresses always start out with zero balance and only count funds they themselves deposit to that address as part of their balance. In other words, Alice is not allowed to shuffle funds by herself and declare a pre-loaded address as reserved for Bob.

If the scenario described above could be scaled indefinitely from Bob & Carol to encompass thousands of customer, the proof of funds protocol could likewise be scaled linearly without issues. The challenge is that not all cryptocurrency storage scenarios can leverage unique addresses. This will be the subject of the next post.

[continued]

CP

 

The economic security of blockchains— lessons from Ethereum Classic (part III)

[continued from part II]

Impact of KYC on exchange risk

Among those commenting on the incident, it did not escape notice that the Gate.IO, the exchange targeted in the attack, does not perform full identity verification on their customers. Given that this is one of the more controversial subjects in the cryptocurrency system, it’s worth exploring potential causal links between existence of KYC requirements and risk profile against attacks from customers. Looking back at the modus operandi for the attack discussed in the previous post and implemented in real-life against Ethereum Classic, one of the implications is that the perpetrator must be able to conduct trades on the targeted cryptocurrency exchange. So there exists some business relationship between the attacker and victim, and presumably some due diligence conducted by the exchange prior to accepting this person as customer. But the extent of that relationship and any recourse the exchange may have against fraudulent behavior on the part of the customer— surely double-spending violated some clause in the terms of use?— varies between exchanges.

On the one hand, there are exchanges that comply with Know Your Customer (KYC) regulations, with stringent identity validation prior to on-boarding customer. For online businesses without bricks-and-mortar presence, that usually involves uploading a picture of government-issued identity such as a passport or driver’s license, linking to existing bank accounts (effectively leveraging KYC work done by those institutions, which can usually perform strong, in-person validation at one of their bricks-and-mortar branches) and providing proof of residential address. They can also limit service based on the jurisdiction the customer is domiciled in, selectively turning away customers located in states or countries outside established areas of operation. On the other extreme are exchanges that require no proof of real-world identity and accept customers from anywhere in the world. Commonly those businesses can not accept fiat transfers since reputable financial institutions subject to KYC regulations are unwilling to act as  money transmitters for other institutions not bound by similar standards.

There are three plausible ways implementing KYC can reduce the counter-party risk an exchange faces from its own customers:

  1. As a deterrent. It’s common sense that people are less willing to commit fraud when their true identity is attached to that activity. Even for those undeterred by the prospect of living with a criminal record, identity verification can protect other exchanges from repeat offenders, since they can check criminal records before accepting a customer.
  2. As a tactical barrier to exploitation. Suppose some vulnerability exists in the way an exchange processes cryptocurrency transactions. (Concrete example: this subtle vulnerability from March 2018 related to how Parity represented partially reverted Ethereum transactions, confusing an exchange into accepting phantom deposits.) An attacker with knowledge of that vulnerability still could not exploit it for personal gain unless they were already authorized to trade on the exchange after having completed all of the ID verification requirements. This is a weaker argument, since it assumes that on-boarding is onerous and slow enough that it will delay the attacker enough to give the exchange an edge in the race to independently discover and patch the vulnerability. Considering that such delays also prevent the acquisition of legitimate customers, relying on the difficulty of on-boarding as a security measure makes no business sense.
  3. As an avenue for recovery. Knowing the identity of perpetrator, an exchange can go after them in court to recoup losses. This is probably the least convincing argument. Litigation is slow and expensive, with no guarantee that the attacker will have assets to compensate for damages even if the court does find in favor of the plaintiff.

Counter-arguments: the limits of identity verification

Does that theory hold up in real life? Gate.IO appears to fall somewhere along the middle of the spectrum. Support documents suggest the exchange permits trading & withdrawals up to some threshold out of the gate, but raising those limits requires a verified account. This is in the spirit of risk management: assuming those thresholds are chosen wisely, the exchange incurs some small risk of loss from random customers while having some assurance of the real-world identity of those engaged in larger transactions.

As of this writing, Gate.IO has not disclosed whether the alleged perpetrator had a verified account. One unexpected twist in the story is that the attacker has agreed to return at least some of their ill-gotten gains. It is unclear if this is the magnanimous gesture of a conscientious white-hat hacker who had only perpetrated the attack to make a point about blockchain security (as portrayed in some press accounts) or because they had a drastic change of heart after Gate.IO lawyers served them a nastygram, perhaps with a reminder about how much the exchange knows about them. But there are at least two a priori reasons to be skeptical about KYC measures alone being sufficient to mitigate these risks.

  • Identity theft. Deterrence only works if the attackers are worried about their own identity getting linked to fraudulent activity. But even the most stringent verification procedures are not 100% reliable. Given a robust underground market in stolen identities— complete with pictures of driver’s licenses, social security numbers and credentials to bank accounts— determined criminals could pass all customer verification requirements without placing their own identity at risk.
  • Account hijacking. Even if KYC procedures were perfected to yield zero false-positives, that does not eliminate another possibility: verified accounts can be hijacked after the fact. The legitimate owner of the account could unwittingly surrender their credentials to an attacker. (Note that commonly deployed 2FA schemes have no effect on phishing. Even with hardware tokens which are not susceptible to phishing, malware running on the user device can take over an existing session post-authentication.) This creates an unusual imbalance of incentives. Consider a dormant account that has been through KYC verification, but is otherwise unused, with no funds on deposit. There is very little at stake for that person from a breach of their account. But if the exchange places implicit trust in that account because of its KYC status, for example by raising limits on trading/withdrawals, the account becomes valuable for an attacker in a position to exploit that trust. Seen from another perspective, the account can do a lot more damage to the exchange than one can reasonably expect to recoup from the legitimate owner. Suppose Gate.IO had been exploited through a compromised account. As before, the legitimate customer who owns the accounts receives a nastygram from attorneys, demanding a return of the double-spent Ethereum Classic. Only this time the customer throws up their hands and says in effect, it was not them taking those actions, but some third-party who hijacked their account. If those statements can be corroborated (perhaps they have an alibi or logs show the relevant activity looks different than legitimate traffic from the same customer) it leaves the exchange with few good options. They can pursue the customer for negligence in failing to protect their own account but it is difficult to fault someone for not defending an account which had very little economic value for that individual.

These limitations suggest that strict KYC requirements can at best thwart opportunistic attacks. An adversary armed with one exploit, looking for any vulnerable target to cash-in quickly— recall that our Ethereum Classic double-spend attacker could have gone after any exchange with ETC/BTC order book— will prefer the path of least resistance among multiple targets. More determined attackers can take their time with target selection and prepare the battlefield by getting access to legitimate accounts at their preferred target.

CP

 

The economic security of blockchains— lessons from Ethereum Classic (part II)

[continued from part I]

Attacks and counter-attacks

At least one commentator suggested that affected exchanges immediately respond with a counter-attack, mining with overpowering hash rate on the original chain to undo the revisionist rewrite. Why would an exchange be motivated to behave this way? Because the cost of temporarily renting 51% hash-power to conduct another long reorganization is presumably much lower than the expected loss. This is an argument from symmetry: the attacker would not have bothered with the attack if their cost of mining the alternative chain was not outweighed by the benefits of swindling the exchange. At one level, this is damage control: by spending a small amount carrying out a successful 51% counter-attack, the exchange averts the higher loss it would otherwise incur if the double-spend is successful. At a deeper level, the strategy is intended as deterrence for future attackers. Assuming a successful counter-attack undoing the original chain reorganization, both the attacker and the exchange are in the red with nothing to show for it. The perpetrators wasted money on a short-lived 51% attack while the defenders wasted an approximately equal amount on reverting that. While the attacker can try again, so can the defender resulting in a game-theoretical stalemate. But that theoretical model suffers from two problems:

  • Assumption that costs are symmetrical. That defender can achieve 51% hash-rate at the same price as the attacker. There are many ways that can fail, the most obvious being one where the attacker is not merely renting hash power from an open market but is in possession of mining hardware, bringing down their costs. Second, even if both parties are bidding for hash power in a market such as NiceHash, the first mover may have an advantage: once demand for hash power for a particular PoW function increases, the next buyer may have to bid higher to achieve the same concentration.
  • More important, this model assumes that the perpetrator and targeted exchange are the only parties with a stake in the reorganization battle. Consider a different attack strategy: instead of simply sending funds back to herself on the alternative chain, Alice instead sends them to another exchange and carries out a second double-spend attack following the same modus operandi: convert all deposits into another cryptocurrency and withdraw those proceeds immediately. At this point, Alice does not care which version of blockchain history wins out. The two exchanges can duke it out all day long by orchestrating their 51% attacks & counter-attacks against each other; Alice comes out ahead in all cases. Even the exchanges cooperating will not change that: at best they can settle for some equitable distribution of losses. (There is one way for the second target to avoid this situation: halt processing of deposits if there is a “deep” blockchain reorganization observed.)

Parallels with ACH fraud: the original double-spend

This situation has interesting parallels with a far more mundane, low-tech type of fraud targeting cryptocurrency businesses: the reversible nature of most fiat transfers. Consider the ACH Network for transferring funds. Suppose a customer initiates an ACH transfer of US dollars to an exchange account and uses those funds to purchase bitcoin. The withdrawal of that bitcoin to a personal wallet is irreversible; once the transaction is mined and confirmed, it is not possible for the exchange to claw-back those funds. (Short of organizing a 51% attack— you can see where this is going.) Surprisingly the incoming ACH deposit is far from being cast in stone: consumer protection laws in the US give account holders several weeks to contact their bank and dispute transactions.

That means a dishonest consumer can in fact reverse the ACH transfer to keep their USD, while walking away with the bitcoin purchased using those same funds. This is effectively double-spending of fiat currency: eating your (USD) cake and having it (back) at the same time. The root-cause is a mismatch between the settlement characteristics of two disparate payment systems: ACH transfers are reversible, or more accurately take on the order of months to “confirm” due to generous 60-day dispute window, while Bitcoin transactions are cast in stone in a matter of hours. When processing incoming ACH transfers and allowing customers to trade using those funds, the exchanges must manage the counter-party risk associated with the reversal of fiat deposits.

What if we replace ACH by another cryptocurrency? It would appear these opportunities to claw back funds disappear because transactions would become irreversible on both sides, with no opportunity for the customer to “reverse” their deposit while walking away with the withdrawal. But as the ETC incident demonstrates, reversibility is a matter of degree: transaction are “final” only to the extent that a deep-enough blockchain reorganization can not rewrite history with an alternative version of events. In one sense, blockchains are more fragile than wire transfers— which can not be unilaterally recalled— or even ACH which has a finite duration for disputes. Given enough mining power, blockchain history can be reverted going back an arbitrary length of time. (On the other hand, ACH and wire transfers are still vulnerable to a different class of “attacker:” lawyers wielding briefs.)

Confirmation times reconsidered

Conventional wisdom holds that blockchain transactions are “safe” as long as participants wait a fixed number of blocks before acting on the outcomes, dependent on the particular economic characteristic of the blockchain. For Bitcoin this magic number has historically hovered between three and six, with an ongoing game of brinkmanship to streamline user experience by creeping closer to zero confirmations. These are motivated by statistical models calculating the likelihood that some transaction may be reversed, given an adversary controlling some percent of hash-power less than 50%. While that may well be the relevant threat model for Bitcoin, less-competitive blockchains have to contend with a different question: what if the adversary can temporarily achieve majority power? Temporary being the operative keyword: while all bets are off with permanent 51% control, even short-lived spikes allow targeted attacks to profit by double-spending some recent transaction.

In this model, the number of confirmations required can not be a magic constant. It depends on the value-at-risk: the notional value of the transaction. Buying a cup of coffee with a small number of confirmations on Ethereum Classic (not that ETC ever aspired to being a realistic alternative for retail payments) is still perfectly reasonable, even in the aftermath of the recent ETC incident. Large amounts on the other hand will require more careful risk management strategies, such as increased confirmation depths, gradually crediting the deposit over time as more blocks are confirmed instead of all at once, requiring additional funds as collateral or placing withdrawal restrictions. For example, a customer could be credited with the full amount of the deposit for trading purposes, but not permitted to withdraw the proceeds from those trades until additional time has elapsed to guard against chain reorganizations.

[continued]

CP

 

The economic security of blockchains: lessons from the Ethereum Classic attack (part I)

In early January, the Ethereum Classic blockchain experienced double-spend attacks created by deep reorganizations of the blockchain. While the perpetrators’ identity remains a mystery— although research from SlowMist suggests that exchanges involved in the incident may have additional information for locating them— there is enough information about the attack to draw general conclusions about the modus operandi and implications for other blockchains. This event has upended core assumptions made in previous economic analysis of blockchain security, defined as the cost/benefit calculus for mounting successful attacks against the integrity of the ledger.

Double-spending in the abstract

In one sense, there is nothing surprising or novel about the attack vector. The vulnerability of blockchains to hijacking by overwhelming mining power had always been acknowledged, even in the original Bitcoin paper by Satoshi. Such attacks have even been observed on other alt-coins in the wild, most notably Bitcoin Gold in May 2018. To recap how such a double-spending attack works in the abstract using the standard cast of cryptographic characters:

  1. Alice and Bob agree to trade using cryptocurrency.
  2. Alice pays Bob by broadcasting a transaction on the Ethereum Classic (ETC) blockchain
  3. Bob waits until this transaction has been “mined” and confirmed, getting buried several blocks deep in the chain history
  4. After the transaction is confirmed, Bob in return supplied Alice with a product or service, such as shipping her a painting or even giving her a bundle of USD cash.
  5. Unbeknownst to Bob at this stage, Alice had been secretly mining an alternative history of the ETC blockchain, with more hash-power than all other miners combined. In this parallel universe, the transaction sending ETC from Alice → Bob never happened.
  6. Given that Alice commands a majority of the hash rate on the network (so-called “51% attack”) her alternative chain will eventually catch up and overtake the existing chain, measured in terms of the objective metric used by all participating nodes to pick a winner among competing histories.
  7. When the blockchain “snaps” to this alternative version created by Alice, Bob no longer has possession of the ETC funds he believed Alice had sent; that transfer has effectively been erased from history.
  8. Alice meanwhile still has the cash Bob provided in exchange, in addition to her original ETC funds.

There is one technicality here: as stated, the transaction broadcast in step #5 would still be valid on the new, revisionist history orchestrated by Alice. That means Bob could try broadcasting it again, after Alice stops mining new blocks and control of the network reverts back to honest miners. To lock in the theft for good, Alice would include another transaction in her version of events to break compatibility. Even a seeming useless transaction sending the same funds back to herself (Alice → Alice) will do the trick; although, the scenario gets more interesting if the same funds are used for another third-party transaction, as we will shortly see. That is the origin of the slightly confusing term double-spending, since the same money is seemingly being used twice. Even though any single version of blockchain history only allows single spending, by creating temporary confusion about what the “true” version of history is, Alice convinces different people at different times that the funds are theirs.

Attacker perspective: ideal targets

Is this attack feasible? It depends on the relative cost of achieving 51% of hash-rate “temporarily,” compared to the expected benefits measured by the value of the goods/services purchased without having to fork over any Ethereum Classic. Hash-rate costs are subject to complex dynamics, involving the specific design of the proof-of-work function used in a blockchain and available spare capacity up for grabs for the higher-bidder on markets such as NiceHash. But assuming an attacker can assemble enough fire-power to revise blockchain history, there is a natural choice of target to go after, a stand-in for the character “Bob:” cryptocurrency exchanges. Alice can deposit ETC on an exchange, trade that to a different cryptocurrency such as Bitcoin (BTC) and withdraw BTC. Note that the 51% attack on ETC chain has no effect on BTC, short of any general market unease caused by an unrelated coin being attacker. (In fairness, there is strong correlation across different cryptocurrencies and past events such as the Ethereum DAO debacle have caused broad declines across the market, even in asset classes having nothing to do with buggy smart-contracts.) The attacker gets to keep the Bitcoin, while the exchange is out of ETC after the deposit is reversed. There is no doubt an interesting legal question here on whether the exchange will eat the loss or if those losses can somehow be passed on to counter-parties involved in the BTC/ETC trade. But that is immaterial for our purposes: the bottom line is that someone has been scammed.

This is the exact playbook observed in the ETC double-spend attack. One of the primary targets has been identified as the exchange Gate.IO, with the attackers converting the proceeds to bitcoin for withdrawal. To the extent there is any element of surprise here, is the fact that such an attack could involve a relatively major currency in the top 20 by market capitalization. It is one thing to prey on Bitcoin Gold or some other thinly-traded altcoin with negligible hash rate. It is another level of capability to amass enough hash-rate to overpower Ethereum Classic, with the unspoken question: which other cryptocurrencies are vulnerable to copy-cat attacks?

Wrong assumptions about costs and benefits

The existence of economic limits to the security of blockchains is not exactly news. It is an accepted risk that Bond villains with unbounded resources can amass sufficient hash-power to overwhelm any blockchain. Without disputing this fact, the standard response to these arguments has been around economic incentives: why would an attacker spend that much money if they can not recoup even greater value by carrying out the attack? Putting aside the fact that this is not an entirely comforting answer— some “attackers” may be motivated by ideology, with the standard example being governments willing to sabotage public blockchains for the greater cause of enforcing capital controls, even when that undertaking would be extraordinarily costly— it leads down the rabbit hole measuring costs and benefits.

Notable, this attack on ETC debunked two premises that go into these models:

  1. Attacker costs include devaluation of their own holdings. It has been an article of faith that miners would not collude to execute a 51% attack because doing so would lead to decrease of confidence in the currency, resulting in the notional value of their own mining rewards going down. In effect, 51% attacks are treated as short-sighted move that may temporarily boost returns but only at the cost of much greater losses down the road. This was rooted in an implicit assumption that perpetrators of the attack are still wedded to that particular cryptocurrency— after all, Alice in the example above is still holding ETC after her double-spend attack has been successfully executed. But the presence of public cryptocurrency exchanges with high liquidity in their order books voids that assumption. Alice can wash her hands clean of ETC, fully cashing out all of her holdings to some other cryptocurrency with nary a care for how far ETC plunges in the aftermath.
  2. Attacker costs also include the depreciation of their specialized mining equipment, which has zero value for any application except mining that specific cryptocurrency. Because the most efficient way to mine Bitcoin involves highly-specialized ASIC hardware that is useless outside that specialized application, the perceived “cost” for an attacker mounting 51% attacks would include both capital expenses to acquire those rigs and more subtly, depreciation for the equipment caused by decline in currency price. Recall that if the price of Bitcoin goes down and mining rigs are good for nothing besides producing more Bitcoin, the expected value provided by a rig over its lifetime also takes a dive. This may have been a reasonable assumption when Bitcoin was the only game in town. Today there are hundreds of alt-coins, including several “families” sharing the same proof-of-work function: mining rigs built for Bitcoin can be diverted to also mine Bitcoin Cash/Gold/Diamond/Tin/Scrap-Metal/etc.**

[continued]

CP

** The last two remain hypothetical at the time of writing, but can not be ruled out if forks continue to create value out of thin air.

Proof of nothing: why the January proof-of-keys ritual missed the mark

[Full disclosure: this blogger was formerly CSO for a cryptocurrency exchange.]

Imagine a country where confidence in the banking system has reached a nadir among the citizenry: no regulatory oversight, no lending standards, no requirement for public audits and no FDIC insurance to serve as backstop in the event of bank failure. Instead  consumers a coalition of consumers decide to take matters into their own hands with a grassroots campaign to verify the solvency of banks. How? By orchestrating a bank-run. Everyone is instructed to take out all of their money out of banks on the same day and deposit them back at a later time after observing to their satisfaction that all withdrawals have been processed successfully.

This is not an entirely far-fetched analogy for what happened in the cryptocurrency space earlier this month with the Proof of Keys event. There are of course key differences, no pun intended. Traditional banks operate a fractional reserve by design. It is no secret they would experience a liquidity problem if all customers showed up to demand 100% of their deposits at the same time, as epitomized in the bank-run scene from It’s a Wonderful Life. But cryptocurrency businesses operate under a different expectation, namely that they retain full custody of customer deposits at all times. No lending, no proprietary trading, not even parking those funds at an interest-bearing account offered by another financial institution lest it create counter-party risk. So on the face of it, there is some value to this withdraw & redeposit ritual: a custodian successfully satisfying every withdrawal was provably in possession of those customer funds.

But the reasoning is flawed for several reasons.

First, participation is voluntary. Even with viral propagation on social media and decent coverage in press outlets dedicated to cryptocurrency, only a small fraction of users representing an even smaller fraction of total funds will participate. (It is easier for retail investors to participate, compared to an institution such as hedge-fund. The latter typically have more stringent requirements around alternative places to keep funds. An off-the-shelf hardware wallet is an adequate solution for storing personal funds; it is a far cry from enterprise-grade storage with redundancy and multiple users for an institution.) While exact numbers are not available, mining fees and memory pool pressure statistics can be used as a gauge of participation. Assuming only 10% of funds were withdrawn from a given exchange, the campaign has only proven that at least 10% of funds are there.

Screen Shot 2019-01-03 at 6.18.53 PM.png

Zooming on mempool state on January 3rd shows a temporary spike, coinciding with morning hours in PST.

Screen Shot 2019-01-17 at 10.57.22 PM.png

Looking at 30-day view paints a different picture. There is nothing remarkable about the transaction volume or fees on January 3rd.

Second, pre-announcing a bank-run ahead of time somewhat defeats the point. It’s not a pop-quiz if the teacher announces that there will be a pop-quiz next Friday. Given enough advance warning, even custodians who were actively investing their deposits can convert all of the capital back to the expected currency.

Finally there is a more subtle reason why this stress-test for custodians fails: it is first and foremost a test of liquidity instead of solvency. In other words, it is subject to false negatives where even a cryptocurrency custodians with 100% of funds on deposit could fail to produce every last satoshi on demand, for a very good reason. Sound risk management for cryptocurrency dictates storing the majority of funds offline, in cold storage. By definition these systems are disconnected from the Internet and require manual steps—such as travel to an offsite location—to effect a withdrawal. Only a small fraction of funds are kept “online” in hot wallets, where they are instantly accessible for satisfying withdrawal requests.

This model is similar to how traditional banks manage cash. Even within a single branch, only a fraction of the cash present at that branch is loaded into the ATM. The remainder would be kept in an interior vault within the branch. Banknotes stuffed into the ATM are available 24/7 for customers to withdraw but also come with a downside: they are subject to heightened risk of theft. Blowing up an ATM or towing it away is easier than breaking into a steel vault. By keeping only sufficient money in the ATM to satisfy expected withdrawal volume, the bank manages its exposure while providing high degree of assurance that customers will have access to their funds. As long as projected liquidity requirements are not too far off the actual observed demand from customers— in other words, barring unexpected events that result in everyone rushing to the ATM at once—this is a good trade-off between security and liquidity.

Cryptocurrency custodians employ a similar strategy for managing the exposure of hot-wallets. If deposits exceeds withdrawals and there is a net influx of funds, the wallet may start running too “hot.” Excess risk is trimmed by sending funds to an offline wallet. Since the transfer is initiated from an online wallet accessible over a network, this step is easy. On the other hand, if withdrawals outpace deposits and there is a net outflow, the system risks running into a liquidity problem and must be replenished by moving funds back from an offline wallet. This step is more time consuming. By design, access to offline wallets is available from the same system operating the hot wallet; otherwise they would be subject to same risks as the lower-lower-assurance system.

Returning to the conceptual problem with the DIY proof-of-solvency, if enough customers actually participate in a coordinated effort to withdraw their funds at the same time, hot-wallets will bottom out and cease to provide liquidity until they are replenished from offline wallets. (Granted, knowing when the stress-test will occur creates additional options to prep. For example the custodian can deliberately bias the wallet distribution to maintain higher-than-usual fraction of funds online.) That means events such as January 3rd are not so much a proof of solvency as they are a proof of available hot-wallet liquidity or perhaps time-trial of how fast the custodian can access offline storage systems. The paradoxical part is that in any system with online/offline separation managed according to risk criteria, some delay in processing withdrawals would be fully expected. If anything, it is a bad sign if the custodian can instantly produce 100% of all funds on short notice. It means they are likely keeping 100% of cryptocurrency online in a hot-wallet, where they are most susceptible to theft. Ask Bitfinex how that turned out in 2016.

To be clear: this is not to trivialize security concerns with storage of cryptocurrency. Given that internal workings of exchanges and custodians remain opaque to most customers, it is completely reasonable to demand periodic assurance that funds deposited with are still accounted for. Considering that proof-of-keys suffers from conceptual flaws and indeed accomplished very little this time around (judging by observed withdrawal volume) the question becomes: what is an effective way for custodians to verify that a custodian is still in possession of their cryptocurrency deposits? A future blog post will look at some alternatives.

CP

Payment networks, subset-sums and tracking consumer spending

(No cause for alarm, for the most part)

A recent Bloomberg article featured a glowing portrayal of the retail analytics company Cardlytics. Readers may forgiven for assuming this outfit had found the magical solution for tracking consumer spending from payment data alone, which had eluded all other attempts. Cue in cheers from hungry-advertisers and consternation from privacy advocates? Not exactly. What the article neglects to mention is that the company has no access to line-level purchase data. In other words, there is no new source of information here. Nothing new that is not already visible to Visa or MasterCard, or for that matter the bank that issued the credit-card. The “innovation,” assuming one exists, lies in better ways of crunching the existing stash of information that payment networks & banks are already sitting on. The implication being that wealth of information was sitting under-utilized, either because they have not gotten around to it, are contractually prevented from engaging in such data mining— unlikely, given that privacy has never been a forte in the payments industry— or more likely, because they lack in-house technical expertise for it.

To better explain this distinction, let’s recap how a payment network such as Visa operates. Suppose a consumer uses their Chase Visa card to buy a cup of coffee from the neighborhood deli. There are three critical participants in the loop facilitating that transaction:

  • Issuer: the bank that gave the credit-card to the consumer. For example, for a Chase Visa, this would be Chase bank.
  • Acquirer: the bank where the merchant has an account
  • The payment network, in this case Visa. This is the network, both in the metaphorical sense of being a densely connected graph between issuers and acquirers, as well as an actual communication network over which payment requests and authorizations are routed.

(This is a simplification; there are many participants all vying for a cut of the transaction, with the most notable ones being payment processors who assist merchants in getting setup to accept credit-cards, often as part of a bundle that includes providing the point-of-sale hardware.)

From a privacy perspective what matters is that each transaction originating at the merchant is routed through the Visa network and must be authorized by the issuing bank. After all, it is Chase bank that gets to decide whether customer Bob is authorized to spend $2345 on a new TV at BestBuy. That decision must take into account several factors, starting with whether Bob has sufficient spending limit left on that card. There is also the minor matter of verifying this purchase is indeed initiated by Bob, as opposed to a fraudulent charge resulting from a stolen card for example. That means the issuing bank knows the purchase amount and merchant ID— so does Visa, which is responsible for relaying the payment request to the issuer and ferrying back the thumbs up/down response for payment authorization.

Of course there is nothing new here. This is how payment networks have always operated. A corollary is that they become unwitting witnesses to consumer spending patterns in a global way. They have global visibility. By contract, merchants have local visibility: BestBuy is aware of every transaction a particular customer conducts at every BestBuy location over time. (There is some ambiguity around whether they are contractually permitted to use the payment card itself as a fixed identifier to correlate such purchases; card numbers are static for the lifetime of the card and more importantly include card-holder name which is likely constant across multiple cards even as they are replaced.) But that visibility ends as soon as the consumer steps outside the store. BestBuy has no idea what the same customer does next door over at Home Depot. Chase Bank on the other hand does, since they can observe the same credit-card being used at both locations. A card network such as Visa or MasterCard does Chase even one better: they can see all transactions across all merchants for that card type.

Again there is no mystery that this information is being collected or mined for patterns— in fact, that is how fraudulent transactions are detected. Issuing banks are on the lookout for red flags: such as the teetotaler racking up large tabs at bars or that card-holder who never leaves Poughkeepsie jet-setting around the Caribbean. What is new is that instead of being used in a defensive manner for combatting fraud within the payment ecosystem, this data is now mined to identify new revenue streams by directly working with merchants to market to consumers according to spending profiles.

But there is one major limitation of this model that companies including Cardlytics have yet to overcome: they have no visibility into so-called line-level purchase information. In other words, all they can observe is the total amount at the bottom of the receipt. They have no visibility into the contents of a shopping cart or itemized list of drinks on the bar tab— information that the merchant knows but is never transmitted as part of the payment authorization protocol. Line-level receipt information has been the Holy Grail of companies that harvest and traffic in consumers spending data. Much to the chagrin of eager startups partnering with banks for access to payment network flows, they are still not any closer to that stash, which remains carefully guarded by merchants.

To be clear, this is not to minimize the privacy risks. On the contrary, merchant IDs and amounts alone can be extremely revealing— and damaging. BestBuy may sound like a saccharine example but consider other merchants that accept credit cards: charitable organizations, treatment facilities specializing in rare conditions and controversial advocacy groups (Nickelback fan-club anyone?) In each case, the existence alone of a purchase amounts to metadata about the card-holder hinting at everything from political persuasion to medical conditions. In other cases, amounts and frequency or purchases can be telling: consider transactions involving liquor stores or casinos. Depending on who gets to make judgements based on data, historic patterns can mean the difference between casual interest and dangerous levels of attachment.

Finally there is an interesting edge case that may be already exploited in the wild: in certain cases one can work backwards from the total amount to line-level data. Consider a store that only offers four items:

 

Widget Price
A $2.48
B $5.49
C $8.75
D $14.99

Given that pricing structure, if the cash-register rings up a customer for $11.23— recall this is the only number Visa, issuing-bank and whoever they are willing to share the data with can observe— there is only one possible combination of widgets the customer could have purchased: A and C. There is no other way to create a basket of goods summing up to that price.

This idea “reverse engineering” shopping cart contents from total amount and individual prices is related to a well-known problem in computer science. It is a variant of the subset-sum problem. In the strict version of subset-sum problem, items can not be repeated. In the retail settings of course customers can buy multiple copies of the same item. It turns out that tweak does not appreciably alter the fundamental difficulty of the problem— and solving subset-sum is very difficult in a well-defined computational sense. It ranks among the group of NP-complete problems for which there are no  known efficient algorithms for solving large instances. Worse it is conjectured that no efficient algorithm exists. The “state of the art” exact solutions are barely faster than exhaustively checking all possible combinations of items, which does not scale to large instances of the problem where the menu contains not four, but dozens of different widgets available for purchase. Efficient approximation algorithms are known for many NP-complete problems but close-enough is not good enough in the context of inferring customer spending. If the algorithms returns an alleged shopping-cart but its contents do not add up to the exact purchase price, it is not the right cart; there is no reason to believe the customer bought any of them. 

Are retail analytics companies working to solve subset sums to recover line-level purchase information? This is unlikely for several reasons, even if they were willing to throw large amounts of CPU time at the problem. This approach can only provide a “unique” solution on a menu with a small number of discrete items, each with unique price. As soon as any of these conditions are violated, there is no unique solution. For example if variable quantities are allowed— as in a grocery store where fruits and vegetables are priced by the pound— any amount can be attributed to say bananas alone. Similarly, if there are two items with the same price, they become indistinguishable. Even if every item has a distinct price individually, because the possible combinations increase exponentially with the number of items, there is no guarantee that they will remain free of “collisions:” two completely distinct basket of goods ends up with same total cost, down to the penny. Finally, assuming the pricing ambiguity could be tamed, there is a practical problem around sourcing accurate information: the data-mining operation must have exact pricing information from thousands of merchants, staying on top of variables such as geographic location (state & local taxes that increase the final sales amount) seasonal fluctuations and daily promotions that one particular outlet may decide to implement. Achieving any semblance of accuracy for that information would require cooperation by the merchant. But if one posits that merchants will be complicit in helping mine customer transactions by sharing information with a third-party, there is no need for solving subset-sum instances any longer.  One may as well ask the merchant “what was in the shopping cart for that customer who bought $84.25 worth of groceries at 17:34EST?”

That scenario could ratchet up the privacy risks an order of magnitude. Until now, merchants have treated purchase data as a highly valuable asset, guarded jealously and only used internally to boost the health of this business. It is not up for grabs by third-party analytics services focusing on identifying global patterns to be monetized elsewhere. Even if that service could do a better job of crunching the data provided by one merchant, the end result may well end up benefiting their competitor instead. If incentives shift to the point that merchants are collectively throwing their own stash of consumer spending patterns into a single pile, it would spell trouble for privacy.

CP

On the limits of decentralized exchanges

[Full disclosure: this author works on security for a cryptocurrency exchange]

Decentralized or non-custodial exchanges are one of the areas of active research and development in cryptocurrency. The key differentiator— no pun intended— is that the exchange does not take temporary possession of customer funds in order to enable trading. By contrast, the prevalent model for exchanges today only supports trading of assets that customers have already deposited on the exchange. To make this more concrete, let’s say Alice wants to buy 1 bitcoin for $6000 USD— using recent prices, which are bound to date this blog post. She wires $6000 to the exchange and places a buy order. Bob meanwhile is looking to liquidate his 1BTC position, coincidentally at the same $6000 price point. He deposits the bitcoin with the exchange and places the corresponding sell order. These orders “cross” on the trading engine, and the exchange updates its internal ledger to swap assets between these customers, minus any fees for the exchange. Critics like point to out these two limitations to this model:

  • Assets are tied up temporarily even when they are not being put to use for trading. If a better opportunity were to emerge for putting that bitcoin to use, it may take some time to recover it. (The situation is worse for fiat; consider the challenge of sending funds during a bank holiday.)
  • Customers must trust the exchange with their funds, which are subject to risks of insider malfeasance and external attacks.

Non-custodial exchanges seek to address these problems by foregoing the requirement to park funds as a prerequisite to trading. Before delving into the comparative strengths and weaknesses of this model, let’s pause to clarify the definition of what counts as an “exchange.”

An exchange is not a glorified bulletin-board

An abstract requirement for an exchange is to enable price discovery. In other words, the state of order books on the exchange must reflect true supply/demand conditions for the underlying asset. If one bitcoin is being offered for $8000 and a seller comes along willing to buy at that price, that trade must execute. If the seller has an option to back out of trades after they are matched, then the posted bids/offers are pieces of fiction that are no longer indicative of market conditions. (This is not to be confused with the ability to cancel orders or even the much maligned practice of high-frequency trading where orders are posted and retracted quickly. The point applies only during the time an order is posted on the book, even if those times are measured in milliseconds. Once another order crosses that, that trade must execute with overwhelming probability, with each side ending up with the assets on offer by their counter-party. That execution can not depend on the willingness of buyer/seller to further cooperate. Otherwise one side will always have an excuse to back-out as soon as market conditions shift, inspiring a bout of buyer’s remorse for not having taken a better deal. (Note this “guarantee” can be an economic incentive. For example, if any party who reneges on a trade is forced to pay significant penalties, that could be a sufficient deterrent for making sure most activity on the exchange settles uneventfully.)

That means services which only pair up buyers and sellers without providing any execution guarantees fall short of this definition of an exchange. Price signals on such a venue may well depart from true market valuations because there is no way to know in general if any assets are indeed changing hands at those prices. Even if the marketplace is continuing to observe participant activity following a trade (for example, by monitoring blockchains to see if funds claimed to be in the possession of the counter-parties were indeed moved) this is providing at best a delayed signal after the fact.

Beyond bidirectional channels

There is another “trivial” sense in which trading can be done without custody, at least for cryptocurrency assets. Instead of depositing funds ahead of time on the exchange and later allocating some fraction of those funds to open orders, the customer can instead create a bidirectional payment channel with the exchange. Suppose Bob has 5 bitcoin and plans to diversify some of that into ether and litecoin. Instead of depositing 5BTC all at once, he creates a channel with the exchange, with the commitment transaction funded entirely by Bob. When he wants to convert 1BTC into ether, he sends 1BTC to the exchange. If he also decides to convert another bitcoin into litecoin, the channel state is updated to now pay the exchange 2BTC, for the combined amount required to back both order. (Transaction fees are neglected in this simplified model.) If he were to change his mind and cancel the BTC/LTC order, the payment channel state is updated by revoking previous transactions and reverting to a new state where the exchange now only gets 1BTC, with the remaining 4 going back to Bob.

In this model, only the assets committed to open orders are in possession of the exchange, as opposed to the entire amount the customer has available for trading. It is in some ways similar to the daily settlement model common in equities trading: the customer opens a channel with the exchange prior to the opening of market, places/cancels any number of orders throughout the day and after close of market, the channel is “closed” to settle the balances. (Granted cryptocurrency trading takes place around the clock, without the sharply delineated “market hours” of traditional markets.)

While this reduces the proportion of assets tied up with an exchange or subject to security risk, it does not eliminate those risks entirely. For example, Bob still must trust the exchange that when his order executes on BTC/LTC,  he will receive the litecoin amount corresponding to his bitcoin offer. The natural question is whether one can design an exchange with stronger guarantees, where Bob parts with the bitcoin if and only if he will receive the stated amount in litecoin. In an ideal setting, that property would be enforced on chain, taking any trusted third-parties out of the equation. That may sound like a tall order, considering blockchains are self contained and have no awareness of the state of other blockchains. (There is an attempt to replicate the state of bitcoin on ethereum but it has not gotten very far.) On its face, that creates a challenge for making transactions conditional on each other, such as creating a dependency between Bob parting with assets on one chain only if he can recoup a precise amount of another asset class managed on a completely independent chain.

Atomic swaps

Atomic swaps— previously discussed here by comparison to the fair-exchange notion from traditional cryptography— provide a useful building block for doing pairwise exchange across chains. Returning to the problem of Alice and Bob executing a BTC/LTC swap:

  1. Alice prepares some bitcoin (in other words, an unspent transaction output or UTXO) with a specific script. This script allows either one of two paths for claiming the funds:
    • Using Alice’s key A after some time elapses, or
    • Using Bob’s key and knowledge of a preimage for the hash H=SHA256(R) where R is a random value Alice picks.
  2. Bob in turn prepares the corresponding amount of litecoin, using a script that mirrors the one Alice created for spending conditions:
    • Using Bob’s key after the same deadline, or
    • Using Alice’s key and knowledge of a preimage for the same SHA256 hash H. (Note that Bob does not know the random R solving that puzzle but he can copy H from the posted bitcoin transaction.)
  3. Alice proceeds to claim Bob’s litecoin by using her key and knowledge of R. In doing so, she will be revealing R.
  4. Bob in turn proceeds to claim Alice’s bitcoin using his key and the now disclosed answer to the preimage puzzle.

Limitations of atomic swaps

This primitive solves the basic problem of a pairwise trading between mutually distrusting parties, but there are a number of challenges to overcome before it can become a realistic alternative to traditional exchanges.  Let’s catalog these now.

Dealing with fiat

One of the glaring problems with atomic swaps is they operate on a blockchain. That means trading against fiat currencies such as the US dollar or euro can not be expressed using these conditions. There are two work-arounds offered for this approach, neither of which are satisfactory from the perspective of eliminating trusted third-parties.

First one introduces oracles to vouch for the fact that some event has occurred outside the blockchain, such as Bob wiring funds to Alice. This can be done generically by creating a multi-signature arrangement where the oracle must also sign the transaction before Bob can claim the bitcoin offered by Alice. Or in the context of ethereum it can be done by making payment conditional on a specific function call from the oracle contract. Either way this is introducing a trusted third-party into the equation and adding even greater delays to the settlement process, meaning that a trade that executes at a specific time will settle at a later point in time after the mediator had enough time to examine the evidence of fiat payment.

The second approach runs even more contrary to the spirit of avoiding trusted third- parties: using a stablecoin designed to have stable exchange rate tracking a specific fiat currency.  For example one could represent USD via Tether or other stablecoins. But the 1:1 correspondence between Tether and the dollar is only guaranteed by a private entity. In other words, by replacing USD in a bank account with tether for the convenience of applying atomic swaps, participants are taking on even greater concentration of risk in the single party backing tethers.

Scaling to an open market

Another challenge with atomic swaps is the pairwise aspect: the protocol has exactly two participants and operates in a carefully choreographed manner. Notice that even the very first step by Alice requires knowing that her counter-party is Bob, because his public-key goes into the construction of the initial UTXO. This is all good and well but it does raise one important question.

How did Alice and Bob find each other in the first place? Presumably this is the role the decentralized exchange plays. But if Alice must know about Bob, there is a chicken-and-egg problem. In the standard setting, Alice would post an order announcing that a certain quantity of bitcoin is available in exchange for a different quantity of ether. Later along comes Bob with an offer to take the other side of the trade, and this particular trade executes. But note that at the time Alice posted her order, there is no Bob in the picture. Also recall that it is not sufficient for our definition of an exchange to simply act as a bulletin-board where seller/buyers post bids and then go offline to attempt settlement  on their own when they paired with a counter-party. In the absence of additional enforcement to prevent participants from backing out of trades, this scheme can not guarantee that activity on the exchange corresponds to assets changing hands at those prices.

Secondly what prevents the participants from backing out of executing the atomic swap?  Recall that even with both transactions ready on chain, it is still up to Alice in step #3 to get the wheels moving. The protocol is only atomic to the extent that if Alice executes step #3, it is guaranteed Bob can also execute step #4. But there is no guarantee that after steps #1 and #2 are completed, Alice will proceed to step #3.

One approach to dealing with this is to have the exchange become a counter-party to every trade. In other words, when constructing the atomic swaps Alice always assumes she will be trading her BTC to the exchange for ETH. Likewise Bob assumes he is sending ETH for BTC when constructing the swap transactions. An atomic swap will work in this model since the identity of the buyer is known ahead of time; it is always the exchange. Meanwhile the exchange does not take on any risk in the event of a cross. Until there is a crossing order from Bob, the exchange will not move to claim BTC from Alice. Only when both orders appears on the book (and there is sufficient buffer left on the time-locks for both, to prevent the owner from reclaiming them) does it make sense to execute both swaps. Since funds from one are used to pay the other, the exchange is net neutral or even slightly ahead due to fees collected from the parties. By making sure the exchange is playing the role of “Alice” in the protocol and choosing the random nonce, the exchange can guarantee that step #3 will always take place and every crossed order will settle properly.

But there is a fatal problem with that approach: while it may be “neutral” in the sense that the exchange does not make directional bets on BTC/ETH, it still has to front funds to pair up with every order. Recall that both sides of an atomic swap must have an on-chain transaction that the counter-party can claim if the swap runs to completion successfully. That means for every order— no matter how unrealistic its chances of being filled given prevailing market conditions— the exchange is forced to set aside capital to guarantee execution. Suppose 1BTC is currently trading for 20ETH but a die-hard bitcoin fan wants to lodge an order to sell for 50ETH. In order to guarantee execution of that order, the exchange must set aside of 50ETH of its own capital for as long as this irrationally exuberant order stays on the book. That is not a viable model.

Partial execution

Theres is one more challenge to address when trying to build an exchange on atomic swaps: partial order execution. Using the previous example, suppose Alice is offering 1 BTC for $8000, while Bob and Carol each want to buy 1/2 BTC for $4000. There is perfect coincidence of wants here: Alice can sell her whole bitcoin and collect the USD she requested, by splitting that order evenly between Bob and Carol. Custodial trading engines handle this case without a problem, since they have full control of assets. More importantly they can pace the execution over time to deal with the far more likely scenario where the counter-parties appear at different times. Imagine Alice places her order, followed quickly by Bob while Carol does not materialize until a few hours have elapsed.

The basic atomic swap can not handle this scenario without additional involvement from the customer. This holds true even if the exchange itself is the counter-party to her swap. When there is only 1/2 BTC demand available, the exchange is in a bind: it can proceed with the swap with Alice for one whole BTC, but then it will be left holding the remaining 1/2 after Bob is paid. Demand for that half may not materialize at the same price, leaving the exchange holding the bag. Alice can always go back and prep a new transaction that sends two half BTC chunks to the exchange. (By using channels between Alice and the exchange, this can even be done offline without significant confirmation delays.) But therein lies the catch: Alice is free to back out of that transaction. On a custodial exchange, unless the order is placed as all-or-none, it will execute against any crossing order including partial lots. With swaps, one must track down Alice to restructure the transaction after every partial execution.

Looking ahead

These limitations do not preclude the possibility that different, more sophisticated protocols and cryptographic techniques could address the current limitations of decentralized exchanges. Instead they point to a scaling challenge with going from a protocol that works great in 1:1 setting to one that must function with large number of participants.  As things stand, non-custodial trading may eliminate the risk of funds storage, but the lack of an execution guarantee means that it greatly reduces confidence in the price signals generated by the market.

CP