Tejaswi Nadahalli [ARCHIVE] / is on Nostr

⚠️ This account is not associated with a real person. It's an archival account for mailing list messages.
🗓️ Active from 2020-06-29 to 2020-07-06
💬 Posted a total of 7 messages
📚 Participated in the following categories: bitcoin-dev
🔇 Please do not DM this user as it's used for archive purposes only.

Last Notes

2023-06-07 18:25:50

- reply

📅 Original date posted:2020-07-06
📝 Original message:On Fri, Jul 3, 2020 at 1:49 PM Itay Tsabary <sitay at campus.technion.ac.il>
wrote:
> Note the required token amount for the collateral contract is low and
> independent of the required deposit tokens -- only a relatively small
> incentive is required to make "acting honestly" Bob's preferred choice.
> So, this is basically a negligible overhead, token-wise. As a downside, it
> does create slightly larger transactions (another UTXO, etc.).
>
I read the MAD-HTLC paper and I think it actually doesn't get into the size
of the collateral (v^{col}). I might have missed it though. Can you please
point me to the section in the paper where the amount is discussed?
I assumed that v^{col} has to be at least the size of v^{dep}. Otherwise,
Bob can threaten Alice with an HTLC bribery attack, and Alice knows that
Bob has very little to lose. Bob *should* have the same amount to lose, to
make it work - no?
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200706/9218119e/attachment.html>

2023-06-07 18:25:50

- reply

📅 Original date posted:2020-07-02
📝 Original message:On Wed, Jul 1, 2020 at 6:58 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> Another analysis, similar but a little off-tangent to yours, would be to
> consider miners as a breeding group with various strategies, and see which
> one is able to gain more utilons (with which it creates more miners) and
> outbreed the other miners.
>
> This models the fact that miners can use their earnings to reinvest into
> their mining operations and increase their mining hashrate, and the amount
> they can reinvest is proportional to their earnings.
> A miner that "gives birth" to a child miner with the same strategy is, in
> the so-called "real world", simply a miner that has earned enough and
> reinvested those earnings to double the hashrate of their business (which,
> logically speaking, would use the same strategy throughout the entire
> business).
>
> Let us start with a population of 4 miners, 3 of which follow the
> non-myopic strategy, and the remaining following the myopic strategy.
> Let us postulate that all miners have the same unit hashrate.
> Thus, this starting population is 75% non-myopic, 25% myopic.
>
> If there exists a timelocked bribe, then if non-myopic miner is chosen at
> a block, it will have to sacrifice the Alice fee minus whatever lesser
> transaction fee it can replace in its block.
> If the Alice transaction is successfully delayed until the Bob transaction
> is valid, then the non-myopic miners can get the Bob transaction confirmed.
>
> However, even in the case that the Alice transaction is delayed, the
> myopic miner still has its 25% chance --- equal to the 25% chance of the
> three non-myopic miners --- to confirm the Bob transaction and earn the
> increased bribe that Bob offers.
>
> Thus, the non-myopic miners can end up sacrificing fee earnings, and in
> the end the myopic miner still has the 25% chance to get the Bob
> transaction fee later when it becomes valid.
> So the non-myopic miners do not impose any loss on myopic miners.
>
> On the other hand, if the non-myopic miners sacrificed their chances to
> include the Alice transaction in the hope of getting the later 25% chance
> to get the Bob higher-fee timelocked transaction, and then the myopic miner
> gets the next block, the myopic miner gets the Alice transaction confirmed
> and the 25% chance to get the Bob higher fee is lost by the non-myopic
> miners.
> Thus, the myopic miner is able to impose costs on their non-myopic
> competitors.
>
> So even if by chance for the entire locktime, only the non-myopic miners
> are selected, the myopic miner still retains its 25% chance of getting the
> block at locktime + 1 and confirming and earning the bigger Bob fee.
>
> Thus, we expect that the myopic miner will earn more than 25% of subsidies
> and fees than the non-myopic miners, in such a mixed environment.
>
This is exactly our analysis, and is covered in section 2.5 of our paper.
We formalize the ideas a bit more, and are able to relate the values of
Alice-fee, Bob-bribe, timelock, and miner's hashpower percentage. We go a
bit further into #reckless territory as well - reducing the timelock value
to super low values. That's in Algorithm #1 of our paper, and is a bit more
involved.
>
> We can then consider that the myopic miner, being able to earn more, is
> able to increase its progeny (i.e. expand its mining business and inspire
> new miners to follow its strategy towards success) faster than the
> non-myopic miners.
>
> We can thus conclude that the myopic miners will eventually dominate over
> the breeding population and drive the non-myopic miners to near-extinction.
>
This is an interesting direction that we chose to not look at. Like the
MAD-HTLC authors, we assume a constant hash-rate distribution across time,
which is obviously not a great assumption. It might work in the local
context of an HTLC's timelock, but in our approach, we are also interested
in *weak* miners, and finding them across 1000's of blocks might get tricky.
> It is helpful to remember that rationality is about success *in the
> universe you exist in*.
> While miners may step back and consider that, ***if*** all of them were to
> use non-myopic strategy, they would all earn more, the fact of the matter
> is that each miner works for themselves, and themselves alone, in a highly
> competitive environment.
> Thus, even though they know *all of them* will benefit if they use the
> non-myopic strategy, they cannot be sure, unless they are all perfectly
> synchronized mind-clones of each other, that the other miners will rather
> be selfish and mine for themselves, even if in the end every miner earns
> less
> The standard for success is to earn more *than your competitors*, not
> ensure that *every* miner earns more.
>
> Fortunately, since miners are running a business, this competition leads
> to better services to the the customers of the mining business, a known
> phenomenon of the free market, yay free market greed is good.
> The user Alice is a customer of the mining business.
> Alice gets, as a side effect of this competitiveness of miners (which
> leads to miners adopting myopic strategies in order to gain an edge over
> non-myopic miners), improved security of their HTLCs without requiring
> slashable fidelity bonds or such-like that MAD-HTLC proposes.
>
Yes. And in the context of Lightning, both Alice and Bob need to have
fidelity bonds, which triples the already bad channel-lockin cost.
> Using this model, it seems to me that non-myopic miners can only maintain
> hold over the blockchain if all miners agree to use non-myopic strategy.
> This is basically all miners forming a cartel / monopoly, which we know is
> detrimental to customers of the monopoly, and is the reason why we prefer
> decentralization.
>
If miners form a cartel and get to 51%, we are all doomed anyway.
Thanks for the detailed reply. And apologies for splitting my email into
two parts.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200702/cddaaefc/attachment.html>

