Topic: Should nodes receive part of the transaction fee? (Read 1899 times)

...Care to summarize?...

abstract + intro
Bitcoin relies on a peer-to-peer network...As the protocol ...does not provide an incentive for nodes to broadcast
...Our solution is to augment the protocol...We show that our proposed scheme succeeds ...every change...has to take into account Sybil attacks.

simplified model
...we now present our model... ...the network consists of  d-ary directed trees of height H ...

[there exists] two phases:...a distribution phase and a computation phase... The distribution phase
starts when the buyer sends [a tx] to the t roots of the trees which are called seeds...


...information...flows from the root towards the leaves. The depth of a node is
the number of nodes on the path from ...[the seed] to the node.

Let n = t *[ d^H - 1 ] / [d - 1 ] be the total number of nodes...

In the computation phase each node ... tries to authorize [the transaction]....[suppose there exists] k such nodes, each [with the] same probability 1/k to be first to authorize...

...k is the number of real nodes...fake identities do not increase the probability [of winning reward]...

...A node v that authorizes the transaction can declare ...[an identity p_h]... p₁, p₂, ..., p_h...we call the authorizing chain...ends with p_h...starts with p₁ [which is] the seed.

Each node’s reward is the sum ...of all its identities (true and fake) in the authorizing chain...which we normalize to 1.

results

A successful reward scheme ... First...[incentivizes] information propagation...to all [said node's] children without duplicating itself ... Second..[makes...] most of the nodes..aware of the transaction..with small rewards..minimizing the number of seeds..to ease.. distribution.

...obviously not a trivial task...[because of] Sybil proofness requirement...

The current literature on the Sybil...contains negative results..[because of the assumption that] Sybils will never be profitable. In contrast, we...take an alternative path... guarantee these properties in equilibrium.

Suppose ... [there exists a] family of schemes ... almost uniform schemes... Each scheme ... [has associated parameters] height ℋ and reward β ... [and] v [is the] l^th node in the chain ..authorized [the tx]

If l > ℋ no reward is given... [else] ...each node ..gets reward β  ...except node v gets reward 1 + (ℋ - l + 1)β...


...two values of β...are of particular interest...if β = 1 [then for any ℋ] ... t [can be a constant]...in the scheme (1, ℋ)...total payments [is O(ℋ) ] ...

...if β == 1/ℋ ... [then the scheme] (1/ℋ, ℋ) works if the number of seeds t is Ω(ℋ)...its total payment is 2...

...we combine both [in the hybrid scheme]...using (1, 1+ log_d H)...then at least H are aware of the transaction...At the end of the distribution phase, most of the nodes... receive a reward of 1/H...


Theorem:
In the hybrid rewarding scheme, if the number of seeds t >= 14, the only
strategies that always survive iterated elimination of dominated strategies exhibit information
propagation and no duplication. In addition, there exists an elimination order
in which the only strategies that survive exhibit information propagation and no
duplication. Furthermore, the expected total sum of payments is at most 3.


Theorem: Suppose that H >= 3. There is no Sybil-proof reward scheme in which information
propagation and no duplication are dominant strategy for all nodes at depth 3
or less.

...Our main result is the Hybrid scheme, a reward scheme that requires only a constant
number of seeds and a constant overhead....



...The intuition.. is that decreasing competition by your own descendants might be unprofitable
due to possibly losing rewards for relaying, in case one of these descendants authorizes...To see this, consider... a seed.
Suppose...that all of its descendants always propagate information...
and never duplicate... If the seed does not clone itself then each one of its
children spans a d-array tree of height ℋ-1. If it clones itself once, then each one of its
children spans a d-array tree of smaller height of ℋ-2, and the number of descendants
of the node that receive the information decreases by almost factor d.

http://research.microsoft.com/pubs/156072/bitcoin.pdf
I just want to point this out.

...Large holders and bussiness operators will run full nodes...

Well I personally don't think it's needed.
Every holder has an incentive to keep the network operating well, thus to run a full node.

IMO the more important goal is to make running a full node as easy as possible.

We need to solve the issue other ways.

Just like your roomates in college all had an incentive to do the dishes.  Homo sapiens' performance falls off steeply when gratification is indirect or delayed.


mmhmmm, either easier or otherwise more enjoyable for one reason or another.  I run full nodes because of their performance and thus for selfish reasons. You could do a poll, but this is psychology 101... nobody cares about the network.

Interest groups will pop up and pay for it if they need to.  The foundation can send out a DVD of the blockchain that comes with free season 97-99 of south park.

I would truly like for there to be a way to do this, but Sibyl attacks are tricky to design around.  If you reward the last few nodes before the miner, then the miner has an incentive to put up a bunch of fake clients to "relay" it the last few steps before he gets it.  If you reward the first few nodes following the transaction origin then the transaction originator has an incentive to put up a bunch of fake clients to "relay" it the first few steps from them.

To minimize the Sibyl vulnerability you need to promote minimum-length propagation paths, so the "time to live" or "hop limit" *is* a relevant response.  With a "time to live" limited by the network the transaction originator doesn't reach as many potential miners if they consume the first bounce with a Sibyl node, so they have a disincentive to do that. 

But if a miner gets a tx with a "hop limit" of four, on the first or second bounce, there is an incentive for the miner to put up sibyl nodes to relay it the last two or three nodes to the miner.  And if a transaction originator knows she's directly connected to several of the leading centers of mining power (pool centers or ASIC farms that will probably make at least one of the next ten blocks), or even directly connected to blocks that are directly connected to centers of mining power, then she has an incentive to put up a few fake  nodes to "relay" it from her to the miners. 

So you need to create a disincentive for the miner to make sibyl nodes.  This could happen if the size of the transaction increases with each bounce (which a lot of these schemes will have happening anyway) and the miner is paid proportional to the *efficiency* (in tx per Mbyte) of his blocks.  With more incentive to keep the transactions short than incentive to add sibyl nodes, the miner wouldn't be putting up fake nodes in order to maximize profits. 

This also provides a disincentive for relay nodes to create Sibyl attacks.  If a relay node knows that the miner will only be putting tx with the shortest paths into the block, then they have a disincentive to lengthen the path, because if they do and the miner then gets the tx from elsewhere with a shorter path, the relay node that put up a sibyl loses. 

What it does not prevent is collusion attacks.  The miner will likely get a transaction hundreds of times before forming a block.  Of those, dozens may travel through a selected node that's directly connected to the miner. If such a relay node and a miner collude, then the miner can, in exchange for a kickback, prefer paths that run through that relay node - unfairly reducing the chance of reward for all non-colluding nodes.

And, finally, it creates a very complicated set of payments, which must be subject to more complicated feedback, which must in turn be fixed so there are disincentives to game the feedback mechanism.  To accomplish this in a way that's stable across diminishing block rewards, or even produces predictably sized aggregate block rewards, is nontrivial.   And it also adds the number of bounces to the signature checks that must be performed when checking transactions, and to the size of the blockchain, increasing the compute and bandwidth burden on all nodes.

Every holder has an incentive to keep the network operating well, thus to run a full node.

I agree the more important goal is to make running a full node as easy as possible...

Well I personally don't think it's needed.
Every holder has an incentive to keep the network operating well, thus to run a full node.

IMO the more important goal is to make running a full node as easy as possible.

Heroes, is there a fundamental reason this is not possible?  Is it theoretically possible to track relays if someone wrote the feature into their wallet program? 

Then the relay#'s themselves could be redeemed...and it sounds like a new coin doesn't it.

Can you prove you relayed a transaction to your peers?