Verifying the authenticity of educational certificates is essential to prevent fraud that can disrupt hiring processes and cause significant productivity losses. While various solutions have been proposed, most fail to offer an affordable, tamper-proof, and integrated platform that validates both the certificate and its issuer. EduTrustChain addresses this gap through a decentralized blockchain-based framework that ensures secure, rapid, and transparent certificate authentication. The system employs hash function mapping for faster searches and incorporates a voting mechanism to authorize new issuers, enhancing trust across stakeholders. To validate its performance, a private Ethereum blockchain was deployed where each peer node represents a key entity validator, issuer, certificate holder, or client. Experimental results demonstrate that EduTrustChain minimizes certificate addition costs, drastically reduces search time (especially for invalid certificates), and offers strong resilience against 51% and Sybil attacks. A static analysis using the Slither framework confirms smart contract security, while comparative evaluations show improved efficiency and cost-effectiveness over existing approaches. By combining speed, trust, and tamper-resistance, EduTrustChain offers a robust and scalable solution for modern credential verification.