265 lines
8.3 KiB
Python
265 lines
8.3 KiB
Python
from unittest import TestCase
|
|
from itertools import repeat
|
|
import numpy as np
|
|
import hashlib
|
|
|
|
from copy import deepcopy
|
|
from cryptarchia.cryptarchia import (
|
|
maxvalid_bg,
|
|
Chain,
|
|
BlockHeader,
|
|
Slot,
|
|
Id,
|
|
MockLeaderProof,
|
|
Coin,
|
|
Follower,
|
|
)
|
|
|
|
from .test_common import mk_chain, mk_config, mk_genesis_state, mk_block
|
|
|
|
|
|
class TestOrphanedProofs(TestCase):
|
|
def test_simple_orphan_import(self):
|
|
c_a, c_b = Coin(sk=0, value=10), Coin(sk=1, value=10)
|
|
coins = [c_a, c_b]
|
|
config = mk_config(coins)
|
|
genesis = mk_genesis_state(coins)
|
|
follower = Follower(genesis, config)
|
|
|
|
# -- fork --
|
|
#
|
|
# b2 == tip
|
|
# /
|
|
# b1
|
|
# \
|
|
# b3
|
|
#
|
|
|
|
b1, c_a = mk_block(genesis.block, 1, c_a), c_a.evolve()
|
|
b2, c_a = mk_block(b1.id(), 2, c_a), c_a.evolve()
|
|
b3, c_b = mk_block(b1.id(), 2, c_b), c_b.evolve()
|
|
|
|
for b in [b1, b2, b3]:
|
|
follower.on_block(b)
|
|
|
|
assert follower.tip() == b2
|
|
assert [f.tip() for f in follower.forks] == [b3]
|
|
assert follower.unimported_orphans(follower.tip_id()) == [b3]
|
|
|
|
# -- extend with import --
|
|
#
|
|
# b2 - b4
|
|
# / /
|
|
# b1 /
|
|
# \ /
|
|
# b3
|
|
#
|
|
b4, c_a = mk_block(b2.id(), 3, c_a, orphaned_proofs=[b3]), c_a.evolve()
|
|
follower.on_block(b4)
|
|
|
|
assert follower.tip() == b4
|
|
assert [f.tip() for f in follower.forks] == [b3]
|
|
assert follower.unimported_orphans(follower.tip_id()) == []
|
|
|
|
def test_orphan_proof_import_from_long_running_fork(self):
|
|
c_a, c_b = Coin(sk=0, value=10), Coin(sk=1, value=10)
|
|
coins = [c_a, c_b]
|
|
config = mk_config(coins)
|
|
genesis = mk_genesis_state(coins)
|
|
follower = Follower(genesis, config)
|
|
|
|
# -- fork --
|
|
#
|
|
# b2 - b3 == tip
|
|
# /
|
|
# b1
|
|
# \
|
|
# b4 - b5
|
|
#
|
|
|
|
b1, c_a = mk_block(genesis.block, 1, c_a), c_a.evolve()
|
|
|
|
b2, c_a = mk_block(b1.id(), 2, c_a), c_a.evolve()
|
|
b3, c_a = mk_block(b2.id(), 3, c_a), c_a.evolve()
|
|
|
|
b4, c_b = mk_block(b1.id(), 2, c_b), c_b.evolve()
|
|
b5, c_b = mk_block(b4.id(), 3, c_b), c_b.evolve()
|
|
|
|
for b in [b1, b2, b3, b4, b5]:
|
|
follower.on_block(b)
|
|
|
|
assert follower.tip() == b3
|
|
assert [f.tip() for f in follower.forks] == [b5]
|
|
assert follower.unimported_orphans(follower.tip_id()) == [b4, b5]
|
|
|
|
# -- extend b3, importing the fork --
|
|
#
|
|
# b2 - b3 - b6 == tip
|
|
# / ___/
|
|
# b1 ___/ /
|
|
# \ / /
|
|
# b4 - b5
|
|
|
|
b6, c_a = mk_block(b3.id(), 4, c_a, orphaned_proofs=[b4, b5]), c_a.evolve()
|
|
follower.on_block(b6)
|
|
|
|
assert follower.tip() == b6
|
|
assert [f.tip() for f in follower.forks] == [b5]
|
|
|
|
def test_orphan_proof_import_from_fork_without_direct_shared_parent(self):
|
|
coins = [Coin(sk=i, value=10) for i in range(2)]
|
|
c_a, c_b = coins
|
|
config = mk_config(coins)
|
|
genesis = mk_genesis_state(coins)
|
|
follower = Follower(genesis, config)
|
|
|
|
# -- forks --
|
|
#
|
|
# b2 - b3 - b4 == tip
|
|
# /
|
|
# b1
|
|
# \
|
|
# b5 - b6 - b7
|
|
|
|
b1, c_a = mk_block(genesis.block, 1, c_a), c_a.evolve()
|
|
|
|
b2, c_a = mk_block(b1.id(), 2, c_a), c_a.evolve()
|
|
b3, c_a = mk_block(b2.id(), 3, c_a), c_a.evolve()
|
|
b4, c_a = mk_block(b3.id(), 4, c_a), c_a.evolve()
|
|
|
|
b5, c_b = mk_block(b1.id(), 2, c_b), c_b.evolve()
|
|
b6, c_b = mk_block(b5.id(), 3, c_b), c_b.evolve()
|
|
b7, c_b = mk_block(b6.id(), 4, c_b), c_b.evolve()
|
|
|
|
for b in [b1, b2, b3, b4, b5, b6, b7]:
|
|
follower.on_block(b)
|
|
|
|
assert follower.tip() == b4
|
|
assert [f.tip() for f in follower.forks] == [b7]
|
|
assert follower.unimported_orphans(follower.tip_id()) == [b5, b6, b7]
|
|
|
|
# -- extend b4, importing the forks --
|
|
#
|
|
# b2 - b3 - b4 - b8 == tip
|
|
# / _______/
|
|
# b1 ____/______/
|
|
# \ / / /
|
|
# b5 - b6 - b7
|
|
#
|
|
# Earlier implementations of orphan proof validation failed to
|
|
# validate b7 as an orphan here.
|
|
|
|
b8, c_a = mk_block(b4.id(), 5, c_a, orphaned_proofs=[b5, b6, b7]), c_a.evolve()
|
|
follower.on_block(b8)
|
|
|
|
assert follower.tip() == b8
|
|
assert [f.tip() for f in follower.forks] == [b7]
|
|
assert follower.unimported_orphans(follower.tip_id()) == []
|
|
|
|
def test_unimported_orphans(self):
|
|
# Given the following fork graph:
|
|
#
|
|
# b2 - b3
|
|
# /
|
|
# b1
|
|
# \
|
|
# b4 - b5
|
|
# \
|
|
# -- b6
|
|
#
|
|
# Orphans w.r.t. to b3 are b4..6, thus extending from b3 with b7 would
|
|
# give the following fork graph
|
|
#
|
|
# b2 - b3 --- b7== tip
|
|
# / ____/
|
|
# b1 ____/ __/
|
|
# \ / / /
|
|
# b4 - b5 /
|
|
# \ /
|
|
# -- b6
|
|
#
|
|
|
|
coins = [Coin(sk=i, value=10) for i in range(3)]
|
|
c_a, c_b, c_c = coins
|
|
config = mk_config(coins)
|
|
genesis = mk_genesis_state(coins)
|
|
follower = Follower(genesis, config)
|
|
|
|
b1, c_a = mk_block(genesis.block, 1, c_a), c_a.evolve()
|
|
|
|
b2, c_a = mk_block(b1.id(), 2, c_a), c_a.evolve()
|
|
b3, c_a = mk_block(b2.id(), 3, c_a), c_a.evolve()
|
|
|
|
b4, c_b = mk_block(b1.id(), 2, c_b), c_b.evolve()
|
|
b5, c_b = mk_block(b4.id(), 3, c_b), c_b.evolve()
|
|
|
|
b6, c_c = mk_block(b4.id(), 3, c_c), c_c.evolve()
|
|
|
|
for b in [b1, b2, b3, b4, b5, b6]:
|
|
follower.on_block(b)
|
|
|
|
assert follower.tip() == b3
|
|
assert [f.tip() for f in follower.forks] == [b5, b6]
|
|
assert follower.unimported_orphans(follower.tip_id()) == [b4, b5, b6]
|
|
|
|
b7, c_a = mk_block(b3.id(), 4, c_a, orphaned_proofs=[b4, b5, b6]), c_a.evolve()
|
|
|
|
follower.on_block(b7)
|
|
assert follower.tip() == b7
|
|
|
|
def test_transitive_orphan_reimports(self):
|
|
# Two forks, one after the other, with some complicated orphan imports.
|
|
# I don't have different line colors to differentiate orphans from parents
|
|
# so I've added o=XX to differentiate orphans from parents.
|
|
#
|
|
# - The first fork at b3(a) is not too interesting.
|
|
# - The second fork at b4(b) has both b6 and b7 importing b5
|
|
# - crucially b7 uses the evolved commitment from b5
|
|
# - Then finally b8 imports b7.
|
|
#
|
|
# proper orphan proof importing will be able to deal with the fact that
|
|
# b7's commitment was produced outside of the main branch AND the commitment
|
|
# is not part of the current list of orphans in b8
|
|
# (b5 had already been imported, therefore it is not included as an orphan in b8)
|
|
#
|
|
# b1(a) - b2(a) - b3(a) - b4(b) - b6(b, o=b5) - b8(b, o=b7)
|
|
# \ \___ __/ __/
|
|
# \ _x_ __/
|
|
# \ / \_ /
|
|
# -b5(a)-----\-b7(a, o=b5)
|
|
|
|
coins = [Coin(sk=i, value=10) for i in range(2)]
|
|
c_a, c_b = coins
|
|
config = mk_config(coins)
|
|
genesis = mk_genesis_state(coins)
|
|
follower = Follower(genesis, config)
|
|
|
|
b1, c_a = mk_block(genesis.block, 1, c_a), c_a.evolve()
|
|
b2, c_a = mk_block(b1.id(), 2, c_a), c_a.evolve()
|
|
b3, c_a = mk_block(b2.id(), 3, c_a), c_a.evolve()
|
|
|
|
b4, c_b = mk_block(b3.id(), 4, c_b), c_b.evolve()
|
|
b5, c_a = mk_block(b3.id(), 4, c_a), c_a.evolve()
|
|
|
|
b6, c_b = mk_block(b4.id(), 5, c_b, orphaned_proofs=[b5]), c_b.evolve()
|
|
b7, c_a = mk_block(b4.id(), 5, c_a, orphaned_proofs=[b5]), c_a.evolve()
|
|
|
|
b8, c_b = mk_block(b6.id(), 6, c_b, orphaned_proofs=[b7]), c_b.evolve()
|
|
|
|
for b in [b1, b2, b3, b4, b5]:
|
|
follower.on_block(b)
|
|
|
|
assert follower.tip() == b4
|
|
assert follower.unimported_orphans(follower.tip_id()) == [b5]
|
|
|
|
for b in [b6, b7]:
|
|
follower.on_block(b)
|
|
|
|
assert follower.tip() == b6
|
|
assert follower.unimported_orphans(follower.tip_id()) == [b7]
|
|
|
|
follower.on_block(b8)
|
|
|
|
assert follower.tip() == b8
|
|
assert follower.unimported_orphans(follower.tip_id()) == []
|