Timeline for Is there an "additive" proof-of-work?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 23, 2015 at 15:51 | answer | added | John Tromp | timeline score: 2 | |
| Nov 21, 2014 at 22:43 | comment | added | John Meacham | Oh, actually, since it is a hamiltonian path, just list the node numbers in order, no need for a bitset. actually, might as well make it a pure travelling salesman then, for 256 cities, seed a CPRNG with your IV and take out 256*256 numbers which will be your distances, the proof of work is just 256 bytes, each the index of the nodes in the order they should be visited. the proof doesn't grow, they just get reordered. | |
| Nov 21, 2014 at 21:35 | comment | added | John Meacham | No, the proof is a bitset that never grows. it simply has a single bit for every pair of nodes for whether it is in the spanning tree or not. You need not include the graph or its weight because it is generated algorithmically via a hash of the IV. the proof of work is constant in size. Completely random graphs have fairly predictable qualities so i think you should be able to get a useful measure of work out of it. The only time the proof of work grows is when you completely exhaust a graph in which case it becomes the IV for the next one, but you can delay that indefinitely by going bigger. | |
| Nov 21, 2014 at 2:03 | comment | added | SDL | The proposal has some merits, but fails to satisfy the requeriments in several aspects: the proof size is unbounded, as long as the graph expands. Also the additive propery is lost when a new graph needs to be created, since you need to verify all previous graphs. Last, it would be very hard to set the difficulty increments in such a way that every increment corresponds to a predefined work. | |
| Nov 20, 2014 at 0:32 | comment | added | John Meacham | oh, once it 'runs dry' you can use the hash of the best solution to seed a new bigger graph to keep it going indefinitely. Not sure how to evaluate how fast this grows but i think it can be made to be within your bounds. | |
| Nov 20, 2014 at 0:29 | comment | added | John Meacham | How about take a random IV and put it through a cryptographic hash, take the hash result and use it to construct a random weighted graph via a deterministic algorithm. proof of work is the IV and a minimum spanning tree of the graph constrained to 2 edges per node (travelling salesman), work done is how close your minimum is to the statistically expected minimum. It will eventually 'run dry' and you are relying on assumptions about how to estimate the minimum and maximum spanning trees of random graphs, but those seem surmountable. | |
| Nov 20, 2014 at 0:18 | comment | added | John Meacham | Are you looking for a challenge-response or a solution-verification algorithm? Is it okay for the proof of work to also inherently allow extending the solution? As in, anyone you prove your work to can use it as a starting point with no extra information. | |
| Nov 19, 2014 at 20:16 | history | asked | SDL | CC BY-SA 3.0 |