ORDER AMENDING OPINION AND AMENDED OPINION

ORDER

The opinion filed February 26, 2007, is hereby amended. The following sentence at 478 F.3d 1033 is deleted:

The following sentence is substituted therefor:

With this amendment, Judges Reinhardt and Wardlaw vote to deny the petition for rehearing; Judge Trott votes to grant the petition for rehearing. General order 5.4(b) now applies.

OPINION

I

This case presents an important question that cuts to the heart of the Double Jeopardy Clause. It involves the right of a defendant to be free from repeated prosecutions in which the government retries him until it obtains a guilty verdict. The government was unable to convict Castillo-Basa the first time it tried him, for illegal reentry, in large part because its counsel failed to locate and present a crucial tape recording that was within its possession. To its surprise, the jury acquitted him. Now, having “found” the tape, the government seeks to prosecute Castillo-Basa again, this time for perjury committed in connection with the illegal reentry trial. The central issue at the second trial would be the same as it was at the first: was Castillo-Basa afforded a deportation hearing at which he was present?

The Double Jeopardy Clause requires the government to put on its strongest ease the first time; it forbids it to conduct a series of prosecutions, involving the same fundamental issues, in which it presents additional arguments and evidence at each iteration. Here, the government has already had its chance to prove that Castillo-Basa had a deportation hearing and that his testimony to the contrary was false. It failed, largely because it didn’t introduce the evidence that it had in its possession. Under the Double Jeopardy Clause, the government may not take a mulligan.

The outcome in this case follows directly from basic principles of collateral estoppel that are inherent in the Double Jeopardy Clause. See Ashe v. Swenson, 397 U.S. 436 , 90 S.Ct. 1189 , 25 L.Ed.2d 469 (1970). The only issue in dispute during Castillo-Basa’s trial for illegal reentry was whether he had been brought before an immigration judge and afforded a deportation hearing prior to his deportation. The ultimate question at issue in the second prosecution — for perjury — would be whether he testified falsely at the previous trial that he had not been present at a deportation hearing. When the jury acquitted Castillo-Basa of the illegal reentry offense, it decided, as the government acknowledged below, that a deportation hearing had not been held and, thus, that he had not been brought before an immigration judge for such a hearing. Accordingly, in rendering its verdict, the jury necessarily decided that Castillo-Basa’s testimony on the critical question of the deportation hearing was not false. The Double Jeopardy Clause bars the government from trying a second time to attempt to show that Castillo-Basa was afforded the hearing in question and that his testimony to the contrary was untruthful.

*894 II

On June 16, 2004, Buenaventura Castillo-Basa 1 was indicted for being a previously deported alien found in the United States in violation of 8 U.S.C. § 1326 (2000). Castillo-Basa’s counsel filed several pretrial motions, including a discovery motion requesting production of “all discovery listed below that is in the custody, control, care, or knowledge of any government agency.” The government informed the district court that an audio tape recording of Castillo-Basa’s deportation hearing existed but asserted that it could not locate the recording. The district court granted Castillo-Basa’s motion to compel discovery, specifically ordering the government to produce the tape recording of his deportation hearing. At another hearing some three months later, defense counsel stated that it was his understanding that there had not been a deportation hearing and reported that he had not received a tape of any hearing. He also suggested that Castillo-Basa may have been deported “in absentia,” without ever being brought before an immigration judge. The court again ordered the government to produce the tape recording, but the government failed to do so.

