Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

[Karl-Johan Alm via bitcoin-dev]

On Tue, Jun 5, 2018 at 10:08 AM, Jim Posen  wrote:
> 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.

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.

-Kalle.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

[Jim Posen via bitcoin-dev]

>
> 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.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP proposal - Dandelion: Privacy Preserving Transaction Propagation

[Bradley Denby via bitcoin-dev]

Hello all,

We now have an arXiv preprint of our latest findings available, which
provides additional details regarding Dandelion:
https://arxiv.org/pdf/1805.11060.pdf

Note that Dandelion's precision guarantees are at the population level,
while the recall guarantees can be interpreted as individual guarantees.
Expected recall is equivalent to the probability of an adversary
associating a single transaction with a given source.

Since these guarantees are probabilistic, a node cannot be sure whether all
of its peers are monitoring it. Dandelion does not protect against these
adversaries, and individuals who are worried about targeted deanonymization
should still use Tor.

One way to conceptualize Dandelion is as a "public health" fix or an
"anonymity vaccination." Higher adoption leads to greater benefits, even
for those who are not using Tor. Individuals who adopt Dandelion benefit
because their transactions make at least one hop before diffusing (or more
as adoption increases).

Nevertheless, the probabilistic nature of the guarantees means that they
are not absolute. We have shown that any solution based only on routing
cannot be absolute due to fundamental lower bounds on precision and recall.

Thank you to Eric Voskuil, Pieter Wuille, Suhas Daftuar, Christian Decker,
and Tim Ruffing for the recent feedback!

On Thu, May 10, 2018 at 8:59 AM, Bradley Denby  wrote:

> Hi all,
>
> We're writing with an update on the Dandelion project. As a reminder,
> Dandelion
> is a practical, lightweight privacy solution that provides Bitcoin users
> formal
> anonymity guarantees. While other privacy solutions aim to protect
> individual
> users, Dandelion protects privacy by limiting the capability of
> adversaries to
> deanonymize the entire network.
>
> Bitcoin's transaction spreading protocol is vulnerable to deanonymization
> attacks. When a node generates a transaction without Dandelion, it
> transmits
> that transaction to its peers with independent, exponential delays. This
> approach, known as diffusion in academia, allows network adversaries to
> link
> transactions to IP addresses.
>
> Dandelion prevents this class of attacks by sending transactions over a
> randomly
> selected path before diffusion. Transactions travel along this path during
> the
> "stem phase" and are then diffused during the "fluff phase" (hence the name
> Dandelion). We have shown that this routing protocol provides near-optimal
> anonymity guarantees among schemes that do not introduce additional
> encryption
> mechanisms.
>
> Since the last time we contacted the list, we have:
>  - Completed additional theoretical analysis and simulations
>  - Built a working prototype
>(https://github.com/mablem8/bitcoin/tree/dandelion)
>  - Built a test suite for the prototype
>(https://github.com/mablem8/bitcoin/blob/dandelion/test/fun
> ctional/p2p_dandelion.py)
>  - Written detailed documentation for the new implementation
>(https://github.com/mablem8/bips/blob/master/bip-dandelion/
> dandelion-reference-documentation.pdf)
>
> Among other things, one question we've addressed in our additional
> analysis is
> how to route messages during the stem phase. For example, if two Dandelion
> transactions arrive at a node from different inbound peers, to which
> Dandelion
> destination(s) should these transactions be sent? We have found that some
> choices are much better than others.
>
> Consider the case in which each Dandelion transaction is forwarded to a
> Dandelion destination selected uniformly at random. We have shown that this
> approach results in a fingerprint attack allowing network-level botnet
> adversaries to achieve total deanonymization of the P2P network after
> observing
> less than ten transactions per node.
>
> To avoid this issue, we suggest "per-inbound-edge" routing. Each inbound
> peer is
> assigned a particular Dandelion destination. Each Dandelion transaction
> that
> arrives via this peer is forwarded to the same Dandelion destination.
> Per-inbound-edge routing breaks the described attack by blocking an
> adversary's
> ability to construct useful fingerprints.
>
> This iteration of Dandelion has been tested on our own small network, and
> we
> would like to get the implementation in front of a wider audience. An
> updated
> BIP document with further details on motivation, specification,
> compatibility,
> and implementation is located here:
> https://github.com/mablem8/bips/blob/master/bip-dandelion.mediawiki
>
> We would like to thank the Bitcoin Core developers and Gregory Maxwell in
> particular for their insightful comments, which helped to inform this
> implementation and some of the follow-up work we conducted. We would also
> like
> to thank the Mimblewimble development community for coining the term
> "stempool,"
> which we happily adopted for this implementation.
>
> All the best,
> Brad Denby 
> Andrew Miller 
> Giulia Fanti 
> Surya Bakshi 
> Shaileshh Bojja Venkatakrishnan 
> Pramod Viswanath 
>
__

Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size

[Riccardo Casatta via bitcoin-dev]

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?

Thanks

Il giorno ven 18 mag 2018 alle ore 08:29 Karl-Johan Alm via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> ha scritto:

> On Fri, May 18, 2018 at 12:25 AM, Matt Corallo via bitcoin-dev
>  wrote:
> > In general, I'm concerned about the size of the filters making existing
> > SPV clients less willing to adopt BIP 158 instead of the existing bloom
> > filter garbage and would like to see a further exploration of ways to
> > split out filters to make them less bandwidth intensive. Some further
> > ideas we should probably play with before finalizing moving forward is
> > providing filters for certain script templates, eg being able to only
> > get outputs that are segwit version X or other similar ideas.
>
> There is also the idea of multi-block filters. The idea is that light
> clients would download a pair of filters for blocks X..X+255 and
> X+256..X+511, check if they have any matches and then grab pairs for
> any that matched, e.g. X..X+127 & X+128..X+255 if left matched, and
> iterate down until it ran out of hits-in-a-row or it got down to
> single-block level.
>
> This has an added benefit where you can accept a slightly higher false
> positive rate for bigger ranges, because the probability of a specific
> entry having a false positive in each filter is (empirically speaking)
> independent. I.e. with a FP probability of 1% in the 256 range block
> and a FP probability of 0.1% in the 128 range block would mean the
> probability is actually 0.001%.
>
> Wrote about this here: https://bc-2.jp/bfd-profile.pdf (but the filter
> type is different in my experiments)
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>


-- 
Riccardo Casatta - @RCasatta 
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev