Jim Posen [ARCHIVE]

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

Public Key

npub1ncnj8arudstdxzfhxk7k4nwgkrw3hyw8sgt0wqqmm5hh2c4knmgs2lqt2n

Profile Code

nprofile1qqsfufer737xc9knpymnt0t2ehytphgmj8rcy9hhqqda6tm4v2mfa5gju7j25

Author Public Key

npub1ncnj8arudstdxzfhxk7k4nwgkrw3hyw8sgt0wqqmm5hh2c4knmgs2lqt2n

Show more details

Last Notes

2023-06-09 12:52:18

- reply

📅 Original date posted:2018-11-08
📝 Original message:
Thanks for proposing this! I think it is absolutely one of the biggest
onboarding/usability challenges for many use cases.
My first thought is that like ZmnSCPxj mentioned, the person offering
liquidity can simply close the channel. So if I'm charging for liquidity,
I'd actually want to charge for the amount (in mSAT/BTC) times time. So
like 1 mSAT per satoshi of bandwidth per hour or something like that. I
don't think there's a perfect way of enforcing this at the protocol layer,
but maybe you could lock up the fees in channel reserve which decreases
over time and gets donated to miners on an early close?
Instead of a flat payment for liquidity, I've considered in the past a
model where you pre-pay on fees. So if I'm a large merchant and I expect to
be receiving lots of volume in payments, it is totally rational for you to
put up liquidity opening a channel to me because you will earn fees on
payments routed to me through that channel. So what I could do to convince
you is to say, "I expect if you open a 1 BTC channel to me, you will earn
at least 10 mSAT per minute in routing fees. And if you don't I'll cover
the difference." So every minute, I'll pay you 10 mSAT up front, then for
all HTLCs that come through the channel to me up to that limit, you'll
forward the fees onto me as reimbursement. I don't think this protocol is
any less vulnerable to attacks, but perhaps aligns incentives better?
My other concern with this sort of proposal is that it makes it easier to
perform HTLC withholding/loop attacks, which are executed by the receiving
end of a circuit. Currently on the network, there's a nice built-in
protection that it's not obvious how to convince victim to open a channel
to you. This is probably something that should get dealt with separately,
but part of me doubts that it'll be possible to create a liquidity market
without factoring in reputation.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20181107/44263e78/attachment.html>

2023-06-09 12:51:51

- reply

📅 Original date posted:2018-10-20
📝 Original message:
Instead of leaving an extra output for CPFP, is it not sufficient to just
sign all inputs with ANYONECANPAY and expect the sender to make an exact
output for the fees input? It would require an extra tx assuming they don't
already have a properly sized UTXO handy (which they may!), but I believe
CPFP would require that as well. Am I missing something?
I'm a fan of the symmetric delays because it simplifies the game theory
analysis, but I don't think the delays need to be the same for both
participants (max of `to_self_delay` for both sides), just that the delay
is applied equally regardless of who publishes the commitment tx. Like your
`to_self_delay` can be what I specify and vice versa, what's the reason for
taking the max?
-jimpo
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20181020/2771eeef/attachment.html>

2023-06-09 12:50:41

- reply

📅 Original date posted:2018-05-08
📝 Original message:
Benjamin,
I don't agree that quantum resistance should be a blocker to deployment of
scriptless scripts on lightning because 1) it is a layer-2 solution and 2)
it already critically depends on the security of DL.
There are arguments against making certain protocol changes to the base
Bitcoin blockchain for the reason that they may not be quantum resistant.
The most notable is Confidential Transactions. There reason is that the
worst case attack is much worse: an attacker could print money freely and
without detection. In Bitcoin today, a DL break would compromise funds in
any addresses for which the pubkey has been revealed and it's not even
clear what to do about the remaining funds on chain. Compromising the
fundamental security of the blockchain is a valid cause for concern.
In the case of Lightning, the attack scenario on scriptless scripts is that
a peer is going to use a quantum computer to steal all live payments routed
through them from their senders before they get to the recipient. This
would be bad, but not catastrophic, and once it is recognized that the
attack is possible, insecure channels could be closed.
But furthermore, an attacker with a quantum computer could just steal the
multisig funding output directly instead of attacking scriptless scripts.
So additional protocol changes relying on the DL assumption don't bother me
in the least.
On Tue, May 8, 2018, 6:32 AM Benjamin Mord <ben at mord.io> wrote:
>
> Sorry, I do not wish to spam the list, but I need to correct a rather
> serious error in my last email. We must never call something
> "post-quantum", absent mathematical proof. (And good luck with that.) I
> apologise for my mistake in doing so myself.
>
> I should not even refer to lattice based cryptography as a post-quantum
> algorithm, I should at best call it a Shor's algorithm-resistant scheme. At
> least, it is not (yet) known how Shor's algorithm could be used to break
> it. Not in public circles, anyhow.
>
> A cursory glance at the history of cryptanalysis shows that primitives
> generally have finite life, which makes it odd that systems seldom use
> redundant primitives, and seldom provide for their rapid and safe swap. A
> system whose entire security rests on nothing but cryptography, ought to
> take particular care! The spectre of quantum computers may render the
> finite life of certain primitives more salient than others, but we must not
> suppose that, absent Shor's algorithm, there would be no need to plan for
> cryptographic failures. The question is not if, but when, Bitcoin and
> lightning will contend with broken primitives, whether due to classical or
> quantum cryptanalysis. Likely, both will come into play at various times,
> and one must plan accordingly.
>
> On Tue, May 8, 2018, 9:09 AM Benjamin Mord <ben at mord.io> wrote:
>
>>
>> That would be awesome. Do you have a reference?
>>
>> As pertains to the whole of asymmetric cryptography, I believe there are
>> not a variety of post quantum schemes, there is only one*: lattice-based
>> cryptography. (Which scares me, because it is not all that different from
>> the others.)
>>
>> (* Actually, in contexts where time can be used for asymmetry, as in
>> TESLA, we can then use hash functions to create something like asymmetric
>> signatures as well. But the functional context has to be compatible with
>> delayed verification.)
>>
>> (But I do not mean to focus exclusively on Schor's algorithm, the history
>> of even pre-quantum cryptanalysis shows that primitives tend to have finite
>> lifespan. Redundancy of any sort of good, even when not focused
>> specifically on quantum risks.)
>>
>> On Tue, May 8, 2018, 8:58 AM Greg Sanders <gsanders87 at gmail.com> wrote:
>>
>>> From what I understand talking to folks, the linear properties of these
>>> signature tricks are maintained under a number of post-quantum schemes.
>>>
>>> On Tue, May 8, 2018 at 8:44 AM, Benjamin Mord <ben at mord.family> wrote:
>>>
>>>>
>>>> If I'm not mistaken, the scriptless scripts concept (as currently
>>>> formulated) falls to Schor's algorithm, and at present there is no
>>>> alternative implementation of the concept to fall back on. Correct? Lest we
>>>> build a house of cards, I'd strongly urge everyone to not depend on
>>>> functional concepts whose underlying cryptographic primitives cannot be
>>>> swapped in an emergency.
>>>>
>>>> Sure, we use ecdsa for example (which is also vulnerable to Schor's
>>>> algorithm), but in contrast to scriptless scripts we have a variety of
>>>> backup primitives at our disposal that fulfill the same functional
>>>> objective.
>>>>
>>>> If scriptless scripts are found possible under lattice-based
>>>> cryptography for example, that would be something I suppose. The functional
>>>> concept of scriptless scripts is indeed very awesome - we just need to add
>>>> some cryptographic conservatism before we build on it.
>>>>
>>>>
>>>> _______________________________________________
>>>> Lightning-dev mailing list
>>>> Lightning-dev at lists.linuxfoundation.org
>>>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>>>>
>>>>
>>> _______________________________________________
> 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/20180508/f3ebdf1a/attachment.html>

2023-06-09 12:50:29

- reply

📅 Original date posted:2018-05-18
📝 Original message:
Yes Rusty, you are correct that an attacker still gets leverage on their
ability to destroy reputation unless the loss rates increase exponentially.
And I agree that would be a very steep increase, serving do decrease
circuit lengths dramatically. The reasoning for the linear increase in
reputation loss comes from viewing reputation loss as compensation for
time-value lost in locked HTLCs. In a sense, every node pays in reputation
for all of the time-value locked in HTLCs upstream from them in proportion
to the value assigned to it by the owners of the funds.
I'm not sure whether this would be an acceptable way of pricing payment
delays, though I do think it is important to make attackers pay for the
resources they are wasting on the network in some form.
On Fri, May 18, 2018 at 4:38 PM, ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> Good morning Rusty,
>
>
> > Also, you talked about reputation_loss_rate as being a private per-node
> >
> > thing, and being an explicit thing in the HTLC. I'm ignoring the
> >
> > former, and assuming the latter.
>
> Reputation (the score) is a private per-node thing, while the
> `reputation_loss_rate` is explicit in the HTLC.
>
> I am uncertain how that changes your analysis, though. In a line network
> like you showed, the reputation "bins" are Node1->Node2 and Node2->Node1
> and so on. It may be more useful to think of the reputation bins as
> assigned to half-chans than to nodes.
>
> So the initial Mallory3->Node18->Mallory2 gives high reputation to
> half-chans Node18->Mallory3 and Node18->Mallory2, then sacrifices the
> Node18->Mallory3 reputation to destroy the NodeN -> NodeN+1 and
> NodeN+1->NodeN reputations.
>
> Along that line, reputation lost is higher as N increases. Graphing
> reputation lost along that line, we form a triangle, and the area of the
> triangle is the total reputation destroyed. Only the length of one edge of
> the triangle is what is lost by the Node18->Mallory3 reputation score. So
> yes, it seems you are correct here.
>
> Regards,
> ZmnSCPxj
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180518/f341c9c4/attachment.html>

2023-06-09 12:50:28

- reply

📅 Original date posted:2018-05-15
📝 Original message:
>
> This can still be manipulated if Rusty1 opens a direct channel to Jim.
> Then Rusty1 can route payments Rusty1->Jim->Rusty2 that succeed quickly,
> then route payments Rusty1->ZmnSCPxj->Jim->Rusty2 that stall. Thus Rusty2
> can have the Jim->Rusty2 reputation boosted, while alternating with
> reputation losses that make ZmnSCPxj->Jim reputation go down. Since local
> reputation is used, ZmnSCPxj and Jim will not talk to each other about how
> Rusty2 seems to stall when not routing a payment from Rusty1. Rusty1 can
> now manipulate the reputation view of ZmnSCPxj and Jim of each other while
> keeping Rusty2 reputation somewhat high.
>
Yes, you are correct that in scenarios like this an attacker can pay to
degrade the reputation of one of its peers (or even nodes further away).
The key point is that doing so should be costly to the attacker because
they must pay the victim node to continue making itself vulnerable to
payment delays. But if the node is getting compensated, is that really an
attack then? This system is designed with the assumption that the best way
to defend an anonymous/decentralized network that allows sybils is by
pricing resource utilization appropriately. In a similar way, the Bitcoin
blockchain is "vulnerable" to spam attacks in the sense that attackers can
pay to fill up block space.
> As mentioned, the CLTV total leaks information on how far the payee is. I
> might decide to keep track of a reputation score, not of the local peers I
> have, but on the entire network. If the CLTV total at my outgoing is high,
> then if the outgoing HTLC takes a long time to respond, I will distribute a
> small reputation loss to a large number of nodes that are accessible from
> the outgoing channel; if the CLTV total at my outgoing is low, I will
> distribute a large reputation loss to a small number of nodes that are
> accessible from the outgoing channel. I now have the incentive to make
> this estimation even more accurate in the future.
>
One could do this today. I'd even argue that they are incentivized to
already as a protection against loop attacks/payment delays. But it's
likely a pretty ineffective strategy depending on the number of channels
that the possible downstream hops have open.
Please describe the below:
>
> 1. Behavior if payment succeeds after T time.
> 2. Behavior if payment fails after T time.
>
> It seems you only described "Behavior if payment succeeds after T time".
>
Ah, sorry if I didn't make that clear. The reputation is increased in the
case of successful payments by the fee collected. The reputation is
decreased on the downstream peer proportional to time T *regardless* of
whether the payment succeeds or fails. If a payment succeeds quickly, the
increase should outweigh the decrease, but if the payment succeeds after a
long time, the change in reputation may be net negative. If the payment
fails, the upstream peer's reputation does not change and the downstream
peer's reputation always decreases proportional to time T.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180515/755f6eaf/attachment-0001.html>

2023-06-09 12:50:27

- reply

📅 Original date posted:2018-05-15
📝 Original message:
>
> You're forgetting the failure cases, where now I can profit.
>
> If I disconnect from another node, I now have a disincentive to tell
> others. At the moment we send an update disabling the channel (though
> we should give a few seconds for reconnect first, but whatever).
>
> Similarly, the rewards aren't proportional: being cheaper than other
> routes gets you all the traffic, but now you profit even if you can't
> service the payments. In fact, once a channel becomes hard to use (low
> capacity, transient disconnect, whatever), I *should* advertize it as
> cheaper route than anyone else: free money!
>
> I'm sure there are other ways to game it, but the underlying reason is
> clear: it misaligns user and node incentives.
If the system is sufficiently decentralized, managing to cheat everyone
> once is very profitable though.
>
I still don't agree with the conclusion.
What are the incentives currently for a node to advertise disabled
channels? Firstly, it reduces computational effort of performing an
unnecessary channel update. The main incentive though is that it is the
recommended spec compliant behavior, and makes the link appear more
reliable to the sender. I think this has to be analyzed as a repeated game,
where senders will prefer links that not only advertise lower fees, but
have a history of being reliable (or at least don't have a history of being
unreliable). So with a fee of 0 on failed payments, we think that there's
probably sufficient reason for nodes to advertise when channels are
disabled. I'll grant, obviously, that if that there is high fee on failed
payments that it would create incentive problems, but not if the
unconditional fee is low enough. Note also the unconditional fee is also
visible to senders, who will choose not to route through such links for
this exact reason. So your example of a node advertising cheap fees on
disabled links, it would only make sense to lower the success-conditional
fee, not the unconditional fee. Ultimately, I think this will reach an
equilibrium assuming senders have good route selection algorithms.
Now, that said, if this unconditional fee were the only (or even main)
protection against loop attacks, it would probably require them to be so
high as to create incentive problems. I am proposing the unconditional fee
as a spam fee to punish senders who just send a bunch of failing payments
in order to collect routing information, and put load on the network in the
process for no good reason. With this as the purpose, I think this
unconditional spam fee can be low enough to avoid the issues you raise.
One of my beliefs in structuring incentives it that it's far more
acceptable for senders to get cheated by nodes they route through than for
routers to be attacked. The reason is that senders collect a lot more
information in failure cases and can avoid repeated occurrences by
selecting routes differently. Routers, on the other hand, have far more
limited information and choices and their operation is critical to the
efficiency and decentralization of the system, so they should be protected
by the protocol to a greater degree.
> But I can make you look like a delaying node whenever I want. The only
> way to ensure that I lose more reputation than you do is to leak
> information about route length for *everyone*. And even then, it's just
> a matter of numbers. I can make successful payments to myself through
> the same peers (but not you!) to stay above their threshold so my
> reputation is intact.
>
> So it's basically a question of how expensive is it for me to throw you
> off the network? You have to tune that number carefully.
>
Remember, reputation is local to each node, so the only way you can raise
your reputation with me is by participating in successful circuits *with
me*. If you route successful payments on circuits with other peers, you may
raise your reputation with them, but will do nothing to convince me to send
more payments through you. So it is not true that you can make me look like
a delaying node whenever you want; after a few bad interactions, I will
stop routing through you until you participate in enough successful
payments *with me* as the downstream to earn back your reputation.
I agree this number needs to be tuned carefully, but ideally this (the
reputation rate loss) is something that can be tuned individually by
routers according to their risk tolerance and history of attacks on the
network. I think it's far preferable to have a number that can be tuned in
the face of DoS attacks than being caught with no protection whatsoever.
But we're busy trying to remove all the methods of deanonymizing the
> network, and you seem to be adding a new one, *and* providing an
> incentive to deanonymize.
>
> Yes, which is why we have mitigations in place (which are still probably
> insufficient). I really don't want to add another vector.
>
This gets to the heart of the tradeoff between network efficiency and
privacy. I admit that my proposal sacrifices on privacy, and I personally
find it acceptable given the added protection against DoS attacks, but I
understand the counterargument as well.
One additional thing to consider, though, is that if DoS attacks are
problematic and there is no protection, many nodes may stop routing
payments entirely. Onion routing through a network with very few possible
circuits certainly is less private than revealing additional circuit
information on a decentralized routing network.
> So now I'll try to deanonymize all payments so I can determine this.
> Those who do this best will be rewarded, and those who don't try will be
> knocked off the network, probably by those who can!
>
I'm not following, how are you deanonymizing payments? Having more
information about downstream hops can help one make better routing
decisions, but if the reputation system works properly, you should only
need to care about the reputation of the next hop.
> So I'd like to see a real design of the reputation system. If it's
> practical (which is a significant hurdle), we then need to carefully
> evaluate whether we're creating significant disincentives to
> neighbourliness.
>
I tried to mostly describe the design in the first email, but it's kind of
disorganized. I'll try to sketch it out here more succinctly.
Each node has a local configuration of its "reputation loss rate" per
channel in units of Hz. This configured rate is not explicitly advertised
to peers. Each update_add_htlc has an additional field the "reputation loss
rate" in units of satoshis per second, calculated as the reputation loss
rate of the upstream HTLC plus the local reputation loss rate times the
offered HTLC value. This value can be obfuscated somewhat by the origin of
the payment and at each hop with some amount of noise, subject to the
concerns raised in my discussion with ZmnSCPxj. When forwarding an HTLC,
the upstream hop measures the elapsed time between delivery of a commitment
signature on the add and receipt of the fail/update.
For each peer node, keep a reputation score in units of satoshis. For each
peer, when a payment completes where they are the upstream or downstream
hop, add the amount collected in fees to their reputation score. For each
payment where they are the downstream hop, subtract from their reputation
score the reputation loss rate on the offered HTLC times its elapsed time.
Reputation score is not explicitly shared between peered nodes, but can be
estimated to within differences in elapsed time measurements.
When you receive an HTLC to be forwarded to some downstream node, compare
their current reputation score with the offered reputation loss rate times
10 minutes times the CLTV on the HTLC. If their reputation is sufficient,
forward the HTLC and place a hold on their total reputation for that amount
(so that concurrently forwarded HTLCs can't exceed their reputation
"balance"). New, unknown, peers should get some initial reputation,
presumably greater for channels that one initiates vs channels one receives.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180515/35dedefc/attachment-0001.html>

2023-06-09 12:50:26

- reply

📅 Original date posted:2018-05-10
📝 Original message:
Hmm, I'm not quite following the situation. What do you mean by "directs
normal traffic"? Since the sender constructs the entire circuit, routing
nodes do not get any discretion over which nodes to forward a payment to,
only whether to forward or fail. What an attacker could do is perform a
loop attack and send a payment to another node that they control and delay
the payment on the receiving end. Note that the sending node loses no
reputation, only the receiving node. Since the hops being attacked are the
ones in the middle and they are faithfully enforcing the reputation
protocol, the receiving node's reputation should be penalized properly,
making it unlikely the attack will succeed in a second attempt.
On Thu, May 10, 2018 at 2:56 PM, Chris Gough <christopher.d.gough at gmail.com>
wrote:
> hello, I'm a curious lurker trying to follow this conversation:
>
> On Thu, 10 May 2018, 2:40 pm ZmnSCPxj via Lightning-dev, <
> lightning-dev at lists.linuxfoundation.org> wrote:
>
>>
>> The concern however is that the CLTV already partly leaks the distance
>> from the payee, whereas the reputation-loss-rate leaks distance from the
>> payer. It is often not interesting to know that some entity is getting
>> paid, but it probably far more interesting to know WHO paid WHO, so leaking
>> both distances simultaneously is more than twice as worse as leaking just
>> one distance.
>>
>
> Consider an asymetrically-resourced malevolent node that wants the ability
> to harm a specific small nodes without aquiring a bad reputation (and is
> willing to pay for it). In preparation, this bad boss node directs normal
> traffic to sacrificial nodes they control, while understating the
> reputation-risk (truthfully as it turns out, because they have out of band
> influence over the node). When the time comes, the sacrificial node
> inflicts delay on the victim node and they both suffer, while the boss
> keeps her nose clean.
>
> Is it the case that understating risk of legitimate traffic from boss node
> to sacrificial node effectively allows transfer of reputation to the
> sacrificial node in preparation for attack, while at the same time
> obscuring their association?
>
> Chris Gough
>
>>
> _______________________________________________
> 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/20180510/e6ddf135/attachment.html>

