A network that consists of a mixed, decentralized, and distributed core, mixed PIR outer layers, variable latency via proof of work, multi data-type support, built-in multi host network support (clearnet, i2p, tor, etc cross communication) and the ability to completely hide who on the network is the recipient.
I think that mixing is very important for strong anonymity. PIR is also very useful but great care needs to be taken in how it is implemented. Cross network communication is a possibility, although it might be better to base it on top of Tor. In the case of routing nodes, it is better if they all share a common anonymity network.
CORE
The core network is a mesh topology in which all members exchange all data. Similar to Freenet.
In Freenet all members usually act as routing nodes and data stores, but all members don't share all data. All members sharing all data sounds more like BitMessage, and I don't like this because I think it will scale poorly. I also think that if all users are routing nodes that the anonymity of the network will be hard to ensure, when clients act as routing nodes it tends to open up the risk of intersection attacks. Freenet has managed to do this in a pretty secure way, but I2P is very vulnerable to intersection attacks due to essentially all clients also being routers. BitMessage is also very weak to intersection attacks due to all clients being routing nodes. Tor has substantially protected its users from several sorts of intersection attack by not having all clients act as routing nodes. Another issue with all nodes being routing nodes is that it will dilute the ability to mix messages. Mix networks are actually more secure if they have less routing nodes, because then more messages mix together at each hop. With a network like Tor the anonymity depends on the size of the network, because the goal is to prevent an attacker from observing both ends of a connection, and the more nodes there are, and the more geographically distributed they are, the less likely it is that an arbitrary attacker can view traffic as it enters and exits the network. With a mix network though, generally we would assume that the attacker is already capable of watching all links between all nodes, regardless of how many nodes there are. The anonymity of a mix network depends on the amount of traffic on the network, and particularly the amount of traffic passing through the utilized mixes, and if there are only a few mixes then there is much more traffic passing through all of them and therefor the anonymity provided significantly increases.
Data is exchanged between machines using a mixed PIR retrieval system. Machines would accumulate data until the threshold is met. They would then mix and advertise their new data to the connections they have. The connections have the option to retrieve all, none, or some (Using PIR) of the advertised data.
That is an interesting idea. A pull rather than push mix network. Normally in a mix network, one of the mixes receives so many messages and then they reorder them and send them on to the next mix on the messages path. Your proposal seems to be that mixes obtain so many messages, and then they reorder them and advertise that they have them, at which point other nodes on the network can pull them with PIR. There are two important points to consider. The first point to consider is, how do the pulling nodes determine which messages they pull? In a traditional mix network, the client selects the path of mixes that the message travels through. The client needs to have public keys for the mixes on the network first, which they obtain via bootstrapping with a set of directory servers. So the client doesn't need to tell each mix individually that it will use it on its path, it merely needs to construct a message that will be routed through each of the mixes on its intended path. If the client communicates with mixes telling them which messages to pull, the anonymity of the system is reduced to the anonymity the client has when constructing their path when they communicate with each of the mixes telling them the message to pull. If the message is tagged with the next mix on the path, then the PIR will be useless since the mixes will already know which messages are being pulled by which mix.
One possibility is for the messages to be tagged with an ECDH shared secret generated with the mixes long term public key and an ephemeral keypair generated by the client, with the ephemeral public key also attached to the message. If all mixes pull all attached ephemeral keys, they can derive shared secrets with them and then pull messages tagged with shared secrets that match shared secrets they generate with the attached ephemeral keys. This would require all mixes to obtain all ephemeral public keys though, and to derive ECDH shared secrets with all ephemeral public keys. That probably wouldn't scale very well.
The second thing to take into consideration is that generally PIR that isn't everybody gets everything assumes that a message is present on several non-cooperative servers. This opens up the strong possibility of intersection attacks if there is a large distributed PIR network. Because if my outgoing message is on 5 servers only, and the next layer of mixes on its route pulls the message with PIR from these servers, then the message is identified as being one of the messages that is on each of the 5 servers being pulled from. Unless all of the people routing messages use the same exact path as me, this will severely degrade any provided anonymity.
Data that is transmitted across the network consists of two parts. The first part is a small identifier for the second, larger, part. The identifier would include the proof-of-work done on the message as well as an encrypted header for the second part. Once the accumulation threshold is reached then the first part is what is announced/sent to connections for advertising new data. If a connection already has one/some of the data being advertised, they will leave it out of their request list to the announcer. This also allows PIR operation to happen unannounced. Additionally this group can/may be padded.
Sounds a lot like BitMessage, and it will likely be weak to some of the same attacks that BitMessage is. For example, if Alice has a message before Bob does, then Bob could not be the sender of the message.