On November 23, 2004, defense counsel filed motions in limine, including a motion to “dismiss the indictment because there was no prior deportation.” On the day of the motions hearing, the defense filed a sworn declaration by Castillo-Basa stating that “[p]rior to May 2, 1996, I never appeared before an immigration judge” and “[pjrior to May 2, 1996, I was never given an immigration hearing.”

Castillo-Basa’s jury trial on the illegal reentry charge began on January 4, 2005. The government argued in its trial memorandum that a tape recording of the deportation was not required to prove the prior deportation. At trial, the government presented four witnesses: Border Patrol Agent Alberto Vallina, who testified that he found Castillo-Basa on June 4; Border Patrol Agent Dwain Holmes, who testified as custodian of Castillo-Basa’s “A” — or alien — file and through whom the government introduced the deportation order dated April 30, 1996, and the Warrant of Deportation; John Torres, a fingerprint expert who testified that the fingerprints of the person arrested on June 4, 2004 matched the fingerprints on the Warrant of Deportation dated May 2, 1996; and Immigration Enforcement Agent Eddie Jackson, whose signature appears on Castillo-Basa’s Warrant of Removal and who testified that he does not sign such a warrant until he observes an alien physically depart from the country. Castillo-Basa testified at trial that he was supposed to appear before an immigration judge on April 30, but that on the date of the hearing, no one came to get him out of his cell. He further testified that he had never come before an immigration judge and that he did not see any representative of the INS until May 2, when the agents took him from his cell to the Mexican border. 2

The defense theory throughout trial was that in order to be deported, an alien must be brought before an immigration judge, and that Castillo-Basa was never placed in front of a judge. In this vein, the defense requested a proposed “theory of the defense” instruction, which stated that in *895 order to find that Castillo-Basa was deported, the “government must prove beyond a reasonable doubt” that he “was physically present at a hearing before an immigration judge, and that the immigration judge ordered a final order of deportation against [him].” The district court rejected the proposed instruction, ruling that all that was required was that a hearing be held, not that Castillo-Basa be present.

Following the government’s case-in-chief and Castillo-Basa’s testimony, the district court denied Castillo-Basa’s motion to dismiss the indictment, finding by a preponderance of the evidence that a deportation hearing was held on April 30, 1996 and that Castillo-Basa was present. The court relied on the deportation order the government presented and on the “normal course” of deportation proceedings; it specifically found Castillo-Basa not to be credible. Nevertheless, in closing argument, Castillo-Basa’s attorney relied heavily on Castillo-Basa’s testimony and identified a number of gaps in the evidence the government had offered in its effort to prove that a deportation hearing had been held. Whether such a hearing was actually held was the only issue in dispute. The jury acquitted Castillo-Basa of the illegal reentry offense.

Less than two weeks after the jury returned its verdict, government agents located the tape recording of the April 30, 1996 deportation hearing. On the recording, Immigration Judge John Williams recited the names of individuals who were to have a deportation hearing that day; Castillo-Basa’s name was among those listed. An individual responded to the name “Bue-naventura Castillo-Basa” and admitted that he had been convicted of a crime in December 1985. The details provided by the responding individual regarding the 1985 conviction, such as the date of the offense and the amount of time served, correlate with the details of Castillo-Basa’s criminal history.

On April 27, 2005, a grand jury indicted Castillo-Basa on two counts of perjury, in violation of 18 U.S.C. § 1621 (2000), charging that he had submitted a false declaration in December 2004 and had falsely testified under oath at his criminal trial that he had never appeared before an immigration judge. Castillo-Basa filed a motion to dismiss the perjury indictment on the basis of “double jeopardy and collateral estoppel.” Following argument by the parties, the district court denied the motion. The district judge concluded that the issue of Castillo-Basa’s veracity with regard to whether he had attended a deportation hearing had not necessarily been decided in the first trial. He opined as well that Castillo-Basa had taken unfair advantage of the government’s inability to locate the tape recording by giving perjured testimony and, in so doing, had violated public policy and adversely affected the integrity of the judicial process. Castillo-Basa now appeals the denial of his motion to dismiss the indictment.

We have jurisdiction under 28 U.S.C. § 1291 (2000). See United States v. Cejas, 817 F.2d 595, 596 (9th Cir.1987) (providing for pretrial appeal under § 1291 of a motion to dismiss an indictment on the basis of collateral estoppel). We review the denial of a motion to dismiss an indictment based upon double jeopardy and collateral estoppel de novo. See United States v. Hickey, 367 F.3d 888 , 891 n. 3 (9th Cir.2004). “A district court’s factual findings, however, including those on which a denial may be based, are reviewed for clear error.” Id.

Ill

The issue before us is not whether Castillo-Basa committed perjury. Indeed, it would appear that he likely did. The *896 question, however, is whether the government is barred from trying him for that wrongful conduct a second time, after a jury has once decided that the testimony at issue was not false. We recognize that the Double Jeopardy Clause, like some of our other constitutional protections, may on occasion result in a guilty individual’s escaping punishment. That is a price, however, that we are willing to pay in order to preserve the basic liberties guaranteed by our Constitution. Were we to permit the government to try individuals repeatedly for the same offense, not only the guilty would ultimately be convicted. Rather, the innocent too would, sooner or later, encounter a jury that would be persuaded by the prosecutor’s arguments, especially as the cost — physical, emotional, and financial — of successive trials would frequently break the will and the spirit of the unjustly accused and leave them without the strength or ability to conduct a successful defense. In many cases the practical result would be that innocent persons, being without the resources to counter the unlimited force brought against them by the power of the state, would plead guilty, sometimes to lesser offenses, sometimes to a lesser number of serious charges. Such a system of justice would be intolerable in our society. Instead, we have wisely opted for a process in which an individual who has been adjudged not guilty may not be charged again for the same offense or held to answer more than once for conduct that the jury has decided he did not commit. Under our constitutional rule, once an issue, such as whether Castillo-Basa told the truth, has been determined in his favor, rightly or wrongly, by a jury, he may not again be compelled to defend himself on that issue. Such is the law under our Bill of Rights, as we will explain in greater detail below.

IV

The Double Jeopardy Clause does not only bar a second prosecution on the same charge of which a defendant has been previously acquitted (or convicted). It also prevents the government from seeking to prosecute a defendant on an issue that has been determined in the defendant’s favor in a prior prosecution, regardless of the particular offense involved in the earlier trial. Ashe v. Swenson, 397 U.S. at 443 , 90 S.Ct. 1189 . 3 In Ashe , the Supreme Court held that “[w]here a previous judgment of acquittal was based upon a general verdict,” and where a defendant seeks to invoke the collateral estoppel doctrine to bar a subsequent prosecution regarding a particular issue, a court is required “to ‘examine the record of a prior proceeding, taking into account the pleadings, evidence, charge, and other relevant matter, and conclude whether a rational jury could have grounded its verdict upon an issue other than that *897 which the defendant seeks to foreclose from consideration.’ ” Id. at 444 , 90 S.Ct. 1189 (quoting Daniel K. Mayers & Fletcher L. Yarbrough, Bix Vexari: New Trials and Successive Prosecutions, 74 Hahv. L. Rev. 1, 38-39 (I960)). Put another way, “[w]hen an issue of fact or law is actually litigated and determined by a final and valid judgment, and the determination is essential to the judgment, the determination is conclusive in a subsequent action between the parties, whether on the same or a different claim.” United States v. Hernandez, 572 F.2d 218, 220 (9th Cir.1978) (quoting Restatement (Seoond) of Judgments § 68 (Tent. Draft No. 1, Mar. 28, 1973)) (internal quotation marks omitted). 4

We have implemented Ashe’s charge through a three-step process:

Id. Application of these three steps to Castillo-Basa’s case makes clear beyond any doubt that collateral estoppel bars the government’s perjury prosecution.

Beginning with the first step, the central question in Castillo-Basa’s illegal reentry trial was whether he was afforded a deportation hearing at which he was present. He testified that he was not. Likewise, the ultimate issue in the perjury prosecution would be whether Castillo-Basa lied when he asserted that he was not afforded, and was not present at, any deportation hearing. The issues in the two trials are undoubtedly both “sufficiently similar” and “sufficiently material.” Id. That is more than enough to satisfy the first step of our collateral estoppel test. See, e.g., Richard, 892 F.2d at 762-63 (holding the first step satisfied where the issue in the first trial was whether the defendant knew that his passengers were illegal aliens and the ultimate issue in the second trial was whether he had perjured himself by testifying and offering a trip log to show that he had not known); Hernandez, 572 F.2d at 220-21 (holding the first step satisfied where the issue in the first trial was how many hours the defendant spent on a certain type of work and the ultimate issue in the second trial was whether he had perjured himself in giving his answer to that question).

The record is similarly clear that the issue whether Castillo-Basa was af *898 forded a deportation hearing at which he was present was “litigated” in the illegal reentry trial. Indeed, Castillo-Basa litigated little else besides this issue. The government does not appear to dispute this fact; instead, it seems to argue that Castillo-Basa cannot pass the second step of our collateral estoppel test because, at the illegal reentry trial, it lacked access to the tape of his deportation hearing, depriving it of a full and fair opportunity to litigate the issue. The government’s argument fails for two reasons. First, there is no rule, nor should there be, that an issue is not “litigated” for purposes of collateral estoppel simply because a party fails to present all of the evidence that it possesses or that it might have obtained in support of its case. That is, the second step of collateral estoppel does not require that an issue be “fully and fairly” litigated to the maximum extent possible, only that it be “litigated.” See Harris, 404 U.S. at 56-57, 92 S.Ct. 183 (reversing a state court’s ruling that a second trial was permissible, despite collateral estoppel, because a material issue had not been “fully litigated” after the trial court excluded important inculpatory evidence (internal quotation marks omitted)). Second, even if the United States had been deprived of the full opportunity to litigate the issue of Castillo-Basa’s deportation hearing, it was self-deprived. It simply failed to introduce the evidence it possessed. No one else was at fault. The government’s failure does not justify making an exception to the Double Jeopardy Clause.

The district court found only that the third step of our collateral estop-pel test — -the “necessarily decided” requirement — is not met. It is completely clear from the record, however, that the question of a deportation hearing and Castillo-Basa’s presence at it was “necessarily decided” in his illegal reentry trial, and that he is therefore entitled to prevail with regard to the third step. To obtain a conviction for illegal reentry, the government must prove that a defendant (1) is an alien (2) who was found in the United States without first obtaining valid permission, and (3) who had been previously deported. United States v. Barragan-Cepeda, 29 F.3d 1378, 1381 (9th Cir.1994). Castillo-Basa expressly admitted the first two elements but strongly contested the third.

To prove previous deportation-— the third element and the only one in dispute at Castillo-Basa’s trial- — the district court instructed the jury that the government must establish “[(1)] that a deportation proceeding occurred as to [the] defendant and as a result, [(2)] a warrant of deportation was issued and [(3)] executed by the removal of the defendant from the United States.” Once again, Castillo-Basa conceded two of these sub-elements- — -the second and third — and rested his entire case on his denial of the first, testifying that he had not been afforded, or been present at, a deportation hearing. Given Castillo-Basa’s concessions, the “single rationally conceivable” basis on which the jury could have acquitted him, see Ashe, 397 U.S. at 445 , 90 S.Ct. 1189 , was that no deportation proceeding had occurred with respect to him. Further, as we explain below, the jury’s decision necessarily entailed a determination that Castillo-Basa was not present at any such hearing. 5 The jury having so determined, collateral estoppel bars the prosecution of *899 Castillo-Basa at a second trial, for perjury, on the basis of his testimony as to facts that the jury found to be true.

The conclusion that collateral es-toppel applies is required by our prior decisions as well as by the Constitution. In United States v. Hernandez, a case in which the defendant’s testimony “was part of his defense and ... had to be weighed by the jury,” and in which his testimony conflicted with the government’s account of events, we held that “[t]he court was required to resolve the conflicting explanations as part of its decision upon the motion for judgment of acquittal” and thus “ ‘necessarily’ had to pass upon the truthfulness of his account.” 572 F.2d at 222 . Therefore, we concluded, double jeopardy barred a subsequent prosecution for perjury. Id. at 219 . The government attempts to distinguish cases such as Hernandez and United States v. Sarno, 596 F.2d 404, 408 (9th Cir.1979) — in which we held that collateral estoppel barred a second prosecution for perjury — by arguing that in those cases, “a prior jury verdict necessarily decided the issue of the testifying defendant’s credibility ... because the defendant’s testimony was essentially the only evidence presented in contrast to the government’s case as to that element.” Here, as in Hernandez and Samo, the defendant’s testimony was the principal evidence offered by the defense. As in those cases, Castillo-Basa’s “explanation cannot have been simply a collateral issue” because Castillo-Basa was the only witness the defense presented. 572 F.2d at 222 . In any case, as we have noted, the jury need not directly decide the veracity of a defendant’s testimony in the first trial for collateral estoppel to bar a subsequent perjury prosecution — it is enough that the jury decide an issue that is “sufficiently similar” to an issue in the prospective second prosecution and that the similar issues are “sufficiently material” in both instances. Id. at 220 .

Collateral estoppel applies when the jury resolves, in a manner adverse to the government, an issue that the government would be required to prove in order to obtain a perjury conviction at the second trial. The jury at Castillo-Basa’s trial necessarily decided the issue of whether Castillo-Basa was afforded a deportation hearing at which he was present. It also necessarily decided that his statements were not false. Defense counsel’s closing argument, in which counsel pointed out other circumstances tending to corroborate Castillo-Basa’s testimony that he did not *900 receive a hearing, was not itself evidence on which the jury could have based its decision. Moreover, the jury could not have credited defense counsel’s closing argument while simultaneously discrediting Castillo-Basa’s testimony. Accordingly, the analysis applied in Hernandez and Samo applies to this case as well. 6

The government relies on three assertions to support its argument that the issue of Castillo-Basa’s presence at a deportation hearing was not necessarily decided. All three are irrelevant and are based on fallacious reasoning. First, the government asserts that physical presence at a deportation hearing is not required to prove previous deportation. This assertion is correct but it is of no assistance to the government here. The government’s argument that the jury may have resolved the issue of previous deportation without passing on the question of Castillo-Basa’s presence at a hearing suffers from a fatal and insuperable flaw.

The government’s logic, which the dissent reiterates, is demonstrably faulty — the conclusion does not follow from its premise. When determining whether an issue was “necessarily decided” for purposes of collateral estoppel, we must start with the outcome of the previous proceeding; the answer may differ depending on whether the defendant was convicted or acquitted, and, here, it necessarily does. 7 *901 Whether the government could convict Castillo-Basa without proving that he had been physically present at a hearing, which it could, is a very different question from whether a jury could acquit him without deciding that “a deportation proceeding [did not] oceur[ ] as to [him].” Here, given the evidence and the arguments before it, the jury could not have acquitted Castillo-Basa without deciding that he had not been afforded a deportation hearing, 8 and thus that he had not been physically present at any such hearing. To suggest otherwise, as the government does here, is nonsensical: no rational jury could have decided that Castillo-Basa had been present at his deportation hearing yet that no such proceeding had been held. Because the jury acquitted Castillo-Basa on the ground that no deportation proceeding had occurred, it must necessarily have decided that he was not present at any such hearing. While the jury’s resolution of that issue alone is enough to satisfy the third component of the collateral estoppel test, it also follows inexorably that the jury decided that Castillo-Basa’s testimony — that he was not present at a deportation hearing— was not untruthful.

The government argues, second, that Castillo-Basa leveled at least eight different attacks on its evidence at the illegal reentry trial — such as “the absence of any tape recording and transcript of Castillo-Basa’s ... immigration hearing” or “the Government’s failure to produce records from the facility at which Castillo-Basa was held in custody to show who participated in immigration proceedings” — and that the jury may have acquitted Castillo-Basa based on these evidentiary gaps, without specifically determining the credibility of his testimony. Every one of Castillo-Basa’s attacks on the government’s case, however, simply sought to bolster the direct evidence offered by way of his testimony, and each such argument related to the same underlying question: whether Castillo-Basa was present at a deportation hearing. Moreover, even if the jury relied upon one or several of Castillo-Basa’s other assertions, and not his testimony, it would be impossible for the jury to have acquitted him without simultaneously finding that the government had failed to prove that he was present at a hearing, and that his testimony was not untruthful. In other words, Castillo-Basa necessarily prevailed on the issue of whether he was *902 present at a deportation hearing and thus on whether his testimony was truthful. Even given the other evidentiary gaps, the jury “was required to resolve the conflicting explanations” given by Castillo-Basa and the government regarding Castillo-Basa’s presence at a hearing. Hernandez, 572 F.2d at 222 . “Thus, [^’necessarily5 had to pass on the truthfulness of his account.” Id. This, as well as the jury’s finding that no hearing was conducted, is enough to invoke double jeopardy. See id.

Third, the government argues that “the jury may simply have found that the Government simply failed to meet its burden of proof that Castillo-Basa was deported.” The argument is not entirely clear. In any event, it fails no matter how we interpret it. If the government’s argument is, as it appears to be, that the jury may have found “only” a reasonable doubt as to Castillo-Basa’s presence at a deportation hearing, rather than having found to a certainty that he did not attend such a hearing, the argument is foreclosed by our precedent, as well as by the most elementary understanding of our system of criminal justice. All that is required to bar a second criminal trial on an issue that has been litigated and once decided is a determination that the government did not prevail on that issue the first time. An acquittal based on a finding that the government failed to prove its case beyond a reasonable doubt is sufficient to bar retrial on any material issue that was litigated and necessarily decided in the trial. See, e.g., Sarno, 596 F.2d at 408 . “Decided” in a criminal case always means only that the jury had a reasonable doubt. Were we now to conclude otherwise, it would not only fundamentally change our system of jurisprudence, but it would render every acquittal by a jury meaningless for purposes of double jeopardy: a jury can always be said to have concluded only that the prosecution failed to prove its case beyond a reasonable doubt. 9 If, rather than making the confounding argument that an acquittal on the ground of reasonable doubt does not count for purposes of double jeopardy, and thus, contrary to over 200 years of constitutional jurisprudence, that the Clause is of no practical significance whatsoever, the government’s argument is that the jury in Castillo-Basa’s illegal reentry case may have found that it failed to prove some other aspect of the illegal reentry charge, its argument fails because it is contrary to the facts and the law. A jury is presumed to have followed the instructions it is given and, as explained above, Castillo-Basa conceded every element of the criminal charge other than the issue of whether he was afforded, and was present at, a deportation hearing.

V

The government attempts to carve out of the Double Jeopardy Clause an exception that we have never recognized and never should. The government suggests that its perjury prosecution is *903 permissible because, at the first trial, “the United States lacked crucial evidence of Castillo-Basa’s untruthfulness” — to wit, the “previously unavailable” tape recording of the deportation hearing. We reject the government’s suggestion for two reasons. First, there is no basis whatsoever for an exception providing that the proffer of evidence that was in existence at the time of the first trial, but was not presented by the government at that trial, nullifies the protections afforded by the Fifth Amendment. Even in civil litigation, each party bears the consequences of its own inadequate litigation efforts and its presentation of insufficient evidence. See Moore’s Federal Practice §§ 132.02[2][d] & [e] (3d ed. 2005). 10 In the criminal context, the Fifth Amendment bolsters this principle, barring the government from treating any criminal trial as a “dry run.” Ashe, 397 U.S. at 447 , 90 S.Ct. 1189 . 11 Plainly the government could not prosecute a second time a defendant acquitted of murder because after the acquittal it discovered the murder weapon bearing the defendant’s fingerprints. The government’s argument in this case is deserving of no different treatment. The Fifth Amendment, as interpreted in Ashe v. Swenson, bars relitigation of an issue already decided, no matter how much additional evidence the government may wish to introduce at a second proceeding. See Harris, 404 U.S. at 56-57 , 92 S.Ct. 183 (reversing a state court decision that, despite collateral estoppel, permitted retrial because important inculpatory evidence had been, in the state court’s view, wrongly excluded); id. (holding that collateral estoppel applies “irrespective of whether the jury considered all relevant evidence, and irrespective of the good faith of the States in bringing successive prosecutions”). The government has at its disposal a wide selection of tools for gathering evidence to prosecute criminal defendants. Under the Double Jeopardy Clause, that privilege is accompanied by the concomitant responsibility to use the tools at the appropriate time. That time is before or during the first prosecution, not after-wards in an effort to justify a second attempt to obtain a conviction. 12

*904 Second, even under the exception the government proposes — permitting a second trial when it obtains evidence that was “previously unavailable” — its argument fails completely in this case. The “United States” did not come into possession of previously unavailable evidence after the first trial — the tape recording was in the government’s possession all along. The government failed to produce the tape before trial, even when the district court twice ordered it to do so. Were we to hold that the tape was “previously unavailable” although it was in the government’s possession during the illegal reentry trial, our decision would allow government incompetence (or even insidiousness) to trump the established protections of the Double Jeopardy Clause. This is not a sensible or acceptable interpretation of our prior decisions, or of our Constitution.

To hold that evidence is “unavailable” to the government when the government possesses it but fails to deliver it to the attorney handling a particular case would be wrong, both factually and legally. To do so would be to ignore the reality of the entity that criminal prosecutions pit individuals against, the entity from whose overreaching the Constitution seeks to protect its citizens. At the same time, it would vitiate the Constitution’s guarantee that an accused will not be compelled to defend himself more than once against allegations that have been resolved by a valid and final judgment. A defendant’s opposing party in a criminal proceeding is not the state’s attorney, but “the state” itself. Indeed, in an analogous context, we have held that evidence possessed by the FBI is in the custody of “the government” although the attorney for the government has not received it. See United States v. Bailleaux, 685 F.2d 1105, 1113-14 (9th Cir.1982) (Rule 16 discovery). We have also held that the government may violate the rule of Brady v. Maryland, 373 U.S. 83 , 83 S.Ct. 1194 , 10 L.Ed.2d 215 (1963), by failing to disclose exculpatory evidence that is within the possession of “the government” as a whole, even where the prosecutor himself does not possess it. See United States v. Blanco, 392 F.3d 382, 388 (9th Cir.2004). That the government itself, not the prosecutor, is the adversary party for purposes of the Double Jeopardy Clause, and thus that material in the possession of the government is not “unavailable,” is, under our system of criminal justice, even more apparent. 13

*905 VI

Our decision today does not create a per se bar against perjury prosecutions involving defendants who testify and are acquitted at trial. 14 The dissent exhibits its misapprehension of the doctrine of collateral estoppel when it asserts that “[a]ny material lie a defendant uses to get an acquittal ... will now be immune from prosecution for perjury because after all, the jurors must have believed it in order to acquit.” Dis. op. at 906 (emphasis removed). 15 Our ruling establishes no such automatic immunity. When an acquitting jury has not necessarily or actually decided the question of a defendant’s veracity, or a material issue sufficiently similar to one the prosecution must establish in the prospective second proceeding, collateral estoppel does not bar a subsequent trial for perjury. See, e.g., Richard, 892 F.2d at 762. 16 In reality, our ruling in Castillo-Basa’s favor merely serves to apply the well-established rule that where an issue actually is decided in reaching a valid and final judgment, collateral estoppel bars re-litigation of that issue. In broader terms, our decision today merely enforces the *906 Double Jeopardy Clause as this court has long interpreted it.

We reverse and remand with instructions to the district court to dismiss the perjury indictment against Castillo-Basa.

REVERSED.

. Two spellings of "Castillo-Basa” appear in the record. We use the spelling from Castillo-Basa's appellate briefs.

. As we will explain, see infra p. 898, to prove "deportation,” the government must show more than mere physical removal from the United States; it must also establish that a deportation proceeding occurred as to the defendant. This latter element was the one disputed at Castillo-Basa's illegal reentry trial.

. Castillo-Basa frames his argument on appeal as a claim based on "double jeopardy and collateral estoppel.” As the Supreme Court has explained, collateral estoppel in the criminal context — the protection against the relitigation of issues previously determined— is "an integral part of the protection against double jeopardy guaranteed by the Fifth and Fourteenth Amendments.” Harris v. Washington, 404 U.S. 55, 56 , 92 S.Ct. 183 , 30 L.Ed.2d 212 (1971) (per curiam). Accordingly, we use the terms “collateral estoppel” and "double jeopardy” interchangeably and deliberately, as well as most appropriately, bring "double jeopardy atmospherics into the equation.” See dis. op. at 909. To the extent that Castillo-Basa argues not that the perjury prosecution is barred by the concept of collateral estoppel, but that it violates the well-known Blockburger test, his argument fails. Perjury and illegal reentry each contains an element that the other offense does not. See Blockburger v. United States, 284 U.S. 299, 304 , 52 S.Ct. 180 , 76 L.Ed. 306 (1932). Our rejection of this claim is immaterial, however, because we reverse the district court on the basis of the collateral estoppel aspect of double jeopardy.

. The dissent would restrict the application of collateral estoppel to issues of “ultimate fact.” See dis. op. at 908. Such a restriction is completely without foundation. See Baker by Thomas v. Gen. Motors Corp., 522 U.S. 222 , 233 n. 5, 118 S.Ct. 657 , 139 L.Ed.2d 580 (1998) (explaining that collateral estoppel applies to "issue[s] of fact or law”); United States v. Richard, 892 F.2d 761, 762 (9th Cir.1989) (same), quoted in dis. op. at 908; see also Hernandez, 572 F.2d at 221 n. 3 (explaining that collateral estoppel applies to issues of "evidentiary fact,” "ultimate fact,” and "law”). Even were the doctrine cabined as the dissent would like, there is no support for the dissent's cramped and piecemeal definition of the term "ultimate fact.” See dis. op. at 908 (defining "ultimate fact” as "an essential element of the crime” or "the identity of the perpetrator of the offense of which the defendant is charged”). An “ultimate fact” is simply "[a] fact essential to the claim or the defense.” Black’s Law Dictionary 629 (8th ed. 2004). In this case, a critical issue that the government seeks to relitigate in the perjury prosecution — whether Castillo-Basa was afforded a deportation hearing at which he was present — clearly concerns facts that, as we will explain, were essential to Castillo-Basa’s illegal reentry defense.

. Indeed, the Assistant United States Attorney who tried the illegal reentry case and who handled the double jeopardy hearing below, speaking on behalf of the government, conceded in district court that the jury in the illegal reentry case "absolutely ... made a determination that [the government] did not prove beyond a reasonable doubt that [Castillo-Basa] had gone before an immigration judge. They definitely made that determination that the government's evidence did not *899 meet the burden of beyond a reasonable doubt on that single element.” Regrettably, the AUSA who made this truthful and accurate concession in the district court was replaced with another AUSA for purposes of this appeal. The government, through the new AUSA, completely reversed its position and argued on appeal that "Castillo-Basa cannot meet his burden to show that the jury’s not guilty verdict in his [illegal reentry] trial necessarily decided the question of whether he was present at the ... deportation hearing.” Although we do not reach the issue, we note that this troubling reversal of position may violate our established judicial estoppel doctrine. That doctrine precludes a party from taking a position in a legal proceeding that directly contradicts an earlier position it took in the same or an earlier proceeding. See Russell v. Rolfs, 893 F.2d 1033, 1037 (9th Cir.1990) (quoting Religious Tech. Ctr. v. Scott, 869 F.2d 1306, 1311 (9th Cir.1989) (Hall, Circuit Judge, dissenting)). The dissent points out, see dis. op. at 913 (citing United States v. Ogles, 440 F.3d 1095, 1099 (9th Cir.2006) (en banc)), that we are not bound by a party’s concession as to the meaning of a statute. Here, however, the disputed issue concerns a mixed question of law and fact regarding what the jury did and did not actually decide under the controlling law. See Russell, 893 F.2d at 1037-38 (applying judicial estoppel to a mixed question regarding the adequacy and availability of a state court remedy in that particular case).

. The decisions the dissent discusses — United States v. Williams, 341 U.S. 58 , 71 S.Ct. 595 , 95 L.Ed. 747 (1951), and Richard — hardly suggest a contrary result in this case. The subsequent perjury prosecutions in Williams and Richard did not violate collateral estoppel because tire facts at issue in the perjury prosecutions had not been necessarily decided in the earlier trials. In Hernandez and Samo, by contrast, as in this case, they had. The dissent appears to believe that because it can point to decisions in which subsequent perjury prosecutions were permitted, such prosecutions are permitted in all cases. That is obviously not the law. Nor do we rely on the equally incorrect sophism that because we can point to decisions in which subsequent perjury prosecutions were barred, they are always barred. The collateral estoppel inquiry is more subtle than that, requiring us to "examine the record of [the] prior proceeding," including the "pleadings, evidence, charge, and other relevant matter." Ashe, 397 U.S. at 444 , 90 S.Ct. 1189 (quoting Mayers & Yarbrough, supra, at 38-39) (internal quotation mark omitted).

The dissent’s O.J. Simpson hypothetical borders on the absurd. There is no reason to think that had the jury disbelieved Simpson’s testimony about not owning the type of shoes that left bloody footprints at the crime scene, "they certainly would have convicted.” Dis. op. at 911. The shoe testimony was hardly the "single rationally conceivable” basis on which the jury could have acquitted Simpson. Perhaps the dissent forgets that the glove didn’t fit (or even the unfortunate non-legal reasons on which the jury may have actually based its decision, including the unprecedented imbalance in legal skills between the Dream Team and the prosecution).

. The dissent’s assertion that "[i]f [an] issue is an element of the underlying offense or is an integral part of an element, then the issue was 'necessarily decided’ in the first trial,” dis. op. at 910, could not be more wrong. Consider a crime with two elements, A and B. A jury may acquit a defendant of this crime by determining that element A has not been satisfied, and pass no judgment whatsoever on element B. Element B need not be decided in order for the jury to acquit. This alone disproves the dissent’s theory. The dissent’s proposition holds true only when a jury convicts a defendant; to convict a defendant of our hypothetical crime, for example, the jury must necessarily determine that both elements A and B are satisfied. Furthermore, even if the dissent’s assertion were correct — which it is not — it would in no way follow, as a matter of logic, that when an issue is not an element of an offense, then that issue was not necessarily decided. See dis. op. at 909. We have often held that an issue was "necessarily decided” at a trial even when the issue was not an element of the offense in question. See, e.g., Samo, 596 F.2d at 408 (holding that the veracity of the defendant's testimony had been necessarily decided in a trial for bribery, of which veracity is not an element).

*901 There are two major problems with the dissent's assertion that an issue is "necessarily” decided if and only if it is an element of the offense. First, were the dissent's theory correct, the requirement in our case law that the previously decided issue be "material,” see Hernandez, 572 F.2d at 220 , would be entirely superfluous. Issues that are elements of the offense are always material. The inclusion of the materiality requirement in our collateral estoppel test therefore demonstrates that the collateral estoppel doctrine applies to issues other than elements of the offense. Second, were the collateral estoppel inquiry as simplistic as the dissent makes it out to be, requiring only an examination of the elements of the crime, we could conduct the inquiry simply by looking to the verdict and to the elements of the offense. There would be no need to follow the Supreme Court's instruction "to 'examine the record of a prior proceeding, taking into account the pleadings, evidence, charge, and other relevant matter, and conclude whether a rational jury could have grounded its verdict upon an issue other than that which the defendant seeks to foreclose from consideration.' " Ashe, 397 U.S. at 444 , 90 S.Ct. 1189 (quoting Mayers & Yarbrough, supra, at 38-39).

. In its brief, the government acknowledges that “to meet its burden of proof of a prior deportation, 'the government ... needs to prove that a deportation proceeding actually occurred with the end result of [the defendant] being deported.’ ” (alteration in original) (quoting United States v. Medina, 236 F.3d 1028, 1031 (9th Cir.2001)). As demonstrated earlier, whether such a hearing was held with respect to Castillo-Basa was the only disputed material issue in the case.

. For this reason, it is enough that the jury in Castillo-Basa’s first trial may have found only a reasonable doubt as to whether Castillo-Basa’s testimony was untruthful. The entire purpose of the perjury prosecution would be to relitigate this exact finding and to prove that there is no reasonable doubt that Castillo-Basa was untruthful. In other words, because the first jury was compelled to decide whether Castillo-Basa had had a deportation hearing, and because it decided that there was at least reasonable doubt as to the matter (regardless of how it reached that conclusion), it also necessarily decided that there was reasonable doubt about the government’s contention that Castillo-Basa was lying about his presence at a hearing — it cannot have remained agnostic on that question. This latter determination was identical to the one a new jury would be asked to resolve, only the opposite way, at a perjury trial. Such an attempt at relitigation would necessarily violate the Double Jeopardy Clause.

. See also Hernandez , a criminal case, in which we set forth with approval the pertinent Commentary from the Restatement of Law: "An issue on which relitigation is foreclosed may be one of evidentiary fact, of 'ultimate fact' (i.e., the application of law to fact), or of law.... Thus, for example, if the party against whom preclusion is sought did in fact litigate an issue of ultimate fact and suffered an adverse determination, new evidentiary facts may not be brought forward to obtain a different determination of the ultimate fact.” 572 F.2d at 221 n. 3 (quoting Restatement (Second) of Judgments § 68 cmt. c (Tent. Draft No. 1, Mar. 28, 1973)) (internal quotation marks omitted).

. Thus, there is, and could be, no parallel to Federal Rule of Civil Procedure 60 — which permits relief from a final judgment based on newly discovered evidence — in criminal cases.

. In Samo, we held that a subsequent perjury prosecution was barred because the defendant prevailed at all three steps of our traditional collateral estoppel test. In an introductory passage, we stated, as the dissent notes, dis. op. at 912, that "unless the subsequent perjury indictment is based upon evidence which was not available at the first trial, it would appear that the government would be merely trying to recover from its initial failure to convince the trier of fact of the falsity of defendant’s testimony at the first trial. Such a rehashing of evidence previously presented would clearly be prohibited by the collateral estoppel doctrine.” Sarno, 596 F.2d at 407 (citing Note, Perjury by Defendants: The Uses of Double Jeopardy and Collateral Estoppel, 74 Harv L. Rev. 752, 763 (1961)) (citation omitted). We subsequently, as the dissent also notes, firmly disavowed this dicta from Samo. See Richard, 892 F.2d at 762 . In any event, Samo, while affirming that a rehash of the evidence is prohibited by the Double Jeopardy Clause, did not determine that when the government does offer *904 evidence that was unavailable at the first trial, its introduction is sufficient to circumvent the collateral estoppel doctrine. Nor could it have done so under the Double Jeopardy Clause.

. The dissent’s citation to United States v. Dipp, 581 F.2d 1323 (9th Cir.1978), to suggest that the tape was "not available” is highly inaccurate and misleading. See dis. op. at 912. In Dipp , we affirmed a perjury conviction obtained subsequent to an earlier acquittal although, in the perjury prosecution, the government used a tape that it had possessed but had not produced during discovery for the first trial. Id. at 1324-25, 1328 . In rejecting Dipp’s collateral estoppel defense, however, we concluded only that the jury at Dipp’s first trial had not necessarily passed on the veracity of Dipp's testimony in acquitting him, or on any other issue "sufficiently similar” to invoke collateral estoppel's bar. Therefore, under our three-part test, collateral estoppel did not apply. Id. at 1326 . The use of the tape and its previous availability or non-availability was irrelevant to this part of our decision. There is no mention of the tape anywhere in the portion of the opinion that discusses collateral estoppel. The tape is first discussed in a subsequent section of the opinion that considers Dipp’s prosecutorial misconduct claim — a claim we rejected because Dipp failed to show that the government had intentionally withheld the tape in order to induce him to commit perjury- Id. at 1327 . There is, of course, no discussion in Dipp of whether the "government” and the "prosecutor” are different entities such that evidence newly available to a "prosecutor” before a second trial, though in the "government’s” possession all along, justifies disregarding the collateral estoppel doctrine and subjecting a defen *905 dant to further jeopardy. In short, Dipp's collateral estoppel defense failed because he could not meet our basic three-part test — the question of the tape was wholly irrelevant to our analysis of that issue and played no part in our decision to permit a second trial regarding an issue that had not been resolved in the first.

Dipp did not even remotely consider the question that the government says it helps us answer: when a jury has necessarily passed on the veracity of the defendant's testimony, does the government’s subsequent "discovery” of additional evidence that was in its possession during the first trial permit it to try the defendant for perjury notwithstanding collateral estoppel? Surely, had it done so, its answer would have been No, as it is here.

.We are not concerned, therefore, with the danger that our decision will encourage or embolden criminal defendants to perjure themselves at trial when they otherwise would not have done so. Most defendants, we think, will be concerned with the impact of their testimony only on the prosecution that immediately threatens their freedom, and not on potential future prosecutions for perjury should they be acquitted. In addition, it is difficult to predict before a trial is completed when collateral estoppel will bar relitigation of particular issues in that trial, making collateral estoppel a highly uncertain safeguard against a potential perjury prosecution. The far more pressing danger in cases such as this one is that if we accept the government's arguments, the prosecution, having failed to convict a criminal defendant of the charges for which it originally arrested him, will try once again by bringing similar charges in the form of a perjuiy case and thus will succeed in circumventing the Double Jeopardy Clause.

Moreover, the possibility of receiving a sentencing enhancement for obstruction of justice serves as a sufficient and immediate deterrent to perjury by criminal defendants. See U.S. Sentencing Guidelines Manual § 3C1.1 & cmt. n. 4(b) (2006); United States v. Dunnigan, 507 U.S. 87, 98 , 113 S.Ct. 1111 , 122 L.Ed.2d 445 (1993) (upholding application of a sentencing enhancement based on perjury at trial). Where the prospect of an enhanced sentence does not deter a particular defendant from committing perjury, we do think that the prospect of a separate perjury prosecution will.

. Indeed, it is the dissent that hints at a per se rule by quoting platitudes about how defendants "must testify truthfully or suffer the consequences.” Dis. op. at 906 (quoting United States v. Havens, 446 U.S. 620, 626 , 100 S.Ct. 1912 , 64 L.Ed.2d 559 (1980)). The dissent makes it sound as if collateral estoppel is never a bar to a subsequent perjuiy prosecution of an acquitted defendant, which is obviously not the law. See, e.g., Sarno, 596 F.2d at 408 ; Hernandez, 572 F.2d at 222 .

. In both Richard and Dipp , this court permitted perjury prosecutions subsequent to acquittals because the issues presented in the perjury trials had not necessarily been decided in the earlier criminal proceedings. The rule that under such circumstances a perjury trial may be held remains unchanged under our decision.