2023-06-09 12:50:25

- reply

📅 Original date posted:2018-05-09
📝 Original message:
One more point in terms of information leakage is that noise can be added
to the "this is the rate that you'll lose reputation at" field to help
obfuscate the number of upstream hops. I proposed setting it to "this is
the upstream rate that I'm losing reputation at" + downstream HTLC value,
but a node can decide to add noise. If they make it too low however,
there's a risk of insufficiently punishing bad nodes and if they make it
too high, there's a heightened risk that the payment fails because the
downstream reputation is insufficient along the route.
This is why I say it's kind of symmetric to the CLTV value: if the delta is
too low, there's risk of loss of funds, if the delta is too high, someone
might decide to fail the payment instead of taking the delay risk.
On Wed, May 9, 2018 at 10:23 AM, Jim Posen <jim.posen at gmail.com> wrote:
> Thanks for the thoughtful responses.
>
> > You missed the vital detail: that you must prove channel closure if you
> > can't unpeel the onion further. That *will* hit an unresponsive party
> > with a penalty.
>
> Ah, that is a good point. I still find the proposal overall worryingly
> complex in terms of communication overhead, time it takes to prove channel
> closure, all of your points in [1], [2], [3], etc. Furthermore, this
> mandates that immediate channel closure is the only allowed reaction to a
> party delaying an HTLC for a time period above a threshold -- the node
> reputation approach gives more discretion to the preceding hop.
> Deobfuscating the route may turn out to be the right option, but I think
> the reputation system has certain advantages over this.
>
> > The models we tried in Milan all created an incentive to fail payments,
> > which is a non-starter.
>
> Do you mind elaborating or summarizing the reasons? The way I'm analyzing
> it, even if there's a nominal spam fee paid to routing nodes that fail
> payments, as long as it's low enough (say 2-5% for arguments sake), the
> nodes still have more to gain by forwarding the payment and earning the
> full fee on a completed payment, and possibly the reputation boost
> associated with completing a payment if that system was in effect.
> Moreover, a node that constantly fails payments will be blacklisted by the
> sender eventually and stop receiving HTLCs from them at all. Overall, I
> don't think this is a profitable strategy. Furthermore, I think it works
> quite well in combination with the reputation system.
>
> > This seems like we'd need some serious evaluation to show that this
> > works, because the risks are very high.
>
> I agree that it needs to be evaluated. I may start working on some network
> simulations to test various DOS mitigation strategies.
>
> > I can destroy your node's reputation by routing crap through you; even
> > if it costs me marginaly more reputation than it does you, that just
> > means that the largest players can force failure upon smaller players,
> > centralizing the network. And I think trying to ensure that it costs me
> > more reputation than the sum of downstream reputation loss leaks too
> > much information
>
> I will add to ZmnSCPxj's response, which is mostly on point. The key here
> is that the only way to lose significant reputation is to delay a payment
> yourself or forward to a malicious downstream that delays -- neither of
> these can be forced by the sender alone. This amounts to a system where you
> are on the hook for any malicious behavior of your downstream peers, which
> is why you must keep a reputation score for each which they earn over time.
> This should keep all links in the network high quality and quickly
> disconnect off delaying nodes if the incentives are right.
>
> While I agree that a lot of reputation is leaked by aggregating the losses
> along the route, this serves exactly to prevent large nodes with high
> reputation from ruining links elsewhere. There are two things a node
> looking to cause reputation loss could do. 1) Identify a node (not itself)
> it thinks will delay a payment and send to them. This locks up funds on
> their behalf, but is actually good behavior because it identifies a faulty
> node and rightfully forces a loss in their reputation, eventually resulting
> in them being booted from the network. Everyone upstream loses some
> reputation for having connectivity to them, but less because of the loss
> aggregation along the route. 2) Delay a payment oneself and force upstream
> reputation loss. This is why I think it's important that the reputation
> loss aggregate so that the malicious party loses the most.
>
> As for the amount of information leaked, yes, it helps determine the
> number of upstream hops in a route. However, the CLTV values help determine
> the number of downstream hops in a route in exactly the same way. I see
> these as symmetric in a sense.
>
> To address ZmnSCPxj's point:
>
> > But it also looks more and more like a policy of "just
> `update_htlc_fail`" keeps our reputation high: indeed never accepting a
> forwarding attempt would ensure reputation.
> > However, earning via fees should help provide incentive against "Just
> `update_htlc_fail`" always. If the goal is "how do I earn money fastest"
> then there is some optimal threshhold > of risk-of-reputation-loss vs.
> fee-earnings-if-I-forward that is unlikely to be near the "Just fail it"
> spectrum, but somewhere in between. We hope.
>
> This is exactly the question that your local view of peer reputations
> helps solve: are the potential fees here worth the risk of forwarding this
> payment to this downstream? If their reputation is high, then you will want
> to forward because you think there's a low chance of you incurring
> reputation loss. If their reputation is low and the HTLC value is too high,
> you will fail it. So I disagree that "just `update_htlc_fail`" is an
> optimal strategy. Consider as well that all fees you earn on successful
> payments are profit to you as well as a reputation boost in the view of
> both of your peers. So in order to earn reputation, you have to forward
> payments. The key is not forwarding through malicious peers.
>
> -jimpo
>
> On Wed, May 9, 2018 at 12:31 AM, ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
>
>> Good morning Rusty, Jim, and list,
>>
>> > I can destroy your node's reputation by routing crap through you; even
>> >
>> > if it costs me marginaly more reputation than it does you, that just
>> >
>> > means that the largest players can force failure upon smaller players,
>> >
>> > centralizing the network.
>>
>> My understanding of the proposal was that reputation loss would occur
>> only if the reply (`update_htlc_fail` or `update_htlc_success`) is delayed;
>> this means that for you to force me to lose reputation, you need to somehow
>> make me delay my reply. In particular if you do simple things like give me
>> an invalid onion, or make me forward to a payee who does not know the
>> preimage, I do not lose reputation by replying very quickly with an
>> `update_htlc_fail`.
>>
>> Of course, a large player could force reputation loss by delaying reply
>> when they receive, and having patsy nodes route to them. So for instance
>> if it is Jim -> ZmnSCPxj -> Rusty, and Rusty activates the
>> Blockstream-takes-over-the-world Apocalypse program, the Rusty node
>> would then delay for a long time before replying, which makes my reputation
>> suffer. But it also makes Rusty reputation suffer even more and my
>> reaction would be that, the next time Jim hands me an HTLC that forwards to
>> Rusty, I would instead quickly `update_htlc_fail` back to Jim (which does
>> not lose me significant reputation due to my quick response) than risk
>> forwarding it to you, since you have a reputation for being slow and
>> unresponsive.
>>
>> Indeed, another aspect of Jim proposal is that it is extremely local: if
>> Jim has no channel to Rusty, then Jim has no opinion about Rusty, only
>> about ZmnSCPxj. However, ZmnSCPxj does have an opinion about Rusty, as
>> ZmnSCPxj has channel with Rusty. If I suffer too much reputation loss due
>> to Rusty, my opinion of Rusty drops even faster, and I decide to
>> `update_htlc_fail` in order to prevent Jim opinion of me from dropping too
>> much that Jim decides not to forward to me (if I have other channels with
>> more reasonable nodes).
>>
>> But it also looks more and more like a policy of "just
>> `update_htlc_fail`" keeps our reputation high: indeed never accepting a
>> forwarding attempt would ensure reputation.
>>
>> However, earning via fees should help provide incentive against "Just
>> `update_htlc_fail`" always. If the goal is "how do I earn money fastest"
>> then there is some optimal threshhold of risk-of-reputation-loss vs.
>> fee-earnings-if-I-forward that is unlikely to be near the "Just fail it"
>> spectrum, but somewhere in between. We hope.
>>
>> > And I think trying to ensure that it costs me
>> >
>> > more reputation than the sum of downstream reputation loss leaks too
>> >
>> > much information
>>
>> Yes, this is a major drawback of the proposal. The rate at which the
>> sender of the HTLC threatens me with reputation loss lets me estimate my
>> distance from the ultimate sender of the funds.
>>
>> Regards,
>> ZmnSCPxj
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180509/1894d9e0/attachment-0001.html>

2023-06-09 12:50:24

- reply

📅 Original date posted:2018-05-09
📝 Original message:
Thanks for the thoughtful responses.
> You missed the vital detail: that you must prove channel closure if you
> can't unpeel the onion further. That *will* hit an unresponsive party
> with a penalty.
Ah, that is a good point. I still find the proposal overall worryingly
complex in terms of communication overhead, time it takes to prove channel
closure, all of your points in [1], [2], [3], etc. Furthermore, this
mandates that immediate channel closure is the only allowed reaction to a
party delaying an HTLC for a time period above a threshold -- the node
reputation approach gives more discretion to the preceding hop.
Deobfuscating the route may turn out to be the right option, but I think
the reputation system has certain advantages over this.
> The models we tried in Milan all created an incentive to fail payments,
> which is a non-starter.
Do you mind elaborating or summarizing the reasons? The way I'm analyzing
it, even if there's a nominal spam fee paid to routing nodes that fail
payments, as long as it's low enough (say 2-5% for arguments sake), the
nodes still have more to gain by forwarding the payment and earning the
full fee on a completed payment, and possibly the reputation boost
associated with completing a payment if that system was in effect.
Moreover, a node that constantly fails payments will be blacklisted by the
sender eventually and stop receiving HTLCs from them at all. Overall, I
don't think this is a profitable strategy. Furthermore, I think it works
quite well in combination with the reputation system.
> This seems like we'd need some serious evaluation to show that this
> works, because the risks are very high.
I agree that it needs to be evaluated. I may start working on some network
simulations to test various DOS mitigation strategies.
> I can destroy your node's reputation by routing crap through you; even
> if it costs me marginaly more reputation than it does you, that just
> means that the largest players can force failure upon smaller players,
> centralizing the network. And I think trying to ensure that it costs me
> more reputation than the sum of downstream reputation loss leaks too
> much information
I will add to ZmnSCPxj's response, which is mostly on point. The key here
is that the only way to lose significant reputation is to delay a payment
yourself or forward to a malicious downstream that delays -- neither of
these can be forced by the sender alone. This amounts to a system where you
are on the hook for any malicious behavior of your downstream peers, which
is why you must keep a reputation score for each which they earn over time.
This should keep all links in the network high quality and quickly
disconnect off delaying nodes if the incentives are right.
While I agree that a lot of reputation is leaked by aggregating the losses
along the route, this serves exactly to prevent large nodes with high
reputation from ruining links elsewhere. There are two things a node
looking to cause reputation loss could do. 1) Identify a node (not itself)
it thinks will delay a payment and send to them. This locks up funds on
their behalf, but is actually good behavior because it identifies a faulty
node and rightfully forces a loss in their reputation, eventually resulting
in them being booted from the network. Everyone upstream loses some
reputation for having connectivity to them, but less because of the loss
aggregation along the route. 2) Delay a payment oneself and force upstream
reputation loss. This is why I think it's important that the reputation
loss aggregate so that the malicious party loses the most.
As for the amount of information leaked, yes, it helps determine the number
of upstream hops in a route. However, the CLTV values help determine the
number of downstream hops in a route in exactly the same way. I see these
as symmetric in a sense.
To address ZmnSCPxj's point:
> But it also looks more and more like a policy of "just
`update_htlc_fail`" keeps our reputation high: indeed never accepting a
forwarding attempt would ensure reputation.
> However, earning via fees should help provide incentive against "Just
`update_htlc_fail`" always. If the goal is "how do I earn money fastest"
then there is some optimal threshhold > of risk-of-reputation-loss vs.
fee-earnings-if-I-forward that is unlikely to be near the "Just fail it"
spectrum, but somewhere in between. We hope.
This is exactly the question that your local view of peer reputations helps
solve: are the potential fees here worth the risk of forwarding this
payment to this downstream? If their reputation is high, then you will want
to forward because you think there's a low chance of you incurring
reputation loss. If their reputation is low and the HTLC value is too high,
you will fail it. So I disagree that "just `update_htlc_fail`" is an
optimal strategy. Consider as well that all fees you earn on successful
payments are profit to you as well as a reputation boost in the view of
both of your peers. So in order to earn reputation, you have to forward
payments. The key is not forwarding through malicious peers.
-jimpo
On Wed, May 9, 2018 at 12:31 AM, ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> Good morning Rusty, Jim, and list,
>
> > I can destroy your node's reputation by routing crap through you; even
> >
> > if it costs me marginaly more reputation than it does you, that just
> >
> > means that the largest players can force failure upon smaller players,
> >
> > centralizing the network.
>
> My understanding of the proposal was that reputation loss would occur only
> if the reply (`update_htlc_fail` or `update_htlc_success`) is delayed; this
> means that for you to force me to lose reputation, you need to somehow make
> me delay my reply. In particular if you do simple things like give me an
> invalid onion, or make me forward to a payee who does not know the
> preimage, I do not lose reputation by replying very quickly with an
> `update_htlc_fail`.
>
> Of course, a large player could force reputation loss by delaying reply
> when they receive, and having patsy nodes route to them. So for instance
> if it is Jim -> ZmnSCPxj -> Rusty, and Rusty activates the
> Blockstream-takes-over-the-world Apocalypse program, the Rusty node would
> then delay for a long time before replying, which makes my reputation
> suffer. But it also makes Rusty reputation suffer even more and my
> reaction would be that, the next time Jim hands me an HTLC that forwards to
> Rusty, I would instead quickly `update_htlc_fail` back to Jim (which does
> not lose me significant reputation due to my quick response) than risk
> forwarding it to you, since you have a reputation for being slow and
> unresponsive.
>
> Indeed, another aspect of Jim proposal is that it is extremely local: if
> Jim has no channel to Rusty, then Jim has no opinion about Rusty, only
> about ZmnSCPxj. However, ZmnSCPxj does have an opinion about Rusty, as
> ZmnSCPxj has channel with Rusty. If I suffer too much reputation loss due
> to Rusty, my opinion of Rusty drops even faster, and I decide to
> `update_htlc_fail` in order to prevent Jim opinion of me from dropping too
> much that Jim decides not to forward to me (if I have other channels with
> more reasonable nodes).
>
> But it also looks more and more like a policy of "just `update_htlc_fail`"
> keeps our reputation high: indeed never accepting a forwarding attempt
> would ensure reputation.
>
> However, earning via fees should help provide incentive against "Just
> `update_htlc_fail`" always. If the goal is "how do I earn money fastest"
> then there is some optimal threshhold of risk-of-reputation-loss vs.
> fee-earnings-if-I-forward that is unlikely to be near the "Just fail it"
> spectrum, but somewhere in between. We hope.
>
> > And I think trying to ensure that it costs me
> >
> > more reputation than the sum of downstream reputation loss leaks too
> >
> > much information
>
> Yes, this is a major drawback of the proposal. The rate at which the
> sender of the HTLC threatens me with reputation loss lets me estimate my
> distance from the ultimate sender of the funds.
>
> Regards,
> ZmnSCPxj
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180509/1cec1f17/attachment-0001.html>

2023-06-09 12:50:23

- reply

📅 Original date posted:2018-05-02
📝 Original message:
I have been thinking a lot lately about attacks on lightning routing nodes,
the worst of which is the so-called Loop Attack [1]. See the mailing list
thread for more details, but the basic idea is that a sender and receiver
collude to create a long circuit and refuse to settle or fail the HTLC at
the end until the last possible moment. The attack is particularly
insidious for a few reasons. Firstly, an attack on a multi-hop route gives
the attacker leverage, so that their funds locked in one channel cause
funds to be locked up in every channel on the route. Second, the onion
routing makes it difficult to attribute blame to a single node and defend
against a repeated attack.
First, I'll note that the case where a sender and recipient collude is a
more active variant on an attack that any node in a route can perform. Even
if a node does not initiate the payment, it can just accept offered HTLCs
in the route, not forward them, and wait until the offered HTLC almost
expires before failing. As noted above, the prior node in the route cannot
determine whether the attacking node is at fault or one downstream from it.
Even the sender may not be able to determine where in the route the payment
failed because of the issue where the obfuscated error reason is not MAC'ed
on every hop.
There are two directions of solutions I have heard: 1) protocol support for
decrypting the onion route if the HTLC is kept in-flight for too long 2)
requiring fees even if the payment fails as a cost to the attacker 3) some
sort of reputation system for nodes.
Option 1 I'm afraid may be quite complex. Say this mechanism kicks in and
all nodes in the circuit deobfuscate the route and are able to see the
delays at each hop. The outcome we hope for is that there is one node
clearly to blame and the prior hop in the route fails all channels with
them. However, the attacker can of course control multiple successive hops
in the route, one that looks innocent in front of one that looks guilty,
then keep the channel alive and try again. So then all nodes need to keep a
record of the full circuits and iteratively shift blame up the chain if bad
HTLCs keep going through those channels.
Option 2 is also problematic because it only protects against the case
where the sender is colluding with the receiver, and not where a routing
node is opportunistically delaying payments. This would, however, likely be
successful against nodes being annoying and sending tons of payments with
randomly generated payment hashes in order to "ping" a circuit.
Option 3 has become my preferred solution. The idea is that that for each
node that one has channels with, it only forwards payments through them if
they have a good history, otherwise it fails the payment. Notably, we
ignore whether the downstream hop is directly responsible for delaying a
payment or whether they are simply willing to forward to another node that
is intentionally delaying -- both should be considered bad behavior. In my
opinion, this type of solution fits best into the Lightning model of
independent, linked channels where each node has private contracts with its
direct peers. It also is the simplest in the context of onion routing
because if you are offered an HTLC to route, the only decision you can make
is whether to forward it or fail it based on the amount, previous hop, and
next hop. When I refer to "reputation" hereafter, I do not mean a global
reputation that is gossiped about -- just a local view of a peer's history.
For a Sybil-resistant reputation system, we can use money as a way of
measuring reputation. Fees collected through routing payments across
channels raise the reputation of the channel peer. You lose reputation by
accepting an HTLC and not failing or fulfilling it quickly, proportional to
the value of the HTLC and time to respond. What this essentially means is
that if an attacker wants people to send them HTLCs to delay, they pay a
certain amount in fees over time. So each node will track for each peer 1)
total fees collected from forwarding on routes where that peer is the prior
hop 2) total fees collect from forwarding on routes where that peer is the
next hop 3) total value times time of money locked in offered HTLCs on
channels to the peer. To track the third, as soon as an offered HTLC is
locked in by the peer, the node starts a timer. When the HTLC is settled or
failed or handled on-chain, the timer stops and the node registers the
total elapsed time multiplied by the value of the HTLC.
A very simple strategy would be to have two factors, R_inbound and
R_outbound and calculate reputation per peer as R_inbound * total inbound
fees + R_outbound * total outbound fees - total Bitcoin-seconds locked in
an HTLC. When forwarding a payment, you calculate the worst case reputation
loss, HTLC value * (CLTV - current block height) * 10 min / block, and fail
the payment if that value is greater than their current score. Effectively,
reputation scores are the maximum number of Bitcoin-seconds on could waste
in HTLCs as the downstream node in a channel. If you think, for example,
having 1 BTC for 1 hour is worth 1 satoshi, you might set R_inbound =
R_outbound = 10^8. Honest nodes should earn reputation passively by
forwarding payments and failing/fulfilling quickly, while an attacker would
lose reputation and have to pay fees to re-earn it. Furthermore, high
reputation nodes should be able to earn reputation faster since peers will
be willing to forward higher value HTLCs through them.
We want an additional property from this system though, which is that an
attacker be limited in their ability to disrupt network connectivity and
induce throttling on other channels. The above scheme has the problem that
for every unit of reputation the attacker loses, each upstream hop also
loses approximately the same amount -- they effectively get leverage on the
ability to reduce reputation. So instead, consider a modification: each hop
loses a quantity of reputation units equal to the *total* amount of
Bitcoin-seconds lost upstream. So say there's a payment A -> B -> C -> D,
where the CLTV decrements by 12 and the amount decrements by 10 satoshis at
each hop, with a terminal CLTV of 12 and a terminal amount of 100. So A
tells B "Here's an HTLC for 120 satoshis, CLTV is in 36 blocks, and you
will lose reputation at a rate of 120 satoshi-seconds per second of delay".
B calculates the maximum he could lose by forwarding to C as 120 * 36
blocks * 10 min / block. Assuming C has a high enough reputation score, B
will offer an HTLC of 110 satoshis, CLTV of 24 blocks, reputation rate of
120 + 110 = 230 satoshi-seconds per second. And finally C requires D to
stake reputation at a rate of 230 + 100 = 330 satoshi-seconds / second. The
effect is that if any node withholds the preimage, they lose an amount of
reputation equal to all of the reputation lost upstream combined, removing
any attack leverage.
This strategy has some downsides, namely in terms of centralization and
privacy. Telling the downstream node the rate at which they must stake
reputation may allow them to determine the number of upstream hops in the
circuit. To obfuscate this, the sender may require an addition reputation
stake, but takes a higher risk of the payment failing somewhere downstream.
The more obvious issue is centralization -- if payments are getting
throttled by reputation, there is even more of an incentive to route
through a small number of channels and decrease the length of payment
circuits. While this is a concern, the degree to while throttling happens
in controlled by the R parameters (the ratio at which fees contribute to
reputation). If R is high and reputation is abundant, then there will be
little throttling. But if a node finds itself under attack, it can raise
its R parameters and start throttling bad peers.
In summary, I think a simple local reputation mechanism of this form could
be implemented with only minor changes to the BOLT spec and could provide
decent resistance against DOS/loop attacks. Sorry for the excessively long
email.
[1] https://lists.linuxfoundation.org/pipermail/lightning-dev/2015-August/
000135.html
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180501/35997f70/attachment.html>

