The paper revisits the problem of extracting a witness from a prover in a special sound protocol, generalizing it into a combinatorial problem involving matroids and a predicate. The authors present a parametrized algorithm that optimizes the trade-off between the running time and the extraction error, allowing for the minimization of soundness error for interactive proofs or extraction time for proofs of knowledge. Unlike previous work, the analysis bounds the distribution of the running time, providing tighter bounds when applied recursively. The main contribution is an exact extraction theorem that applies directly to special sound protocols, capturing a natural class of protocols. The paper also discusses the construction of accepting basis extractors and provides a detailed analysis of their performance, including tail bounds for the number of queries made by the extractor. The recursive algorithm is described, which sequentially samples good candidates for roots of accepting bases and interrupts the execution if it takes too long, ensuring efficiency and effectiveness in extracting the witness.The paper revisits the problem of extracting a witness from a prover in a special sound protocol, generalizing it into a combinatorial problem involving matroids and a predicate. The authors present a parametrized algorithm that optimizes the trade-off between the running time and the extraction error, allowing for the minimization of soundness error for interactive proofs or extraction time for proofs of knowledge. Unlike previous work, the analysis bounds the distribution of the running time, providing tighter bounds when applied recursively. The main contribution is an exact extraction theorem that applies directly to special sound protocols, capturing a natural class of protocols. The paper also discusses the construction of accepting basis extractors and provides a detailed analysis of their performance, including tail bounds for the number of queries made by the extractor. The recursive algorithm is described, which sequentially samples good candidates for roots of accepting bases and interrupts the execution if it takes too long, ensuring efficiency and effectiveness in extracting the witness.