Topic: [Announce] Project Quixote - BitShares, BitNames and 'BitMessage' - page 9. (Read 48264 times)

If you follow some of my old posts on the BitMessage forum I had an idea of hierarchal streams based upon bits in the address.  The problem is this opens up a new kind of attack where your address can be isolated and forced into a stream with only messages for you and the attacker.   I also don't want people to have to change their 'address' just to change channels. 

How is that different to Bitmessage? Users can change and move to new addresses if they wish, it just requires the hassle of telling your contacts that you have moved to a new address

Also with a global broadcast channel, will there not be a scalability issue when there are 12 gazillion users needing to 'discover' each other?


Anyway, it would be nice if the hiding_in_the_crowd mechanism could be somehow decoupled from a user's address.

Here is a less than well thought out proposal...

We assume that the set of users' addresses (public keys) are uniformly distributed.

We can define a 'crowd-specifier' as being an address prefix such as '1ab'

• Any address with that prefix can be considered part of the crowd

When Alice sends to Bob, instead of attaching the 'stream_id' value to the message, she will attach a small prefix of Bob's public key address.

• The size of the prefix is chosen s.t it encompasses a minimum 'crowd-size' to prevent observers from inferring the true recipient

When connecting to the network, Bob, then provides his peers with a crowd specifier prefix, according to his particular needs at that moment.

• He may want to be part of a bigger crowd and give a shorter prefix
• He may lengthen the prefix if the messaging system starts to demand too much HDD space or bandwidth

Perhaps there is a less naive way to perform the partitioning, with the use of some hash functions.

BitChat in our system does not fix a user to a stream.

All users are in stream 0 which is the 'discovery stream'.
When you 'friend someone' you share with them your stream ID.
You can switch stream IDs at any time and notify your friends that you moved.

Thus dynamic load balancing is possible.

Yeah I realise this, im just wondering if the current implementation of Streams is a little too much of a blunt tool. Perhaps something better could be developed.

Just reposted this from the other topic...

So this is my understanding of the use of Streams & POW in Bitmessage. Please correct me if I am wrong...

[POW]

Proof of work acts as a limiter on the ability of someone to post a message over a broadcast channel.

• It serves to deter SPAM.
• By making it more expensive to send a message, it acts as a way to reduce the number of messages sent over a channel, reducing the bandwidth+storage costs of each node.

The POW difficulty need not be static but could adapt dynamically in an effort to constrain the bandwidth + storage requirements of each node to some fixed level

• One could have different POW requirements for each channel

[STREAMS]

If there were no Streams, we would be left with a best-effort broadcast channel.

• This would force each node to be responsible for the relaying and storage of a huge number of messages.
• Or the POW difficulty would be so high as to render the system useless
• It would not scale.

So we partition the network into a number of Streams, where each Stream is a best-effort broadcast channel.

• Each identity is assigned to one stream (it is fixed in the BM address).
• Some streams may be more active than others, node requirements(bandwidth/storage) will vary.

Partitioning is an effort to even out the network load.

• The only opportunity to do this load balancing and create a new partition is when a user wants to create an identity (BM address)
• If the current stream is deemed 'too busy', the identity will be created on a brand new stream

Once a stream is established, there is nothing the network can do to make itself more efficient and more evenly distribute the load on the nodes.

• It must resort to making it more difficult to post messages, by increasing POW difficulty
• This will likely not be in the user's interest

At my current level of understanding, it seems to me that Streams are quite a rigid mechanism. I see two problems:

• Once a stream is established, it cannot be re-partitioned because each identity is directly linked to a particular stream
• There is a trade-off between cost_to_run_a_node and level of anonymity. If a stream is quiet, the node's own messages will be less well hidden than if a stream was really chatty. In the current system, the user is less empowered to make a choice based on his own individual needs.

Thoughts ...?

We can talk about that on this thread.    From an abstract sense, the security provided by bitmessage is based upon hiding in the crowd.  You hide which messages are for you by privately picking them out of the stream of data flowing by your computer.   Unfortunately it doesn't scale to have one stream of data so an alternative method of grouping messages such that only 1 / 1000 are destined for you is required or you have to revert back to inbox based designs...

So lets consider this problem from the perspective that not all people require the same level of security.   For example, it is pointless to hide the fact that you know most of the people you interact with in real life.   The government already knows who you work with, anyone you use a credit card with, anyone whom you text message or call on the phone, and anyone who you ever use regular email to communicate with.   Adding a lot of overhead to 'hide' this connection between you and them is pointless.  It only adds value to those who want to establish a new contact with someone and want to keep that contact secret (say sending something to wikileaks).    I suppose there is some benefit to hiding how often you exchange messages with your friends and family but it is certainly pointless to hide that you know them.

As a result you can modify BitMessage to directly connect to most of your friends and family.  The existence of the connection doesn't reveal any new information to an observer.   You then send both regular anonymous traffic as well as direct messages / emails / chat  to your friends and family.   Now you no longer have to deal with expensive streams with proof-of-work that get broadcast to the entire network.  Instead your direct communications are hidden by an encrypted TCP connection that is simultaneously multiplexing BitShares, BitDNS, BitChat, and BitID messages.   Thus no 'streams' required for most of your communication.  For your secure anonymous needs where you want to hide your IP address you have to fall back on a streams based design.

I hope this helps and if you have ideas that are better I welcome them.

Could we get another Bytemaster thread for discussions about the Bitmessage sequel ...

Ive posted on the Bitmessage topic but its pretty well buried on the 20th page https://bitcointalksearch.org/topic/m.3055421

Basically I was just wondering if there could be an alternative approach to 'Streams' as it seems a little inflexible, but it is possible that i misunderstood something.

Now you know where I stand.

https://bitcointalksearch.org/topic/m.3057936

Those following this thread may be interested in this poll..

https://bitcointalksearch.org/topic/m.3054804

I believe I can use economics to defeat centralization of mining in the hands of ASIC developers and those with economies of scale.    Ie:  If I put a fixed limit on mining payout to $5 million per year, the no one would invest capital in ASIC development.    But with bitcoin's $200 million / year payout the equation is entirely different.

See the other thread for my analysis of the security implications.   This is all just theory, but I think I might have something here.

AnonyMint... your comments on this forum have earned you some notoriety.. http://www.reddit.com/r/Bitcoin/comments/1lfuev/innovation_is_spreading_the_cryptoecosystem_is/

We are preparing terms for a large competition (estimated prize at $10,000 (no commitment on that yet)) for the generation of the best possible proof of work that will achieve the following goals:

1) Keep things decentralized, optimized on commodity hardware widely in circulation.
2) Motivate the development of better general purpose computers, ie. R&D on mining has outside benefits.
3) Can be validated very quickly.
4) ASIC resistant and GPU proof.

I hope you contribute your PoW work to the effort because everyone benefits from sharing knowledge.

I don't think so. Btw, in addition to that link, I have another unarguable point on how to achieve anonymity in the blockchain, which gmaxell says is "off topic".


Exactly my point at the first link above. [redacted] Realize that stealing coins is effectively from both blockchains, since the dominant blockchain is issuing all coin supply.

P.S. I spent more time researching my PoW scheme, including such issues as direct-mapped vs. set associative L1 caches. That will give you a hint.

I actually managed to find a way of protecting the higher-POW chains.  Effectively, the only light-weight/decentralized/signature is proof of work, so the only way to 'sign something' from one chain to another chain is via proof-of-work which means that the signature of 'one chain' handing value to 'another chain' could be forged with POW and thus instead of a 51% attack allowing double spending of your own coins, a 51% attack allowed stealing of 100% of the weaker chain while leaving the main chain secure.

Perhaps your logic was something like this.

If coins are allowed to be moved between blockchains at par (no market exchange variance) and the blockchains don't exchange coins at par with any blockchains that don't adhere, the problem remains that 50% attacking the blockchain with the lowest PoW difficulty will infect with ill effects the blockchains with higher PoW difficulty.

I have to choose between white papers and writing code.   I am trying to do a brain dump to some others who will hopefully produce the white paper.

Bottom line: 
Read the BitMessage white paper.   
Replace their address discovery / key lookup system with BitID.   
My message encryption scheme is similar to theirs.
Broadcast message with similar system to BitMessage... with the following changes:
     1) proof of work scales difficulty on any given channel to maintain 128kbit/sec average
     2) alternative proof of work, lighter weight version of BitShares POW that is memory and CPU hard and GPU resistant but still runs in about 1 ms.
     3) channel 0 is the discovery channel (everyone listens on) and is restricted to small messages
Storage:  Fixed sized storage for emails per channel.  To broadcast a new email you must bump someone else from storage.
     1) weight of message in storage =  (1 month - age_of_message) * proof of work on message / size of message.  (this equation may be tweaked to make it non-linear)
          - result is a defined maximum disk usage per channel, maximum 1 month, market-based priority on storage time.
     2) all messages of any length are compressed with the best possible algorithm we can find for the message... trying multiple algorithms if necessary.
Contacts:
     1) works like skype, you can add friends which will then share which channel you are listening on with your friends.
     2) automated sharing of a common private key for chat rooms and mailing lists.
Real Time Communication:
     1) The fact that you are communicating with your family is no secret, so certain contacts can be flagged to allow 'direct connect'
           -- the only thing revealed by doing a direct connect is that you *might* know this person.
           -- when and how much you communicate with this person is still hidden  (unless you start doing large-file transfers)
     2) From the outside, direct connections look identical to all other communication channels.
           -- packet sizes and timing should appear similar enough
           -- doubles as a normal peer-to-peer connection.
     3) From the inside, direct connections do not require proof of work.
     4) Control the number of hops on the network via 'indirect connect',  you and your contacts clients will pick a random 3rd node that you will both connect to.  This node does not know it is being intentionally chosen, it just sees two incoming connections.  Network latency is no longer 'arbitrary', but can be kept to 1 hop.   This is slightly more private than a direct connection, but still requires proof-of-work.

Then implement it with much better software architecture that allows the system to be used for more than just human-readable messages, but for data between software components.