2023-06-09 12:50:06

- reply

📅 Original date posted:2018-04-16
📝 Original message:
>
> It seems to me that adding an entire new attack vector in order to only
> *mitigate* (not eliminate!) another attack vector is not a good enough
> trade-off. In particular the new attack seems *easier* to perform. The
> current attack where I annoy the other side until it closes has the risk
> that the other side may have a high tolerance for annoyance, and decide not
> to close the channel unilaterally anyway. But in a symmetric-delay world,
> I do not have to wait for the other side to get annoyed: I just trigger the
> lockup period immediately in the active attack.
>
I don't see the two attacks in the symmetric case as any different from one
another. In 1.1, you force a unilateral close by becoming unresponsive and
forcing the other side to eventually broadcast the commitment. In this case
you waste the other party's channel balance for the full time of the delay
PLUS the additional time they wait around to determine if you are ever
going to come online. In 1.2, you force a unilateral close by broadcasting
yourself. This is actually a weaker attack because the other party only has
to wait for the delay period and there is no uncertainty about when they
will get access to funds. So basically, I see no reason for an attacker to
ever choose 1.2 over 1.1.
So the question is whether 1.1 or 2.1 is a worse DOS. To me it's pretty
clear that it is 2.1 because the attacker does not get penalized and can
for more quickly use any remaining channel balance to open a new channel
with someone else and start over.
I also would not classify 1.1 nor 2.1 as a passive attack -- the attacker
is proactively rebalancing the victim's channel balances in order to waste
the maximal amount of time-money. Passive attacks [1] are where an attacker
does not directly interact with the victim and just eavesdrops or tries to
observe and extract information.
> > For example, in the case where the side unilaterally closing the channel
> has zero balance, the other side gets no delay and symmetry as measured by
> (coins locked) * (duration of lock) equals zero on both sides. When the
> side closing the channel has at least 50% of the balance, both sides must
> wait the full delay. Thoughts?
>
> So on channel setup where I am the funder to a 1BTC channel I make to
> Daniel:
>
> * Daniel holds a commitment transaction with: ZmnSCPxj=1BTC+no delay,
> Daniel=0BTC+no delay
> * I hold a commitment transaction with: ZmnSCPxj=1BTC+no delay,
> Daniel=0BTC+no delay
>
I rather like Daniel's suggestion to scale the delay in proportion to the
time-money lost by the broadcasting party. Essentially, the delay just
serves as punishment, so we should ensure that the punishment delivered is
no greater than the time-value lost by the initiator of the unilateral
close.
This example is not quite right: the commitment delays do not need to be
the same in both commitment transaction with this scaling strategy. So the
delay for the local output is ALWAYS the to_local_delay, as it is in the
BOLT 3 spec today. When assigning the delay on the remote output, however,
instead of using 0 as BOLT specifies now or to_remote_delay as I originally
proposed, a better rule might be min(to_remote_delay, to_local_delay *
to_local_value / to_remote_value). So the delay is never worse than what
the opposite side would get by broadcasting themself, but is the punishment
duration is reduced if the attacker broadcasts a commitment transaction in
which the balance of funds is skewed towards the victim's end of the
channel. However, I'm not sure how much this matters because as I argued
above, an attacker should always prefer to become unresponsive rather than
broadcast the commitment themself.
[1] https://en.wikipedia.org/wiki/Passive_attack
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180415/b2c9ac05/attachment-0001.html>

2023-06-09 12:50:03

- reply

📅 Original date posted:2018-04-12
📝 Original message:
As specified in BOLT 3, in the commitment transactions the to_local output
is time-locked with OP_CSV while the to_remote is a simple P2WPKH. The
to_local output must be time-locked in order to allow the other party to
come online and sweep funds from a published revoked commitment. In the
case of an honest unilateral close, however, this wastes the time-value of
capital locked in the channel for the publisher but not the other party.
This seems to create perverse incentives where a party that goes offline
and forces a unilateral close is not penalized and only the party that
broadcasts is. I see this as a problem in both normal operation and attack
scenarios. Consider cases where the peer is misbehaving and the node needs
to broadcast to chain. Concretely, consider a case where the other party
does not send an update_fail_htlc after it expires. A rational node might
decide to just become unresponsive instead of broadcasting the commitment
in the hopes that the other party publishes instead. Or if the value of the
HTLC is sufficient, it would want to claim the time-locked output ASAP in
which case the misbehaving peer is not punished and gets access to its
funds immediately.
I find it easier to analyze the game theory of these situations if the
to_remote output is also time-locked by the to_remote_delay. Making the
consequence of an on-chain settlement symmetric changes the game from
chicken [1] to a tragedy of the commons [2]. I'm curious how other people
think about this.
-jimpo
[1] https://en.wikipedia.org/wiki/Chicken_(game)
[2] https://en.wikipedia.org/wiki/Tragedy_of_the_commons
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180412/18ef498c/attachment.html>

2023-06-09 12:49:18

- reply

📅 Original date posted:2018-03-02
📝 Original message:
Regarding ping flooding, if it is problematic, the best solution is
probably including a small proof-of-work with the ping, similar to BIP 154.
However, the whole purpose of the ping in the first place is to be a
cheaper way to collect routing information than attempting to send a
payment, so I think adding a PoW starts to become counterproductive. Note
that the sender needs to expend a certain amount of computation just
creating the onion packet up front (on the order of a few ms, I believe),
so perhaps that is sufficient.
Also, if someone wanted to DoS the network, there are much better ways than
using this proposed ping mechanism. For example, someone can send payments
along any circuit with a randomly generated payment hash (for which the
preimage is unknown), and force a payment failure at the end of the route.
That is basically a way to ping that works now, but is more expensive for
everyone.
On Thu, Mar 1, 2018 at 4:16 PM, gb <kiwigb at yahoo.com> wrote:
> .... and any thoughts on protections against flood pinging?
>
> On Thu, 2018-03-01 at 09:45 -0500, Jim Posen wrote:
>
>
> > The main benefit is that this should make it quicker to send a
> > successful payment because latency is lower than sending an actual
> > payment and the sender could ping all possible routes in parallel,
> > whereas they can't send multiple payments in parallel. The main
> > downside I can think of is that, by the same token, it is faster and
> > cheaper for someone to extract information about channel capacities on
> > the network with a binary search.
> >
> >
> > -jimpo
> > _______________________________________________
> > 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/20180302/e1a8e668/attachment.html>

2023-06-09 12:49:17

- reply

📅 Original date posted:2018-03-01
📝 Original message:
My understanding is that the best strategy for choosing a route to send
funds over is to determine all possible routes, rank them by estimated fees
based on channel announcements and number of hops, then try them
successively until one works.
It seems inefficient to me to actually do a full HTLC commitment handshake
on each hop just to find out that the last hop in the route didn't have
sufficient remaining capacity in the first place. Depending on how many
people are using the network, I could also forsee situations where this
creates more payment failures because bandwidth is locked up in HTLCs that
are about to fail anyway.
One idea that would likely help is the ability to send a ping over an onion
route asking "does every hop have capacity to send X msat?" Every hop would
forward the onion request if the answer is yes, or immediately send the
response back up the circuit if the answer is no. This should reveal no
additional information about the channel capacities that the sender
couldn't determine by sending a test payment to themself (assuming they
could find a loop). Additionally, the hops could respond with the latest
fee rate in case channel updates are slow to propagate.
The main benefit is that this should make it quicker to send a successful
payment because latency is lower than sending an actual payment and the
sender could ping all possible routes in parallel, whereas they can't send
multiple payments in parallel. The main downside I can think of is that, by
the same token, it is faster and cheaper for someone to extract information
about channel capacities on the network with a binary search.
-jimpo
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180301/55533bfa/attachment.html>

2023-06-09 12:49:00

- reply

📅 Original date posted:2018-02-08
📝 Original message:
If using two hashes to deliver the payment while still getting a proof, I'm
not sure what that provides above just sending regular lightning payments
over multiple routes with one hash. Firstly, if there is a second hash, it
would presumably be the same for all routes, making them linkable again,
which AMP tries to solve. And secondly, the receiver has no incentive to
claim any of the HTLCs before all of them are locked in, because in that
case they are releasing the transaction receipt before fully being paid.
On Thu, Feb 8, 2018 at 8:41 AM, Johan Torås Halseth <johanth at gmail.com>
wrote:
> An obvious way to make this compatible with proof-of-payment would be to
> require two hashes to claim the HTLC: the presage from the invoice payment
> hash (as today) + the new hash introduced here. This would give the sender
> a receipt after only one of the HTLCs was claimed. Would require changes to
> the scripts of course.
>
> With Schnorr/EC operations this could probably be made more elegant, as
> mentioned.
>
> - Johan
> On Wed, Feb 7, 2018 at 18:21, Rusty Russell <rusty at rustcorp.com.au> wrote:
>
> Olaoluwa Osuntokun <laolu32 at gmail.com> writes:
> > Hi Y'all,
> >
> > A common question I've seen concerning Lightning is: "I have five $2
> > channels, is it possible for me to *atomically* send $6 to fulfill a
> > payment?". The answer to this question is "yes", provided that the
> receiver
>
> This is awesome! I'm kicking myself for not proposing it :)
>
> Unfortunately, your proposal defines a way to make multipath donations,
> not multipath payments :(
>
> In other words, you've lost proof of payment, which IMHO is critical.
>
> Fortunately, this can be fairly trivially fixed when we go to scriptless
> scripts or other equivalent decorrelation mechanism, when I think this
> mechanism becomes extremely powerful.
>
> > - Potential fee savings for larger payments, contingent on there being a
> > super-linear component to routed fees. It's possible that with
> > modifications to the fee schedule, it's actually *cheaper* to send
> > payments over multiple flows rather than one giant flow.
>
> This is a stretch. I'd stick with the increased reliability/privacy
> arguments which are overwhelmingly compelling IMHO.
>
> If I have any important feedback on deeper reading (and after a sccond
> coffee), I'll send a separate email.
>
> Thanks!
> Rusty.
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>
> _______________________________________________
> 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/20180208/31041639/attachment.html>

2023-06-09 12:48:59

- reply

📅 Original date posted:2018-02-07
📝 Original message:
This is a really neat idea.
This is a question about non-interactive payments in general, but is there
any way to get a proof of payment? With regular invoices, knowledge of the
preimage serves as cryptographic proof that the payment was delivered.
On Feb 6, 2018 6:26 PM, "Conner Fromknecht" <conner at lightning.engineering>
wrote:
>
> Hi ZmnSCPxj and Laolu,
>
> > Indeed, the existence of per-hop fees (`fee_base_msat`) means,
> splitting the
> > payment over multiple flows will be, very likely, more expensive,
> compared to
> > using a single flow.
>
> As Laolu pointed out, we have yet to see how fees evolve on mainnet or
> what will
> emerge as a sane, default fee schedules. I agree that if the same
> proportional
> fee is used across all partial payments, then it could certainly be more
> expensive.
>
> However, it could also be the case that you were paying a needlessly high
> proportional fee to begin with, because paths of sufficient capacity to the
> destination were scarce. In an AMP world, there will be an abundance of
> channels
> that can route small, partial payments, which may itself drive down the
> competitive fee rate for smaller payments. Just a hypothesis, we shall see
> where
> supply meets demand!
>
> At the end of the day, the user can always fall back to regular payment if
> they
> expect to end up paying more fees using an AMP.
>
> > (If we want to support multiple routes converging to an intermediate
> node,
> > then continue routing to a different final node after routes have merged
> (i.e.
> > A->B->C->D, and A->E->C->D, with the payment being merged by C, who
> forwards
> > the combination to D), then we need to follow the current hop data
> format, but
> > I think supporting AMP at final payees is actually enough...
>
> I think this is an interesting idea, sounds maybe like a
> recursive/hierarchical
> AMP? The ability to merge the payments seems like it would result in a
> decent privacy
> leak, as I believe an intermediary would have enough evidence to prove
> that two
> payments were merged/correlated. Simple traffic analysis would also reveal
> a
> discrepancy in the number of incoming and outgoing packets, and possibly
> other
> observable differences in routing (some) AMPs vs regular payments.
>
> FWIW the current proposal allows the paths of partial payments to overlap,
> in such a scenario C would just forward the HTLCs independently. One could
> send
> them all along the same path if they desired! I'm assuming the intent here
> is to
> try and reduce total fees?
>
> Minor correction^2:
>
> > This should actually be (H(s_0 || s_1 || ...), s_i).
>
> This assumes the receiver knows the indexes of each share. Without this
> knowledge they would have to brute force all orderings to check the
> fingerprint.
>
> To maintain order invariance on the receiving end, I would propose sending
> (0, s_i) for the first n-1 partial payments, and then (n, s_i) on the
> final one.
> As in the description of the basic AMP scheme, the receiver maintains a
> persistent count of how many partial payments have been received for ID.
> If the
> receiver does not get the last payment last, the receiver just waits until
> all n
> have been received before deciding that its reconstructed value is BP.
>
> The receiver can verify they've received the correct BP and n by
> rederiving the
> partial preimages r_i = H(BP || i) and checking that there are n
> outstanding
> payments, one for each h_i = H(r_i). This also saves the receiving node n
> additional hash invocations.
>
> -Conner
>
> On Tue, Feb 6, 2018 at 4:04 PM Olaoluwa Osuntokun <laolu32 at gmail.com>
> wrote:
>
>> Hi ZmnSCPxj,
>>
>> > This is excellent work!
>>
>> Thanks!
>>
>> > I think, a `globalfeatures` odd bit could be used for this. As it is
>> > end-ot-end, `localfeatures` is not appropriate.
>>
>> Yep, it would need to be a global feature bit. In the case that we're
>> sending to a destination which isn't publicly advertised, then perhaps an
>> extension to BOLT-11 could be made to signal receiver support.
>>
>> > I believe, currently, fees have not this super-linear component
>>
>> Yep they don't. Arguably, we should also have a component that scales
>> according to the proposed CLTV value of the outgoing HTLC. At Scaling
>> Bitcoin Stanford, Aviv Zohar gave a talked titled "How to Charge
>> Lightning"
>> where the authors analyzed the possible evolution of fees on the network
>> (and also suggested adding this super-linear component to extend the
>> lifetime of channels). However, the talk itself focused on a very simple
>> "mega super duper hub" topology. Towards the end he alluded to a
>> forthcoming
>> paper that had more comprehensive analysis of more complex topologies. I
>> look forward to the publication of their finalized work.
>>
>> > Indeed, the existence of per-hop fees (`fee_base_msat`) means, splitting
>> > the payment over multiple flows will be, very likely, more expensive,
>> > compared to using a single flow.
>>
>> Well it's still to be seen how the fee structure on mainnet emerges once
>> the
>> network is still fully bootstrapped. AFAIK, most running on mainnet atm
>> are
>> using the default fee schedules for their respective implementations. For
>> example, the default fee_base_msat for lnd is 1000 msat (1 satoshi).
>>
>> > I believe the `realm` byte is intended for this.
>>
>> The realm byte is meant to signal "forward this to the dogecoin channel".
>> ATM, we just default to 0 as "Bitcoin". However, the byte itself only
>> really
>> need significance between the sender and the intermediate node. So there
>> isn't necessarily pressure to have a globally synchronized set of realm
>> bytes.
>>
>> > Thus, you can route over nodes that are unaware of AMP, and only provide
>> > an AMP realm byte to the destination node, who, is able to reconstruct
>> this
>> > your AMP data as per your algorithm.
>>
>> Yes, the intermediate nodes don't need to be aware of the end-to-end
>> protocol. For the final hop, there are actually 53 free bytes (before one
>> needs to signal the existence of EOBs):
>>
>> * 1 byte realm
>> * 8 bytes next addr (all zeroes to signal final dest)
>> * 32 bytes hmac (also all zeroes for the final dest)
>> * 12 bytes padding
>>
>> So any combo of these bytes can be used to signal more advanced protocols
>> to
>> the final destination.
>>
>>
>> A correction from the prior email description:
>>
>> > We can further modify our usage of the per-hop payloads to send
>> > (H(BP), s_i) to consume most of the EOB sent from sender to receiver.
>>
>> This should actually be (H(s_0 || s_1 || ...), s_i). So we still allow
>> them
>> to check this finger print to see if they have all the final shares, but
>> don't allow them to preemptively pull all the payments.
>>
>>
>> -- Laolu
>>
>>
>> On Mon, Feb 5, 2018 at 11:12 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
>>
>>> Good morning Laolu,
>>>
>>> This is excellent work!
>>>
>>> Some minor comments...
>>>
>>>
>>> (Atomic Multi-path Payments). It can be experimented with on Lightning
>>> *today* with the addition of a new feature bit to gate this new
>>> feature. The beauty of the scheme is that it requires no fundamental
>>> changes
>>> to the protocol as is now, as the negotiation is strictly *end-to-end*
>>> between sender and receiver.
>>>
>>>
>>> I think, a `globalfeatures` odd bit could be used for this. As it is
>>> end-ot-end, `localfeatures` is not appropriate.
>>>
>>> - Potential fee savings for larger payments, contingent on there being
>>> a
>>> super-linear component to routed fees. It's possible that with
>>> modifications to the fee schedule, it's actually *cheaper* to send
>>> payments over multiple flows rather than one giant flow.
>>>
>>>
>>> I believe, currently, fees have not this super-linear component.
>>> Indeed, the existence of per-hop fees (`fee_base_msat`) means, splitting
>>> the payment over multiple flows will be, very likely, more expensive,
>>> compared to using a single flow. Tiny roundoffs in computing the
>>> proportional fees (`fee_proportional_millionths`) may make smaller
>>> flows give a slight fee advantage, but I think the multiplication of
>>> per-hop fees will dominate.
>>>
>>>
>>> - Using smaller payments increases the set of possible paths a partial
>>> payment could have taken, which reduces the effectiveness of static
>>> analysis techniques involving channel capacities and the plaintext
>>> values being forwarded.
>>>
>>>
>>> Strongly agree!
>>>
>>>
>>> In order to include the three tuple within the per-hop payload for the
>>> final
>>> destination, we repurpose the _first_ byte of the un-used padding bytes
>>> in
>>> the payload to signal version 0x01 of the AMP protocol (note this is a
>>> PoC
>>> outline, we would need to standardize signalling of these 12 bytes to
>>> support other protocols).
>>>
>>>
>>> I believe the `realm` byte is intended for this. Intermediate nodes do
>>> not need to understand realm bytes that are understood by other nodes in
>>> the route, including the realm bytes understood by the final destination,
>>> as intermediate nodes cannot, indeed, read the hop data of other nodes.
>>> Thus, you can route over nodes that are unaware of AMP, and only provide an
>>> AMP realm byte to the destination node, who, is able to reconstruct this
>>> your AMP data as per your algorithm.
>>>
>>> Indeed, the `realm` byte controls the interpretation of the rest of the
>>> 65-byte packet. If you define, instead, a separate `realm` that is
>>> understood by the destination node, you can redefine the entire 64 bytes of
>>> the final hop data as you wish.
>>>
>>> If we support AMP only at final payees, we can completely redefine the
>>> 64 bytes in the final hop data for the new AMP `realm`, and not consume the
>>> next hop (which would reduce route length by 1).
>>>
>>> (If we want to support multiple routes converging to an intermediate
>>> node, then continue routing to a different final node after routes have
>>> merged (i.e. A->B->C->D, and A->E->C->D, with the payment being merged by
>>> C, who forwards the combination to D), then we need to follow the current
>>> hop data format, but I think supporting AMP at final payees is actually
>>> enough... AMP at intermediate nodes might not be used often enough by
>>> senders for it to matter, as taking advantage of that seems more complex
>>> than just asking your routing algo to provide you multiple routes to a
>>> destination, which you are probably already doing)
>>>
>>> ----
>>>
>>> Overall, good work I think.
>>>
>>> Regards,
>>> ZmnSCPxj
>>>
>> _______________________________________________
>> Lightning-dev mailing list
>> Lightning-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>>
>
> _______________________________________________
> 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/20180207/48a507f8/attachment-0001.html>

2023-06-09 12:48:51

- reply

📅 Original date posted:2018-02-07
📝 Original message:
I like Christian's proposal of adding a simple announcement cutoff
timestamp with the intention of designing something more sophisticated
given more time.
I prefer the approach of having an optional feature bit signalling that a
`set_gossip_timestamp` message must be sent immediately after `init`, as
Laolu suggested. This way it doesn't conflict with and other possible
handshake extensions.
On Feb 7, 2018 9:50 AM, "Fabrice Drouin" <fabrice.drouin at acinq.fr> wrote:
Hi,
Suppose you partition nodes into 3 generic roles:
- payers: they mostly send payments, are typically small and operated
by end users, and are offline quite a lot
- relayers: they mostly relay payments, and would be online most of
the time (if they're too unreliable other nodes will eventually close
their channels with them)
- payees: they mostly receive payments, how often they can be online
is directly link to their particular mode of operations (since you
need to be online to receive payments)
Of course most nodes would play more or less all roles. However,
mobile nodes would probably be mostly "payers", and they have specific
properties:
- if they don't relay payments they don't have to be announced. There
could be millions of mobile nodes that would have no impact on the
size of the routing table
- it does not impact the network when they're offline
- but they need an accurate routing table. This is very different from
nodes who mostly relay or accept payements
- they would be connected to a very small number of nodes
- they would typically be online for just a few hours every day, but
could be stopped/paused/restarted many times a day
Laolu wrote:
> So I think the primary distinction between y'alls proposals is that
> cdecker's proposal focuses on eventually synchronizing all the set of
> _updates_, while Fabrice's proposal cares *only* about the newly created
> channels. It only cares about new channels as the rationale is that if
once
> tries to route over a channel with a state channel update for it, then
> you'll get an error with the latest update encapsulated.
If you have one filter per day and they don't match (because your peer
has channels that you missed, or
have been closed and you were not aware of it) then you will receive
all channel announcements for
this particular day, and the associated updates
Laolu wrote:
> I think he's actually proposing just a general update horizon in which
> vertexes+edges with a lower time stamp just shouldn't be set at all. In
the
> case of an old zombie channel which was resurrected, it would eventually
be
> re-propagated as the node on either end of the channel should broadcast a
> fresh update along with the original chan ann.
Yes but it could take a long time. It may be worse on testnet since it
seems that nodes
don't change their fees very often. "Payer nodes" need a good routing
table (as opposed
to "relayers" which could work without one if they never initiate payments)
Laolu wrote:
> This seems to assume that both nodes have a strongly synchronized view of
> the network. Otherwise, they'll fall back to sending everything that went
on
> during the entire epoch regularly. It also doesn't address the zombie
churn
> issue as they may eventually send you very old channels you'll have to
deal
> with (or discard).
Yes I agree that for nodes which have connections to a lot of peers,
strongly synchronized routing tables is
harder to achieve since a small change may invalidate an entire
bucket. Real queryable filters would be much
better, but worst case scenario is we've sent an additionnal 30 Kb or
o of sync messages.
(A very naive filter would be sort + pack all short ids for example)
But we focus on nodes which are connected to a very small number of
peers, and in this particular
case it is not an unrealistic expectation.
We have built a prototype and on testnet it works fairly well. I also
found nodes which have no direct
channel betweem them but produce the same filters for 75% of the
buckets ("produce" here means
that I opened a simple gossip connection to them, got their routing
table and used it to generate filters).
Laolu wrote:
> How far back would this go? Weeks, months, years?
Since forever :)
One filter per day for all annoucements that are older than now - 1
week (modulo 144)
One filter per block for recent announcements
>
> FWIW this approach optimizes for just learning of new channels instead of
> learning of the freshest state you haven't yet seen.
I'd say it optimizes the case where you are connected to very few
peers, and are online a few times every day (?)
>
> -- Laolu
>
>
> On Mon, Feb 5, 2018 at 7:08 AM Fabrice Drouin <fabrice.drouin at acinq.fr>
> wrote:
>>
>> Hi,
>>
>> On 5 February 2018 at 14:02, Christian Decker
>> <decker.christian at gmail.com> wrote:
>> > Hi everyone
>> >
>> > The feature bit is even, meaning that it is required from the peer,
>> > since we extend the `init` message itself, and a peer that does not
>> > support this feature would be unable to parse any future extensions to
>> > the `init` message. Alternatively we could create a new
>> > `set_gossip_timestamp` message that is only sent if both endpoints
>> > support this proposal, but that could result in duplicate messages
being
>> > delivered between the `init` and the `set_gossip_timestamp` message and
>> > it'd require additional messages.
>>
>> We chose the other aproach and propose to use an optional feature
>>
>> > The reason I'm using timestamp and not the blockheight in the short
>> > channel ID is that we already use the timestamp for pruning. In the
>> > blockheight based timestamp we might ignore channels that were created,
>> > then not announced or forgotten, and then later came back and are now
>> > stable.
>>
>> Just to be clear, you propose to use the timestamp of the most recent
>> channel updates to filter
>> the associated channel announcements ?
>>
>> > I hope this rather simple proposal is sufficient to fix the short-term
>> > issues we are facing with the initial sync, while we wait for a real
>> > sync protocol. It is definitely not meant to allow perfect
>> > synchronization of the topology between peers, but then again I don't
>> > believe that is strictly necessary to make the routing successful.
>> >
>> > Please let me know what you think, and I'd love to discuss Pierre's
>> > proposal as well.
>> >
>> > Cheers,
>> > Christian
>>
>> Our idea is to group channel announcements by "buckets", create a
>> filter for each bucket, exchange and use them to filter out channel
>> announcements.
>>
>> We would add a new `use_channel_announcement_filters` optional feature
>> bit (7 for example), and a new `channel_announcement_filters` message.
>>
>> When a node that supports channel announcement filters receives an
>> `init` message with the `use_channel_announcement_filters` bit set, it
>> sends back its channel filters.
>>
>> When a node that supports channel announcement filters receives
>> a`channel_announcement_filters` message, it uses it to filter channel
>> announcements (and, implicitly ,channel updates) before sending them.
>>
>> The filters we have in mind are simple:
>> - Sort announcements by short channel id
>> - Compute a marker height, which is `144 * ((now - 7 * 144) / 144)`
>> (we round to multiples of 144 to make sync easier)
>> - Group channel announcements that were created before this marker by
>> groups of 144 blocks
>> - Group channel announcements that were created after this marker by
>> groups of 1 block
>> - For each group, sort and concatenate all channel announcements short
>> channel ids and hash the result (we could use sha256, or the first 16
>> bytes of the sha256 hash)
>>
>> The new `channel_announcement_filters` would then be a list of
>> (height, hash) pairs ordered by increasing heights.
>>
>> This implies that implementation can easily sort announcements by
>> short channel id, which should not be very difficult.
>> An additional step could be to send all short channel ids for all
>> groups for which the group hash did not match. Alternatively we could
>> use smarter filters
>>
>> The use case we have in mind is mobile nodes, or more generally nodes
>> which are often offline and need to resync very often.
>>
>> Cheers,
>> Fabrice
>> _______________________________________________
>> Lightning-dev mailing list
>> Lightning-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
_______________________________________________
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/20180207/cb4ed693/attachment-0001.html>

