Audit of Aleo Puzzle
April 8th, 2024

Description. Checking a synthesis puzzle solution (computing the proof target from a solution ID) is computationally expensive: taking approximately 100ms on commodity hardware. Hence if unauthenticated / untrusted clients are allowed to submit solutions to a validator / pool they can perform a Denial-of-Service attack: by submitting a large number of invalid solutions, requiring the validator to spend $\approx 100ms$ per solution to check its validity.

Impact. Aleo has clarified that this vector of attack is expected to be mitigated at the network layer by operators: not allowing unauthenticated clients to submit solutions. Given the nature of the synthesis puzzle, the high cost of checking a solution is inherent and ZKSecurity sees no other way to mitigate this issue.

Description. Across the different EpochHash values, the running time of the puzzle has two distinct "peaks" as shown in the figure below: Meaning that every EpochHash corresponded to either a "fast" or a "slow" puzzle. This behavior was caused by padding the leaves, essentially the extended witness for the R1CS relation, to the next power of eight (the comment below is inaccurate):

// Pad the leaves to the next power of two.
let Some(num_padded_leaves) = checked_next_power_of_n(leaves.len(), ARITY as usize) else {
    bail!("Integer overflow when computing the maximum number of leaves in the Merkle tree");
};

// Pad the leaves up to the next power of two.
if leaves.len() < num_padded_leaves {
    leaves.resize(num_padded_leaves, vec![false; 254]);
}

This padding caused the number of leaves for some EpochHashs to be either 32768 or 262144. For the latter, the running time of the puzzle solver was dominates by computing the Merkle tree root hash over the leaves.

Impact: This observation has no security implications.

Recommendation. This is being addressed, even prior to the audit, by the Aleo team: by precomputing the Merkle tree root hash for trees consisting only of padding, the padded root hash for 32768 and 262144 leaves can be computed in (essentially) the same time. Thus entirely removing the "slow" peak in the plot above and getting a single normal distribution as expected.

Description. The the least significant 64 bits of the epoch_hash is used to seed the PRG when generating the Aleo Instructions for the synthesis puzzle (the puzzle instance):

// Initialize the RNG from the lower 32 bits of the epoch hash.
let lower = u64::from_bytes_le(&epoch_hash.to_bytes_le()?[0..8])?;
let mut rng = ChaChaRng::seed_from_u64(lower);

Because the set of puzzle instances is relatively small ($2^{64}$) an attacker can theoretically precompute solutions for a subset of possible values of lower e.g. $2^{32}$ different values of lower, i.e. for lower in 0..(1 << 32) compute tables:

solution: [u64; 1 << 32] // map from lower -> winning nonce

The attacker could then grind on the epoch_hash until the hash match one of the precomputed values: in our case, the top 32 bits of least significant 64 bits of the epoch_hash is zero: epoch_hash = high_192_bits || 0x00000000 || low_32_bits. In the example outlined this requires $2^{32}$ double SHA-2 hashes to be computed on average.

This latter step, the grinding phase, is the only online computation required by the attacker and does not involve computing the synthesis puzzle at all. Once the attacker has found a match, they can use the precomputed SolutionID as a valid solution for the given epoch_hash.

Note: In general, the attacker could chose his offline/online memory/time tradeoff e.g. using a precomputation of $2^{16}$ would require $2^{64 - 16} = 2^{48}$ double SHA-2 hashes in the online phase and only $2^{16}$ puzzle solutions in the offline phase; which is within the range of capabilities of specialized hardware (ASICs).

Impact: ZKSecurity has judged that the attack above is not practically relevant: the cost of the attack, for reasonable proof_target, is more expensive than the cost of simply solving the puzzle. Additionally, the attack requires a great amount of control over the epoch hash, which was deemed infeasible.

Recommendation. In the interest of defense-in-depth and making the crypto more "boring" we recommend making the seed depend on the full epoch hash. Since the size of the epoch hash does not match the size of the seed, we recommend seeding the PRG as:

// hash the epoch hash to get a 256 bit seed for the PRG
let seed = sha256(&epoch_hash);
let mut rng = ChaChaRng::from_seed(seed);

This change has no practical cost.

Description. When checking a solution, the validator computes the solution's proof target itself.

