node/vms/txs/mempool/mempool.go

// Copyright (C) 2019-2025, Lux Industries Inc. All rights reserved.
// See the file LICENSE for licensing terms.

package mempool

import (
	"context"
	"errors"
	"fmt"
	"sync"

	"github.com/luxfi/concurrent/lock"
	"github.com/luxfi/constants"
	"github.com/luxfi/container/linked"
	"github.com/luxfi/container/setmap"
	"github.com/luxfi/ids"
	"github.com/luxfi/math/set"
	"github.com/luxfi/node/cache/lru"
	"github.com/luxfi/vm"
)

const (
	// MaxTxSize is the maximum number of bytes a transaction can use to be
	// allowed into the mempool. Increased from 64 KiB to 2 MiB to support
	// large genesis configurations (e.g., ZOO chain genesis is ~613 KiB).
	MaxTxSize = 2 * constants.MiB

	// droppedTxIDsCacheSize is the maximum number of dropped txIDs to cache
	droppedTxIDsCacheSize = 64

	// maxMempoolSize is the maximum number of bytes allowed in the mempool
	maxMempoolSize = 64 * constants.MiB
)

var (
	ErrDuplicateTx          = errors.New("duplicate tx")
	ErrTxTooLarge           = errors.New("tx too large")
	ErrMempoolFull          = errors.New("mempool is full")
	ErrConflictsWithOtherTx = errors.New("tx conflicts with other tx")
	// ErrAdmissionRejected wraps a rejection emitted by an AdmissionVerifier
	// configured via NewWithAdmissionVerifier. The wrapped error carries the
	// verifier's specific reason (e.g. NIZK proof invalid, fee bid below
	// floor, budget meter exhausted).
	ErrAdmissionRejected = errors.New("tx admission rejected")
)

type Tx interface {
	InputIDs() set.Set[ids.ID]
	ID() ids.ID
	Size() int
}

// AdmissionVerifier is an optional admission gate. When configured via
// NewWithAdmissionVerifier the mempool calls VerifyAdmit on every Add()
// after the cheap structural checks (duplicate / size / space / conflict)
// pass and before the tx is inserted. A non-nil return rejects the tx; the
// returned error is wrapped in ErrAdmissionRejected and recorded as the
// drop reason.
//
// Intended consumers: validators that admit encrypted-payload transactions
// (FHE ciphertext + NIZK proof of well-formedness) without decryption, per
// LP-066 / luxfi/precompile/fhe. The verifier runs signature verify + fee
// check + NIZK verify; the actual decryption never happens at admission
// time.
//
// VerifyAdmit MUST be safe to call without holding any mempool lock — the
// mempool holds its own write lock across Add() and the call is made from
// within that critical section. Implementations that need to do expensive
// work (NIZK verification) should not perform additional locking that
// could re-enter the mempool.
type AdmissionVerifier[T Tx] interface {
	VerifyAdmit(tx T) error
}

type Metrics interface {
	Update(numTxs, bytesAvailable int)
}

type Mempool[T Tx] interface {
	Add(tx T) error
	Get(txID ids.ID) (T, bool)
	// Remove [txs] and any conflicts of [txs] from the mempool.
	Remove(txs ...T)

	// Peek returns the oldest tx in the mempool.
	Peek() (tx T, exists bool)

	// Iterate iterates over the txs until f returns false
	Iterate(f func(tx T) bool)

	// Note: dropped txs are added to droppedTxIDs but are not evicted from
	// unissued decision/staker txs. This allows previously dropped txs to be
	// possibly reissued.
	MarkDropped(txID ids.ID, reason error)
	GetDropReason(txID ids.ID) error

	// Len returns the number of txs in the mempool.
	Len() int

	// WaitForEvent waits until there is at least one tx in the mempool.
	WaitForEvent(ctx context.Context) (vm.Message, error)
}

type mempool[T Tx] struct {
	lock           sync.RWMutex
	cond           *lock.Cond
	unissuedTxs    *linked.Hashmap[ids.ID, T]
	consumedUTXOs  *setmap.SetMap[ids.ID, ids.ID] // TxID -> Consumed UTXOs
	bytesAvailable int
	droppedTxIDs   *lru.Cache[ids.ID, error] // TxID -> Verification error

	metrics Metrics

	// admissionVerifier is nil for the default New constructor (preserving
	// the existing admission policy of signature/fee verification happening
	// at the caller). When non-nil it is invoked from Add() after the cheap
	// checks pass.
	admissionVerifier AdmissionVerifier[T]
}

func New[T Tx](
	metrics Metrics,
) *mempool[T] {
	return NewWithAdmissionVerifier[T](metrics, nil)
}

// NewWithAdmissionVerifier constructs a mempool that runs verifier.VerifyAdmit
// on every Add() after the duplicate / size / space / conflict checks
// succeed. A nil verifier is equivalent to New — no admission gate is
// installed and behavior is byte-identical to the prior API.
//
// This is the entry point for encrypted-payload tx pools per luxfi/node#115:
// validators construct a mempool partition with a verifier that runs
// signature + fee + NIZK checks (sourced from luxfi/precompile/fhe) so
// ciphertexts are admitted without decryption.
func NewWithAdmissionVerifier[T Tx](
	metrics Metrics,
	verifier AdmissionVerifier[T],
) *mempool[T] {
	m := &mempool[T]{
		unissuedTxs:       linked.NewHashmap[ids.ID, T](),
		consumedUTXOs:     setmap.New[ids.ID, ids.ID](),
		bytesAvailable:    maxMempoolSize,
		droppedTxIDs:      lru.NewCache[ids.ID, error](droppedTxIDsCacheSize),
		metrics:           metrics,
		admissionVerifier: verifier,
	}
	m.cond = lock.NewCond(&m.lock)
	m.updateMetrics()
	return m
}

