Quote from: HunterMinerCrafter on September 21, 2016, 06:12:50 PM

Right now, testnet tokens are just "free" anyway, you can basically mine proof shares without actually doing the job's work... so if I need some coins I'll just "take" them from the network! Wink

(But that is another bug, for another day...)

So I guess that today is as good a day as any....

Let's look at an (only slightly more) interesting and fun bug, which we'll call "HMC bug #6" but which is more generally known as "basic work stealing." (Note that XEL is not the first design to encounter this problem!)

Consider a cast of characters:

Altruistic Alice, the "wealthy peer" - She is a big XEL donor, holds lots of XEL, and uses it to stake-forge blocks on the network. Being altruistic she selects transactions indiscriminately, simply prioritizing those she receives first.

Basic Bob, the "normal miner" - He doesn't have much XEL, but he has a big farm of small CPUs and GPUs left over from other coin mining, so he mines PoW/PoB hoping to one day strike it XEL-rich by getting lucky on some big work order. He's a bit of a loner because his small apartment is always noisy and hot, and his few friends give him funny looks when he runs out in the middle of dinner because "the damn rig is on a fork again" whatever that means...

Crafty Cathy, the "hax0r" - She's an attacker on the network, looking to heist some coins to sell in order to add to her BTC hoardings. Maybe we should call her Cracker Cybil, because she keeps excessively well-connected nodes using a heavily modified client on her ill-gotten botnet nodes around the world.

Developer Dave, the "code monkey" - He's a bioinformatics software engineer at a scientific research institution, tasked with solving for a new crispr sequence to adjust dermal elasticity in primates, with the hopes of addressing the epidemic plight of crows feet on aging people's faces. (Or something like that. He's got work to request, that's the only important aspect, here, about Dave.)

Now consider the scenario:

1. Dave codes up some big, complex job to do some gene sequencing search, which he knows can have only a single possible bounty solution.
2. After some local testing, he's so confident with the job construction that he submits it to the network backed by his entire 2 million XEL budget offered up. (It's a well-funded research institute.)
3. Alice sees his work order TX and forges it into a block.
4. Bob sees the job, says to himself "this is the one!" and points all of his cpu resource at it, raising the temperature in his hot apartment another 5 degrees.
5. Let's say that Bob gets really lucky, and finds 2 PoW certificates and then stumbles upon the 1 PoB certificate.
6. Excitedly, Bob pushes these 3 transactions out to his peers. (Over half of which are actually just Cathy.)
7. Cathy's modified, well connected nodes don't relay the TXs. Instead, they quickly create new transactions with the same input values, but signed by her, and relay these instead.
8. Alice sees Cathy's TXs before Bob's TXs, since Cathy is both well connected and happens to have botnet C&C nodes in a datacenter on an OC-12 uplink geographically near Alice. Alice starts forging them into the next block.
9. Alice then sees Bob's TXs, but rejects them as duplicate, forging Cathy's into a block instead.
10. Bob sees the block with *his* solution values, but signed by Cathy and, being none the wiser, assumes he's been improbably out-lucked. He gives up on life and jumps out of the nearby window.
11. Dave goes about his life, being none the wiser, happy to have received his solution so quickly.
12. Alice goes about her life, being none the wiser, happy to have contributed to the network.
13. Cathy immediately cashes out the free 2 million XEL on the open XEL/BTC markets, crashing the spot price - but hey what does she care? She goes about her life, happy to have increased her BTC position.

Woops.

The original Satoshi PoW designs (as well as sound derivatives, like MotoCoin ) are not subject to this sort of problem, because the block contents being hashed over in the work function are always unique to each miner as they contain a signature in the coin-base transaction. Changing this signature invalidates the solution. This might suggest a "simple" solution of including some PoW-submitter-specific identifier directly in the hashing, but the same sort of solution can't be used to prevent PoB stealing.

In order to prevent both certificates from being subject to stealing the "allowed" input values for a miner would need to be made somehow specific to that miner, perhaps derived as a deterministic stream from their public identifier. However, since miners need to be able to iterate a *lot* of (effectively unbounded) input values, this is only a partial mitigation - jobs with a low number of inputs (96 bits is not all that much entropy these days) could still be subject to a variant of the attack where after seeing Bob's solution, Alice just "grinds" her input value stream generator on her botnet in hopes to quickly find a stream position which produces the same inputs. (On average this would still be lower cost to her than actually doing the work, ofc.) To prevent this, the amount of input values would need to be forced to always be sufficiently large such that there is no reasonable probability of grinding the inputs to find a corresponding "position" in their own stream which creates the same inputs.

In other words, XEL should probably always fill *all* input memory with random values, taken from a deterministic generated sequence derived from something miner-specific, and work/bounty solution certificates should include the position in the stream which gives the corresponding inputs, for validation.

Questions?