Bitslog

The need for direct connection between the main miner pools or solo-miners (which is often called the miner backbone), was discussed several times in the forums and in this blog during the last two years.  A miner backbone provides not only benefits to the network as a whole, but benefits for those miners that establish such connections. A backbone decreases the chances of blocks being orphaned, so miners also have a strong incentive to have direct connections between them and announce a solved block as soon as possible. This is one of the fundamental properties of the 5 second block rate solution adopted by NimbleCoin and the MinCen protocol. Also the network benefits from the backbone because a backbone decreases the probability of a block-chain split between two competing subnets because of an accidental or deliberate loss of connectivity. There are several possible attacks to the Bitcoin network widely analyzed that try to isolate nodes, such as the Sybil attack or the Timejacking attack. A direct backbone would allow miners to either go around the attacked nodes or detect if the other miners are unreachable and therefore they are being isolated. A backbone can be created manually: two mining pool administrators meet in an IRC channel, they convince each other that they are who they say they are, they convince each other what their hashing power is, they exchange PGP public keys, they verify the public keys in a public keystore,  and finally they exchange encrypted and signed e-mails containing their IP addresses. This “solution” has many drawbacks:

1. It’s very difficult to be kept anonymous: to connect another top miner, who must know who the miner administrator is or have his contact information, and there are several communication stages over different protocols (SMTP, PGP, IRC, HTTP) that must be done though anonymous protocols to preserve anonymity.
2. It does not scale: if there are n top miners, this method requires that each party manually contact privately (n-1) other parties.
3. It’s static: if the network hash distribution changes, or a new top miner emerges, then new private channels must be created manually.
4. It’s complicated: it requires at least 4 manual verifications through external channels of the information provided by the other party (administrator search, identity, hashing power, PGP keys)

We’d like to have a protocol that has the following properties:

1. Allow anonymous messages: top miners can contact other top miners administrators without relying in other anonymization technologies such as Tor.
2. Scalability up to 100 top miners. Scaling more seems to be unnecessary.
3. Dynamic: it must adapt automatically to changes in the network hashing power distribution.
4. Simple: It should not rely in many other protocol layers.
5. Automatic: creating and maintaining the backbone should not require user intervention.
6. Private: each miner may choose which IP/Tor addresses to inform each other miner and IP/Tor addresses should not be published to every node. This allows the identification of the source in case of a DoS attacks over one of the backbone connections.
7. Simultaneous Zero knowledge proof of minimum hashpower (SIZKPMH): miners should be able to prove to other miners that they control a certain minimum amount haspower only if the other miner also has the same minimum hashpower. Because the backbone is intended to protect the top miners (e.g. having more than 5% of the network hashing power), the protocol should prevent that a miner that has 0.01% of the network hashing power obtain a direct connections to a miner having 10% of hashing power or even discover this fact.

One of the solutions proposed is that in every block each miners publishes a list of IP addresses he owns (or Tor addresses), allowing other miners (and any other party) to connect to them directly. The problem with this solution is that this information is made public to everyone, but it was intended for only the other top miners (the private property is not hold).

The PAMBA Protocol [1]

An improvement over this protocol is that the miners create private communication channels using pairwise Diffie-Hellman shared keys automatically, and exchange their IP addresses over encrypted block payload.

The first version of this protocol requires that the top miners reveal their pool sizes by including an unique identification in their blocks. Because of this, the PAMBA protocol does not completely achieve the zero-knowledge property. This does not seem to be a privacy problem since currently Bitcoin mining pools do it.

Every miner having more than 10% of the network power (e.g. mining pools) include in their blocks an identification and an encryption public key. This could be done by re-using the same ECDSA public key for the first generation transaction output in every block and using that key for ECIES encryption. But this pose several risks: first signing keys and encryption keys do not have the same lifespan and second it’s not proven that re-using the keys for encryption does not lead to an attack on the signature scheme (it’s it proved for Schnorr signatures).  So each miner creates another key-pair for encryption (s(i),P(i)) where s(i) the secret key and P(i) is the public key. The protocol request that miners periodically (e.g. once a day) include in the coinbase field the record < “MID” , P(i) > where:

– The tag “MID” (Master ID) marks this block to be the source of miner Identification information

– P(i) is the encryption public key.

An rogue miner M(j) may copy the P(i) value of the miner M(i) and include P(i) in his blocks, instead of P(j). This can only increase the apparent hashing power of the miner M(i), and provide not benefit to the miner M(j).  If this is a problem, a Schnorr signature scheme can be used and the value sign(GenerationTx, P(i)) can be included in the MID record. This proves that whoever created the generation transaction also knows the private key s(i).

For all blocks that are not MID blocks, a shorter version of ID is used: < “ID”, Truncate(H(P(i)),8) >, where Truncate(x,n) truncates a bit-string to n bytes and H(x) is a cryptographic hash function. The “ID” block overhead is therefore only 10 bytes.

The remaining miners can track the creation of encryption keys in MID blocks and associate all remaining blocks that belong to the same miner by tracking ID blocks.

