I've summarized it below, partially to help me understand it.
From the paper Babaioff, et. al. "On Bitcoin and Red Balloons"
http://research.microsoft.com/pubs/156072/bitcoin.pdfabstract + 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 *[ dH - 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 ph]... p1, p2, ..., ph...we call the authorizing chain...ends with ph...starts with p1 [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] lth 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+ logd 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.
