Bitcoin Forum
December 07, 2016, 08:47:24 AM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Proofnet: a P2P broadcast network based on proof-of-work to minimize spam  (Read 5040 times)
Astrohacker
Full Member
***
Offline Offline

Activity: 156



View Profile WWW
July 22, 2011, 10:13:55 PM
 #1

Proofnet: a P2P broadcast network based on proof-of-work to minimize spam

There is no standard decentralized way to broadcast information around the world. After trying to solve many other problems, particularly the problem of trust, I've realized it would be extremely useful to have such a system. The basic idea is to have a peer-to-peer (P2P) network where anyone on the network can broadcast any kind of information to their peers, who rebroadcast the information, until everyone has it. The problem, of course, is spam, since if such a system ever became popular, it would be flooded with valueless spam. One way to solve this problem is to use bitcoins to pay people to rebroadcast your message. But it would be hard to know if you can trust anonymous nodes and thus no one would be willing to spend bitcoins on it. Another method is to attach proof-of-work to each message. This is the method that I propose. Nodes rebroadcast all the messages they can, but give preference to greater work. It would still be possible to spam this network, but it would be expensive. The protocol I've designed for this is called "proofnet". In this article I will explain how the basic message format looks, and describe some applications. If people are interested in this, I will create an example implementation in Python.

The message format

The nodes will be connected to one another in a web. The nodes will then broadcast messages to one another. A message might look like this:

(proof-of-work hash)(message)

The (proof-of-work hash) is a SHA-256 hash of the message that follows. The lower the hash, the more work went into it. Nodes rebroadcast as many messages as they can, giving priority to messages with high proof-of-work (i.e., a lower hash). There are problems with this simplistic format, however. The only way to increase the work would be to change the message. So we should include a nonce:

(proof-of-work hash)(nonce)(message)

The nonce is just a random number that is iterated until the proof-of-work hash is low enough that other nodes are likely to rebroadcast it. Another problem is that spammers might find one high proof-of-work message, and then rebroadcast it again and again. People who just joined the network would be duped by the spam messages. Thus, we should include a timestamp.

(proof-of-work hash)(nonce)(utc timestamp)(message)

Nodes will only rebroadcast messages that 1) they've never seen before, and 2) are fairly new, say within the past 10 minutes. That way, we can be sure no one is just spamming the same old messages. All nodes will need to keep their clocks accurate otherwise their messages will be ignored.

Another problem is that if this protocol became popular, the network would be saturated with messages, and many users would not have enough computing power or bandwidth to be able to participate. So we'd like to allow for separate channels.

(proof-of-work hash)(nonce)(utc timestamp)(channel hash)(message)

The channel hash is a SHA-256 hash of a string like "Proofnet1" or "My awesome channel". The reason for using a hash of the string is to make the format simpler since the hash will always be a constant number of bytes (32), and for some level of privacy, since only people who are privy to the channel name will know what the channel is about (they cannot practically invert the hash to find out).

It's worth noting that the nonce, UTC timestamp, channel hash, and message must all be included in the proof-of-work hash: 1) The nonce must be included to easily allow people to compute different proof-of-work hashes until they get a low one. 2) The UTC timestamp must be included so that you can't just change the UTC time without redoing the proof-of-work, thus you can't just spam old messages. 3) The channel hash must be included so that spammers can't just take a message from one channel and spam it on all others without redoing the proof-of-work. 4) The message itself must obviously be included in the proof-of-work hash so that spammers can't just change the message and rebroadcast it without redoing the proof-of-work. In summary, all information must be included in the proof-of-work hash so that every new broadcast message requires new work.

There is one more piece we need. Since this is going to be a general information broacast network, we need to support different message types.

(proof-of-work hash)(nonce)(utc timestamp)(channel hash)(message type hash)(message)

The (message type hash) is a SHA-256 hash of a string describing the message, like "UTF-8 text" or "JPG Image". We take the hash so that the format is simpler and also to allow for some secrecy, just like with the channel hash. If a client doesn't know what string goes into a hash, it doesn't need to know.

This allows anyone to broadcast any kind of information, and the more computational power they have, the more people will get it. Messages with higher work (lower proof-of-work hashes) are declared more valuable and thus given preference to being rebroadcast. There is no guarantee a given message will make it to every node. The format allows for different channels to exist while not allowing messages on one channel to be rebroadcast on another without redoing the work. It also allows information of any kind to be broadcast and is not limit to text. It allows messages of any size to be broadcast, but longer messages take more work to hash, and thus smaller messages will be easier to broadcast.

Proofnet can broadcast any kind of information, but the standard Proofnet client will include a few applications by default: 1) Text broadcast. 2) Signed text broadcast, like a decentralized IRC. 3) Signed, encrypted messages, like encrypted email, except the recipient is not guaranteed to receive the message. 4) A trust-declaration broadcast system, like decentralized eBay rankings.

1. Text broadcast

Text broadcast is the simplest application. The message type is the string "proofnet:text". And the message is just UTF-8 text. When a client receives this, they can immediately read the message. They will also know how much work went into the message. Messages with more work will look more impressive. The author will be unknown.

2. Signed text broadcast

It is often valuable to know who is sending a message. The message type for this will be "proofnet:textfrom" and the message will take this form:

(message)=(from public key)(public key signature of utf-8 text)(utf-8 text)

This would be like a decentralized IRC. A slightly more sophisticated version could encrypt messages with a password, and only people who know the password could decrypt the message.

3. Private messages

It would be nice to send private messages over this network. The message type will be "proofnet:textto". The message looks like this:

(message)=(to public key)(encrypted message)
(encrypted message)=encrypted[(from public key)(from public key signature of reply-to public key and utf-8 text)(reply-to public key)(utf-8 text)]

People would know they are receiving a message by spotting their public key, but no one else would know who sent it or what the message is. A new reply-to address is included to encourage further privacy. Conversations could take place where the main identities of the participants aren't known, and what they are saying isn't known, except to the people participating.

4. Trust rankings

The internet is filled with scammers. We need a decentralized ranking system, like eBay rankings but on a P2P network. We can do this by allowing public keys to advertise how much they trust other public keys on Proofnet. A "trust ranking" is a ranking between 0 and 1. User X might trust User Y with 0.9, and then User Y trusts User Z with 0.5, and thus User X would know that User Z should be trusted with about 0.45. Trust is relative; objective rankings are meaningless because new identities can be created at will and thus someone can cheaply rank theirself up. Only relative rankings through the web of trust make sense.

The message type is "proofnet:trustrank". The message format looks like this:

(message)=(from public key)(public key being ranked)(signed decimal and message)(fixed point decimal from 0 to 1)(optional utf-8 text message explanation)

To send out a scammer alert, you can give someone a ranking of 0 and put an enormous amount of work into the message. To know trust rankings, you would need to monitor the network continuously, or download them from a service that saves all of them. There could a be a channel devoted specifically to trust rankings, e.g. "Proofnet Trust Channel".

A similar application could be created for a social network, e.g. expressing someone as a friend rather than expressing how much you trust them. The social network could include any arbitrary features we wanted, like posting messages on a wall, posting and labeling images, etc. Since most people will not be on the network continuously, there would need to be services that are on it continuously and will give you the information later. Or rather than using centralized services for this, old broadcasted data could be shared via BitTorrent.

Bitcoin

Proofnet is useful to bitcoin in at least two ways. 1) It might be valuable to encode bitcoin transaction broadcasts in this format, making it harder to spam the network with transactions. 2) The trust network would enable people to know who they can trust on the internet and thus who is worth giving bitcoins to.

Other applications

It is fun to consider how many applications of Proofnet there could be.

* It would be possible to implement decentralized torrent trackers and indexes on Proofnet, eliminating the only central weakness in BitTorrent file transfers. Peers who are seeding a given torrent could broadcast themselves on the "example.torrent" channel. Torrent files could be searched for, requested, and sent via broadcasted messages, in a way that is completely anonymous, except for the IPs that you connect to for file transfer.

* A decentralized data storage service. A request could be sent out to save a file of a certain file size, and responses would come back from public keys with a price given in bitcoins. The user could look at the trust ranking of the public keys of the responses, and also at the prices, and decide who is worth saving their data with. This would be a completely anonymous file storage service, but you would still know if you can trust the people you are dealing with.

* A decentralized replacement for DNS. Names could be assigned to IPs by using the information on the trust network or social network. e.g., if your friend who has a trust rating of 0.9 thinks wikileaks.org points to some address, and your enemy with a ranking of 0.001 thinks wikileaks.org points to another IP, you would trust your friend. This is very different than Namecoin, which aims to establish objective control over names. But in this case, names would be controlled by popular opinion.

* A decentralized Twitter. The message format is just like "proofnet:textfrom" except limited to 140 characters. Messages longer than that would not be rebroadcast. To follow someone, just log on to the channel and display broadcasts from that user, or use a website that logs the history of that channel.

