Re: [Bitcoin-development] Decentralizing ming
Jeff, I think the message you're replying to got clipped. Satoshi's only comment AFAIK on the topic of GPU mining was to wish for a gentlemen's agreement to postpone it as long as possible, to help make sure the distribution of coins was as even as possible. Indeed this predated pooled mining. -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Decentralizing ming
Oops, sorry, I see the subject line changed. This is what I get for working down the thread list top to bottom :) I think the best path forward now is to finish off getblocktemplate support in the various tools so it's possible to pool for payout purposes without giving up control of block creation modulo the coinbase. Combined with the recent sipa performance enhancing goodness, it would hopefully persuade some non-trivial chunk of hashpower to go back to running their own node and start the process of turning pools merely into payout trackers rather than block selectors. On Fri, Jul 18, 2014 at 12:41 PM, Mike Hearn m...@plan99.net wrote: Jeff, I think the message you're replying to got clipped. Satoshi's only comment AFAIK on the topic of GPU mining was to wish for a gentlemen's agreement to postpone it as long as possible, to help make sure the distribution of coins was as even as possible. Indeed this predated pooled mining. -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Decentralizing ming
Before they got traction, yes. But he projected a bit, as anyone could, to see the trend. On Thu, Jul 17, 2014 at 1:22 PM, slush sl...@centrum.cz wrote: On Thu, Jul 17, 2014 at 6:14 PM, Jeff Garzik jgar...@bitpay.com wrote: Historical note: On one hand, Satoshi seemed to dislike the early emergence of GPU mining pools quite a bit. To my knowledge, Satoshi left the project before mining pools got a traction. slush -- Jeff Garzik Bitcoin core developer and open source evangelist BitPay, Inc. https://bitpay.com/ -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Decentralizing ming
Yes. That, and several other things. If you can figure out how to propagate a block without re-propagating all the transactions everyone already has, you address the large-blocks-slower-to-relay problem, and additionally create an incentive for miners to mine blocks consisting of publicly broadcast transactions (versus a bunch of secret ones mined with secret agreements). Democratizing transaction selection takes a bit of power away from the miners and gives it back to the network at large. GBT is another piece of that puzzle. On Fri, Jul 18, 2014 at 6:43 AM, Mike Hearn m...@plan99.net wrote: Oops, sorry, I see the subject line changed. This is what I get for working down the thread list top to bottom :) I think the best path forward now is to finish off getblocktemplate support in the various tools so it's possible to pool for payout purposes without giving up control of block creation modulo the coinbase. Combined with the recent sipa performance enhancing goodness, it would hopefully persuade some non-trivial chunk of hashpower to go back to running their own node and start the process of turning pools merely into payout trackers rather than block selectors. On Fri, Jul 18, 2014 at 12:41 PM, Mike Hearn m...@plan99.net wrote: Jeff, I think the message you're replying to got clipped. Satoshi's only comment AFAIK on the topic of GPU mining was to wish for a gentlemen's agreement to postpone it as long as possible, to help make sure the distribution of coins was as even as possible. Indeed this predated pooled mining. -- Jeff Garzik Bitcoin core developer and open source evangelist BitPay, Inc. https://bitpay.com/ -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire
On Thu, Jul 17, 2014 at 6:46 PM, Gavin Andresen gavinandre...@gmail.com wrote: I'd encourage you to code up a prototype first (or at the same time), in whatever programming language / networking library you're most familiar with. +1 Maybe not even using the existing p2p protocol; there could be a mining-only very-fast-block-propagation network separate from the existing p2p network. Combining your optimizations with broadcast as many near-miss blocks as bandwidth will allow on a mining backbone network should allow insanely fast propagation of most newly solved blocks. Yes, I would encourage thinking along these lines. That was the motivation of the UDP P2P protocol extension I wrote: https://bitcointalk.org/index.php?topic=156769.0 The intention was to experiment with sending block header + tx list + coinbase, via UDP best effort broadcast. Incentives: If your neighbors receiving this message already have the TXs in the TX list, then the block is complete, and may be relayed further. If your neighbors do not have all TXs in the block, they must fetch them at additional time/latency cost. Thus, you have an incentive to relay blocks containing TXs already distributed out into network mempools and cached in the signature cache. We want to capture that incentive in whatever protocol is eventually used. Miners have a TX fee incentive to include many transactions. In theory, they want to include as many TX as possible. It will help us scale quite a bit to solve this problem. -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire
Two more half-baked thoughts: We should be able to assume that the majority of transaction data (except for coinbase) has already been propagated. As Jeff said, incentivizing nodes to propagate transactions is a very good thing (the signature cache already gives a small incentive to miners to propagate and not 'hoard' transactions). So the only information that theoretically needs to be propagated is which transactions a miner is including in their block, and in what order they are included. But if there was some agreed-upon canonical ordering, then it should theoretically be possible to take shortcuts in the what order. You'd start with setof(transactions I think everybody knows about) Select some subset, based on miner's policy Sort that subset with the canonical ordering algorithm Very efficiently broadcast, taking all sorts of shortcuts assuming most of your peers already know the set you started with and expect the same canonical ordering (see gmaxwell's thoughts on block encoding). Second half-baked thought: I wonder if broadcasting your transaction selection policy (11KB of free transactions, sorted by priority, then 111K of fee-paying transactions, sorted by fee) might make it possible to save even more bandwidth by letting your peers create a very good approximation of your block with just that information -- -- Gavin Andresen -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire
On Fri, Jul 18, 2014 at 10:53 AM, Gavin Andresen gavinandre...@gmail.com wrote: But if there was some agreed-upon canonical ordering, then it should theoretically be possible to take shortcuts in the what order. You'd start with setof(transactions I think everybody knows about) Select some subset, based on miner's policy Sort that subset with the canonical ordering algorithm Very efficiently broadcast, taking all sorts of shortcuts assuming most of your peers already know the set you started with and expect the same canonical ordering (see gmaxwell's thoughts on block encoding). Related implementation detail: Having pursued this train of thought, I noted that you don't want to include too-young transactions that you received in the past few seconds, because those are likely still propagating around the network. Second half-baked thought: I wonder if broadcasting your transaction selection policy (11KB of free transactions, sorted by priority, then 111K of fee-paying transactions, sorted by fee) might make it possible to save even more bandwidth by letting your peers create a very good approximation of your block with just that information Absolutely. One path I would like to see pursued is multiple p2pool-esque chains. Each with their own policy, perhaps with their own administrative team. ie. you could have a fully decentralized p2pool-like chain, or multiple such chains, each with a stated policy/reward pattern. Or, GHash/BTCGuild/Eligius could run a semi-centrally managed chain ultimately guaranteed not only by protocol but by administrators' digital signatures. In each case, advertising technical attributes about your pool [chain] policy would give nodes the better ability to predict what is in an upcoming block. And the flip side of that, such predictions are never perfect. Need to make sure the fallback case, while undoubtedly more costly than the Fast Path, is not overly painful. -- Jeff Garzik Bitcoin core developer and open source evangelist BitPay, Inc. https://bitpay.com/ -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] Small update to BIP 62
Hi all, I've sent a pull request to make a small change to BIP 62 (my anti-malleability proposal) which is still a draft; see: * https://github.com/bitcoin/bips/pull/90 (the request) * https://github.com/sipa/bips/blob/bip62up/bip-0062.mediawiki (the result) It makes two of the 7 new rules mandatory in new blocks, even for old-style transactions. Both are already non-standard since 0.8.0, and have no use cases in my opinion. The reason for this change is dropping the requirement for signature verification engines to be bug-for-bug compatible with OpenSSL (which supports many non-standard encodings for signatures). Requiring strict DER compliance for signatures means any implementation just needs to support DER. Comments? -- Pieter -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Small update to BIP 62
The rationale doesn't seem to apply to rule #4, what's so special about that one? Although I agree not having to support all of DER is nice, in practice I think all implementations do and libraries to parse DER are widespread. Given that the last time we modified tx rules without bumping version numbers we managed to break the only functioning iPhone client, I've become a big fan of backwards compatibility: seems the default choice should be to preserve compatibility over technical niceness until the old versions have been fully phased out. -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Small update to BIP 62
On Fri, Jul 18, 2014 at 5:39 PM, Mike Hearn m...@plan99.net wrote: The rationale doesn't seem to apply to rule #4, what's so special about that one? Nothing really. If it's controversial in any way, I'm fine with changing that. It's just one those things that nobody needs, nobody uses, has never been standard, and shouldn't have been possible in the first place IMHO. Given that, it's easier to just make it a consensus rule. Although I agree not having to support all of DER is nice, in practice I think all implementations do and libraries to parse DER are widespread. Given that the last time we modified tx rules without bumping version numbers we managed to break the only functioning iPhone client, I've become a big fan of backwards compatibility: seems the default choice should be to preserve compatibility over technical niceness until the old versions have been fully phased out. I'm not comfortable with dropping OpenSSL-based signature parsing until we have well-defined rules about which encodings are valid. At this point I'm not even convinced we *know* about all possible ways to modify signature encodings without invalidating them. But perhaps we should investigate how many non-DER signatures still make it into blocks first... -- Pieter -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Small update to BIP 62
On Fri, Jul 18, 2014 at 5:45 PM, Pieter Wuille pieter.wui...@gmail.com wrote: But perhaps we should investigate how many non-DER signatures still make it into blocks first... In the last 11 blocks (4148 transactions), apparently none. -- Pieter -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire
Peers exchanging mempool priority policies is great; that accomplishes the flexibility in what txes to remember that I was going for with the forget-filters, but much more neatly, with less overhead and some side benefits. Here's what I'm picturing now: - exchange priority policies in peer introductions - assign unique sequential IDs in the order the transactions were inved (per peer) - receiving a getdata for a tx updates last-known-peer-received inv to all invs up to the one referenced - include ID-last-received, last-known-peer-received in sparse block - reference txes in sparse block by index in receiver's prioritiziation with peer's sent invs up to ID-last-received and sender's prior invs up to last-known-peer-received Possible new messages: - sparseblock - invack message a node can send at times when it's received a bunch of invs it already has, so it hasn't acked with a getdata in a while - gettx: getdata, but using new sequential ID to save 28 bytes per tx It seems important for ordering policies to be able to be specified in as much detail as possible. Parameters that should be available: - total inputs - total outputs - bytes - coin days destroyed - net UTXO size change - sigops - is data carrier - is output raw multisig - age in mempool - what else? This parameter set should be extensible to allow for unforeseen future factors. Ordering policies should allow arbitrary algebraic combinations of their parameters, as well as thresholds. Boolean combinations of sub-policies would also be desirable. This could be implemented with a tx-script-like stack-based language, in which each supported tx property is pushed onto the stack by a particular opcode, and +-*//min/max/boolean operators combine them to yield the sort key. Difficult parameters: * Coin-days-destroyed: changes, peers need agreement on when (if?) it's recalculated. Probably can just not recalculate, but peers still need agreement on time seen to get CDD. * Age in mempool: seems intractable in terms of time, but could be done easily in terms of how many txes old is this sequential ID One potential pitfall: this allows for an environment of completely heterogeneous mempool policies. I think that's a good thing, but we need to avoid a situation where only least-common-denominator transactions make it farther than a hop or two, and we don't want nodes to have a strong preference for connecting to like-minded peers since clustering reduces overall connectivity. It may be worthwhile to add a parallel mechanism for relay policies, to differentiate between what a node would keep in its mempool vs. what it wouldn't even relay and doesn't want to see at all. Relay policies could be specified just like prioritization policies, but with the final stack value evaluated in a boolean context. An interesting additional use of policy-scripts would be a standardized way for miners to include a policy script in a coinbase, allowing miners a mechanism to advertise things like their relative price of sigops vs bytes. Nodes may then choose to take this information into account in order to optimize their mempool policies for likelihood of consistency with future blocks. Since policy scripts provide only relative information on prices of different transaction properties rather than an absolute fee, this should not allow miners to vote fees up, although care would need to be taken they wouldn't be able to drive up prices by claiming common transaction types are at the high end of the fee scale. -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire
On a flood-fill network, you don't want to create a storm of I already have this replies. On Fri, Jul 18, 2014 at 1:39 PM, Kaz Wesley kezi...@gmail.com wrote: Peers exchanging mempool priority policies is great; that accomplishes the flexibility in what txes to remember that I was going for with the forget-filters, but much more neatly, with less overhead and some side benefits. Here's what I'm picturing now: - exchange priority policies in peer introductions - assign unique sequential IDs in the order the transactions were inved (per peer) - receiving a getdata for a tx updates last-known-peer-received inv to all invs up to the one referenced - include ID-last-received, last-known-peer-received in sparse block - reference txes in sparse block by index in receiver's prioritiziation with peer's sent invs up to ID-last-received and sender's prior invs up to last-known-peer-received Possible new messages: - sparseblock - invack message a node can send at times when it's received a bunch of invs it already has, so it hasn't acked with a getdata in a while - gettx: getdata, but using new sequential ID to save 28 bytes per tx It seems important for ordering policies to be able to be specified in as much detail as possible. Parameters that should be available: - total inputs - total outputs - bytes - coin days destroyed - net UTXO size change - sigops - is data carrier - is output raw multisig - age in mempool - what else? This parameter set should be extensible to allow for unforeseen future factors. Ordering policies should allow arbitrary algebraic combinations of their parameters, as well as thresholds. Boolean combinations of sub-policies would also be desirable. This could be implemented with a tx-script-like stack-based language, in which each supported tx property is pushed onto the stack by a particular opcode, and +-*//min/max/boolean operators combine them to yield the sort key. Difficult parameters: * Coin-days-destroyed: changes, peers need agreement on when (if?) it's recalculated. Probably can just not recalculate, but peers still need agreement on time seen to get CDD. * Age in mempool: seems intractable in terms of time, but could be done easily in terms of how many txes old is this sequential ID One potential pitfall: this allows for an environment of completely heterogeneous mempool policies. I think that's a good thing, but we need to avoid a situation where only least-common-denominator transactions make it farther than a hop or two, and we don't want nodes to have a strong preference for connecting to like-minded peers since clustering reduces overall connectivity. It may be worthwhile to add a parallel mechanism for relay policies, to differentiate between what a node would keep in its mempool vs. what it wouldn't even relay and doesn't want to see at all. Relay policies could be specified just like prioritization policies, but with the final stack value evaluated in a boolean context. An interesting additional use of policy-scripts would be a standardized way for miners to include a policy script in a coinbase, allowing miners a mechanism to advertise things like their relative price of sigops vs bytes. Nodes may then choose to take this information into account in order to optimize their mempool policies for likelihood of consistency with future blocks. Since policy scripts provide only relative information on prices of different transaction properties rather than an absolute fee, this should not allow miners to vote fees up, although care would need to be taken they wouldn't be able to drive up prices by claiming common transaction types are at the high end of the fee scale. -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development -- Jeff Garzik Bitcoin core developer and open source evangelist BitPay, Inc. https://bitpay.com/ -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Small update to BIP 62
On Fri, Jul 18, 2014 at 5:14 PM, Pieter Wuille pieter.wui...@gmail.com wrote: Hi all, I've sent a pull request to make a small change to BIP 62 (my anti-malleability proposal) which is still a draft; see: * https://github.com/bitcoin/bips/pull/90 (the request) * https://github.com/sipa/bips/blob/bip62up/bip-0062.mediawiki (the result) It makes two of the 7 new rules mandatory in new blocks, even for old-style transactions. Both are already non-standard since 0.8.0, and have no use cases in my opinion. Looks good to me. The reason for this change is dropping the requirement for signature verification engines to be bug-for-bug compatible with OpenSSL (which supports many non-standard encodings for signatures). Requiring strict DER compliance for signatures means any implementation just needs to support DER. This is certainly a good thing. Not even OpenSSL is guaranteed to be bug-for-bug compatible with its own prior versions forever, so better to strictly define what is allowed. Wladimir -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Small update to BIP 62
9. New signatures by the sender I'm not suggesting it be required, but it would be possible to mitigate this one by requiring that all signatures deterministically generate k per RFC6979. I'm using this in breadwallet. Aaron Voisine breadwallet.com On Fri, Jul 18, 2014 at 1:56 PM, Wladimir laa...@gmail.com wrote: On Fri, Jul 18, 2014 at 5:39 PM, Mike Hearn m...@plan99.net wrote: The rationale doesn't seem to apply to rule #4, what's so special about that one? 4. Non-push operations in scriptSig Any non-push operation in a scriptSig invalidates it. Having non-push operations in the scriptSig is a source of malleability, as there can be multiple sequences of opcodes that evaluate to the same result. Wladimir -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Decentralizing ming
I thought I'd chime in and point out some research results that might help. Even if they don't, there is a cool underlying technique that some of you might find interesting. The problem being tackled here is very similar to set reconciliation, where peer A thinks that the set of transactions that should be in the block is S_A, and peer B has actually included set S_B, and S_A and S_B are expected to not differ much. Ideally, one would like the communication complexity between A and B to be O(delta), not O(S_B) as it is right now. And ideally, one would like B to send a single message to A, and for A to figure out the difference between the two sets, without any lengthy back and forth communication. In essence, I would like to give you some magical packet that is pretty small and communicates just the delta between what you and I know. This paper from Cornell describes a scheme for achieving this: Yaron Minsky, Ari Trachtenberg, Richard Zippel: Set reconciliation with nearly optimal communication complexity. IEEE Transactions on Information Theory 49(9): 2213-2218 (2003) http://ipsit.bu.edu/documents/ieee-it3-web.pdf Those of you looking for a TL;DR should read the intro and then skip to page 8 for the example. The underlying trick is very cool, comes from the peer-to-peer/gossip literature, and it is underused. It'd be really cool if it could be applied to this problem to reduce the size of the packets. This approach has three benefits over the Bloom filter approach (if I understand the Bloom filter idea correctly): (1) Bloom filters require packets that are still O(S_A), (2) Bloom filters are probabilistic, so require extra complications when there is a hash collision. In the worst case, A might get confused about which transaction B actually included, which would lead to a fork. (I am not sure if I followed the Bloom filter idea fully -- this may not happen with the proposal, but it's a possibility with a naive Bloom filter implementation) (3) Bloom filters are interactive, so when A detects that B has included some transactions that A does not know about, it has to send a message to figure out what those transactions are. Set reconciliation is O(delta), non-probabilistic, and non-interactive. The naive version requires that one have some idea of the size of the delta, but I think the paper has some discussion of how to handle the delta estimate. I have not gone through the full exercise of actually applying this trick to the Bitcoin p2p protocol yet, but wanted to draw your attention to it. If someone is interested in applying this stuff to Bitcoin, I'd be happy to communicate further off list. - egs On Fri, Jul 18, 2014 at 6:44 AM, Jeff Garzik jgar...@bitpay.com wrote: Yes. That, and several other things. If you can figure out how to propagate a block without re-propagating all the transactions everyone already has, you address the large-blocks-slower-to-relay problem, and additionally create an incentive for miners to mine blocks consisting of publicly broadcast transactions (versus a bunch of secret ones mined with secret agreements). Democratizing transaction selection takes a bit of power away from the miners and gives it back to the network at large. GBT is another piece of that puzzle. On Fri, Jul 18, 2014 at 6:43 AM, Mike Hearn m...@plan99.net wrote: Oops, sorry, I see the subject line changed. This is what I get for working down the thread list top to bottom :) I think the best path forward now is to finish off getblocktemplate support in the various tools so it's possible to pool for payout purposes without giving up control of block creation modulo the coinbase. Combined with the recent sipa performance enhancing goodness, it would hopefully persuade some non-trivial chunk of hashpower to go back to running their own node and start the process of turning pools merely into payout trackers rather than block selectors. On Fri, Jul 18, 2014 at 12:41 PM, Mike Hearn m...@plan99.net wrote: Jeff, I think the message you're replying to got clipped. Satoshi's only comment AFAIK on the topic of GPU mining was to wish for a gentlemen's agreement to postpone it as long as possible, to help make sure the distribution of coins was as even as possible. Indeed this predated pooled mining. -- Jeff Garzik Bitcoin core developer and open source evangelist BitPay, Inc. https://bitpay.com/ -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net
Re: [Bitcoin-development] Decentralizing ming
My apologies for posting to the wrong thread. On Fri, Jul 18, 2014 at 5:51 PM, Emin Gün Sirer el33th4...@gmail.com wrote: I thought I'd chime in and point out some research results that might help. Even if they don't, there is a cool underlying technique that some of you might find interesting. The problem being tackled here is very similar to set reconciliation, where peer A thinks that the set of transactions that should be in the block is S_A, and peer B has actually included set S_B, and S_A and S_B are expected to not differ much. Ideally, one would like the communication complexity between A and B to be O(delta), not O(S_B) as it is right now. And ideally, one would like B to send a single message to A, and for A to figure out the difference between the two sets, without any lengthy back and forth communication. In essence, I would like to give you some magical packet that is pretty small and communicates just the delta between what you and I know. This paper from Cornell describes a scheme for achieving this: Yaron Minsky, Ari Trachtenberg, Richard Zippel: Set reconciliation with nearly optimal communication complexity. IEEE Transactions on Information Theory 49(9): 2213-2218 (2003) http://ipsit.bu.edu/documents/ieee-it3-web.pdf Those of you looking for a TL;DR should read the intro and then skip to page 8 for the example. The underlying trick is very cool, comes from the peer-to-peer/gossip literature, and it is underused. It'd be really cool if it could be applied to this problem to reduce the size of the packets. This approach has three benefits over the Bloom filter approach (if I understand the Bloom filter idea correctly): (1) Bloom filters require packets that are still O(S_A), (2) Bloom filters are probabilistic, so require extra complications when there is a hash collision. In the worst case, A might get confused about which transaction B actually included, which would lead to a fork. (I am not sure if I followed the Bloom filter idea fully -- this may not happen with the proposal, but it's a possibility with a naive Bloom filter implementation) (3) Bloom filters are interactive, so when A detects that B has included some transactions that A does not know about, it has to send a message to figure out what those transactions are. Set reconciliation is O(delta), non-probabilistic, and non-interactive. The naive version requires that one have some idea of the size of the delta, but I think the paper has some discussion of how to handle the delta estimate. I have not gone through the full exercise of actually applying this trick to the Bitcoin p2p protocol yet, but wanted to draw your attention to it. If someone is interested in applying this stuff to Bitcoin, I'd be happy to communicate further off list. - egs On Fri, Jul 18, 2014 at 6:44 AM, Jeff Garzik jgar...@bitpay.com wrote: Yes. That, and several other things. If you can figure out how to propagate a block without re-propagating all the transactions everyone already has, you address the large-blocks-slower-to-relay problem, and additionally create an incentive for miners to mine blocks consisting of publicly broadcast transactions (versus a bunch of secret ones mined with secret agreements). Democratizing transaction selection takes a bit of power away from the miners and gives it back to the network at large. GBT is another piece of that puzzle. On Fri, Jul 18, 2014 at 6:43 AM, Mike Hearn m...@plan99.net wrote: Oops, sorry, I see the subject line changed. This is what I get for working down the thread list top to bottom :) I think the best path forward now is to finish off getblocktemplate support in the various tools so it's possible to pool for payout purposes without giving up control of block creation modulo the coinbase. Combined with the recent sipa performance enhancing goodness, it would hopefully persuade some non-trivial chunk of hashpower to go back to running their own node and start the process of turning pools merely into payout trackers rather than block selectors. On Fri, Jul 18, 2014 at 12:41 PM, Mike Hearn m...@plan99.net wrote: Jeff, I think the message you're replying to got clipped. Satoshi's only comment AFAIK on the topic of GPU mining was to wish for a gentlemen's agreement to postpone it as long as possible, to help make sure the distribution of coins was as even as possible. Indeed this predated pooled mining. -- Jeff Garzik Bitcoin core developer and open source evangelist BitPay, Inc. https://bitpay.com/ -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now.
Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire
I thought I'd chime in and point out some research results that might help. Even if they don't, there is a cool underlying technique that some of you might find interesting. The problem being tackled here is very similar to set reconciliation, where peer A thinks that the set of transactions that should be in the block is S_A, and peer B has actually included set S_B, and S_A and S_B are expected to not differ much. Ideally, one would like the communication complexity between A and B to be O(delta), not O(S_B) as it is right now. And ideally, one would like B to send a single message to A, and for A to figure out the difference between the two sets, without any lengthy back and forth communication. In essence, I would like to give you some magical packet that is pretty small and communicates just the delta between what you and I know. This paper from Cornell describes a scheme for achieving this: Yaron Minsky, Ari Trachtenberg, Richard Zippel: Set reconciliation with nearly optimal communication complexity. IEEE Transactions on Information Theory 49(9): 2213-2218 (2003) http://ipsit.bu.edu/documents/ieee-it3-web.pdf Those of you looking for a TL;DR should read the intro and then skip to page 8 for the example. The underlying trick is very cool, comes from the peer-to-peer/gossip literature, and it is underused. It'd be really cool if it could be applied to this problem to reduce the size of the packets. This approach has three benefits over the Bloom filter approach (if I understand the Bloom filter idea correctly): (1) Bloom filters require packets that are still O(S_A), (2) Bloom filters are probabilistic, so require extra complications when there is a hash collision. In the worst case, A might get confused about which transaction B actually included, which would lead to a fork. (I am not sure if I followed the Bloom filter idea fully -- this may not happen with the proposal, but it's a possibility with a naive Bloom filter implementation) (3) Bloom filters are interactive, so when A detects that B has included some transactions that A does not know about, it has to send a message to figure out what those transactions are. Set reconciliation is O(delta), non-probabilistic, and non-interactive. The naive version requires that one have some idea of the size of the delta, but I think the paper has some discussion of how to handle the delta estimate. I have not gone through the full exercise of actually applying this trick to the Bitcoin p2p protocol yet, but wanted to draw your attention to it. If someone is interested in applying this stuff to Bitcoin, I'd be happy to communicate further off list. - egs On Fri, Jul 18, 2014 at 12:55 PM, Jeff Garzik jgar...@bitpay.com wrote: Related: We must handle some legitimate miner-privately-mined cases, such as miner payout TXs (outside coinbase) or side chain conditional TXs[1]. [1] https://bitcointalk.org/index.php?topic=676703.msg7682680#msg7682680 On Fri, Jul 18, 2014 at 3:51 PM, Kaz Wesley kezi...@gmail.com wrote: I've updated the gist, and added an additional proposal that I think meshes well: https://gist.github.com/kazcw/43c97d3924326beca87d#ultra-fast-block-validation sparseblocks + UFBV would tighten the new-block process to this (when txes have been received in advance): - receive block (~2kB for 1000 tx) - check whether block contains txes known to belong to conflict-sets, and if so whether more than one tx from a single conflict-set has been included (a few operations on very small sets) - relay block (~2kB) The benefits of these changes only occur when the transactions have been seen in advance, but incentivizing ahead-of-block transaction propogation is a plus, as Jeff mentioned; working on a block without first ensuring peers have its transactions would be very expensive from a miner's point of view. -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development -- Jeff Garzik Bitcoin core developer and open source evangelist BitPay, Inc. https://bitpay.com/ -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___
Re: [Bitcoin-development] Squashing redundant tx data in blocks on the wire
On Fri, Jul 18, 2014 at 5:54 PM, Emin Gün Sirer el33th4...@gmail.com wrote: The problem being tackled here is very similar to set reconciliation, where peer A thinks that the set of transactions that should be in the block is S_A, Most things I've seen working in this space are attempting to minimize the data transfered. At least for the miner-interested case the round complexity is much more important because a single RTT is enough to basically send the whole block on a lot of very relevant paths. I know much better is possible (see up-thread where I linked to an old proposal to use forward error correction to transfer with low data transfer (but not optimal) and negligible probability of needing a round-trip, with a tradeoff for more overhead for lower roundtrip probability). -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Small update to BIP 62
On Fri, Jul 18, 2014 at 3:03 PM, Aaron Voisine vois...@gmail.com wrote: 9. New signatures by the sender I'm not suggesting it be required, but it would be possible to mitigate this one by requiring that all signatures deterministically generate k per RFC6979. I'm using this in breadwallet. Nope. Your homework assignment is to explain why. :) -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Small update to BIP 62
Well, you could always create a transaction with a different signature hash, say, by changing something trivial like nLockTime, or changing the order of inputs or outputs. Is that what you're talking about? Or is there some sophistry I'm ignorant of having to do with the elliptic curve math in the signature itself? Aaron Voisine breadwallet.com On Fri, Jul 18, 2014 at 6:28 PM, Gregory Maxwell gmaxw...@gmail.com wrote: On Fri, Jul 18, 2014 at 3:03 PM, Aaron Voisine vois...@gmail.com wrote: 9. New signatures by the sender I'm not suggesting it be required, but it would be possible to mitigate this one by requiring that all signatures deterministically generate k per RFC6979. I'm using this in breadwallet. Nope. Your homework assignment is to explain why. :) -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] Signature with negative integer?
Hey all, I'm wondering if anyone can help explain to me tx 70f7c15c6f62139cc41afa858894650344eda9975b46656d893ee59df8914a3d... (https://blockchain.info/tx/70f7c15c6f62139cc41afa858894650344eda9975b46656d893ee59df8914a3d) The input signature script is: 304402206b5c3b1c86748dcf328b9f3a65e10085afcf5d1af5b40970d8ce3a9355e06b5b0220cdbdc23e6d3618e47056fccc60c5f73d1a542186705197e5791e97f0e6582a3201 Which decodes to: r= 48560432700441876832361368709121298776045893858160378595187765610521057848155 s= -22732680560694206332190468058638664750027418114195068375538144640549433890254 (http://lapo.it/asn1js/#304402206B5C3B1C86748DCF328B9F3A65E10085AFCF5D1AF5B40970D8CE3A9355E06B5B0220CDBDC23E6D3618E47056FCCC60C5F73D1A542186705197E5791E97F0E6582A32) The ECC library I'm using is failing to verify this, which I think makes sense, since I the point needs to be positive, no? But it is obviously valid, as it has been verified and spent. I have tried simply modulo curve.order to positive-ify it, but that didn't seem to work either. Given a point P (with Py 0) is there some fancy way to bring it into the elliptic curve space, such that Px = 0 and Py = 0? Thanks! RicMoo .·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸¸.·´¯`·.¸(((º Richard Moore ~ Founder Genetic Mistakes Software inc. phone: (778) 882-6125 email: ric...@geneticmistakes.com www: http://GeneticMistakes.com -- Want fast and easy access to all the code in your enterprise? Index and search up to 200,000 lines of code with a free copy of Black Duck Code Sight - the same software that powers the world's largest code search on Ohloh, the Black Duck Open Hub! Try it now. http://p.sf.net/sfu/bds ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
