BSIP64: Hashed Time-Locked Contract (Replaces BSIP44)

[ryanRfox]

BSIP: 0064
Title: HTLC Updates - Allow length as Optional & Add HASH160
Authors: Core Team
Status: Draft
Type: Protocol
Created: 2019-06-07
Discussion: #174

Abstract

This BSIP describes two modifications to the current implementation of Hashed Time-Locked Contract (HTLC) defined in BSIP44. The first makes the length parameter optional. The second adds the HASH160 algorithm to the set of allowed hash functions.

Motivation

In order to become fully compatible with BIP199 the BitShares implementation must include both of these changes.

Rational

Make length an Optional Parameter

Add HASH160 hash function

Discussion

#174
https://github.com/bitshares/bsips/pulls/

Summary for Tokenholders

The current HTLC implementation requires two additional modifications to be fully compatable with the most widely implemented specification as defined in BIP199.

Copyright

This document is placed in the public domain.

See Also

A description of Hashed Timelock Contracts

[ryanRfox]

This proposed BSIP64 will replace BSIP44 which contains a design bug related to the current implementation's requirement to provide a preimage_length which is incomparable with some less robust implementations and hinders adoption of our solution. By making the preimage_length an optional parameter, the protocol is less restrictive and requires a protocol upgrade to change the design.

[pmconrad]

IMO this document should describe the planned changes only, not the entire HTLC implementation. In the current form it is difficult to see what the relevant changes are.

[jmjatlanta]

IMO this document should describe the planned changes only, not the entire HTLC implementation. In the current form it is difficult to see what the relevant changes are.

If you wanted to go through the pains of adding html tags, you could strikethrough the old (easy) and colorcode the new (harder)

https://stackoverflow.com/questions/35465557/how-to-apply-color-in-markdown

[jmjatlanta]

I would like to propose the addition of HASH160 to the list of available hashes in BitShares. This, along with making the preimage size optional, will make us even more compatible with Bitcoin's BIP199.

For this document, it would be added under Specifications->Objects as htlc_algo_hash160

The implementation would be simple and IMHO the impact large.

• Even if the workaround is easy, users and implementers like the warm fuzzy of complete compatibility.
• While HTLC is still often misunderstood and not highly automated, this change could prevent end users from writing incompatible contracts.

As for my opinion of making the preimage size optional: I believe it to be a good idea, even though it increases risk. What I believe is even more necessary is a document that lists the risks of HTLCs, and how to mitigate them. This should be generic (across all chains). Maybe more than 1 document. One for implementers and one for end users.

[ryanRfox]

Sorry @pmconrad I’m not clear what the final BSIP should contain. It is my current understanding that BSIP44 should be superseded by this BSIP, which represents the complete new spec.

I am happy to reformat the Description text within this Issue to highlight the proposed changes to focus our attention there. Once we agree on the content, a PR can be made with the complete BSIP text.

Does that meet the intended purpose of redefining this spec?

[jmjatlanta]

Sorry @pmconrad I’m not clear what the final BSIP should contain.

I believe what @pmconrad is after is some way of easily seeing what has changed, so he can see why you feel the old BSIP should be replaced.

Or, instead of attempting to replace BSIP44, a BSIP that references BSIP44 and notes the changes.

[MichelSantos]

I think that we need both in some form. A change document to identify what is different. This will be valuable for tokenholders when evaluating the BSIP.

Then a consolidated version of the updated document so that one does not need to flip back and forth. This will be valuable in the future for anyone trying to evaluate the current specs of the BitShares implementation.

[pmconrad]

What I believe is even more necessary is a document that lists the risks of HTLCs, and how to mitigate them.

This!

Sorry @pmconrad I’m not clear what the final BSIP should contain. It is my current understanding that BSIP44 should be superseded by this BSIP, which represents the complete new spec.

In my understanding, BSIPs do not document features. A BSIP, as the name implies, describes an improvement to what currently exists. It does not describe everything that's already there, except perhaps some context needed to understand the improvement. IMO it is important for shareholders and implementors to focus on the change in question, not on the future result.

A consolidated version like Michel suggests is a good idea and should be generated once the BSIP has been accepted. For 3rd party developers this would serve as reference documentation.

[christophersanborn]

Does declaring preimage length reduce collision risk?

Short answer: No. (And in fact, may increase attack surface.)

Full answer:

"Hash Space" vs. "Preimage Space"