* It would be possible to broadcast images, streaming audio, and streaming video. It would be necessary to put information about the chronological order of a piece of information for anything that is streamed, and there would be no guarantee that every piece would reach every node. There are also bandwidth limitations; one channel would probably only be able to support one streaming video at a time.

* It would be possible to send alerts about important events. If a very important event occurs, then put a lot of work into the message, and people will quickly learn about it all over the world. The more work, the more impressive the message, and the more people will notice.

The P2P network

It does not actually matter what technology is used to connect peers together, although the standard client will obviously support TCP/IP and could be extended to support IPv6 in the future. Nodes can find each other in many ways: 1) An IRC channel could be established for the purpose of allowing nodes to find each other, like with Bitcoin. 2) Nodes could broadcast themselves on the network that they are allowing connections to get more nodes connected that are already on the network. 3) Lists of nodes could be pasted on the web or shared in torrents.

PyProofnet: The first client

I have not actually written a client for Proofnet, but I will if people express interest. It will be written in Python.

Conclusion

Proofnet is a decentralized, general purpose information broadcast system operating on a P2P network and based on proof-of-work, where anyone can send a message to their peers, but messages are only rebroadcast by their peers if they demonstrate enough work. Any kind of information can be broadcast. It is reasonably secure against spammers since spammers would need to do a lot of work to spam their messages. There are many conceivable applications that could be developed on top of this system. Since it is decentralized, it has the advantage over centralized systems that no one can limit what you do with it. I will write an example implementation in Python if people are interested. Comments and criticisms appreciated.
1481100444
Hero Member
*
Offline Offline

Posts: 1481100444

View Profile Personal Message (Offline)

Ignore
1481100444
Reply with quote  #2

1481100444
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481100444
Hero Member
*
Offline Offline

Posts: 1481100444

View Profile Personal Message (Offline)

Ignore
1481100444
Reply with quote  #2

1481100444
Report to moderator
1481100444
Hero Member
*
Offline Offline

Posts: 1481100444

View Profile Personal Message (Offline)

Ignore
1481100444
Reply with quote  #2

1481100444
Report to moderator
Astrohacker
Full Member
***
Offline Offline

Activity: 156



View Profile WWW
July 23, 2011, 10:47:15 PM
 #2

OK I've written some code: https://github.com/astrohacker/Proofnet

You can now construct Proofnet messages. Code is included to iterate the nonce until a proof-of-work hash is found that is below the target. Here is the output of an example:

target: b'00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF'
proof: b'0058EBAD77C56EFC376F6A718857F169D57A8C3E9D797B4B8B110E0CF28DC6F5'
nonce: 105
utc time: 1311461103.877562
channel: Proofnet1
message type: proofnet:text
message bytes: b'My UTF-8 text message.'
base16 encoded proofnet message: b'0058EBAD77C56EFC376F6A718857F169D57A8C3E9D797B4B8B110E0CF28DC6F5690000000000000 0EF4E2B4E00000000E79DCC7E4AB352211F26A90C498ED7C4F03A5319DB76A2748A6C11B58459DB 775DBE83855B3889DBC4A8DF9ADD9EAA9AB164CB1B800B24CF05470D9C018B2E6F'
notme
Legendary
*
Offline Offline

Activity: 1526


View Profile
July 23, 2011, 11:34:32 PM
 #3

Are the messages just broadcast until everyone has seen them, and those that care record them?  Or are you wanting to encode the messages into a block chain?

https://www.bitcoin.org/bitcoin.pdf
While no idea is perfect, some ideas are useful.
12jh3odyAAaR2XedPKZNCR4X4sebuotQzN
Astrohacker
Full Member
***
Offline Offline

Activity: 156



View Profile WWW
July 24, 2011, 04:33:49 AM
 #4

Are the messages just broadcast until everyone has seen them, and those that care record them?  Or are you wanting to encode the messages into a block chain?

Each node rebroadcasts a message once. Since most nodes are only going to be on the network for a short period of time, they also will not rebroadcast old messages even if they haven't seen them (to prevent people spamming the same old messages). The idea is that each message should only get broadcast once, and to broadcast it again, the sender will have to do more work.

There is no block chain. There is no objective record of what was broadcast.
Anonymous
Guest

July 24, 2011, 05:39:23 AM
 #5

It would be interesting to use this for a "wikileaks" net for whistletblowers to broadcast documents too.

Isnt this just hashcash ? Wont botnets just be used to do the proof of work?
Astrohacker
Full Member
***
Offline Offline

Activity: 156



