search

interledger / rfcs

Specifications for Interledger and related protocols
https://interledger.org
Other
455 stars 111 forks source link

Conditions are only SHA-256 #153

Closed justmoon closed 6 years ago

justmoon commented 7 years ago

Thanks for @emschwartz for pioneering this line of thinking and forcing me to write it up for discussion and - eventually - posterity.

History

When the first prototype of Interledger was written back in January 2015, we thought that each ledger transfer would depend on the next one in the chain. In my mind, Interledger was merely one example of a vast network of cryptographic conditions triggering code, triggering other conditions and so on. Today, this idea lives on as an Internet Draft titled Crypto Conditions.

However, a lot has happened since January 2015. We realized that the condition for all of the transfers could be the same - a signed receipt from the receiver. Then, Joseph Poon and Thaddeus Dryja released the Lightning Network paper which contained the same basic flow we were using, but with a simpler SHA-256 hashlock condition instead of a complex crypto-condition. After learning about this, we switched our implementation to SHA-256 conditions as well. However, the full power of crypto-conditions is technically still supported in Interledger.js. We just don't use it.

Constraints

In order for an interledger network (a network of ledgers where money can be transferred between any two accounts) to exist, some set of ledgers must exist, all of which support some non-empty set of condition types. If two ledgers do not support any common condition type, they cannot be part of the same payment which means they aren't part of the same interledger network. Therefore, all ledgers in an interledger network must have at least one condition type in common.

Further, for a connector to forward a payment, it must be able to identify the next hop to forward it to. In Interledger, this is done via a routing table lookup. If the payment depends on a given set of condition types, we need a routing table which contains only routes that support this set of conditions or a superset.

In other words, we would need all connectors to have a separate routing table for each possible set of condition types.

A large number of separate routing tables at each connector would be extremely expensive, so we need a way to simplify.

We can omit those routing tables where a routing table for a superset of condition types already exists. This is because we can route a payment using routes that support a superset of the condition types in the payment. However, if the superset is much larger than the original set of conditions, we are probably missing out on some routes, since many ledgers that would have supported all conditions from the smaller set would not be considered as possible routes because they don't support the superset.

Proposal

Having multiple routing tables at all adds significant complexity. We have only identified a few use cases that would require anything more than a hashlock condition:

Many use cases that at first glance seem to require crypto-conditions, actually don't. For example, sending a (repudiable) payment non-interactively can be done by generating a random secret, encrypting it with the recipient's public key and attaching it to the payment.

As a result, for 99% of payments we don't need anything more than hashlock conditions.

Note that this not only avoids having to have multiple routing tables per connector, it avoids the need to have support for multiple routing tables - at least for now.

Since the success of standards seems so heavily to depend on their simplicity, especially their simplicity in the early days, @emschwartz and I propose to support only one set of condition types in ILP. The set containing only SHA-256 preimage conditions.

Why SHA-256?

SHA-256 is an instance of SHA-2, the most widely supported yet still secure cryptographic hashing algorithm. SHA-256 is used by the Lightning Network¹ because it happens to be the only hashing function currently supported by Bitcoin's scripting language. There isn't a strong reason to use a different hashing function and using the same one makes the two networks interoperable. We believe that to achieve interoperability, we have to lead by example and not make arbitrary choices that break interoperability for no good reason.

¹ Technically, SHA-256d (two iterations of SHA-256) is used, however, the two are interoperable: Given a SHA-256 condition c, the equivalent SHA-256d condition is simply c' = SHA-256(c). Since SHA-256d(x) = SHA-256(SHA-256(x)) the same fulfillment f will fulfill both c = SHA-256(f) and c': c' = SHA-256(c) = SHA-256(SHA-256(f)) = SHA-256d(f)

Long-term

SHA-256 is expected to remain secure at least until scalable quantum computers become feasible and there is some evidence that it will survive even longer than that. If past experience is any guide, any cryptographic algorithm's days are ultimately numbered and we should assume that SHA-256 is no exception.

If we need to upgrade the hash algorithm in the future, we can still create the ability to have multiple routing tables and define other algorithms that may be supported. However, we don't have to do so right now.

To be clear, I don't think we even have the option of adding support for multiple routing tables right now. We simply don't have the developer resources to add that amount of complexity to the routing protocol. We do have the option of using a larger agreed-upon set of conditions, e.g. all conditions specified in the current draft of crypto-conditions. However, doing this would drop compatibility with Lightning and add a significant amount of work for ledger (adapter) implementers. In the absence of a strong use case, it isn't a worthwhile trade-off.

