This is, probably, Halochoh Le'Moshe, but not from Sinai, a bit earlier. When God sends Moses to lead the Hebrews out of Egypt (Exodus.3.10 and on), He starts with reasoning, but when Moses continues to refuse, He teaches some handy tricks Moses can use to convince the people that he's the one. This pattern perfectly mimics the dynamics of R' Eliezer's argument with the Sages:
At first, He reasons:
"Come, therefore, I will send you to Pharaoh, and you shall free My people, the Israelites, from Egypt. But Moses said to God, “Who am I that I should go to Pharaoh and free the Israelites from Egypt?” And He said, “I will be with you; that shall be your sign that it was I who sent you. And when you have freed the people from Egypt, you shall worship God at this mountain. Moses said to God, “When I come to the Israelites and say to them, ‘The God of your fathers has sent me to you,’ and they ask me, ‘What is His name?’ what shall I say to them?” And God said to Moses, “Ehyeh-Asher-Ehyeh.” He continued, “Thus shall you say to the Israelites, ‘Ehyeh sent me to you.’... They will listen to you;”
But Moses foresees the reaction of his people and the fact that reasoning alone will not do the job and continues to demand further assurances:
But Moses spoke up and said, “What if they do not believe me and do not listen to me, but say: The LORD did not appear to you?” The LORD said to him, “What is that in your hand?” And he replied, “A rod.” He said, “Cast it on the ground.” He cast it on the ground and it became a snake, and Moses recoiled from it. Then the LORD said to Moses, “Put out your hand and grasp it by the tail”—he put out his hand and seized it, and it became a rod in his hand— “that they may believe that the LORD, the God of their fathers, the God of Abraham, the God of Isaac, and the God of Jacob, did appear to you.” The LORD said to him further, “Put your hand into your bosom.” He put his hand into his bosom; and when he took it out, his hand was encrusted with snowy scales! And He said, “Put your hand back into your bosom.”—He put his hand back into his bosom; and when he took it out of his bosom, there it was again like the rest of his body.— “And if they do not believe you or pay heed to the first sign, they will believe the second.
So the very first encounter with God has taught Moses that witchcraft does work in proving God's points. He kept using it many times after the receiving of the Torah also, for example, in Korakh's case:
"And Moses said, “By this, you shall know that it was the LORD who sent me to do all these things; that they are not of my own devising: if these men die as all men do, if their lot be the common fate of all mankind, it was not the LORD who sent me. But if the LORD brings about something unheard-of, so that the ground opens its mouth and swallows them up with all that belongs to them, and they go down alive into Sheol, you shall know that these men have spurned the LORD.” Numbers.16.28
Again, God's miracles prove Moses' righteousness.
I was thinking about the underlying mechanisms, and it might be based on the Biblical idea of a Prophet's truthfulness - the only way of telling a true prophet from a false one is to see his prophecies fulfill and especially most improbable ones and that shows that Hashem is with this person (later known as Ruah Hakodesh). So if a prophet says: "this tree will now move 400 cubits" and it moves, that proves his truthfulness.
Early Tannoyim traditionally relied on this prophetic tradition of appealing to miracles as proofs of their Ruach Hakodesh and therefore truthfulness, for example, the verse "כי מציון תצא תורה" was interpreted that the Halachah should come forth from the place of constant divine miracles (the Temple, see Avot.5.4 ). But R' Yehoshua promoted a more pragmatic idea, following the destruction of the Temple, of detaching from mysticism and divine guidance that accompanied the Jewish people for the last 1500 years (since Matan Torah) and sticking with human authorities (Nassi, majority of a gathering, etc).
Even nowadays, some prominent Sefardic AND Ashkenazi Rabbis are highly esteemed (especially in the eyes of low socioeconomic groups) for alleged miracles they perform, and their Halachic authority is maintained by the surrounding mysticism.