2023-06-07 18:17:27

- reply

📅 Original date posted:2019-04-03
📝 Original message:Big Concept ACK. I think this would be one of the biggest usability
improvements for Bitcoin and I see no security issues with the assumevalid
approach. I also agree that it's important to start work on this even
before the ultimate, perfect accumulator has been designed/tested and the
commitment scheme can always be upgraded later on. assumeutxo syncing
actually seems pretty orthogonal to the accumulator research.
I have a few questions
- So any nodes that do an initial sync will stop at the assumeutxo height,
serialize a snapshot of the chain state and store it? How many nodes are
expected to do this? Any idea how long this takes? Should it be enabled by
default?
- Would pruned nodes still download all historic blocks to double-check the
snapshot or only full nodes that intend to serve block data?
- How long are old snapshots retained? Presumably during a new release
nodes should keep at least a version back. Without P2P signalling of which
snapshots are available, they maybe have to keep all old snapshots or even
download old ones.
and comments
- The snapshot should probably be chunked up to minimize the amount of
bandwidth/IO/memory a malicious node could waste before you realize. Also,
it would make parallel downloading easier.
On Tue, Apr 2, 2019 at 4:43 PM James O'Beirne via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Hi,
>
> I'd like to discuss assumeutxo, which is an appealing and simple
> optimization in the spirit of assumevalid[0].
>
> # Motivation
>
> To start a fully validating bitcoin client from scratch, that client
> currently
> needs to perform an initial block download. To the surprise of no one, IBD
> takes a linear amount time based on the length of the chain's history. For
> clients running on modest hardware under limited bandwidth constraints,
> say a mobile device, completing IBD takes a considerable amount of time
> and thus poses serious usability challenges.
>
> As a result, having fully validating clients run on such hardware is rare
> and
> basically unrealistic. Clients with even moderate resource constraints
> are encouraged to rely on the SPV trust model. Though we have promising
> improvements to existing SPV modes pending deployment[1], it's worth
> thinking about a mechanism that would allow such clients to use trust
> models closer to full validation.
>
> The subject of this mail is a proposal for a complementary alternative to
> SPV
> modes, and which is in the spirit of an existing default, `assumevalid`.
> It may
> help modest clients transact under a security model that closely resembles
> full validation within minutes instead of hours or days.
>
> # assumeutxo
>
> The basic idea is to allow nodes to initialize using a serialized version
> of the
> UTXO set rendered by another node at some predetermined height. The
> initializing node syncs the headers chain from the network, then obtains
> and
> loads one of these UTXO snapshots (i.e. a serialized version of the UTXO
> set
> bundled with the block header indicating its "base" and some other
> metadata).
>
> Based upon the snapshot, the node is able to quickly reconstruct its
> chainstate,
> and compares a hash of the resulting UTXO set to a preordained hash
> hard-coded
> in the software a la assumevalid. This all takes ~23 minutes, not
> accounting for
> download of the 3.2GB snapshot[2].
>
> The node then syncs to the network tip and afterwards begins a simultaneous
> background validation (i.e., a conventional IBD) up to the base height of
> the
> snapshot in order to achieve full validation. Crucially, even while the
> background validation is happening the node can validate incoming blocks
> and
> transact with the benefit of the full (assumed-valid) UTXO set.
>
> Snapshots could be obtained from multiple separate peers in the same
> manner as
> block download, but I haven't put much thought into this. In concept it
> doesn't
> matter too much where the snapshots come from since their validity is
> determined via content hash.
>
> # Security
>
> Obviously there are some security implications due consideration. While
> this
> proposal is in the spirit of assumevalid, practical attacks may become
> easier.
> Under assumevalid, a user can be tricked into transacting under a false
> history
> if an attacker convinces them to start bitcoind with a malicious
> `-assumevalid`
> parameter, sybils their node, and then feeds them a bogus chain
> encompassing
> all of the hard-coded checkpoints[3].
>
> The same attack is made easier in assumeutxo because, unlike in
> assumevalid,
> the attacker need not construct a valid PoW chain to get the victim's node
> into
> a false state; they simply need to get the user to accept a bad
> `-assumeutxo`
> parameter and then supply them an easily made UTXO snapshot containing,
> say, a
> false coin assignment.
>
> For this reason, I recommend that if we were to implement assumeutxo, we
> not
> allow its specification via commandline argument[4].
>
> Beyond this risk, I can't think of material differences in security
> relative to
> assumevalid, though I appeal to the list for help with this.
>
> # More fully validating clients
>
> A particularly exciting use-case for assumeutxo is the possibility of
> mobile
> devices functioning as fully validating nodes with access to the complete
> UTXO
> set (as an alternative to SPV models). The total resource burden needed to
> start a node
> from scratch based on a snapshot is, at time of writing, a ~(3.2GB
> + blocks_to_tip * 4MB) download and a few minutes of processing time,
> which sounds
> manageable for many mobile devices currently in use.
>
> A mobile user could initialize an assumed-valid bitcoin node within an
> hour,
> transact immediately, and complete a pruned full validation of their
> assumed-valid chain over the next few days, perhaps only doing the
> background
> IBD when their device has access to suitable high-bandwidth connections.
>
> If we end up implementing an accumulator-based UTXO scaling design[5][6]
> down
> the road, it's easy to imagine an analogous process that would allow very
> fast
> startup using an accumulator of a few kilobytes in lieu of a multi-GB
> snapshot.
>
> ---
>
> I've created a related issue at our Github repository here:
> https://github.com/bitcoin/bitcoin/issues/15605
>
> and have submitted a draft implementation of snapshot usage via RPC here:
> https://github.com/bitcoin/bitcoin/pull/15606
>
> I'd like to discuss here whether this is a good fit for Bitcoin
> conceptually. Concrete
> plans for deployment steps should be discussed in the Github issue, and
> after all
> that my implementation may be reviewed as a sketch of the specific software
> changes necessary.
>
> Regards,
> James
>
>
> [0]:
> https://bitcoincore.org/en/2017/03/08/release-0.14.0/#assumed-valid-blocks
> [1]: https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki
> [2]: as tested at height 569895, on a 12 core Intel Xeon Silver 4116 CPU @
> 2.10GHz
> [3]:
> https://github.com/bitcoin/bitcoin/blob/84d0fdc/src/chainparams.cpp#L145-L161
> [4]: Marco Falke is due credit for this point
> [5]: utreexo: https://www.youtube.com/watch?v=edRun-6ubCc
> [6]: Boneh, Bunz, Fisch on accumulators: https://eprint.iacr.org/2018/1188
>
> _______________________________________________
> 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/20190403/49377fdf/attachment.html>

2023-06-07 18:17:24

- reply

📅 Original date posted:2019-04-04
📝 Original message:>
> Learning C++ is something within everyone's capability. Even people who do
> not
> wish to learn it can hire someone to perform review for them.
>
Anyone with enough knowledge of C++ to audit the entire the Bitcoin Core
codebase is more than capable of running it with assumeutxo disabled and
checking the hard-coded vale themself.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20190403/fa2a9a58/attachment.html>

2023-06-07 18:12:55

- reply

