Gleb Naumenko [ARCHIVE] / is on Nostr

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

Last Notes

2023-06-09 13:01:36

- reply

📅 Original date posted:2020-11-30
📝 Original message:
Hi Dave,
Thanks for the hard questions.
>Can’t a malicious user get around this restriction by opening channels
with themself?
You are right, preventing this kind of Sybil attack is challenging, but I don’t think it’s a no-go.
Three separate observations which make me positive about are:
1. This still requires locking funds by an attacker
2. We might start with a low credit for just random valid Stake Certificates, but increase if they showed good activity: e.g., they we route through them a lot, or they paid us a lot of fees previously. Both ideas would require some extra work of linking Stake Certificates to these activities in a private matter. The paid-fees one should be easier.
3. We might give more credit if they or their channel counterparty is just a known good actor. This can be achieved by a routing node have this second list of trustworthy UTXOs payment sender may prove inclusion for.
(2) and (3) may be just a part of routing node Stake Certificate acceptance policy, I think if we like the ideas, new can make them work in a desirable private/scalable way.
We might also have senders proving that they paid fees to *other* (real) non-Sybil routing nodes, although it adds even more complexity.
Also, now that I’m thinking, maybe payment receiver could also contribute to the Stake Certificate…
>How would a stake certificate prove that the UTXO was generated for LN rather than just belonging to a user with a 2-of-2 multisig wallet or any key-path-spendable taproot wallet?)
You are right, we can only get so close to proving that it’s indeed a payment channel. I think the problem of channels-with-themselves (see a beginning of this response) includes this one, so if we solve that, this won’t be a big deal.
>That cost doesn’t seem high enough to me to effectively prevent attacks.
Perhaps having 1000 BTC staked should not allow them to send 1000 BTC over Lightning, but maybe, with Stake Certificates, this could be restricted to say 100 BTC per 0.1 hour?
This, of course, requires hypothesizing about honest economic activity in the Lightning Network.
The exact economics of Stake Certificates still has to be worked out, I’m just suggesting that we probably have a lot flexibility with restrictions, since we’re very permissive towards users to begin with.
– gleb
On Nov 28, 2020, 8:25 PM +0200, David A. Harding <dave at dtrt.org>, wrote:
> On Thu, Nov 26, 2020 at 11:40:46PM +0200, Gleb Naumenko wrote:
> >
> > Hello list,
>
> Gleb and Antoine,
>
> This is an interesting idea! Thank you for working on it.
>
> I had difficulty with one part of the proposal:
>
> > #### Should we allow holding *any* Bitcoins (not just LN channels) for Stake Certificates?
> >
> > [...] we believe that allowing any UTXO would give an attacker more
> > opportunities to use their cold funds for this attack, or even have a
> > secondary market where holders sell their proofs (they have nothing to
> > loose).
>
> Can't a malicious user get around this restriction by opening channels
> with themself? (Also, aren't current channel open outputs just P2WSH
> 2-of-2 multisigs, and in the future won't they be generic P2TR outputs?
> How would a stake certificate prove that the UTXO was generated for LN
> rather than just belonging to a user with a 2-of-2 multisig wallet or
> any key-path-spendable taproot wallet?)
>
> According to some random website, the current total channel balance of
> the public LN is about 1,000 BTC. Although I'm sure this will grow with
> time, it seems to me that an attacker who can rent access to stake
> certificates for a one-week attack at, say, a 5% annual interest rate
> would only need to pay 1 BTC to acquire stake certificates equal to all
> honest users at present. That cost doesn't seem high enough to me to
> effectively prevent attacks. Am I missing something?
>
> Thanks,
>
> -Dave
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20201130/1155fb80/attachment.html>

2023-06-09 13:01:36

- reply