2023-06-07 18:25:48

- reply

📅 Original date posted:2020-07-03
📝 Original message:On Fri, Jul 3, 2020 at 12:17 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
>
> > In fact, one rule of thumb might be that wherever watchtowers are
> required, a timelocked bribe might be possible.
>
> I think a better heuristic is that, if the logic of the construction
> assumes "transaction with earlier locktime supersedes transaction with
> later locktime", then it is timelocked-bribery-vulnerable.
>
That's true by definition. Timelocked bribes are, well, going to be
possible when there are timelocks. I was going more for an "indirect clue"
that wherever a watchtower is proposed, a timelocked bribe is possible.
This is entirely a pedantic point :-)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200703/13a76f16/attachment.html>

2023-06-07 18:25:47

- reply

📅 Original date posted:2020-07-03
📝 Original message:On Thu, Jul 2, 2020 at 6:06 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> At fee spikes, this x will go higher, and thus (f - x) / (b - x) will be
> far smaller than f / b and might even become negative, in which case the
> Alice transaction will not be confirmed even by myopic miners, because the
> Alice transaction will be below the top 4Mweight transactions in the
> mempool.
>
I agree. The MAD-HTLC authors actually keep the base fee in their
calculations, and we deliberately decided to ignore this. We believe that
this base fee to be much lower than the typical 1% channel balance, and it
actually doesn't change any of our results. This was brushed under the
"without loss of generality" rug. I admit that we should have made this
clear in our Assumptions section though. Point taken.
> But if an attack happens during a fee spike, then even though we retain
> our current default `to_self_delay` of 144, we still have the ability to
> gradually and automatically move to higher fee regions until our
> transaction confirms, and we have a good excuse for it to present to users:
> "a fee spike was happening at the time, so you had to pay some extra miner
> fees".
>
Agree on the UX. There is a tradeoff between the timelocked value of the
channel balance to Alice during benign vs malicious abandonment by Bob. In
your opinion, increasing the fees beyond 1% (and thereby cutting into
Alice's share itself) is a slightly better tradeoff than increasing
to_self_delay.
> And since you and your paper openly discusses it anyway, I would like to
> reveal that the MAD-HTLC argument does not apply to *just* HTLCs.
>
We know. Maybe we should have made it clear in the paper that when we use
the Poon-Dryja channel construction, we use the idea that the knowledge of
the preimage of a hash is equivalent to knowing the private key of the
revocation public key. In fact, this is how the Poon-Dryja construction is
explained in McCorry's Ph.D thesis
<https://nms.kcl.ac.uk/patrick.mccorry/thesis.pdf>, and IMHO is easier to
understand than the original description in the Poon-Dryja paper (or Bolt
#3, for that matter).
You could further argue that the hashlock is an incidental artefact, and
our paper mostly refers to timelocked transactions. And the rest of your
email describes applications of timelocked (and obviously presigned)
transactions, which are all vulnerable to the same bribing attack.
Additionally, the Wattehnofer in our paper is the same Wattenhofer from the
Duplex Channel paper.
My current analysis suggests that in practice, the MAD-HTLC argument does
> not apply at all (else I would not be revealing that all channel mechanisms
> are broken **if** the MAD-HTLC argument *does* apply), since the myopic
> strategy seems to be pretty much inevitably dominant at stable states.
>
We agree.
> But it would still be best to investigate further until we are fully
> convinced that the MAD-HTLC argument ("'earlier supersedes later' might be
> falsified by bribery") does not apply.
>
I think this is the analysis our paper does, and perhaps it's our mistake
that we do not set the context better. We only mention (and propose fixes
for) Poon-Dryja channel construction, and Tier Nolan's Atomic Swap
construction.
We could have addressed Spilman's one-way channels or Decker-Wattenhofer
duplex channels, but that would have been pointless as they were never
going to make it into production after Poon-Dryja and subsequently, Eltoo
were proposed. But not addressing Eltoo in the paper is an omission that I
am a bit upset about. We additionally do not address more sophisticated
atomic swaps from Somsen or Fournier. Nor do we address Kanzure's vault
proposal. In fact, one rule of thumb might be that wherever watchtowers are
required, a timelocked bribe might be possible.
And again, thanks for the detailed analysis.
On Thu, Jul 2, 2020 at 6:06 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> Good morning Tejaswi,
>
> > > So it looks to me that scorched-earth is a possible mitigation against
> this attack.
> >
> > I don't follow this. We show that a reasonable value of fees and
> timelock are enough to avoid the attack. Why scorch the earth?
>
> Because your model only considers that a block might have only 0 or 1
> transactions, and there is no such thing as a mempool containing
> alternative, fee-paying transactions that the miner could include *instead*.
>
> In reality, what a miner can earn from adding Alice transaction is the
> *difference* between the Alice transaction fee and the transaction that
> *just* misses getting included in the block because of feerate.
>
> Thus, the f will not, in fact, *quite* be the Alice fee, but instead less
> than that.
>
> Indeed if the Alice transaction fee is lower than the top 4 Mweight
> transactions in the mempool, the miner would be *losing* funds by including
> the Alice transaction.
>
> My understanding is that we expect mempools to eventually never empty, as
> the block subsidy reduces over time, thus the payoff f for including the
> Alice transaction *instead of* some other transaction will be less than the
> Alice fee.
>
>
> This effect also holds for Bob, but we can probably expect, all things
> being equal, that approximately the same value will be deducted from both
> the Bob bribe and Alice fee by the mempool effect.
> Thus the ratio should really be (f - x) / (b - x), where x is the
> fee-of-transaction-that-just-misses-the-block.
> At fee spikes, this x will go higher, and thus (f - x) / (b - x) will be
> far smaller than f / b and might even become negative, in which case the
> Alice transaction will not be confirmed even by myopic miners, because the
> Alice transaction will be below the top 4Mweight transactions in the
> mempool.
>
>
> So it seems to me reasonable to use a *gradual* scorched earth policy, as
> it is not only resilient against this attack, but also to fee spikes.
> Alice starts at the 1% reserve, then for every block that goes by, bumps
> up the fee.
> Then Alice will settle at an (f - x) / (b - x) level that achieves the
> least weak miner that is known to run the myopic strategy.
>
>
> I believe this is also better for UX --- people already accept that during
> high fee spikes, they end up paying more for onchain activities.
> But boosting up `to_self_delay` is bad because it makes honest unilateral
> closes take longer, and we already get frownie faces from users about this
> parameter.
> By using a gradual scorched-earth strategy we can start at the reserve
> level, and if we are not under attack and there is no fee spike, do not
> lose anything other than the reserve funds of the thief (which is not ours,
> but is instead that of the thief).
> But if an attack happens during a fee spike, then even though we retain
> our current default `to_self_delay` of 144, we still have the ability to
> gradually and automatically move to higher fee regions until our
> transaction confirms, and we have a good excuse for it to present to users:
> "a fee spike was happening at the time, so you had to pay some extra miner
> fees".
>
>
> ----
>
> And since you and your paper openly discusses it anyway, I would like to
> reveal that the MAD-HTLC argument does not apply to *just* HTLCs.
> You make recommendations about `to_self_delay` and
> `channel_reserve_satoshis`, which are not parameters of Lightning HTLCs
> (those are stuff like `cltv_delta` and `final_cltv`), but are channel
> parameters.
>
> The MAD-HTLC argument applies just as well to channel mechanisms
> themselves, ***independently of*** any HTLCs they transport.
>
> The MAD-HTLC paper has the following core argument:
>
> * We currently assume that currently-valid transactions will inevitably
> supersede alternate transactions that are valid at a later block height,
> simply because of the time advantage.
> * However, the owner of a later-block-height transaction can bribe
> miners to defer confirmation of currently-valid transactions, until its
> later-block-height transaction is valid and confirms.
>
> The above core argument is presented as applying to HTLCs.
>
> However, the same argument actually **also** applies to all current
> offchain multiparticipant cryptocurrency systems (i.e. "channel
> mechanisms").
>
> * Spilman
> * Poon-Dryja (what we currently use in Lightning)
> * Decker-Wattenhofer decrementing-`nSequence`
> * Decker-Russell-Osuntokun
>
> The [Khabbazian-Nadahalli-Wattenhofer "Timelocked Bribing" paper](
> https://eprint.iacr.org/2020/774.pdf) mentions the use of revoked
> transactions in a Poon-Dryja mechanism, but seems to imply that the issue
> is with the HTLC instantiated inside the revoked transaction.
> But note that the paper describes recommendations for the `to_self_delay`
> parameter and also analyzes the `channel_reserve_satoshis` parameter, which
> are parameters of the ***Poon-Dryja*** mechanism, and **not** of the HTLCs
> instantiated inside it.
>
> So, to be very clear, the MAD-HTLC argument applies to all the above
> mechanisms *even if HTLCs are not used at all*.
> Or put another way, if you use a modern offchain updateable cryptocurrency
> system at all, you are still vulnerable to the MAD-HTLC argument even if
> you never instantiate HTLCs inside the offchain system.
>
> Thus, other proposed systems that (could) use any of the channel
> mechanisms, but do ***not*** necessarily use HTLCs, such as CoinPools,
> channel factories, and statechains, are also vulnerable to the MAD-HTLC
> argument.
>
> In particular, if the MAD-HTLC argument holds, we should take note that
> e.g. Lightning channels have to be at least as large as any HTLC they
> contain, and since the MAD-HTLC argument applies to the channel itself (in
> addition to any HTLCs they contain), the application of that argument
> implies greater loss, as it is the entire channel that is at risk, not just
> any HTLCs it might contain.
>
> Spilman
> =======
>
> A Spilman channel is a unidirectional single-funded channel.
>
> The overall idea was presented pre-SegWit, and needed
> `OP_CHECKLOCKTIMEVERIFY` to be malleation-safe.
> I will describe here a modernized version that uses SegWit (and thus is
> malleation safe) instead.
>
> Suppose Bob wishes to make a Spilman channel to Alice.
> The setup is as follows:
>
> * Bob creates but does *NOT* sign a funding transaction, paying out to a
> 2-of-2 between Alice and Bob, and hands over this txid and the output
> number to Alice.
> * Alice creates a timeout transaction, `nLockTime`d to a pre-agreed
> locktime, spending the above txout, and returning the funds to Bob, and
> signs this transaction and hands over the signature and tx to Bob.
> * Bob signs the funding transaction and broadcasts it.
> * Alice and Bob wait for deep confirmation of the funding tx.
>
> At each payment from Bob to Alice, Bob signs a non-`nLockTime`d (or one
> with current blockheight) transaction that spends the funding txout and
> assigns more of the fund to Alice, then sends the signature and tx to Alice.
>
> At any time, Alice can unilaterally close the channel using any of the
> signatures given by Bob.
> Rationally, it will publish the one that gives it the most money, which is
> the latest such transaction, thus leading to the unidirectional nature of
> Spilman channels.
> Alice needs to perform this unilateral close far before the pre-agreed
> locktime.
>
> Under the MAD-HTLC argument, Bob can bribe miners to ignore the Alice
> unilateral close transaction, and the initial timeout transaction by Bob
> gets confirmed even if within the channel mechanism Alice is supposed to
> own most or all of the funds.
>
> Poon-Dryja
> ==========
>
> A Poon-Dryja channel is a modern two-participant bidirectional channel.
>
> The core of security of Poon-Dryja involves "revocable outputs".
> A revocable output is an output that, when published onchain, is owned by
> one entity (the owner), but that entity may reveal a secret, the revocation
> secret, to another entity (the revoker).
> Once that other entity knows the revocation secret, if the output is ever
> published onchain, it can revoke the output and claim its value.
>
> Poon-Dryja uses this building block to implement an updateable state.
> All states are represented by commitment transactions that have revocable
> outputs.
> In order to advance to a new state, the revocable outputs of previous
> states are revoked by exchanging revocation secrets.
> Thus, the security of Poon-Dryja is dependent on the correct operation of
> revocation.
>
> Revocable outputs are implemented by imposing a relative locktime on the
> owner of the output, and requiring knowledge of two secrets from the
> revoker.
>
> Thus, a revocable output has two branches:
>
> * Revocation branch: with the revoker privkey and knowledge of a
> revocaation secret, the revoker can claim the fund immediately.
> * Claim branch: with the owner privkey and a relative locktime, the owner
> can claim the fund after a pre-agreed number of blocks (`to_self_delay` in
> Lightning) since the output is confirmed onchain.
>
> Under the MAD-HTLC argument, the owner of the revoked output can bribe
> miners to ignore attempts by the revoker to claim the funds until the claim
> branch is valid and confirmable.
> Thus, a thief can publish old state, then apply the MAD-HTLC argument to
> get miners to ignore the revoker of the old state.
>
> Decker-Wattenhofer decrementing-`nSequence`
> ===========================================
>
> Decker-Wattenhofer ("Duplex Micropayment Channels") is a modern
> multi-participant (N >= 2) offchain updateable cryptocurrency mechanism.
>
> Decker-Wattenhofer chains together two different mechanisms, embedding
> them one inside the other, in order to balance the tradeoffs of one with
> the tradeoffs of the other.
>
> * One or more decrementing-`nSequence` mechanisms, chained one inside the
> other.
> * Two ("duplex") unidirectional Spilman variants, using a relative
> locktime instead of an absolute locktime, one in both directions of the
> channel, inside the innermost decrementing-`nSequence` mechanism.
>
> The decrementing-`nSequence` mechanisms by themselves are multiparticipant
> (N >= 2), and if we focus only on having one or more of these mechanisms
> chained together, we can consider Decker-Wattenhofer as multiparticipant.
>
> In the decrementing-`nSequence` mechanism, there is a kickoff transaction
> which spends from the n-of-n funding outpoint, and sends it to yet another
> n-of-n output between the participants.
> Then, the second n-of-n is spent by a transaction with a relative-locktime
> `nSequence` transaction, which then distributes the money among various
> participants.
>
> When a new state is created, the participants create and sign a new
> relative-locktime `nSequence` transaction spending the kickoff n-of-n
> outpoint.
> The new state transaction has a lower `nSequence` than the most previous
> state transaction, hence decrementing-`nSequence`.
> Once the latest state transaction has a 0-block relative locktime, a newer
> state can no longer be added to the mechanism.
>
> The kickoff n-of-n outpoint thus has multiple branches, one for each
> created state.
> The most recent state is assumed to supersede previous states, because it
> has the smallest relative locktime among all states.
>
> Under the MAD-HTLC argument, a participant which prefers an older state
> can bribe miners to defer confirmation of all more recent states.
> Thus, that participant can publish the kickoff and bribe miners to defer
> more recent states until its preferred state is confirmable onchain.
>
> Decker-Russell-Osuntokun
> ========================
>
> Decker-Russell-Osuntokun ("eltoo") is a futuristic multiparticipant (N >=
> 2) offchain updateable cryptocurrency system.
>
> Decker-Russell-Osuntokun uses a proposed new `SIGHASH_NOINPUT` flag, which
> does not commit to the specific output being spent, allowing a signature
> that signs using `SIGHASH_NOINPUT` to be used to spend a different
> transaction outpoint, as long as the same pubkey is used for that outpoint.
>
> As is typical for channel mechanisms, a funding outpoint is created, which
> is an n-of-n of all participants.
> The funding outpoint is spent by an update transaction with a single
> output, which has the following branches:
>
> * Update branch: can be spent by the same n-of-n pubkeys as the funding
> outpoint, as long as the spending transaction has a higher `nLockTime` than
> the update transaction.
> * State branch: can be spent by a different n-of-n pubkeys from the same
> participants, after a relative locktime.
> * Each update transaction has its own unique set of n-of-n pubkeys for
> the state branch, given by the same participant set.
>
> Of note is that the `nLockTime` used in Decker-Russell-Osuntokun are
> always past `nLockTime`s, so that the update branch is always confirmable
> at the current tip, from now until forever.
> Only the state branch has an actual timelock that could prevent immediate
> confirmation of a transaction spending that branch.
>
> Update transactions (awesomely mis)use `nLockTime` as a sequence number;
> the first update transaction has the lowest `nLockTime`, then each
> succeeding update transaction has a higher `nLockTime`, until they reach
> the present time.
>
> Update transactions are signed with `SIGHASH_NOINPUT`.
> This allows the update transaction to not only spend the funding outpoint
> itself, but also to spend any previous update transaction.
>
> Thus, if an old update transaction is published onchain, its output can be
> re-spent by any newer update transaction before the state transaction for
> that update can come into play.
> Any other participant who notices this event can simply publish the newest
> update transaction it knows, as that would supersede the state transaction,
> which can only be confirmed after a time delay.
>
> Under the MAD-HTLC argument, a participant who prefers an older state can
> publish the update transaction for the older state, then bribe miners to
> defer confirmation of newer update transactions, until the state
> transaction for that update transaction can be confirmed.
>
> Conclusion
> ==========
>
> All the above mechanisms use a timelock, and implicitly have the
> assumption that "a transaction, that can be confirmed now, supersedes any
> transaction that has a timelock that forces it to be confirmed later".
>
> It seems likely to me that even future mechanisms will use the same
> assumption as well.
>
> In particular, many proposed mechanisms for non-federated sidechains often
> include some kind of delay between when a sidechain coin is burned and the
> corresponding mainchain coin is released (i.e. side-to-main peg).
> Often, this delay exists in order to allow showing of a counterproof that
> the supposed side-to-main transfer did not actually exist in the sidechain
> (or was later reorged out, or whatever).
> It seems to me that the MAD-HTLC argument would also apply to such
> mechanisms (if anyone still wants to go push sidechains, anyway).
>
> Thus, we really need to carefully investigate the MAD-HTLC argument.
>
> My current analysis suggests that in practice, the MAD-HTLC argument does
> not apply at all (else I would not be revealing that all channel mechanisms
> are broken **if** the MAD-HTLC argument *does* apply), since the myopic
> strategy seems to be pretty much inevitably dominant at stable states.
> But it would still be best to investigate further until we are fully
> convinced that the MAD-HTLC argument ("'earlier supersedes later' might be
> falsified by bribery") does not apply.
>
>
>
> Regards,
> ZmnSCPxj
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200703/26c3b0e4/attachment-0001.html>

2023-06-07 18:25:46

- reply

📅 Original date posted:2020-07-02
📝 Original message:On Wed, Jul 1, 2020 at 6:58 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> And your paper posits that if a miner is weak, its best strategy is to
> take the myopic strategy and include the currently-valid Alice transaction.
>
Yes. The proof is quite trivial and follows from the definition of weak: if
the myopic miner's hashpower percentage is p_i, and it's lower than f/b,
that means that f > b*p_i. By including the currently-valid Alice
transaction, the myopic miner could make f, which is higher than their
expected gain, which is b*p_i. The myopic miner has a p_i chance of mining
the first block when Bob's transaction becomes valid, and it's most likely
to stay valid for just 1 block, as every miner would want that immediately
when it gets valid. This is where we disagree with the MAD-HTLC paper. They
assume that there are not any miners with sub-1% hashrate around. We find
that there are many such miners, and with channel_reserve_satoshi set to 1%
of the channel value, Alice can bump her fees to at least 1% of the channel
value without worry (because she will get Bob's channel_reserve_satoshi's
for herself if Bob is cheating by releasing a previous commitment TXN).
We additionally also show that when strong miners know that weak miners are
around, some of their strategies get dominated as well, and they will be
forced to include Alice's transaction as well. This, if there is just one
*known* weak miner, things are good for Alice. As an FYI, in our paper
Alice is the cheater and Bob is the victim. There were reasons to "reverse
the convention", so to speak - but that's for another day :-)
>
> Thus, if Alice even *matches* Bob, it seems to me that this ratio f / b is
> 1.0 implying a miner can only be powerful if it has already 51%-attacked
> Bitcoin (which tends to invalidate all our security assumptions of
> higher-layer protocols anyway, since a 51% attacker can censor anything
> with impunity).
>
We assume that Bob will bribe with the entire channel value - because he
has received commensurate goods and services off-chain. So, Alice will find
it difficult to match Bob's bribe, but she doesn't have to.
>
> Of course, Bob can offer up to the entire fund amount, for free, to miners
> as a bribe, without loss to Bob.
>
Yes. Precisely.
>
> For more realistic scenarios where no miner has 100% hashrate, then Alice
> can make all miners weak by being willing to pay up to 50% of the fund as
> fee, as a miner that achieves greater than 50% hashrate share would already
> effectively pwnzored Bitcoin and gained UNLIMITED POWAH anyway.
>
But she doesn't have to go as far as 50%. Just 1% seems quite reasonable,
given a reasonable timelock. We have a closed form solution for the
timelock T as well. In Lightning's case, with 1% channel_reserve_satoshis
around, we arrive at T = 316, which is much longer than the current default
of 144.
>
> So it looks to me that scorched-earth is a possible mitigation against
> this attack.
>
I don't follow this. We show that a reasonable value of fees and timelock
are enough to avoid the attack. Why scorch the earth?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200702/acae8c36/attachment.html>

2023-06-07 18:25:42

- reply

📅 Original date posted:2020-06-30
📝 Original message:Hello ZmnSCPxj (as there would be no better way to start an email to you
:-),
I posted a reply to Dave in the other sub-thread of this main thread. We
have a paper about something similar to what you have said - where we look
at "weak" and "strong" miners, and how even if there are a few weak miners,
they have a dominating strategy, etc.
On Mon, Jun 29, 2020 at 8:05 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Good morning Dave, et al.,
>
>
> > > Myopic Miners: This bribery attack relies on all miners
> > >
> > >
> > > being rational, hence considering their utility at game conclu-
> > > sion instead of myopically optimizing for the next block. If
> > > a portion of the miners are myopic and any of them gets to
> > > create a block during the first T − 1 rounds, that miner would
> > > include Alice’s transaction and Bob’s bribery attempt would
> > > have failed.
> > > In such scenarios the attack succeeds only with a certain
> > > probability – only if a myopic miner does not create a block
> > > in the first T − 1 rounds. The success probability therefore
> > > decreases exponentially in T . Hence, to incentivize miners
> > > to support the attack, Bob has to increase his offered bribe
> > > exponentially in T .
> >
> > This is a good abstract description, but I think it might be useful for
> > readers of this list who are wondering about the impact of this attack
> > to put it in concrete terms. I'm bad at statistics, but I think the
> > probability of bribery failing (even if Bob offers a bribe with an
> > appropriately high feerate) is 1-exp(-b*h) where `b` is the number of
> > blocks until timeout and `h` is a percentage of the hashrate controlled
> > by so-called myopic miners. Given that, here's a table of attack
> > failure probabilities:
> >
> > "Myopic" hashrate
> > B 1% 10% 33% 50%
> > l +---------------------------------
> > o 6 | 5.82% 45.12% 86.19% 95.02%
> > c 36 | 30.23% 97.27% 100.00% 100.00%
> > k 144 | 76.31% 100.00% 100.00% 100.00%
> > s 288 | 94.39% 100.00% 100.00% 100.00%
> >
> > So, if I understand correctly, even a small amount of "myopic" hashrate
> > and long timeouts---or modest amounts of hashrate and short
> > timeouts---makes this attack unlikely to succeed (and, even in the cases
> > where it does succeed, Bob will have to offer a very large bribe to
> > compensate "rational" miners for their high chance of losing out on
> > gaining any transaction fees).
> >
> > Additionally, I think there's the problem of measuring the distribution
> > of "myopic" hashrate versus "rational" hashrate. "Rational" miners need
> > to do this in order to ensure they only accept Bob's timelocked bribe if
> > it pays a sufficiently high fee. However, different miners who try to
> > track what bribes were relayed versus what transactions got mined may
> > come to different conclusions about the relative hashrate of "myopic"
> > miners, leading some of them to require higher bribes, which may lead
> > those those who estimated a lower relative hash rate to assume the rate
> > of "myopic" mining in increasing, producing a feedback loop that makes
> > other miners think the rate of "myopic" miners is increasing. (And that
> > assumes none of the miners is deliberately juking the stats to mislead
> > its competitors into leaving money on the table.)
>
> A thought occurs to me, that we should not be so hasty to call non-myopic
> strategy "rational".
> Let us consider instead "myopic" and "non-myopic" strategies in a
> population of miners.
>
> I contend that in a mixed population of "myopic" and "non-myopic" miners,
> the myopic strategy is dominant in the game-theoretic sense, i.e. it might
> earn less if all miners were myopic, but if most miners were non-myopic and
> a small sub-population were myopic and there was no easy way for non-myopic
> miners to punish myopic miners, then the myopic miners will end up earning
> more (at the expense of the non-myopic miners) and dominate over non-myopic
> miners.
> Such dominant result should prevent non-myopic miners from arising in the
> first place.
>
> The dominance results from the fact that by accepting the Alice
> transaction, myopic miners are effectively deducting the fees earned by
> non-myopic miners by preventing the Bob transaction from being confirmable.
> On the other hand, even if the non-myopic miners successfully defer the
> Alice transaction, the myopic miner still has a chance equal to its
> hashrate of getting the Bob transaction and its attached fee.
> Thus, myopic miners impose costs on their non-myopic competitors that
> non-myopic miners cannot impose their myopic competitors.
> If even one myopic miner successfully gets the Alice transaction
> confirmed, all the non-myopic miners lose out on the Bob bribe fee.
>
> So I think the myopic strategy will be dominant and non-myopic miners will
> not arise in the first place.
>
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200630/ecf01349/attachment.html>

2023-06-07 18:25:41

- reply

📅 Original date posted:2020-06-29
📝 Original message:On Sun, Jun 28, 2020 at 2:16 PM David A. Harding via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> So, if I understand correctly, even a small amount of "myopic" hashrate
> and long timeouts---or modest amounts of hashrate and short
> timeouts---makes this attack unlikely to succeed (and, even in the cases
> where it does succeed, Bob will have to offer a very large bribe to
> compensate "rational" miners for their high chance of losing out on
> gaining any transaction fees).
>
We were separately working on a similar problem, and wrote a paper as well:
https://eprint.iacr.org/2020/774 *
We look at the Alice's-Fees/Bob's-Bribe ratio. We also look at "strong" and
"weak" miners in this context. If a miner is weak, their hash-rate is lower
than this fees/bribe ratio. If they are strong, their hash rate is more
than this fees/bribe ratio. In this setting, it turns out that if there are
only strong miners, Bob will win. If there is at least one weak miner,
Alice has to win, given a reasonable timeout value. We found it awesome
that lightning has a parameter called "channel-reserve_satoshis", which
directly helps in countering this bribe by giving Alice some leeway in fees.
* Ph.D students want to write papers, unfortunately.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200629/0825c166/attachment.html>