The software puzzle scheme counters resource-inflated Denial-of-Service (DoS) attacks by requiring each client connecting to the server to correctly solve a cryptographic puzzle before a connection can be established. It is specifically designed to thwart attempts at utilizing high-performance Graphic Processing Units (GPUs) to cut down solution time, by dynamically and randomly generating the puzzle in such a way that an attacker cannot easily translate the puzzle to a GPU implementation. The puzzle to be delivered to the client, in the form of Java bytecode, needs to be protected with code-compliant obfuscation, to hinder reverse engineering without leaking hints on wrong key attempts that the attacker can abandon quickly. The original puzzle obfuscation method permutes instructions within syntactically similar instruction sets to preserve syntactic validity regardless of the key. However, this method will not significantly obstruct a more sophisticated bytecode verification that goes beyond syntax checking. On the other hand, due to Java's stringent specifications, existing obfuscation methods that produce fully verifiable bytecode have very restricted transformations and hence weak obfuscation strength. This paper proposes an advanced Java bytecode obfuscation method with deeper consideration of bytecode validity based on JVM verification step. It overcomes the code-compliant restriction by transforming a sequence of instructions instead of individual instructions, and introduces a randomness element that enables one-to-many transformations of the software puzzle even with the same key, thus increasing the barrier to reverse engineering.