[ANNOUNCE] Whitepaper for Bitstorage - a peer to peer, cloud storage network

[Sarchar]

Bitstorage - A distributed, peer to peer, cloud data storage network based on blockchain technology.

Whitepaper at http://dropcanvas.com/m942t

This is just a rough draft, and it heavily depends on coming up with some improvements to the distributed Proof of Data Possession (PDP) strategy, but I believe the incentives are all in the right place.

I intend to start this project over the next few weeks.  Feedback welcome.

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

$ md5sum Bitstorage.pdf
d5483a62bb3f735a86543d2fb650c67d Bitstorage.pdf

RIPEMD160(SHA256(d5483a62bb3f735a86543d2fb650c67d)) = 883f641127ca05a96224c8c4a937117c287b431f
Bitcoin Address: 1DRQqZmYZeoc4kRE8pjiVq3tn7KqUfBeor

Transaction 52ffd13473d68eb68d48b88dbe259699a75a05a0f1e556d577c127b1da6bfb80


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)

iQEcBAEBAgAGBQJSlfH8AAoJEBSq1Xfbtr1c5s4H/3mmDzva5AzNRFx5ZiYILUrD
x4fXiZvQU1ECFw3e3rZeesSG5OEsZ711OF2pT/J9WyXgW9jsO7WCUgoHDN9nEg+j
H8YM+nYgzwrZrf44cbePbwEnLFthCxNs88PgokEegsWpLP6Xha4o8yBnKuxq7Bj+
yjiQJheWGYpOdWf1rJeFG6/K5j9myULZpfy8txHVUv29pbhA5+fqwDPIzv4wXBob
/14/ZGXgTTVH4r9/t5VOKVXBCEoYVWRL7/2qmpXaHJlJtoxZg2WlMNYa2KDvLDZk
d0edNi2KJTzlQi3BSgTTvSzZm9ylpbGZ424heIyymjeW+i8DjBWyGe7wDiLVpgo=
=qBc0
-----END PGP SIGNATURE-----

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: GnuPG v1.4.10 (GNU/Linux)

mQENBFKV4jcBCAC3isJW4DG3bsFqvkWorFkGDkX10EtAGOcMy8XzA+jxBim1qgzw
ry2eWNDa4XYozW8g6awQ/lWOpat8NBcnEyscDAAldM6dV/ymJItKZ6TW4alxDdk6
OwrcMp/7qf60j529rcbnXNNwov5lXoqp3IxT/Iqwk7e1IkJt4D80EpbMeFvtH6aB
WV27aWDfBzSjl+JhfAsyLnQRPxfcC4jpUAzXKub5akBS9AgUSApMeub9Q4pXvudY
O4w4Q0i20AQ/EjQNgqbkDj7L+QXFh17P8k1ojH1a7bNAdpqjDNR7gR3b/paJzi8U
Y+LLHet20/RXORJ99ApfDh5NzOSegWULBYfZABEBAAG0G1NhcmNoYXIgPHNhcmNo
YXJAbG9jYWxob3N0PokBPgQTAQIAKAUCUpXiNwIbAwUJCWYBgAYLCQgHAwIGFQgC
CQoLBBYCAwECHgECF4AACgkQFKrVd9u2vVwuKwgAptl7NkiFFDfXpjjWadZIVJUv
AXAnjr5yI3BUCpquAXauOtS3lwfi+yvCDmOIPkSq4+yQxA8q6JyQxKPsYDo4M84i
DaPjpo0uyryU4aKB1rpnVQoUY/KQQgX4kSLGrxzq6lV8O2EycmRk0Lss1zc1nYx8
g6nNiUZRrgs1kLdnCFIF5aRwq+ChIslpm9bCd2O+lALTp9FRY1nVgHgrs0J3ut7v
ZOxsHFvcGw/MfHFambTR+u+X6ib7zn3o8LCy4BUb+2bQF253Tx4ze+Xa1e3g/jCo
5AYXzaLbJxjSFyOO8A/M2GYJCMbIbSQuw9zr6/IaT0fUm5H5UriagVxMI9yuHLkB
DQRSleI3AQgAyBcA+D7DEAwDIKYfH569tDINWuIQcGBaMgteaxX4DBIGmCt0gC/Z
qEtJP8V1o1RQAgA5ks/v7YzmINyLYUMB4WI6FyrLVldL8adPg7KAx3iqAZVGHTol
6j21Wi8poB8c1m3aYx21M9aJOzAcF3nuZk/9pHz+G+Gk9NJVvD1/CyHLl8qB8jb3
nIDYfQeaeSqotEZvaqwkDy1RdnxDlyj9AUePubGXhFfAMycRSuhh7qdNyqWiEgu0
1YydxXc+m8fiF+klHy6DQeeIMg0SzUpLab5brMDNkft0O7rVjgZcXKf+e9uCBDuo
G3YKAAxqnV5H2jy8LrjFOvTmjT5SseqwZQARAQABiQElBBgBAgAPBQJSleI3AhsM
BQkJZgGAAAoJEBSq1Xfbtr1cmEAH/j0Obtzb+AokpkfdAJx5fdn6cg1yivXSIpke
qbYkeeVa7Udm3v1CTFvlQczSLvRX8d8JD618ZZS/rConsFVvMEcdlBB41kTbg/Xu
aR2BoK/5mlWF2o/f2M/zaqleG4EAY6MyJd0AkIwNePT402jCqGloXLamgLNyE0lv
v4wjP0nV2H4fy5rf55SIjduLRMLYUXlhftGNUxn3L40qtuzZ0XXPHbNL7IVL1Sca
UqA4opv906X3EaLOlr4pTspFYeWknGOnLmwH7pBehqYLBlmLoMP6E1hSiXxuXpp7
srhYUnILkvMXciVK/FBQKa6goJ+VrJfzm9R/bhDhoPZ5S3Tm5gM=
=U9o1
-----END PGP PUBLIC KEY BLOCK-----