View Profile WWW
July 24, 2011, 04:41:36 PM
 #6

It would be interesting to use this for a "wikileaks" net for whistletblowers to broadcast documents too.

Isnt this just hashcash ? Wont botnets just be used to do the proof of work?

Whistleblowers: Yep. If you have an important document, put a ton of work into your message and broadcast it. People will notice. And it will be anonymous, so long as you can find a lot of computing power anonymously. (Possibly people could sell computing power paid for with bitcoins.)

Hashcash: Hashcash is for email. This is like Hashcash for broadcasted messages. Everyone on the network receives every high proof-of-work message. But if a message is encrypted for someone else, you won't be able to read it.

Botnets: Botnets could spam, but it would be expensive. If spammers become more of a problem for, say, chat, then one solution would be to develop infrastructure on top of Proofnet for a new kind of chat channel that gives op-status to one public key who can then ban spammers. To make it expensive to create new identities and re-enter the chat, you could require one really high proof-of-work message for each person entering the chat. Without that first high proof-of-work message, their messages are ignored.
nookngood
Newbie
*
Offline Offline

Activity: 9


View Profile
July 24, 2011, 08:41:24 PM
 #7

On the practical level, I am having a hard time decoding Proofnet messages from the base16 encoded proofnet message.  Huh
Astrohacker
Full Member
***
Offline Offline

Activity: 156



View Profile WWW
July 24, 2011, 09:33:27 PM
 #8

On the practical level, I am having a hard time decoding Proofnet messages from the base16 encoded proofnet message.  Huh

I have added the ability to decode messages to the latest push on github (although it decodes it from bytes, not from a base16 encoded string). I may have made a mistake in the code I had written to encode messages earlier... I remember having to fix something. But it works now.

Edit: Here's some output of test_decode_message.py which shows a base16 message which is then decoded. There may have been a problem with the earlier message I showed, but this one is possible to decode. I place it here as an example of a working Proofnet message.

base16 encoded proofnet message: b'008C77AF46C1822FC9F837059AE8C6ED170AF5929C7A239ED480871FAD3F9F1EE50000000000000 09FA12C4E00000000E79DCC7E4AB352211F26A90C498ED7C4F03A5319DB76A2748A6C11B58459DB 775DBE83855B3889DBC4A8DF9ADD9EAA9AB164CB1B800B24CF05470D9C018B2E6F4D79205554462 D382074657874206D6573736167652E'
decoded proof: b'008C77AF46C1822FC9F837059AE8C6ED170AF5929C7A239ED480871FAD3F9F1E'
decoded nonce: 229
decoded time: 1311547807.0
decoded channel: Proofnet1
decoded message type: proofnet:text
decoded message: My UTF-8 text message.
Astrohacker
Full Member
***
Offline Offline

Activity: 156



View Profile WWW
July 29, 2011, 08:41:34 PM
 #9

In the latest pushes I am now using the Python unittest framework, and I will now be employing test-driven development (aka TDD) to create Proofnet. Soon I will create some very simple TCP functionality so Proofnet can get up and running.

https://github.com/astrohacker/Proofnet
Astrohacker
Full Member
***
Offline Offline

Activity: 156



View Profile WWW
July 31, 2011, 08:29:14 PM
 #10

Apparently longs are 8 bytes on my 64bit computer, and only 4 bytes on my 32bit computer. In order to have compatibility with 32bit machines, I've changed the message format so that nonces and timestamps are now 32bit unsigned ints rather than 64bit unsigned longs. I discovered this because my unit tests failed on my 32bit computer. Now the unit tests pass on both my 64bit and 32bit computers.
Astrohacker
Full Member
***
Offline Offline

Activity: 156



View Profile WWW
July 31, 2011, 11:32:24 PM
 #11

You can now encode and decode proofnet:text messages from the command line. I've tested this on my 32bit netbook, Ubuntu 11.04. Example:

astrohacker@ah-nb> ./b16encode_text.py "this is my test message"
003A183EAB5A45A72CCBC8C45B622A40443889B49DBC724FC96D126D2AAF4787E700000018E5354 E6DEB35011A633E4C91202D569C2EABCDF28D6CAF2DD4B62D8E886F83773CF2AD5DBE83855B3889 DBC4A8DF9ADD9EAA9AB164CB1B800B24CF05470D9C018B2E6F74686973206973206D79207465737 4206D657373616765
astrohacker@ah-nb> ./b16encode_text.py "this is my test message" --nzeros=16
0000CACABC9716072D1F4548CC824CD6DA72D35198A72CD34180B80DE75815F45F3401001FE5354 E6DEB35011A633E4C91202D569C2EABCDF28D6CAF2DD4B62D8E886F83773CF2AD5DBE83855B3889 DBC4A8DF9ADD9EAA9AB164CB1B800B24CF05470D9C018B2E6F74686973206973206D79207465737 4206D657373616765
astrohacker@ah-nb> ./b16encode_text.py "this is my test message" | xargs ./b16decode_text.py
this is my test message
jackjack
Hero Member
*****
Offline Offline

