Steem: Update Proof of Work Algorithm to Prevent Shortcut

[bytemaster]

[bytemaster]

The proposed solution is to make the final step of the POW dependent upon block id.

[theoreticalbts]

Why do we need a pow2 operation? I would suggest merely move the check from validate() to evaluate(), and if that makes re-indexing take too long, either:

• Do the right thing, add a new skip flag allowing us to skip pow checks specifically, or
• Do the hacky thing, only check the PoW in the evaluator if we don't have skip_validate

[bytemaster]

@theoreticalbts we need a new operation because we need to include new data in the work, including version number and worker_account. Also, POW validation should be done outside of chain evaluator because it does not depend on chain state.

[bytemaster]

New proof of work algorithm

[theoreticalbts]

Working on the following issues in this code:

• Replace work with difficulty in operation
• Handle fractional difficulty bits
• Thread safety for has_hardfork() DB call
• Set difficulty on op to target difficulty

[theoreticalbts]

OK, on discussion we're not going to do fractional difficulty bits. Additional things which need to happen:

• Check block ID in pow2
• Use nonce to forbid duplicate work

[theoreticalbts]

The difficulty on the operation is not the number of leading zeros of the work. Instead, it is the target difficulty of the database, which (we check in validate()) is less than the number of leading zeros.

In other words, if we get too many leading zeros, we pass off the work as less difficult work, and validate() lets us do this.

The reason we want to do this is because it allows us to estimate the total hashes applied to the network over some time period by simply walking the pow_operation during that time period and for each operation, noting 1 << D hashes are required (on average) to pass difficulty D.

[theoreticalbts]

Additionally, now that work is never stored, we need a new way of tracking duplicate work to forbid it. Since two works with distinct nonces are always distinct, I simply create an object for each nonce which occurs in the current block, clearing the objects on a new block. A unique index on the nonce, therefore, forces newly submitted work to use a different nonce from all other work in the same block.

Of course the block_id check forces work submitted in distinct blocks to be distinct.

[theoreticalbts]

The algorithm as a whole should still be reviewed and tested before release.

[b0y2k]

So whats being done about this?
He is owning the entire Que in sequential order...
https://i.snag.gy/5iJefj.jpg

[mvandeberg]

The change that @theoreticalbts made by removing the work entirely and only including difficulty makes a node vulnerable to exploitation. This new algorithm uses a deterministic "private key". The validation of the work is to do the same work as the miner. The old algorithm had an actual private key, so the validation was only validation, not computation.

Because of this, a miner can submit a POW with a unique (account_name, block_id, nonce) tuple without needing to do any computation. The mining is effectively left to the node. To get around this, the POW needs to include at least part of the work. This does not prevent a miner from forcing a node to do work, but it does prevent them from getting paid for said work. That DoS still needs to be addressed, but I have a proposed solution to more efficiently store the POW.

Using a single 32 bit field, the high 8 bits are a log_2 representation of the number followed by the first 24 non-zero bits of the work.

For a target difficulty with 16 leading 0s followed by 0x888888 would create the number 0xef888888. This is a monotonic function, so inequalities from the compact form to extended form remain true.

For verifying the work, we would calculate a target difficulty number, T, and apply the transformation, f to it to calculate f(T). When a miner submits a proof of work, they transform the work, W, to f(W). To validate the work, a node first checks that f(T) >= f(W) and that their computed work, W', satisfies F(W') = F(W). The chance of a collision for this representation is one in 2^24 for the lower 24 bits to match and and exponentially decreasing probability for the upper 8 bits to match as the difficulty increases. At the "average" difficulty of 104, the actual probability of a collision is 1 in 2^54. The rate limiting of the p2p network code should make that a near impossibility to the point where an attack in this form for profit does not pay.

[theoreticalbts]

Yeah, if you add in extra bits, basically an attacker would have to guess both the nonce and extra bits, which means this particular exploit would proceeds 16 million times slower than honest PoW.

[theoreticalbts]

@mvandeberg cogently points out that nonce objects are unnecessary for pow2 from the following facts:

• We can cryptographically guarantee any re-submission of already-used work will re-submit for the same account, as the account name is hashed into the work.
• Account is added to the miner queue when it finds a work.
• Uniqueness of accounts in the miner queue is enforced.
• Miner queue drains at most once per block.

Essentially resubmission would require the attacker to wait until they get out of the miner queue, by which time many blocks have passed.

[theoreticalbts]

Fields should be re-ordered and names changed so that arguments to create() match name / order of fields in struct.

[theoreticalbts]

Additional nitpicks:

• Move worker_account, prev_block, nonce to own struct so log_work isn't hashed
• Require account to sign if exists, require new owner key to sign if it does not exist (i.e. is new account)
• Require existing account to have a witness object (which the user can create with witness_update); witness objects always exist for mined accounts

[theoreticalbts]

OK, this needs to be re-worked some more. Specifically, we're requiring the _active_ authority to sign blocks, which shouldn't be -- it should be the signing_key. In fact the entire purpose of having a block signing key different from any other key is so that the blockchain doesn't require keeping the active key "hot" on block-producing nodes (having a key that controls funds / accounts on any internet connected computer is a security risk).

• Make public_key field in pow2_operation non-optional
• Rename this field from new_owner_key to signing_key
• If account does not exist, create default account and witness object, set all keys to signing_key
• If witness object does not exist, fail -- account did not authorize mining with this key
• If witness object exists, require signing key specified in op to match signing key specified in witness object

Basically an account needs to pre-authorize any miner who's mining in the account's name by creating a witness object and giving the miner the private key for the signing key. Except anyone is authorized to mine in the name of non-existing accounts, in that case the key that discovers the PoW is used for all account operations until changed by the user.

When I wrote the above, I was confused. I put myself in a miner's shoes and thought "I should be able to mine with only the block signing key," while Steem's actual philosophy is "You're able to produce blocks with only the block signing key, but producing PoW's (which queue you and give your account block producing authority) requires the active key." I confused mining with block production -- very easy mistake because they are highly related, and essentially all blockchains other than Steem completely conflate the two ideas.