func (m *mempool[T]) updateMetrics() {
	m.metrics.Update(m.unissuedTxs.Len(), m.bytesAvailable)
}

func (m *mempool[T]) Add(tx T) error {
	txID := tx.ID()

	m.lock.Lock()
	defer m.lock.Unlock()

	if _, ok := m.unissuedTxs.Get(txID); ok {
		return fmt.Errorf("%w: %s", ErrDuplicateTx, txID)
	}

	txSize := tx.Size()
	if txSize > MaxTxSize {
		return fmt.Errorf("%w: %s size (%d) > max size (%d)",
			ErrTxTooLarge,
			txID,
			txSize,
			MaxTxSize,
		)
	}
	if txSize > m.bytesAvailable {
		return fmt.Errorf("%w: %s size (%d) > available space (%d)",
			ErrMempoolFull,
			txID,
			txSize,
			m.bytesAvailable,
		)
	}

	inputs := tx.InputIDs()
	if m.consumedUTXOs.HasOverlap(inputs) {
		return fmt.Errorf("%w: %s", ErrConflictsWithOtherTx, txID)
	}

	// Admission gate runs last among Add() checks: it is the most expensive
	// (e.g. NIZK verify for encrypted-payload txs per LP-066). All cheap
	// rejects have fired by this point so verification cost is only paid on
	// txs that pass structural admission.
	if m.admissionVerifier != nil {
		if verr := m.admissionVerifier.VerifyAdmit(tx); verr != nil {
			wrapped := fmt.Errorf("%w: %s: %w", ErrAdmissionRejected, txID, verr)
			// Record the drop reason so downstream propagation / inspection
			// surfaces match the existing dropped-tx tracking contract.
			m.droppedTxIDs.Put(txID, wrapped)
			return wrapped
		}
	}

	m.bytesAvailable -= txSize
	m.unissuedTxs.Put(txID, tx)
	m.updateMetrics()

	// Mark these UTXOs as consumed in the mempool
	m.consumedUTXOs.Put(txID, inputs)

	// An added tx must not be marked as dropped.
	m.droppedTxIDs.Evict(txID)
	m.cond.Broadcast()
	return nil
}

func (m *mempool[T]) Get(txID ids.ID) (T, bool) {
	m.lock.RLock()
	defer m.lock.RUnlock()

	return m.unissuedTxs.Get(txID)
}

func (m *mempool[T]) Remove(txs ...T) {
	m.lock.Lock()
	defer m.lock.Unlock()

	for _, tx := range txs {
		txID := tx.ID()
		// If the transaction is in the mempool, remove it.
		if _, ok := m.consumedUTXOs.DeleteKey(txID); ok {
			m.unissuedTxs.Delete(txID)
			m.bytesAvailable += tx.Size()
			continue
		}

		// If the transaction isn't in the mempool, remove any conflicts it has.
		inputs := tx.InputIDs()
		for _, removed := range m.consumedUTXOs.DeleteOverlapping(inputs) {
			tx, _ := m.unissuedTxs.Get(removed.Key)
			m.unissuedTxs.Delete(removed.Key)
			m.bytesAvailable += tx.Size()
		}
	}
	m.updateMetrics()
}

func (m *mempool[T]) Peek() (T, bool) {
	m.lock.RLock()
	defer m.lock.RUnlock()

	_, tx, exists := m.unissuedTxs.Oldest()
	return tx, exists
}

func (m *mempool[T]) Iterate(f func(T) bool) {
	m.lock.RLock()
	defer m.lock.RUnlock()

	it := m.unissuedTxs.NewIterator()
	for it.Next() {
		if !f(it.Value()) {
			return
		}
	}
}

func (m *mempool[_]) MarkDropped(txID ids.ID, reason error) {
	if errors.Is(reason, ErrMempoolFull) {
		return
	}

	m.lock.RLock()
	defer m.lock.RUnlock()

	if _, ok := m.unissuedTxs.Get(txID); ok {
		return
	}

	m.droppedTxIDs.Put(txID, reason)
}

func (m *mempool[_]) GetDropReason(txID ids.ID) error {
	err, _ := m.droppedTxIDs.Get(txID)
	return err
}

func (m *mempool[_]) Len() int {
	m.lock.RLock()
	defer m.lock.RUnlock()

	return m.unissuedTxs.Len()
}

func (m *mempool[_]) WaitForEvent(ctx context.Context) (vm.Message, error) {
	m.lock.Lock()
	defer m.lock.Unlock()

	for m.unissuedTxs.Len() == 0 {
		if err := m.cond.Wait(ctx); err != nil {
			return vm.Message{}, err
		}
	}
	return vm.Message{Type: vm.PendingTxs}, nil
}