Certificate Revocation is a critical issue for a practical, public-key infrastructure. A new efficient revocation protocol using a one-way hash tree structure (instead of the classical list structure, which is known as a standard for revocation), was proposed and examined to reduce communication and computation costs. In this paper, we analysis a k-ary hash tree for certificate revocation and prove that k = 2 minimizes communication cost.