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, cloud-based 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 cloud-based 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 blockchain-based 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.