diff --git a/src/avalanche/processor.h b/src/avalanche/processor.h
--- a/src/avalanche/processor.h
+++ b/src/avalanche/processor.h
@@ -273,6 +273,7 @@
     bool forNode(NodeId nodeid, std::function<bool(const Node &n)> func) const;
 
     CPubKey getSessionPubKey() const;
+    bool sendHello(CNode *pfrom) const;
 
     bool startEventLoop(CScheduler &scheduler);
     bool stopEventLoop();
diff --git a/src/avalanche/processor.cpp b/src/avalanche/processor.cpp
--- a/src/avalanche/processor.cpp
+++ b/src/avalanche/processor.cpp
@@ -173,8 +173,12 @@
             stream >> peerData->proof;
 
             // Ensure the peer manager knows about it.
-            LOCK(cs_peerManager);
-            peerManager->getPeerId(peerData->proof);
+            // FIXME: There is no way to register the proof at this time because
+            // we might not have the proper chainstate at the moment. We need to
+            // find a way to delay the registration of the proof until after IBD
+            // has finished and the chain state is settled.
+            // LOCK(cs_peerManager);
+            // peerManager->getPeerId(peerData->proof);
         }
 
         // Generate the delegation to the session key.
@@ -394,6 +398,36 @@
     return sessionKey.GetPubKey();
 }
 
+bool Processor::sendHello(CNode *pfrom) const {
+    if (!peerData) {
+        // We do not have a delegation to advertise.
+        return false;
+    }
+
+    // Now let's sign!
+    std::array<uint8_t, 64> sig;
+
+    {
+        CHashWriter hasher(SER_GETHASH, 0);
+        hasher << peerData->delegation.getId();
+        hasher << pfrom->GetLocalNonce();
+        hasher << pfrom->nRemoteHostNonce;
+        hasher << pfrom->GetLocalExtraEntropy();
+        hasher << pfrom->nRemoteExtraEntropy;
+        const uint256 hash = hasher.GetHash();
+
+        if (!sessionKey.SignSchnorr(hash, sig)) {
+            return false;
+        }
+    }
+
+    connman->PushMessage(pfrom, CNetMsgMaker(pfrom->GetSendVersion())
+                                    .Make(NetMsgType::AVAHELLO,
+                                          Hello(peerData->delegation, sig)));
+
+    return true;
+}
+
 bool Processor::startEventLoop(CScheduler &scheduler) {
     return eventLoop.startEventLoop(
         scheduler, [this]() { this->runEventLoop(); }, AVALANCHE_TIME_STEP);
diff --git a/src/avalanche/protocol.h b/src/avalanche/protocol.h
--- a/src/avalanche/protocol.h
+++ b/src/avalanche/protocol.h
@@ -5,6 +5,7 @@
 #ifndef BITCOIN_AVALANCHE_PROTOCOL_H
 #define BITCOIN_AVALANCHE_PROTOCOL_H
 
+#include <avalanche/delegation.h>
 #include <protocol.h> // for CInv
 #include <serialize.h>
 #include <uint256.h>
@@ -80,6 +81,24 @@
     }
 };
 
+class Hello {
+    Delegation delegation;
+    std::array<uint8_t, 64> sig;
+
+public:
+    Hello(Delegation delegationIn, std::array<uint8_t, 64> sigIn)
+        : delegation(std::move(delegationIn)), sig(sigIn) {}
+
+    // serialization support
+    ADD_SERIALIZE_METHODS;
+
+    template <typename Stream, typename Operation>
+    inline void SerializationOp(Stream &s, Operation ser_action) {
+        READWRITE(delegation);
+        READWRITE(sig);
+    }
+};
+
 } // namespace avalanche
 
 #endif // BITCOIN_AVALANCHE_PROTOCOL_H
diff --git a/src/net.h b/src/net.h
--- a/src/net.h
+++ b/src/net.h
@@ -10,6 +10,7 @@
 #include <addrdb.h>
 #include <addrman.h>
 #include <amount.h>
+#include <avalanche/delegation.h>
 #include <bloom.h>
 #include <chainparams.h>
 #include <compat.h>
@@ -853,6 +854,7 @@
     const CAddress addr;
     // Bind address of our side of the connection
     const CAddress addrBind;
+    // The nonce provided by the remote host.
     std::atomic<int> nVersion{0};
     // The nonce provided by the remote host.
     uint64_t nRemoteHostNonce{0};
@@ -998,6 +1000,15 @@
     // m_tx_relay == nullptr if we're not relaying transactions with this peer
     std::unique_ptr<TxRelay> m_tx_relay;
 
+    struct AvalancheState {
+        AvalancheState() {}
+
+        avalanche::Delegation delegation;
+    };
+
+    // m_avalanche_state == nullptr if we're not using avalanche with this peer
+    std::unique_ptr<AvalancheState> m_avalanche_state;
+
     // Used for headers announcements - unfiltered blocks to relay
     std::vector<BlockHash> vBlockHashesToAnnounce GUARDED_BY(cs_inventory);
 
diff --git a/src/net_processing.cpp b/src/net_processing.cpp
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -7,6 +7,8 @@
 
 #include <addrman.h>
 #include <avalanche/processor.h>
+#include <avalanche/proof.h>
+#include <avalanche/validation.h>
 #include <banman.h>
 #include <blockdb.h>
 #include <blockencodings.h>
@@ -2807,6 +2809,7 @@
             m_connman.PushMessage(&pfrom,
                                   msgMaker.Make(NetMsgType::SENDHEADERS));
         }
+
         if (pfrom.nVersion >= SHORT_IDS_BLOCKS_VERSION) {
             // Tell our peer we are willing to provide version 1 or 2
             // cmpctblocks. However, we do not request new block announcements
@@ -2819,6 +2822,15 @@
                                                 fAnnounceUsingCMPCTBLOCK,
                                                 nCMPCTBLOCKVersion));
         }
+
+        if ((pfrom.nServices & NODE_AVALANCHE) && g_avalanche &&
+            gArgs.GetBoolArg("-enableavalanche", AVALANCHE_DEFAULT_ENABLED)) {
+            if (g_avalanche->sendHello(&pfrom)) {
+                LogPrint(BCLog::NET, "Send avahello to peer %d\n",
+                         pfrom.GetId());
+            }
+        }
+
         pfrom.fSuccessfullyConnected = true;
         return;
     }
@@ -3833,6 +3845,30 @@
         return;
     }
 
+    if (msg_type == NetMsgType::AVAHELLO && g_avalanche &&
+        gArgs.GetBoolArg("-enableavalanche", AVALANCHE_DEFAULT_ENABLED)) {
+        if (!pfrom.m_avalanche_state) {
+            pfrom.m_avalanche_state = std::make_unique<CNode::AvalancheState>();
+        }
+
+        CHashVerifier<CDataStream> verifier(&vRecv);
+        avalanche::Delegation &delegation = pfrom.m_avalanche_state->delegation;
+        verifier >> delegation;
+
+        avalanche::Proof proof;
+
+        avalanche::DelegationState state;
+        CPubKey pubkey;
+        if (!delegation.verify(state, proof, pubkey)) {
+            LOCK(cs_main);
+            Misbehaving(pfrom, 100, "invalid-delegation");
+            return;
+        }
+
+        std::array<uint8_t, 64> sig;
+        verifier >> sig;
+    }
+
     // Ignore avalanche requests while importing
     if (msg_type == NetMsgType::AVAPOLL && !fImporting && !fReindex &&
         g_avalanche &&
diff --git a/src/protocol.h b/src/protocol.h
--- a/src/protocol.h
+++ b/src/protocol.h
@@ -288,6 +288,10 @@
  * evenly spaced filter headers for blocks on the requested chain.
  */
 extern const char *CFCHECKPT;
+/**
+ * Contains a delegation and a signature.
+ */
+extern const char *AVAHELLO;
 /**
  * Contains an avalanche::Poll.
  * Peer should respond with "avaresponse" message.
diff --git a/src/protocol.cpp b/src/protocol.cpp
--- a/src/protocol.cpp
+++ b/src/protocol.cpp
@@ -49,6 +49,7 @@
 const char *CFHEADERS = "cfheaders";
 const char *GETCFCHECKPT = "getcfcheckpt";
 const char *CFCHECKPT = "cfcheckpt";
+const char *AVAHELLO = "avahello";
 const char *AVAPOLL = "avapoll";
 const char *AVARESPONSE = "avaresponse";
 
diff --git a/test/functional/abc_p2p_avalanche.py b/test/functional/abc_p2p_avalanche.py
--- a/test/functional/abc_p2p_avalanche.py
+++ b/test/functional/abc_p2p_avalanche.py
@@ -16,6 +16,8 @@
     CInv,
     msg_avapoll,
     msg_tcpavaresponse,
+    NODE_AVALANCHE,
+    NODE_NETWORK,
     TCPAvalancheResponse,
 )
 from test_framework.test_framework import BitcoinTestFramework
@@ -38,10 +40,27 @@
 
     def __init__(self):
         self.round = 0
+        self.avahello = None
         self.avaresponses = []
         self.avapolls = []
         super().__init__()
 
+    def peer_connect(self, *args, **kwargs):
+        create_conn = super().peer_connect(*args, **kwargs)
+
+        # Save the nonce and extra entropy so they can be reused later.
+        self.local_nonce = self.on_connection_send_msg.nNonce
+        self.local_extra_entropy = self.on_connection_send_msg.nExtraEntropy
+
+        return create_conn
+
+    def on_version(self, message):
+        super().on_version(message)
+
+        # Save the nonce and extra entropy so they can be reused later.
+        self.remote_nonce = message.nNonce
+        self.remote_extra_entropy = message.nExtraEntropy
+
     def on_avaresponse(self, message):
         with mininode_lock:
             self.avaresponses.append(message.response)
@@ -50,6 +69,11 @@
         with mininode_lock:
             self.avapolls.append(message.poll)
 
+    def on_avahello(self, message):
+        with mininode_lock:
+            assert(self.avahello is None)
+            self.avahello = message
+
     def send_avaresponse(self, round, votes, privkey):
         response = AvalancheResponse(round, 0, votes)
         sig = privkey.sign_schnorr(response.get_hash())
@@ -57,6 +81,15 @@
         msg.response = TCPAvalancheResponse(response, sig)
         self.send_message(msg)
 
+    def wait_for_avaresponse(self, timeout=5):
+        wait_until(
+            lambda: len(self.avaresponses) > 0,
+            timeout=timeout,
+            lock=mininode_lock)
+
+        with mininode_lock:
+            return self.avaresponses.pop(0)
+
     def send_poll(self, hashes):
         msg = msg_avapoll()
         msg.poll.round = self.round
@@ -65,18 +98,18 @@
             msg.poll.invs.append(CInv(2, h))
         self.send_message(msg)
 
-    def wait_for_avaresponse(self, timeout=5):
+    def get_avapoll_if_available(self):
+        with mininode_lock:
+            return self.avapolls.pop(0) if len(self.avapolls) > 0 else None
+
+    def wait_for_avahello(self, timeout=5):
         wait_until(
-            lambda: len(self.avaresponses) > 0,
+            lambda: self.avahello is not None,
             timeout=timeout,
             lock=mininode_lock)
 
         with mininode_lock:
-            return self.avaresponses.pop(0)
-
-    def get_avapoll_if_available(self):
-        with mininode_lock:
-            return self.avapolls.pop(0) if len(self.avapolls) > 0 else None
+            return self.avahello
 
 
 class AvalancheTest(BitcoinTestFramework):
@@ -95,7 +128,8 @@
         def get_quorum():
             def get_node():
                 n = TestNode()
-                node.add_p2p_connection(n)
+                node.add_p2p_connection(
+                    n, services=NODE_NETWORK | NODE_AVALANCHE)
                 n.wait_for_verack()
 
                 # Get our own node id so we can use it later.
@@ -105,9 +139,8 @@
 
             return [get_node() for _ in range(0, 16)]
 
-        quorum = get_quorum()
-
         # Pick on node from the quorum for polling.
+        quorum = get_quorum()
         poll_node = quorum[0]
 
         # Generate many block and poll for them.
@@ -288,8 +321,6 @@
         node.generate(1)
 
         tip_to_park = node.getbestblockhash()
-        self.log.info(tip_to_park)
-
         hash_to_find = int(tip_to_park, 16)
         assert(tip_to_park != fork_tip)
 
@@ -301,6 +332,21 @@
         wait_until(has_parked_new_tip, timeout=15)
         assert_equal(node.getbestblockhash(), fork_tip)
 
+        # Restart the node and rebuild the quorum
+        self.restart_node(0, self.extra_args[0] + [
+            "-avaproof={}".format(proof),
+            "-avamasterkey=cND2ZvtabDbJ1gucx9GWH6XT9kgTAqfb6cotPt5Q5CyxVDhid2EN",
+        ])
+        quorum = get_quorum()
+        poll_node = quorum[0]
+
+        # Check the avahello is consistent
+        avahello = poll_node.wait_for_avahello().hello
+
+        avakey.set(bytes.fromhex(node.getavalanchekey()))
+        assert avakey.verify_schnorr(
+            avahello.sig, avahello.get_sighash(poll_node))
+
 
 if __name__ == '__main__':
     AvalancheTest().main()
diff --git a/test/functional/test_framework/messages.py b/test/functional/test_framework/messages.py
--- a/test/functional/test_framework/messages.py
+++ b/test/functional/test_framework/messages.py
@@ -870,6 +870,86 @@
             repr(self.response), self.sig)
 
 
+class AvalancheDelegationLevel:
+    __slots__ = ("pubkey", "sig")
+
+    def __init__(self, pubkey="", sig=b"\0" * 64):
+        self.pubkey = pubkey
+        self.sig = sig
+
+    def deserialize(self, f):
+        self.pubkey = deser_string(f)
+        self.sig = f.read(64)
+
+    def serialize(self):
+        r = b""
+        r += ser_string(self.pubkey)
+        r += self.sig
+        return r
+
+    def __repr__(self):
+        return "AvalancheDelegationLevel(pubkey={}, sig={})".format(
+            self.pubkey.hex(), self.sig)
+
+
+class AvalancheDelegation:
+    __slots__ = ("proofid", "levels")
+
+    def __init__(self, proofid=0, levels=None):
+        self.proofid = proofid
+        self.levels = levels
+
+    def deserialize(self, f):
+        self.proofid = deser_uint256(f)
+        self.levels = deser_vector(f, AvalancheDelegationLevel)
+
+    def serialize(self):
+        r = b""
+        r += ser_uint256(self.proofid)
+        r += ser_vector(self.levels)
+        return r
+
+    def __repr__(self):
+        return "AvalancheDelegation(proofid={:064x}, levels={})".format(
+            self.proofid, repr(self.levels))
+
+    def getid(self):
+        h = ser_uint256(self.proofid)
+        for level in self.levels:
+            h = hash256(h + ser_string(level.pubkey))
+        return h
+
+
+class AvalancheHello():
+    __slots__ = ("delegation", "sig")
+
+    def __init__(self, delegation=AvalancheDelegation(), sig=b"\0" * 64):
+        self.delegation = delegation
+        self.sig = sig
+
+    def deserialize(self, f):
+        self.delegation.deserialize(f)
+        self.sig = f.read(64)
+
+    def serialize(self):
+        r = b""
+        r += self.delegation.serialize()
+        r += self.sig
+        return r
+
+    def __repr__(self):
+        return "AvalancheHello(delegation={}, sig={})".format(
+            repr(self.delegation), self.sig)
+
+    def get_sighash(self, node):
+        b = self.delegation.getid()
+        b += struct.pack("<Q", node.remote_nonce)
+        b += struct.pack("<Q", node.local_nonce)
+        b += struct.pack("<Q", node.remote_extra_entropy)
+        b += struct.pack("<Q", node.local_extra_entropy)
+        return hash256(b)
+
+
 class CPartialMerkleTree:
     __slots__ = ("nTransactions", "vBits", "vHash")
 
@@ -1687,3 +1767,22 @@
 
     def __repr__(self):
         return "msg_tcpavaresponse(response={})".format(repr(self.response))
+
+
+class msg_avahello():
+    __slots__ = ("hello",)
+    msgtype = b"avahello"
+
+    def __init__(self):
+        self.hello = AvalancheHello()
+
+    def deserialize(self, f):
+        self.hello.deserialize(f)
+
+    def serialize(self):
+        r = b""
+        r += self.hello.serialize()
+        return r
+
+    def __repr__(self):
+        return "msg_avahello(response={})".format(repr(self.hello))
diff --git a/test/functional/test_framework/mininode.py b/test/functional/test_framework/mininode.py
--- a/test/functional/test_framework/mininode.py
+++ b/test/functional/test_framework/mininode.py
@@ -27,6 +27,7 @@
     msg_addr,
     msg_avapoll,
     msg_tcpavaresponse,
+    msg_avahello,
     msg_block,
     MSG_BLOCK,
     msg_blocktxn,
@@ -68,6 +69,7 @@
     b"addr": msg_addr,
     b"avapoll": msg_avapoll,
     b"avaresponse": msg_tcpavaresponse,
+    b"avahello": msg_avahello,
     b"block": msg_block,
     b"blocktxn": msg_blocktxn,
     b"cfcheckpt": msg_cfcheckpt,
@@ -334,6 +336,7 @@
             vt.addrTo.port = self.dstport
             vt.addrFrom.ip = "0.0.0.0"
             vt.addrFrom.port = 0
+
             # Will be sent soon after connection_made
             self.on_connection_send_msg = vt
 
@@ -372,6 +375,8 @@
 
     def on_avaresponse(self, message): pass
 
+    def on_avahello(self, message): pass
+
     def on_block(self, message): pass
 
     def on_blocktxn(self, message): pass