Topic: Is there an alt-chain that does useful work instead of plain hashes? (Read 1458 times)

I do think the idea of pairing and grouping miners to perform the work is feasible, it may not be easy, but definitely doable once those concerns are addressed.

Here is the list of distributed computing work  http://en.wikipedia.org/wiki/List_of_distributed_computing_projects . Instead of focusing on particular example (prime numbers), maybe we can generalize the challenge. (making it more difficult too)

The way I see it, there should be some kind of API that can be used by these organizations: mixing, obfuscating, formatting and publishing their data. The difficulty of their problems should be adjustable.

I don't have huge problem with (somewhat) centralized feeders, if I choose to run such a client, I am essentially volunteering my computing resource to these organizations, I'll have some trust in them, accepting certain level of risk associated with this trust. i.e. sacrificing some Bitcoin's elegance & and ideology in exchange for practicality.

On a side note, coblee's POA https://bitcointalksearch.org/topic/proof-of-activity-proposal-102355 may be helpful in such a situation, adding randomness to the picture.... may be a hybrid of POW & POA?

 

This doesn't make sense.

To deterministically pair all miners you have to KNOW who all miners are.  If you have some unique identifier for ALL miners then it's pretty simple to pair them off in a verifiable manner.  But then that information MUST be saved - or noone can ever verify that data produced from those pairings was valid - a pre-requisite for validating past blocks.  All information needed to verify a block MUST be in the block-chain or noone can ever load a block-chain with any confidence in its correctness.

That's why details of all miners connected would need to be saved for every block.  You say this would be done via the bonds (i.e. connected miners would be defined as those who had paid a bond/deposit for that block).  That's where block-chain bloat would occur - as no sensible miner is going to pay a bond up front for more than 1 block given their ability to lose it due to a load of factors.

At various points you talk about "the system" working things out.  But what is this system if it isn't the miners?  Either you mean some centralised authority or you mean the miners - if the latter than ALL miners have to have ALL information or they can't collectively reach any decision.  Whilst in Bitcoin it's not an issue if a miner hasn't, for example, received a transaction, in this coin it WOULD be an issue if a miner didn't have information on ALL work done by ALL miners - as that would lead to them rejecting a block because it didn't contain the fee for a deposit they believed should be forfeited or a deposit return they believe should not be returned.  That makes network traffic proportional to N^^2 where N is the number of miners - as every miner has to have information about every other miner.

Similarly, if deposits are returned or converted to fees based on work done then that work done MUST be stored in the block-chain.  Otherwise how can blocks be verified?  Noone can sign those deposit refunds/fee charges other than a miner - so how does someone who connects to the network verify whether the refunds/fees in a block are valid?  What stops a miner who finds a block taking as fees  deposits that should be returned - and returning deposits that should be forfeited to their own sock-puppets?  The ONLY way to stop that is for ALL miners to have ALL information - otherwise noone would ever agree that anyone else's block was valid as it would be based on a different subset of information.

The deposits are transactions.  Given those are necessary for someone to mine, what incentive is there for miners to include deposits from other miners into their blocks?  By excluding other miners' deposits (i.e. leaving the transaction out of blocks you process) you can deny other miners the right to mine.  This gives the ultimate attack vector - where if a pool can even briefly get a good portion of the mining power they can progressively shut other miners out.  And even if 100 times their mining power connects, that 100 times their power has no way to mine - as it's impossible for them to submit a valid block without a deposit having been processed for them: and whoever managed to gain control has a serious financial incentive not to include any deposits in blocks.

If someone managed to hit that point then not only can they prevent anyone else mining, but they can also double-spend like crazy - with the only way for someone to unseat them being to create a new chain of greater length from a point some significant time in the past.

With a small number of honest miners the system would work fine - but it could never scale to a large size due to either an enormous increase in bandwidth/block chain AND/OR a loss of consensus causing massive chain splits.

Yes PoS == Proof of Stake in my post.  It is a more energy efficient alternative to Proof of Work but one with different attack vectors which some argue to be somewhat less secure than Proof of Work but Sunny would technically be the resident expert on the system to date....

