Quote from: kano on February 20, 2015, 10:28:51 AM

Everyone on p2pool has to have the same shares and agree the same shares are valid.
Thus the share chain exists and is based on the BTC block chain idea.

If you remove the share chain, you have to keep a pool database of shares (yeah something I know quite a bit about Tongue

)
You suddenly need a full fledged database that's able to store all the shares required and also ... the biggest issue of all ... ensure that database is the same on EVERY p2pool node ... so how do you do that? Share chain ... Tongue

Yes, there needs to be some data structure (which you call a database) to keep track of all of the shares. The point I'm raising is that the structure for linking the shares together does not have to be a chain. In a chain, each link has one parent and one child. This forces the serialization of share mining and submission, which causes performance problems for parallel and distributed systems. I'm proposing that we instead use a different structure, such as a directed acyclic graph (which I previously incorrectly called a tree).

You don't need to ensure that the database is the same on every node. There are some types of differences (a couple of extra leaves on the DAG, for example, or orphans on the share chain) that do not cause problems. You just need to ensure that if someone sends you a share, you can find all its (recent) ancestors and ensure that the submitted share rewards them all appropriately.

Essentially, the problem falls to how you deal with branching. Let's imagine shares as if they were mathematicians. Pythagoras proved a^2 + b^2 = c^2. Euclid referenced Pythagoras when he wrote Elements on the subject of geometry. Skipping a few years, Newton created calculus while making use of Euclid's geometry. At about the same time, Leibniz created calculus while making use of Euclid's geometry. A century later, Euler used calculus to define the number e. Who does he credit for calculus? If we're using a share chain, then even if Euler knows both Newton's and Leibniz's works, he has to choose one of them to ignore simply because they didn't know each other's works. What I'm proposing is that we allow Euler to credit both Leibniz and Newton at the same time, as siblings in science. Then, when Riemann comes along and cites Euler, we know that Riemann inherited influence from both Leibniz and Newton, and we don't have to stiff Leibniz just because Newton was better connected. Heck, we could even have the Indian genius Ramanujan (early 20th century) reference both Riemann (19th century) and Madhava of the Kerala school (14th century), so long neglected by Europeans.

When verifying a share (i.e. a candidate block), you collect all of the ancestors of that share and ensure that the candidate share includes appropriate payouts to the mining address associated with those ancestors. As long as you have verified all of the immediate parents of that share (of which there might be 10), you will also have all of the more distant ancestors. If you are missing any of those parent shares, you can get them from the node that's forwarding the candidate share to you, and then you can recursively verify those, etc. until you get to the height limit for the PPLNS system.

One (optional?) constraint that makes sense for which shares can be incorporated: all parent shares must have been efforts at solving the same bitcoin block. No need to reward work that is actually obsolete. Something else might be needed here. Need to think about it later.

The main benefit is that verifying shares and switching the share you're working on to one that's based on the most recent published shares is no longer time-sensitive. If you aren't working off the tallest share branch in existence, the shares you published will still probably be incorporated into the share DAG. Thus, even if new shares are being published every second, you don't have to rerun GetBlockTemplate() and flush the work on your miner for many tens of seconds, and possibly hundreds of seconds. The only constraint is that you need to publish your share early enough that it's cited before a new block is found.