Bitcoin Forum

I was reading up on P2Pool and an alternative pool chain is a cool idea.

However, one of the issues is higher variance.

Variance could be improved by having nodes claim hashes and then prove it later.

The alt chain would have 4 types of link.  Links would include the hash of the previous link.  The only proof of work is the linking into the main chain.  However, links can be proven to be part of the chain.

Introduction Link

This contains would have a payment address for the node

- a payment address
- a public key for the node
- a nonce

An introduction link is valid if the hash of the info has 24 leading zero bits (could be tweaked if there is spam).  That would require about 16 million hashes to create.

Adding a difficulty adjustment here could prevent spamming of the chain, though identity is just for spam protection.

An introduction link cannot be re-submitted until it is past 50% of the chain "memory" and it is not "locked". 

This allows nodes to prevent their identity from falling off the end of the chain.

Win Link

This is a link for a node to announce that it has found a hash that "wins" on the main bitcoin chain.

A win link is valid if it corresponds to a valid block in the bitcoin chain and has payouts in accordance with the pool rules.

Win links can be submitted by any node to prevent winners trying to prevent their accounts from being debited.

The win link would have to be encoded into the official coinbase transaction format, for this to be possible.

Claim Link

This contains a claim by a node that it has performed a number of hashes.  This "locks" the introduction link.

All hashes claimed by the claim link must be of the same difficulty.

A claim link is valid if it matches an unlocked introduction link.

Proof Link

A proof link can only be submitted after 2 win links have been added to the chain since the claim link (and until the claim link falls off the chain).

This unlocks the introduction link, if the proof is valid.

The proof link proves that hashes have been performed.

Each message in the set of messages hashed contains a unique number from 0 to N-1 as a nonce.

The proof must contain hashes of the following sequence

h = Hash(win node 2 after the claim node's hash)
for i = 1 to p {
  toProve[ i ] = h % N // so pick a random hash
  h = hash(h)
}

This means that p hashes are chosen in a way that the node could not predict in advance.

Assume the node performed x hashes but claimed y hashes (y > x) and his proof was p hashes long.

Then the chances of all hashes he has to show being valid is (x/y)^p.  The hashes selected are always the same no matter when the claim link is submitted, so he gets one shot at the proof.  If it fails, he doesn't get credit and the introduction link cannot be unlocked.

The expected payout is

p(cheat success) = (x/y)^p
p(caught) = 1 - (x/y)^p

Gain(cheating): y * (x/y)^p
Gain(fair): x   (this is the same as cheating if (x = y))

In order to make cheating a bad strategy, then p must be set so that

y * (x/y)^p < x  for all y

If p is 2, then

y * x^2 / y^2 < x

x * (x/y) < y

Since y must be greater than x to cheat, if p = 2 (or higher), then cheating has a lower expected value than playing fair.

Setting p to 4 or more would make it an even worse idea to cheat.

Network Rules

After a Win link is added, a new coinbase transaction target is determined directly by the rules.  All nodes must hash against that transaction to gain credit.  The first output of the transaction is the "winner" output and can be set to whatever the node likes and it is still considered valid.

Claim links can contain hashes for multiple win links, so they don't need to submit a claim after each win link. 

The reward is 95% of the average total coinbase payout of the next 8 win links times the claim link's hash total divided by the expected number of hashes required to solve that difficulty.  On difficulty changes, it is the last 8 win links for that difficulty (or all the win nodes for that difficulty, if fewer than 8).

When a node's proof node is accepted his "account" in incremented by his reward, after 8 more win nodes (or difficulty change if that happens first).

Payout transaction outputs shall be included using the following rule
Priority: Any account unpaid for more than 25% of the chain's memory should be paid (up to 97% of the total)
Standard: Any other accounts (up to 90% of the total)

The 2 groups shall be sorted so that larger accounts are first, with ties broken so earlier proofs are handled first.

If the transaction hits one of the payout limits, the last transaction should be partially paid, so the exact limit is paid.

This creates a unique coinbase transaction after each win node.

Also, by paying larger accounts first, it should keep transaction spam on the main bitcoin chain lower.  However, in the end the 97% rule should ensure payment, including due to variation in the winnings of the pool.

The chain selection rules are:
  - A chain with greater total proof of work for its win links is stronger
  - If tied, a chain with a win link corresponding to a later main bitcoin block is stronger
  - If tied, a chain with more links is stronger

Nodes should build on the strongest chain.

Variance

A node could set its difficulty so that it can solve blocks every second.  This would mean very low variance.  When claims are submitted, the payout is computed exactly.

There is still pool variance, but it pretty much eliminates miner variance.