Horizontal scaling

There was some recent talk on Nano subreddit by /u/BuyNanoNotBitcoin which I would like to explore here.

So, DAG structure of the Nano ledger theoretically allows to implement "shard nodes" - nodes which vote on (and keep the ledger of) transactions involving wallets from some subset of addresses. Implementation of such nodes would turn Nano ledger into some kind of distributed storage and would allow to scale almost infinitely.

Basic suggestion: allow shard nodes.

"Shard node" by definition is a node which is vouched for by "Master node". It is allowed to vote on transactions instead of master node. If multiple shard nodes (or shard nodes and master node) vote on the same transaction, only one of the votes are considered (it is a byzantine behavior, similar to node voting twice). Master node can revoke shard node permissions at any time.
I think it requires only small changes to the protocol?

Now, what can we do with these shard nodes? Say, 100 redditors decide to gang up and create a distributed node, best in existence. They choose some master node (there is as much trust in the whole thing as in the master node, want to point this). Some users delegate to the master node, master node gives permissions to the every shard.

Now, every shard picks some subset of address space (they can even adjust it dynamically later). They also choose the subsets in such a way that every address is held by multiple shards (2-3 is enough).

When the transaction comes, only shards which have the sender address in their subset even look on it. Of these shards, one knows it needs to vote (it is first in some order which is obtained from the hash of the transaction). Shards also periodically ping each other to see if anyone went down - in which case, they arbitrage to the master node, and it judges it by proof of authority.

After the transaction is settled, the shards inform other shards of relevant pending blocks - i.e., if transaction is from A to B, then all shards which handle B need to be informed about pending block.

Possible byzantine behavior by shards is easily detected by master node: if some shard decides to vote on things it is not supposed to, and this vote ever gets rebroadcast to the honest shard, it provides the proof of such behavior to the master node. If some shard refuses to vote on things it is supposed to consistently, it also can be detected (albeit, a bit harder).


It is important to organize shard cluster in such a way that network bandwidth is not a bottleneck. I think shards need to be peers of each others if their subsets intersect, and outgoing connections should be distributed randomly in the cluster.

3 Likes

This sounds like a standard cluster configuration with each node responsible for a subset of the keyspace. The rep key would be installed on each machine and the cluster can be of arbitrary size.

This can be done right now without any protocol changes.

The only differentiator is there isn't a way to revoke keys as can be done in your scheme.

1 Like

Yes, the change to the protocol required is miniscule. But it is needed to allow non-trusted parties to contribute computational effort. Do you think it could be done without this change?

I think if such system is implemented we will be able to scale theoretically on retail-level nodes only!

1 Like

Couldn't non-trusted parties simply contribute computational effort by donating money to the rep? Wouldn't that be somewhat simular? And then you would not have to trust the non-trusted parties either, or create a system to trust non-trusted parties

1 Like

Distributed computation scales much better.

Edit: also it is easy to contribute computation because basically everyone already has a PC.

How about this: Those 100 redditors starts mining on their computer, donates the money to the rep and and the reps owner scales the node horizontally/vertically based on how much money comes in? :stuck_out_tongue:

Think you are joking. Building 100x more fast computer is much harder than rallying up 200-300 redditors to plug in their old laptops. Come on.

1 Like

It's a click of a button if you're using a cloud provider. If those 100 redditors would donate 1$ a month you could probably get a decent beefy server. Would love to see calculations on how much dollars give how much cps.

We should get some specifics on what needs to be changed and the upgrade path difficulty. New node release, canary block, or epoch?

It seems like what you're describing means revokable authority, rather than completely non-trusted peer or relying on consensus from the reps in some way. The fault would lie on the rep as long as they didn't revoke authority from the mal-actor.

I think it would at least be worth designing the non-protocol-changing scheme and I think a lot of people would benefit from that first step. We can build more complex versions of that afterward. The key difference from what you describe is it's a single rep key that is divided between multiple nodes in a trusted way, standard cluster cluster configuration, rather than having a revocation scheme that is fed through full ledger consensus.

The drawback is the rep key is irrevocable so it must be trusted. The advantage is it requires no protocol changes and more complex variants would likely build off this structure anyway so it's a good first step.

The main question to be answered with both of these schemes is how does the cluster communicate an agreement on the parts they are responsible for? Violations of this, as you said, are byzantine faults. This agreement does not need to go through ledger consensus along with normal transactions, the QoS for cluster agreements should be better and really only nodes in the cluster need to come to agreement, not the entire network.

5 Likes

Ok, so basically we need cluster node anyways, and it is an independent problem. Good point, change to the protocol might be so minor it should be done afterwards.

1 Like

People have talked about this before and I'd rather have a solution before it's required. If anyone can work out a design we can queue it up for implementation.

2 Likes

This is called vertical scaling. It's largely considered an anti-pattern. We shouldn't be relying on anti-patterns for scale.

1 Like

I think there's two separate solutions here:

  • Horizontal node scaling.
  • Network sharding.

Horizontal node scaling is more straight-forward since it requires minimal protocol changes, if any, and is now standard practice for server side applications. Network sharding is far more complex and it's riskier, but it may eliminate the need for horizontal scaling altogether, and may provide more scalability overall.

One of Nano's greatest strengths is its asynchronous nature, but I think this strength is largely squandered by relying on vertical scaling. Nano's network is a textbook candidate for some sort of partitioning, but no partitioning is done, either at the node level or network level.

