Nano sharding (next-level block lattice)

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

Disclaimer: This was previously posted as a comment on the horizontal scaling thread, Colin kindly suggested that this is a new topic. I am not an engineer so this might be obviously flawed and I may be using the wrong terminology.

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).

The idea is a seeding system that essentially maps 'regions' of the ledger (account sets) together with node IDs (signatures). You would input the sender's public signature, and the node (self) public signature, and the algorithm would output a set of node IDs to contact.

Terminolgy

  • Mapped and unmapped: A mapped node contains the account of the specific address in question as determined by the algorithm and is capable of confirming it. Mapped nodes are a subset of all the nodes for any given account - thus saving local ledger space. Unmapped nodes are incapable of verification of the transaction in question because they do not hold the account information.

  • Adjacent: two nodes that are aware of each other's presence as "mapped" for a given transaction, via the algorithm.

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 random set of mapped nodes). The output of the algorithm is essentially the adjacent blocks (eg. 6 nodes).

Process
Your wallet connects to a node with it's transaction.
This node uses the algorithm to generate 6 mapped node IDs and sends the transaction on to these nodes. If the initial node is itself "mapped" then the 6 node IDs will be "adjacent" nodes (a two-way concept similar to blocks on a 3-D map), if the inital node is not mapped the algorithm will generate a set of 6 mapped IDs (using the sender's key as a seed).

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 not necessarily trusted (as we only require 1 of the 6 adjacent nodes to be honest). This is to reduce bandwidth waste.

The node then sends the transaction and its approval signature (if it is itself "mapped) to these 6 "mapped" nodes, which, due to the algorithm's design will all also contain copies of the account in question's balance (by nature of being mapped). These nodes check that any approved sends come from an adjacent node (using the algorithm since adjacency holds two-ways). If the transaction is sent by a non-adjacent node then confirmations are discarded. Thus confirmation of a send can only be transmitted via directly adjacent nodes.

These 6 mapped nodes then 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....

Consensus
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 can be used to effectively resample weighting results (by requesting weighting from all adjacent nodes 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).

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.

So what
With a large node network, this should reduce the bandwidth use on any one node (as the majority of nodes will be able to ignore/and not be contacted for a given transaction). Worst case, a sender could contact an "unmapped" node, and that unmapped node may be malicious and not use the algorithm but send the transactions to other "unmapped" nodes. However, eventually an honest node will use the algorithm to locate mapped nodes and then contact those, thus avoiding any further waste of unmapped node resources.

Equally by each node holding a subset of the ledger, this should increase reduce storage required - even if the algorithm and "node address book" add some extra mbs initially.

Close
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.

2 Likes