Repository: celestiaorg/celestia-app

Issue:
Adjust the estimated gas price during congestion when it's equal to the minimum
If the mempool is full of transactions that are all using the minimum gas price, the current estimation mechanism will return the minimum gas price regardless of the priority. We can fix this by applying an adjustment to the estimation given the priority to increase the inclusion probability.

Discussion:

Solution patch:
diff --git a/app/grpc/gasestimation/gas_estimator.go b/app/grpc/gasestimation/gas_estimator.go
index ed481fbf..3a529815 100644
--- a/app/grpc/gasestimation/gas_estimator.go
+++ b/app/grpc/gasestimation/gas_estimator.go
@@ -4,6 +4,7 @@ import (
 	"context"
 	"errors"
 	"fmt"
+	"math"
 	"sort"
 
 	tmclient "github.com/tendermint/tendermint/rpc/client"
@@ -126,6 +127,20 @@ func (s *gasEstimatorServer) estimateGasPrice(ctx context.Context, priority TxPr
 	return estimateGasPriceForTransactions(gasPrices, priority)
 }
 
+const (
+	// highPriorityGasAdjustmentRate is the percentage increase applied to the
+	// estimated gas price when the block is more than 70% full, i.e., gasPriceEstimationThreshold,
+	// but the gas prices are tightly clustered. This ensures that high-priority
+	// transactions still have a competitive fee to improve inclusion probability.
+	highPriorityGasAdjustmentRate = 1.3
+	// mediumPriorityGasAdjustmentRate similar to highPriorityGasAdjustmentRate but for
+	// the medium priority.
+	mediumPriorityGasAdjustmentRate = 1.1
+	// gasPriceAdjustmentThreshold the standard deviation threshold under which we
+	// apply the gas price adjustment.
+	gasPriceAdjustmentThreshold = 0.001
+)
+
 // estimateGasPriceForTransactions takes a list of transactions and priority
 // and returns a gas price estimation.
 // The priority sets the estimation as follows:
@@ -133,14 +148,24 @@ func (s *gasEstimatorServer) estimateGasPrice(ctx context.Context, priority TxPr
 // - Medium Priority: The gas price is the median price of the all gas prices in the mempool.
 // - Low Priority: The gas price is the median price of the bottom 10% of gas prices in the mempool.
 // - Unspecified Priority (default): This is equivalent to the Medium priority, using the median price of all gas prices in the mempool.
+// If the list of gas prices has a standard deviation < gasPriceAdjustmentThreshold, meaning the gas price values are tightly clustered,
+// an increase of 30% and 10% will be added for high and medium priority respectively.
 // More information can be found in ADR-023.
 func estimateGasPriceForTransactions(gasPrices []float64, priority TxPriority) (float64, error) {
 	if len(gasPrices) == 0 {
 		return 0, errors.New("empty gas prices list")
 	}
+	stDev := StandardDeviation(Mean(gasPrices), gasPrices)
 	switch priority {
-	case TxPriority_TX_PRIORITY_UNSPECIFIED:
-		return Median(gasPrices)
+	case TxPriority_TX_PRIORITY_MEDIUM, TxPriority_TX_PRIORITY_UNSPECIFIED:
+		estimation, err := Median(gasPrices)
+		if err != nil {
+			return 0, err
+		}
+		if stDev < gasPriceAdjustmentThreshold {
+			return estimation * mediumPriorityGasAdjustmentRate, nil
+		}
+		return estimation, nil
 	case TxPriority_TX_PRIORITY_LOW:
 		bottom10PercentIndex := len(gasPrices) * 10 / 100
 		if bottom10PercentIndex == 0 {
@@ -148,10 +173,15 @@ func estimateGasPriceForTransactions(gasPrices []float64, priority TxPriority) (
 			bottom10PercentIndex = 1
 		}
 		return Median(gasPrices[:bottom10PercentIndex])
-	case TxPriority_TX_PRIORITY_MEDIUM:
-		return Median(gasPrices)
 	case TxPriority_TX_PRIORITY_HIGH:
-		return Median(gasPrices[len(gasPrices)*90/100:])
+		estimation, err := Median(gasPrices[len(gasPrices)*90/100:])
+		if err != nil {
+			return 0, err
+		}
+		if stDev < gasPriceAdjustmentThreshold {
+			return estimation * highPriorityGasAdjustmentRate, nil
+		}
+		return estimation, nil
 	default:
 		return 0, fmt.Errorf("unknown priority: %d", priority)
 	}
@@ -221,3 +251,29 @@ func Median(gasPrices []float64) (float64, error) {
 	mid2 := gasPrices[n/2]
 	return (mid1 + mid2) / 2.0, nil
 }
+
+// Mean calculates the mean value of the provided gas prices.
+func Mean(gasPrices []float64) float64 {
+	if len(gasPrices) == 0 {
+		return 0
+	}
+	sum := 0.0
+	for _, gasPrice := range gasPrices {
+		sum += gasPrice
+	}
+	return sum / float64(len(gasPrices))
+}
+
+// StandardDeviation calculates the standard deviation of the provided gas prices.
+func StandardDeviation(meanGasPrice float64, gasPrices []float64) float64 {
+	if len(gasPrices) < 2 {
+		return 0
+	}
+	var variance float64
+	for _, gasPrice := range gasPrices {
+		diff := gasPrice - meanGasPrice
+		variance += diff * diff
+	}
+	variance /= float64(len(gasPrices))
+	return math.Sqrt(variance)
+}
diff --git a/docs/architecture/adr-023-gas-used-and-gas-price-estimation.md b/docs/architecture/adr-023-gas-used-and-gas-price-estimation.md
index 13532947..c19125db 100644
--- a/docs/architecture/adr-023-gas-used-and-gas-price-estimation.md
+++ b/docs/architecture/adr-023-gas-used-and-gas-price-estimation.md
@@ -48,6 +48,8 @@ There are multiple ways to have a gas price estimation for a priority level. Thi
 
 If the mempool has more transactions that it can fit in the next block, the estimation will be based on the top gas prices that can fit in a full block. Otherwise, if the mempool transactions can't fill more than 70% of the max block size, the minimum gas price will be returned.
 
+If the gas prices used for the estimation are tightly clustered, an increase of 30% and 10% will be added for high and medium priority respectively. Tightly clustered values are defined by the standard deviation of the elements being below the `gasPriceAdjustmentThreshold`. 
+
 The following is a basic implementation of the median that we can use:
 
 ```go



Test patch:
diff --git a/app/grpc/gasestimation/gas_estimator_test.go b/app/grpc/gasestimation/gas_estimator_test.go
index c6876dc7..ee3d603a 100644
--- a/app/grpc/gasestimation/gas_estimator_test.go
+++ b/app/grpc/gasestimation/gas_estimator_test.go
@@ -1,8 +1,12 @@
 package gasestimation
 
 import (
+	"math"
 	"testing"
 
+	"github.com/celestiaorg/celestia-app/v3/pkg/appconsts"
+	"github.com/tendermint/tendermint/libs/rand"
+
 	"github.com/stretchr/testify/require"
 
 	"github.com/stretchr/testify/assert"
@@ -105,6 +109,64 @@ func TestEstimateGasPriceForTransactions(t *testing.T) {
 	}
 }
 
+func TestEstimateClusteredGasPrices(t *testing.T) {
+	minGasPrice := appconsts.DefaultMinGasPrice * 2
+	maxGasPrice := minGasPrice + gasPriceAdjustmentThreshold
+	gasPrices := make([]float64, 20)
+	for i := range gasPrices {
+		randomGasPrice := minGasPrice + rand.Float64()*(maxGasPrice-minGasPrice)
+		gasPrices[i] = randomGasPrice
+	}
+	medianGasPrice, err := Median(gasPrices)
+	require.NoError(t, err)
+	medianGasPrice *= mediumPriorityGasAdjustmentRate
+	bottomMedian, err := Median(gasPrices[:len(gasPrices)*10/100])
+	require.NoError(t, err)
+	topMedian, err := Median(gasPrices[len(gasPrices)*90/100:])
+	require.NoError(t, err)
+	topMedian *= highPriorityGasAdjustmentRate
+
+	tests := []struct {
+		name     string
+		priority TxPriority
+		want     float64
+		wantErr  bool
+	}{
+		{
+			name:     "NONE -> same as MEDIUM (median)",
+			priority: TxPriority_TX_PRIORITY_UNSPECIFIED,
+			want:     medianGasPrice,
+		},
+		{
+			name:     "LOW -> bottom 10% median",
+			priority: TxPriority_TX_PRIORITY_LOW,
+			want:     bottomMedian,
+		},
+		{
+			name:     "MEDIUM -> median",
+			priority: TxPriority_TX_PRIORITY_MEDIUM,
+			want:     medianGasPrice,
+		},
+		{
+			name:     "HIGH -> top 10% median",
+			priority: TxPriority_TX_PRIORITY_HIGH,
+			want:     topMedian,
+		},
+	}
+
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			got, err := estimateGasPriceForTransactions(gasPrices, tt.priority)
+			if tt.wantErr {
+				assert.Error(t, err)
+			} else {
+				assert.NoError(t, err)
+				assert.Equal(t, tt.want, got)
+			}
+		})
+	}
+}
+
 func TestEstimateGasPriceSmallList(t *testing.T) {
 	gasPrices := []float64{10, 20, 30, 40, 50, 60}
 	bottomMedian, err := Median(gasPrices[:1])
@@ -114,3 +176,82 @@ func TestEstimateGasPriceSmallList(t *testing.T) {
 	assert.NoError(t, err)
 	assert.Equal(t, got, bottomMedian)
 }
+
+func TestMean(t *testing.T) {
+	tests := []struct {
+		name      string
+		gasPrices []float64
+		want      float64
+	}{
+		{
+			name:      "Empty slice",
+			gasPrices: []float64{},
+			want:      0,
+		},
+		{
+			name:      "Single element",
+			gasPrices: []float64{10},
+			want:      10,
+		},
+		{
+			name:      "Multiple elements",
+			gasPrices: []float64{1, 2, 3, 4, 5},
+			want:      3,
+		},
+		{
+			name:      "Mixed floats",
+			gasPrices: []float64{1.5, 2.5, 3.5},
+			want:      2.5,
+		},
+	}
+
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			got := Mean(tt.gasPrices)
+			if got != tt.want {
+				t.Errorf("mean(%v) = %v, want %v", tt.gasPrices, got, tt.want)
+			}
+		})
+	}
+}
+
+func TestStandardDeviation(t *testing.T) {
+	tests := []struct {
+		name      string
+		gasPrices []float64
+		want      float64
+	}{
+		{
+			name:      "Empty slice",
+			gasPrices: []float64{},
+			want:      0,
+		},
+		{
+			name:      "Single element",
+			gasPrices: []float64{10},
+			want:      0,
+		},
+		{
+			name:      "Multiple elements",
+			gasPrices: []float64{10, 20, 30, 40, 50},
+			// Variance = 200, stdev ~ 14.142135...
+			want: 14.142135623730951,
+		},
+		{
+			name:      "Identical elements",
+			gasPrices: []float64{5, 5, 5, 5},
+			want:      0,
+		},
+	}
+
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			meanVal := Mean(tt.gasPrices)
+			got := StandardDeviation(meanVal, tt.gasPrices)
+			// We'll do a tolerance check for floating-point comparisons.
+			if math.Abs(got-tt.want) > 1e-9 {
+				t.Errorf("stdDev(%v) = %v, want %v", tt.gasPrices, got, tt.want)
+			}
+		})
+	}
+}