📅 Original date posted:2020-11-30
📝 Original message:
Hi Lloyd,
> I agree with Z that this proposal is missing a strong argument as to why this is a better “proof-of-stake” than channel balances themselves.
I think Z’s consideration is about the alternative Stake Certificates proposed by t-bast, where every link in the route proves something to the next hop.
For the context see this post, specifically “point-to-point property”: https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-November/002888.html
I think you managed to apply the same argument to our original proposal as well :)
> In order to send a jamming HTLC you have to have to lock up funds to do it (they need outgoing balance for the sender and incoming balance for the receiver).
I think the issue here is with loop attacks (https://lists.linuxfoundation.org/pipermail/lightning-dev/2015-August/000135.html)? This restriction with locking funds doesn’t really work…
After getting past their intermediate hop, an attacker can make arbitrary loops and lock 100 BTC channels even by just having 1 BTC locked in the initial hop.
Stake Certificates allow for a node in the middle of the route to distinguish where the payment is coming from (in a privacy-preserving manner of course), to distinguish heavy channel users from normal.
They also allow to force an attacker to distribute jamming in time and across many channels.
Perhaps, alternative restrictions may take place by restricting based on from which immediate channel/node they are coming (one-hop). But that sounds like a mess, as a payment sender doesn’t have any control, and gossiping that would probably be a privacy leak, also it still allows free jamming I think (just a bit different).
The big deal here is to distinguish the flows, to better control them.
We can discuss this separately.
It’s true that any token might achieve the same goal here, but how to make it Sybil-resistant and prevent generating new tokens? Stake Certificates, I don’t know what else we can commit to.
> If we are talking about non-economic adversaries who simply wish to destroy LN then that’s another game altogether.
I was thinking about this scenario all the way, but maybe I should think about the other one as well.
> As David points out I don’t think you can make a distinction between real LN outputs and fake ones.
Responding here:
https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-November/002894.html
– gleb
On Nov 30, 2020, 6:39 AM +0200, Lloyd Fournier <lloyd.fourn at gmail.com>, wrote:
> Hi Gleb et al,
>
> I really appreciate the out-of-the-box thinking of this proposal.
> I will put to the side the very difficult task of creating a cryptosystem that efficiently achieves what's necessary for this to work because that seems not to be the main concern.
>
> I agree with Z that this proposal is missing a strong argument as to why this is a better "proof-of-stake" than channel balances themselves.
> In order to send a jamming HTLC you have to have to lock up funds to do it (they need outgoing balance for the sender and incoming balance for the receiver).
> Why would stake certificates be more powerful than this? I get that you decrement the UTXO's credit even if they fail. This increases the cost of sending spam (but it also increases the cost of sending normal payments since you now may be honest but have all your UTXOs run out of credit.)
> Does this increased cost (it was not zero before) actually prevent the attack without inhibiting normal usage?
>
> In general there seems to be an open question about whether these channel jamming attacks are actually economic.
> If I want to get more payments routed through me would it really be optimal to do channel jamming?
> Suppose that the nodes react to the jamming by adding extra capacity by splicing out from somewhere else. Then I have jammed up my own coins and got nothing for it.
> What if instead of attacking I allocated the coins instead to creating more valuable channels. Couldn't this be more profitable?
> I just posed this question in [1].
>
> If we are talking about non-economic adversaries who simply wish to destroy LN then that's another game altogether.
> For example if the CCP with its 1% of all Bitcoin it seized from the plustoken scam were to try and attack lightning they would likely succeed even if we had this system in place simply because they have a lot of "stake".
> As David points out I don't think you can make a distinction between real LN outputs and fake ones.
> It seems unavoidable that any coins you own could be used to produce a certificate to give you spam bandwidth (especially if you actually manage to guarantee privacy through ZKPs).
>
> [1] https://github.com/t-bast/lightning-docs/issues/7
>
> Cheers,
>
> LL
>
>
> > On Sun, Nov 29, 2020 at 5:25 AM David A. Harding <dave at dtrt.org> wrote:
> > > On Thu, Nov 26, 2020 at 11:40:46PM +0200, Gleb Naumenko wrote:
> > > >
> > > > Hello list,
> > >
> > > Gleb and Antoine,
> > >
> > > This is an interesting idea! Thank you for working on it.
> > >
> > > I had difficulty with one part of the proposal:
> > >
> > > > #### Should we allow holding *any* Bitcoins (not just LN channels) for Stake Certificates?
> > > >
> > > > [...] we believe that allowing any UTXO would give an attacker more
> > > > opportunities to use their cold funds for this attack, or even have a
> > > > secondary market where holders sell their proofs (they have nothing to
> > > > loose).
> > >
> > > Can't a malicious user get around this restriction by opening channels
> > > with themself? (Also, aren't current channel open outputs just P2WSH
> > > 2-of-2 multisigs, and in the future won't they be generic P2TR outputs?
> > > How would a stake certificate prove that the UTXO was generated for LN
> > > rather than just belonging to a user with a 2-of-2 multisig wallet or
> > > any key-path-spendable taproot wallet?)
> > >
> > > According to some random website, the current total channel balance of
> > > the public LN is about 1,000 BTC. Although I'm sure this will grow with
> > > time, it seems to me that an attacker who can rent access to stake
> > > certificates for a one-week attack at, say, a 5% annual interest rate
> > > would only need to pay 1 BTC to acquire stake certificates equal to all
> > > honest users at present. That cost doesn't seem high enough to me to
> > > effectively prevent attacks. Am I missing something?
> > >
> > > Thanks,
> > >
> > > -Dave
> > > _______________________________________________
> > > Lightning-dev mailing list
> > > Lightning-dev at lists.linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20201130/6eb06798/attachment-0001.html>

2023-06-09 13:01:32

- reply

📅 Original date posted:2020-11-27
📝 Original message:
Thank you for your interest :)
> Quick question: if I am a routing node and receive a valid stake certificate, can I reuse this stake certificate on my own outgoing payments?
That probably should be avoided, otherwise a mediocre routing node gets a lot of jamming opportunities for no good.
You are right, that’s a strong argument for proof “interactivity”: every Certificate should probably commit to *at least* public key of the routing node it is generated for.
– gleb
On Nov 27, 2020, 2:16 AM +0200, ZmnSCPxj <ZmnSCPxj at protonmail.com>, wrote:
> Good morning Gleb and Antoine,
>
> This is certainly interesting!
>
> Quick question: if I am a routing node and receive a valid stake certificate, can I reuse this stake certificate on my own outgoing payments?
>
> It seems to me that the proof-of-stake-certificate should also somehow integrate a detail of the current payment (such as payment hash/point) so it cannot be reused by routing nodes for their own outgoing payments.
>
> For example, looking only at your naive privacy-broken proposal, the signature must use a `sign-to-contract` where the `R` in the signature is actually `R' + h(R' | payment_hash)` with the `R'` also revealed.
>
> Regards,
> ZmnSCPxj
>
> > Hello list,
> >
> > In this post, we explore a different approach to channel jamming mitigation.
> > We won’t talk about the background here, for the problem description as well as some proposed solutions (mainly upfront payment schemes), see [1].
> >
> > We’re suggesting using UTXO ownership proofs (a.k.a. Stake Certificates) to solve this problem. Previously, these proofs were only used in the Lightning Network at channel announcement time to prevent malicious actors from announcing channels they don’t control. One can think of it as a “fidelity bond” (as a scarce resource) as a requirement for sending HTLCs.
> >
> > We start by overviewing issues with other solutions, and then present a naive, privacy-broken Stake Certificates. Then we examine designing a privacy-preserving version, evaluating them. At the end, we talk about non-trivial design decisions and open questions.
> >
> > ## Issues with other proposals
> >
> > We find unsatisfying that upfront payment schemes come at a cost of new fees (forward and/or backward), thus inflating payment cost for *any* payment.
> > In the future, the upfront base fee might even make “micropayments” economically infeasible by exceeding the value they transfer. Thus, a good solution should not inflate payment cost while still requiring “burning” a scarce resource (so that the attack is not free).
> >
> > Another issue with upfront payments is a circular trust dependency. Ideally, we shouldn’t introduce anything less trust-minimized than the Lightning Network itself.
> > Upfront payment schemes are not like that, because they in one way or another rely on the honest behavior of route participants.
> >
> > We believe Stake Certificates we are going to introduce are satisfactory in both of these directions: they don’t inflate payment costs for honest users and don’t require trust. The main disadvantage of Stake Certificates seems to be the novel cryptography required.
> > See more details in the “Evaluation” section.
> >
> > ## Channel Ownership Proofs as Routing Credit Balance
> >
> > Let’s say Alice wants to relay an HTLC to Carol through Bob. Per the Stake Certificates scheme, she has to commit to a particular channel UTXO by embedding an ownership proof in the onion packet while sending an HTLC to Bob.
> >
> > Bob then unwraps the onion and verifies:
> > 1) the channel identifier is pointing unambiguously to an on-chain UTXO;
> > 2) the ownership proof (e.g., a signature) is valid against the previously disclosed UTXO witness script.
> >
> > If all those checks succeed, Bob should see if Alice hasn’t exceeded her credit balance. In case she hasn’t, Bob has to “decrement Alice’s credit balance” and relay the HTLC to Carol.
> > Decrementing credit balance unconditionally of packet success or failure bounds liquidity abuse by malicious HTLC senders.
> > Since there is no credit assigned initially, “decrementing the credit balance” means just remembering that “Alice spent X out of Y of the credit she received for her Stake Certificates”.
> >
> > Unfortunately, this naive protocol is a privacy nightmare, because routing nodes can now easily assign every HTLC they forward to the sender’s UTXO.
> >
> > Let’s first define the terms here one more time, and then proceed to the non-naive, private Stake Certificates.
> >
> > - Stake Certificate. Either means a solution we’re proposing or the primitive it is based on, namely proof of UTXO ownership. As we will argue later, it actually makes sense to use proof of LN channel UTXO ownership specifically rather than any funds ownership.
> > - Stake Certificate value. An amount of the corresponding UTXO or a ballpark this amount provably belongs to.
> > - Credit balance. When Alice provides a routing node Bob with a Stake Certificate, Bob should increase Alice’s routing credit balance. Alice is then limited in her payments by this balance, and this rule is enforced by routing nodes to prevent free channel jamming in the network. Note that ideally “Alice’s credit balance“ should be virtual and only known to Alice, while routing nodes should only observe per-UTXO credit balance. We currently assume that each routing node keeps track of per-UTXO credit balance separately, see “Design decisions” for more details.
> > - Stake-to-credit function defines how much credit balance is given per a Stake Certificate of a given value. This function is a policy of a routing node, and it should be announced.
> > - Credit-to-value-transferred function defines how much value a sender can transfer along a given channel considering how much credit they might claim. The function may also consider different factors (e.g., the available capacity of a channel being used) to provide extra robustness.
> >
> > ## Privacy-preserving Stake Certificates
> >
> > The presented scheme could preserve privacy if it relied on zero-knowledge proofs of UTXO ownership by avoiding pointing to a particular UTXO.
> > More specifically, the verifier should be able to check that:
> > a) The staked UTXO is an element of the current UTXO set
> > b) The prover knows the witness script committed by the UTXO witness program
> > c) The prover knows a valid witness for the witness script
> > d) The staked UTXO was not used to produce a different Stake Certificate which is currently in use as well.
> >
> > The verifier should also have a way to see a Stake Certificate value to properly account for the credit. This can be achieved by restricting the UTXO set being proved upon to only those UTXOs with a specific range of values: “I will prove that I own a UTXO among all UTXOs between 0.5 BTC and 1 BTC”.
> >
> > Unfortunately, steps (b) and (c) require zero-knowledge protocols for general statements, which are more experimental primitives than most of the stuff we have in Bitcoin protocols,
> > although we assume it’s feasible to consider them for non-consensus stuff.
> >
> > ## Evaluation
> >
> > Stake Certificates, upfront payment schemes, and other potential solutions (given a particular configuration) may be compared along the following axis:
> > 1) Economic feasibility
> > 1a) What is the cost of overcoming the protection for an attacker? Likely a non-linear function: sats_spent =f(channels_to_jam, […])
> > 1b) How does this solution limit honest users?
> > 2) How sophisticated is this solution in terms of integration and making good UX?
> > 3) How complex is this solution in terms of protocol design/implementation?
> >
> > When it comes to (1a), both Stake Certificates and upfront payments are probably equal, in a way that they’re just best-effort ideas to increase the attack cost. Unfortunately, we currently don’t know how to design something as economically powerful as PoW in Bitcoin [3].
> > This aspect can be properly evaluated by applying these ideas to different hypothetical kinds of LN in a simulation and observing the resulting trade-off between (1a) and (1b) considering different attack strategies.
> >
> > In the previous sections of this post, we have argued that Stake Certificates may provide a much better (1b) for the cost of (3) because it relies on zero-knowledge.
> > When it comes to (2), the design of Stake Certificates may vary in terms of UX burden, from completely automatic to requiring custom actions with private keys from users.
> >
> > Some of these trade-offs along with other interesting questions are discussed in the following section.
> >
> > ## Design decisions and questions
> >
> > #### Should the credit spending be gossipped across the entire network, or should only the routing nodes involved in the payment know?
> >
> > Economically, these two approaches are likely to be equivalent, and it’s just a matter of stake-to-credit ratio.
> > However, announcing credit spending to the network results in a privacy leak. It also imposes bandwidth and CPU overhead on the routing nodes.
> >
> > #### Which zero-knowledge system should be used for Stake Certificates?
> >
> > Choosing a ZK system boils down to picking the right trade-offs of proving and verifying time, and assumptions. As we mentioned previously, we would need proving general statements.
> > At the same time, we need something cheap in both proving and verification, because Lightning is supposed to be fast.
> > At the same time, the setup probably doesn’t matter, because proofs are supposed to be verified only by one participant, a routing node this proof is generated for.
> > Perhaps we can also pick any cryptographic assumptions we want since this stuff is not mission-critical and can be easily updated if someone breaks a cryptographic assumption and we observe an attack.
> >
> > #### Should we allow holding *any* Bitcoins (not just LN channels) for Stake Certificates?
> >
> > This idea might make sense if we’re worried that some LN users might want to send more payments than they can afford per their credit. However, we believe that allowing any UTXO would give an attacker more opportunities to use their cold funds for this attack, or even have a secondary market where holders sell their proofs (they have nothing to loose).
> > Instead, we should a) design the credit-to-stake-functions better; b) encourage users send payments across different routing nodes (since credits are not tracked globally) [4].
> >
> > #### What’s the best credit-to-value-transferred function?
> >
> > We reckon that this function should be not just linear to provide maximum security against malicious channel jammers. For example, we can charge more credit for the last 20% of the capacity of the *channel used for routing*. Alternatively, we could discourage making too many payments from the same UTXO within a short period of time by charging more credit in this case.
> >
> > #### What about the interactivity and lifetime of Stake Certificates?
> >
> > Interactive proofs mean that they are constructed on demand of a routing node, non-interactive means constructed by a payment sender ahead of time.
> > Both interactivity and lifetime have something to do with the ease of producing proof and accessing keys.
> > We will omit the details of the trade-off we consider, but it remains an open question.
> >
> > #### If Stake Certificates are valid for N blocks after proof generation, does it mean that if the UTXO is spent during those N blocks, new proof can be generated from the same coins without invalidating the old proof?
> >
> > Yes, but an attacker would, first of all, have to pay an on-chain fee for this. If we’re still worried about this problem, there are workaround ideas.
> > For example, we could have epochs of 100 blocks (every epoch starts at #XYZXYZ00 block). If at the start of an epoch, a channel wasn’t in the UTXO set, it provides very little credit.
> > Alternatively, we could expand the zero-knowledge part to proving that the coins were not yet spent.
> >
> > #### Should spending a UTXO reveal all Stake Certificates generated from it?
> >
> > This would also solve the problem in the previous question, but it would mean a retrospective privacy leak again. To avoid a privacy leak, we should prevent this.
> >
> > #### What if malicious Sybil *routing* nodes failing payments causing other honest routing nodes to reduce the credit of an honest payment sender?
> >
> > Both Stake Certificates and upfront payment schemes suffer from malicious routing nodes failing the payments and “wasting” the sender’s credit or fees. This problem even applies out of the channel jamming context, when considering payment failure rate.
> > This problem can be addressed by reducing the reputation of faulty links and routing nodes on the payment sender node. When payment routing becomes a for-profit activity, this would encourage routing nodes to sanitize their links.
> > The mitigation can be even stronger by using “provable blaming” introduced in [2].
> >
> > ## Conclusion
> >
> > We propose Stake Certificates, a new solution to channel jamming. Perhaps, it might not be the best near-term solution due to the complexity, but the zero satoshi overhead for honest payments is an appealing argument to switch to it in the future.
> > This proposal also illustrates how stake-based protocols can solve Sybil challenges in the Bitcoin ecosystem. Since this might be useful in other contexts (Sybil-resistance of many kinds, proof-of-ownership), discussing Stake Certificates is even more useful.
> > The next step is a discussion of Stake Certificates. If the community finds it interesting, then we should discuss the design questions mentioned above, and choose a cryptosystem.
> >
> > Cheers,
> > Gleb Naumenko and Antoine Riard
> >
> > ———
> >
> > References and footnotes:
> > 1. https://github.com/t-bast/lightning-docs/blob/master/spam-prevention.md
> > 2. https://lists.linuxfoundation.org/pipermail/lightning-dev/2015-August/000135.html
> > 3. We don’t actually suggest PoW to solve these issues, because a) the trade-off between honest user cost and attacker cost is misaligned due to specialized hardware and b) smartphones would die too fast if they have to compute PoW; PoW is just an unreachable example of system robustness due to well-aligned game theory.
> > 4. Secondary markets are still possible even if we restrict acceptable proofs to only LN channels, but supply would be much smaller, and markets would work much worse for an attacker.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20201127/b8659b5f/attachment-0001.html>