Suppose that Alice has the encryption key P(A) (public key) that corresponds to her secret key s(A). After detecting a change on the network hashing power a miner Alice that wants to establish a direct connection with a set of miners X(1)..X(n). Each miner X(i) has an encryption key P(i).  Alice then creates a shared secret with each miner. We use a slight modification of the ECIES scheme. Let ENCA() be an encryption and authentication function (e.g. AES + SHA-256) and DECA() the decryption and authentication verification function.   The procedure is as follows:

1. Alice creates a Diffie-Hellman shared secrets with each miner X(i) as T(i) = s(A)*P(i) (multiplication in the elliptic curve)
2. Alice derives a AES key AES(i) and MAC key MAC(i) using a key-derivation function from each shared secret T(i): < AES(i),MAC(i) > = KeyDerivation(T(i))
3. For each miner X(i), Alice includes in a block in the coinbase field the a secret message containing her encrypted IP address: < “IP”, H(P(i)), ENCA(<IP address> , (AES(i), MAC(i)) ) >.

If the payload is large (e.g. many IP addresses) and the same payload is sent for every miner X(i) then a two-level encryption scheme can be used: first a single symmetric key is created randomly and it is encrypted for each miner using the shared secret, and then the symmetric key is used to encrypt the large payload.

To decrypt the IP address, every miner X(i) does the following procedure:

1. Find the record “IP” containing H(P(i)) as the second component. Let this record be < “IP”, H(P(i)), m  >
2. Compute T(i) = s(i)*P(A)
3. Derives a AES key AES(i) and MAC key MAC(i) as < AES(i),MAC(i) > = KeyDerivation(T(i))
4. Compute <IP address > = DECA(m, (AES(i), MAC(i)) ). Abort if authentication fails.

The PAMBA+ Protocol

The PAMBA protocol could be modified to preserve the privacy of the amount of hashing power owned and that the miner identity is only revealed when two miners attempt to communicate to exchange IP addresses: each miner maintains separate identities for each 1% of the network hashing power. Then a miner having n% of the hashing power should establish (100-n) shared secrets with the remaining parties. This is costly but also this does not prevent a miner with very low hashing power from obtaining the the IP of a top mining pool. The problem is how can two miners simultaneously prove to each other they own a certain hashing power without disclosing more information than what it is received. I propose a possible solution where miners alternately exchange information regarding a certain level of ownership and increase that level alternatively in small steps until one of them has no more hashing power to prove. Here is an example of how two miners Alice and Bob could achieve a better SIZKPMH property. The Zero-knowledge property if not fully achieved because miners learn information about the other party hashing power that can be user to convince a third party of that fact. Nevertheless the information released and obtained is symmetric: either both obtain it from the other or no one does.

Let VA(0) = H( PA(0) ). PA(0) is a public key for the random keypair (sA(0),PA(0)). H is the application of a cryptographic hashing function.

VA(i) = H ( VA(i-1) || PA(i) ).

Let Alice computes VA(0)..VA(k). Alice includes in 10% of her blocks the record <“H”, VA(k-1)  > in the coinbase fields. She includes <“H” , VA(k-2) > in another 10% , and so on. Bob does the same using VB(i) and PB(i).

Suppose Alice and Bob each own 20% of the network hashing power. They can gradually reach the simultaneous prove in 10 steps using this SIZKPMH protocol:

1. Alice proves to Bob she owns 2% of the network hashing power by revealing VA(k-1) || PA(k) and using sA(i) to authenticate herself (e.g. signing a random message chosen by both parties (e.g. fair coin flip) or taking the hash of the last 100 block headers).
2. Bob verifies Alice claimed ownership of 2% of the blocks by inspecting the “H” records of the last 1000 blocks , and verifies Alice control of PA(k).
3. Bob proves to Alice he also owns 2% by revealing VB(k-1) || PB(k)
4. Alice verifies Bob claimed ownership of 2% of the blocks and the protocol goes back to step 1 for another 2% of the blocks, until one of them asserts he has no more blocks in control.
5. Alice and Bob decide if they’re going to reveal their IP addresses.

If Alice thinks the Bob percentage of network hashing power is not enough to justify a direct connection, she won’t reveal her IP address. There are several ways to exchange the protocol messages. One is that the messages involved in the protocol are embedded in each block as a side-channel. To allow this to be done efficiently, instead of including the side-channel information in the block itself, the networking protocol can be modified so each block B(i) has reference to an external message MSG(i), which is sent some time afterwards. MSG(i) could be large (e.g. 10 Kbytes) and should be forwarded by the network and cached for a couple of hours after B(i) was created. The coinbase field of B(i) would include a record < “MSG” : H(MSG(i)) > to allow the propagation of message MSG(i) after the block is well confirmed (e.g. 6 confirmations) but still preventing the abuse of this special inter-miner messaging system.

Another option is that each miner having n% of the total hashing power also owns n different IP addresses, so each block publishes one of n addresses randomly. Then all miners look as they have at most 1% of the network hashing power, but once the miner is contacted, the SIZKPMH protocol is run interactively to discover the real hashing power share of the other party.

To summarize, a private backbone between the top miners can be built automatically without the need to disclose the hashing power of each miner to non-top miners.

[1] Do you know how difficult is to create a protocol with an pronounceable acronym?