[1714776815]

1714776815

[1714776815]

1714776815

[Mike Hearn]

Hey there!

Very cool stuff. I just wanted to say hi and point out that myself and Simon de la Rouviere have been implementing something a bit like this for a while, but not as ambitious or complex. We're very much about building something up one brick at a time rather than aiming for the stars right from day 1.

We start with the foundation of micropayment channels, and paying for bandwidth to download files. You can see a video of the app in action. It's still got a few bugs and other issues to resolve before it's released for regular users, but it's real code and it works. You can view the source here.

Once there are servers that can charge users for downloads, the next step is to allow uploads of data and micropayments for proof of storage. I'm thinking that a client can calculate a series of hash challenges and each time the server passes a hash challenge, the client increments the micropayment channel. An Android app would be ideal for this because it's typically always on and nearly always connected to the internet, so waking up at night every few days to check the files are still there and make a payment is quite straightforward. Also, we've done some work on exposing micropayment channels via a local RPC interface to the Bitcoin Wallet app, so an app that wishes to use micropayments on Android doesn't have to manage their own wallet. The main wallet app grants permissions over subsets of the users balance to individual apps.

Once you can upload, download and store files on a specific server for micropayments, the next obvious leap is to join the servers together in a simple broadcast/advertisement network. Not really a full blown DHT but just a way to find servers that are advertising their services (this is the "TradeNet" for anyone who saw my talk in Edinburgh). Then clients can seek out the cheapest/best servers and start using them.

All this is very complicated because it has to be done in a low trust manner. For instance, a malicious server could advertise the lowest price possible and just attract all the business, and there are various subtle knife-edges in micropayments, like transaction malleability attacks, that require changes on the Bitcoin side.

But overall I think it's simpler than an entirely new block chain and P2P network, and it has the advantage that every few months or so you could release an actually useful piece of software and build up your userbase slowly.

Get in touch with simondlr on this forum if you're interested in taking part. He'll be on vacation for a couple of weeks though soon. I don't anticipate much more coding on this until the new year.

[Sarchar]

Sounds similar? Can we collaborate? BTW, I like your name better

Well, your writing is much nicer than mine, so I appreciate that.  I'd be interested in seeing more how your system works.  Can you share some documents?  

Very cool stuff. I just wanted to say hi and point out that myself and Simon de la Rouviere have been implementing something a bit like this for a while, but not as ambitious or complex. We're very much about building something up one brick at a time rather than aiming for the stars right from day 1.

That's probably the best way to do it, building piece by piece, I mean.  I checked out your video and it's cool, but it has its limited usages (peer to peer micropayments is a freaking cool thing).  Does it work or can it be adopted for things like public WiFi usage?

How would you accomplish the proof of storage challenge if the original author of the data isn't available online to challenge (or the user loses his metadata required to produce those challenges)?  I think part of the strategy that I'd like to see a distributed approach take is for the "blockchain" to be the source of the proof of possession challenges.  The randomness of block hashes would be the seed of the challenge algorithm and miners would verify those challenges and receive payment in a coinbase for doing so.  

Is your TradeNet talk available somewhere?