2023-06-09 13:01:31

- reply

📅 Original date posted:2020-11-26
📝 Original message:
Hello list,
In this post, we explore a different approach to channel jamming mitigation.
We won’t talk about the background here, for the problem description as well as some proposed solutions (mainly upfront payment schemes), see [1].
We’re suggesting using UTXO ownership proofs (a.k.a. Stake Certificates) to solve this problem. Previously, these proofs were only used in the Lightning Network at channel announcement time to prevent malicious actors from announcing channels they don’t control. One can think of it as a “fidelity bond” (as a scarce resource) as a requirement for sending HTLCs.
We start by overviewing issues with other solutions, and then present a naive, privacy-broken Stake Certificates. Then we examine designing a privacy-preserving version, evaluating them. At the end, we talk about non-trivial design decisions and open questions.
## Issues with other proposals
We find unsatisfying that upfront payment schemes come at a cost of new fees (forward and/or backward), thus inflating payment cost for *any* payment.
In the future, the upfront base fee might even make “micropayments” economically infeasible by exceeding the value they transfer. Thus, a good solution should not inflate payment cost while still requiring “burning” a scarce resource (so that the attack is not free).
Another issue with upfront payments is a circular trust dependency. Ideally, we shouldn’t introduce anything less trust-minimized than the Lightning Network itself.
Upfront payment schemes are not like that, because they in one way or another rely on the honest behavior of route participants.
We believe Stake Certificates we are going to introduce are satisfactory in both of these directions: they don’t inflate payment costs for honest users and don’t require trust. The main disadvantage of Stake Certificates seems to be the novel cryptography required.
See more details in the “Evaluation” section.
## Channel Ownership Proofs as Routing Credit Balance
Let’s say Alice wants to relay an HTLC to Carol through Bob. Per the Stake Certificates scheme, she has to commit to a particular channel UTXO by embedding an ownership proof in the onion packet while sending an HTLC to Bob.
Bob then unwraps the onion and verifies:
1) the channel identifier is pointing unambiguously to an on-chain UTXO;
2) the ownership proof (e.g., a signature) is valid against the previously disclosed UTXO witness script.
If all those checks succeed, Bob should see if Alice hasn’t exceeded her credit balance. In case she hasn’t, Bob has to “decrement Alice’s credit balance” and relay the HTLC to Carol.
Decrementing credit balance unconditionally of packet success or failure bounds liquidity abuse by malicious HTLC senders.
Since there is no credit assigned initially, “decrementing the credit balance” means just remembering that “Alice spent X out of Y of the credit she received for her Stake Certificates”.
Unfortunately, this naive protocol is a privacy nightmare, because routing nodes can now easily assign every HTLC they forward to the sender’s UTXO.
Let’s first define the terms here one more time, and then proceed to the non-naive, private Stake Certificates.
- Stake Certificate. Either means a solution we’re proposing or the primitive it is based on, namely proof of UTXO ownership. As we will argue later, it actually makes sense to use proof of LN channel UTXO ownership specifically rather than any funds ownership.
- Stake Certificate value. An amount of the corresponding UTXO or a ballpark this amount provably belongs to.
- Credit balance. When Alice provides a routing node Bob with a Stake Certificate, Bob should increase Alice’s routing credit balance. Alice is then limited in her payments by this balance, and this rule is enforced by routing nodes to prevent free channel jamming in the network. Note that ideally “Alice’s credit balance“ should be virtual and only known to Alice, while routing nodes should only observe per-UTXO credit balance. We currently assume that each routing node keeps track of per-UTXO credit balance separately, see “Design decisions” for more details.
- Stake-to-credit function defines how much credit balance is given per a Stake Certificate of a given value. This function is a policy of a routing node, and it should be announced.
- Credit-to-value-transferred function defines how much value a sender can transfer along a given channel considering how much credit they might claim. The function may also consider different factors (e.g., the available capacity of a channel being used) to provide extra robustness.
## Privacy-preserving Stake Certificates
The presented scheme could preserve privacy if it relied on zero-knowledge proofs of UTXO ownership by avoiding pointing to a particular UTXO.
More specifically, the verifier should be able to check that:
a) The staked UTXO is an element of the current UTXO set
b) The prover knows the witness script committed by the UTXO witness program
c) The prover knows a valid witness for the witness script
d) The staked UTXO was not used to produce a different Stake Certificate which is currently in use as well.
The verifier should also have a way to see a Stake Certificate value to properly account for the credit. This can be achieved by restricting the UTXO set being proved upon to only those UTXOs with a specific range of values: “I will prove that I own a UTXO among all UTXOs between 0.5 BTC and 1 BTC”.
Unfortunately, steps (b) and (c) require zero-knowledge protocols for general statements, which are more experimental primitives than most of the stuff we have in Bitcoin protocols,
although we assume it’s feasible to consider them for non-consensus stuff.
## Evaluation
Stake Certificates, upfront payment schemes, and other potential solutions (given a particular configuration) may be compared along the following axis:
1) Economic feasibility
1a) What is the cost of overcoming the protection for an attacker? Likely a non-linear function: sats_spent =f(channels_to_jam, […])
1b) How does this solution limit honest users?
2) How sophisticated is this solution in terms of integration and making good UX?
3) How complex is this solution in terms of protocol design/implementation?
When it comes to (1a), both Stake Certificates and upfront payments are probably equal, in a way that they’re just best-effort ideas to increase the attack cost. Unfortunately, we currently don’t know how to design something as economically powerful as PoW in Bitcoin [3].
This aspect can be properly evaluated by applying these ideas to different hypothetical kinds of LN in a simulation and observing the resulting trade-off between (1a) and (1b) considering different attack strategies.
In the previous sections of this post, we have argued that Stake Certificates may provide a much better (1b) for the cost of (3) because it relies on zero-knowledge.
When it comes to (2), the design of Stake Certificates may vary in terms of UX burden, from completely automatic to requiring custom actions with private keys from users.
Some of these trade-offs along with other interesting questions are discussed in the following section.
## Design decisions and questions
#### Should the credit spending be gossipped across the entire network, or should only the routing nodes involved in the payment know?
Economically, these two approaches are likely to be equivalent, and it’s just a matter of stake-to-credit ratio.
However, announcing credit spending to the network results in a privacy leak. It also imposes bandwidth and CPU overhead on the routing nodes.
#### Which zero-knowledge system should be used for Stake Certificates?
Choosing a ZK system boils down to picking the right trade-offs of proving and verifying time, and assumptions. As we mentioned previously, we would need proving general statements.
At the same time, we need something cheap in both proving and verification, because Lightning is supposed to be fast.
At the same time, the setup probably doesn’t matter, because proofs are supposed to be verified only by one participant, a routing node this proof is generated for.
Perhaps we can also pick any cryptographic assumptions we want since this stuff is not mission-critical and can be easily updated if someone breaks a cryptographic assumption and we observe an attack.
#### Should we allow holding *any* Bitcoins (not just LN channels) for Stake Certificates?
This idea might make sense if we’re worried that some LN users might want to send more payments than they can afford per their credit. However, we believe that allowing any UTXO would give an attacker more opportunities to use their cold funds for this attack, or even have a secondary market where holders sell their proofs (they have nothing to loose).
Instead, we should a) design the credit-to-stake-functions better; b) encourage users send payments across different routing nodes (since credits are not tracked globally) [4].
#### What’s the best credit-to-value-transferred function?
We reckon that this function should be not just linear to provide maximum security against malicious channel jammers. For example, we can charge more credit for the last 20% of the capacity of the *channel used for routing*. Alternatively, we could discourage making too many payments from the same UTXO within a short period of time by charging more credit in this case.
#### What about the interactivity and lifetime of Stake Certificates?
Interactive proofs mean that they are constructed on demand of a routing node, non-interactive means constructed by a payment sender ahead of time.
Both interactivity and lifetime have something to do with the ease of producing proof and accessing keys.
We will omit the details of the trade-off we consider, but it remains an open question.
#### If Stake Certificates are valid for N blocks after proof generation, does it mean that if the UTXO is spent during those N blocks, new proof can be generated from the same coins without invalidating the old proof?
Yes, but an attacker would, first of all, have to pay an on-chain fee for this. If we’re still worried about this problem, there are workaround ideas.
For example, we could have epochs of 100 blocks (every epoch starts at #XYZXYZ00 block). If at the start of an epoch, a channel wasn’t in the UTXO set, it provides very little credit.
Alternatively, we could expand the zero-knowledge part to proving that the coins were not yet spent.
#### Should spending a UTXO reveal all Stake Certificates generated from it?
This would also solve the problem in the previous question, but it would mean a retrospective privacy leak again. To avoid a privacy leak, we should prevent this.
#### What if malicious Sybil *routing* nodes failing payments causing other honest routing nodes to reduce the credit of an honest payment sender?
Both Stake Certificates and upfront payment schemes suffer from malicious routing nodes failing the payments and “wasting” the sender’s credit or fees. This problem even applies out of the channel jamming context, when considering payment failure rate.
This problem can be addressed by reducing the reputation of faulty links and routing nodes on the payment sender node. When payment routing becomes a for-profit activity, this would encourage routing nodes to sanitize their links.
The mitigation can be even stronger by using “provable blaming” introduced in [2].
## Conclusion
We propose Stake Certificates, a new solution to channel jamming. Perhaps, it might not be the best near-term solution due to the complexity, but the zero satoshi overhead for honest payments is an appealing argument to switch to it in the future.
This proposal also illustrates how stake-based protocols can solve Sybil challenges in the Bitcoin ecosystem. Since this might be useful in other contexts (Sybil-resistance of many kinds, proof-of-ownership), discussing Stake Certificates is even more useful.
The next step is a discussion of Stake Certificates. If the community finds it interesting, then we should discuss the design questions mentioned above, and choose a cryptosystem.
Cheers,
Gleb Naumenko and Antoine Riard
———
References and footnotes:
1. https://github.com/t-bast/lightning-docs/blob/master/spam-prevention.md
2. https://lists.linuxfoundation.org/pipermail/lightning-dev/2015-August/000135.html
3. We don’t actually suggest PoW to solve these issues, because a) the trade-off between honest user cost and attacker cost is misaligned due to specialized hardware and b) smartphones would die too fast if they have to compute PoW; PoW is just an unreachable example of system robustness due to well-aligned game theory.
4. Secondary markets are still possible even if we restrict acceptable proofs to only LN channels, but supply would be much smaller, and markets would work much worse for an attacker.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20201126/618274fa/attachment-0001.html>