📅 Original date posted:2018-06-10
📝 Original message:I generally like the direction of this proposal in terms of allowing full
nodes to run with a different storage/bandwidth tradeoff. Cory, were this
implemented, would you expect Core to support both operating modes (full
UTXO set and UHS) depending on user configuration, or would UHS be
mandatory?
Also, given that Bram Cohen's TXO bitfield proposal was an inspiration for
this, could you comment on why the UHS is preferable to that approach? An
alternative that goes even further in the direction of more bandwidth, less
storage, would be for nodes to simply maintain a Merkle Mountain Range over
all TXOs in order of creation and a spentness bitfield. Blocks could be
requested with the prev outputs and a Merkle proof linking them into the
MMR root. Since the Merkle proof is deterministic, it could be computed by
archive nodes and miners and saved alongside the block data for relay.
Another benefit of this is the TXO MMR root may be independently useful if
committed into the coinbase transaction.
On Thu, Jun 7, 2018 at 7:02 AM Sjors Provoost via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> eMMC storage, which low end devices often use, come in 2x increments.
> Running a pruned full node on 8 GB is difficult if not impossible (the UTXO
> set peaked at 3.5 GB in January, but a full node stores additional stuff).
>
> However, 16 GB is only €10 more expensive and presumably standard by the
> time this would be rolled out.
>
> On AWS every GB of SSD storage avoided saves $1 per year, not end of the
> world stuff, but not negligible either. Outbound traffic costs $0.10 / GB
> (ignoring free allowance), so when uploading 200 GB per year, the 5% would
> offset $1 of storage cost savings.
>
> The above seems marginal, probably not worth it unless there’s really no
> downside.
>
> What I find attractive about this proposal is the ability to squeeze more
> out of limited RAM (typically only 1 or 2 GB on these low end devices). I’d
> have to test Cory’s branch to see if that actually matters in practice.
>
> It’s also useful to distinguish benefits during initial sync from ongoing
> operation. The former I’ve almost given up on for low end devices (can
> take weeks), in favor of doing it on a faster computer and copying the
> result. The latter needs far less RAM, so perhaps this proposal doesn’t
> help much there, but that would be useful to measure.
>
> Did you try the recent SHA256 optimizations on your branch?
>
> Sjors
>
> > Op 17 mei 2018, om 18:56 heeft Gregory Maxwell via bitcoin-dev <
> bitcoin-dev at lists.linuxfoundation.org> het volgende geschreven:
> >
> > On Wed, May 16, 2018 at 4:36 PM, Cory Fields via bitcoin-dev
> > <bitcoin-dev at lists.linuxfoundation.org> wrote:
> >> Tl;dr: Rather than storing all unspent outputs, store their hashes.
> >
> > My initial thoughts are it's not _completely_ obvious to me that a 5%
> > ongoing bandwidth increase is actually a win to get something like a
> > 40% reduction in the size of a pruned node (and less than a 1%
> > reduction in an archive node) primarily because I've not seen size of
> > a pruned node cited as a usage limiting factor basically anywhere. I
> > would assume it is a win but wouldn't be shocked to see a careful
> > analysis that concluded it wasn't.
> >
> > But perhaps more interestingly, I think the overhead is not really 5%,
> > but it's 5% measured in the context of the phenomenally inefficient tx
> > mechanisms ( https://bitcointalk.org/index.php?topic=1377345.0 ).
> > Napkin math on the size of a txn alone tells me it's more like a 25%
> > increase if you just consider size of tx vs size of
> > tx+scriptpubkeys,amounts. If I'm not missing something there, I think
> > that would get in into a very clear not-win range.
> >
> > On the positive side is that it doesn't change the blockchain
> > datastructure, so it's something implementations could do without
> > marrying the network to it forever.
> >
>
> _______________________________________________
> 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/20180610/609b21d1/attachment.html>

2023-06-07 18:12:44

- reply

📅 Original date posted:2018-06-04
📝 Original message:>
> I was wondering why this multi-layer multi-block filter proposal isn't
> getting any comment,
> is it because not asking all filters is leaking information?
>
It's an interesting idea, but it adds more complexity to the client and
could be added later on if clients adopt BIP 157 and complain about
bandwidth. It also derives all bandwidth gains from address reuse. So I'm
hesitant to make the complexity tradeoff for bandwidth savings due to a
behavior that is actively discouraged.
On another note, I've been thinking that block TXO commitments could
resolve the issue we are facing now with deciding between the prev script
approach and outpoint. The whole argument for outpoints is that there are
compact-ish (<1 MiB) proofs of filter validity, which is not currently
possible if the filters included prev output data. Such proofs would be
feasible if blocks headers (well, actually coinbase txs) had a commitment
to the Merkle root of all newly created outputs in the block.
This idea has been tossed around before in the context of fraud proofs and
TXO bitfields, and seems to unlock a whole bunch of other P2P commitments.
For example, if we wanted to do P2P commitments (BIP 157-style) to the
distribution of tx fees in a block, one could use block TXO commitments to
prove correctness of fees for non-segwit txs. It also enables block
validity proofs (assuming parent blocks are valid), which are not as
powerful as invalidity/fraud proofs, but interesting nonetheless.
This would require a new getdata type BLOCK_WITH_PREVOUTS or something. I
assume for most coinbase-tx-committed proposals, we'll also need a new
getcoinbases/coinbases that requests the coinbase tx and Merkle branch for
a range of headers as well. But with these additions, we could start
serving more block-derived data to light clients under the BIP 157
at-least-one-honest-peer assumption.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180604/ec43b862/attachment-0001.html>

2023-06-07 18:12:44

- reply

📅 Original date posted:2018-06-05
📝 Original message:>
> I don't understand this comment. The bandwidth gains are not from
> address reuse, they are from the observed property that false
> positives are independent between two filters. I.e. clients that
> connect once a day will probably download 2-3 filters at most, if they
> had nothing relevant in the last ~144 blocks.
>
Your multi-layer digest proposal (https://bc-2.jp/bfd-profile.pdf) uses a
different type of filter which seems more like a compressed Bloom filter if
I understand it correctly. Appendix A shows how the FP rate increases with
the number of elements.
With the Golomb-Coded Sets, the filter size increases linearly in the
number of elements for a fixed FP rate. So currently we are targeting an
~1/2^20 rate (actually 1/784931 now), and filter sizes are ~20 bits * N for
N elements. With a 1-layer digest covering let's say 16 blocks, you could
drop the FP rate on the digest filters and the block filters each to ~10
bits per element, I think, to get the same FP rate for a given block by
your argument of independence. But the digest is only half the size of the
16 combined filters and there's a high probability of downloading the other
half anyway. So unless there is greater duplication of elements in the
digest filters, it's not clear to me that there are great bandwidth
savings. But maybe there are. Even so, I think we should just ship the
block filters and consider multi-layer digests later.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180605/1d6de3bd/attachment.html>

2023-06-07 18:12:38

- reply

📅 Original date posted:2018-06-01
📝 Original message:To address the at-least-one-honest peer security assumption for light
clients, I think this is a rather good security model for light clients.
First it significantly reduces the chances that an attacker can eclipse a
client just by chance, and clients can implement measures like ensuring
connectivity to peers from different subnets. But even if, as you suggest,
a network attacker controls the target's local network, peers still can
have good security guarantees by requiring authenticated connections to
semi-trusted peers. A client can select a set of N servers that it believes
will not collude to attack it, and only sync filters if connected to a
threshold of them. So even if the network is malicious, the attacker cannot
forge the authenticated responses. The level of trust in these designated
parties again is quite low because only one has to be honest. This would
require something like BIP 150.
Even if clients are uncomfortable with whitelisting required peers, it
could have a policy of requiring a certain number of connections to peers
that have honestly served it filters in the past. This is sort of like
trust-on-first-use. This type of scheme, however, would require nodes to
advertise a pubkey per address, which BIP 150/151 does not support at
present.
All in all, I think this is an acceptable security model for light clients.
Without the ability to verify filter validity, a client would have to stop
syncing altogether in the presence of just one malicious peer, which is
unacceptable.
The other concern you raise, Greg, is using a filter for P2P communications
that we expect may be replaced in the future. You also raise the point that
full node wallets can use the smaller filters for rescans because the
filter validity is not in question. I'd perfectly fine with the idea of
defining two filter types in the BIP, one that is output script + outpoint
and the other output script + prev script. But I imagine some people would
object to the idea of full nodes storing two different filters that overlap
in contents. If we had to pick just one though, I'm strongly in support of
output script + outpoint so that BIP 157 can be deployed ASAP without a
consensus change. It's entirely possible we will learn even more about
optimal filter design through deployment and adoption.
On Fri, Jun 1, 2018 at 5:22 PM Gregory Maxwell <greg at xiph.org> wrote:
> On Sat, Jun 2, 2018 at 12:01 AM, Olaoluwa Osuntokun <laolu32 at gmail.com>
> wrote:
> >> A typical network attacker (e.g. someone on your lan or wifi segmet, or
> >> someone who has compromised or operates an upstream router) can be all
> of
> >> your peers.
> >
> > This is true, but it cannot make us accept any invalid filters unless the
> > attacker is also creating invalid blocks w/ valid PoW.
>
> I wish that were the true, but absent commitments that wouldn't be the
> case unless you were always downloading all the blocks-- since you
> wouldn't have any sign that there was something wrong with the
> filter-- and downloading all the blocks would moot using the filters
> in the first place. :)
>
> Or have I misunderstood you massively here?
>
> For segwit originally I had proposed adding additional commitments
> that would make it possible to efficiently prove invalidity of a
> block; but that got stripped because many people were of the view that
> the "assume you have at least one honest peer who saw that block and
> rejected it to tell you that the block was invalid" security
> assumption was of dubious value. Maybe it's more justifiable to make
> use of a dubious assumption for a P2P feature than for a consensus
> feature? Perhaps, I'd rather have both filter types from day one so
> that things not implementing the comparison techniques don't get the
> efficiency loss or the extra work to change filter types for a
> consensus one.
>
> [I think now that we're much closer to a design that would be worth
> making a consensus committed version of than we were a few months ago
> now, since we are effectively already on a second generation of the
> design with the various improvements lately]
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180601/b99c927d/attachment-0001.html>

2023-06-07 18:12:29

- reply

📅 Original date posted:2018-05-29
📝 Original message:This is a really cool finding, thanks Pieter!
I did some more analysis on selecting a good P value to reduce total data
downloaded considering both filters themselves and blocks in the case of
false positive matches, using data from mainnet. The quantity it minimizes
is:
filter_size(N, B) + block_size * false_positive_probability(C, N, B)
N is the number of filter elements per block
B is the Golomb-Rice coding parameter
C is the number of filter elements watched by the client
The main result is that:
For C = 10, B = 13 is optimal
For C = 100, B = 16 is optimal
For C = 1,000, B = 20 is optimal
For C = 10,000, B = 23 is optimal
So any value of B in the range 16 to 20 seems reasonable, with M = 1.4971 *
2^B for optimal compression, as Pieter derived. The selection of the
parameter depends on the target number of elements that a client may watch.
I attached some of the results, and would be happy to share the CSV and raw
notebook if people are interested.
On Fri, May 25, 2018 at 2:14 PM Gregory Maxwell via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> On Fri, May 25, 2018 at 6:42 PM, Gregory Maxwell <greg at xiph.org> wrote:
> > configuration is roughly right, then M=1569861 and rice parameter 19
> > should be used.
>
> That should have been M=784931 B=19 ... paste error.
> _______________________________________________
> 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/20180529/1a5d37e0/attachment-0002.html>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180529/1a5d37e0/attachment-0003.html>

2023-06-07 18:12:17

- reply

📅 Original date posted:2018-05-28
📝 Original message:> Is there an application that requires watching for output scripts that
> doesn't also require watching for input scrips (or, less efficiently,
> input outpoints)?
>
Certain wallets may be able to use only the output script filter by using
output scripts to watch for confirmations on sent transactions, assuming
that application is the only one with access to the private keys. The
additional benefit of the input script/outpoint filter is to watch for
unexpected spends (coins getting stolen or spent from another wallet) or
transactions without a unique change or output address. I think this is a
reasonable implementation, and it would be nice to be able to download that
filter without any input elements.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180528/8fdc2ff6/attachment.html>

2023-06-07 18:12:16

- reply

📅 Original date posted:2018-05-24
📝 Original message:Greg, I've attached a graph including the input scripts.
In the top graph, we can see how the input script filter compares to the
input outpoint filter. It is definitely smaller as a result of address
reuse. The bottom graph shows the ratio over time of combining the input
prev script and output script filters vs keeping them separate. In more
recent blocks, it appears that there are decreasing savings.
On Wed, May 23, 2018 at 6:04 PM Conner Fromknecht
<conner at lightning.engineering> wrote:
> Hi all,
>
> Jimpo, thanks for looking into those stats! I had always imagined that
> there
> would be a more significant savings in having all filters in one bundle, as
> opposed to separate. These results are interesting, to say the least, and
> definitely offer us some flexibility in options for filter sharding.
>
> So far, the bulk of this discussion has centered around bandwidth. I am
> concerned, however, that splitting up the filters is at odds with the
> other
> goal of the proposal in offering improved privacy.
>
> Allowing clients to choose individual filter sets trivially exposes the
> type of
> data that client is interested in. This alone might be enough to
> fingerprint the
> function of a peer and reduce anonymity set justifying their potential
> behavior.
>
> Furthermore, if a match is encountered, and block requested, full nodes
> have
> more targeted insight into what caused a particular match. They could
> infer that
> the client received funds in a particular block, e.g., if they are only
> requesting
> output scripts.
>
> This is above and beyond the additional complexity of now syncing,
> validating,
> and managing five or six distinct header/filter-header/filter/block chains.
>
> I agree that saving on bandwidth is an important goal, but bandwidth and
> privacy
> are always seemingly at odds. Strictly comparing the bandwidth
> requirements of
> a system that heavily weighs privacy to existing ones, e.g. BIP39, that
> don't is a
> losing battle IMO.
>
> I'm not fundamentally opposed to splitting the filters, I certainly see the
> arguments for flexibility. However, I also want to ensure we are
> considering the
> second order effects that fall out of optimizing for one metric when
> others exist.
>
> Cheers,
> Conner
> On Wed, May 23, 2018 at 10:29 Gregory Maxwell via bitcoin-dev <
> bitcoin-dev at lists.linuxfoundation.org> wrote:
>
>> Any chance you could add a graph of input-scripts (instead of input
>> outpoints)?
>>
>> On Wed, May 23, 2018 at 7:38 AM, Jim Posen via bitcoin-dev
>> <bitcoin-dev at lists.linuxfoundation.org> wrote:
>> > So I checked filter sizes (as a proportion of block size) for each of
>> the
>> > sub-filters. The graph is attached.
>> >
>> > As interpretation, the first ~120,000 blocks are so small that the
>> > Golomb-Rice coding can't compress the filters that well, which is why
>> the
>> > filter sizes are so high proportional to the block size. Except for the
>> > input filter, because the coinbase input is skipped, so many of them
>> have 0
>> > elements. But after block 120,000 or so, the filter compression
>> converges
>> > pretty quickly to near the optimal value. The encouraging thing here is
>> that
>> > if you look at the ratio of the combined size of the separated filters
>> vs
>> > the size of a filter containing all of them (currently known as the
>> basic
>> > filter), they are pretty much the same size. The mean of the ratio
>> between
>> > them after block 150,000 is 99.4%. So basically, not much compression
>> > efficiently is lost by separating the basic filter into sub-filters.
>> >
>> > On Tue, May 22, 2018 at 5:42 PM, Jim Posen <jim.posen at gmail.com> wrote:
>> >>>
>> >>> My suggestion was to advertise a bitfield for each filter type the
>> node
>> >>> serves,
>> >>> where the bitfield indicates what elements are part of the filters.
>> This
>> >>> essentially
>> >>> removes the notion of decided filter types and instead leaves the
>> >>> decision to
>> >>> full-nodes.
>> >>
>> >>
>> >> I think it makes more sense to construct entirely separate filters for
>> the
>> >> different types of elements and allow clients to download only the
>> ones they
>> >> care about. If there are enough elements per filter, the compression
>> ratio
>> >> shouldn't be much worse by splitting them up. This prevents the
>> exponential
>> >> blowup in the number of filters that you mention, Johan, and it works
>> nicely
>> >> with service bits for advertising different filter types independently.
>> >>
>> >> So if we created three separate filter types, one for output scripts,
>> one
>> >> for input outpoints, and one for TXIDs, each signaled with a separate
>> >> service bit, are people good with that? Or do you think there
>> shouldn't be a
>> >> TXID filter at all, Matt? I didn't include the option of a prev output
>> >> script filter or rolling that into the block output script filter
>> because it
>> >> changes the security model (cannot be proven to be correct/incorrect
>> >> succinctly).
>> >>
>> >> Then there's the question of whether to separate or combine the
>> headers.
>> >> I'd lean towards keeping them separate because it's simpler that way.
>> >
>> >
>> >
>> > _______________________________________________
>> > bitcoin-dev mailing list
>> > bitcoin-dev at lists.linuxfoundation.org
>> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>> >
>> _______________________________________________
>> 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/20180523/fe5608eb/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: filter_sizes.svg
Type: image/svg+xml
Size: 2833873 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/fe5608eb/attachment-0001.svg>

2023-06-07 18:12:14

- reply

📅 Original date posted:2018-05-22
📝 Original message:>
> My suggestion was to advertise a bitfield for each filter type the node
> serves,
> where the bitfield indicates what elements are part of the filters. This
> essentially
> removes the notion of decided filter types and instead leaves the decision
> to
> full-nodes.
>
I think it makes more sense to construct entirely separate filters for the
different types of elements and allow clients to download only the ones
they care about. If there are enough elements per filter, the compression
ratio shouldn't be much worse by splitting them up. This prevents the
exponential blowup in the number of filters that you mention, Johan, and it
works nicely with service bits for advertising different filter types
independently.
So if we created three separate filter types, one for output scripts, one
for input outpoints, and one for TXIDs, each signaled with a separate
service bit, are people good with that? Or do you think there shouldn't be
a TXID filter at all, Matt? I didn't include the option of a prev output
script filter or rolling that into the block output script filter because
it changes the security model (cannot be proven to be correct/incorrect
succinctly).
Then there's the question of whether to separate or combine the headers.
I'd lean towards keeping them separate because it's simpler that way.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180522/328a953f/attachment-0001.html>

2023-06-07 18:12:14

- reply

📅 Original date posted:2018-05-23
📝 Original message:So I checked filter sizes (as a proportion of block size) for each of the
sub-filters. The graph is attached.
As interpretation, the first ~120,000 blocks are so small that the
Golomb-Rice coding can't compress the filters that well, which is why the
filter sizes are so high proportional to the block size. Except for the
input filter, because the coinbase input is skipped, so many of them have 0
elements. But after block 120,000 or so, the filter compression converges
pretty quickly to near the optimal value. The encouraging thing here is
that if you look at the ratio of the combined size of the separated filters
vs the size of a filter containing all of them (currently known as the
basic filter), they are pretty much the same size. The mean of the ratio
between them after block 150,000 is 99.4%. So basically, not much
compression efficiently is lost by separating the basic filter into
sub-filters.
On Tue, May 22, 2018 at 5:42 PM, Jim Posen <jim.posen at gmail.com> wrote:
> My suggestion was to advertise a bitfield for each filter type the node
>> serves,
>> where the bitfield indicates what elements are part of the filters. This
>> essentially
>> removes the notion of decided filter types and instead leaves the
>> decision to
>> full-nodes.
>>
>
> I think it makes more sense to construct entirely separate filters for the
> different types of elements and allow clients to download only the ones
> they care about. If there are enough elements per filter, the compression
> ratio shouldn't be much worse by splitting them up. This prevents the
> exponential blowup in the number of filters that you mention, Johan, and it
> works nicely with service bits for advertising different filter types
> independently.
>
> So if we created three separate filter types, one for output scripts, one
> for input outpoints, and one for TXIDs, each signaled with a separate
> service bit, are people good with that? Or do you think there shouldn't be
> a TXID filter at all, Matt? I didn't include the option of a prev output
> script filter or rolling that into the block output script filter because
> it changes the security model (cannot be proven to be correct/incorrect
> succinctly).
>
> Then there's the question of whether to separate or combine the headers.
> I'd lean towards keeping them separate because it's simpler that way.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/5a74bcf7/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: filter_sizes.svg
Type: image/svg+xml
Size: 2066101 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/5a74bcf7/attachment-0001.svg>

2023-06-07 18:12:12

- reply

📅 Original date posted:2018-05-17
📝 Original message:>
> I think lite clients cross checking is something which very likely
> will never be implemented by anyone, and probably not stay working
> (due to under-usage) if it is implemented. This thought is driven by
> three things (1) the bandwidth overhead of performing the check, (2)
> thinking about the network-interacting-state-machine complexity of it,
> and by the multitude of sanity checks that lite clients already don't
> implement (e.g. when a lite client noticed a split tip it could ask
> peers for the respective blocks and check at least the stateless
> checks, but none has ever done that), and...
>
In my opinion, it's overly pessimistic to design the protocol in an
insecure way because some light clients historically have taken shortcuts.
If the protocol can provide clients the option of getting additional
security, it should.
On the general topic, Peter makes a good point that in many cases filtering
by txid of spending transaction may be preferable to filtering by outpoint
spend, which has the nice benefit that there are obviously fewer txs in a
block than txins. This wouldn't work for malleable transactions though.
I'm open to the idea of splitting the basic filter into three separate
filters based on data type, but there are some bandwidth concerns. First,
the GCS encoding gets better compression with a greater number of elements,
though as I recall in my analysis, that starts to tail off at ~1000
elements per filter with P=20, in which case it's not as much of a concern
given current block sizes. The other is that clients need to download
and/or store the filter header chain for each filter type, which are 32
bytes each per block. So if a client is expected to download all three
filter types anyway, or even two of three, it's less efficient in these
terms. It would be possible though to split the filters themselves, but
still have the basic filter header cover all three filters. This would mean
that full nodes could not support just a subset of the basic filters --
they'd have to compute all of them to compute the filter header.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180517/c25d9cf4/attachment.html>

2023-06-07 18:12:12

- reply

📅 Original date posted:2018-05-17
📝 Original message:>
> It isn't a question of 'some lite clients' -- I am aware of no
> implementation of these kinds of measures in any cryptocurrency ever.
>
Doesn't mean there can't or shouldn't be a first. :-)
> The same kind of comparison to the block could have been done with
> BIP37 filtering, but no one has implemented that. (similarly, the
> whitepaper suggests doing that for all network rules when a
> disagreement has been seen, though that isn't practical for all
> network rules it could be done for many of them-- but again no
> implementation or AFAIK any interest in implementing that)
Correct me if I'm wrong, but I don't think it's true that the same could be
done for BIP 37. With BIP 37, one would have to download every partial
block from every peer to determine if there is a difference between them.
With BIP 157, you only download a 32 byte filter header from every peer
(because filters are deterministic), and using that commitment can
determine whether there's a conflict requiring further interrogation. The
difference in overhead makes checking for conflicts with BIP 157 practical,
whereas it's not as practical with BIP 37.
> Sure, but at what cost? And "additional" while nice doesn't
> necessarily translate into a meaningful increase in delivered security
> for any particular application.
>
> I think we might be speaking too generally here.
>
Sure. The security model that BIP 157 now allows is that a light client with*
at least one honest peer serving filters* can get the correct information
about the chain. No, this does not prevent against total eclipse attacks,
but I think it's a much stronger security guarantee than requiring all
peers or even a majority of peers to be honest. In a decentralized network
that stores money, I think there's a big difference between those security
models.
> But in exchange the filters for a given FP rate would be probably
> about half the current size (actual measurements would be needed
> because the figure depends on much scriptpubkey reuse there is, it
> probably could be anywhere between 1/3 and 2/3rd).
>
This does not seem right. Let's assume txids are removed because they are
not relevant to this particular point. The difference as I understand it is
whether to include in the filter serialized outpoints for inputs or
serialized prev scriptPubkeys for inputs. When hashed these are the same
size, and there's an equal number of them (one per input in a block). So
the only savings comes from deduping the prev scriptPubkeys with each other
and with the scriptPubkeys in the block's outputs. So it comes down
entirely to how much address reuse there is on the chain.
> Monitoring inputs by scriptPubkey vs input-txid also has a massive
> advantage for parallel filtering: You can usually known your pubkeys
> well in advance, but if you have to change what you're watching block
> N+1 for based on the txids that paid you in N you can't filter them
> in parallel.
>
Yes, I'll grant that this is a benefit of your suggestion.
> I think Peter missed Matt's point that you can monitor for a specific
> transaction's confirmation by monitoring for any of the outpoints that
> transaction contains. Because the txid commits to the outpoints there
> shouldn't be any case where the txid is knowable but (an) outpoint is
> not. Removal of the txid and monitoring for any one of the outputs
> should be a strict reduction in the false positive rate for a given
> filter size (the filter will contain strictly fewer elements and the
> client will match for the same (or usually, fewer) number).
>
> I _think_ dropping txids as matt suggests is an obvious win that costs
> nothing. Replacing inputs with scripts as I suggested has some
> trade-offs.
>
I may have interpreted this differently. So wallets need a way to know when
the transactions they send get confirmed (for obvious usability reasons and
so for automatic fee-bumping). One way is to match the spent outpoints
against the filter, which I think of as the standard. Another would be to
match the txid of the spending transaction against the first, which only
works if the transaction is not malleable. Another would be to match the
change output script against the first, assuming the wallet does not reuse
change addresses and that the spending transaction does in fact have a
change output.
Now lets say these pieces of data, txids, output scripts, and spent
outpoints are in three separate filters that a wallet can download
separately or choose not to download. The spent outpoint method is the most
reliable and has no caviats. It also allows for theft detection as Peter
notes, which is a very nice property indeed. If the wallet uses the txid
matching though, the txid filter would be smaller because there are fewer
txids per block than inputs. So there could be some bandwidth savings to
that approach. The change output watching is probably the nicest in some
ways because the client needs the output filter anyway. If the transaction
has no change output with a unique script, the client could watch for any
of the other outputs on the spending tx, but may get more false positives
depending on the degree of address reuse.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180517/01b8298f/attachment-0001.html>

