Analysis of Loki's double spend protection implementation

Loki double spend analysis

How loki handles double spends

Loki service node (which is a just cryptonode with extra functionality) maintains a map of

tx_hash -> blink_tx

mutable std::unordered_map<crypto::hash, std::shared_ptr<cryptonote::blink_tx>> m_blinks;

where blink_tx is the class, containing:

• tx or tx_hash (TODO: understand the rationale behind "for regular blink txes received via p2p this will contain the hash" )

   /// The blink transaction *or* hash. The transaction is present when building a blink tx for
   /// blink quorum signing; for regular blink txes received via p2p this will contain the hash
   /// instead.
  
   boost::variant<transaction, crypto::hash> tx;
  

• subquorum enum (TODO: not clear what is it)

• signature_status - enum describing current status of blink_tx

• height - block height when tx has been created (authorization height); in graft we have auth_sample_height for the same purpose

When transaction comes to mempool it processed by tx_memory_pool::add_tx method in the tx_memory_pool::add_tx method there 3 possible cases while dealing with double spending transactions:

1. new ordinary tx added to mempool - in this case following code works:

if (double_spend)
{
	mark_double_spend(tx);
	LOG_PRINT_L1("Transaction with id= "<< id << " used already spent key images");
	tvc.m_verifivation_failed = true;
	tvc.m_double_spend = true;
	return false;
}

2. ordinary tx popped up from block due chain reorg or rollback (already seen) -> it checked against all blink transactions. In case any match - it marked as double spend and not being added to the mempool

