diff --git a/src/net.h b/src/net.h
--- a/src/net.h
+++ b/src/net.h
@@ -998,6 +998,7 @@
     std::unique_ptr<TxRelay> m_tx_relay;
 
     struct ProofRelay {
+        mutable RecursiveMutex cs_filter;
         mutable RecursiveMutex cs_proof_inventory;
         CRollingBloomFilter filterInventoryKnown GUARDED_BY(cs_proof_inventory){
             50000, 0.000001};
diff --git a/src/net_processing.h b/src/net_processing.h
--- a/src/net_processing.h
+++ b/src/net_processing.h
@@ -215,4 +215,7 @@
 /** Relay transaction to every node */
 void RelayTransaction(const TxId &txid, const CConnman &connman);
 
+/** Relay proof to every node */
+void RelayProof(const avalanche::ProofId &proofid, const CConnman &connman);
+
 #endif // BITCOIN_NET_PROCESSING_H
diff --git a/src/net_processing.cpp b/src/net_processing.cpp
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -1763,6 +1763,11 @@
         [&txid](CNode *pnode) { pnode->PushTxInventory(txid); });
 }
 
+void RelayProof(const avalanche::ProofId &proofid, const CConnman &connman) {
+    connman.ForEachNode(
+        [&proofid](CNode *pnode) { pnode->PushProofInventory(proofid); });
+}
+
 static void RelayAddress(const CAddress &addr, bool fReachable,
                          const CConnman &connman) {
     // Limited relaying of addresses outside our network(s)
@@ -4017,12 +4022,16 @@
 
         pfrom.AddKnownProof(proof.getId());
 
-        if (!g_avalanche->addProof(std::move(proof)) &&
-            !g_avalanche->getProof(proof.getId())) {
+        if (g_avalanche->addProof(std::move(proof))) {
+            // It was successfuly verified and we didn't already have it
+            RelayProof(proof.getId(), m_connman);
+        } else if (!g_avalanche->getProof(proof.getId())) {
             // We didn't add it, and it is not because we already have it.
             // It must be bad.
             Misbehaving(pfrom, 100, "invalid-proof");
         }
+        // Else we already had it, and there is nothing to do
+
         return;
     }
 
@@ -5350,6 +5359,80 @@
                     }
                 }
             }
+
+            // Send avaproof inventories
+            if (pto->m_proof_relay != nullptr) {
+                LOCK(pto->m_proof_relay->cs_proof_inventory);
+                // Check whether periodic sends should happen
+                bool fSendTrickle = pto->HasPermission(PF_NOBAN);
+                if (pto->m_proof_relay->nNextInvSend < current_time) {
+                    fSendTrickle = true;
+                    if (pto->IsInboundConn()) {
+                        pto->m_proof_relay->nNextInvSend =
+                            std::chrono::microseconds{
+                                m_connman.PoissonNextSendInbound(
+                                    nNow, INVENTORY_BROADCAST_INTERVAL)};
+                    } else {
+                        // Skip delay for outbound peers, as there is less
+                        // privacy concern for them.
+                        pto->m_tx_relay->nNextInvSend = current_time;
+                    }
+                }
+
+                // Determine proofs to relay
+                if (fSendTrickle) {
+                    // Produce a vector with all candidates for sending
+                    std::vector<avalanche::ProofId> vInvProof;
+                    vInvProof.reserve(
+                        pto->m_proof_relay->setInventoryProofsToSend.size());
+                    for (auto &it :
+                         pto->m_proof_relay->setInventoryProofsToSend) {
+                        vInvProof.push_back(it);
+                    }
+
+                    // Topologically sort the inventory we send for privacy
+                    // reasons. A heap is used so that not
+                    // all items need sorting if only a few are being sent.
+                    std::make_heap(vInvProof.begin(), vInvProof.end());
+                    // No reason to drain out at many times the network's
+                    // capacity, especially since we have many peers and some
+                    // will draw much shorter delays.
+                    unsigned int nRelayedProofs = 0;
+                    LOCK(pto->m_proof_relay->cs_filter);
+                    while (!vInvProof.empty() &&
+                           nRelayedProofs < INVENTORY_BROADCAST_MAX_PER_MB *
+                                                config.GetMaxBlockSize() /
+                                                1000000) {
+                        // Fetch the top element from the heap
+                        std::pop_heap(vInvProof.begin(), vInvProof.end());
+                        const avalanche::ProofId proofid = vInvProof.back();
+                        vInvProof.pop_back();
+                        // Remove it from the to-be-sent set
+                        pto->m_proof_relay->setInventoryProofsToSend.erase(
+                            proofid);
+                        // Check if not in the filter already
+                        if (pto->m_proof_relay->filterInventoryKnown.contains(
+                                proofid)) {
+                            continue;
+                        }
+                        // Not in the set of valid or orphan proofs anymore?
+                        // Don't bother sending it.
+                        avalanche::Proof proof =
+                            *g_avalanche->getProof(proofid);
+
+                        // Send
+                        vInv.push_back(CInv(MSG_AVA_PROOF, proofid));
+                        nRelayedProofs++;
+                        if (vInv.size() == MAX_INV_SZ) {
+                            m_connman.PushMessage(
+                                pto, msgMaker.Make(NetMsgType::INV, vInv));
+                            vInv.clear();
+                        }
+                        pto->m_proof_relay->filterInventoryKnown.insert(
+                            proofid);
+                    }
+                }
+            }
         }
         if (!vInv.empty()) {
             m_connman.PushMessage(pto, msgMaker.Make(NetMsgType::INV, vInv));