diff --git a/src/avalanche/delegation.h b/src/avalanche/delegation.h
--- a/src/avalanche/delegation.h
+++ b/src/avalanche/delegation.h
@@ -49,6 +49,15 @@
         SER_READ(obj, obj.dgid = obj.computeDelegationId());
     }
 
+    /**
+     * Verify the delegation: check all the signatures at
+     * each level.
+     *
+     * @param[out] state Verification state of the delegation.
+     * @param[in] proof Avalanche proof corresponding to this delegation.
+     * @param[out] auth pubkey for the last level of the delegation.
+     * @return true if the verification is successful, else false
+     */
     bool verify(DelegationState &state, const Proof &proof,
                 CPubKey &auth) const;
 };
diff --git a/src/net.h b/src/net.h
--- a/src/net.h
+++ b/src/net.h
@@ -998,6 +998,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
@@ -3128,6 +3128,8 @@
         pfrom.vRecvGetData.insert(pfrom.vRecvGetData.end(), vInv.begin(),
                                   vInv.end());
         ProcessGetData(config, pfrom, m_connman, m_mempool, interruptMsgProc);
+        // TODO: implement MSG_AVALANCHE_PROOF: send a proof in an AVAPROOF
+        // message
         return;
     }
 
@@ -3954,12 +3956,29 @@
             pfrom.m_avalanche_state = std::make_unique<CNode::AvalancheState>();
         }
 
+        // Store the delegation and signature for later verification.
         CHashVerifier<CDataStream> verifier(&vRecv);
         avalanche::Delegation &delegation = pfrom.m_avalanche_state->delegation;
         verifier >> delegation;
 
+        SchnorrSig &sig = pfrom.m_avalanche_state->sig;
+        verifier >> sig;
+
+        // Ask for the proof.
+        std::vector<CInv> vGetData;
+        vGetData.emplace_back(
+            CInv(MSG_AVALANCHE_PROOF, delegation.getProofId()));
+        m_connman.PushMessage(&pfrom,
+                              msgMaker.Make(NetMsgType::GETDATA, vGetData));
+    }
+
+    if (msg_type == NetMsgType::AVAPROOF && g_avalanche) {
+        // Read the proof.
         avalanche::Proof proof;
+        vRecv >> proof;
 
+        // Verify the delegation is internally consistent.
+        avalanche::Delegation &delegation = pfrom.m_avalanche_state->delegation;
         avalanche::DelegationState state;
         CPubKey pubkey;
         if (!delegation.verify(state, proof, pubkey)) {
@@ -3967,8 +3986,32 @@
             return;
         }
 
-        SchnorrSig sig;
-        verifier >> sig;
+        // Use the delegated pubkey to verify the signature received
+        // in the avahello message.
+        SchnorrSig &sig = pfrom.m_avalanche_state->sig;
+        CHashWriter hasher(SER_GETHASH, 0);
+        hasher << delegation.getId();
+        hasher << pfrom.nRemoteHostNonce;
+        hasher << pfrom.GetLocalNonce();
+        hasher << pfrom.nRemoteExtraEntropy;
+        hasher << pfrom.GetLocalExtraEntropy();
+        const uint256 hash = hasher.GetHash();
+
+        bool success;
+        success = pubkey.VerifySchnorr(hash, sig);
+        if (!success) {
+            Misbehaving(pfrom, 100, "invalid-avalanche-handshake");
+            return;
+        }
+
+        // Add the node the avalanche peers.
+        success = g_avalanche->addNode(pfrom.GetId(), proof, delegation);
+        if (success) {
+            LogPrint(BCLog::NET, "added avalanche node=%d\n", pfrom.GetId());
+        } else {
+            LogPrint(BCLog::NET, "failed to add avalanche node=%d\n",
+                     pfrom.GetId());
+        }
     }
 
     // Ignore avalanche requests while importing
diff --git a/src/protocol.h b/src/protocol.h
--- a/src/protocol.h
+++ b/src/protocol.h
@@ -310,6 +310,12 @@
  * Sent in response to a "avapoll" message.
  */
 extern const char *AVARESPONSE;
+/**
+ * Contains an avalanche::Proof.
+ * Sent in response to a "getdata" message with inventory type
+ * MSG_AVALANCHE_PROOF.
+ */
+extern const char *AVAPROOF;
 
 /**
  * Indicate if the message is used to transmit the content of a block.
@@ -495,6 +501,7 @@
     MSG_FILTERED_BLOCK = 3,
     //! Defined in BIP152
     MSG_CMPCT_BLOCK = 4,
+    MSG_AVALANCHE_PROOF = 5,
 };
 
 /**