2023-06-07 18:12:02

- reply

📅 Original date posted:2018-05-10
📝 Original message:That is a good observation that most of the historical data does not need
to be kept around. I believe what you are suggested is already implemented,
however. Bitcoin Core can operate in a pruned mode, where the bulk of the
historical block data is discarded and only the current UTXO set (and a few
recent blocks) are kept. As you note, some nodes on the network need to run
in archive mode to help new nodes get in sync. BIP 159 helps identify these
archive nodes at the gossip layer.
In the case of lightning, some implementations made use of the additional
txindex, which is not compatible with pruned mode.
On Wed, May 9, 2018 at 5:56 PM, Segue via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> On 3/17/18, someone posted on the Lightning-dev list, "Can I try Lightning
> without running a fully-fledged bitcoin block chain? (Yubin Ruan)." The
> inquirer was asking because he didn't have much space to store the entire
> blockchain on his laptop.
>
> I replied:
>
> "Developers,
>
> On THIS note and slightly off-topic but relevant, why can't chunks of
> blockchain peel off the backend periodically and be archived, say on
> minimum of 150 computers across 7 continents?
>
> It seems crazy to continue adding on to an increasingly long chain to
> infinity if the old chapters (i.e. more than, say, 2 years old) could be
> stored in an evenly distributed manner across the planet. The same 150
> computers would not need to store every chapter either, just the index
> would need to be widely distributed in order to reconnect with a chapter if
> needed. Then maybe it is no longer a limitation in the future for people
> like Yubin. "
>
> It was suggested by a couple of lightning developers that I post this idea
> on the bitcoin-dev list. So, here I post :).
>
> Segue
>
>
>
>
> _______________________________________________
> 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/20180509/4a7cccc7/attachment-0001.html>

2023-06-07 18:11:58

- reply

📅 Original date posted:2018-05-17
📝 Original message:>
> This brings us another theoretical problem: someone could spend our
> OP_TRUE with a low-fee non-RBF tx, and we'd not be able to use it to
> CPFP the tx. It'd be hard to do, but possible. I think the network
> benefits from using OP_TRUE (anyone can clean, and size, vs some
> only-known-to-me pubkey) outweighs the risk, but it'd be nice if OP_TRUE
> P2WSH spends were always considered RBF.
>
I believe OP_CSV with a relative locktime of 0 could be used to enforce RBF
on the spending tx?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180517/da8223c0/attachment-0001.html>

2023-06-07 18:11:45

- reply

📅 Original date posted:2018-05-01
📝 Original message:I'm still not following why this doesn't accumulate.
In the example route, let's look at it from the point of view of C. C sees
the following regardless of whether D or E or someone behind E is the last
hop in the route:
B -> HTLC(expire = X + delta) -> C -> HTLC(expire = X) -> D
So D is not required to reveal the preimage before time X, and in the case
of an on-chain settle, C needs to be able to redeem the HTLC output through
the timeout clause before time X + delta. C can't redeem the HTLC (with
sufficient confirmations) at least until the settlement transaction is
confirmed. So it seems to me that regardless of the overall route and the
maximum CSV on it, the delta for the C hop has to be greater than the CSV
delay on the update transaction. And that this must be true at every hop
for the same reason.
On Tue, May 1, 2018 at 9:29 AM, Christian Decker <decker.christian at gmail.com
> wrote:
> Jim Posen <jim.posen at gmail.com> writes:
> > Can you explain why a fixed offset along the whole circuit is enough to
> > ensure safely as opposed to an increased delta at each hop?
>
> Sure. Let's assume we have chosen a path `A->B->C->D->E`. For simplicity
> let's assume they all have a CLTV delta of 144 blocks (lnd's default
> setting). Furthermore let's assume that the CSV timeout for the channels
> is also 144.
>
> This means that with the current LN-penalty mechanism you'd have the
> following CLTV deltas in the HTLC:
>
> ```
> A -(576)-> B -(432)-> C -(288)-> D -(144)-> E
> ```
>
> Meaning that if the current time is approaching the absolute CLTV we
> need initiate a channel closure to safely fetch the preimage on-chain,
> and be able to turn around and send it on the upstream channel.
>
> This is minimal, but can be arbitrarily higher, if you follow the best
> practice of obfuscating the final destination by building a shadow route
> behind the real recipient, and add it's CLTV deltas and fees to your
> route.
>
> With eltoo you'd need to make sure that you have the settlement
> transaction confirmed before your desired CLTV timeout delta begins to
> count down. So if the CLTV of the HTLC is `now + CSV timeout + CLTV
> delta` you need to initiate a close, whereas Lightning allows you to
> wait for time `now + CLTV delta`. Effectively this results in the
> following time deltas:
>
> ```
> A -(576+144)-> B -(432+144)-> C -(288+144)-> D -(144+144)-> E
> ```
>
> Taking the last hop for example, if we had a CLTV of 1000 with eltoo
> we'd need to start closing at height 712, instead of 856 with
> LN-penalty. However, this increased delta does not accumulate along the
> path, it's just a fixed offset. The longer the route, the smaller the
> actual impact of this offset.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180501/ecea5831/attachment.html>

2023-06-07 18:11:45

- reply

📅 Original date posted:2018-05-01
📝 Original message:OK, I see what you are saying. You are effectively suggesting pipelining
the broadcasts of the update transactions. I think this introduces a
problem that a node in the circuit that withholds the preimage for too long
can force all upstream channels to be closed, at only the expense of their
one upstream channel being closed. I believe such an attack could
significantly disrupt the network.
Let me elaborate on the way I'm thinking about this:
So say I'm a routing node with an upstream HTLC with CLTV = X. I need to
ensure that if I learn the preimage, that I have time to broadcast and
confirm an HTLC-success transaction before height X. We'll call this number
of blocks D_success. So if I know the preimage, let's say X - D_success is
the latest height that I can safely broadcast the HTLC-success transaction,
assuming the settlement transaction is already final (ie. the update
transaction is confirmed and the CSV delay has passed). So now I also need
to know when to close the channel with the update transaction. I'll assume
it will take at most D_update blocks from the time I broadcast the update
transaction for it to be mined. So unless the downstream HTLC is already
failed, I should always close the upstream channel at height X - D_success
- CSV_update - D_update.
Now we'll look at the downstream HTLC with CLTV = Y. In order to minimize
the safe delta between the upstream and downstream CLTVs, I will want to
broadcast and confirm an HTLC-timeout transaction as soon after height Y as
possible. So assuming that the downstream settlement transaction is final
at height Y and it takes at most D_timeout blocks for the HTLC timeout
transaction to confirm once it is final assuming no double spends, then Y +
D_timeout is very latest I might learn the payment preimage from the
downstream channel on-chain. So I should be safe as long as X - D_success >
Y + D_timeout. This assumes that the update transaction for the downstream
channel is already mined and the CSV has passed. However, we know from
above that I had to close the upstream channel at time X - D_success -
CSV_update - D_update, which may very well be before Y. So if the
downstream hop waits until just before Y to publish the preimage, they can
force me to close my upstream channel. This applies transitively for
further upstream hops, assuming a large enough CSV value.
Granted, upstream hops can watch the blockchain for preimage reveals in
other closings transaction and perhaps fulfill off-chain if there is
sufficient time. This would not be possible with payment decorrelation
through scriptless scripts or the like.
Does that logic sound right to you?
On Tue, May 1, 2018 at 10:31 AM, Christian Decker <
decker.christian at gmail.com> wrote:
> Jim Posen <jim.posen at gmail.com> writes:
> > I'm still not following why this doesn't accumulate.
> >
> > In the example route, let's look at it from the point of view of C. C
> sees
> > the following regardless of whether D or E or someone behind E is the
> last
> > hop in the route:
> >
> > B -> HTLC(expire = X + delta) -> C -> HTLC(expire = X) -> D
> >
> > So D is not required to reveal the preimage before time X, and in the
> case
> > of an on-chain settle, C needs to be able to redeem the HTLC output
> through
> > the timeout clause before time X + delta. C can't redeem the HTLC (with
> > sufficient confirmations) at least until the settlement transaction is
> > confirmed. So it seems to me that regardless of the overall route and the
> > maximum CSV on it, the delta for the C hop has to be greater than the CSV
> > delay on the update transaction. And that this must be true at every hop
> > for the same reason.
>
> That'd be a purely reactionary behavior, i.e., chosing the delta in such
> a way that I can both settle the channel and have enough time to react
> to turn around and reveal the preimage. So with the assumptions we had
> before (CSV = 144 and CLTV delta = 144) you'd have an effective delta of
> 288 on each hop, yes. That's basically the case in which each channel
> reacts serially.
>
> You can trivially parallelize these closures by looking ahead and
> noticing that each hop really just cares about its own closure deadline,
> i.e., each node just cares to close 288 blocks before the CLTV expires,
> not that its delta w.r.t. to the downstream channel is that far in the
> future. So all we care about is that once we are due to give the
> upstream hop the preimage we've already closed the downstream channel
> and can now read the HTLC preimage from that channel.
>
> The CSV timeout isn't part of the delta on each hop, but we need to
> implement the deadline computation as:
>
> ```
> CLTV - CLTV delta - CSV
> ```
>
> instead of LN-penaltiy's
>
> ```
> CLTV - CLTV delta
> ```
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180501/91de4f67/attachment-0001.html>

2023-06-07 18:11:44

- reply

📅 Original date posted:2018-05-01
📝 Original message:Can you explain why a fixed offset along the whole circuit is enough to
ensure safely as opposed to an increased delta at each hop?
On Tue, May 1, 2018, 5:05 AM Christian Decker <decker.christian at gmail.com>
wrote:
> Jim Posen <jim.posen at gmail.com> writes:
> > If my understanding is correct though, this construction would
> > significantly increase the safe CLTV delta requirements because HTLCs
> > cannot be timed out immediately on the settlement transaction. Consider a
> > case where node B receives an HTLC from A and forwards to C. If the HTLC
> > offered to C times out and C does not fail the HTLC off-chain, Lightning
> > currently guarantees that the CLTV delta is sufficient that I may close
> the
> > channel to C on-chain and claim the timed-out HTLC before my upstream
> HTLC
> > to A times out. If the CLTV delta is too small, I may fail the upstream
> > HTLC as soon as it times out, and then C may still claim the downstream
> > HTLC with the preimage on-chain. With eltoo, when B closes the downstream
> > channel on-chain, it must wait the CSV timeout on the update transaction
> > before locking in the timed-out HTLC. This effectively means the CLTV
> delta
> > has to be greater than the CSV timeout, plus some extra (whereas it is
> > currently safe to make it significantly shorter). Is that true or am I
> > missing something?
>
> That's a good point Jim. We need to make sure that the CLTVs are far
> enough in the future for the CSV timeout to expire and to grab any
> preimage downstream and insert it upstream. Overall this results in an
> offset of all the CLTVs to (less than) the maximum CSV timeout along the
> path. This would be a fixed offset for each channel and can be announced
> using the gossip protocol, so senders can take it into consideration
> when computing the routes. Notice that this is not really the CLTV
> delta, which would accumulate along the path, but an offset on which the
> CLTV deltas build on.
>
> In today's network we have many nodes that have a CLTV delta of 144
> blocks, which quickly results in HTLC funds unavailable for several days
> depending on the route length, so I don't think that adding a fixed
> offset is much worse. Once we have watch-towers we can reduce both the
> offset as well as the CLTV deltas. Since eltoo makes watch-towers less
> expensive, given the reduced storage costs, I'd argue that it's a net
> positive for the Lightning network (but then again I'm biased) :-)
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180501/817a0ce3/attachment.html>

2023-06-07 18:11:43

- reply

📅 Original date posted:2018-04-30
📝 Original message:This construction is pretty neat and seems to solve a lot of problems. I
find the use of CLTV with past timestamps to provide ordering in particular
to be quite clever.
If my understanding is correct though, this construction would
significantly increase the safe CLTV delta requirements because HTLCs
cannot be timed out immediately on the settlement transaction. Consider a
case where node B receives an HTLC from A and forwards to C. If the HTLC
offered to C times out and C does not fail the HTLC off-chain, Lightning
currently guarantees that the CLTV delta is sufficient that I may close the
channel to C on-chain and claim the timed-out HTLC before my upstream HTLC
to A times out. If the CLTV delta is too small, I may fail the upstream
HTLC as soon as it times out, and then C may still claim the downstream
HTLC with the preimage on-chain. With eltoo, when B closes the downstream
channel on-chain, it must wait the CSV timeout on the update transaction
before locking in the timed-out HTLC. This effectively means the CLTV delta
has to be greater than the CSV timeout, plus some extra (whereas it is
currently safe to make it significantly shorter). Is that true or am I
missing something?
On Mon, Apr 30, 2018 at 8:41 AM, Christian Decker via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> (cross-posting to bitcoin-dev since this serves as motivation behind the
> sighash_noinput proposal)
>
> > TL;DR: we announce a new, simple, update mechanism for off-chain
> protocols,
> > see the announcement [1] and the paper [2] :-)
>
> A little over a year ago, the three Lightning Network implementation
> teams joined forces to work on a common specification for the protocol
> stack. Now that both that specification and our three implementations
> are becoming stable and usable, it is time to look forward: to further
> improve the protocol, to add new features, to simplify, and to fix
> downsides.
>
> One of the core innovations that enabled Lightning in the first place was
> an
> off-chain update mechanism to renegotiate a new state and ensure that the
> old
> state can not be settled on-chain. Today, we're excited to release our
> latest
> research paper on a new, simplified, update mechanism for layer 2
> protocols,
> called eltoo.
>
> eltoo is a drop-in replacement for the penalty based invalidation
> mechanism that is used today in the Lightning specification. It is
> similar in many ways to the sequence number mechanism that was already
> present in the original Bitcoin implementation. But, while sequence
> numbers were unenforceable on the blockchain, eltoo is enforceable by
> overriding subsequent states on-chain.
>
> Unlike the current mechanism used in Lightning so far, it is not penalty
> based, i.e., publishing an old state does not result in the faulty node
> to automatically lose funds, and is most similar to the duplex
> micropayment channels construction. It is a symmetric scheme, i.e., all
> participants share an identical set of transactions, and it ensures that
> the
> last agreed upon state is settled on-chain, with similar tradeoffs as
> today's Lightning (timelock vs. online requirement).
>
> eltoo addresses some of the issues we encountered while speficying and
> implementing the Lightning Network. For example outsourcing becomes very
> simple since old states becoming public can't hurt us anymore. We
> completely remove the need to estimate fees ahead of time. The
> construction allows us to attach fees when settling, and even allows for
> fees to be bumped using CPFP or RBF.
>
> Beyond Lightning, eltoo can be used as a generic update mechanism for an
> off-chain contract, for a larger number of participants. This was not
> possible in the current update mechanism since reactions to a
> misbehaving participant needed to be tailore to that participant. This
> enables other protocols such as the channel factories, and in
> combination with Schnorr signatures allows for very large off-chain
> contracts with minimal on-chain footprint.
>
> Before we can implement eltoo, we need a minor change to Bitcoin: the
> introduction of the SIGHASH_NOINPUT flag for signatures. This was first
> discussed a few months ago in the context of watchtowers to help secure
> Lightning channels, but was not formally proposed. A formal proposal may
> now be found in the eltoo paper.
>
> We invite the community to consider our proposal and to participate in
> its discussion. We hope to arrive at a consensus for the usage of
> SIGHASH_NOINPUT, so that it can be accepted and included in a future
> soft fork of Bitcoin Script. Doing so will put us on the road to a more
> reliable and simpler Lightning Network, incorporating a new update
> mechanism that can also be used for many other applications.
>
> The full official announcement can be found at [1] and the paper with the
> full
> details can be found at [2].
>
> Looking forward to the communities feedback,
> Christian
>
> [1] https://blockstream.com/2018/04/30/eltoo-next-lightning.html
> [2] https://blockstream.com/eltoo.pdf
> _______________________________________________
> 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/20180430/b6a46771/attachment-0001.html>

2023-06-07 18:11:39

- reply

📅 Original date posted:2018-04-13
📝 Original message:Why not add the outpoints owned by the wallet to the filter and watch for
those instead of elements in the input script or witness data?
On Fri, Apr 13, 2018 at 12:12 PM, Jonas Schnelli via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Hi Andreas
>
> Thanks for bringing this up and this seems indeed to be suboptimal.
>
> > I wonder if Bitcoin Core would be willing to extend the BIP37 matching
> > rules such that data elements in the witness are also matched against?
>
> Bitcoin Core is not an identity that can be „willing to extend“ (or
> reject) a feature.
> Someone needs to come up with a proposal (pull request).
>
> Maybe an extension for BIP37 would make sense (*meh*).
> Just inserting the witness data into the bloom filter seems to be an easy
> solution (CBloomFilter::IsRelevantAndUpdate())
>
> /jonas
>
> _______________________________________________
> 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/20180413/cedc5780/attachment.html>

2023-06-07 18:11:27

- reply

📅 Original date posted:2018-04-03
📝 Original message: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/89d5a284/attachment.html>

2023-06-07 18:11:25

- reply

