public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed

* [Bitcoin-development] Auto-generated miner backbone
@ 2013-11-04 11:26 Mike Hearn
  2013-11-04 11:53 ` Peter Todd
                   ` (3 more replies)
  0 siblings, 4 replies; 31+ messages in thread
From: Mike Hearn @ 2013-11-04 11:26 UTC (permalink / raw)
  To: Bitcoin Dev

[-- Attachment #1: Type: text/plain, Size: 1224 bytes --]

W.R.T. this paper and the oft-discussed miner backbone,

  http://arxiv.org/pdf/1311.0243v1.pdf

I'm wondering about an alternative protocol change that perhaps has less
subtle implications than their suggested change. Rather than address the
problem by assuming the network is full of sybil nodes and changing the
rules for selecting the chain to build on, how about if we wrote code to
automatically build a miner backbone by having IP addresses of nodes
embedded into coinbases, then having any bitcoind that is creating work
automatically connect to IPs that appeared in enough recent blocks?

This would have the effect of automatically linking all the major pools
together, with no administration overhead.

For bonus points, the IPs could be IPv6 and then the trick we use to pack
hidden services into IPv6 address space would allow nodes to be reached via
Tor. This might be useful in the case of pools that don't to reveal the
location of their bitcoin node[s], like for anti-DoS reasons.

It feels like this should be achievable with a few days of solid coding and
a couple of new command line flags, and the impact is much easier to reason
about than a fundamental rule change like the one proposed by the paper.

[-- Attachment #2: Type: text/html, Size: 1439 bytes --]

^ permalink raw reply	[flat|nested] 31+ messages in thread

• * Re: [Bitcoin-development] Auto-generated miner backbone
    2013-11-04 11:26 [Bitcoin-development] Auto-generated miner backbone Mike Hearn
  @ 2013-11-04 11:53 ` Peter Todd
    2013-11-04 12:00   ` Mike Hearn
    2013-11-04 11:58 ` [Bitcoin-development] Auto-generated miner backbone Michael Gronager
                     ` (2 subsequent siblings)
    3 siblings, 1 reply; 31+ messages in thread
  From: Peter Todd @ 2013-11-04 11:53 UTC (permalink / raw)
    To: Mike Hearn; +Cc: Bitcoin Dev
  
  [-- Attachment #1: Type: text/plain, Size: 2865 bytes --]
  
  On Mon, Nov 04, 2013 at 12:26:30PM +0100, Mike Hearn wrote:
  > W.R.T. this paper and the oft-discussed miner backbone,
  > 
  >   http://arxiv.org/pdf/1311.0243v1.pdf
  > 
  > I'm wondering about an alternative protocol change that perhaps has less
  > subtle implications than their suggested change. Rather than address the
  > problem by assuming the network is full of sybil nodes and changing the
  > rules for selecting the chain to build on, how about if we wrote code to
  > automatically build a miner backbone by having IP addresses of nodes
  > embedded into coinbases, then having any bitcoind that is creating work
  > automatically connect to IPs that appeared in enough recent blocks?
  
  I proposed this as a means of giving a mechanism for wallets to get
  non-sybilled peers as well.
  
  > This would have the effect of automatically linking all the major pools
  > together, with no administration overhead.
  > 
  > For bonus points, the IPs could be IPv6 and then the trick we use to pack
  > hidden services into IPv6 address space would allow nodes to be reached via
  > Tor. This might be useful in the case of pools that don't to reveal the
  > location of their bitcoin node[s], like for anti-DoS reasons.
  > 
  > It feels like this should be achievable with a few days of solid coding and
  > a couple of new command line flags, and the impact is much easier to reason
  > about than a fundamental rule change like the one proposed by the paper.
  
  Doing so encourages pools to only bother connecting to other pools,
  which is a strong centralizing force. But given the nasty incentives
  present anyway - it's in your advantage to distribute your blocks to no
  more than a majority of hashing power if you can do so consistently -
  I'm unconvinced that this won't happen anyway.
  
  The maximal benefit would be if two sets of addresses were published:
  public and private. The issue with publishing addresses is DoS attacks,
  but publishing Tor addresses doesn't stop attacks. What would discourage
  attacks however would be to encrypt that data such that only the
  creators of specific prior blocks could decrypt it. This limits the
  audience to those with incentives not to commit a DoS attack. (DoS
  attack the IP, and you'll no longer get preferential peering)
  
  Say what you want about centralization, but for the pools involved it's
  a good idea.
  
  
  On a technical level, the coinbase is limited in size, and people use it
  for other purposes, so lets define a standard where this data is stored
  in an OP_RETURN txout of the form:
  
  OP_RETURN <key> <value> <key> <value> ...
  
  Multiple values with the same key should be allowed. This data should be
  placed in the last txout so that SPV nodes can eventually be given it
  with a SHA256 midstate.
  
  -- 
  'peter'[:-1]@petertodd.org
  00000000000000080e395c361bdf9db583d5f4c0e144f476c229285b15eae59c
  
  [-- Attachment #2: Digital signature --]
  [-- Type: application/pgp-signature, Size: 685 bytes --]
  
  ^ permalink raw reply	[flat|nested] 31+ messages in thread

• • * Re: [Bitcoin-development] Auto-generated miner backbone
      2013-11-04 11:53 ` Peter Todd
    @ 2013-11-04 12:00   ` Mike Hearn
      2013-11-04 18:16     ` [Bitcoin-development] Committing to extra block data/a better merge-mine standard Peter Todd
      0 siblings, 1 reply; 31+ messages in thread
    From: Mike Hearn @ 2013-11-04 12:00 UTC (permalink / raw)
      To: Peter Todd; +Cc: Bitcoin Dev
    
    [-- Attachment #1: Type: text/plain, Size: 1217 bytes --]
    
    On Mon, Nov 4, 2013 at 12:53 PM, Peter Todd <pete@petertodd•org> wrote:
    
    > I proposed this as a means of giving a mechanism for wallets to get
    > non-sybilled peers as well.
    >
    
    Ah yes, good point.
    
    
    > Doing so encourages pools to only bother connecting to other pools,
    > which is a strong centralizing force.
    >
    
    They could already create such a setup, but we don't observe it in practice.
    
    
    > On a technical level, the coinbase is limited in size, and people use it
    > for other purposes, so lets define a standard ....
    
    
    Given that IP address data is inherently transient, perhaps a better
    solution is to define a short hash in the coinbase that commits to extra
    data that is relayed along with block data (e.g. appended to the block
    message). It can then be stored temporarily in the block db and erased
    after some time, like a few months. It would therefore not really be a part
    of the chain, but could be extended as we see fit with any other
    semi-transient data required. A new "getextra" message would let nodes
    query for it.
    
    The hash can be short because it doesn't have to survive brute forcing
    attacks longer than the expected validity period of the transient data
    anyway. 80 bits would probably be overkill.
    
    [-- Attachment #2: Type: text/html, Size: 2011 bytes --]
    
    ^ permalink raw reply	[flat|nested] 31+ messages in thread

  • • * [Bitcoin-development] Committing to extra block data/a better merge-mine standard
        2013-11-04 12:00   ` Mike Hearn
      @ 2013-11-04 18:16     ` Peter Todd
        2013-11-04 18:32       ` Peter Todd
                               ` (2 more replies)
        0 siblings, 3 replies; 31+ messages in thread
      From: Peter Todd @ 2013-11-04 18:16 UTC (permalink / raw)
        To: Mike Hearn; +Cc: Bitcoin Dev
      
      [-- Attachment #1: Type: text/plain, Size: 2906 bytes --]
      
      On Mon, Nov 04, 2013 at 01:00:16PM +0100, Mike Hearn wrote:
      > Given that IP address data is inherently transient, perhaps a better
      > solution is to define a short hash in the coinbase that commits to extra
      > data that is relayed along with block data (e.g. appended to the block
      > message). It can then be stored temporarily in the block db and erased
      > after some time, like a few months. It would therefore not really be a part
      > of the chain, but could be extended as we see fit with any other
      > semi-transient data required. A new "getextra" message would let nodes
      > query for it.
      > 
      > The hash can be short because it doesn't have to survive brute forcing
      > attacks longer than the expected validity period of the transient data
      > anyway. 80 bits would probably be overkill.
      
      No sense in compromising - you need a whole merkle path to prove the
      extra data is valid so you might as well make this a full 256 bits;
      another 22 bytes is insignificant compared to the size of the path.
      
      Again, the right way to do this is define the standard to use the last
      txout so that midstate compression can be applied in the future. We can
      re-use this for merge-mining and other commitments easily by defining a
      simple standard based on defined path directions. Essentially for each
      thing you might want to commit, perhaps a merge-mined coin, a p2pool
      share, a UTXO commitment, whatever, generate a random 128-bit UUID.
      
      Now interpret the bits of that UUID as an allowed path: 0 = left, 1 =
      right, from the top of the tree. When you build the tree, make sure
      everything that is going to be committed to uses it's allowed path; the
      tree will look a bit jagged. If everyone picks their per-purpose UUIDs
      randomly the paths won't collide for very many levels on average, and
      path lengths will remain short. Validating that some given data was
      committed properly is simple and easy: just check the path, and check
      that the directions from the top of the tree followed the spec.
      
      For timestamping, just pick any empty spot in the tree.
      
      You'll want to put some "reasonable" limit on actual path lengths, just
      pick something like 32 levels; if applications pick their UUIDs honestly
      a collision will be very unlikely. You can also make the allowed paths
      block specific by defining them as H(uuid | nonce), with nonce as an
      optional PUSHDATA just prior to the commitment pushdata, allowing overly
      long paths to be eliminated entirely by simply incrmenting the nonce.
      
      Unlike the original, broken, merge-mining standard alt-coins have used
      this actually works, extends indefinitely, and is simple and easy to
      validate given a single merkle-path for each purpose. Generating the
      trees of commitments is a bit convoluted, but at least that code only
      needs to be written once.
      
      -- 
      'peter'[:-1]@petertodd.org
      0000000000000002c43b3c05c0ed0842317747f0d1e3982489d0a51e7c8a05a3
      
      [-- Attachment #2: Digital signature --]
      [-- Type: application/pgp-signature, Size: 490 bytes --]
      
      ^ permalink raw reply	[flat|nested] 31+ messages in thread

    • • * Re: [Bitcoin-development] Committing to extra block data/a better merge-mine standard
          2013-11-04 18:16     ` [Bitcoin-development] Committing to extra block data/a better merge-mine standard Peter Todd
        @ 2013-11-04 18:32       ` Peter Todd
          2013-11-04 19:11       ` Mark Friedenbach
          2013-11-04 19:38       ` Mike Hearn
          2 siblings, 0 replies; 31+ messages in thread
        From: Peter Todd @ 2013-11-04 18:32 UTC (permalink / raw)
          To: Mike Hearn; +Cc: Bitcoin Dev
        
        [-- Attachment #1: Type: text/plain, Size: 640 bytes --]
        
        On Mon, Nov 04, 2013 at 01:16:49PM -0500, Peter Todd wrote:
        > You'll want to put some "reasonable" limit on actual path lengths, just
        > pick something like 32 levels; if applications pick their UUIDs honestly
        > a collision will be very unlikely. You can also make the allowed paths
        > block specific by defining them as H(uuid | nonce), with nonce as an
        
        This could be H(uuid | nLockTime) Coinbase transactions still have a
        nLockTime, and while it's generally left at zero it can be any value
        valid for a transaction in the block.
        
        -- 
        'peter'[:-1]@petertodd.org
        00000000000000086d6d5b17d979d44a24a68bcf92eb9aea18351e4f6bc485b6
        
        [-- Attachment #2: Digital signature --]
        [-- Type: application/pgp-signature, Size: 490 bytes --]
        
        ^ permalink raw reply	[flat|nested] 31+ messages in thread

      • * Re: [Bitcoin-development] Committing to extra block data/a better merge-mine standard
          2013-11-04 18:16     ` [Bitcoin-development] Committing to extra block data/a better merge-mine standard Peter Todd
          2013-11-04 18:32       ` Peter Todd
        @ 2013-11-04 19:11       ` Mark Friedenbach
          2013-11-15 22:06         ` Peter Todd
          2013-11-04 19:38       ` Mike Hearn
          2 siblings, 1 reply; 31+ messages in thread
        From: Mark Friedenbach @ 2013-11-04 19:11 UTC (permalink / raw)
          To: bitcoin-development
        
        -----BEGIN PGP SIGNED MESSAGE-----
        Hash: SHA1
        
        On 11/4/13 10:16 AM, Peter Todd wrote:
        > Again, the right way to do this is define the standard to use the
        > last txout so that midstate compression can be applied in the
        > future. We can re-use this for merge-mining and other commitments
        > easily by defining a simple standard based on defined path
        > directions. Essentially for each thing you might want to commit,
        > perhaps a merge-mined coin, a p2pool share, a UTXO commitment,
        > whatever, generate a random 128-bit UUID.
        > 
        > Now interpret the bits of that UUID as an allowed path: 0 = left, 1
        > = right, from the top of the tree. When you build the tree, make
        > sure everything that is going to be committed to uses it's allowed
        > path; the tree will look a bit jagged. If everyone picks their
        > per-purpose UUIDs randomly the paths won't collide for very many
        > levels on average, and path lengths will remain short. Validating
        > that some given data was committed properly is simple and easy:
        > just check the path, and check that the directions from the top of
        > the tree followed the spec.
        
        You mean... an authenticated prefix tree? Composable/commutative
        properties are not needed as far as I can see, so you could make the
        path validation, traversal, and proof size smaller by using level
        compression.
        
        I had previously proposed to this list a hash256-to-UUID mechanism
        explicitly for this purpose. Recap: use 122 of the low 128 bits of the
        aux-chain's genesis block to form a version=4 (random) or version=6
        (previously unused) UUID. However since making that proposal I am now
        leaning towards simply using the hash of the genesis block directly to
        identify aux chains since level compression will allow longer keys
        with the same path length.
        
        I'm in the middle of writing BIPs to this end, among my many other
        tasks. But basically it's the same as you describe ("OP_RETURN
        <32-byte auth tree root>" for the last output), except keys don't
        necessarily have to be UUIDs.
        
        If there is general interest, I can make finishing this a higher priority.
        
        Mark
        -----BEGIN PGP SIGNATURE-----
        Version: GnuPG/MacGPG2 v2.0.19 (Darwin)
        Comment: GPGTools - http://gpgtools.org
        Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
        
        iQIcBAEBAgAGBQJSd/FmAAoJEAdzVfsmodw4pA0QALtgKLKsMNFocUanKGNp5T1F
        918IjFt/HASRMs4GXiPpIeTB+o5Id6aCsg1ikKRuL9xD+WKoSyo83JP5UmcxGjFA
        WTPi/0/ArYRh8L7ECvWoBSanNrun3z72p3KMI1Aa8qcJCgWbPx88AYeJv0Ki4JOo
        1Pxc883772bOJnazrh4f/C4gcrqrlgs29PwI1rc3yCD9dmJhVmkz+O0/yfq+U8Gg
        FXrpqR14mUM36wGX2HjqEual7Ry/7TEz5Ne4o8uncaVHtGgaYVw45a5Hk6rdo1rH
        F3EV9nIpsLhGyqbKPqSxSju2h3eYQxQXKUP14mJS+ja/mKFXVc3PXDV+IHtXAplk
        4gW8vtTWtVIDJAGTTh5RkJu5yAr57vq9lUMTNGGk6v1C3xOPP2C097sHRLaD4kD+
        olsw5M9NW/Qpn1X3SCN3K85f7dvV3+fucmWL8mPM9KMLfc38fgs7I5SQgurMngsS
        2D5jSwcZVjI/4n6ocgK3Y66yKC5xuzOOi2ZV+pPM38TjUeCF8fbjRnoIWyaBPDWy
        mKA0bJiw5NMzi+IsNK5YDS5Gqb3qxS6tYLCp1+hesW3pBj35Zv/LdSh5DyecRETW
        J0ye56lw/DfRAfNf+YERvrznqC2WVDZcQaElACq8R/nPJ2HD53p+SfxMSbljVO+I
        SDsDOSvAzfQjQBLGdkx7
        =5fPS
        -----END PGP SIGNATURE-----
        
        
        
        ^ permalink raw reply	[flat|nested] 31+ messages in thread

      • • * Re: [Bitcoin-development] Committing to extra block data/a better merge-mine standard
            2013-11-04 19:11       ` Mark Friedenbach
          @ 2013-11-15 22:06         ` Peter Todd
            0 siblings, 0 replies; 31+ messages in thread
          From: Peter Todd @ 2013-11-15 22:06 UTC (permalink / raw)
            To: Mark Friedenbach; +Cc: bitcoin-development
          
          [-- Attachment #1: Type: text/plain, Size: 2181 bytes --]
          
          On Mon, Nov 04, 2013 at 11:11:34AM -0800, Mark Friedenbach wrote:
          > > Now interpret the bits of that UUID as an allowed path: 0 = left, 1
          > > = right, from the top of the tree. When you build the tree, make
          > > sure everything that is going to be committed to uses it's allowed
          > > path; the tree will look a bit jagged. If everyone picks their
          > > per-purpose UUIDs randomly the paths won't collide for very many
          > > levels on average, and path lengths will remain short. Validating
          > > that some given data was committed properly is simple and easy:
          > > just check the path, and check that the directions from the top of
          > > the tree followed the spec.
          > 
          > You mean... an authenticated prefix tree? Composable/commutative
          > properties are not needed as far as I can see, so you could make the
          > path validation, traversal, and proof size smaller by using level
          > compression.
          
          You don't need level compression if you adopt my per-block randomization
          idea. I think we'd be better off keeping the proofs as simple as
          possible, just dumb merkle paths.
          
          > I had previously proposed to this list a hash256-to-UUID mechanism
          > explicitly for this purpose. Recap: use 122 of the low 128 bits of the
          > aux-chain's genesis block to form a version=4 (random) or version=6
          > (previously unused) UUID. However since making that proposal I am now
          > leaning towards simply using the hash of the genesis block directly to
          > identify aux chains since level compression will allow longer keys
          > with the same path length.
          
          I mentioned UUID more in spirit than in terms of the official UUID
          standard; any large randomly picked integer is fine.
          
          > If there is general interest, I can make finishing this a higher priority.
          
          Wouldn't hurt to run the idea past forrestv, given p2pool will be
          affected as it'd need to adopt the standard. He's run into some oddness
          with mining hardware and nonces that would be good to understand. (note
          how p2pool blocks don't commit to a fully random hash - there's some
          extra bytes in there due to stratum or something IIRC)
          
          -- 
          'peter'[:-1]@petertodd.org
          000000000000000601a5b2f2b4a597851fdf00f6fc3572bbc03f26857c170032
          
          [-- Attachment #2: Digital signature --]
          [-- Type: application/pgp-signature, Size: 490 bytes --]
          
          ^ permalink raw reply	[flat|nested] 31+ messages in thread

      • * Re: [Bitcoin-development] Committing to extra block data/a better merge-mine standard
          2013-11-04 18:16     ` [Bitcoin-development] Committing to extra block data/a better merge-mine standard Peter Todd
          2013-11-04 18:32       ` Peter Todd
          2013-11-04 19:11       ` Mark Friedenbach
        @ 2013-11-04 19:38       ` Mike Hearn
          2013-11-04 19:53         ` Mark Friedenbach
          2 siblings, 1 reply; 31+ messages in thread
        From: Mike Hearn @ 2013-11-04 19:38 UTC (permalink / raw)
          To: Peter Todd; +Cc: Bitcoin Dev
        
        [-- Attachment #1: Type: text/plain, Size: 664 bytes --]
        
        I like the UUID-as-path idea. That resolves the problem of how to share the
        alt-chain merkle tree quite nicely.
        
        On Mon, Nov 4, 2013 at 7:16 PM, Peter Todd <pete@petertodd•org> wrote:
        
        > No sense in compromising - you need a whole merkle path to prove the
        > extra data is valid so you might as well make this a full 256 bits;
        >
        
        The Merkle branch doesn't get stored indefinitely though, whereas the
        coinbase hash does. The data stored in the coinbase [output] can always
        just be the 256-bit root hash truncated to less.
        
        I doubt the additional bytes make much difference really, so the additional
        complexity may not be worth it. But it wouldn't be an issue to do.
        
        [-- Attachment #2: Type: text/html, Size: 1015 bytes --]
        
        ^ permalink raw reply	[flat|nested] 31+ messages in thread

      • • * Re: [Bitcoin-development] Committing to extra block data/a better merge-mine standard
            2013-11-04 19:38       ` Mike Hearn
          @ 2013-11-04 19:53         ` Mark Friedenbach
            2013-11-04 20:10           ` Mike Hearn
            0 siblings, 1 reply; 31+ messages in thread
          From: Mark Friedenbach @ 2013-11-04 19:53 UTC (permalink / raw)
            To: bitcoin-development
          
          -----BEGIN PGP SIGNED MESSAGE-----
          Hash: SHA1
          
          On 11/4/13 11:38 AM, Mike Hearn wrote:
          > The Merkle branch doesn't get stored indefinitely though, whereas
          > the coinbase hash does. The data stored in the coinbase [output]
          > can always just be the 256-bit root hash truncated to less.
          > 
          > I doubt the additional bytes make much difference really, so the 
          > additional complexity may not be worth it. But it wouldn't be an
          > issue to do.
          
          The bits make a difference if you are merged mining. You can use the
          birthday attack to construct two data trees whose hash match the
          (truncated) value, each containing separate aux block headers. This
          allows you to double-count the bitcoin PoW for more than one aux block
          on the same chain, potentially facilitating aux chain attacks.
          
          If you want 128 bits of security for merged mined aux chains, you need
          256 bits of hash in the coinbase.
          -----BEGIN PGP SIGNATURE-----
          Version: GnuPG/MacGPG2 v2.0.19 (Darwin)
          Comment: GPGTools - http://gpgtools.org
          Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
          
          iQIcBAEBAgAGBQJSd/shAAoJEAdzVfsmodw48a0P/RaCOctBDvhU0THnsUw6nRBm
          A8oH3Kpio4ZltU4oIT0tznZbUOG2j2xVrmATqXDYOZQ6FuGihjmkKJ9jHgl57pb5
          0qDdCBiEuWtLIh2+Awrb3Y0s8czyCQP9/1CJyzdEFmI8rSwCaqJMa6B2Ny6Xz6+8
          eiK45YdXCPgdTAb56FKOi9WzOe0g1aOO5KiUOci22xRkXvh4qPYrt2F0LIgjZTdC
          koyXU6dcKON9H8Cecu+ag7jJ5A9ZDj7oIq5rflEyolh2V4ie0tGQ50rFGg/ii6iQ
          Tz9AWwigsHEkuinBTuN5041Xb8nAgHLvA60RQ41lWUHJxfAvDE+wN6NqgHmMVaRo
          NHqlZcCuEl1jn7HW81XQTpgarrXHk1G7b2vK10pB/lUxUNIstZvCSjcp8QdtmC9v
          tIhC2czSnsQaE6kIBuHxDNZxOlZ8DxBYCAgXSkycwznwzGhFPP0xB1lV9HfaP5+i
          aikmx5SQmqBXQQKsxmIacoykrfu5x+O2TB/bq8JhJ1ak2jG9LVFyQqjorABVAgA7
          pLEN6EomWht5qstaLVfHYpNsLMf6WA7UzRG08HKItUeDPtG7bDx8vBx5TvIUjT44
          A0i09bOt8ZIgp+lJ8lFLWiPLChViAoy7fqKy2vrdsZerOF3l4LUQeQO/xnfZc+dG
          AEG+7iCBOMxJSVoJ5bP6
          =nydG
          -----END PGP SIGNATURE-----
          
          
          
          ^ permalink raw reply	[flat|nested] 31+ messages in thread

        • • * Re: [Bitcoin-development] Committing to extra block data/a better merge-mine standard
              2013-11-04 19:53         ` Mark Friedenbach
            @ 2013-11-04 20:10           ` Mike Hearn
              0 siblings, 0 replies; 31+ messages in thread
            From: Mike Hearn @ 2013-11-04 20:10 UTC (permalink / raw)
              To: Mark Friedenbach; +Cc: Bitcoin Dev
            
            [-- Attachment #1: Type: text/plain, Size: 2680 bytes --]
            
            Yes, sure. I was talking about the case of transiently relayed data, like
            IP addresses.
            
            
            On Mon, Nov 4, 2013 at 8:53 PM, Mark Friedenbach <mark@monetize•io> wrote:
            
            > -----BEGIN PGP SIGNED MESSAGE-----
            > Hash: SHA1
            >
            > On 11/4/13 11:38 AM, Mike Hearn wrote:
            > > The Merkle branch doesn't get stored indefinitely though, whereas
            > > the coinbase hash does. The data stored in the coinbase [output]
            > > can always just be the 256-bit root hash truncated to less.
            > >
            > > I doubt the additional bytes make much difference really, so the
            > > additional complexity may not be worth it. But it wouldn't be an
            > > issue to do.
            >
            > The bits make a difference if you are merged mining. You can use the
            > birthday attack to construct two data trees whose hash match the
            > (truncated) value, each containing separate aux block headers. This
            > allows you to double-count the bitcoin PoW for more than one aux block
            > on the same chain, potentially facilitating aux chain attacks.
            >
            > If you want 128 bits of security for merged mined aux chains, you need
            > 256 bits of hash in the coinbase.
            > -----BEGIN PGP SIGNATURE-----
            > Version: GnuPG/MacGPG2 v2.0.19 (Darwin)
            > Comment: GPGTools - http://gpgtools.org
            > Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
            >
            > iQIcBAEBAgAGBQJSd/shAAoJEAdzVfsmodw48a0P/RaCOctBDvhU0THnsUw6nRBm
            > A8oH3Kpio4ZltU4oIT0tznZbUOG2j2xVrmATqXDYOZQ6FuGihjmkKJ9jHgl57pb5
            > 0qDdCBiEuWtLIh2+Awrb3Y0s8czyCQP9/1CJyzdEFmI8rSwCaqJMa6B2Ny6Xz6+8
            > eiK45YdXCPgdTAb56FKOi9WzOe0g1aOO5KiUOci22xRkXvh4qPYrt2F0LIgjZTdC
            > koyXU6dcKON9H8Cecu+ag7jJ5A9ZDj7oIq5rflEyolh2V4ie0tGQ50rFGg/ii6iQ
            > Tz9AWwigsHEkuinBTuN5041Xb8nAgHLvA60RQ41lWUHJxfAvDE+wN6NqgHmMVaRo
            > NHqlZcCuEl1jn7HW81XQTpgarrXHk1G7b2vK10pB/lUxUNIstZvCSjcp8QdtmC9v
            > tIhC2czSnsQaE6kIBuHxDNZxOlZ8DxBYCAgXSkycwznwzGhFPP0xB1lV9HfaP5+i
            > aikmx5SQmqBXQQKsxmIacoykrfu5x+O2TB/bq8JhJ1ak2jG9LVFyQqjorABVAgA7
            > pLEN6EomWht5qstaLVfHYpNsLMf6WA7UzRG08HKItUeDPtG7bDx8vBx5TvIUjT44
            > A0i09bOt8ZIgp+lJ8lFLWiPLChViAoy7fqKy2vrdsZerOF3l4LUQeQO/xnfZc+dG
            > AEG+7iCBOMxJSVoJ5bP6
            > =nydG
            > -----END PGP SIGNATURE-----
            >
            >
            > ------------------------------------------------------------------------------
            > Android is increasing in popularity, but the open development platform that
            > developers love is also attractive to malware creators. Download this white
            > paper to learn more about secure code signing practices that can help keep
            > Android apps secure.
            > http://pubads.g.doubleclick.net/gampad/clk?id=65839951&iu=/4140/ostg.clktrk
            > _______________________________________________
            > Bitcoin-development mailing list
            > Bitcoin-development@lists•sourceforge.net
            > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
            >
            
            [-- Attachment #2: Type: text/html, Size: 3647 bytes --]
            
            ^ permalink raw reply	[flat|nested] 31+ messages in thread

• * Re: [Bitcoin-development] Auto-generated miner backbone
    2013-11-04 11:26 [Bitcoin-development] Auto-generated miner backbone Mike Hearn
    2013-11-04 11:53 ` Peter Todd
  @ 2013-11-04 11:58 ` Michael Gronager
    2013-11-04 12:03   ` Mike Hearn
    2013-11-04 15:58   ` Gregory Maxwell
    2013-11-04 14:26 ` Peter Todd
    2013-11-04 15:51 ` Gregory Maxwell
    3 siblings, 2 replies; 31+ messages in thread
  From: Michael Gronager @ 2013-11-04 11:58 UTC (permalink / raw)
    To: bitcoin-development
  
  On 4/11/13, 12:26 , Mike Hearn wrote:
  > W.R.T. this paper and the oft-discussed miner backbone,
  > 
  >   http://arxiv.org/pdf/1311.0243v1.pdf
  > 
  > I'm wondering about an alternative protocol change that perhaps has less
  > subtle implications than their suggested change. 
  
  The suggested change is actually very simple (minutes of coding) and
  elegant and addresses precisely the identified problem. It is actually a
  mental shortcut in the assumption of how probability works when mining a
  chain. The paper simply corrects this error - nice work!
  
  > Rather than address the
  > problem by assuming the network is full of sybil nodes and changing the
  > rules for selecting the chain to build on, how about if we wrote code to
  > automatically build a miner backbone by having IP addresses of nodes
  > embedded into coinbases, then having any bitcoind that is creating work
  > automatically connect to IPs that appeared in enough recent blocks? 
  
  You suggestion could perhaps be fun for other purposes, but does not
  rule out pools of "selfish miners". Further, it binds physical state
  (ip) to the blockchain, which has so far held no assumptions on the
  technology of the system on which it is running.
  
  > 
  > This would have the effect of automatically linking all the major pools
  > together, with no administration overhead.
  > 
  > For bonus points, the IPs could be IPv6 and then the trick we use to
  > pack hidden services into IPv6 address space would allow nodes to be
  > reached via Tor. This might be useful in the case of pools that don't to
  > reveal the location of their bitcoin node[s], like for anti-DoS reasons.
  > 
  > It feels like this should be achievable with a few days of solid coding
  > and a couple of new command line flags, and the impact is much easier to
  > reason about than a fundamental rule change like the one proposed by the
  > paper.
  > 
  > 
  > ------------------------------------------------------------------------------
  > Android is increasing in popularity, but the open development platform that
  > developers love is also attractive to malware creators. Download this white
  > paper to learn more about secure code signing practices that can help keep
  > Android apps secure.
  > http://pubads.g.doubleclick.net/gampad/clk?id=65839951&iu=/4140/ostg.clktrk
  > 
  > 
  > 
  > _______________________________________________
  > Bitcoin-development mailing list
  > Bitcoin-development@lists•sourceforge.net
  > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
  > 
  
  
  
  
  ^ permalink raw reply	[flat|nested] 31+ messages in thread

• • * Re: [Bitcoin-development] Auto-generated miner backbone
      2013-11-04 11:58 ` [Bitcoin-development] Auto-generated miner backbone Michael Gronager
    @ 2013-11-04 12:03   ` Mike Hearn
      2013-11-04 12:20     ` Peter Todd
      2013-11-04 12:40     ` Michael Gronager
      2013-11-04 15:58   ` Gregory Maxwell
      1 sibling, 2 replies; 31+ messages in thread
    From: Mike Hearn @ 2013-11-04 12:03 UTC (permalink / raw)
      To: Michael Gronager; +Cc: Bitcoin Dev
    
    [-- Attachment #1: Type: text/plain, Size: 815 bytes --]
    
    >
    > The suggested change is actually very simple (minutes of coding) and
    > elegant and addresses precisely the identified problem.
    >
    
    Disagree. Unless I'm misunderstanding what they propose, their suggested
    change would mean anyone could broadcast a newly discovered block at any
    point and have a 50% chance of being the winner. That is a fundamental
    change to the dynamics of how Bitcoin works that would require careful
    thought and study.
    
    Also, their solution doesn't really address the problem they bring up, it
    just changes the size of the threshold required.
    
    Fundamentally, their attack is a sybil attack. It doesn't work if they
    can't delay or block a pools competitors because mostly their block will
    come in second place and they'll lose the race. Thus the solution should be
    a solution to sybil attacks.
    
    [-- Attachment #2: Type: text/html, Size: 1179 bytes --]
    
    ^ permalink raw reply	[flat|nested] 31+ messages in thread

  • • * Re: [Bitcoin-development] Auto-generated miner backbone
        2013-11-04 12:03   ` Mike Hearn
      @ 2013-11-04 12:20     ` Peter Todd
        2013-11-04 12:40     ` Michael Gronager
        1 sibling, 0 replies; 31+ messages in thread
      From: Peter Todd @ 2013-11-04 12:20 UTC (permalink / raw)
        To: Mike Hearn; +Cc: Bitcoin Dev, Michael Gronager
      
      [-- Attachment #1: Type: text/plain, Size: 1636 bytes --]
      
      On Mon, Nov 04, 2013 at 01:03:50PM +0100, Mike Hearn wrote:
      > >
      > > The suggested change is actually very simple (minutes of coding) and
      > > elegant and addresses precisely the identified problem.
      > >
      > 
      > Disagree. Unless I'm misunderstanding what they propose, their suggested
      > change would mean anyone could broadcast a newly discovered block at any
      > point and have a 50% chance of being the winner. That is a fundamental
      > change to the dynamics of how Bitcoin works that would require careful
      > thought and study.
      
      It's worth pointing out that my previous post on this list for
      "near-block broadcasts" - where blocks that almost but not quite met the
      proof-of-work threshold are also broadcast so that propagation of
      transactions can be proven - also naturally leads to their proposed
      solution. Any miner who sees a near-block-broadcast extending a chain
      fork that they aren't mining on would naturally see that as evidence
      that the other side has more hashing power, and thus it's in their
      interest to mine it rather than the side they are mining.
      
      
      You know, the whole paper follows the same logic as the point I made
      months ago in how if there is no explicit blocksize limit miners have
      incentives to make their blocks large enough that they only propagate to
      just over 50% of the hashing power, thus causing their competitors to
      waste effort.  They analyze the situation in terms of a sybil attack,
      where I proposed a more fundemental mechanism to achieve the same goal
      based on simple physics.
      
      -- 
      'peter'[:-1]@petertodd.org
      000000000000000719f061e0fa83343ddbe80d2b6a1fefc84691ffe8652385e0
      
      [-- Attachment #2: Digital signature --]
      [-- Type: application/pgp-signature, Size: 685 bytes --]
      
      ^ permalink raw reply	[flat|nested] 31+ messages in thread

    • * Re: [Bitcoin-development] Auto-generated miner backbone
        2013-11-04 12:03   ` Mike Hearn
        2013-11-04 12:20     ` Peter Todd
      @ 2013-11-04 12:40     ` Michael Gronager
        1 sibling, 0 replies; 31+ messages in thread
      From: Michael Gronager @ 2013-11-04 12:40 UTC (permalink / raw)
        To: Mike Hearn; +Cc: Bitcoin Dev
      
      "We propose a simple, backwards-compatible change to the Bitcoin
      protocol to address this problem and raise the threshold. Specifically,
      when a miner learns of competing branches of the same length, it should
      propagate all of them, and choose which one to mine on uniformly at random."
      
      So only in the case of two competing chains... The "Selfish Miner" today
      has an advantage knowing which chain the other will work on, and by
      simply choosing the other they get their advantage making it likely that
      it is the other that will waste their effort. By using the random scheme
      this advantage is gone.
      
      Note again that it is only in the case of two competing chains, which
      will happen on average every 60 blocks. So it is only roughly once every
      60 block that you change from choosing one chain to doing a 50% random.
      
      A rough calculation on earnings will be that you loose roughly 1/(2*60)
      ~ 1% of your blocks using this scheme. But at the same time you make it
      harder for such an attack to happen. (This number might be slightly
      higher, as working in parallel on both chains will make the two chains
      last longer, so agree that we need a bit more analysis...)
      
      I also agree that it is a kind of a Sybil attack, but I think we should
      accept the risk of a Sybil attack but of course minimize it, rather than
      introducing various social network (ip addresses) solutions, which in
      one way or the other always have some central auth / oracle assumption.
      
      
      
      On 4/11/13, 13:03 , Mike Hearn wrote:
      >     The suggested change is actually very simple (minutes of coding) and
      >     elegant and addresses precisely the identified problem.
      > 
      > 
      > Disagree. Unless I'm misunderstanding what they propose, their suggested
      > change would mean anyone could broadcast a newly discovered block at any
      > point and have a 50% chance of being the winner. That is a fundamental
      > change to the dynamics of how Bitcoin works that would require careful
      > thought and study.
      > 
      > Also, their solution doesn't really address the problem they bring up,
      > it just changes the size of the threshold required. 
      > 
      > Fundamentally, their attack is a sybil attack. It doesn't work if they
      > can't delay or block a pools competitors because mostly their block will
      > come in second place and they'll lose the race. Thus the solution should
      > be a solution to sybil attacks.
      
      
      
      
      ^ permalink raw reply	[flat|nested] 31+ messages in thread

  • * Re: [Bitcoin-development] Auto-generated miner backbone
      2013-11-04 11:58 ` [Bitcoin-development] Auto-generated miner backbone Michael Gronager
      2013-11-04 12:03   ` Mike Hearn
    @ 2013-11-04 15:58   ` Gregory Maxwell
      1 sibling, 0 replies; 31+ messages in thread
    From: Gregory Maxwell @ 2013-11-04 15:58 UTC (permalink / raw)
      To: Michael Gronager; +Cc: Bitcoin Development
    
    On Mon, Nov 4, 2013 at 3:58 AM, Michael Gronager <gronager@ceptacle•com> wrote:
    > The suggested change is actually very simple (minutes of coding) and
    > elegant and addresses precisely the identified problem. It is actually a
    > mental shortcut in the assumption of how probability works when mining a
    > chain. The paper simply corrects this error - nice work!
    
    This isn't so.  Their solution creates a weaker form of the
    vulnerability at all times, not just when the attacker has a
    informational/positional advantage.
    
    Normally delaying your blocks is negative expectation because you will
    get orphaned by blocks that are announced before you most of the time
    because miners extend the first seen. However, if you can position
    yourself all over the network you can condition your announcements on
    other blocks being announced and still win the race even if you
    delayed.
    
    Eliminating the first seen rule means that a miner with enough
    hashpower (including the largest pools existing today) could execute
    this attack without positioning themselves all over the network, the
    improvement is that a low hashrate attacker couldn't do as well, even
    with positioning themselves all over the network.  I don't think this
    can be described as "simply corrects the error".  The largest pool
    would gain an advantage in delaying their blocks and would receive a
    superliner share of mining income from doing so, something they can't
    simply do today without attacking the network.
    
    At the moment I believe we can improve the situation with propagation
    advantage without the other changes, so we should do that first while
    thinking carefully about this.
    
    Simply relaying late blocks might be fine, if anything it would at
    least make it easier to keep reliable orphan stats... though I'm
    concerned with the bandwidth overhead and risk of flooding if its not
    implemented carefully.
    
    
    
    ^ permalink raw reply	[flat|nested] 31+ messages in thread

• * Re: [Bitcoin-development] Auto-generated miner backbone
    2013-11-04 11:26 [Bitcoin-development] Auto-generated miner backbone Mike Hearn
    2013-11-04 11:53 ` Peter Todd
    2013-11-04 11:58 ` [Bitcoin-development] Auto-generated miner backbone Michael Gronager
  @ 2013-11-04 14:26 ` Peter Todd
    2013-11-04 14:34   ` Pieter Wuille
                       ` (2 more replies)
    2013-11-04 15:51 ` Gregory Maxwell
    3 siblings, 3 replies; 31+ messages in thread
  From: Peter Todd @ 2013-11-04 14:26 UTC (permalink / raw)
    To: Mike Hearn, Ittay Eyal; +Cc: Bitcoin Dev
  
  [-- Attachment #1: Type: text/plain, Size: 3523 bytes --]
  
  On Mon, Nov 04, 2013 at 12:26:30PM +0100, Mike Hearn wrote:
  > W.R.T. this paper and the oft-discussed miner backbone,
  > 
  >   http://arxiv.org/pdf/1311.0243v1.pdf
  > 
  > I'm wondering about an alternative protocol change that perhaps has less
  > subtle implications than their suggested change. Rather than address the
  > problem by assuming the network is full of sybil nodes and changing the
  > rules for selecting the chain to build on, how about if we wrote code to
  > automatically build a miner backbone by having IP addresses of nodes
  > embedded into coinbases, then having any bitcoind that is creating work
  > automatically connect to IPs that appeared in enough recent blocks?
  > 
  > It feels like this should be achievable with a few days of solid coding and
  > a couple of new command line flags, and the impact is much easier to reason
  > about than a fundamental rule change like the one proposed by the paper.
  
  Actually on further reflection this idea will make the attack described
  in the paper easier to carry out, rather than harder.
  
  I think where you're misunderstanding originates is the description of
  this attack as requiring a sybil attack on the network - you see this
  underlying sybil as one of numerical advantage, when it's actually one
  of *informational* advantage.
  
  Remember that the selfish miner strategy outlined in the paper is
  essentially a way to use knowledge of what blocks miners will be mining
  on, from the "first seen" rule, and the ability to broadcast blocks you
  have mined more widely than other miners. That knowledge and ability is
  then used in conjunction with a small lead (obtainable by chance) to
  outpace the rest of the network.
  
  By making all miners easily identifiable you make gaining that
  informational and broadcast capability easier to obtain rather than
  harder. The attacker now only needs to connect to every identified miner
  with especially fast nodes. With judicious use of DoS attacks and low
  latency they can still gain the informational and broadcast "upper hand"
  over other miners and carry out the attack.
  
  Where the paper goes wrong is they don't recognize the fundemental
  nature of the strategy being based on an informational advantage. Their
  "pick a random side of the fork" strategy may work to some extent, but
  it's incomplete and isn't necessarily rational for the miners
  individually.
  
  The correct, and rational, approach for a miner is to always mine to
  extend the block that the majority of hashing power is trying to extend.
  The current relay rules don't give you that information at all, but they
  can if we do two things:
  
  1) Relay all blocks that meet the PoW target. (as suggested in the
     paper)
  
  2) Relay block headers that nearly meet the PoW target.
  
  Mining strategy is now to mine to extend the first block you see, on the
  assumption that the earlier one probably propagated to a large portion
  of the total hashing power. But as you receive "near-blocks" that are
  under the PoW target, use them to estimate the hashing power on each
  fork, and if it looks like you are not on the majority side, switch.
  
  This very effectively defeats the paper's selfish-miner strategy, as all
  miners will very quickly be mining on the block that truly has the
  majority of hashing power trying to extend it. This is also a better
  overall outcome, because it puts the 51% attack threshhold back at 51%
  
  -- 
  'peter'[:-1]@petertodd.org
  0000000000000004ee9bb13b022c412d75692b5e85454013c53f89e5d6fa8c69
  
  [-- Attachment #2: Digital signature --]
  [-- Type: application/pgp-signature, Size: 490 bytes --]
  
  ^ permalink raw reply	[flat|nested] 31+ messages in thread

• • * Re: [Bitcoin-development] Auto-generated miner backbone
      2013-11-04 14:26 ` Peter Todd
    @ 2013-11-04 14:34   ` Pieter Wuille
      2013-11-04 14:46     ` Peter Todd
           [not found]   ` <CABT1wWm1NzKSS9H=Qh3Z6pFmNHbOFKC12WaE=b3kE0mNsRgfmw@mail.gmail.com>
      2013-11-04 15:27   ` Mike Hearn
      2 siblings, 1 reply; 31+ messages in thread
    From: Pieter Wuille @ 2013-11-04 14:34 UTC (permalink / raw)
      To: Peter Todd; +Cc: Ittay Eyal, Bitcoin Dev
    
    On Mon, Nov 4, 2013 at 3:26 PM, Peter Todd <pete@petertodd•org> wrote:
    > The correct, and rational, approach for a miner is to always mine to
    > extend the block that the majority of hashing power is trying to extend.
    > The current relay rules don't give you that information at all, but they
    > can if we do two things:
    >
    > 1) Relay all blocks that meet the PoW target. (as suggested in the
    >    paper)
    >
    > 2) Relay block headers that nearly meet the PoW target.
    >
    > Mining strategy is now to mine to extend the first block you see, on the
    > assumption that the earlier one probably propagated to a large portion
    > of the total hashing power. But as you receive "near-blocks" that are
    > under the PoW target, use them to estimate the hashing power on each
    > fork, and if it looks like you are not on the majority side, switch.
    
    Doesn't that mean that by selective blocking these near-PoW headers,
    you can bias peers into preferring to mine on those with near-PoW
    headers, turning the attack around? Of course, because of their size,
    headers are likely much harder to slow down (in propagation speed)
    than full blocks...
    
    -- 
    Pieter
    
    
    
    ^ permalink raw reply	[flat|nested] 31+ messages in thread

  • • * Re: [Bitcoin-development] Auto-generated miner backbone
        2013-11-04 14:34   ` Pieter Wuille
      @ 2013-11-04 14:46     ` Peter Todd
        0 siblings, 0 replies; 31+ messages in thread
      From: Peter Todd @ 2013-11-04 14:46 UTC (permalink / raw)
        To: Pieter Wuille; +Cc: Ittay Eyal, Bitcoin Dev
      
      [-- Attachment #1: Type: text/plain, Size: 1477 bytes --]
      
      On Mon, Nov 04, 2013 at 03:34:35PM +0100, Pieter Wuille wrote:
      > > Mining strategy is now to mine to extend the first block you see, on the
      > > assumption that the earlier one probably propagated to a large portion
      > > of the total hashing power. But as you receive "near-blocks" that are
      > > under the PoW target, use them to estimate the hashing power on each
      > > fork, and if it looks like you are not on the majority side, switch.
      > 
      > Doesn't that mean that by selective blocking these near-PoW headers,
      > you can bias peers into preferring to mine on those with near-PoW
      > headers, turning the attack around? Of course, because of their size,
      > headers are likely much harder to slow down (in propagation speed)
      > than full blocks...
      
      Remember that the attack described in the paper *doesn't* depend on the
      ability to selectively block or even just slow down anything - it works
      even on a unlimited bandwidth jam-free network so long as latency is
      non-zero.
      
      As for other possible attacks, if you can selectively block or slow down
      certain near-target headers you haven't achieved anything novel. Why not
      use that ability to block or slow down blocks themselves? Even if you
      did block some PoW headers for whatever reason the original purpose of
      broadcasting them - getting all hashing power to work to extend the same
      block - is still achieved.
      
      -- 
      'peter'[:-1]@petertodd.org
      0000000000000001d7eb7fceb2e27f3dd1eb5f516464a6b6874fdf6debbd0227
      
      [-- Attachment #2: Digital signature --]
      [-- Type: application/pgp-signature, Size: 490 bytes --]
      
      ^ permalink raw reply	[flat|nested] 31+ messages in thread

  • [parent not found: <CABT1wWm1NzKSS9H=Qh3Z6pFmNHbOFKC12WaE=b3kE0mNsRgfmw@mail.gmail.com>]

  • • * Re: [Bitcoin-development] Auto-generated miner backbone
             [not found]   ` <CABT1wWm1NzKSS9H=Qh3Z6pFmNHbOFKC12WaE=b3kE0mNsRgfmw@mail.gmail.com>
      @ 2013-11-04 15:04     ` Peter Todd
             [not found]       ` <CABT1wWmONUeOWRg-=FKr88bgBQf0un4bvjYW2h8d-10ys-VKtA@mail.gmail.com>
        0 siblings, 1 reply; 31+ messages in thread
      From: Peter Todd @ 2013-11-04 15:04 UTC (permalink / raw)
        To: Ittay; +Cc: Bitcoin Dev
      
      [-- Attachment #1: Type: text/plain, Size: 2200 bytes --]
      
      On Mon, Nov 04, 2013 at 09:49:09AM -0500, Ittay wrote:
      > 1. Something important that is being overlooked is that the attack is
      > relevant even without the sybil attack. Even if you assume the selfish
      > miners loose every time on a 1:1 competition, they can still benefit in
      > pools larger than 33%. And pools often reach this size.
      > 
      > 2. The selfish pool can essentially hide its behavior behind multiple IP
      > addresses. I fear employing an anti-sybil mechanism of this sort may expose
      > new vulnerabilities. The current approach is great - the attacker cannot
      > partition the network, only gain a slight timing advantage. Our approach
      > just takes away the network-induced arbitrariness and replaces it with
      > explicit randomness, which cannot introduce new vulnerabilities. It
      > protects us from 25% attacks, which is excellent (though unfortunately not
      > as good as the 51% security we believed before).
      
      The problem is picking which side of the fork you mine on randomly isn't
      rational for an individual miner. The time that you heard about a block
      is important information: the block you heard about first is more likely
      to have propagated to the majority of the hashing power than the one you
      learn about second. You're rational incentive is to always mine on the
      majority side as that side has the highest probability of no competing
      blocks being found when the next block is found. (with the one exception
      of the previous block being yours) In addition the next block found will
      propagate to the majority of hashing power faster, as that majority
      already has the previous block. By suggesting that miners pick randomly
      half the time they will be going against their best interests. (if not
      the interests of the network as a whole)
      
      On the other hand my near-target broadcast solution gives miners honest
      proof of what the majority actually is. Making use of that information
      is the economically rational choice even at an individual level. Yet it
      still defeats the attack, and it does better in returning the threshold
      to the originally assumed 51% level.
      
      -- 
      'peter'[:-1]@petertodd.org
      0000000000000005fa5454135b2638d1b2240d565737a24586f31490025e2de0
      
      [-- Attachment #2: Digital signature --]
      [-- Type: application/pgp-signature, Size: 490 bytes --]
      
      ^ permalink raw reply	[flat|nested] 31+ messages in thread

    • • [parent not found: <CABT1wWmONUeOWRg-=FKr88bgBQf0un4bvjYW2h8d-10ys-VKtA@mail.gmail.com>]

      • • * Re: [Bitcoin-development] Auto-generated miner backbone
                 [not found]       ` <CABT1wWmONUeOWRg-=FKr88bgBQf0un4bvjYW2h8d-10ys-VKtA@mail.gmail.com>
          @ 2013-11-04 15:46         ` Peter Todd
                 [not found]           ` <CABT1wWmM466jWWdWAo5GmzP58xJFT70Vcr74ta+2QF2fWT+1SA@mail.gmail.com>
                 [not found]         ` <CABT1wWmwb17b4ACHMmDKqd94tUSKsvwAPx344mZ0VS+47myeWg@mail.gmail.com>
            1 sibling, 1 reply; 31+ messages in thread
          From: Peter Todd @ 2013-11-04 15:46 UTC (permalink / raw)
            To: Ittay; +Cc: Bitcoin Dev, Emin Gün Sirer
          
          [-- Attachment #1: Type: text/plain, Size: 1642 bytes --]
          
          On Mon, Nov 04, 2013 at 10:25:19AM -0500, Ittay wrote:
          > Peter - how can you guarantee that the majority mines on the non-selfish
          > block?
          
          Feedback basically. So suppose the hashing power is split exactly 50:50,
          with half the hashing power hearing about one block first, and half the
          other. Also suppose the near-target threshold is 1/64th, that is a block
          header that means a target with difficulty 1/64th of the actual
          difficulty will be broadcast around the network by nodes. With a 10
          minute block interval, near-target block headers will be found on
          average every 9.4 seconds.
          
          Eventually one of the two halves will find a near-target PoW solution,
          and the corresponding block-header will be broadcast on the network. Now
          if you are a miner, and you receive such a PoW solution, that's evidence
          that whatever block that block header built on has more hashing power
          than other competing blocks. Thus you would be rational to switch, and
          start mining to extend that block if you aren't already. Once miners
          start doing that, very soon another near-block solution will be
          generated, giving even more certainty about what block the majority are
          mining on.
          
          Of course, it may be the case that competing near-block headers are
          found, but no matter: as long as miners switch to the block with the
          most hashing power, this forms a feedback effect that quickly brings
          everyone to consensus. With everyone mining to extend the same block,
          there's nothing the selfish miner can do; there's no disagreement to
          exploit.
          
          -- 
          'peter'[:-1]@petertodd.org
          000000000000000771e068338fef7e2285b8a6db582e37473f42b76573677adf
          
          [-- Attachment #2: Digital signature --]
          [-- Type: application/pgp-signature, Size: 490 bytes --]
          
          ^ permalink raw reply	[flat|nested] 31+ messages in thread

        • • [parent not found: <CABT1wWmM466jWWdWAo5GmzP58xJFT70Vcr74ta+2QF2fWT+1SA@mail.gmail.com>]

          • • * Re: [Bitcoin-development] Auto-generated miner backbone
                     [not found]           ` <CABT1wWmM466jWWdWAo5GmzP58xJFT70Vcr74ta+2QF2fWT+1SA@mail.gmail.com>
              @ 2013-11-04 16:07             ` Peter Todd
                     [not found]               ` <CABT1wWm5BDZf7U40pOqZvTqdOKeTWUTekjUNckq5McMV=LDu_g@mail.gmail.com>
                0 siblings, 1 reply; 31+ messages in thread
              From: Peter Todd @ 2013-11-04 16:07 UTC (permalink / raw)
                To: Ittay; +Cc: Bitcoin Dev, Emin Gün Sirer
              
              [-- Attachment #1: Type: text/plain, Size: 2417 bytes --]
              
              (not sure if you meant this to go to the list, my apologies if not)
              
              On Mon, Nov 04, 2013 at 10:50:25AM -0500, Ittay wrote:
              > On Mon, Nov 4, 2013 at 10:46 AM, Peter Todd <pete@petertodd•org> wrote:
              > 
              > > On Mon, Nov 04, 2013 at 10:25:19AM -0500, Ittay wrote:
              > > > Peter - how can you guarantee that the majority mines on the non-selfish
              > > > block?
              > >
              > > Of course, it may be the case that competing near-block headers are
              > > found, but no matter: as long as miners switch to the block with the
              > > most hashing power, this forms a feedback effect that quickly brings
              > > everyone to consensus. With everyone mining to extend the same block,
              > > there's nothing the selfish miner can do; there's no disagreement to
              > > exploit.
              > >
              > 
              > This is not the exploit! The majority you create might just as well follow
              > the previously-private block, so we're back in square one.
              
              Right, but the thing is, if all miners quickly come to consensus and are
              all mining on the same block, there's nothing the attacker can exploit
              in the first place.
              
              Suppose Alice the attacker is 100 blocks ahead of the main network
              somehow. We'll say the other miners are working to extend block n, and
              she's in posession of 100 blocks extending that. She also has just under
              50% of the hashing power.
              
              Now when the main network finds a block n+1, Alice can do one of two
              things: she can publish her own n+1 block, or she can do nothing. If she
              does nothing, the main network will find block n+2 faster than she finds
              n+101, so eventually she loses. Thus she has to publish.
              
              In your attack she publishes to a subset of nodes strategicly, splitting
              the hashing power between nodes working to extend her n+1, and the other
              n+1 found. However, with near-target headers, very quickly all hashing
              power will come to consensus and all work to extend the same block,
              either theirs or Alice's. Given that they have the majority, they will
              find another block faster on average than Alice can extend her lead, and
              thus eventually Alice will lose.
              
              Now there is still a slight advantage for Alice in that it takes some
              time for the whole network to come to consensus, but this is a much
              slimmer margin, maybe a few percentage points, so at best Alice might
              need, say, 45% of the total hashing power.
              
              -- 
              'peter'[:-1]@petertodd.org
              0000000000000004b8381fe97338c8b710cb662160f08e391820f30a375bb9b9
              
              [-- Attachment #2: Digital signature --]
              [-- Type: application/pgp-signature, Size: 490 bytes --]
              
              ^ permalink raw reply	[flat|nested] 31+ messages in thread

            • • [parent not found: <CABT1wWm5BDZf7U40pOqZvTqdOKeTWUTekjUNckq5McMV=LDu_g@mail.gmail.com>]

              • • * Re: [Bitcoin-development] Auto-generated miner backbone
                         [not found]               ` <CABT1wWm5BDZf7U40pOqZvTqdOKeTWUTekjUNckq5McMV=LDu_g@mail.gmail.com>
                  @ 2013-11-04 16:51                 ` Peter Todd
                    0 siblings, 0 replies; 31+ messages in thread
                  From: Peter Todd @ 2013-11-04 16:51 UTC (permalink / raw)
                    To: Ittay; +Cc: Bitcoin Dev, Emin Gün Sirer
                  
                  [-- Attachment #1: Type: text/plain, Size: 1484 bytes --]
                  
                  On Mon, Nov 04, 2013 at 11:24:33AM -0500, Ittay wrote:
                  > Yes - this is for the mailing list.
                  > 
                  > Regarding the algorithm - as we explain in the paper, as long as the
                  > attacker is way ahead - the others can mine on whatever they like. Doesn't
                  > really matter. Once they almost close the gap (and they will, because
                  > they're the majority), leaving only 1 block lead, the selfish miners
                  > publish their secret blocks, loose their lead, but win the entire secret
                  > chain. The honest miners thus loose all the work they did so far. It
                  > doesn't really matter how the honest miners waste their time.
                  
                  Yes, they lose their work, but that's irrelevant: what's important is
                  eventually Alice runs out of secret blocks and then has no advantage
                  over the other miners.
                  
                  In your paper Alice created her lead by exploiting the fact that not all
                  of the hashing power was working to extend the same block due to the
                  "first-wins" rule. With my solution that situation doesn't happen in the
                  first place: forks are resolved quickly because both sides have both
                  forks, and consensus on which one is the winner is achieved very quickly
                  by proving which side has the majority of hashing power through
                  near-target PoW solutions. With the majority of hashing power in
                  consensus and working to extend the same block there's nothing Alice can
                  do to get ahead, defeating the attack.
                  
                  -- 
                  'peter'[:-1]@petertodd.org
                  0000000000000008adb581077dcfa0bf067a4ee010fbabb92d136292625b2299
                  
                  [-- Attachment #2: Digital signature --]
                  [-- Type: application/pgp-signature, Size: 490 bytes --]
                  
                  ^ permalink raw reply	[flat|nested] 31+ messages in thread

        • [parent not found: <CABT1wWmwb17b4ACHMmDKqd94tUSKsvwAPx344mZ0VS+47myeWg@mail.gmail.com>]

        • • * Re: [Bitcoin-development] Auto-generated miner backbone
                   [not found]         ` <CABT1wWmwb17b4ACHMmDKqd94tUSKsvwAPx344mZ0VS+47myeWg@mail.gmail.com>
            @ 2013-11-04 21:04           ` Peter Todd
              2013-11-04 21:45             ` Alan Reiner
              0 siblings, 1 reply; 31+ messages in thread
            From: Peter Todd @ 2013-11-04 21:04 UTC (permalink / raw)
              To: Ittay; +Cc: Bitcoin Dev, Emin Gün Sirer
            
            [-- Attachment #1: Type: text/plain, Size: 6907 bytes --]
            
            On Mon, Nov 04, 2013 at 02:12:44PM -0500, Ittay wrote:
            > On Mon, Nov 4, 2013 at 10:25 AM, Ittay <ittay.eyal@cornell•edu> wrote:
            > 
            > > As for the rational motivation of the individual miners - that's a good
            > > point!
            > > Here is a solution we did not put in the paper due to space constraints
            > > that should alleviate your concern:
            > > Instead of locally choosing a block at random, have a deterministic
            > > pseudo-random mechanism for choosing between competing chains. E.g., take
            > > the one whose last block hash is smaller. This way all miners choose the
            > > same chain, and the guarantees of our solution hold.
            > >
            > 
            > I take that back.
            
            Speaking of, I'm going to take back my solution as well; I misunderstood
            your paper.
            
            So here's your argument in a ELI5 nutshell:
            
            Alice is a miner with some amount of hashing power. She has the ability
            to detect new blocks on the network extremely effectively for whatever
            reason; in short she has unusually good knowledge of the state of the
            network. She is also very good at publishing her blocks and getting them
            to the majority of hashing power in very little time; she has unusually
            good connectivity to all miners. (low-latency and high bandwidth)
            
            She's so good at this that when she finds a new block, she keeps it a
            secret! She can get away with this because she knows that the moment Bob
            finds a block, she can immediately broadcast it to the rest of the
            network before the other block propagates. Instead of building on Bob's
            blocks, almost everyone builds on Alice's block, depriving Bob of the
            revenue. Gradually Alice gets more and more miners because Bob, and
            other pools, don't pay out as much.
            
            You propose a rule where essentially miners extend Bob's block 50% of
            the time, and show in your paper how that leads to a scenario where
            Alice needs to have at leastr 1/4 of the total hashing power to
            succesfully pull this attack off anyway.
            
            
            What I did succesfully show is that for a short-term rational miner
            they're still better off mining to extend the block they hear about
            first rather than using your pick-one-at-random rule, because when you
            hear about a block is important information about whether or not the
            majority is mining on it. This is true even if others are using the
            pick-one-at-random rule. (they're better defecting than doing what's
            right for the whole network) Even worse is that miners have a rational
            incentive to broadcast such near-target headers to try to encourage
            other miners to work on the same fork that they are working on. The
            near-target idea came about for a totally different reason, so it's
            something that might wind up being implemented anyway.
            
            Mike Hearn's idea of making it easy to identify nodes associated with
            hashing power is still wrong. Although again, it's something that miners
            themselves have rational incentives to do. (you always want to encourage
            others to send you their blocks, and you also want to be able to send
            your blocks to the majority of hashing power as quickly as possible)
            
            Where the idea goes wrong is it makes it easier for Alice to identify
            hashing power, specifically where she needs to send her blocks to
            distribute them to the majority as quickly as possible. The second
            problem occurs if those nodes also distribute blocks to connecting
            peers: this makes it easy for Alice to be sure she'll hear about a new
            block as soon as possible by connecting to every one of those peers with
            a high-speed, low-latency connection. Bizzarely the idea does work if
            the advertised nodes only accept blocks, and never send blocks - instead
            miners would *only* send their blocks to other miners who have proven
            their hashing power, and do so essentially largest miner to smallest.
            Now unless Alice already is a large miner, her strategy can't work.  Of
            course this will strongly encourage further centralization of pools. But
            it is in the interests of rational miners sadly.
            
            That blocks take a finite amount of time to propagate makes the problem
            worse: for Alice to learn that another block has been mined only
            requires her to receive the small 80 byte header from a peer; she
            doesn't need the whole block. She thus can know the block exists well
            before it has a chance to propagate fully. Even if every miner were
            directly peered to every other as some suggest, Alice could simply make
            smaller blocks, faster propagating than everyone else and use especially
            low-latency connections to win the race.
            
            On the other hand, the Bitcoin protocol is currently designed such that
            a miner can mine a block without knowing the previous block in full.
            Given the large block reward and/or a supply of transactions they knew
            no other miner had a rational miner would start trying to extend the
            longest chain they know about prior to actually receiving and validating
            the full block. Again, when miners start doing this - perhaps out of
            desperation due to low revenue - as long as Alice has the lowest latency
            network she'll win. (she doesn't even need to have the highest bandwidth
            in this case) We can change the protocol to force miners to fully
            validate blocks prior to mining extensions, but that only forces Alice
            to get more bandwidth - she still wins.
            
            Speaking of low-latency, latency not only centralizes control in a
            single pool, it centralizes pools and even mining hardware itself in a
            single physical location. Anyone at the edges of the propagation network
            will get comparatively less revenue than those in the center, gradually
            tightening the network, even without selfish mining. Alice's strategy of
            course should be to position her nodes in the geographical center. It's
            worth noting how if Alice is the one with the lowest average latency,
            she will win against any other miner trying to persue the same selfish
            miner strategy that she is using.
            
            
            Finally nLockTime makes the selfish miner strategy even more profitable.
            You may not be aware, but it's possible to make a transaction that can't
            be mined until some time in the future, measured by either block height
            or block timestamp. I've proposed to use this mechanism in
            announce/commit sacrifices: you create a transaction that can't be mined
            until some point in the future that sacrifices a large amount to mining
            fees, and then prior to that point you include it in the blockchain as
            data, proving the whole world knew about your transaction. The idea was
            that which miner managed to include the transaction, and collect the
            reward, would be random. However whenever Alice is able to maintain a
            lead over other miners she's able to reliably mine significantly more of
            those valuable transactions, further increasing her revenue over other
            miners.
            
            
            I must say, you've really opened a can of worms...
            
            -- 
            'peter'[:-1]@petertodd.org
            000000000000000379e2a349ccee65efc29d43e2c742f8e4a9247d68025ace84
            
            [-- Attachment #2: Digital signature --]
            [-- Type: application/pgp-signature, Size: 490 bytes --]
            
            ^ permalink raw reply	[flat|nested] 31+ messages in thread

          • • * Re: [Bitcoin-development] Auto-generated miner backbone
                2013-11-04 21:04           ` Peter Todd
              @ 2013-11-04 21:45             ` Alan Reiner
                2013-11-04 22:03               ` Peter Todd
                0 siblings, 1 reply; 31+ messages in thread
              From: Alan Reiner @ 2013-11-04 21:45 UTC (permalink / raw)
                To: bitcoin-development
              
              [-- Attachment #1: Type: text/plain, Size: 9535 bytes --]
              
              Sorry guys, I'm a little late to the party here.  I skimmed over the
              paper, and appreciated Peter Todd's recap of it.  My first thought was
              that this seems profit-neutral at best, when you take into account all
              the races you lose by trying to beat the propagation of other miners'
              blocks.
              
              So given the assumption that Alice is "well-connected" as Peter
              mentioned, it seems like this is a concern.  But is this a realistic
              assumption?  All miners have an incentive to be thoroughly connected to
              one another, to make sure they minimize the amount of time they spend
              mining on forks and that their blocks win with minimal chance of being
              orphaned.  Is it realistic that one miner can somehow monopolize the
              good connections when the big miners are already trying to do the same
              thing for honest reasons?  If you have a network full of honest miners
              and this one selfish-miner, it seems that all the honest miners need to
              do is try to establish those connections to each other as well as Alice
              does, and Alice will end up orphaning all her profit away.
              
              Furthermore, you can de-incentivize it by simply randomizing the order
              of broadcasts.  Although you are maintaining multiple concurrent
              connections, the data still exits your network card as a serial stream
              of packets, and it seems that if you randomize who gets your new-block
              broadcasts first, then it further reduces the Alice's advantage if she's
              not guaranteed to "be first."   Sure, she can do it sometimes, but it
              would seem that even a couple failures to beat the rest of the network
              is going to erase most/all of what she gained on the blocks/chains that
              she wins.
              
              I liked the statement by Chris WIllmer on the reddit thread:  "practice
              > theory".  The more we can theorize our way to believing the
              conclusions that this is a problem, the more incentive there is for
              someone intelligent to actually try it.  It's very possible that the
              conditions needed to execute this "attack" just cannot be attained in
              practice. 
              
              -Alan
              
              
              
              
              On 11/04/2013 04:04 PM, Peter Todd wrote:
              > On Mon, Nov 04, 2013 at 02:12:44PM -0500, Ittay wrote:
              >> On Mon, Nov 4, 2013 at 10:25 AM, Ittay <ittay.eyal@cornell•edu> wrote:
              >>
              >>> As for the rational motivation of the individual miners - that's a good
              >>> point!
              >>> Here is a solution we did not put in the paper due to space constraints
              >>> that should alleviate your concern:
              >>> Instead of locally choosing a block at random, have a deterministic
              >>> pseudo-random mechanism for choosing between competing chains. E.g., take
              >>> the one whose last block hash is smaller. This way all miners choose the
              >>> same chain, and the guarantees of our solution hold.
              >>>
              >> I take that back.
              > Speaking of, I'm going to take back my solution as well; I misunderstood
              > your paper.
              >
              > So here's your argument in a ELI5 nutshell:
              >
              > Alice is a miner with some amount of hashing power. She has the ability
              > to detect new blocks on the network extremely effectively for whatever
              > reason; in short she has unusually good knowledge of the state of the
              > network. She is also very good at publishing her blocks and getting them
              > to the majority of hashing power in very little time; she has unusually
              > good connectivity to all miners. (low-latency and high bandwidth)
              >
              > She's so good at this that when she finds a new block, she keeps it a
              > secret! She can get away with this because she knows that the moment Bob
              > finds a block, she can immediately broadcast it to the rest of the
              > network before the other block propagates. Instead of building on Bob's
              > blocks, almost everyone builds on Alice's block, depriving Bob of the
              > revenue. Gradually Alice gets more and more miners because Bob, and
              > other pools, don't pay out as much.
              >
              > You propose a rule where essentially miners extend Bob's block 50% of
              > the time, and show in your paper how that leads to a scenario where
              > Alice needs to have at leastr 1/4 of the total hashing power to
              > succesfully pull this attack off anyway.
              >
              >
              > What I did succesfully show is that for a short-term rational miner
              > they're still better off mining to extend the block they hear about
              > first rather than using your pick-one-at-random rule, because when you
              > hear about a block is important information about whether or not the
              > majority is mining on it. This is true even if others are using the
              > pick-one-at-random rule. (they're better defecting than doing what's
              > right for the whole network) Even worse is that miners have a rational
              > incentive to broadcast such near-target headers to try to encourage
              > other miners to work on the same fork that they are working on. The
              > near-target idea came about for a totally different reason, so it's
              > something that might wind up being implemented anyway.
              >
              > Mike Hearn's idea of making it easy to identify nodes associated with
              > hashing power is still wrong. Although again, it's something that miners
              > themselves have rational incentives to do. (you always want to encourage
              > others to send you their blocks, and you also want to be able to send
              > your blocks to the majority of hashing power as quickly as possible)
              >
              > Where the idea goes wrong is it makes it easier for Alice to identify
              > hashing power, specifically where she needs to send her blocks to
              > distribute them to the majority as quickly as possible. The second
              > problem occurs if those nodes also distribute blocks to connecting
              > peers: this makes it easy for Alice to be sure she'll hear about a new
              > block as soon as possible by connecting to every one of those peers with
              > a high-speed, low-latency connection. Bizzarely the idea does work if
              > the advertised nodes only accept blocks, and never send blocks - instead
              > miners would *only* send their blocks to other miners who have proven
              > their hashing power, and do so essentially largest miner to smallest.
              > Now unless Alice already is a large miner, her strategy can't work.  Of
              > course this will strongly encourage further centralization of pools. But
              > it is in the interests of rational miners sadly.
              >
              > That blocks take a finite amount of time to propagate makes the problem
              > worse: for Alice to learn that another block has been mined only
              > requires her to receive the small 80 byte header from a peer; she
              > doesn't need the whole block. She thus can know the block exists well
              > before it has a chance to propagate fully. Even if every miner were
              > directly peered to every other as some suggest, Alice could simply make
              > smaller blocks, faster propagating than everyone else and use especially
              > low-latency connections to win the race.
              >
              > On the other hand, the Bitcoin protocol is currently designed such that
              > a miner can mine a block without knowing the previous block in full.
              > Given the large block reward and/or a supply of transactions they knew
              > no other miner had a rational miner would start trying to extend the
              > longest chain they know about prior to actually receiving and validating
              > the full block. Again, when miners start doing this - perhaps out of
              > desperation due to low revenue - as long as Alice has the lowest latency
              > network she'll win. (she doesn't even need to have the highest bandwidth
              > in this case) We can change the protocol to force miners to fully
              > validate blocks prior to mining extensions, but that only forces Alice
              > to get more bandwidth - she still wins.
              >
              > Speaking of low-latency, latency not only centralizes control in a
              > single pool, it centralizes pools and even mining hardware itself in a
              > single physical location. Anyone at the edges of the propagation network
              > will get comparatively less revenue than those in the center, gradually
              > tightening the network, even without selfish mining. Alice's strategy of
              > course should be to position her nodes in the geographical center. It's
              > worth noting how if Alice is the one with the lowest average latency,
              > she will win against any other miner trying to persue the same selfish
              > miner strategy that she is using.
              >
              >
              > Finally nLockTime makes the selfish miner strategy even more profitable.
              > You may not be aware, but it's possible to make a transaction that can't
              > be mined until some time in the future, measured by either block height
              > or block timestamp. I've proposed to use this mechanism in
              > announce/commit sacrifices: you create a transaction that can't be mined
              > until some point in the future that sacrifices a large amount to mining
              > fees, and then prior to that point you include it in the blockchain as
              > data, proving the whole world knew about your transaction. The idea was
              > that which miner managed to include the transaction, and collect the
              > reward, would be random. However whenever Alice is able to maintain a
              > lead over other miners she's able to reliably mine significantly more of
              > those valuable transactions, further increasing her revenue over other
              > miners.
              >
              >
              > I must say, you've really opened a can of worms...
              >
              >
              >
              > ------------------------------------------------------------------------------
              > Android is increasing in popularity, but the open development platform that
              > developers love is also attractive to malware creators. Download this white
              > paper to learn more about secure code signing practices that can help keep
              > Android apps secure.
              > http://pubads.g.doubleclick.net/gampad/clk?id=65839951&iu=/4140/ostg.clktrk
              >
              >
              > _______________________________________________
              > Bitcoin-development mailing list
              > Bitcoin-development@lists•sourceforge.net
              > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
              
              
              [-- Attachment #2: Type: text/html, Size: 10744 bytes --]
              
              ^ permalink raw reply	[flat|nested] 31+ messages in thread

            • • * Re: [Bitcoin-development] Auto-generated miner backbone
                  2013-11-04 21:45             ` Alan Reiner
                @ 2013-11-04 22:03               ` Peter Todd
                  0 siblings, 0 replies; 31+ messages in thread
                From: Peter Todd @ 2013-11-04 22:03 UTC (permalink / raw)
                  To: Alan Reiner; +Cc: bitcoin-development
                
                [-- Attachment #1: Type: text/plain, Size: 2853 bytes --]
                
                On Mon, Nov 04, 2013 at 04:45:24PM -0500, Alan Reiner wrote:
                > So given the assumption that Alice is "well-connected" as Peter
                > mentioned, it seems like this is a concern.  But is this a realistic
                > assumption?  All miners have an incentive to be thoroughly connected to
                > one another, to make sure they minimize the amount of time they spend
                > mining on forks and that their blocks win with minimal chance of being
                > orphaned.  Is it realistic that one miner can somehow monopolize the
                > good connections when the big miners are already trying to do the same
                > thing for honest reasons?  If you have a network full of honest miners
                > and this one selfish-miner, it seems that all the honest miners need to
                > do is try to establish those connections to each other as well as Alice
                > does, and Alice will end up orphaning all her profit away.
                
                Right, but as I said, I think this is likely to become a contest of who
                can create the lowest latency mining operation, or to be more precise,
                who can get the best ratio of latency per dollar.
                
                Unfortunately even with totally "honest" mining winning orphan rates is
                a function of latency; what this paper has done is mainly show a
                remarkably effective way of leveraging low-latency and very good
                visibility to the network.
                
                Regardless, globe-spanning low-latency networks cost a lot of money, so
                if they are something that makes mining more profitable, for whatever
                reason, that's an effect that will incentivise pools to grow larger and
                more centralized.
                
                > Furthermore, you can de-incentivize it by simply randomizing the order
                > of broadcasts.  Although you are maintaining multiple concurrent
                > connections, the data still exits your network card as a serial stream
                > of packets, and it seems that if you randomize who gets your new-block
                > broadcasts first, then it further reduces the Alice's advantage if she's
                > not guaranteed to "be first."   Sure, she can do it sometimes, but it
                > would seem that even a couple failures to beat the rest of the network
                > is going to erase most/all of what she gained on the blocks/chains that
                > she wins.
                
                Yeah, there's a lot of possible solutions, but what I'm seeing looking
                at them is they all tend to be not economically rational, in the short
                term, or even worse, they actually incentivize mining pools to get
                larger. For instance anything that tries to prevent Alice from sybiling
                the network by forcing nodes to prove they have mining capacity just
                means that larger miners will have an advantage over smaller ones in
                getting their blocks propagated as fast as possible. Once Alice does
                have a reasonable amount of mining capacity, she can still use the
                selfish miner attack to grow larger and more profitable.
                
                -- 
                'peter'[:-1]@petertodd.org
                000000000000000aae6d13639c5b4555eeda301ebcbc53f12e8a633e267c8331
                
                [-- Attachment #2: Digital signature --]
                [-- Type: application/pgp-signature, Size: 490 bytes --]
                
                ^ permalink raw reply	[flat|nested] 31+ messages in thread

  • * Re: [Bitcoin-development] Auto-generated miner backbone
      2013-11-04 14:26 ` Peter Todd
      2013-11-04 14:34   ` Pieter Wuille
           [not found]   ` <CABT1wWm1NzKSS9H=Qh3Z6pFmNHbOFKC12WaE=b3kE0mNsRgfmw@mail.gmail.com>
    @ 2013-11-04 15:27   ` Mike Hearn
      2013-11-04 17:36     ` Peter Todd
      2 siblings, 1 reply; 31+ messages in thread
    From: Mike Hearn @ 2013-11-04 15:27 UTC (permalink / raw)
      To: Peter Todd; +Cc: Ittay Eyal, Bitcoin Dev
    
    [-- Attachment #1: Type: text/plain, Size: 1608 bytes --]
    
    On Mon, Nov 4, 2013 at 3:26 PM, Peter Todd <pete@petertodd•org> wrote:
    
    > The attacker now only needs to connect to every identified miner
    > with especially fast nodes. With judicious use of DoS attacks and low
    > latency .....
    >
    
    So you're back to a complicated sybil attack. I don't follow your thought
    process here - I didn't say anything about numerical advantage. The attack
    outlined in the paper *requires* you to be able to race the rest of the
    network and win some non-trivial fraction of the time. If you can't do that
    then all it means is that when you try to release a private block to
    compete with the other found block, you're quite likely to lose and you
    sacrifice the block rewards by doing so.
    
    
    > The correct, and rational, approach for a miner is to always mine to
    > extend the block that the majority of hashing power is trying to extend.
    >
    
    There's no stable way to know that. The whole purpose of the block chain to
    establish the majority. I think your near-miss headers solution is
    circular/unstable for that reason, it's essentially a recursive solution.
    
    
    > Mining strategy is now to mine to extend the first block you see, on the
    > assumption that the earlier one probably propagated to a large portion
    > of the total hashing power. But as you receive "near-blocks" that are
    > under the PoW target, use them to estimate the hashing power on each
    > fork, and if it looks like you are not on the majority side, switch.
    >
    
    But you can't reliably estimate that. You can't even reliably estimate the
    speed of the overall network especially not on a short term basis like a
    block interval.
    
    [-- Attachment #2: Type: text/html, Size: 2362 bytes --]
    
    ^ permalink raw reply	[flat|nested] 31+ messages in thread

  • • * Re: [Bitcoin-development] Auto-generated miner backbone
        2013-11-04 15:27   ` Mike Hearn
      @ 2013-11-04 17:36     ` Peter Todd
        0 siblings, 0 replies; 31+ messages in thread
      From: Peter Todd @ 2013-11-04 17:36 UTC (permalink / raw)
        To: Mike Hearn; +Cc: Ittay Eyal, Bitcoin Dev
      
      [-- Attachment #1: Type: text/plain, Size: 1547 bytes --]
      
      On Mon, Nov 04, 2013 at 04:27:58PM +0100, Mike Hearn wrote:
      > > The correct, and rational, approach for a miner is to always mine to
      > > extend the block that the majority of hashing power is trying to extend.
      > >
      > 
      > There's no stable way to know that. The whole purpose of the block chain to
      > establish the majority. I think your near-miss headers solution is
      > circular/unstable for that reason, it's essentially a recursive solution.
      > 
      > 
      > > Mining strategy is now to mine to extend the first block you see, on the
      > > assumption that the earlier one probably propagated to a large portion
      > > of the total hashing power. But as you receive "near-blocks" that are
      > > under the PoW target, use them to estimate the hashing power on each
      > > fork, and if it looks like you are not on the majority side, switch.
      > >
      > 
      > But you can't reliably estimate that. You can't even reliably estimate the
      > speed of the overall network especially not on a short term basis like a
      > block interval.
      
      Re-read my proposal - the whole point of it is to give a way to quickly
      come to consensus about which side of the fork has the majority of
      hashing power. It doesn't, and doesn't need to, reliable determine what
      the hashing power actually is on either side. Rather it's a feedback
      mechanism that creates a clear majority consensus in a short amount of
      time with the use of only a small amount of bandwidth. (~5KB/10minutes)
      
      -- 
      'peter'[:-1]@petertodd.org
      00000000000000079c8a642234cb452cbe261fcdb5885af604471c458c257956
      
      [-- Attachment #2: Digital signature --]
      [-- Type: application/pgp-signature, Size: 490 bytes --]
      
      ^ permalink raw reply	[flat|nested] 31+ messages in thread

• * Re: [Bitcoin-development] Auto-generated miner backbone
    2013-11-04 11:26 [Bitcoin-development] Auto-generated miner backbone Mike Hearn
                     ` (2 preceding siblings ...)
    2013-11-04 14:26 ` Peter Todd
  @ 2013-11-04 15:51 ` Gregory Maxwell
    3 siblings, 0 replies; 31+ messages in thread
  From: Gregory Maxwell @ 2013-11-04 15:51 UTC (permalink / raw)
    To: Mike Hearn; +Cc: Bitcoin Dev
  
  On Mon, Nov 4, 2013 at 3:26 AM, Mike Hearn <mike@plan99•net> wrote:
  > I'm wondering about an alternative protocol change that perhaps has less
  > subtle implications than their suggested change. Rather than address the
  > problem by assuming the network is full of sybil nodes and changing the
  > rules for selecting the chain to build on, how about if we wrote code to
  > automatically build a miner backbone by having IP addresses of nodes
  > embedded into coinbases, then having any bitcoind that is creating work
  > automatically connect to IPs that appeared in enough recent blocks?
  
  Yea, I've proposed this too (both in the past and in the context of
  this). I don't think, however, that the announcements need to be the
  miners themselves— but instead just need to be nodes that the miners
  think are good (and, for their own sake— ones they're well connected
  to).
  
  Miner's could keep a list of address messages nodes they
  like/are-connected to, perhaps prioritizing their own nodes, than
  exclude ones which are already in the most recent blocks, and include
  the best remaining. Of course, if it's using address messages (or
  perhaps a new address message syntax) it would automatically support
  hidden services.
  
  They should probably be included as OP_RETURN outputs in coinbase
  transactions, maybe only limited (by what other clients pay attention
  to) to one or two per block.
  
  This should make it harder to get partitioned from the majority
  hashrate (or partition the majority hashrate from itself), though
  these hosts would be DOS targets, so it isn't a silver bullet.
  
  Making the majority hashrate self-unpartitionabilty stronger is
  possible— have miners add an encryption key to their coinbase
  transactions, then have subsequent miners mine encrypted addr messages
  to single other block sources to automatically weave a miner darknet
  with access controlled by successful block creation. But I doubt it's
  worth the complexity of bandwidth.
  
  
  
  ^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [Bitcoin-development] Auto-generated miner backbone
@ 2013-11-05  4:14 Gustaw Wieczorek
  2013-11-05  4:39 ` Peter Todd
  0 siblings, 1 reply; 31+ messages in thread
From: Gustaw Wieczorek @ 2013-11-05  4:14 UTC (permalink / raw)
  To: bitcoin-development

[-- Attachment #1: Type: text/plain, Size: 605 bytes --]

Mike Hearn wrote:

> how about if we wrote code to automatically build a miner backbone

Yeah, let's build a backbone, or a cloud, and then we could have Google run it!

Come on, Mike, your conflict-of-interest as an employee is hanging out in the open, flapping in the breeze here...  Don't you think it's a bit obvious for somebody in your position to advocate centralization of infrastructure, especially when it comes to bitcoin?


On the other hand, I guess your blind trust in IP addresses as a solid foundation for security is why you were so shocked when the NSA hacked your "backbone".

[-- Attachment #2: Type: text/html, Size: 2258 bytes --]

^ permalink raw reply	[flat|nested] 31+ messages in thread

• * Re: [Bitcoin-development] Auto-generated miner backbone
    2013-11-05  4:14 Gustaw Wieczorek
  @ 2013-11-05  4:39 ` Peter Todd
    2013-11-05  6:37   ` Gregory Maxwell
    0 siblings, 1 reply; 31+ messages in thread
  From: Peter Todd @ 2013-11-05  4:39 UTC (permalink / raw)
    To: Gustaw Wieczorek; +Cc: bitcoin-development
  
  [-- Attachment #1: Type: text/plain, Size: 1209 bytes --]
  
  On Mon, Nov 04, 2013 at 08:14:37PM -0800, Gustaw Wieczorek wrote:
  > Mike Hearn wrote:
  > 
  > > how about if we wrote code to automatically build a miner backbone
  > 
  > Yeah, let's build a backbone, or a cloud, and then we could have Google run it!
  > 
  > Come on, Mike, your conflict-of-interest as an employee is hanging out in the open, flapping in the breeze here...  Don't you think it's a bit obvious for somebody in your position to advocate centralization of infrastructure, especially when it comes to bitcoin?
  > 
  > 
  > On the other hand, I guess your blind trust in IP addresses as a solid foundation for security is why you were so shocked when the NSA hacked your "backbone".
  
  Go away.
  
  Mike specifically mentioned the idea of using Tor addresses, which are
  authenticated. In addition this mechanism to create a backbone
  *automatically* is exactly as decentralized as Bitcoin mining itself is.
  It has nothing to do with Google.
  
  I suggested the mechanism myself for slightly different reasons, and if
  you know me, you'd know I'm the first to jump on anyone pushing
  centralization.
  
  -- 
  'peter'[:-1]@petertodd.org
  000000000000000517064a43348fa39325bdc244ffb1d0da11ab85676d494a85
  
  [-- Attachment #2: Digital signature --]
  [-- Type: application/pgp-signature, Size: 490 bytes --]
  
  ^ permalink raw reply	[flat|nested] 31+ messages in thread

• • * Re: [Bitcoin-development] Auto-generated miner backbone
      2013-11-05  4:39 ` Peter Todd
    @ 2013-11-05  6:37   ` Gregory Maxwell
      0 siblings, 0 replies; 31+ messages in thread
    From: Gregory Maxwell @ 2013-11-05  6:37 UTC (permalink / raw)
      To: Peter Todd; +Cc: bitcoin-development
    
    On Mon, Nov 4, 2013 at 8:39 PM, Peter Todd <pete@petertodd•org> wrote:
    > I suggested the mechanism myself for slightly different reasons, and if
    > you know me, you'd know I'm the first to jump on anyone pushing
    > centralization.
    
    Likewise, I did too and am also not very tolerant with "trusted" or
    "centeralized" things in general.
    
    An authenticated miner announced set of nodes is _far_ from a cure
    all, as any attack they stop can be recovered by adding "and dos
    attacks the public miner announced nodes" to the attack's
    requirements... but we build security with layers.
    
    Bitcoin's security is only improved when we can weave the network
    tighter and make partitioning it more difficult.
    
    
    
    ^ permalink raw reply	[flat|nested] 31+ messages in thread

end of thread, other threads:[~2013-11-15 22:07 UTC | newest]

Thread overview: 31+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-11-04 11:26 [Bitcoin-development] Auto-generated miner backbone Mike Hearn
2013-11-04 11:53 ` Peter Todd
2013-11-04 12:00   ` Mike Hearn
2013-11-04 18:16     ` [Bitcoin-development] Committing to extra block data/a better merge-mine standard Peter Todd
2013-11-04 18:32       ` Peter Todd
2013-11-04 19:11       ` Mark Friedenbach
2013-11-15 22:06         ` Peter Todd
2013-11-04 19:38       ` Mike Hearn
2013-11-04 19:53         ` Mark Friedenbach
2013-11-04 20:10           ` Mike Hearn
2013-11-04 11:58 ` [Bitcoin-development] Auto-generated miner backbone Michael Gronager
2013-11-04 12:03   ` Mike Hearn
2013-11-04 12:20     ` Peter Todd
2013-11-04 12:40     ` Michael Gronager
2013-11-04 15:58   ` Gregory Maxwell
2013-11-04 14:26 ` Peter Todd
2013-11-04 14:34   ` Pieter Wuille
2013-11-04 14:46     ` Peter Todd
     [not found]   ` <CABT1wWm1NzKSS9H=Qh3Z6pFmNHbOFKC12WaE=b3kE0mNsRgfmw@mail.gmail.com>
2013-11-04 15:04     ` Peter Todd
     [not found]       ` <CABT1wWmONUeOWRg-=FKr88bgBQf0un4bvjYW2h8d-10ys-VKtA@mail.gmail.com>
2013-11-04 15:46         ` Peter Todd
     [not found]           ` <CABT1wWmM466jWWdWAo5GmzP58xJFT70Vcr74ta+2QF2fWT+1SA@mail.gmail.com>
2013-11-04 16:07             ` Peter Todd
     [not found]               ` <CABT1wWm5BDZf7U40pOqZvTqdOKeTWUTekjUNckq5McMV=LDu_g@mail.gmail.com>
2013-11-04 16:51                 ` Peter Todd
     [not found]         ` <CABT1wWmwb17b4ACHMmDKqd94tUSKsvwAPx344mZ0VS+47myeWg@mail.gmail.com>
2013-11-04 21:04           ` Peter Todd
2013-11-04 21:45             ` Alan Reiner
2013-11-04 22:03               ` Peter Todd
2013-11-04 15:27   ` Mike Hearn
2013-11-04 17:36     ` Peter Todd
2013-11-04 15:51 ` Gregory Maxwell
2013-11-05  4:14 Gustaw Wieczorek
2013-11-05  4:39 ` Peter Todd
2013-11-05  6:37   ` Gregory Maxwell

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox