mimblewimble team mailing list archive

[Ignotus Peverell <igno.peverell@xxxxxxxxxxxxxx>]

Lots of great points. You're right about the need to make it harder to force backtracking by asking contenders to prove enough work. And thinking about it some more, a new node will eventually have to request Z headers from h to H, so it may as well do it beforehand to check the accumulated work.

So I'm thinking of amending the spec in the following, which remains fairly simple (despite the notation - the fact that horizon, height and header all start with h makes it harder :P)

- New node asks for header Dz at height h=(H-Z) using a modulo of Z/5 for example, to make alignment on the same height easier and potentially allow UTXO set caching.

- New node downloads children headers Cz (at h+1, h+2, etc.) for each received differing header Dz, calculating accumulated work.

- New node drops the download of children Cz that don't prove enough work compared to another Cz (assuming we received multiple Dz).

- When we're back at H, a few cases arise:


- We have a singly rooted Cz set, we're done syncing.

- We still have multiple differing heads, then we backtrack with Z'=Z'+Z.

- We've backtracked twice already, fail and notify user.


This achieves the objectives of making it hard for a potential attacker to mess with our syncing (they would have to forge 3*Z proof of work at a difficulty similar to the main chain) when the only thing to gain is a failed syncing that could be resolved manually.

Does that seem better and alleviate some concerns?

- Igno



-------- Original Message --------
Subject: Re: [Mimblewimble] Chain syncing spec
Local Time: January 5, 2017 1:25 PM
UTC Time: January 5, 2017 9:25 PM
From: MoaningMyrtle@xxxxxxxxxxxxxx
To: Ignotus Peverell <igno.peverell@xxxxxxxxxxxxxx>
mimblewimble@xxxxxxxxxxxxxxxxxxx <mimblewimble@xxxxxxxxxxxxxxxxxxx>

I agree that the horizon choice shouldn't be so important so long as it is sufficiently large. However as written I think the spec degenerates too quickly to full history sync in the presence of adversaries of relatively low sophistication. Given that a mismatch at H in the spec leads to undefined behavior, and a mismatch at h causes rewind of history that is easy for an attacker to maintain (requiring just a single valid PoW at h at minimum difficulty), as written the only safe thing a bootstrapping node can do is fall back to full history sync with full PoW validation, relying on an ever-shrinking pool of full history nodes (as Gellert notes). It seems that in this scheme, checkpoints built into the system would become necessary to allow most nodes to prune.

One small tweak to the spec that addresses this issue could be to require the full replay of Z blocks even if there's a consensus mismatch in either H or h = H-Z. This makes forging h with a valid H effectively impossible; it would require the ability to generate headers chains that end on a preset hash. Additionally, even if the state at H is forged, the attacker would at a minimum have to forge Z blocks of valid PoW at minimum difficulty to be viewed as a valid chain. After receiving the Z blocks, they would be PoW validated; if they fail to validate, that peer would be blacklisted and removed from the connection pool. If they do validate, the horizon is pushed back and the exercise is repeated again. There would be no indication to the adversary that their forging was successful, requiring them to maintain a massive set of fully validating n*Z blocks, as header connectivity would be enforced. The primary tradeoff here is the bootstrapping node takes on a much greater amount of work, maintaining potentially several parallel forks to compare, but considering the alternative is full PoW validation from genesis I think this is fair.

One concern with this scheme is since the head H and the horizon chainstate h can be entirely fabricated, it may be possible to reuse sets of valid n*Z blocks, removing a lot of the work this scheme relies on. However, if Z is sufficiently large and minimum difficulty is sufficiently high, combined with some reasonable heuristics (be suspicious of many recurring sets of blocks constantly at minimum difficulty, plus strictly enforced timestamps) this may be a workable scheme.

One other, unrelated point: I think redefining the horizon block to be h = floor(H-Z, ERA) with ERA possibly = Z would be a worthwhile tweak; combined with the above (asking for h even if there's a mismatch in H), this makes the algorithm a bit more resilient to bootstrapping nodes being in slightly different states (being one block ahead or behind or on a slightly different short fork). Given you're targeting a short block time, this situation seems like it would be somewhat common.


-MW


-------- Original Message --------
Subject: Re: [Mimblewimble] Chain syncing spec
Local Time: January 5, 2017 10:31 AM
UTC Time: January 5, 2017 6:31 PM
From: igno.peverell@xxxxxxxxxxxxxx
To: mimblewimble@xxxxxxxxxxxxxxxxxxx <mimblewimble@xxxxxxxxxxxxxxxxxxx>

Dear Gellert,

I agree on all points. I'll just add that the choice on the horizon length may not be as crucial as you think given that the node will back-track anyway and that this process should be fairly fast (only requiring a block header from each peer).

- Igno


-------- Original Message --------
Subject: Re: [Mimblewimble] Chain syncing spec
Local Time: January 5, 2017 6:22 AM
UTC Time: January 5, 2017 2:22 PM
From: grindelwald@xxxxxxxxxxx
To: mimblewimble@xxxxxxxxxxxxxxxxxxx

> Greetings Gellert Grindelwald,
>
> Thank you for the reading and the review. The attack you described is
> definitely something that comes to mind as a potential danger but it would
> require to both have a partial rewrite of the chain *and* a full sybil
> attack (where the attacker controls all the peers the new node is
> connected to). Pretty much all cryptocurrencies are vulnerable to a full
> sybil attack, including bitcoin, so it's not something I consider
> acceptable udner our security model.
>
> To elaborate, when a new node joins the network it does the following:
>
> - Connect to a certain number of peers (typically 6 to 10).
>
> - Ask for the latest head H.
>
> - Ask *all* peers for the horizon block header at h=H-O.
>
> - Check for consensus among *all* peers it's connected to on h.
>
>
>
> At this latest step, under the attack you describe, the new node would
> detect the attacker's fork. Not knowing which header to believe, it
> backtracks, increasing O until reaching agreement between all its peers.
>
> - Igno
>

Yeah basically worst case scenario in the full sybil attack scenario is
the bootstrapping node has a forged history of the chain which is pretty
disastrous but unlikely to occur in a mature decentralized network.

Best case scenario where only a couple peers are malicious this is a DoS
attack that forces the node to constantly keep back-tracking for consensus
among peers on a block. Once consensus is found on a block then banning
the peer who is DoSing would be warranted. I think if we gave the block
horizon a one month(or larger) period this would largely thwart any major
threat of adversaries being able to take advantage of the full sybil
scenario while still addressing the DoS attack which will always be
possible to a certain extent. This is under the assumption the network has
a strong hashrate and a one month block horizon is completely unreasonable
to rewrite from a work perspective.

Having pruned nodes only connect to full nodes for syncing past blocks
would make this attack disappear, forcing the attacker to completely
rewrite the blockchain history rather than just H - Z blocks, but as full
nodes go out of favour for pruned nodes this solution is not really
sustainable long term and bolsters the strength of the aforementioned full
sybil attack when full nodes with the entire chain history is scarce.
Choosing the length of the block horizon will be crucial to the security
of the network.

-Gellert



--
Mailing list: https://launchpad.net/~mimblewimble
Post to : mimblewimble@xxxxxxxxxxxxxxxxxxx
Unsubscribe : https://launchpad.net/~mimblewimble
More help : https://help.launchpad.net/ListHelp