feature/ghost (#77)

* started ghost implementation * rename * fixed
yeeth · Mar 18, 2019 · d6e6418 · d6e6418
1 parent 171d21d
commit d6e6418
Show file tree

Hide file tree

Showing 15 changed files with 87 additions and 12 deletions.
diff --git a/Sources/BeaconChain/DataStructures/Blocks/BeaconBlock.swift b/Sources/BeaconChain/DataStructures/Blocks/BeaconBlock.swift
@@ -1,6 +1,6 @@
 import Foundation
 
-struct BeaconBlock {
+struct BeaconBlock: Equatable {
     let slot: UInt64
     let parentRoot: Data
     let stateRoot: Data

diff --git a/Sources/BeaconChain/DataStructures/Blocks/BeaconBlockBody.swift b/Sources/BeaconChain/DataStructures/Blocks/BeaconBlockBody.swift
@@ -1,6 +1,6 @@
 import Foundation
 
-struct BeaconBlockBody {
+struct BeaconBlockBody: Equatable {
     let proposerSlashings: [ProposerSlashing]
     let attesterSlashings: [AttesterSlashing]
     let attestations: [Attestation]

diff --git a/Sources/BeaconChain/DataStructures/Blocks/ProposalSignedData.swift b/Sources/BeaconChain/DataStructures/Blocks/ProposalSignedData.swift
@@ -1,6 +1,6 @@
 import Foundation
 
-struct Proposal {
+struct Proposal: Equatable {
     let slot: UInt64
     let shard: UInt64
     let blockRoot: Data

diff --git a/Sources/BeaconChain/DataStructures/Transactions/Attestations/Attestation.swift b/Sources/BeaconChain/DataStructures/Transactions/Attestations/Attestation.swift
@@ -1,6 +1,6 @@
 import Foundation
 
-struct Attestation {
+struct Attestation: Equatable {
     let aggregationBitfield: Data
     let data: AttestationData
     let custodyBitfield: Data

diff --git a/Sources/BeaconChain/DataStructures/Transactions/AttesterSlashings/AttesterSlashing.swift b/Sources/BeaconChain/DataStructures/Transactions/AttesterSlashings/AttesterSlashing.swift
@@ -1,6 +1,6 @@
 import Foundation
 
-struct AttesterSlashing {
+struct AttesterSlashing: Equatable {
     let slashableAttestation1: SlashableAttestation
     let slashableAttestation2: SlashableAttestation
 }
diff --git a/Sources/BeaconChain/DataStructures/Transactions/AttesterSlashings/SlashableAttestation.swift b/Sources/BeaconChain/DataStructures/Transactions/AttesterSlashings/SlashableAttestation.swift
@@ -1,6 +1,6 @@
 import Foundation
 
-struct SlashableAttestation {
+struct SlashableAttestation: Equatable {
     let validatorIndices: [UInt64]
     let data: AttestationData
     let custodyBitfield: Data

diff --git a/Sources/BeaconChain/DataStructures/Transactions/Deposits/Deposit.swift b/Sources/BeaconChain/DataStructures/Transactions/Deposits/Deposit.swift
@@ -1,6 +1,6 @@
 import Foundation
 
-struct Deposit {
+struct Deposit: Equatable {
     let branch: [Data]
     let index: UInt64
     let depositData: DepositData

diff --git a/Sources/BeaconChain/DataStructures/Transactions/Deposits/DepositData.swift b/Sources/BeaconChain/DataStructures/Transactions/Deposits/DepositData.swift
@@ -1,6 +1,6 @@
 import Foundation
 
-struct DepositData {
+struct DepositData: Equatable {
     let amount: UInt64
     let timestamp: UInt64
     let depositInput: DepositInput

diff --git a/Sources/BeaconChain/DataStructures/Transactions/Deposits/DepositInput.swift b/Sources/BeaconChain/DataStructures/Transactions/Deposits/DepositInput.swift
@@ -1,6 +1,6 @@
 import Foundation
 
-struct DepositInput {
+struct DepositInput: Equatable {
     let pubkey: Data
     let withdrawalCredentials: Data
     let proofOfPossession: Data

diff --git a/Sources/BeaconChain/DataStructures/Transactions/ProposerSlashing.swift b/Sources/BeaconChain/DataStructures/Transactions/ProposerSlashing.swift
@@ -1,6 +1,6 @@
 import Foundation
 
-struct ProposerSlashing {
+struct ProposerSlashing: Equatable {
     let proposerIndex: UInt64
     let proposal1: Proposal
     let proposal2: Proposal

diff --git a/Sources/BeaconChain/DataStructures/Transactions/Transfer.swift b/Sources/BeaconChain/DataStructures/Transactions/Transfer.swift
@@ -1,6 +1,6 @@
 import Foundation
 
-struct Transfer {
+struct Transfer: Equatable {
     let from: UInt64
     let to: UInt64
     let amount: UInt64

diff --git a/Sources/BeaconChain/DataStructures/Transactions/VoluntaryExit.swift b/Sources/BeaconChain/DataStructures/Transactions/VoluntaryExit.swift
@@ -1,6 +1,6 @@
 import Foundation
 
-struct VoluntaryExit {
+struct VoluntaryExit: Equatable {
     let epoch: UInt64
     let validatorIndex: UInt64
     let signature: Data

diff --git a/Sources/BeaconChain/ForkChoice/ForkChoice.swift b/Sources/BeaconChain/ForkChoice/ForkChoice.swift
@@ -0,0 +1,7 @@
+import Foundation
+
+protocol ForkChoice {
+
+    func execute(store: Store, startState: BeaconState, startBlock: BeaconBlock) -> BeaconBlock
+
+}
diff --git a/Sources/BeaconChain/ForkChoice/LMDGhost.swift b/Sources/BeaconChain/ForkChoice/LMDGhost.swift
@@ -0,0 +1,43 @@
+import Foundation
+
+class LMDGhost: ForkChoice {
+
+    func execute(store: Store, startState: BeaconState, startBlock: BeaconBlock) -> BeaconBlock {
+        let attestationTargets = startState.validatorRegistry.activeIndices(epoch: startState.slot.toEpoch()).map {
+            ($0, store.latestAttestationTarget(validator: $0))
+        }
+
+        var head = startBlock
+        while true {
+            let children = store.children(head)
+            if children.count == 0 {
+                return head
+            }
+
+            head = children.max {
+                voteCount(store: store, state: startState, block: $0, attestationTargets: attestationTargets) < voteCount(store: store, state: startState, block: $1, attestationTargets: attestationTargets)
+            }!
+        }
+    }
+
+    private func voteCount(
+        store: Store,
+        state: BeaconState,
+        block: BeaconBlock,
+        attestationTargets: [(ValidatorIndex, BeaconBlock)]
+    ) -> UInt64 {
+        return attestationTargets.compactMap {
+            (index, target) in
+            guard let ancestor = store.ancestor(block: target, slot: index) else {
+                return nil
+            }
+
+            if ancestor == block {
+                return BeaconChain.getEffectiveBalance(state: state, index: index) / FORK_CHOICE_BALANCE_INCREMENT
+            }
+
+            return nil
+        }
+        .reduce(0, +)
+    }
+}
diff --git a/Sources/BeaconChain/Store/Store.swift b/Sources/BeaconChain/Store/Store.swift
@@ -0,0 +1,25 @@
+import Foundation
+
+protocol Store {
+
+    func parent(_ block: BeaconBlock) -> BeaconBlock
+    func children(_ block: BeaconBlock) -> [BeaconBlock]
+    func latestAttestation(validator: ValidatorIndex) -> Attestation
+    func latestAttestationTarget(validator: ValidatorIndex) -> BeaconBlock
+}
+
+extension Store {
+
+    func ancestor(block: BeaconBlock, slot: Slot) -> BeaconBlock? {
+        if block.slot == slot {
+            return block
+        }
+
+        if block.slot < slot {
+            return nil
+        }
+
+        return ancestor(block: parent(block), slot: slot)
+    }
+}
+