You don't need a block chain, look up talks on the ledger system alternative to a block chain.  And at some point in the recent past I even suggested a hybrid ledger/block chain approach which IMHO gives you all the strengths of both systems.  The hybrid approach would create a "rolling genesis ledger" or "check point ledger" in which all previous block data could be purged and you would say have a ?1000? block, block chain from the "rolling genisis ledger" and every so many blocks you'd fold more recent history into the ledger and purge the chain that was stored into it.  The ?1000? block, block chain should be sufficient to have orphaned chains etc. all resolved and that history to be highly probable to never need changing.  Of course others have proposed a 100% pure ledger system which I don't see why that couldn't work for you as well.

I'm don't quite understand why you're saying that you don't need a block chain-- you still need one to process the transactions (if you mean that you don't need one for the algoritm calculation part then you're right-- I think).  By-the-way, I've never heard of BIONC project till now, have just had a quick read about it on wikipedia, it looks like an interesting project and could perhaps be useful (if not useful outright as is, then could be useful for tips/ideas in managing large distributed calculations)-- thanks for making me aware of it!


I don't know much about the PoS  (do you mean proof-of-stake here?) generally, but I should look into it to think.  thanks.
 

One thing that might make this easier on you in finding an answer to your problem is that 1 you don't have to have a block chain and 2 centralized sources can be utilized to feed a decentralized data processing machine.... in the latter example, you could bootstrap to the boinc network, world community grid and folding at home etc. Perhaps reward a small coin generate from any confirmed non-rejected results that are returned to those projects.  The trick then becomes how to verify the results are not a data forgery, ie. perhaps this is where the randomly assigned groups etc. come into play where the first entity registers a hash of their data on the network and when enough randomly assigned peers register the same hash then all are rewarded and transactions are processed.....  the only way I see a similar mechanic of difficulty working is by making assigned groups larger and requiring more validations to confirm......

Heck maybe sunny could weigh in on PoS... maybe the above model is just for initial generates and distributions plus being an optional alternative way to earn coin and then you could use PoS for transaction processing and ledger/block chain management etc.?  PoS should be 100% rewarding of tx fees etc. while the project processing and validation gets small generates whether your first or just a validator.

No, every node doesn't need to know every other node.  Also, every miner doesn't need to know every other miner, in fact, it is better if none of the miners are aware who the other miners are to minimize collusion.

The determinism comes from the block-chain,  this is the only required infomation which must be common to all miners. It is trivial (I believe) to group the miners deterministically but effectively randomly using hashes based on a combination of the miners' own data such as a receiving address and the current state of the block chain and the alorgithms already run for the current block.  This is not much more of a burden than what happens already in bitcoin.




There is no information that need be kept indefinitely besides the block-chain.  The algorthims that were used can be removed from the separate p2p file system immediately after the algoritms calculation is complete.  The result itself can also be deleted from the p2p file system provided that the current nodes at the time have tested that its hash matches that claimed by the miners for a reasonable number of block confirmations.  The reason why even the result can be removed is because the block chain only needs a large amount of work for the previous blocks immediately behind the current block being solved.  eg: Once a malicious miner with less than 45% network power is behind 100 blocks it is too unlikely to catch up to the present, regardless how much work went into the blocks before the last 100.  So the system can ignore the blocks' algorithm calculation for the blocks before the last 100 (ie: the p2p file system deletes the result and the nodes don't bother comparing its hash to the miners claimed value) and just keeps the lesser hash rate component. eg: Let's say that the system strives to keep the algorithm work at about 95% and the hash at 5% of the total work, so before the last hundred blocks the amount of work required to rewrite the transaction drops to 5% of the total work that was done previously for a given block when the system ignores the algorithm work, so a malicious miner with 45% can easily gain ground on these transactions but will not be able to overcome the last 100 blocks.

The only information that need be permanately stored is the normal bitcoin block-chain stuff relating to transactions, none of the general algorithm stuff need be stored.


By-the-way: incase anyone is wondering, the reason why the miner's result hashes should be initiallly sealed by the owing mining is because the slowest miner shouldn't be allowed to see the result of the fastest miner before it has finished, otherwise the slowest miner could abandon its work and copy the faster miner's result  (which would be unfair to the fastest miner and also gives a false total-number-steps count).  However, the faster miner needs a way to prove that it did finish first with a valid result-- hence it seals its hash of the result, publicly broadcasts it and then unseals it once the slow miner has finished.