[jspilman]

Is there some mechanism for preventing a single node storing a single copy of the data, and then spoofing multiple identities and claiming payment as-if the data were stored across multiple nodes?

The obvious solutions are proof-of-work or proof-of-stake, but I can't see how proof-of-work alone would suffice.

If the expected cost of performing the proof-of-work is greater than the reward for storing the block, then no one stores it. Otherwise, what's to stop an attacker from generating multiple possession-txs in order to claim all the available payments for a given storereq-tx?

Proof-of-stake would at least provide some capital reserve to allocate to each identity, then you could add a field for minimum proof-of-stake amount into the storereq-tx, and/or you could use it as an ordering criteria instead of the Kademlia distance.

[Natanael]

Please look up Tahoe-LAFS, and how it can be used with I2P! Tahoe-LAFS is developed by experienced computer scientists and cryptography experts. I2P is an anonymization network. The combination is a far more flexible and advanced decentralized storage system than Freenet, and is under active development with flexible access control features.

https://www.i2p2.de and https://tahoe-lafs.org

[Sarchar]

Is there some mechanism for preventing a single node storing a single copy of the data, and then spoofing multiple identities and claiming payment as-if the data were stored across multiple nodes?

No and yes, that's kind of the point though.  If miners are honest and pick only the N closest nodes (using the Kademlia distance metric), then there's high chance that the data will be distributed amongst at least >1 nodes.  The more requested nodes in the storereq-tx the greater the chance the data is actually distributed.  Metrics that show how dense the identities around your data are can give you an indicator of how likely it is that multiple nodes store the data instead of just a few. The more nodes you're willing to pay to store your data, the more secure your data is.

The obvious solutions are proof-of-work or proof-of-stake, but I can't see how proof-of-work alone would suffice.

If the expected cost of performing the proof-of-work is greater than the reward for storing the block, then no one stores it. Otherwise, what's to stop an attacker from generating multiple possession-txs in order to claim all the available payments for a given storereq-tx?

I imagine they would try, but like I said earlier, payments should go to only the closest nodes to data. As the network grows, there will be too many identities that trying to get closer to a given data block wouldn't be worth it when you can just store some other data that you are actually close to. Managing a lot of identities and data blocks quickly becomes an exponential problem.

Proof-of-stake would at least provide some capital reserve to allocate to each identity, then you could add a field for minimum proof-of-stake amount into the storereq-tx, and/or you could use it as an ordering criteria instead of the Kademlia distance.

I will look into it, and TBH I haven't considered proof of stake for this.  Sounds intriguing.

[Sarchar]

Please look up Tahoe-LAFS, and how it can be used with I2P! Tahoe-LAFS is developed by experienced computer scientists and cryptography experts. I2P is an anonymization network. The combination is a far more flexible and advanced decentralized storage system than Freenet, and is under active development with flexible access control features.

https://www.i2p2.de and https://tahoe-lafs.org

As far as I can tell, Tahoe-LAFS doesn't offer any incentive for me to contribute my storage and bandwidth to the network.

[Natanael]

Sarchar: That can be added easily. You could simply rent out storage space.

[Sarchar]

Sarchar: That can be added easily. You could simply rent out storage space.

To whom? Who's responsible for fulfilling the payments? How do you fairly get paid for that storage?

[Mike Hearn]

That's probably the best way to do it, building piece by piece, I mean.  I checked out your video and it's cool, but it has its limited usages (peer to peer micropayments is a freaking cool thing).  Does it work or can it be adopted for things like public WiFi usage?

It's a general framework. Yes, paying for wifi access is possible (more possible than you might imagine).

How would you accomplish the proof of storage challenge if the original author of the data isn't available online to challenge (or the user loses his metadata required to produce those challenges)?

If the challenge metadata is stored in the same place as the micropayment channels, you either lose both or neither. I think that's solvable. The challenges don't have to be big. If you want 1000 days worth of storage, store 1000 80-bit hashes and you're done, right? 10kb of data is trivial.

Is your TradeNet talk available somewhere?

Yep, see the top video and slide deck beneath it here:

http://plan99.net/~mike/

(unfortunately, the slides in the video are hard to see and washed out)

[Sarchar]

That's probably the best way to do it, building piece by piece, I mean.  I checked out your video and it's cool, but it has its limited usages (peer to peer micropayments is a freaking cool thing).  Does it work or can it be adopted for things like public WiFi usage?

It's a general framework. Yes, paying for wifi access is possible (more possible than you might imagine).

Cool. I'm going to look more into this project.