mDuo13 commented 7 years ago

This is a pretty convincing argument. However, I think that expressing conditions as "crypto-conditions" in an extensible format still makes sense:

It might be that we don't need all the advanced features of Crypto-Conditions (e.g. nesting, thresholds) but we should still preserve the ability to communicate which hash function we use. If that's all we do, then labeling routing tables per cipher doesn't seem so bad.

Admittedly, the requirements on common ciphers are stricter for the hashes used in ILP, but think of how many ciphers have been used with SSL/TLS and how frequently they need to be changed.

adrianhopebailie commented 7 years ago

In my opinion this proposal has a few flaws:

The theoretical vs real cost of supporting crypto-conditions vs the real cost of a future upgrade

The proposal makes the following claim:

A large number of separate routing tables at each connector would be extremely expensive, so we need a way to simplify.

While this is theoretically true it is not actually true in reality. Connectors can be designed to consider supported condition types as a dimension in their routing data but the reality is that for the foreseeable future that dimension will only ever have a single value: PREIMAGE-SHA256.

If a connector wants to only maintain routing tables for ledgers that support SHA-256 hash-locks then it can discard any other routing info it gets and reject any transactions that use other types. i.e. The implementation cost is almost negligible for connectors.

Note that the routing protocols that support IP have evolved hugely since IP was first developed but that has not required IP itself to change, just the routers that must support these routing protocols. This is a critical factor in why IP has stood the test of time.

Keeping support for crypto-conditions, but assuming that for the foreseeable future only SHA-256 hashlocks will be used means:

  1. We continue to use the well-defined encoding formats for conditions meaning that implementations either use a DER or URI parser (widely available mature libraries) to extract the SHA-256 hash from the condition.
  2. Protocols for sharing routing information SHOULD include data about supported condition types but could assume a default of PREIMAGE-SHA256 if not specified.
  3. Connectors choose to support routing by type or not, on the understanding that if the network evolves around them they will need to add support in future or become increasingly isolated. (NB: This is an implementation decision not a design decision - a good thing)

In the future, when the ecosystem finds a need for a new type of condition, this will roll out seamlessly because the protocol has been designed for it.