I am sure we will find other improvements along the way, but that is the rough outline of our objectives.


     

You got an ETA on the Secure Messaging whitepaper? I would likely be keen to work on a few bounties on that project

Also I just frikin love this open approach to development. I hope it will succeed and set a precedent for others to follow

There is some inertia with mining and also the 'set-it and forget-it' management.  Which would probably provide enough dampening to cause all chains to approach average.

That said, I can see some benefit for encouraging some merged mining.  Though I don't think it needs to be as exaggerated as it is in your approach.

I think you could achieve some compromise between:

reward / (depth^1)   and reward / (depth^2)

Perhaps along the lines of reward / (depth^1.5).

It would be nice if there were some principled approach to figuring this out.

I cannot follow your argument, why miners would merge mine with your given equation.
Let me illustrate it using a simple example:
We have four chains A,B,C,D with block-reward/difficulty:
A: 5.6 BTS
B: 5.2 BTS
C: 4.8 BTS
D: 4.4 BTS

A merge miner would have a merkle branch depth of 2 and therefore with your equation an average reward of 5 BTS. Therefore it is less profitable in comparison to mining on A, which will directly give you 5.6 BTS reward. Therefore all miners will switch to A and do single mining and nobody would do merge mining.

You might argue, that after time this will decrease the mining reward in A and B because people will switch to it, and increase it in chains C and D. So there might indeed be a fix-point at which all four chains have a reward of 5 BTS. BUT this fix point is not very stable, because as soon as you perturb the system, all miners will switch to the chain with the highest reward.
So the whole system of all your chains will only contain miners, who do not merge mine, and the system will get oscillatory behavior.
You might argue, that your adaptation of your block-reward is so fast, that it will dampen these oscillations. But, my original point still remains: It is insecure because an attacker can easily obtain 50% hashing power in one of your chains, because nobody will merge mine, because they will seek the maximum profit in the chain with the currently maximum reward.

If we look at the same example and you use my modified equation, where you give a reward of block-reward / merkel-branch-depth, then a merge miner will get an average reward of 10 BTS. Therefore you would give an incentive to do merge mining (and thereby also to run full nodes in many chains). This would be much more secure, while you still lower the reward.

Secure messaging system works as follows, if it can be modified to utilize the above that would be great.

Lookup User's pubic key with BitID  =>  RecvPublicKey

Generate a one-time PrivateKey  => SenderOneTimePrivKey and  SenderOneTimePublicKey

Calculate a ECDH shared secret...    SenderOneTimePrivKey * RecvKey  => Shared Secret.

Create your message  TXT
SIG = SendPrivKey.sign( SHA256(TXT) )

AES_ENCRYPT( SharedSecret,   (TXT + SIG) )  => EncryptedMessage

CHECK = RIPEMD160( Shared Secret + EncryptedMessage)

Broadcast:  SenderOneTimePublicKey + CHECK + EncryptedMessage

The receiver will then test each of their private keys like so:

RecvPrivateKey * SenderOneTimePublicKey => Recv Shared Secret
TEST(RIPEMD160(Recv SharedSecret+EncryptedMessage) == CHECK)
AES_DECRYPT( Recv Shared Secret, EncryptedMessage )  =>  TXT + SIG

Recover SenderPublicKey via  SHA256(TXT) and SIG

Note:  this algorithm has not yet been audited so any feedback is appreciated.

I have been meaning to get back to this topic.   I put a lot of thought into it.   Allowing users to merge mine with 0 extra cost opens up potential attack vectors where a 'legitimate block' and an 'attack block' are mined at the same time with no additional cost to the creator.   In fact, it allows people to subsidize their creation of alternate histories.   So allowing it to be 'free' is not wise.  

Assuming all chains are of 'equal' value, then my algorithm if discounting the mining reward proportional to the tree depth^2 would result in equal payout for mining vs merged mining.   This assumes that all chains follow the same rule.

What is the goal of merged mining?   In my view it is to share one set of hash power across the entire network.  With the depth^2 discount, hash power is shared but profits are identical assuming the two chains have equal value.  

If one chain has more value than the other (different dividend payouts, different reward rates, different markets)  then merged mining is a calculated / speculative risk.  You divide your hash power evenly between them, but your immediate payout will be the average value of the two chains rather than the sum of the value of the two chains.   Both chains still benefit from added security.  

New chains do not have to follow the same rules, and to drive adoption may allow 100% reward even with merged mining until the difficulty reaches some threshold.  This would change the economic calculation on merged mining yet again such that as long as the alt-coin had at least 50% of the value of the 'main-coin' then it is more profitable to merge-mine.  

@bytemaster
You still haven't replied, so I guess you overlooked my post?
Do you agree to my point? Or do you have a fundamentally different understanding of how a multi-chain system should be secured by mining? My point is, that merge mining does not only increase the reward of the miners, but it is actually very important for the security of all chains. Without merge-mining, all chains are insecure because chain-hopping of mining resources will make it easy for an attacker to gain 50% in individual chains.
Or do you think that my reasoning is flawed? Then why?