A "hash" is a random-esque mapping from a preimage space to a hash space. The size of a hash space is easy to understand: the number of unique hashes is simply 2^(bit-length of the hash). So, for SHA256, it is 2^256. Quite big.

The size of the preimage space, on the other hand, is unbounded. There are an infinite number of preimages, unless you constrain the size. Once you constrain the size of the preimage, then you constrain the size of the preimage "space". For example, a preimage of length 4 bytes (32 bits) exists in a space of 2^32 (or about four billion) unique possiblities.

Each one of those four billion 4-byte preimages has a mapping somewhere in the hash space.

Collision probability across preimage sizes:

For a fixed short bit-length n, and a hash algorithm of bit-length m > n, the preimage space "spans" a "subspace" of the hash space. The fraction of the hash space spanned by the preimage space is F = 2^n / 2^m.

For a 4 byte preimage and 256 bit hash, this fraction is 1 / 2^(256-32) = 1 / 2^224. (Tiny)

For a 5 byte preimage and 256 bit hash, the fraction is 1 / 2^(256-40) = 1 / 2^216. (Bigger, but still tiny)

The chances of there being any collision between these two spaces (nevermind the chances of two people picking the colliding values randomly) is understandable by analogy to throwing two darts, (one thicker than the other), randomly, at a VERY large dart board (2^216 times bigger than the thicker dart), and having one dart hit the other dart. (Although some subtleties are ignored in this analogy.)

Basically, for all intents and purposes, there is no collision between these two spaces.

Now, as the preimage length goes up, approaching the hash length, the chances of there existing a collision across preimage lengths does increase. However, in the cases where those collisions exist, the chances of two participants randomly choosing the particular colliding values goes down, and very rapidly. (Because the preimage space is increasing exponentially.)

So what are the actual chances of collisions?

Assuming preimages are chosen using good randomness, the answer breaks into two categories.

For preimages of bit length n equal to or greater than the hash length m, the hash length sets the probability. P = 1 / 2^m. Collision odds are essentially infinitessimal, and are not made smaller by forcing a specified length.

But for preimages of bit length n < m, where the preimage length is declared publicly, the situation arises where an attacker can search for a collision by scanning a preimage space that is smaller than the hash space, and this reduces the security provided by the hash algorithm from m bits down to n bits. Example: if I know the preimage is 4 bytes, then I only need to scan a 32-bit subspace to find a collision, rather than the whole 256-bit space of, e.g., SHA256.

In other words, by declaring a preimage size that's smaller than the hash size, you have reduced the amount of work an attacker need perform to guess a preimage.

Conclusions:

• For best security, use preimages that are at least as long as the hash length. Don't bother specifying preimage length, as it will not add to security. (Edited to add: "security" here refers ONLY to the chances of an attacker finding a hash collision by leveraging the additional degrees of freedom afforded by an unconstrained hash length. This should not be interpreted to mean there are not OTHER motivations to constrain the hash length.)

• If, for some reason, you have chosen a preimage shorter than the hash length, DO NOT declare so publicly, as this will allow an attacker to optimize a brute force strategy.

• Committing to a preimage length in the HTLC, generally, does not add more security against a hash-collision attack. Where it may be useful, however, is to allow one party to make an assurance to the other party that a preimage they have chosen does not exceed some limitation of the blockchain that the other party is using. (But this possibility needs a little further analysis, in my opinion.)

[pmconrad]

Agree with everything except that "it will not add to security".

Where it may be useful, however, is to allow one party to make an assurance to the other party that a preimage they have chosen does not exceed some limitation of the blockchain that the other party is using.

This is the part that I'm worried about.

Suppose you own BTC and start an HTLC exchange for BTS. You choose a 100k preimage, but you publish only the hash via HTLC tx on BTC chain. Your counterparty creates HTLC with same hash on BTS chain. You claim the HTLC on BTS, publishing the 100k preimage. Your counterparty will need to publish the 100k preimage on BTC chain in order to claim, which is unlikely to be accepted into the chain, and may be prohibitively expensive. After the HTLC on BTC chain has expired, you walk away with both the BTS and the BTC.

Publishing the preimage length is a nice and simple way to prevent such scams.

[jmjatlanta]

Here is what @pmconrad was worried about, and possible ways to craft the fix in Bitcoin: https://gist.github.com/markblundeberg/7a932c98179de2190049f5823907c016

Note: Additional possible fixes in the comments of the article.

[pmconrad]

This duplicates #163 now - which one should we close / where to continue the discussion?

[jmjatlanta]

Closing this in favor of #163. Please continue the discussion there.