Re: [Bitcoin-development] Tree-chains preliminary summary
On Sat, Mar 22, 2014 at 12:43:34PM -0700, Mark Friedenbach wrote: Btw, any chance we could get a summary description of tree-chains posted to bitcoin-development? Sure: Introduction Bitcoin doesn't scale. There's a lot of issues at hand here, but the most fundemental of them is that to create a block you need to update the state of the UTXO set, and the way Bitcoin is designed means that updating that state requires bandwidth equal to all the transaction volume to keep up with the changes to what set. Long story short, we get O(n^2) scaling, which is just plain infeasible. So let's split up the transaction volume so every individual miner only needs to keep up with some portion. In a rough sense that's what alt-coins do - all the tipping microtransactions on Doge never have to hit the Bitcoin blockchain for instance, reducing pressure on the latter. But moving value between chains is inconvenient; right now moving value requires trusted third parties. Two-way atomic chain transfers does help here, but as recent discussions on the topic showed there's all sorts of edge cases with reorganizations that are tricky to handle; at worst they could lead to inflation. So what's the underlying issue there? The chains are too independent. Even with merge-mining there's no real link between one chain and another with regard to the order of transactions. Secondly merge-mining suffers from 51% attacks if the chain being merge-mined doesn't have a majority of total hashing power... which kinda defeats the point if we're worried about miner scalability. Blocks and the TXO set as a binary radix tree = So how can we do better? Start with the big picture idea and take the linear blockchain and turn it into a tree: ┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ Obviously if we could somehow split up the UTXO set such that individual miners/full nodes only had to deal with subsets of this tree we could significantly reduce the bandwidth that any one miner would need to process. Every transaction output would get a unique identifier, say txoutid=H(txout) and we put those outputs in blocks appropriately. We can't just wave a magic wand and say that every block has the above structure and all miners co-ordinate to generate all blocks in one go. Instead we'll do something akin to merge mining. Start with a linear blockchain with ten blocks. Arrows indicate hashing: a0 ⇽ a1 ⇽ a2 ⇽ a3 ⇽ a4 ⇽ a5 ⇽ a6 ⇽ a7 ⇽ a8 ⇽ a9 The following data structure could be the block header in this scheme. We'll simplify things a bit and make up our own; obviously with some more effort the standard Satoshi structures can be used too: struct BlockHeader: uint256 prevBlockHash uint256 blockContentsHash uint256 target uint256 nonce uint time For now we'll say this is a pure-proof-of-publication chain, so our block contents are very simple: struct BlockContents: uint256 merkleRoot As usual the PoW is valid if H(blockHeader) blockHeader.target. Every block creates new txouts, and the union of all such txouts is the txout set. As shown previously(1) this basic proof-of-publication functionality is sufficient to build a crypto-currency even without actually validating the contents of the so-called transaction outputs. The scalability of this sucks, so let's add two more chains below the root to start forming a tree. For fairness we'll only allow miners to either mine a, a+b, or a+c; attempting to mine a block with both the b and c chains simultaneously is not allowed. struct BlockContents: uint256 childBlockHash # may be null bool childSide # left or right uint256 merkleRoot Furthermore we shard the TXO space by defining txoid = H(txout) and allowing any txout in chain a, and only txouts with LSB=0 in b, LSB=1 in c; the beginning of a binary radix tree. With some variance thrown in we get the following: b0 ⇽⇽ b1 ⇽ b2 ⇽ b3 ⇽ b4 ⇽ b5 ⇽ b6 ⇽ b7 ⇽ b8 ↙↙ a0 ⇽ a1 ⇽ a2 ⇽ a3 ⇽⇽ a4 ⇽ a5 ⇽ a6 ⇽ a7 ⇽ a8 ↖↖ ↖ ↖ ↖ c0 ⇽ c1 ⇽ c2 ⇽ c3 ⇽⇽ c4 ⇽ c5 ⇽ c6 ⇽⇽ c7 We now have three different versions of the TXO set: ∑a, ∑a + ∑b, and ∑a+∑c. Each of these versions is consistent in that for a given txoutid prefix we can achieve consensus over the contents of the TXO set. Of course, this definition is recursive: a0 ⇽ a1 ⇽ a2 ⇽ a3 ⇽⇽ a4 ⇽ a5 ⇽ a6 ⇽ a7 ⇽ a8 ↖↖ ↖ ↖ ↖ c0 ⇽ c1 ⇽ c2 ⇽ c3 ⇽⇽ c4 ⇽ c5 ⇽ c6 ⇽⇽ c7 ↖ ↖ ↖↖ ↖ d0 ⇽ d1 ⇽⇽ d2 ⇽⇽ d3 ⇽ d4 ⇽⇽⇽ d5 d6 Unicode unfortunately lacks 3D box drawing at present, so I've only shown left-sided child chains. Herding the child-chains
Re: [Bitcoin-development] Tree-chains preliminary summary
On Tue, Mar 25, 2014 at 8:28 AM, Peter Todd p...@petertodd.org wrote: Bitcoin doesn't scale. There's a lot of issues at hand here, but the most fundemental of them is that to create a block you need to update the state of the UTXO set, and the way Bitcoin is designed means that updating that state requires bandwidth equal to all the transaction volume to keep up with the changes to what set. Long story short, we get O(n^2) scaling, which is just plain infeasible. We have a fundamental disagreement here. If you go back and read Satoshi's original thoughts on scaling, it is clear that he imagined tens of thousands of mining nodes and hundreds of millions of lightweight SPV users. Scaling is a problem if every person is a fully validating node; then, indeed, you get an O(n^2) problem. Which can be solved by extending some tentative trust to your peers, but lets put all those possible solutions aside. Given tens of thousands of fully validating nodes, you get O(m*n), where m is the number of fully validating peers and is a large constant (10s of thousands). We don't know how large m can or will be; we have only just started to scale up. Bitcoin doesn't scale is pure FUD. It might not scale in exactly the way you want, but it WILL scale. -- -- Gavin Andresen Chief Scientist, Bitcoin Foundation https://www.bitcoinfoundation.org/ -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Tree-chains preliminary summary
On Tue, Mar 25, 2014 at 08:28:51AM -0400, Peter Todd wrote: On Sat, Mar 22, 2014 at 12:43:34PM -0700, Mark Friedenbach wrote: Btw, any chance we could get a summary description of tree-chains posted to bitcoin-development? Sure: Introduction BTW for those whose email clients have problems with unicode: http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg04388.html Also, I was in a bit of a rush - catching a flight - and know I should have cited a few things, including, but not limited to, various peoples' work on chain-to-chain transfers and SPV proofs. -- 'peter'[:-1]@petertodd.org 5f3189269d2c39711d6a340a617267d72f95848a9ab8e7ba signature.asc Description: Digital signature -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
This *could* be a useful feature, but only if it's generalizable to other processor architectures, and **in particular** has an implementation using dedicated silicon that has a **public** open-source hardware layout, so you can X-ray the chip, and confirm with a thermal imager that yes, the encryption code is actually running where you think it's running. I was *almost* convinced that the 'new key per address' was a good idea to mitigate ECDSA side channel attacks. Now, however, I find it quite plausible that intelligence agencies are promoting 'new key per transaction' as a way to make sure all your keys are leaked all over RAM and the nearby electromagnetic spectrum with side channels intentionally embedded in commodity hardware. If you want to convince me otherwise, then help me crowdfund an open-source hardware Bitcoin ASIC that does the crypto and stores your private keys. I expect the 'new key per transaction' crowd will be in for a rude awakening when they finally understand the silicon area cost to do this securely. Conclusion: Not only is 'de-prioritizing address re-use' BAD privacy, it provides a social engineering/key leakage attack vector where someone can track you down from the EMF generated by your bitcoin wallet when they send you money. If you think otherwise, let's build some ficking open-source hardware and find out how much silicon this will cost. Although it's probably more profitable to just build a bitcoin wallet detector and keep your mouth shut. On Thu, Mar 06, 2014 at 11:00:14AM +0100, Natanael wrote: You've heard of TRESOR? No, not Trezor. https://en.wikipedia.org/wiki/TRESOR Signing on the CPU, without touching RAM. - Sent from my phone Den 6 mar 2014 09:41 skrev Mike Hearn m...@plan99.net: I'm wondering about whether (don't laugh) moving signing into the kernel and then using the MTRRs to disable caching entirely for a small scratch region of memory would also work. You could then disable pre-emption and prevent anything on the same core from interrupting or timing the signing operation. However I suspect just making a hardened secp256k1 signer implementation in userspace would be of similar difficulty, in which case it would naturally be preferable. On Wed, Mar 5, 2014 at 11:25 PM, Gregory Maxwell gmaxw...@gmail.comwrote: On Wed, Mar 5, 2014 at 2:14 PM, Eric Lombrozo elombr...@gmail.com wrote: Everything you say is true. However, branchless does reduce the attack surface considerably - if nothing else, it significantly ups the difficulty of an attack for a relatively low cost in program complexity, and that might still make it worth doing. Absolutely. I believe these things are worth doing. My comment on it being insufficient was only that my signer is branchless doesn't make other defense measures (avoiding reuse, multsig with multiple devices, not sharing hardware, etc.) unimportant. As for uniform memory access, if we avoided any kind of heap allocation, wouldn't we avoid such issues? No. At a minimum to hide a memory timing side-channel you must perform no data dependent loads (e.g. no operation where an offset into memory is calculated). A strategy for this is to always load the same values, but then mask out the ones you didn't intend to read... even that I'd worry about on sufficiently advanced hardware, since I would very much not be surprised if the processor was able to determine that the load had no effect and eliminate it! :) ) Maybe in practice if your data dependencies end up only picking around in the same cache-line it doesn't actually matter... but it's hard to be sure, and unclear when a future optimization in the rest of the system might leave it exposed again. (In particular, you can't generally write timing sign-channel immune code in C (or other high level language) because the compiler is freely permitted to optimize things in a way that break the property. ... It may be _unlikely_ for it to do this, but its permitted— and will actually do so in some cases—, so you cannot be completely sure unless you check and freeze the toolchain) Anyhow, without having gone into the full details of this particular attack, it seems the main attack point is differences in how squaring and multiplication (in the case of field exponentiation) or doubling and point addition (in the case of ECDSA) are performed. I believe using a branchless implementation where each phase of the operation executes the exact same code and accesses the exact same stack frames would not be vulnerable to FLUSH+RELOAD. I wouldn't be surprised. -- Subversion Kills Productivity. Get off Subversion Make the Move to Perforce. With Perforce, you get hassle-free workflows. Merge that actually works. Faster operations. Version large binaries. Built-in WAN
Re: [Bitcoin-development] New side channel attack that can recover Bitcoin keys
Y'all are getting deep into tinfoil-wearing-hat-conspiracy-theory territory. If you are worried about the NSA compromising your hardware or software, then use multisig transactions and sign on diverse hardware/software stacks. Generate the multiple private keys on different hardware/software stacks, too. Or, in other words, eliminate the single point of failure and you will mitigate whole families of possible attacks, from NSA compromised the hardware random number generator in my CPU to NSA is listening to EMF radiation coming from my dedicated server in my data center to the much more likely data center employee is tricked into letting somebody have access to my dedicated server. -- -- Gavin Andresen -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Tree-chains preliminary summary
On Tue, Mar 25, 2014 at 08:45:00AM -0400, Gavin Andresen wrote: On Tue, Mar 25, 2014 at 8:28 AM, Peter Todd p...@petertodd.org wrote: Bitcoin doesn't scale. There's a lot of issues at hand here, but the most fundemental of them is that to create a block you need to update the state of the UTXO set, and the way Bitcoin is designed means that updating that state requires bandwidth equal to all the transaction volume to keep up with the changes to what set. Long story short, we get O(n^2) scaling, which is just plain infeasible. We have a fundamental disagreement here. If you go back and read Satoshi's original thoughts on scaling, it is clear that he imagined tens of thousands of mining nodes and hundreds of millions of lightweight SPV users. Yeah, about that... https://blockchain.info/pools For someone with 'Chief Scientist' as their job title, I'm surprised you think so little of hard evidence and so much of idol worshipping. P.S. A year or so ago you complained that if I cared so much about decentralization, I should make P2Pool better. Your homework: What do tree-chains and Andrew Miller's non-outsourcable puzzles(1) have to do with that? What about the cube-square law? And why don't I think TXO commitments solve the blocksize problem? 1) https://bitcointalk.org/index.php?topic=309073.0;all -- 'peter'[:-1]@petertodd.org 20366a15799010ae0432be831c197e06b19133028a9aa6f3 signature.asc Description: Digital signature -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Tree-chains preliminary summary
A few months ago I had a conversation with an executive at a Bitcoin company, and I suggested their developers should get involved with the development list. I was told that they are all subscribed but refuse to post. Puzzled, I asked why, maybe the process isn't clear or we didn't talk about what they were interested in? No, it's because in that executives words They see how Peter Todd shoots people down in flames and want nothing to do with that. Peter, you were named explicitly as the source of the problem. Your immediate knee-jerk reaction to anyone who disagrees with you is making this forum aggressive and ugly - it puts other people off from contributing. For what it's worth, if I were the moderator of this list I would have banned you a long time ago because I value a friendly atmosphere more than your insights, which are often deeply suspect (as in this case). Besides, ground up redesigns of Bitcoin like what you propose are more appropriate for bitcointalk. So please take it there. -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Tree-chains preliminary summary
-BEGIN PGP SIGNED MESSAGE- Hash: SHA256 For the record, tree chains is designed to be a soft-fork upgrade to bitcoin, at least if we can get the economics to work out. Assuming it does, you would do this by defining bitcoin itself to be the top level chain, and carrying what appear to be anyone can spend txouts from block to block so that transaction outputs can be created when funds are redeemed in the top block chain from children lower in the tree. Very similar ideas as the chain to chain stuff via spv proofs that Mark and Adam were talking about here earlier, although I think the order and reorganisation guarantees is a big advantage over their unsynched chain model. Most of the other ideas are identical, and they deserve credit. I'm on the currency design panel at the Princeton Bitcoin Research Conference this week - tree chains will be discussed informally if not on the panel itself. Regarding cryptocurrency research related posts, the feedback I've gotten has always been quite positive. You are in the minority as far as I can tell, and anyway the volume of such posts is a small part of the total list volume. As for the rest of your email, doctor, heal thyself. Gavin's constant namecalling of legit and well accepted scaling concerns as FUD has irritated many people for over a year now, among many other things. Statements similar to what you claim are said about me are also often said to me about you and Gavin. But anyway, reply off list please. On 25 March 2014 11:20:05 GMT-04:00, Mike Hearn m...@plan99.net wrote: A few months ago I had a conversation with an executive at a Bitcoin company, and I suggested their developers should get involved with the development list. I was told that they are all subscribed but refuse to post. Puzzled, I asked why, maybe the process isn't clear or we didn't talk about what they were interested in? No, it's because in that executives words They see how Peter Todd shoots people down in flames and want nothing to do with that. Peter, you were named explicitly as the source of the problem. Your immediate knee-jerk reaction to anyone who disagrees with you is making this forum aggressive and ugly - it puts other people off from contributing. For what it's worth, if I were the moderator of this list I would have banned you a long time ago because I value a friendly atmosphere more than your insights, which are often deeply suspect (as in this case). Besides, ground up redesigns of Bitcoin like what you propose are more appropriate for bitcointalk. So please take it there. -BEGIN PGP SIGNATURE- Version: APG v1.0.9 iQFQBAEBCAA6BQJTMbMyMxxQZXRlciBUb2RkIChsb3cgc2VjdXJpdHkga2V5KSA8 cGV0ZUBwZXRlcnRvZGQub3JnPgAKCRAZnIM7qOfwheooB/9pKwUKLni8ZBPfe7qQ e3dTTWXeottw1dOT1iUDvk2VVRe0ou38UZhqVQTr9KL3sf6OKsijwb7mgPdoSolA ZJ30mPk68KPMdmESfDeXvl8l/hdXCdI1mHmeAcUwirH85eVc9olBL5AKOpfIFtPx ReagvnMVy5nWguGnRNq4O3A5G7BBcFWnIhTjj656Hsqywf0j2l9P+JcgSpHhOupF q/v6Ybeae5UJHmINMA9Mw5isZT1uFGDxYPoG6xvz0/O/gaPVTXNQiQJa9rq9v0wp +EQEF5br+wN1VmBQOYV+6ig5Ttz4s4i+tCyVIZPF5HKmipBuK+mtDT81dqxRqh7q dF86 =37x3 -END PGP SIGNATURE- -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Tree-chains preliminary summary
On Tue, Mar 25, 2014 at 9:49 AM, Peter Todd p...@petertodd.org wrote: For someone with 'Chief Scientist' as their job title, I'm surprised you think so little of hard evidence and so much of idol worshipping. Peter, take this unprofessional, personal crap off-list. Mike's anecdote of hostility is not an isolated one. Just today, a bitcore developer commented on Peter Todd's ..apocalyptic vision and... negative view on bitcoin which turned off some other developers from participating more interactively. As I commented on IRC, open source projects are no strangers to people who simultaneously (a) make useful contributions and (b) turn potential contributors away with an abrasive or hostile attitude toward others. It's an unsolved problem in OSS, that I saw for 15+ years in the Linux kernel community. For this list, as Mike suggested on IRC, introducing an openly stated moderation policy may be the one route. -- Jeff Garzik Bitcoin core developer and open source evangelist BitPay, Inc. https://bitpay.com/ -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Tree-chains preliminary summary
I would echo the need for some kind of moderation. I believe Peter Todd is an extremely intelligent individual, who has a lot to offer the Bitcoin community. He has a firm grasp of a lot of really deep Bitcoin concepts and his *technical* insight is generally positive. Technically. But the way he communicates on this list is *extremely* corrosive and breeds hostility. It makes it a scary place to discuss things, with frequent, public ridicule of everything posted. I agree that I would rather have a friendly environment to discuss technicals, even if it means losing additional technical insight. People who would explicitly insult other contributors intelligence and character on a public list should be subject to some kind of negative reinforcement. Maybe there's solutions other than outright banning. -Alan On 03/25/2014 01:37 PM, Jeff Garzik wrote: On Tue, Mar 25, 2014 at 9:49 AM, Peter Todd p...@petertodd.org wrote: For someone with 'Chief Scientist' as their job title, I'm surprised you think so little of hard evidence and so much of idol worshipping. Peter, take this unprofessional, personal crap off-list. Mike's anecdote of hostility is not an isolated one. Just today, a bitcore developer commented on Peter Todd's ..apocalyptic vision and... negative view on bitcoin which turned off some other developers from participating more interactively. As I commented on IRC, open source projects are no strangers to people who simultaneously (a) make useful contributions and (b) turn potential contributors away with an abrasive or hostile attitude toward others. It's an unsolved problem in OSS, that I saw for 15+ years in the Linux kernel community. For this list, as Mike suggested on IRC, introducing an openly stated moderation policy may be the one route. -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Tree-chains preliminary summary
-BEGIN PGP SIGNED MESSAGE- Hash: SHA256 OK, deal. You guys stop calling my concerns FUD, accusing me of having ulterior motives, etc. and I'll pay the same respect to you. On 25 March 2014 14:13:36 GMT-04:00, slush sl...@centrum.cz wrote: I fully agree, please keep friendly environment on this list. Btw I also met people who were making fun about Peter's reactions on bitcoin-dev. slush On Tue, Mar 25, 2014 at 7:02 PM, Alan Reiner etothe...@gmail.com wrote: I would echo the need for some kind of moderation. I believe Peter Todd is an extremely intelligent individual, who has a lot to offer the Bitcoin community. He has a firm grasp of a lot of really deep Bitcoin concepts and his *technical* insight is generally positive. Technically. But the way he communicates on this list is *extremely* corrosive and breeds hostility. It makes it a scary place to discuss things, with frequent, public ridicule of everything posted. I agree that I would rather have a friendly environment to discuss technicals, even if it means losing additional technical insight. People who would explicitly insult other contributors intelligence and character on a public list should be subject to some kind of negative reinforcement. Maybe there's solutions other than outright banning. -Alan On 03/25/2014 01:37 PM, Jeff Garzik wrote: On Tue, Mar 25, 2014 at 9:49 AM, Peter Todd p...@petertodd.org wrote: For someone with 'Chief Scientist' as their job title, I'm surprised you think so little of hard evidence and so much of idol worshipping. Peter, take this unprofessional, personal crap off-list. Mike's anecdote of hostility is not an isolated one. Just today, a bitcore developer commented on Peter Todd's ..apocalyptic vision and... negative view on bitcoin which turned off some other developers from participating more interactively. As I commented on IRC, open source projects are no strangers to people who simultaneously (a) make useful contributions and (b) turn potential contributors away with an abrasive or hostile attitude toward others. It's an unsolved problem in OSS, that I saw for 15+ years in the Linux kernel community. For this list, as Mike suggested on IRC, introducing an openly stated moderation policy may be the one route. -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development -BEGIN PGP SIGNATURE- Version: APG v1.0.9 iQFQBAEBCAA6BQJTMd1DMxxQZXRlciBUb2RkIChsb3cgc2VjdXJpdHkga2V5KSA8 cGV0ZUBwZXRlcnRvZGQub3JnPgAKCRAZnIM7qOfwhb89B/98Tb0Xncho+1cbja1K R9xYOKPhWU5EIuPr7zbpuQxufuM8hZsyFSo/ptnQnJ8EAJ2GvUUEnE2vDDjvqqJm vy5URtOwKc6ztBDrjtWToKCgBwpJTektWrJMu2FQaO5CV/4sHhVM4By8BoDvCNLt xeN7BccjvlDZ+2ggRaYt4P/QKctEyt9qZrdDmIsNxUa+bLzplHoqdoQMjQ2CUcUA T+/Lq7MH+vROJXqx7d3JSsZAQ59evQDyorvCrxNgfVbB7j10t1zr5r5viWUEDtZ5 /9DAP92vpSCokmKWfSlysHbC4KEqWglWka7aSBLXmAVrJeFxJRojsLQbCKUUFrG0 IigO =91oy -END PGP SIGNATURE- -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Tree-chains preliminary summary
2014-03-25 13:49 GMT+00:00 Peter Todd p...@petertodd.org: On Tue, Mar 25, 2014 at 08:45:00AM -0400, Gavin Andresen wrote: On Tue, Mar 25, 2014 at 8:28 AM, Peter Todd p...@petertodd.org wrote: Bitcoin doesn't scale. There's a lot of issues at hand here, but the most fundemental of them is that to create a block you need to update the state of the UTXO set, and the way Bitcoin is designed means that updating that state requires bandwidth equal to all the transaction volume to keep up with the changes to what set. Long story short, we get O(n^2) scaling, which is just plain infeasible. We have a fundamental disagreement here. If you go back and read Satoshi's original thoughts on scaling, it is clear that he imagined tens of thousands of mining nodes and hundreds of millions of lightweight SPV users. Yeah, about that... https://blockchain.info/pools On-topic: This argument is quite the fallacy. The only reason we have that few pools is because each of their miners doesn't find it feasible to mine on their own. if you count the individual miners on those pools you will get to the scale Gavin was trying to point out. Nevertheless i think that is just a minor disagreement, since tree chains help decentralization. For someone with 'Chief Scientist' as their job title, I'm surprised you think so little of hard evidence and so much of idol worshipping. P.S. A year or so ago you complained that if I cared so much about decentralization, I should make P2Pool better. Your homework: What do tree-chains and Andrew Miller's non-outsourcable puzzles(1) have to do with that? What about the cube-square law? And why don't I think TXO commitments solve the blocksize problem? 1) https://bitcointalk.org/index.php?topic=309073.0;all -- 'peter'[:-1]@petertodd.org 20366a15799010ae0432be831c197e06b19133028a9aa6f3 -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Tree-chains preliminary summary
I'm afraid I'm going to be the jerk that requested more details and then only nitpicks seemingly minor points in your introduction. But its because I need more time to digest the contents of your proposal. Until then: But moving value between chains is inconvenient; right now moving value requires trusted third parties. Two-way atomic chain transfers does help here, but as recent discussions on the topic showed there's all sorts of edge cases with reorganizations that are tricky to handle; at worst they could lead to inflation. This isn't true. The re-org issue is fairly handled in the 2-way pegging scheme that Greg Maxwell developed and Adam Back described a week ago on this list. Depending on the implementation it could even be configurable by the person performing the peg too - allowing the transfer to specify the confirmation depth required during the quieting period in order to protect against re-orgs up to a sufficient depth. I think this is worked out quite well with sufficient enumeration of edge cases, and I don't think they are particularly tricky to handle or lead to money-losing situations under the explicit security assumptions. More importantly, to your last point there is absolutely no way this scheme can lead to inflation. The worst that could happen is theft of coins willingly put into the pegging pool. But in no way is it possible to inflate the coin supply. I will look at your proposal in more depth. But I also think you should give 2-way pegging a fair shake as pegging to side chains and private accounting servers may eliminate the need. -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Tree-chains preliminary summary
Peter, I think you and I both know there is WAAYY to much MONEY to be taken from naive end-users by the companies that employ people who call your concerns FUD. And for everyone else, I want to apologize in advance for anything I might happen to say that might be abrasive, arrogant, angry, or 'in need of moderation'. So for those who do not wish to hear or read such things, delete my message now. === disclaimer: strong language follows === What the fuck Groupthink? committee for GROUPTHINKPROFIT? I'd rather have Peter Todd calling some developers idiots on the list than some fucking idiots who get paid way to fucking much calling 'end-users' stupid for believing MtGox. Hell, I was one of these idiots that fell for a marketing scam by a company that had a good story. But here is the damn point. The Excecutive who was whining about how his devs won't show up should probably consider hiring people who make VOCAL points on the mailing list. Or maybe he should consider that his developers might know his business model is shit and if they DID say something, it would be CLEAR to the world that only an idiot would use their companies services, and kill the company. Would you rather hear of vulnerabilities and scaling limits on bitcoin-development, or would you rather hear about them by a chorus of They got hacked, their code must suck, but AFTER the fact. It seems to be an unfortunate fact of life that sleazy people take a shitload of money from nice people. Moderate Peter and I into oblivion at your own risk. Wouldn't you rather have us pointing out obvious flaws than ignoring shit? ... But just remember, your employers probably make more money by ignoring shit On Tue, Mar 25, 2014 at 03:47:15PM -0400, Peter Todd wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA256 OK, deal. You guys stop calling my concerns FUD, accusing me of having ulterior motives, etc. and I'll pay the same respect to you. On 25 March 2014 14:13:36 GMT-04:00, slush sl...@centrum.cz wrote: I fully agree, please keep friendly environment on this list. Btw I also met people who were making fun about Peter's reactions on bitcoin-dev. slush On Tue, Mar 25, 2014 at 7:02 PM, Alan Reiner etothe...@gmail.com wrote: I would echo the need for some kind of moderation. I believe Peter Todd is an extremely intelligent individual, who has a lot to offer the Bitcoin community. He has a firm grasp of a lot of really deep Bitcoin concepts and his *technical* insight is generally positive. Technically. But the way he communicates on this list is *extremely* corrosive and breeds hostility. It makes it a scary place to discuss things, with frequent, public ridicule of everything posted. I agree that I would rather have a friendly environment to discuss technicals, even if it means losing additional technical insight. People who would explicitly insult other contributors intelligence and character on a public list should be subject to some kind of negative reinforcement. Maybe there's solutions other than outright banning. -Alan On 03/25/2014 01:37 PM, Jeff Garzik wrote: On Tue, Mar 25, 2014 at 9:49 AM, Peter Todd p...@petertodd.org wrote: For someone with 'Chief Scientist' as their job title, I'm surprised you think so little of hard evidence and so much of idol worshipping. Peter, take this unprofessional, personal crap off-list. Mike's anecdote of hostility is not an isolated one. Just today, a bitcore developer commented on Peter Todd's ..apocalyptic vision and... negative view on bitcoin which turned off some other developers from participating more interactively. As I commented on IRC, open source projects are no strangers to people who simultaneously (a) make useful contributions and (b) turn potential contributors away with an abrasive or hostile attitude toward others. It's an unsolved problem in OSS, that I saw for 15+ years in the Linux kernel community. For this list, as Mike suggested on IRC, introducing an openly stated moderation policy may be the one route. -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development -- Learn Graph Databases - Download FREE O'Reilly Book Graph
Re: [Bitcoin-development] Tree-chains preliminary summary
On Tue, Mar 25, 2014 at 08:40:40PM +, Ricardo Filipe wrote: 2014-03-25 13:49 GMT+00:00 Peter Todd p...@petertodd.org: On Tue, Mar 25, 2014 at 08:45:00AM -0400, Gavin Andresen wrote: On Tue, Mar 25, 2014 at 8:28 AM, Peter Todd p...@petertodd.org wrote: Bitcoin doesn't scale. There's a lot of issues at hand here, but the most fundemental of them is that to create a block you need to update the state of the UTXO set, and the way Bitcoin is designed means that updating that state requires bandwidth equal to all the transaction volume to keep up with the changes to what set. Long story short, we get O(n^2) scaling, which is just plain infeasible. We have a fundamental disagreement here. If you go back and read Satoshi's original thoughts on scaling, it is clear that he imagined tens of thousands of mining nodes and hundreds of millions of lightweight SPV users. Yeah, about that... https://blockchain.info/pools On-topic: This argument is quite the fallacy. The only reason we have that few pools is because each of their miners doesn't find it feasible to mine on their own. if you count the individual miners on those pools you will get to the scale Gavin was trying to point out. Nevertheless i think that is just a minor disagreement, since tree chains help decentralization. I think is actually a major fundamental disagreement, and opinions tend to correlate strongly with salary considerations. It is difficult to get a man to understand something, when his salary depends upon his not understanding it! -- Upton Sinclair Let us either agree to disagree, or get on with moderating this list so that only sensible salaried discussions can take place. -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] Privacy-Protecting Proof of Reserves without the Moon-Math and without the backup angst
Introduction In the wake of the Mt. Gox debacle merkle-sum-trees for proof-of-reserve(1) have been getting attention again. A serious objection to using them is exchange privacy as the merkle-sum-tree inherently reveals the sum total of all deposits held by a given service. A second, lesser, consideration is the privacy of the users' balances, as changes to those balances are reflected in the tree and various levels of aggregate information can be extracted from the solvency proofs. For instance consider how an attacker who had knowledge of a few balance changes to a particular user's account - perhaps because that attacker had deposited funds themselves - could then corrolate those balance changes with changes in merkle path proofs to determine an upper bound on the victim's total balance. With some effort and/or luck that upper bound could be even improved to the exact account balance by obtaining a solvency proof from an account adjacent to the victim's account. Real or imagined the privacy problems with merkle-sum-trees pose a barrier to adoption. Jesse from the exchange Kraken stated recently(2) on reddit: This is asking a lot of an exchange, and I don't think information is worth the price you're paying in security and privacy. Your interests would be better served by a private auditor's report. While there has been much discussion recently on #bitcoin-wizards and other places about applying advanced cryptographic techniques - so called Moon Math - generate zero-knowledge-proofs of blinded account sum trees so as to not leak any information, these techniques all suffer from implementation complexity. Fortunately private proof-of-solvency without moon math is possible without significant increase in complexity. Objectives -- First let's look at what exactly it is that our proof-of-solvency is supposed to achieve. For expediency we'll refer to the third-parties proving solvency as 'banks' and start with the big picture: 0) No more banks stealing everyone's money! Of course, since the banks have the private keys to the bitcoins in question the best we can actually do is much weaker: 1) Prove that at some point in the past, the bank had access to a private key that can be used to spend unspent txout(s) that still exists now. Note how the bank may have since lost that key! But objective #1 isn't good enough by itself; we also need to: 2) Prove that those txout(s) have no been re-used in any other proof of solvency or ownership. Most discussions about merkle-sum-trees miss this critical point. To see why it matters, consider the example of BigBank. They have a very simple proof-of-solvency scheme where they simply allocate one address per customer, holding at least their entire balance. To prove their solvency to Alice they simply sign a message: $ btc verifymessage 13pPCfupiDhWadEXTZDnqSHm5Cy2rdUDho \ ID6Wk3SDsg3os4cSWRtG13lODY84zoVYpfEC2Y4kfHqGqqZV9hy1xD5yRKCyjL0II3UwPirEVKxm5meJ3VVDW/0= \ Hi Alice true Alice checks that the txouts with that address sum up to at least as many Bitcoins as her balance, sees that it does, and is satisfied BigBank is solvent. Meanwhile LittleBank is running short of funds, so they decide to borrow some from BigBank. One of their customers, Bob, asks for a proof-of-solvency for his balance, and LittleBank happily obliges: $ btc verifymessage 13pPCfupiDhWadEXTZDnqSHm5Cy2rdUDho \ H9af7wCdJrVIPG5Z0qrSviwAsElPkGw9v5FrUBAdaBtpeEtP/G8UdwN6KxKOytqyU7ObzcQs3qa6urHceZIXDg4= \ Hi Bob true It's rather unlikely that Alice and Bob will compare notes so this reuse-fraud goes undetected. Solving txout reuse-fraud with per-txout commitments By committing the txout to one and only one purpose we can ensure that they can't be reused for more than one proof-of-solvency. Take the following scriptPubKey: H(bigbank.com) DROP pubkey CHECKSIG LittleBank in our above example can't reuse that txout as it is obviously not committed to them. The additional data is kinda ugly and lacks privacy but can be replaced with the same math used in BIP32 HD wallet derivation: pubkey + H(domain)*G CHECKSIG or in the multisig case: n pubkey_1 + H(domain)*G ... pubkey_m + H(domain)*G m CHECKMULTISIG The domain must be provably globally unique; the URL of the third-party would be appropriate in most cases. A simple random UUID is *not* sufficient as there is no good way to be sure that these UUIDs have not been reused. Internal reuse-fraud Suppose BigBank gains a second customer, Bob. After depositing some funds he asks for a proof-of-solvency. BigBank has since added anti-reuse-fraud to their very simple one-address-per-customer scheme: $ btc verifymessage 1HHuBBExHYqPwfgmKiBEHAGFSaLSdVayh5 \ H6IJztw/QM4WjbtHl51WFo5L8rXn5aONZZvpQIo/8ORz7Yx0puLD68Z2WOCmAEvFQfpz0wYSX3D28RhevYBexpQ= \ Hi Bob
Re: [Bitcoin-development] Handling miner adoption gracefully for embedded consensus systems via double-spending/replace-by-fee
On Mon, Mar 24, 2014 at 01:57:14PM -0700, Mark Friedenbach wrote: On 03/24/2014 01:34 PM, Troy Benjegerdes wrote: I'm here because I want to sell corn for bitcoin, and I believe it will be more profitable for me to do that with a bitcoin-blockchain-based system in which I have the capability to audit the code that executes the trade. A discussion over such a system would be on-topic. Indeed I have made my own proposals for systems with that capability in the past: http://sourceforge.net/p/bitcoin/mailman/message/31322676/ There's no reason to invoke alts however. There are ways where this can be done within the bitcoin ecosystem, using bitcoins: http://sourceforge.net/p/bitcoin/mailman/message/32108143/ I think that's fair, so long as we limit bitcoin-development discussion to issues that are relevant to the owners of the hashrate and companies that pay developer salaries. What I'm asking for is some honesty that Bitcoin is a centralized system and to stop arguing technical points on the altar of distributed/decentralized whatever. It's pretty clear if you want decentralized you should go with altchains. Bitcoin is not a centralized system, and neither is its development. I don't even know how to respond to that. Bringing up altchains is a total red herring. This is *bitcoin*-development. Please don't make it have to become a moderated mailing list. When I can pick up a miner at Best Buy and pay it off in 9 months I'll agree with you that bitcoin *might* be decentralized. Maybe there's a chance this *will* happen eventually, but right now we have a couple of mining cartels that control most of the hashrate. There are plenty of interesting alt-hash-chains for which mass produced, general purpose (or gpgpu-purpose) hardware exists and is in high volume mass production. -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Tree-chains preliminary summary
On Tue, Mar 25, 2014 at 2:03 PM, Mark Friedenbach m...@monetize.io wrote: More importantly, to your last point there is absolutely no way this scheme can lead to inflation. The worst that could happen is theft of coins willingly put into the pegging pool. But in no way is it possible to inflate the coin supply. I don't think it would be entirely unfair to describe one of the possible ways a secondary coin becoming unbacked can play out as inflation— after all, people have described altcoins as inflation. In the worst case its no _worse_ inflation, I think, than an altcoin is— however. I will look at your proposal in more depth. But I also think you should give 2-way pegging a fair shake as pegging to side chains and private accounting servers may eliminate the need. I think that chain geometries which improve the scale/decentralization trade-off are complementary. If PT's ideas here do amount to something that gives better scaling without ugly compromise I believe it would still be useful no matter how well the 2-way peg stuff works simply because scaling and decenteralization are both good things which we would pretty much always want more of... -- Learn Graph Databases - Download FREE O'Reilly Book Graph Databases is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
