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
@@ -288,12 +288,12 @@
         privkey = ECKey()
         privkey.set(bytes.fromhex(
             "12b004fff7f4b69ef8650e767f18f11ede158148b425660723b9f9a66e61f747"), True)
-        pubkey = privkey.get_pubkey()
+        proof_master = privkey.get_pubkey().get_bytes().hex()
 
         proof_sequence = 11
         proof_expiration = 12
         proof = node.buildavalancheproof(
-            proof_sequence, proof_expiration, pubkey.get_bytes().hex(),
+            proof_sequence, proof_expiration, proof_master,
             [{
                 'txid': coinbases[0]['txid'],
                 'vout': coinbases[0]['n'],
@@ -306,7 +306,7 @@
         # Activate the quorum.
         for n in quorum:
             success = node.addavalanchenode(
-                n.nodeid, pubkey.get_bytes().hex(), proof)
+                n.nodeid, proof_master, proof)
             assert success is True
 
         self.log.info("Testing getavalanchepeerinfo...")
@@ -320,7 +320,7 @@
                      list(range(1, QUORUM_NODE_COUNT + 1)))
         assert_equal(avapeerinfo[0]["sequence"], proof_sequence)
         assert_equal(avapeerinfo[0]["expiration"], proof_expiration)
-        assert_equal(avapeerinfo[0]["master"], pubkey.get_bytes().hex())
+        assert_equal(avapeerinfo[0]["master"], proof_master)
         assert_equal(avapeerinfo[0]["proof"], proof)
         assert_equal(len(avapeerinfo[0]["stakes"]), 1)
         assert_equal(avapeerinfo[0]["stakes"][0]["txid"], coinbases[0]['txid'])
@@ -411,24 +411,25 @@
         poll_node = quorum[0]
 
         # Check the handshake sequence
-        self.log.info("Receive AVAHELLO, request the corresponding proof")
+        self.log.info("Test avahello sequence node -> poll_node")
         avahello = poll_node.wait_for_avahello().hello
-
         avakey.set(bytes.fromhex(node.getavalanchekey()))
         assert avakey.verify_schnorr(
             avahello.sig, avahello.get_sighash(poll_node))
 
         poll_node.send_getdata([CInv(MSG_AVALANCHE_PROOF,
                                      avahello.delegation.proofid)])
-        poll_node.wait_for_avaproof()
-        # TODO: deserialize proof and check it in more details
+        avaproof = poll_node.wait_for_avaproof().proof
+        assert_equal(proof, avaproof.serialize().hex())
+        assert_equal(avaproof.proofid, avahello.delegation.proofid)
 
         self.log.info(
-            "Send an AVAHELLO to the node, check that it ask for our prooof")
+            "Test avahello sequence poll_node -> node")
+        # This is testing only the first couple of steps (for now)
+        # TODO: make a proper delegation and a valid signature for avahello,
+        #       reply with a valid avaproof, test that the node adds us.
         poll_node.send_avahello()
         poll_node.wait_for_getdata([DUMMY_PROOFID])
-        # TODO: reply with a new AVAPROOF message and verify that poll node is
-        # added to node's avalanche peers
 
         # Check the maximum number of stakes policy
         blocks = node.generatetoaddress(AVALANCHE_MAX_PROOF_STAKES + 1,
@@ -443,17 +444,17 @@
                                     addrkey0.key)
         good_proof = node.buildavalancheproof(
             proof_sequence, proof_expiration,
-            pubkey.get_bytes().hex(), maximum_stakes)
+            proof_master, maximum_stakes)
         node.addavalanchenode(
-            get_node().nodeid, pubkey.get_bytes().hex(), good_proof)
+            get_node().nodeid, proof_master, good_proof)
 
         self.log.info("A proof using too many stakes should be rejected...")
         bad_proof = node.buildavalancheproof(
             proof_sequence, proof_expiration,
-            pubkey.get_bytes().hex(), too_many_stakes)
+            proof_master, too_many_stakes)
         assert_raises_rpc_error(-32602, "Avalanche proof has too many UTXOs",
                                 node.addavalanchenode,
-                                get_node().nodeid, pubkey.get_bytes().hex(),
+                                get_node().nodeid, proof_master,
                                 bad_proof)
 
 
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
@@ -854,23 +854,115 @@
             self.round, repr(self.invs))
 
 
