Ripple (distributed) and its security
Jan Michelfeit
my name is Jan Michelfeit and I recently graduated IT security with a master's
thesis on Ripple. I guess sharing it with the rest of the world would be a
good idea ;) so here it is:
[http://is.muni.cz/th/139865/fi_m/dp_139865.pdf?lang=en] (PDF)
[http://is.muni.cz/th/139865/fi_m/source.zip?lang=en] (LaTeX source)
I still consider it just version 1 and far from perfect, but I choose to
publish it now, as I don't know if there will ever be a version 2
(perfectionism is a curse, believe me).
Anyway, as for the contents, there's a chapter on the economic aspects of
Ripple (from a slightly libertarian perspective ;), then a proposal of a
formalism which didn't get used much in the end, a general security "analysis"
of distributed Ripple, and a discussion of the path discovery algorithm.
The whole paper is in the public domain (I'm not a big fan of IP), so feel
free to use and remix it as you wish. Attribution is always welcome, but
definitely not required.
Best regards
Jan Michelfeit
Ryan Fugger
http://ripple-project.org/Main/Concept
Did a quick read and it looks interesting. I agree with the paper's
conclusion about the distributed path search algorithm envisioned in
the v0.4 protocol and earlier:
> The currently proposed path discovery algorithm has several flaws with regard to secu-
> rity. It implements the hop limits and the Bloom filters in a way that could disclose the
> length of the payment path and possibly identify the payer or the payee. The depth-first
> searching employed constitutes a trap path attack vulnerability. All the routing schemes
> proposed for use in the algorithm are prone to disruption by malicious nodes leading to
> ineffective routing.
Real-time distributed path search is a hard problem to solve in a
scalable, secure way. That is why recent protocol ideas have focused
more on link-state advertisements, despite some privacy concerns. A
fully privacy-respecting network isn't much good if it doesn't work.
Jan, in your comments about my link-state routing proposals you
indicated that you did not feel advertising inter-node paths ahead of
time was desirable. I'm not very optimistic about your host based
routing solution, since it seems to require that all the nodes on a
single host form a single well-connected credit network enabling any
node to route any incoming payment to any other node on its host. I'm
not sure that's a realistic assumption.
On the other hand, a host could group always together *some* of its
nodes for routing purposes. There's probably no way to prevent that
actually, and it should just work without special consideration in the
protocol.
For organizing groups of nodes on multiple hosts, what do you think
about my proposal to use a Bitcoin-style block chain for forming a
consensus on who belongs to the group, and who signs the routing
advertisements:
http://ripple-project.org/Protocol/BuildingCellsByBlockChain
Also, I wonder what you think about the following conundrum: I've
been thinking of letting nodes charge fees simply for reserving credit
for a transaction in advance of a commit, because reserving the credit
can block other transactions and could be more easily used as a DoS
attack on the network if it were free. However, in a system where
nodes advertise the exchanges they will make, and the cost of those
exchanges, this might provide a perverse incentive to advertise
deceptively cheap exchange rates in order to win credit reservation
fees, and then cancelling the transaction.
My thoughts are either to not allow nodes to charge for credit
reservations, and come up with other ways to mitigate this DoS attack
(ideas?), or to not allow nodes to advertise their exchange rates, but
simply the fact that they'll make an exchange. I prefer the former,
because in the latter case we're back to the problem of having to
search out an acceptable set of paths in real time, and all the
privacy leakages that can result from attempting to make this
efficient. If the payer has full knowledge of the path ahead of time,
he can encrypt instructions to each node and none of them need to know
who the payer or recipient are.
The problem then becomes how to keep everyone's knowledge of link
states throughout the network up-to-date so very few transactions fail
due to stale information. My idea is that nodes only advertise part
of their available credit, but enough to satisfy most transactions,
and then they won't need to send out updates continuously as
transactions flow through. This also protects their privacy.
Transactions that need more credit availability can use multiple
paths.
Thoughts?
Ryan
> --
> You received this message because you are subscribed to the Google Groups "Ripple Project" group.
> To post to this group, send email to rippl...@googlegroups.com.
> To unsubscribe from this group, send email to rippleusers...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/rippleusers?hl=en.
>
>
Ryan Fugger
transaction goes through, then you haven't dissuaded nodes from lying
about their exchange rates. And if you only refund if it doesn't go
through, then you haven't dissuaded DoS attacks.
I think simply limiting the number of through-transaction requests
from the same node/host over a certain time period could be a decent
way to prevent DoS attacks, at least at first.
Ryan
Daniel
rate than the advertised rate?
Your other proposal could also work, and I think a lot of questions like
this would best be answered empirically through actual practice rather
than specified too far in advance...
Ryan Fugger
> How about if you refund the deposit when the lender asks for a different
> rate than the advertised rate?
>
Because it doesn't work that way. The payer encrypts a message to
each intermediary saying what exchange rate he would like, and each
intermediary can say yes or no. If the intermediary ahead of you says
no, you have no idea if it is because of the intermediary falsely
advertising a better exchange rate than they actually offer, or the
payer asking for something unreasonable, or insufficient credit on the
next step, or even if it was that intermediary that said no.
> Your other proposal could also work, and I think a lot of questions like
> this would best be answered empirically through actual practice rather
> than specified too far in advance...
>
On the other hand, if a lot of people get value tied up in the network
and then a bunch of it gets stolen because a flaw in the protocol, we
may not get a second chance... I don't want to delay forever trying
to ensure it is perfect on the first go, but I would like to try to
have solutions ready for flaws that I can see on the face of it before
putting it out there.
Ryan
Romualdo Grillo
I'm in the third chapter.
Daniel
There's too much to respond to fully in just a post but obviously the
paper has already sparked some new major discussions and will presumably
lead to more.
I think the economics overview is useful as background for people to get
a decent understanding of Ripple's context. I learned a lot about graph
details relevant to us from the sections on paths and routing. I'm
excited about where this can lead in terms of useful production
services, and of course I'm sure others will find more interesting
theoretical directions.
Thanks for sharing!