Voluntary Mind

BIP324

Introduction

Abstract

This document proposes an end-to-end encrypted P2P transport protocol for Bitcoin.

This document is licensed under the 3-clause BSD license and is placed in the public domain.

Motivation

The current Bitcoin P2P protocol(referred to as v1 in this document) is plaintext. It is self-revealing and presents malicious intermediaries a low cost to covertly censor, tamper or hijack. This proposal aims to make such attacks overt and increase the cost of attack using end-to-end encryption and an indistinguishable from random, shapable bytestream. The proposal intends to achieve the goals without adding computation overhead or risking network partitions by maintaining compatibility with v1.

Design

Bitcoin is a permissionless, public network. By design, the protocol lacks identity and depends on proof-of-work for consensus. That should not, however, deter us from considering encrypting traffic because it will raise the cost for intermediaries to censor/tamper/hijack connections and increase privacy for network participants.

The overall proposed design is:

The proposal tries to achieve the following properties:

Transport layer specification

Signaling v2 support

Peers supporting the v2 transport protocol signal support using the NODE_P2P_V2 = (1 << 11) service flag advertised using addr relay.

v2 encrypted message structure

The structure of the v2 encrypted messages is as follows:

Field Size in bytes Comments
header 3 Encrypt(LittleEndian(ciphertext_length + ignore<<23))
ciphertext ciphertext_length Encrypted payload. ciphertext_length <= 2^23-1
mac 16 Poly1305(header+ciphertext)

Initial handshake

 ----------------------------------------------------------------------------------------
 | Initiator                             Responder                                      |
 |                                                                                      |
 | x, X := v2_keygen(initiating=True)                                                   |
 | INITIATOR_HDATA := secp256k1_ellsq_encode(X)                                         |
 |                                                                                      |
 |               --- INITIATOR_HDATA --->                                               |
 |                                                                                      |
 |                                       y, Y := v2_keygen(initiating=False)            |
 |                                       X := secp256k1_ellsq_decode(INITIATOR_HDATA)   |
 |                                       ECDH_KEY := secp256k1_ecdh(X,y)                |
 |                                       RESPONDER_HDATA := secp256k1_ellsq_encode(Y)   |
 |                                                                                      |
 |               <-- RESPONDER_HDATA || v2_enc_msg(RESPONDER_TRANSPORT_VERSION) ---     |
 |                                                                                      |
 | Y := secp256k1_ellsq_decode(RESPONDER_HDATA)                                         |
 | ECDH_KEY := secp256k1_ecdh(x,Y)                                                      |
 |                                                                                      |
 |               --- v2_enc_msg(INITIATOR_TRANSPORT_VERSION) --->                       |
 |                                                                                      |
 ----------------------------------------------------------------------------------------

To establish a v2 encrypted connection, the initiator generates an ephemeral secp256k1 keypair and sends the unencrypted elligator-squared2 3 encoding of the public key to the responding peer.

def initiate_v2_handshake(responder):
    x, X = v2_keygen(initiating=True)
    initiator_hdata = secp256k1_ellsq_encode(X)
    send(responder, initiator_hdata)

The responder decodes the initiator’s public key, generates an ephemeral keypair for itself and computes the ECDH secret which enables it to instantiate the encrypted transport. It then sends 64 bytes of the unencrypted elligator-squared encoding of its own public key appended with a v2 protocol encrypted message where the payload is set to a transport version number. The initial v2 clients implementing this proposal (v2.0 clients) will only support transport version 0. An empty payload should be interpreted as transport version 0. This design choice allows deferral of the transport version number encoding until version 1.

def respond_v2_handshake(initiator, initiator_hdata):
    X = secp256k1_ellsq_decode(initiator_hdata)
    y, Y = v2_keygen(initiating=False)
    responder_hdata = secp256k1_ellsq_encode(Y)
    ecdh_secret = secp256k1_ecdh(X, y)
    initialize_v2_transport(initiator, ecdh_secret, initiator_hdata, responder_hdata, False)
    send_bytes = responder_hdata + v2_enc_msg(initiator, TRANSPORT_VERSION)
    send(initiator, send_bytes)

