40
votes

How does the Ripple system solve the double-spend problem? Does it also use some block-chain-like entity that officially dictates which transactions are confirmed and which are not, or does it use some other clever mechanism?

locked by Andrew Chow Aug 4 at 0:14

This question exists because it has historical significance, but it is not considered a good, on-topic question for this site so please do not use it as evidence that you can ask similar questions here. This question and its answers are frozen and cannot be changed. See the help center for guidance on writing a good question.

Read more about locked posts here.

33
votes

The details are very complex, but the core concept is fairly simple. Ripple solves the double-spend problem by consensus.

The analogy I use is an "agreement room". To walk into the room, you have to agree with everyone who is already in there. If you want to disagree, you have to leave and form your own room. Everyone who is honest wants to get into the biggest room they can with the most people in it.

In the room, people constantly agree on the current state of the system. It's implemented as a hash tree, so that's just one 256-bit number.

To perform a transaction, you walk into the big room and read out the transaction. Everyone checks the transaction against their ledger. Assuming there's no conflicting transaction or other problem, everyone agrees that the transaction is valid and they include it in the set of transactions they believe should be applied.

They then work on any disagreements they have by an avalanche process. Essentially, if someone is voting yes on a transaction that doesn't have overwhelming majority support, they just change their vote to no. This ensures there's a quick agreement on a set of transactions.

Once a set of candidate transactions is agreed upon, those transaction are applied and everyone computes the next ledger according to a set of deterministic rules. They all sign it, publish those signatures, and now clients know which transactions have been accepted by the consensus process.

If a transaction doesn't get in for some reason, but it's still valid, every honest person in the room will say yes to that transaction in the next round.

So, back to the double spend problem. A double spend is essentially two transactions, each of which is valid if and only if it's applied before the other. Thus solving the double spend problem "merely" requires agreeing on an order for the two transactions. If everyone agrees which comes first, the problem is solved -- the one that comes first is applied and thus the other is invalid.

In the Ripple system, if two transactions are a double spend, one of three things can happen:

  1. One transaction will get voted into a consensus set before the other. In this case, that transaction will be in a ledger signed by all the people in the room, forever invalidating the other.

  2. Both get into the same consensus set (this should almost never happen). In this case, a deterministic rule when the consensus set is applied determines which gets into the ledger, forever blocking the other.

  3. Neither gets into a consensus set because neither gets a majority and both transactions are at around 50%. In this case, every node that sees both transactions (which will quickly be the vast majority of nodes) will vote yes on the transaction that wins by a deterministic rule and no on the transaction that loses by that rule. The one that wins by that deterministic rule will get in the consensus set, be applied to the ledger, and forever block the other.

That's a gross oversimplification, but it's inherently fairly complex.

  • 5
    How is this different from Bitcoin, if it is different? – Colin Dean Feb 12 '13 at 1:47
  • 11
    @ColinDean: Bitcoin uses proof of work. The methods are completely different. – David Schwartz Feb 12 '13 at 1:49
  • 3
    Is there any 'cost' to having a vote? Does each node on the network represent one vote? If there is not a high cost, is there a risk that an attacker can spam nodes on the network to get more votes? Thanks for the detailed writeup. – Brian Armstrong Apr 12 '13 at 7:10
  • 3
    @StevenRoose Ripple has accounts with balances. If I send you $10, that's a double spend if I don't have $10 but it's not a double spend if I have (another) $10. So what you need to prevent a double spend is the current balance, not historical transactions. – David Schwartz Jan 14 '14 at 22:37
  • 5
    @StevenRoose Every account also has a sequence number. For a transaction to be legal, the sequence number in the transaction must equal the sequence number in the account that performed the transaction. As part of performing the transaction, the account's sequence number is incremented, forever preventing that transaction from being applied again. So, again, you only need the current state of the account and no historical transactions. – David Schwartz Jan 15 '14 at 17:48
5
votes

@David's answer essentially doesn't talk about an attack scenario where the room is full of dishonest nodes. This is essentially what the proof-of-work was designed to fix.

If you get a hold of a lot of IPs (nodes in the Ripple network) you could become a majority in the room. The difference is that it's really easy to get an IP, but extremely hard to prove you work in a proof-of-work system (like Bitcoin's).

For my understanding, Ripple doesn't solve the double-spending problem mathematically, as Bitcoin does (assuming honest nodes are overpowering the network). It solves it using a distributed consensus system that can easily be overthrown if you can obtain the majority of the IPs and you act honestly for a while, making other nodes trust you.

In conclusion double-spending is possible with both Bitcoin and Ripple, but with Bitcoin it's much harder to double-spend because the system is based on a mathematical race against the proof-of-work system, whilst Ripple relies on consensus of a number of nodes that can be more easily reproduced by an attacker.

  • 3
    reason why i'm being downvoted? – Luca Matteis Nov 12 '13 at 18:28
  • 4
    IPs and nodes have nothing to do with anything. The algorithm doesn't care how many IPs or nodes you have or don't have. It's based on public keys that human beings have chosen to extend very small amounts of trust to. As for "it's really easy to get an IP, but extremely hard to prove you work in a proof-of-work system", that's basically false. They both take money. What's hard to do is convince other human beings that lots of keys have totally independent ownership when they actually don't. – David Schwartz Nov 13 '13 at 0:52
  • 1
    Sorry but it's still not clear to me. The Ripple system requires trust to certain amount of nodes, right? How easily can trust be faked by a single entity, simply creating a variety of different nodes in the system (sybil attack). Essentially, what if the room is full of dishonest people, and how easy would it be to do this? – Luca Matteis Nov 13 '13 at 9:47
  • 1
    This forum isn't really suitable to conversation. If you like, you can post to the Bitcoin forums or the Ripple forums. A single entity can create as many nodes as they want, but they have to actually convince people that the nodes are independent for them to count. Human beings make the decision of which keys to count based on their conviction that the keys are independently administered. There's a discussion of this issue here. – David Schwartz Nov 13 '13 at 9:55
  • 3
    For one thing, this system wasn't known until two years after Bitcoin was made public. Jed McCaleb proposed it as a response to what he perceived as mining's inefficiency. – David Schwartz Nov 13 '13 at 13:23

Not the answer you're looking for? Browse other questions tagged or ask your own question.