📅 Original date posted:2018-03-29
📝 Original message:Thanks for giving it a read and for sparking the discussion with your
observation about the 40% savings from dropping prev_hash!
> Thought this wasn't effective in case overt asic boost get widely adopted,
> but then I understood that at the moment only two bits of version get
> scrambled by that technique so this looks fine, maybe add a comment about
> this so the reader doesn't get the same initial doubt I got.
>
I still need to compute for historical blocks how many could have an
omitted version. Will post back with that when I get results. If overt ASIC
Boost made this less effective, that would be unfortunate, but so be it.
> My feeling is that encoding of the headers and checkpoints/parallel
> download are separate subjects for two BIPS.
> About the checkpoints I don't grasp why they are useful since an attacker
> could lie about them but maybe I am missing something...
>
Yeah, I guess the background wasn't explained in the BIP itself. After your
original post on the mailing list, there were suggestions that instead of
modifying the format of existing messages, it would be better do create a
new headers message. And as long as we're designing a new headers message,
we should change the semantics to allow parallel download. But if you want
to download from peers in parallel, you need to get a summary of the blocks
that they have. Hence the checkpoints message. So that is why both of these
messages are in the same BIP -- only together can they perform an efficient
sync.
Regarding the reliability of the checkpoints, I think it's strictly better
than what we have now. Let's say a node is connected to 6 honest peers and
2 malicious peers. Even if the node does not know which ones are good or
bad until it validates the headers, it sees that 6 of the peers are on the
same chain, and can download those headers in parallel from 6 different
sources. So that's already a win.
Taken a step further though, I'm really interested in treating the
checkpoints as commitments to chain work and using random sampling to
detect lying peers before downloading all of their headers. So imagine you
are connected to two peers, one good one bad, where the good one claims a
chain with X total work and the bad one claims a chain with Y total work.
To determine quickly which is correct, you can randomly sample ranges of
headers and check the proofs of work to see whether it matches what the
peer claimed. So basically you pick a checkpoint at random (weighted by the
work delta) which commits to a total amount of work from the last
checkpoint, then request all headers in between. If the peer responds with
headers with the correct start hash, end hash, and start height (from the
coinbase tx of the first header), then you can be somewhat more confident
their total PoW matches the claimed amount.
How many times do you need to sample? I don't know yet, but I've heard
Benedikt Bunz is exploring this question with his research on FlyClients
[1], which was an inspiration for this.
> Bitfield allows great savings, however the encoding depends on the headers
> height a client ask for, this cause a little computational burden on the
> node and the undesirable side effect of difficult caching. Variable length
> encoding cause caching difficulties too...
> A simpler approach could be to encode the headers in groups of 2016
> headers (the difficulty period) where the first header is complete and the
> others 2015 are missing the previous hash and the difficulty, this achieve
> comparable savings ~45%, allows better caching and has fixed length
> encoding. This could be useful for the node by caching headers on a single
> file on disk and simply stream out the relative range when requested or to
> serve the same encoded headers format in other context like http,
> leveraging http caching infrastructure.
>
I don't see too much of a problem with caching. Most node implementations I
know of keep all headers in memory anyway, often in contiguous segments of
RAM for historical headers, so it should be fairly inexpensive to serve
queries. Beyond that, the response for a particular query (start_height,
end_hash, encoding version) can be cached, so if some service wants to
precompute max size responses for all start_height multiples of 1,000, they
could cache those.
-Jim
[1] https://www.youtube.com/watch?time_continue=8400&v=BPNs9EVxWrA
> 2018-03-28 1:31 GMT+02:00 Jim Posen via bitcoin-dev <bitcoin-dev at lists.
> linuxfoundation.org>:
>
>> Based on some ideas that were thrown around in this thread (
>> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/
>> 2017-December/015385.html), I have been working on a P2P extension that
>> will allow faster header sync mechanisms. The one-sentence summary is that
>> by encoding headers more efficiently (eg. omitting prev_hash) and
>> downloading evenly spaced checkpoints throughout history (say every
>> 1,000th) from all peers first, we could speed up header sync, which would
>> be a huge improvement for light clients. Here is a draft of the BIP:
>> https://github.com/jimpo/bips/blob/headers-sync/headersv2.mediawiki. The
>> full text is below as well.
>>
>> I'd love to hear any feedback people have.
>>
>> ----------------------------------------------------------
>>
>> == Abstract ==
>>
>> This BIP describes a P2P network extension enabling faster, more reliable methods for syncing the block header chain. New P2P messages are proposed as more efficient replacements for <code>getheaders</code> and <code>headers</code> during initial block download. The proposed header download protocol reduces bandwidth usage by ~40%-50% and supports downloading headers ranges from multiple peers in parallel, which is not possible with the current mechanism. This also enables sync strategies with better resistance to denial-of-service attacks.
>>
>> == Motivation ==
>>
>> Since 2015, optimized Bitcoin clients fetch all block headers before blocks themselves in order to avoid downloading ones that are not part of the most work chain. The protocol currently in use for fetching headers leaves room for further optimization, specifically by compressing header data and downloading more headers simulaneously<ref>https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015385.html</ref>. Any savings here should have a large impact given that both full nodes and light clients must sync the header chain as a first step, and that the time to validate and index the headers is negligible compared to the time spent downloading them from the network. Furthermore, some current implementations of headers syncing rely on preconfigured checkpoints to discourage attackers attempting to fill up a victim's disk space with low-work headers. The proposed messages enable sync strategies that are resilient against these types of attacks. The P2P messages are designed to be flexible, supporting multiple header sync strategies and leaving room for future innovations, while also compact.
>>
>> == Definitions ==
>>
>> ''double-SHA256'' is a hash algorithm defined by two invocations of SHA-256: <code>double-SHA256(x) = SHA256(SHA256(x))</code>.
>>
>> == Specification ==
>>
>> The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119.
>>
>> === New Structures ===
>>
>> ==== Compressed Headers ====
>>
>> Bitcoin headers are serialized by default in 80 bytes as follows:
>>
>> {| class="wikitable"
>> ! Field Name
>> ! Data Type
>> ! Byte Size
>> ! Description
>> |-
>> | version
>> | int32_t
>> | 4
>> | Block version information
>> |-
>> | prev_block
>> | uint256
>> | 32
>> | The hash of the previous block
>> |-
>> | merkle_root
>> | uint256
>> | 32
>> | The root hash of the transaction Merkle tree
>> |-
>> | timestamp
>> | uint32_t
>> | 4
>> | A Unix timestamp of the block creation time, as reported by the miner
>> |-
>> | bits
>> | uint32_t
>> | 4
>> | The calculated difficulty target for this block
>> |-
>> | nonce
>> | uint32_t
>> | 4
>> | A nonce that is set such that the header's hash matches the difficulty target
>> |}
>>
>> When deserializing a correctly-formed sequence of block headers encoded in this way, it can be noted that:
>>
>> * The prev_block field should always match the double-SHA256 hash of the previous header, making it redundant
>> * According to Bitcoin consensus rules, the bits field only changes every 2016 blocks
>> * The version often matches that of a recent ancestor block
>> * The timestamp is often a small delta from the preceding header's timestamp
>>
>> To take advantage of these possible savings, this document defines a variable-sized ''compressed encoding'' of block headers that occur in a range. Note that no savings are possible when serializing a single header; it should only be used for vectors of sequential headers. The full headers are reconstructed using data from previous headers in the range. The serialization begins with an ''encoding indicator'', which is a bitfield specifying how each field is serialized. The bits of the indicator have the following semantics:
>>
>> {| class="wikitable"
>> ! Bit Index
>> ! Reconstruction
>> ! Description
>> |-
>> | 0
>> | <code>prev_block[i] = DSHA256(header[i-1])</code>
>> | The prev_block field is ommitted and assigned to the double-SHA256 hash of the previous uncompressed header.
>> |-
>> | 1
>> | <code>nbits[i] = nbits[i-1]</code>
>> | The nbits field is omitted and matches that of the previous header.
>> |-
>> | 2
>> | <code>timestamp[i] = timestamp[i-1] + value</code>
>> | The timestamp is replaced by a 2-byte signed short int, representing an offset from the previous block's timestamp
>> |-
>> | 3
>> |
>> | Interpreted along with bits 4 & 5.
>> |-
>> | 4
>> |
>> | Interpreted along with bits 3 & 5.
>> |-
>> | 5
>> | <code>version[i] = version[i - ((bit[3] << 2) + (bit[4] << 1) + bit[5])]</code>
>> | Bits 3, 4, and 5 are first interpreted as a 3-bit offset, with bit index 3 as the most significant and bit index 5 as the least significant. If the offset is non-zero, the version field is omitted and assigned to the version of the block at the offset number of blocks prior.
>> |-
>> | 6
>> |
>> | Reserved.
>> |-
>> | 7
>> |
>> | Reserved. May be used in a future encoding version to signal another indicator byte.
>> |}
>>
>> The compressed header format is versioned by a 256-bit unsigned integer. This document defines version 0.
>>
>> ==== VarInt ====
>>
>> ''VarInt'' is a variable-length unsigned integer encoding that supports a greater range of numbers than the standard ''CompactSize''. This encoding was introduced at the database layer in Bitcoin Core<ref>https://github.com/bitcoin/bitcoin/commit/4d6144f97faf9d2a6c89f41d7d2360f21f0b71e2</ref> in 2012, but is new to the Bitcoin P2P layer.
>>
>> This definition is per the code comments in Bitcoin Core written by Pieter Wuille:
>>
>> <pre>
>> Variable-length integers: bytes are a MSB base-128 encoding of the number.
>> The high bit in each byte signifies whether another digit follows. To make
>> the encoding is one-to-one, one is subtracted from all but the last digit.
>> Thus, the byte sequence a[] with length len, where all but the last byte
>> has bit 128 set, encodes the number:
>>
>> (a[len-1] & 0x7F) + sum(i=1..len-1, 128^i*((a[len-i-1] & 0x7F)+1))
>>
>> Properties:
>> * Very small (0-127: 1 byte, 128-16511: 2 bytes, 16512-2113663: 3 bytes)
>> * Every integer has exactly one encoding
>> * Encoding does not depend on size of original integer type
>> * No redundancy: every (infinite) byte sequence corresponds to a list
>> of encoded integers.
>>
>> 0: [0x00] 256: [0x81 0x00]
>> 1: [0x01] 16383: [0xFE 0x7F]
>> 127: [0x7F] 16384: [0xFF 0x00]
>> 128: [0x80 0x00] 16511: [0x80 0xFF 0x7F]
>> 255: [0x80 0x7F] 65535: [0x82 0xFD 0x7F]
>> 2^32: [0x8E 0xFE 0xFE 0xFF 0x00]
>> </pre>
>>
>> ==== Checkpoints ====
>>
>> A ''checkpoint'' is defined for a block as a tuple of its hash and the chain work:
>>
>> {| class="wikitable"
>> ! Field Name
>> ! Data Type
>> ! Byte Size
>> ! Description
>> |-
>> | block_hash
>> | uint256
>> | 32
>> | The hash of the block
>> |-
>> | chain_work
>> | VarInt
>> | Variable(1-20)
>> | A delta between the total work in the chain at the checkpoint block and a previous checkpoint, determined by context
>> |}
>>
>> === Service Bit ===
>>
>> This BIP allocates a new service bit:
>>
>> {| class="wikitable"
>> |-
>> | NODE_HEADERS_V2
>> | <code>1 << ?</code>
>> | If enabled, the node MUST respond to <code>getcheckpts</code> and <code>getheaders2</code> queries
>> |}
>>
>> === New Messages ===
>>
>> ==== getcheckpts ====
>> <code>getcheckpts</code> is used to request block headers at a specified distance from each other which serve as checkpoints during parallel header download. The message contains the following fields:
>>
>> {| class="wikitable"
>> ! Field Name
>> ! Data Type
>> ! Byte Size
>> ! Description
>> |-
>> | block_locator
>> | uint256[]
>> | Variable
>> | A vector of block hashes in descending order by height used to identify the header chain of the requesting node
>> |-
>> | interval
>> | uint32_t
>> | 4
>> | The distance in block height between requested block hashes
>> |}
>>
>> # Nodes SHOULD NOT send <code>getcheckpts</code> unless the peer has set the <code>NODE_HEADERS_V2</code> service bit
>> # The hashes in <code>block_locator</code> MUST be in descending order by block height
>> # The block locator SHOULD be generated as it is in <code>getheaders</code> requests
>> # The receiving node MUST respond to valid requests with a <code>checkpts</code> response where the interval is the same as in the request and the first checkpoint hash matches the first common block hash in the block locator
>>
>> ==== checkpts ====
>> <code>checkpts</code> is sent in response to <code>getcheckpts</code>, listing block hashes at the specified interval. The message contains the following fields:
>>
>> {| class="wikitable"
>> ! Field Name
>> ! Data Type
>> ! Byte Size
>> ! Description
>> |-
>> | start_height
>> | uint32_t
>> | 4
>> | The height of the first block in the active chain matching the request's block locator
>> |-
>> | end_height
>> | uint32_t
>> | 4
>> | The height of the last block in the active chain
>> |-
>> | start_checkpoint
>> | Checkpoint
>> | 48
>> | The checkpoint structure for the block in the active chain at height start_height
>> |-
>> | end_checkpoint
>> | Checkpoint
>> | 48
>> | The checkpoint structure for the block in the active chain at height end_height
>> |-
>> | interval
>> | uint32_t
>> | 4
>> | The distance in block height between checkpoints
>> |-
>> | checkpoints_length
>> | CompactSize
>> | Variable(1-5)
>> | The number of checkpoints to follow
>> |-
>> | checkpoints
>> | Checkpoint[]
>> | checkoints_length * Variable(33-52)
>> | The checkpoints as specified below
>> |}
>>
>> # The interval SHOULD match the field in the <code>getcheckpts</code> request
>> # The start_checkpoint SHOULD correspond to the first block hash in the locator from the <code>getcheckpts</code> request that is part of the active chain
>> # The end_checkpoint SHOULD correspond to the tip of the node's active chain
>> # The start_height MOST be set to the block height of the start_checkpoint
>> # The end_height MOST be set to the block height of the end_checkpoint
>> # If the interval is zero, the checkpoints vector MUST be empty
>> # If the interval is non-zero, checkpoints MUST correspond to blocks on the active chain between the start_checkpoint and the end_checkpoint (exclusive), where the difference in block height between each entry and the previous one is equal to the interval
>> # The checkpoints_length MUST be less than or equal to 2,000
>> # The node SHOULD include as many checkpoints on its active chain as are available, up to the limit of 2,000
>> # The chain_work field in the first checkpoint MUST be the total work in the chain ending at that block
>> # The chain_work field in each subsequent checkpoint MUST be the difference in chain work between that block and the previous checkpoint
>> # The chain_work field in each checkpoint MUST be a properly-encoded VarInt, not exceeding 20 bytes
>>
>> ==== getheaders2 ====
>> <code>getheaders2</code> is used to request compressed headers for a range of blocks. The message contains the following fields:
>>
>> {| class="wikitable"
>> ! Field Name
>> ! Data Type
>> ! Byte Size
>> ! Description
>> |-
>> | max_version
>> | uint8_t
>> | 1
>> | The maximum supported encoding version of the headers
>> |-
>> | flags
>> | uint8_t
>> | 1
>> | A bitfield of message encoding flags
>> |-
>> | start_height
>> | uint32_t
>> | 4
>> | The height of the first block header in the requested range
>> |-
>> | end_hash
>> | uint256
>> | 32
>> | The hash of the last block header in the requested range
>> |}
>>
>> # Nodes SHOULD NOT send <code>getheaders2</code> unless the peer has set the <code>NODE_HEADERS_V2</code> service bit
>> # The height of the block with hash end_hash MUST be greater than or equal to start_height, and the difference MUST be strictly less than 3,000
>> # The end_hash SHOULD match one in a previously received <code>checkpts</code> message, otherwise the receiving node MAY disconnect
>> # The 0th bit (least significant order) of the flags field MAY be set to request the coinbase transaction and merkle branch for the block at height start_height
>>
>> ==== headers2 ====
>> <code>headers2</code> is sent in response to <code>getheaders2</code>, listing the compressed headers in the requested range. The message contains the following fields:
>>
>> {| class="wikitable"
>> ! Field Name
>> ! Data Type
>> ! Byte Size
>> ! Description
>> |-
>> | version
>> | uint8_t
>> | 1
>> | The encoding version of the headers
>> |-
>> | flags
>> | uint8_t
>> | 1
>> | A bitfield of message encoding flags
>> |-
>> | start_height
>> | uint32_t
>> | 4
>> | The height of the first block header returned
>> |-
>> | headers_length
>> | CompactSize
>> | 1-3
>> | The number of block headers to follow
>> |-
>> | headers
>> | CompressedHeader[]
>> | Variable
>> | The compressed block headers
>> |-
>> | start_block_coinbase_tx
>> | CTransaction
>> | Variable
>> | The coinbase transaction in the block at start_height
>> |-
>> | start_block_coinbase_branch
>> | uint256[]
>> | Variable
>> | A merkle branch linking the coinbase transaction in the block at start_height to its header
>> |}
>>
>> # The version MUST be less than or equal to the max_version field of the <code>getheaders2</code> request
>> # Any bits set in the flags field of the <code>getheaders2</code> request MAY be set in the response field
>> # Any bits not set in the flags field of the <code>getheaders2</code> request MUST NOT be set in the response field
>> # The first header MUST be encoded with a 0-byte indicator (ie. the header is uncompressed)
>> # start_height MUST be set to the block height of the first header
>> # The hash of the last block SHOULD equal the end_hash of the <code>getheaders2</code> request, ''even if the block is no longer part of the active chain''
>> # The length of the headers vector MUST be less than or equal to 3,000
>> # The headers MUST be sequential in order of height, with each header a successor of the previous one
>> # Each header SHOULD be optimally compressed
>> # The start_block_coinbase_tx should be the serialized coinbase transaction in the block corresponding to the first header
>> # The start_block_coinbase_branch should be a vector of right-hand-side hashes in the merkle branch linking the coinbase transaction to the first header, in order from bottom of the tree to top
>> # If the 0th bit (least significant order) of the flags field is unset, the start_block_coinbase_tx and start_block_coinbase_branch fields MUST be omitted
>>
>> === Sync Strategies ===
>>
>> The general header sync protocol for clients now is to first request checkpoints from all peers with <code>getcheckpts</code>, then decide which peers to fetch ranges of headers from and download them with <code>getheaders2</code>.
>>
>> ==== Forward Sequential Syncing ====
>>
>> Similar to the current sync protocol, a client may choose one peer to download headers from, then fetch them in forward sequential order. Once this peer is out of headers, the client performs the same routine with any peers offering more headers.
>>
>> With this strategy, the client is able to fully validate the block headers in order and abort if the peer serves an invalid one. On the other hand, the peer may be able to serve a longer, lower-work chain than the global active chain, wasting the client's time, memory, and storage space.
>>
>> ==== Parallel Header Download ====
>>
>> In order to increase the throughput of header downloads, a node may download multiple header ranges in parallel from all peers serving the same checkpoints, then validate them in sequential order.
>>
>> ==== Random Sampling Proof-of-Work ====
>>
>> Similar the FlyClient<ref>https://www.youtube.com/watch?time_continue=8400&v=BPNs9EVxWrA</ref> header download protocol, clients can select the peer claiming the greatest total work chain and use random sampling to efficiently determine if the peer is likely to be reporting its chain work honestly.
>>
>> The client treats the checkpoint message as a commitment to chain work of intermediate ranges of headers, the client then randomly samples ranges of headers weighted by total work to determine whether the total chain work is valid before downloading all headers. To defend against malicious peers attempting to reuse earlier headers later in the chain to fake greater total work, the client should check the block height in the coinbase transaction for all headers after the BIP 34 activation height. If the peer is found to be dishonest, they can be banned before the client downloads too many headers, otherwise the client chooses this as the primary sync peer for forward sequential sync or parallel download.
>>
>> == Rationale ==
>>
>> * '''Why include the coinbase transaction in the headers messages?''' The primary reason is that after BIP 34<ref>https://github.com/bitcoin/bips/blob/master/bip-0034.mediawiki</ref> activation at block height 227,835, coinbase transactions constitute cryptographic commitments to a block's height in the chain, which mitigates certain attacks during header sync. Furthermore, the <code>getheaders2</code> message can be used as a simple way of requesting a coinbase transaction for a single header, which may be independently useful.
>>
>> * '''Why not omit nBits entirely?''' The compression is designed to permit full decompression of all headers in a <code>headers2</code> message ''without'' requiring any other chain context. This is desirable so that proofs of work may be validated for arbitrary header ranges. While nBits can be computed knowing previous headers, this requires block headers that may not be sent in the same message.
>>
>> == Compatibility ==
>>
>> This is backwards compatible, as it defines new P2P messages which are available if a service bit is signaled. There are no changes to consensus rules.
>>
>> == Acknowledgements ==
>>
>> Thanks to Gregory Maxwell for suggestions on the compressed header encoding and the DOS-resistant sync strategies. Thanks to Suhas Daftuar for helpful discussions.
>>
>> Credit for the VarInt encoding goes to Pieter Wuille.
>>
>>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>>
>
>
> --
> Riccardo Casatta - @RCasatta <https://twitter.com/RCasatta>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180329/4817a551/attachment-0001.html>

2023-06-07 18:11:23

- reply