NOTE : have heavily edited this to make to read better.

Wouldn't be that many transactions.  At the moment on bitcoin the number of miners is just in the thousands (I believe) and each miner usually mines for quite long period straight (hours/days/weeks/months) at a time.  If you made it that the miners mine indefinitely unless they formerly exit (or run out of bond) then that's not many transactions per day.  It would be less than Sastoshi Dice.
The number of transactions regarding the bonds can actually be dramatically reduced-- the system keeps a running total of the bonds and fees off-main-chain among the nodes over a minning session or set of blocks (which ever is smaller) and clears it at session exit or on the last block of the set.  

Please note: I thinking about a new system here- I'm not limited to what I can do by how bitcoin currently works.  I'm not in the slightest interested in maintaining compatibility with the current bitcoin system-- this is not a bitcoin fork proposal but a complete new system based on some of the more interesting parts of bitcoin technology!




You could make the fee self adjusting according to formula that accounts for number of miners, total reward, total transaction amount.



I think you're confusing calculations with transaction blocks.
I explicitly stated that the dishing out of calculations is handled deterministically by the system.  It may require that a hash of each algorithm is pre-registered/acknowledged by a group-of-miners somewhere before it gets processed or something like that-- but I imagine that it is possible to solve this.  The miners are still free to choose whichever transactions to include in a block that they want (besides the bond/fee ones).


I'm trying to understand what you wrote here-- but am not following it, sorry.  I think you're confusing calculations with transactions.  The bond stuff is a transaction not a calculation.  The miners are very restricted as to which calculations they're allowed to perform.


However, despite all these objections, I hope you realise something:  you've gone past the point of denying the system works outright and into questioning specific details.  This is GREAT,  I appreciate your feedback very much cause it is making me think about the system more--  till now it has been just a general idea that I've had for a few years and never put that much thought into it.

Surely this is going to lead to HUGE block-chain bloat as ALL of the following have to be stored indefinitely:

1.  Wallet address and a bond transaction for EVERY miner on the network EVERY time they join it.
2   Each block, every miner has to have a transaction either paying from their wallet to the block finder or refunding to them.

Also, there's an issue with the idea of a bond for doing a fixed amount of work.  Either:

a) It's trivial to do - so serves no purpose to prevent anyone submitting loads of fake miners to lock other people into partnerships that will never finish.

or

b) It's hard enough to do that miners below a certain size legitimately won't be able to meet it sometimes : leading to increasing centralisation of mining.

Oh - and you do realise miners can choose which transactions to include?  The incentive would be for miners to try generating missing out other people's transactions until they found a set pairing them with a partner they wanted.  Then not only can they collude but they lock other perfectly valid miners out - as the other miners can't mine at all without a bond in the chain.

Ultimately all a miner has to do is generate a block with JUST bonds from himself and a partner - then noone else can ever join as they can't get a bond payment processed.  Or run a pool with a high fee that only includes deposits from its own members: the fee is worth it for members as once the pool finds a few blocks they gain a shot at locking everyone else out from mining.

I'm not convinced just how useful this is for starters.  It's pretty easy to detect whether a Mersenne number is composite - and it's definitely NOT in miner's interest to be checking a Mersenne number that may actually be a prime.  So miners would focus on numbers that definitely were NOT prime - and hence deliver absolutely nothing useful (or do you know of some use for the factors of a Mersenne number?).

Also, with a difficulty level, miners would be best served not checking below a prime of the requisite size (as no use to them finding it) and moving to a new candidate if/when it became more efficient than continuing to check the current one (the extent to which this is an issue depends on the method used to check primes).

Other problem I see is the allocation of work.  This has to be done to prevent offline generation of a bunch of results then a double-spend attack.

And of course a pool of miners can collude and store results which don't quite meet the difficulty requirement - then leave network to lower difficulty and submit them on rejoining (and mine offline in interim).

The miners wishing to start mining join the action by making a special transaction on the block-chain- once it is in the block chain for say the 2nd confirmation they are now in the game-- ie: their bond is active so they must mine.  You could set it up so that they must mine for just one block, or a fixed number of blocks controlled by the size of the transaction they made or indefinitely (indefinitely would require another transaction to officially exit the mining game), this is just detail though, going beyond what I've thought about.  