Ledgers and connectors will begin to support the new condition and over time more and more routes will be established that support the new condition(s). This is preferable to a situation where all nodes MUST upgrade before anyone can support the new condition because the format of a fundamental data member has changed (See @mDuo13 's reference to IPv6).

We'd probabaly use the same encoding even if we didn't use crypto-conditions

As an exercise consider the ideal way to represent a hashlock if that was the only condition type but we wanted to allow for this to be upgraded in future. I.e. assuming crypto-conditions didn't exist but we want to accommodate a future where a different hash algorithm might be needed...

Using an ni: URI would probably be the best encoding format for text as it is designed to solve exactly that problem. While it can be argued that the binary encoding would simply be the hash this would not support upgradability and critically ignores the value of the cost property so we'd probably come up with a binary encoding that is not too different to what we already have.

Forking the Interledger

The proposal makes the following claim:

for 99% of payments we don't need anything more than hashlock conditions.

Atomic mode ILP and the implementations of this by companies such as Ripple require more sophisticated conditions than SHA-256 hashlocks so I would contest that this proposal assumes that the uses cases being dealt with within this community are sufficient to inform our design decisions.

I think that we are conflating the use cases that are important to bootstrap the public Interledger network and the use cases that a global value transfer protocol must support.

If we only design for the former then we risk creating a protocol that cannot, by design, acheive what we have set out to acheive which is a create a universal value transfer protocol that ultimately underpins the Internet of Value.

Concretely, assuming the long term vision for the protocol is a single network that includes private ledgers and nodes, like those running ILP-kit today, and large financial institutions, like those running Ripple solutions, then the protocol used by the two networks cannot fork or we will have to find a way, in the future to try and bring them back together.

Proposal

justmoon commented 7 years ago

Great responses, thanks guys! :+1:

Ok, so it sounds like the decision to only support PREIMAGE-SHA-256 isn't all that controversial and you guys seem more concerned with future-proofing and how conditions are encoded, so let me focus on those points more.

There are several different mechanisms for future-proofing:

(This is not meant to be an exhaustive list.)

Although we have expectations that SHA-256 will last for a while, upgrading a network that doesn't have a built-in upgrade mechanism is very difficult (example: IPv6)

IPv4 does have an upgrade mechanism, namely versioning: the first byte is a version byte where IPv4 uses the value 4 and IPv6 uses the value 6. As a result, IPv4 and IPv6 work fine alongside each other on the same network.

I don't see what the designers of IPv4 should have done differently. Sure, maybe they should have overspec'd the size of the address space, but overspecing in our case would be to choose SHA-512, which is a different discussion. Should they have made the address size upgradable? I'd argue that that would have been pointless, because upgrading the address space is so disruptive that you may as well just increment the protocol version. Worse than pointless, it would have been counterproductive, because it would have made IPv4 much more complex due to variable-length address fields etc.

The point is: Some choices are so fundamental to the design of a system that making them pluggable becomes pointless and - due to the cost of abstraction - harmful.

In terms of what adopting a new condition type would look like: You would define the new type. Then, you would define at least one new transport layer protocol that uses it. Then, you would define application layer protocols that use the new transport protocol. Next, all ledgers¹ have to be upgraded, followed by all connectors¹, followed by all clients¹. Connectors will have to maintain (at least) two routing tables. Until you get most tier 1 providers to add support, you wouldn't be able to use any of this in the wild.

This is independent of whether we add bitmask flagged routing tables, etc. In other words, no matter what "upgradability" we add, actually adding a new condition type would be about the same amount of work as the switch from IPv4 to IPv6. So I expect that if you were going to add a new condition type because SHA-256 is reaching the end of its life, you'd probably want to use this opportunity to roll out ILPv2 at the same time.

Note that this discussion is a bit academic, because the condition doesn't appear in the ILP packet at all. So whether we support one type or many, ILP wouldn't be any different, as @adrianhopebailie also points out. Even CCP probably wouldn't be any different, because we'll already support tagging routes with custom properties, so you could tag routes with the bitmask of supported conditions. That means that the proposals by @adrianhopebailie and myself - as far as ILP, ILQP, CCP, SSP, SPSP are concerned - are equivalent.

¹ If they want to be part of the new network.

Alright, I talked a lot about what we don't have to decide - so what do we have to decide right now?

Decision Proposed Lightning
Hash function SHA-256 SHA-256d²
Preimage length =32 =32

If we want to have compatibility with Lightning, we MUST choose the same preimage rules, because a payment that doesn't meet the rules for Lightning can't be (securely) transferred over it.

Bitcoin would support preimages up to 520 bytes and crypto-conditions (five-bells-ledger, rippled) support some arbitrary maximum size, likely much larger than 520 bytes. So if we didn't care about Lightning compatibility, we could make our own Bitcoin payment channels spec that allows up to 512-byte preimages for instance.

Why support larger preimages? You could use conditions to buy data. If that data is larger than 32 bytes and we set the preimage size to 32 bytes, you wouldn't be able to buy more than 32 bytes at a time. However, you may be able to prove in zero knowledge that the preimage is the decryption key for a certain larger piece of data that you want - so it might not matter.

The other use case for larger preimages would be @emschwartz' idea, which is essentially combining ILP and CAS (content-addressed storage) to form a paid file sharing network on the interledger layer. However, elegant as this may be, it's probably good enough to just build filesharing networks with payments built-in, without this sort of deep integration.

Why not support larger preimages? Lightning interoperability as I mentioned. Plus it eliminates one more variable that could cause a problem down the line. (E.g. some ledger confuses <=512 bytes with <512 bytes, nobody notices, then suddenly, someone manages to steal $10 million from a connector.)

I'd advocate we go with =32 bytes, i.e. all preimages must be exactly 32 bytes in size.

² SHA-256d can be made interoperable with SHA-256 because, within the trapdoor SHA-256d, there is another trapdoor that is plain SHA-256.

Finally, a note on encoding formats: Conditions don't actually appear in ILP packets, so technically ILP does not even need to specify a format for them. Where do they appear?

Ledger Protocols

We are using crypto-conditions (in URI or binary format) in the Five Bells Ledger API, Common Ledger API, Plugin Virtual, BigchainDB and Rippled. Afaik nobody is advocating that we change that.

Internally in Implementations

Each implementation needs a way to pass around conditions in its various internal APIs, like the Ledger Plugin Interface. This will likely be different from implementation to implementation and it's relatively easy to change (it's a breaking change in the library, but no change on the wire.)

For Interledger.js' Ledger Plugin Interface, I propose we use a 32-byte buffer containing the hash.

In IPR

Interledger Payment Requests contain a condition, which must be encoded somehow. I propose that we use crypto-condition URI format.

Note: Luckily, SSP does not transmit conditions over the wire and so doesn't need to prescribe a format. And it's looking like SSP will be the transport we'll use for now. That gives us more time to spend on IPR to get it right.

