[Bitcoin-development] Virtual Notary.
Hi everyone, Given the recent discussions on projects that use the Bitcoin blockchain to record factoids, people on this list might be interested in the Virtual Notary project. Virtual Notary is essentially an online witness (aka attestor) to online factoids. It can provide: * proof of Bitcoin funds (without revealing public addresses or fund location on the blockchain) * proof of Bitcoin address ownership * proof of Tweet * proof of real estate value * proof of DNS ownership * proof of existence * proof of web page contents * proof of weather conditions The factoids can be recorded on the blockchain (if you pay for the transaction with Bitcoin or PayPal), or they can be part of a free attestation chain that we maintain. The website provides a permanent URL to the factoids it generates; it also provides an X.509 certificate that you can download and keep safe in perpetuity, independent of the website. The link to the website is here: http://virtual-notary.org The link to the writeup describing the various factoids and their use cases is here: http://hackingdistributed.com/2013/06/20/virtual-notary-intro/ We are actively looking for people who are interested in developing the service further. Specifically, if you have suggestions for how to extend the service, for new proof/factoid types, or for how to build a business case around the core idea, please let us know. Best, - egs -- One dashboard for servers and applications across Physical-Virtual-Cloud Widest out-of-the-box monitoring support with 50+ applications Performance metrics, stats and reports that give you Actionable Insights Deep dive visibility with transaction tracing using APM Insight. http://ad.doubleclick.net/ddm/clk/290420510;117567292;y___ 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. http
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 ___