📅 Original date posted:2018-03-27
📝 Original message:Based on some ideas that were thrown around in this thread (
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015385.html),
I have been working on a P2P extension that will allow faster header sync
mechanisms. The one-sentence summary is that by encoding headers more
efficiently (eg. omitting prev_hash) and downloading evenly spaced
checkpoints throughout history (say every 1,000th) from all peers first, we
could speed up header sync, which would be a huge improvement for light
clients. Here is a draft of the BIP:
https://github.com/jimpo/bips/blob/headers-sync/headersv2.mediawiki. The
full text is below as well.
I'd love to hear any feedback people have.
----------------------------------------------------------
== Abstract ==
This BIP describes a P2P network extension enabling faster, more
reliable methods for syncing the block header chain. New P2P messages
are proposed as more efficient replacements for
<code>getheaders</code> and <code>headers</code> during initial block
download. The proposed header download protocol reduces bandwidth
usage by ~40%-50% and supports downloading headers ranges from
multiple peers in parallel, which is not possible with the current
mechanism. This also enables sync strategies with better resistance to
denial-of-service attacks.
== Motivation ==
Since 2015, optimized Bitcoin clients fetch all block headers before
blocks themselves in order to avoid downloading ones that are not part
of the most work chain. The protocol currently in use for fetching
headers leaves room for further optimization, specifically by
compressing header data and downloading more headers
simulaneously<ref>https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015385.html</ref>.
Any savings here should have a large impact given that both full nodes
and light clients must sync the header chain as a first step, and that
the time to validate and index the headers is negligible compared to
the time spent downloading them from the network. Furthermore, some
current implementations of headers syncing rely on preconfigured
checkpoints to discourage attackers attempting to fill up a victim's
disk space with low-work headers. The proposed messages enable sync
strategies that are resilient against these types of attacks. The P2P
messages are designed to be flexible, supporting multiple header sync
strategies and leaving room for future innovations, while also
compact.
== Definitions ==
''double-SHA256'' is a hash algorithm defined by two invocations of
SHA-256: <code>double-SHA256(x) = SHA256(SHA256(x))</code>.
== Specification ==
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119.
=== New Structures ===
==== Compressed Headers ====
Bitcoin headers are serialized by default in 80 bytes as follows:
{| class="wikitable"
! Field Name
! Data Type
! Byte Size
! Description
|-
| version
| int32_t
| 4
| Block version information
|-
| prev_block
| uint256
| 32
| The hash of the previous block
|-
| merkle_root
| uint256
| 32
| The root hash of the transaction Merkle tree
|-
| timestamp
| uint32_t
| 4
| A Unix timestamp of the block creation time, as reported by the miner
|-
| bits
| uint32_t
| 4
| The calculated difficulty target for this block
|-
| nonce
| uint32_t
| 4
| A nonce that is set such that the header's hash matches the difficulty target
|}
When deserializing a correctly-formed sequence of block headers
encoded in this way, it can be noted that:
* The prev_block field should always match the double-SHA256 hash of
the previous header, making it redundant
* According to Bitcoin consensus rules, the bits field only changes
every 2016 blocks
* The version often matches that of a recent ancestor block
* The timestamp is often a small delta from the preceding header's timestamp
To take advantage of these possible savings, this document defines a
variable-sized ''compressed encoding'' of block headers that occur in
a range. Note that no savings are possible when serializing a single
header; it should only be used for vectors of sequential headers. The
full headers are reconstructed using data from previous headers in the
range. The serialization begins with an ''encoding indicator'', which
is a bitfield specifying how each field is serialized. The bits of the
indicator have the following semantics:
{| class="wikitable"
! Bit Index
! Reconstruction
! Description
|-
| 0
| <code>prev_block[i] = DSHA256(header[i-1])</code>
| The prev_block field is ommitted and assigned to the double-SHA256
hash of the previous uncompressed header.
|-
| 1
| <code>nbits[i] = nbits[i-1]</code>
| The nbits field is omitted and matches that of the previous header.
|-
| 2
| <code>timestamp[i] = timestamp[i-1] + value</code>
| The timestamp is replaced by a 2-byte signed short int, representing
an offset from the previous block's timestamp
|-
| 3
|
| Interpreted along with bits 4 & 5.
|-
| 4
|
| Interpreted along with bits 3 & 5.
|-
| 5
| <code>version[i] = version[i - ((bit[3] << 2) + (bit[4] << 1) +
bit[5])]</code>
| Bits 3, 4, and 5 are first interpreted as a 3-bit offset, with bit
index 3 as the most significant and bit index 5 as the least
significant. If the offset is non-zero, the version field is omitted
and assigned to the version of the block at the offset number of
blocks prior.
|-
| 6
|
| Reserved.
|-
| 7
|
| Reserved. May be used in a future encoding version to signal another
indicator byte.
|}
The compressed header format is versioned by a 256-bit unsigned
integer. This document defines version 0.
==== VarInt ====
''VarInt'' is a variable-length unsigned integer encoding that
supports a greater range of numbers than the standard ''CompactSize''.
This encoding was introduced at the database layer in Bitcoin
Core<ref>https://github.com/bitcoin/bitcoin/commit/4d6144f97faf9d2a6c89f41d7d2360f21f0b71e2</ref>
in 2012, but is new to the Bitcoin P2P layer.
This definition is per the code comments in Bitcoin Core written by
Pieter Wuille:
<pre>
Variable-length integers: bytes are a MSB base-128 encoding of the number.
The high bit in each byte signifies whether another digit follows. To make
the encoding is one-to-one, one is subtracted from all but the last digit.
Thus, the byte sequence a[] with length len, where all but the last byte
has bit 128 set, encodes the number:
(a[len-1] & 0x7F) + sum(i=1..len-1, 128^i*((a[len-i-1] & 0x7F)+1))
Properties:
* Very small (0-127: 1 byte, 128-16511: 2 bytes, 16512-2113663: 3 bytes)
* Every integer has exactly one encoding
* Encoding does not depend on size of original integer type
* No redundancy: every (infinite) byte sequence corresponds to a list
of encoded integers.
0: [0x00] 256: [0x81 0x00]
1: [0x01] 16383: [0xFE 0x7F]
127: [0x7F] 16384: [0xFF 0x00]
128: [0x80 0x00] 16511: [0x80 0xFF 0x7F]
255: [0x80 0x7F] 65535: [0x82 0xFD 0x7F]
2^32: [0x8E 0xFE 0xFE 0xFF 0x00]
</pre>
==== Checkpoints ====
A ''checkpoint'' is defined for a block as a tuple of its hash and the
chain work:
{| class="wikitable"
! Field Name
! Data Type
! Byte Size
! Description
|-
| block_hash
| uint256
| 32
| The hash of the block
|-
| chain_work
| VarInt
| Variable(1-20)
| A delta between the total work in the chain at the checkpoint block
and a previous checkpoint, determined by context
|}
=== Service Bit ===
This BIP allocates a new service bit:
{| class="wikitable"
|-
| NODE_HEADERS_V2
| <code>1 << ?</code>
| If enabled, the node MUST respond to <code>getcheckpts</code> and
<code>getheaders2</code> queries
|}
=== New Messages ===
==== getcheckpts ====
<code>getcheckpts</code> is used to request block headers at a
specified distance from each other which serve as checkpoints during
parallel header download. The message contains the following fields:
{| class="wikitable"
! Field Name
! Data Type
! Byte Size
! Description
|-
| block_locator
| uint256[]
| Variable
| A vector of block hashes in descending order by height used to
identify the header chain of the requesting node
|-
| interval
| uint32_t
| 4
| The distance in block height between requested block hashes
|}
# Nodes SHOULD NOT send <code>getcheckpts</code> unless the peer has
set the <code>NODE_HEADERS_V2</code> service bit
# The hashes in <code>block_locator</code> MUST be in descending order
by block height
# The block locator SHOULD be generated as it is in
<code>getheaders</code> requests
# The receiving node MUST respond to valid requests with a
<code>checkpts</code> response where the interval is the same as in
the request and the first checkpoint hash matches the first common
block hash in the block locator
==== checkpts ====
<code>checkpts</code> is sent in response to <code>getcheckpts</code>,
listing block hashes at the specified interval. The message contains
the following fields:
{| class="wikitable"
! Field Name
! Data Type
! Byte Size
! Description
|-
| start_height
| uint32_t
| 4
| The height of the first block in the active chain matching the
request's block locator
|-
| end_height
| uint32_t
| 4
| The height of the last block in the active chain
|-
| start_checkpoint
| Checkpoint
| 48
| The checkpoint structure for the block in the active chain at height
start_height
|-
| end_checkpoint
| Checkpoint
| 48
| The checkpoint structure for the block in the active chain at height
end_height
|-
| interval
| uint32_t
| 4
| The distance in block height between checkpoints
|-
| checkpoints_length
| CompactSize
| Variable(1-5)
| The number of checkpoints to follow
|-
| checkpoints
| Checkpoint[]
| checkoints_length * Variable(33-52)
| The checkpoints as specified below
|}
# The interval SHOULD match the field in the <code>getcheckpts</code> request
# The start_checkpoint SHOULD correspond to the first block hash in
the locator from the <code>getcheckpts</code> request that is part of
the active chain
# The end_checkpoint SHOULD correspond to the tip of the node's active chain
# The start_height MOST be set to the block height of the start_checkpoint
# The end_height MOST be set to the block height of the end_checkpoint
# If the interval is zero, the checkpoints vector MUST be empty
# If the interval is non-zero, checkpoints MUST correspond to blocks
on the active chain between the start_checkpoint and the
end_checkpoint (exclusive), where the difference in block height
between each entry and the previous one is equal to the interval
# The checkpoints_length MUST be less than or equal to 2,000
# The node SHOULD include as many checkpoints on its active chain as
are available, up to the limit of 2,000
# The chain_work field in the first checkpoint MUST be the total work
in the chain ending at that block
# The chain_work field in each subsequent checkpoint MUST be the
difference in chain work between that block and the previous
checkpoint
# The chain_work field in each checkpoint MUST be a properly-encoded
VarInt, not exceeding 20 bytes
==== getheaders2 ====
<code>getheaders2</code> is used to request compressed headers for a
range of blocks. The message contains the following fields:
{| class="wikitable"
! Field Name
! Data Type
! Byte Size
! Description
|-
| max_version
| uint8_t
| 1
| The maximum supported encoding version of the headers
|-
| flags
| uint8_t
| 1
| A bitfield of message encoding flags
|-
| start_height
| uint32_t
| 4
| The height of the first block header in the requested range
|-
| end_hash
| uint256
| 32
| The hash of the last block header in the requested range
|}
# Nodes SHOULD NOT send <code>getheaders2</code> unless the peer has
set the <code>NODE_HEADERS_V2</code> service bit
# The height of the block with hash end_hash MUST be greater than or
equal to start_height, and the difference MUST be strictly less than
3,000
# The end_hash SHOULD match one in a previously received
<code>checkpts</code> message, otherwise the receiving node MAY
disconnect
# The 0th bit (least significant order) of the flags field MAY be set
to request the coinbase transaction and merkle branch for the block at
height start_height
==== headers2 ====
<code>headers2</code> is sent in response to <code>getheaders2</code>,
listing the compressed headers in the requested range. The message
contains the following fields:
{| class="wikitable"
! Field Name
! Data Type
! Byte Size
! Description
|-
| version
| uint8_t
| 1
| The encoding version of the headers
|-
| flags
| uint8_t
| 1
| A bitfield of message encoding flags
|-
| start_height
| uint32_t
| 4
| The height of the first block header returned
|-
| headers_length
| CompactSize
| 1-3
| The number of block headers to follow
|-
| headers
| CompressedHeader[]
| Variable
| The compressed block headers
|-
| start_block_coinbase_tx
| CTransaction
| Variable
| The coinbase transaction in the block at start_height
|-
| start_block_coinbase_branch
| uint256[]
| Variable
| A merkle branch linking the coinbase transaction in the block at
start_height to its header
|}
# The version MUST be less than or equal to the max_version field of
the <code>getheaders2</code> request
# Any bits set in the flags field of the <code>getheaders2</code>
request MAY be set in the response field
# Any bits not set in the flags field of the <code>getheaders2</code>
request MUST NOT be set in the response field
# The first header MUST be encoded with a 0-byte indicator (ie. the
header is uncompressed)
# start_height MUST be set to the block height of the first header
# The hash of the last block SHOULD equal the end_hash of the
<code>getheaders2</code> request, ''even if the block is no longer
part of the active chain''
# The length of the headers vector MUST be less than or equal to 3,000
# The headers MUST be sequential in order of height, with each header
a successor of the previous one
# Each header SHOULD be optimally compressed
# The start_block_coinbase_tx should be the serialized coinbase
transaction in the block corresponding to the first header
# The start_block_coinbase_branch should be a vector of
right-hand-side hashes in the merkle branch linking the coinbase
transaction to the first header, in order from bottom of the tree to
top
# If the 0th bit (least significant order) of the flags field is
unset, the start_block_coinbase_tx and start_block_coinbase_branch
fields MUST be omitted
=== Sync Strategies ===
The general header sync protocol for clients now is to first request
checkpoints from all peers with <code>getcheckpts</code>, then decide
which peers to fetch ranges of headers from and download them with
<code>getheaders2</code>.
==== Forward Sequential Syncing ====
Similar to the current sync protocol, a client may choose one peer to
download headers from, then fetch them in forward sequential order.
Once this peer is out of headers, the client performs the same routine
with any peers offering more headers.
With this strategy, the client is able to fully validate the block
headers in order and abort if the peer serves an invalid one. On the
other hand, the peer may be able to serve a longer, lower-work chain
than the global active chain, wasting the client's time, memory, and
storage space.
==== Parallel Header Download ====
In order to increase the throughput of header downloads, a node may
download multiple header ranges in parallel from all peers serving the
same checkpoints, then validate them in sequential order.
==== Random Sampling Proof-of-Work ====
Similar the FlyClient<ref>https://www.youtube.com/watch?time_continue=8400&v=BPNs9EVxWrA</ref>
header download protocol, clients can select the peer claiming the
greatest total work chain and use random sampling to efficiently
determine if the peer is likely to be reporting its chain work
honestly.
The client treats the checkpoint message as a commitment to chain work
of intermediate ranges of headers, the client then randomly samples
ranges of headers weighted by total work to determine whether the
total chain work is valid before downloading all headers. To defend
against malicious peers attempting to reuse earlier headers later in
the chain to fake greater total work, the client should check the
block height in the coinbase transaction for all headers after the BIP
34 activation height. If the peer is found to be dishonest, they can
be banned before the client downloads too many headers, otherwise the
client chooses this as the primary sync peer for forward sequential
sync or parallel download.
== Rationale ==
* '''Why include the coinbase transaction in the headers messages?'''
The primary reason is that after BIP
34<ref>https://github.com/bitcoin/bips/blob/master/bip-0034.mediawiki</ref>
activation at block height 227,835, coinbase transactions constitute
cryptographic commitments to a block's height in the chain, which
mitigates certain attacks during header sync. Furthermore, the
<code>getheaders2</code> message can be used as a simple way of
requesting a coinbase transaction for a single header, which may be
independently useful.
* '''Why not omit nBits entirely?''' The compression is designed to
permit full decompression of all headers in a <code>headers2</code>
message ''without'' requiring any other chain context. This is
desirable so that proofs of work may be validated for arbitrary header
ranges. While nBits can be computed knowing previous headers, this
requires block headers that may not be sent in the same message.
== Compatibility ==
This is backwards compatible, as it defines new P2P messages which are
available if a service bit is signaled. There are no changes to
consensus rules.
== Acknowledgements ==
Thanks to Gregory Maxwell for suggestions on the compressed header
encoding and the DOS-resistant sync strategies. Thanks to Suhas
Daftuar for helpful discussions.
Credit for the VarInt encoding goes to Pieter Wuille.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180327/65c9ed79/attachment-0001.html>

2023-06-07 18:11:13

- reply

📅 Original date posted:2018-03-15
📝 Original message:I like this proposal, it seems sufficiently general.
How are scripts with OP_CLTV and OP_CSV handled by verifiers? Do they
always succeed? Or should an nLockTime and nSequence also be included in
the proof in a way that can be parsed out and displayed to verifiers?
I assume any signatures in the scriptSig/witness data would have no sighash
type?
On Wed, Mar 14, 2018 at 8:01 PM, Karl Johan Alm via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> On Wed, Mar 14, 2018 at 5:46 AM, Kalle Rosenbaum <kalle at rosenbaum.se>
> wrote:
> > I can't really see from your proposal if you had thought of this: A soft
> > fork can make old nodes accept invalid message signatures as valid. For
> > example, a "signer" can use a witness version unknown to the verifier to
> > fool the verifier. Witness version is detectable (just reject unknown
> > witness versions) but there may be more subtle changes. Segwit was not
> > "detectable" in that way, for example.
> >
> > This is the reason why I withdrew BIP120. If you have thought about the
> > above, I'd be very interested.
>
> I'm not sure I see the problem. The scriptPubKey is derived directly
> from the address in all cases, which means the unknown witness version
> would have to be committed to in the address itself.
>
> So yeah, I can make a P2SH address with a witness version > 0 and a to
> me unknown pubkey and then fool you into thinking I own it, but I
> don't really see why you'd ultimately care. In other words, if I can
> SPEND funds sent to that address today, I can prove that I can spend
> today, which is the purpose of the tool, I think.
>
> For the case where the witness version HAS been upgraded, the above
> still applies, but I'm not sure it's a big issue. And it doesn't
> really require an old node. I just need to set witness version >
> current witness version and the problem applies to all nodes.
>
> On Wed, Mar 14, 2018 at 8:36 AM, Luke Dashjr <luke at dashjr.org> wrote:
> > I don't see a need for a new RPC interface, just a new signature format.
>
> All right.
>
> > Ideally, it should support not only just "proof I receive at this
> address",
> > but also "proof of funds" (as a separate feature) since this is a popular
> > misuse of the current message signing (which doesn't actually prove
> funds at
> > all). To do this, it needs to be capable of signing for multiple inputs.
>
> I assume by inputs you mean addresses/keys. The address field could
> optionally be an array. That'd be enough?
>
> > Preferably, it should also avoid disclosing the public key for existing
> or
> > future UTXOs. But I don't think it's possible to avoid this without
> something
> > MAST-like first. Perhaps it can be a MAST upgrade later on, but the new
> > signature scheme should probably be designed with it in mind.
>
> I'd love to not have to reveal the public key, but I'm not sure how it
> would be done, even with MAST.
>
> On Wed, Mar 14, 2018 at 12:12 PM, Anthony Towns <aj at erisian.com.au> wrote:
> > Wouldn't it be sufficient for old nodes to check for standardness of the
> spending script and report non-standard scripts as either invalid outright,
> or at least highly questionable? That should prevent confusion as long as
> soft forks are only making nonstandard behaviours invalid.
>
> That seems sensible to me. A warning would probably be useful, in case
> the verifier is running old software.
>
> -Kalle.
> _______________________________________________
> 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/20180314/0281bc39/attachment-0001.html>

2023-06-07 18:08:46

- reply

📅 Original date posted:2017-12-15
📝 Original message:One of the ideas that Greg Maxwell brought up in the "'Compressed' headers
stream" thread is the possibility of a header sync mechanism that allowed
parallel download from multiple peers. With the current getheaders/headers
semantics, headers must be downloaded sequentially from genesis. In my
testing, I saw that syncing headers directly from a colocated node took <5s
whereas syncing normally from network peers takes ~5 min for me, which goes
to show that 5s is an upper bound on the time to process all headers if
they are locally available. So if we can introduce new p2p messages for
header sync, what would they look like? Here's one idea.
A new getheadersv2 request would include a start height for the range of
headers requested and a commitment to the last block in the chain that you
want to download. Then you find N peers that are all on the same chain,
partition the range of headers from 0 to the chain height minus some
reasonable reorg safety buffer (~6 blocks), and send download requests in
parallel. So how do we know that the peers are on the same chain and that
their headers served connect into this chain?
When you connect to outbound peers and are in IBD, you will query them for
a Merkle Mountain Range commitment to all headers up to a height X (which
is 6ish blocks before their start height from the version message). Then
you choose the commitment that the majority of the queried peers sent (or
some other heuristic), and these become your download peers. Every
getheadersv2 request includes the start height, X, and the chain
commitment. The headersv2 response messages include all of the headers
followed by a merkle branch linking the last header into the chain
commitment. Headers are processed in order as they arrive and if any of the
headers are invalid, you can ban/disconnect all peers that committed to it,
drop the buffer of later headers and start over.
That's the basic idea. Here are other details:
- This would require an additional 32-byte MMR commitment for each header
in memory.
- When a node receives a headersv2 request and constructs a merkle proof
for the last header, it checks against the sent commitment. In the case of
a really deep reorg, that check would fail, and the node can instead
respond with an updated commitment hash for that height.
- Another packet is needed, getheaderchain or something, that a syncing
peer first sends along with a header locator and an end height. The peer
responds with headerchain, which includes the last common header from the
locator along with the chain commitment at that height and a merkle branch
proving inclusion of that header in the chain.
- Nodes would cache chain commitments for the last ~20 blocks (somewhat
arbitrary), and refuse to serve chain commitments for heights before that.
Thoughts? This is a pretty recycled idea, so please point me at prior
proposals that are similar as well.
-jimpo
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20171215/267e7064/attachment-0001.html>