secp256k1_ecdh is defined as the ECDH function provided by libsecp256k1 with hashfp set to secp256k1_ecdh_hash_function_default (which uses SHA256) and data set to NULL.

Upon receiving the responder public key, the initiator decodes it, instantiates the encrypted transport and sends its own transport version number as well. The transport session version 4 is set to the minimum of the supported versions. If the received version number is empty or malformed, it will be interpreted as transport version 0.

def initiator_complete_handshake(responder, response):
    responder_hdata = response[:64]
    Y = secp256k1_ellsq_decode(responder_hdata)
    ecdh_secret = secp256k1_ecdh(Y, x)
    initialize_v2_transport(responder, ecdh_secret, initiator_hdata, responder_hdata, True)
    responder_transport_version = v2_dec_msg(responder, response[64:])
    send(responder, v2_enc_msg(responder, TRANSPORT_VERSION))
    set_transport_version(responder, min(responder_transport_version, TRANSPORT_VERSION))

The responder also similarly sets the session version:

def responder_complete_handshake(initiator, msg):
    initiator_transport_version = v2_dec_msg(initiator, msg)
    set_transport_version(initiator, min(initiator_transport_version, TRANSPORT_VERSION))

Ephemeral keypair generation

To aid disambiguation of v1 and v2 handshakes, public keys with Elligator-squared encodings starting with the 12-bytes of NETWORK_MAGIC || "version\x00" are forbidden for use by the initiator 5. This restriction does not apply to the responder.

def v2_keygen(initiating):
    priv, pub = secp256k1_keygen()
    if initiating:
        while True:
            encoded_pubkey = secp256k1_ellsq_encode(pub)
            if (encoded_pubkey[:12] == NETWORK_MAGIC + "version\x00"):
                # Encoded public key cannot start with the specified prefix
                priv, pub = secp256k1_keygen()
            else:
                break
    return priv, pub

Elligator-squared mapping and encoding of field elements

The elligator-squared paper prescribes the properties of the mapping function from field elements to curve points and provides one such choice in section 4.3. The mapping function used in this proposal is described in another paper by Fouque and Tibouchi. Let f be the function from field elements to curve points, defined as follows:

def f(t):
    c = 0xa2d2ba93507f1df233770c2a797962cc61f6d15da14ecd47d8d27ae1cd5f852
    x1 = (c - 1)/2 - c*t^2 / (t^2 + 8) (mod p)
    x2 = (-c - 1)/2 + c*t^2 / (t^2 + 8) (mod p)
    x3 = 1 - (t^2 + 8)^2 / (3*t^2) (mod p)

    // At least one of (x1, x2, x3) is guaranteed to be a valid x-coordinate on the curve for any t
    for x_candidate in (x1, x2, x3):
        if secp256k1_is_valid_x_coord(x_candidate):
            x = x_candidate
            break

    // Pick the curve point where the Y co-ordinate is the same parity(even/odd) as t
    if t % 2:
        y = secp256k1_odd_y(x)
    else:
        y = secp256k1_even_y(x)

    return secp256k1_point(x, y)

The Elligator-squared encoding of a curve point P(public key) consists of the 32-byte big-endian encodings of field elements u1 and u2 concatenated, where f(u1)+f(u2) = P. The encoding algorithm is described in the paper, and effectively picks a uniformly random pair (u1,u2) among those which encode P. For completeness, to make the encoding able to deal with all inputs, if f(u1)+f(u2) is the point at infinity, the decoding is defined to be f(u1) instead. A detailed writeup on the encoding algorithm we use can be found here.

Keys and Session ID Derivation

The authenticated encryption construction proposed here requires two ChaCha20Forward4064-Poly1305 cipher suite instances per communication direction. Four 32-byte keys and session id are computed using HKDF per RFC 5869 as shown below.

def initialize_v2_transport(peer, ecdh_secret, initiator_hdata, responder_hdata, initiating):
    prk = HKDF_Extract(Hash=sha256, salt="bitcoin_v2_shared_secret" + initiator_hdata + responder_hdata + NETWORK_MAGIC, ikm=ecdh_secret)

    # We no longer need the ECDH secret
    memory_cleanse(ecdh_secret)

    initiator_F = HKDF_Expand(Hash=sha256, PRK=prk, info="initiator_F", L=32)
    initiator_V = HKDF_Expand(Hash=sha256, PRK=prk, info="initiator_V", L=32)
    responder_F = HKDF_Expand(Hash=sha256, PRK=prk, info="responder_F", L=32)
    responder_V = HKDF_Expand(Hash=sha256, PRK=prk, info="responder_V", L=32)
    sid         = HKDF_Expand(Hash=sha256, PRK=prk, info="session_id",  L=32)

    if initiating:
        peer.send_F = initiator_F
        peer.send_V = initiator_V
        peer.recv_F = responder_F
        peer.recv_V = responder_V
    else:
        peer.recv_F = initiator_F
        peer.recv_V = initiator_V
        peer.send_F = responder_F
        peer.send_V = responder_V

v2 clients supporting this proposal must present the session id to the user upon request to allow for manual, out of band connection verification. Future transport versions may integrate authentication1.

[email protected] Cipher Suite

Background: Existing cryptographic primitives

ChaCha20PRF(key, iv, ctr) is the pseudo-random function(PRF) defined in this paper. It takes a 256-bit key, a 64-bit IV and a 64-bit counter as inputs, and returns 512 pseudorandom bits.

The PRF can be composed into a deterministic random bit generator(DRBG) producing a pseudo-random keystream as shown below.

def ChaCha20DRBG(key, iv):
    ctr = 0
    while ctr < 2**64:
        yield ChaCha20PRF(key, iv, ctr)
        ctr += 1

This keystream can be XORed with plaintext to create a stream cipher. The stream cipher derived from ChaCha20DRBG(key, iv) does not provide forward secrecy6 in case of a compromised key. This proposal outlines a new ChaCha20Forward4064DRBG(key) construction to permit implementations that offer forward secrecy.

Our proposal also utilizes Poly1305(key, ciphertext), a one-time Carter-Wegman MAC defined in this paper. It uses a 256-bit key and produces a 128-bit message authentication code.

New primitive: ChaCha20Forward4064DRBG

The ChaCha20Forward4064DRBG(key) is composed by using the first 4064 bytes7 from the ChaCha20DRBG(key, iv) as the keystream and then re-keying the DRBG using the next 32 bytes8. The IV is incremented upon re-key.

CHACHA20_KEYLEN = 32 # bytes
CHACHA20_BLOCKSIZE = 64
KEY_ROTATION_INTERVAL = 4064

def ChaCha20Forward4064DRBG(key):
    c20_key = key
    iv = 0
    while True:
        for _ in range(0, KEY_ROTATION_INTERVAL - CHACHA20_BLOCKSIZE, step=CHACHA20_BLOCKSIZE):
            yield from ChaCha20DRBG(c20_key, iv)
        byts = ChaCha20DRBG(c20_key, iv)
        memory_cleanse(c20_key)
        c20_key = byts[(CHACHA20_BLOCKSIZE - CHACHA20_KEYLEN):]
        iv += 1
        yield byts[:(CHACHA20_BLOCKSIZE - CHACHA20_KEYLEN)]

Detailed construction

The [email protected] cipher suite requires two instances9 of ChaCha20Forward4064DRBG per communication direction. We will call the instances F(used for fixed-length keystream purposes, using 35 bytes per message) and V(used for variable length purposes).

Encrypting

When encrypting a message M of length len(M) bytes:

Decrypting

Application layer specification

v2 Bitcoin P2P message structure

v2 Bitcoin P2P messages use the v2 encrypted message structure shown above. The ciphertext payload is composed of:

Field Size in bytes Comments
message_type 1-13 Encrypted one byte message type ID or ASCII message type
payload payload_length Encrypted payload

If the first byte is in the range [1, 12], it is interpreted as the number of ASCII bytes that follow for the message type. If it is in the range [13, 255], it is interpreted as a message type ID. This structure results in smaller messages than the v1 protocol as most messages sent/received will have a message type ID. 10

The message type IDs for existing P2P message types are:

ADDR:13
BLOCK:14
BLOCKTXN:15
CMPCTBLOCK:16
FEEFILTER:17
FILTERADD:18
FILTERCLEAR:19
FILTERLOAD:20
GETADDR:21
GETBLOCKS:22
GETBLOCKTXN:23
GETDATA:24
GETHEADERS:25
HEADERS:26
INV:27
MEMPOOL:28
MERKLEBLOCK:29
NOTFOUND:30
PING:31
PONG:32
SENDCMPCT:33
SENDHEADERS:34
TX:35
VERACK:36
VERSION:37
GETCFILTERS:38
CFILTER:39
GETCFHEADERS:40
CFHEADERS:41
GETCFCHECKPT:42
CFCHECKPT:43
WTXIDRELAY:44
ADDRV:45
SENDADDRV:46

The message types may be updated separately after BIP finalization.

Test Vectors

TODO: Update test vectors to: (ellsq_pubkey_1, ellsq_pubkey_2, initiator_F, initiator_V, responder_F, responder_V, session_id, [plaintext_initiator, ciphertext+mac_initiator, plaintext_responder, ciphertext+mac_responder])

plaintext:
1d00000000000000000000000000000000000000000000000000000000000000

k_F:
0000000000000000000000000000000000000000000000000000000000000000

k_V:
0000000000000000000000000000000000000000000000000000000000000000

ciphertext+mac:
6bb8e076b8e0ada0f13d90405d6ae55386bd28bdd219b8a08ded1aa836efcc8babf71de83e6e27c82490bdc8615d0c9e
This test vector has an incorrect header to show that header correctness is an application layer responsibility

plaintext:
0100000000000000000000000000000000000000000000000000000000000000

k_F:
0000000000000000000000000000000000000000000000000000000000000000

k_V:
0000000000000000000000000000000000000000000000000000000000000000

ciphertext+mac:
77b8e076b8e0ada0f13d90405d6ae55386bd28bdd219b8a08ded1aa836efcc8bfb6cf9dcd7e2ee807d5ff981eb4a135a
plaintext:
fc0000f195e66982105ffb640bb7757f579da31602fc93ec01ac56f85ac3c134a4547b733b46413042c9440049176905d3be59ea1c53f15916155c2be8241a38008b9a26bc35941e2444177c8ade6689de95264986d95889fb60e84629c9bd9a5acb1cc118be563eb9b3a4a472f82e09a7e778492b562ef7130e88dfe031c79db9d4f7c7a899151b9a475032b63fc385245fe054e3dd5a97a5f576fe064025d3ce042c566ab2c507b138db853e3d6959660996546cc9c4a6eafdc777c040d70eaf46f76dad3979e5c5360c3317166a1c894c94a371876a94df7628fe4eaaf2ccb27d5aaae0ad7ad0f9d4b6ad3b54098746d4524d38407a6deb3ab78fab78c9

k_F:
ff0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f

k_V:
000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f

ciphertext+mac:
3a40c1c868cd145bd54691e9b6b402c78bd7ea9c3724fc50dfc69a4a96be8dec4e70e958188aa69222eaef3f47f8003f1bc13dcf9e661be8e1b671e9cf46ba705bca963e0477a5b3c2e2c66feb8207269ddb01b1372aad68563bb4aad135afb06fbe40b310b63bef578ff939f3a00a6da9e744d28ba070294e5746d2ca7bb8ac2c8e3a855ab4c9bcd0d5855e11b52cacaa2ddb34c0a26cd04f4bc10de6dc151d4ee7ced2c2b0de8ded33ff11f301e4027559e8938b69bceb1e5e259d4122056f6adbd48a0628b912f90d72838f2f3aaf6b88342cf5bac3cb688a9b0f7afc73a7e3cad8e71254c786ea000240ae7bd1df8bcfca07f3b885723a9d7f89736461917bb2791faffbe34650c8501daaef76