How would you accomplish the proof of storage challenge if the original author of the data isn't available online to challenge (or the user loses his metadata required to produce those challenges)?

If the challenge metadata is stored in the same place as the micropayment channels, you either lose both or neither. I think that's solvable. The challenges don't have to be big. If you want 1000 days worth of storage, store 1000 80-bit hashes and you're done, right? 10kb of data is trivial.

I think that would be a problem in a distributed environment with terabytes of data meant to be stored indefinitely.  The paper linked in my document describes a crypto method that allows for infinite challenges with O(1) metadata storage requirements less than a few kb in size.  That metadata can easily be stored in a blockchain.

Is your TradeNet talk available somewhere?

Yep, see the top video and slide deck beneath it here:

http://plan99.net/~mike/

(unfortunately, the slides in the video are hard to see and washed out)

Thanks.

[Natanael]

Sarchar: That can be added easily. You could simply rent out storage space.

To whom? Who's responsible for fulfilling the payments? How do you fairly get paid for that storage?

Your node offers storage space for a price. Clients pay. You store the files. You can integrate proof of storage and more and use Bitcoin's scripts to make sure neither side is at a significant risk of getting screwed over. It's not like it can't mimic most of the features of Bitstorage.

[Peter Todd]

Is there some mechanism for preventing a single node storing a single copy of the data, and then spoofing multiple identities and claiming payment as-if the data were stored across multiple nodes?

That's impossible unfortunately - no amount of math can prevent a node from outsourcing the actual storage to a central location that is a single-point-of-failure.

The best you'll ever be able to do is pay enough that there is incentive to do the job right, and/or use social/legal mechanisms to audit what node operators do and then arrange these transactions with specific operators. Not terribly exciting solutions unfortunately...

The obvious solutions are proof-of-work or proof-of-stake, but I can't see how proof-of-work alone would suffice.

Yeah, proof-of-work can only prove IO bandwidth, not where the data is located.

However... interactive latency measurements can prove data within some sphere of radius t*c. With multiple trusted challenge servers around the world located in co-location centers one could easily prove that the data must be physically present in multiple locations.


You can even do in a fully decentralized way with some extensions to the Bitcoin scripting language by creating a txout that can only be spent by proving you have some data fragment, where the fragment is chosen randomly based on the previous block hash.

Because the fragment is based on the previous block hash, there is a time limit to how quickly the fragment must be retrieved, thereby proving (after sufficient trials) that the data is physically located within a sphere of radius 10minutes * the speed of light - currently this would prove the data may be physically located on Earth, the Moon and Venus, but no other planet. With a second proof-of-work blockchain established on, say, Pluto, we could then easily prove a similar result for data located on or nearby Pluto. (proving the Pluto proof-of-work blockchain is in fact located on Pluto is left as an exercise for the reader)

[jspilman]

Because the fragment is based on the previous block hash, there is a time limit to how quickly the fragment must be retrieved, thereby proving (after sufficient trials) that the data is physically located within a sphere of radius 10minutes * the speed of light - currently this would prove the data may be physically located on Earth, the Moon and Venus, but no other planet. With a second proof-of-work blockchain established on, say, Pluto, we could then easily prove a similar result for data located on or nearby Pluto. (proving the Pluto proof-of-work blockchain is in fact located on Pluto is left as an exercise for the reader)

I suppose the proof of work could take the previous block hash along with some nonce and then iterate on the data in a 'memory-hard' fashion to add latency. Each nonce+result would be redeemable for a single payment coupon within some fixed time period, e.g. when the next block is found.

I think a good solution to this problem is useful in all sorts of interesting ways... for example, when the blockchain itself is the target data, and the storage payments are transaction fees.

[Mike Hearn]

The E-PDP paper is interesting but my reading of it was different to yours - their sample had to store 128mb of tags for a 4g file. It doesn't have the small overhead you think: it reduces client overhead by increasing server overhead. It's also more intensive - randomized hash challenges boil down to one disk seek on the server (in the best case of an unfragmented file) and some hashing which is fast, whereas their scheme involves lots of hopping around.

Still, I think it's not a huge difference. You could implement v1 using a simpler proof of storage and then upgrade to more complex proofs in a v2.

[mappum]

It all looks pretty solid, I've only come up with a few small issues.

First of all, I don't think there is a need to limit the downloads to nodes that are close and the owner. This prevents use as a CDN, and also, it is trivial to keep generating new private keys until one is found that is close to the desired file.

Also, (this may or may not be a problem) as mentioned in IRC, attackers could also keep changing their data to change its hash to decide what nodes they want to store it.