if (double_spend)
{
........
	if (opts.kept_by_block)

3. new approved blink tx:

}
else if (opts.approved_blink)
{
	MDEBUG("Incoming blink tx is approved, but has " << conflict_txs.size() << " conflicting local tx(es); dropping conflicts");
.......

The tx_memory_pool::remove_blink_conflicts() method removes conflicting non-blink transactions from mempool and also checks if incoming blink transaction conflicting with older (already mined into blocks) ordinary transactions or blink transactions. In case blink vs non-blink conflict can be resolved with rolllback - it returns true and blink_rollback_height pointer; in case conflict can't be resolved with rollback (older blink transaction or regular transaction mined in the checkpointed block) - method returns false, which signals caller to mark incoming tx as double spending:

else
	MERROR("Blink error: incoming blink tx cannot be accepted as it conflicts with checkpointed txs");

then blink_rollback_height variable passed to tx_memory_pool::check_tx_inputs which in turn updates blink_rollback_height with earliest block height:

        std::vector<std::pair<cryptonote::blobdata, cryptonote::block>> blocks;
        if (m_blockchain.get_blocks(immutable + 1, height, blocks))
        {
          std::vector<cryptonote::transaction> txs;
          std::vector<crypto::hash> missed_txs;
          uint64_t earliest = height;
          for (auto it = blocks.rbegin(); it != blocks.rend(); it++)
          {
            const auto& block = it->second;
            auto block_height = cryptonote::get_block_height(block);
            txs.clear();
            missed_txs.clear();

            if (!m_blockchain.get_transactions(block.tx_hashes, txs, missed_txs))
            {
              MERROR("Unable to get transactions for block " << block.hash);
              can_fix_with_a_rollback = false;
              break;
            }
            for (const auto& tx : txs) {
              for (const auto& in : tx.vin) {
                if (in.type() == typeid(txin_to_key) && key_image_conflicts.erase(boost::get<txin_to_key>(in).k_image)) {
                  earliest = std::min(earliest, block_height);
                  if (key_image_conflicts.empty())
                    goto end;
                }
              }
            }
          }
end:
          if (key_image_conflicts.empty() && earliest < height && earliest > immutable)
          {
            MDEBUG("Blink admission requires rolling back to height " << earliest);
            can_fix_with_a_rollback = true;
            if (*blink_rollback_height == 0 || *blink_rollback_height > earliest)
              *blink_rollback_height = earliest;
          }
        }

Actual chain rollback only happened in:

cryptonote_protocol_handler::handle_notify_new_transaction()
 ->  core::handle_parsed_txs()
   -> tx_memory_pool::add_tx() -> this one returns "blink_rollback_height"
 ->  Blockchain::blink_rollback() -> this one does actuall blockchain rollback

Questions:

1. Does loki add something extra to the blockchain?

• yes:
  • checkpoints (MDB_cursor *block_checkpoints)
  • alt_blocks (introduced in monero 15)
  • service_node_data
  • service_node_proofs
  • output_blacklist (TODO: check what is this, most likely loki specific)

2. Is m_blinks memory-only container or it stored in blockchain db? - it looks like its in-memory only container. TODO: explain algorithm and rationale why it is used at all as it will be empty right after node restarted.

3. In what place graftnoded should check for conflicts "new rta vs old rta/non-rta" when new RTA tx is coming?

• when tx comes from RPC /sendrawtransaction core_rpc_server::on_send_raw_tx (both RTA and regular txes comes this way)
• when tx relayed over p2p cryptonote_protocol_handler::handle_notify_new_transaction

4. In what place we should "rollback" blockchain in case rta vs non-rta conflict?

   • rollback inside cryptonote_protocol_handler::handle_notify_new_transaction() (same way as loki)
   • rollback inside core_rpc_server::on_send_raw_tx (TODO: explain why loki doesn't rollback there, as cryptonote_protocol_handler::handle_notify_new_transaction() is not triggered after this call)
   • rollback when node receives new block in synced state (cryptonote_protocol_handler::handle_notify_new_fluffy_block()) - is it possible if someone will send this message with the block containing double spent transaction? Even if so, this block would be rejected as per current implementation but what if such a block contains valid RTA transaction but malicious non-rta transaction already in mempool or even mined? - Guess it's definitely impossible because miners will never mine such block
   • rollback when node receives new txs and blocks in syncing state (cryptonote_protocol_handler::handle_notify_new_fluffy_block())

5. check how loki's wallet submits blink transaction DONE, checked - via standard "sendrawtransaction" RPC. Only difference is the "blink" flag

6. What are the differences between blink and RTA architectures

• RTA keys/signatures are stored directly in transaction (extra + extra2) while blink signatures are stored (?) in the separate objects in blockchain (TODO: where exactly it stored, can't see it at this time, need further research). Documentation (https://docs.loki.network/LokiServices/Blink/) says it only stored until block, containing blink tx (which is ordinary tx unlike RTA) get checkpointed, after it should be dropped.

• ordinary wallet can send blink transactions, only difference with regular transactions is "blink" flag in request structure, not in TX itself; (and different tx fee)

• service node's functionality implemented directly in the "node" process, no separate processes for service nodes

5. How loki's service nodes get rewarded? at the moment tx created, sender's walled doesn't know who will be validating transaction

• service nodes got 50% of block rewards. Client who sends blink pays some extra blink fee which is burned (?)

6. what cryptonote_protocol_handler handlers are called when node synchronizes with the peers (syncing state)?

• cryptonote_protocol_handler::handle_response_chain_entry()
• cryptonote_protocol_handler::handle_response_get_objects() (TODO check what handlers in loki are called while node synchronizes, probably it will be more clear why rollback only done in cryptonote_protocol_handler::handle_notify_new_transaction() )`

7. what cryptonote_protocol_handler handlers are called when chain reorg happening?

• only cryptonote_protocol_handler::handle_response_get_objects() (upd: loki removed this command from protocol)

8. Does loki extends cryptonote protocol with extra messages?

• yes, Graft/Monero and Loki cryptonote protocol differs now (Loki removed NOTIFY_REQUEST_GET_OBJECTS, NOTIFY_RESPONSE_GET_OBJECTS commands and added NOTIFY_REQUEST_GET_TXS, NOTIFY_UPTIME_PROOF, NOTIFY_NEW_SERVICE_NODE_VOTE, NOTIFY_REQUEST_BLOCK_BLINKS, NOTIFY_RESPONSE_BLOCK_BLINKS )

Graft:

BEGIN_INVOKE_MAP2(cryptonote_protocol_handler)
   HANDLE_NOTIFY_T2(NOTIFY_NEW_BLOCK, &cryptonote_protocol_handler::handle_notify_new_block)
   HANDLE_NOTIFY_T2(NOTIFY_NEW_TRANSACTIONS, &cryptonote_protocol_handler::handle_notify_new_transactions)
   HANDLE_NOTIFY_T2(NOTIFY_REQUEST_GET_OBJECTS, &cryptonote_protocol_handler::handle_request_get_objects)
   HANDLE_NOTIFY_T2(NOTIFY_RESPONSE_GET_OBJECTS, &cryptonote_protocol_handler::handle_response_get_objects)
   HANDLE_NOTIFY_T2(NOTIFY_REQUEST_CHAIN, &cryptonote_protocol_handler::handle_request_chain)
   HANDLE_NOTIFY_T2(NOTIFY_RESPONSE_CHAIN_ENTRY, &cryptonote_protocol_handler::handle_response_chain_entry)
   HANDLE_NOTIFY_T2(NOTIFY_NEW_FLUFFY_BLOCK, &cryptonote_protocol_handler::handle_notify_new_fluffy_block)			
   HANDLE_NOTIFY_T2(NOTIFY_REQUEST_FLUFFY_MISSING_TX, &cryptonote_protocol_handler::handle_request_fluffy_missing_tx)						
 END_INVOKE_MAP2()

Loki:

 BEGIN_INVOKE_MAP2(cryptonote_protocol_handler)
   HANDLE_NOTIFY_T2(NOTIFY_NEW_TRANSACTIONS, handle_notify_new_transactions)
   HANDLE_NOTIFY_T2(NOTIFY_REQUEST_GET_BLOCKS, handle_request_get_blocks)
   HANDLE_NOTIFY_T2(NOTIFY_RESPONSE_GET_BLOCKS, handle_response_get_blocks)
   HANDLE_NOTIFY_T2(NOTIFY_REQUEST_GET_TXS, handle_request_get_txs)
   HANDLE_NOTIFY_T2(NOTIFY_REQUEST_CHAIN, handle_request_chain)
   HANDLE_NOTIFY_T2(NOTIFY_RESPONSE_CHAIN_ENTRY, handle_response_chain_entry)
   HANDLE_NOTIFY_T2(NOTIFY_NEW_FLUFFY_BLOCK, handle_notify_new_fluffy_block)
   HANDLE_NOTIFY_T2(NOTIFY_REQUEST_FLUFFY_MISSING_TX, handle_request_fluffy_missing_tx)
   HANDLE_NOTIFY_T2(NOTIFY_UPTIME_PROOF, handle_uptime_proof)
   HANDLE_NOTIFY_T2(NOTIFY_NEW_SERVICE_NODE_VOTE, handle_notify_new_service_node_vote)
   HANDLE_NOTIFY_T2(NOTIFY_REQUEST_BLOCK_BLINKS, handle_request_block_blinks)
   HANDLE_NOTIFY_T2(NOTIFY_RESPONSE_BLOCK_BLINKS, handle_response_block_blinks)
 END_INVOKE_MAP2()

9. Check what motivation behind removing NOTIFY_REQUEST_GET_OBJECTS, NOTIFY_RESPONSE_GET_OBJECTS and introducing NOTIFY_REQUEST_GET_TXS ?

10. Does loki offers any tests for blink vs non-blink conflict and rollback?

• Can't see such explicit tests but it might be tested somehow in core_tests/double_spend.cpp (need to check more detailed way)