Tracing byzantine faults in ad hoc networks

Let R = (s=x₀,x₁,…,x_t,d) be the routing path, where s and d are the source and destination nodes. The sending phase is essentially the same as that of the AODV protocol, except that we require that the source s and each intermediate node x_i set a timer_i to a time based on their distance from the destination.

On the upstream phase

body_s := (id_s,id_d,counter_d,data),h_Ksd(body_s);

timer_i := 2(t-i);

Where  is an upper bound on the time allocated for each hop.

On the downstream phase:

body_d := (id_s,id_d,counter_d),h_Ksd(body_d);

If a node x_i does not receive an acknowledgement, body_d, or a valid fault_report in the allocated time, timer_i, then the node x_i reports the fault to the source node s by sending an authenticated fault_report:

fault_report_i:= (id_s,id_d,counter_d,id_xi), sig_Ki(fault_report_i)