Activity: 868


May Bitcoin be touched by his Noodly Appendage


View Profile
August 01, 2011, 12:51:25 AM
 #12

This is relevant to my interests

Too bad Python3 is needed

Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2
Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc.
Sukrim
Legendary
*
Offline Offline

Activity: 1848


View Profile
August 01, 2011, 09:43:35 AM
 #13

Isn't it a systematic flaw that I, if I want to for example store a message as secure as possible, have to have more hashing power than someone who would like to see this message gone?

In the end, all that spammers have to do is run a dozen GPUs in the basement - rarely any normal user will be able to compete with that, so they either have to buy hashing power from someone or not use the system.

https://bitfinex.com <-- leveraged trading of BTCUSD, LTCUSD and LTCBTC (long and short) - 10% discount on fees for the first 30 days with this refcode: x5K9YtL3Zb
Mail me at Bitmessage: BM-BbiHiVv5qh858ULsyRDtpRrG9WjXN3xf
AgoristTeen2
Jr. Member
*
Offline Offline

Activity: 32



View Profile
August 01, 2011, 02:41:15 PM
 #14

This definitely seems interesting though I'm left with a couple of questions...first how does the proof-of-work work exactly? like for example, how do I put more work into a message? Also I don't really understand the hash talk much, so....do you know where I could go to learn more about that?

Astrohacker
Full Member
***
Offline Offline

Activity: 156



View Profile WWW
August 01, 2011, 03:12:38 PM
 #15

Isn't it a systematic flaw that I, if I want to for example store a message as secure as possible, have to have more hashing power than someone who would like to see this message gone?

In the end, all that spammers have to do is run a dozen GPUs in the basement - rarely any normal user will be able to compete with that, so they either have to buy hashing power from someone or not use the system.

That's why there is more than one channel. If spammers, or your enemies, are spamming up one channel, you can use another. The spammers would either have to concentrate their computing power on one channel, or spread it thinly across many.

There are other ways to minimize spam. Proof-of-work doesn't have to be the only metric for deciding if a message gets rebroadcast or not. Different channels can have different rules. It is actually up to each node to decide whether or not to rebroadcast a message, so presumably they would voluntarily employ the right rules for the channel they are in. If a majority of nodes chose different rules, those rules would win in that channel.

One option is to only rebroadcast messages that are encrypted with some password. Only people who knew the password would be able to participate in that channel.

Another option is to require people to send a very, very high proof-of-work message as a let-me-in message, signed with their private key. Only people who have recently broadcast the let-me-in message would have their messages rebroadcast. Then you can personally block people if they start to spam.

Another option is to have moderators on some channels. All messages signed by the moderators always get through. They can issue commands to the nodes, for instance to issue a white list or black list of identities that can participate.

Unfortunately, it will always be the case that some people have more computing power than others, so proof-of-work will never be perfectly democratic. However, since we all live in the same technological generation at the same time, we actually will always have roughly the same amount of computing power, so proof-of-work is actually not terribly undemocratic.
Astrohacker
Full Member
***
Offline Offline

Activity: 156



View Profile WWW
August 01, 2011, 03:18:48 PM
 #16

This definitely seems interesting though I'm left with a couple of questions...first how does the proof-of-work work exactly? like for example, how do I put more work into a message? Also I don't really understand the hash talk much, so....do you know where I could go to learn more about that?

A hash is a function that cannot be easily inverted. To do a lot of work on some data, you just find the hash of the data+nonce, where the nonce is just a number that you iterate. As you change the nonce, the hash is different. Find a hash that starts with a lot of 0s. If you find a hash that starts with, say, 10 zeros, that proves you had to do roughly 2^10 operations to find that hash. So you can prove you've done lots of work on the message. To do more work on a message, keep iterating the nonce until you find a hash that starts with more 0s.

This is the same technology that bitcoin uses to secure the block chain.
AgoristTeen2
Jr. Member
*
Offline Offline

Activity: 32



View Profile
August 01, 2011, 04:18:48 PM
 #17

Okay thanks.

Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!