In this work, we propose a satellite-aided permissionless consensus protocol for scalable space-terrestrial blockchains. We design its working principle and workflow by taking full advantage of satellites for extensive coverage and ubiquitous connectivity. Based on the proposed protocol, we demonstrate how such a space-terrestrial blockchain grows and evolves through several typical cases in the presence of adversarial nodes, user misbehavior, and transmission outage. Taking proof of work (PoW) as a benchmark, we assess the system security by considering both adversarial miners and possible colluding satellites. Then, we analyze the maximum blockchain throughput under network capacity limits and evaluate the impact of information propagation delay via a Markov model. Simulation results support that the proposed satellite-aided consensus protocol achieves higher throughput and exhibits greater scalability than PoW.