I've already explained what happens when someone leaves during the calculation stage, the result of single miner is who left is considered valid as for as the total-number-steps is concerned and the miner that didn't finished is penalised by losing their bond.

NOTE: I've just edited this heavily and re-worded it-- the first edition was a mess

Firstly, note that the chances of colluding miners is reduced since the groups are formed beyond their control (you can't pick your partner- the system hands one to you randomly).  Though, as you note, the one miner can make many personalities to increase their chances of getting two of them into the same pairing.

However, for a miner to participate they pay a bond-- this bond is taken if they DON'T complete the required number of steps-- so for every personality that doesn't get matched to one of their own they have to complete the calculation to not lose the bond.  Though, this will be overcome eventually if they totalyl flood the system with their personalities-- since eventually their is a point where the chances of a match raise above 50%.

So, a potential way to stop this is to have the miners a pays a fee (in additon to the bond above).  For each pairing, this fee gets reimbursed to the miner which first completes the algorithms number-of-steps but for the other miner his fee goes towards the block reward.  In this case the miner loses out at the calculation stage (although if he wins the block reward he gets it back, but this is hard to do).  
eg:  both pairings members pay 1coin, however, only the faster calculator gets his coin back. If a miner owns both members of a pair then he pays 2coin but only gets 1 back-- so he loses out, thus is discourages from doing this.

Biggest problem I immediately see with beeble's post is it's very hard to deal with things like assigning miners to groups when people are constantly joining and leaving the network.  Then there's the issue of how someone who just joined can have a bond somehow verified so they can start mining immediately.

Any system which requires EVERY node to know every other node in the network is just not going to work.  Any deterministic way of pairing people off based on wallet addresses NEEDS either that - or a centralised authority.

The former (knowing everyone else on the network) fails because above a certain size the participants in the network will change (or appear to change) far faster than a complete list can be circulated and agreed upon.  And not only does the list have to be agreed upon and propagated, it has to be stored forever - so it can be verified that a team claiming work were actually a valid team.

For that reason alone, I don't see anything which requires teams to be feasible.  And as you already realised (which is why you added teams I assume) it's totally exploitable without them.

beeble, an obvious question is that how do you prevent miners collude to give false result if the result is not easily verifiable by everybody? Note the 'miners' are just mining nodes that someone could produce a lot of, and only collude if a 'group' happens to consist of only its own nodes. You need a detailed plan how to prevent this with bonds etc.

That's true for the way it's currently done, but my idea takes a different track.  I have done a few searches but all I find is people asking why bitcoin doesn't do useful work.  All alt-coins that I've seen use the traditional hash base method.


My idea takes a completely new approach to the original idea that "miners do work that all nodes verify".  However, please note, I haven't though about the in-and-outs of very deeply so it is most likely fundamentally flawed.
What I envision is a system that works broadly as follows:  the miners are split into groups to perform calcuations individually but their result must concur with the other miners in the group.  The nodes don't verify the work, but verify that the miners' results concur.

A (shallow) example how this could be achived:

The miners are grouped off into dynamic pairings to do a useful calculations.  These pairing are determined in a deterministic but essentially random way,  also the pairing members will change from each calculation to the next, eg: they can be determined by way of modulo hash the miners recieving address+other data derived from last calculation
The useful calculations can be *any* calculation-- the public upload the algorithms they want run to a p2p file system and request a certain number of computation steps (computation steps according to an idealized turing machine) to be done.  The network divvies up the calculations in a deterministic but essentially randon way among the mining groups, eg:the dishing out of problems can be based on hashes of algorithm+data modulo the number of groups.  The miner's commit to paying a bond which forces them to solve the calculation to required number of steps or forfeit the bond.  Once a miner completes the required number of steps it publishes a sealed-hash of the result publicly which goes to the block-chain nodes, then it is free to enter a new calculation round with a new partner.   When both members of a pair have finished the calculation (ie: when both notice that the other has finished) they publish the result (which can be quite a size) to the p2p file system and unseals the hash given to the nodes.  The nodes of the network verify that the two now un-sealed hashes of the result from both miners are the same, if they are the same then these results are considered valid and the number of steps of the calculation goes toward the miners collectlive total for the current block.  If they are different then the results are considered invalid and the miners don't get to increment the total-number-of-steps count.  (if one miner publishes a hash but their partner doesn't before the block closes then the one that publishes gets to increase their total-step-count while the other loses their bond to the block fee pool, if neither publishes then they both lose their bond).

Once the total number of steps performed collectively by all miners surpasses a set limit then the miners race to find the next block like normal in bitcoin.  Once a new block is found, the miner's overall total number of steps is reset to zero and it starts again.  The system adjusts both the block hash difficulty and the cumulative-number-of-steps/block to maintain the block rate  (though it increases the steps faster than the hash difficulty).

To improve the system you can introduce fees per step that each agorithm owner offers to pay (this fee go toward the block finding reward) to have their algorithm run and the miners state the minimum fee per step  they're prepared to accept and the system uses a pricing mechanism of determining the minimum fee per step that a candidate algorithm must have-- doing this discourages miners from asking for their own algorithm's to be solved since they may have to pay for it.

One obvious problem is that malicious miners may deliberately give false results, this could be mitigated by increasing the group size and require a majority concurrence.  Another is the publishling of the result hash to the block-chain nodes in a timely manner so that an overwhelming majoirty of nodes can get it in time to check that the hashes concur.

Hopefully other problems, such as collusion to reduce the amount of work actually performed,  could be migitaged by way of bonds, rewards, fees with game-theory so that the malicious actions cost the perpetrator(s).

Fascinating, let me throw what I can to the brainstorm:

pyra-proxy is right, verifying a factor can be easy.

Let's start with Mersenne numbers 2**p - 1 (p is prime).

A factor of a Mersenne number can be verified fairly quickly.

Now we can treat such a proof-of-factor as our proof-of-work. But how about difficulty? I think making the factor big could do it. That is, factor f (prime?) must be greater than a 'difficulty', and of course less than the squareroot of the Mersenne number.

To prevent reuse, each block must present a different (unique) Mersenne number from the previous blocks. Difficulty is adjusted dynamically similar to what's done in ppcoin/devcoin.

Now I need to find a math genius to tell me he can generate those trivially with arbitrary difficulty  

Don't ask me about the stockpile in the great internet mersenne search ... let's beat them with difficulty  

Note: I said it was related to prime number factorization... not necessarily find the next prime number etc.  Example, RSA to find the 2 prime number factors of some "semi-prime" number... finding the factors is the hard part, verifying they are the factors and are prime not as hard.... as far a sequential work is concerned RSA must have a way for theirs.,,,  in any case this was not what I saw as well but my google-fu is failing me :-(

Yes. Basically this has been hashed out (see what I did there) for years, original poster maybe didn't do the homework / research the prior art.

-MarkM-

Yeah - the work needs to be much more the nature of finding a needle in a haystack (easy to verify it's a needle once it's found) than calculating the total length of all bits of hay in said haystack (only verifiable by duplicating the work). 

Whilst verifying a number is prime is obviously MUCH easier than finding the next prime number after X it has to be remembered that blocks need to be able to be verified by ALL users of the block-chain, so needs to be able to be done by someone using just an old CPU in a trivial amount of time.  That really does cut down the useful work that is feasible - as the work has to be divisible into parts that are individually easy to either compute or verify (which also means there have to be an immense number of such tasks available).

There's also the problem of duplication - you have to ensure that if valid work is done it isn't feasible for someone to submit something based on the same work again for a future block.  That means verifying involves checking against a list of all previously computer work contained in the block-chain.  And you then still have to deal with the problem that if the same work is being done outside the block-chain then results from that can also be submitted without the submitter having actually done the work at all.

But how do you easily and cheaply prove a number is prime?

The point about needing the previous work to proceed to the next is an important one that slipped my mind when I posted earlier.

-MarkM-

While it may not be useful it would be interesting... I heard tell of a person describing a competitive proof of work algo utilizing prime number factorization or some such, if possible I suspect the results would be more useful in science/engineering disciplines than just sha hashing.... thought it was on redit or some such......