Re: [bitcoin-dev] Hash-based accumulators with quick insertion
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
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
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
В 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