diff --git a/src/avalanche/processor.h b/src/avalanche/processor.h
--- a/src/avalanche/processor.h
+++ b/src/avalanche/processor.h
@@ -41,6 +41,11 @@
  */
 static constexpr bool AVALANCHE_DEFAULT_ENABLED = false;
 
+/**
+ * Is avalanche peer discovery enabled.
+ */
+static constexpr bool AVALANCHE_DEFAULT_SHARE_PROOFS = false;
+
 /**
  * Finalization score.
  */
diff --git a/src/init.cpp b/src/init.cpp
--- a/src/init.cpp
+++ b/src/init.cpp
@@ -1222,6 +1222,13 @@
         "-enableavalanche",
         strprintf("Enable avalanche (default: %u)", AVALANCHE_DEFAULT_ENABLED),
         ArgsManager::ALLOW_ANY, OptionsCategory::AVALANCHE);
+    argsman.AddArg(
+        "-exchangeavaproofs",
+        strprintf("Exchange avalanche proofs when meeting an avalanche peer."
+                  "If disabled, peers can only be added via the "
+                  "addavalanchenode RPC command (default: %u)",
+                  AVALANCHE_DEFAULT_SHARE_PROOFS),
+        ArgsManager::ALLOW_ANY, OptionsCategory::AVALANCHE);
     argsman.AddArg(
         "-avacooldown",
         strprintf("Mandatory cooldown between two avapoll (default: %u)",
diff --git a/src/net.h b/src/net.h
--- a/src/net.h
+++ b/src/net.h
@@ -1000,6 +1000,7 @@
         AvalancheState() {}
 
         avalanche::Delegation delegation;
+        SchnorrSig sig;
     };
 
     // m_avalanche_state == nullptr if we're not using avalanche with this peer
diff --git a/src/net_processing.cpp b/src/net_processing.cpp
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -2105,6 +2105,33 @@
         }
     }
 