For Nano to reach the scale necessary to become a daily currency, one of these proposals needs to be implemented and needs to be a priority, because both will be exponentially more difficult to implement over time.

I would consider Nano's lack of one of these solutions to be severe technical debt.

Just my 2 cents as someone who works on 1 million CCU systems.

3 Likes

What are the main barriers to modelling a network sharding type structure on eth 2.0/cardano's solutions?
Obviously, the code will have to be different, but surely the conceptual distributive model can be replicated and then tinkered with as needed.

I'm not sure it would eliminate the need entirely, within each network shard it would be desirable for validators to be able to configure horizontally.

Partitioning of which parts? I'm curious. I have ideas for vote-bandwidth partitioning but that doesn't seem like the highest priority to me.

1 Like

Sharding of which parts? P2P currency requires global consensus which is the most expensive operation.

1 Like

Shard node ideally should be configured to say "pretty please rebroadcast only relevant info". Eventually, when most stuff is sharded, the whole network will look like separate graphs of shard nodes, with some connections between the shards of the same shardnode cluster.

Do you have some better topology / network organization in mind?

I’ve been designing is a topology where votes can be filtered at a network level based on accounts the node is interested in. Since consensus on things a specific node is interested in can be less expensive than consensus on everything, via relaying and caching, it can help most nodes except PRs.

1 Like

"To boil it down, the main 'innovation' I'm proposing is a predefined, immutable addressing system that makes it possible for a web of nodes to map together uniquely for each account address."

Disclaimer: I am not an engineer so this might be obviously flawed and I may be using the wrong terminology.

I was referring to sharding in a more generic way I think. First imagine each node holds a subset of the state block record (which I go on to call a ledger, don't ask me why haha).

I'm thinking about a seeding system that essentially maps 'regions' of the ledger (account sets) together with node signatures. You would input the senders public signature, and the node (self) public signature, and it would output a set of node IDs.

An analogy for visualisation:
Forgive me for the crude analogy, but I'm envisioning minecraft blocks with the sender signature as the world seed, and the algorithm reads the node signature as coordinates (if the initial node does not contain the account in question then it selects a spawn point (near the centre of the world)). Node IDs are blocks near the spawn point and build out from there as new nodes come online. The output of the algorithm is essentially the adjacent blocks (eg. 6 nodes).

Consensus
The node then sends the transaction and its vote to these 6 adjacent nodes, which, due to the algorithm's design will all also contain copies of the account in question's balance. These nodes repeat the process the signatures and block spread like dye in water, through our node-mapping structure. As currently occurs, if a node uncovers a conflict, quorum is triggered....

For PR vote weighting, with a correctly designed algorithm nodes should be able to only consult their partial ledger to observe weightings, the 6 adjacent ledgers should be placed such that sufficient global ledger coverage ensures that no PR weighting estimates are unbiased (although they will be imprecise in practice). However, in areas of conflict adjacency limits can be expanded (ie from 6 to 24 considerations) and a blending function that allows nodes to submit their weighting results (along with a signature). Honest nodes then adopt this blended weighting and resubmit their quorum result. I think sufficient iterations of blend-adoption cycles should resolve (although I think the 51% security would be lost to something significantly lower).

Once each node reaches quorum (confirmation) on the send, it then uses the algorithm; inputing the receiver's public key (seed) and its own key (coordinates) (note this will be its own if it holds the account, otherwise random spawn - this is handled by the algorithm since it knows which nodes hold which keys).

The node then contacts the 6 adjacent nodes generated (by the algorithm), with the quorum confirmation and the send block. As all relevant nodes will do this, multi-spawning of the confirmation result will occur to allow the same consensus format as previously described (checking adjacent nodes are consistent). If another conflict occurs, the receiver's address nodes are able to use the algorithm to resample the quorum set manually, before running another consensus process (I'm a bit sketchy on my knowledge here if this is either unnecessary or insufficient to guarantee the receiver receives the confirmed transaction).

Note: this would require a node ID to url address ledger of some kind, held only among the nodes. It only has to be maintained but not necessarily trusted (as we only require 1 of the 6 adjacent nodes to be honest). This is to reduce bandwidth waste.

A few notes on said "algorithm"

  • This is very easy to run forward (to determine addresses), but impossible to run backward (such that a wallet cannot preselect the nodes it wishes to store on) - it would have to continuously re-roll to 'game' the system, which could be made difficult with the anti-spam measures proposed by rob.
  • The algorithm essentially maps new 'adjacency' sets for each public address, that can be easily generated by any node. The algorithm is designed such that when a node is 'unmapped' for a particular public key a random set of mapped nodes (near the centre) is generated.
  • These adjacency sets fit together like a map, spreading out from a central zone.
  • This algorithm would need to also be generating node addresses (so it's likely nodes would need to migrate addresses to a new system).

To boil it down, the main 'innovation' I'm proposing is a predefined, immutable addressing system that makes it possible for a web of nodes to map together uniquely for each account address.

By writing this, I suppose I am hoping that there is something in all of that guff that might inspire the geniuses among you. But that is what I'm imagining and I have a feeling that a lot of the issues can be ironed out with some clever maths.

The p2p nature requires that any address can send to any other so we must assume any transaction sender will attempt to circumvent the sharding algorithm and force it to take a worst-case path.

Your suggestion doesn't seem to improve the worst case path, so it should improve some usual-case situation. With the vote filtering it filters the usual case that nodes are only interested in a specific set of addresses.

Which usual case are you trying to address i.e. which resource consumption are you trying to improve?