In traditional electronic health records (EHRs), medical-related information is generally separately controlled by different hospitals and thus it leads to the inconvenience of information sharing. Cloud-based EHRs solve the problem of information sharing in the traditional EHRs. However, cloudbased EHRs suffer the centralized problem, i.e., cloud service center and key-generation center. This paper works on creating a new EHRs paradigm which can help in dealing with the centralized problem of cloudbased EHRs. Our solution is to make use of the emerging technology of blockchain to EHRs (denoted as blockchain-based EHRs for convenience). First, we formally define the system model of blockchainbased EHRs in the setting of consortium blockchain. In addition, the authentication issue is very important for EHRs. However, existing authentication schemes for blockchain-based EHRs have their own weak points. Therefore, in this paper, we also propose an authentication scheme for blockchain-based EHRs. Our proposal is an identity-based signature scheme with multiple authorities which can resist collusion attack out of N from N −1 authorities. Furthermore, our scheme is provably secure in the random oracle model and has more efficient signing and verification algorithms than existing authentication schemes of blockchain-based EHRs.