The ability of tracing states of logistic transportations requires an efficient storage and retrieval of the state of logistic transportations and locations of logistic objects. However, the restriction of sharing states and locations of logistic objects across organizations from different countries makes it hard to deploy a centralized database for implementing the traceability in a cross-border logistic system. This paper proposes a semantic data model on Blockchain to represent a logistic process based on the Semantic Link Network model where each semantic link represents a logistic transportation of a logistic object between two parties. A state representation model is designed to represent the states of a logistic transportation with semantic links. It enables the locations of logistic objects to be derived from the link states. A mapping from the semantic links to the blockchain transactions is designed to enable schema of semantic links and states of semantic links to be published in blockchain transactions. To improve the efficiency of tracing a path of semantic links on blockchain platform, an algorithm is designed to build shortcuts along the path of semantic links to enable a query on the path of a logistic object to reach the target in logarithmic steps on the blockchain platform. A reward-penalty policy is designed to allow participants to confirm the state of links on blockchain. Analysis and simulation demonstrate the flexibility, effectiveness and the efficiency of Semantic Link Network on immutable blockchain for implementing logistic traceability.