Impact. There is a potential for lazy solvers to submit solutions without actually doing the work. They can sample a number of candidate "solutions" (producing them by simply incrementing the counter) and provide these to the validator, hoping that one (or more) will be lucky to be valid. Since verifying the proof target takes approximately 100ms, transmitting a candidate solution is much cheaper than actually checking it.

Recommendation. Include the proof target in the solution, ensuring that a rational solver will compute the proof target: the validator will reject the solution if the claimed proof target differs from the computed proof target. The validator still needs to compute the proof target to check if the solution is valid, see considerations about Denial-of-Service.

Description. Solution IDs are computed as a 64 bit digest of address, epoch_hash, and counter:

/// The solution ID.
#[derive(Copy, Clone, Eq, PartialEq, Hash)]
pub struct SolutionID<N: Network>([u8; 32], PhantomData<N>);

impl<N: Network> SolutionID<N> {
    /// Initializes the solution ID from the given epoch hash, address, and counter.
    pub fn new(epoch_hash: N::BlockHash, address: Address<N>, counter: u64) -> Result<Self> {
        // Construct the nonce as sha256d(epoch_hash_bytes_le || address || counter).
        let mut bytes_le = Vec::with_capacity(32 + 32 + 8);
        bytes_le.extend_from_slice(epoch_hash.to_bytes_le()?);
        bytes_le.extend_from_slice(&address.to_bytes_le()?);
        bytes_le.extend_from_slice(&counter.to_bytes_le()?);
        Ok(Self::from(sha256d(&bytes_le)))
    }
}

This provides only weak binding between a solution and the solver: given a solution ID solution_id = sha2(sha2(address1, epoch_hash, counter1)).to_u64() for a valid solution, an attacker can find (address2, epoch_hash, counter2) such that sha2(sha2(address2, epoch_hash, counter2)).to_u64() == solution_id and submit the solution as their own, effectively stealing the reward.

This attack requires $2^{64}$ double SHA-2 evaluations and is a multi-target attack: given $n$ valid solutions, the attacker can attempt to find a collision with any of them requiring $2^{64} / n$ double SHA-2 evaluations.

Impact. ZKSecurity has judged that the attack above is not practically relevant: the cost of the attack, for reasonable proof_target, is more expensive than the cost of solving the puzzle. The Aleo team has clarified the pool of solutions ($n$ above) is expected to be small.

Recommendation. Despite this, in the interest of defense-in-depth and making the crypto more "boring" we recommend increasing the size of the solution nonces to 256 bits, i.e. u256 nonce = sha2(sha2(address, epoch_hash, counter)). This makes the binding between the candidate solution (program inputs) and the solver cryptographically strong: since the distribution over generated candidate solutions sampled with the PRG has high entropy. We note that the motivation for the current nonce size is to keep the solution ID size small -- to reduce the amount of storage/complexity required when checking for duplicate solutions. One possible approach is to use the lower 64 bits of the 256 bit nonce as the solution ID (solution_id = nonce.to_u64()) and require the uniqueness of these, but still use the full 256 bit nonce for the PRG (prg = ChaChaRng::from(nonce)).

Description. Despite the puzzle of each epoch consisting of a distinct set of Aleo Instructions, the running time of the synthesis puzzle is tightly distributed. This is partly because the running time of the synthesis puzzle is dominated by a constant prefix, which is the same for every generated program. In turn the dominating part of this prefix is 10 applications of the Poseidon hash function:

hash.psd2 r12 into r20 as u8;
hash.psd2 r13 into r21 as u8;

hash.psd2 r12 into r22 as u16;
hash.psd2 r13 into r23 as u16;

hash.psd2 r12 into r24 as u32;
hash.psd2 r13 into r25 as u32;

hash.psd2 r12 into r26 as u64;
hash.psd2 r13 into r27 as u64;

hash.psd2 r12 into r28 as u128;
hash.psd2 r13 into r29 as u128;

Below is a flamegraph showing the running time of the synthesis (Instruction<N>::execute) for a generated program. We observed that the hash applications (Poseidon) account for $\approx 90 \%$ of the running time when generating the extended witness for a candidate assignment:

Note: Since 8 of the 10 applications of Poseidon are on the same input, the synthesis step of puzzle solving can be optimized by simply avoiding recomputing the Poseidon hashes for the same input.

Note: This observation has no security implications.