Boa noite amigos!
No último versículo vimos a nona parte da tradução de “Advances In Distributed Security”. Hoje a décima
Carimbo de Tempo Seguro
Carimbo de tempo seguro é uma maneira de uma parte com um documento confidencial, ou duas ou mais partes enviando mensagens privadas, comprometerem entre si e com terceiros um carimbo de de data e hora não-forjável e não repudiável. Esse carimbo de tempo consiste em um local em ordem total consistindo nessa mensagem, na mensagem das outras partes, e em tiques de relógio. Esse comprometimento é alcançado sem que as partes tenham que revelar o conteúdo daquelas mensagens, a menos que ou até que sejam contestadas por provas a terceiros. (Mesmo assim, existem provas de conhecimento zero que permitem à parte provar que ela possui o documento correspondente ao carimbo de data e hora sem revelar o documento.)
Estes protocolos funcionam por usuários enviando um hash criptográfico (também conhecido como resumo de mensagem) de seu documento aos servidores de carimbo de tempo. Os servidores encadeiam as mensagens e os tiques de relógio por ordem de chegada. Servidores replicados podem quebrar ambiguidades na ordem de chegada com um protocolo tal qual o lançamento justo de moedas para conseguir uma ordem total justa.
O Problema dos Generais Bizantinos
Lamport criou uma estrutura teórica para segurança e tolerância a falhas em um serviço distribuído com o problema dos generais Bizantinos. Estes generais podem ser leais, seguindo ordens e repassando-as fielmente, ou podem ser traidores. O pior caso de comportamento dos generais traidores é modelado pelo truque sujo de mandar ordens contraditórias – por exemplo, dizer um general que a ordem é marchar e a outro general que a ordem é bater em retirada.
(Lamport queria significar a estória dos generais bizantinos como uma ilustração interessante e cartunista da teoria da tolerância a falhas contra a corrupção por adversários maliciosos, mas esse tipo de problema de fato ocorreu entre generais. Os generais do Império Bizantino não eram mais propensos a traição do que qualquer um de seus inimigos, como os persas ou os turcos. Se alguém é parcial em relação aos bizantinos, pode-se pensar nos generais iraquianos na atual guerra lá – os generais da Coalizão esperam que alguns generais iraquianos desertem e estão tentando inserir mensagens forjadas em sua rede de comunicações. Eles esperam que alguns generais sejam enganados para seguir essas ordens ilusórias.)
Existem N generais; um deles é o general comandante ou marechal de campo. Eles podem enviar e receber mensagens entre si. O problema dos generais bizantinos é desenvolver um protocolo para o general comandante enviar mensagens aos seus subordinados N-1 de forma que:
- Todos os generais leais obedeçam a mesma ordem, e
- Se o marechal de campo for leal, todo general leal obedece a ordem que ele envia.
O protocolo deve ser capaz de resistir até T generais traidores. No caso de um protocolo totalmente determinístico (não é permitido escolhas aleatórias ou criptográficas) o melhor que podemos fazer é tolerar T = piso(N/3) – 1 para uma rede síncrona. Para uma rede assíncrona e determinística nenhum traidor pode ser tolerado. [FLP85]
No entanto, o problema dos generais Bizantinos é facilmente resolvido por transmissões físicas não-traváveis. Não coincidentemente, resolver o problema de transmissão lógica na rede em que a transmissão física está ausente é muito similar, e tão difícil quanto, resolver o problema dos generais bizantinos.
O resultados pessimistas acima relacionados a T em redes determinísticas – e a ineficiência de protocolos que poderiam fornecer essas soluções fracas ao problema dos generais bizantinos – até recentemente desencorajaram pesquisadores e engenheiros de encontrar soluções práticas para garantir serviços distribuídos. No entanto, sob premissas apenas um pouco mais fracas – as de criptografia, de que precisamos apenas obter segurança com uma probabilidade muito alta – o acordo entre os generais bizantinos não só foi alcançado [Ben-Or] como alcançado eficientemente [Cachin]. O insight básico nestas soluções é que precisamos romper os laços em uma ordem parcial de Lamport de maneira imparcial com números aleatórios.
Esta foi a décima parte da tradução, no versículo seguinte a parte 11. Grande abraço!
