Re: [bitcoin-dev] Hash-based accumulators with quick insertion

2020-06-08 Thread German Luna via bitcoin-dev
Interesting work! I should be fortunate to make time to read it.

I will point out, in case you'd not considered it, that you can support
addition and removal indirectly by formulating it as a difference of sets.
Similar to the collision-resistant replicated data types (CRDTs) concept.
Checking for membership would simply become CheckMembershipInAdditionSet &&
!CheckMembershipInRemovalSet, assuming an item could only be added/removed
once. You could also perhaps support multiple addition/removal by attaching
a count of how many times it's been added though that might break some of
the building blocks in the paper.

-- 
Germán
Mathematician
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Time-dilation Attacks on the Lightning Network

2020-06-08 Thread Aymeric Vitte via bitcoin-dev

Le 08/06/2020 à 06:56, ZmnSCPxj via bitcoin-dev a écrit :
> Running both Bitcoin and Lightning nodes on clearnet automatically links 
> them, making them easier to attack, whereas running Lightning on Tor does not.
> Of course, they could still be linked by onchain transaction monitoring, but 
> at least this increases the effort to attack, hopefully it becomes marginally 
> less desirable to attack you.
Or makes it easier in fact, correcting what I said in my previous
answer, stating a "yes" for a mixed bitcoin and/or LN node in clearnet
and Tor, with or without different IPs, it's probably not difficult for
the Tor attacker to identify you (for example pinging the nodes with a
new received tx to see who has it in mempool)

Similar to "Deanonymizing the VPN peers"
https://github.com/Ayms/torrent-live, this is not public but the method
uses the clearnet/VPN "mixity" and unexpectedly the more you try to hide
the better you can get deanonymized

The conclusion is always the same: do not use the Tor network for
services it is not designed for
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[bitcoin-dev] Hash-based accumulators with quick insertion

2020-06-08 Thread Salvatore Ingala via bitcoin-dev
Dear all,

I have been working on some constructions for cryptographic accumulators
that optimise for quick insertion.

As a brief background, an accumulator is a data structure that maintains
compact commitments to a potentially very large (and dynamic) set, while
keeping proofs of membership short. Unsurprisingly, they are getting more
popular, and one notable application in Bitcoin is to create light-weight
full nodes that do not need to store the UTXO set (Utreexo accumulator[1]).

In this work, I focus on additive accumulators that supports adding new
elements, but not removing them. My motivation is to support extending
Script with access to an arbitrarily large portion of the blockchain
history and state (e.g., past blocks, txids, or any more complex state
obtained from them - with all due care). The additional storage and
computation cost for nodes is small, and the cost (in additional bytesize)
for any transaction that wishes to access state committed in the
accumulator should be just slightly bigger than typical Merkle proofs.

I have focused on:
- An accumulator with insertion time O(1) and proof size O(log^2 n)
- A construction with insertion time O(log log n) and proof size O(log n
log log n)

All the performance metrics above are in "number of hashes".

You can find:
- draft writeup:
https://github.com/bigspider/accumulator/blob/master/docs/paper-draft.pdf
- sample python code (only for the first construction at this time):
https://github.com/bigspider/accumulator

While this is still an unfinished work, the ideas in the draft are
hopefully clear enough and easy to understand. I wanted to share it at this
stage as it can benefit from comments to improve the constructions, to
cover any related work or to find potential applications in Bitcoin (e.g.
Script, layer2, side chains, etc).

Best,
Salvatore Ingala

[1] - Thaddeus Dryja, Utreexo: A dynamic hash-based accumulator optimized
for the Bitcoin UTXO set - https://eprint.iacr.org/2019/611.pdf
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] [was BIP OP_CHECKTEMPLATEVERIFY] Fee Bumping Operation

2020-06-08 Thread Dmitry Petukhov via bitcoin-dev
В Sun, 7 Jun 2020 23:43:39 -0700
Jeremy via bitcoin-dev  wrote:

> > PFN transaction would still be valid if some of 'ghost parents' are
> >  
> already confirmed, so the miners could have more fees than strictly
> necessary. But this is the same as with CPFP.
> 
> This is problematic and can't be done as it requires a new index of
> all past txns for consensus.

If the logic would match CPFP, then PFN would be valid if some of the
'ghost parents' are confirmed, but would be invalid if some of them are
spent. I believe in this case txindex won't be required.

> My thinking is that a Fee Bump transaction can name a list of TXIDs
> (Or one TXID which implies all ancestors of) that it wishes to be
> included in a block with. It must be included in that block. A Fee
> Bump transaction may have no unconfirmed ancestors nor any children.
> Potentially, it also may not be RBF'd. You treat the Fee Bump
> Transactions as the lowest descendant of whatever it targets and then
> set it's feerate/total fee based on the package that would have to
> co-confirm for it to be worth mining. This makes it sort like normal
> transactions for inclusion. You can require some minimums for mempool
> inclusion at all.
> 
> If it's target is confirmed or replaced, it should drop from the
> mempool.

Re "may not be RBF'd": What if the sender of PFN tx wants to increase
the fee it offers for the 'ghost parents'? RBF-ing PFN tx itself seems
like less wasteful way than RBF-ing some of the parents/'ghost parents'
just for this purpose. Sometimes I think the sender of PFN will not be
even able to replace any other transactions beside their own PFN tx
(like when they offer 'fee bumping' service for others)
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY

2020-06-08 Thread Dmitry Petukhov via bitcoin-dev
В Sun, 7 Jun 2020 15:45:16 -0700
Jeremy via bitcoin-dev  wrote:

> What I think we'll eventually land on is a way of doing a tx
> that contributes fee to another tx chain as a passive observer to
> them. While this breaks one abstraction around how dependencies
> between transactions are processed, it also could help resolve some
> really difficult challenges we face with application-DoS (pinning and
> other attacks) in the mempool beyond CTV. I have a napkin design for
> how this could work, but nothing quite ready to share yet.

I had an idea of 'Pay for neighbor' transaction where a transaction
that is not directly a child of some other transaction can specify that
it wants to pay the fee for that other transaction(s). It can become
like 'ghost child' transaction for them, in what it cannot be mined
unless its 'ghost parents' are confirmed, too. It will be like CPFP,
but without direct dependency via inputs. Such 'PFN' transaction would
not spend any coins beside what it specifies in its own inputs, of
course.

The idea required a hardfork at first, but Anthony Towns suggested
a way to make it into a soft fork (past-taproot) by putting the txids of
'ghost parents' into taproot annex.

PFN transaction would still be valid if some of 'ghost parents' are
already confirmed, so the miners could have more fees than strictly
necessary. But this is the same as with CPFP.

Looking at the mempool code, it seems that only a way how parent/child
transactions relationships are established will need to be adjusted to
account for this 'ghost relationships', and once established, other
logic will work as with CPFP. There could be complications regarding
transaction package size. But I cannot claim that I understand that
code enough to say something about this with certainty.

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


[bitcoin-dev] [was BIP OP_CHECKTEMPLATEVERIFY] Fee Bumping Operation

2020-06-08 Thread Jeremy via bitcoin-dev
Broke out to a separate thread.

At core, the reason why this method *might* work is that it's essentially
just CPFP but we can guarantee that the link we're examining is always
exactly one hop away, so we get rid of most of the CPFP graph traversal
issues.

Your description largely matches my thinking for how something like this
could work (pay for neighbor). The issue is that the extant CPFP logic is
somewhat brittle and doesn't work as expected (Child not Children, which is
problematic for multiple PFN's).

> PFN transaction would still be valid if some of 'ghost parents' are
already confirmed, so the miners could have more fees than strictly
necessary. But this is the same as with CPFP.

This is problematic and can't be done as it requires a new index of all
past txns for consensus.

My thinking is that a Fee Bump transaction can name a list of TXIDs (Or one
TXID which implies all ancestors of) that it wishes to be included in a
block with. It must be included in that block. A Fee Bump transaction may
have no unconfirmed ancestors nor any children. Potentially, it also may
not be RBF'd. You treat the Fee Bump Transactions as the lowest descendant
of whatever it targets and then set it's feerate/total fee based on the
package that would have to co-confirm for it to be worth mining. This makes
it sort like normal transactions for inclusion. You can require some
minimums for mempool inclusion at all.

If it's target is confirmed or replaced, it should drop from the mempool.

Transactions in the mempool may set a flag that opts out of CPFP for
descendants/blocks any descendants. Channel protocols should set this bit
to prevent pinning, and then use the Fee Bump to add fees to whatever txns
need to go through. If done right you can also layer a coinswap protocol
with the fee-bumping txns change so that you are getting a privacy benefit
at the same time.

BTW the annex *could* be used for this purpose, but it would also be
acceptable to have it be in some kind of anyone can spend output. Then it
would just be a anyone-can-spend tx with OP_CHECK_TXID_IN_BLOCK (or
OP_CHECK_UTXO_SPENT_IN_BLOCK), and a miner could claim all such outputs at
the end of the block. This is worse in terms of on-chain overheads, but
nice in that it's the minimal semantic change & introduces some general
purpose functionality.

But my thoughts are still pretty loose at the moment around it. I suspect
that to make fee bumping work nicely would require removing CPFP entirely,
but I don't know that to be the case concretely.

--
@JeremyRubin 



On Sun, Jun 7, 2020 at 11:02 PM Dmitry Petukhov  wrote:

> В Sun, 7 Jun 2020 15:45:16 -0700
> Jeremy via bitcoin-dev  wrote:
>
> > What I think we'll eventually land on is a way of doing a tx
> > that contributes fee to another tx chain as a passive observer to
> > them. While this breaks one abstraction around how dependencies
> > between transactions are processed, it also could help resolve some
> > really difficult challenges we face with application-DoS (pinning and
> > other attacks) in the mempool beyond CTV. I have a napkin design for
> > how this could work, but nothing quite ready to share yet.
>
> I had an idea of 'Pay for neighbor' transaction where a transaction
> that is not directly a child of some other transaction can specify that
> it wants to pay the fee for that other transaction(s). It can become
> like 'ghost child' transaction for them, in what it cannot be mined
> unless its 'ghost parents' are confirmed, too. It will be like CPFP,
> but without direct dependency via inputs. Such 'PFN' transaction would
> not spend any coins beside what it specifies in its own inputs, of
> course.
>
> The idea required a hardfork at first, but Anthony Towns suggested
> a way to make it into a soft fork (past-taproot) by putting the txids of
> 'ghost parents' into taproot annex.
>
> PFN transaction would still be valid if some of 'ghost parents' are
> already confirmed, so the miners could have more fees than strictly
> necessary. But this is the same as with CPFP.
>
> Looking at the mempool code, it seems that only a way how parent/child
> transactions relationships are established will need to be adjusted to
> account for this 'ghost relationships', and once established, other
> logic will work as with CPFP. There could be complications regarding
> transaction package size. But I cannot claim that I understand that
> code enough to say something about this with certainty.
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev