Busca de Caminho

Como a origem escolhe uma rota provável, calcula fees e CLTV, e aprende com falhas

Lightning · Técnico

Com o grafo de canais em mãos, a origem ainda não tem uma resposta pronta. Ela sabe quais canais públicos foram anunciados, quais políticas de roteamento estão no channel_update e quais short_channel_id apontam para funding outputs on-chain. Mas ela não sabe a informação mais importante para entregar o pagamento: quanto saldo existe naquela direção agora.

A busca de caminho é 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 especificação não manda usar um algoritmo único. Os BOLTs definem os dados e as regras que precisam ser respeitados; a escolha entre rotas é uma heurística de implementação.

As fontes primárias desta página são a BOLT 7 para políticas 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 próximo salto. Na Lightning, a origem escolhe a rota inteira. Isso é necessário porque a origem precisa construir a cebola antes de enviar o primeiro update_add_htlc. Cada hop recebe apenas seu próprio payload: quanto encaminhar, para qual canal e com qual CLTV.

Uma rota candidata tem esta forma:

Alice -> Bob -> Carol -> Dina

Alice é a pagadora. Dina é a recebedora. Bob e Carol são 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 várias alternativas até o destino.
A busca é feita sobre uma visão local e incompleta do grafo.
Descrição longa do diagrama

O diagrama mostra um grafo de nós Lightning. A origem aparece em um lado e o destino em outro. Várias rotas possíveis ligam os dois. Uma rota está destacada, indicando que a origem escolheu todos os saltos antes de enviar o pagamento.

Entradas da busca

A busca combina dados públicos, dados privados e memória local. Nenhum desses conjuntos é 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, política direcional, flag disabled e timestamps.
Estado local canais do próprio nó, saldo local conhecido, peers conectados, limites do canal, HTLCs pendentes e histórico de falhas.
Memória de tentativas penalidades e probabilidades aprendidas com falhas onion, pagamentos bem-sucedidos, probing e informação expirada.

A invoice diz o que pagar. O gossip diz por onde talvez seja possível passar. O estado local diz por onde você consegue sair agora. O histórico de tentativas diz quais caminhos parecem ruins ou bons neste momento.

BOLT vs. heurística

Esta separação evita muita confusão:

Por isso, dizer "a Lightning usa Dijkstra" é uma simplificação. Muitas implementações usam uma busca de menor custo sobre um grafo, frequentemente calculada de trás para frente porque fees e CLTV se acumulam a partir do destino. Mas a rede não exige um algoritmo específico.

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

1. identificar destino, valor, payment_secret e CLTV final mínimo
2. adicionar routing hints privados, se a invoice tiver campo r
3. filtrar arestas por direção, disabled, min/max HTLC e features
4. calcular de trás 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 preferência 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 não pode ser usado cru. A carteira primeiro transforma o grafo público em um conjunto de arestas candidatas para aquele pagamento. O filtro precisa respeitar a direção exata do canal, porque channel_update é direcional.

Filtros comuns antes de tentar uma rota
Verificação Por que importa
Direção do canal A política usada é a do sentido exato do encaminhamento. Um canal público tem duas direções possíveis.
channel_flags O bit de direção identifica qual node id assinou aquele update; o bit disabled remove aquela direção da rota.
htlc_minimum_msat O HTLC encaminhado precisa ser maior ou igual ao mínimo anunciado para aquela direção.
htlc_maximum_msat Se anunciado, limita o maior HTLC aceito por aquela direção; não 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 mínima entre o HTLC de entrada e o HTLC de saída daquele hop.
features O pagador precisa evitar rotas que exigem recursos que ele, os hops ou o recebedor não suportam.

O short_channel_id conecta a aresta do grafo a uma funding output na blockchain: altura do bloco, índice da transação e índice da saída. Essa ligação prova que o canal público existiu, mas não prova que a saída ainda tem uma distribuição de saldos favorável para o pagamento. Para entender essa ponte on-chain, revise UTXO, saída de transação e Short Channel ID.

Fees de roteamento

A taxa Lightning de um hop não é a mesma coisa que a taxa de minerador de uma transação Bitcoin. A taxa on-chain paga espaço em bloco. A taxa Lightning remunera um nó intermediário por bloquear liquidez e assumir risco operacional ao encaminhar HTLCs.

Na política anunciada por channel_update, a fórmula é:

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

O detalhe importante é o sentido do cálculo. Para saber quanto Alice deve enviar ao primeiro hop, ela começa pelo valor que Dina precisa receber e anda para trás. Cada hop cobra taxa sobre o valor que ele vai encaminhar ao próximo hop.

Exemplo: pagamento final de 100.000 msat
Direção 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 diferença de 1.530 msat é 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 mínimo, normalmente pelo campo c de BOLT 11 ou pelo valor padrão quando ele não aparece. Cada hop intermediário acrescenta seu cltv_expiry_delta. Assim como as fees, o CLTV é calculado de trás 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 aceitável para os hops, mas também prende liquidez por mais tempo quando o pagamento fica pendente ou falha tarde. Por isso, muitas carteiras colocam um custo de tempo na função de custo, além da taxa em msat.

Há ainda uma técnica de privacidade chamada shadow routing: a origem adiciona um CLTV extra (e, às vezes, uma folga de taxa) além do destino, como se houvesse mais hops depois do recebedor real. Isso dificulta que os hops intermediários deduzam, pelo CLTV que veem, a que distância estão do fim da rota. É uma escolha de implementação, não uma exigência do protocolo.

Liquidez local e remota

Capacidade do canal não é liquidez disponível naquela direção. Se um canal tem capacidade de 1.000.000 sats, isso não diz se há 200.000 sats do lado certo para encaminhar agora.

Para um canal entre Alice e Bob:

Essa é a razão de a busca ser probabilística. O pagador conhece bem seus próprios canais, mas a parte remota do caminho é uma estimativa. O htlc_maximum_msat anunciado pode impedir um pagamento grande demais, mas não 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 é didática: calcula a parte determinística da política anunciada, mas não simula liquidez oculta, falhas onion, concorrência, privacidade ou penalidades de implementação.

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 informação é 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 não viram verdade global sobre a rede.
Descrição longa do diagrama

O diagrama mostra uma origem tentando uma primeira rota. Um dos canais intermediários está 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 direção não conseguiu encaminhar agora. Pode indicar falta de liquidez, canal indisponível ou estado temporário.
amount_below_minimum O valor ficou abaixo do htlc_minimum_msat anunciado ou esperado pelo hop.
fee_insufficient O HTLC de entrada não pagou a taxa exigida para aquela direção.
incorrect_cltv_expiry O CLTV oferecido não bate com a política do hop para o próximo salto.
expiry_too_soon O HTLC chegaria perto demais do vencimento para ser seguro encaminhar.
channel_disabled A direção foi marcada como desabilitada em channel_update.
unknown_next_peer O hop não conhece ou não consegue usar o próximo peer indicado.
incorrect_or_unknown_payment_details O destino rejeitou o pagamento, por invoice desconhecida, valor incorreto, segredo incorreto ou expiração.

Uma carteira bem comportada não tenta infinitamente. Ela limita tentativas, evita repetir a mesma falha, respeita expiração da invoice, evita CLTV inseguro e não assume que um erro antigo ainda vale depois de muitos blocos ou depois de políticas de canal mudarem.

Falhas que trazem a política nova

Nem toda falha é apenas "não deu certo". O byte mais alto do failure_code é um conjunto de flags que dizem à origem como reagir:

Flags do byte alto de failure_code
Flag Nome Significado
0x8000 BADONION A cebola recebida do peer anterior não pôde ser interpretada.
0x4000 PERM Falha permanente: a origem não deve re-tentar aquela mesma aresta.
0x2000 NODE A falha é do nó, não de um canal específico dele.
0x1000 UPDATE A falha carrega um channel_update com a política corrigida para a origem re-tentar.

O flag UPDATE é o mais útil para a busca. Quando um hop rejeita o HTLC porque a taxa ou o CLTV não bateram com a política dele, a falha carrega um channel_update embutido com a política atual daquela direção. A origem lê esse update, corrige o cálculo e re-tenta pela mesma rota, sem precisar esperar o gossip propagar a mudança. Algumas dessas falhas ainda trazem campos extras que explicam o motivo exato:

Falhas com flag UPDATE e o que carregam
Falha Dados embutidos
temporary_channel_failure channel_update
amount_below_minimum htlc_msat, channel_update
fee_insufficient htlc_msat, channel_update
incorrect_cltv_expiry cltv_expiry, channel_update
expiry_too_soon channel_update
channel_disabled disabled_flags, channel_update

Aplicar cegamente um channel_update vindo de uma falha é um vetor de fingerprinting: um hop malicioso poderia entregar políticas diferentes a alvos diferentes e depois observar o comportamento. Por isso as carteiras tratam esse update com cautela, e um nó que não quer anexar política define o campo len do channel_update como zero.

Probing

Probing é 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 técnica de vigilância, quando alguém tenta mapear saldos de canais de terceiros.

A Lightning não tem uma mensagem "me diga seu saldo". O probing explora efeitos colaterais: se um HTLC quase chega ao destino e falha de uma forma específica, 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 é uma faca de dois gumes. Ajuda pathfinding, mas prejudica privacidade, consome recursos de roteamento e pode revelar informação de liquidez. O payment_secret em BOLT 11 ajuda o destino a rejeitar tentativas que conhecem apenas o payment_hash, mas não elimina probing sobre hops intermediários.

Pagamentos em partes (MPP)

Quando uma rota única parece improvável ou cara demais, a origem pode dividir o pagamento em partes. Em MPP (Multi-Part Payments), vários HTLCs carregam o mesmo payment_hash e chegam ao mesmo recebedor com o mesmo payment_secret. O payload final também 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 pedaços enviados por rotas diferentes, todos com o mesmo payment_hash.
MPP reduz dependência de um único canal grande, mas aumenta complexidade de tentativa e correlação.
Descrição longa do diagrama

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

MPP não é magia de liquidez. A origem ainda precisa escolher tamanho de partes, rotas candidatas, CLTVs compatíveis 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.

Como o recebedor junta as partes

O que amarra as partes é um campo TLV no payload do último hop, o payment_data (tipo 8), presente em cada HTLC do conjunto:

payment_data (tipo 8):
  payment_secret : 32 bytes
  total_msat     : valor total esperado do pagamento inteiro

O recebedor agrupa por payment_hash em um HTLC set e segue regras estritas antes de liquidar:

Esse payment_secret é o que impede um hop intermediário de "sondar" o destino: sem o segredo correto vindo da invoice, tentativas de partes com valores variados são rejeitadas, então um atacante não consegue montar um pagamento válido só com o payment_hash público.

Modelos probabilísticos

Algumas explicações avançadas modelam roteamento como um processo probabilístico. Uma cadeia de Markov, por exemplo, pode representar nós como estados e canais como transições ponderadas por custo, sucesso esperado, capacidade anunciada, histórico e aleatoriedade. Isso ajuda a raciocinar sobre distribuição de caminhos, centralização e inferência de privacidade.

Mas isso é modelo analítico ou heurística, não parte obrigatória dos BOLTs. A rede não exige que uma carteira use cadeia de Markov. O cuidado técnico é não confundir uma ferramenta matemática para estudar escolhas de rota com uma regra de consenso ou uma mensagem de protocolo.

Sinais usados por heurísticas de rota
Sinal Efeito comum no score
Falha recente aumentar penalidade daquele canal, direção, par de nós ou intervalo de valor por algum tempo.
Sucesso recente aumentar a probabilidade de usar caminhos parecidos, sem assumir que a liquidez continua igual.
Canal próprio usar saldo local real e limites do canal, porque essa parte é conhecida pelo pagador.
Gossip antigo penalizar updates antigos ou políticas que mudam com frequência.
Valor alto preferir canais com maior capacidade, dividir em MPP ou aceitar mais tentativas.
Privacidade evitar sempre o caminho mais barato, randomizar entre rotas razoáveis 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.