February-27, 2023 NEM Stall Post Mortem

Observation

Root Cause Analysis

1. M sends a multisig transaction MT with an inner transaction - X - signed by A
2. The multisig transaction gets committed to the chain and TransactionHashesObserver (running as part of BlockTransactionFactory) adds both H(MT), H(X) to HashTransactionsCache

   public void notify(final TransactionHashesNotification notification, final BlockNotificationContext context) {
   if (NotificationTrigger.Execute == context.getTrigger()) {
   	this.transactionHashCache.putAll(notification.getPairs());
   } 
   ...

   Importantly, when the TransactionsHashesNotification is created, streamDefault is used, which expands to both outer and inner transactions:

   protected void notifyTransactionHashes() {
   	final List<HashMetaDataPair> pairs = BlockExtensions.streamDefault(this.block)
   			.map(t -> new HashMetaDataPair(HashUtils.calculateHash(t), new HashMetaData(this.block.getHeight(), t.getTimeStamp())))
   			.collect(Collectors.toList());
   	this.observer.notify(new TransactionHashesNotification(pairs));
   }
   

3. M sends a multisig transaction MT' with the SAME inner transaction X signed by B
4. BatchUniqueHashTransactionValidator checks that H(MT') is not in HashTransactionsCache, so it gets added to UnconfirmedTransactionsCache ✅

   public ValidationResult validate(final List<TransactionsContextPair> groupedTransactions) {
           ...
   	final List<Hash> hashes = groupedTransactions.stream().flatMap(pair -> pair.getTransactions().stream())
   			.map(HashUtils::calculateHash).collect(Collectors.toList());
   
   	return this.validate(hashes);
   }
   

   Importantly, pair.getTransactions() returns Collection<Transaction>, which only contains outer transactions. As a result, H(MT') != H(MT) is checked but H(X) is not checked.
5. MT' gets selected for a block by the harvester. BlockUniqueHashTransactionValidator has the same logic as BatchUniqueHashTransactionValidator, so only the hash of the outer MT' is checked. As a result, the transaction is included in the harvested block ✅

   public ValidationResult validate(final Block 
           ...
   	final List<Hash> hashes = block.getTransactions().stream().map(HashUtils::calculateHash).collect(Collectors.toList());
   	return this.transactionHashCache.anyHashExists(hashes) ? ValidationResult.NEUTRAL : ValidationResult.SUCCESS;
   }

6. When the newly harvested block - containing MT' - is processed, TransactionHashesObserver attempts to add both H(MT') and H(X) to HashTransactionsCache during part of the block processing that makes state changes. This fails because H(X) is already present in the UnconfirmedTransactionsCache, so the harvested block gets rejected 🛑
7. Go to step 5 until H(MT') expires out of the UnconfirmedTransactionsCache

Fix

BatchUniqueHashTransactionValidator

public ValidationResult validate(final List<TransactionsContextPair> groupedTransactions) {
    if (groupedTransactions.isEmpty()) {
        return ValidationResult.SUCCESS;
    }

    final List<Hash> hashes = groupedTransactions.stream().flatMap(pair -> pair.getTransactions().stream())
            .flatMap(transaction -> TransactionExtensions.streamDefault(transaction)).map(HashUtils::calculateHash)
            .collect(Collectors.toList());
    return this.validate(hashes);
}

BlockUniqueHashTransactionValidator

public ValidationResult validate(final Block block) {
    if (block.getTransactions().isEmpty()) {
        return ValidationResult.SUCCESS;
    }

    final List<Hash> hashes = block.getTransactions().stream().flatMap(transaction -> TransactionExtensions.streamDefault(transaction))
            .map(HashUtils::calculateHash).collect(Collectors.toList());
    return this.transactionHashCache.anyHashExists(hashes) ? ValidationResult.NEUTRAL : ValidationResult.SUCCESS;
}