2023-06-09 12:59:06

- reply

📅 Original date posted:2020-02-26
📝 Original message:
In this email, myself (gleb) and ariard want to discuss some aspects of the LN implementations when it comes to massive channel closing.
LN security model relies on the unilateral capability to timely confirm on-chain commitment transaction. Currently, fee rates of both commitment transaction and HTLC-timeout/HTLC-Success are pre-committed at signatures and can be interactively updated with a `update_fee` message. In case of mempool fee rates surge and a counterparty being adversarial or irresponsive (by being offline by occasion or under attack), this mechanism isn’t reliable because a low-fee rate commitment transaction may never make it into network mempools. Switching to automatic single-party dynamic fee-bumping of *their* commitment transaction via CPFP/package relay would solve this issue, while potentially opening new attack vectors.
If dynamic fee-bumping is used by a significant fraction of LN nodes, this security measure may be exploited by a miner, a massive LN channels closing would choke the mempool, dynamic fee-bumpers would react in consequence and fee rates raise to the roof. Miners would harvest abnormal high-fees for multiple blocks.
A massive channel closing may be provoked by feeding an invalid block to light clients (in the BIP157 paradigm), as they don’t have utxo access, they can’t verify input signatures (note: the only utxo spend they can check is the funding_output and they should do so) and lead to think than their channel is closed. This may provoke a spurious broadcast of their local commitment transaction, this one being valid and propagating on the base layer. Even if an invalid block isn’t fetched, the secure strategy on what to do when your chain view is messed up by an attacker is still an open question. Note that one invalid block may be used to force-close multiple channels, making this attack more economically feasible.
Another attack building block could be to exploit any LN protocol/implementation vulnerability like a malicious HTLC-of-death which would provoke honest parties to close their mutual channel when routed through [0]
LN light clients should disable HTLC routing and avoid any aggressive fee-bumping for a broadcast of local commitment transactions as time-sensitivity doesn’t matter in this case beyond UX and funds stuck in-flight.
Bounding dynamic-fees engine may be viewed as a game-theoretic aspect between LN parties (burn the maximum in fee rate to avoid an attacker to make any profit) and macro-considerations (prevent miner to exploit the whole LN network, conservative mempool/resources usage).
Considering that most of the block reward is currently subsidized, the incentives for miners to launch this attack are questionable. However, this might change when the fraction of fees in the reward becomes higher.
As LN becomes an important part of the Bitcoin ecosystem, it’s important to acknowledge the mining-related incentives and risks, as these may at the end be used to influence protocol development.
Since the LN infrastructure seems to be moving towards the heavy use of light clients, and the attacks we mentioned are expected to appear again (at least in some of the implementations), we believe it’s important to understand the mechanics of these attacks and countermeasures.
It would be interesting to have an empirical study (based on the historical data) and a simulation of the fee spikes, with parameterized:
- how many channels are vulnerable to force-closing (based on the particular LN implementations)
- what are the properties of those channels (amount, timelocks)
- what is the distribution of those channels across nodes
- how many nodes implement dynamic bumping
- mining reward allocation
What are your opinions on these issues?
– gleb
[0] One example with this RL issue:
(https://github.com/rust-bitcoin/rust-lightning/pull/513)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20200226/d529ce9f/attachment-0001.html>

2023-06-07 23:19:06

- reply

📅 Original date posted:2023-02-02
🗒️ Summary of this message: This post discusses the game-theoretic security of time-sensitive protocols if miners are open to censorship for a reward, and outlines the requirements for such behavior to become practical. It also presents simple opcode-based and nLockTime-based constructions for two-party contracts.
📝 Original message:## Intro
Most of it feels like implicit knowledge, but I couldn't find anything written so here it is. The ideas towards anchor outputs and the conclusions probably have some new perspectives.
This post is about the game-theoretic security of time-sensitive protocols if miners are open to censorship for a reward. To become practical, the following has to happen.
1) a substantial hashrate has to be willing to participate in this behaviour, according to the known formula from the Whitepaper. The more blocks it takes to attack (defined by a particular protocol configuration and could be tuned), the exponentially higher % hashrate is required.
2) a communication layer is required to send bribes to these miners. This could be a private transaction relay network, or a mempool allowing still-time-locked transactions. It could be even an announcement board (e.g., submitting raw txs under a Twitter hashtag and inviting miners to monitor it).
3) a bribe transaction construction (will be explained later).
In this post, I talk about the case when:
1. a significant hashrate (e.g., 95%+) is open to take these bribes;
2. but miners don't trust each other;
3. and there is no reorgs.
Assumption \*(2) is more nuanced. What I mean here is roughly "miner X would rather take an immediate gain than commit to a lenghty scenario where many miners coordinate to take reward on behalf of each other and then distribute it accordingly to the hashrate". The game theory of this assumption should be better defined in the future.
We will see, how widely known tweaks lift the bar for (2) and (3) and how this could be further improved.
*A special case of this scenario is miners withholding Alice's transaction to force her to bump fees, even if Bob hasn't submitted a bribe. Here I assume miners won't do it unless there is an external incentive (Bob's bribe), although this issue is also interesting.*
## Simple opcode-based construction
The simplest time-sensitive two-party contract is PowSwap (a bet on the future block issuance rate), a single on-chain UTXO with the following spending conditions:
- Alice’s key can spend if height=H is reached;
- Bob’s key can spend if Time=T is reached.
Say H is approaching quickly, and T is far behind. Bob now uses a private mining relay to submit his non-mineable transaction paying e.g. half of the UTXO value towards fees.
Alice has two problems: 1) she can’t figure out why her transaction isn’t mined and how much fee to overpay; 2) the attack is free for Bob (he has nothing to lose), while Alice loses everything up to the full UTXO value.
## Simple nLockTime-based construction
If parties use pre-signed transactions with nLockTime (instead of the opcodes), Bob’s fee can be pre-signed to a rather low value, so that Alice can reasonably overbid it without much loss (she probably doesn't even need to take any action).
Bob can, however, bump the fee by creating a CPFP transaction with super-high fee. All it requires now is submitting twice as much data to the private mining relay (and burning slightly more in fees).
## nLockTime-based construction with OP_CSV output
If Bob’s output can’t be spent right away, but is forced to be deterred to even one block in the future, it makes taking this bribe not rational: a censoring miner can’t be sure about the deferred reward (remember, miners don't trust each other). At the same time, mining the honest transaction and taking its fee is always available earlier.
Smart contracts could possibly make it rational for miners (see [1]), e.g. by allowing Bob to allocate the bribe based on the historic hashrate distribution linked to coinbase pubkeys.
At the same time, this approach makes dynamic fee management impossible.
## Anchor outputs
Anchor outputs allow bringing external capital for fee management while locking internal capital. Bob can use this capital for a bribe. If the attack fails, Bob's external capital remains safe, so this is not so bad for Bob.
The attack can be more costly if this external capital was claimable:
- by Alice: e.g., Alice can steal a (covenanted) anchor output if it's revealed before Bob's nLockTime makes it mineable (requires her to monitor the private relay);
- or by miners, e.g. if Alice forces Bob, at contract setup, to use a reverse time-lock (the anchor can be stolen by miner if seen before time=T); or if mining Alice's honest transaction also allows miners to take Bob's fee output (e.g., Alice's honest transaction *could* act as a parent/preimage, conditionally, although this may require reverse time-locking Alice to protect Bob...)
*Ephemeral anchors doesn’t do much w.r.t. our trade-off, as it is a mempool-oriented thing.*
## Lightning
Lightning is different from the described protocol in two things:
1) It relies on intermediate transactions (e.g., Commitment in Poon-Dryja);
2) Usually both parties have some balance in the channel.
I believe that (1) doesn’t change the situation much, it just makes it more nuanced.
(2) is irrelevant because an attacker can just spend the entire channel before the attack.
Thus, most of these concerns apply to lightning equally.
## Related work
The LN paper briefly mentioned this problem, although it was claimed impractical due to a high degree of required collusion. We already see private mining relay in mevwatch.info (ethereum), and we had FIBRE (I think it was neutral).
[2] discussed constructions and economics for bribing miners. [1] suggests more practical considerations for achieving this. Both don’t focus on the risks of particular time-sensitive protocol constructions.
[3] highlighted a similar protocol risk, but the proposed solution seems to work only if an attacker has funds to lose locked in the contract (e.g., collateral, lightning balance, powswap payout).
## Conclusions
To increase the attack bar w.r.t the configuration described in the intro, we should either:
- stick to the *nLockTime-based construction with OP_CSV output*, forget about dynamic fee management, and hope that bribe allocation smart contracts doesn't work out;
- use anchor outputs (or another external fee scheme), but enforce a way to steal/burn the external fee if it's an attack;
- design new fee/channel constructions.
These ideas may also be helpful for alternative payment channels designs as well (v3+ephemeral anchors, SIGHASH_GROUP, etc.), or in the future to protect against more powerful covenants allowing stronger bribes (see [1]).
Thanks to Antoine Riard and Greg Sanders for initial discussion.
-------------------------
## References
1. TxWithhold Smart Contracts by Gleb Naumenko | BitMEX Blog (https://blog.bitmex.com/txwithhold-smart-contracts/)
2. Temporary Censorship Attacks in the Presence of Rational Miners (https://eprint.iacr.org/2019/748.pdf)
3. MAD-HTLC: Because HTLC is Crazy-Cheap to Attack (https://arxiv.org/pdf/2006.12031.pdf)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230202/275a0387/attachment.html>

2023-06-07 18:25:11

- reply

📅 Original date posted:2020-06-03
📝 Original message:Hi! I and Antoine Riard explored time-dilation attacks on Lightning.
We have a blogpost, which is probably too long to include in the email in full.
You can read it here: https://discrete-blog.github.io/time-dilation/
There’s also a paper we wrote: https://arxiv.org/abs/2006.01418
We believe this work should be interesting for anyone curious/excited about LN or other second-layer protocols in Bitcoin. We are very interested in your opinions!
Now, let me share the intro from the post with you (which is really a summary of the work), since it’s about the right size for a mailing list post. Hopefully, it would motivate you to read further.
Protocols on top of the Bitcoin base layer are really cool. They offer tremendous opportunities in terms of scalability, confidentiality, and functionality, at a cost of new security assumptions.
We all know payment channels have to be monitored, otherwise, the funds can be stolen. That sounds too abstract though. We decided to study what an attacker actually has to do to steal funds from LN users.
More specifically, we explored how peer-to-peer layer attacks can help with breaking the assumption above. Per time-dilation attacks, an attacker controls the victim’s access to the Bitcoin network (hard, but not impossible) and delays block delivery to the victim. After that, the attacker exploits that the victim can’t access recent blocks in a timely manner. In some cases, it is enough to isolate the victim only for two hours.
Then the attacker makes a couple (totally legit) actions on the Lightning Network towards the victim’s channels, and at the same time commits a different state instead. Since the victim is behind in terms of the latest blockchain tip, they cannot detect this and react as required by the protocol.
We demonstrate three different ways the attacker can steal funds from the victim, and discuss the feasibility/cost of these attacks. We also explore the broad scope of countermeasures, which may significantly increase the attack cost.
In short, the takeaways from our work are:
1. Many Lightning users (those with Bitcoin light clients) are currently vulnerable to Eclipse attacks.
2. Those Lightning users which run Bitcoin Core full nodes are more robust to Eclipse attacks, but the attacks are still possible as recent research suggests.
3. Eclipse attacks enable stealing funds via time-dilation.
4. Time-dilation attacks can’t be mitigated with just observing slow block arrival, so there is no simple solution to (3).
5. Thus, time-dilation is a practical way to steal funds from eclipsed users. Neither it requires hashrate nor targets merchants only. Light client users are a good target because they are easy to attack. Full node users are a good target because they are often used by major hubs (or service providers), and stealing their aggregate liquidiy might justify the high attack cost.
6. Strong anti-Eclipse measures is the key solution. WatchTowers are cool too.
Best,
Gleb Naumenko and Antoine Riard
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200603/c9aff631/attachment.html>

2023-06-07 18:21:23

- reply

📅 Original date posted:2019-10-23
📝 Original message:Hi,
### Introduction
I was recently looking into AddrMan and I realized that unlike with blocks (BIP152) and transactions (a node can opt-out via various mechanisms such as blocks-only or block-only-relay), address relay is under-specified.
For example, we had a discussion [1] on whether SPV nodes store/relay IP addresses. While it seems they don’t do it currently in practice, in some cases they should if they want to be secure and reliable.
### Motivation
This change would decouple addr relay considerations from light/full node/block-relay-only.
This would also allow us to easier analyze (in a scientific sense, not in a spying sense) and adjust address relay, which currently seems to have understudied properties and guarantees.
In practice, this may allow more efficient address relay (fewer messages and less time to relay a new address across all nodes) both immediately and potentially long-term.
### Solution
I want to suggest making explicit whether a node promises to participate in address relay by a) forwarding unsolicited messages (I work on a somewhat related issue in this PR [2]) , and, b) responding to GETADDR.
In my opinion, these 2 signals (a and b) should be viewed independently.
Obviously, these signals should not be relied upon and future protocol changes should assume they may represent lies.
However, explicitly opting-out of relay addresses will help to improve non-adversarial address relay.
### Implementation
I see 2 ways to implement this:
- 2 new service bits
- per-link-direction negotiation: e.g., use BIP-155 (a new message sendaddrv2 is discussed here [3] and can be used to signal this)
Both of them can allow decoupling addr relay from node type, but they do have different trade-offs.
#### Service bits
Having service bits makes sense only if nodes are going to make peering decisions based on it. (everything else might be achieved without introducing a service bit). It is not clear to me whether this makes sense in this context.
The fundamental problem with service bits is that they make a uniform “promise” for all connections to a given node. E.g., if node X announces NODE_ADDR_FORWARD, all nodes in the network expect node X to forward addresses. (If the “promise” is not strong, then additional negotiation is required anyway, so service bits do not solve the problem).
It’s worth keeping in mind that all of the honest reachable full nodes nodes DO relay addresses, and we already won’t connect to those nodes which don’t (light clients). Service bits won’t help here because the problem of connecting to non-addr-relaying full nodes does not exist.
Maybe, if we think that a large fraction of reachable nodes might start completely disabling addr relay to all in the future, then it makes sense to have this service bit, to prevent nodes from accidentally connecting to these peers only and not learning addrs.
Intuitively, it’s also easier to shoot in the leg with the deployment of service bits (might make it easier for attacker to accumulate connections comparing to the case of victims choosing their peers uniformly at random without considering new service bit).
#### Per-link-direction negotiation
This approach does not have the shortcomings mentioned above.
In addition, I think that having more flexibility (Per-link-direction negotiation) is better for the future of the protocol, where some nodes might want to opt-out of addr relay for a subset of their links.
(A node might want to opt-out from addr relay for particular links due to privacy reasons because addr-relay currently leaks information and maybe we shouldn’t relay transactions through the same links).
And I think this future is much more likely to happen than a future where a significant fraction of reachable nodes disable addr relay to *everyone* and need to announce this to the network. Also, even if needed, this can be done with per-link-direction negotiation too, and handled by the peers accordingly.
Per-link-direction negotiation also allows to decouple the behaviour from inbound/outbound type of connection (currently we do not respond to GETADDR from outbound). This logic seems not fundamental to me, but rather a temporary heuristic to prevent attacks, which might be changed in future.
### Conclusion
I think the solution fundamentally depends on the answer to:
“Do we believe that some of the future security advices for node operators would be to disable address relay to all (or most) of the links”.
If yes, I think we should use service bits.
If no, I think we should use per-link-direction negotiation.
If the answer will change, we can also add a service bit later.
Anyway, according to the current considerations I explained in this email, I’d suggest extending BIP-155 with per-link-direction negotiation, but I’m interested in the opinion of the community.
### References
1. Bitcoin core dev IRC meeting (http://www.erisian.com.au/bitcoin-core-dev/log-2019-10-17.html)
2. p2p: Avoid forwarding ADDR messages to SPV nodes (https://github.com/bitcoin/bitcoin/pull/17194)
3. BIP 155: addrv2 BIP proposal (https://github.com/bitcoin/bips/pull/766)
– gleb
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20191023/55c63626/attachment.html>

2023-06-07 18:20:42

- reply

📅 Original date posted:2019-09-25
📝 Original message:We are opening for review a draft of the new BIP, which describes low-level specifications for the reconciliation-based transaction announcement protocol.
https://github.com/naumenkogs/bips/blob/bip-reconcil/bip-reconcil.mediawiki
Agreeing on this spec would enable integration of more bandwidth-efficient relay protocols, like Erlay (https://arxiv.org/abs/1905.10518).
The draft has all the background necessary to understand the work, so please read and review.
It introduces salted short transaction IDs (required to do reconciliation efficiently) and demonstrates how to compute sketches based on these IDs (including simple python scripts).
It also introduces wtxid-based truncated transaction IDs (to trivially save significant fraction of the bandwidth).
Finally, it specifies all the messages to be used by an efficient reconciliation-based protocol, and new state variables required for the protocol.
Please note that, comparing to the Erlay paper, we decided to add extra round, where 2 parties explicitly map 32-bit short IDs to 128-bit truncated IDs, because otherwise peers which take >1s to reconcile would cause transmitting duplicate transactions (extra bandwidth), and we cannot assume <1s latency in Bitcoin, especially over Tor.
According to my estimates, the bandwidth overhead due to the measure from the BIP (extra communication round) is only extra 10% comparing to the original Erlay estimates.
It is possible that we missed some of the state variables required to handle corner cases of the protocol, because the spec is based on my prototype code, and it might evolve when we will be building an actual production-ready implementation.
Overall, I believe that this spec is ready for review.
Even though this work does not require a fork, the change is quite significant, and peer-review is critical for the system, so please take a look. Feel free to reach out for questions and comments here or directly over email.
– gleb
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20190925/90bfdb64/attachment.html>

2023-06-07 18:18:25

- reply

📅 Original date posted:2019-05-27
📝 Original message:Hi all,
We are making public our latest work on Erlay, an efficient transaction relay protocol for Bitcoin.
It is available here: https://arxiv.org/abs/1905.10518
The main idea is that instead of announcing every transaction to every peer, announcements are only sent directly over a small number of connections (only 8 outgoing ones). Further relay is achieved by periodically running a set reconciliation protocol over every connection between the sets of withheld announcements in both directions.
The set reconciliation protocol uses error correcting codes to communicate a set of transactions to a peer with an unknown but similar set using bandwidth only equal to the size of the difference and not the size of the sets themselves.
Results: we save half of the bandwidth a node consumes, allow increasing connectivity almost for free, and, as a side effect, better withstand timing attacks.
If outbound peer count were increased to 32, Erlay saves around 75% overall bandwidth compared to the current protocol.
This work uses Minisketch, an efficient library for set reconciliation, which we made public before: github.com/sipa/minisketch.
Some of you may already know about it from discussions with me, Scaling Bitcoin 18, or CoreDev in Tokyo. Our proposal has become more precise since then.
The next step here is to receive more feedback, have a broader discussion, and then write a BIP along with improving reference implementation. We are looking forward to hearing your suggestions or concerns regarding this work.
This protocol is a result of work by myself, Gregory Maxwell, Pieter Wuille, and my supervisors at UBC: Ivan Beschastnikh and Sasha Fedorova.
I would like to thank Tim Ruffing and Ben Woosley for contributions to the write-up, and Blockstream for supporting my work on this protocol.
– gleb
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20190527/b84a5c9f/attachment.html>

2023-06-07 18:12:27

- reply

📅 Original date posted:2018-05-23
📝 Original message:Hi all,
I'm bringing this up again because since the last time (2014) new papers on
network attacks have been published, and in general I think this is
something that has to be done in one or another form.
### Motivation
It has been shown that revealing the topology of the network may increase
the risk of network-related attacks including partitioning/eclipse (and
consequentially double-spending attacks and attacks on mining) and
deanonymization of transactions.
The current join/leave algorithm makes the network fairly static, which
makes it possible to reconstruct the topology by observing events in the
network (for example, see Dandelion threat model [1] or Exploiting
Transaction Accumulation and Double Spends for Topology Inference in
Bitcoin [2]).
Rotation of the peers is an obvious solution, but there are several
questions to answer.
[The idea has also been discussed here: [3] and in the mailing list: [4],
but ended up not well-researched.]
### Issues with rotation
In P2P network, rotation of peers may cause an additional threat, because
it is safer to stick to the existing connections, due to the fact that
having connections to more different peers increases the chances of
connecting to an attacker. Considering the fact that an attacker can
influence your future behavior including what connections you make, this
may worsen the situation.
One important detail to keep in mind here is that a node may act
legitimately, but just to wait when all of the connections are under the
control of an attacker. So a good idea here is to avoid disconnecting the
most reliable peers.
### Reliable peers
There are several metrics that might be used to consider peers to be
reliable:
Which fraction of recent blocks have a particular node relayed to us?
… of recent transactions ... ?
For how long the connection has been maintained?
### Implementation details
Rotation of the outgoing connections only seems to be sufficient yet not
very hard to implement and analyze. In addition, it will cause rotation of
the incoming connections of nodes in the network due to the fact that each
of the outgoing connections is also an incoming connection on the second
side; and due to the scoring mechanism for replacing existing incoming
connections when getting a new one.
Current 8 peers for outgoing connections is an arbitrary number, however,
there is a reason behind keeping a number of outgoing connections low.
Anyway, considering the threat highlighted before it is a good idea to
rotate only a fraction of peers.
Thus, there are 3 values to discuss (N, M, T):
N — Number of persistent peers which are considered to be trustworthy based
on the metrics as per Section 3
M — Number of peers to be rotated every T seconds
The trade-off here is how to add enough entropy while not ending up being
connected to dishonest peers only. It is tunable by modifying {N, M}.
Lower bound for T is a value that won’t significantly delay transaction
propagation because of establishing handshakes (and it will not result in
connecting to dishonest peers only), while the upper bound is a value at
which it would be still infeasible to execute an attack.
Figuring out an optimal set {N, M, T} may be done analytically or by
simulation.
I'd be happy to discuss the way of figuring it out.
### Protocol extensions
It may also be useful to keep track of the previous connections (which were
evicted due to the rotation) and get back to those after a while under
certain conditions.
For example, to decrease a chance of connecting to dishonest peers, a peer
may alternate connecting to the brand new peer with connecting to the old
and fairly reliable peer.
### Transactions de-anonymized
Rotation of the peers itself may increase the chance that particular
Bitcoin address or set of transactions would be linked to a node.
In this case either Dandelion [1] or sending own transactions to a static
set of peers (say first 8 peers) may help.
[1] https://github.com/mablem8/bips/blob/master/bip-dandelion.mediawiki
[2] https://fc18.ifca.ai/bitcoin/papers/bitcoin18-final10.pdf
[3] https://github.com/bitcoin/bitcoin/pull/4723
[4]
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2014-August/006502.html
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/3364ae51/attachment.html>

2023-06-07 18:11:28

- reply

📅 Original date posted:2018-04-04
📝 Original message:Thanks for the links!
Blocksonly is definitely a relevant piece. However, I’m wondering what are the implications, especially at larger scale. For example, transactions processing will be not smooth anymore and will happen every 10 minutes at once. Another question is transaction propagation.
I think what I’ve proposed does not have those implications. Well, propagation is still a concern, but it’s not that extreme. One weakness of my idea is relative complexity comparing to blocksonly.
Another variation of the idea I described might work without INVs at all (then N=1 and transactions are relayed through 1 link only, during the time between blocks) and it would have the same security assumptions as blocksonly.
Your IBLT and BCH-sets proposals sound very promising. I had something like that on mind, but I decided to start with a more conservative protocol.
It looks like sync-relay idea has a lot of interesting questions, I’m excited to follow that research.
On Apr 3, 2018, 12:04 PM -0700, Gregory Maxwell <gmaxwell at gmail.com>, wrote:
> On Mon, Apr 2, 2018 at 10:18 PM, Gleb Naumenko via bitcoin-dev
> <bitcoin-dev at lists.linuxfoundation.org> wrote:
> > Hi all,
> > I have a couple of ideas regarding transaction relay protocol and wanted to
> > share it with and probably get some feedback.
>
>
>
> https://bitcointalk.org/index.php?topic=1377345.0
>
> https://people.xiph.org/~greg/mempool_sync_relay.txt
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180403/44e266d0/attachment.html>

2023-06-07 18:11:27

- reply

📅 Original date posted:2018-04-02
📝 Original message:Hi all,
I have a couple of ideas regarding transaction relay protocol and wanted to share it with and probably get some feedback.
I did some emulation and simulation and found out that around 90% of INV messages sent by public-IP nodes are idle (duplicate), obviously because each node creates 8 connections. I also realized that sending INV messages is a significant part of the overall bandwidth consumed by a public-IP node. At a larger scale, this will result in people not able to run a public-IP node.
My idea is in some sense similar to BIP37 but applied to public-IP nodes. Here I want to emphasize that all the nodes will still receive *all* of the transactions. A new protocol should also keep the same zero-trust, robustness, decentralization guarantees and latency.
Idea: while joining the network, a new node agrees on some filter with each of 8 nodes it connects to. So that NewNode <-> Node_A will be used to relay only a subset of transactions, NewNode <-> Node_B for another subset. This will significantly decrease the redundancy.
To keep the guarantees, I would keep some redundancy (for example, each transaction INV is sent over 2 links).
To make it robust to attacks, I have 2 extensions in my mind:
1. Set reconciliation (for a subset of transactions) with *other* nodes. Getting a bloom filter of a subset of the mempool transactions from Node_B may help to figure out whether Node_A is malicious, very slow, etc.
2. Rotating the filters every N minutes (N < 10)
I can see some issues with latency here, but I believe this problem has a solution.
Feedback is appreciated!
If you want to look at a draft of the proposal — please let me know.
If there were any similar ideas — please let me know.
Best,
Gleb
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180402/a990f1dc/attachment.html>

2023-06-07 18:11:27

- reply

📅 Original date posted:2018-04-03
📝 Original message:Yeah, sure.
> How much bandwidth is consumed by redundant tx INVs currently?
Currently, for an average public-IP node all INVs consume 0.05 Mbps or 540 megabytes per day. This number is based on current ratio public-IP nodes:private-IP nodes and transaction rate. This number is a sum of both incoming and outgoing aspects. Thus redundant INV’s on average consume 0.044 Mbps or 475 megabytes per day.
> What is this as a % of overall bandwidth usage?
This is hard to estimate because overall bandwidth includes helping other nodes to bootstrap from scratch. If we don’t consider this aspect, my very rough estimate, and a short experiment shows that INV’s are around 50% of overall bandwidth (it also depends on different factors like your hardware comparing to other public-IP nodes). I’m going to double-check this number soon.
> How would filtering txs through N=2 links affect network propagation?
Yes, network propagation for a new protocol definitely worth measuring. I’m going to look at it in the near future.
> Do you propose setting filters on inbound peers as well?
This is a good question.
I think some filter may be applied to inbound connections. Theoretically, a symmetrical filter does not make much sense — it might be eventually the same filter for all of the connections except first 8 outgoing ones, so it’s better to use independent filters.
However, I’m not entirely sure it is needed. Filters on inbound peers will reduce a download aspect. It might be much less critical than upload (if we assume that private-IP nodes hear about transactions later because those have much fewer connections). I think this question needs another experiment.
On Apr 3, 2018, 10:45 AM -0700, Jim Posen <jim.posen at gmail.com>, wrote:
> Hey. This idea sounds quite interesting. It'd be helpful to see some more numbers to evaluate it.
>
> - How much bandwidth is consumed by redundant tx INVs currently? What is this as a % of overall bandwidth usage?
> - How would filtering txs through N=2 links affect network propagation? This probably requires simulation to determine.
> - Do you propose setting filters on inbound peers as well?
>
> > On Mon, Apr 2, 2018 at 3:18 PM, Gleb Naumenko via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
> > > Hi all,
> > > I have a couple of ideas regarding transaction relay protocol and wanted to share it with and probably get some feedback.
> > >
> > > I did some emulation and simulation and found out that around 90% of INV messages sent by public-IP nodes are idle (duplicate), obviously because each node creates 8 connections. I also realized that sending INV messages is a significant part of the overall bandwidth consumed by a public-IP node. At a larger scale, this will result in people not able to run a public-IP node.
> > >
> > > My idea is in some sense similar to BIP37 but applied to public-IP nodes. Here I want to emphasize that all the nodes will still receive *all* of the transactions. A new protocol should also keep the same zero-trust, robustness, decentralization guarantees and latency.
> > >
> > > Idea: while joining the network, a new node agrees on some filter with each of 8 nodes it connects to. So that NewNode <-> Node_A will be used to relay only a subset of transactions, NewNode <-> Node_B for another subset. This will significantly decrease the redundancy.
> > >
> > > To keep the guarantees, I would keep some redundancy (for example, each transaction INV is sent over 2 links).
> > >
> > > To make it robust to attacks, I have 2 extensions in my mind:
> > > 1. Set reconciliation (for a subset of transactions) with *other* nodes. Getting a bloom filter of a subset of the mempool transactions from Node_B may help to figure out whether Node_A is malicious, very slow, etc.
> > > 2. Rotating the filters every N minutes (N < 10)
> > >
> > > I can see some issues with latency here, but I believe this problem has a solution.
> > >
> > > Feedback is appreciated!
> > >
> > > If you want to look at a draft of the proposal — please let me know.
> > > If there were any similar ideas — please let me know.
> > >
> > > Best,
> > > Gleb
> > >
> > >
> > > _______________________________________________
> > > 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/20180403/91b04bda/attachment.html>