+    // Process the avalanche proof items.
+    while (it != pfrom.vRecvGetData.end() && it->type == MSG_AVA_PROOF) {
+        if (interruptMsgProc) {
+            return;
+        }
+
+        const CInv &inv = *it++;
+
+        if (!g_avalanche ||
+            !gArgs.GetBoolArg("-enableavalanche", AVALANCHE_DEFAULT_ENABLED) ||
+            !gArgs.IsArgSet("-avaproof") ||
+            !gArgs.GetBoolArg("-exchangeavaproofs",
+                              AVALANCHE_DEFAULT_SHARE_PROOFS)) {
+            vNotFound.push_back(inv);
+        } else {
+            const avalanche::ProofId proofid{inv.hash};
+            const avalanche::Proof proof = g_avalanche->getProof();
+            // For now, we respond only to requests for our local proof.
+            if (proofid == proof.getId()) {
+                connman.PushMessage(&pfrom,
+                                    msgMaker.Make(NetMsgType::AVAPROOF, proof));
+            } else {
+                vNotFound.push_back(inv);
+            }
+        }
+    }
+
     // Only process one BLOCK item per call, since they're uncommon and can be
     // expensive to process.
     if (it != pfrom.vRecvGetData.end() && !pfrom.fPauseSend) {
@@ -2700,7 +2727,8 @@
 bool IsAvalancheMessageType(const std::string &msg_type) {
     return msg_type == NetMsgType::AVAHELLO ||
            msg_type == NetMsgType::AVAPOLL ||
-           msg_type == NetMsgType::AVARESPONSE;
+           msg_type == NetMsgType::AVARESPONSE ||
+           msg_type == NetMsgType::AVAPROOF;
 }
 
 void PeerManager::ProcessMessage(const Config &config, CNode &pfrom,
@@ -4023,10 +4051,45 @@
         }
 
         CHashVerifier<CDataStream> verifier(&vRecv);
-        avalanche::Delegation &delegation = pfrom.m_avalanche_state->delegation;
-        verifier >> delegation;
+        verifier >> pfrom.m_avalanche_state->delegation;
+        verifier >> pfrom.m_avalanche_state->sig;
+
+        // Request the proof (TODO: do it only if we don't already have it).
+        if (!gArgs.GetBoolArg("-exchangeavaproofs",
+                              AVALANCHE_DEFAULT_SHARE_PROOFS)) {
+            return;
+        }
+        std::vector<CInv> vGetData;
+        vGetData.emplace_back(CInv(
+            MSG_AVA_PROOF, pfrom.m_avalanche_state->delegation.getProofId()));
+        m_connman.PushMessage(&pfrom,
+                              msgMaker.Make(NetMsgType::GETDATA, vGetData));
+    }
+
+    if (msg_type == NetMsgType::AVAPROOF) {
+        if (!gArgs.GetBoolArg("-exchangeavaproofs",
+                              AVALANCHE_DEFAULT_SHARE_PROOFS)) {
+            return;
+        }
+        // If the sender hasn't shared his delegation, we currently can't
+        // add his proof.
+        if (!pfrom.m_avalanche_state) {
+            return;
+        }
 
         avalanche::Proof proof;
+        vRecv >> proof;
+
+        // Get the delegated pubkey.
+        const avalanche::Delegation &delegation =
+            pfrom.m_avalanche_state->delegation;
+
+        if (proof.getId() != delegation.getProofId()) {
+            // For now we don't support reception of proofs that do not
+            // belong to the sender.
+            return;
+        }
+
         avalanche::DelegationState state;
         CPubKey pubkey;
         if (!delegation.verify(state, proof, pubkey)) {
@@ -4034,8 +4097,18 @@
             return;
         }
 
-        SchnorrSig sig;
-        verifier >> sig;
+        // Use the delegated pubkey to verify the AVAHELLO signature.
+        const uint256 hash = g_avalanche->buildRemoteSighash(&pfrom);
+        if (!pubkey.VerifySchnorr(hash, pfrom.m_avalanche_state->sig)) {
+            Misbehaving(pfrom, 100, "invalid-avalanche-signature");
+            return;
+        }
+
+        // Add the node to the avalanche peers.
+        if (g_avalanche->addNode(pfrom.GetId(), proof, delegation)) {
+            LogPrint(BCLog::NET, "added avalanche node=%d\n", pfrom.GetId());
+        }
+        return;
     }
 
     if (msg_type == NetMsgType::AVAPOLL) {
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
@@ -4,18 +4,29 @@
 # file COPYING or http://www.opensource.org/licenses/mit-license.php.
 """Test the resolution of forks via avalanche."""
 import random
+import struct
+from typing import List
 
 from test_framework.avatools import create_coinbase_stakes
 from test_framework.key import (
+    bytes_to_wif,
     ECKey,
     ECPubKey,
 )
 from test_framework.mininode import P2PInterface, mininode_lock
 from test_framework.messages import (
+    AvalancheDelegation,
+    AvalancheProof,
     AvalancheResponse,
     AvalancheVote,
     CInv,
+    FromHex,
+    hash256,
+    MSG_AVA_PROOF,
     msg_avapoll,
+    msg_avahello,
+    msg_avaproof,
+    msg_getdata,
     msg_tcpavaresponse,
     NODE_AVALANCHE,
     NODE_NETWORK,
@@ -45,6 +56,7 @@
         self.avahello = None
         self.avaresponses = []
         self.avapolls = []
+        self.avaproof = None
         super().__init__()
 
     def peer_connect(self, *args, **kwargs):
@@ -110,6 +122,42 @@
         with mininode_lock:
             return self.avahello
 
+    def send_avahello(self, delegation_hex: str, privkey: ECKey):
+        msg = msg_avahello()
+        msg.hello.delegation = FromHex(AvalancheDelegation(), delegation_hex)
+
+        b = msg.hello.delegation.getid()
+        b += struct.pack("<Q", self.local_nonce)
+        b += struct.pack("<Q", self.remote_nonce)
+        b += struct.pack("<Q", self.local_extra_entropy)
+        b += struct.pack("<Q", self.remote_extra_entropy)
+        msg.hello.sig = privkey.sign_schnorr(hash256(b))
+
+        self.send_message(msg)
+
+    def send_getdata(self, inv: List[CInv]):
+        msg = msg_getdata()
+        msg.inv = inv
+        self.send_message(msg)
+
+    def on_avaproof(self, message):
+        assert(self.avaproof is None)
+        self.avaproof = message
+
+    def wait_for_avaproof(self, timeout=10):
+        wait_until(
+            lambda: self.avaproof is not None,
+            timeout=timeout,
+            lock=mininode_lock)
+
+        with mininode_lock:
+            return self.avaproof
+
+    def send_avaproof(self, proof_hex):
+        msg_proof = msg_avaproof()
+        msg_proof.proof = FromHex(AvalancheProof(), proof_hex)
+        self.send_message(msg_proof)
+
 
 class AvalancheTest(BitcoinTestFramework):
     def set_test_params(self):
@@ -345,21 +393,57 @@
         self.restart_node(0, self.extra_args[0] + [
             "-avaproof={}".format(proof),
             "-avamasterkey=cND2ZvtabDbJ1gucx9GWH6XT9kgTAqfb6cotPt5Q5CyxVDhid2EN",
+            "-exchangeavaproofs=1",
         ])
 
         assert_equal(
             int(node.getnetworkinfo()['localservices'], 16) & NODE_AVALANCHE,
             NODE_AVALANCHE)
 
-        self.log.info("Test the avahello signature")
-        quorum = get_quorum()
-        poll_node = quorum[0]
+        self.log.info("Test the avalanche handshake (node -> P2PInterface)")
+        interface = get_node()
 
-        avahello = poll_node.wait_for_avahello().hello
+        avahello = interface.wait_for_avahello().hello
 
         avakey.set(bytes.fromhex(node.getavalanchekey()))
         assert avakey.verify_schnorr(
-            avahello.sig, avahello.get_sighash(poll_node))
+            avahello.sig, avahello.get_sighash(interface))
+
+        self.log.info("Ask for the proof")
+        interface.send_getdata(
+            [CInv(MSG_AVA_PROOF, avahello.delegation.proofid)])
+        avaproof = interface.wait_for_avaproof()
+        assert avaproof.proof.serialize().hex() == proof
+
+        self.log.info("Test the avalanche handshake (P2PInterface -> node)")
+        # Create a different valid proof
+        stakes = create_coinbase_stakes(node, [blockhashes[1]], addrkey0.key)
+        interface_proof_hex = node.buildavalancheproof(
+            proof_sequence, proof_expiration, pubkey.get_bytes().hex(),
+            stakes)
+        # delegate
+        delegated_privkey = ECKey()
+        delegated_privkey.generate()
+        interface_delegation_hex = node.delegateavalancheproof(
+            interface_proof_hex,
+            bytes_to_wif(privkey.get_bytes()),
+            delegated_privkey.get_pubkey().get_bytes().hex(),
+            None
+        )
+
+        interface.send_avahello(interface_delegation_hex, delegated_privkey)
+        expected_proofid = FromHex(
+            AvalancheProof(),
+            interface_proof_hex).proofid
+        interface.wait_for_getdata([expected_proofid])
+
+        self.log.info("Test that node adds an avalanche peer")
+        interface.send_avaproof(interface_proof_hex)
+
+        wait_until(
+            lambda: len(node.getavalanchepeerinfo()) > 0,
+            timeout=5,
+            lock=mininode_lock)
 
 
 if __name__ == '__main__':
diff --git a/test/functional/p2p_invalid_messages.py b/test/functional/p2p_invalid_messages.py
--- a/test/functional/p2p_invalid_messages.py
+++ b/test/functional/p2p_invalid_messages.py
@@ -12,6 +12,7 @@
     CInv,
     msg_avahello,
     msg_avapoll,
+    msg_avaproof,
     msg_avaresponse,
     msg_getdata,
     msg_headers,
@@ -372,6 +373,10 @@
                 ['Misbehaving', 'peer=9 (40 -> 60): unsolicited-avaresponse']):
             msg = msg_avaresponse()
             conn.send_and_ping(msg)
+        with self.nodes[0].assert_debug_log(
+                ['Misbehaving', 'peer=9 (60 -> 80): unsolicited-avaproof']):
+            msg = msg_avaproof()
+            conn.send_and_ping(msg)
         self.nodes[0].disconnect_p2ps()
 
     def _tweak_msg_data_size(self, message, wrong_size):