Proof of funds for cryptocurrency custody: public verifiability (part IV)

[continued from part III]

Zero-knowledge proofs

Borrowing on a principle from blockchain ideologues that that trusted intermediaries introduce vulnerabilities, we can instead fallback on a purely cryptographic approach to constructing a proof of solvency. The first attempt at this in the literature dates to a paper from CCS 2015 introducing a scheme called Provisions. The authors independently tackle both sides of the accounting book.

• Liabilities are publicly made available as a set of cryptographic commitments, with one commitment for the each customer balance. Commitments are private in the sense that the number is not publicly visible, but it can be selectively disclosed. Each commitment is opened only for the specific customer, for example by emailing them with the information required to verify the committed value. This part effectively crowd-sources verification, by allowing every customer to confirm that their balance is represented accurately. More importantly, the commitment scheme uses a construction that also allows committing to a total balance which is verifiably equal to the sum of individual commitments. That figure represents the total amount of customer claims to cryptocurrency stored by the customer. While the proof implies a public commitment to the sum, that number is not publicly disclosed. As such the amount of assets under custody can remain confidential as a proprietary business metric.
• Proof of assets is done using zero-knowledge proofs, over a cover set that includes the actual custodian addresses as a proper subset. The main contribution of the paper is a provably secure protocol for doing that demonstration without disclosing specific addresses or for that matter total assets. True custodian addresses are obscured among a larger cover set, which could be all addresses on the blockchain if one wanted maximum privacy. The prover uses zero-knowledge proofs over the entire set to demonstrate that the smaller subset for which she knows the private keys— in other words, custodian keys— collectively have enough bitcoin balance to exceed the liabilities committed to in the first step. Again this proof is made public for anyone interested to verify.

Falling short of the goal

At a high level, this model certainly succeeds in removing trust in a third-party accounting firm, allowing anyone including those who have no business relationship with the custodian to verify its financial health. But looking closer at the paper reveals a number of limitations:

1. Proving that liabilities were represented accurately now depends on the diligence of individual customers. This is really the same problem faced by trusted third-party accountant  in a different disguise: ledger integrity. Only this time there is a fighting chance for discrepancies to be uncovered: each customer can verify if their own balance was represented accurately. So the assurance provided by this “proof” is only as good as customer diligence in validating the ledger. It remains an article of faith that such participation will materialize. (Much like the belief that open source software must be getting more secure over time, because if there were any vulnerabilities someone, somewhere looking at it surely would have said something.) Consider that the level of effort involved is non-trivial and involves running random software to verify the commitment.
2. Limitations in the protocol, most importantly the lack of support for multi-signature addresses. This is a deal-breaker in the current incarnation: if there are few things cryptocurrency community can agree on, one of them is that the additional security and redundancy provided by multisig addresses is crucial for risk management when dealing with large amounts. This limitation affects core functionality, not just privacy. Provisions can not be used if the custodian itself is using multisig addresses, even if every other address in the cover set were P2PKH. (In other words, even if we are willing to give up privacy by exposing P2SH custodian addresses among the P2PKH decoys.)
3. Compatibility with hardware wallets. There is a more subtle implementation problem with incorporating a Provision-type design into an existing cryptocurrency storage system. The zero-knowledge proofs require using private key material in non-standard constructions. By “non-standard” we do not mean that they are dangerous or incorrect, only that these are not garden variety algorithms such as ECDSA signature, ECDH key-exchange or ECIES encryption that are widely supported. This matters because of another tried-and-true risk management strategy: using dedicated cryptographic hardware to store high value keys. Off the shelf hardware such as PCs or phones are not ideal for keeping keys due to their large attack surface. Special purpose devices such as hardware-security modules, smart cards and USB tokens are designed and validated to stringent threat models for the safekeeping of secrets. Their simplicity is an advantage for security becomes a disadvantage when contemplating fancy new protocols: these devices are deliberately not extensible. In other words, they support a fixed array of algorithms such as ECDSA and they can not be easily programmed— short of the manufacturer introducing an update— to perform arbitrary new computations using secret keys.
4. Not applicable to fiat currencies. Bank account balances are not verifiable by cryptographic techniques and will remain that way, short of all financial institutions agreeing on a new standard for digitally signed statements. That is not a problem for custodians only handling cryptocurrency. But in every other situation where fiat currency coexists with digital assets, it means the proof of solvency is incomplete. Recall the original reason why proofs are carried out independently for each asset class: to prevent the custodian from shifting balances around between currencies. Putting on the tinfoil hat, a paranoid customer could argue the custodian completed the solvency proof by temporarily using fiat deposits to purchase cryptocurrency.
   Without independent verification of fiat assets against liabilities, there is no way to disprove that line of conspiratorial thinking. (As an aside: stablecoins at first glance offer a solution. For the purpose of the proof, custodian converts its dollar assets into a stablecoin pegged one-to-one against the US dollar. Since stablecoins are tokens represented on a blockchain, the usual cryptographic proofs could then be carried out over control of private-keys in that setting. But the idea that this switch will dispense with third-party trust is illusory: the integrity of the stablecoin depends on its issuer. Transposing the problem from an old-fashioned attestation about bank statements into stablecoin balances introduces a host of new trust assumptions. Specifically that the issuer is carefully maintaining that 1:1 ratio by only minting new coins in proportion to fiat deposits and will allow timely conversion of the stablecoin back into USD on demand— just ask Tether customers how well that is working out.)

Internal controls vs externally verifiable proofs

As the state of the art advances, new protocols may well overcome some of these limitations. But there are more fundamental problems with a public cryptographic proof: possession of keys alone does not equate to sane procedures and risk management. Recent bankruptcy of the Canadian exchange QuadrigaCX is a great example of this. In court filings, company representatives identifies the root cause of $130M+ USD in customer funds being stuck: Quadriga used a single laptop for cold storage, with the password only known to the company founder who recently passed away. That is a staggering failure of internal controls: failure to identify the founder as key-person risk, failure to identify laptop as single point of failure. (There are many other ways this could have gone sideways, including disk corruption on that device.) But as long as one person at Quadriga had access to that cold wallet, they could have produced Provisions-style proofs and passed the solvency test with flying colors.

That is the intrinsic limitation of externally verifiable cryptographic proofs: they can demonstrate that the custodian controls the necessary secret keys at a point in time, but as the saying goes past performance is no guarantee of future results. By contrast a trusted-third party examination need not be limited to quantifying assets/liabilities. They can look into the actual design of cryptocurrency storage— is it a USB drive under the mat or geographically distributed HSMs? They can review policies & procedures around how funds are moved, interview select employees, ask for evidence showing that written procedures are being followed faithfully in day-to-day operations. None of that can guarantee the custodian will not experience a security breach or commit a serious blunder resulting in lost funds. But knowing an organization has consistently applied sound internal controls is at least as valuable a signal as seeing public proof that all the keys are accessible; unlike a point-in-time demonstration, organizational culture around risk management is indicative of future behavior.

The good news is that these two approaches are not mutually exclusive: we can combine third-party audits with partially-public proofs. The starting point is to revisit some of the privacy assumptions behind Provisions: from the perspective of the custodian, what are the zero-knowledge techniques trying to protect and how realistic is that expectation?

[continued]

CP

Updated 2/17: Additional comment on stablecoins.

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