Sharding designs compendium

Thanks for sharing @jamesray1

The Spectre paper claims that the protocol is ‘secure’ (as defined by them i.e. satisfying Properties 1-3) if the attacker controls less than 50% of the computational power.

I believe Lamprot, Shostak & Pease showed that this is only possible in a world without firewalls, else any distributed network is only safe if an attacker controls less than 1/3rd of the computational power.
(Theorem 3 in https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf).

Do Sompolinsky and Zohar simply assume that there aren’t any firewalls? If not, how do they get to 50%?

2 Likes

Looking at the blog post they have a DAG not a blockchain

So there seem to be no global ordering of transactions and the theorem does not apply.

But if there is no global ordering, you cant really run smart contracts on it …

1 Like

Hence why they introduced PHANTOM, which has global ordering, AIUI.

Appendix E of the SPECTRE paper spends a significant amount of space to proving the security threshold, I suggest you look over it and see what assumptions they make and whether or not they are valid. To my knowledge, they make no assumptions of firewalls, but I would like to see where that assumption is made implicitly.

You can also deviate from their specification and create a past ordering ex post facto by combining the DAG into a summarized version that becomes a chain. You can have a separate rule for resolving cyclic precedence of transactions.

Re-read the paper … The ordering these guys are proposing does not have any upper time bound so it is useless, since an attacker can make it arbitrary long.

Essentially there is no time T after which you can assume a particular region of the chain to be stable. Therefore, the ordering is useless since an attacker can wait an arbitrary long time before screwing a particular part of the chain.

As @ns2808 noted this thing if true would contradict existing proofs for consensus ordering.

But this is only true for the attacker’s transactions. Honest participants can get very high probability their activities will not be reversed very quickly. You can attach a block to the genesis block, but that doesn’t mean the rest of the DAG will accept your block. In fact, most of the blocks will vote against your block, so I don’t see how you can “screw with the chain” as easily as you make it sound.

Unfortunately you can not separate honest guys from bad guys.

If an unfinalized attacker transaction is at a later time finalized in front of a previously finalized honest user transaction, it could be a double spend or all kinds of other things.

Essentially for smart contracts to run one needs to have a chain which is reasonably settled and stable.

This comes to the point I guess that there is no free lunch.
For a usable consensus less than 1/3 of nodes can be byzantine, it is a math theorem.

If you relax that you get a mess which one hardly understands at all, and is, therefore, not secure. Hashgraph is a good example.

I’m not sure I follow. An attacker can be defined as trying to spend the same tokens twice. If that happens, then as noted previously you cannot accept one of the transactions robustly. If you add a rule to reject non-robustly accepted transactions after some period T, then you can resolve the double spend and it will fail. If there is no double spend, then there is no conflict to cause the transaction to not be accepted robustly.

The only times where transactions are not accepted robustly is when a double spend is attempted, and the paper goes to considerable length to show that if an attacker does not have a majority hashpower they cannot create a DAG that is robustly accepted.

Could you perhaps explain what you mean in more detail?

This is what the paper says at the end

“. It is of yet unclear whether we can further achieve a linear ordering without compromising the fast confirmation times.”

Things without linear ordering have little use, definitely before a smart contract runs you got to have linear ordering

Smart contracts are trusted programs that require linear ordering before operation. Maybe one can introduce smart contracts on DAG without linear ordering - they will probably be so exotic though few people will use them …

Right, which is why I suggest some deviations from their spec (in the case of SPECTRE), namely a time to finality that rejects non-robustly accepted transactions, or you can go the route suggested in PHANTOM and use a k-clustering technique of the block headers to get a linear ordering. In either case, it seems like there are some improvements in both protocols that can be integrated into future versions of Ethereum to improve scalability.

1 Like

I think we can totally have a smart contracts in a system w/out a total linear order on TXs without making our smart contracts exotic at all. Imagine if we insisted on a liner order for TXs interacting with any specific smart contracts - but if two transactions touch totally unrelated accounts, we don’t have to order them (and the blocks can be mined concurrently).

In many ways, this would be preferable to the system we have currently - it’s probably more scalable! That being said, I don’t think this is what the above papers suggest.

You are right, they aren’t exactly what the above papers suggest, but I think they inspire a line of thought that is good for scalability in general. That is exactly why I suggested we take a look at them :).

Nate - I agree

An simple example of a system without total ordering is a system of multiple blockchains that interact using asynchronous messages (such as sharding) - as you said it is much more scalable that a single chain …

I updated the post to make it a wiki to refer to not just PHANTOM and SPECTRE, but alternative sharding and other protocol designs.

Ethereum should have a dataflow programming smart contact language, Ziliqa style.

1 Like

I added another paper: Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for
Cryptocurrencies

Alternative blockchains

RapidChain: A Fast Blockchain Protocol via Full Sharding

is also an interesting idea posted on IACR’s eprint archive.

1 Like

I haven’t read all of it.

Commentary:

To verify cross-shard transactions, RapidChain’s committees discover each other via an efficient routing mechanism inspired by Kademlia [46] that incurs only a logarithmic (in number of committees) latency and storage. In contrast, the committee discovery in existing solutions [45, 40] requires several “gossip-to-all” invocations

We’re already working on this with gossipsub

Third, to ensure the members of C out agree on the same block, they participate in a Byzantine consensus protocol that we construct based on the synchronous protocol of Ren et al. [58].

It’s a synchronous protocol for committees, and partially synchronous for the rest of the protocol.

The paper is also in a UTXO context, which makes the whole protocol substantially different.

A node who wishes to participate in the protocol for the next epoch will be admitted to the system only if it can solve a fresh puzzle before the next reconfiguration event.

It’s also PoW.

Yep, definitely a different design space, but it’s interesting to come across a paper focusing on this from a UTXO standpoint.

1 Like