search

bitshares / bsips

BitShares Improvement Proposals and Protocols. These technical documents describe the process of updating and improving the BitShares blockchain and technical ecosystem.
https://bitshares.github.io
63 stars 86 forks source link

BSIP64: Hashed Time-Locked Contract (Replaces BSIP44) #174

Closed ryanRfox closed 5 years ago

ryanRfox commented 5 years ago

BSIP: 0064\ Title: HTLC Updates - Allow length as Optional & Add HASH160\ Authors: Core Team\ Status: Draft\ Type: Protocol\ Created: 2019-06-07\ Discussion: https://github.com/bitshares/bsips/issues/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

https://github.com/bitshares/bsips/issues/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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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.

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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:

pmconrad commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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

jmjatlanta commented 5 years ago

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