diff --git a/src/net.h b/src/net.h
--- a/src/net.h
+++ b/src/net.h
@@ -996,6 +996,15 @@
     // m_tx_relay == nullptr if we're not relaying transactions with this peer
     std::unique_ptr<TxRelay> m_tx_relay;
 
+    struct ProofRelay {
+        mutable RecursiveMutex cs_proof_inventory;
+        std::set<avalanche::ProofId>
+            setInventoryProofToSend GUARDED_BY(cs_proof_inventory);
+    };
+
+    // m_proof_relay == nullptr if we're not relaying proofs with this peer
+    std::unique_ptr<ProofRelay> m_proof_relay;
+
     struct AvalancheState {
         AvalancheState() {}
 
@@ -1161,6 +1170,15 @@
         }
     }
 
+    void PushProofInventory(const avalanche::ProofId &proofid) {
+        if (m_proof_relay == nullptr) {
+            m_proof_relay = std::make_unique<ProofRelay>();
+        }
+
+        WITH_LOCK(m_proof_relay->cs_proof_inventory,
+                  m_proof_relay->setInventoryProofToSend.insert(proofid));
+    }
+
     void CloseSocketDisconnect();
 
     void copyStats(CNodeStats &stats, const std::vector<bool> &m_asmap);
diff --git a/src/net_processing.cpp b/src/net_processing.cpp
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -2978,9 +2978,14 @@
                                                 nCMPCTBLOCKVersion));
         }
 
-        if ((pfrom.nServices & NODE_AVALANCHE) && g_avalanche &&
+        if (g_avalanche &&
             gArgs.GetBoolArg("-enableavalanche", AVALANCHE_DEFAULT_ENABLED)) {
-            if (g_avalanche->sendHello(&pfrom)) {
+            for (const avalanche::Peer &peer : g_avalanche->getPeers()) {
+                pfrom.PushProofInventory(peer.proof.getId());
+            }
+
+            if ((pfrom.nServices & NODE_AVALANCHE) &&
+                g_avalanche->sendHello(&pfrom)) {
                 LogPrint(BCLog::NET, "Send avahello to peer %d\n",
                          pfrom.GetId());
             }
@@ -5359,7 +5364,19 @@
                     }
                 }
             }
+
+            // Add proofs to inventory
+            if (pto->m_proof_relay != nullptr) {
+                LOCK(pto->m_proof_relay->cs_proof_inventory);
+                auto it = pto->m_proof_relay->setInventoryProofToSend.begin();
+                while (it !=
+                       pto->m_proof_relay->setInventoryProofToSend.end()) {
+                    addInvAndMaybeFlush(MSG_AVA_PROOF, *it);
+                    it = pto->m_proof_relay->setInventoryProofToSend.erase(it);
+                }
+            }
         }
+
         if (!vInv.empty()) {
             m_connman.PushMessage(pto, msgMaker.Make(NetMsgType::INV, vInv));
         }
diff --git a/test/functional/abc_p2p_proof_inventory.py b/test/functional/abc_p2p_proof_inventory.py
new file mode 100644
--- /dev/null
+++ b/test/functional/abc_p2p_proof_inventory.py
@@ -0,0 +1,97 @@
+#!/usr/bin/env python3
+# Copyright (c) 2021 The Bitcoin developers
+# Distributed under the MIT software license, see the accompanying
+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
+"""
+Test proof inventory relaying
+"""
+
+from test_framework.avatools import (
+    create_coinbase_stakes,
+    get_proof_ids,
+)
+from test_framework.key import ECKey, bytes_to_wif
+from test_framework.messages import (
+    AvalancheProof,
+    FromHex,
+)
+from test_framework.mininode import (
+    P2PInterface,
+    mininode_lock,
+)
+from test_framework.test_framework import BitcoinTestFramework
+from test_framework.util import (
+    connect_nodes,
+    wait_until,
+)
+
+
+class ProofInventoryTest(BitcoinTestFramework):
+    def set_test_params(self):
+        self.num_nodes = 1
+        self.extra_args = [['-enableavalanche=1',
+                            '-avacooldown=0']] * self.num_nodes
+
+    def gen_proof(self, node):
+        blockhashes = node.generate(10)
+
+        privkey = ECKey()
+        privkey.generate()
+        pubkey = privkey.get_pubkey()
+
+        stakes = create_coinbase_stakes(
+            node, blockhashes, node.get_deterministic_priv_key().key)
+        proof_hex = node.buildavalancheproof(
+            42, 2000000000, pubkey.get_bytes().hex(), stakes)
+
+        return bytes_to_wif(privkey.get_bytes()), FromHex(
+            AvalancheProof(), proof_hex)
+
+    def restart_nodes_with_proof(self, nodes):
+        proofids = set()
+        for i, node in enumerate(nodes):
+            privkey, proof = self.gen_proof(node)
+            proofids.add(proof.proofid)
+
+            self.restart_node(node.index, self.extra_args[node.index] + [
+                "-avaproof={}".format(proof.serialize().hex()),
+                "-avamasterkey={}".format(privkey)
+            ])
+
+            # Connect a block to make the proof be added to our pool
+            node.generate(1)
+            self.log.info(
+                "Wait for node{} to have its own proof in its pool".format(
+                    node.index))
+            wait_until(
+                lambda: proof.proofid in get_proof_ids(node), timeout=5)
+
+            [connect_nodes(node, n) for n in nodes[:i]]
+
+        return proofids
+
+    def test_send_proof_inv(self):
+        self.log.info("Test that we send our proofs to our peers")
+
+        node = self.nodes[0]
+
+        # Restart our node with a valid -avaproof set.
+        # This is the only proof that this node knows.
+        proofid = self.restart_nodes_with_proof([node]).pop()
+
+        for i in range(10):
+            node.add_p2p_connection(P2PInterface())
+
+        def proof_inv_found(peer):
+            with mininode_lock:
+                return peer.last_message.get(
+                    "inv") and peer.last_message["inv"].inv[-1].hash == proofid
+
+        wait_until(lambda: all(proof_inv_found(i) for i in node.p2ps))
+
+    def run_test(self):
+        self.test_send_proof_inv()
+
+
+if __name__ == '__main__':
+    ProofInventoryTest().main()
diff --git a/test/functional/test_framework/avatools.py b/test/functional/test_framework/avatools.py
--- a/test/functional/test_framework/avatools.py
+++ b/test/functional/test_framework/avatools.py
@@ -7,6 +7,7 @@
 from typing import Any, Optional, List, Dict
 
 from .messages import (
+    AvalancheProof,
     CTransaction,
     FromHex,
     ToHex
@@ -114,3 +115,8 @@
         })
 
     return stakes
+
+
+def get_proof_ids(node):
+    return [FromHex(AvalancheProof(), peer['proof']
+                    ).proofid for peer in node.getavalanchepeerinfo()]