adrianhopebailie commented 7 years ago

Agree with a lot of @justmoon 's points above but think it would be useful to be 100% clear on what is being proposed.

Firstly, I think an upgrade to an addressing scheme is significantly more impactful to a network than an upgrade to (or even addition of) a routing dimension so I'm not sure that the future upgrade is as scary as described or comparing to the IP upgrade is entirely accurate.

i.e. Supporting a new condition type would be analogous to a change in the Data Link Layer (not the Networking Layer) which bubbles up to the Network Layer purely as new route options. I.e. It confines all changes to implementation specific code. Most importantly, it does not require a new version of ILP.

In contrast, as pointed out my @justmoon , the IPv4 to IPv6 upgrade uses protocol versioning which is as disruptive as it comes in terms of upgrade paths. As an implementor I need to accept that when I get an IPv6 packet it could be completely different to an IPv4 packet.

The change for most modules on the Interledger network for a new condition would be minor if they are already all expecting crypto-conditions but only support a specific type:

  1. Ledgers would upgrade their internal logic for evaluating fulfillments and releasing funds (entirely self-contained upgrade and impacts nobody else). No API change if their external interface already supports crypto-conditions.

  2. Connectors add a new dimension to their routing as they become aware of ledgers that they connect through adding support for the new condition (or they don't and continue to only participate in routes that use SHA-256 only). Potentially no API change either unless the routing protocol messaging is not designed to accommodate this (which would be a pity).

  3. Clients potentially change nothing because the new condition type is passed around opaquely in the existing encoding. The biggest change would be the sender and receiver clients who actually construct the condition but one assumes this is expected since they would be driving the change.

I think it would be more likely that existing transport protocols would upgrade rather than we'd invent new ones, unless the new condition type is being introduced to enable new functionality at that layer, so I think that's likely to be less disruptive that described but, as with all of these speculative exercises we are guessing a little.

So what are we actually proposing here?

Ultimately we are defining the minimum requirements of any implementation of one of the components participating in an Interledger transfer. But, when we define a protocol we also need to define what a component must do if it doesn't support some optional aspect of the protocol so that everyone behaves in the correct way.

We also need to help implementors plan for the future by indicating where we think the protocol will evolve. (Think, "Reserved for future use"). Ultimately it's up to implementations to decide what they do with that information.

i.e. There are normative and informative aspects of the specification and what we are really debating here is what to make normative and what to make informative.

I think we all agree that the basic requirements of a ledger are:

I understand the current proposal to be:

My proposal would be to make this slightly more explicit:

In terms of implementation, this allows the any ledger to define it's ledger API to use a Buffer that is understood to be a SHA-256 hash. That is a limitation of that ledger implementation that is codified in the API of that ledger (as opposed to being defined at a protocol level).

It's an implementation decision by the developers of THAT component that they choose simplification now at the expense of possibly requiring a new API in future.

The plugin API (ILP RFC 4) should still use crypto-conditions otherwise we force all other ledgers to ONLY use SHA-256 hashes.

In my opinion, if we use the less explicit version we, as the protocol designers, are being irresponsible because we know there are implementations that support more condition types and we're ignoring that in our specification. Further, we are actively preventing those implementations from using anything else.

tarcieri commented 7 years ago

SHA-256 is expected to remain secure at least until scalable quantum computers become feasible and there is some evidence that it will survive even longer than that.

A bit of a sidebar point here, but I've been talking to a number of cryptographers about this lately (namely Dan Boneh and @veorq) and most seem confident in SHA-256's post-quantum security (despite e.g. NSA's recommendation to move to SHA-384).

@veorq specifically had this to say:

SHA-256 would still have 128-bit security against preimages, so fine. plus, not all “2^128” complexities are equivalent to each other; a quantum “2^128” would likely add a huge constant factor compared to classical optimized parallelizable “2^128” search and you need a huge quantum circuit implementing SHA-256 (see https://arxiv.org/abs/1512.04965v1 for the AES case)

adrianhopebailie commented 7 years ago

From the discussion on the call today I propose the following is adopted.

tarcieri commented 7 years ago

Sorry for missing the call!

When I first started reading this post I was very enamored with the idea of Lightning-like hash-locked conditions as a unifying principle. But then I read @adrianhopebailie's response and sympathized with it as well, and think his latest proposal is probably the way to go: HTLCs as the happy path, but with the option of extensibility.

zookozcash commented 7 years ago

Hi folks! I'm looking into these discussions because of Zcash's new emphasis on Cross-Chain Atomic Transactions, and because Michiel de Jong has encouraged me to look closer at achieving actual ILP interop.

I want to respond to one particular comment, from the original post by @justmoon:

"If past experience is any guide, any cryptographic algorithm's days are ultimately numbered"

This is true for collision-resistance but false for pre-image-resistance!

Please read this half-written paper that comes with a disclaimer saying you shouldn't read it:

https://tahoe-lafs.org/~zooko/preimage-attacks-color.html

IMHO we should assume that SHA-256 may become vulnerable to collisions, but that it will never become vulnerable to pre-images.

So that leads to the critical question: is pre-image-resistance all we need out of SHA-256 for ILP to be safe? About 95% of the time, engineers faced with this question say "Oh yeah, collision-but-not-preimage is harmless to my system.", and about 10% of the time those engineers are wrong, so think carefully about this.

Imagine that you are evil, and you are the only person in the world who knows how to make SHA-256 collisions, or even knows that it is possible to make SHA-256 collisions. You are not limited to "random-looking" inputs, either! You can generate inputs X and Y, each of which has whatever "structure" or information that you want, including a leading prefix, but they both have the same SHA-256 hash as each other. You can also generate multi-collisions, i.e. millions of different inputs, all of which have the same SHA-256 hash as each other (and whatever "structure" you want). Now, can you defraud people or destroy the ILP network with this power?

justmoon commented 7 years ago

@zookozcash Fascinating read, thanks!

Now, can you defraud people or destroy the ILP network with this power?

This might be one of those situations where it would be better to say nothing and look like a fool than open my mouth and remove any doubt, but I'll take a stab at answering your question.

Since I can't assume everyone reading this thread is familiar with Interledger, I'll first recap some relevant background on Interledger's architecture:

It's best to think of Interledger simply as an abstraction layer between different ledger protocols and different application protocols. Aside from being an abstraction layer, Interledger also deals with quoting, relaying payments via so-called connectors and routing. The transport layer exists because certain aspects of application layer protocols are common across many of them, so it makes sense to break out those common elements into their own layer to make them reusable.

The Interledger layers are inspired by but are totally distinct from the Internet layers. In Interledger, we assume that users of a ledger can communicate with each other using some ledger-defined way and users of an application protocol may communicate with each other somehow, but how that works, whether it is using the Internet or something else, does not matter to us.

SHA-256 hashlocks appear in two places:

Because the preimages are chosen outside of the Interledger layer, I do believe that on the Interledger layer we only require preimage resistance, because the attacker has no control over the preimage at all, assuming the transport protocol is designed correctly. So in order to answer the original question, we will have to look at each transport layer protocol individually.

Before we move on to that, a couple of notes on the security of the Interledger Protocol (ILP):

Now, for the more interesting part, a look at the different transport layer protocols (that we have come up with thus far.)

Pre-Shared Key (PSK)

In this protocol, we assume that sender and recipient have a shared secret available.

Typically, the recipient will generate the shared secret using HMAC-SHA-256 where the key is a private value and the message is a random public token, generated by the recipient. The token and thusly generated shared secret are given to the sender by the application layer protocol via a secure, application-specific channel such as TLS.

If the attacker can break the security of the secure channel and eavesdrop, the protocol is obviously broken. However, if they cannot - and assuming the protocol is implemented securely - the attacker cannot influence or know the private key of the recipient. As a result, they cannot know or influence the shared secret.

For each payment, the sender uses the shared secret as the key for another HMAC operation. This time the message is the Interledger packet for the payment that she is about to send. The resulting value is used as the preimage for the payment's hashlock. This preimage is eventually revealed, but the shared secret never is.

Interledger Payment Request (IPR)

In this protocol, the recipient generates a per-payment secret using HMAC with a randomly generated secret as the key and the payment details (amount, destination address, attached data) as the message. Implementations should rotate the key from time to time. To be clear, the key is never revealed.

The recipient provides the payment details, along with the hashlock to the sender via an authenticated, but not necessarily private, channel.

There are a bunch of other transport protocols we are working on, but they may still change, so I'm going to skip them here.

Based on my lay understanding, we are relying on

This seems not to require collision resistance if I understand HMAC's properties correctly, but it does put pressure on the designers of the application layer protocol to choose an appropriate channel.

cc/ @dappelt

stale[bot] commented 6 years ago

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions. \n\n If this issue is important, please feel free to bring it up on the next Interledger Community Group Call or in the Gitter chat.