This paper presents a generalization and abstraction of the problem of extracting a witness from a prover in a special sound protocol into a combinatorial problem involving sequences of matroids and predicates. The authors propose a parametrized algorithm that solves this problem, offering a tight tradeoff between running time and extraction error. The algorithm allows optimization of parameters to minimize soundness error for interactive proofs or extraction time for proofs of knowledge. The paper introduces the concept of special soundness in the context of matroids, which captures a natural class of protocols. It defines a special sound protocol as one where a witness can be efficiently extracted from two accepting transcripts with a common first prover message and distinct verifier messages. The authors then generalize this notion to require that accepting transcripts form a tree, with independent verifier messages at each branching point. The paper presents a main theorem that provides an exact extraction theorem applicable to special sound protocols. The theorem states that if a protocol satisfies certain conditions, then an extraction algorithm exists that can efficiently extract a witness from a tree of accepting transcripts. The algorithm's running time is tightly bounded, and the distribution of the running time is concentrated, making it suitable for real-world applications. The paper also discusses the importance of considering the distribution of running time rather than just the expected running time in exact security analysis. This approach provides tighter bounds and more insight, simplifying the rigorous reuse of previous work. The authors analyze the general case where independence between accepting transcripts is required to extract a witness, which is typical in proofs over groups. They also discuss the application of their results to real-world protocols such as batch proofs of decryption and proofs of shuffles, which are used in electronic voting systems. The paper concludes by presenting a recursive algorithm for extracting accepting basis trees, which is shown to be efficient and effective in extracting witnesses from special sound protocols. The algorithm is parametrized to allow optimization of parameters for different applications, and it is shown to have a tight running time bound and concentrated distribution of running time. The paper also provides a detailed analysis of the algorithm's performance and its applicability to various types of protocols.This paper presents a generalization and abstraction of the problem of extracting a witness from a prover in a special sound protocol into a combinatorial problem involving sequences of matroids and predicates. The authors propose a parametrized algorithm that solves this problem, offering a tight tradeoff between running time and extraction error. The algorithm allows optimization of parameters to minimize soundness error for interactive proofs or extraction time for proofs of knowledge. The paper introduces the concept of special soundness in the context of matroids, which captures a natural class of protocols. It defines a special sound protocol as one where a witness can be efficiently extracted from two accepting transcripts with a common first prover message and distinct verifier messages. The authors then generalize this notion to require that accepting transcripts form a tree, with independent verifier messages at each branching point. The paper presents a main theorem that provides an exact extraction theorem applicable to special sound protocols. The theorem states that if a protocol satisfies certain conditions, then an extraction algorithm exists that can efficiently extract a witness from a tree of accepting transcripts. The algorithm's running time is tightly bounded, and the distribution of the running time is concentrated, making it suitable for real-world applications. The paper also discusses the importance of considering the distribution of running time rather than just the expected running time in exact security analysis. This approach provides tighter bounds and more insight, simplifying the rigorous reuse of previous work. The authors analyze the general case where independence between accepting transcripts is required to extract a witness, which is typical in proofs over groups. They also discuss the application of their results to real-world protocols such as batch proofs of decryption and proofs of shuffles, which are used in electronic voting systems. The paper concludes by presenting a recursive algorithm for extracting accepting basis trees, which is shown to be efficient and effective in extracting witnesses from special sound protocols. The algorithm is parametrized to allow optimization of parameters for different applications, and it is shown to have a tight running time bound and concentrated distribution of running time. The paper also provides a detailed analysis of the algorithm's performance and its applicability to various types of protocols.