# Random Oracles TODO: this section is poorly written, improve. In computer science, an *oracle* is a magic being that performs some task for us. Oracles have *many* uses, one of them is to assume we can perform some computation without bothering ourselves with the details. Instead, we reason in an alternate universe where a magical oracle does the computation for us. This way we can *divide the work* with someone working to *implement* a random oracle. *hash functions* such as SHA-256, Keccak, or k-HeavyHash are an implementation of a certain kind of oracle called a *random oracle*. The random oracle model has a nice mathematical description that is oblivious to how the hash function is actually implemented. A random oracle *consistently* turn an arbitrary string $$s$$ to a *random, fixed length* string $$\mathsf{H}(s)$$. What does this all mean? *Fixed length* just means that $$\mathsf{H}(s)$$ is always the same length, regardless of $$s$$ or its length. Under the hood, we assume that $$s$$ is a strings of ones and zeros (but that shouldn't concern you), so we call the length *bits*. Proof-of-work typically uses hash functions with an output length of 256 bits. C*onsistency* and *randomness* mean that when the oracle responds to a string $$s$$, the oracle should respond to queries like this: * (consistency) if she was queried about the string $$s$$ before, respond with the same $$\mathsf{H}(s)$$ * (randomness) otherwise, respond with a *uniformly random 256-bit string* One key property of a random oracle is that it is *hard to invert*. If you have a string $$h$$ of appropriate length, and you an $$s$$ such that $$h=\mathsf{H}(s)$$, how would you go about finding it? This problem is called *inverting* $$\mathsf{H}$$ (in the point $$h$$). The only way to get information from the oracle is by making queries. But due to the randomness, if you query on some $$s$$, and get a response different than $$h$$, this tells you next to nothing. Yes, you know that $$s$$ is not the correct answer, but that's it. You haven't eliminated any single other possibility. The consequences are that the best way to solve the problem is by querying on different strings until you stumble backwards into one that gives the correct answer. Now, how long this should take? If the output length is $$n$$ bits, then there are $$2^n$$ possible outputs. Recall that the oracle always chooses the string *uniformly*. Hence, the probability a query produces the desired result is one in $$2^n$$. That is, it would take about $$2^n$$ attempts. At a trillion attempts per second, inverting a 256 bits hash function will take over three billion trillion trillion trillion trillion years. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://shai-deshe.gitbook.io/understanding-blockdags-and-ghostdag/supplementary-material/computer-science/page-3/random-oracles.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.