Busca de Caminho

Como a origem escolhe uma rota provavel, calcula fees e CLTV, e aprende com falhas

Lightning · Técnico

Com o grafo de canais em maos, a origem ainda nao tem uma resposta pronta. Ela sabe quais canais publicos foram anunciados, quais politicas de roteamento estao no channel_update e quais short_channel_id apontam para funding outputs on-chain. Mas ela nao sabe a informacao mais importante para entregar o pagamento: quanto saldo existe naquela direcao agora.

A busca de caminho e o processo de escolher uma rota, calcular o valor e o CLTV que cada hop deve receber, montar o pacote onion, tentar o pagamento e aprender com as falhas. A especificacao nao manda usar um algoritmo unico. Os BOLTs definem os dados e as regras que precisam ser respeitados; a escolha entre rotas e uma heuristica de implementacao.

As fontes primarias desta pagina sao a BOLT 7 para politicas de roteamento e gossip, a BOLT 4 para payloads e falhas onion, a BOLT 2 para HTLCs entre peers e a BOLT 11 para os dados vindos da invoice.

Conteúdo

Modelo mental

Na internet, cada roteador escolhe o proximo salto. Na Lightning, a origem escolhe a rota inteira. Isso e necessario porque a origem precisa construir a cebola antes de enviar o primeiro update_add_htlc. Cada hop recebe apenas seu proprio payload: quanto encaminhar, para qual canal e com qual CLTV.

Uma rota candidata tem esta forma:

Alice -> Bob -> Carol -> Dina

Alice e a pagadora. Dina e a recebedora. Bob e Carol sao hops de encaminhamento. Alice calcula quanto deve oferecer a Bob para que Bob consiga pagar Carol, Carol consiga pagar Dina, cada hop receba sua taxa e todos os CLTVs tenham folga suficiente.

A origem calcula a rota inteira sobre o grafo, escolhendo um caminho entre varias alternativas ate o destino.
A busca e feita sobre uma visao local e incompleta do grafo.
Descricao longa do diagrama

O diagrama mostra um grafo de nos Lightning. A origem aparece em um lado e o destino em outro. Varias rotas possiveis ligam os dois. Uma rota esta destacada, indicando que a origem escolheu todos os saltos antes de enviar o pagamento.

Entradas da busca

A busca combina dados publicos, dados privados e memoria local. Nenhum desses conjuntos e perfeito.

Fontes usadas para calcular uma rota
Fonte Dados usados
Invoice BOLT 11 valor, destino, payment_hash, payment_secret, min_final_cltv_expiry_delta, features e routing hints opcionais.
Grafo de gossip channel_announcement, channel_update, node_announcement, short_channel_id, politica direcional, flag disabled e timestamps.
Estado local canais do proprio no, saldo local conhecido, peers conectados, limites do canal, HTLCs pendentes e historico de falhas.
Memoria de tentativas penalidades e probabilidades aprendidas com falhas onion, pagamentos bem-sucedidos, probing e informacao expirada.

A invoice diz o que pagar. O gossip diz por onde talvez seja possivel passar. O estado local diz por onde voce consegue sair agora. O historico de tentativas diz quais caminhos parecem ruins ou bons neste momento.

BOLT vs. heuristica

Esta separacao evita muita confusao:

Por isso, dizer "a Lightning usa Dijkstra" e uma simplificacao. Muitas implementacoes usam uma busca de menor custo sobre um grafo, frequentemente calculada de tras para frente porque fees e CLTV se acumulam a partir do destino. Mas a rede nao exige um algoritmo especifico.

entrada:
- invoice BOLT 11
- grafo local de gossip
- altura atual do bloco
- estado dos canais locais
- historico de tentativas

1. identificar destino, valor, payment_secret e CLTV final minimo
2. adicionar routing hints privados, se a invoice tiver campo r
3. filtrar arestas por direcao, disabled, min/max HTLC e features
4. calcular de tras para frente:
   - valor que cada hop precisa receber
   - taxa cobrada por cada hop
   - CLTV de entrada exigido por cada hop
5. atribuir custo:
   - taxa total
   - custo de tempo por CLTV acumulado
   - penalidades por falha ou baixa probabilidade
   - custo de privacidade ou preferencia local
6. montar a onion route da melhor candidata
7. enviar update_add_htlc pelo primeiro canal
8. em caso de falha, atualizar penalidades e tentar outra rota

Grafo candidato

O grafo de gossip nao pode ser usado cru. A carteira primeiro transforma o grafo publico em um conjunto de arestas candidatas para aquele pagamento. O filtro precisa respeitar a direcao exata do canal, porque channel_update e direcional.

Filtros comuns antes de tentar uma rota
Verificacao Por que importa
Direcao do canal A politica usada e a do sentido exato do encaminhamento. Um canal publico tem duas direcoes possiveis.
channel_flags O bit de direcao identifica qual node id assinou aquele update; o bit disabled remove aquela direcao da rota.
htlc_minimum_msat O HTLC encaminhado precisa ser maior ou igual ao minimo anunciado para aquela direcao.
htlc_maximum_msat Se anunciado, limita o maior HTLC aceito por aquela direcao; nao prova liquidez real.
fee_base_msat e fee_proportional_millionths Definem a taxa que o hop cobra sobre o valor que ele vai encaminhar.
cltv_expiry_delta Define a folga minima entre o HTLC de entrada e o HTLC de saida daquele hop.
features O pagador precisa evitar rotas que exigem recursos que ele, os hops ou o recebedor nao suportam.

O short_channel_id conecta a aresta do grafo a uma funding output na blockchain: altura do bloco, indice da transacao e indice da saida. Essa ligacao prova que o canal publico existiu, mas nao prova que a saida ainda tem uma distribuicao de saldos favoravel para o pagamento. Para entender essa ponte on-chain, revise UTXO, saida de transacao e Short Channel ID.

Fees de roteamento

A taxa Lightning de um hop nao e a mesma coisa que a taxa de minerador de uma transacao Bitcoin. A taxa on-chain paga espaco em bloco. A taxa Lightning remunera um no intermediario por bloquear liquidez e assumir risco operacional ao encaminhar HTLCs.

Na politica anunciada por channel_update, a formula e:

fee_msat = fee_base_msat + floor(amount_to_forward_msat * fee_proportional_millionths / 1_000_000)

O detalhe importante e o sentido do calculo. Para saber quanto Alice deve enviar ao primeiro hop, ela comeca pelo valor que Dina precisa receber e anda para tras. Cada hop cobra taxa sobre o valor que ele vai encaminhar ao proximo hop.

Exemplo: pagamento final de 100.000 msat
Direcao Encaminha Base PPM Taxa Precisa receber
Carol -> Dina 100.000 1.000 100 1.010 101.010
Bob -> Carol 101.010 500 200 520 101.530 
altura atual = 800
valor final = 100.000 msat
min_final_cltv_expiry_delta = 18

Carol -> Dina:
  fee = 1.000 + floor(100.000 * 100 / 1.000.000)
  fee = 1.010 msat
  Carol precisa receber 101.010 msat
  CLTV de entrada de Carol = 818 + 40 = 858

Bob -> Carol:
  fee = 500 + floor(101.010 * 200 / 1.000.000)
  fee = 520 msat
  Bob precisa receber 101.530 msat
  CLTV de entrada de Bob = 858 + 80 = 938

Alice envia para Bob:
  amount_msat = 101.530
  cltv_expiry = 938
  taxa total = 1.530 msat

O valor enviado pelo primeiro hop inclui todas as taxas posteriores. No exemplo, Alice oferece 101.530 msat a Bob para que Dina receba 100.000 msat. A diferenca de 1.530 msat e a taxa total de roteamento.

CLTV acumulado

Cada HTLC tem um vencimento absoluto em altura de bloco. Esse prazo se conecta ao locktime do Bitcoin porque, se algo der errado e o canal fechar unilateralmente, as partes precisam de tempo para resolver HTLCs on-chain.

A invoice informa um delta final minimo, normalmente pelo campo c de BOLT 11 ou pelo valor padrao quando ele nao aparece. Cada hop intermediario acrescenta seu cltv_expiry_delta. Assim como as fees, o CLTV e calculado de tras para frente.

Exemplo de CLTV com altura atual 800
Etapa Delta aplicado CLTV resultante
Dina recebe min_final_cltv_expiry_delta = 18 800 + 18 = 818
Carol exige folga cltv_expiry_delta = 40 818 + 40 = 858
Bob exige folga cltv_expiry_delta = 80 858 + 80 = 938

Um CLTV maior aumenta a chance de a rota ser aceitavel para os hops, mas tambem prende liquidez por mais tempo quando o pagamento fica pendente ou falha tarde. Por isso, muitas carteiras colocam um custo de tempo na funcao de custo, alem da taxa em msat.

Liquidez local e remota

Capacidade do canal nao e liquidez disponivel naquela direcao. Se um canal tem capacidade de 1.000.000 sats, isso nao diz se ha 200.000 sats do lado certo para encaminhar agora.

Para um canal entre Alice e Bob:

Essa e a razao de a busca ser probabilistica. O pagador conhece bem seus proprios canais, mas a parte remota do caminho e uma estimativa. O htlc_maximum_msat anunciado pode impedir um pagamento grande demais, mas nao garante que o canal tenha saldo suficiente.

Ferramenta: Comparador de Rotas

A ferramenta abaixo compara rotas candidatas pela taxa total e pelo CLTV total. Ela e didatica: calcula a parte deterministica da politica anunciada, mas nao simula liquidez oculta, falhas onion, concorrencia, privacidade ou penalidades de implementacao.

Comparador de Rotas

Comparador de Rotas

Compare rotas candidatas por taxa, CLTV e uma penalidade local fictícia. É uma heurística didática, não prova liquidez real.

Uma por linha. Formato: Nome | base/ppm/cltv > base/ppm/cltv | penalidade_msat | probabilidade_0a100.

Resultado do comparador de rotas

Falhas e retries

A entrega real costuma ser um ciclo de tentativa e aprendizado. A origem monta a cebola, envia o HTLC pelo primeiro canal e espera o resultado. Se o pagamento falha, uma falha onion volta pelo caminho reverso. A origem tenta interpretar o erro sem esquecer que a informacao e parcial, temporal e pode ser imprecisa.

Ciclo de tentativa: a primeira rota falha por falta de saldo, o erro onion volta, e a carteira tenta outra rota.
Falhas alimentam o score local, mas nao viram verdade global sobre a rede.
Descricao longa do diagrama

O diagrama mostra uma origem tentando uma primeira rota. Um dos canais intermediarios esta marcado como sem liquidez suficiente. Uma seta de erro volta para a origem. Em seguida, a origem escolhe uma segunda rota diferente e tenta novamente.

Falhas onion que influenciam retries
Falha Como a origem pode interpretar
temporary_channel_failure O canal ou direcao nao conseguiu encaminhar agora. Pode indicar falta de liquidez, canal indisponivel ou estado temporario.
amount_below_minimum O valor ficou abaixo do htlc_minimum_msat anunciado ou esperado pelo hop.
fee_insufficient O HTLC de entrada nao pagou a taxa exigida para aquela direcao.
incorrect_cltv_expiry O CLTV oferecido nao bate com a politica do hop para o proximo salto.
expiry_too_soon O HTLC chegaria perto demais do vencimento para ser seguro encaminhar.
channel_disabled A direcao foi marcada como desabilitada em channel_update.
unknown_next_peer O hop nao conhece ou nao consegue usar o proximo peer indicado.
incorrect_or_unknown_payment_details O destino rejeitou o pagamento, por invoice desconhecida, valor incorreto, segredo incorreto ou expiracao.

Uma carteira bem comportada nao tenta infinitamente. Ela limita tentativas, evita repetir a mesma falha, respeita expiracao da invoice, evita CLTV inseguro e nao assume que um erro antigo ainda vale depois de muitos blocos ou depois de politicas de canal mudarem.

Probing

Probing e usar tentativas de pagamento para aprender algo sobre liquidez ou topologia. Pode aparecer de forma defensiva, quando a carteira testa caminhos para melhorar entrega, ou como tecnica de vigilancia, quando alguem tenta mapear saldos de canais de terceiros.

A Lightning nao tem uma mensagem "me diga seu saldo". O probing explora efeitos colaterais: se um HTLC quase chega ao destino e falha de uma forma especifica, a origem aprende que os canais anteriores provavelmente tinham liquidez suficiente para aquele valor. Se falha antes, a origem aprende um limite aproximado sobre algum trecho.

Probing e uma faca de dois gumes. Ajuda pathfinding, mas prejudica privacidade, consome recursos de roteamento e pode revelar informacao de liquidez. O payment_secret em BOLT 11 ajuda o destino a rejeitar tentativas que conhecem apenas o payment_hash, mas nao elimina probing sobre hops intermediarios.

Pagamentos em partes (MPP)

Quando uma rota unica parece improvavel ou cara demais, a origem pode dividir o pagamento em partes. Em MPP (Multi-Part Payments), varios HTLCs carregam o mesmo payment_hash e chegam ao mesmo recebedor com o mesmo payment_secret. O payload final tambem informa o valor total esperado, permitindo que o recebedor aceite o conjunto apenas quando as partes somam o total.

Pagamento multipartes: a origem divide o valor em pedacos enviados por rotas diferentes, todos com o mesmo payment_hash.
MPP reduz dependencia de um unico canal grande, mas aumenta complexidade de tentativa e correlacao.
Descricao longa do diagrama

O diagrama mostra uma origem dividindo um pagamento em tres partes. Cada parte segue uma rota diferente por canais distintos. Todas chegam ao mesmo destino e estao marcadas com o mesmo payment_hash. O destino so liquida quando a soma das partes atinge o valor total.

MPP nao e magia de liquidez. A origem ainda precisa escolher tamanho de partes, rotas candidatas, CLTVs compativeis e limite de tentativas. Partes pequenas demais podem bater em htlc_minimum_msat ou pagar muita taxa base. Partes grandes demais podem falhar por falta de saldo. E se uma parte falha, a carteira precisa decidir se tenta substituir aquela parte, reinicia tudo ou espera o timeout.

Modelos probabilisticos

Algumas explicacoes avancadas modelam roteamento como um processo probabilistico. Uma cadeia de Markov, por exemplo, pode representar nos como estados e canais como transicoes ponderadas por custo, sucesso esperado, capacidade anunciada, historico e aleatoriedade. Isso ajuda a raciocinar sobre distribuicao de caminhos, centralizacao e inferencia de privacidade.

Mas isso e modelo analitico ou heuristica, nao parte obrigatoria dos BOLTs. A rede nao exige que uma carteira use cadeia de Markov. O cuidado tecnico e nao confundir uma ferramenta matematica para estudar escolhas de rota com uma regra de consenso ou uma mensagem de protocolo.

Sinais usados por heuristicas de rota
Sinal Efeito comum no score
Falha recente aumentar penalidade daquele canal, direcao, par de nos ou intervalo de valor por algum tempo.
Sucesso recente aumentar a probabilidade de usar caminhos parecidos, sem assumir que a liquidez continua igual.
Canal proprio usar saldo local real e limites do canal, porque essa parte e conhecida pelo pagador.
Gossip antigo penalizar updates antigos ou politicas que mudam com frequencia.
Valor alto preferir canais com maior capacidade, dividir em MPP ou aceitar mais tentativas.
Privacidade evitar sempre o caminho mais barato, randomizar entre rotas razoaveis ou usar partes menores.

Armadilhas comuns

Resumo

Mapa de dependências conceituais

Antes de ler esta página

Depois desta página

Referências técnicas usadas

A seguir, voltamos ao ponto de partida do pagamento: a invoice BOLT 11, que informa destino, valor, payment_hash, payment_secret, CLTV final e dicas de rota.