Hash Chain Tokenization Criticism

(originally posted on yours.org July 2018)

This document explores issues with the Hash Chain technique proposed to create tokens in the nChain document “591 — Token access chains and linked keys v1.3.pdf”.

This document proposes 1 technique to allow a user to mint an arbitrary number of tokens, and 4 techniques to steal tokens during transfer.

Background

Hash Chain tokens have been verbally discussed as a promising tokenization technique since approximately the beginning of the year. The referenced nChain document was released publicly on the Bitcoin Cash Tokens Telegram working group, however it is marked confidential in a classic corporate confusion strategy. Therefore I am not comfortable linking it directly. But you can access it here: https://github.com/bitcoincashorg/bitcoincash.org/blob/master/workgroups/wg-tokens/workgroup.md). Join the working group and click the “files” button on the right to see all uploaded files.

I presented this criticism to nChain a week or so after the document was released on May 31, and had a meeting with representatives of the company soon thereafter. Since there has been no restatement or retraction of this proposal after a month and a half, I feel that I must present this information publicly. As we discuss tokenization proposals, it is important that the public to understand that, as presented, the nChain hash chains tokenization proposal is extremely flawed.

Finally, since nChain CEO Jimmy Nguyen has consistently refused to meet with me to discuss this topic, I would like to make a public statement that perhaps he will see. “Bitcoin Unlimited has presented several criticisms of nChain initiatives, but we are not your enemy. We are simply acting as a voice of truth and rationality, and it is better to identify the problems with these initiatives earlier than deal with exploits later. Your enemy is your internal processes, specifically your company’s inability to internally review both formal and informal communications to catch simple errors and exploits.”

Summary of the Proposal

Reminder: Alice == token owner/seller, Bob == token issuer, Charlie == token buyer

The proposal basically suggests that Alice create a hash chain — a list of numbers where each is the hash of the next, and then periodically reveal them in reverse order to the token issuer (Bob) to “activate” them. Bob has to store the last activated token, so he can verify that the next one hashes to it.

This proposal can exist independently of the blockchain. The advantage a blockchain confers is minimal:

1. Reliable database for Bob. Bob has to maintain a mapping to certify that certain numbers are his tokens. If he loses this database everyone is unhappy. The blockchain is a distributed, reliable storage mechanism. (The document does not mention this use)
2. Token purchase. Alice could send BCH to Bob and commit to the last hash number in a single transaction. (The document does not mention this use)
3. Token activation. Alice could reveal a hash and therefore activate her next token on the blockchain. But she might as well just send the hash to Bob directly…
4. Token transfer.

Weaknesses of the Proposal

Unprovable Ownership

If Bob claims Alice’s hash chain is not one of his tokens, she cannot prove otherwise (unless Bob’s database is on the blockchain, an idea not mentioned by the proposal).

If Bob loses his database, anyone can claim to Bob that a hash chain is one of his tokens.

A possible remedy of Alice’s unprovable ownership would be to have Bob sign the hash that Alice gave him, and return that to Alice. However, this does not solve the problem of Bob losing his database or Bob claiming Alice already spent those tokens.

Centralized Transfer

Token transfer involves Bob. He could freeze the transfer, or be offline. Alice gets the money even if Bob invalidates the transfer.

Attacks against Minting

Section 1.1.3 claims “Bob stores tn [the last hash] and no other value”. But Bob must also store the length of the hash chain. Otherwise Alice could generate a longer chain than she advertised to Bob and use it to mint extra tokens.

In section 1.1.4, there is a clarification needed regarding “Calculates the value of her token.” It should be stated here that this is the 32 byte token itself, not its value (i.e. price).

Linear Cost Token Validation

Token validation requires a SHA256 per token. Therefore this proposal is more useful for low-quantity token applications. Moving a billion tokens means 1 billion sequential SHA256 operations. We cannot use miner ASIC hardware, or parallel CPUs for this, since each SHA256 operation depends on the output of the last one.

Attacks Against Token Transfer (section 1.2)

Fake Token Attack

Alice creates a new hash chain that was never provided to Bob. Charlie creates the locking script as per the document:

LockingScript CheckSig H ( Pa ) AND Solve H ( t.n-m-1 ) 
                                AND Solve H ( s.n-m)

Alice spends this script, taking the BCH and revealing t.n-m-1.

Charlie provides the spend transaction to Bob, who replies that Alice’s token does not exist.

Incorrect Quantity Attack

Alice tells Charlie that she has n-m tokens to sell, but she actually has p < n-m. The transaction goes through fine. After Charlie activates p-m tokens (this could be a long time later, depending on the purpose of the tokens), Bob responds that the next token is invalid.

Alice can’t prove to Charlie the length of her hash chain (quantity of tokens), without revealing the hash chain which would allow him to steal the tokens.

It is impossible to determine who cheated: Alice or Bob (or even Charlie, who could falsely claim the number of tokens he was sold).

Use During Transfer Attack

The transaction proceeds normally until Charlie creates the payment transaction. Before Alice spends it, she contacts Bob and activates all of her tokens. Next, Alice spends the transaction, taking the BCH and revealing the already-spent token to Charlie. Bob rejects Charlie’s request to transfer the already-used token.

Even if Bob signs the token as suggested above, and Alice provides that signature to Charlie as proof of token existence, this attack still works.

If Bob creates an API that allows Charlie to verify the token, there is still time for Alice to spend it. Bob needs to provide an API that locks the token for the duration of the transfer. At this point, the proposal is essentially equivalent to that of a centralized token database maintained by Bob.

Multi-spend Attack

Alice sells the same tokens N times simultaneously to many people, call them Charlie1…N. She waits for all the Charlie’s to put their payment transactions on the blockchain. She then spends all of the transactions, taking payment and revealing her token. Charlie1…N now race each other to confirm the transfer of their tokens with Bob. The first Charlie to contact Bob wins.

This attack defeats the locking API proposed in the prior example.

Summary

To remedy the above attacks, Bob’s cooperation is essential for proper token transfer. Bob must provide an atomic, centralized, lockable database, containing token quantity and owners, and ACID APIs for token owners to access it. Even with such a database, special operations will be needed to ensure that updates to this database are atomic with respect to payment transfers (which may or may not be blockchain based). Perhaps this can be done by requiring that all database updates occur on the blockchain (although this does not defeat the multi-spend attack), but if implemented as such, this reduces the proposal to authority-based or OP_RETURN based tokenization strategies that have been suggested by many other proposals.

We have therefore shown that the hash chain concept, as currently specified, requires the standard centralized database client-server design pattern, or well known blockchain token design patterns. At this point, the database might as well contain just the holder’s public keys and token quantity instead of a hash chain. Hash chains confer no advantage, and have a key disadvantage which is that CPU validation time is linear with the number of tokens transferred.

Finally, one advantage of blockchain based tokens are that they are mostly independent of the issuer once issued. This proposal cannot achieve that as “Bob” is involved in every transfer.