Proof of Nodework (PoNW) is a way to reward individual nodes for keeping a full copy of and verifying the blockchain.
Hopefully they also do useful ‘traditional’ node activities too like relay transactions and blocks, but there isn’t really any way I can think of to trustlessly verify this.
PoNW would require a new separate area of block space, a nodeblock, purely concerned with administering the system. A nodeblock is committed to a block as with SegWit. A recent history of nodeblocks needs to be stored by nodes, however the data eventually becomes obsolete and so does not need to be retained forever.
In order to prevent Sybil, a node must register a Bitcoin address by submitting an addNode transaction – along with a security deposit to prevent cheating.
This transaction will be stored in the nodeblock. Once a node can see that its addNode transaction has been added it can begin the PoNW process. The node’s registered address will be hashed with the block header of the block it wants to work on. This will determine exactly where within the blockchain to begin the PoNW.
The PoNW method could be as simple as creating a Merkle tree from the randomly generated point on the blockchain, though a method that is CPU/Memory heavy and less likely to be outsourced to dedicated hardware like ASICs would be better. This process could not begin until the most recent block has been fully verified, and while being carried out should still enable normal relay activities to proceed as normal, since it shouldn’t tie up network at all. The data processed should also be mixed with data from the latest block so that it cannot be computed in advance.
A node can do as much PoNW for a block as it likes. Once finished it will then create a nodeWorkComplete transaction for that block with its final proof value, add how much ‘work’ it did – and create a couple of assertions about what it processed (such as there were x number of pieces o...