Acknowledgements

Thanks to everyone(alphabetical order) that helped invent and develop the ideas in this proposal:

Rationale and References


  1. Adding authentication with a future transport version will incur an extra round trip when compared to incorporating it in this proposal (version 0). However, given the low frequency of connections, this cost is low and a trade-off that permits simpler design for version 0 and keeps authentication optional. [return]
  2. Elligator-squared is an encoding for elliptic curve points that allows us to make the serialization indistinguishable from a uniformly distributed bitstream. While a random 256-bit string has about 50% chance of being a valid x-coordinate on the secp256k1 curve, every 512-bit string is a valid Elligator-squared encoding of a curve point, making the encoded point indistinguishable from random when using an encoder that can sample uniformly. [return]
  3. In writing this proposal, the performance of Elligator-squared encoding was benchmarked. Encoded ECDH is about ~2.72x as expensive than the unencoded ECDH. Given the fast performance of ECDH and the low frequency of new connections, we found the performance trade-off acceptable for the pseudo-random bytestream and future censorship resistance it can enable. [return]
  4. Once an encrypted transport and its session version is established, further properties of the transport can be negotiated. Examples include post-quantum cryptography upgrades to the handshake and identity key authentication. While this proposal does not include any such features, it allows for an upgrade path using transport version numbers. As a hypothetical example, v2.1 clients would exchange the transport version number 1. If both peers are v2.1, the transport session version would be 1. This could imply that before any P2P messages are exchanged, a post-quantum key exchange mechanism must be used (as defined in the hypothetical v2.1 protocol) to upgrade the security of the derived encryption keys against quantum computers. [return]
  5. Disallowing elligator-squared encodings that begin with the specified prefix does result in a less than perfectly indistinguishable-from-random bytestream. While the 2^-96 bias this introduces is strictly speaking above our 128-bit security level, the low frequency of connections makes this practically unexploitable, while significantly simplifying compatibility. [return]
  6. If an attacker passively collects ciphertext and later, learns the key, they can decrypt all the historical ciphertext. [return]
  7. Assuming a node sends only ping messages (28 bytes in the v2 protocol) every 20 minutes (the timeout interval for post-BIP31 connections) on a connection, the node will transmit 4064 bytes in a little over 2 days. [return]
  8. This is a single ratchet as opposed to a double ratchet mechanism used in Signal. The proposed hash-based single ratchet provides forward secrecy but not future secrecy. This choice reduces the complexity of the proposal, but requires clients to disconnect and reconnect if they want to renegotiate keys. [return]
  9. An MITM attacker should be assumed to have knowledge of the plaintext corresponding to the encrypted 3-byte header. This can lead to malleability in the header ciphertext since it is used prior to checking the MAC. We use two cipher instances to avoid any consequences of such malleability leaking into the payload portion of the ciphertext. The two cipher instances make it easier to reason about the security of the suite. The cost in creating additional ChaCha20 and Poly1305 instances is very low. [return]
  10. Here are some length comparisons between v1 and v2 messages:

    v1 inv: 4(Magic)+12(Message-Type)+4(MessageSize)+4(Checksum)+37(Payload) == 61
    v2 inv: 3(Header)+1(Message-Type)+37(Payload)+16(MAC) == 57
    (93.44%)
    
    v1 ping: 4(Magic)+12(Message-Type)+4(MessageSize)+4(Checksum)+8(Payload) == 32
    v2 ping: 3(Header)+1(Message-Type)+8(Payload)+16(MAC) == 28
    (87.5%)
    
    v1 block: 4(Magic)+12(Message-Type)+4(MessageSize)+4(Checksum)+1’048’576(Payload) = 1’048’600
    v2 block: 3(Header)+1(Message-Type)+1’048’576(Payload)+16(MAC) = 1’048’596
    (99.9996%)
    [return]