-# TODO: implement the Proof with all its attributes
-class AvalancheProof:
-    __slots__ = ("blob")
+class AvalancheStake:
+    def __init__(self, utxo=None, amount=0, height=0,
+                 pubkey=b"", is_coinbase=False):
+        self.utxo: COutPoint = utxo or COutPoint()
+        self.amount: int = amount
+        """Amount in satoshis (int64)"""
+        self.height: int = height
+        """Block height containing this utxo (uint32)"""
+        self.pubkey: bytes = pubkey
+        """Public key"""
+
+        self.is_coinbase: bool = is_coinbase
+
+    def deserialize(self, f):
+        self.utxo = COutPoint()
+        self.utxo.deserialize(f)
+        self.amount = struct.unpack("<q", f.read(8))[0]
+        height_ser = struct.unpack("<I", f.read(4))[0]
+        self.is_coinbase = bool(height_ser & 1)
+        self.height = height_ser >> 1
+        self.pubkey = deser_string(f)
+
+    def serialize(self) -> bytes:
+        r = self.utxo.serialize()
+        height_ser = self.height << 1 | int(self.is_coinbase)
+        r += struct.pack('<q', self.amount)
+        r += struct.pack('<I', height_ser)
+        r += ser_compact_size(len(self.pubkey))
+        r += self.pubkey
+        return r
+
+    def get_hash(self, proofid) -> bytes:
+        """Return the bitcoin hash of the concatenation of proofid
+        and the serialized stake."""
+        return hash256(proofid + self.serialize())
+
+    def __repr__(self):
+        return f"AvalancheStake(utxo={self.utxo}, amount={self.amount}," \
+               f" height={self.height}, " \
+               f"pubkey={self.pubkey.hex()})"
+
 
-    def __init__(self, blob: bytes = b""):
-        self.blob: bytes = blob
+class AvalancheSignedStake:
+    def __init__(self, stake=None, sig=b""):
+        self.stake: AvalancheStake = stake or AvalancheStake()
+        self.sig: bytes = sig
+        """Signature for this stake, bytes of length 64"""
+
+    def deserialize(self, f):
+        self.stake = AvalancheStake()
+        self.stake.deserialize(f)
+        self.sig = f.read(64)
+
+    def serialize(self) -> bytes:
+        return self.stake.serialize() + self.sig
+
+    def __repr__(self):
+        return f"AvalancheSignedStake(stake={self.stake}, sig={self.sig.hex()})"
+
+
+class AvalancheProof:
+    __slots__ = ("sequence", "expiration", "master", "stakes", "proofid")
+
+    def __init__(self, sequence=0, expiration=0,
+                 master=b"", signed_stakes=None):
+        self.sequence: int = sequence
+        self.expiration: int = expiration
+        self.master: bytes = master
+
+        self.stakes: List[AvalancheSignedStake] = signed_stakes or [
+            AvalancheSignedStake()]
+        self.proofid: int = self.compute_proof_id()
+
+    def compute_proof_id(self) -> int:
+        """Return Bitcoin's 256-bit hash (double SHA-256) of the
+        serialized proof data.
+        :return: bytes of length 32
+        """
+        ss = struct.pack("<Qq", self.sequence, self.expiration)
+        ss += ser_compact_size(len(self.master))
+        ss += self.master
+        ss += ser_compact_size(len(self.stakes))
+        for s in self.stakes:
+            ss += s.stake.serialize()
+        h = hash256(ss)
+        # make it an int, for comparing with Delegation.proofid
+        return uint256_from_str(h)
 
     def deserialize(self, f):
-        self.blob = f.read()
+        self.sequence = struct.unpack("<Q", f.read(8))[0]
+        self.expiration = struct.unpack("<q", f.read(8))[0]
+        self.master = deser_string(f)
+        self.stakes = deser_vector(f, AvalancheSignedStake)
+        self.proofid = self.compute_proof_id()
 
     def serialize(self):
         r = b""
-        r += self.blob
+        r += struct.pack("<Q", self.sequence)
+        r += struct.pack("<q", self.expiration)
+        r += ser_compact_size(len(self.master))
+        r += self.master
+        r += ser_vector(self.stakes)
         return r
 
     def __repr__(self):
-        return "AvalancheProof({})".format(self.serialize().hex())
+        return f"AvalancheProof(sequence={self.sequence}, " \
+               f"expiration={self.expiration}, " \
+               f"master={self.master.hex()}, " \
+               f"stakes={self.stakes})"
 
 
 class AvalancheVote():