A bigger problem is that infinite nodes can be hosting the same data while the owner will only pay out to n nodes. The nodes that get to be paid are simply the ones who announce it first, and any attacker can just keep announcing the data they have (unless all nodes are recording all announcements). This could add up to be a lot of data. Even with no attackers, it means potential income isn't guaranteed, and you will lose a lot of it from the bad luck of not being first.

[Sarchar]

The E-PDP paper is interesting but my reading of it was different to yours - their sample had to store 128mb of tags for a 4g file. It doesn't have the small overhead you think: it reduces client overhead by increasing server overhead. It's also more intensive - randomized hash challenges boil down to one disk seek on the server (in the best case of an unfragmented file) and some hashing which is fast, whereas their scheme involves lots of hopping around.

Still, I think it's not a huge difference. You could implement v1 using a simpler proof of storage and then upgrade to more complex proofs in a v2.

Kinda, yeah.  I think in a distributed network, using larger blocks than 4KB (say 32KB) would be much better.  I had envisioned each store request supposed to be less than 1MB in size, so with a 1024-bit modulus that would require 4096 bytes of extra storage.  Increasing the message size to 128KB means only 1Kb extra storage.   Unfortunately, that's data that has go to go into the blockchain.  It'd be nice if there was a better way that allowed for smaller storage + infinite challenges.  

Are my numbers right, here?  

Definitely, the best way would be to develop this in steps, and the first step would definitely not implement the E-PDP algorithm, only a simple hash and verify method.

[Sarchar]

It all looks pretty solid, I've only come up with a few small issues.

First of all, I don't think there is a need to limit the downloads to nodes that are close and the owner. This prevents use as a CDN, and also, it is trivial to keep generating new private keys until one is found that is close to the desired file.

Right, ultimately however, each storage node should get to decide for himself which nodes to allow the transfer to.  I don't think it is trivial, actually. If I have a key that's only a few bits away, it's going to be very hard for you to search for a key closer.  With large amounts of data and keys, it's extremely likely that someone else will be between you and data randomly.

Also, (this may or may not be a problem) as mentioned in IRC, attackers could also keep changing their data to change its hash to decide what nodes they want to store it.

I see this as a benefit, actually: store the same data twice but with two different hashes. You could change the encryption key and/or a nonce in the header.  In fact, this might help distribute your data more effectively.

A bigger problem is that infinite nodes can be hosting the same data while the owner will only pay out to n nodes. The nodes that get to be paid are simply the ones who announce it first, and any attacker can just keep announcing the data they have (unless all nodes are recording all announcements). This could add up to be a lot of data. Even with no attackers, it means potential income isn't guaranteed, and you will lose a lot of it from the bad luck of not being first.

It's not supposed to be first-come-first-serve, but it's supposed to be more like closest-first-comers. It means that if you later join and you're closer than someone else, you can claim the payment if miners decide to throw you in.

[indyjo]

Bitstorage - A distributed, peer to peer, cloud data storage network based on blockchain technology.

Hi Sarchar!

I must say that I really like the proposal. I am currently development something similar: BitWrk - like Bitstorage, but for computing power, not for storage. See this post for reference: https://bitcointalk.org/index.php?topic=179948.0

At first, I had the same reservations as jspilman:

Is there some mechanism for preventing a single node storing a single copy of the data, and then spoofing multiple identities and claiming payment as-if the data were stored across multiple nodes?

We should probably assume that no direct solution exists for this problem.

There is, however, an indirect solution: A reputation system. Just like eBay's. You basically want to create incentive for not creating enormous amounts of fake accounts by offering advantages to users with a long, successful trade history.

Then there is the problem regarding proof of existence. How can I, as the original data owner, verify a proof of existence without being in possession of the original data? When I don't have the original data anymore, that's when I need to verify it the most (otherwise, I would have to accept any data).

My solution is that I wouldn't verify the proof of existence in this case. Instead, the data would contain a signature issued by my, the original owner. So, by downloading the data, I could verify its authenticity (d'ough!).

But then, assume I have downloaded my original data back from one of the storage peers. If I was malicious, I could claim that the downloaded data wasn't my original data. If I did that, the peer would simply publish the data, containing my signature, making it obvious to everyone that I wasn't telling the truth.

All in all I think it can be done. Great work!

As a user, I would prefer to be compensated in BTC, instead of yet another virtual currency.

[tubbyjr]

The concept seems similar to what Datacoin is doing, although I haven't actually read through your whitepaper.