TrustChain is capable of creating trusted transactions among strangers without central control. This enables new areas of blockchain use with a focus on building trust between individuals. Our innovative approach offers scalability, openness and Sybil-resistance while replacing proof-of-work with a mechanism to establish the validity and integrity of transactions.TrustChain is a permission-less tamper-proof data structure for storing transaction records of agents. We create an immutable chain of temporally ordered interactions for each agent. It is inherently parallel and every agent creates his own genesis block. TrustChain includes a novel Sybil-resistant algorithm named NetFlow to determine trustworthiness of agents in an online community. NetFlow ensures that agents who take resources from the community also contribute back. We demonstrate that irrefutable historical transaction records offer security and seamless scalability, without requiring global consensus. Experimentation shows that the transaction throughput of TrustChain surpasses that of traditional blockchain architectures like Bitcoin. We show by using extracted data from a live network that TrustChain has sufficient informativeness to identify freeriders, leading to refusal of service.