I saw an interesting article that I think is revelant to this community:

https://medium.com/@kelvinfichter/whats-a-sparse-merkle-tree-acda70aeb837

Basically, it's an extention to Merkle tree's so you use the tree as a Key/Value store and allows you to create simple merkel proofs that a value for a specific key doesn't exist. This can help solve double spends, prove censorship etc.

Interestingly enough, the underlying data structure was developed by Google for their certificate transparency effort. https://www.certificate-transparency.org/.

What I'm trying to understand, is how sparse merkel trees improves upon more traditional authenticated dictionaries. Authenticated dictionaries that use a red/black tree or skip list merkle tree structure that seem to have similar performance. Additionally, proof-of-non-inclusion can be constructred by providing proofs to the left and right of the target key.

Can anyone please enlighten me how sparse merkle trees improve upon more traditional approaches to authenticated dictionaries?

Hello,

I have come with a tweak on directed acyclic graph blockchain structure which reduces latency. Basically, each user has their own personal blockchain "swimlane", and these chains are linked together temporally through witness hashes. There is no chance of un-intentional forking. You will still need to define a consensus function to deal with bad actors. If someone tries to attack by splitting their "swimlane" for example, consensus could choose the lane which has the most witnesses or just permanently ban them from participating in the ledger.
 
Here's a basic idea of what I'm talking about:


A whitepaper.
https://www.scribd.com/document/386713928/Restricted-DAG

Please let me know what you guys think. Thank you!

Absolutely agreed on this point, though I think if we really abstract away the application from the content data, we have no way of knowing the transaction is valid or not. If I'm not running BitUber, how would my client determine if the BitUber transactions are valid.

Also in my opinion, you are fundamentally responsible for being your own block emitter. If you want to spend a cryptocurrency you obtained, and your blocks have not propagated enough you may need to provide the store with a large packet containing all the blocks/chains necessary to fully trace the inputs to your transaction for validation.

Nothing is stopping someone from someone having many chains, one for crypto-currency (keep it small) and another for content (Large!).

Thank you for your input. I look forward to hearing your design.

Decentralized Social Media:
Quietly I've developed a decentralized "message board" application on top of Blockchain technology. It does not have the issues with centralization that PoW mining leads to. I have the basic concept implemented but it's not ready to be released publicly. Unlike imnotback, I will describe my specific approach .

The basic idea is this: Instead of a "Single Global Blockchain" where there is contention to get your information into the chain through mining, every user has their own chain. They hash their previous header/new data then sign it from their new header (like traditional blockchain). Here's the difference: instead of mining, the header includes "witness hashes" pointing to the most recent blocks from chains of their peers. The "witnesses" prove your data is more recent in topological time, as well as provide a vote to prevent a "double spend" attack in other chains. This structure forms a DAG which can be sorted in linear time.

In order to form "chain communities", people can subscribe to 1 or more "root" blocks. The software client looks for subsequent blocks which have cryptographic traceability to these roots. The person who created the root block may publish branching messages on their chain pointing to other peers chains. This will inform software clients that they may also follow these other peer chains of they so choose. The peers chains can issues branching as well. If one of these chains starts spamming too much information/branches the client has configurable rules to discontinue following these sub-peers. Each person for themselves can determine how much of the network they can handle store, etc.

The End Result: "chain communities" every single block/message is un-censorable and has full traceability back to the root (like in blockchain). My design has all the benefits of the chain, (integrity, non repudiation, byzantine fault tolerance, etc.) while being low-latency (< 1sec) by avoiding PoW mining. It should be resistant to Sybil attacks, spammers, double spends as far as I can tell. You could build crypto-currency applications, smart contracts on top of it if you so choose.

Let me know what you guys think.