Hyperdimensional Computing (HDC) is a promising bio-inspired learning paradigm for its advantage of balancing performance and efficiency and has been increasingly applied to the bio-medical domain. In bio-medical applications, trustworthiness such as replicability and verifiability of the trained learning models is crucial. In this work, we introduce HDCoin, the first proof-of-useful-work blockchain framework for HDC. With HDCoin, we transform the conventional energy-wasteful mining process into a competitive process for developing high accuracy, trustworthy and verifiable hyperdimensional models. We explore four diverse biomedical datasets, and conduct an extensive design-space exploration of key HDC hyperparameters of blockchain miners such as dimensionality, learning rate, and retraining iterations for model performance, adaptive mining difficulty and fairness on proof-of-useful-work.